Четырехзначный умножитель элементов поля Галуа GF(2 @ ) Советский патент 1992 года по МПК G06F7/49 H03K19/08 

Ъи

Л

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

L+ф(/еЛ

А.

w

со

SI

со

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

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

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

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

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

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

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

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

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

5 входами первого и второго преобразователей двухзначных кодов в четырехзначный, выходы которых соединены соответственно с входами второй и третьей групп блока умножения, выход которого соединен с вхо0 дом преобразователя четырехзначного кода в двузначный, выход которого соединен с выходом результата умножителя, при этом в блоке умножения шестнадцать ячеек формирования частичных произведений обра5 зуют матрицу размерностью (I, J), где , ..., 4; ,. .. , 4, причем первый вход (I, )-й ячейки формирования частичных произведений матрицы соединен соответственно с j-м входом второй группы блока умножения,

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

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

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

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

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

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

10 третьим и четвертым выходами ячейки.

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

5 схема ячейки формирования частичных произведений; на фиг. 4 - структурная схема ячейки нормализации первой ступени; на фиг. 5 - структурная схема ячейки нормализации второй ступени; на фиг. 6 - структур0 ная схема блока суммирования; на фиг. 7 - принципиальная схема двухвходового умножителя; на фиг. 8 - принципиальная схема двухвходового сумматора; на фиг. 9 - принципиальная схема формирователя ве5 совых коэффициентов производящего полинома устройства.

Четырехзначный умножитель элементов поля Галуа GF(2 , содержит два байтных преобразователя 1 двузначных представле0 ний элементов поля Галуа в четырехзначные, блок 2 умножения с тремя группами входом 3-5 и байтный преобразочатель 6 четырехзначных представлений элементов поля Галуа в двузначные, при этом группы входов 7

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

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

5 первой ячейки 12 нормализации первой ступени подключены к входам 17-20 блока 14 суммирования, выходы 16 второй ячейки 12 нормализации первой ступени подключены к входам первой ячейки 13 нормализации второй ступени, выходы 21-24

подключены к соответствующим входам блока 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, входы 5t (где 1 1,,.., 4) задания весов коэффициентов производящего многочлена, входы 15{ (где J 0,.,., 3} результатов формирования частичных произведений, подключенных к первым входам двухвходовых сумматоров 34, на вторые входы которых поданы значения весовых коэффициентов производящего полинома, а также вход 38 переноса Р+и выходы 16j результатов нормализации значений вычислений матричного умножения,

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

к соответствующим входам 5 весовых коэффициентов производящего полинома, а вход 4 множителя - к четвертому выходу 16з ячейки 12 нормализации первой ступени,

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

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

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

5 Двухвходовый умножитель 33 содержит первый дискриминатор 43 с задаваемыми при помощи источников 44-46 (инжекторов) с весами 0.5, 1.5, 2.5 порогами срабатывания, входной отражатель 47 тока и порого0 вые многоколлекторные транзисторы 48-50, входящие в состав первого дискриминатора 43, трех- и двухвходовые суммато- ры 51-53 тока с регулируемыми инжекторами тока 1.0, 2.0, 3.0; 2.0, 2.0 и 3.0,

5 2.0, 1.0 соответственно, первый и второй пороговые дополнительные транзисторы 62 и 63 с инжекторами 64 тока с весами токов 1,0, второй дискриминатор 65 с задаваемыми при помощи источников 66-68 порогами

0 срабатывания с весами 0.5,1.5, 2.5 соответственно, входной отражатель 69 тока и пороговые транзисторы 70-72, входящие в состав второго дискриминатора, вход 4 которого является входом YI одного из сомнр5 жителей ячейки 33, пятый-девятый дополнительные пороговые транзисторы 73-76 с инжекторами 64 с единичными весами, вход первого дискриминатора 43 подключен к первому входу двухвходового умножителя четырехзначных элементов поля Галуа, выход 15 произведения Q и выход 35 переноса Р+, первый-пятый отражатели 77-81 тока с инжекторами 64 с весом 1,0 соответственно и шестой отражатель 82 тока, на входе и выходе которого включены инжекторы 83 тока с весами 2,0, выход отражателя 81 является выходом 35 результата переноса Р+, при этом в первом канале первого дискриминатора 43 коллекторы первого порогового транзистора 48 соединены с входами первого трехвходового сумматора 51 тока, во втором канале первого дискриминатора два коллектора второго порогового транзистора 49 соединены с входами двухвходового сумматора 52 тока, а третий коллектор соединен с базой первого дополнительного транзистора 62, три коллектора которого подключены к входам первого трехвходового сумматора 51 тока, в третьем канале первого дискриминатора три коллектора порогового транзистора 50 соединены с входами второго трехвходового сумматора 53 тока, а четвертый коллектор соединен с базой второго дополнительного транзистора 63, два коллектора которого соединены с входами двухвходового сумматора 52 тока, первые коллекторы пороговых транзисторов 71 и 72 второго и третьего каналов второго дискриминатора 65 подключены соответственно к базам третьего и четвертого дополнительных транзисторов 76, первые коллекторы которых подключены соответственно к второму и первому коллекторам пороговых транзисторов 70 и 72 первого и третьего каналов второго дискриминатора 65, первый и второй коллекторы пороговых транзисторов 70-72 первого, второго и третьего каналов второго дискриминатора 65 подключены к базам пятого, шестого и седьмого дополнительных транзисторов 73-75, эмиттеры которых подключены соответственно к первым, вторым и третьим выходам каналов трехвходовых 51 и 53 и двухвходового 52 сумматоров тока, а коллекторы через выходной отражатель тока 95 подключены к выходу 84 произведения, база первого транзистора 77 формирователя переноса подключена соответственно к второму и четвертому коллекторам пороговых транзисторов 50 и 72 третьих каналов первого 43 и второго 65 дискриминаторов, база второго транзистора 78 формирователя переноса подключена соответственно к второму и третьему коллекторам пороговых транзисторов 49,71 вторых каналов первого и второго дискриминаторов, коллекторы транзисторов формирователя переноса через отражатель 82 тока подключены к выходу переноса двухвходового умножителя,

дополнительно введены три дополнительных отражатели 79-81 тока, причем база первого дополнительного отражателя 79 тока подключена к первому коллектору допол- 5 нительного порогового транзистора 76 второго канала второго дискриминатора, в база второго дополнительного отражателя 80 тока к коллектору второго дополнительного порогового транзистора 63 третьего ка10 нала первого дискриминатора 43, коллекторы первого и второго дополнительных отражателей 79 и 89 тока соединены вместе и подключены к базе третьего дополнительного отражателя 81 тока, коллектор

15 которого подключен к выходу 35 переноса Р+ двухвходового умножителя четырехзначных элементов поля Галуа.

Двухвходовой сумматор 34 четырехзначных элементов псля Галуа аналогично

0 двухвходовому умножителю 33 содержит первый входной отражатель 47 тока, входящий в состав первого дискриминатора 43. три пороговых пятиколлекторных транзистора 85-87 с задаваемыми при помощи ис5 точников 44-46 с весами инжектируемых токов 0.5, 1.5. 2.5 и с порогами срабатывания, три дополнительных четырехколлек- торных пороговых транзистора 88-90, в базы которых включены инжекторы 91 с ве0 сами 1.0, четырехвходовые сумматоры 92- 95 тока с регулируемыми инжекторами 96-111 с весами 3.0, 2.0, 1.0, 0.0; 0,0, 3.0, 2.0, 1.0; 1.0, 0.0, 3.0, 2.0; 2.0, 1.0, 0.0, 3.0 соответственно, а также второй дискрими5 натор 65, включающий второй входной отражатель 112 тока, двухколлекторные пороговые транзисторы 113-115 с задаваемыми при помощи источников 44-46 с весами инжектируемых токов 0.5, 1.5, 2.5 с

0 порогом срабатывания и три дополнительных пороговых транзистора 116-118, в базы которых включены инжекторы с весами 1.0, кроме того, в состав сумматора 34 входит выходной четырехвходовый сумматор тока,

5 состоящий из отражателей 119-122 тока, в базы которых включены инжекторы 123 с весами 3.0, а коллекторы объединены вместе и образуют выход 15 сумматора, к которому также подключен еще один инжектор

0 123 с весом 3.0, при этом выходы 124-127 второго дискриминатора 65 подключены к соответствующим выходам сумматоров 92- 95, к которым также подключены коллекторы дополнительных пороговых транзис5 торов 117 и 118, базы первого 47 и второго 112 входных отражателей тока образуют два входа 36 и 84 сумматора, три коллектора отражателей 47 и 112 тока подключены соответственно к базам шести пороговых пяти- и, двухколлекторных транзисторов 85-87

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(28) порожденного производящим полиномом (а)х х + х + х + х + 1 и с примитивным элементом а 0000 0010 может быть сформирован, за исключением нуля, путем возведения в степень примитивного элемента «поля, т.е. GF(256){О, (г, а1, а2, ..., . Для заданного а(х) коэф- фициенты при всех его степенях образуют набор однозарядных двоичных чисел 1,0, 0,1,1,1,0,1 или для дальнейшего перехода к четырехзначным представлениям набор двуразрядных чисел 01, 00, 01, 11, 01. Так называемые весовые коэффициенты производящего полинома а(х).

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

Обозначим символами из Ek {0,1, 2,3J упорядоченные элементы поля Галуа GF(4): О, с - 1, а1 - 2, с - 3. Тогда операция суммирования над полем GF(4) описывается в табл.2.

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

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

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

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

0000 0011 X 0000 00011 - о25 о25 о50 00000101;

0000 0011 X 0000 0010 о25 а1 а26 0110 и т.д.

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

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

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

В основу функционирования двухвходовых умножителя 33 и сумматора 34 положены таблицы истинности (см. табл. 1,2 и 4). В частности, двухвходовый умножитель 33 формирует результат умножения по модулю 4 (см. табл. 1) и перенос Р+ (см. табл. 4). Если на входы 3 и 4 умножителя 33 поступают входные токи Ux такие, что I8x E4 {0,1,2, 3}, закрываются те из транзисторов 48-50,. 70-72, для которых выполняется условие tex lit, где ITI - ток 1-го инжектора 44-46, 66-68, задающего порог срабатывания в первом 43 и втором 65 дискриминаторах;

1тЈ{0.5,1.5,2.5}. При этом в базы f-й группы транзистров сумматоров тока 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 соответственно.

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

от выходного инжектора 83 (вес 2,0), что и обеспечивает требуемое значение переноса 1.0 в соответствии с табл. 4.

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

5 умножителя 33. В отличие от умножителя 33 в сумматоре 34 содержатся три дополнительных четырехколлекторных транзистора 88-90 и три дополнительных одноколлек- торных транзистора 116-118, а также пять

0 четырехвходовых сумматоров 92-95 тока в инжекторами, пятый из которых непронумерован, сформирован на транзисторах 119- 122 и выполняет функцию выходного сумматора тока. В силу свойства операции

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

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

0 36 и 84 сумматора 34 поступают нулевые исходные сигналы, транзисторы 85-87 открыты, а транзисторы 88-90 закрыты, аналогично закрыты транзисторы 113-118. При этом в результате взаимодействия транзи5 сторон 85-87 и 89, 90 и открываются транзисторы сумматора 92 тока с инжекторами 96-99 с весами 0.0, 1.0, 2.0 и 3.0 соответственно. Благодаря влиянию транзисторов 113-118 открывается только транзистор 119

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

5 переменных 00.

Если на входы 36 и 84 сумматора поступают значения, например, xi 1, Х2 2, то на выходе 15 в соответствии с табл. 2 должен быть сформирован сигнал 3.0. Проана0 лизируем работу устройства на предмет получения данного результата. В силу того, что на РХОД 36 сумматора 34 поступает ток с весом, равным 1.0, а на вход 84 - ток с весом - 2.0, то транзисторы 47 и 112 пере5 ходят в открытое состояние, отражая зеркально (инвертируя) значения xi и Х2 в своих коллекторах. При этом в первом дискриминаторе 43 закрывается транзистор 85 и открывается транзистор 88, а во втором - 65 - открываются транзисторы 116 и 117 и закрывзются транзисторы 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) рассмотрим на примере умножения двух максимальных значений четырехразрядных четырехзначных числе xi Х2 3333.

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

3333 &33JL3 ,0001 0001

рЮ001

10001

11111111

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

т

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

следующим образом. При возникновении сигнала переноса Р+ (см. табл. 4) на выходе крайней левой ячейки 11 формирователя частичных произведений он поступает на вход формирователя 37 весовых коэффици0 ентов производящего полинома. На задающие входы формирователя 37 поступают значения тока с весами, соответствующими коэффициентам порождающего полинома. С приходом сигнала на вход формировате5 ля 37 открывается входной пороговый транзистор 128 и управляемые инжекторы 129-132 на выходах 133-136 репродуцируют коэффициенты порождающего многочлена 0131. Весовый коэффициент

0 при максимальной степени неопределенной переменной многочлена опущен ввиду свойств вычислений в полях Галуа. Репродуцированные коэффициенты производящего полинома а(х) в нормализаторе 12 поступа5 ют на соответствующие входы сумматоров 34, на вторые входы которых поступают результаты частичных произведений из данной строки матричного умножения.

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

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

5 произведений множимого на один из разрядов множителя, прямое суммирование которых приводит к увеличению разрядности конечного результата. Это потребовало метода и введения средств нормирования ре0 зультатов умножения. Исследование процедур нормализации показало, что они осуществимы в два этапа: сдвиг влево результата умножения на один разряд и, если перенос Р+ в крайней слева ячейке

5 матричного умножителя равен 1, к оставшимся разрядам прибавляются значения весовых коэффициентов 0131: если перенос Р+ 2, то прибавка равна 2(хХ 3 2 2 и, если Р+ 3 прибавка равна 3(х)01 3 1

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

5 поразрядное их сложение со сдвинутыми результатами частичных произведений, так как перенос Pt для них принимает значение только равное 1 (с м. табл. 4).

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

любое значение из ,1,2,3}, то и на входе/i-1 1 1 1 1 1 1 1 10131

16 ячейки 13 после сдвига влево результата1 0131 1103

нормализации первой ступени дает любое 020 1

К значений. Поэтому для осуществления всей1013 1

процедуры нормализации необходим норма- 5.3 3 01 1

лизатор 13 второй ступени, в состав которого 0213

вместо репродукционного устройства 37 вве-3 202

дены двухвходовые умножителя, идентичныеОстаток от деления (набор 3202) сов- ячейкам 11 формирователя частичных про- падает с результатом, полученным при ум- иэведений, которые умножают значение на10 ножении с помощью предлагаемого входе на соответствующие весовые коэффи-устройства, что позволяет утверждать, что циенты производящего полинома. Далее воно выполняет операцию умножения четы- каждой ячейке 13 нормализации второй сту-рехразрядных четырехзначных представле- пени схематически осуществляется сдвиг наний элементов поля Галуа GF(28) в полном один разряд результатов нормализации сту-15 соответствии со свойствами используемого пени, или результатов нормализации второйполя.

ступени для третьей и четвертой строки мат-Так как прототип рассчитан на реализаричного умножения. Эти сдвиги и определя-цию операции умножения элементов полей

ют число используемых ячеек 13 в каждой Галуа GF(pn) при различных производящих

строке блока умножения 2: в первой строке20 полиномах а(х), то в целях сравнения необячейка 13 отсутствует, во второй - одна, входимо выравнять порядки q поля Галуа в

третьей - две, а в четвертой - три.обоих устройствах, который в таком случае

В соответствии с примером, в первойдолжен равняться 256. В прототипе достистроке матричного умножителя в соответст-гается это при р - 3 и п 6, или р - 5, п вии с табл. 4 перенос всегда равен 1, поэто-25 4.

му в ячейке 12 нормализации первойТак как в прототипе содержится л блоступени получают ков формирования частичных произведений

Ј,000 tи п блоков суммирования по модулю р, у

013 1которых п входов по (р - 1) шин, п входов

013030 коэффициентов производящего полинома

во вторрй строке получаем за счет сдвига ипо (р - 1} шин, п входов по (р - 1) шин

двух этапов, нормализации с учетом того, чтокоэффициентов В, (р - 1) шин входов у п

перенос на входе ячейки 13 нормализацииблоков формирования частичных произвевторой С1упени равен 0:дений. (р -1)2 выходов этих блоков и п выхо130035 дов по (р -1) шин у блоков суммирования по

третьей (перенос из предыдущей ступенимодулю р, то общая формула эпмирической

нормализации равен 1):зависимости числа связей от р и п для про30000тотипа записывается как

0131, Мобщ п2(р-1) + (р-1)2п + 4п(р-1)

313140 и при р 3, п 6 - N06tu 132 связи, а при р в четвертой (перенос равен 3 на входе треть- 5, п « 4 - М0бщ 192 связи,

его нормализатора второй ступени)Прямой подсчет связей предлагаемого

1310устройства дает общее число связей 108.

(р Необходимо отметить, что это число связей

021345 неизменно для всех п 2,.... 8.

1103Таким образом, введение в умножитель

Таким образом, на входы 17-32 блокаэлементов полей Галуа двух преобразоватесуммирования 14 поступают наборы: 0130,лей двузначных чисел в четырехзначные,

1300,3131,1 ЮЗиврезультатепораз-одного преобразователя четырехзначных

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

1300числа функциональных связей, в два раза

(+)числа двузначных входов и выходов блока

313155 2 умножения, а также обеспечивает пол1 103ную однородность и однотипность схемо3202техники всех Субблоков устройства в

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

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

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

размерностью (I, J), где 1 1,.... 4; j 14,

причем первый вход (i, jj-й ячейки формирования частичных произведений матрицы соединен соответственно с J-м входом второй группы блока умножения, второй вход (I, )-й ячейки формирования частичных произведений матрицы соединен соответственно с 1-м входом третьей группы блока умножения, третий вход(1,1)-х ячеек формирования частичных произведений матрицы соединен с входом логического нуля умножителя, выход переноса (i, j)-u ячейки формирования частичных произведений матрицы, кроме выходов переноса (I, 4)-х ячеек, соединен соответственно с третьим входом (I, j + 1)-й ячейки формирования частичных произведений матрицы, выходы переноса (I. 4)-х ячеек формирования частичных произведений матрицы соединены с входами соответствующих ячеек нормализации первой ступени, выходы суммы j-x ячеек формирования частичных произведений в каждой 1-й строке матрицы соединены соответственно с входами первой группы k-й ячейки нормализации первой ступени, (к 31 1 4), входы второй группы которой

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

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

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

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

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

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

Таблица 1

Умножение над полем GF (4) (Умножение по модулю 4)

Таблица 2 30 Операция суммы над полем GF (4)

0

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

Таблица 3

Таблица 4

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

Ко

JS

/

Г

/ЩЯ /ЩР

L

JL

L. JS

fl

fa

13

13

7W

13

13

Я

J /Хг 3 /3

/%i ,%о

м.м.

//

/f36Уо

Г

/ЩЯ /ЩР

L

JL

-Z425-28

M

9

&-J2

«

11

J5

Ч

15

16

ts2Itf

Фиг Л

IX.

Xi

м

36

84

JJ

№.J

16й

гз т чh- п

г-т

Ч

Гь

Ь 53 Si

о о

О

ш

гш

Гь

-о

т

-о

/Л

о

/J

(Ptel