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

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

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

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

строке информационного накопителя, второй накопитель контрольных разрядов, в каждом из m столбцов которого хранится по I контрольных разрядов кода Хемминга, относящихся к соответствующему столбцу информационного накопителя; первую группу блоков коррекции, каждый из которых имеет (m + k) входов, соединенных с выходами соответствующей строки информационного накопителя и одноименной строки первого накопителя контрольных разрядов, m откорректированных информационных выходов и. один выход обнаружения двойной ошибки данной строки информационного и первого контрольного накопителя; вторую группу ; блоков коррекции, каждый из которых имеет (п + I) входов, соединенных с выходами соответствующего столбца информацией00

о

К) К)

-ч

00

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

. Существенным отличием изобретения является наличие этих двух матриц: матрицы, содержащей nm двухвходовых элементов И, и матрицы, содержащей nm. двухвходовых сумматоров по модулю два, причем первые входы m двухвходовых элементов И каждой из п строк матрицы двухвходовых элементов 1/1 соединены между собой и с выходом двойной ошибки соответствующего блока коррекции первой группы блоков коррекции, вторые входы п двухвходовых элементов И каждого из m столбцов матрицы двухвходовых элементов И соединены между, собой и с выходом двойной ошибки соответствующего блока коррекции второй группы блоков коррекции, выход каждого из m двухвходовых элементов И 1-й (I I, п) строки матрицы двухвходовых элементов И соединен с первым входом соответствующего сумматора по модулю два 1-й строки матрицы двухвходовых сумматоров по модулю два, выход каждого из m двухвходовых коммутаторов i-й (i 1, п) строки матрицы двухвходовых коммутаторов соединен со вторым входом соответствующего сумматора по модулю два 1-й строки матрицы двухвходовых сумматоров по модулю два, выходы двухвходовых сумматоров по модулю два являются выходами устройства.

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

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

возможных схем узла синдрома и дешифратора; на фиг. 5 - один из вариантов узла коррекции.

Предлагаемое устройство состоит из .информационного 1, первого контрольного

5 2 и второго контрольного 3 накопителей запоминающих элементов, первой группы 4 и второй группы 5 блоков 6 коррекции, двухвходовых коммутаторов 9, управляемых ин- .верторов (сумматоров по модулю два) 12 и

0 двухвходовых элементов И 13.

В информационном накопителе 1 имеется mn запоминающих элементов (например, одноразрядных микросхем памяти): п строк и m столбцов. На фиг. 1 п 8, m. 8 (8

5 информационных байтов по 8 разрядов в каждом). В первом контрольном накопителе 2 имеется kn контрольных разрядов кода Хемминга. На фиг. 1 п 8, k 5, так как для коррекции одиночных ошибок и обнаруже0 ния двойной ошибки в восьми информационных разрядах в коде Хемминга требуется 5 контрольных разрядов, т. е. в каждой 1-й (I 1, п) строке первой контрольной матрицы 2 содержится по к 5 контрольных разрядов

5 кода .Хемминга, относящихся к i-й строке информационного накопителя 1.

Аналогичным образом во втором контрольном накопителе 3 хранятся ml контрольных разрядов кода Хемминга : по I 5

0 контрольных разрядов в каждом из m столбцов - для коррекции одиночных и обнаружения двойных ошибок в соответствующем столбце накопителей 1 и 3.

Коммутаторы 9 составляют матрицу ком5. мутаторов (на фиг, 1 границы этой матрицы не показаны для упрощения рисунка), содержа- щую п строк и m столбцов, т. е, общее количество коммутаторов 9 равно mn.

Для облегчения объяснения работы пред0 лагаемого устройства введем такие термины, как одиночные ошибки, двойные горизонтальные и двойные вертикальные ошибки. Эти термины поясняются на фиг. 2. На фиг. 2, а показан случай с тремя одиночными ошибками; на фиг.

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

Предлагаемое устройство работает следующим образом. При отсутствии ошибок, а также при наличии только одиночных ошибок (фиг. 2, а) на выходах 7 блоков коррекции 6 первой группы 4 блоков коррекции образуются nm (на фиг. 1 8 байтов по 8 разрядов), откорректированных информационных сигналов, так как каждый из блоков коррекции 6 группы 4, на входах которых имеется одиночная ошибка, исправит ее. По этой же причине на выходах 7 блоков коррекции 6 группы 5 также образуется mn таких же откорректированных выходных сигналов (т. е, 64 выхода блоков коррекции 6 группы 4 совпадают с 64 выходами блоков коррекции 6 группы 5). Управляющие входы 10 коммутаторов 9, относящихся к определенной строке накопителей 1 и 2 и соответственно к определенному блоку коррекции б группы 4, соединены между собой и с выходом 8 двойной ошибки данного блока коррекции 6. Поэтому при отсутствии двойной ошибки в данной строке накопителей 1 и 2 на выходы 11 коммутаторов 9 данной строки пройдут выходные сигналы данного блока .коррекции 6..

Откорректированные сигналы 11с выходов mn коммутаторов 9 без изменений пройдут через сумматоры 12 по модулю два (управляемые инверторы). Это произойдет потому, что выходные сигналы 16 всех элементов И 13 будут равны О (так как двой- ные ошибки отсутствуют, и все сигналы двойных ошибок 8 блоков коррекции 6 будут равны О). Таким образом, на выходы 17 управляемых инверторов 12, являющихся выходами устройства, пройдет откорректированный nm-разрядный код (п строк по m столбцов) из блоков коррекции 6 группы 4.

Рассмотрим теперь показанные на фиг. 2, б, в случаи с двойными ошибками.

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

При горизонтальной двойной ошибке (фиг. 2, в) эта ошибка не будет откорректирована тем блоком коррекции 6 группы 4, на входах которого имеется эта ошибка (так как обычный код Хемминга,только обнаруживает, но не корректирует такие ошибки). Однако сигнал 8 двойной ошибки этого блока коррекции переключит все m коммутаторов 9 этой строки и поэтому через эти коммутаторы данный байт пройдет не с выходом 7 этого блока коррекции, а с выходов 7 блоков

коррекции 6 группы 5 (для которых двойная горизонтальная ошибка является двумя простыми одиночными и поэтому корректируемыми ошибками).

5После прохождения откорректированного кода через коммутаторы 9 дальнейшее его прохождение через сумматоры по модулю два 12, как и в предыдущих случаях, произойдет без изменений, так как ни в 0 одном из двухвходовых элементов И 13 на обоих входах 14 и 15 одновременно не образуются сигналы 1. Такое событие может произойти лишь в случае, если данный бит принадлежит одновременно двум двойным

5 ошибкам - одной горизонтальной и одной вертикальной,

Именно такой случай показан на фиг. 2, г. В этом случае нижняя ошибка будет откорректирована соответствующим бло0 ком коррекции 6 группы 4 (как в случае, показанном на фиг. 2, а). Левая ошибка будет, откорректирована соответствующим блоком коррекции в группе 5 (как в случае, показанном на фиг. 2, в). Что касается ошиб5 ки, лежащей в- вершине угла, то эта ошибка блоками коррекции 6 откорректирована не будет, так как она входит в состав обеих двойных ошибок - как вертикальной, так и горизонтальной. Коррекция этой ошибки бу0. дет произведена тем элементом И 13 и сумматором по модулю два 12, которые расположены на пересечении того столбца матриц 1 и 3 и этой строки матриц 1 и 2, в которых имеются двойные ошибки.

5 При случае, показанном на фиг. 2, д, устройство будет работать неправильно: вертикальная двойная ошибка будет откорректирована как в случае, показанном на фиг. 2, б, горизонтальная двойная ошибка 0 как в случае, показанном на фиг. 2, в. Однако устройством, а точнее тем элементом И 13 и тем сумматором 12, которые находятся на пересечении обеих двойных ошибок, будет произведено инвертирование (т. е. бу5 дет внесена ошибка) исправного разряда, находящегося на этом пересечении. Следует однако учитывать малую вероятность таких двух двойных ошибок, при которых неисправными оказываются сразу четыре

0 запоминающих элемента.

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

5 блока коррекции 6, который состоит из узла синдрома 18, дешифратора 19 и узла коррекции 20. Узел синдрома 18 вырабатывает сигнал двойной ошибки 8 и синдром - двоичный код разряда, в котором имеется одиночная ошибка. Дешифратор 19 дешифрирует

этот код, а узел коррекции 20 производит инвертирование (т. е. коррекцию) дефектного разряда. Входными сигналами блока 6 коррекции, например, для группы 4, показанной на фиг. 1, являются восемь информационных сигналов Р1-Р8 данного байта и пять контрольных разрядов К1-К5 данной строки первой контрольного накопителя 2. Информационными выходами блока коррекции 6 являются восемь откорректированных сигналов 7 данного байта.

На фиг. 4 показана одна из возможных схем узла синдрома 18 и дешифратора 19 блоков коррекции 6 первой группы 4. Узел синдрома содержит четыре сумматора 21 по модулю два (свертки) С1-С4, вырабатывающих четыре разряда синдрома в соответствии с табл. 1 классического кода Хемминга, В каждом из четырех столбцов табл. 1 указаны те разряды Р и К, которые подаются на входы данной свертки С,

На входы каждой из сверток 21 подается только один контрольный рязрез К, который при исправном устройстве дополняет до четности сумму по модулю два остальных входных сигналов данной свертки. Пятый контрольный разряд К5 дополняет до четно-, сти сумму всех 12-ти разрядов кода Хемминга (Р1-Р8, К1-К4), Все эти 13 разрядов суммируются по модулю два сверткой 22. Поэтому выходной сигнал свертки 22 равен 1 при нечетной ошибке (в том числе при одиночной) и равен О при отсутствии ошибок или при четной ошибке (в том числе при двойной).

Четыре инвертора 23 и инвертор 31 вырабатывают сигналы, инверсные выходным сигналам сверток 21 и 22.

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

Четырехвходовой элемент ИЛ И 30 складывает (по ИЛИ) выходные сигналы всех четырех сверток 21, вырабатывающих синдром. Поэтому при любой ошибке в 13 разрядах Р и К на выходе элемента ИЛИ 30 будет сигнал 1. Если при этом выходной сигнал свертки 22 равен О (а выходной

сигнал инвертора 31 равен 1), то это означает, что имеется двойная (точнее, четная) ошибка и выходной сигнал 8 двухвходового элемента И 32 будет равен 1 . Таким образом, если выходной сигнал двойной ошибки

8 на выходе узла синдрома 18 равен 1, то это означает наличие двойной ошибки в контролируемом 13-разрядном коде.

Аналогичным образом строятся узлы синдрома 18 и дешифратора 19 блоков коррекции 6 второй группы 5 (при этом номера байтов и разрядов меняются местами).

На фиг. 5 показана одна из возможных схем узла коррекции 20 блоков коррекции 6 первой группы 4 блоков коррекции. Схема

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

инвертирование (коррекция) того выходного информационного сигнала Pi информационной матрицы 1, в котором имеется ошибка, т. е, того разряда PI, для которого соответствующий сигнал 26 ошРГ на выходе дешифратора 19 данного блока коррекции 6 равен единице. В этом случае на обоих входах соответствующего элемента И 28 присутствует два сигнала один из них поступает с выхода инвертора 29 при отсутствии двойной ошибки, а второй сигнал 26 ошР1 - с соответствующего выходного дешифратора 19. Выходной сигнал элемента И 28, равный 1, подается на один из входов соответствующего двухвходового сумматора 27, который и производит инвертирование (коррекцию) соответствующего информационного сигнала Pi информационной матрицы 1,

Аналогичным образом строятся узлы

коррекции 20 блоков коррекции 6 второй группы 5 блоков коррекции.

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

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

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

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

Изобретение относится к автоматике и вычислительной технике, в частности к постоянным и полупостоянным запоминающим устройствам с коррекцией ошибок. Целью изобретения является повышение надежности устройства. Это достигается за счет введения дополнительного накопителя контрольных разрядов кодов Хемминга, коммутаторов, образующих матрицу коммутаторов, дополнительных блоков коррекции, матрицы элементов И и сумматоров по модулю два. Совместная работа блока коррекции строк матрицы и блока коррекции столбцов матрицы позволяет корректировать любое количество одиночных ошибок в строках и столбцах матрицы, любое количество двойных ошиб.ок в столбцах матрицы, одну двойную ошибку в строке. Для коррекции двух ошибок - двойной ошибки в строке и двойной ошибки в столбце, имеющих совпадающую ошибку, в устройстве имеется матрица двухвходовых элементов И и матрица управляемых инверторов (двухвходо- вые сумматоры по модулю два). 5 ил.

Таблица

Таблица2

О

§ Н . . .

V - 0

X X

3 глф

LZZIOQI

Фиг. 4