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

 

ОПИСЛНИЕ

ИЗОБРЕТЕНИЯ

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

Сециапистическии

Республик 1796848 (61) Дополнительное к авт. саид-ву (я)м. К„.з (22) Заявлено 120179 (21) 27136 84/18-24 с йрисоединением заявки Hо(23) ПриоритетG 06 F 11/10

Государственный комнтет

СССР но делам нзобретеннй и открнтнй

Опубликовано 15..10,81, Бюллетень ЙЯ 2

Дата опубликования описания 15,03„81 (53) УДК 81. 3 . (088. 8) В. М. Амербаев, Р. Г. Бияшев, A. И. Карпухин и P. Н . Нугманов (72) Авторы изобретения (73) Заявитель (54 ) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК

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

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

Известно устройство для исправления ошибок в корректируктних кодах при циклическом сдвиге вправо и влево; которое содержит сумматор по модулю три или семь, узлы коррекции, входы которых соединены с выходами контрольных и информационных разрядов à t5 . выходы — c входами сумматора Q, Недостатком этого устройства является невозможность формирования контрольных разрядов для исправления одиночной ошибки. 20

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

Недостатками этого устройства являются его сложность и повышенная стоимость»

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

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

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

796 848 входы первого и второго, третьего и четвертого, пятого и шестого элементов

И соединены с соответствующими входами блока управления, управляющие входы первого и шестого, второго и третьего элементов И подключены к соответствующим выходам второго сдвигателя контрольного слова и сумматора по модулю два, выход которого соединен с управляющими входами четвертого и пятого элементов И, выходы первого, третьего и пятого элемен- 10 тов И подключены к соответствующим входам первого элемента ИЛИ, а выходы второго, четвертого и шестого элементов И подключены к соответствующим входам второго элемента ИЛИ, выходы первого и второго элементов

ИЛИ являются соответствующими входами второго сдвигателя контрольного слова.

На фиг. 1 представлена блок-схе- Щ ма устройства, на фиг. 2 — электрическая схема генератора модуля сдвига контрольного слова.

Устройство содер>кит сдвигатель информационного слова 1, первый и второй сдвигатели контрольного слова 2 и 3, генератор модуля сдвига контрольного слова 4, блок управления 5, сумматор по модулю два 6, первый и второй управляющие входы генератора модуля сдвига контрольного слова 7 и 8, первый, второй, третий, четвертый, пятый и шестой элементы И 9, 10, 11,: 12, 13 и 14, четвертый, второй и третий установочные входы генератора модуля сдвига контрольного слова 15, 16 и 17, первый и второй элементы ИЛИ 18 и

19.

Контрольное слово, передаваемое вместе с информационным, служит: 40 .совместно с последним для выявления и исправления ошибок в соответствии с применяемым корректирующим кодом (например, обобщенным кодом Хэминга), т. е. между информациОнным и контрольным словами существует некоторое соответствие. Однако при циклическом сдвиге в информационном и контрольном словах в общем случае это соответствие нарушается, т. е. кодо. вое слово, состоящее из информационного и контрольного слов, перестает быть кодовый и, следовательно, одиночная ошибка, возникшая в нем, может быть неисправлена.

Изобретение позволяет путем формирования особым образом контрольных разрядов (контрольного слова) при циклическом сдвиге на любое число разрядов обеспечить соответствие между информационными и контрольными слова- 60 ми.

Соотношение между контрольным словом, передаваемым вместе с исходной информацией (а „, а„ + ), и контрольным словом после операции сдвига 65 а,„, а К„1 ) для первого контрольного слова равно

<е т. е. в первом контрольном слове сдвиг производится также циклически, в ту же сторону и на то же число разрядов.

Для второго контрольного слова

=/2 а /Р (х)>, (2) т. е. во втором контрольном слове сдвиг производится по модулю неприводимого многочлена над полем

GF,(2") P (x) . Здесь + g — число сдвигов влево или вправо, n — разрядность сдвигателя.

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

При подаче иэ блока 5 сигнала сдвига на 1 разрядов в сдвигателях 1 и 2 производится циклический сдвиг на р разрядов в соответствующую сторону, а в сдвигателе 3 осуществляется сдвиг на Р разрядов по модулю неприводимого над GF(2) многочлена.

После произведенного таким образом сдвига кодовое слово остается кодовым.

Построение генератора 4 зависит от значения и от вида неприводимого над 6Р(2) многочлена степени и . При

n=2 неприводимым многочленом будет

Р(х) = x +x+ 1, корень которого 2 является примитивным элементом поля GF(22).

Генератор 4 работает следующим образом.

При подаче установочных сигналов (число необходимых сдвигов) от блока 5 на входы 15, 16, 17 элементы

И 9, 10, 11, 12, 13 и 14 и элементы ИЛИ 18 и 19 осуществляют коммутацию входов и выходов сдвигателя 3, что позволяет изменять модуль сдвига в соответствии с необходимой коррекцией контрольного слова.

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

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

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

1б

Составитель И. Алексеев

Редактор К. Волощук Техред М.Голинка Корректор С. Шекмар

Заказ 9771/67 Тираж 754 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент"„ г. Ужгород, ул. Проектная, 4 тора по модулю два, первого и второго элементов ИЛИ, и элементов И, причем, установочные входы первого и второго третьего и четвертого, пятого и шестого элементов И соединены с соответствующими выходами блока управления, управляющие входы первого и шестого, второго и третьего элементов И подключены к соответствующим выходам второго сдвигателя контрольного слова и сумматора по модулю два, выход которого соединен с управляющими входами четвертого и пятого элементов И, выходы первого, третьего и пятого элементов И подключены к соответствующим входам первого. элемента ИЛИ, а выходы второго, четвертого и шестого элементов И подключены к соответствующим входам второго элемента ИЛИ, выходы первого и второго элементов ИЛИ являются соответствующими входами второго сдвигателя контрольного слова.

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

1. Путинцев Н. Д. Аппаратный контроль управляющих цифровых вычислительных машин, М., "Советское радио", 19бб, с. 171-183.

10 2. Фон Нейман Дж. Вероятностная логика. Сб. Автоматы. "Иностранная литература", 1956, с. á8-140.

3. Франци Т. A. ßíáûõ Г. Ф. Избыточность в электронных дискретных устройствах. Л., "Энергия", 1979, с. 227-235 (прототип).