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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1801227 АЗ ц 5 6 11 С 17/О ТЕНИ НИЕ ИЗОБ К ПАТЕ Н Изобретение о щим устройствам (3 янным и полупосто ошибок,Цель изобретен недостатка, т. е, пов тройства в работе и топрйгодности,тноситсяУ), в частянным ЗУия - уст раышениеувеличе к запомин ности к пос с коррекц нениеданного надежности усние его ремонГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(71) Научно-исследовательский институт вычислительных комплексов(54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к автоматике и вычислительной технике, в частности к постоянным и полупостоянным запоминающим устройствам с коррекцией ошибок. Целью изобретения является повышение Сущность изобретения заключается. в том, что запоминающее устройство Содержит состоящий из гп столбцов и и строк информационный накопитель запоминающих элементов, хранящих информационные разряды, первый накопитель контрольных разрядов, в каждой из и строк которого хранится по 1 контрольных разрядов кода Хемминга, относящихся к соответствующей 2 надежности устройства, Это достигается за счет введения дополнительного накопителя контрольных разрядов кодов Хемминга, коммутато ров, образующих матрицу коммутаторов, дополнительных блоков коррекции, матрицы элементов И и сумматоров по модулю два, Совместная работа блока коррекции строк матрицы и блока коррекции столбцов матрицы позволяет корректировать любое количество одиночных ошибок в строках и столбцах матрицы, любое количество двойных ошибок в столбцах матрицы,одну двойную ошибку в строке. Для коррекции двух ошибок - двойной ошибки в строке и двойной ошибки в столбце, имеющих совпадающую ошибку, в устройстве имеется, матрица двухвходовых элементов И и матрица управляемых инверторов (двухвходо-, щ вые сумматоры по модулю два). 5 ил. строке информационного накопителя, второй накопитель контрольных разрядов, в каждом из а столбцов которого хранится по 1 контрольных разрядов кода Хемминга, относящихся к соответствующему столбцу ин- О формационного накопителя; первую группу ф блоков коррекции, каждый из которых име- Я ет (а + к) входов, соединенных с выходами Я соответствующей строки информационного снакопителя и одноименной строки первого накопителя контрольных разрядов, гп откор- ф ректированных информационных выходов и. фф один выход обнаружения двойной ошибки данной строки информационного и первого контрольного накопителя; вторую группу, блоков коррекции, каждый из которых имеет (и +) входов, соединенных с выходами соответствующего столбца информацион 1801227ного накопителя и одновременного столбца второго контрольного накопителя, и откор ректированных информационных выходов и выход обнаружения двойной ошибки данного столбца информационного и второго контрольного накопителя; матрицу коммутаторов, содержащую щп двухвходовых коммутато.ров, первые информационные входы в коммутаторов каждой из и строк матрицы коммутаторов соединены с щ выходами соответствующего блока коррекции первой группы, вторые информационные входы и коммутаторов каждого из в столбцов матрицы коммутаторов соединены с и выходами соответствующего блока коррекции второй группы, управляющие входы т коммутаторов каждой из и строк матрицы коммутаторов соединены между собой и с выходом обнаружения двойной ошибки соответствующего блока коррекции первой группы; запоминающее устройство содержит также матрицу двухвходовых элементов и и матрицу двухвходовых сумматоров по модулю два,. Существенным отличием изобретения является наличие этих двух матриц; матрицы, содержащей пт двухвходовых элементов И, и матрицы, содержащей пщ двухвходовых сумматоров по модулю два, причем первые входы щ двухвходовых элементов И каждой из и строк матрицы двухвходовых элементов И соединены между собой и с выходом двойной ошибки.соответствующего блока коррекции первой группы блоков коррекции, вторые входы и двухвходовых элементов И каждого из в столбцов матрицы двухвходовых элементов И соединены между собой и с выходом двойной ошибки соответствующего блока коррекции второй группы блоков коррекции, выход каждого из в двухвходовых элементов И 1-й ( = 1, и) строки матрицы двухвходовых элементов И соединен с первым входом соответствующего сумматора по модулю два 1-й строки матрицы двухвходовых сумматоров по модулю два, выход каждого из щ двухвходовых коммутаторов 1-й ( = 1, и) строки матрицы двухвходовых коммутаторов соединен со вторым входом соответствующего сумматора по модулю два 1-й строки матрицы двухвходовых сумматоров по модулю два, выходы двухвходовых сумматоров по модулю два являются выходами устройства,Совокупность перечисленных признаков поЗволяет откорректировать две двойные ошибки - вертикальную и горизонтальную, расположенные "узлом", что в указанном прототипе не выполнялось, Это позволяет повысить надежность устройства,На фиг. 1 показана схема запоминающего устройства; на фиг. 2 - условные обоз-начения информационного накопителя 1,первого накопителя 2 контрольных разря 5 дов кодов Хемминга, второго накопителя 3контрольных разрядов кодов Хемминга сошибочными разрядами (места ошибок показаны знаком "Х"); на фиг. 3 - структурнаясхема блока коррекции; на фиг, 4 - одна из"0 возможных схем узла синдрома и дешифра- .тора; на фиг. 5 - один из вариантов узлакоррекции.Предлагаемое устройство состоит из,информационного 1, первого контрольного15 2 и второго контрольного 3 накопителей запоминающих элементов, первой группы 4 ивторой группы 5 блоков 6 коррекции, двухвходовых коммутаторов 9, управляемых ин.верторов (сумматоров по модулю два) 12 и20 двухвходовых элементов И 13.В информационном накопителе 1 имеется вп запоминающих элементов (например, одноразрядных микросхем памяти); истроки в столбцов. На фиг, 1 и =8, щ =8(825 информационных байтов по 8 разрядов вкаждом). В первом контрольном накопителе2 имеется Кп контрольных разрядов кодаХемминга, На фиг. 1 и = 8, К = 5, так как длякоррекции одиночных ошибок и обнаруже 30 ния двойной ошибки в восьми информационных разрядах в коде Хемминга требуется5 контрольных разрядов, т. е, в каждой-й= 1, п) строке первой контрольной матрицы2 содержится по Е =5 контрольных разрядов35 кода Хемминга, относящихся к 1-й строкеинформационного накопителя 1.Аналогичным образом во втором контрольном накопителе 3 хранятся т контрольных разрядов кода Хемминга; по= 540 контрольных разрядов в каждом из гп столбцов - для коррекции одиночных и обнаружения двойных ошибок в соответствующемстолбце накопителей 1 и 3./Коммутаторы 9 составляют матрицу ком 45. мутаторов (на фиг, 1 границы этой матрицы непоказаны для упрощения рисунка), содержащую и строк и гп столбцов, т. е, общее количество коммутаторов 9 равно гпп,Для облегчения объяснения работы пред 50 лагаемого устройства введем такие термины,как одиночные ошибки, двойные горизонтальные и двойные вертикальные ошибки, Эти термины поясняются на фиг, 2, На фиг, 2, а показанслучай с тремя одиночными ошибками; на фиг,552, б- одна одиночная и одна двойная вертикальная ошибка; на фиг, 2, в - одна двойная горизонтальная ошибка; на фиг, 2, г - две двойныеошибки - вертикальная и горизонтальная, расположенные "углом",т, е, с общей ошибкой (вершинаим двойным ошибкам - вертикальной и горизонтальной; на фиг. 2, д - две "обычные" двойные ошибки,Предлагаемое устройство работает следующим образом, При отсутствии ошибок, а также при наличии только одиночных ошибок (фиг. 2, а) на выходах 7 блоков коррекции 6 первой группы 4 блоков коррекции образуются па (на фиг. 1 8 байтов по 8 разрядов), откорректированных информационных сигналов, так как каждый из блоков коррекции 6 группы 4, на входах которых имеется одиночная ошибка, исправит ее, По этой же причине на выходах 7 блоков коррекции 6 группы 5 также образуется пп таких же откорректированных выходных сигналов (т. е, 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, являющихся выходами устройства, пройдет откорректированный па-разрядный код (и строк по а столбцов) из блоков коррекции 6 группы 4.Рассмотрим теперь показанные на фиг.2, б, в случаи с двойными ошибками.При вертикальной двойной ошибке, показанной на фиг. 2, б, она вместе с одиночной ошибкой будет откорректирована обычным образом, как при случае, показанном на фиг. 2, а.При горизонтальной двойной ошибке (фиг. 2, в) эта ошибка не будет откорректирована тем блоком коррекции 6 группы 4, на входах которого имеется эта ошибка (так как обычный код Хемминга,только обнаруживает, но не корректирует такие ошибки). Одна- ко сигнал 8 двойной ошибки этого блока коррекции переключит все пз коммутаторов 9 этой строки и поэтому через эти коммутаторы данный байт пройдет не с выходом 7 . этого блока коррекции, а с выходов 7 блоков20 ком коррекции 6 группы 4 (как в случае,показанном на фиг. 2, а). "Левая" ошибка будет, откорректирована соответствующим 45 50 5 10 15 30 35 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 10 15 25 30 35 40 45 50 55 этот код, а узел коррекции 20 производит инвертирование(т.е,коррекцию)дефектного разряда, Входными сигналами блока 6 коррекции, например, для группы 4, показанной на фиг. 1, являются восемь информационных сигналов Р 1-Р 8 данного байта и пять контрольных разрядов К 1 - К 5 данной строки первой контрольного накопителя 2. Информационными выходами блока коррекции 6 являются восемь откорректированных сигналов 7 данного байта.На фиг. 4 показана одна из возможных схем узла синдрома 18 и дешифратора 19 блоков коррекции 6 первой группы 4. Узел синдрома содержит четыре сумматора 21 по модулю два (свертки) С 1 - С 4, вырабатывающих четыре разряда синдрома в соответствии с табл. 1 классического кода Хемминга, В каждом из четырех столбцов табл. 1 указаны те разрядь 1 Р и К, которые подаются на входы данной свертки С,дой из сверток 21) выходные сигналы всех четырех сверток 21 равны нулю), Поэтому все четыре входных сигнала 25 элемента 24 разряда Рб будут равны "1" и на выходе 26 этого элемента образуется сигнал "ошРб", сигнализирующий об ошибке в разряде Рб,Четырехвходовой элемент ИЛИ 30 складывает (по ИЛИ) выходные сигналы всех четырех сверток 21, вырабатывающих синдром. Поэтому при любой ошибке в,13 разрядах Р и К на выходе элемента ИЛИ ЗО будет сигнал "1"; Если при этом выходной сигнал свертки 22 равен "0" (а выходной сигнал инвертора 31 равен "1"), то это означает, что имеется двойная (точнее, четная) ошибка и выходной сигнал 8 двухвходового элемента И 32 будет равен "1", Таким образом, если выходной сигнал двойной ошибки 8 на выходе узла синдрома 18 равен "1", то это означает наличие двойной ошибки в контролируемом 13-разрядном коде,Аналогичным образом строятся узлы синдрома 18 и дешифратора 19 блоков коррекции б второй группы 5 (при этом номера байтов и разрядов меняются местами),На фиг, 5 показана одна из возможных схем узла коррекции 20 блоков коррекции б первой группы 4 блоков коррекции, Схема содержит восемь двухвходовых сумматоров 27 по модулю два, восемь двухвходовых элементов И 28 и один инвертор 29. Задачей, выполняемой узлом коррекции 20, является (при условии отсутствия двойной ошибки) инвертирование(коррекция) того выходного информационного сигнала Р информационной матрицы 1, в котором имеется ошибка, т. е, того разряда Р 1, для которого соответствующий сигнал 26 "ошРГ на выходе дешифратора 19 данного блока коррекции 6 равен единице. В этом случае на обоих входах соответствующего элемента И 28 присутствует два сигнала "1": один из них поступает с выхода инвертора 29 при отсутствии двойной ошибки, а второй сигнал 26"ош РГ - с соответствующего выходного дешифратора 19. Выходной сигнал элемента И 28, равный "1", подается на один из входов соответствующего двухвходового сумматора 27, который и производит инвертирование (коррекцию) соответствующего информационного сигнала Р информационной матрицы 1.Аналогичным образом строятся узлы коррекции 20 блоков коррекции б второй группы 5 блоков коррекции.Формула изобретения Запоминающее устройство, содержащее информационный накопитель, основной накопитель контрольных разрядов10 1801227 Таблица 1 абли кодов Хемминга, основные блоки коррекции, первые входы каждого из которых соединены с соответствующими выходамиинформационного накопителя, а вторыевходы каждого из основных блоков коррекции соединены с соответствующими выходами основного накопителя контрольныхразрядов кодов Хемминга, о т л и ч а ю щ ее с я тем, что, с целью повышения надежности устройства, оно содержит дополнитель Оный накопитель контрольных разрядовкодов Хемминга, коммутаторы, образующиематрицу коммутаторов, дополнительные. блоки коррекции, матрицу элементов И исумматоры по модулю два, выходы которых 15являются выходами устройства, первыевходы каждого из дополнительных блоков коррекции соединены с соответствующимивыходами информационного накопителя, авторые входы каждого из дополнительных 20блоков коррекции соединены с соответствующими выходами дополнительного накопителя контрольных разрядов кодовХемминга, информационные выходы каждого из дополнительных блоков коррекции соединены с первыми информационными входами коммутаторов соответствующео столбца матрицы, вторые информационные входы коммутаторов каждой строки матрицы соединены с информационными выходами соответствующего основного блока коррекции, выход обнаружения двойной ошибки каждого основного блока коррекции соединен с управляющими входами коммутаторов соответствующей строки матрицы, первые входы элементов И каждой строки матрицы объединены и подключены к выходу двойной ошибки соответствующего основного блока коррекции, вторые входы элементов И каждого столбца матрицы объединены и подключены к выходу двойной ошибки соответствующего дополнительного блока коррекции, выход каждого из элементов И соединен с первым входом соответствующего сумматора по модулю два, выход каждого из коммутаторов соединен с вторым входом соответствующего сумматора по модулю два,1801227 Составитель Е.БрикТехред М,Моргентал Корректор Е,П Редакт аказ 1191 Тираж Подписное8 НИИПИ Государственного комитета по изобретениям и открыти113035, Москва, Ж, Раушская наб., 4/5 ГКНТ ССС оизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101