Запоминающее устройство
COlO3 СОВЕТСКИХ
СОЦИАЛ И СТИЧ Е С К ИХ
РЕСПУБЛИК (5!)5 G 11 С 17/00
ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ
ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К ПАТЕ НТУ (21) 4881323/24 (22) 09,08.90 (46) 07.02.93, Бюл. ¹ 5 (71) Научно-исследовательский институт вычислительных комплексов (72) С.В.Бирюков, Е,А.Брик и А.А.Крупский (73) С.В.Бирюков, Е,А.Брик и А.А.Крупский (56) Дублирование в запоминающих устройствах. — Вопросы радиоэлектроники, серия
ЭВТ, вып, 10. 1990. (54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к автоматике и вычислительной технике, в частности к полИзобретение относится к запоминающим устройствам (ЗУ) и в частности — к полупостоянным ЗУ с коррекцией ошибок.
Известны ЗУ с исправлением (коррекцией) одиночных и обнаружением двойных ошибок в кодовых. словах, использующие код Хемминга, Недостатком таких устройств является невозможность коррекции более сложных ошибок.
Известно также запоминающее устройство принятое эа прототип, способное корректировать более сложные ошибки и в том числе двойную ошибку в одной из строк или в одном из столбцов матрицы, образованной запоминающими элементами накопителя. Более сложные ошибки, например, две двойные ошибки в разных строках матрицы накопителя, данным устройством не коррек.тируются. а тройные ошибки и неисправности аппаратуры коррекции не обнаруживаются и некорректируются.
Целью изобретения является повышение надежности путем увеличения коррек„„SU„„1794261 А3 упостоянным запоминающим устройствам с коррекцией ошибок. Целью изобретения является повышение надежности устройства.
Поставленная цель достигается за счет введения дополнительного накопителя контрольных разрядов кодов Хемминга, коммутаторов, образующих матрицу коммутаторов, дополнительных блоков коррекции, элементов сравнения, первого и второго элементов ИЛИ, инвертора и элемента ИЛИ, В случае возникновения двойных ошибок в строках или столбцах информационной матрицы элементы сравнения отключаются, 5 ил„2 табл. тирующей способности устройства, охвата контролем аппаратуры коррекции ошибок и обнаружение тройных ошибок.
Поставленная цель достигается при помощи увеличения информационной избыточности путем введения дополнительного накопителя контрольных разрядов кодов
Хемминга, дополнительных блоков коррекции и матрицы выходных коммутаторов, а Ф также двухвходовых элементов сравнения Ю (при помощи которых производится сравне- 0 ние выходных сигналов основных и допол- а ни ельных блоков коррекции), двух элементов ИЛИ, инвертора и элемента И.
На фиг.1 показано предлагаемое устройство; на фиг,2 — условные обозначения информационного накопителя и двух контрольных накопителей с ошибочными разрядами, обозначенными знаком "X"; на фиг,3 — структурная схема блока коррекции; на фиг.4 — схема узла синдрома и дешифратора, один из возможных вариантов; на фиг.5 — схема узла коррекции, один иэ вариантов.
1794261
На фиг,1-5 и в тексте приняты следующие обозначения: 1 — информационный накопитель, 2 — основной накопитель контрольных разрядов кодов Хемминга; 3 — дополнительный накопитель контрольных разрядов кодов
Хемминга; 4 — основные блоки коррекции; 5— дополнительные блоки коррекции; 6 — информационные выходы основных блоков коррекции; 7 — информационнь!е выходы дополнительных блоков коррекции; 8 — сигнал двойной ошибки; 9.— двухвходоьь!е коммутаторы; 10 — управля1ощие входы коммутаторов;
1 1 — выхоДы ксммутатoIJGB, 12 — Двух<3хсДОвые эпементь сравнения:.!3 — первый элемент ИЛИ; 14 — второй элемент ИГ!И; 15— инвертор, 16 — двухвходовой элемент И; 17 — сии!ал ошибок блоков коррекции или тройной сшиб:; 18 — узел синдром,; 19— дешифратор; 20 — узел коррекции; 21 — сумматоры по модулго два (свертки) узла синдрома; 22 — свертка полного кода Хемминга;
23 — инверторы;, 4 — четырехвходовые элементы И; 25 — входы элементов И 24; 26— выходы дешифраторов 19; 27 — сумматоры по модул!о два; 28 — двухвходовые элементы
И; 29 — илвертор; 30 — четы рехвходовой элемент il f! N; 31 — ин вертор; 32 - двухвходовой элеме!!т И, Предлагаемое запомина!ощее устройство сociоит из и!!формационного накопителя 1, пoðâoão контрольного 2 и . торого контрольного 3 накопителей, основн!лх бло1 c p B в и е н и я 1 2, и е р 13 о Го 3n B vi o l-l TB И Л И 1 3, второго элемента ИЛИ 14, инвертсра 15 и двухвходсвого алел ента И 16, Коммутаторы 9 (фиг,1) составл»0T;naTрицу коммутаторов (на фиг.1 границы этой матрицы не показаны), содержащую п строк и fTl столбцов, т,е, общее количество коммутаторов 9 равно nrn, В информационном накопителе 1 имеется пгп запоминающих элементов (например, одноразрядных микрос;<ем памяти); и строк и m столбцов, На фиг,! и == 8, nl =-8 (8 информационнь|х байтов 10 8 разрядов в ка>кдом). В основном контроль::ом накопителе 2 имеет I XQviftt1lfr На фиг,1 п — -- 8, !< = 5, т к. для коррекции одино lt!ых ошибок и обн;.ружеltfn5l двойной Оц!ибки B Всеь!<И in! !: Ормац51онных разрядах в коде Хеминга требуется 5 контрольных pBBp51JJOB, T.B. В !;В >к:,О!! I-й (1 = i, и} CTpof l<0rt ITBn5l 2 copeð>!<ится nо I< =- 5 !<О!!Тр0 bt1 l ix раз!эяГ10!3 кода Хеммиl1 га, 0TH oc53!litnxc f < I ff строке информа11исннсго на1кспителя 1. А!1алОГич11ым ОбРазом !3 ДОП 051!115т !1ь 1!Ом контрольном накопителе 3 хран5!т . ml контрольных разрядов кода Хемминга: по =- 5 контрольных разрядов в каждом из m столбцов — для коррекции одиноч51ых и обнаружения двойных ошибок в соответству«ощем столбце накопителей 1 и 3. Для облегчения объяснения работы предлагаемого устройства введем такие термины как одиночные ошибки, двойные горизонтальные и двойные вертикальные ошибки, тройные горизонтальные и тройные вертикальные ошибки. На фиг.2а показан случай с пять50 одиночными ошибками, на фиг.26 — одна одиночная ошибка и одна горизонтальная тройная ошибки, на фиг.2в — одна одиночная и одна вертикальная тройная, на фиг,2à — Одна Одиночная tn ОДнз Двоиная Вертикальна51, на фиг.2д — одна двойная горизонтальная ошибка и, и наконец, на фиг.2е показаны две двойные ошибки — вер20 тикальная и горизонтальная, располо>кенные "углом", Предлагаемое устройство работает следу1ощим образом. При отсутствии ошибок, а также при наличии только одиночных ошибок (фиг,2а) на выходах 6 основных блоков коррекции 4 образу!отся пгп (на фиг,1 — 8 байтов по 8 разрядов) откорректированных информационных сигналов, т,к, каждый из основных блоков 30 коррекции 4, на входах которых имеется одиночная ошибка, исправят ее.,По этой же причине на выходах 7 дополнительных блоков коррекции 5 также образуется nm таких же откорректированных выходных сигналов (т,е, 64 выхода основных блоков коррекции 4 совпадают с 6 -1 выходами дополнительных блоков коррекции 5), Управл5!1ощие входы 10 коммутаторов 9, относящихся к определенной строке накопителей 1 и 2 и соответ-. ствен lo к определенному основному блоку коррекции 4, соединены между собой и с выходом 8 двойной ошибки данного основного блокэ коррекции 4, Поэтому при отсутствии двойной ошибки в данной строке 45 накопителей 1 и 2 на выходы 11 коммутаторОВ 9 данной строки, являющиеся информационными выходами устройства, пройдут выходные сигналы данного основного блока коррекции 4, 50 Поскольку для случая, показанного на фиг,2а, Выходные сигнапь! 6 и 7 блоков коррекции 4 и 5 совпадают, то на выходах nm элементов сраВнения 12, прсизВОд51щих псрязрядное побитнос сравне! i !е информаци013!!!!х Bыхсдов 6 5J 7 06eln>< rpyrtrf блоков коррекции образу!Отея си3 лалы "0". СледоВате!1ьно 13ыходнсй 01!Гнал ВтороГО элемента ИЛИ !4 также будет равен "0", Выходной сигнал первого эламе rra ИЛИ 13 также равен "0", т,к. двойных ошибок нет и выходные 1794261 сигналы 8 всех n + m блоков коррекции 4 и 5, соединенные со входами первого элемента ИЛИ 13, также будут равны "О",. На выходе инвертора 15 образуется сигнал "1", а на выходе 17 элемента И 16 будет уровень "0". сигнализирующий этим о исправности блоков коррекции 4 и 5, Если при ситуации, показанной на фиг,2а, произойдет сбой или отказ в каком-нибудь из блоков коррекции 4 и 5. то на выходе одного (или нескольких) элемента сравнения 12 и соответственно на выходе второго элемента ИЛИ 14, образуется сигнал ".1", который пройдет через двухвходовой элемент И 16, что и будет означать неисправность блоков коррекции, Сигнал 17 будет равен "1" еще в двух "случаях — при тройной горизонтальной или тройной вертикальной ошибке (фиг.2б,в). Тройная ошибка воспринимается соответствующим блоком коррекции как одиночная, в результате чего этот блок коррекции к имеющимся трем ошибкам добавляет четвертую; Следовательно выходные сигналы 6 и 7 основных и дополнительных блоков коррекции в четырех разрядах (из 64) при тройной ошибке будут отличаться друг от друга. Поэтому на выходах четырех элементов 12 (т.е, на четырех входах второго элемент элемента ИЛИ 14) образуются сигналы "1", и на выходах элементов 14 и 16 также. образуются сигналы "1". Сигнал "1".на выходе 17 элемента И 16 таким образом позволяет обнару>кить тройную ошибку, сигнализируя при горизонтальной тройной ошибке о неправлльной работе устройства (при вертикальной тройной ошибке устройство работает правильно, т.к. через соответствующие коммутаторы 9 все ошибочные разряды пройдут откорректированными — от основных блоков коррекции 4. Одиночные ошибки в случаях, показанных на фиг.2б и в, будут откорректированны обычным путем (как при фиг.2а), Рассмотрим теперь случаи с двойными ошибками (фиг,2г,д). При вертикальной двойной ошибке, показанной на фиг.2г, она вместе с одиночной ошибкой будет откорректирована обычным образом, как при случaå. показанном на фиг.2а, При горизонтальной двойной ошибке (фиг.2д) эта ошибка не будет откорректирована тем основным блоком коррекции 4, на входах которого имеется эта ошибка (т.к. обычный код Хемминга только обнаруживает, но не корректирует такие ошибки). Однако сигнал 8 двойной ошибки этого блока коррекции переключит все m коммутаторов 9 этой строки и поэтому через эти коммутаторы данный байт пройдет не с выходов 6 50 ответствующим дополнительным блоком коррекции 5 (как в случае, показанном на фиг.2д). Что касается ошибки, лежащей в вершине "угла", То эта ошибка откорректирована не будет, т.к, она входит в состав обеих двойных ошибок — как вертикальной, так и горизонтальной. Несмотря на этот недостаток предложенное устройство обладает значительно более высокой надежностью, чем устройство-прототип. Это происходит как благодаря полному контролю исправности блоков коррекции 4 и 5 (которые являются довольно сложными узлами), так и благодаря обнару>кению тройных ошибок. На фиг.3 показана структурная схема ос. oBMolo блока коррекции 4, который со стоит из узла синдрома 18, дешифратора 19 и узла коррекции 20. Узел синдрома 18 вырабатывает сигнал двойной ошибки 8 и синдром — двоичный код разряда, в котором имеется одиночная ошибка. Дешифратор 19 дешифрирует этот код, а узел коррекции 20 производит инвертирование (т.е. коррекцию) дефектного разряда. Входными сигналами основных блоков коррекции 4, показанных на фиг,1, являются 8 информационных сигналов Р1 — РЯ данного байта и пять контрольных разрядов К1 — К5 данной этого блока коррекции, а с выходов 7 дополнительных блоков коррекции 5 (для которых двойная горизонтальная ошибка является двумя простыми одиночными, и поэтому корректируемыми ошибками). При любой двойной ошибке на выходе элемента ИЛИ 14 образуется сигнал "1". т.к, на выходах двух элементов сравнения 12 образуются сигналы "1",. Для того, чтобы этот сигнал не прошел через элемент И 16, s устройстве предусмотрен первый п + mвходовой элемент ИЛИ 13. входы которого соединены с выходами 8 двойных ошибок всех n + m блоков коррекции. Таким образом, при любых двойных ошибках (вертикальных или горизонтальных) на выходе первого элемента ИЛИ 13 образуется сигнал "1", который через инвертор 15 блокирует прохождение через элемент "И" 16 20 сигнала "1" с выхода второго элемента ИЛИ 14, Другими словами, при двойных ошибках предотвращается ложный сигнал тревоги 17 (при двойных ошибках этот сигнал тревоги был бы ложным, т.к. двойные ошибки корректируются), При двух двойных ошибках, расположенных "углом", как показано на фиг.2е,, "нижняя" ошибка будет откорректирована соответствующим основных блоков коррек30 ции 4 (как в случае, показанном на фиг.2а). "Левая" ошибка будет откорректирована со1794261 40 строки основной контрольной матрицы 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 равны нулю). Поэтому все четыре Формула изобретения Запоминающее устройство, содержащее информационный накопитель, основной. накопитель контрольных разрядов 35 входных сигнала 25 элемента 24 разряда Р6 будут равны "1" и на выходе 26 этого элемента образуется сигнал "1", сигнализирующий об ошибке в разряде 6. Четы рехвходовой элемент ИЛИ 30 складывает (по ИЛИ) выходные сигналы всех четырех сверток, вырабатыва|ощих синдром. Поэтому при любой ошибке в 13 разрядах P и К на выходе элемента ИЛИ 30 будет сигнал "1". Если при этом выходной сигнал свертки 22 равен 0(а выходной сигнал инвертора 31 равен 1), то это означает, что имеется двойная (точнее четная) ошибка и выходной сигнал 8 двухвходового элемента И 32 будет равен 1, Таким образом, если выходной сигнал двойной ошибки 8 на выходе узла синдрома 18 равен "1", то это означает наличие двойной ошибки в контролируемом 13-разрядном коде. Аналогичным образом строятся узлы синдрома 18 и дешифраторы 19 дополнительных блоков коррекции 5 (при этом номера байтов и разрядов меняются местами). . На фиг.5 показана одна из возможных схем узла коррекции 20 основных блоков коррекции 4, Схема содержит восемь двухвходовых сумматоров по модулю два 27, восемь двухвходовых элементов И 28 и один инвертор 29, Задачей, выполняемой узлом коррекции 20, является (при условии отсутствия двойной ошибки) инвертирование (коррекция) того выходного информационного сигнала P информационного накопителя 1, в котором имеется ошибка, (т,е, того разряда Р, для которого соответствующий сигнал 26 "ош Р;" на выходе дешифратора 19 данного основного блока 4 коррекции равен единице). В этом случае на обоих входах соответст вуюш его элемента И 28. и рисутствуют два сигнала "1": один из них поступает с выхода инвертора 29 при отсутствиидвойной ошибки, а второй — сигнал 26 "ошР." — с соответствующего выхода дешифратора 19. Выходной сигнал элемента И 28, равный "1", подается на один из входов соответствующего двухвходового сумматора по модулю два 27, который и производит инвертирование (коррекцию) срответствующего информационного сигнала Р информационного накопителя 1. Аналогичным образом строятся узлы коррекции 20 дополнительных блоков 5 коррекции. кодов Хемминга, основные блоки коррекции, первые входы каждого из которых соединены с соответствующими выходами информационного накопителя, а вторые 1794261 Табл ица1 Табл ица2 Выхо ные сигналы све ток 21 и и ошибке PG С2 СЗ входы — с соответствующими выходами основного накопителя контрольных разрядов кодов Хемминга, отл ича ю ще ес я тем, что, с целью повышения надежности устройства, ойо содержит дополнительный накопитель контрольных разрядов кодов Хемминга, коммутаторы, образующие матрицу коммутаторов, дополнительные блоки коррекции, элементы сравнения, первый и второй элементы ИЛИ, инвертор и элемент И, выход которого является выходом неисправности устройства, первые входы каждого из дополнительных блоков коррекции соединены с соответствующими выходами информационного накопителя, а вторые входы каждого из дополнительных блоков - коррекции соединены с соответствующими выходами дополнительного накопителя контрольных разрядов кодов Хемминга, информационные выходы каждого из дополнительных блоков коррекции соединены с первыми информационными входами коммутаторов соответствующего столбца матрицы I коммутаторов, вторые информационные входы коммутаторов каждой строки матрицы соединены с информационными выходами соответствующего основного блока 5 коррекции, выход обнаружения двойной ошибки каждого основного блока коррекции соединен с управляющими входами коммутаторов соответствующей строки матрицы, выходы коммутаторов являются выходами устройства, 10 выход обнаружения двойной ошибки каждого основного и каждого дополнительного блока коррекции соединен с соответствующим в- oäoì первого элемента ИЛИ, выход которого соединен с входом инвертора, выход 15 которого соединен с первым входом элемента И, первый и второй входы каждого из элементов сравнения соединены соответственно с первым и вторым информационными входами соответствующего коммутатора, 20 выход каждого из элементов сравнения соединен с соответствующим входом второго элемента ИЛИ. выход которого соединен с вторым входом элемента И. 1794261 1794261 1794261 1794261 1794261 Составитель . Е,Брик Техред М.Моргентал Редактор Б,Федотов Корректор Н.Милюкова Производственно-издательский комбинат "Патент", г. Ужгород ул.Гагарина. 101 Заказ 533 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва. Ж-35, Раушская наб.. 4/5
