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

(19) (11) 5 6 06 Р 7/49, 7/52 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И,И,Ковалив(56) Блок Э.Л., Зяблов В.В. Обобщенные каскадные коды (Алгебраическая теория и сложность реализации) вып. 5, - М.: Связь, 1976, с, 106, рис, 3.37.Авторское свидетельство СССР В 1226445, кл, 6 06 Р 7/52, 1984.(541 УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЭЛЕМЕНТОВ КОНЕЧНОГО ПОЛЯ ОР(2 ) ПРИ а 3(57) Изобретение относится к специализированным устройствам вычислительной техИзобретение относится к специализированным устройствам вычислительной техники и может использоваться в кодирующих и декодирующих устройствах, работающих с элементами конечных полей полиномов ОЦ 2 ) при щ3, например в устройствах системы "компакт-диск".Известны устройства деления полиномов над конечными полями ОР(2 ), содержащее два блока логарифмирования, блок вычитания и блок антилогарифмирования, причем входы блоков логарифмирования являются входами коэффициентов полиномов-сомножителей, выходы блоков лога-, рифмирования подсоединены к двум,:. группам входов блока вычитания соответст-; венно, выход которого подсоединен к входу блока антилогарифмирования, выходы которого являются выходами коэффициентов ники и может быть использовано в кодирующих и декодирующих устройствах, работающих с элементами конечных полей полиномов ОГ(2 ) при в3, например в устройствах системы "компакт-диск". Цель изобретения - сокращение аппаратурн ых затрат. Устройство умножения элементов конечного поля ОР(2 ) состоит из первого и второго регистров с О-триггерами, третьего регистра с ВЗ-триггерами, группы блоков матричного преобразования, первого и второго пультиплексоров, группы блоков элементов И, блока сумматоров по модулю дваи блока управления, который состоит из элемента НЕ, двух двухвходовых элементов и элемента ИЛИ - НЕ, О-триггера, элемента И, 1 о 92 а+1)-разрядного двоичного счетчика и ф элемента ИЛИ. 1 з.п. ф-лы, 9 ил. полинома-произведения соответственно, При замене в таких устройствах блока вычитания блоком суммирования устройства деления преобразуются в устройства умножения двух полиномов над конечными полями ОР(2 ),Недостатками таких устройств являются их большая сложность реализации и большие.аппаратурные затраты при в4.Известно устройство для деления элементов поля Галуа, содержащее первый и второй сдвиговые регистры, один элемент И, один элемент ИЛИ-НЕ, декодер, кодер и умножитель, причем, информационные входы первого и второго сдвиговых регистров являются входами устройства коэффициентов полинома-делителя и полинома-делимого соответственно, выходы подсоединены к входам декодера и к первой группе входов=2 в+ 2 - 4 = 2 в - 4+ 2 = К+ 2.Тогда,э май ю.гР10С;+ =(С В)=ВЪ)= В =В;что и требовалось доказать. Другими словами,прив 2,в М,Сп=ВСп = В = В, где символом В записан полином из поля ОР(2 ), обратный ненулевому полиному из этого же конечногополя.Таким образом, при формировании сигнала высокого уровня на выходе "Готов" устройства на информационных выходах 20устройства будут сформированы сигналы,соответствующие коэффициентам полинома, равного обратному к обращаемому полиному.При формировании сигнала высокого 25уровня на третьем выходе блока 7 управления регистр 2 сбрасывается в нулевое состояние,Сигналы высокого уровня на выходе"Готов" устройства и на третьем выходе блока 7 управления будут сохраняться до техпор, пока на вход "Исходное состояние" устройства не будет подан импульсный сигналвысокого уровня, При этом блок 7 управления установится в свое исходное состояние 35и после переходных процессов от переднего фронта импульсного сигнала, поступающего на второй вход блока 7 управления, навыходе "Готов" устройства сформируетсясигнал низкого уровня, а по заднему срезу 40импульсного сигнала высокого уровня, поступающего на второй вход блока 7 управления, на третьем выходе блока 7 управлениясформируется сигнал низкого уровня.Кроме того, по импульсному сигналу, 45поступающему на вход "Исходное состояние" устройства, его оба регистра 11 и 1 гсбросятся в нулевое состояние, после чеговозможно выполнение очередной операцииумножения или обращения над полем 50ОЦ 2 ),Необходимо заметить, что наличие сигнала высокого уровня на выходе "Занят"устройства указывают внешним устройствам на то, что устройство занято выполнением операции обращения и не можетпринимать на свои информационные входы,на входы "Обращение" и "Исходное состояние" сигналы, отличные от сигналов низкогоуровня; наличиесигнала высокогоуровня на выходе Готов" устройства указывает внешним устройствам на то, что на информационных выходах устройства умножения сформированы сигналы, соответствующие коэффициентам обратного элемента поля,Таким образом, предлагаемое устройство выполняет операцию умножения двух элементов поля ОР(2 ) так же, как и известное за один такт работы устройства, а операцию обращения элемента поля ОР(2 ) за 2 а - 3 такта работы устройства, включая.и такт приема коэффициентов обращаемого элемента, против а тактов работы при выполнении такой же операции обращения известн ым устройством.Однако выполнение операций предлагаемым устройством производится меньшими аппаратурными затратами,Докажем это утверждение.Аппаратурные затраты прототипа составляют три а-разрядные регистра с 1 К- триггерами, два мультиплексора на три группы по в входов каждая, один мультиплексор на две группы по в информационных входов каждая, одну группу блоков матричного преобразования, две группы по в элементов И каждая, два блока по щ-вхогдовых сумматора по модулю два каждый и блок синхронизации, содержащий (гп+2) О- триггера, пять двухвходовых элементов И, два двухвходовые элементы ИЛИ - НЕ и один инвертор.Аппаратурные затраты предлагаемого устройства составляют три щ-разрядные регистра, из которых два с О-триггерами и один с КЯ-триггерами, два мультиплексора на две группы по в информационных входов каждый, одну группу блоков матричного преобразования, одну группу из в элементов И, один блок из в в-входовых сумматоров по модулю два и блок управления, содержащий один инвертор, один двухвходовый элемент И, один 01 оцгво-входовый элемент ИЛИ - НЕ, один двухвходовый элемент ИЛИ, два элемента ИЛИ - НЕ и Цоцгв+2) О-триггеров, где символом )1 оцгщ обозначено натуральное число, полученное в результате округления до ближайшего большего целого числа 1 одгв, если 1 оцга число не целое.При этом каждый из трех регистров известного устройства состоит из в 1 К-триггеров и щ инверторов, а в предлагаемом устройстве два регистра содержат каждый по в О-триггеров, синхронизируемых по фронту и третий регистр содержит в КЯ-триггеров.1 К-триггер, входящий в состав регистра известного устройства, имеющий минимальные аппаратурные затраты, может быть реализован по известной схеме, где К-триггер содержит четыре двухвходовыхдятся два в-разрядные регистра с О-триггерами, один п-разрядный регистр с РЗ-триггерами, один мультиплексор на две группы по гп входов и блок управления.Для сравнения исключенных из известного устройства и введенных в него аппаратурных затрат приведем аппаратурныезатраты функциональных элементов типа регистров, мультиплексоров, блоков синхронизации и управления через их синтез налогическихэлементахтипа И, И - НЕ и ИЛИ - НЕ, причем, синтез введенных функциональных элементов осуществим на двухвходовых логических элементах, представляющих в совокупности максимальныеаппаратурные затраты введенных функциональных элементов. Так, например, До 9 га)-входовый элемент ИЛИ - НЕ может быть реализован на Цо 92 щ - 2) двухвходовых элементах ИЛИ и одном двухвходовом элементе ИЛИ-НЕ по схеме, приведенной на фиг.7,Если на схеме, приведенной на фиг.7, поменять двухвходовые элементы ИЛИ и ИЛИ - НЕ соответственно на двухвходовые элементы И и И - НЕ, то приведенная на фиг.7 схема будет реализовывать Цо 92 п 3)- входовый элемент И - НЕ.Докажем, что число двухвходовых элементов ИЛИ на схеме, приведенной на фиг.7, равно До 92 гп). Доказательство приведем по методу математической индукции.Схема Ц 092 в)-входового элемента ИЛИ-НЕ, приведенная на фиг,7, составлена так, чтобы ни один из входов ни одного из 25303540 45 50 55 элемента И - НЕ и два трехвходовых элемента И - НЕ. О-триггер, входящий в состав первых двух регистров предлагаемогоустройства, имеющий минимальные аппаратурные затраты, может быть реализован по 5другой известной схеме, причем для синхронизации триггера положительным фронтомв этой схеме элементы ИЛИ заменяются наэлементы И, О-триггер содержит здесьшесть трехвходовых элемента И - Н Е. 10РЗ-триггер, входящий в состав третьегорегистра предлагаемого устройства, имеющий минимальные аппаратурные затраты,может быть реализован по известной схеме,где РЯ-триггер содержит два двухвходовых 15элемента И - НЕ,Для реализации схемы предлагаемогоустройства из известного исключаются трив-разрядн ые регистра сК-триггерами, двамультиплексора на три группы по в входов 20каждая, одна группа из в двухвходовыхэлементов И, один блок из гп в-входовыхсумматоров по модулю два и блок синхронизации, кроме того, в известную схему вводвухвходовых элементов ИЛИ и ИЛИ - НЕ не был бы свободным и чтобы ни один из входов двухвходовых элементов ИЛИ и ИЛИ - НЕ не соединялись. Значит, при гп4 нет необходимости применять элементы ИЛИ, так как два входа двухвходового элемента ИЛИ - НЕ будут являться входами Цо 92 в)- входового элемента ИЛИ-НЕ, Для преобразования двухвходового элемента ИЛИ - НЕ в трехвходовый элемент ИЛИ - НЕ один из входов элемента ИЛИ-НЕ присоединим к выходу двухвходового элемента ИЛИ, два входа которого будут являться входами трехвходового элемента ИЛИ-НЕ, третий вход которого подсоединен к другому входу двухвходового элемента ИЛИ-НЕ. Следовательно, при числео 92 в= 3 число двухвходовых элементов ИЛИ в трехвходовом элементе ИЛИ - НЕ равно единице.Для преобразования трехвходового элемента ИЛИ - НЕ в четырехвходовый необходимо и достаточно один из входов трехвходового элемента ИЛИ - НЕ подсоединить к выходу двухвходового элемента ИЛИ; два входа которого будут являться двумя входами четырехвходового элемента ИЛИ - НЕ, следующих два входа которого подсоединены соответственно к второму и третьему входам трехвходового элемента ИЛИ - НЕ. Следовательно, при 1 о 92 в = 4 число двух-. входовых элементов ИЛИ в четырехвходовом элементе ИЛИ - НЕ равно двум.Допустим, что 1-входовый элемент И.ЛИ - Н.Е содержит Кдвухвходовых элементов ИЛИ, Тогда для преобразования 1-входового элемента ИЛИ - НЕ в (1+1)- входовый элемент ИЛИ-НЕ необходимо и достаточно его подсоединить к дополнительному одному двухвходовому элементу ИЛИ, входы которого будут являться двумя входами (1+1)-входового элемента ИЛИНЕ, остальные Квходов которого будут являться остальными, неподсоединенными к выходу дополнительного элемента ИЛИ, К - 1 входами 1-входового элемента ИЛИ-НЕ соответственно, Следовательно, (1+1)-входовый элемент ИЛИ-НЕ, числом равным К - 2 + 1 = К - 1. Отсюда До 92 в)-входовый элемент ИЛИ-Н Е содержит Цо 92 а - 2) двухвходовых элемента ИЛИ и один двухвходовый элемент ИЛИ-НЕ, что и требовалось доказать.Таким образом, для реализации схемы предлагаемого устройства из известной схемы исключаются в составе трех а-разрядных регистров 3 а инверторов, 12 в двухвходовых элементов И - НЕ и 6 гп трехвходовых элементов И-НЕ, в составе двух мультиплексоров на три группы по в входов - бв двухвходовых элементов И и 2 в трехвходовых элементов ИЛИ, в составе группы из в элементов И - п 1 двухвходовых элег 2ментов И, в составе блока из а в-входовых сумматоров по модулю два - в в-входовые сумматоры по модулю два и в составе блока 5 синхронизации - пять двухвходовых элементов И, один инвертор, два двухвходовые . элемента ИЛИ - НЕ и (а+2) О-триггеров, при этом в известную схему вводятся в составе двух а-разрядных регистров с О-триггера ми 12 а трехвходовых элементов И - НЕ, в составе в-разрядного регистра с КЯ-триггерами вводятся 2 п 1 двухвходовых элементов И - Н Е, в составе мультиплексора на две группы по п 1 входов вводятся 2 п 1 двухвходо вых элементов И и в двухвходовых элементов ИЛИ, и в составе блока управления вводятся один инвертор, один двухвходовый элемент И, один двухвходовый элемент ИЛИ, два двухвходовых элемента ИЛИ - НЕ, 20 один оц 2 а-входовы й элемент ИЛ И - Н Е, эквивалентный (оц 2 а - 2 двухвходовым элементам ИЛИ и одному элементу ИЛИ - НЕ, а также (2 + оц 2 в) О-триггеров где оц 2 в - число, полученное в результате ок ругления числа оц 2 а до ближайшего большего целого, если число оц 2 в есть число не целое.При подсчете алгебраической суммы числа однотипных логических элементов, 30 исключенных (со знаком "минус") и введенных (со знаком "плюс") в известное устройство и из него соответственно, при реализации предлагаемого устройства имеем: число исключенных инверторов равно 35 Зв; число исключенных двухвходовых элементов И равно(в +4 а+4); число исклю 2ченных двухвходовых элементов И - НЕ равно 10 а; число исключенных трехвходовых элементов ИЛИ равно 2 а; число исклю ченных в-входовых сумматоров по модулю два равно в; число исключенных О-триггеров равно (а - оц 2 а); число введенных двухвходовых элементов ИЛИ равно (в + оц 2 а - 1); число введенных двухвходовых 45 элементов ИЛИ - НЕ равно 1; число введенных трехвходовых элементов И - НЕ равно 6 в.Для дальнейшего сравнения аппаратурных затрат известного и предлагаемого уст ройств рассматриваем введенные трехвходовые элементы И - НЕ как совокупности из одного двухвходового элемента И и одного двухвходового элемента И - НЕ. Тогда число исключенных инверторов равно 55 За; число исключенных двухвходовых элементов И равно в + 4 в+ 4; число исключенных двухвходовых элеентов И-НЕ равно 10 а; число исключенных трехвходовых элементов ИЛИ равно 2 в; число исключенных в-входовых сумматоров по модулю два равно в; число исключенных О-триггеров равно (а - оц 2 а; число введенных двухвходовых элементов ИЛИ равно (а+оц 2 в - 1); число введенных двухвходовых элементов ИЛИНЕ равно единице; число введенных двухвходовых элементов И равно 6 а и число введенных элементов И-НЕ равно 6 в.Физически, по технологическим параметрам выполнение по одной технологии, аппаратурные затраты на один двухвходовый элемент ИЛИ можно приравнять к аппаратурным затратам на один элемент И, а аппаратурные затраты на один элемент ИЛИ - НЕ можно приравнять к аппаратурным затратам на один двухвходовый элемент И - НЕ. Следовательно, с учетом вышесказанного, при реализации из известного предлагаемого устройства баланс аппаратурных затрат составляет экономию Зв+ в +4 а+4+10 а+2 а+ в+ в - оц 2 в=2= в + 21 а - оц 2 а+ 4 элементов против увеличения на в +оцгв - 1+ 1+ 6 а+ 6 в = 13 а + оц 2 в элементов, что в конечном счете дает общую экономию аппаратурных затрат на а + 21 а - оц 2 а + 4 - 13 а -2оц 2 в = а + 8 а - 2 оц 2 в+ 4 логических элементов.Так, например, при в = 8 зкономия аппаратурных затрат составит 126 логических элементов без учета того, что в-входовые сумматоры по модулю два эквивалентны в - 1 двухвходовым сумматорам по модулю два, которые в свою очередь по минимальному составу эквивалентны трем двухвходовым элементам (по одному элементу И, ИЛИ и И-НЕ) каждый,Таким образом, для реализации предлагаемого устройства умножения над полем ОЕ(2 ) необходимо иметь аппаратурных затрат на (а + 8 - 2 оц 2 в+ 4) логических2элементов меньше, чем для реализации известного.Хотя время выполнения предлагаемым устройством операции обращения элемента поля ОЕ(2") увеличивается по сравнению со временем выполнения этой операции известным устройством на в - 3 тактов его работы, но значительное уменьшение аппаратурных затрат на реализацию предлагаемого устройства может во многих случаях оказаться решающим в выборе предлагаемого устройства для применения его в составе, например, декодирующих устройств умножения над полем ОЕ(2 ).Формула изобретения 1. Устройство для умножения элементов конечного поля ОЕ(2 ) при а3, содержащее три регистра, два мультиплексора, группу блоков матричного преобразования,25 1728858 26 5 10 15 20 25 30 35 40 45 50 55 группу блоков элементов И, блок сумматоров по модулю 2 и блок управления, причем выходы блоков матричного преобразования группы соединены соответственно с первыми входами блоков элементов И группы, выходы которых соединены с соответствующими входами сумматоров по модулю 2 блока, информационные входы первой и второй групп устройства соединены соответственно с информационными входами первой и второй групп первого мультиплексора, выходы первого регистра соединены с соответствующими входами блоков матричного преобразования, первый и второй входы блока управления соединены соответственно с входами "обращения" и тактовым входом устройства, выход "готовности" которого соединен с первым выходом блока управления, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, информационные входы первой группы устройства соединены с соответствующими установочными входами первого и второго регистров, выходы первого мультиплексора соединены соответственно с установочными входами третьего регистра, выходы которого соединены соответственно с информационными входами первой группы второго мультиплексора, информационные входы второй группы которого со-. единены соответственно с выходами второго регистра, а выходы - соответственно с вторыми входами блоков элементов И группы, выходы сумматоров по модулю 2 блока соединены с информационными входами первого и третьего регистров и выходами результата устройства, вход сброса которого соединен с входами сброса первого и третьего регистров и третьим входом блока управления, первый вход которого соединен с первым управляющим входом первого мультиплексора, второй управляющий вход которого соединен с вторым входом блока управления, третий выход которого соединен с тактовыми входами первого и третьего регистров, четвертый, пятый, шестой и седьмой выходы блока управления соединены соответственно с входом сброса второго регистра, первым и вторым управляющими входами второго мультиплексора и выходом "Занят" устройства.2. Устройство по п.1; о т л и ч а ю щ е ес я тем, что блок управления содержит элемент ИЛИ, элемент И, три элемента ИЛИН Е, Р-тр и гге р, Ц од 2 в+1)-разрядный двоичный счетчик, (где )од 2 в-ближайшее целое, большее к 1 од 2 в число, если 1 од 2 в - нецелое) и элемент НЕ, вход которого соединен с первым входом блока управления и первым входом первого элемента ИЛИ - НЕ, выход которого соединен с первым входом второго элемента ИЛИ-НЕ, второй вход которого соединен с входом сброса О-триггера, выходом элемента ИЛИ и четвертым выходом блока управления, второй вход которого соединен с тактовым входом О-триггера и первым входом элемента И, второй вход которого соединен с выходом О-триггера, информационный вход которого соединен с выходом второго элемента ИЛИ - НЕ, вторым входом первого элемента ИЛИ - НЕ и седьмым выходом блока управления, третий вход которого соединен с первым входом элемента ИЛИ и входом установки в нуль 1 одггп+1)-разрядного двоичного счетчика, счетный вход которого соединен с выходом элемента И и третьим выходом блока управления, второй выход которого соединен с выходом элемента НЕ, а четвертый и пятый выходы - соответственно с прямым и инверсным выходами младшегого раз ряда Цод 2 в+1)-разрядного двоичного счетчика, прямые выходы 9 од 2 вО старших разрядов которого соединены с соответствующими входами третьего элемента ИЛИ-НЕ, выход которого соединен с шестым выходом блока управления и вторым входом элемента ИЛИ.ственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 ои аказ 1409 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/55 10 умножителя соответственно, а тактовые входы объединены и подсоединены к выходу элемента И, первый вход которого является тактовым входом устройства, а второй вход подсоединен к выходу элемента ИЛИ - НЕ, входы которого объединены с второй группой входов умножителя и подсоединены к выходам кодера, входы которого подсоединены к выходам декодера, при этом выходы умножителя являются выходами коэффициентов результирующего полинома.В этом устройстве производится операция умножения элементов конечного поля, а для выполнения операции деления элементов поля Галуа производится предварительное определение обратного элемента для полинома-делителя при помощи декодера и кодера, содержащее ПЗУ каждый.Недостатком такого устройства являются его большие аппаратурные затраты.Цель изобретения - сокращение аппаратурных затрат,Для достижения поставленной цели в устройстве умножения элементов конечного поля ОР(2 ) при гп3, содержащем три регистра, два мультиплексора, группу блоков матричного преобразования, группу блоков элементов И, блок сумматоров по модулю два и блок управления, причем выходы блоков матричного преобразования группы соединены соответственно с первыми входами блоков элементов И группы, выходы которых соединены с соответствующими входами сумматоров по модулю два блока, информационные входы первой и второй групп устройства соединены соответственно с информационными входами первой и второй групп первого мультиплексора, выходы первого регистра соединены с соответствующими входами блоков матричного преобразования, первый и второй входы блока управления соединены соответственно с входами "Обращение" и тактовым входом устройства, выход "Готовность" которого соединен с первым выходом блока управления, информационные входы первой группы устройства соединены с соответствующими установочными входами первого и второго регистров, выходы первого мультиплексора соединены соответственносустановочными входами третьего регистра, выходы которого соединены соответственно с информационными входами первой группы второго мультиплексора, информационные входы второй группы которого соединены соответственно с выходами второго регистра, а выходы соответственно с вторыми входами блоков элементов И группы, выходы сумматоров по модулю два блока соединены соответствен 15 20 25 30 35 40 45 50 55 но с информационными входами первого и третьего регистров и выходами результата устройства, вход сброса которого соединен с входами сброса первого и третьего регистров и третьим входом блока управления, первый вход которого соединен с первым управляющим входом первого мультиплексора, второй управляющий вход которого соединен с вторым входом блока управления, третий выход которого соединен с тактовыми входами первого и третьего регистров, четвертый, пятый, шестой и седьмой выходы блока управления соединены соответственно с входом сброса второго регистра, первым и вторым управляющими входами второго мультиплексора и выходом "Занят" устройства.При этом блок управления содержит элемент ИЛИ, элемент И, три элемента ИЛИ - НЕ, О-триггер, оцгщ(+1)-разрядный двоичный счетчик (где )оц 2 в - ближайшее целое большее коц 2 гп число, если 1 оцгщ - нецелое) и элемент НЕ, вход которого соединен с первым входом блока управления и первым входом первого элемента ИЛИ - НЕ, выход которого соединен с первым входом второго элемента ИЛИ - НЕ, второй вход которого соединен с входом сброса О-триггера, выходом элемента ИЛИ и четвертым выходом блока управления, второй вход которого соединен с тактовым входом 0-триггера и первым входом элемента И, второй вход которого соединен с выходом О-триггера, информационный вход которого соединен с выходом второго элемента ИЛИ - НЕ, вторым входом первого элемента ИЛИ - НЕ и седьмым выходом блока управления, третий вход которого соединен с первым входом элемента ИЛИ и входом установки в нуль 9 оц 2 п(+1)-разрядного двоичного счетчика, счетный вход которого соединен с выходом элемента И и третьим выходом блока управления, второй выход которого соединен с выходом элемента НЕ, а четвертый и пятый выходы - соответственно с прямым и инверсным выходами младшего разряда Ц оцггп(+1)-разрядного двоичного счетчика, прямые выходы Доргазм старших разрядов которого соединены с соответствующими входами третьего элемента ИЛИ - НЕ, выход которого соединен с шестым выходом блока управления и вторым входом элемента ИЛИ.На фиг.1 изображена структурная блоксхема устройства умножения над полем О Р(2 ); на фиг.2 - структурная схема регистра с О-триггерами; на фиг.3 - структурная схема регистра с ЙЗ-триггерами; на фиг.4 - структурная схема мультиплексора; на фиг.5 - структурная схема блока управле40 второй группы информационных входов первого мультиплексора 41 являются одноименными а входами второй группы информационных входов устройства, щ выходов первого мультиплексора 41 подсоединены к 45 одноименным в установочным входам второго регистра 1 г, гп выходов которого подсоединены к одноименным п 1 входам первой группы информационных входов второго мультиплексора 4 г, п 1 входов второй группы информационных входов которого подсоединены к одноименным а выходам регистра 2, а а выходов второго мультиплексора 4 г подсоединены к одноименным гп входам второй группы входов группы 5 блоков элементов И, причем е выходов блока 6 сумматоров по модулю два объединены с одноименными а информационными входами первого и второго регистров 11 и 1 г и являются одноименными в информационными выходами устройства,50 55 ния; на фиг.6- структурная схема двоичного счетчика блока управления; на фиг.7 - структурная схема )оцгв(-входового элемента ИЛИ-НЕ блока управления; на фиг.8 - временные диаграммы работы блока уп равления; на фиг.9 - временные диаграммы работы устройства умножения над полем ОГ(2 ) при выполнении им операции обращения элемента поля при а 3.Устройство умножения над полем 10 ОР(2") (фиг.1) состоит из первого и второго регистров 11 и 1 г с О-триггерами, третьего регистра 2 с ВЯ-триггерами, одной группы 3 блоков матричного преобразования, первого и второго мультиплексоров 41 и 4 г с двумя 15 группами информационных входов каждый, одной группы 5 блоков элементов И, одного блока 6 сумматоров по модулю два и блока 7 управления, причем в установочных входов первого регистра 11 являются одно именными в входами первой группы информационных входов устройства и объединены с одноименными п 1 входами первой группы информационных входов первого мультиплексора 41 и с а информа ционными входами регистра 2, а прямых выходов первого регистра 11 подсоединены к одноименным а входам группы 3 блоков матричного преобразования, в выходов которого подсоединены к соответствующим 30 гп 1 входов первой группы входов группы 5 блоков элементов И, а выходов которой подсоединены к соответствующим а входам блока 6 сумматоров по модулю два, п 1 выходов которого являются одноименным 35 т информационными выходами устройства и подсоединены к одноименным объединенным п 1 информационным входам первого и второго регистров 11 и 1 г, при этом п 1 входов при этом первый и второй входы блока 7 управления, являющиеся соответственно входами "Обращение" и "Исходное состояние" устройства, подсоединены к первому управляющему входу первого мультиплексора 41 и к объединенным входам сброса в нулевое состояние первого и второго регистров 11 и 1 г, а третий вхОд блока 7 управления является тактовым входом устройства, при этом с первого по пятый выходы блока 7 управления подсоединены к второму управляющему входу первого мультиплексора 41, к объединенным тактовым входам первого и второго регистров 11 и 1 г, к входу сброса в нулевое состояние регистра 2, к первому и к второму управляющим входам второго мультиплексора 4 г соответственно; а шестой и седьмой выходы блока 7 управления - являются выходами "Готов" и "Занят" устройства. Регистр 11 (1 г) (фиг.2) состоит из щ О-триггеров 8, причем входы установки в единичное состояние и информационные входы всех а О-триггеров 8 являются одноименными .с порядковыми номерами О- триггеров 8 а установочными и гп информационными входами регистра 11(1 г) соответственно, прямые выходы О-триггеров 8 являются одноименными с порядковыми номерами О-триггеров 8 в выходами регистра 11(1 г), при этом объединенные тактовые входы всех а О-триггеров 8 являются тактовым входом регистра 11(1 г), а объединенные входы сброса в нулевое состояние всех п 1 О-триггеров являются входом сброса в нулевое состояние регистра 11 (1 г),Регистр 2 (фиг.3) состоит из а ВЯ-триггеров 9, причем входы установки в единичное состояние всех а ВЯ-триггеров 9 являются одноименными с порядковыми номерами КЯ- триггеров 9 в установочными входами регистра 2, а объединенные входы сброса всех ВЯ-триггеров 9 являются входом сброса в нулевое состояние регистра 2.Мультиплексор 41 (4 г) (фиг.4) состоит из 2 а двухвходовых элементов И 10 и п 1 двухвходовых элементов ИЛИ 11, причем первые входы первых по порядку счета п 1 двухвходовых элементов И 10 являются одноименными с порядковыми номерами двухвходовых элементов И 10 в входами первой группы информационных входов мультиплексора 41(4 г), первые входы следующих по порядку счета в двухвходовых элементов И 10 с порядковыми номерами от (а + 1) по 2 а являются в входами второй группы информационных входов мультиплексора 41(4 г) номерами на в меньше порядковых номеров соответствующего двухвходового элемента И 10, при этом вторые объединенные входы первых по поряд 1728858ку счета а двухвходовых элементов И 10 объединены и являются первым управляющим входом мультиплексора 4 (42), а вторые объединенные входы следующих по порядку счета в двухвходовых элементов И 10 с порядковыми номерами от (в + 1) по 2 щ включительно являются вторым управляющим входом мультиплексора 41 (42), причем выходы первых по порядку счета в двухвходовых элементов И 10 подсоединены к первым входам всех а одноименных двухвходовых элементов ИЛИ 11, вторые входы которых подсоединены к выходам следующих по порядку счета в двухвходовых элементов И 10 с порядковыми номерами на щ больше порядковых номеров двухвходовых элементов ИЛИ 11 соответственно, а выходы являются одноименными а выходами мультиплексора 41 (42),Блок 7 управления (фиг.5) состоит из инвертора 12, первого и второго двухвходовых элементов ИЛИ-НЕ 131 и 132, О-триггера 14, элемента И 15, (одгщ 41)-разрядного двоичного счетчика 16, где символомодге обозначено натуральное число, полученное и ри округлении числа одев до ближайшего целого, если число одоп - нецелое, (одгв)- входового элемента ИЛИ - НЕ 17 и элемента 18 ИЛИ, причем, вход инвертора 12 является первым входом блока 7 управления и объединен с первым входом первого двухвходового элемента ИЛИ - НЕ 131, выход которого подсоединен к первому входу второго двухвходового элемента ИЛИ - НЕ 13 г, первый вход элемента ИЛИ 18 является вторым входом блока 7 управления и объединен с входом установки в исходное состояние (од 2 щ+1)-разрядного двоичного счетчика 16, прямой вход О-триггера 14 подсоединен к первому входу элемента И 15, а тактовый вход О-триггера 14 объединен с вторым входом элемента И 15 и является третьим входом блока 7 управления, при этом выход инвертора 12 является первым выходом блока 7 управления, выход элемента И 15 объединен со счетным входом (одгт+1)-разрядного двоичного счетчика 16 и является вторым выходом блока 7 управления, выход элемента ИЛИ 18 объединен с вторым входом двухвходового элемента ИЛИ - НЕ 13 г, с входом сброса в нулевое состояние О-триггера 14 и является третьим выходом блока 7 управления, причем инверсный и прямой выходы самого младшего разряда (од 2 т+1)-разрядного двоичного счетчика 16 являются четвертым и пятым выходами блока 7 управления соответственно, выход (одггп)-входового элемента ИЛИ-НЕ 17 объединен с вторым входом элемента ИЛИ 18 и является шестым 5 10 15 20 25 30 35 40 45 50 55 выходом блока 7 управления, выход второго двухвходового элемента ИЛИ-НЕ 132 является седьмым выходом блока 7 управления и объединен с вторым входом первого двухвходового элемента ИЛИ - НЕ 131 и с информационным входом О-триггера 14, при этом прямые выходыод 2 встарших разрядов (одев старших разрядов (од 2 гп+1)-.разрядного двоичного счетчика 16 подсоединены соответственно к входам (одев)-входового элемента ИЛИ - НЕ 17.(од 2 щ+ )-разрядный двоичный счетчик 16 (фиг.6) блока 7 управления состоит из (од 2 в+1) О-триггеров 19, где символом одгв обозначено натуральное число, получаемое в результате округления до ближайшего целого числа одггп, если оно не целое, причем тактовый вход первого О-триггера 191 памяти является счетным входом двоичного счетчика 16, инверсный выход каждого из О-триггеров 19 подсоединен к собственному информационному входу, прямой выход предыдущего О-триггера 19 ь где= 1, 2, , одггп, подсоединен к тактовому входу последующего О-триггера 19 н, при этом инверсный и прямой выходы первого О- триггера 191 являются первым и вторым выходами двоичного счетчика 16, а прямые выходы остальных одарю О-триггеров 19, где =2,3, ,одгщ+1, являются остальными од 2 в выходами двоичного счетчика 16 с порядковыми номерами начиная с третьего, причем вход сброса в нулевое состояние первого О-триггера 191 является входом установки в исходное состояние двоичного счетчика 16 и подсоединен к входам установки в единичное состояние тех О-триггеров 191,где= 2, 3,.,од 2 гп+1, для которых соответствующие Ц)-е оазряды двоичного представления числа (2- гп + 2) равны единице, и к входам сброса в нулевое состояние тех О-триггеров 19;, для которых соответствующие азуяды двоичного представления числа (2" - щ + 2) равны нулю,(одгв)-входовый элемент ИЛИ - НЕ 17 (фиг.7) блока 7 управления состоит из двухвходового элемента ИЛИ - НЕ 20 и из одев 0 при гп4 двухвходовых элементов ИЛИ 21, причем выход двухвходового элемента ИЛИ - НЕ 20 является выходом (одзв)-входового элемента ИЛИ-НЕ 17, первый вход является первым входом (одгв)-входового элемента ИЛИ - НЕ 17, а второй вход является вторым входом (од 2 гп)-входового элемента ИЛИ - НЕ 17 при в = 3 или 4 либо подсоединен к выходу первого двухвходового элемента 211 при а4, при этом первые входы (одев - 2)двухвходовых элементов ИЛИ 21 являются последующими входами Ц од 2 а)-входового элемента ИЛИ - НЕ 17 с порядковыми номерами на единицу больше порядковых номеров двухвходовых элементов ИЛИ-НЕ 17, 5 вторые входы предыдущих двухвходовых элементов ИЛИ 21 ь где = 1, 2, ., 1 од 2 в - 3, подсоединены к выходам следующих двухвходовых элементов ИЛИ 211+1, при этом второй выход последнего двухвходово го элемента 21 оя 2 щ-2 ИЛИ является последним, 1 од 2 п(, входомфод 2 п+входового элемента ИЛИ - НЕ 17.Временные диаграммы работы блока 7 управления (фиг,8) состоят из двенадцати(а, 15 б, в, г, д, е, ж, 3, и, к, л, м) диаграмм изменений сигналов во времени при работе блока 7 управления на входах и выходах блока 7 управления и его элементов.Буквенные обозначения временных ди аграмм работы блока 7 управления устройства умножения над полем ОЕ(2 ) (фиг.8) соответствуют изменениям во времени сигналам на следующих входах и выходах блока 7 управления и его элементов (фиг.5): а - 25 первый, вход блока 7 управления; б - первый выход блока 7 управления; в - выход второго двухвходового элемента ИЛИ - НЕ 132 блока 6 управления (седьмой выход блока 7 управления); г - второй вход блока 7 управ ления; д - выход двухвходового элемента ИЛИ 18 (третий выход блока 7 управления); е - прямой выход элемента 14 памяти блока 7 управления; ж - третий вход блока 7 управления; з - выход двухвходового элемен та И 15 (второй выход блока 7 управления); и - четвертый выход блока 7 управления; к - пятый выход блока 7 управления; л - входы )1 од 2 щ-входо ваго элемента ИЛ И - Н Е 17 блока 7 управления; м - выход Додетт)-вхо дового элемента ИЛИ - НЕ 17(шестой выход блока 7 управления).Временные диаграммы работы устройства над полем ОЦ 2 ) при выполнении им операции обращения элемента поля при в 453 (фиг,9) состоят из двенадцати (а, б, в, г, д, е, ж, з, и, к, л, м) диаграмм изменений сигналов во времени при выполнении устройством операции обращения элементов на входах и выходах устройства, блоке 7 50 управления и функциональных элементах устройства.Буквенные обозначения временных диаграмм работы устройства умножения над полем ОЕ(2") при выполнении им операции 55 обращения элемента поля (фиг.9) соответствует изменениям во времени сигналам на следующих входах и выходах устройства умножения над полем ОЦ 2"), его блоке 7 управления и функциональных элементах(фиг,1): а - первая группа информационных входов устройства; б - вход "Обращение" устройства; в - вход "Исходное состояние" устройства; г - тактовый вход устройства; д - первый выход блока 7 управления; е - второй выход блока 7 управления; ж - третий выход блока 7 управления; з - четвертый выход блока 7 управления; и - пятый выход блока 7 управления; к- шестой выход блока 7 управления (выход "Готов" устройства); л - седьмой выход блока 7 управления (выход "Занят" устройства); м- группа информационных выходов устройства.При описании принципа действия устройства умножения над полем ОР(2 ) (фиг,1) и его функцинальных элементов выберем в качестве параметра сигнала на выходе или входе элемента или устройства напряжение, уровни которого определяются как для "положительной логики". Таким образом, будем считать, что высокий уровень сигнала на входе или выходе функционального элемента или устройства определяет истинное значение величины приписываемой этому входу или выходу, в нулевой алгебре, а низкий уровень - ложное.Кроме того, будем считать, что единице в двоичном представлении какого-либо числа соответствует сигнал высокого уровня на соответствующем выходе или входе, а нулю - низкого уровня и, наоборот, сигнал высокого уровня на каком-либо входе или выходе соответствует единице в двоичном представлении соответствующего числа, а низкого уровня - нулю.Прежде чем приступить к описанию принципа действия устройства умножения над полем ОР(2 ) (фиг.1), опишем сначала принцип действия.Цодев)-входового элемента ИЛИ - НЕ 17 и двоичного счетчика 16 блока 7 управления устройства умножения над полем Щ 2 ) (фиг.7 и 6 соответственно), опишем принцип действия блока 7 управления устройства умножения над полем О Р(2") (фиг.5), а также принцип действия мультиплексора 41(42), регистра 2 с ЯЯ-триггерами и регистра 1 (1 г) с О-триггерами устройства умножения над полем ОР(2 ) (фиг.4, 3 и 2 соответственно).Кроме того, будем считать идентичными термин полинам и термин элемент поля.0 одзп 10-входовый элемент ИЛИ - НЕ 17 блока 7 управления над полем ОР(2 ) (фиг.7) работает следующим образом.Если на всех входах Цодоп)-входового элемента ИЛИ - НЕ 17 будут сформированы сигналы низких уровней, то на выходах всех его элементов 21 ИЛИ формируются сигналы низких уровней, а значит на оба входа двухвходового элемента ИЛИ-НЕ 20 под 1728858 125 10 15 20 25 30 35 40 45 50 55 аются сигналы низких уровней, что приводит к формированию на его выходе и, следовательно, на выходе Д 1 одгв)-входового элемента ИЛИ-НЕ 17 сигнала высокого уровня. В противном случае, если хотя бы на одном входе Д 1 одгв)-входового элемента ИЛИ - НЕ 17 будет сформирован сигнал высокого уровня, то на его выходе сформируется сигнал низкого уровня.фодгв+1)-разрядный двоичный счетчик 16 блока 7 управления устройства умножения над полем ОР(2 ) (фиг.6) работает следующим образом.В исходном состоянии двоичного счетчика 16 его первый О-триггер 191 сброшен в нулевое состояние, а состояния остальных О-триггеров 19 соответствуют двоичному представлению числа 2 ч - в + 2. Приочагаэтом на оба входа двоичного счетчика 16 подаются сигналы низких уровней. Если счетчик 16 находится не в исходном состоянии, то при подаче на вход установки в исходное состояние двоичного счетчика 16 импульсного сигнала высокого уровня первый О-триггер 191 сбросится в нулевое состояние, а остальные О-триггеры 19, где 1= 2, 3, 1 одгв+ 1, установятся в состояния, соответствующие (1 - 1)-м разрядам двоичного представления натурального числа 2)09 гщ в . 2 При этом на первом и втором выходах двоичного счетчика 16 сформируются сигналы высокого и низкого уровней соответственно, а на остальных выходах - сигналы, соответствуюшгие двоичному представлению числа 2 ц " - в+2По переднему фронту каждого импульсного сигнала высокого уровня, поступающего на счетный вход двоичного счетчика 16 при сигнале низкого уровня на его входе установки в исходное состояние, состояние счетчика 16 увеличивается на единицу, При этом если все О-триггеры 19 двоичного счетчика 16 были установлены в единичное состояние, то по переднему фронту очередного импульсного сигнала, поступающего на счетный вход двоичного счетчика 16, последний сбросится в нуль и на всех его выходах, кроме первого, сформируются сигналы низких уровней.Блок 7 управления устройства умножения (фиг.5) работает следующим образом.В исходном состоянии блока 7 управления его Додгв+1)-разрядный двоичный счетчик 16 находится в своем исходном состоянии фиг.5 и 6), О-триггер 14 сброшен в нулевое состояние, на выходе первого элемента ИЛИ - НЕ 131 сформирован сигнал высокого уровня, на первый и второй входы блока 7 управления подаются сигналы низких уровней, а на третий вход постоянно подаются тактовые импульсы (фиг,5 и 8). При этом на первом и четвертом выходах блока 7 управления сформированы сигналы высоких уровней каксигналы на выходе инвертора 12, на вход которого подан сигнал низкого уровня, и на инверсном выходе сброшенного в нуль первого О-триггера 19 двоичного счетчика 16 (фиг.5 и 6), а на остальных выходах блока 7 управления сформированы сигналы низких уровней: на втором выходе - как на выходе двухвходового элемента И 15, на первый вход которого подан сигнал низкого уровня; на шестом выходе, как на выходе Д 1 одгв)-входового элемента ИЛИ - НЕ 17, не на всех входах которого сформированы сигналы низких уровней, ибо число 2)- в + 2 не равно нулю при в2; на третьем выходе, как на выходе элемента И 18, на все входы которого подаются сигналы низких уровней; на пятом выходе, как на прямом выходе сброшенного в нуль первого О-триггера 191 П 1 одгв+1)-разрядного счетчика 16 (фиг.5 и 6), на седьмом выходе, как на выходе элемента ИЛИ - НЕ 13 г, на первый вход которого подается сигнал высокого уровня,На двухвходовых элементах ИЛИ - НЕ 13 собран Ю-триггер, поэтому в исходном состоянии блока 7 управления на выходе второго двухвходового элемента ИЛИ - НЕ 13 г, а значит и на информационном входе элемента 14 памяти, сформирован сигнал низкого уровня.При подаче сигнала высокого уровня на первый вход блока 7 управления на выходе первого элемента ИЛИ - НЕ 131 и на первом выходе блока 7 управления формируются сигналы низких уровней, а на выходе второго элемента ИЛИ - НЕ 13 г и, значит, на информационном входе О-триггера 14 и седьмом выходе блока 7 управления формируется сигнал высокого уровня, По переднему фронту очередного тактового импульса, поступающего на третий вход блока 7 управления, а значит и на тактовый вход О-триггера 14 и второй вход элемента И 15, О-триггер 14 установится в единицу, на первом входе элемента И 15 сформируется сигнал высокого уровня, и тактовые импульсы начнут формироваться на выходе элемента И 15, а значит и на втором выходе блока 7 управления и на счетном входе Ц 1 одгв+1)- разрядного двоичного счетчика 16 (фиг.5 и 8), При этом состояние Цодгв+1)-разрядного счетчика 16 будет изменяться до тех пор, пока на всех входах Ц 1 одгв)-входового элемента ИЛИ-НЕ 17 не сформируются сигналы низких уровней, При формировании сигналов низких уровней на всех входахЦод 2 а)-входового элемента ИЛИ-Н Е 17 на его выходе формируется сигнал высокого уровня, который поступает на шестой выход блока 7 управления и на второй вход элемента ИЛИ 18, на выходе которого тоже 5 формируется сигнал высокого уровня, который поступает на третий выход блока 7 управления, на вход сброса в нулевое состояние элемента памяти 14 и на второй вход второго элемента ИЛИ-НЕ 132. При 10 этом на выходе второго элемента ИЛИ-НЕ 132, а значит на седьмом выходе блока 7 управления и на информационном входе О- триггера, формируются сигналы низкого уровня, на первом входе элемента И 15 фор мируется сигнал низкого уровня и, следовательно, на выходе элемента И 15, а значит на счетном входе двоичного счетчика и на втором выходе блока 7 управления, формируется сигнал низкого уровня (фиг.5 и 8), а 20 состояние блока 7 управления может измениться только при поступлении сигнала высокого уровня на его первый или второй выходы.При подаче сигнала высокого уровня 25 на второй вход блока 7 управления при сигнале низкого уровня на его первом входе Дод 2 гп+1)-разрядный двоичный счетчик 16 устанавливается в свое исходное состояние и на выходе двухвходового элемента 30 ИЛИ 18, а значит на входе сброса в нулевое состояние О-триггера 14, на втором входевторого элемента ИЛИ-НЕ 132 и на третьем выходе блока 7 управления, формируется сигнал высокого уровня, по которому О-триггер 35 14 сбрасывается в нулевое состояние, а на выходах первого и второго элементов ИЛИН Е 131 и 132 формируются сигналы высокого и низкого уровня соответственно.Следовательно, при подаче сигнала вы сокого уровня на второй вход блока 7 управления блок 7 управления переходит в свое исходное состояние,Таким образом, после подачи на первый вход блока 7 управления импульсного сиг нала высокого уровня, при сигнале низкого уровня на его втором входе и непрерывной серией тактовых импульсов на его третьем входе, блок 7 управления отрабатываетсвой полный цикл работы, в течение которого 50 сигнал на пятом выходе блока 7 управления изменит свдй уровень с низкого на высокий2 мо 92 в 2 о 92 в п 1 + 2)раз, Следовательно, поскольку на тактовый вход двоичного счетчика 16 должно посту-,55 пить в два раза больше перепадов уровней сигналов с низкого на высокий, чем сформированных таких же перепадов на его втором выходе, то на втором выходе блока 7 управления при отработке им полного цикла работы сформируются 2(а - 2) импульсных сигналов высокого уровня.Мультиплексор 4 устройства умножения над полем 6 Е(2 в) (фиг.4) работает следующим образом.На первый и второй управляющие входы мультиплексора 4 подаются сигналы противоположных уровней, При этом на выходах мультиплексора 4 формируются сигналы, равные сигналам на одноименных входах первой группы информационных входов мультиплексора 4 при подаче на его первый управляющий вход сигнала высокого уровня, и сигналы, равные сигналам на одноименных входах второй группы информационных входов мультиплексора 4 при подаче сигнала высокого уровня на его второй управляющий вход. Мультиплексор 4 выполняет функцию управляемого ключа.Регистр 2 устройства умножения .над полем ОЕ(2 ) (фиг,3) работает следующим образом.В исходном состоянии регистра 2 все ЯЯ-триггеры 9 находятся в нулевом состоянии и на все входы регистра 2 подаются сигналы низких уровней. При этом на всех выходах регистра 2 сформированы сигналы низких уровней (регистр 2 сброшен в нулевое состояние).При подаче каких-либо сигналов на ин-. формационные входы регистра 2 при сигнале низкого уровня на его входе сброса в нулевое состояние на выходах регистра формируются сигналы, равные сигналам на одноименных информационных входах, и эти сигналы сохраняются сколь угодно длительно даже при подаче на информационные входы регистра 2 сигналов низких уровней, При подаче сигнала высокого уровня на вход сброса в нулевое состояние регистра 2 при сигналах низких уровней на всех его информационных входах, на всех выходах регистра 2 формируются сигналы низких уровней.Регистр 1 устройства умножения над полем ОЕ(2") фиг.2) работает следующим образом.В исходном состоянии регистра 1 его О-триггеры 8 находятся в нулевых состояниях, а на все входы принудительной установки регистра 1, на его тактовый вход и вход сброса в нулевое состояние подаются сигналы низких уровней. При исходном состоянии регистра 2 сигналы на его информационных входах не определяются и могут быть произвольными. При этом на всех выходах регистра 2 с О-триггерами сформированы сигналы низких уровней (регистр 2 сброшен в нулевое состояние). При подаче произвольных сигналов на входы принудительной установ45 50 55 ки регистра 1 при сигналах низких уровней на его тактовом входе и входе сброса в нулевое состояние, на выходах регистра 1 сформируются сигналы, равные сигналам на его одноименных входах принудительной установки. Значения уровней сигналов на выходах регистра 1 сохраняются и после подачи на все его входы принудительной установки сигналов низких уровней. При подаче сигнала высокого уровня на вход сброса в нулевое состояние регистра 1 при сигналах низких уровней на всех его входах принудительной установки все О-триггеры 8 сбрасываются в нулевое состояние и регистр 1 переходит в свое исходное состояние при сигнале низкого уровня на его тактовом входе.По переднему фронту импульсного сигнала высокого уровня, поступающего на тактовый вход регистра 1 при сигналах низких уровней на его входах принудительной установки и входе сброса в нулевое состояние, на выходах регистра 1 формируются сигналы, равные сигналам на его одноименных информационных входах. Сигналы на выходах регистра 1 сохраняются сколь угодно долго даже при изменении сигналов на его информационных входах при сигналах низких уровней на его входах принудитель.ной установки, тактовом входе и входе сброса в нулевое состояние.Устройство умножения над полем СЕ(2 ) работает следующим образом.В исходном состоянии устройства умножения над полем 6 Е(2") его регистры 1, регистр 2 и блок 7 управления находятся в своих исходных состояниях, на тактовый вход устройства подается непрерывная серия тактовых импульсов высокого уровня, а на остальные входы подаются сигналы низких уровней, При этом, на всех входах группы 3 блоков матричного преобразования, а значит и на всех ее выходах сформированы сигналы низких уровней. Следовательно, на всех выходах группы 5 блоков элементов И, а значит и на всех выходах блока 6 сумматора по модулю два, тоже сформированы сигналы низких уровней, которые подаются на информационные выходы устройства умножения и на информационные входы обоих регистров 11 и 12, причем на выходе "Готов" устройства сформированы сигнал низкого уровня (фиг.9).В исходном состоянии устройства умножения над полем 6 Е(2 ) (фиг.1 и 9) на первом и втором управляющих входах первого мультиплексора 41 сформированы сигналы низкого и высокого уровней соответственно, а на первом и втором управляющих входах второго мультиплексора 4 г 5 10 15 20 25 30 35 сформированы сигналы высокого и низкого уровней соответственно.Устройство умножения над полем 6 Е (фиг.1) может выполнять две операции над конечным полем полиномов 6 Е(2 ): операцию умножения двух элементов поля и операцию определения обратного элемента для ненулевого элемента поля.При выполнении устройством .операции умножения двух элементов поля 6 Е(2 ) на входы первой и второй групп информационных входов устройства умножения над полем 6 Е(2 ) подаются сигналы, соответствующие коэффициентам первого и второго полиномов-сомножителей соответственно. При этом на выходах первого и второго регистров 11 и 12 (фиг.1 и 2) формируются сигналы, равные сигналам на установочных входах, а значит и на входах первой и второй групп информационных входов устройства соответственно, Сигналы с выходов первого регистра 11 с О-триггерами, преобразуясь в группе 3 блоков матричного преобразования, подаются на входы первой группы информационных входов группы 5 блоков элементов И, на входы второй группы информационных входов которой поступают через второй мультиплексор 42 сигналы с выходов второго регистра 12, При этом на выходах блока б сумматоров по модулю два и на информационных выходах устройства умножения над полем 6 Е(2 ), формируются сигналы, соответствующие коэффициентам полинома-произведения.Так, исходное состояние устройства умножения над полем 6 Е(2 ), соответствует операции умножения нулей поля 6 Е(2"). Для выполнения устройством умножения над полем 6 Е(2 ) операции определения обратного элемента для ненулевого элемента поля 6 Е(2 ) необходимо подать на входы первой группы информационных входов устройства сигналы, соответствующие коэффициентам обращаемого полинома, и ри сигналах низких уровней на всех входах второй группы информационных входов устройства, на вход "Обращение" устройства подать импульсный сигнал высокого уровня длительностью достаточной для передачи сигналов с входов первой группы информационных входов мультиплексора 41 на его выходы, а затем на все входы первой группы информационных входов устройства снова подать сигналы низких уровней (фиг,1 и 9). При этом на выходах обоих регистров 11 и 12 и на выходах регистра 2 формируются сигналы, соответствующие коэффициентам обращаемого полинома, на выходе "Занят" устройства формируется сигнал высокого10 15 20 25 мого полинома 30 35 45 50 55 уровня, на выходах блока 6 сумматоров по модулю два, а значит и на информационных входах обоих регистров 11 и 12, формируются сигналы, соответствующие коэффициентам полинома, равного квадрату обращаемого полинома, а блок 7 управления начинает работу в соответствии с логикой его работы (фиг.1 - 9). По переднему фронту первого тактового сигнала, формирующемуся на втором выходе блока 7 управления, на четвертом и пятом выходах блока 7 управления, а значит и на первом и втором управляющих входах второго мультиплексора 42,формируются сиГналы низкОГО и Высокого уровней соответственно. При этом регистры 11 и 12 устанавливаются в состояния, соответствующие сигналам на выходах блока 6 сумматоров по модулю два, а значит коэффициентам полинома, равного квадрату обращаемого элемента, а на входы второй группы входов группы 5 блоков элементов И подаются через второй мультиплексор 42 сигналы с выходов регистра 2, соответствующие коэффициентам обращаеСледовательно, на протяжении первого тактового импульса, формирующегося на втором выходе блока 7 управления, на выходах блока 6 сумматоров по модулю два формируются сигналы, соответствующие кубу обращаемого полинома.По переднему фронту второго тактового импульсного сигнала, формирующегося на втором выходе блока 7 управления, на четвертом и на пятом выходах блока 7 управления формируются сигналы высокого и низкого уровней соответственно. При этом регистры 11 и 12 устанавливаются в состояния, соответствующие кубу обращаемого полинома, а на входы второй группы входов группы 5 блоков элементов И подаются сигналы с второго регистра 12. Следовательно, на протяжении второго тактового импульса, формирующегося на втором выходе блока 7 управления, на выходах блока 6 сумматоров по модулю два, а значит и на информационных выходах устройства, формируются сигналы, соответствующие коэффициентам полинома, равного шестой степени обращаемого полинома.Аналогично в течение действия каждого нечетного по порядку счета тактового импульса, формирующегося на втором выходе блока 7 управления, на информационных выходах устройства формируются сигналы, пропорциональные коэффициентам полинома, равного произведению обращаемого полинома на полином, равный соответствующей четной степени обращаемого полинома, сформированной в течение предыдущего четного по порядку счета тактового сигнала на втором выходе блока 7управления, а в течение действия следующего четного по порядку счета тактовогоимпульса, формирующегося на втором выходе блока 7 управления, на информационных выходах устройства формируютсясигналы, соответствующие коэффициентамполионома, равного квадрату полинома, соответствующего сигналам, сформированным на информационных выходахустройства в течение действия предыдущего нечетного по порядку счета тактовогосигнала на втором выходе блока 7 управления.При полном цикле работы блока 7 управления на его втором выходе сформируются 2(гп - 2) тактовых импульсных сигналоввысокого уровня. Другими словами, при отработке блоком 7 управления полного циклаработы на его втором выходе формируютсяа - 2 пар тактовых сигналов.При этом в течение действия последнего в полном цикле работы (2 а)-го тактового сигнала на втором выходе блока 7управления на его третьем, четвертом и шестом выходах и, значит, на выходе "Готов"устройства, формируются сигналы высоких уровней, причем на втором и седьмомвыходах блока 7 управления после формирования сигнала высокого уровня на еготретьем выходе формируются сигналынизкого уровня, которые не изменяются доподачи, импульсного сИгнала высокогоуровня на вход "Обращение" устройства,Следовательно, при формировании сигнала высокого уровня на выходе Готов" устройства на его информационных выходахбудут сформированы сигналы, соответствующие коэффициентам полинома, равного(2 - 2)-й степени обращаемого полинома,ибо после занесения коэффициентов обращаемого полинома в устройство на его выходах сразу же были сформированысигналы, соответствующие коэффициентамполинома, равного квадрату обращаемогополинома.Докажем это утверждение методом математической индукции, Обозначим буквойВ значение обращаемого полинома, а .буквой С - значение полинома, соответствующего сигналам, сформированным наинформационных выходах устройства послеотработки блоком 7 управления полногоцикла работы.При в 1= 3 число к 1= 2 в - 4 = 2 (тактовыхимпульсов) и С 1 = (В 2 В)2 = В 6 = В . ВПри в 2=4 с 2=2 4-,4=4 и С 2=(С 1 В) =