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

На фиг. 1-5 и в тексте приняты следующие обозначения: 1 - информационный накопитель; 2 - основной накопитель контрольных разрядов кодов Хемминга; 3 - дополнительный накопитель контрольных разрядов кодов Хемминга; 4 - основные блоки коррекции; 5 - дополнительные блоки коррекции; б -информационные выходы основных блоков коррекции; 7 - информационные выходы дополнительных блоков коррекции; 8- сигнал двойной ошибки; 9-двухвходовые коммутаторы; 10--управляющие входы коммутаторов; 11 - выходы коммутаторов; 12 - двухвходовые элементы сравнения:.13 - первый элемент ИЛИ; 14 - второй элемент ИЛИ; 15 - инвертор; 16 - двухвходовой элемент И; 17 - сигнал ошибок блоков коррекции или тройной ошибки; 18 - узел синдрома; 19 - дешифратор; 20 - узел коррекции; 21 - сумматоры по модулю два (свертки) узла сиид- рома; 22 - свертка полного кода Хемминга; 23 - инверторы; 24 - четырехвходовые элементы И; 25 - входы элементов И 24; 26 - выходы дешифраторов 19; 27 - сумматоры по модулю два; 28 -двухвходовые элементы И; 29 -инвертор; 30- четырехвходовойэлемент ИЛИ; 31 - инвертор; 32 -двухвходовой элемент И,

Предлагаемое запоминающее устройство состоит из информационного накопи- теля 1, первого контрольного 2 и гторого контрольного 3 накопителей, основных блоков коррекции 4, дополнительных блоков коррекции 5, коммутаторов. 9, элементов сравнения 12, первого элемента ИЛИ 13, второго элемента ИЛИ 14, инвертора 15 и двухвходового элемента И 16,

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

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

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

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

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

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

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

Поскольку для случая, показанного на фиг.2а, выходные сигналы 6 и 7 блоков коррекции 4 и 5 совпадают, то на выходах nm элементов сравнения 12, производящих по- разрядное побитное сравнение информационных выходов 6 и 7 обеих групп блоков коррекции образуются сигналы О. Следовательно выходной сигнал второго элемента ИЛИ 14 также будет равен О, Выходной сигнал первого элемента ИЛИ 13 также равен О, т.к. двойных ошибок нет и выходные

сигналы 8 всех n + m блоков коррекции 4 и 5, соединенные со входами первого элемента ИЛИ 13, также будут равны О. На выходе инвертора 15 образуется сигнал 1, а на выходе 17 элемента И 16 будет уровень О, сигнализирующий этим о исправности блоков коррекции А и 5. Если при ситуации, показанной на фиг,2а, произойдет сбой или отказ в каком-нибудь из блоков коррекции 4 и 5, то на выходе одного (или нескольких) элемента сравнения 12 и соответственно на выходе второго элемента ИЛИ 14, образуется сигнал 1, который пройдет через двух- входовой элемент И 16, что и будет означать неисправность блоков коррекции.

Сигнал 17 будет равен 1 еще в двух случаях - при тройной горизонтальной или тройной вертикальной ошибке (фиг.26,в). Тройная ошибка воспринимается соответствующим блоком коррекции как одиночная, в результате чего этот блок коррекции к имеющимся трем ошибкам добавляет четвертую. Следовательно выходные сигналы 6 и 7 основных и дополнительных блоков коррекции в четырех разрядах (из 64) при тройной ошибке будут отличаться друг от друга. Поэтому на-выходах четырех элементов 12 (т.е. на четырех входах второго элемент элемента ИЛИ 14) образуются сигналы 1, и на выходах элементов 14 и 16 также образуются сигналы 1. Сигнал 1 на выходе 17 элемента И 16 таким образом позволяет обнаружить тройную ошибку, сигнализируя при горизонтальной тройной ошибке о неправильной работе устройства (при вертикальной тройной ошибке устройство работает правильно, т.к. через соответствующие коммутаторы 9 все ошибочные разряды пройдут откорректированными - от основных блоков коррекции 4.

Одиночные ошибки в случаях, показанных на фиг.2б и в, будут откорректированны обычным путем (как при фиг.2а).

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

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

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

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

При любой двойной ошибке на выходе элемента ИЛИ 14 образуется сигнал 1. т.к. на выходах двух элементов сравнения 12 образуются сигналы 1. Для того, чтобы

этот сигнал не прошел через элемент И 16, в устройстве предусмотрен первый n + m- входовой элемент ИЛИ 13, входы которого соединены с выходами 8 двойных ошибок всех n + m блоков коррекции. Таким обра5 зом, при любых двойных ошибках (вертикальных или горизонтальных) на выходе первого элемента ИЛИ 13 образуется сигнал 1, который через инвертор 15 блокирует прохождение через элемент И 16

0 сигнала 1 с выхода второго элемента ИЛИ 14. Другими словами, при двойных ошибках предотвращается ложный сигнал тревоги 17 (при двойных ошибках этот сигнал тревоги был бы ложным, т.к. двойные ошибки кор5 ректируются),

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

5 вершине угла, то эта ошибка откорректирована не будет, т.к. она входит в состав обеих двойных ошибок - как вертикальной, так и горизонтальной.

Несмотря на этот недостаток предло0 женное устройство обладает значительно более высокой надежностью, чем устройство-прототип. Это происходит как благодаря полному контролю исправности блоков коррекции 4 и 5 (которые являются довольно

5 сложными узлами), так и благодаря обнаружению тройных ошибок.

На фиг.З показана структурная схема основного блока коррекции 4, который состоит из узла синдрома 18, дешифратора 19

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

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

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

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

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

. числу разрядов Р1-Р8)четырехвходовых(по числу кодовых столбцов в табл.1) элементов и 24. На выходе каждого из элементов 24 вырабатывается сигнал 26 ошибки соответ- ствующего информационного разряда Р, т.к. 4 входа 25 каждого из элементов 24

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

входных сигнала 25 элемента 24 разряда Рб будут равны 1 и на выходе 26 этого элемента образуется сигнал 1, сигнализирующий об ошибке в разряде 6.

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

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

. На фиг.5 показана одна из возможных схем узла коррекции 20 основных блоков коррекции 4, Схема содержит восемь двух- входовых сумматоров по модулю два 27, восемь двухвходовых элементов И 28 и один инвертор 29. Задачей, выполняемой узлом коррекции 20, является (при условии отсутствия двойной ошибки) инвертирование (коррекция) того выходного информационного сигнала Р информационного накопителя 1, в котором имеется ошибка, (т.е. того разряда Р, для которого соответствующий сигнал 26 otuPi на выходе дешифратора 19 данного основного блока 4 коррекции равен единице) В этом случае на обоих входах соответствующего элемента И 28.присутствуют два сигнала один из них поступает с выхода инвертора 29 при отсутствии двойной ошибки, а второй - сигнал 26 ouiPj - с соответствующего выхода дешифратора 19. Выходной сигнал элемента И 28, равный 1, подается на один из входов соответствующего двухвходового сумматора по модулю два 27, который и производит инвертирование (коррекцию) соответствующего информационного с.чгнала информационного накопителя 1.

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

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

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

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

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

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

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

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

выход каждого из элементов сравнения соединен с соответствующим входом второго элемента ИЛИ. выход которого соединен с вторым входом элемента И.

Таблица

Таблица2

У

X

X

X

X

- $

X

X

x

&4

X X

v

X

XX