Устройство для умножения элементов в поле галуа gf(2 )

(57) Излительнпользовчислителцессора 3 СР ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВ 4289768/24-2424.07.8723.10.89. Бюл. У 39Объединенный институдованийН.М.Никитюк681.325(088.8)Гуськов Б.Н., Калиннев В.Р. и др. Быстроараллельный счетчик,ника эксперимента, 1 ПВ У 0061345,11/10, опублик. 1982. РОИСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕПОЛЕ ГАЛУА СР (2 )бретение относится к вычисй технике и может быть исно в специализированных выьных устройствах и микропрооперирующих над элемента 801517 ми поля Галуа, а также в системахкодирования, в устройствах обнаружения и исправления ошибок в кодовыхсловах, построение которых базируется на теории полей Галуа СР (2 )Цель изобретения - расширение функциональных возможностей за счет одновременного умножения Б ненулевыхэлементов поля Галуа СР (2 ), В устройство для умножения элементов вполе Галуа СР (2 ), содержащее Бблоков преобразования 2.1-2,Ю элементов поля Галуа СР (2 ) в двоичныекоды, первый сумматор 5 п модулю2 - 1 и блок преобразования 7 двоичных кодов в соответствующие имэлементы поля Галуа СР (2), введенвторой сумматор 4 по модулю 2 - 1,ш-разрядный сумматор 6 и циклическийкомпрессор 3, содержащий М каскадовпо ш групп (и, К)-параллельных счетчиков3 ил, 1517022Изобретение отнрсится к вычислительной технике и может быть ис 20 пользовано в специализированных вычислительных устройствах и микропроцессорах, оперирующих над элементами в поле Галуа, а также в системах кодирования, в устройствах обнаружения и исправления ошибок в кодовых словах, построение которых базируется на теории полей Галуа СР (2 ).Цель изобретения - расширение функциональных возможностей за счет одновременного умножения И ненулевых элементов поля Галуа СР (2 ).На фиг, 1 приведена функциональная схема устройства для случая когда ш = 4, т,е, умножения пятнадцати элементов поля Галуа СР (2 на фиг. 2 - один из вариантов конкретной реализации циклического компрессора для случая, когда ш = 4; на фиг. 3 - пример одновременного суммирования 15 степеней элементов поля Галуа при использовании вариан та циклического компрессора.Устройство для умножения (фиг, 1) содержит входы 1,1-1.15 для сомножителей, блоки 2.1-2,15 преобразованияэлементов поля ГалУа СР (2 ) в двоич ные коды, циклический компрессор 3, сумматоры 4 и 5 по модулю 2"- 1, 4-разрядный сумматор 6, блок 7 преобразования двоичных кодов в соответствующие им элементы поля Галуа СР (2 ) и выход 8 устройства умноЬ 1 35 жения.Циклический компрессор 3 (фиг. 2) содержит (15,4)-параллельные счетчики 9-12, (2,2)-параллельные счетчики 13-18, (3,2)-параллельные счетчики 19-21, (4,3)-параллельный счетчик 22 и четыре группы выходов 23- 26.Параллельный счетчик - это уст 45 ройство, которое подсчитывает число сигналов, поступающих одновременно на его входы. Обычно параллельный счетчик имеет и входов и К=1 о 8 и выходов. Данные на входы параллельного счетчика поступают в позиционном50 унитарном коде, а на его выходах получается двоичный код, равный числу единиц на входах. Каждый из входов 1,1-1.15 имеет по 4 шины. Таким образом, каждый из блоков 2.1-2,15 име ет по 4 входные и 4 выходные шины. Все блоки 2.1-2,15 являются идентичньгчи и в каждом из них выполняется преобразование типа а = а.ф 1111; а 0001; а - 0010; а -+ 0013; а 0300 а 01011 а 0110 а -ф 0111; ао - 1000; а 1001а" 1010 а" 1011; а" - 1100;1101; а" 1310.Каждый из блоков имеет по 4 выхода, имеющие двоичные веса 2 , 2, 2 и 2 , Выходы с равносильными ве 2 3сами объединены в группы по 15 шин в каждой группе.Работа основана на свойстве цикличности поля Галуа, которое для случая ш = 4 образуется над непри" водимым полиномом четвертой степени Х + Х + 1. Полагая, что а = 0100 есть корень этого полинома, получают 14 остальных его элементов из уравнения а + а + 1 = О, где знак4"+" означает суммирование по модулю два, а операции сложения и вычитания равнозначны, В этом поле имеетсяо 4 линейно независимых элемента а - 1000 = 1; а = 0100; а= 0010 и а = 0001. Из уравнения а = а + + а получают, что а = 1100; а4а а=а +а=0110; аа а=а +а =0011; а=аз +ха=а +а =а +а +а=1101.Аналогично получают а = 1010 а = 0101; а= 1110; а" = 0111;12 1111, 13 101114 1001 силу цикличности поля, так как 2 -1 = 15. Далее степень произведения элементов равна циклической сумме степеней каждого из сомножителей.14 19 15 4а или, складывая число 5 = 0101 и число 14 = 1110 по модулю 15, получают,0101 1110 0011 1 0100 = 4 Выполняя обратное преобразование 0100 -+ 1100 = а , получают окончательный результат произведения двух элементовДопустим, что необходимо одновременно умножить 15 единичных элементов а = ав поле Галуа СР (2 ).О Коды, соответствующие элементу а1000, одновременно подаются на входы блоков 2.1-2.15, на выходах которых формируются коды 1111 = 15.1517022Затем с помощью циклического компрессора происходит суммиронание единиц, выполняющееся параллельно по столбцам (фнг. 3). В каждом столбце содержится по 15 = 1111 единиц. Эти единицы записываются по диагонали так, что старший разряд суммы весов 2 оказывается записанным под цифраоми четвертого столбца, где содержатз10 ся цифры с весом 2 . Аналогично записываются результаты суммирования единиц с весами 2 , 2 и 2 . В реэультате после первого этапа суммирования из 15 слагаемых получается 4, которые суммируются на втором этапе. Аналогично на третьем этапе ныполняется суммирование уже трех операндов. При этом вертикальной линией отделены те ци 3 ры, которые нозникают в результате циклического переносаПосле суммирования на третьем этапе получается два слагаемых, т.е. из 15 двоичных 4-разрядных чисел получается два 8-разрядньж двоичных числа. Эти числа разделены на две группы, по четыре разряда в каждой группе, По существу числа слева от вертикальной линии представляют собой циклические переносы, которые возникают при суммировании чисел на соответствующих этапах 2,3,4 (фиг, 3). С помощью сумматора 4 получается результат суммирования без учета циклических переносов, С помощью сумматора 6 получается число, равное общему количеству циклических переносов, которое равно 11010000. Старшие разряды этого числа 1101 складываются с результатом, полученным на выходах сумматора 4. После суммирования на выходах сумматора 5 получается код 0110, и на выходах блока 7 формируется элемент произведения а = а . Данный пример характерен тем, что он дает величину максимального количества циклических переносов, которое может получиться при циклическом суммировании в поле СР (2 ). Эта величина равна 1101000. Тем самым отпадает необходимость в использовании циклического переноса н сумматоре 6.Блок 7 представляет собой устрой-. ство, в котором выполняется преобразование двоичного кода, соответствующего степени произведения в элемент поля Галуа СР (2 ), равный произведению. При этом выполняется преоб ра эование следующего вида: 0001 - а0100 0010 а 0030; 0011 а=0001 Ф 0100 а щ 1100; 0101 - а0330; 0110 -е а = 0011; 011 - ф -а 101 1000 -ф а ф1010;1001 -ь а 0101; 1 ОО -е а = 13103 3011 -ф а" = 01113 3100 - а= 1111 1101 - а" = 10113 1110 - а= 3001;1111 -. а ф= аф = 1000. Формула изобретения Устройство для умножения элементов в поле Галуа СР (2"), содержащее0 блоков преобразования элементовполя Галуа СР (2 ) в двоичные коды(2 с К " 2 - 1), первый сумматорпо модулю 7. - 1 и блок преобразования двоичных кодов в соответствующие им элементы поля Галуа СР (2 ),причем выходы первого сумматора помодулю 2 - 1 соединены с входами 25 блока преобразования двоичных кодовв соответствующие им элементы поляГалуа СР (2 ), выходы которого соединены с выходами устройства, информационные входы которого соединеныс входами блоков преобразования элементов поля Галуа СР (2) в двоичныекоды, выход старшего разряда первогосумматора по модулю 2 " - 1 соединенс входом младшего разряда первогосумматора по модулю 2 - 1, выходыоодинаковлж двоичных Весов 22 2 - 1 И блоков преобразованияэлементов поля Галуа СР (2 ) вдвоичные коды объединены в ш групп, 40 0 т л и ч а ю щ е е с я тем, что,с целью расширения функциональныхвозможностей за счет одновременногоумножения Ю ненулевых элементов поля Галуа СР (2"), введены второй 45сумматор по модулю 2 - 1, ш-разрядный сумматор и циклический компрессор, содержащий М каскадов(М - количество двоичных цифр в числе в)пош групп (и, К)-параллельных счетчиков (К = 108 п) и имеющий ш групппо 2 - 1 входов и четыре группы пош выходов, причем выходы Х блоковпреобразования элементов поля ГалуаСР (2) соединены с соответствующимивходами (и, К)-параллельных счетчикон,первого каскада циклического компрессора, выходы первой и второй групп1517022 входом младшего разряда второго сумматора по модулю 2 - 1, выходы(и, К)-параллельных счетчиков ь-го 5каскада (д = 1,2 М) циклического компрессора, кроме выходовмладших разрядов, соединены с входами соответствующих двоичных весов( + 1)-го каскада циклического компрессора, выходы младших разрядов(и, К)-параллельных счетчиков каждого каскада циклического компрессорасоединены соответственно с входамиМ младших разрядов второго сумматора по модулю 2 - 1. 11 1 1 7 1 1 1 11 1 77 Раг 1 11 6Фиг 3 Составитель Е. МурзинаРедактор О, Ирковецкая Техред Л.Олийнык Корректо нчакова аказ 6391/51 Тираж 668НШ 1 ПИ Государственного комитета по изобретениям и 113035, Москва, Ж, Раушская цаб Подписноеоткрытиям при ГКНТ СССР ю д ф роизводствеццо-издательский комбинат "Патент , г.ужгорол, ул. Гагарин динены соответственно с входами старших т - М разрядов первого и второгослагаемых второго сумматора по модулю 2 - 1, выход которого соединен свходом первого слагаемого первогосумматора по модулю 2 - 1, входвторого слагаемого которого соединенс выходом ш-разрядного сумматора,входы первого и второго слагаемыхкоторого соединены соответственно свыходами третьей и четвертой групп(и, К)-параллельных счетчиков М-гокаскада циклического компрессора,выход старшего разряда второго сумматора по модулю 2" - 1 соединен с 1577 7 ф1 1 1 11 1 61 11 1 111 11 1 1 111 11 1117 71 1 11 11