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

Е ИЗОБРЕТЕН ОПИСА С(; ь 11 Фиеев устройать более е двойнуюодном й запоеля. Боле двойные цы накопи ректируютинающ ктиров м числ или в ованно акопит мер, дв матрине кор из ми- ее ошибки в разных строкахтеля) данным устройствомся,нформацио нный тхп информациОСУДАРСТВЕННЫИ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Научно-исследовательский институт вычислительных комплексов(54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к запоминающим устройствам, в частности к полупостоя н н ым ЗУ с коррекцией ошибок. Целью Изобретечие относится к запоминающим устройствам (ЗУ), в частности к полупостоянным ЗУ с коррекцией ошибок,Известны ЗУ с исправлением (коррекцией) одиНочных и обнаружением двойных ошибок в кодовых словах, использующих код Хемминга.Недостатком таких устройств является невозможность коррекции более сложных ошибок,Известно также запом ство, способное корре сложные ошибки и в то ошибку в одной из стро столбцов матрицы, образ наЮщими элементами н сложные ошибки (напри изобретения является повышение йадежности за счет корректирующей способности устройства, Цель достигается за счет введения дополнительного наКопителя контрольных разрядов кодов Хемминга, дополнительных блоков коррекции, коммутаторов, образующих матрицу, Сущность изобретения заключается в использовании ортогонального кодированйя матрицы с эапомйнающими элемейтами путей йсйользования кодовых словХемминга отдельно для каждой строки и для каждого столбца матрицы и использовании коммутаторов, осуществляющих передачу строк матрицы, откорректированных узлами коррекции строк или столбцов матрицы, 2 табл 5 ил. С:Целью изобретения является повыше- р ние надежности устройства путем увеличения его корректирующей способности.Поставленная цель достигается при по- а мощи увеличения информационной избыточности путем введеййя "дополнительного накопителя контрольных- разрядов-кодов Хемминга, дополнительных блоков коррекции и матрицы выходных коммутаторов, при помощи которых на выход устройства пропускаются выходные сигналы основных или д дополнительных блоков коррекции в зависимости оттого,где и как размещены дефек-. ф тные биты.На фиг.1 показана схемазаявленного устройства; на фиг,2 и 3 места ошибок в накопителях устройства (места ошибок показаны знаком х); на фиг,4 - схема узлов синдрома и дешифраторов; на фиг.5 -схема узлов коррекции,ЗУ (фиг.1) содержит инакопитель 3, содержащей10 одна одиночная и одна вертикальная двойная ошибки; на фиг, 2 в - одна двойная гори-30 35 онных разрядов 1, основной накопитель 4 контрольных разрядов 2 кодов Хемминга, дополнительный накопитель 10 дополнительных контрольных разрядов 9 кодов Хемминга, основные блоки 5 коррекции, дополнительные блоки 11 коррекции и матрицу коммутаторов 12, содержащую и строк и щ столбцов,Для объяснения работы устройства, введет понятия: одиночные ошибки, двой- ные . горизонтальные, двойные вертикальные, тройные горизонтальные и вертикальные ошибки (фиг.2), На фиг. 2 а имеется.5 одиночных ошибок, на фиг. 2 б -зонтальная и одна одиночная ошибки; на фиг, 2 г - одна тройная вертикальная и одна одиночная ошибки; на фиг. 2 д - тройная горизонтальная ошибка; на фиг, 2 е - две двойные ошибки - горизонтальная и вертикальная, расположенные углом.Устройство работает следующим образом,При отсутствии ошибок, а также при наличии только одиночных ошибок на информационных выходах 13 основных блоков 5 коррекции образуются пхт (на фиг.1- 8 байтов по 8 разрядов) откорректированных информационных сигналов, так как каждый из основных блоков 5 коррекции, на входах которого имеется одиночная ошибка, исправит ее. По этой же причине на информационных выходах 14 дополнительных блоков 11 коррекции также образуется пха таких же откорректированных выходных .сигналов (т,е, сигналы 13 и 15 совпадают).Управляющие входы 15 коммутаторов 12, относящихся к определенной строке накопителей 3 и 4 и, соответственно, к определенному основному блоку 5 коррекции, соединены с выходом 16 двойной ошибки данного основного блока 5 коррекции. Поэ тому при отсутствии двойной ошибки в данной строке накопителей 3 и 4 на выходы 17 коммутаторов 12 данной стройки пройдут выходные сигналы данного основного блока 5 коррекции.На выходах (фиг.2 б) того дополнительного блока 11 коррекции, на входах которого имеется двойная (вертикальная) ошибка,эта ошибка не будет откорректирована (так как обычный ход Хемминга только обнаруживает, но не корректирует такие ошибки). Тем не менее, на выходах 17 всех вп коммутаторов 12 образуется правильный пгп-разрядный код, так как через эти коммутаторы будут проходить выходные сигналы основнцх блоков 5 коррекции (ни один из.зтих блоков коррекции на своих а+1 информаци 20 25 онных входах не имеетдвойной ошибки).Аналогичная картина будет иметь место прислучае, показанном на фиг, 2 г (несмотря натройную вертикальную ошибку),В случае, показанном на фиг, 2 в (однаодиночная ошибка в 7-м байте и одна гори- .зонтальная двойная в 4-м байте), одиночнаяошибка будет. откорректирована как в предыдущих случаях (фиг, 2 а, б, г), Что касаетсядвойной горизонтальной ошибки, то она тоже окажется откорректированной, так какна выходе 16 основного блока коррекции4-го байта образуется сигнал двойной ошибки, который переключает коммутаторы 124-го байта и через эти коммутаторы пройдутвсе выходные сигналы основного блока 5коррекции ( как во всех остальных пв-вкоммутаторах 12), а выходные сигналы 14дополнительных блоков 11 коррекции, относящиеся к 4-му байту (т,е. по одному сигналу4-го разряда от всех восьми дополнительных блоков 11 коррекции),При случаях, показанных на фиг, 2 д и е,коррекция ошибок не произойдет, т,е; устройство будет работать неверно (кроме того, при тройной горизонтальной ошибке непроизойдет й обнаружение ошибки, а к тремимеющимся ошибкам добавится четвертаяошибка, выработанная основным блокомкоррекции байта, в котором произошлатройная ошибка, которую основной блоккоррекции примет за одиночную). 8 случае,показанном на фиг, 2 е, две ошибки на выходах 17 устройства окажутся откорректиро-ванными (нижняя ошибка - основнымблоком коррекции, а правая ошибка - дополнительным блоком коррекции), а третьяошибка, находящаяся в вершине угла, останется неоткорректированной, так как онарасположена на пересечении двух двойныхошибок - горизонтальной и вертикальной.Несмотря на отмеченный недостаток,предложенное устройство обладает высокой корректирующей способностью и можеткорректировать разнообразные и в том числе весьма сложные ошибки, Такой случайсложной, но полностью корректируемой ситуации для примера показан на фиг.3.На фиг.4 показана одна из возможныхсхем узлов 6 синдрома и дешифраторов 7основных блоков 5 коррекции для случаягп = 8, М = 5. Узел синдрома содержит четыресумматора 18 по модулю два (свертки) С 1 С 4, вырабатывающих 4 разряда синдрома всоответствии с табл.1 классического кодаХемминга. На входах каждой из сверток 18 имеется только один контрольный разряд К, который при исправном устройстве дополняет дочетности сумму по модулю два остальных . емой узлом 8 коррекции, является (при условходных сигналов данной свертки, вии отсутствия двойной ошибки, инвертироПятый контрольный разряд К 5 дополня- вание того выходного информационногоет до четности сумму всех 12 разрядов хода сигнала Р информационного накопителя 3,Хемминга (Р 1-Р 7, К 1-К 4), поэтому выходной 5 в котором имеется ошибка (т.е. т ого разрядасигнал свертки 19 равен "О" (а выходной Рь для которого имеется соответствующийсигнал инвертора 27 равен "1"), если в 13- сигнал 22 ошР 1, на выходе дешифратора 7разрядном коде (Р 1-Р 7, К 1-К 5) нет ошибок данного основного блока 5 коррекции,или есть четная ошибка, Выходной сигналэлемента ИЛИ 28 при отсутствии ошибок в 10 В этом случае на обоих входах соответ 12-разрядном коде равен "О" (так как все ствующего элемента 24 присутствуют двавыходные сигналы сверток 18 равны "О") и сигнала "1" (один из них поступает с выходаравен "1", если в 12-разрядном коде есть инвертора 25 приотсутствиидвойнойошибкакая-нибудь ошибка (так как один или не- ки, а второй - сигнал 22 ошР - с соответстсколько выходных сигналов сверток 18 рав вующего выхода дешифратора 7). Выходнойны "1"). сигнал элемента И 24 подается на один изТаким образом, при четной ошибке(и в входов соответствующего сумматора 23 потом числе при наиболее вероятной из них - модулю два, который и производит инвертидвойной ошибке) оба выходных сигнала эле- рование соответствующего информационмента И 29 равны "1" и поэтому на выходе 20 ного сигнала Р информационногоэтого элемента выходной сигнал 16 двойной накопителя 3.ошибки будет равен "1". Так производится Аналогичным образом строятся узлы 8обнаружение двойной (четной) ошибки уз- коррекции дополнительных блоков 11 корлом 6 синдрома, ркц,Дешифратор 7 состоит из четырех инверторов 26, инвертирующих выходные сиг- ф о р м у л а и з о б р е т е н и яналы сверток 18, восьми (по числу разрядовР 1-Р 8) 4-входовых (по числу кодовых столб- Запоминающее устройство, содержацов в табл.3) элементов И 20. На выходе щее информационный накопитель, основкаждого из элементов 20 вырабатывается 30 ной накопитель контрольных разрядовсигнал ошибки соответствующего информа- кодов Хемминга, основные блоки коррекционного разряда Р, так как 4 входа 21 каж- ции, первые входы каждого из которых соедого из элементов 20 соединены с выходами динены с соответствующими выходами. сверток 18 и инверторов 26 в соответствии, информационного накопителя, а вторыес табл Например, входы элемента 20, вы входы каждого из основных блоков коррекрабатывающего сигнал ошибки разряда Р 6, ции соединены с соответствующими выхосоединены с выходами сверток С 2 и СЗ и дами основного накопителя контрольныхвыходами двух инверторов 26, инвертирую- рязрядов кодов Хемминга, о т л и ч а ю щ ещих выходные сигналы сверток С 1 и С 4.еся тем,что,сцельюповышения надежноТакое соединение определяется строчкой 40 стиустройства, оно содержитдополнительР 6 в табл,1 (код 0110). Поэтому, если в раэ- ный накопитель контрольных разрядовряде Р 6 произойдет ошибка, то на выходах кодов Хемминга, коммутаторы, образующиесверток 18 образуется код синдрома 0110, матрицу, дополнительные блоки коррекции,показанный в табл.2 (при отсутствии оши- первые входы каждого из которых соединебок, т.е. при четности количества единиц на 45 ны с соответствующими выходами инфорвходах каждой из сверток 18, выходныесиг- мационного накопителя, а. вторые входыналы всех 4 сверток 18 равны нулю), Поэто- каждого из дополнительных блоков коррекму все 4 входных сигнала элемента 20 ции соединены с соответствующими выхоразряда Р 6 будут равны "1" и на выходе 22 дами дополнительного накопителяэтого элемента образуется сигнал "1", сиг контрольных разрядов кодов Хемминга, иннализирующий об ошибке в разряде Рб. формационные, выходы каждого из дополнительных блоков коррекции соединены сАналогичным образом строятся узлы первыми информационными входами комсиндрома 6 и дешифраторы 7 дополнитель- мутаторов соответствующего столбца матных блоков 11 коррекции. На фиг.5 показанаэ 5 рицы, вторые информационные входыодна из возможных схем узла 8 коррекции. коммутаторов каждойстроки матрицы соеосновных блоков 5 коррекции. Схема содер- динены с информационными выходами сожит восемь двухвходовых сумматоров 22 по ответствующегоосновного блокамодулю два, восемь 2-входовых элементов коррекции, выход обнаружения двойнойИ 24 и один инвертор 25. Задачей, выполня-ошибки каждого основного блока коррек1753491 Таблица 1 лица ции соединен с управляющими входамикоммутаторов соответствующей строки мат-,рицы, выходы коммутаторов матрицы являются выходами устройства.