Вычислительное устройство в поле галуа gf (2 )

1635193 Изобретение относится к вычислительной технике,Целью изобретения является упрощение устройства,На фиг, 1 представлена функциональная схема вычислительного устройства в поле Галуа СР (2 ); на фиг,2 -временная диаграмма его работы,Вычислительное устройство в полеГалуа СР (2") содержит мультиплексоры 1-3, регистр Е сдвига, регистр 5,умножитель 6, блок 7 ключей и сумматор 8 по модулю два накапливающеготипа,При этом на первые входы мультиплексоров 1-3 поданы соответственновходы данных (А, В, К), на каждый измультиплексоров 1-3, регистр Е сдвига и блок 7 ключей по соответствующему входу - свой управляющий сигнал Б , а на вторые входы мультиплексоров 1 и 2 - соответственно входы данных (С П). Мультиплексор 1,регистр Е сдвига и мультиплексор 3соединены последовательно, Мультиплексор 2, регистр 5, умножитель 6и блок 7 ключей также соединены последовательно; Выход мультиплексора3 подключен к входам умножителя 6.Вход сумматора 8 соединен с выходомумножителя 6 и третьим входом мультиплексора 2. Выход блока 7 ключей является выходом данных Р устройства,а выход сумматора 8 - выходом данных Е устройства. Важной особенностью элементов внормальном виде является простота возведения в степень 2 или 2 любогоэлемента поля ф , Это осуществляетсяпутем циклического сдвига соответственно вправо или влево полинома А(Х),25 помещенного в регистр сдвига, наразрядов. Сдвиг можно также осуществить путем соответствующего переключения выходных цепей регистра, В предлагаемом устройстве используетсясдвиг содержимого регистра при возведении в степень. Этим обеспечивается уменьшение количества умножений и,следовательно, числа умножителей. Работа рассматривается при основныхоперациях, используемых в системахпомехоустойчивого кодирования.1Элементы поля Галуа СР (2 )121 - 10101101 Е 2 -22 - 00111000 ЕЗ -23 - 11000011 4424 - 11100010 45 -25 - 00101010 Еб -26 - 01101100 4727 - 01000001 4828 - 00111001 Е 9- 29 - 11101101 5030 - 00101111 5131 - 11100011 5232 - 00000100 53 -33 - 100000 1 54ЗЕ - 10001000- 55 -35 - 01010001 5636 - 00001101 5737 - 10011110 5838 - 01011111 59 -39 - 00100110 6040 - 11011100 6141 - 1101001162 11010110 01011001 00011100 10000100 11100001 10011111 01110001 11101011 00010101 10111011 00110110 1110100010100000 10100110 10011100 11000100 11110110 10111111 10010111 01100000 11110001 0 - 11111111 1 - 10000000 2 - 01000000 3 - 00010111 Е - 00100000 5 - 11100110 6 - 10001011 7 - 11100100 8 - 00010000 9 - 00110100 10 - 01110011 11 - 01110000 12 - 11000101 13 - 11011000 14 - 01110010 15 - 01011 О 16 - 00001000 17 - 0001000 1 18 - 00011010 19 - 10111110 20 - 10111001 Рассмотрим работу устройства при основных операциях по фиг. 1 при использовании поля СР (28), Элементы поля образуются с помощью полинома д(Х) = Х + Х + Х + Х + 1 и их представление в нормальном базисе приведено ниже. Характерной особенностью элементов поля СР (2 ), представленпных в нормальном базисе, является их запись в виде где а, - коэффициенты, принимающие значение 0 и 1 для двоичного п.ля.1635193 247 - 11001110 248 - 01111100 249 - 01110101 250 - 01001010 251 - 10011101 252 - 11101010 253 - 00111011 254 - 01110110 255 - 11111111 237 - 10110100 238 - 00110011 239 - 01100111 240 - 11100101 241 - 00111110 242 - 11111001 243 - 10111010 244 - 00011000 245 - 00100101 246 - 01101001 Здесь десятичные числа являются степенью1, Умножение и сложение входныхданных.Требуется произвести следующиедействия. 1 1+ 1 г)1где К, ф 1, М" и 0( - элементы поляСР (2"),Элементы поля подаются: на А -Ф,В - 0, С - 0 Р, В - К , В начальныймомент времени Т управляющие сигналы Б и Б, которые подаются на управляющие входы мультиплексоров 1 и2, соединяют входы А с входами регистра 4 сдвига и входы В с входамирегистра 5. В результате этого нарегистр 4 записывается элементМ ,на регистр 5 - элемент К). В следующий момент времени с укаэанныеэлементы поступают на входы умножителя 6, на выходе которого получаютпроизведение 0( К . Произведениепоступает на сумматор 8, где складывается с нулевой комбинацией. В данном случае сумматор 8 по модулю дванакапливающего типа (фиг, 2) построен на основе Р-триггеров, инверсныйвыход которых подсоединен на свойО-вход.1В момент временисигналы Б иБ изменяют свое значение и подклю 2чают на входы регистров 4 и 5 соответственно входы С и Р устройства.В результате на регистр 3 записывается элемент 0(, а на регистр 4 - элемент К". В следующий момент С 4 в умножителе 6 получается произведениеф 0 0(, которое складывается в сумматоре 8 с К. К, В результате навыходе Е получается.0 М + 0(" С,Укаэанные операции нужно производить при кодировании и декодированиипомехоустойчивыми кодами,2, Возведе,ие в степень М элемента поляУкаэанную операцию опишем на примере поля СГ (2 ). Степень И в двоичВном представлении записывается какоВ = Ь 0 2 + Ъ 2 + Ъ;2 + + + Ьт 27, (2) 25Таким образом,и ь,а" ь, га, г+,+ь, аЬ Ъ 2 Ь 2 Ъаоэффициенты Ьо Ь . Ьт принимают значение 0 или 1.Из выражений (2) и (3) видно, чтовозведение в степень И можно заменить, перемножением сомножителей52 35Каждйй из сомножителейполучают путем сдвига содержимого регистра 4.Работу схемы рассмотрим с помощьювременной диаграммы на фиг, 2. На 40 линии А показаны синхронизирующиеимпульсы ТВ начальный момент времени сигналы Б и Б 2 (фиг, 2, линии Би Б 2) подключают входы А через мультиплексор 1 на входы регистра 4, авходы В через мультиплексор 2 - иавходы регистра, 5, На входы А подается , а на входы В - М. Таким образом, в момент с 1 на регистр 4 записан элемент поля Р , а на регистр5 - К , Сигнал Б (фиг. 2, линия Б)изменяется в соответствии с двоичнймпредставлением И, Например, если р211то М = (11110001) - старший разрядслева, Б = 1 и выход регистра 4 через мультиплексор 3 подключается навход умножителя 6, а Б в момент вре 2мени й подключает выход умножителя6 на вход регистра 5, т.е. замыкаетцепь обратной связи. Произведение навыходе умножителя 6 появляется с задержкой 6. В результате в регистр 5записывается (3 . В момент временитакже подается сигнал сдвига Б 5 нарегистр 4, в результате чего его содержимое сдвигается циклически наодин разряд вправо, Следовательно,при сдвиге на один разряд в регистре4 появляется величина р . Далее навходах умножителя 6 появляются р с-гвыхода регистра 4 и Я с регистра 5,2.Произведениепо цепи обратнойсвязи с выхода умножителя 6 (фиг. 2,линия 6) через мультиплексор 2 записывается в регистр 5. Далее работасхемы происходит аналогично в соответствии с временной диаграммой(фиг, 2). При появлении в двоичномпредставлении М нулевого разряда Б = 200 (фиг, 2, линия Б) через мультиплексор 3 на входы умножителя 6 проходит Мо с входа К (фиг, 2, линия 3) .Следовательно, в регистр 5 переписыется его предыдущее значение. 25В конце цикла вычислений открывается блок 7 ключей с помощью сигналаБ 4 и р выдается на выход Р уст- Нройства,3, Деление единичного элементаона, т,е. операцияВ поле СР (20) произвольный эле 255мент поля Р = 1, т.е.= 3 .яИТаким образом, операция ( аналогична возведению в степень М = 254, Вдвоичном представлении И = (11111110) .Далее процесс аналогичен предыдущемурежиму.4, Возведение в отрицательную степеньи зн 40В данном случае= Р . Величина 255-И представляется в двоичном виде, в соответствии с которойуправляет мультиплексором 3 сигналБ , Дальше процесс аналогичен процессу вычисления Р по и. 2,5. Вычисление произведенияПроцесс вычислений аналогиченп. 2, за исключением момента С, вкоторый на вход В подается вместо Кэлемент поля 6, Вычисление произведения ,ф- ф,Процесс вычисления аналогиченп, 4, однако в момент 1 на вход Ввместо К подается элемент поляоФормула изобретенияВычислительное устройство в поле Галуа СР (2 ), содержащее три мульттиплексора, регистр, умножитель, ре гистр сдвига, сумматор по модулю два и блок ключей, выход регистра подключен к первому входу умножителя, выход которого подключен к первому входу блока ключей, первые информационные входы первого, второго и третьего мультиплексоров соединены с первым, вторым и третьим входами данных устройства соответственно, выход умножителя соединен с вторым информационньм входом второго мультиплексора, выход которого соединен с входом регистра, управляющие входы первого, второго и третьего мультиплексоров, второй вход блока ключей и управляющий вход регистра сдвига соединены с соответствующими управляющими входами устройства, выход сумматора по модулю два является первым выходом данных устройства, вход сумматора по модулю два соединен с выходом умно- жителя, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, сумматор по модулю два выполнен накапливающим, последовательный выход регистра сдвига соединен с его последовательным входом, выход блока ключей является вторым выходом данных устройства, второй информационный вход первого и третий информационный вход второго мультиплексоров соединены с четвертым и пятым входами данных устройства соответственно, выход первого мультиплексора подключен к параллельному входу регистра сдвига, параллельный выход которого подключен к второму информационному входу третьего мультиплексора, выход которого соединен с вторым входом умно- жителя./ФФ 41е й ч еЦф Фиг 7 Редактор А.Лежнина Заказ 757 Тираж 414 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, И-Э 5, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 1(Т Составитель В,БерезкинТехред А,Кравчук Корректор В.Гирняк й й