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

 

Изобретение относится к запоминающим устройствам, в частности к полупостоянным ЗУ с коррекцией ошибок. Целью изобретения является повышение надежности за счет корректирующей способности устройства. Цель достигается за счет введения дополнительного накопителя контрольных разрядов кодов Хемминга, дополнительных блоков коррекции, коммутаторов , образующих матрицу. Сущность изобретения заключается в использовании ортогонального кодирования матрицы с запоминающими элементами путем Использования кодовых словХемминга отдельно для каждой строки и для каждого столбца матрицы и использовании комМутаторОЁ, осуществляющих передачу строк матрицы, откорректированных узлами коррекции строк или столбцов матрицы. 2 табл., 5 ил.

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

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

РЕСПУБЛИК

> SU 1753491 А1 (я)5 6 11 С .17/00 .

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

» » 1 -- Ъ. э|, П

ОПИСАНИЕ ИЗОБРЕТЕНИЯ !",, „"„,,:,, К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к запоминающим устройствам, в частности к полупосто янным ЗУ с коррекцией ошибок. Целью

Изобретечие относится к запоминающим устройствам (ЗУ), в частности к полупостоянным ЗУ с коррекцией ошибок.

Известны ЗУ с исправлением (коррекцией) одиНочных и обнаружением двойных ошибок в кодовых словах, использующих код Хемминга.

Недостатком таких устройств является невозможность коррекции более сложных ошибок, Известно также запоминающее устройство, способное корректировать более сложные ошибки и в том числе двойную ошибку в одной из строк или в одном из столбцов матрицы, образованной запоминак1щими элементами накопителя. Более сложные ошибки (например, две двойные ошибки в разных строках матрицы накопи-. теля) данным устройством не корректируются.

1 (21) 4834155/24 (22) 27.04.90 (46) 07.08.92. Бюл, N. 29 (71) Научно-исследовательский институт вычислительных комплексов (72) С.В.Бирюков, Е.А.Брик и А,А.Крупский (56) Карцев M.À, Арифметика цифровых ма.шин. Наука, 1969, с. 99-106.

Дублирование в запоминающих устройствах. Вопросы радиоэлектроники, сер.

ЭВТ, вып, 10, 1990. изобретения является повышение йадежности за счет корректирующей способности устройства, Цель достигается за счет введения дополнительного наКопителя контрольных разрядов кодов Хемминга, дополнительных блоков коррекции, коммутаторов, образующих матрицу. Сущность изобретения заключается в использовании ортогонального кодированйя матрицы с запоминающими элементами путем йсйользования кодовых словХемминга отдельно для каждой строки и для каждого столбца матрицы и использовании коммутаторов, осуществляющих передачу строк матрицы, откорректированных узлами коррекции . строк или столбцов матрицы, 2 табл„5 ил.

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

Поставленная цель достигается при помощи увеличения информационной избыточности путем введения"дополнительного накопителя контрольных=разрядов кодов

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

На фиг.1 показана схема заявленного устройства; на фиг.2 и 3 места ошибок в накопителях устройства (места ошибок показаны знаком х); на фиг,4 — схема узлов синдрома и дешифраторов; на фиг.5 — схема узлов коррекции.

ЗУ (фиг.1) содержит информационный накопитель 3, содержащей mxn информаци1753491

10 одна одиночная и одна вертикальная двой- 15 ная ошибки; на фиг, 2в — одна двойная гори-

35 онных разрядов 1, основной накопитель 4 контрольных разрядов 2 кодов Хемминга, дополнительный накопитель 10 дополнительных контрольных разрядов 9 кодов Хемминга, основные блоки 5 коррекции, дополнительные блоки 11 коррекции и матрицу коммутаторов 12, содержащую и строк и m столбцов, Для объяснения работы устройства, введет понятия: одиночные ошибки, двой- ные.горизонтальные, двойные вертикальные, тройные горизонтальные и вертикальные ошибки (фиг.2), На фиг. 2а имеется.5 одиночных ошибок, на фиг. 26— зонтальная и одна одиночная ошибки; на фиг. 2г — одна тройная вертикальная и одна одиночная ошибки; на фиг. 2д — тройная горизонтальная ошибка; на фиг, 2е — две двойные ошибки — горизонтальная и вертикальная, расположенные углом.

Устройство работает следующим образом.

При отсутствии ошибок, а также при наличии только одиночных ошибок на информационных выходах 13 основных блоков 5 коррекции образуются nxm (на фиг.1- 8 байтов по 8 разрядов) откорректированных информационных сигналов, так как каждый из основных блоков 5 коррекции, на входах которого имеется одиночная ошибка, исправит ее. По этой же причине на информационных выходах 14 дополнительных блоков 11 коррекции также образуется.nxm таких же откорректированных выходных . сигналов (т.е, сигналы 13 и 15 совпадают).

Управляющие входы 15 коммутаторов

12, относящихся к определенной строке накопителей 3 и 4 и, соответственно, к определенному основному блоку 5 коррекции, соединены с выходом 16 двойной ошибки данного основного блока 5 коррекции. Поэ тому при отсутствии двойной ошибки в данНоА.строке накопителей 3 и 4 на выходы 17 коммутаторов 12 данной стройки пройдут выходные сигналы данного основного блока

5 коррекции.

На выходах (фиг.26) того дополнительного блока 11 коррекции, на входах которого имеется двойная (вертикальная) ошибка, эта ошибка не будет откорректирована (так как обычный ход Хемминга только обнаруживает, но не корректирует такие ошибки).

Тем не менее, на выходах 17 всех mn коммутаторов 12 образуется правильный nm-разрядный код, так как через эти коммутаторы будут проходить выходные сигналы основных блоков 5 коррекции (ни один из этих блоков коррекции на своих m+k информаци20

25 онных входах не имеет двойной ошибки).

Аналогичная картина будет иметь место при случае, показанном на фиг, 2г (несмотря на тройную вертикальную ошибку), В случае, показанном на фиг, 2в (одна одиночная ошибка в 7-м байте и одна гори- . зонтальная двойная в 4-м байте), одиночная ошибка будет. откорректирована как в предыдущих случаях (фиг. 2а, б, г), Что касается двойной горизонтальной ошибки, то она тоже окажется откорректированной, так как на выходе 16 основного блока коррекции

4-го байта образуется сигнал двойной ошибки, который переключает коммутаторы 12

4-го байта и через эти коммутаторы пройдут все выходные сигналы основного блока 5 коррекции (как во всех остальных nm-m коммутаторах 12), а выходные сигналы 14 дополнительных блоков 11 коррекции, относящиеся к 4-му байту (т,е. по одному сигналу

4-со разряда от всех-восьми дополнительных блоков 11 коррекции), При случаях, показанных на фиг, 2д и е, коррекция ошибок не произойдет, т,е; устройство будет работать неверно (кроме того, при тройной горизонтальной ошибке не произойдет и обнаружение ошибки, а к трем имеющимся ошибкам добавится четвертая ошибка, выработанная основным блоком коррекции байта, в котором произошла тройная ошибка, которую основной блок коррекции примет за одиночную). 8 случае, показанном на фиг, 2е, две ошибки на выходах 17 устройства окажутся откорректиро- ванными (нижняя ошибка — основным блоком коррекции, а правая ошибка — дополнительным блоком коррекции), а третья ошибка, находящаяся в вершине угла, останется неоткорректированной, так как она расположена на пересечении двух двойных ошибок — горизонтальной и вертикальной.

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

На фиг.4 показана одна из возможных схем узлов 6 синдрома и дешифраторов 7 основных блоков 5 коррекции для случая

m = 8, k = 5. Узел синдрома содержит четыре сумматора 18 по модулю два (свертки) С1С4, вырабатывающих 4 разряда синдрома в соответствии с табл.1 классического кода

Хемминга.

На входах каждой из сверток 18 имеется только один контрольный разряд К, который при исправном устройстве дополняет до

1753491 четности сумму по модулю два остальных . емой узлом 8 коррекции, является (при условходных сигналов данной свертки, вии отсутствия двойной ошибки, инвертироПятый контрольный разряд К5дополня- вание того выходного информационного ет до четности сумму всех 12 разрядов хода сигнала Pi информационного накопителя 3, Хемминга (Р1-Р7, К1-К4), поэтому выходной 5 в котором имеется ошибка (т.е. т ого разряда сигнал свертки 19 равен "0" (а выходной Рь для которого имеется соответствующий сигнал инвертора 27 равен "1"), если в 13- сигнал 22 ошРь на выходе дешифратора 7 разрядном .коде (Р1-Р7, К1-К5) нет ошибок данного основного блока 5 коррекции. или есть четная ошибка. Выходной сигнал элемента ИЛИ 28 при отсутствии ошибок в 10 В этом случае на обоих входах соответ12-разрядном коде равен "0" (так как все ствующего элемента 24 присутствуют два выходные сигналы сверток 18 равны "0") и сигнала "1" (один из них поступает с выхода равен "1", если в 12-разрядном коде есть инвертора25 при отсутствиидвойнойошибкэкая-нибудь ошибка (так как один или не- ки, а второй — сигнал 22 ошР— с соответстсколько выходных сигналов сверток 18 рав- 15 вующего выхода дешифратора 7). Выходной ны "1").. сигнал элемента И 24 подается на один из

Таким образом, при четной ошибке(и в входов соответствующего сумматора 23 по том числе при наиболее вероятной из них — модулю два, который и производит инвертидвойной ошибке) оба выходных сигнала эле- рование соответствующего информационмента И 29 равны "1" и поэтому нэ выходе 20 ного сигнала Р информационного этого элемента выходной сигнал 16 двойной накопителя 3. ошибки будет равен "1". Так производится " Аналогичным образом строятся узлы 8 обнаружение двойной (четной) ошибки уз- коррекции дополнительных блоков 11 корлом 6 синдрома, P66K KQMMNN.

Дешифратор 7 состоит из четырех ин- 25 верторов 26, инвертирующих выходные сиг- Ф о р м у л а и з о б р е т е н и я налы сверток 18, восьми (по числу разрядов

Р1-Р8) 4-входоаых (no числу кодовых столб- Запоминающее устройство, содержэцов в табл.3) элементов И 20. На выходе щее информационный накопитель, основкаждого из элементов 20 вырабатывается 30 ной накопитель контрольных разрядов сигнал ошибки соответствующего информэ- кодов Хемминга, основные блоки коррекционного разряда Р, так кэк 4 входа 21 каж- ции, первые входы каждого из которых соедого из элементов 20 соединены с выходами динены с соответствующими выходами . сверток 18 и инверторов 26 в соответствии . информационного накопителя, а вторые с табл.3. Например, входы элемента 20, вы- 35 входы каждого из основных блоков коррекрабатывающего сигнал ошибки разряда Р6, ции соединены с соответствующими выхосоединены с выходами сверток С2 и СЗ и дами основного накопителя контрольных выходами двух инаерторов 26, инвертирую- рязрядов кодов Хемминга, о т л и ч а ю щ ещих выходные сигналы сверток С1 и С4. еся тем, что, с целью повышения надежноТакое соединение определяется строчкой 40 стиустройства, оно содержитдополнительР6 в табл,1 (код 0110). Поэтому, если в раэ- ный накопитель контрольных разрядов ряде Рб произойдет ошибка, То на выходах кодов Хемминга, коммутаторы, образующие сверток 18 образуется код синдрома 0110, матрицу, дополнительные блоки коррекции, показанный в табл.2 (при отсутствии оши- первые входы каждого из которых соединебок, т.е. при четности количества единиц на 45 ны с соответствующими выходами инфорвходах каждой из сверток 18, выходные сиг- мационного накопителя, а. вторые входы налы всех 4 сверток 18 равны нулю). Поэто- каждого из дополнительных блоков коррекму все 4 входных сигнала элемента 20 ции соединены с соответствующими выхоразряда Р6 будут равны "1" и на выходе 22 дами дополнительного накопителя этого элемента образуется сигнал "1", сиг- 50 контрольных разрядов кодов Хемминга, иннализирующий об ошибке в разряде Рб. формационные. выходы каждого из дополнительных блоков коррекции соединены с

Аналогичным образом строятся узлы первыми информационными входами комсиндрома 6 и дешифраторы 7 дополнитель- мутаторов соответствующего столбца матных блоков 11 коррекции. На фиг.5 покэзэнаэ5 рицы, вторые информационные входы одна из возможных схем узла 8 коррекции. коммутаторов каждой строки матрицы соеосновных блоков 5коррекции. Схема содер- динены с информационными выходами сожит восемь двухвходовых сумматоров 22 по ответствующего основного блока модулю два, восемь 2-аходовых элементов коррекции, выход обнаружения двойной

И 24 и один инвертор 25. Задачей, выполня- ошибки каждого основного блока коррек1753491

Таблица1

Таблица2 ции соединен с управляющими входами коммутаторов соответствующей строки мат-, рицы, выходы коммутаторов матрицы являются выходами устройства.

175349) 1753491 1753491

1753491

Составитель E.ÁðèK

Техред М,Моргентэл

Редактор Л,Гратилло

Корректор А,Ворович

Производственно-издательский комбинат "Патент" г, Ужгоро, л.Г жгород, ул. агарина, 101

Заказ 2770 Тираж Подписное

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

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