Устройство для полиномиального разложения логических функций Советский патент 1988 года по МПК G06F5/00 G06F7/00 

СО 00

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

Цель изобретения - расширение функциональных возможностей устройства для полиномиального разложения логических функций за счет выполнения конъюнктивно-полиномиального разложения по k переменным, где k О, ..., п.

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

Устройство содержит дешифратор 1, два элемента ИЛИ 2 и 2, четьфё элемента И 3,-34 первого яруса, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4,-44; первой группы, четьфе элемента И 5,-,54 второй группы, четыре элемента СЛОКЖНИЕ ПО МОДУЛЮ ДВА 6,-64 второй группы, четыре элемента И третьего яруса, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 8,-84. третьей группы, два управляющих входа 9,.-.и 9, восемь информационных выходов 10,-IOg и восемь информационных входов Ib-llg.

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

На i-й информационный вход (i 1, .,., 2 ) подается значение Vj.; преобразуемой логической функции п переменных f f(x, ,.,, х,) на (2 -i)-M наборе, на управляющие входы сигналы настройки U , ..., Ug, значения которых принадлежат множеству {0,1. Сигналы и,, ..., HS опреS .

деляют количество k Ug

j

переменных х,, .,,, Хц, по которым разлагается функция f(x., .,,, х„). При k О разложения не происходит

и на выходах устройства сигналы совпадают с соответствующими коэффициентами СДНФ, подаваемыми на его входы. При k л происходит преобразование СДНФ в полином Жегалкина (сигналы на выходах устройства совпадают с соответствующими коэффициентами полинома). Если , ;.,, п-1, осуществляется коньюнктивно-полиномиальное разложение функции f(x,,, х), которое имеет вид

л1

f(x, ,.,, х) © KjCfgCx,

- f

п)

(1)

5

0

5

0

5

0

где

К( (1 1, ..., 2) - множество всевозможных попарно не тождественных конъюнкций ранга г (, ..,, k) переменных х,, ,,,, х (коэффициент К 1, т.е. является конъюнкцией ран- га ).

На выходах устройства формируются таблицы истинности (двоичные номера) логических функций h-k переменных

причем значение на t-м наборе переменных х, , ..., х„ (t 0, .,,, , - 1) реализуется на 2 - - (1-1) - выходе устройства,

Для устройства, приведенного на чертеже, возможны п 3 конъюнктивно- полиномиальных разложения (при подаче на управлякядие входы 9f и 94 сигна- лов соответственно U j (k 0) разложения не будет).

Если k 1 (и, 0; Ua 1),. то f(x,, х, х,) Cp,(Xi,x,)0x,ifi(x4, Xj),

Если (U«.1, ), то f(x,, х, х,) с. (x)ffiXiV(x,)x,9,(x,)@ @х,х((х,),

Если (U, 1, 0 1), то f(x,,

О и О

X J, Х) С,®Х,(

9i,, в(.4@

©x,etj.@x,,X2 et,©x, eig, где t;efO,1} и i 1, ,,., 8, В качестве примера в таблице представлены значения сигналов на входах и выходах устройства при разложении логической.функции f (х,,

Xj, Х) Х,Х ,V X, X,V J.

Как следуе т из таблицы, f(x, , Xj,

Xj) X,XyV x, X V (x i V X:j)® ®X,(,) 1 ® XjX, (STx.X, © © X, XiX 1 ® , ® X @ X,X, © W X, X j .

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

Исходным для нахождения двоичных

номеров функций tfl(x ,

1 1 ,

2 (выражение (1) )

X,,),

является вектор значений разлагаемой

логической функции f(x|, . х) :

W.

(уо ..., У) У. У,

Улп) . Далее формируется по следов атель

ность векторов,, , .. , И ( , . .. , п) , 5

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

ч,

JZinn-t у

J-

J-

..,

1,

Значение функции Cf, (х , на t-M наборе переменных х ,

XH:I

xnd 1,

t о.

-1) совпадает с (1-1) +

. t

+ t + lj-й компонентной вектора W.

Компоненты вектор W, , , ..., n, формируются на выходе k-й группы элементов СЛОЖЕНИЕ НА МОДУЛЮ ДВА. Дешифратор и п-1 элемент ИЛИ обеспе- 25 чивают транзитную передачу компонент вектора W на соответствующие выходы устройства при подаче на его управляющие входы двоичных сигналов

15 ройстм формируются компоненты вектора У-,(У„), которые являются коэффициентами полинома Жегалкина.

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

Формула изобретения

Устройство для полиномиального разложения логических функций, содержащее п групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА по элементов в кажи

л

Ug, код которых равен k.

30

2

дои (п - количество двоичных переменных разлагаемой логической функ ции), отличающееся тем, что, с целью расширения функциональных возможностей за счет выполнения конъюнктивно-полиномиальных разложеk О на первом вьгходе дешифратора 1 ° переменных (,1, ... п) содержит п групп элементов И по 2

где k

b-iДля рассматриваемого примера при эде дешифратора 1 (на втором

присутствует сигнал и третьем выходах - сигналы , который поступает на входы элементов И 3,-3 первой группы и через элементы ИЛИ 2, и 2 2 - на входы элементов И 5i - 54 и 7, - 74 второй и третьей групп соответственно. При этом происходит передача коэффициентов СДНФ разлагаемой функции на выходы 114 llg устройства без преобразований.

Если k 1, сигнал 1 присутствует на втором выходе дешифратора 1 (на первом и третьем выходах - сигналы О). При этом на входы элементов И (}. первой группы подается сигнал О, что обеспечивает формирование на выходе элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4/,-44 компонент вектора vf, , которые без изменений проходят ла выходы 11i-11g устройства (на пер- , вые входы элементов И 5 -. и 7| -74 второй и третьей групп nocvynaeT

40

45

50

55

элементов в каждой, п-1 элемент ИЛИ и дешифратор, г-й вход которого (г 1, 2,...,s; S Jlogj (n+1) ) сд единены с г-м управляющим входом, а первый выход соединен с первыми входами элементов И первой группы и первым входом пер- , вого элемента ИЛИ, второй вход которого соединен с вторым выходом дешиф- ратора, а выход соединен с первыми , входами элементов И второй группы, j-й выход дешифратора (j 3, 4, ..., п) соединен с первым входом (j-l)-ro элемента ИЛИ, выход которого соединен с первыми входами элементов И j-й группы, а второй вход соединен С - выходом (j-2)-ro элемента ИЛИ, вьпсод . i-ro элемента И (i 1, 2, ...,) р-й группы (р 1, 2, ..., п) соединен с первым входом i-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы, второй вход которого соединен с вторым входом i-ro элемента И р-й

1441380

сигнал 2

(

и 2).

Если k

) , 5 ствует

на

с выходов элементов ИЛИ

2, сигнал 1 присут- третьем выходе дешифра

:I

25 ы тора 1 (на первом и втором выходах - сигналы О), При этом сформированный на выходе логидеских элементов второй группы вектор W проходит транзитом

10 на выходе 11,-llg устройства.

Если k 3 (k п) на всех выходах дешифратора присутствуют сигналы - О, которые поступают на входы элементов И всех групп. На выходах уст15 ройстм формируются компоненты вектора У-,(У„), которые являются коэффициентами полинома Жегалкина.

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

Формула изобретения

Устройство для полиномиального разложения логических функций, содержащее п групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА по элементов в каж30

держит п групп элементов И по 2

0

5

0

5

элементов в каждой, п-1 элемент ИЛИ и дешифратор, г-й вход которого (г 1, 2,...,s; S Jlogj (n+1) ) сд единены с г-м управляющим входом, а первый выход соединен с первыми входами элементов И первой группы и первым входом пер- , вого элемента ИЛИ, второй вход которого соединен с вторым выходом дешиф- ратора, а выход соединен с первыми , входами элементов И второй группы, j-й выход дешифратора (j 3, 4, ..., п) соединен с первым входом (j-l)-ro элемента ИЛИ, выход которого соединен с первыми входами элементов И j-й группы, а второй вход соединен С - выходом (j-2)-ro элемента ИЛИ, вьпсод . i-ro элемента И (i 1, 2, ...,) р-й группы (р 1, 2, ..., п) соединен с первым входом i-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы, второй вход которого соединен с вторым входом i-ro элемента И р-й

группы, выход (.2 + v)-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА q-й группы (z , V 1, 2, ..,, Z, q 1, 2, ..., n-1) соединен с вторым входом v-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (я+1)-й группы, третий вход которого соединен с выходом v-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА q-ft группы, выход w -f-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА q-й группы ff l- w 1 7 7

L W- ||/.у «t 9

g 1,2, .. . , n - 2) соединен с вторым входом h-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (h (2w-1)f/2) п-й группы, третий вход которого соедий

14А13806

ней с выходом (wf-l)-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА g-й группы, второй и третий входы (t + 1)-го

элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы (t 2 -d, , 1 1, 2, ..,, d) соединены соответственно с (2 t+d+l)-M и (2 t+l)-M информационными входами устройства, выходы

d-i-x элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы соединены с (d « + G. ) входами (С О, .,., 2), 2 -и информационный вход устройства соединен с 2 -выводом устройства.

Изобретение относится к области вычислительной техники и предназначено для использования в высокопроизводительных ЭВМ для аппаратурной реализации системы команд, а также .для построения специализированных процессоров. Цель изобретения - расширение функциональных возможностей устройства для :полиномиального разложения логических функций п переменных за счет выполнения /конъюнктивно- полиномиальных разложений по k переменным (k ,0, 1, ..., п) . Поставленная цель достигается тем, что устройство для полиномиального разложения логических функций п переменных содержит п групп элементов .СЛОЖЕНИЕ ЦО МОДУЛЮ ДВА, по элементов в каждой, п групп элементов И по , элементов в каждой, п-1 элемент ИЛИ и дешифратор на s входов, где s . log-(n + 1) f. Устройство имеет 2 информационных входов, & управляющих входов и 2 выходов. На входы устройства подается значение преобразуемой логической функции переменных, а на входе устройства,реализуется ,п кpJl ъloнктивнo-пoлинoм иaльныx разложений, определяемых управляющими входами устройства. 1 ил., 1 табл. а (Л

и, и

9, 9 10, 10 10 10 10 10б Ш lOg 11, 11, 11, 11 llg. 11б11т 11j

У,