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

кй 1 ентно- сон;и йбл ото Союз СоветскихСоциалистическихРеспублик(51) М 1 л е ( 06 Р 11/О осударстеенныи комитетСавета Министрав СССРпо делам изобретенийн аткрытий 3) Приоритет(43) Опубликовано 05.0 (45) Дата опуоликован 7 Бюллетень1писания 30. 03, 77 2) Авторы изобретени в, Ю. Н, Черкасо Амербаев,Н. Белова, Р и Э. И. Альзамарова ики АН Казахской ССР) Заявите итут математики и м 54) УСТРОИСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕН ОШИБОК АРИФМЕТИЧНЫХ ПРЕОБРАЗОВАНИЙ ПОЛИ НОМИАЛЬНЫХ КОДОВ анизаиии сум менем пределяетс максималь 10 ды которых соединены соот ния вы с твенно ов и со входами двух сум ва, Выходы обоих су атор ены соответстве о модулю два с х дополнительных и входам пе Изобретение относится к области вычислительной техники, в частности к устройствам для обнаружения и исправления ошибок, возникающих в процессе арифметичных преобразований над полиномами, За 5 основу кодирования полиномов приняты коды Лагранжа, которые, подобно непозиционным кодам целых чисел обладают параллельной стуктуройотносительноосновных арифметических операций.Известно устройство для обнаружения и исправления ошибок в непозиционной системе счисления - системе счисления остаточных классов 11.Наиболее близким техническим решением 15 к данному изобретению является устройство для обнаружения и исправления ошибок, содержащее два блока хранения констант исправления, три сумматора по модулю два, блок входных регистров, вхо ды которого являются входами устройства, блок анализа на нуль, выход которого является выходом ошибки устройства.Недостатком известного устройства для обнаружения и исправления ошибок 25 является малое быстродействие, котор мирования Л вычетов по ному подр системы оснований.Е 1 елью изобретения является повышение быстродействия устройства для обн ружения и исправления ошибок в кодах Лагранжа за счет использования параллельных сумматоров по модулю два.Коды Лагранжа, представляющие особ бую группу среди непозиционных кодов, обладают свойством самокоррекции при минимальной кодовой избыточности,Цель изобретения достигается тем что в предложенное устройство введены две матрицы результатов модульного ум ножения и два дополнительных блока анализа на нуль. Выходы блока входных регистров соединены со входами двух матриц результатов модульного умноже 542194В результате получается (п,к) - код) названный кодом Лагранжа, дпя обнаружения и исправпения(. ошибок, которым необходимо и достаточно 2 с, избыточных симвопов.Рассмотрим процедуру декодирования одиночной ошибки (под одиночной ошибкой понимается ошибка в символе) при двух бО бпоков анализа на нуль, выходы которыхсоединены со входами двух блоков-хранения констант исправления и блока анализа на нуль, Выходы двух блоков хранения констант исправления соединены спервым и вторым входами третьего сумматора по модулю два, выход которогоявляется выходом устройства. Вторыевходы двух дополнительных блоков анапиза на нуль и третий вход третьего сум- щматора по модулю два являются входамиустройства,На чертеже показана блок.хема устройства дпя обнаружения и исправления ошибокарифметичных преобразований полиномиальных кодов. При описании алгоритма декодирования в кодах Лагранжа введена следующая симвопика.3, - множество всех элементов поля Руйорядоченных некоторым образом:сю,( ю (соВсе подмножества множества )упорядочены в соответствии с порядком 3УЗ 11 - подмножество из ъ элементов множества Э, , 2 б3 - подмножество из ) эпементов мнок.жества 3с Эк - дополнение множества Эк до ЭПрим( - 1 существует единственныймногочлен (х) ЕР,ГХ 3 степени с и такой, что 3он принимает при 11+ различных значенияхпеременной Хи , а 1, В,6 7 заданнь езначения 1 (во), 1 (е 4) 1 (щи )Этот многочлен опредепяется интерполяционной формупой Лагранжа. 351(Х)= Е 1(Ы )Ь (Х), (Й)где к.-о(Ок ш ) " (ш ш )(Ф -ш ) - (Фк-ц)11)40фундаментальные многочпены Лагранжа.Пусть 3- множество информационныхузлов, с 3 к - множество избыточных узлов.Пусть А,ос, "Ы,- информационные байты кодового вектора, Избыточные байты с,).11 определим интерпопированием с узлом ) на узлы с Эпо формуле ЛагранКжа.(1) (1)Если в результате обработки, хранения или передачи в кодовом спое имело место искажение 1 -го символа,ос; = ;+М; то после повторного вычисления контрольных символов1 1) С(. - 2 Е-" 11+Л имеем4=д- О+ос =до Ь Гх )% Сч)Л+Л 11+ г1 Т+ 2По таблице ошибок, входами в которую служат величины невязок Ь 1 и д, находят номер ошибочного символа 1 и величину ошибки Ь с(,;.Исправление ошибки производится суммированием искаженного симвопа и величины ошибки;(Ь)Отметим,что в случае исправления одиночной ошибки при двух контрольных символах информационная часть кода содержит ч, - 3 символа(в нашем случае 2 - 3), а избыточность составляет 2 л(в нашем случае 21 п), Таким образом, при возрастании ти- степени неприводимого многочлена избыточность резко уменьшается и уже при т =8 она равна2 22 ь У, что составляет менее 1%, В дальнейшем примем символ, равный байту.Устройство для обнаружения и исправпе.ния ошибок арифметичных преобразований полиномиальных кодов содержит блок входных регистров 1 по числу обрабатываемых байтов, предназначенный дпя временного запоминания байтов, входящих в массив, объем которого при минимальной избыточности не превышает 256 байтов, матрицы 2 и 3 результатов модульного умноже542194дт Составитель В. Крыловаехина Техред Н. Андрейчук Корректор А, Лакида едактор 983/3 НИИПИ 64 Подписно комитета Совета М етений и открытий шская наб., д. 4/5 Тираж Государственног по делам изоб осква, Ж, Ра