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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (я)ю G 11 С 17/00

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) 1

ОПИСАНИЕ ИЗОБРЕТЕНИ

К ПАТЕ НТУ (21) 4881343/24 (22) 09,08.90

У (46) 07.03.93, Бюл. М 9 (71) Научно-исследовательский институт вычислительных комплексов (72) С. В. Бирюков, Е. А. Брик, В. Н. Владимиров, А. А. Крупский и С. А, Назаров (73) С. В. Бирюков, Е. А. Брик, В. Н. Владимиров, А. А. Крупский и С, А. Назаров (56) Дублирование в запоминающих устройствах // Вопросы радиоэлектроники. Сер.

Э ВТ. Вып. 10, 1990. (54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к автоматике и вычислительной технике, в частности к постоянным и полупостоянным запоминающим устройствам с коррекцией ошибок.

Целью изобретения является повышение

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

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

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

1 контрольных разрядов кода Хемминга, относящихся к соответствующему столбцу информационного накопителя; первую группу блоков коррекции, каждый из которых име- Я ет (m + k) входов, соединенных с выходами :) соответствующей строки информационного с накопителя и одноименной строки первого накопителя контрольных разрядов, m откорректированных информационных выходов и. один выход обнаружения двойной ошибки 4д данной строки информационного и первого контрольного накопителя; вторую группу, блоков коррекции, каждый из которых име. ет (n + I) входов, соединенных с выходами соответствующего столбца информацион1801227 ного накопителя и одновременного столбца второго контрольного накопителя, и откор ректированных информационных выходов и выход обнаружения двойной ошибки данного столбца информационного и второго контрольного накопителя; матрицу коммутаторов, содержащую mn двухвходовых коммутато.ров, первые информационные входы m коммутаторов каждой из и строк матрицы коммутаторов соединены с m выходами соответствующего блока коррекции первой группы, вторые информационные входы и коммутаторов каждого из m столбцов матрицы коммутаторов соединены с и выходами соответствующего блока коррекции второй группы, управляющие входы m коммутаторов каждой из и строк матрицы коммутаторов соединены между собой и с выходом обнаружения двойной ошибки соответствующего блока коррекции первой группы; запоминающее устройство содержит также матрицу двухвходовых элементов и и матрицу двухвходовых сумматоров по модулю два, . Существенным отличием изобретения является наличие этих двух матриц: матрицы, содержащей пгп двухвходовых элементов И, и матрицы, содержащей nm двухвходовых сумматоров по модулю два, причем первые входы m двухвходовых элементов И каждой из и строк матрицы двухвходовых элементов И соединены между собой и с выходом двойной ошибки.соответствующего блока коррекции первой группы блоков коррекции, вторые входы и двухвходовых элементов И каждого из m столбцов матрицы двухвходовых элементов И соединены между собой и с выходом двойной ошибки соответствующего блока коррекции второй группы блоков коррекции, выход каждого из m двухвходовых элементов И l-й (l = 1, n) строки матрицы двухвходовых элементов И соединен с первым входом соответствующего сумматора по модулю два 1-й строки матрицы двухвходовых сумматоров по модулю два, выход каждого из m двухвходовых коммутаторов i-й (i = 1, и} строки матрицы двухвходовых коммутаторов соединен со вторым входом соответствующего сумматора по модулю два I-й строки матрицы двухвходовых сумматоров по модулю два, выходы двухвходовых сумматоров по модулю два являются выходами устройства.

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

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

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

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

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

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

2 имеется kn контрольных разрядов кода

Хемминга, На фиг. 1 n = 8, k = 5, так как для коррекции одиночных ошибок и обнаружения двойной ошибки в восьми информационных разрядах в коде Хемминга требуется

5 контрольных разрядов, т. е. в каждой i-й (i = 1, n) строке первой контрольной матрицы

2 содержится по k = 5 контрольных разрядов кода Хемминга, относящихся к i-й строке информационного накопителя 1.

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

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

Коммутаторы 9 составляют матрицу ком45. мутаторов (на фиг, 1 границы этой матрицы не показаны для упрощения рисунка), содержащую и строк и m столбцов, т. е, общее количество коммутаторов 9 равно mn, Для облегчения объяснения работы пред50 лагаемого устройства введем такие термины, как одиночные ошибки, двойные горизонтальные и двойные вертикальные ошибки, Эти термины поясняются на фиг, 2, На фиг, 2, а показан случай с тремя одиночными ошибками; на фиг.

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

"угла"), принадлежащей одновременно обе1801227 им двойным ошибкам — вертикальной и горизонтальной; на фиг. 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 и соответственно к определенному блоку коррекции 6 группы 4, соединены между собой и с выходом 8 двойной ошибки данного блока коррекции 6, Поэтому при отсутствии двойной ошибки в данной строке накопителей 1 и 2 на выходы 11 коммутаторов 9 данной строки пройдут выходные сигналы данного блока .коррекции 6.

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

Рассмотрим теперь показанные на фиг.

2, б, в случаи с двойными ошибками.

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

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

9 этой строки и поэтому через эти коммутаторы данный байт пройдет не с выходом 7 .. этого блока коррекции, а с выходов 7 блоков

20 ком коррекции 6 группы 4 (как в случае, показанном на фиг. 2, а). "Левая" ошибка будет, откорректирована соответствующим

50

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

После прохождения откорректированного кода через коммутаторы 9 дальнейшее

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

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

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

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

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

1801227

15

25

35

45

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

Информационными выходами блока коррекции 6 являются восемь откорректированных сигналов 7 данного байта.

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

"1" при нечетной ошибке (в том числе при одиночной) и равен "0" при отсутствии ошибок или при четной ошибке (в том числе при двойной).

Четыре инвертора 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 (код О 1

1 О). Поэтому, если в разряде Р6 произойдет ошибка, то на выходах сверток 21 образуется синдром, показанный в табл, 2 (напомним, что при отсутствии ошибок, т . е. при четности количества единиц на входах каждой из сверток 21) выходные сигналы всех четырех сверток 21 равны нулю), Поэтому все четыре входных сигнала 25 элемента 24 разряда Р6 будут равны "1" и на выходе 26 этого элемента образуется сигнал "ошР6", сигнализирующий об ошибке в разряде Р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, в котором имеется ошибка, т. е, того разряда Pl, для которого соответствующий сигнал 26 "ошРГ на выходе дешифратора 19 данного блока коррекции 6 равен единице. В этом случае на обоих входах соответствующего элемента И 28 присутствует два сигнала "1": один из них поступает с выхода инвертора 29 при отсутствии двойной ошибки, а второй сигнал 26

"ош Рà — с соответствующего выходного дешифратора 19. Выходной сигнал элемента И

28, равный "1", подается на один из входов соответствующего двухвходового сумматора 27, который и производит инвертирование (коррекцию) соответствующего информационного сигнала Pi информационной матрицы 1.

Аналогичным образом строятся узлы коррекции 20 блоков коррекции 6 второй группы 5 блоков коррекции.

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

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

1801227

Таблица1

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

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

1801227

1801227

1801227

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

Техред М. Моргентал

Корректор E.Папп.Редактор

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

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

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

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