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

/24-2434. Бюл. 1 Ф 44бузов, Л.Н Паращук ято а и ус ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЬПЪЙ(56) 1. Патент США В 4163147,кл. 6 06 Р 11/12, опублик. 19792. Патент США Иф 4030067,клС 06 Р 11./12, опублик. 1977(54)(57) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВОС КОРРЕКЦИЕЙ ОШИБОК, содержащеенакопитель, первый элемент ИЛИ,формирователь импульсов контрольных разрядов, формировагель.импульсов контрольного слова, блокпостоянной памяти, первый и второйдешифраторы, сумматор по модулюдва, причем информационный входнакопителя соединен с входом формирователя импульсов контрольныхразрядов и является входом устройства, выход формирователя импульсовконтрольных разрядов соединен скон рольным .входом накопителя,вы- .ход которого подключен к входу формирователя импульсов контрольногослова и первому входу сумматорапо модулю два, выход которого является информационным выходом. устройства, первый выход формирователя,импульсов контрольного слова соединен с входами первого элемента ИЛИи блока постоянной памяти, выходкоторого подключен к входам первого и второго.дешифраторов, выходы которых соединены соответственно с вторым и третьим входами сумматора по модулю два, о т л и ч а ю щ е е с я тем, что, с целью повышения надежности устройства, оно содержит элементы И, второй, третий и четвертый элементы ИЛИ, элемент ИЛИ-НЕ,причем второй выход формирователя импульсов контрольного слова соединен с первыми входами первого, второго и . третьего элементов И, выход первого элемента ИЛИ подключен к вторым входам первого, второго и третьего элементов И и к первому входу четвертого элемента И, выход блока :лостоянной памяти соединен с входами третьего и четвертого элементов ИЛИ и входом пятого элемента И, выход третьего элемента ИЛИ подключен к третьим входам первогои треть- Я его элементов И и к второму входу четвертого элемен а И; выход четвертого элемента ИЛИ соединен с чет" вертыми входами первого и третьего элементов И и с третьим входом четвертого элемента И, выходы первого и второго элементов И соединены с. входами второго элемента ИЛИ, выход фф которого подключен к четвертому входу сумматора по модулю два, выходы третьего, четвертого и пятого элементов И соединены с входами элемента ИЛИ-НЕ, выход которого подключен к п му входу сумматора по модулю дв является контрольным выходом тройства.1127012 Изобретение относится к вычислительной технике, в частности кконтролю. работы запоминающихустройств, и может быть использованов запоминающих устройствах ЭВМ.Известно запоминающее устройствос коррекцией ошибок;, содержащеенакопитель, схемы формирования проверочного слова, дешифраторы одноразрядной и двухразрядной ошибок, 10постоянное запоминающее устройство,схему обнаружения ошибок и селектор 13,Однако многократное обращение кпостоянному запоминающему устройствупри возникновении ошибки в укаэанномустройстве значительно увеличиваетвремя обращения к запоминающемуустройству.Наиболее близким по технической 1 Осущности к изобретению являетсязапоминающее устройство с коррекцией ошибок, содержащее накопитель,информационный вход которого является информационным входом устройства, формирователь импульсов контрольных .разрядов, вход которогосоединен с информационным входомустройства, а выход .соединен с контрольным входом накопителя, блокпоразрядного суммирования по модулюдва, выход которого является информационным выходом устройства, апервый вход соединен с выходомнакопителя, соединенные последова 35тельно формирователь импульсов контрольного слова, вход которого соединен с выходом накопителя, .блокпостоянной памяти и первый дешифратор, выход которого соединен с вторым входом блжа поразрядного суммирования по модулю два, первыйэлемент ИЛИ, входы которого соединены с выходами формирователя импульсов контрольного слова, междувыходами разрядов блока постояннойпамяти и третьим входом блокапоразрядного суммирования по модулюдва включен второй дешифратор 2 1,Недостаток данного устройстваобусловлен невозможностью обнаруженияпакетных ошибок и сочетаний одно-,разрядных и пакетных ошибок, которыемогут возникнуть при использовании многоразрядных блоков накопителя, что снижает достоверность хранимой информации.1 ель изобретения - повышение надежности устройства. 1Поставленная цель достигается тем, что в запоминающее устройство с коррекцией ошибок, содержащее накопитель, первый элемент ИЛИ,формирователь импульсов контрольных разрядов, формирователь импульсов контрольного слова, блок постоянной памяти, первый и второй дешифраторы, сумматор по модулю два, причем информационный вход накопителя соединен с входом формирователя импульсов контрольных разрядов и является входом устройства, выход формирователя импульсов контрольных разрядов соединен с контрольным входом накопителя, выход которого подключен к входу. формирователя импульсов контрольного слова и первому входу сумматора по модулю два, выход которого является информационным выходом устройства, первый выход формирователя импульсов контрольного слова соединен с входами первого элемента ИЛИ и блока постоянной памяти, выход которого подключен к входам первого и второго дешифраторов, выходы которых соединены соответственно с вторым и третьим входами сумматора по модулю два, введены элементы И, второй, третий и четвертый элементы ИЛИ, элемент ИЛИ-НЕ, причем второй выход формирователя импульсов контрольного слова соединен с первыми входами первого, второго и третьего элементов И, выход первого элемента ИЛИ подключен к вторым входам первого, второго и третьего элементов И и к первому входу четвертого элемента И, выход блока постоянной памяти соединен с входами третьего и четвертого элементов ИЛИ и входом пятого элемента И выход третьего элемента ИЛИ подключен к третьим входам первогои третьего элементов И и к второму входу четвертого элемента И, выход четвертого элемента ИЛИ соединен с четвертыми вхо-, дами первого и третьего элементов И и с третьим входом четвертого .элемента И, выходы первого и второго элементов И соединены с входами второго элемента ИЛИ, выход которого подключен к четвертому входу сумматора по модулю два,выходы третьего, четвертого и пятого элементов И соединены с входами элемента ИЛИ-НЕ, выход которого под3ключен к пятому входу сумматора ПР модулю два и является контрольным выходом устройства.На фиг.1 представлена структурная схема предложенного устройства, на фиг.2 - пример выполнения блока поразрядного суммированияпо модулю два, на фиг.З и 4 - поовевочная Н-матрица кода для разрядности запоминающего устр йства, равной 128 . 10 разрядам. 11 27012 О 1 1 1 1 1 О 1 1 80 35 45 50 Устройство, содержит накопитель 1,формирователь 2.импульсов контрольных разрядов, сумматор 3 по модулюдва, формирователь 4 импульсов кон.трольного слова, блок 5 постояннойпамяти, первый дешифратор 6, первыйэлемент ИЛИ 7, второй дешифратор 8,первый элемент И 9, второй элемент И 10, третий элемент. И 11, чет"вертый элемент И 12, пятый элемент И 13, элемент ИЛИ-НЕ 14, второй элемент ИЛИ 15, третий эле.мент. ИЛИ 16, четвертый элемент ИЛИ17, блок 18 элементов ИЛИ, блок 19элементов И, блок 20 двухвходовыхсхем сложения по модулю два,1 1 О О 1 О О с с о о о с( с Фгде сР - вектор-столбцы степени 1. , Н-матрицы для поля Галуа СР(2 ф).Разряд 80 проверочного словаполучается сложением по модулю два тех разрядов, у которых имеется"1" в верхней строке матрицы.Разряды 81 проверочного слова получаются сложением. по модулю два разрядов второй строки, а разряды82 - третьей строки Н-матрицы. Разряд общей четности определяется как 80 ф = 80 + 81 82.При возникновении ошибок в 1 иразрядах хранимого в накопителе слова значения разрядов 81 и 82 проверочного слова, определяются-.Р "О (1 "Разряд общей четности 80+ = О,Прн возникновении ошибки в одномразряде хранимого слова выполняютсяусловия 4В осиову работы предложенного устройства положены следующие теоретические предпосылки.Повышениетребований к надежности, запоминающих устройств (ЗУ) на полупроводниковых запоминающих микросхемах привело.к необходимости.применения корректирующих кодов Боуэа-Чоудхури-Хоквингема (БЧХ),исправляю- щих одну или две одноразрядные ошибки и обнаруживающих три одноразрядные ошибки, воэникаюшие в результате сбоев или отказов в полупроводниковом ЗУ, Однако эти коды не обнару" живают ошибки.при отказах строки запоминающих микросхем модуля памяти, всего модуля памяти, схем кодирования и декодирования и др., т.е. при отказах и сбоях, приводящих к пакетным ошибкам, а также к сочетаниям пакетных и одноразрядных ошибок. Для кода БЧХ с параметрами и - кодовое слово, равное 16 и информационное слово, равное 7, порождающий полином имеет видР(Х) = (Х+ Х+ 1).Проверочная Н-матрица декодирования следующая 7сэ 10 11 12 1 Э И с с с с с с о О(81)з=82, 80=1.При возникновении трех ошибок разряд общей четности 8 С" равен единице, а условие 82=(81) не выполняется. Для обнаружения пакетных ошибок и их сочетания с одноразрядными необходимо, чтобы сумма по модулю два любого числа вектор-столбцов, входящих в состав одного пакета разрядов или в сочетании с любым вектор - столбцом Н - матрицы , не должна равняться никакому из используемых вектор - столбцов Н-матрицы или никакой сумме двух лю. бых вектор - . столбцов Н - мат - рицыЭтому требованию удовлетворяетраспределение вектор-столбцовН-матрицы декодирования по пакетамкоторое при разрядности пакета,равной 4, имеет видо дСО 5 С 1 4СЗ С 8 СА 3Проверочная Н-матрица кодирования строится аналогично проверочной Н-матрице декодирования, только порождающщй цолинои Р(Х) = (Х +Х+1)(Хф+Х 9+Х 2+Х+1) выбирается по из вестным таблицам построения кода БЧХ.Устройство работает следующим образом.При записи информационное сло О во поступает с информационного вхо" да устройства в накопитель 1 и формирователь 2 импульсов контрольных разрядов, где в соответствии, с Н-матрицей кодирования формируют ся значения контрольных разрядов, которые также поступают в накопитель 1 через его контрольный вход.При считывании значения информационных и контрольных разрядов ЗО поступают на Формирователь 4 импульсов контрольного слова, где определяются значения разрядов 80, 81 и 82 контрольного слова в соответствии с Н-матрицей декодирования (фиг,3 и 4) . В Формирователе 4 импульсов контрольного слова определяется также значение разряда общей четности, как сумка по модулю два значений разрядов 80, 81 и 82 контрольного слова,т.е. 804981 Ж 82.,Значение разряда общей четности контрольного слова. поступает с дополнительного выхода Формирователя 4 импульсов контрольного слова на первый инверсный вход первого.элемента И 9, первый вход второго элемента И 10, и первый вход третьего элемента И 11. Значения разрядов 81 и 82 проверочного слова являются адресными разрядами блока 5 постоянБО ной памяти. По адресу 81 82 из.блока 5 постоянной памяти считывается два слова АА уо- ь иоьБ Бр у в которых содержатсяв двоичной Форме значения местополо", .жения либо одной одноразрядной ошибки (слово.А .А о (, либо двух одноразрядных ошибок (слово бС 5 С 7 С 6 71 2 6 С 2А 1 А Яо.для первой ошибки, аслово Б 1 Брдля второйошибкф Здесь 1 о. ь 1 означаетближайшее большее целое число, и -.кодовое слово, определяемое как сумма информационных и контрольныхразрядов .При возникновении одной или двуходноразрядных ошибок считанные изблока 5 постоянной памяти кодовыеслова дешифруются в первом дешифраторе 6 (слово А 1 Аои вто 2 пром дешифраторе 8 (слово Б Боа затем в сумматоре 3 по модулюдва.происходит непосредственное исправление отказавших разрядов.В первом элементе ИЛИ 7 происходит определение неравенства нулюразрядов 81 и 82 .проверочного слова.В третьем 16 и четвертом 17 элементах ИЛИ происходит определениенеравенства нулю считанных из блокапостоянной памяти 5 кодовых словААров. (и ББ, 1 соотг Й 1ветственно.В первом 9 и втором 10 элементах И и во втором элементе ИЛИ 15происходит определение значения.вектора, ошибки контрольного разряда СО,т.е, в случае ошибки в этом разрядена выходе второго элемента ИЛИ 1,5 вырабатывается сигнал логической "1".Первый элемент И 9 вырабатывает сигнал вектора ошибки контрольного разряда СО только в том случае, когда имеется вторая ошибка в любом другомразряде .хранимого в накопителе 1слова. Второй элемент И 10 вырабатывает сигнал. вектора ошибки контроль-,ного разряда СО, когда имеется толькоодна ошибка в считанном из накопителя1 слове и она находится в контрольномразряде СО,В третьем. элементе И 11 вырабатывается сигнал о наличии трех одноразрядных ошибок в слове, считанномиз накопителя 1, причем среди них нетошибки контрольного разряда СО,1127012 7В пятом элементе И .13 вырабатывается сигнал о наличии пакетнойошибки,При этом из блока э постоян- .ной памяти считываются кодовые слова,все. Разряды которых равны логической 5В элементе ИЛИ-НЕ 14 вырабатывается управляювряй,сигнал для сумматора 3 по модулю два. При наличииодной или двух одноразрядных ошибоквырабатывается сигнал логической,"1",10который разрешает. коррекцию отказавших разрядов с помощью блока 19 эле.ментов И и блока 20 двухвходовых схемсложения по модулю два (фнг 2). Вблоке схем ИЛИ 18 происходит поразрйцт 15ное объединение соответствующих вы-,ходов первого дешифратора б ш второго дешифратора 8. При наличии треходноразрядных ошибок или пакетныхошибок, или сочетания пакетных 20ошибок с одноразрядныю вырабатывается сигнал логического "О", запрещающий коррекцию в сумматоре З,по.модулюдва.В зависимости от значений разрядфв, 258082 контрольного слова и значенийразрядов кодовых слов ААри В 1 Вро 1 возможнй случаи, приведенные в таолице.Для обнаружения сочетанийпакетных ошибок с одноразрядными необходимо, чтобы суммапо модулю два любого пакета разрядов с любым вектор-столбцом одиночного разряда Н-матрицы не равня 35лась никакому из используемых вектор-столбцов Н-матрицы или никакойсумме двух любых .вектор-столбцовН-матрицы.Различие сочетания 4-разряднойпакетной ошибки и одноразряднойошибки от двух одноразрядных ошибок, осуществляется .за счет различия разряда общей четности,Различие сочетания :-й 4-раз-рядной пакетной ошибки и )-й одноразрядной ошибки от любой одноразрядной осуществляется эа счет значения разрядов 81 контрольного слова для сочетания ошибок могут совпадать со значениями разрядов 81 контрольного слова только 1-й одноразрядной ошибки, так как разряды 81 пакетной ошибки всегда равны нулю (Н-матрица на фиг.3 и 4), значения разрядов 82 контрольного слова для сочетания ошибок всегда неравны значениям разрядов 82 контрольного слова )-й одноразрядной ошибки, так как значения разрядов 82 контрольного слова -й 4-разрядной пакетной ошибки всегда неравны нулю (Н-матрица на фиг.3 и 4).При разрядности пакетных ошибок, равной восьми, необходимо объединить два пакета по четыре разряда проверочной Н-матрицы. Все комбинации пяти, шести и семиразрядных ошибок среди восьмиразрядного пакета ошибок определяются с помощью ЭВИ.Процент обнаружения этих комбинаций ошибок равен 97-99, а для восьми- разрядного пакета - 100. Устройствопозволяет повысить достоверность хранимой в ЗУ и выдаваемой из него на обработку в другие ф устройства информации за счет того, что в нем по сравнению с прототипом происходит обнаружение пакетных ошибок и сочетания пакетных ошибок с одноразрядными. Признак наличия.обнаруживаемой, но некорректируемой"ошибки поступает на выход данного устройства и в приемном устройстве может использоваться для блокировки приема и обработки ошибочной информации.