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

Союз Советскик Соцналистическнк Республик(22) Заявлено 291279 (21) 2861685/18-24 (51) М. Кл. 6 06 Р 11/08 с присоединением заявки Мо(23) Приоритет Государственный комитет СССР по девам изобретений и открытийОпубликовано 30.12.81. Бюллетень йо 48 Дата опубликования описания 30. 12. 81(71) Заявите Московск 54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИ ОШИБОК АРИФМЕТИЧЕСКИХ ПРЕОБРАЗОВАНИИ ПОЛИНОМИНАЛЬНЫХ КОДОВносится к вычисли- может быть испольения и исправления их в процессе арифазований над полино- передаче и хранении тавленной в коде ройство для обнаружеия ошибок, содержащее ния констант исправлеора по модулю два, гистров, входы которо- одом ошибки устройст 15 яв ты те Изобретение оттельной технике иэовано для обнаружошибок, возникающметических преобрмами, а также приинформации, предсЛагранжа.Известно устних и исправлендва блока хранения, три сумматблок входных рего являются выхва 1) .Недостатком .устройства является малое быстродействие, которое определяется временем организации суммирования и вычетов по максимальному модулю системы оснований. 20Наиболее близким к предлагаемому является устройство для обнаружения И исправления ошибок арифметических преобразований полиноминальных кодов, содержащее два блока хранения кон стант исправления, три сумматора по модулю два, блок входных регистров, входы которого являются входами устройства, блок анализа на нуль, выход которого является выходом ошибки уст ройства, две матрицы результатов модульного умножения и два дополнительных блока анализа на нуль, причем выходы блока входных регистров соединены со входами двух матриц результатов модульного умножения, выходы которых соединены соответственно со входами двух сумматоров по модулю два, выходы обоих сумматоров по модулю два соединены соответственно с первыми входами двух дополнитель" ных блоков анализа на нуль, выходы которых соединены со входами двух блоков хранения констант исправления и блока анализа на нуль, выходы двух блоков хранения констант исправления и блока анализа на нуль, выходы двух блоков хранения констант исправления соединены с первым и вторым входами третьего сумматора по модулю два, выход которого является выходом устройства, вторые входы двух допол- . нительных блоков анализа на нуль и третий вход третьего сумматора по модулю два являются входами устройства 2 .Недостатком известного устройства ляется низкая надежность его рабо"связанная с внесением дополни.льной ошибки при возникновенииошибок кратности два и более, а также с отсутствием контроля за работой устройства.Цель изобретения - повышение надежности работы устройства.Поставленная цель достигается тем, что н устройство для обнаружения и исправления ошибок арифметических преобразований полиноминальных кодов, содержащее (К+3) входных регистров (где К - количество информационных символов кода), первый и второй блоки умножения по модулю О, первую, вторую и третью схемы сравнения, первый, второй и третий сумматоры по модулю два, блок хранения констант умножения, причем входы входных регистров являются группой входов устройства, введены К Дешифраторов (К+1) блоков умножения по модулю с 1, четвертый, пятый, шестой и седьмой сумматоры по модулю два,первый и второй элементы И, четвертая схема сравнения, элемент ИЛИ, причем выходы К входных регистров соединены со входами соответствующих дешифраторов и с соответствующими .входами первого элемента И, первый, второй и третий выходы каждого дешифратора соединены с соответствующими входами соответствующих блоков умножения по модулю с 1, четвертые, пятые и шестые входы которых объединены "оотнетственно между собой и подключены соответственно к первому, второму и третьему выходам блока хранения констант умножения, перные выходы первых К блоков умножения по модулю о соединены соответственно со входами первого сумматора по модулю дна, вторые - со входами второго сумматора по модулю два, третьи - со входами третьего сумматора по модулю два, выходы первого, второго и третьего сумматоров по модулю два соединены с первыми входами соответственно первой, второй и третьей схем сравнения, вторые входы которых соединены соответственно с (К+1) -ым, (К+2) -ым и (К+3) -ым выходами входных регистров, первые выхо ды первой, второй и третьей схем сравнения соединены со входами элемента ИЛИ, выход которого:. является первым выходом устройства, ,вторые выходы первой, второй и третьей схем сравнения соединены с со ) Ькн о)" (цф(к э) 0= 3 о.Ь (К 9) (1)(2)Пусть х хя гф хк+ н набор элементов поля СГ(2 ), тогдО фв соответствии с формулой (1) определим контрольные символы(.К 4 1(К 1 )К+4 (1 8 - число контрольных символов х, хО 1 4 ф ф1 И 6х- и различных элементов поля ф СР(с 1), и сц, упорядоченных некоторым образом.Рассмотрим процедуру исправления одйночной ошибки (под одиночной сшиб кой понимается любое искажение симво ла) и обнаружение ошибок большей кратности при использовании трех контрольных символов кода Лагранжа отнетстнующими входами (К+1) -го блока умножения по модулю с( и второгоэлемента И, четвертый вход которого соединен с выходом четвертой схеиы сравнения, четвертый, пятый ишестой ныходы блока хранения констант умножения соединены соответстненно с третьим, четвертым и пятымвходами (К+1) -го блока умножения помодулю с 1, первый, второй и третийвыходы которого соединены соответственно с первым, вторым входами четвертого сумматора по модулю два и спервым входом пятого сумматора по модулю дна, второй вход которо.э соединен со вторым выходом первой схемы 15 сравнения, выходы четвертого и пятого сумматоров по модулю дна соединены соответственно с перными входами(К+2) -го и (К+3) -го блоков умноженияпо модулю ц, вторые входы которых Щ соединены с седьмым выходом блокахранения констант умножения, третьивходы (К+2)-го и (К+3)-го блоков умножения по модулю с 1 соединены соответственно со вторым и четвертым выходами (К+1) -го блока умножения помодулю с 1 (К+2) -го и (КЗ) -го блоковумножения по модулю с 1 соединены соответственно со входами четвертой схемы сравнения, управляющий вход второго элемента И соединен с выходом(К+2).-го блока умножения по модулюо, а выходы первого и второго элементов И соединены со входами шестогосумматора по модулю два, выход которого является нторым выходом устройства, первые К входов седьмого сумма.тора по модулю два соединены соотнет.ственно с первыми К выходами входныхрегистров, (К+1)-ый,(К+2)-ой и(К+3)-ий входы соединены соотнетст венно с выходами первого, второго итретьего сумматоров по модулю два,выход седьмого сумматора по модулюдна является третьим выходом устройства.При описании алгоритма декодирования и кодах Лагранжа введена следующая символика:Осд Ис - информационные символыконтрольные символы определяются поФормуле50(4),Х; Ьб Наиболее простыми получаются фундаментальные многочлены Лагранжа (2) в случае, когдаК+( =хо=0, х К+2=хам=1, хэ =х=2Тогда контрольные символы (3) при нимают вид Х; Ь 1 0+1)15Если в результате обработки, хранения или передачи в-ом кодовом символе (13 и) имеет место искажениеа.= д.+М то после повторного вычисления контрольных символов о1к с(К 1 сК имеем,( . (,. (, Ь;О+1)(Х;Е 2)1 К25Х 3(Х 0+2) (5)2 КЯ. К-Д1 ( Х 3 (ХЭ 6 Ч)Ь= Кь + К 5= 3 30Номер искаженного символа вычисляется из любой пары отношений (5),7из имеем ") =Ч3 5 иэ в - имеем у : ЪЧ бчч НЕ 5 Ч 9при этом должно выполняться х дх.Величина ошибки определяется йз соот Оношений (5) простым суммированием трех равенств Исправление производится суммиро-; 45 ванием искаженного символа и величины ошибкис(. 9 дс А,/При возникновении ошибки кратности два и более равенство х:х не выполняется.Для организайии"контроля правильности выполнения операций в блоках модульного умножения и сумматоров по модулю два, а также блока хранения констант умножения, используется соотношениеКо(Е (0 (. О й к =с .2 КЪ 1На чертеже представлена блок-схема устройства.Устройство "одержит (К+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 и х 92 от дешифраторов и три входа, на которые поступают константы 2 , 3 и б-" из блока 14 хранения констант умножения. Каждый блок умножения по модулю имеет три выхода, на которых форми" руются сигналы о(х 1)(х 92 / /2, 1(х(х 92) ) /3 1 (х (х.61) ) /6. Первые три сумматора по модулю 2 имеют по К входов. На входы первого сумматора по модулю со всех К блоков модульного умножения по модулю ц поступают сигналы, соответствующие сх;р)(х;б) ) /2, на входы второго сйгналы соответствующиеох(х Щ )/3 на входы третьего - сигналы. соответствующие с( (х(х,;Я 1/б. На выходах сумматоров по модулю два получаются вычисленные значения контрольных символовсКК, с ки акУстройство работает следующим образом.Кодовая последовательность символов записывается во входные регистры 1. На входы первых К блоков 3 ум" ножения по модулю с 1 для вычисле ния значенийЬ 94)(ХВ 2) Х(Х 9 г.), д.( с выхода входных регистров подаются значения информационных символов, с выходов дешифраторов 2 - значения х , х 91, х 2, с выхода блока 14 хранения констант умножения - значения 2 "; 3 "; б . С выхода блоков 3 умножения по модулю с), сформированные значения подаются на входы соответ" ствующих сумматоров по модулю два 7, 8 и 9, где происходит вычисление но 1вых контрольных символовСК,якЗначения получаемых и принятых койтрольных символов сравниваются вбольшей кратности, равную Р . Для телефонных каналанР - 10 зПредлагаемое устройстно надежно, . его обнаруживающие способности н 10 раз выше, чем у известного, так как обнаруживаются и исправляются как одиночные, так и двойные ошибки. Кроме того, наличие дополнительной информации в виде сигналов Нет ошибки и Авария дает возможность визуально наблюдать за испраннай работой устройства.1 устройство для обнаружения и исправления ошибок арифметических преобразований полинаминальных кадав,содержащее (К+3) входных регистров(где К - количество информационныхсимволов када), первый и второй блоки умножения по модулю .( первую,вторую и третью схемы сравнения, первый,второй и третий сумматоры по модулю два, блок хранения констант умножения, причем входы входных регистров являются группой входов устройства, о т л и ч а ю щ е е с я тем, чта, с целью повышения надежности, оно содержит К дешифраторав, (К+1) блоков умножения па модулю ф ( четвертый, пятый, шестой и седьмой сумматоры по модулю два, первый и второй элементы И, четвертую схему сравне-ния, элемент ИЛИ, причем выходы К нходных регистров соединены со входа. ми соответствующих дешифраторав и с соответствующими входами первого элемента И, первый,.второй и третий выходы каждого дешифратора соединены с соответствующими входами соответстнующих блоков умножения па модулю ф (четвертые( пятые и шестые входы которых объединены соответственномежду собой и подключены соответствыходам блока хранения констант умножения, первые выходы первых К блоков умножения по модулю ( соединенысоответственно со входами первогосумматора по модулю дна, нторые - совходами второго сумматора по модулюдва, третьи - со входами третьего сумматора по модулю два, выходы первого, нтораго и третьего сумматоровпо модулю два соединены с первымивходами соответственно первой, второй и третьей схеьи сравнения, нтоственно с (К+1) -ым, (К+2)-ым и(К+3) -им выходами входных регистров,первые ныходы первой, второй и третьей схем сравнения соединены совходами элемента ИЛИ,. выход которогоявляется первым выходом устройствавторые выходы первой, второй и тресхемах 15 - 17 сравнения. В случае ихравенства на выходе элемента ИЛИ 19.присутствует нулевой потенциал - ука-зывающий на отсутствие ошибок, и кодовое слово поступает на дальнейшуюобработку, В случае отсутствия равенства значения Ч 1 ( Ч( Часа вторыхвыходов схем 15 - 17 сравнения подаются на входы (К) -го блока и умножения по модулю ч где вычисляются2 р 4( 3 Ч 2 ЗЧ( б Ч,. Значения Ч,2 Ч(37, З.ЧЭ подаются на входы четвертога 10 и пятого 11 сумматоров па мо.дулю два для. вычисления значений29493 Ч 1 и ЧС+)ЗЧ 3( которые затем поступают на входы (К+2) -го и (К+3)- го блоков 5 и б умножения па модулю 15формула изобретения(. На блоки 5 и б от блока 14 хранения констант умножения подается сигнал 1-" . На выходе блоков 5 и б фор(,мируются сигналы х и х , которыеподаются на входы четвертой схемы 18 20сравнения. Если равенство х-х невыполняется, то четвертая схема 18сравнения вырабатывает сигналОшибка. При выполнении равенства х=х через нтарой элемент И 21значения Ч 71( Ч подаются на входшестого сумматора 13 по модулю два,где вычисляется величина ошибкиДД ,. Затем через первый, элемент И 20прй наличии разрешающего сигнала хна вход сумматора 12 по .модулю дваподается значение искаженного символа (и реализуется исправление ошиб.киЬ( В 1;=35Для реализации контроля правильности работы блоков устройства значения 0(К есц+Эскс выходов сумматоров 7 - 9 по модулю дна и значенияинформационных символов из входныхрегистров 1 подаются на входы седьмого сумматора 14 по модулю два,гдереализуется выражение (б). В случаенеравенства нулю результата суммирования вырабатывается сигнал (Аваия 45.Расчет экономическомической эффективнос- венно к первому, второму и третьемути.Ошибки в предлагаемом устройствене обнаруживаются, если, ),дК (1)- 4Ь1,:.Р - вероятность выполнения этих условий;Р- нероятность того, что ошибки будут в узлах х, х , х;Р - вероятность ошибки в канале.Вероятность того, что ошибка пред- рые входы которых соединены саатветлагаемым устройством не будет обнаружена ЬОРФ Р РЭПри длине слова 256 байтР 4 10Известное устройство имеет вероятность необнаружения ошибки двойной и Ь 5тьей схем сравнения соединены с соответствующими входами (К+1)-го блока умножения по модулюф и второгоэлемента И, четвертый вход которогосоединен с выходом четвертой схемысравнения, четвертый, пятый и шестойвыходы блока хранения констант умножения соединены соответственно стретьим, четвертым и пятым входами,(К+1)-го блока умножения по модулю ф,первый, второй и третий выходы которого соединены соответственно с первым, вторым входами четвертого сумматора по модулю два и с первым входомпятого сумматора по модулю два, второй вход которого соединен со вторымвыходом первой схемы сравнения, выходы четвертого и пятого сумматоров по .модулю два соединены соответственнос первыми входами (К+2)-го и (К+3)-гоблоков умножения по модулю ф, вторыевходыкоторых соединены с седьмым выходом блока хранения констант умноже. -ния, третьи входы (К+2)-го и (К+3)-гоблоков умножения по модулю ф соединены соответственно со вторым и четвертым выходами (К+1) -го блока умноже ния по модулю (1., выходы (К+2) -го и(К+3) -го блоков умножения по модулю( соединены соответственно со входами четвертой схемы сравнения, управляющий вход второго элемента И соеди"нен с выходом (К+2)-го блока умножения по модулю ф, выходы первого и второго элементов И соединены со входамишестого сумматора по модулю два, выход которого является вторым выходомустройства, первые К входов седьмогосумматора по модулю два соединены соответственно с первыми К выходамивходных регистров, а (К+1)-ый,(К+2)-ой и (К+3)-ий входы соединенысоответственно с выходами первого,второго и третьего сумматоров по мб"дулю два, выход седьмого сумматорапо модулю два является третьим выходом устройства.Источники инФормации,принятые во внимание при экспертизе1. Авторское свидетельство СССР9 398950, кл. С Об Г 11/00, 1971.2. Авторское свидетельство СССР9 542194, кл. С Об Г 11/00,1977 (прототип).Ре Закаэ 11490/78 1130 5 лиал ППП фПатент, г. Ужгород, ул. Проектная,Тираж 748 ИПИ. Государственн по делам изобретеМосква, Ж, Р Подписноео комитета СССРй и открытийушская наб., д.