Устройство для реализации переключательных функций в поле галуа gf 2.
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Номер патента: 1234861
Автор: Никитюк
Текст
(50 4 О 06 Г 7/00 Й НОМИТЕТ СС РЕТЕНИЙ И ОТНРЫТОСУДАРСТВЕНН ПО ДЕЛАМ ИЗОБ фи ЯР НИЕ ОПИС ИЗОБРЕТЕНИ 1 ЛЬСТ в поле Галуа ОУдискретных устетения - повьипениставленная цельто устройство со(21) 3739353/24-24(71) Объединенный институт ядерныхисследований(2 ) ьных функции при синтезе в. Цель изоб одействия. П гается тем,рой быс ост енного выния в степень и умножения двух поле Галуа, схемы умно Галуа ОР (2), регистр Сокращение времени вып раций в устройстве дос счет схем для одноврем дения в степень и умно элементов в поле Галуа торые позволяют выполи ч. 11, Р 18, р. 421. видетельство СССРО Об Р 7/00.О ДЛЯ РЕАЛИЗАЦИИ ПЕРЕУНКЦИЙ В ПОЛЕ ГАЛУА ие относится к областитехники и может бьггь для реализации переклюре ву роист хемах за такое ж и в я умножени 2 табл.(57) Пзобретевычислительноиспользовано ржит схемы для однов лнения операций возв элементов в жения в поле ы и коммутато олнения опетигается за енного возвежения двух ОГ (2 ), коять эти операУстройство относится к области вычислительной техники и может быть использовано для реализации переключательных Функций в поле ГалуаСР (2 ) при синтезе дискретныхустройств.Цель изобретения - увеличениебыстродействия.На фиг. 1 приведена структурнаяблок-схема предлагаемого устройствадля случая =3, т.е. когда Х==(Хэ, Х, Х); на Фиг, 2 - структурная схема ячейки устройства, с помощью которой можно реализоватьвсе булевы функции двух переменных,т.е. вычисляется полином А, Х+А, Х +г23устройство содержит информационные входы 1 переменных, коммутатор2, настроечные входы 3, управляющиевходы 4, регистры 5-7 первой группы,регистр 8 второй группы, регистры9-14 первой группы, регистр 15 второй группы, блоки 16-18 умноженияв поле Галуа, блоки 19 и 20-24 дляодновременного возведения в степеньи умножения двух элементов в полеГалуа, сумматоры 25 и 26, выходнуюмагистраль 27. Ячейка состоит из элементов И 28-36, двухразрядных регистров 37-39, сумматоров 40-45 по модулю два, выходов 46 и 47 ячейки,входа 48 установки регистров в состояее 0 . С помощью этой ячейкигре али зуют ся элеме нты поля ЬР ( 2 )а =10=1; а =01; а-=11" 0=00,Злементь этого ноля могут бытьполучены с помощью неприводимогогмногочлена Х Х+1, полагая что ар.являетсл его корнем, Тогда а =-а +апричем а"=10= - единичный элемент.Два различных элемента А и Б в поле, 2ОРэ (2 ) представимы какр оАо а А иВогде коэффициенты А, А В , Вмогут принимать значения 0 или 1,А эБ = ( а А + а А ) ( а Б + а В ) .Аналитические выражения для параллельного умножения двух .элементовв поле Галуа:Ао Вр А Ва )АВ, +А, В +АВ,а),Выражения для возведения элемента А в квадрат;А +А, :с а;А .а )Одновременное возведение в квадэат и умножение двух элементов: ВА" =(а В+а В,(Аа+А,а );АрВ+А, В+А,В с ар);,Рассмотрим пример работы ячейки.5 Пусть К=а =01; Аг, =а =10; Аа=а =11; А . =а =10, Коэффициенты настройки запоминаются в регистрах37-39, С помощью элементов И 32-36и сумма;,"оров 42 и 43 по модулю двавыполняются параллельное умножениекоэффициента А =а на переменнуюгХ=а, в результате этого на выходахсумматоров 42 и 43 получается произведение15 а а =а =а =10С помощью логических элементовИ 28-31 и сумматоров 40 и 4 выполняется одновременное умножение коэффиЦиента Аг и возвеДеие в кваДРатпеременной Х в соответствии сА, Х =а а =аг о г гДалее на сумматорах 44 и 45 по модулю два выполняется сложение. Нижеприводятся аналитические выражениядля вычисления членов2, 35. 5, 6А Х; А 5 ХАэХ; А .Х; АХ,Операции выполняются над элементамиполя А и Х, которые образованы сТаблица.2 Выход Входные переменныеХ 000 = 0 000 = 0 0 = 000 ХХ Х Х Х,Х Х ХХ Х,Х,Х, Х Х,Хг а = 100 а = 010 000 = 0 000 = 0 а = 001 000 = О а=110 000 = 0 а= 011 Ххгпяг а = 111 100 = а =1 огх,х,х а = 01 000 = 0 2 -1 6АХ=А Х АОХ,Х +А Х,Х,+А Х;,Х, + +А ХАХ, =АХ+А г Х, Хг+А ХХ, +Аг ХХ, + +Ах ХгХо Хг Аг Хо Хг Устройство работает следующим образом. 1 ОДопустим, что необходимо настроить модуль на выполнение следующей булевой функции трех геременных:х(Х Х, Х ) Х ХХ ХХХДля вычисления коэффициентов на стройки в поле Галуа СР (2 ) переключательную функцию т переменных можно представить в виде полинома 2 -1 степени. При ш=2 и ш=З функции двух и трех переменных можно пред ставить в видех(Х)=Аг Х+А Х +Аз;+А 76 Х +А 7,где Аг Аг, Агз и Х в выражении для 1,(х) - элементы по ля Галуа СГ (2 ), причем Х=Х , Х) в выражении для х, (х) А 7,Аиг Азз А. 4, А, А 76, А 7 г элементы поля Гппп ДХ (22, пРммпм Х=1 Х , Х Хп где Х, Х Хг булевы переменные, КоэфФициенты А, вычисляются из вы- ражения 61 4ется с помощью сумматора 25, выходыкоторого подключены к шинам выходноймагистрали 27,Таким образом, ячейки устройствапараллельно реализуют булеву функциюГ(Х)=Хв+Х,Х,+Х Х при заданных коэффициентах настройки. Для вычислениякоэффициентов настройки реализующейфункции трех переменных, т.е. переключательной функции Г(Х)=А Х+35 где С - значения функции на выходе. Для вычисления коэффициентов Аг А и Аг использУетсЯ табл. 1 . Таблица11=ХХ,00 = 0 55Значение Г(Х)=ха+Хга при Х=а и Х=а равно единичному элементу. Суммирование членов в формуле выполняЗдесь а -а - элементы поля ГалуаО 6ЭСт (2 ), и каждому элементу поля поставлена в соответствие булева функция трех переменных Х , Х Хг,В соответствии с табл. 2 коэффиии2 6 енты настройки равны а, а, а, .а 1а , а . Выражение для 1:(х) принимает вид+ао. При подстановке а =111=ХХхг получж 1(х)=100=а . При остальных а это равенство равно нулю.При вычисленных коэффициентах настройки устройство реализует все булевы функции трех переменных, общее число которых равно 2 =25 б, Для по 7строения модуля на большое число переменных в схему необходимо параллельно подключать соответствующее число логических ячеек в поле Галуа, Так, например, при оп=4 необходимо4 добавить ячейку поля Галуа СГ (2 ).Сокращение времени выполнения операций в устройстве достигается1234861 У 3 ию 71 Подписное жгород, ул. Проект благодаря блокам для одновременноговозведения в степень и умножениядвух элементов в поле Галуа ОР (2 ),которые позволяют выполнять этиоперации за такое же время, как ив схемах для умножения двух элементов,формула изобретения Устройство для реализации переключательных функций в поле Галуа ОР (2 ), содержащее ш логических ячеек, каждая из которых содержит сумматор по модулю два и п 1 блоков умножения в поле Галуа порядка п 1, выходы которых в каждой ячейке, начиная со второй, подключены к первым входам соответствующих сумматоров, выходы которых подключены к выходной шине устройства, первые входы блоков умножения в поле Галуа порядка п 1 подключены к информационным входам переменных устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, в каждую логическую ячейку, начиная со второй, введены по 2 -3 блоков одновременногойвозведения в степень, начиная со 111 ИИПИ Заказ 2987/52 1 роизв.-полигр, пр-ти второй до (2-2)-й степени, и умножения двух элементов в поле Галуапорядка ш, первые входы которых сое 5 динены с информационными входами пеИ 1ременных устройства, по 2 -2 регист.ров первой группы и одному региструвторой группы, коммутатор, первыевходы которого являются настроечными 1 О входами устройства вторые - управляющими, при этом входы регистровпервой и второй групп подключены квыходам коммутатора, выход первогорегистра первой группы каждой ячей ки подключен к второму входу блокаумножения в поле Галуа порядка шданной ячейки, выход -го регистрапервой группы (1=1, 2, 3 2 -2)в каждой )-й ячейке (1=2, , ш) 20 подключен к второму входу блока одновременного возведения в степеньи умножения двух элементов в полеГалуа порядка ш 1-й степени -йячейки, при этом выходы блоков од новременного возведения в степеньи умножения двух элементов в нолеГалуа порядка ш,)-й ячейки, а также,выходы регистров второй группы,1-й ячейки подключены к входам сумЭо матора 1-й ячейки.
СмотретьЗаявка
3739353, 08.05.1984
ОБЪЕДИНЕННЫЙ ИНСТИТУТ ЯДЕРНЫХ ИССЛЕДОВАНИЙ
НИКИТЮК НИКОЛАЙ МИХАЙЛОВИЧ
МПК / Метки
МПК: G06F 7/00
Метки: галуа, переключательных, поле, реализации, функций
Опубликовано: 30.05.1986
Код ссылки
<a href="https://patents.su/4-1234861-ustrojjstvo-dlya-realizacii-pereklyuchatelnykh-funkcijj-v-pole-galua-gf-2.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для реализации переключательных функций в поле галуа gf 2.</a>
Предыдущий патент: Мозаичное печатающее устройство
Следующий патент: Устройство для регистрации времени работы оборудования
Случайный патент: Устройство программного опро-ca телеметрических каналов