Устройство для полиномиального разложения логических функций
Иллюстрации
Показать всеРеферат
Изобретение относится к области вычислительной техники и предназначено для использования в высокопроизводительных ЭВМ для аппаратурной реализации системы команд, а также .для построения специализированных процессоров. Цель изобретения - расширение функциональных возможностей устройства для :полиномиального разложения логических функций п переменных за счет выполнения /конъюнктивнополиномиальных разложений по 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