Устройство для обнаружения и исправления ошибок арифметичных преобразований полиномиальных кодов

 

ИЗОБРЕТЕН ИЯ кй1 е,н т н о-,, . сон;и нбл Q "м

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

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

Республик (11) 542194.

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

61) Дополнительное к авт. свид-ву— (22) Заявлено 25.06.75 (21) 2152634/24 с присоединением заявки №вЂ” (23) Приоритет (43) Опубликовано 05.01.77..Бюллетень № 1 (45) Дата опуоликования описания30.03.77 (51) М. Кл.е („06 F ll/00

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

Совета Министров СССР

Il0 делам изобретений н открытий (53) УДК 681 326.,7 (088.8) (72) Авторы изобретения

В. М. Амербаев, № Н. Белова, P. Г. Бияшев, Ю. Н. Черкасов и Э. И. Альзамарова

Институт математики и механики AH Казахской CCP (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ

ОШИБОК АРИФМЕТИЧНЫХ ПРЕОБРАЗОВАНИЙ

ПОЛИ НОМИАЛЬНЫХ КОДОВ

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

Известно устройство для обнаружения и исправления ошибок в непозиционной систе ме счисления - системе счисления остаточных классов (1) .

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

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

Белью изобретения является повышение быстродействия устройства pJIs обнаружения и исправления ошибок в кодах

Лагранжа за счет использования параллельных сумматоров по модулю два.

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

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

5421 94

В результате получается (и, к) — код) названный кодом Лагранжа, для обнаружения и исправления d ошибок, которым необходимо и достаточно 2»(. избыточных символов.

Рассмотрим процедуру декодирования одиночной ошибки (под одиночной ошибкой понимается ошибка в символе) при двух бО блоков анализа на нуль, выходы которых соединены со входами двух блоков-хранения констант исправления и блока анализа на нуль, Выходы двух блоков хранения констант исправления соединены с первым и вторым входами третьего сумматора по модулю два, выход которого является выходом устройства. Вторые входы двух дополнительных блоков анализа на нуль и третий вход третьего сум- к,) матора по модулю два являются входами устройства.

На чертеже показана блок-схеМа устройства для обнаружения и исправления ошибок арифметичных преобразований IIoëèíoìèàëbных кодов. При описании алгоритма декодирования в кодах Лагранжа введена следующая символика. множество всех элементов поля Р,, уйорядоченных некоторым образом:

uu,с » с...ссо„(Все подмножества множества ) упорядочены в соответствии с порядком 3»

У 11 — подмножество из w элементов множества Э 25

3 — подмножество из )С элементов мнок

-жества „„ с Э„ — дополнение множества к до Э„„.

Припс — 1 существует единственный многочлен f (к) ЕР,(Х) степени и такой, что З() он принимает при и+» различных значениях переменной x и „, и>,,... N„E, 7„заданнь е значения 3 iw ), 3 (ю. ),..., 5(ur ).

Этот многочлен определяется интерполяционной формулой Лагранжа. 35

f (X.) = Е f (ca ) ), (7 ), (i )> где к=о (к) (x-и о)... (х-»27<» )(x- ><+»)" «-и7.„)

Ьп(х)= (и -шо) "(и к-и )(и -и + ) " и к и)п)40 фундаментальные многочлены Лагранжа.

Пусть З„- множество информационных узлов, с Эк — множество избыточных узлов.

Пусть о-„,dz;"K„- информационные байты кодового вектора. Избыточные байты с(. ... ) определим интерполированием с узлом ) на узлы с Э„по формуле Лагранж жа. (1) 50 ф. < ; gL.L (и) ) 5сп-к. (2)

К»5 щ gg 1 J К»& к

П1 избыточных символах при = 2, гт -степень неприводимого полинома, выбоанного в качестве модуля, с коэффициентами из Cr 72) Тогда, полагая с(.1, d.... d. информационными, à d 7„+», «-.л».2 - контрольными символами, в соответствии с формулой (2), имеем;

tt (1 7 и (») где (1) (i) »»1

1=» имеем

41= "-,„Od- =ЬК L, (Х (i7 И+» 1 11+»

» (1 7

Д, d. О ol. Л.К Ь (X )

2 11+2 11+2 1 и+2

По таблице ошибок, входами в которую служат величины невязок 1 и д2, находят номер ошибочного символа 1 и величину ошибки Ь с(-.;.

Исправление ошибки производится суммированием искаженного символа и величины ошибки:

+46(.. =сС.

1 1 1 (6) Отметим,что в случае исправления одиночной ошибки при двух контрольных символах информационная часть кода содержит ч, - 3 символа(в нашем случае

2 — 3), а избыточность составляет

2 z (в нашем случае Z ), Таким образом, при возрастании ти- степени неприводимого многочлена избыточность резко уменьшается и уже при )и =8 она равна

2 2

2ь- 2Уg, что составляет менее 1%. В дальнейшем примем символ, равный байту.

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

2 и 3 результатов модульного умножеЕсли в результате обработки, хранения или передачи в кодовом слое имело место искажение (-го символа,ос; =+i+Mi то после повторного вычисления контрольных символов

542194 ния обрабатываемых байтов на фундаментальные многочлены Лагранжа, сумматоры

4 и 5 по модулю два, предназначенные для параллельного определения двух конт k » рольных байтов А „„и А„,,блоки 6 и 7 анализа на нуль (контрольных байтов), выполненные на сумматорах по модулю два и осушествляюшие определение невязок Ь1 и а, блоки 8 и 9 хранения констант исправления, выполненные в виде матриц для запоминания константы исправления и номера байта, в котором произошла ошибка, сумматор 10 по модулю два, блок 11 анализа на нуль невязок й,) и

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

Массив, проверка правильности операций над которым должна быть произведена, подается на блок входных регистров 1 (число регистров соответствует числу байтов в массиве) ° Каждый входной регистр связан с двумя матрицами 2 и 3, хранящими результат умножения модульного значения байта (;,содержащегося на входном байтовом регистре, на фундаментальные многочпены Лагранжа— (1) (1 ) с - 1. (Х ) ив(L (Х ).

С выходов матриц 2 и 3 результаты модульного умножения поступают на входы сумматоров 4 и 5, где осуществляется определение контрольных байтов d. „+„, а(.„, по формулам

% 77 (1) с(,„= Kd.; Ь ()(, )

1=4

77 (1) (+ - «- ) (",+,). и7

%Значение сформированных контрольных байтов с выходов сумматоров 4 и 5 поступают соответственно на входы блоков 6 и 7, анализа на нуль, на вторые входы которых подаются те значения контрольных байтов, которые был .и получены в результате обработки массива Ал „ и 4. и+ . Блоки 6 и 7, выполненные на сумматорах по модулю два, определяют значение невязок

Ь7 и Л по формулам алгоритма декодирования

Ч(» )1=Ф- + Оd- d =.(0,(77+ 77+1 Л 77+ + I+/

Значения невязок p < и *, отличные от нуля, являются адресами обращения к блокам 8 и

9, хранящим значение констант исправления

do(, и номер ошибочного байта " ".Значение ошибочного байта в соответствии с определенным номером байта подается на вход сумматора 10 по модулю два, на второй вход которого с выхода блока 8 поступает величина ошибки ас(.В сумматоре 10 вычисляется истинное значение байта по формуле*„.Юо(=.- . В случае если ошибка не

Х обнаружена, блок анализа на нуль 11 по

)Q значению невязок, равным нулю (ь1=0,а =()), выдает сигнал отсутствия ошибки.

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

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

2 выходы блока входных регистров соединены со входами двух матриц результатов модульного умножения, вь7ходь которых соединены соответственно сс входами двух сумматоров по модулю два, выходы обоих сумматоров по модулю два соединены соответственно с первыми входами двух дополнительных блоков анализа на нуль, выходы которых соединены со входами двух блоков хранения констант исправления и блока анализа на нуль, выходы двух блоков хране40 ния констант исправления соединены с первым и вторым входами третьего сумматора по модулю два, выход которого является выходом устройства, вторые входы двух

45 дополнительных блоков анализа на нуль и третий вход третьего сумматора по модулю два являются входами устройства.

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

1. Авторское свидетельство СССР № 226278, М.кл. . 6г 06 F 11/00, 1967г.

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

N 398950, М. кл C 06 F 11/00, 1971 г. (прототип), 542194

>a z

Составитель В. Крылова

Редактор Л. Утехина ТехРед Н. АндРейчУк КоРРектоР А. Лакида

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

11HHHI1H Государственного комитета Совета Министров СССР по делам изобретений и открытий

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

Филиал ППП Патент", г. Ужгород, ул. Проектная, 4