Устройство для обнаружения и исправления ошибок арифметических преобразований полиномиальных кодов Советский патент 1981 года по МПК G06F11/08 

ошиоок кратности два и более, а также с отсутствием контроля за работой устройства. Цель изобретения - повышение надежности работы устройства. Поставленная цель достигается тем что в устройство для обнаружения и исправления ошибок арифметических преобразований полиноминальных кодов содержащее (К+3) входных регистров (где К - количество информационных символов кода), первый и второй блок умножения по модулю q, первую, вторую и третью схемы срав.нения, первый второй и третий сумматоры по модулю два, блок хранения констант умножения, причем входы входных регистров являются группой входов устройства, введены К Дешифраторов (К+1) блоков умножения по модулю q, четвертый, пя тый, шестой и седьмой сумматоры по модулю два,первый и второй элементы четвертая схема сравнения, элемент ИЛИ, Причем выходы К входных регист ров соединены со входами соответствующих дешифраторов и с соответствующими .входами первого элемента И, первый, второй и третий выходы кажд го Дешифратора соединены с соответствующими входами соответствующих блоков умножения по модулю q, четве тые, пятые и шестые входы которых объединены соответственно между собой и подключены соответственно к первому, второму и третьему выходам блока хранения констант умножения, первые выходы первых К блоков умножения по модулю q, соединены соответственно со входами первого сумма тора по модулю два, вторые - со вхо дами второго сумматора по модулю дв третьи - со входами третьего сумматора по модулю два, выходы первого, второго и третьего сумматоров по мо дулю два соединены с первыми входами соответственно первой, второй и третьей схем сравнения, вторые вход которых соединены соответственно с (К+1)-ым, (К+2)-ым и (К+3)-ым выходами входных регистров, первые выхо ды первой, второй и третьей схемсравнения соединены со входами элемента ИЛИ, выход которогоявляется первым выходом устройства, /вторые выходы первой, второй и третьей схем сравнения соединены с соfi) (). {XK«)-- - число контрольных символов Xfl.- X., ., .X n+q - п различных элементов пoляGF(q), п «:q, упорядоченных некоторым образом. Рассмотрим процедуру исправления одиночной ошибки (под одиночной оши кой понимается любое искажение симв ла) и обнаружение ошибок большей кратности при использовании трех контрольных символов кода Лагранжа ответствующими входами (К+1)-го бло ка умножения по модулю q и второго элемента И, четвертый вход которого соединен с выходом четвертой схемы сравнения, четвертый, пятый и естой выходы блока хранения констант умножения соединены соответственно с третьим, четвертым и пятым входами (К+1)-го блока умножения по модулю q, первый., второй и третий выходы которого соединены соответственно с первым, вторым входами четвертого сумматора по модулю два и с первым входом пятого сумматора по модулю два, второй вход которого соединен со вторьлм выходом первой схемы сравнения, выходы четвертого и пятого сумматоров по модулю два соединены соответственно с первыми входами {К+2)-го и (К+3)-го блоков умножения по модулю q, вторые входы которых соединены с седьмым выходом блока хрйнения констант умножения, третьи входаа (К+2)-го и (К+3)-го блоков умножения по модулю q соединены соответственно со вторым, и четвертым выходами (К+1)-го блока умножения по модулю q, (К+2)-го и ()-го блоков умножения по модулю q соединены соответственно со входами четвертой схемы сравнения, управляющий вход второго элемента И соединен с выходом (К+2)-го блока умножения по модулю q, а выходы первого и второго элементов И соединены со входами.шестого сумматора по модулю два, выход которого является вторым выходом устройства, первые К входов седьмого сумматора по модулю два соединены соответственно с первыми К выходами входных регистров, (К+1)-ый,(К+2)-ой и (К+3)-ий входы соединены соответственно с выходами первого, второго и третьего сумматоров по модулю два, выход седьмого сумматора по модулю два является третьим выходом устройства. При описании алгоритма декодирования в кодах Лагранжа введена следующая символика: oLfiof... информационные символы контрольные символы определяются по формуле (К+чХ K+.- /i-Хл-1Х к, ic) ) x,i4e полный Пусть XQ, Х,..., набор элементов поля GF(2), тогда в соответствий с формулой (1) определим контрольные символы .Nf/i/ -.) k+2-- /iL W42) Ь() Наиболее простыми получаются фу даментальные многочлены Лагранжа ( в случае, когда 5«li4-t . «):4.(Ь Тогда контрольные символы (3) п нимают вид |,. (Xi®l)a,©2) ol,-. |. ) (4). 1-1 Э J f/1 . Если в результате обработки, хр нения или передачи в -ом кодовом символе (lej п) имеет место иска ние .j. dij+tidij, то- после повторног вычисления контрольных символов oiv j л «К2. имеем y,--dL,.A.04®i)m) . Xj(Xj®2) (5 2 « Ка®° и--АоХоСХэ®-) t,j--Aoti Номер искаженного символа вычисл ется из любой пары отношений (5), имеем X;3при этом должно выполняться . Величина ошибки определяется из со ношений (5) простым суммированием трех равенств Дс(-V ®V2©V. Исправление производится суммиро ванием искаженного символа и величи ны ошибки ot ® Aol-3 - j . При возникновении ошибки кратност два и более равенство х-г xj не выполняется. Для организаздииконтроля правиль ности выполнения операций в блоках модульного умножения и сумматоров п модулю два, а также блока хранения констант умножения, используется соотношение К,,®Ео1.,-О . . На чертеже представлена блок-схе ма устройства. Устройство содержит (К+3) входн регистров 1 по числу обрабатываемых символов (байт), предназначенных дл временного запоминания символов, образующих обрабатываемое слово, дешифраторы 2-1, 2-2,..., 2-Кг предназначенные для дешифрации каждого символа (байта) обрабатываемогослова, блоки умножения по модулю (, а (И - степень неприводимого многочлена) 3-1, 3-2,..., 3-К, 4-6, первый 7, второй 8, третий 9, четвертый 10, пятый 11, шестой 12 и седьмой 13 сумматоры по модулю два, блок 14 хранения констант умножения, первую 15, вторую 16, третью 17 и четвертую 18 схемы сравнения, элемент. ИЛИ 19 первый 20, второй 21 элементы И. Каждый дешифратор 2 имеет три выхода, на первом выходе формируется х- , на втором - по модулю два, на третьем - по модулю два, каждый блок умножения по модулю имеет три входа, на которые подаются сигналы и х ®2 от дешифраторов и три входа, на которые поступают константы , 3 и 6 из блока 14 хранения констант умножения. Каждый блок умножения по модулю q имеет три выхода, на которых формируются сигналы .о/( () ())/ /2,at(x (х-©2))/Зо(;(.®1))/б. Первые три сумматора по модулю 2 имеют по К входов. На входы первого сумматора по модулю со всех К блоков модульного умножения по модулю q поступают сигналы, соответствующие О/ (() ( )/2, на входы второго сигналы соответствующие с (х( )/3 на входы третьего - сигналы, соответствующие о (х ( )) /6 . На выходах сумматоров по модулю два получаются вычисленные значения контрольных симВОЛОВо4| ,oi ко. o KjУстройство работает следующим образом. Кодовая последовательность символов записывается во входные регистры 1. На входы первых К блоков 3 умножения по модулю q для вычисле ния значений (Xi©l)(Xi02) . ) с выхода входных регистров подаются значения информационных символов, с выходов дешифраторов 2 - значения X;, , х-®2, с выхода блока 14 хранения констант умножения - значения ; ; . С выхода блоков 3 умножения по модулю ( сформированные значения подаются на входы соответствующих сумматоров по модулю два 7, 8 и 9, где происходит вычисление ноых контрольных СИМВОЛОВО / /( . Значения получаемых и принятых онтрольных символов сравниваются в схемах 15 - 17 сравнения. В случае и равенства на выходе элемента ИЛИ 19 присутствует нулевой потенциал - ука зывающий на отсутствие ошибок, и кодовое слово поступает на дальнейшую обработку. В случае отсутствия равенства значения V 7 V-jCO вторых выходов схем 15 - 17 сравнения подаются на входы (K-l)-ro блока и умн жения по модулю Ц , где вычисляются 3 V, , бу. Значения 3Va. 3.V подаются на входы четвертого 10 И пятого 11 сумматоров по мо.дулю два для. вычисления значений 2V(53 V.2. и V,,@3V3f которые затем поступают на входы (К+2)-го и (К+3) го блоков 5 и 6 умножения по модулю «. На блоки 5 и 6 от блока 14 хране ния констант умножения подается сиг нал I- . На выходе блоков 5 и 6 фор мируются сигналы Щ и xj, которые подаются на входы четвертой схемы 1 сравн.ения. Если равенство .- не выполняется, то четвертая схема 18 сравнения вырабатывает сигнап Ошибка. При выполнении равенства л через второй элемен И 21 значения V , V, Va подаются на вхо шестого сумматора 13 по модулю два, где вычисляется величина ошибки A(. Затем через первый .элемент И 2 при наличии разрешающего сигнала х j на вход сумматора 12 по .модулю два подается значение искаженного симво ла и реализуется исправление оши ки .) Для реализации контроля правильности работы блоков устройства значения с/х к выходов суммато ров 7-9 по модулю два и значения информационных символов из входных регистров 1 подаются на входы седьмого сумматора 14 по модулю два,где реализуется выражение (б). В случае неравенства нулю результата сумми- рования вырабатывается сигнал Ава рия . Расчет экономической эффективнос ти. Ошибки в предлагаемом устройстве не обнаруживаются, если г А ьЩ-- Д кЬЦPL - вероятность выполнения этих условий;Р вероятность того, что ошибки бу дут в узлах , х, PI- вероятность ошибки в канале. Вероятность того, что ошибка пре лагаемым устройством не будет обнару жена Р Р. РЗ. При длине слова 256 байт р, . Известное устройство имеет вероя ность необнаружения ошибки двойной большей кратности, равную Р. Для телефонных каналов Р Ю--гЮ . Предлагаемое устройство надежно, . его обнаруживающие способности в 10 раз выше, чем у известного, так как обнаруживаются и исправляются как одиночные, так и двойные ошибки. Кроме того, наличие дополнительной информации в виде сигналов Нет ошибки и Авария дает возможность визуально наблюдать за исправной работой устройства. Формула изобретения Устройство для обнаружения и исправления ошибок арифметических преобразований полиноминальных кодов,со-, держащее (К+3) входных регистров (где К - количество информационных символов кода), первый и второй блоки умножения по модулю с., первую, вторую и третью схемы сравнения, первый, второй и третий сумматоры по модулю два, блок хранения констант умножения, причем входы входных регистров являются группой входов устройства, отличающееся тем, что, с целью повышения надежности, оно содержит К дешифра-торов, (К+1) блоков умножения по, модулю ( , четвертый, пятый., шестой и седьмой сумматоры по модулю два, первый и второй элементы И, четвертую схему сравнения, элемент ИЛИ, причем выходы к входных регистров соединены со входами соответствующих дешифраторов и с соответствующими входами первого элемента И, первый,.второй и третий выходы каждого дешифратора соединены с соответствующими входами соответствующих блоков умножения по модулю 9- ,четвертые, пятые и шестые входы которых объединены соответственно между собой и подключены соответственно к первому, второму и третьему выходам блока хранения констант умножения, первые выходы первых К блоков умножения по модулю J, соединены соответственно со входами первого сумматора по модулю два, вторые - со входами второго сумматора по модулю два, третьи - со входами третьего сумматора по модулю два, выходы первого, второго и третьего сумматоров по модулю два соединены с перьыми входами соответственно первой, второй и третьей, схемы сравнения, вторые входы которых соединены соответственно с (К+1)-ым, (К+2)-Ь1М и (К+3)-им выходами входных регистров, первые выходы первой, второй и третьей схем сравнения соединены со входами элемента ИЛИ, выход которого является первым выходом устройства вторые выходы первой, второй и третьей схем сравнения соединены с соответствующими входами (К+1)-го блока умножения по модулю и второго элемента И, четвертый вход которого соединен с выходом четвертой схемы сравнения, четвёртый, пятый и шестой выходы блока хранения констант умножения соединены соответственно с третьим, четвертым и пятым входами .(.К+1)-го блока умножения по модулю, первый, второй и третий выходы которого соединены соответственно с первым, вторым входами четвертого сумматора по модулю два и с первым входом пятого сумматора по модулю два, второй вход которого соединен со вторым выходом первой схемы сравнения, выходы четвертого и пятого сумматоров по модулю два соединены соответствейно с первыми входами (К+2)-го и (К+3)-го блоков умножения по модулю ( , вторые входыкоторых соединены с седьмым выходом блока хранения констант умножения, третьи входы (К+2)-го и (К+3)-го блоков умножения по модулю ф соединены соответственно со вторым и четвертым выходами (К+-1)-го блока умножения по модулю ф, выходы (К+2)-го и (К+3)-го блоков умножения по модулю у соединены соответственно со входами четвертой схемы сравнения, управляющий вход второго элемента И соединен с выходом (К+2)-го блока умножения по модулю (, выходы первого и втрого элементов И соединены со входам шестого сумматора по модулю два, выход которого является вторым выходом устройства, первые К входов седьмого сумматора по модулю два соединены соответственно с первыьои К выходами входных регистров, а (К+1)-ый, (К+2)-6й л (К+3)-иП входы соединены соответственно с выходами пербого, второго и третьего сумматоров по модулю два, выход седьмого cyi MaTopa по модулю два является третьим выходом устройства.

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

1.Авторское свидетельство СССР 398950, кл. G 06 F 11/00, 1971.

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

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