Запоминающее устройство Советский патент 1992 года по МПК G11C17/00 

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

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

Недостатком таких устройств является невозможность коррекции более сложных ошибок.

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

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

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

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

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

С

и

СО

о

онных разрядов 1, основной накопитель 4 контрольных разрядов 2 кодов Хемминга, дополнительный накопитель 10 дополни тельных контрольных разрядов 9 кодов Хем- микга, основные блоки 5 коррекции, дополнительные блоки 11 коррекции и матрицу коммутаторов 12, содержащую п строк и m столбцов.

Для объяснения работы устройства, введет понятия: одиночные ошибки, двойные горизонтальные, двойные вертикальные, тройные горизонтальные и вертикальные ошибки (фиг.2) На фиг. 2а имеется 5 одиночных ошибок, на фиг. 26 - одна одиночная и одна вертикальная двойная ошибки; на фиг, 20 - одна двойная горизонтальная и одна одиночная ошибки; на фиг. 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 коррекции.

На выходах (фиг.2б) того дополнительного блока 11 коррекции, на входах которого имеется двойная (вертикальная) ошибка, эта ошибка не будет откорректирована (так как обычный ход Хемминга только обнаруживает, но не корректирует такие ошибки). Тем не менее, на выходах 17 всех mn коммутаторов 12 образуется правильный nm-рзз- рядный код, так как через эти коммутаторы будут проходить выходные сигналы основных блоков 5 коррекции (ни один из этих блоков коррекции на своих m+k информационных входах не имеет двойной ошибки). Аналогичная картина будет иметь место при случае, показанном на фиг, 2г (несмотря на тройную вертикальную ошибку),

В случае, показанном на фиг. 2в (одна

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

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

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

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

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

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

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

На фиг.4 показана одна из возможных

схем узлов 6 синдрома и дешифраторов 7 основных блоков 5 коррекции для случая m - 8, к 5. Узел синдрома содержит четыре сумматора IS по модулю два (свертки) С1- С4, вырабатывающих 4 разряда синдрома в

5 соответствии с табл.1 классического кода Хемминга.

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

четности сумму по модулю два остальных входных сигналов данной свертки.

Пятый контрольный разряд КБ дополняет до четности сумму всех 12 разрядов хода Хемминга (Р1-Р7, К1-К4), поэтому выходной сигнал свертки 19 равен О (а выходной сигнал инвертора 27 равен 1), если в 13- разрядном коде (Р1-Р7, К1-К5) нет ошибок или есть четная ошибка. Выходной сигнал элемента ИЛИ 28 при отсутствии ошибок в 12-разрядном коде равен О (так как все выходные сигналы сверток 18 равны О) и равен 1, если в 12-разрядном коде есть какая-нибудь ошибка (так как один или несколько выходных сигналов сверток 18 рай- ны 1).

Таким образом, при четной ошибке (и в том числе при наиболее вероятной из них - двойной ошибке) оба выходных сигнала элемента И 29 равны 1 и поэтому на выходе этого элемента выходной сигнал 16 двойной ошибки будет равен 1. Так производится обнаружение двойной (четной) ошибки узлом 6 синдрома.

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

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

В этом случае на обоих входах соответствующего элемента 24 присутствуют два сигнала 1 (один из них поступает с выхода инвертора 25 при отсутствии двойной ошибки, а второй - сигнал 22 ошР| - с соответствующего выхода дешифратора 7). Выходной сигнал элемента И 24 подается на один из входов соответствующего сумматора 23 по модулю два, который и производит инвертирование соответствующего информационного сигнала PI информационного накопителя 3.

Аналогичным образом строятся узлы 8 коррекции дополнительных блоков 11 коррекции.

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

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

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

Таблица 1

Та бл и ца 2

It

5 2 8

Фиг. 1

X Х х

X

л

О)

X X

в)

X

X

Фиг. 2

X X

Фиг. J

L

l

/У

Ьбияа

j/.fftf

16

S

П

I T yJL

фиг. 5