Устройство для исправления ошибок в корректирующих кодах Советский патент 1982 года по МПК G06F11/10 

(54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОИИБОК В КОРРЕКТИРУЮЩИХ КОДАХ

Изобретение относится к вычислительной технике и может быть использовано в устройствах обнаружения и исправления одиночных ошибок при производстве циклических сдвигов как влево, так и вправо на любое число разрядов. Известно по основному авт. св. № 796848 устройство для исправления ошибок в корректирующих кодах, содержащее блок управления, выходы которого подключены к входам сдвигателя информационного слова, первого сдвигателя контрольного слова и генератора модуля сдвига второго контрольного слова, и второй сдвигатель контрольного слова, . входы которого подключены к выходамгенератора модуля сдвига, а выходы к входам генератора модуля сдвига tl. Недостатком этого устройства являет ся малая разрядность сдвигателя. Цель изобретения - расширение функциональных возможностей устройства за счет исправления одиночных ошибок пои циклическом сдвиге на любое число разрядов влево или вправо. Поставленная цель достигается тем, что в генератор модуля сдвига дополнительно введены три сумматора по модулю два, третий элемент ИЛИ и элементы И, причем установочные входы всех введенных элементов И подключены к соответствующим выходам блока управления, управляющие входы седьмого и восьмого элементов И соединены с соответствующим выходом второго сдвигателя контрольного слова, управляющие входы девятого и десятого, оди ннадцатого и двенадцатого, тринадцатого и четьф- надцатого элементов И соединены QOOT ветственно с выходами второго, третьего и четвертого сумматоров по модулю два, выходы седьмого, девятого, одиннадцатого и тринадцатого элементов И соединены с входами первого элемента ИЛИ, а выходы восьмого, десятого, двенадцатого и четьфнадцатого элементов И соедршены с входами элемента ИЛИ, ynpGJ3J-rarouMe входы 1итнадцатого9 шестнад цатого и семнадцатого элементов И соединены с соответствующими выходами второ го сдвигателя контрольного слова, управляющие входы с восемнадцатого по двад- цать первый элементов И соединены соот ветственно с выходами первого, второго, третьего и четвертого сумматоров по модулю два, выходы с пятнадцатого по двадцать первый элементов И соединены с входами третьего элемента ИЛИ, выход которого соединен с соответствующим входом второго сдвигателя контрольного слова, соответствующие выходы которого соединены с первым и вторым входами вто .рого и третьего сумматоров по модулю дв и первым входом четвертого сумматора по модулю два, второй вход которого соедине с выходом третьего сумматора по модулю два, второй вход которого соединен с выходом третьего сумматора по модулю два, . На фиг. 1 представлена блок-схема устройства для исправления ошибок в корректирующих кодах при циклическом сдвиге; на фиг. 2 - функциональная схема генератора модуля сдвига; на фиг. 3 схема блока управления. Устройство для исправления ошибок в корректирующих кодах при циклическом сдвиге на любое число разрядов вправо и влево состоит из сдвигателя 1 информационных слоев, первого сдвигателя 2 Контрольного слова, второго сдвигателя 3 контрольного слова, генератора 4 модуля сдвига и 6ло1са 5 управления. Генератор модуля сдвига содержит сумматоры 6 - 9 по модулю два, элементы И Ю-30, элементы ИЛИ 31, 32 и 33, входы 34 и 35, выход 36/.БЛОК 5 управления содержит реверсив ный счетчик 37 кода сдвига на пять раз рядов, делитель 38 кода сдвига на три разряда,, дешифратор 39, генератор 40 .тактовых импульсов (ГТИ), элемент НЕ 41 два элемента И 42 п 43 на два входа, четырнадцать элементов И 44 - 57 на три входа кшкдый, шесть элементов ИЛИ 58 - 63 и входы 64 и 6 5 кода сдв . Блок управленияработает следуюцщм обраеом. При поступЛении кода сдвига с входов 64 наустановочные входы реверсивного счетчика 37 и на делитель 38 кода сдвига, а с.входов 65 - направление сдв га на элементы И 44-57, дешифратор 39 выбирает соответствующий элемент ИЛИ 58-63, а счетчик 37 начинает вычитать тактовые импульсы с ГТИ. При. этом элементы И 44 и 45 вьщают импульсы сдвига соответствующего направления на сдвигатели 1 и 2, а сигнал с выбранного элемента ИЛИ 58 - 63 поступает на соответствующий вход генератора 4 модуля сдвига. При установке счетчика 37 в нуль прекращается поступление тактовых импульсов через элементы И 44 - 57 и блок переходит в режим ожидания. Устройство работает следующим образом. При подач управляющего сигнала на входы 34 1 енератора 4 модуля сдвига элементы И 1О - 30 и ИЛИ 31, 32 и 33 в соответствии с входными сигналами, поступающими с входа 35, и сигналами, вьфабатываемыми сумматорами 6 9, генерируют выходные сигналы второго проверочного слова. Любая ошибка, возникающая в генераторе 4 модуля сдвига исправляется последующим исправляющим слоем, тш как генератор 4 модуля сдвига связан только с вторым сдвига- телем 3 контрольного слова. Таким образом, генератор 4 модуля осуществляет сдвиг во втором сдвигателе контрольного слова на . разрядов по модулю неприводимого над GF{2l многочлена. В сдвигателе 1 информационного слова и в первом сдвигателе 2 контрольного слова производится циклический сдвиг на 6 разрядов. После произведенного таким образом сдвига кодовое слово остается кодовым. Действительно, над полем GF (2) можно построить код (2 + i, 2 - 1). Всегда можно подобрать поле Q (2) такое, что примитивным элементом этого поля будет 2. Тогда проверочные части кода определяются согласно уравнениям o,., .jSJu-л . к vs-л « - aij6v, ,; , -1, Пусть произведен циклический сдвиг ыа ± i разрядов, где знак означает циклический сдвиг влево и вправо, Сдвиг на + разрядов равносилен ум5 ;j U3eножению на 2-2 . Умножим (l) и (П) ца 2±С . Получим W-1 .,, км2 а,„ 2 ai JO i-o J /-0 .е-i,-. .. ,ilPtx l aiji |PCx) ,- j- ui - 1Ц 2. 0(i,j р(х) , (1У) где ) - неприводимый многочлен« над полем-G F U) степени И, ..,.РЫ е 1 , . ITTJ- целая часть от деления ца и. Легко проверить, что правые части 15 равенства (JJI) и (1У) будут соответствовать проверочным символам с1ц+1 , «к+г после сдвига. Рассмотрим постоепне генератора модуля сдвига. При И 3 в качестве не- 20 1ФИВОДИМОГО многочлена возьмем . Следовательно К 7 и веса каждой группы образуют последователыюсть (6,2,7,4,5,3,1). Три разряда контрольной группы обозна- 25 чим («301г «1 ) Произведем сдвнг влево на I разряд и прибавим модуль многочлена Р(х) (a5,aj,a,,0)v(lOH)-(, 30 где ,® а,; а; а . То же, при сдвиге на 2 разряда (a,a.ai,o)vOov04Q,af, / tti г. , г . 1 у. где о(| а, ; а,®а,; .®а, .« При сдвиге на 3 разряда V :(а, a1,a,,o), a,), где a. af a,; oif o.. «f a ®a,. При сдвиге на 4 разряда ,, .XV , X , п 0 Q (, W|, .uj iuAT; iMb , -г ,( J .а2, где , ; .®а,®о1, a,®aj, ; af .j®aa . При сдвиге на 5 разрядов (af,,o)4wi) (a,), (O ®cs)(5) ® ,raeala cxfa ; a, a,. a а,®сх При сдвиге на 6 разрядов (,0)(Ol1)-{af,af,af), где afl o,,«a ; af «3 ; ajl at, . При сдвиге на 7 разрядов влево . ,. , X Q,,Qj,of,0) (Ю11Ха 4,аГ). 56 mШО) f l Oj 3 O(j .- Произведем теперь сдвнг вправо на I разряд и прибавим Модуль многочлена PC) (.,Q..Q,)4ioii)), rAeo,.,®«, Jaf-o., To же, гфи сдвиге на 2 разряда (0,a,,Qi ) ( Q i / s 2 де-,На,ва,е„ ;af-a, ;afla,ea,. „ При сдвиге на 3 разряда (О, ,)(31l) (a,), гае ; а ; ai . При сдвиге на 4 разряда . , чч / « М й,К (O,af ,) (lOH)(.,af), где а Л ®а г. - г г г -313 р разрядов . ,, .х ,; (,, af )4l01T)4ft«)( Х$5)), где af а ; о4 а,® ;afia,®a, при сдвигейа е разрядов /0.a,cx,) « «Г о., ,®aj ; afl о,, При сдвиге на 7 разрядов вправо , ч, (O, ) C Jq/taJ)). ,де..„( „., «f, «, ; af a, Объединяя I 2 и 3 разряды второго. .сдвинутого на i разрядов вправо и влеВО ПО модулю pfx) контрольного слова, i 1 получим Ло«.ч lOfovaiOt vajai ,, v(Q,)oC5V(cx,a,) dcaag vCcx.,a..)oiA v()ot, v ()о1.,, )ot vaAsVCXbCSCe, a,,, -a3,aoV6c,(a,vai)ot, v )ь v(:a,v,)i,v Wt vcx ос. V,, « «Co - «двиг на 7i разрядов влево jjjjjj вправо; oC,, СДВКГ на 7i + 1 разряд влево . или на 7i + 6разрядов вправо;. оС, - сдвиг на 7i + 2 разряда влево или на 7t + 5 разрядов вправо; 7 . + 3 разряда - сдвиг на 7 во или на 7| + 4 вправо; о(,ц - сдвиг на 71 + 4 расзряда вле во или на 7( + 3 разряда вправо; . - сдвиг на 7{ 4-5 разрядов влево или на TI +2 рафада вправо; оСл- сдвиг на 7-i +6 разрядов вле во или на 7t - 1 вправо. Изобретение позволяет исправлять оди ночные ошибки при циклическом сдвиге на любое число разрядов или вправо при увеличении числа разрадов сдвигателя до 21. Формула изобретения Устройство для исправления ошибок в корректирующих кодах по авторскому сви детельству № 796848i отличающееся тем, что, с целью расширени функциональных возможностей за счет исправления одиночных ошибок при цикли ческом сдвиге на любое число разрядов влево или вправо, в генератор модуля сдвига дополнительно введены три сумматора по модулю два, третий элемент ЯЛ И а элементы И, причем установочные входы всех введенных элементов И подключены к соответствующим выходам бл ка управления, управляющие входы седьмого и восьмого элементов И соединены с соответствующим выходом второго сдвигателз контрольно1 о слова, управляю 9 8 щие входы девятого и десятого, одиннадцатого и двенадцатого, тринадцатого и четырнадцатого элементов И соединены соответственно с выходами второго, тре тьего и четвертого сумматоров по модулю два, выходы седьмого, девятого, один надцатого и тринадцатого элементов И соединены с входами первого элемента ИЛИ, а выходы .восьмого, десятого, двенадцатого и четырнадцатого элементов И соединены с входами второго элемента ИЛИ, управляющие входы пятнадцатого, шестнадцатого и семнадцатого элементов И соединены с Соответствующими выходами второго контрольного слова, управляющие входы с восемнадцатого по двадцать первый элемент И соединены соответственно с выходами первого, второго, третьего и четвертого сумматоров по модулю два, выходы с. пятнадцатого по двадцать первый элементов И соединены с входами третьего элемента ИЛИ, выход которого соединен с соответствующим входом второго сдвигателя контрольного слова, соответствующие выходы которого соединены с первым и вторым входами второго и третьего сумматоров по модулю два и первым входом четвертого сумматора по модулю два, второй вход которого соединен с выходом третьего сумматора по модулю два. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № 796848, кл. (3 06 F И/10. 1979 (хфототип).

36

фиг. Z