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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1)4 С 06 Р 7/4 ТЕНИЯ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ И А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР У 900281, кл. С 06 Р 7/49, 1982.Авторское свидетельство СССР В 1383338, кл. С 06 Р 7/49, 1986ЯО 1499334 А 1 2(54) ПАРАЛЛЕЛЬНОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В ПОЛЕ ГАЛУА СР(2 )(57) Изобретение относится к области вычислительной техники и может быть использовано в устройствах копирова- . ния помехоустойчивыми кодами при передаче данных. Цель изобретения - упрощение устройства. Параллельное устройство для умножения в поле Галуа СР (2 ) .содержит и блоков 1-1,1-2, 1-и ключей, в каждый из которых входят и элементов И 2-1,2-2,2-и и и групп сумматоров 3- 1, 3-23-и по модулю два, соединенные между собой функционально. 3 ил., 1 табл,О е3 14993Изобретение относится к областивычислительной техники и может бытьиспользовано в устройствах кодирования помехоустойчивыми кодами при пе 5редаче данных.Цель изобретения - упрощение устройства.На фиг.1 представлена структурнаясхема параллельного устройства для Оумножения в поле Галуа СР (2"); нафиг.2 и 3 - функциональная схема параллельного устройства для умножения в поле Галуа СР (2 О),варианты.Параллельное устройство для умножения в поле Галуа СР (2") содержити блоков 1-1, 1-21-и ключей, вкаждый из которых входят и элементовИ 2-1, 2-22-и и и групп 3-1,3-23-и сумматоров по модулю два, 20соединенные между собой функциональ"но,Параллельное устройство для умножения в поле Галуа СР (28) элементов,представленных в нормальном базисе спомощью полинома ц(х)=х"+х +х +х +1,6содержит восемь блоков 1-1, 1-21-8 ключей, в каждый из которых входит по восемь элементов И 2-1,2-2,,2-8, причем каждая входная цельмножимого А(х) соединена соответственно с первыми входами элементов Иблоков 1- 1, 1-21-8 ключей, ивосемь групп 3-1,3-23-8 сумматоров по модулю два, при этом выходы 4,567 элементов И блоков1-1, 1-21-8 ключей соединены свходами сумматоров групп 3-1,3-23-3 следующим образом: входы сумматора 3-1-1 соединены соответственно 40с выходами 6,18,19,20,22,30,32,33 и39 элементов И, входы сумматора 3-1-2соединены соответственно с выходами10,17,21,24,38,45,50 и 57 элементовИ, входы сумматора 3-2-1 соединены 45соответственно с выходами 15,27,38,48,56 и 62 элементов И, входы сумматора 3-3-1 соединены соответственно а выходами 7,24,28,29,38,41,50,51и 57 элементов И, входы сумматора 503-5-1 соединены соответственно с выходами 11,19,25,33,42,46,47,56 и 59элементов И, входы сумматора 3-7-2соединены соответственно с выходами5,10,12,14,15,21,39,43 и 52 элементов И, входы сумматора 3-7-1 соединены соответственно с выходами 20,34,55,60 и 65 элементов И, входы сумматора 3-1-3 соединены соответствен 34 4но с выходами 9, 14, 34,44,47,53,55, 61и 67 элементов И, и с выходами 68 и69 сумматоров 3-1-1,3-1-2, входы сумматора 3-2-2 соединены .соответственно с выходами 4,27,29,41,43,47,53,54,59,61,64 и 66 элементов И и с выходами 68 и 70 сумматоров 3-1-1,3-2-1, входы сумматора 3-3-2 соединены соответственно с выходами 6,9,1,13,20,32,35,39,44,60,63 и 65 элементов И и с выходами О и 71 сумматоров3-2" 1, 3-3-1, входы сумматора 3-4соединены соответственно с выходами5,8,10,12,15,16,8,22,33,36,37,47,48,52,53,59,65 и бб элементов И и свыходом 7 сумматора 3-3-1,входысумматора 3-5-2 соединены соответственно с выходами 14,16,27,32,37,60,61,62 и 66 элементов И и с выходами69 и 72 сумматоров 3-1"2,3-5-1, входы сумматора 3"6 соединены соответственно с выходами 5.,6,7,12,23,26,28,30,40,52,54,6 и 66 элементов И ис выходами 72 и 4 сумматоров 3-5-1,3-7-1, входы сумматора 3-7-3 соединены соответственно с выходами 6,11,16,32,35,37,39,44,49,52,57,63 и 64элементов И и с выходами 73 и 74сумматоров 3-7-2,. 3-7-1, входы сумматора 3-8 соединены соответственно с выходами 8,9,19,23,24,25,30,36,38,41,44,46,48,52,58,61,64 и 65 эле-ментов И и с выходом 73 сумматора3-7-2, вторые входы элементов И блоков 1-1, 1-21-8 ключей соединены с соответствующими входами множителя В(х), выходы групп сумматоровявляются выходами С(х) устроиства,Устройство работает следующим образом,Множимое А(х) и множитель В(х), как и в известном устройстве, представляются в виде выраженийй- л-А(х)=, а;х и В(х)=, Ь х, (1);-о :оВ данном случае а; и Ь равно двоичной 1 или О. Величину хвсегда можно представить через примитивный элемент поля СР (2"), т.е.5Тогда (2) представляется так А(х) В(х)=, ., а , Ь оь, (4)1=0 ао а аКонкретное представление х в виде (3) зависит от полинома, порождающего поле СР (2 ). Покажем принципы построения параллельного устройства умножения элементов поля Галуа СР (2 ), образованного с помощьюВполинома е(х)=х +х +х +х + 1, Элементы поля представлены в таблице. 14993 А(х) В(х) = /аоЬ + аЬб + а, Ь 7 + а Ъо + а Ьо + а Ьз + а Ь +(5) 55 Формула изобретения В соответствии с полученной формулпй синтезировано устройство для умножения двух элементов поля Галуа СР (2 о) (фиг,2), Это устройство построено на элементах И, образующих матрицу размером 88, и сумматорах по модулю два. Из представленного выражения также видно, что некоторые 34 6Десятичные числа представляют собой степени О .В данном случае множитель и множимое можно представить в виде7 7;:о хОС помощью уравнения (4) и таблицы произведение А(х) В(х) приводится к виду суммы в круглых скобках совпадают иэто уменьшает количество сумматоровпо модулю два. Параллельное устройство для умно.жения в поле Галуа СР (2"),содержа1499334 щее и блоков ключей, в каждом из которых имеется и элементов И, приэтом вход каждого разряда первогомножимого устройства соединен с первыми входами и элементов И соответствующего блока ключей и и блоковсуммирования, выходы которых являются выходом устройства, о т л и ч аю щ е е с я тем, что, с целью упрощения устройства, блоки суммированиявыполнены в виде п групп сумматоров по модулю два, входы с первого поп-й каждого из которых соединены соответственно с теми выходами и блоков ключей, которые определяются видом порождающего поле Галуа СР (2")полинома,причем вход каждого разрядавторого множимого устройства соединен с вторыми входами элементов И со-ответствующего разряда всех блоковключей. 1 О Галуа СГ (2 )6 Элементы поля 35 36 37 0100001 0000101 10011110 01011111 00100110 38 39 40 1011100 11010011 1100110 О 011001 00011100 10000100 11100001 10011111 01110001 11101011 00010101 10111011 00110110 11101000 10100000 10100110 10011100 11000100 11110110 10111111 10010111 01100000 11110001 10101011 00000010 1,0011011 11010000 01100011- 01000100 10310110 00010100 10010101 11111011 00100001 13001000 01000100 105 - 10010000 106 - 01130100 107 - 01100100 108 - 01010000 109 - 00300011 310 - 01010011 10000010 11011011 11000131 - 0100001110100010 - 00111101 177 178 - 179 180 .181 182 141 142 143 344 145 146 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 33 32 33 34 11111111 10000000 01000000 00010111 00100000 31100110 10001011 11100100 00010000 00110100 01110011 01110000 11000101 11011000 01110010 01011110 00001000 00010001 00011010 10111 О 10111001 10101101 00111000 11000011 11100010 00101010 01101100 01000001 00111001 11101101 00101111 11300011 00000100 10100001 10001000 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 бб 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 0101000 10110111 10000110 01311010 О 001111 00010010 10101111 10100011 00010011 10000001 03101110 11011010 11101001 1000130 0110101 О 010101 10101100 000101 О 00001310 0001011 01000010 10001100 33110000 100001013003111 01010010 10331000 10000011 11110101 00001010 10001010 1001010 11011101 111101 0001101. Гратилл ехр КНТ ССС комбинат "Патент", г. Ужгород, ул, Гагарина, 101 оизводственно-издател В, Гусевавчук Заказ 4694/47 Тираж 668 П ВНИИПИ Государственного комитета по изобрете