Запоминающее устройство с исправлением ошибок Советский патент 1986 года по МПК G11C29/00 

Изобретение относится к ньпшсли- тельной технике и может быть использовано в запоминающих системах повышенной надежности, выполненных на функциональных узлах с большой и средней степенью интеграции.

Целью изобретения является повышение надежности устройства за счет исправления двукратных ошибок и обнаружения ошибок произвольной кратности .

На фиг.1 представлена структурная схема запоминающего устройства, на фиг.2 - один из возможных вариантов блока кодирования, на фиг.З - один из возможных вариантов блока декодирования.

Запоминакяцее устройство содеряшт блок 1 кодирования, вход 2 которого связан с выходом информационной магистрали, а выход подключен к накопителю 3, имеющему направляющий вход 4,, выход накопителя 3 подключен к первому входу 5 блока .6 коррекции и к блоку 7 декодирования, выход 8 блока 7 соединен о йлелентом ИЛИ-НЕ 9, выход которого связан с управляющим входом блока 6, с первым входом 10 первого сумматора 11 по модулю, два, с входами дервого элемента ИЛИ 12, второй выход

13блока 7 подключен к первому входу

14блока 15 сравнения, св язанного с вторым элементом ИЛИ 16, первый вход 17 второго элемента ИЛИ 16 соединен с выходом элемента ИЛИ 12, а второй вход 18 с первым выходом 19 блока 15., выход элемента ИЛИ 16 подключен к первому входу 20 счетчика 21, выход 22 которого связан с вторым входом 23 сумматора 11, а выход 24 - с первым входом 25 элемента И 26, имеющего индикаторньш выход 27, к второму входу 28 элемента И 26 подключен выход 19 блока 15, выход 22 счетчика 21 соединен с вторым входом 29 треть его элемента ИЛИ 30, а также с вторым дешифратором 31 ошибки, выход которого подключен к третьему входу 32

блока 6, выход 33 сумматора 11 связан с первым дешифратором 34 ошибки, вы- :ход которого соединен с вторым входом 35 блока бис цервым входом 36 элемента ИЛИ 30, выход элемента ИЛИ 30 соединен с входом блока 37 дополнительной памяти, выход которого подключен к входу второго сумматора 38 по модулю два, выход 39 которого связан с вторым входом 40 блока 15, второй выход 41 блока 15 соединен с вто

2265362

рым входом 42 счетчика 21, а также с управлякхцим входом 43 дешифратора 34 и с 5 правляющим входом 44 дешифратора ЗЬ, Выход 45 блока 6 подключен к

5 входу информационной магистрали. .

Иа фиг,2 представлен блок кодирования для кодирования 7 -разрядного слова в соответствии с таблицей кодирования для БЧХ-кода, исправлякщего

10 две ошибки. Блок состоит из двухвхо- довых сумматоров 46-62 по модулю два. На фиг.З приведен вариант построения блока 7 декодирования при п 15 разрядов ( длина слов, хранимых

.15 в накопителе 3). Блок состоит из двухвходовых сзл маторов 63-105 по модулю два, к входам которых подключены соответствующие разряды слова, удовлетворяющие таблице декодирова20 НИН для БЧХ-кода, исправляющего двукратные ошибки.

Блок 6 коррекции представляет собой регистр, входы которого связаны с выходами накопителя 3 и выходами

25 дешифраторов 31 и 34, имeюшз ми по W входов (2 ). Сумматоры 11 и 38 имеют П7 входов. Блок 37 дополни30

тельной памяти состоит из 2 m-разрядных быстродействующих регистров. Счетчик 21 имеет m входов и 2 состояний.

Б устройстве используется БЧХ-код длины п 2 -1 (т - целое положительное число), исправляющий две ошибки. Порождающая матрица G размерности krn (k n-2in) такого кода может быть представлена в виде

г - II Т7Р II

t - I EG К ,

где Е - единичная матрица размерности k k, G - подматрица размерности k«n-k, строки которой представляют собой остатки от деления единицы с нолями на порождаемый полином кода.

В соответствии с матрицей Q строят блок 1 кодирования.

Пусть V произвольное k-разрядное число V(V| 5 .. ., V , V,) . Произведение V на Q задает операцию кодирова- ния

V VQ-|1V,,.,,,V,V,C,C2.,,.,.,C,11,

где W - кодовое слово. С, - контрольные символы. Контрольньй символ 55 С

j равен сумме по модулю два содержимого тех разрядов исходного слова V,

которым соответствуют столбце подматрицы Q ,

единицы в 4 -м Для кода длиныц 15, исправлякяцего две ошибки, порождакяций полином л (х) равен д(х) или 111010001. Тогда строками подматрицы Q являются следующие остатки от деления

100000000000000 111010001

111010001

110100010

111010001 011100111

и 110011001

111010001

Разряды исходного слова 7654321

265364

Остаток под номером j (в кружочке) соответствует j -и строке подматрицы G Тогда порождающая матрица для рассматриваемого примера равна

5 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1 О О О О О 0111010007

О 1 О О О О 0011101006 10

О О 1 О ОО 0001110105

О О О 000011101А

0000100111001103

о о о о о1 0011100112

00 о о оо 1110100011

20

и, исходя из этого, может быть построена таблица кодирования.

Контрольные разряды 87654321

Изобретение относится к области вычислительной техники и может быть использовано в запоминающих системах повышенной надежности, выполненных на функциональных узлах с большой и средней степенью интеграции. Цель изобретения состоит в повышении надежности устройства за счет исправления двукратных ошибок и обнаружения ошибок произвольной кратности. Устройство содержит блок кодирования, накопитель, блок коррекции, блок декодирования, элемент ШШ-НЕ, сумматоры, элементы ИЛИ, блок сравнения, счетчик, элемент И, дешифраторы, дополнительньй блок памяти. В устройстве используется БЧХ-код, исправляющий двукратные .ошибки. 3 ил. (Л

В соответствии с таблицей построен блок кодирования на фиг.2, Значения контрольных разрядов равны сумме по модулю два содержимого подчеркнутых разрядов.

Для БЧХ-кода, исправлякщего две ошибки, проверочная матрица Н размерности 21П П задается в виде

Н

где столбцы a;() первых m строк представляют собой всевозможные ненулевые двоичныеm-мерные векторы (локаторы).

Вторая группа из (п строк строится таким образом, что каждый столбец является кубом по модулю неприводимого многочлена степени m вектора, записанного в этом столбце в первых м строках. Синдром 5 (вычисляется блоком 7) принятого вектора И определя

ется как .R (Т - операция транспонирования) и содержит 2т координат. Первые т координат дают сумму S, (выход 8) локаторов искаженных позиций, а вторые m координат синдрома дают сумму 5 (выход 13)

кубов локаторов искаженных позиций. Если и jf - локаторы искаженных разрядов, то

rs,,

(1)

где + означает операцию сложения по модулю два.

Декодирование заключается в определении |3 и у по известным 5, и Sj . Локаторы рассматриваются как ненуле- 55 вые элементы поля GF(2), представленные в виде двоичных многочленов степени, меньшей m , от корня ей некоторого неприводимого многочлена

$1226536«

стегГёни m. Это представление уста- да будет совпадать со степенью oi навливает такое соответствие между (нумератдш позиций начинается с 1). разрядами слова и локаторами, при Если п 15, то проверочная котором уменьшенный на 1 номер разря- матрица представляется в виде

15 14 13121110987 6 54 3 2 1

. 06 ; 0 oi oi . oi ( ы o oi c 0.:°

где cd - корень неприводимого многочлена X +х -f-1. Каждой из 15 позиций кода однозначно сопоставлен локатор из (16), Каждьй злемент

Представление элемента oi - в виде ления о; на неприводимый многочлен многочлена от «i равно остатку от де- ci + i-f1, а многочленам от ей однознач(2).

(°т od ) в этом поле является степенью сб и однозначно представляется в виде многочлена от об степени, меньшей 4 (табл.1).

Таблица 1

но соответствуют двоичные числа. Элементы матрицы (2) в нижней строке являются кубами элементов верхней стро-И

9 13 15 14 7 10 5 11 12 6 3 8 4 2 1

15 10 12 8 1 15 10 12

I 15 10 12 .8 1

или в двоичном представлении

111101011001000 011110101100100 001111010110010 111010110010001 111101111011110

101001010010100 110001100011000

10001 1000110001

Единицы в j -и строке матрицы Н указьшают, какие разряды принятого слова входят в j -е контрольное соотношение. Это позволяет построить таблицу декодирования

Разряды принятого слова 15 1А 13 12 11 10 9 8 7 6 5 ii 3 2 1

Синдром равен SrSj tSj BgBj значение В- равно сумме по модулю два содержимого соответствующих ему (подчеркнутых) разрядов. В соответствии с таблицей декодирования построен блок 7, представленный на фиг. 3.

Найдем 5 из первого уравнения системы (1) у S,+B и подставим во второе |i +(5,+|})У. Зададимся определенным значением |3 и вычислим У Если , то р - локатор ошибочного разряда, тогда 6, +р - локатор другого ошибочного разряда. Для вычисления величины У используется блок 37, в котором по адресу х (х -т -разрядное число) записана величина х по модулю неприводимого многочлена с ге- пени И1 , и m - разрядный сумматор 38, на выходе которого появляется вели-12265368

ки, находящихся в тех же столбцах. Например, для элементас ; :(«) Следовательно,

ai

I 15 10 12 .8 1

чина У. При ц 15 соответствие между адресами ячеек блока 37 и их со- 10 держимым имеет вид

Объем блока 37 равен 2 №-разрядных двоичных чисел. Пртадавая j3 по- следоватетгьные значения, начиная от 1 (на счетчике 21), вычисляя У и сравнивая У и 5,j , можно найти такое

г

значение р , при котором У S

Подлежащее записи (u-2tn)-разрядное слово поступает на блок 1, где кодируется и записьшается в накопитель 3.

Чтение слова инициируется подачей управляющего сигнала на вход 4. Считанное слово посчз пает в блоки 6 н 7, Если , считанное из накопителя cjio во не содержит ошибок, то 5, 0 и сигнал с выхода элемента ИЛИ-НЕ 9 разрешает вьщачу длова из блока 6. При наличии ошибок (S, 0) счетчик

21устанавливается в состояние 1, Код, содержащийся в счетчике 21 (локатор), складьгоается на сумматоре

11 с 5, . К блоку 37 производятся два обращения: по адресу р (выход

22счетчика 21л, равному состоянию Счетчика, и по адресу 5,+ fb (результат суммирования на су 1маторе 11, т.е. выход 33). На сумматоре 38 производится сложение по модулю два двух считанных из блока 37 слов р и (5,+р). Если результат суммирования У (выход 39) равен 5 (выход 13), то сигнал с выхода 41 блока 15 разрешает дешифрование кодов |} (выход 22) и 5, + |J (выход 33 сумматора 11), поступающих на дешифраторы 31 и 34 соответственно, производится коррекщ я, а счетчик 21 по входу 42 устанавливается в О. Подключение выходов дешифраторов 31 и 34 задает табл.1. Номерам выходов дешифраторов, записанных в четвертом столбце, соответствуют номера входов блока 6, записанные в первом столбце. Если блок 15 не зафиксирует ра 5енства кодов, то сигнал с выхода 19 через элемент ШЖ 16, поступая на вход 20 счетчика 21, устанавливает его в следуняцее состояние (увеличивает на 1), и перечисленные операции повторяются.

Если за и тактов равенство У 5 не будет зафиксировано, то по совпадению сигналов с выхода 19 блока 15 и выхода 24 счетчика 21 с выхода 27 элемента И 26 в центральное устройство управления поступает ущ) щий сигнал Ошибка, Это означает, что считанное из накопителя слово содержит ошибку кратности три и бол

П р и м е р. Пусть необходимо записать в накопитель слово

7654321 1011010

Блок 1 формирует значения контрольн разрядов в соответствии с таблицей кодирования

Cj 1+1+0 0 (сигнал на выходе сумматора 48 по модулю два равен единице сигнал на выходе сумматора 59 равен нулю)5

С„ 1+0+1 0 сигнал на .выходе элемента 49 равен единице, элемента 58 - нулю),

Cj 0+1+0 1 (в формировании С участвуют сумматоры 51 и 57). €4 1+1+1 1 (сумматоры 50 и 56), С5 0+1+1+1+0 1 (сумматоры 48, 50, 55 и 62),

Се 1+0+1+0+1 1 (сумматоры 47, 49 54 и 61),

€7 1+0+0+1+0 0 (суг- маторы 47, 48, 53 и 60),

Са 1+0+0 1 (сумматоры 46 и 52).

о в накопитель записывается слово

101101010111100 Пусть при чтении получено число 15 14 1342 11 10 9876543 21 1 00 1 О 1 0101110 0-0,

содержащее ошибки в 3 и 13 разрядах которое, поступает в блоки 6 и 7, числяющие значение синдрома в соответствии с таблицей декодирования:

В - 1+0+0+1+1+1+0+1 1 (сумматоры 63,, 6, 65, 66, 83, 84 и 97), 8 0+0+1+0+0+0+1+0 0 (сумматоры 64„ 67, 69, 85, 86 и 98), Bg-0+1+0+1+1+1+1+0 1 (сумматоры 70, 71, -72, 64, 87, 88 и 99),

0

+ 0+0+0+0+ 1 +1 + 0 (сумматоры 63, 73, 74, 75, 89Т 90 и 100), В 1+0+0+1+1+0+1+0+1+1+0+0 0 (сумматоры 64,63,66,76,77,78,91,92,93, 101 и 102),

В,. 1+0+1 +1 + (сумматоры 79, 80, 94, 81 и 103),

В2 1+0+1+0+1+1 0(сумматоры 63, 76, 77, 95 и 104),

Bj 1+0+1+1+1+0 0 (сумматоры 70, 72, 82, 96 и 105),

т„е. 5,1011, 5., 0000,

Единичный сигнал с выхода элемента 12 проходит на выход элемента ИЛИ 16 и устанавливает счетчик 21 в состояние (1)fj(. , Код 0001 с выхода 22 счетчика 21 через эле- генты ИЛИ 30 поступает на вход блока 37, откуда считывается код 0001

5

0

()„ Сумматор 11 по модулю два складьь- ает коды 0001 + 1011 1010. По адресу 1010 из блока 37 считьюа- ется код 1111, и таким образом на выходе 39 сумматора 38 появляется код 0001 + 1111 1110, которьй имеете с кодом 0000 (выход 13 блока 7) яоступает на блок 15, Так как эт:и коды не равны, то сигнал с выхода 19 блока 15 устанавливает счетчик 21 в состояние (2)(0010)2. Из блока 37 по адресу 0010 считывается код 1000, а по адресу 1011 + 0010 1001 (результат суммирования 5, и состояния счетчика 21 на сумматоре

5 11) код 1111,, которые складьгоаются па cyMi-iaTope 38 1000 + 1111 0111, Блок 15 снова определяет неравенство сравниваемых кодов. Счетчик 21 . з станав.пивается в состояние (3),

0.(0011)2 . По адресу 0011 из блока 37 считьшается код 1111, а по адресу 1011 + 0011 1000 - код 1010, т.е. на выходе 39 появится слово 1111 + f 1010 - 0101, не равное 5. Блок 15

5 зафиксщ ует равенство лишь тогда, когда состояние счетчика 21 будет равно (4), Действительно, из блока 37 по адресу 0100 считьшаетЪя код 1100, а по адресу 1011 + 0100

0 1111, вьщисленному на сумматоре 11, - код 1100. Тогда на выходе 39 сумматора 38 появ1-гтся код 0000 и блок 15 зафиксирует равенство. Сигнал с выхода 41 блока 15 устанавли5 вает счетчик 21 в исходйое состояние и разрешает дешифрование на дешифра- тсфах 31 и 34 кодов 0100 и 1111 соответственно. Но четвертому выходу де-

11

шифратора соответствует третий разряд блока 6, а пятнад{ ;атому - тринадцатый (табл.1), и, таким образом будет скорректировано содержание 3 13 разрядов считанного слова, что приведет к исправлению ошибок.

Таким образом, предлагаемое устройство исправляет двукратные ошибк и обнарз живает ошибки произвольной кратности. Пусть считанное из накопителя слово содержит ошибку кратно .ти 3 и более. Тогда 5 0 и

Рг

,

,.-,Ре 52Согласно предлагаемому способу исправления ошибок задают /J, , находят |ij по адресу 5, + Pi P2 + Ре «а- ходят (j + ,... t+l) и вычисляют (pj + ,. . ., + Ре) . Для того, чтобы ошибка осталась незамеченной, необходимо, чтобы , в этом случае кроме разряда с локатором р, был бы исправлен и разряд с локатором Рг + ,..о,+ е, т.е. исправление было бы неверным. Но У S, так как (р,+,...,+ г ),...,+ /5j ,. поэтому за И тактов не будет зафиксировано равенство У S .

Таким образом ошибки кратности три и более обнаруживается.

Формула изобретения

Запоминакнцее устройство с исправлением ошибок, содержащее блок кодирования, накопитель, блок декодирования, первый элемент ИЛИ, блок коррекции, первый дешифратор ошибки, элемент И, выход которого является индикаторным выходом устройства, информационным входом которого является вход блока кодирования, выход которого соединен с информационным входом накопителя, управляющий вход которого является управляющим входом устройства, выход накопителя подключен к входу блока декодирования и

12

первому- входу блока корре.пяции,второй вход которого соединен с выходом первого дешифратора ошибки, выА)Д блока корреляции является информадион 5 ным выходом устройства, первый выход блока декодирования подключен к входу первого элемента ИЛИ, отличающееся тем, что, с целью пЬвьш1е- ния надежности устройства за счет

0 исправления двукратных ошибок и обнаружения ошибок произвольной кратности, в него введены первый и второй сумматоры по модулю два, счетчик, второй и третий элементы ИЛИ, второй

5 дешифратор ошибки, блок сравнения блок Дополнительной памяти, элемент ИЛИ-НЕ, причем первьш выход блока декодрфования подключен к входу элемента ИЛИ-НЕ и первому входу первого

Q сумматора по модулю два, выход которого соединен с первым входом первого дешифратора ошибки и второго элемента ИЛИ, первый выход счетчика соединен с вторым входом первого сум5 матора по модулю два, вторым входом второго элемента ИЛИ и первым входом второго дешифратора ошибки, выход которого подключен к третьему входу блока коррекции, четвертый вход

которого соединен с выходом элемента ИЛИ-НЕ, второй выход блока декодирования соединен с первым входом блока сравнения, второй вход которого подключен к выходу второго сумматора по модулю два, вход которого соединен с выходом блока дополнительной памяти, вход которого подключен к выходу второго элемента ИЛИ, выход первого элемента ИЛИ соединен с первым входом третьего элемента ИЛИ, второй вход которого подключен к одному выходу блока сравнения и одному входу элемента И, другой выход блока сравнения соединен с первым входом счетчика и вторыми входами дешифраторов ошибки, выход третьего элемента ИЛИ подключен к второму входу счетчика, второй выход которого соединен с другим входом элемента И.

5

0

5

LL.,

ЦнГ se

Hi.

лГ

S3

Kf

..J

Составитель О.Кулаков Редактор А.Шандор Техред И.Попович КорректорС.Шекмар

Заказ 2140/52 Тираж 543Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская набо. До 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4