Изобретение относится к вычислительной технике и предназначено для использования в качестве логического модуля при синтезе дискретных устройств, а также в качестве блока- преобразователя при построении универсальных логических устройств.
Цель изобретения расширение функциональных возможностей за счет реализации вычисления выражений вида А В (k 1 , I ).
На чертеже приведена схема устройства для случая го 3 и вычисления выражения А В,
Устройство содержит сумматоры I по модулю два, коммутаторы 2, группы 3 двухвходовых элементов И 4, группы 5 т-входовых элементов И 6, управляюпще входы 7, информационные входы 8, вхоры 9 настройки, выходы 10, коммутационное поле 1 задания логических функций.
Устройство работает следующим образом.
Работа устройства основана на т
что в поле Галуа GF (2 ) можно однвременно с помощью комбинационных схем вьтолнять операции возведения в степень и умножение двух элемент
Известно, что поле Галуа GF(2 содержит 2 - 1 различных элементо которые образуют циклический код. Среди них m элементов являются линейно независимыми. Путем линейной комбинации этих элементов можно получить остальные. Элементы поля можно получить с помощью неприводимых полиномов га-й степени. Так при m 3 таким полиномом является X + X + 1, а линейно независимыми элементами поля при m 3 являются а° lOOj а 100 и a 001 .
С помощью этих элементов любой элемент в поле Галуа GF(2) можно представить в виде А + А,.а + f а другой элемент отличаетс от элемента А значениями коэффициентов АО, А, и AJ, т.е. элемент В + В, а + В.а , причем коэфициенты Ар 5 А,, А, В , В и В в двоичной системе счисления принимают значения О или 1.
Если элемент а является корнем полинома X + X + , получают а- + а , отсюда а а ПО; а а а а + а
А Б -f А
А„В,
,В, , -f А, В,; -ь А,В« -f А, В., -f А,В, + ,
5
а а + а
110; а
а° -i- а I 1 1 ; а а
3
а
.Tgi а- +
а а
--а + а
+ а2
- а 101; а
- а а а°1
-,
а
,3
а
5
+ а а
8 о с
а а а а и т. д .
Умножение двух элементов поля вьтолняется путем прямого умножения элементов,, представленных в виде полинома: А В ( + А.а + + } Чв„а + В, а В,,аЧ + А,а°В, а ,а + 4- А,а В°„а° + А,а В, + А,, + + + , а А.,В,а .
Учитывая, что а 100.- единичный элемент, а а а , далее а а° + а и а а + а, имеем А.+ В а°( А, -v В, + А,В,) + + а (А,В, + А,В, + А,В, + , +- + ) + -f А,В, + A,,Bj),,
Обозначив коэффициенты при а, а и а соответственно через С,,, С
+ А,В, + А,В, ;
С, АоВ. С А„В, + А,В, + А, В, + А,
С„ А.В., - А,В, + А,
ч- А,В, +
0
,,
При А В из выражений () получают выражения для возведения элемента поля GF(2 ) в квадрате
5.
5
+ А,А, + А,А, Л„ С, А,А, + А,А + А, А
с:. А,А,
+ А,А,,
А, + А,;
А„А, + А,А, ,А, .
+ А.А.
А,А
Л
Путем итерации получают выражения Д.ПЯ возведения элемента А в куб, так как А А А :
С А„ + А, + А, + А,
С, , + А„А, + А, ;
С./ А„А, + А,
и та.к далее вплоть до шестой степени.
Приняв выражения для умножения двух элемектов поля и вoзвeдeE ия в
степень как исходные, получают выражения для одновременного возведения в степень к умножения двух элементов, которые аппаратно реализуются в устройстве при помощи групп 3 и 5
-элементов И, коммутационного поля и сумматора 1 по модулю два:
ВА, ВА„
ВА
и так далее, вплоть до 6 степени, Например, пусть даны элементы В а 110иА а 111. Необходимо вычислить ВА . Имеем В„ 1; В, I; В, 0; А 1; А, и
I . Подставляя эти коэффициенты
3
А,
в выражения для вычисления ВА , полчим ВА- 0; ВА 0; BA-i 1. В реОi и
зультате получаем элемент а 001;
так как (А) а (а ) а (а)
к а а и а а а .
В устройстве выбор одного из выржений В А проводится при помощи комутаторов 2 путем подачи соответст- вующего кода на входы задания показателя степени 7 устройства.
Формула изобретени
Устройство для умножения и возведения в степень двух элементов в поле Галуа GF(2, содержащее 2 - 1 групп из m cyMNtaTopoB по модулю два m коммутаторов и m групп из m двух- входовых элементов И, причем выход i-ro сумматора по модулю два (i 1, m) j-й группы (j 1, 2 - 1) соединен с j-м информационным входо
.В, В
2 1
S
А.А
4 +
,
А, В.
А,В + + А, В, А А В
,
А, + А
А, В, А В,
АЛ
+ +
АЛ
л
з -го коммутатора, выход которого соединен с i-t-j выходом устройстваJ i-й вход задания показателя степени устройства соединен с i-ми управляющими входами каждого коммутатора, отличающееся тем. что, с
счет реализации вы- выражений вида А В (k
целью расширения функциональных
возможностей за
числения
,2 - ), в него введены m групп из m m-входовых элементов И и коммутационное поле задания функций, причем 1-й информационнь й вход устройства (i 1S т) соединен с первым входом каждого двухвходового элемента И i-й группы и i-M входом каждого т-входового элемента К I,,, (i-I) и (i + 1).,. та групп, i-й вход настройки устройства соединен с вторыми входами i-x двухвходовых элементов И группы и j-м входом т-входового элемента И j-и группы (j i, m) входы каждого двухвходовых элементов И каждой группы и выходы каждого т-входового элемента И каждой группы соединены через коммутационное поле задания функций с входами сумматоров групп.
fO
Изобретение относится к вычислительной технике и предназначено для использования в качестве логического модуля при синтезе дискретных уст- . ройств. Целью изобретения является расширение его функциональных возможностей за счет реализации вычисления выражений вида А В (1с t, 2 ), Устройство содержит входные и выходные шины, элементы И и сумматоры по модулю два. Работа устройства основана на том, что в поле Галуа GF (2) можно одновременно с помощью комбинационных схем вьтол.- нять операции возведения в сте- . пень и умножения двух элементов . 1 ил, с (О to со О5 ел м
Редактор Н. Гунько
Составитель 0„ Мороз
Техред М.Ходзнтш Корректор В .Бутяга
Заказ 3091/51Тир.аж 671Подписное
ВНИИГШ Государственного комитета СССР
по делам изобретений и открьзтий 113035, Москва, Ж-35, Раушская наб., д, 4/5
Производственно-полиграфг-гческое предприятиер г. Ужгород, ул. Проектная, А
| Патент США 3805037, кл | |||
| Приспособление для точного наложения листов бумаги при снятии оттисков | 1922 |
|
SU6A1 |
| Фараджев Р.Г | |||
| Линейные последова- твльностные машины.-М.: Советское радио, 1975. | |||
