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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к специализированным устройствам вычислительной техники и может быть использовано в кодирующих и декодирующих устройствах, работающих с элементами конечных полей полиномов GF(2m) при m S 3, например в устройствах системы компакт-диск. Цель изобретения - сокращение аппаратурных затрат. Устройство умножения элементов конечного поля GF(2m) состоит из первого и второго регистров с D-триггерами, третьего регистра с RS-триггерами, группы блоков матричного преобразования, первого и второго пультиплексоров, группы блоков элементов И, блока сумматоров по модулю два и блока управления, который состоит из элемента НЕ, двух двухвходовых элементов и элемента ИЛИ-НЕ, D-триггера, элемента И, 1од2т +1)-разрядного двоичного счетчика и элемента ИЛИ. 1 з.п. ф-лы, 9 ил. сл с

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИН (19) (11) (я)5 G 06 F 7/49, 7/52

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4798969/24 (22) 05.03.90 (46) 23.04.92. Бюл. ¹ 15 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И.И.Ковалив (53) 681.325 (088,8) (56) Блок Э.Л., Зяблов В.В. Обобщенные каскадные коды (Алгебраическая теория и сложность реализации) вып. 5.— М.: Связь, 1976, с. 106, рис. 3.37.

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

¹ 1226445, кл, G 06 F 7/52, 1984. (54) УСТРОЙ СТВ О ДЛ Я УМНОЖЕНИЯ

ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ GF(2 )

ПРИ т >3 (57) Изобретение относится к специализированным устройствам вычислительной техИзобретение относится к специализированным устройствам вычислительной техники и может использоваться в кодирующих и декодирующих устройствах, работающих с элементами конечных полей полиномов

GF(2 ) при m 3, например в устройствах системы "компакт-диск".

Известны устройства деления полиномов над конечными полями GF(2 ), содержащее два блока логарифмирования, блок вычитания и блок антилогарифмирования, причем входы блоков логарифмирования являются входами коэффициентов полиномов-сомножителей, выходы блоков лога-., рифмирования подсоединены к двум.: группам входов блока вычитания соответст -, венно, выход которого подсоединен к входу блока антилогарифмирования, выходы которого являются выходами коэффициентов ники и может быть использовано в кодирующих и декодирующих устройствах, работающих с элементами конечных полей полиномов GF(2 ) при m > 3, например в устройствах системы "компакт-диск". Цель изобретения — сокращение аппаратурн ых затрат. Устройство умножения элементов конечного поля 6Р(2 ) состоит из первого и второго регистров с D-триггерами, третьего регистра с RS-триггерами, группы блоков матричного преобразования, первого и второго пультиплексоров, группы блоков элементов И, блока сумматоров по модулю два и блока управления, который состоит из элемента НЕ, двух двухвходовых элементов и элемента ИЛИ вЂ” НЕ, D-триггера, элемента И, jlogzm(+1)-разрядного двоичного счетчика и элемента ИЛИ. 1 з.п. ф-лы, 9 ил. полинома-произведения соответственно, При замене в таких устройствах блока вычитания блоком суммирования устройства деления преобразуются в устройства умножения двух полиномов над конечными полями GF(2 ).

Недостатками таких устройств являются их большая сложность реализации и большие.аппаратурные затраты при m > 4.

Известно устройство для деления элементов поля Галуа, содержащее первый и второй сдвиговые регистры, один элемент

И, один элемент ИЛИ-НЕ, декодер, кодер и умножитель, причем, информационные входы первого и второго сдвиговых регистров являются входами устройства коэффициентов полинома-делителя и полинома-делимого соответственно, выходы подсоединены к входам декодера и к первой группе входов

1728858

10 умножителя соответственно, а тактовые входы объединены и подсоединены к выходу элемента И, первый вход которого является тактовым входом устройства, а второй вход подсоединен к выходу элемента ИЛИ—

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

В этом устройстве производится операция умножения элементов конечного поля, а для выполнения операции деления элементов поля Галуа производится предварительное определение обратного элемента для полинома-делителя при помощи декодера и кодера, содержащее ПЗУ каждый.

Недостатком такого устройства являются его большие аппаратурные затраты.

Цель изобретения — сокращение аппаратурн ых затрат.

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

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

"Занят" устройства.

При этом блок управления содержит элемент ИЛИ, элемент И, три элемента

ИЛИ вЂ” НЕ, О-триггер, ()logzm(+1)-разрядный двоичный счетчик (где )logzm(— ближайшее целое большее к logzm число, если logzm— нецелое) и элемент НЕ, вход которого соединен с первым входом блока управления и первым входом первого элемента ИЛИ вЂ” НЕ, выход которого соединен с первым входом второго элемента ИЛИ вЂ” НЕ, второй вход которого соединен с входом сброса D-триггера, выходом элемента ИЛИ и четвертым выходом блока управления, второй вход которого соединен с тактовым входом D"òðèãгера и первым входом элемента И, второй вход которого соединен с выходом D-триггера, информационный вход которого соединен с выходом второго элемента

ИЛИ вЂ” НЕ, вторым входом первого элемента

ИЛИ вЂ” НЕ и седьмым выходом блока управления, третий вход которого соединен с первым входом элемента ИЛИ и входом установки в нуль plogzm(+1)-разрядного двоичного счетчика, счетный вход которого соединен с выходом элемента И и третьим выходом блока управления, второй выход которого соединен с выходом элемента НЕ, а четвертый и пятый выходы — соответственно с прямым и инверсным выходами младшее го ра з ряда () I ogzm(+1)-разрядного двоичного счетчика, прямые выходы

PlogzmP старших разрядов которого соединены с соответствующими входами третьего элемента ИЛИ вЂ” НЕ, выход которого соединен с шестым выходом блока управления и вторым входом элемента ИЛИ.

На фиг.1 изображена структурная блоксхема устройства умножения над полем

G F(2 ); на фиг.2 — структурная схема регистра с 0-триггерами; на фиг.3 — структурная схема регистра с RS-триггерами; на фиг.4— структурная схема мультиплексора; на фиг.5 — структурная схема блока управле1728858 6 второй группы информационных входов первого мультиплексора 4> являются одноименными m входами второй группы информационных входов устройства, m выходов первого мультиплексора 4> подсоединены к одноименным m установочным входам второго регистра 1z, m выходов которого подсоединены к одноименным m входам первой группы информационных входов второго мультиплексора 42, m входов второй группы информационных входов которого подсоединены к одноименным m выходам регистра 2, а m выходов второго мультиплексора 4z подсоединены к одноименным m входам второй группы входов группы 5 блоков элементов И, причем m выходов блока 6 сумматоров по модулю два объединены с одноименными m информационными входами первого и второго регистров 11 и 12 и являются одноименными в информационными выходами устройства, 40

55 ния; на фиг.6- структурная схема двоичного счетчика блока управления; на фиг.7— структурная схема jlogzm(-входового элемента ИЛИ-НЕ блока управления; на фиг.8 — временные диаграммы работы блока уп- 5 равления, на фиг.9 — временные диаграммы работы устройства умножения над полем

GF(2 ) при выполнении им операции обращения элемента поля при m 3.

Устройство умножения над полем 10

GF(2 ) (фиг.1) состоит из первого и второго регистров 11 и 12 с D-триггерами, третьего регистра 2 с RS-триггерами, одной группы 3 блоков матричного преобразования, первого и второго мультиплексоров 41 и 42 с двумя 15 группами информационных входов каждый, одной группы 5 блоков элементов И, одного блока 6 сумматоров по модулю два и блока

7 управления, причем m установочных входов первого регистра 1> являются одно- 20 именными m входами первой группы информационных входов устройства и объединены с одноименными m входами первой группы информационных входов первого мультиплексора 4> и с m информа- 25 ционными входами регистра 2, m прямых выходов первого регистра 1> подсоединены к одноименным m входам группы 3 блоков матричного преобразования, m выходов которого подсоединены к соответствующим 30 г

m входов первой группы входов группы 5 блоков элементов И, m выходов которой подсоединены к соответствующим m входам блока 6 сумматоров по модулю два, m выходов которого являются одноименным 35

m информационными выходами устройства и подсоединены к одноименным объединенным m информационным входам первого и второго регистров 11 и 1г, при этом m входов при этом первый и второй входы блока 7 управления, являющиеся соответственно входами "Обращение" и "Исходное состояние" устройства, подсоединены к первому управляющему входу первого мультиплексора 41 и к объединенным входам сброса в нулевое состояние первого и второго регистров 1> и 1z, а третий вх0д блока 7 управления является тактовым входом устройства, при этом с первого по пятый выходы блока

7 управления подсоединены к второму управляющему входу первого мультиплексора

41, к объединенным тактовым входам первого и второго регистров 11 и 1z, к входу сброса в нулевое состояние регистра 2, к первому и к второму управляющим входам второго мультиплексора 4z соответственно; а шестой и седьмой выходы блока 7 управления— являются выходами "Готов " и "Занят" устройства. Регистр 1> (1z) (фиг.2) состоит из m

D-триггеров 8, причем входы установки в единичное состояние и информационные входы всех m D-триггеров 8 являются одноименными .с порядковыми номерами Dтриггеров 8 m установочными и и; информационными входами регистра 11 1z) соответственно, прямые выходы D-триггеров 8 являются одноименными с порядковыми номерами О-триггеров 8 m выходами регистра 11(1z), при этом объединенные тактовые входы всех m 0-триггеров 8 являются тактовым входом регистра 11(1z), а объединенные входы сброса в нулевое состояние всех m D-триггеров являются входом сброса в нулевое состояние регистра 1> (12).

Регистр 2 (фиг.3) состоит из m RS-триггеров 9, причем входы установки в единичное состояние всех m RS-триггеров 9 являются одноименными с порядковыми номерами RSтриггеров 9 m установочными входами регистра 2, а объединенные входы сброса всех

RS-триггеров 9 являются входом сброса в нулевое состояние регистра 2.

Мультиплексор 41 (42) (фиг.4) состоит из

2m двухвходовых элементов И 10 и m двухвходовых элементов ИЛИ 11, причем первые входы первых по порядку счета m двухвходовых элементов И 10 являются одноименными с порядковыми номерами двухвходовых элементов И 10 m входами первой группы информационных входов мультиплексора 41(4z), первые входы следующих по порядку счета m двухвходовых элементов И 10 с порядковыми номерами от (m + 1) по 2m являются m входами второй группы информационных входов мультиплексора 41 (4z) номерами Hà m меньше порядковых номеров соответствующего двухвходового элемента И 10, при этом вторые объединенные входы первых по поряд1728858 ку счета m двухвходовых элементов И 10 объединены и являются первым управляющим входом мультиплексора 4> (4z), а вторые объединенные входы следующих по порядку счета m двухвходовых элементов И

10 с порядковыми номерами от (m + 1) по

2m включительно являются вторым управляющим входом мультиплексора 41 (42), причем выходы первых по порядку счета m двухвходовых элементов И 10 подсоединены к первым входам всех m одноименных двухвходовых элементов ИЛИ 11, вторые входы которых подсоединены к выходам следующих по порядку счета m двухвходовых элементов И 10 с порядковыми номерами на m больше порядковых номеров двухвходовых элементов ИЛИ 11 соответственно, а выходы являются одноименными m выходами мультиплексора 4> (4 ), Блок 7 управления (фиг.5) состоит из инвертора 12, первого и второго двухвходовых элементов ИЛИ-НЕ 131 и 132, D-триггера 14, элемента И 15, ()logjam(+1)-разрядного двоичного счетчика 16, где символом )!оцге( обозначено натуральное число, полученное при округлении числа logjam до ближайшего целого, если число !о9гт — нецелое, ()logzmpвходового элемента ИЛИ вЂ” НЕ 17 и элемента

18 ИЛИ, причем, вход инвертора 12 является первым входом блока 7 управления и объединен с первым входом первого двухвходового элемента ИЛИ вЂ” НЕ 13, выход которого подсоединен к первому входу второго двухвходового элемента ИЛИ вЂ” НЕ

13, первый вход элемента ИЛИ 18 является вторым входом блока 7 управления и объединен с входом установки в исходное состоя н ие ()logjam(+1)-разрядного двоичного счетчика 16, прямой вход D-триггера 14 подсоединен к первому входу элемента И 15, а тактовый вход D-триггера 14 объединен с вторым входом элемента И 15 и является третьим входом блока 7 управления, при этом выход инвертора 12 является первым выходом блока 7 управления, выход элемента И 15 объединен со счетным входом ()!о9гт(+1)-разрядного двоичного счетчика

16 и является вторым выходом блока 7 управления, выход элемента ИЛИ 18 объединен с вторым входом двухвходового элемента ИЛИ вЂ” НЕ 13г, с входом сброса в нулевое состояние D-триггера 14 и является третьим выходом блока 7 управления, причем инверсный и прямой выходы самого младшего разряда ()logjam(+1)-разрядного двоичного счетчика 16 являются четвертым и пятым выходами блока 7 управления соответственно, выход Plogzm()-входового элемента ИЛИ-НЕ 17 объединен с вторым входом элемента ИЛИ 18 и является шестым

55 выходом блока 7 управления, выход второго двухвходового элемента ИЛИ-НЕ 13 является седьмым выходом блока 7 управления и объединен с вторым входом первого двухвходового элемента ИЛИ вЂ” НЕ 13> и с информационным входом D-триггера 14, при этом прямые выходы )!092т(старших разрядов ()!оцупа(старших разрядов ()logjam(+1)-.разрядного двоичного счетчика 16 подсоединены соответственно к входам ()log2mP-входового элемента ИЛИ—

HE 17.

Plogzm(+1)-разрядный двоичный счетчик 16 (фиг.6) блока 7 управления состоит из ()logjam(+1) D-триггеров 19, где символом

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

19> памяти является счетным входом двоичного счетчика 16, инверсный выход каждого из 0-триггеров 19 подсоединен к собственному информационному входу, прямой выход предыдущего D-триггера 19ь где = 1, 2, ..., )logjam(, подсоединен к тактовому входу последующего D-триггера 19н-, при этом инверсный и прямой выходы первого Dтриггера 19> являются первым и вторым выходами двоичного счетчика 16, а прямые выходы остальных )logjam(D-триггеров 19!, где j = 2, 3, ..., )logjam(+1, являются остальными )logjam(выходами двоичного счетчика 16 с порядковыми номерами начиная с третьего, причем вход сброса в нулевое состояние первого D-триггера 19! является входом установки в исходное состояние двоичного счетчика 16 и подсоединен к входам установки в единичное состояние тех D-триггеров 191, где j = 2, 3, .„, )logjam(+1, для которых соответствующие (!-1)-е разряды двоичного представления числа (2 (— m + 2) равны единице; и к входам сброса в нулевое состояние тех D-триггеров 19>, для которых соответствующие азояды двоичного представления числа (2 — m + 2) равны нулю, ()logjam()-входовый элемент ИЛИ вЂ” НЕ 17 (фиг.7) блока 7 управления состоит из двухвходового элемента ИЛИ вЂ” НЕ 20 и из

)log2m(2 > 0 при m > 4 двухвходовых элементов ИЛИ 21, причем выход двухвходового элемента ИЛИ вЂ” НЕ 20 является выходом ()log2m() входового элемента ИЛИ-НЕ 17, первый вход является первым входом ()logjam()-входового элемента ИЛИ вЂ” НЕ 17, а второй вход является вторым входом

Plogzm()-входового элемента ИЛИ вЂ” HE 17 при m = 3 или 4 либо подсоединен к выходу первого двухвходового элемента 211 при

m > 4, при этом первые входы ()logjam(— 2) 1728858

10 двухвходовых элементов ИЛИ 21 являются последующими входами ()logjam()-входового элемента ИЛИ вЂ” НЕ 17 с порядковыми номерами на единицу больше порядковых номеров двухвходовых элементов ИЛИ-НЕ 17, 5 вторые входы предыдущих двухвходовых элементов ИЛИ 21ь где l = 1, 2, ..., )logzm(—

3, подсоединены к выходам следующих двухвходовых элементов ИЛИ 21 +>, при этом второй выход последнего двухвходово- 10 го элемента 21 )log2m (-2 ИЛИ является последним, )log2m(, sxopoMglogzm(l-входового элемента ИЛИ вЂ” НЕ 17.

Временные диаграммы работы блока 7 управления (фиг,8) состоят из двенадцати (а, 15 б, в, г, д, е, ж, з, и, к, л, м) диаграмм изменений сигналов во времени при работе блока

7 управления на входах и выходах блока 7 управления и его элементов.

Буквенные обозначения временных ди- 20 аграмм работы блока 7 управления устройства умножения над полем GF(2 ) (фиг.8) соответствуют изменениям во времени сигналам на следующих входах и выходах блока 7 управления и его элементов (фиг.5): а — 25 первый, вход блока 7 управления; б — первый выход блока 7 управления; в — выход второго двухвходового элемента ИЛИ вЂ” НЕ 132 блока 6 управления (седьмой выход блока 7 управления); г — второй вход блока 7 управ- 30 ления; д — выход двухвходового элемента

ИЛИ 18 (третий выход блока 7 управления); е — прямой выход элемента 14 памяти блока

7 управления; ж — третий вход блока 7 управления; з — выход двухвходового элемен- 35 та И 15 (второй выход блока 7 управления); и — четвертый выход блока 7 управления; к . — пятый выход блока 7управления; л — входы

)logjam(-входо ваго элемента ИЛ И вЂ” Н Е 17 блока 7 управления; м — выход ()logjam()-вхо- .40 довс го элемента ИЛИ вЂ” Н Е 17 (шестой выход блока 7 управления).

Временные диаграммы работы устройства над полем GF(2m) при выполнении им операции обращения элемента поля при m 45

> 3 (фиг.9) состоят из двенадцати (а, б, в, г, д, е, ж, з, и, к, л, м) диаграмм изменений сигналов во времени при выполнении устройством операции обращения элементов на входах и выходах устройства, блоке 7 50 управления и функциональных элементах устройства.

Буквенные обозначения временных диаграмм работы устройства умножения над . полем GF(2 ) при выполнении им операции 55 обращения элемента поля (фиг.9) соответствует изменениям во времени сигналам на следующих входах и выходах устройства умножения над полем GF(2"), его блоке 7 управления и функциональных элементах (фиг.1): а — первая группа информационных входов устройства; б — вход "Обращение" устройства; в — вход "Исходное состояние" устройства; г — тактовый вход устройства; д — первый выход блока 7 управления; е— второй выход блока 7 управления;ж — третий выход блока 7 управления; з — четвертый выход блока 7 управления; и — пятый выход блока 7 управления; к- шестой выход блока

7 управления (выход "Готов" устройства); л — седьмой выход блока 7 управления (выход

"Занят" устройства); м- группа информационныхых выходов устройства.

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

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

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

Прежде чем приступить к описанию принципа действия устройства умножения над полем GF(2 ) (фиг.1), опишем сначала принцип действия -()log2m()-входового элемента ИЛИ вЂ” НЕ 17 и двоичного счетчика 16 блока 7 управления устройства умножения над полем GF(2 ) (фиг.7 и 6 соответственно), опишем принцип действия блока 7управления устройства умножения над полем G F(2") (фиг.5), а также принцип действия мультиплексора 41(42), регистра 2 с RS-триггерами и регистра 1> (1г) с 0-триггерами устройства умножения над полем GF(2 ) (фиг.4, 3 и 2 соответственно).

Кроме того, будем считать идентичными термин полинам и термин элемент поля.

plogzm()-входовый элемент ИЛИ вЂ” НЕ 77 блока 7 управления над полем GF(2 ) (фиг.7) работает следующим образом.

Если на всех входах()logzmP-входового элемента ИЛИ вЂ” НЕ 17 будут сформированы сигналы низких уровней, то на выходах всех его элементов 21 ИЛИ формируются сигналы низких уровней, а значит на оба входа двухвходового элемента ИЛИ-НЕ 20 под1728858

5

35

55 аются сигналы низких уровней, что приводит к формированию на его выходе и, следовательно, на выходе ()log2mD-входового элемента ИЛИ-НЕ 17 сигнала высокого уровня. В противном случае, если хотя бы на одном входе ()log2mP-входового элемента

ИЛИ вЂ” НЕ 17 будет сформирован сигнал высокого уровня, то на его выходе сформируется сигнал низкого уровня. ()!оцга(+1)-разрядный двоичный счетчик 16 блока 7 управления устройства умножения над полем GF(2 ) (фиг.6) работает следующим образом.

B исходном состоянии двоичного счетчика 16 его первый 0-триггер 191 сброшен в нулевое состояние, а состояния остальных

0-триггеров 19 соответствуют двоичному представлению числа 2 — m + 2. При

)log2m( этом на оба входа двоичного счетчика 16 подаются сигналы низких уровней. Если счетчик 16 находится не в исходном состоянии, то при подаче на вход установки в исходное состояние двоичного счетчика 16 импульсного сигнала высокого уровня первый D-триггер 191 сбросится в нулевое состояние, а остальные D-триггеры 19i, где

i = 2, 3, „„)logjam(+ 1, установятся в состояния, соответствующие (i — 1)-м разрядам двоичного представления натурального числа

2)log2m(гп + 2

При этом на первом и втором выходах двоичного счетчика 16 сформируются сигналы высокого и низкого уровней соответственно, а на остальных выходах — сигналы, соответствующие двоичному представлению числа 2) — m+2.

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

Блок 7 управления устройства умножения (фиг.5) работает следующим образом.

В исходном состоянии блока 7 управления его ()logjam(+1)-разрядный двоичный счетчик 16 находится в своем исходном состоянии (фиг.5 и 6), D-триггер 14 сброшен в нулевое состояние, на выходе первого элемента ИЛИ вЂ” НЕ 131 сформирован сигнал высокого уровня, на первый и второй входы блока 7 управления подаются сигналы низких уровней, а на третий вход постоянно подаются тактовые импульсы (фиг,5 и 8).

При этом на первом и четвертом выходах блока 7 управления сформированы сигналы высоких уровней каксигналы на выходе инвертора 12, на вход которого подан сигнал низкого уровня, и на инверсном выходе сброшенного в нуль первого D-триггера 191 двоичного счетчика 16 (фиг.5 и 6), а на остальных выходах блока 7 управления сформированы сигналы низких уровней: на втором выходе — как на выходе двухвходового элемента И 15, на первый вход которого подан сигнал низкого уровня; на шестом выходе, как на выходе Plog2mP-входового элемента ИЛИ вЂ” НЕ 17, не на всех входах которого сформированы сигналы низких уровней, ибо число 2) (— п1 + 2 не равно нулю при m > 2; на третьем выходе, как на выходе элемента И 18, на все входы которого подаются сигналы низких уровней; на пятом выходе, как на прямом выходе сброшенного в нуль первого D-триггера 191 ()logjam(+1)-разрядного счетчика 16 (фиг.5 и

6), на седьмом выходе, как на выходе элемента ИЛИ вЂ” НЕ 13г, на первый вход которого подается сигнал высокого уровня, На двухвходовых элементах ИЛИ вЂ” НЕ

13 собран RS-триггер, поэтому в исходном состоянии блока 7 управления на выходе второго двухвходового элемента ИЛИ вЂ” НЕ

13г, а значит и на информационном входе элемента 14 памяти, сформирован сигнал низкого уровня.

При подаче сигнала высокого уровня на первый вход блока 7 управления на выходе первого элемента ИЛИ вЂ” НЕ 131 и на первом выходе блока 7 управления формируются сигналы низких уровней, а на выходе второго элемента ИЛИ вЂ” НЕ 13г и, значит, на информационном входе D-триггера 14 и седьмом выходе блока 7 управления формируется сигнал высокого уровня, По переднему фронту очередного тактового импульса, поступающего на третий вход блока 7 управления, а значит и на тактовый вход D-триггера 14 и второй вход элемента И 15, D-триггер 14 установится в единицу, на первом входе элемента И 15 сформируется сигнал высокого уровня, и тактовые импульсы начнут формироваться на выходе элемента

И 15, а значит и на втором выходе блока 7 управления и на счетном входе ()logjam(+1)разрядного двоичного счетчика 16 (фиг.5 и

8), При этом состояние ()(оцггп(+1)-разрядного счетчика 16 будет изменяться до тех пор, пока на всех входах Plogzm()-входового элемента ИЛИ-НЕ 17 не сформируются сигналы низких уровней. При формировании сигналов низких уровней на всех входах

13

1728858

14 ()log2mp-входового элемента ИЛИ-НЕ 17 на его выходе формируется сигнал высокого уровня, который поступает на шестой выход блока 7 управления и на второй вход элемента ИЛИ 18, на выходе которого тоже 5 формируется сигнал высокого уровня, который поступает на третий выход блока 7 управления, на вход сброса в нулевое состояние элемента памяти 14 и на второй вход второго элемента ИЛИ-НЕ 132. При 10 этом на выходе второго элемента ИЛИ-НЕ

132, а значит на седьмом выходе блока 7 управления и на информационном входе Dтриггера, формируются сигналы низкого уровня, на первом входе элемента И 15 фор- 15 мируется сигнал низкого уровня и, следовательно, на выходе элемента И 15, а значит на счетном входе двоичного счетчика и на втором выходе блока 7 управления, формируется сигнал низкого уровня (фиг.5 и 8), а 20 состояние блока 7 управления может измениться только при поступлении сигнала высокого уровня на его первый или второй выходы.

При подаче сигнала высокого уровня 25 на второй вход блока 7 управления при сигнале низкого уровня на его первом входе Ц(од2гп(+1)-разрядный двоичный счетчик

16 устанавливается в свое исходное состоя- . ние и на выходе двухвходового элемента 30

ИЛИ 18, а значит на входе сброса в нулевое состояние D-триггера 14, на втором входе второго элемента ИЛИ-НЕ 132 и на третьем выходе блока 7 управления, формируется сигнал высокого уровня, по которому 0-триггер 35

14 сбрасывается в нулевое состояние, а на выходах первого и второго элементов ИЛИН Е 131 и 132 формируются сигналы высокого и низкого уровня соответственно.

Следовательно, при подаче сигнала вы- 40 сокого уровня на второй вход блока 7 управления блок 7 управления переходит в свое исходное состояние.

Таким образом, после подачи на первый вход блока 7 управления импульсного сиг- 45 нала высокого уровня, при сигнале низкого уровня на его втором входе и непрерывной серией тактовых импульсов на его третьем входе, блок 7управления отрабатываетсвой полный цикл работы, в течение которого 50 сигнал на пятом выходе блока 7 управления изменит ceqA уровень с низкого на высокий

2)log2m((2)log2m(m + 2) = m раз, Следовательно, поскольку на тактовый вход двоичного счетчика 16 должно посту-,55 пить в два раза больше перепадов уровней сигналов с низкого на высокий, чем сформированных таких же перепадов на его втором выходе, то на втором выходе блока 7 управления при отработке им полного цикла работы сформируются 2(m — 2) импульсных сигналов высокого уровня.

Мультиплексор 4 устройства умножения над полем GF(2 и) (фиг.4) работает следующим образом.

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

Регистр 2 устройства умножения .над полем GF(2 ) (фиг,3) работает следующим образом.

В исходном состоянии регистра 2 все

RS-триггеры 9 находятся в нулевом состоянии и на все входы-регистра 2 подаются сигналы низких уровней. При этом на всех выходах регистра 2 сформированы сигналы низких уровней (регистр 2 сброшен в нулевое состояние).

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

Регистр 1 устройства умножения над полем GF(2") (фиг.2) работает следующим образом.

В исходном состоянии регистра 1 его

D-триггеры 8 находятся в нулевых состояниях, а на все входы принудительной установки регистра 1, на его тактовый вход и вход сброса в нулевое состояние подаются сигналы низких уровней. При исходном состоянии регистра 2 сигналы на его информационных входах не определяются и могут быть произвольными. При этом на всех выходах регистра 2 с D-триггерами сформированы сигналы низких уровней (регистр 2 сброшен в нулевое состояние). При подаче произвольных сигналов на входы принудительной установ15

1728858

5

25

55 ки регистра 1 при сигналах низких уровней на его тактовом входе и входе сброса в нулевое состояние, на выходах регистра 1 сформируются сигналы, равные сигналам на его одноименных входах принудительной установки. Значения уровней сигналов на выходах регистра 1 сохраняются и после подачи на все его входы принудительной установки сигналов низких уровней. При подаче сигнала высокого уровня на вход сброса в нулевое состояние регистра 1 при сигналах низких уровней на всех его входах принудительной установки все D-триггеры 8 сбрасываются в нулевое состояние и регистр 1 переходит в свое исходное состояние при сигнале низкого уровня на его тактовом входе.

По переднему фронту импульсного сигнала высокого уровня, поступающего на тактовый вход регистра 1 при сигналах низких уровней на его входах принудительной установки и входе сброса в нулевое состояние, на выходах регистра 1 формируются сигналы, равные сигналам на его одноименных информационных входах. Сигналы на выходах регистра 1 сохраняются сколь угодно долго даже при изменении сигналов на его информационных входах при сигналах низких уровней íà его входах принудительной установки, тактовом входе и входе сброса в нулевое состояние.

Устройство умножения над полем

CF(2 ) работает следующим образом.

B исходном состоянии устройства умножения над полем GF(2 ) его регистры 1, регистр 2 и блок 7 управления находятся в своих исходных состояниях, на тактовый вход устройства подается непрерывная серия тактовых импульсов высокого уровня, а на остальные входы подаются сигналы низких уровней, При этом, на всех входах группы 3 блоков матричного преобразования, а значит и на всех ее выходах сформированы сигналы низких уровней. Следовательно, на всех выходах группы 5 блоков элементов И, а значит и на всех выходах блока 6 сумматора по модулю два, тоже сформированы сигналы низких уровней, которые подаются на информационные выходы устройства умножения и на информационные входы обоих регистров 1 и 1z, причем на выходе "Готов" устройства сформированы сигнал низкого уровня (фиг.9).

В исходном состоянии устройства умножения над полем GF(2 ) (фиг.1 и 9) на первом и втором управляющих входах первого мультиплексора 4 сформированы сигналы низкого и высокого уровней соответственно, а на первом и втором управляющих входах второго мультиплексора 4г сформированы сигналы высокого и низкого уровней соответственно.

Устройство умножения над полем GF() (фиг.1) может выполнять две операции над конечным полем полиномов GF(2 ): операцию умножения двух элементов поля и операцию определения обратного элемента для ненулевого элемента поля.

При выполнении устройством .операции умножения двух элементов поля

GF(2 ) на входы первой и второй групп информационных входов устройства умножения над полем GF(2 ) подаются сигналы, соответствующие коэффициентам первого и второго полиномов-сомножителей соответственно. При этом на выходах первого и второго регистров 11 и 12 (фиг.1 и 2) формируются сигналы, равные сигналам на установочных входах, а значит и на входах первой и второй групп информационных входов устройства соответственно, Сигналы с выходов первого регистра 1> с D-триггерами, преобразуясь в группе 3 блоков матричного преобразования, подаются на входы первой группы информационных входов группы 5 блоков элементов И, на входы второй группы информационных входов которой поступают через второй мультиплексор

4г сигналы с выходов второго регистра 1г.

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

Так, исходное состояние устройства умножения над полем GF(2 ), соответствует операции умножения нулей поля GF(2 ).

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