Запоминающее устройство с исправлением ошибок

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

«Ю «И (51) 4 С 11 С 29/00

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ М,.М АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ke.- -,-„„, 1

)f з ,.; 1 (21) 3804622/24-24 (22) 23. 10. 84 (46) 23,04.86. Бюл. № 15 (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Г.М.Дерикот, И.А.Дичка, В.И.Корнейчук, В.П.Палкин и В.Я.Юрчишин (53) 681.327(088.8) (56) Авторское свидетельство СССР

¹ 470866, кл. G 11 С 29/00, 1976.

Electronic engineering (Jr.Br.), 1979, V.5 1, № 617, с. 49, 52-53. (54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С ИСПРАВЛЕНИЕМ ОШИБОК (57) Изобретение относится к области вычислительной техники и может быть использовано в запоминающих системах повьппенной надежности, выполненных на функциональных узлах с большой и средней степенью интеграции. Цель изобретения состоит в повьппении надежности устройства за счет исправления двукратных ошибок и обнаружения ошибок произвольной кратности. Устройство содержит блок кодирования, накопитель, блок коррекции, блок декодирования, элемент

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

БЧХ-код, исправляющий двукратные ошибки. 3 ил.

1226536

G = jf EG / ния50

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

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

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

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

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

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 блока 6 и с первым входом 36 элемента ИЛИ 30, выход элемента ИЛИ

30 соединен с входом блока 37 дополнительной памяти, выход которого подключен к входу второго сумматора 38 по модулю два, выход 39 которого связан с вторым входом 40 блока 15, второй выход 41 блока 15 соединен с вто5 !

О .15

35 рым входом 42 счетчика 2 1, а также с управляющим входом 43 дешифратора 34 и с управляющим входом 44 дешифратора 31. Выход 45 блока 6 подключен к входу информационной магистрали.

На фиг,2 представлен блок кодирования для кодирования 7-разрядного слова в соответствии с таблицей кодирования для БЧХ-кода„ исправляющего дне ошибки. Блок состоит из двухнходовых сумматоров 46-62 по модулюдва.

На фиг.3 приведен вариант построения блока 7 декодирования при п =15 разрядов (0- длина слов, хранимых в накопителе 3). Блок состоит из

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

Блок 6 коррекции представляет собой регистр, входы которого связаны с выходами накопителя 3 и выходами дешифраторов 31 и 34, имеющими по tn входов (2 -1=h). Сумматоры 11 и 38 имеют m входов. Блок 37 дополнительной памяти состоит из 2 щ -разрядных быстродействующих регистров.

l7l

Счетчик 21 имеет е входов и 2 состояний.

Б устройстве используется БЧХ-код длины 0 =2 -1 (ш — целое положительное число), исправляющий две ошибки.

Порождающая матрица 6 размерности

k n (k:и-2m) такого кода может быть представлена в виде где Š— единичная матрица размерности krak, С - подматрица размерности

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

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

Пусть произвольное k --разрядное число i7=(),...,Ч,, Vf). Произведение 1 на G задает операцию кодировагде Ф вЂ” кодовое слово, С; — контрольные символы. Контрольный символ

С; равен сумме по модулю два содержимого тех разрядов исходного слова, которым соответствуют единицы в 1 -м

1 столбце подматрицы G . Для кода дли"

1226536 ны и =15, исправляющего две ошибки, порождающий полином g (х) равен ф(х)=х +х +х +х +1 или 11l010001 ° (Тогда строками подматрицы являются следующие остатки от деления

Я чо оооио

111010001

Q2

О3

1 1 1010001

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

8 7 6 5 4 3 2

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

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

Р Х 5 °

P y =5» где столбцы а; (=1: n) первых rn строк представляют собой всевозможные ненулевые двоичные 1в -мерные векторы (локаторы).

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

®

07 оооооооооооаоо >

111010001

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

7 6 5 4 3 2 1

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

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

1000000111010007

0100000011101006

00100000011 i 0105

0001000000111014

0 0 0 0 1 0 О 1 1 1 0 0 1 1 0 3

0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 2

0 0 0 0 0 0 f 11010001 1

20 и, исходя из этого, может быть построена таблица кодирования. ется как ST=Í Rг (Т вЂ” операция транспонирования) и содержит 2rn координат.

Первые п1 координат дают сумму S (вы46 ход 8) локаторов искаженных позиций, а вторые е координат синдрома дают сумму 5< (выход 13) кубов локаторов искаженных позиций.

Если Р и — локаторы искаженных

45 разРядов, то где + означает операцию сложения

Ь и по модулю два.

Декодирование заключается в определении Р и Ip по известным 6 и 5

Локаторы рассматриваются как ненуле55 вые элементы поля GF(2 ), представленные в виде двоичных многочленов степени, меньшей п1, от корня ас некоторого неприводимого многочлена

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

1 3 <и H

Д (2) где — корень неприводимого много4 члена х +х +1. Каждой из 15 позиций кода однозначно сопоставлен локатор из доля ГР (16). Каждый элемент (к af ) в этом поле является степенью с6 и однозначно представляется в виде многочлена от о степени, меньшей 4 (табл.1).

Таблица 1

Позиция Иногочлены от ж Локаторы кода (элементы поля) в. предст. дес.предст.

0001

1 000

0011

1011

0101

0111

1101 с =о +1 6 зщ2

0 =0 < 0 +!

Ы,=К 1 б

10 ф " = 0(, + of. Ф 1 аи аб 2

12 э р+

of, =++Ê +1

g 4 of. 4j

+(5

14

1001

1 ления g" на неприводимый многочлен +ot+1, а многочленам oT of однознач4

Представление элемента of, в виде многочлена от of равно остатку от де3 1226536 d стегени e . .Это представление уста- да будет совпадать со степенью е навливает такое соответствие между (нумерация позиций начинается с 1) . разрядами слова и локаторами, при Если и =2 -1=15, то проверочная

Ф котором уменьшенный на 1 номер разря- матрица представляется в виде

1226536

10

Си«драм старшие разряды в в, — в, — в

8< в, вз

81 — в< младшие разряды но соответствуют двоичные числа. Элементы матрицы (2) в нижней строке яв1 ляются кубами элементов верхней строН . 9 13 15 14 7 10 5

15 10 12 8 1 15 10 или в двоичном представлении

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0

0 1 1 1 1 0 1 0 1 1 0 0 1 0 0

1 1 1 0 1 0 1 1 001 000 1

11110111101» 10

100011000110001

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

Разряды принятого слова

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

<индРОм Равен Я 1 . S В В В В В В В значение В равно сумме по модулю два содержймого соответствующих ему (подчеркнутых) разрядов. В соответствии с таблицей декодирования построен блок 7, представленный на фиг. 3.

Найдем из первого уравнения системы (1) 2I =S +В и подставим во второе р9 +(51 +p) =У. Зададимся определенным значением Р и вычислим У.

Если У=52, то t! — локатор ошибочноГо разряда, тогда 5, +P — локатор другого ошибочного разряда. Для вычисления величины У используется блок 37, в котором по адресу х (х -rn --разрядное число) записана величина х 2 по модулю неприводимого многочлена с<репени в, и rn — разрядный сумматор 38, на выходе которого появляется велиl5

55 ки, находящихся в тех же столбцах.

Например, для эле1!ентав :(к ) =-о

6, и з 18

<5 — Следовательно, 12 6 3 8 4 2 1

8 1 15 10 12.8 1 чина У. При 11 =15 соответствие между адресами ячеек блока 37 и их содержимым имеет вид х 0 1 . 2 3 4 9 6 7 8 9 10 1 1 12 13 14 15

Объем блока 37 равен ?" 1« -разрядHbIx дВОичных чисел Пр1щавая р ПО следовательные значения, начиная от

1 (на счетчике 21), вычисляя У и сравнивая У и Q, можно найти такое значение Р при котором У = Р .

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

Чтение слова инициируется подачей управляющего сигнала на вход 4. Считанное слово поступает в блоки 6 и 7.

Если. считанное из накопителя слово не содержит ошибок, то 5, =-0 и сигнал с выхода элемента ИЛИ-HF. 9 разрешает выдачу слова из блока б.

При наличии ошибок (5,3 0) счетчик

21 устанавливается в состояние "1".

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

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

22 счетчика 21, равному состоянию счетчика, и по адресу О, + P (результат суммирования на сумматоре

11, т.е. выход 33). На сумматоре

38 производится сложение по модулю два двух считанных из блока 37 слов и (о,+P) . Если результат суммирования У (выход 39) равен 52 (выход 13), то сигнал с выхода 41 блока 15 разрешает дешифрование кодов р (выход 22) и 5, + 13 (выход 33 сумматора 11), поступающих на дешифраторы 31 и 34 соответственно, производится коррекция, а счетчик 21 по входу 42 устанавливается в "0" ° Подключение выходов дешифраторов 31 и

34 задает табл.1. Номерам выходов дешифраторов, записанных в четвертом столбце, соответствуют номера входов блока 6, записанные в первом столбце, Если блок 15 не зафиксиру!

226536 ет равенства кодов, то сигнал с Bbl хода 19 через элемент ИЛИ 16, посгупая на вход 20 счетчика 21, устанавливает его в следующее состояние (увеличивает на 1), и перечисленные операции повторяются.

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

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

765432

10110!О

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

С =I+1+0=0 (сигнал на выходе сумма1 тора 48 по модулю два равен единице„ сигнал на выходе сумматора 59 равен нулю), С„=1+0+1=0 (сигнал на выходе элеменL та 49 равен единице, элемента 58— нулю), С =0+1+0=1 (в формировании С> участ 5 вуют сумматоры 51 и 5?)

С,«= i+1+1=1 (сумматоры 50 и 56), С =О+1+1+1+О =! (сумматоры 48, 50, 55 и 62), Сь =1+0+1+0+1=1 (сумматоры 47, 49, 54 и 61), С =1+О+0+1+0=0 (сумматоры 47, 48, 53 и 60), С =1+0+0=1 (сумматоры 46 и 52).

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

Пусть при чтении получено число «,"

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

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

В:=1+0+0+1+1+1+0+1=1 (сумматоры 63„

64, 65, 66, 83, 84 и 97), В =-0+0+1+0+0+0+1+0=0 (сумматоры 64„

67, 69, 85, 86 и 98), В =-0+1+0+1+1+1+1+0=1 (сумматоры 70, 71, 72, 64, 87, 88 и 99), В =1+О+О+О+О+ 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+1+0=0 (сумматоры 79, 80, 94, 81 и 103), В. = 1+0+1+0+1+1=0 (сумматоры 63, 76, 77, 95 и 104), В =1+0+1+1+1+0=0 (сумматоры 70, 72, 82„ 96 и l05) т. е. 5 =10!1, 5, =0000.

} дипичный сигнал с выхода элемента ИЛИ 12 проходит на выход элемента ИЛИ 16 и устанавливает счетчик 21 в состояние (1)„„= (0001) . Код 0001 с,ыхода ?2 счетчика 21 через элементы ИЛИ 30 поступает на вход блока 37, откуда считывается код 0001 (1 =.=1), Сумматор 11 по модулю два складывает коды 0001 + 1011 = 1010.

По адресу 1010 из блока 37 считывается код 1111, и таким образом на выходе 39 сумматора 38 появляется код 0001 + 1111 = 1 l10, который вместе с кодом 0000 (выход 13 блока 7} гоступает на блок 15. Так как эти коды не равны, то сигнал с выхода 19 блок;а 15 устанавливает счетчик

21 в состсяние (2)„=-(0010) . Из блока 37 по адресу 0010 считывается код 1000, а по адресу 1011 + 0010 = !

001 (результат суммирования G,è состояния счетчика 21 на сумматоре

1 I) код 1111, которые складываются на суюлаторе 38 1000 + 1111 = 0111.

Блок 15 снова определяет неравенство сравниваемых кодов. Счетчик 21 устанавливается в состояние (3), =

=(0011) . По адресу 0011 из блока 37 считывается код 1111, а по адресу

1011 + 0011 == 1000 — код 1010, т.е, па выходе 39 появится слово 1111 +

1010 -- 0101, не равное В . Блок 15 зафиксирует равенство лишь тогда, когда состояние счетчика 21 будет равно (4),д--0100. Действительно, из блока 37 по адресу 0100 считывается код 1100, а по адресу 1011 + 0100 — 1111, вычисленному на сумматоре

1 I — код !100. Тогда на выходе 39 сумматора 38 появится код 0000 и блок 15 зафиксирует равенство. Сигнал с вь«хода 4 блока 15 устанавливает счетчик 21 в исходйое состояние и разрешает дешифрование на дешифраторах 31 и 34 кодов 0100 и 1111 соответственно. Но четвертому выходу де122653б

15

Согласно предлагаемому способу исправления ошибок задают Р, находят

J3 по адресу G, + P, = Pz+,..., 3, нахОдят (P +, ° ° °,+ P ) и Вычисляют

У=/,+(P +,...,+ Е) . Для того, чтобы ошибка осталась незамеченной 1 необходимо, чтобы У= 5 в этом случае кроме разряда с локатором P„ был бы исправлен и разряд с локатором

p2+,...,+ p т.е. исправление было бы неверным, Но У &, так как (P2+ ° ° ° + Pg ) 1 P2, + +P тому за h тактов не будет зафиксировано равенство У= б

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

25

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

Запоминающее устройство с исправлением ошибок, содержащее блок кодирования, накопитель, блок декодирования, первый элемент ИЛИ, блок коррекции, первый дешифратор ошибки, элемент И, выход которого является индикаторным выходом устройства, информационным входом которого являетФ ся вход блока кодирования, выход которого соединен с информационным входом накопителя, управляющий вход которого является управляющим входом устройства, выход накопителя подключен к входу блока декодирования и шифратора соответствует третий разряд блока б, а пятнад11атому — тринадцатый (табл.1), и, таким образом,будет скорректировано содержание 3 и

13 разрядов считанного слова, что 5 приведет к исправлению ошибок.

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

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

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

1226536 и

1226536

Филд

Составитель О.Кулаков

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

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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