Устройство для исправления ошибок в корректирующих кодах

 

Союз Советскик

Соцналнстнчесник

Реслублнн

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (((>903885 (6I) Дополнительное к авт. санд-ву % 796848 (22) Заявлено 10.01,80(21) 2904681/18-24 с присоединением заявки .% (23) Приоритет.

Опубликовано 07.02.82. Бюллетень (те

Дата опубликования описания 09.02.82 (5})M. Кл.

&06 Р 11/10

9кударстваваый комитет

СССР

10 делам изобретений к открытей (53) УДК681.325 (088.8) (В. М. Амербаев, Р. Г. Бияшев, А. И. Карпухин и Р. Н.gyp os (-. .:. . и" н(л (72) Авторы изобретения (7)) Заявитель (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК

В КОРРЕКТИРУЮШИХ КОДАХ

Изобретение относится к вычислительной технике и может быть использовано в усгройствах обнаружения и исправления . одиночных ошибок при производстве циклических сдвигов как влево, так и вправо на любое число разрядов.

Известно по основному авт. св.

М 796848 устройство для исправления ошибок в корректирующих кодах, содержащее блок управления, выходы которого подключены к входам сдвигателя инфор30 мационного слова, первого сдвигателя контрольного слова и генератора модуля сдвига второго контрольного слова, и второй сдвигатель контрольного слова, 15, входы которого подключены к выходам. генератора модуля сдвига, а выходы— к входам генератора модуля сдвига 513.

Недостатком этого устройства являет20 ся малая разрядность сдвигателя.

Цель изобретения — расширение функциональных возможностей устройства за счет исправления одиночных ошибок ппи циклическом сдвиге на любое число разрядов влево или вправо.

Поставленная цель достигается тем, что в генератор модуля сдвига дополни- . тельно введены три сумматора по модулю два, третий элемент ИЛИ и элементы И, причем установочные входы всех введенных элементов И подключены к соответствующим выходам блока управления, управляющие входы седьмого и восьмого элементов И соединены с соответствующим выходом второго сдвигателя контрольного слова, управляющие входы девятого и десятого, одиннадцатого и двенадцатого, тринадцатого и четырнадцатого элементов И соединены соответственно с выходами второго, третьего и четвертого сумматоров по модулю два, выходы седьмого, девятого, одиннадцатого и тринадцатого элементов И соединены с входами первого элемента ИЛИ, а выходы восьмого, десятого, двенадцатого и четырнадцатого элементов И соединены с входами второго элемента NIH, управляющие входы пятнадцатого, шестнадцатого и семнадцатого элементов И соединены с соответствующими выходами второго сдвигателя контрольного слова, управляющие входы с восемнадцатого Но двад-. цать первый элементов И соединены соответственно с выходами первого, второго, третьего и четвертого сумматоров цо модулю два, выходы с пятнадцатогс Но двадцать первый элементов И соединены с входами третьего элемента ИЛИ, выход которого соединен с соответствующим, входом второго сдвигателя контроль, то слова, соответствующие выходы которого соединены с первым и вторым входами вто- . рого и третьего сумматоров по модулю два и первым входом четвертого сумматора по модулю два, второй вход которого соединен с выходом третьего сумматора по модулю два, второй вход которого соединен " 2о выходом третьего сумматора по модулю два.

Па фиг, 1 представлена блок-схема устройства для исправления ошибок в корректирующих кодах при циклическом 25 сдвиге; на фиг. 2 — функциональная схема генератора модуля сдвига; на фиг. 3— схема блока управления.

Устройство для исправления ошибок в корректирующих кодах при циклическом Зр сдвиге на любое число разрядов вправо и влево соетоит из сдвигателя 1 информационных слоев, первого сдвигателя 2 контрольного слова„ второго сдвигателя 3 контрольного слова, генератора 4 модуля сдвига и блока 5 управления;

Генератор модуля сдвига содержит сумматоры 6 — 9 по модулю два, элементы И 10 -30, элементы ИЛИ 31, 32 и

33, входы 34 и 35, выход 36.

Блок 5 управления содержит реверсивный счетчик 37 кода сдвига на нять разрядов, делитель 38 кода сдвига на три разряда,, дешифратор 39, генератор 40 тактовых импульсов (ГТИ), элемент НЕ 41, 5 два элемента И 42 и 43 на два входа, четырнадцать элементов И 44 — 57 на три входа каждый, шесть элементов

ИЛИ 58 — 63 и входы 64 и 65 кода сдвиге.

SO

Блок управления работает следующим обравом.

При поступлении кода сдвига с входов 64 на установочные входы реверсивного счетчика 37 и на делитель 38 кода 55 сдвигa, à с входов 65 - направление сдвига на элементы И 44 - 57, дешифратор

39 выбирает соответствующий элемент

5 4

ИЛИ 58 — 63, а счетчик 37 начинает вычитать тактовые импульсы с ГТИ. При. этом элементы И 44 и 45 выдают импу« льсы сдвига соответствующего направления на сдвигатели 1 и 2, а сигнал с выбранного элемента ИЛИ 58 — 63 поступает на GOQTBeTGTBóþøèé вход генератора 4 модуля сдвига.

При установке счетчика 37 в нуль прекращается поступление тактовых импульсов через элементы И 44 — 57 и блок переходит в режим ожидания.

Устройство работает следующим образом.

При подаче управляющего сигнала на входы 34 генератора 4 модуля сдвига элементы И 10 — 30 и ИЛИ 31, 32 и

33 в соответствии с входными сигналами, поступающими с входа 35, и сигналами, вырабатываемыми сумматорами

6 — 9, генерируют выходные сигналы второго проверочного слова. Любая ошибка, возникающая в генераторе 4 модуля сдвига исправляется последующим исправляющим слбем, так как генератор 4 модуля сдвига связан только с вторым сдвигателем 3 контрольного слова.

Таким образом, генератор 4 модуля осуществляет сдвиг во втором сдвигателе контрольного слова на 1 разрядов по модулю неприводимого над 5f(2) uvo гочлена. В сдвигателе l информационного слова и в первом сдвигателе 2 контрольного слова производится циклический сдвиг на Г разрядов. После произведенного таким образом сдвига кодовое слово остается кодовым. Действительно, над полем GF (2") можно построить код (20 + 1, 2 — 1). Всегда можно подобрать поле GF (2 ) такое, что примитивным элементом этого поля будет 2. Тогда проверочные части кода определяются согласно уравнениям к K Ч-1 а„„= Ео.,= F. а-.)Ы =м =,).о и-h . x

= Х26 E Ql; (1) ,)о - Ч

Ll u-a

;-.::„,;-- . 6,О,= X. 6,2 ijc = "+" Й ьл уо

L(R ° Х

Ф Z О;;6„(П) где Ь! -- a" " """ <=-z"- < = 1 ... к

>" а

Пусть произведен циклический сдвиг на «+ разрядов, где знак "+ означает циклический сдвиг влево и вправо.

Сдвиг на + f Разрядов равносилен ум 5 003065 ножению на 2 -6 . умножим (13 и (П 3 на 2 (. Получим

+г за(. u-» jk-q (ш3 (И (3) H)

rae а„- а„° а = а, а - а г

Произведем теперь сдвиг вправо на 1 разряд и прибавим модуль многочлена P() (О, а„с4, а„} (1о113 -(а,", а") а „")1 бэ г е (" е гдеa„„=- а„а, а =a. а =а з—

То же, при сдвиге на 2 разряда (О, а,, a,,,а, " ) . (1О11}=(а,"), с г), О.")), 1 () Е (г) (г) Е где "1 =а„аг а;аг = а„-сзз= с(„сзг.

При сдвиге на 3 разряда (О, а",), О,,а" ) (1О11) =(С©а,), «Р) гдеа„=а а (з) Е

При сдвиге на 4 разряда ((о) З) „а)}, (101, } (,» с) )(о „(4) где с(„ a(z z., а =а а;сЗз=а1

При сдвиге на 5 разрядов (О, ()(;), О@) Q®} (elf) = (О(;),О(в a„ ) гдеа =а;а =а ®а;а а ®а (Л, (S) г ° аг г з 3= 1 з

При сдвиге на 6 разрядов (О, а," сф а,). (1о11) =(а®а") а")) гдеа,=а а =а®а а=а (6), (6) (6) г= » 3 3= г

При сдвиге на 7 разрядов вправо (О, Ог,аг,с)) 5 (10ц) =(e(г)()г("Ос ), () (з) (з) где a„=а„, d аг a3=аз

Объединяя 1,2 и 3 разряды второго, сдвинутого на с разрядов вправо и влево по модулю p(x) контрольного слова, получим

O „o. 0{ ÷ a a. v O Ô v (©, ()(Ф,, v ч(()(г»схД 0(„v(o„ с(г a ) 0(0 v (()(„»" 5065, а„в =Огссо Ч(а„а,5и, V(a,+(:(,)06, Ч (Q» О г С ъ5 Мъ у (р„» Ог5 о(„, ЧО «(6ЧЙ Ф, а, —— О(0(Ä V0(Äa, Ч(с(,()(з}с(,з V (с(,.а.„1(з.ь ч (а,. ог. аз)с4,ч (а„а,) о(v („()(в ) где (— сдвиг на 7(, разрядов влево или вправо;

«(.1 - сдвиг на 71 + 1 разряд e0< . или на 7 g + 6 разрядов вправо с(- сдвиг на 7(+ 2 разряда вле1 во или íà 7(+ 5 разрядов вправо;

М-1 jest <-1 а +г1рЬ)=1 Е: я . с». аi,)2. I q(x)=

j-О 6О - k-1 ц»

- Г, С, Z а»,,j р(х) = а „, (1у3 где Р () — неприводимый многочлен 10 над полем 6Г Ь) степени И, )А) р(ч)= A od р(х)

c, =)» — à — UЗ I, j= Ij — Ьц, е

f — „j- целая часть от деления 8 на и

Легко проверить, что правые части равенства (Ш) и (1У3 будут соответствовать проверочным символам а +( а к+ q после сдвига.

Рассмотрим постоение генератора модуля сдвига. При И = 3 в качестве не- 20 приводимого многочлена возьмем р )«3)(3+)(+q . Следовательно К = 7 и веса каждой группы образуют последовательность (6, 2, 7, 4, 5, 3, 13. Три разряда контрольной группы а «»,г обозначим (a>,а, a 3. Произведем сдвиг влево на 1 разряд и прибавим модуль многочлена Р(х) (Q,Î 2 О,,О} (10И}= (ОЗ,()Р Ф ) 30 р) (e) гдов,, =a; о =а 9а; а =аг (4) з ог. 1 з 3

То же, йри сдвиге на 2 разряда (OÄ O,", а„О} (1О115 -(a© а(г ), а „ }, (г) . (.г) . (г)

a, = аг «x =а Ваз; аз =а,®аз г 3 . 3S

При сдвиге на 3 разряда . (а",), а",), О,,О) + (1О11} =(O®, О",, O(,"), где сд) а®а а 3) а аа+«(° а(з =а еа

1» ь г 1 3 е) г= г 3

При сдвиге на 4 разряда ,40 с)) (3) - М О} (1O11} () а(".) (- ()) (.)(г =-С(гс, а„а,=а, а„ (4) 6)

3 а» а аг

При сдвиге на 5 разрядов (() (О 0),(1011)=(aþ,о,2",О"), (s) д Е ° (1) (3) 0) 50 где 0„- а„с» a; a. = а„,. аз о а„с(г

При сдвиге на 6 разрядов (o )Оюо 0) (1011, (Qú o2О")} («) ® (6) (6) где а„= а ®а

» г — 3 3= »

;а,а,а а

При сдвиге на 7 разрядов влево (с.,O>,О,),О}+ (1О«} = (а,", о",, о! }. (3) г» г 3 г-з

; а = а еа а = а ео @О903885,; — сдвиг на 7 + 3 разряда влево или на 7 + 4 разряда вправо; — сдвиг на 7 + 4 разряда влеЧ во или на 7 + 3 разряда вправо;

oC> — сдвиг на 7 + 5 разрядов влево или на 71 + 2 разряда вправо; С. - сдвиг на 71 + 6 разрядов вле- 10 во или на 7 - 1 вправо.

Изобретение позволяет исправлять одиночные ошибки при циклическом сдвиге на любое число разрядов или вправо при увеличении числа разрядов сдвигателя 15 цо 21.

Фор мула изобретения

Устройство для исправления ошибок в, корректирующих кодах по авторскому свидетельству l4 796848, о т л и ч а ю— щ е е с я тем, что, с целью расширения функциональных возможностей за счет rs исправления одиночных ошибок при циклическом сдвиге на любое число разрядов влево или вправо, в генератор модуля сдвига дополнительно введены три сумматора по модулю два, третий элемент 1п

)ЯИ и элементы И, причем установочные входы всех. введенных элементов И подключены к соответствующим выходам блока управления, управляющие входы седьмого и восьмого элементов И соединены с соответствующим выходом второго сдвигателя контрольного слова, управляющие входы девятого и десятого, одиннадцатого и двенадцатого, тринадцатого и четырнадцатого элементов И соединены соответственно с выходами второго, третьего и четвертого сумматоров по модулю два, выходы седьмого, девятого, один» надцатого и тринадцатого элементов H соединены с входами первого элемента

ИЛИ, а выходы, восьмого, десятого, двенадцатого и четырнадцатого элементов И соединены с входами второго элемента

ИЛИ, управляющие входы пятнадцатого, шестнадцатого и семнадцатого элементов

И соединены с Соответствующими выходами второго сдвигателя контрольного слова, управляющие входы с восемнадцатого по двадцать первый элемент И соединены соответственно с выходами первого, второго, третьего и четвертого сумматоров по модулю два, выходы с.пятнадцатого по двадцать первый элементов И соединены с входами третьего элемента ИЛИ, выход которого соединен с соответствующим входом второго сдвигателя контрольного слова, соответствующие выходы которого соединены с первым и вторым входами второго и третьего сумматоров по модулю два и первым входом четвертого сумматора по модулю два, второй вход которого соединен с выходом третьего сумматора по модулю два.

Источники информации, принятые во внимание при экспертизе

l. Авторское свидетельство СССР

М 796848, кл. G 06 Р Ll/10, 1979 (прототип).

903885

Составитель И. ;".взоь

Редактор Т. Кугрышева Техред М. Надь, Корректор Г. Назарова

Заказ 123/31 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, -35, Раушская наб., 4/5 филиал ППП "Патент", r. Ужгород, ул. Проектная, 4