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

.К ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(71) Киевский ордена Ленинанический институт им. 50-леткой Октябрьской социалистичесреволюции(56) Авторское свидетельство СССРНф 470866, кл. С 11 С 29/00, 1976.Е 1 есегопдс епдыеег 1 пя (.Зг.Вт,1979, Ч,5 1, У 617, с. 49, 52-53,(54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С ИСПРАВЛЕНИЕМ ОШИБОК(57) Изобретение относится к области вычислительной техники и можетбыть использовано в запоминающихсистемах повышенной надежности, выполненных на функциональных узлахс большой и средней степенью интеграции. Цель изобретения состоит вповышении надежности устройства засчет исправления двукратных ошибоки обнаружения ошибок произвольнойкратности. Устройство содержит блоккодирования, накопитель, блок коррекции, блок декодирования, элементИЛИ-НЕ, сумматоры, элементы ИЛИ,блок сравнения, счетчик, элемент И,дешифраторы, дополнительный блокпамяти. В устройстве используетсяБЧХ-код, исправляющий двукратныеошибки. 3 ил,С =ЕС ния 50 Изобретение относится к вычислительной технике и может быть использовано в запоминающих системах повышенной надежности, выполненных на функциональных узлах с большой и средней степенью интеграции.Целью изобретения является повы-шение надежности устройства за счет исправления двукратных ошибок и обнаружения ошибок произвольной кратности.На фиг.1 представлена структурная схема запоминающего устройства, на фиг.2 - один из возможных вариан 1тов блока кодирования, на фиг.З - один из возможных вариантов блока декодирования.Запоминающее устройство содержит блок 1 кодирования, вход 2 которого связан с выходом информационной магистрали, а выход подключен к накопителю 3, имеющему направляющий вход 4, выход накопителя 3 подключен к первому входу 5 блока,б коррекции и к блоку 7 декодирования, выход 8 блока 7 соединен с элементом ИЛИ-НЕ 9, выход которого связан с управляющим входом блока 6, с первым входом 10 первого сумматора 11 по модулю два, с входами первого элемента ИЛИ 12, второй выход 13 блока 7 подключен к первому входу 14 блока 15 сравнения, связанного с вторым элементом ИЛИ 16, первыйвход 17 второго элемента ИЛИ 16 соединен с выходом элемента ИЛИ 12, а второй вход 18 - с первым выходом 19 блока 15., выход элемента ИЛИ 16 подключен к первому входу 20 счетчика 21, выход 22 которого связан с вторым входом 23 сумматора 11, а выход 24 - с первым входом 25 элемента И 26, имеющего индикаторный выход 27, к второму входу 28 элемента И 26 подключен выход 19 блока 15, выход 22 счетчика 21 соединен с вторым входом 29 треть" его элемента ИЛИ 30, а также с вторым дешифратором 31 ошибки, выход которого подключен к третьему входу 32 блока 6, выход 33 сумматора 11 связан с первым дешифратором 34 ошибки, вы.ход которого соединен с вторым вхо" дом 35 блока 6 и с первым входом 36 элемента ИЛИ 30, выход элемента ИЛИ 30 соединен с входом блока 37 дополнительной памяти, выход которого подключен к входу второго сумматора 38 по модулю два, выход 39 которого связан с вторым входом 40 блока 15, второй выход 41 блока 15 соединен с вто 5 О ,15 20 25 30 35 рым входом 42 счетчика 2 1, а также с управляющим входом 43 дешифратора 34 и с управляющим входом 44 дешифратора 31, Выход 45 блока 6 подключен к входу информационной магистрали.На фиг,2 представлен блок кодирования для кодирования 7-разрядного слова в соответствии с таблицей кодирования для БЧХ-кода исправляющего две ошибки, Блок состоит из двухвходовых сумматоров 46-62 по модулюдва,На фиг.З приведен вариант построения блока 7 декодирования при п =15 разрядов (1- длина слов, хранимых в накопителе 3), Блок состоит из двухвходовых сумматоров 63-105 по модулю два, к входам которых подключены соответствующие разряды слова, удовлетворяющие таблице декодирования для БЧХ-кода, исправляющего двукратные ошибки.Блок 6 коррекции представляет собой регистр, входы которого связаны с выходами накопителя 3 и выходами дешифраторов 31 и 34, имеющими по Ф входов (2 -1=в). Сумматоры 11 и 38 имеют п 1 входов. Блок 37 дополнительной памяти состоит из 2 щ -разрядных быстродействующих регистров. Счетчик 21 имеет п входов и 2 состояний.В устройстве используется БЧХ-код длины О =2 -1 (в - целое положительное число), исправляющий две ошибки. Порождающая матрица 6 размерности 1 сп Ь:=иш) такого кода может быть представлена в виде где Е - единичная матрица размерности Ы 1, С - подматрица размерности 1 п, строки которой представляют собой остатки от деления единицы с нолями на порождаемый полином кода.В соответствии с матрицей Ц строят блок 1 кодирования.Пустьпроизвольное 1 -разрядное число 7=0 Ч 2, У,) . Произведение l на ( задает операцию кодировагде Ф - кодовое слово, С; - контрольные символы, Контрольный символ С; равен сумме по модулю два содержимого тех разрядов исходного слова М, которым соответствуют единицы в 1 -м1столбце подматрицы О . Для кода дли"1226536 Остатокпод номером 1 (в кружочке)соответствует 1 -й строке подматрицы 6 . Тогда порождающая матрицадля рассматриваемого примера равна 5 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1 0 0 0 0 0 011101000 7 0 1 0 0 О 0 00111010061 О О О 1 О О О 0001110105 0 0 0 1 0 0 0000111014 Я ноооон 111010001 Д 2 03 0 0 0 0 1 0 0111001103 111010001 1001 0 1 0 0 0 0 0 0 0 0и исходястроена та 0 111 о го мож кодиров т быть пония. нтрольнь азряды 6 5 к Ят=Н ьЯг (вания) и содп 1 координатлокаторова вторыеа дают суммокаторов исфи -лов, то таблицей построенна фиг.2. Значениядов равны сумме пжимого подчеркнуть пера 2 п 1 к исправляюцего дв ая матрица Н раз а; з; ( =1-:и) первых собой всевозмож ныещ -мерные ве 5д 5 рде столбць пр едставля 1 Е НЕ где +означа Ь и операцию сложен левые дво по модулю два.ДекодированиеделенииипЛокаторы рассматвые элементы поленные в виде двстепени, меньшейкоторого неприво локаторы),Вторая гр аким образозаключается в опрео известным О, и 5 риваются как ненулеля СР(2 ), представоичных многочленовв 1, от корня К недимого многочлена Ф строаждый троится лбец яв одимого запиа чт по мляется кубо епе многочлена ст санного в этостроках. Синд ком 7) принят ся бло- ределяом го ны 11 =15, исправляющего две ошибки, порождающий полином(х) равен (х)=х +х +х +х +1 или 1110100011Тогда строками подматрицы 6 являются следующие остатки от деления оооооооооооаоо иоооо111010001 азряды исходного слова 7654321 В соответствии с блок кодирования контрольных разр модулю два содер разрядов,Для БЧХ-кода, ошибки, провероч ности 2 ш и задается в виде ется к спонир Первые 46 ход 8) зиций,синдро кубов Если 45 разрядция траноординат,у Б, (вых понатод 13)позиций,каженных дают сумм искаженны в коорди У б (вых аженных аторы ис(2) где- корень неприводимого много 4члена х +х +1, Каждой из 15 позицийкода однозначно сопоставлен локаториз доля ГР (16). Каждый элемент(к-. Ы) в этом поле является степенью Ы и однозначно представляется в виде многочлена от сс степени, меньшей 4 (табл.1).)Таблица 1 Позиция Многочлены от ж Локаторыкода (элементы поля) в, предст. дес.предст. 0001 0010 0100 1000 0011 0110 1100 1011 0101 1010 0111 11101 1101 г (1 Мф =О 1 М. "-Ы 1,вз, г 12 О =О +Ы, =К+1б 10 10 и Ь г 12 0 фК 0 +ОЧК =0 +К 1к1% 13 14 1001 15 ления " на неприводимый многочлен+ М +1, а многочленам от ж однозначй Представление элемента М" в виде многочлена отравно остатку от де 3 1226536 бстеПени а . Это представление уста- да будет совпадать со степенью ю навливает такое соответствие между (нумерация позиций начинается с 1). разрядами слова и локаторами, при Если и =2 -1=15, то проверочная котором уменьшенный на 1 номер развя- матрица представляется в виде1226536 12 10 Синдром старшие разряды В В, - Вмладшие разряды но соответствуют двоичные числа, Элементы матрицы (2) в нижней строке яв 1ляются кубами элементов верхней строН 9 13 15 14 7 1 О 5 15 10 12 8 1 15 1 О или в двоичном представлении 1 1 1 1 О 1 О 1 1 О О 1 О О О 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 111 гог гггог 11 го 1 О 1 О 0 1 0 1 0 0 1 0 1 0 0 110001 100011000 1 0 0 0 1 1 0 0 0 1 1 0 0 О 1 Единицы в-й строке матрицы Н указывают, какие разряды принятого слова входят в 1 -е контрольное соотношение. Это позволяет построить таблицу декодирования1 разряды принятого слова 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1Синдром равен Я в ,Я В В В В В В В, значение В равно сумме по модулю два содержймого соответствующих ему (подчеркнутых) разрядов. В соответствии с таблицей декодирования построен блок 7, представленный на фиг. 3,Найдемиз первого уравнения системы (1)=Б,+В и подставим во второе+(51 +г 3)=У, Зададимся определенным значением гз и вычислим У. Если У=52, то Р - локатор ошибочноГо разряда, тогда б, + - локатор другого ошибочного разряда. Для вычисления величины У используется блок 37, В КОТОРОМ ПО аДРЕСУ Х Ь -1 л -РаЗРЯД- ное число) записана величина хпо модулю неприводимого многочлена степени е, и в - разрядный сумматор 38, на выходе которого появляется вели 15 20 25 30 35 40 45 50 55 ки, находящихся в тех же столбцах.Например, для эле 1 ентаа:(к )з =-Ыб, й з 13- Следовательно,12 6 3 8 4 2 1 8 1 15 10 12.8 1 чина У. При 11 =15 соответствие между адресами ячеек блока 37 и их содержимым имеет вид х 0 1 . 2 3 4 5 6 7 8 9 10 1 1 12 13 14 15 Объем блока 37 равен 2"1 н -разрядных двоичных чисел. Придавая 13 последовательные значения, начиная от1 (на счетчике 21), вычисляя У исравнивая У и 5 , можно найти такоезначение, при котором У = 5 Р .Подлежащее записи (11-2 и) -разрядное слово поступает на блок 1, гдекодируется и записывается в накопитель 3,Чтение слова инициируется подачейуправляющего сигнала на вход 4. Считанное слово поступает в блоки 6 и 7.Если. считанное из накопителя слово не содержит ошибок, то о, .=0 исигнал с выхода элемента ИЛИ-НЕ 9разрешает выдачу слова из блока б,При наличии ошибок (5,3 бо) счетчик21 устанавливается в состояние "1",Код, содержащийся в счетчике 21 (локатор), складывается на сумматоре11 с 5 К блоку 37 производятсядва обращения: по адресу Р (выход22 счетчика 21, равному состояниюСчетчика, и по адресу 5, + ф (Результат суммирования на сумматоре11, т.е. выход 33). На сумматоре38 производится сложение по модулюдва двух считанных из блока 37 слови (5,+г)з. Если результат суммирования У (выход 39) равен 5 (выход 13), то сигнал с выхода 41 блока 15 разрешает дешифрование кодовга (выход 22) и 5, + 13 (выход 33 сумматора 11), поступающих на дешифраторы 31 и 34 соответственно, производится коррекция, а счетчик 21 повходу 42 устанавливается в "О"Подключение выходов дешифраторов 31 и34 задает табл.1. Номерам выходовдешифраторов, записанных в четвертом столбце, соответствуют номеравходов блока 6, записанные в первомстолбце, Если блок 15 не зафиксиру 1226536ет равенства кодов, то сигнал с выхода 19 через элемент ИЛИ 16, пас гупая на вход 20 счетчика 21, устанавливает его в следующее состояние (увеличивает на 1), и перечисленные операции повторяются,Если за и тактов равенство У= 5 не будет зафиксировано, то по совпадению сигналов с выхода 19 блока 15 и выхода 24 счетчика 21 с выхода 27 о элемента И 26 в центральное устройство управления поступает управляющий сигнал Ошибка". Этоозначает что считанноеиз накопителя слово содержит ошибку кратности три и более,;П р и м е р. Пусть необходимо записать в накопитель слово765432101100Блок 1 формирует значения контрольныхразрядов в соответствии с таблицейкодированияС =1+1+0=0 (сигнал на выходе сумматора 48 по модулю два равен единицесигнал на выходе сумматора 59 равеннулю),С=1+0+1=0 (сигнал на выходе элемен 4.та 49 равен единице, элемента 58 -нулю),С =0+ 1+0=1 (в формировании С участ 5вуют сумматоры 51 и 5).С 4=1+1+1= (сумматоры 50 и 56),С=О+1+1+1+О= (сумматоры 48, 50,55 и 62),Сь =1+0+ 1+0+1= (сумматоры 47, 49,54 и 61),С=1+О+О+1+0=0 (сумматоры 47, 48,53 и 60),С =1+0+0=1 (сумматоры 46 и 52)8В накопитель записывается слово1 0 1 1 0 1 0 1 0 1 1 1 1 0 0Пусть при чтении получено число15 14 1312 11 10 9 8 7 6 5 4 3 2 11 0 0 1 О010111000,содержащее ошибки в 3 и 3 разрядах, которое поступает в блоки 6 и 7, вычисляющие значение синдрома в соответствии с таблицей декодирования:В =1+0+0+1+1+1+0+1=1 (сумматоры 636, 65, 66, 83, 84 и 97),В =0+0+1+0+0+0+1+0=0 (сумматоры 6467, 69, 85, 86 и 98),В=-ОО1+1+1+0= (сумматоры 70,71, 72, 64, 87, 88 и 99),В=1+О+О+О+О+ 10= (сумматоры 63,73, 74, 75, 89, 90 и 100),В =1+0+0+1+1+0+1+0+1+1+0+0=0 (сумматоры 64,63,66,76,77,78,91,92,93,101 и 102),В., =1+0+1+1+1+0=О (сумматоры 79, 80,94, 81 и 1 ОЗ),В, = 1+0+1+0+1+1=0 (сумматоры 63, 76,77, 95 и 104),В =1+0+1+1+1+0=0 (сумматоры 70, 72,82 96 и 105),т. е. 5 =1011, 5, =0000.Единичный сигнал с выхода элемента ИЛИ 12 проходит на выход элемента ИЛИ 16 и устанавливает счетчик 21 в состояние (1)=(0001) , Код 0001 с вьхода 22 счетчика 21 через элементы ИЛИ 30 поступает на вход блока 37, откуда считывается код 0001 (1-1), Сумматор 11 по модулю два складывает коды 0001 + 1011 = 1010, По адресу 010 из блока 37 считывается код 1111, и таким образом на выходе 39 сумматора 38 появляется код 0001 + 1111 - 1110, которыи вместе с кодом ОООО (выход 13 блока 7) гоступает на блок 15. Так как эти коды не равны, то сигнал с выхода 19 блок:а 15 устанавливает счетчик 21 в состсяние (2)=.(0010) , Из блока 37 по адресу 0010 считывается код 1000, а по адресу 1011 + 00 10 =1001 (результат суммирования б,и состояния счетчика 21 на сумматоре 11) код 1111, которые складываются на сумлаторе 38 1000 + 1111 = 0111. Блок 15 снова определяет неравенство сравниваемых кодов, Счетчик 21 устанавливается в состояние (3), = =(0011) . По адресу 0011 из блока 37 считывается код 1111, а по адресу 1011 + 0011 =.- 1000 - код 1010, т,е, на выходе 39 появится слово 1111 +1010 = 0101, не равное В, Блок 15 зафиксирует равенство лишь тогда, когда состояние счетчика 21 будет равно (4), =000, Действительно, из блока 37 по адресу 0100 считывается код 1100, а по адресу 1011 + 0100 - 1111, вычисленному на сумматоре 11, - код 100. Тогда на выходе 39 сумматора 38 появится код 0000 и блок 15 зафиксирует равенство. Сигнал с вьхода 4 блока 15 устанавливает счетчик 21 в исходйое состояние и разрешает дешифрование на дешифраторах 31 и 34 кодов 0100 и 1111 соответственно. Но четвертому выходу де 12265361226536 оставитель О.Кулаковехред И,Попович КорректорС.Шекмар актор А.Шандор каз Проектна Производственно-полиграфическое предприятие, г. Ужгор 2140/52 Тираж 543 ВНИИПИ Государственн по делам изобрете 113035, Москва, Ж, РПодписноего комитета СССРий и открытийушская наб., д. 4/5