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

 

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

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

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

РЕСПУ БЛИН (5f) 4 Г 06 F 5/00, 7/00

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4263399/24-24 (22) 16.06.87 (46) 30.11.88. Бюл. Н- 44 (72) Л.Б.Авгуль, В.А.Мищенко и В.П.Супрун (53) 681.3(088.8) (56) Авторское свидетельство СССР

В 781822. кл. С 06 F 15/31. 1978.

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

1 » 1124281, кл. Г 06 F 5/00, 1983, (54) УСТРОЙСТВО ДЛЯ ПОЛИНОМИАЛЬНОГО

РАЗЛОЖЕНИЯ ЛОПИЕСКИХ ФУНКЦИЙ (57) Изобретение относится к области вычислительной техники и предназначено для использования в высокопро:изводительных ЭВМ для аппаратурной реализации системы команд, а также для построения специализированных процессоров. Цель изобретения — расширение функциональных возможностей устройства для:полиномиального раз„.SU„„1441380 А 1 ложения логических функций и переменных за счет выполнения конъюнктивнополиномиальных разложений no k переменным (k = i0, 1, ..., и). Поставленная цель достигается тем, что устройство для полиномиального разложения логических функций и переменных содержит и групп элементов, СЛОЖЕНИЕ

ПО МОДУЛЮ ДВА, по ? . элементов в

h -1 каждой, и групп элементов И по ? элементов в каждой, и-1 элемент ИЛИ и дешифратор на я входов, где з =

=)l.og -(п + 1) j. Устройство имеет 2 информационных входов, в управляющих входов и 2" выходов. На входы устройства подается значение преобразу- 3 емой логической функции переменных, рр а на входе устройства,реализуется %ФФ ,п конъюнктивно-полиномиальных разложений, определяемых управляющими входами устройства. 1 ил., 1 табл, Д

1441380

45 переменных х,, ..., х „, по которым разлагается функция f (x ..., x ) .

При k = 0 разложения не происходит и на выходах устройства сигналы совпадают с соответствующими коэффициентами СДНФ, подаваемыми на его входы. При k = n происходит преобразование СДНФ в полином Жегалкина

«55 (сигналы на выходах устройства совпадают с соответствующими коэффициентами полинома). Если k=1, :... n-1, осуществляется конъюнктивно-полиномиИзобретение относится к области вычислительной техники и предназначено для использования в высокопроизводительных ЭВМ для аппаратурной реализации системы команд, а также для построения специализированных процессоров, Пель изобретения — расширение функциональных возможностей устройст- 10 ва для полиномиального разложения логических функций эа счет выполнения конъюнк тив но-пол иномиально го ра зложеиия по k переменным, где k = О, ° ° ° ю» и ° 15 Йа чертеже представлена схема устройства для полиномиального разложения логических функций для п=3.

Устройство содержит дешифратор 1, два элемента ИЛИ 2 и 2, четыре элемента И 3, -3 первого яруса, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА

4,-44 первой группы, четыре элемента

И 5, вЂ,54 второй группы, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6 -64 вто. 25 рой группы, четыре элемента И 7,-7 третьего яруса, четыре элемента

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 8 -84 третьей группы, два управляющих входа 9,.-.и

9, восемь информационных входов

10,-108 и восемь информационных входов 11< -11а .

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

Ha i-й информационный вход (i

l3

1, ..., 2 ) подается значение у и; преобразуемой логической функции и переменных f = f(x<, ° ° °, x„) на (2 -i)-м наборе, на управляющие 40 входы сигналы настройки U1 . ...., U> значения которых принадлежат множеству (0,11. Сигналы U<, ..., Пз опре5 деляют количество k=, Б

j=l альное разложение функции f(x<, х ), которое имеет вид

I к

f(xq ° ° °, хь) Я KC VC(хк+, C=t хр) 1 к где (Kc) (1 = 1, ..., 2 ) — множество всевозможных попарно не тождественных конъюнкций ранга r (r=O, ..., k} переменных х, ..., х „ (коэффициент К 1, т. е. является конъюнкцией ранга r=O), На выходах устройства формируются таблицы истинности (двоичные номера) логических функций h-k переменных

2 (х...,х),1=1,...,2 - C к+< причем значение д на й-м наборе переменных хк ..., х,„ (t = О, ° ° у

2" " — 1) реализуется на (2

2 (1-1) — t) -м выходе устройства.

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

Если k 1 (U =0; U =1), то

f (х,, х,, х )= ц,(х,,х )фх,с z(х<> ху)

Если k=2(U<=1, U =O) то f(x, х х>) =® (х )Юх у (х )Юх, у. (х. )@

®х, x (p4(x >) .

Если k=3(U 1, U =1), то f (x<, х э х ) — Ы,Е х (4 gSxg 4 у®õ x ы4®

®х 0Lg Ях х у Ы ®х х Myg x х х у 0 а у где Ы;Е)0,1j u i 1, ..., 8.

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

Как следует из таблицы, f (X» х, х ) = х,х,,ч х,х v х x> = (х ч х )® (+)x (x v x ) = 1®x x (Bx x О+

Q+ х, х х = 1 ® х,хз О+ х, 8 х, х, О+

Юх,х х

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

Исходным для нахождения -дзвичных номеров функций tel(x » ..., х„), 1 = 1, ..., 2 (выражение (1) ) является вектор значений раэлагаемой

144 l 380 логической функции f (xl, ..., х„): ф

6 6 (у ° у2 ) у у ее у „) . Далее формируется последователь2 — Ф ность ВеКТоров +I ..., Ик (k=1 °, и), 5 компоненты которых вычисляются согласно следующим рекуррентным соотношениям:

1 1- 2irrl+t у 2inl+t

15

Формула

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

МОДУЛИ ДВА по 2 элементов в каждой (n — количество двоичных пере30 менных разлагаемой логической функции), о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения

1 -()-1 (2;i l =У 2; « ОУ(2,,1,„ ! п-1 .. 1-1 где ш = 2, i = О, ..., 2 — 1;

1 ° ° ° у m> 1 1 у ° ° ° у k °

Значение функции ((х „+,, ..., х ) на t-м наборе переменных х „+, к. х (1=1,...,2; t=0, 2" " -1) совпадает с (2" (1-1) +

+ + 11-й компонентной вектора W к

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

U4, ..., Ug, код которых равен k, 5 -(где k=, Б „° 2

l=i сигнал 1 с выходов элементов ИЛИ

2, и 2 ), Если k = 2, сигнал "1" присутствует на третьем выходе дешифратора l (на первом и втором выходах— сигналы "0"). При этом сформированный на выходе логических элементов второй группы вектор W проходит транзитом на выходе l1,-11s устройства.

Если k = 3 (k = n) на всех выходах дешифратора присутствуют сигналы"0", которые поступают на входы элементов И всех групп. На выходах устройства формируются компоненты вектора И,,(Ы„), которые являются коэффициентами полинома Жегалкина °

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

Для рассматриваемого примера при

0 на первом выходе дешифратора 1 присутствует сигнал " 1" (на втором и третьем выходах — сигналы "0"/, который поступает на входы элементов

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

Если k = 1, сигнал "1" присутствует на втором выходе дешифратора 1 (на первом и третьем выходах — сигналы "0"). При этом на входы элементов

И 31-34. первой группы подается сигнал

"О", что обеспечивает формирование на выходе элементов СЛОЖЕНИЕ ПО

МОДУЛЮ ДВА 4,,-4 компонент вектора

Р,, которые без изменений проходят .на выходы 11,-11 устройства (на nepBble- Bxopbl 9JIeMeEIToB И э (-5y H 7, -74 второй и третьей групп пос;упает конъюнктивно-полиномиальных разложе35 ний по k переменных (k=0,1,...,n) содержит и групп элементов И по 2" элементов в каждой,п-1 элемент ИЛИ и дешифратор, r-й вход которого (r = 1, 2,..., s;

s = 1од z (n+1) () соединены с r-м управляющим входом, а первый выход соединен с первыми входами элементов

И первой группы и первым входом пер-, вого элемента ИЛИ, второй вход которого соединен с вторым выходом дешиф

Ф ратора, а выход соединен с первыми ". входами элементов И второй группы, j-й выход дешифратора (j = 3, 4, n) соединен с первым входом (j-1)-го элемента ИЛИ, выход которого соеди50 нен с первыми входами элементов И

j-й группы, а второй вход соединен с выходом ()-2)-го элемента ИЛИ, выход

i-го элемента И (i = 1, 2, ..., 2 ) .р-й группы (р = 1, 2, ..., n) соеди55 нен с первым входом i-го элемента

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы, второй вход которого соединен с вторым входом i-го элемента И р-й

Сигналы на информационных входах

Сингалы. на выходах устройства

Сигналы настройк

Уд У Уб У У Уу У У, 91 9 10< 10 101 10+ 10 10< 10т 108 11< 11< 11> 11 11 11 11т 118

0 0 1 0 1 0 О 1 I 1 1 0 1 0 О 1 1 1

0 1 1 0 1 0 0 1 1 1 i 1 0 1 0 1 1

1 0 1 0 1 0 0» 1 1 O

1 0 1 0 0 1. 1 1 1 0 1 1 1 0 0 !

5 1441380 6 групйы, выход 1z + v)-го элемента нен с выходом (wf-1) — го элемента

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА о-й группы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА g-й группы, и-4- (z=2,v 1,?,...,z, второй и третий входы (t + 1)-го с1 = 1, 2, ..., и-1) соединен с элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й вторым входом ч-го элемента СЛОЖЕНИЕ группд, (t=2 ",1

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

Ч и гРУппы, выход м -Г-го элемента 10 d i-x элементов СЛОЖЕНИЕ ПО МОДУЛЮ

СЛОЖЕНИЕ ПО МОДУЛЮ QBA q-й группы ДВА р-й группы соединены с (d + ь-1,, ф -1

2, + С

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

Составитель В. Сорокин

Редактор Е. Конча Техред M.Äèäûê Корректор С.Шекмар

Заказ 6289/52 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4