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

 

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

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

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

<11>89471 1 (61) Дополнительное к авт, свмд-ву (22) Заявлено 291279 (21) 2861685/18-24 с присоединением заявки No (23) Приоритет

Опубликовано 301281 Бюллетень 14о 48

Дата опубликования описания 30. 12. 81 р1)м. кл.

G 06 F ll/08

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

СССР по девам изобретений и открытий (53) У (К 681. 326. 7 (088. 8) В.М. Амер баев, P . Г. Бияшев, Ю.Н. Черкасов .,( и В.Г.Евстигнеев (72) Авторы изобретения

I ll i (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ

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

ПОЛИНОМИНАЛЬНЫХ КОДОВ ройства, две матрицы результатов модульного умножения и два дополнительных блока анализа на нуль, причем выходы блока входных регистров соединены со входами двух матриц результатов модульного умножения, выходы которых соединены соответственно со входами двух сумматоров по модулю два, выходы обоих сумматоров по модулю два соединены соответственно с первыми входами двух дополнитель" ных блоков анализа на нуль, выходы которых соединены со входами двух блоков хранения констант исправления и блока анализа на нуль, выходы двух . блоков хранения констант исправления и блока анализа на нуль, выходы двух блоков хранения констант исправления соединены с первым и вторым входами третьего сумматора по модулю два, выход которого является выходом устройства, вторые входы двух допол- . нительных блоков анализа на нуль и третий вход третьего сумматора по модулю два являются входами устройства (2) .

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

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

Лагранжа.

Известно устройство для обнаружения и исправления ошибок, содержащее два блока хранения констант исправления, три сумматора по модулю два, блок входных регистров, входы которого являются выходом ошибки устройства (1) . t5

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

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

Московский институт инженеров гражданскЬй-авиации

894711 ошибок кратности два и более, а также с отсутствием контроля за работой устройства.

Цель изобретения — повышение надежности работы устройства.

Поставленная цель достигается тем, что н устройство для обнаружения и исправления ошибок арифметических преобразований полиноминальных кодов, содержащее (K+3) входных регистров (где К вЂ” количество информационных симнолов кода), первый и второй блоки умножения по модулю q, первую, вторую и третью схемы сравнения, первый, второй и третий сумматоры по модулю два, блок хранения констант умножения, причем входы входных регистров являются группой входов устройства, введены К Дешифраторов (К+1) блоков умножения по модулю q, четвертый, пятый, шестой и седьмой сумматоры по модулю два,первый и второй элементы И, четвертая схема сравнения, элемент

ИЛИ, причем выходы К входных регистров соединены со входами соответствующих дешифраторов и с соответствующими .входами первого элемента И, первый, второй и третий выходы каждого дешифратора соединены с соответствующими входами соответствующих блоков умножения по модулю q, четвертые, пятые и шестые входы которых объединены "оответственно между собой и подключены соответственно к первому, второму и третьему выходам блока хранения констант умножения, перные выходы первых К блоков умножения no q соединены соответственно со входами первого сумматора по модулю дна, вторые — со входами второго сумматора по модулю два, третьи — co входами третьего сумматора по модулю два, выходы первого, второго и третьего сумматоров по модулю два соединены с первыми входами соответственно первой, второй и третьей схем сравнения, вторые входы которых соединены соответственно с (К+1) -ым, (К+2) -ым и (К+3) -ым выходами входных регистров, первые выхо ды первой, второй и третьей схем сравнения соединены со входами эле мента ИЛИ, выход которого:. является первым выходом устройства,,вторые выходы первой, второй и третьей схем сравнения соединены с со(1

Ех„„-,)-- (qpp g (xx+s)= (х. х ) (0 К+ = Е О(„-) ()(К+9, (1) к (i)

) = I

)(„-)(„„(х; -х;+„)."((;-х„) (2)

Пусть х i хя i ° ° ° i +к+ н набор элементов поля GF (2 ), тогд

0 в соответствии с формулой (1) определим контрольные символы

60 „(„) С„„ В414 ((„,„)

К+4

К

К+2 ) " 1 ) )()(К+ 2) S — число контрольных символов х,.х

О 4 х - n различных элементов поля GF(q), n «eq, упорядоченных некоторым образом.

Рассмотрим процедуру исправления одйночной ошибки (под одиночной сшиб кой понимается любое искажение симво ла) и обнаружение ошибок большей кратности при использовании трех контрольных символов кода Лагранжа отнетстнующими входами (К+1) -го бло ка умножения по модулю q и второго элемента И, четвертый вход которого соединен с выходом четвертой схеиы сравнения, четвертый, пятый и шестой ныходы блока хранения констант умножения соединены соответстненно с третьим, четвертым и пятым входами (К+1) -го блока умножения по модулю q, первый, второй и третий выходы которого соединены соответственно с первым, вторым входами четвертого сумматора по модулю два и с первым входом пятого сумматора по модулю дна, второй вход которо. э соединен со вторым выходом первей схемы

15 сравнения, выходы четвертого и пятого сумматоров по модулю дна соединены соответственно с перными входами (К+2) -го и (K+3) -ro блоков умножения по модулю q, вторые входы которых

Щ соединены с седьмым выходом блока хранения констант умножения, третьи входы (К+2) -го и (К+3) -го блоков умножения по модулю о соединены соответственно со вторым и четвертым выходами (К+1) -го блока умножения по модулю q, (К+2) -ro и (К -3) -го блоков умножения по модулю q соединены соответственно со входами четвертой схемы сравнения, управляющий вход второго элемента И соединен с выходом (К+2).-го блока умножения по модулю

q, а выходы первого и второго элементов И соединены со входами шестого сумматора по модулю два, выход которого является нторым выходом устройства, первые К входов седьмого сумматора по модулю два соединены соответственно с первыми К выходами входных регистров, (К+1)-ый,(К+2)-ой и (K+3) — ий входы соединены соотнетст40 венно с выходами первого, второго и третьего сумматоров по модулю два, выход седьмого сумматора по модулю дна является третьим выходом устройства.

При описании алгоритма декодирования и кодах Лагранжа введена следующая символика:

ОЦ, с(... с(< — информационные символы контрольные символы определяются по формуле

894711 (X» 6)1) 0(»Å2)

К»1.„1 2 еи

)(4 (Х; Ег) г ° 1

10 (4).

19 2@ЧЗ

)(1 (х„® ()

Наиболее простыми получаются фундаментальные многочлены Лагранжа (2) в случае, когда

К+1 =XQ=Ot х К+ 2ииx4 =1, хК+ З =x =2

Тогда контрольные символы (3) при нимают вид

)(1(Х10+1)

Если в результате обработки, хранения или передачи в g -ом кодовом . символе (1 j n) имеет место искажеI ° ниеа .= dа + то после повторного вычисления контрольных символов g

1 к с(К,d.у имеем

«,(У О )(Х;Е2) к1 к1 =а

25 ч О 4 хз(ХЗ О+2) (5) °

2 кг кг- (Х, (х 91)

Ь Кь+ К5 1

Номер искаженного символа вычисляется из любой пары отношений (5), 71 зч из 1 имеем "3 =

Ч

3 5 ие — - имеем )(Ч 6Ч

Чд ч1Э ЗчЗ при этом должно выполняться х =х .

Величина ошибки определяется йз соот- 40 ношений (5) простым суммированием . трех равенств

Исправление производится суммиро-, ванием искаженного символа и величины ошибки с(. 9 а = А

При возникновении ошибки кратности. два и более равенство х =х1 не выполняется.

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

К (К Е к 0+1. О+% =О.

1 2 къ „«1 1 60

На чертеже представлена блок-схема устройства.

Устройство "одержит (K+3) входных регистров 1 по числу обрабатываемых символов (байт), предназначенных для 65 временного запоминания символов, образующих обрабатываемое слово, дешифраторы 2-1, 2-2,..., 2-К, предназначенные для дешифрации каждого символа (байта) обрабатываемого слова, блоки умножения по модулю (=2 »», а (ю) - степень неприводимого многочлена) 3-1, 3-2,..., З-К, 4 — б, первый 7, второй 8, третий 9 четвертый 10, пятый 11, шестой 12 и седьмой 13 сумматоры по модулю два, блок 14 хранения констант умножения, первую 15, вторую 16, третью 17 и четвертую 18 схемы сравнения, элемент. ИЛИ 19 первый 20, второй 21 элементы И.

Каждый дешифратор 2 имеет три выхода, на первом выходе формируется х;, на втором — х О+1 по модулю два, на третьем — х„.®2 по модулю два, каждый блок умножения по модулю имеет три входа, на которые подаются сигналы х-; х„91 и х Е2 от дешифраторов и три входа, на которые поступают константы 2, 3 и б " из блока 14 хранения констант умножения.

Каждый блок умножения по модулю имеет три выхода, на которых форми" руются сигналы о(„((х„91) (х192) ) /

/2, 1(х„(х„.92) ) /3 1 (x (х.61) ) /6.

Первые три сумматора по модулю 2 имеют по К входов. На входы первого сумматора по модулю со всех К блоков модульного умножения по модулю q поступают сигналы, соответствующие

»/„((х„-@ ) (х;б) ) /2, на входы второго сйгналы соответствующие о(„(х „(х.Щ ) /3

1 на входы третьего — сигналы. соответствующие a(„(x „(x„. gl ) ) / б . На выходах сумматоров по модулю два получаются вычисленные значения контрольных сим I 1 волов cCy „, 4 к г и к

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

Кодовая последовательность символов записывается во входные регистры 1. На входы первых К блоков 3 ум" ножения по модулю о для вычисле ния значений (Х„. Q1)()(„g z) X; (х„. 92) о(4,,(.„. (с выхода входных регистров подаются значения информационных символов, с выходов дешифраторов 2 - значения х, х„ 91, х ®2, с выхода блока 14

1 хранейия констант умножения — значения 2 "; 3 "; б 1. С выхода блоков 3 умножения по модулю с сформированные значения подаются на входы соответ" ствующих сумматоров по модулю два 7, 8 и 9, где происходит вычисление но1 вых контрольных символовс „,„, к, (к . Значения получаемых и принятых койтрольных символов сравниваются в

894711 большей кратности, равную Р . Для телефонных каналан

Р— 10 — 10

Предлагаемое устройство надежно, . ега обнаруживающие способности в

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

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

1 устройство для обнаружения и исправления ошибок арифметических преобразований полинаминальных кадов,содержащее (К+3) входных регистров (где К - количество информационных символов када), первый и второй блоки умножения по модулю ()., первую, вторую и третью схемы сравнения, первый,второй и третий сумматоры по модулю два, блок хранения констант умножения, причем входы входных регистров являются группой входов устройства, о т л и ч а ю щ е е с я тем, чта, с целью повышения надежности, оно содержит К дешифраторов, (К+1) блоков умножения па модулю ф, четвертый, пятый, шестой и седьмой сумматоры по модулю два, первый и второй элементы И, четвертую схему сравне- ния, элемент ИЛИ, причем выходы K нходных регистров соединены со входа. ми соответствующих дешифраторав и с соответствующими входами первого элемента И, первый,.второй и третий выходы каждого дешифратора соединены с соответствующими входами соответстнующих блоков умножения па модулю ф,четвертые, пятые и шестые нходы которых объединены соответственно между собой и подключены соответствыходам блока хранения констант умножения, первые выходы первых К блоков умножения по модулю g, соединены соответственно со входами первого сумматора по модулю дна, нторые — co входами второго сумматора по модулю два, третьи — со входами третьего сумматора па модулю два, выходы первого, нтораго и третьего сумматоров па модулю два соединены с первыми входами соответственно первой, вто» рой и третьей схе)и сравнения, нтоственно с (К+1) -ым, (К+2) -ым и (K+3) -им выходами входных регистров, первые выходы первой, второй и третьей схем сравнения соединены со входами элемента ИЛИ,. выход которого является первым выходом устройства вторые выходы первой, второй и тресхемах 15 — 17 сравнения. В случае их равенства на выходе элемента ИЛИ 19 .присутствует нулевой потенциал — ука- зывающий на отсутствие ошибок, и кодовое слово поступает на дальнейшую обработку. В случае отсутствия равенства значения Ч, 9«7зсо вторых выходов схем 15 — 17 сравнения подаются на входы (К-1) -го блока и умножения по модулю ®(где вычисляются

2у< 3 V> 3gy(б дз Значения Д (2 „(!О

jy<, 3V9 подаются на входы четвертого 10 и пятого 11 сумматоров па мо.дулю два для вычисления значений

2 ЦЗЗ V1 и )(,)Q+3Qg которые затем поступают на входы (К+2) -го и (К+3)го блоков 5 и б умножения па модулю формула изобретения

4 . На блоки 5 и б от блока 14 хранения констант умножения подается сигнал 1-" . На выходе блоков 5 и б фор(, мируются сигналы х и х, которые подаются на входы четвертой схемы 18 20

t. сравнения. Если равенство х х не выполняется, то четвертая схема 18 сравнения вырабатывает сигнал Ошибка . При выполнении равенства хА =х через нтарой элемент И 21 значения V, V<, g> подаются на вход шестого сумматора 13 по модулю два, где вычисляется величина ошибки дД .. Затем через первый, элемент И 20 прн наличии разрешающего сигнала х на вход сумматора 12 по .модулю два падается значение искаженного символа („ и реализуется исправление ошиб5 ки

Ь - В,1 ;=Ы

Для реализации контроля правильности работы блоков устройства значения a(y„QoLyP+d.к с выходов сумматоров 7 — 9 по модулю дна и значения информационных символов из входных регистров 1 подаются на входы седьмого сумматора 14 по модулю два,где реализуется выражение (б). В случае неравенства нулю результата суммирования вырабатывается сигнал Aaa((45.

Расчет эканомическо мической эффективнос- венно к первому, второму и третьему ти.

Ошибки в предлагаемом устройстве не обнаруживаются, если

) () - с) 50

К (g) 4

= +1.

©)

Р - вероятность выполнения этих условий;

Р - нероятность того, что ошибки будут .в узлах х, х, х„;

Р - вероятность ошибки и канале.

Вероятность того, что ошибка пред- рые входы которых соединены соатветлагаемым устройством не будет обнаружена ЬО

Рф Рф РЭ

При длине слова 256 байт

Р4 10

Известное устройство имеет вероятность необнаружения ошибки двойной и 65

894711

10 тьей схем сравнения соединены с соответствующими входами (К+1)-го блока умножения по модулюф и второго элемента И, четвертый вход которого соединен с выходом четвертой схемы сравнения, четвертый, пятый и шестой выходы блока хранения констант умножения соединены соответственно с третьим, четвертым и пятым входами ,(К+1)-го блока умножения по модулю ф, первый, второй и третий выходы которого соединены соответственно с первым, вторым входами четвертого сумматора по модулю два и с первым входом пятого сумматора по модулю два, второй вход которого соединен со вторым выходом первой схемы сравнения, выхо- ды четвертого и пятого сумматоров по . модулю два соединены соответствейно с первыми входами (К+2)-ro и (К+3)-го блоков умножения по модулю ф, вторые входы которых соединены с седьмым вы- 20 ходом блока хранения констант умножения, третьи входы (К+2)-го и (К+3)-го блоков умножения по модулю g соединены соответственно со вторым и четвертым выходами (К+1) -го блока умноже- g5

Ф ния по модулю 0., выходы (К+2) -го и (K+3) -го блоков умножения по модулю (соединены соответственно со входами четвертой схемы сравнения, управляющий вход второго элемента И соеди" нен с выходом (К+2)-го блока умножения по модулю (),, выходы первого и второго элементов И соединены со входами шестого сумматора по модулю два, выход которого является вторым выходом устройства, первые К входов седьмого сумматора по модулю два соединены соответственно с первыми К выходами входных регистров, а (К+1)-ый, (K+2)-ой и (К+3)-ий входы соединены соответственно с выходами первого, второго и третьего сумматоров по мбдулю два, выход седьмого сумматора по модулю два является третьим выходом устройства.

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

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

Р 398950, кл. G 06 F 11/00, 1971.

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

9 542194, кл. G 06 F 11/00,1977 (прототип).

894 711

Заказ 11490/78

Тираж 748 Подписное

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

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

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

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

Редактор Е.Дичинская ТехредТ. Яаточка корректор М.Шароши