Четырехзначный умножитель элементов поля галуа gf(2 @ )

 

Изобретение относится к вычислительной технике и кибернетике и может быть использовано в цифровых вычислительных машинах и системах, видеои звуковых цифровых системах, а также в системах кодирования информации, устройствах обнаружения и исправления ошибок кодов Рида-Соломона. Цель изобретения - упрощение устройства. Четырехзначный умножитель содержит два преобразователя 1 двухзначных кодов в четырехзначные, блок 2 умножения и преобразователь 6 четырехзначного кода в двухзначный. Блок 2 умножения состоит из шестнадцати ячеек формирования частичных произведений, четырех ячеек нормализации первой ступени, шести ячеек нормализации второй ступени и узла суммирования. 3. з.п. ф-лы, 9 ил.

(19) (11) СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)а 6 06 F 7/49- Н 03 К f 9/С8

ГОСУДАРСТВЕН.ЫЙ КОМИТЕТ .

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1, (2 1) 4845113/24 (22) 28,66.9О (46) 30 05,92. Бал. й. 20 (71) Научно-исследовательский институт бы- товой радиоэлектронной аппаратуры (72) И,И.Ковалив и З.Д,Коноплянко (53) 681„325(088.8) (56) ВаГ1ее 7 С., Schnekder D.Z. Computation lth Finite Веаэ. — Ыоюо and Cones), 1963, ЬЬ 63, р. 74-98.

Авторское свидетельство СССР

М 90Î281, кл, 6 О6 F 7/49, 1991. (54) ЧЕТЫРЕХЗНАЧНЫЙ УМНДЖИТЕЛЬ

ЭЛЕМЕНТОВ ПОЛЯ ГАЛУА GF(2 (57) Изобретение относится к вычислительной технике и кибернетике и может быть . использовано в цифровых вычислительных машинах и системах, видео- и звуковых цифровых системах. а также в системах кодирования информации, устройствах обнаружения и исправления ошибок кодов

Рида-Соломона. Цель изобретения — упроацение устройства. Четырехзначный умножитель содержит два преобразователя 1 двухзначных кодов в четырехзначные. блок

2 умножения и преобразователь 6 четырехзначного кода в двухзначный. Блок 2 умножения состоит из Шестнадцати. ячеек формирования частичных произведений. четырех ячеек нормализации первой ступени, шести ячеек нормализации второй ступени и узла суммирования. 3. з.п. ф-лы, 9 ил, 1737443

Изобретение относится к вычислительной технике и кибернетике и может быть использовано в цифровых вычислительных машинах и системах, видео- и звуковых цифровых системах, а также в системах кодирования информации, устройствах обнаружения и исправления ошибок кодов РидаСоломона.

Известен умножитель элементов поля

GF(2 ), построение и работа которого основывается на специальных уравнениях над полем.GF(2 ).

Недостатками этого устройства являются его сложность и большое число функциональных связей.

Наиболее близким к предлагаемому является устройство умножения произвольных элементов полей Галуа ОЕ(р"), содержащее и модульных блоков умножения, и блоков формирования частичных произведений и и блоков суммирования, причем входы первых групп модульных блоков умножения соединены с входами производящего полинома устройства, входы второй группы первого модульного блока соединены со входами первой группы первого блока формирования частичных произведений и входами первой группы произвольных элементов полей Галуа GF(p") устройства, выходы каждого модульнога блока умножения соединены с входами первой группы блоков формирования частичных произведений, входы второй группы каждого блока формирования частичных произведений соединены с соответствующими входами второй группы произвольных элементов полей Галуа GF(p"j, входы каждого блока суммирования соединены с выходами блоков формирования частичных произведений, выходы блоков суммирования являются выходами устройс ва.

Недостатками устройства является большое число функциональных межсоединений и связей, в частности каждый вход и выход модульных блоков умножения, блоков формирования частичных произведений и блоков содержит (р - 1) шину, а число таких блоков пропЬрционально п. Таким образом, с увеличением порядка поля Галуа GF(p") возрастает и число функциональных связей, что усложняет реализацию таких устройств в виде БИС иэ-за увеличения площади кристалла, отводимой под металлизацию, а также из-за увеличения числа уровней металлиэации интегральный схемы.

Цель изобретения — упроЩение устройства.

Для достижения поставленной цели в четырехзначный умножитель элементов поля Галуа GF(28), содержащий блок умножения, состоящий из шестнадцати ячеек формирования частичных произведений и узла суммирования, выход которого соединен с выходом блока умножения, входы первой группы которого соединены с входами производящего полинома умножителя, введены два преобразователя двухзначных кодов в четырехзначный и преобразователь четырехэначного кода в двухзначный, а в блок умножения введены четыре ячейки нормализации первой ступени и шесть ячеек нормализации второй ступени, причем разрядные входы множимого и множителя умножителя соединены соответственно с

10 входами первого и второго преобразователей двухэначнмх кодов в четырехзначный, выходы которых соединены соответственно с входами второй и третьей групп блока умножения, выход которого соединен с вхо-. дом преобразователя четырехзначного кода в двузначный, выход которого соединен

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

j-м входом второй группы блока умножения, второй вход (I, j)-й ячейки формирования частичных произведений матрицы соединен соответственно с 1-м входом третьей группы

30 блока умножения, третий вход (1, 1)-х ячеек формирования частичных произведений матрицы соединен со входом логического нуля умножителя, выход переноса (i, j)-й ячейки формирования частичных произведений матрицы, кроме выходов переноса (I, 4)-х ячеек, соединен соответственно с третьим входом (1, j + 1)-й ячейки формирования частичных произведений матрицы, выходы

40 переноса (i, 4)-х ячеек формирования частичных произведений матрицы соединены с входами соответствующих ячеек нормалиэации первой ступени, выходы суммы j-x ячеек формирования частичных произведений в каждой i-й строке матрицы соединены соответственно с входами первой группы

k-й ячейки нормализации первой ступени, (k =

1, ..., 4), входы второй группы которой соединены с входами первой группы блока умноже- . ния и входами первой группы ячеек нормализации второй ступени с первой по шестую, выходы первой ячейки нормализации первой ступени соединены со входами первой группы узла суммирования, выхода второй, третьей и четвертой ячеек нормализации первой ступени соединены соответственно со входами второй группы первой, второй и третьей ячеек нормализации вто50

25 зуют матрицу размерностью (i, j), где i = 1, ..., 4; 1=1,..., 4, причем первый вход(1, j)-й ячейки формирования частичных проиэве1737443 рой ступени, выходы второй и третьей ячеек нормализации второй ступени, соединены соответственно с входами второй группы четвертой и пятой ячеек нормализации второй ступени, выходы пятой ячейки нормализации второй ступени соединены с входами второй группы шестой ячейки нормализации второй ступени, выходы первой, четвертой и шестой ячеек нормализации второй ступени соединены соответственно со входами второй, третьей и четвертой групп узла суммирования.

Каждая ячейка формирования частичных произведений содержит схему умножения инжекционного типа и сумматор инжекционного типа, причем первый и второй входы схемы умножения инжекционного типа соединены соответственно с первым и вторым входами ячейки, а первый и второй выходы — с выходом переноса ячейки и первым входом сумматора инжекцион ного типа, вто. рой вход которого соединен с третьим входом ячейки, а выход — с выходом суммы ячейки.

Кроме того, каждая ячейка нормализации первой ступени содержит формирователь весовых коэффициентов производящего полинома и четыре сумматора инжекционного типа, причем входы с первого по четвертый формирователя весовых коэффициентов производящего полинома соединены с входами второй группы ячеек, входы первой группы которой соединены с первыми входами соответствующих сумматоров инжекционного типа, вторые входы которых соединены с соответствующими выходами формирователя весовых коэффициентов производящего полинома, пятый вход которого соединен с входом ячейки, выходы которой соединены с выходами сумматоров инжекционного типа.

Каждая ячейка нормализации второй ступени содержит четыре ячейки формирования частичных произведений, три сумматора инжекционного типа и формирователь весовых коэффициентов производящего полинома, входы которого соединены со входами первой группы ячейки, а выходы -с первыми входами соответствующих ячеек формирования частичных произведений, четвертый вход второй группы ячейки соединен с вторыми входами всех ячеек формирования частичных произведений, третий вход 1-й ячейки формирования частичных произведений соединен соответственно с выходом переноса (I - 1)-й ячейки, формирования частичных произведений (I = 2, 3, 4), выходы суммы первой, второй и третьей ячеек формирования частичных произведений соединены соответственно с первыми входами первого, второго и третьего сумматоров инжекционного типа, вторые входы которых соединены соответственно с третьим, вторым и первым входами второй группы ячейки. первый выход которого соединен с выходом четвертой ячейки формирования частичных произведений, выходы третьего, второго и первого сумматоров инжекционного типа соединены соответственно со вторым, 10 третьим и четвертым выходами ячейки

На фиг. 1 приведена структурная схема четырехзначного умножителя элементов поля Галуа GF(28); на фиг, 2 — структурная схема блока умножения; на фиг. 3- структурная схема ячейки формирования частичных пролуа в двузначные, при этом группы входов 7 и 8 преобразователей 1 образуют разрядные входы множимого и множителя четырехзначного умножителя, а их выходы 3 и 4

35 соединены с соответствующими входами блока 2 умножения, выходы 9 которого подключены соответственно к входам байтного преобразователя 6, выходы 10 последнего образуют выход устройства в целом.

Блок 2 умножения состоит из шестнад40 цати ячеек 11 формирования частичных произведений, четырех ячеек 12 нормализации первой ступени, шести ячеек 13 нормализа45 ции второй ступени, блока 14 суммирования, выходы 15 ячеек 11 формирования частичных произведений подключены к соответствующим входам ячеек 12 нормализации первой ступени, вторые входы которых

50 являются третьей группой входов блока умножения и соединены с входами 5 производящего полинома устройства. выходы 16 первой ячейки 12 нормализации первой ступени подключены к входам 17 — 20 блока 14 суммирования, выходы 16 второй ячейки 12 нормализации первой ступени подключены к входам первой ячейки 13 нормализации второй ступени, выходы 21-24 изведений; на фиг. 4 — структурная схема ячейки нормализации первой ступени; на фиг. 5 — структурная схема ячейки нормализации второй ступени; на фиг. 6 — структур20 ная схема блока суммирования; на фиг. 7— принципиальная схема двухвходового умножителя; на фиг. 8 — принципиальная схема двухвходового сумматора; на фиг. 9— принципиальная схема формирователя ве25 совых коэффициентов производящего поли нома устройства.

Четырехзначный умножитель элементов поля Галуа GF(2, "одержит два байтных преобразователя 1 двузначных представле30 ний элементов поля Галуа в четырехзначные. блок 2 умножения с тремя группами входом

3-5 и байтный преобразователь 6 четырехзначных представлений элементов поля Га1737443

25

40

50 подключены к соответствующим входам блока 14 суммирования, выходы 16 третьей ячейки 12 нормализации первой ступени подключены к входам второй ячейки 13 нормалиэации второй ступени, выходы которой через третью ячейку 13 нормализации второй ступени подключены к входам 25-28 блока 14 суммирования, выходы 16 четвертой ячейки 12 нормализации первой ступени подключены к соответствующим входам четвертой ячейки 13 нормализации второй ступени, выходы которой через пятую и шестую ячейки 13 нормализации второй ступени подключены к входам 29-32 блока 14 суммирования, свободные входы первой, второй и четвертой ячеек 13 нормализации второй ступени подключены к входам 5 производящего полинома устройства.

Ячейка 11 формирования частичных произведений содержит двухвходовый умножитель 33 и двухвходовый сумматор 34, причем первый вход двухвходового умножителя 33 соединен с разрядным входом.3 множимого, а второй вход — с разрядным входом 4 множителя, один выход 35 умножителя 33 является выходом переноса Р+, а второй обьединен с первым входом двухвходового сумматора, второй вход 36 которого является входом результата предыдущего переноса Р- матричного умножителя, выход

15 сумматора 34 является выходом результата Р ячейки 11 формирователя частичных произведений, а выход 35 переноса Р+— выходом предыдущего переноса матричного умножителя.

Ячейка 12 нормализации первой ступени содержит формирователь 37 весовых коэффициентов производящего полинома и четыре двухвходовых сумматора 34, входы

5< (где l = 1..... 4) задания весов коэффициентов производящего многочлена, входы

151 (где ) = О, ..., 3) результатов формирования частичных произведений, подключенных к первым входам двухвходовых сумматоров 34, на вторые входы которых поданы значения весовых коэффициентов производящего полинома, а также вход 38 переноса Р+ и выходы 161 результатов нормалиэации значений вычислений матричного умножения.

Ячейка 13 нормализации второй ступени состоит из четырех ячеек 11 формирования частичных произведений, трех двухвходовых сумматоров 34 и формирователя 37 весовых коэффициентов производящего полинома, причем входы 3 множимого первой, второй и четвертой ячеек 11 формирования частичных произведений через формирователь 37. весовых коэффициентов производящего полинома подключены.к соответствующим входам 5 весовых коэффициентов производящего полинома, а вход 4 множителя — к четвертому выходу 16з ячейки 12 нормализации первой ступени, оставшиеся три выхода которого подключены к первым входам двухвходовых сумматоров 34, выходы 39-42 которых образуют три старших выходы 40-42 ячейки 13 нормализации второй ступени, младший разрядный выход непосредственно образован выходом четвертой ячейки 11 формирования частичных произведений, выходы 5 ячейки 13 транзитом передают значения весовых коэффициентов производящего полинома на последующую. ячейку

13, кроме того, у третьей, пятой и шестой ячеек 13 входы 3 множимого ячеек 11 через формирователи 37 подключены к входам 5 задания значений весовых коэффициентов производящего полинома, а входы 4 множителей — к соответствующим выходам 39 — 42 предыдущей ячейки 13, соответственно выходы первой, третьей и шестой ячеек 13 подключены к входам 21-32 блока 14 суммирования.

Блок 14 суммирования содержит двенадцать двухвходовых сумматоров 34, входы нулевых 17-20, первых 24 — 24, вторых

25 — 28 и третьих 29-32 разрядов суммируемых результатов частичных умножений и нормализации первой и второй ступеней, выходы 9 окончательных результатов матричного умножения двух четырехзначных элементов поля Галуа GF(28).

Двухвходовый умножитель 33 содержит первый дискриминатор 43 с. задаваемыми при помощи источников 44 — 46 (инжекторов) с весами 0.5, 1,5, 2,5 порогами срабатывания, входной отражатель 47 тока и пороговые многоколлекторные транзисторы

48 — 50, входящие в состав первого дискриминатора 43, трех- и двухвходовые сумматоры 51-53 тока с регулируемыми инжекторами тока 1.0, 2,0, 3.0; 2.0, 2.0 и 3.0, 2,0, 1.0 соответственно, первый vi второй пороговые дополнительные транзисторы 62 и 63 с инжекторами 64 тока с весами токов

1,0, второй дискриминатор 65 с задаваемыми при помощи источников 66-68 порогами срабатывания с весами 0.5, 1.5, 2.5 соответственно, входной отражатель 69 тока и пороговые транзисторы 70-72, входящие в состав второго дискриминатора, вход 4 которого является входом Yt одного из сомножителей ячейки 33, пятый-девятый дополнительные пороговые транзисторы

73-76 с инжекторами 64 с единичными весами, вход первого дискриминатора 43 подключен к первому входу двухвходового умножителя четырехзначных элементов по1737443 ля Галуа, выход 15 произведения 0 и выход дополнительно, введены три дополнитель35 переноса P+, первый-пятый отражатели ных отражатели 79-81 тока, причем база

77-81 тока с инжекторами 64 с весом 1,0 первогодополнительногоотражателя79тосоответственно и шестой отражатель 82 то- ка подключена к первому коллектору дополка, на входе и выходе которого включены 5 нительного порогового транзистора 76 инжекторы83токасвесами2,0, выходотра- второго канала второго дискриминатора, а жателя 81 является выходом 35 результата база второго дополнительного отражателя переноса Р+, при этом в первом канале пер- 80 тока к коллектору второго дополнительвого дискриминатора 43 коллекторы перво- ного порогового транзистора 63 третьего каго порогового транзистора 48 соединены с 10 нала первого дискриминатора 43, входами первого трехвходового.сумматора коллекторы первого и второго дополнитель51 тока, so втором канале первого дискри- ных отражателей 79 и 89 тока соединены минатора два коллектора второго порого- вместе и подключены к базе третьего дополвого транзистора 49 соединены с входами нитеа ного отражателя 81 тока, коллектор двухвходового сумматора 52 тока, а третий 15 которого подключен к выходу 35 переноса коллектор соединен с базой первого допол- Р+ двухвходового умножителя четырехэначнительного транзистора 62, три коллектора ных элементов поля Галуа. которого подключены к входам первого Двухвходовой сумматор 34 четырех. трехвходового сумматора 51 тока, в треть- значных элементов псля Галуа аналогично ем канале первого дискриминатора три 20 двухвходовому умножителю 33 содержит коллектора порогового трайзистора 50 со- первый входной отражатель 47 тока, входяединены с входами второго трехвходового щий в состав первого дискриминатора 43, сумматора 53 тока, а четвертый коллектор три пороговых пятиколлекторных транэисоединен с базой второго дополнительно- стара 85 — 87 с задаваемыми при помощи исго транзистора 63, два коллектора которо- 25 точников 44-46 с весами инжектируемых го соединены с входами двухвходового токов 0.5, 1.5, 2,5 и с порогами срабатыва- . сумматора 52 тока, первые коллекторы по- ния, три дополнительных четырехколлекроговых транзисторов 71 и 72 второго и торных пороговых транзистора 88 — 90, в третьего каналов второго дискриминатора базы которых включены инжекторы 91 с ве65 подключены соответственно к базам 30 сами 1,0, четырехвходовые сумматоры 92третьего и четвертого дополнительных 95 тока с регулируемыми инжекторами транзисторов 76, первые коллекторы кото- 96 — 111 с весами 3.0, 2.0, 1.0, 0.0; 0.0, 3.0, рых подключены соответственнО к второму . 2.0,, 1.0; 1.0, О.О, 3.0, 2.0; 2.0, 1.0, О.О, 3.0 и первому коллекторам пороговых транзи- соответственно.,атакжевторойдискримисторов 70 и 72 первого и третьего каналов 35 натор 65, включающий второй входной второго дискриминатора 65, первый и вто- отражатель 112 тока, двухколлекторные рой коллекторы пороговых транзисторов пороговые транзисторы 113 — 115 с эадавае70-72 первого, второго и третьего каналов мыми при помощи источников 44 — 46 с весавторого дискриминатора 65 подключены к ми инжектируемых токов 0.5. 1.5, 2.5 с базам пятого, шестого и седьмого допол- 40 порогом срабатывания и три дополнительнительных транзисторов 73-75, эмиттеры, ных пороговых транзистора 116 — 118, в базы которых подключены соответственно к пер- которых включены инжекторы с весами 1.0, вым, вторым и третьим выходам каналов кроме того, в состав сумматора 34 входит трехвходовых 51 и 53 и двухвходового 52 выходной четырехвходовый сумматор тока, сумматоров тока, а коллекторы через вы- 45 состоящий из отражателей 119 — 122 тока, в ходной отражатель тока 95 подключены к базы которых включены инжекторы 123 с выходу 84 произведения, база первого весами З.О, а коллекторы объединены вметранзистора 77 формирователя переноса сте и образуют выход 15 сумматора, к котоподклеченасоответственноквторомуичет- рому также подключен еще один инжектор вертому коллекторам пороговых транзи- 50 123 с весом 3.0, при этом выходы 124-127 сторов 50 и 72 третьих каналов первого 43 второго дискриминатора 65 подключены к и второго 65 дискриминаторов, база вто- соответствующим выходам сумматоров 92— рого транзистора 78 формирователя пере- 95, к которым также подключены.коллектоноса подключена соответственно к ры дополнительных пороговых транэисвторому и третьему коллекторам пороговых 55 торов 117 и 118, базы первого 47 и второго транзисторов 49, 71 вторых каналов первого 112 входных отражателей тока образуют два и второго дискриминаторов, коллекторы входа 36 и 84 сумматора, три коллектора транзисторов формирователя переноса че- отражателей 47 и 112 тока подключены соотрез отражатель 82 тока подключены к выхо- ветственно к базам шести пороговых пяти- и ду переноса двухвходового умножителя, двухколлекторных транзисторов 85-87

1737443

113-115, пятые коллекторы транзисторов

85 — 37 подключены к базам пороговых четырехколлекторных транзисторов 88-90, коллекторы транзисторов 85 и 86, а коллекторы порогового транзистора 88 †. к базам отражателей 96-99 тока первого сумматора 92 тока, Формирователь 37 весовых коэффициентов производящего полинома содержит один четырехколлекторный транзистор 128, база которого образует вход 38 (Р+) формирователя 37, четыре управляемые инжекторы 129-132, эмиттеры которых образуют входы 5 задания весовых коэффициентов производящего полинома устройства, а коллекторы — выходы 133-136 сформированных коэффциентов производящего полинома, коллекторы транзистров 128 подключены к базам управляемых инжекторов 129-132.

Работы умножителя 33 однозначно задается — табл. 1, а двухвходового сумматора

34 четырехзначных элементов поля Галуа— табл. 2, Основные свойства исходных состояний базовых компонент предлагаемого устройства, следующие, Из теории конечных полей GF(q) известно, что производьный элемент поля GF(2 ) порожденного проиэво8 дящим полиномом (B)x = х + х + х + х + 1

З 2 и с примитивным элементом а- 0000 0010 может быть сформирован, за исключением нуля, путем возведения в степень примитивного элемента аполя, т е. GF(256) =(О, aÐ, а1, сР, ..., сР ). Для заданного а(х) коэффициенты при всех его степенях образуют набор однозарядных двоичных чисел 1, О, О, 1, 1, 1, 0,.1 или для дальнейшего перехода к четырехзначным представлениям набор двуразрядных чисел 01, 00, 01, 11, 01. Так называемые весовые коэффициенты производящего полинома а(х).

Предлагаемое устройство в качестве основания системы счисления использует значность К - 4, в которой работают все его арифметические устройства. При этом возникает ряд особенностей в алгоритмах вычисления умножения элементов поля.

Операция умножения по модулю в К-значной логике задается таблицей истинности (см. табл. 1), которая частично совпадает с умножением над полем GF(4).

Обозначим символами из Е (О, 1, 2, 3} упорядоченные элементы поля Галуа GF(4):

0, а - - 1, а - 2, cÐ - 3. Тогда операция суммирования над полем GF(4) описывается в табл. 2.

Для операции умножения над полем

GF(4) определяют соответствие между четырехзначной логикой и полем Галуа GF(2+

Для используемого поля определяют соответствие его элементов с их представлением в Е4. Тогла при использовании весовых коэффициентов порождающего многочле5 на а(х), соответствия записываются в виде

00 - 0; 01 - 1; 10 - 2; 11 = 3, откуда для указанного порождающего многочлена получают кортеж 1, О, 1, 3, 1. Отсюда видно, что преобразование двузначных представле10 ний элементов поля Галуа GF(2 ) в четырехзначные, и наоборот, легко реализуется с помощью преобразователей двузначного кода в четырехэначный и четырехзначного в рауа начн ы й.

15 Операция умножения элементов поля

Галуа GF(2 ), которые соответствуют элементам поля GF(4) и четырехзначной логике, может быть представлена таблицей истинности (см. табл, 3).

20 Табл, 3 получена на основе свойств элементов поля Галуа 6F{2 ), которые формируются путем возведения в степень примитивного элемента а и операции умноженив над данным полем.

25 0000О0» X 000000011= сР а- 5= а5о= 0000 0101;

000000» ХО0000010= а a" = а=

=0000 0» 0 и т.д.

30 Отсюда получаем, что в четырехзначном представлении умножение (см. табл. 1) по модулю 4 совпадает с умножением над полем GF(2 ), но дополнительно возникает перенос, описываемый таблицей истинности

35 (см. табл. 4).

Принципы работы четырехзначного умножителя элементов поля Галуа GF(28) определяются, в основном, функционированием блока 2 умножения, работа которого зависит

40 от принципов действия двухвходовых умножителя 33 и сумматора, а также ячеек 12 и 13 нормализации первой и второй ступени.

Рассмотрим принципы действия перечисленных субблоков, что позволит одно45 значно определить принципы действия устройства в целом.

В основу функционирования двухвходовых умножителя 33 и сумматора 34 положены таблицы истинности (см, табл. 1, 2 и 4). В

50 частности, двухвходовый умножитель ЗЗ формирует результат умножения по модулю

4 (см, табл. 1) и перенос Р+ (см. табл, 4). Если на входы 3 и 4 умножителя 33 поступают входные токи I» такие, что 4х E4 = (О, 1, 2, 55 3), закрываются те из транзисторов 48-50,.

70-72, для которых выполняется условие

4x - lyi, где lsd — ток l-ro инжектора 44-46, 66-68, задающего порог срабатывания в первом 43 и втором 65 дискриминаторах;

1737443

14! ТЯ0.5, 1.5, 2.5}. При этом в базы I é группы транэистров сумматоров тока 51-53 втекают токи соответствующих инжекторов. Одновременно открываются все предыдущие первые дополнительные транзисторы 62 и

63, так как в их базы втекают токи инжекторов 64 с весами 1.0, отключая от баэ соответствующих транзисторов выходных сумматоров 51-53 тока соответствующие инжекторы 54-61 с весами инжектируемых токов 1.0, 2,0, 3.0; 2.0, 2.0 и 3.0, 2.0, 1,0 соответственно.

Транзисторы, входящие в состав I-й группы сумматора тока, открываются и на вторые дополнительные транзисторы 73-75 поступают сигналы отданной 1-й группы транзисторов и к выходу 84 подключается тот сигнал; для которого открыт один из транзисторов 73-75. От инжектора 59 (вес 3.0), включенного в базу выходного отражателя тока, отобрано (вычтено) ток, значение которого

- определяется величиной, задаваемой на одном из выходов I-I I I сумматоров 51-53 тока.

В свою очередь, выходной отражатель тока остаток тока, втекающий в его базу, вычитает из выходного инжектора 59 тока (вес 3.0), включенного в его коллектор и на выход 84 . двухвходового умножителя поступает оставшийся вытекающий ток, вес которого совпадает со значением, поступающим из сумматоров 51 — 53 тока, и соответствует результату умножения двух четырехзначных элементов поля (см. табл. 1), Результат переноса Р+ (см. табл. 4) возникает только для следующих наборов входных сигналов: 22, 32, 23, 33. Отсюда, если на входах 3 и 4 двухвходового умножителя 33 появляются такие сочетания, происходит отбирание тока от инжекторов 64, включенных в базы отражателей 77 и 78 тока. Формирование сигнала переноса отражателем

82 тока осуществляется аналогично как и выходного сигнала двухвходового умножителя. Однако в силу специфики переноса при умножении элементов полей Галуа (см. табл. 4), который. принимает значение не более 1,0, то в.структуре умножителя на случай набора входных сигналов "33" введены дополнительно три отражателя 79-81 тока с инжектором 64 (вес 1.0), при этом базы отражателей 79 и 80 подключены к третьим коллекторам пороговых транзисторов 63, 76. При наборе "33" транзисторы 79 и 89 закрываются, так как пороговые транзисторы 63 и 76 открыты и своими коллекторами полностью отбирают ток от инжекторов. 64, включенных в базы транзисторов 79, 80.

Транзистор 81 переходит в открытое состояние и своим коллектором, как зеркальный отражатель тока, отбирает ток, равнйй 1.0

15

30

50

55 от выходного инжектора 83 (вес 2.0), что и обеспечивает требуемое значение переноса

1.0 в соответствии с табл. 4.

Работа двухвходового сумматора 34 определяется табл, 2 и может быть выполнена по схеме, структура которой совпадает со структурой двухвходового умножителя 33.

Структура, лежащая в основе умножителя

33, универсальна и, соответствуя ее модификации по настройке на выполняемую функцию и отсутствию переноса, позволяет реализовать схему сумматора (по фиг, 8). В схеме 34 тоже содержатся два дискриминатора 43 и 65, идентичные дискреминаторам умножителя 33. В отличие от умножителя 33 в сумматоре 34 содержатся три дополнительных четырехколлекторных транзистора

88-90 и три дополнительных одноколлекторных транзистора 116-118, а также пять четырехвходовых сумматоров 92 — 95 тока в инжекторами, пятый из которых непронумерован, сформирован на транзисторах 119—

122 и выполняет функцию выходного сумматора тока. В силу свойства операции суммирования четырехзначных элементов поля Галуа, она не содержит переноса и схема сумматора 34 не содержит соответствующего формирователя переноса.

В исходном состоянии, когда на входы

36 и 84 сумматора 34 поступают нулевые исходные сигналы, транзисторы 85 — 87 открыты, а транзисторы 88 — 90 закрыты, аналогично закрыты транзисторы 113 — 118. При этом в результате взаимодействия транзисторов 85 — 87 и 89, 90 и открываются транзисторы сумматора 92 тока с инжекторами

96-99 с весами 0,0, 1.0, 2.0 и 3.0 соответственно, Благодаря влиянию транзисторов

113 — 118 открывается только трэн истор 119 пятого сумматора тока и в силу равенства весов (3,0) инжекторов тока 123, включенных в базу и коллектор транзистора 119, на выход 15 сумматора поступает нулевой сигнал, соответствующий (см. табл. 2) набору переменных 00.

Если на входы 36 и 84 сумматора поступают значения; например, х1 = 1. х2 = 2, то на выходе 15 в соответствии с табл, 2 должен быть сформирован сигнал 3.0, Проанализируем работу устройства на предмет получения данного результата. В силу того, что на аход 36 сумматора 34 поступает ток с весом, равным 1.0, а на вход 84 — ток с весом — 2.0, то транзисторы 47 и 112 переходят в открытое состояние, отражая зеркально (инвертируя) значения х1 и х2 в своих коллекторах. При этом в первом дискриминаторе 43 закрывается транзистор 85 и открывается транзистор 88, а во втором — 65— открываются транзисторы 116 и 117 и эа15

1737443 крываются транзисторы 113, 114, остальные остаются в исходном состоянии. Изменения состояний транзисторов приводят в первом канале к выключению сумматора 92 и включению сумматора 93 тока и, соответственно, во втором дискриминаторе единственный открытый отражатель тока сумматора 94 тока с инжектором 105 (вес 3,0) отбирает от инжектора 123 (вес 3,0) полностью весь ток и на выходе 14 появляется ток с весом 3.0 от выходного инжектора 123. Выходы других сумматоров тока 92, 93 и 95 заблокируются за счет работы транзисторов 115-117.

Таким образом, на рассмотренных примерах проиллюстрирована работа схемы двухвходового сумматора 34 элементов поля

Галуа, Рассмотрим действие четырехзначносго умножителя элементов поля Галуа GF(2 ).

При поступлении нулевых исходных сигналов на входы 7 и 8 преобразоваталей

1 двузначных представлений элементов поля Галуа GF(28) в четырехзначные на их выходах 3 и 4 имеются тоже нулевые выходные сигналы, аналогично на выходах 9 блока 2 умножения в соответствии с табл. 1, 2 и 4 тоже сформируются нулевые сигналы, что обеспечивает нулевой выходной сигнал у преобразователя 3 четырехзначных представлений элементов поля Галуа GF(2я) в двузначные.

Работу четырехзначного умножителя элементов поля Галуа GF(28) рассмотрим на примере умножения двух максимальных значений четырехразрядных четырехзначных числе х1 хр - 3333.

Матричное умножение многозарядных чисел, с учетом свойств операций умножения и сложения (табл. 1. 2 и 4) для ячеек 11 формирователя частичных произведений

- дает следующий результат:

3333

С>3333 0001 л, Т0001

-ЛO001 l 000 1

11111111

Из примера видно, что матричное умно-. жение из-за наличия переноса в операции умножения (см. табл. 4) приводит к двойному увеличению числа разрядов результата, в m время как операции умножения и сложения в поле Галуа GF(2 ) дают фиксированную разрядную сетку из-за свойств цикличности и, как следствие, отсутствия переноса. Поэтому в структуре блока 2 умножения в каждой строке матричного умножения включено по одному нормализатору 12 первой ступени и один, два и три нормализатора 13 второй

20. ной строки матричного умножения.

Во всех строках матричное умножение

30 выполнено в соответствии с таблицами ис35

55 ступени соответственно во второй, третьей и четвертой строках матричного умножителя. Функцию, выполненную нормализатором 12 первой ступени, можно определить следующим образом. При возникновении сигнала переноса Р+ (см. табл. 4) на выходе крайней левой ячейки 11 формирователя частичных произведений он поступает на вход формирователя 37 весовых коэффициентов производящего полинома. На задающие входы формирователя 37 поступают значения тока с весами, соответствующими коэффициентам порождающего аолинома.

С приходом сигнала на вход формирователя 37 открывается входной пороговый транзистор 128 и управляемые инжекторы 129-132 на выходах 133 — 13б репродуцируют коэффициенты порождающего многочлена О 1 3 1. Весовый коэффициент при максимальной степени неопределенной переменной многочлена опущен ввиду свойств вычислений в полях Галуа. Репродуцированные коэффициенты производящего полинома а(х) в нормализаторе 12 поступают на соответствующие входы сумматоров

34, на вторые входы которых поступают результаты частичных произведений иэ дантинности (табл. 1, 2 и 4). В результате этого на выходах 15 каждой строки матричного умножения формируются ячейками 11 сдвинутые на один разряд влево результаты частичных произведений множимого на один из разрядов множителя, прямое суммирование которых приводит к увеличению разрядности конечного результата. 3m потребовало метода и введения средств нормирования результатов умножения, Исследование процедур нормализации показало, что они осуществимы в два этапа; сдвиг влево результата умножения на один разряд и, если перенос Р+ в крайней слева ячейке матричного умножителя равен 1, к оставшимся разрядам прибавляются значения весовых коэффициентов 0 1 3 1: если перенос Р+ = 2, то прибавка равна 2®0 1 3 I = 0

3 2 2 и, если Р+ = 3 прибавка равна 3(х)0 1 3 1

= 0 2 1 3. В состав умножителя необходимо в каждой строке матричного умножения включить нормализатор первой ступени, осуществляющий умножение весовых коэффициентов производящего полинома на 1 и поразрядное их сложение со сдвинутыми результатами частичных произведений, так как перенос Pt для них принимает значение только равное 1 (см. табл, 4).

Так как результат сложения на выходе l6 сумматора 34 в нормализаторе 12 дает

1737443 любое значение из К (О, 1, 2,3), то и на входе

16 ячейки 13 после сдвига влево результата нормализации первой ступени дает любое из

К значений. Поэтому для осуществления всей процедуры нормализации необходим норма- 5 лизатор 13 второй ступени, в состав которого вместо репродукционного устройства 37 введены двухвходовые умножителя. идентичные ячейкам 11 формирователя частичных произведений, которые умножают значение на 10 входе на соответствующие весовые коэффициенты производящего полинома, Далее в каждой ячейке 13 нормализации второй сту- пени схематически осуществляется сдвиг на один разряд результатов нормализации сту- 15 пени, или результатов нормализации второй ступени для третьей и четвертой строки матричного умножения. Эти сдвиги и определяют число используемых ячеек 13 в каждой " строке блока умножения 2: s первой строке 20 ячейка 13 отсутствует, во второй — одна, в

- третьей — две, а в четвертой — три.

В соответствии с примером, в первой строке матричного умножителя в соответствии с табл. 4 перенос всегда равен 1, поэто-. 25 му в ячейке 12 нормализации первой ступени получают ,000 1

®0 3 1

0130 30 во вторрй строке получаем за счет сдвига и двух этапов нормализации с учетом того, что перенос на входе ячейки 13 нормализации второй ступени равен 0:

1300 35 в третьей (перенос иэ предыдущей ступени нормализации равен 1): ...3 0000 0131

3131 40

s четвертой (перенос равен 3 на входе третьего нормализатора второй ступени)

1310 (+7

02 13 45

1 1.0 3

Таким образом, на входы 17-32 блока суммирования 14 поступают наборы: 01 3 О, 1 3 0 О, 3 1 3 1, 1 1 О 3 и в результате поразрядного суммирования в соответствии с 50 табл. Z получают;

1300 о+

313 1 55

1 1Щ

3202

Проверка результата описанных вычис "ний через деление на производящий пол" м а(х) дает: 10131

Ер11111111

10131

Т0201

10131

ТТо11 30213 М Г

Остаток от деления (набор 3 2 О 2) совпадает с результатом, полученным при умножении с помощью предлагаемого устройства, что позволяет утверждать, что оно выполняет операцию умнсжения четырехразрядных четырехзначных представлений элементов поля Галуа GF(28) в полном соответствии со свойствами используемого поля.

Так как прототип рассчитан на реализацию операции умножения элементов полей

Галуа GF(p") при различных производящих полиномах а(х), то в целях сравнения необходимо выравнять порядки р поля Галуа в обоих устройствах, который в таком случае должен равняться 256. В прототипе достигается это при р - 3 и n - 6, или р - 5, и а.

Так как в прототипе содержится п блоков формирования частичных произведений и и блоков суммирования по модулю р, у которых и входов по (р - 1) шин, и входов коэффициентов производящего полинома по (р - 1) шин, и входов по (р - 1) шин коэффициентов BI, (р - 1) шин входов у и блоков формирования частичных произведений, (р - 1) выходов этих блоков и и выходов по (p - 1) шин у блоков суммирования по модулю р, то общая формула эпмирической зависимости числа связей от р и и для прототипа записывается как

Мобщ - и (р - 1) + (р - 1) и + 4п(р - 1) и при р = 3, n - 6- йобщ -132 связи, а при р—

-5, п-4- йобщ=192 связи.

Прямой подсчет связей предлагаемого устройства дает общее число связей 108.

Необходимо отметить, что это число связей неизменно для всех и 2, ..., 8, Таким образом, введение в умножитель элементов полей Галуа двух преобразователей двузначных чисел в четырехзначные, одного преобразователя четырехзначных чисел в двузначные и двух типов ячеек нор-. мализации первой и второй ступени обеспечивэчт уменьшение в 1,23-1,77 раза числа функциональных связей, в два раза числа двузначных входов и выходов блока

2 умножения, а также обеспечивает полную однородность и однотипность схемотехники всех субблоков устройства в целом. Дело в том, что используемое структурно-схемотехническое решение является универсальным, обладающим максималь19

1737443

20 ным параллелизмом всех процессов преобразований (максимальным быстродействием), Абсолютная однородность всех схемных решений упрощает до предела проектирование топологии БИС, снижая время на ее проектирование и вероятность возникновения ошибок в разводке, Формула изобретения

1. Четырехзначный умножитель элементов поля Галуа GF(28), содержащий блок умножения, состоящий из шестнадцати ячеек формирования частичных произведений и узла суммирования, выход которого соеди нен с выходом блока умножения. входы первой группы которого соединены с входами производящего полинома умножителя, о тл и ч а ю шийся тем, что, с целью упрощения умножителя, в него введены два преобразователя двухэначн ых кодов в четырехзначный и преобразователь четырехзначного кода в двухзначный, а в блок умножения введены четыре ячейки нормализации первой ступени и шесть ячеек нормализации второй ступени, причем разрядные входы множимого и множителя умножителя соединены соответственно с входами первого и второго преобразователей двухзначных кодов в четырехзначный, выходы которых соединены соответственно с входами второй и третьей групп блока умножения, выход которого соединен с входом преобразователя четырехзначного кода в двухзначный, выход которого соединен с выходом результата умножителя, при этом в блоке умножения шестнадцать ячеек формирования частичных произведений образуют матрицу размерностью (i, j), где i = 1, ..., 4; j = 1, ..., 4, причем первый вход(i, j)-й ячейки формирования частичных произведений матрицы соединен соответственно c j-м входом второй группы блока умножения, второй вход (i, j)-й ячейки формирования частичных произведений матрицы соединен соответственно с I-м входом третьей группы блока умножения, третий вход (i, 1)-х ячеек формирования частичных произведЕний матрицы соединен с входом логического нуля умножителя, выход переноса (1, ))-й ячейки формирования частичных произведений матрицы, кроме выходов переноса (i, 4)-х ячеек, соединен соответственно с третьим входом (1, j + 1)-й ячейки формирования частичных произведений матрицы, выходы переноса (i, 4)-х ячеек формирования частичных произведений матрицы соединены с входами соответствующих ячеек нормализации первой ступени, выходы суммы.)-х ячеек формирования частичных произведений в каждой 1-й строке матрицы соединены соответственно с входами первой группы

Ic-й ячейки нормализации первой ступени, (Ic

1, ..., 4), входы второй группы которой

5 соединены с входами первой группы блока умножения и входами первой группы с первой по шестую ячеек нормализации второй ступени, выходы первой ячейки нормализации первой ступени соединены с входами

10 первой группы узла суммирования, выходы второй-четвертой ячеек нормализации первой ступени соединены соответственно с входами второй группы. первойтретьей ячеек нормализации второй

15 ступени, выходы второй и третьей ячеек нормализации второй ступени соединены соответственно с входами второй группы четвертой и пятой ячеек нормализации второй ступени, выходы пятой ячейки нормали20 эации второй ступени — с входами второй группы шестой ячейки нормализации второй ступени, выходы первой, четвертой и шестой ячеек нормализации второй ступени — соответственно в входами второй-четвер25 той групп узла суммирования.

2. Умножитель поп. 1, отл ич а ющи йс я тем, что каждая ячейка формирования частичных произведений содержит схему умножения инжекционного типа и сумма30 тор инжекционного типа, причем первый и второй входы схемы умножения инжекционного типа соединены соответственно с первым и вторым входами ячейки, а первый и второй выходы — соответственно с выхо35 дом переноса ячейки и первым входом сумматора инжекционного типа, второй вход которого соединен с третьим входом ячейки, а выход — с выходом суммы ячейки.

3. Умнсжитель по и. 1, о т л и ч а ю щ и й40 с я тем, что каждая ячейка нормализации первой ступени содержит формирователь весовых коэффициентов производящего полинома и четыре сумматора инжекционного типа, причем с первого по четвертый

45 входы формирвателя весовых коэффициентов производящего полинома соединены с входами второй группы ячейки, входы первой группы которой соединены с первыми входами соответствующих сумматоров ин50 жекционного типа, вторые входы которых соединены с соответствующими выходами формирователя весовых коэффициентов производящего полийома, пятый вход которого соединен с входом ячейки, выходы ко55 торой соединены с выходами сумматоров инжекционного типа.

4. Умножитель по и. 1, о т л и ч а ю щ и йс я тем, что каждая ячейка нормализации второй ступени содержит четыре ячейки формирования частичных произведений, 1737443

22

Таблица 1

Таблица 3

25

Таблица 4

Таблица 2 30

40 три сумматора инжекционного типа и формирователь весовых коэффициентов производящего полинома. входы которого соединены с входами первой группы ячейки, а выходы — с первыми входами соответ. ствующих ячеек формирования частичных произведений, четвертый вход второй группы ячейки соединен с вторыми входами всех ячеек формирования частичных произведений, третий вход 1-й ячейки формирования частичных произведений соединен соответственно с выходом переноса (! - 1)-й ячейки формирования частичных произведений

Умножение над полем GF (4) (Умножение по модулю 4) Операция суммы над полем GF (4) (I - 2, 3, 4), выходы суммы первой-третьей . ячеек формирования частичных произведений соединены соответственно с первыми входами первого-третьего сумматоров ин5 жекционного типа, вторые входы. которых соединены соответственно с третьим, вторым и первым входами второй группы ячейки, первый выход которого соединен с выходом четвертой ячейки формирования

10 частичных произведений, выходы третьего, второго и первого сумматоров инжекционного типа соединены соответственно с вторым-четвертым выходами ячейки.

Перенос для операции умножения над полем GF (4) 1737443

1737443

Фиг.4

1737443

1737443

1737443

1737443

1737443

Составитель Э. Коноплянко

Техред М.Моргентал Корректор М. Максимишинец

Редактор Л. Пиолинская

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 1892 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Рауыская наб., 4/5