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

 

Изобретение относится к области вычислительной техники и предназначено для использования в высокопроизводительных ЭВМ, интерпретирующих программу, написанную на языке высокого уровня, а также для построения специализированных процессов. Цель изобретения - расширение функциональных возможностей за счет преобразования дизъюнктивной нормальной формь (д.н.ф .) логических функций в канонические поляризованные полиномы .- . (к.п.п.). Преобразователь содержит п ярусов элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА по элементов в каждом (п - количество логических переменных), п элементов НЕ и п ярусов элементов И-ИЛИ по 2 элементов в каждом. На информационные входы преобразователя подаются коэффициенты д.н.ф. логической функции, на настроечные входы преобразователя подаются компоненты вектора поляризации, на выхо- § дах преобразователя реализуется вектор коэффициентов поляризованного полиномиального разложения. 1 ил., 1 табл. (Л

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

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

РЕСПУБЛИК (19) (113

1 Ai (51) 4 С 06 Р 5/00, 7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н двтогскоигк свидеткльствм

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

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

Р 781822, кл. С 06 Р 15/31, 1978.

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

Р 1124281, кл. С 06 F 5/00, 1983. (54) ПРЕОБРАЗОВАТЕЛЬ ФОРМЫ ПРЕДСТАВЛЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ (57) Изобретение относится к области вычислительной техники и предназначено для использования в высокопроизводительных ЗВМ, интерпретирующих программу, написанную на языке высокого уровня, а также для построенияспециализированных процессов. Цель из обрете ния — расширение функциональ- ных воэможностей за счет преобразования дизъюнктивной нормальной формы (д.н.ф .) логических функций в канонические поляризованные полиномы (к.п.п.). Преобразователь содержит п ярусов элементов СЛОЖЕНИЕ ПО МОДУЛЮ

ДВА по 2" элементов в каждом (n— количество логических переменных), п элементов НЕ и и ярусов элементов И-ИЛИ по 2 " 1 элементов в каждом.

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

С2 дах преобразователя реализуется век" . тор коэффициентов поляризованного полиномиального разложения. 1 ил., 1 табл.

1441381

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

Цель изобретения — расширение функциональных возможностей преобразователя формы представления логических функций за счет преобраэб вания дизъюнктивной нормальной формы (д.н.ф.) логических функций н канонические поляризованные полиномы 15 (к.п.п.).

На чертеже представлена схема преобразователя при n = 3..

Преобразователь содержит четыре элемента 1-4 СЛОЖЕНИЕ ПО МОДЮЛЮ ДВА первого яруса, четыре элемента 5-8

СЛОЖЕНИЕ ПО МОДУЛЮ. ДВА второго яруса, четыре элемента 9-12 СЛОЖЕНИЕ ПО

МОДУЛЮ ДВА третьего яруса, четыре элемента 13-16 И-ИЛИ первого яруса, 25 четыре элемента 17-20 И-ИЛИ второго яруса, четыре элемента 21-24 И-ИЛИ третьего яруса, три элемента HE 2527, восемь информационных входов

28-35 преобразователя, тпи настроеч- 30 ных входа 36-38 преобразователя, восемь выходов 39-46 преобразователя.

Логическую функцию F = F (х, х, ..., х„) можно задавать посредством 2 -разрядного булева вектора

ll ее значеиий Q (F) = (И4, (д, д „), где ы, — значение F на

2 -

Р

i-м наборе (i = О, 1, ..., 2 — 1) .

Канонический поляризованный полином

Р (Г) логической функции F задаи ется 2 -разрядным вектором — вектором коэффициентов а (Г) = (а„, а,, а „ ), где а. = 1 тогда и только и э I . Съ тогда когда слагаемое х " х

Ф 3 х " (О» Kñ и) входит, н

Зк

Рб(Р) и 1,, ), °, )„- номера единичных компонент двоичного n-pasрядного эквивалента числа 1.

Здень вектор G =(G Я, ...,Gn ) яВляется дВОичным Вектором поляризации полинома. Причем Ж = 0 тогда и только тогда, когда аргумент х;(i — 1,2, ..., п) входит в слагаемые полинома Р (F) без отрицания. Одна часть аргументов функции F ВХОДит в полином только без отрицания, а другая — только с отрицанием. При п = 3 к.п.п. функции F В общем елучае имеет вид

ОР б„аC;, S a., О аКХ Х3 + абх х ®а х Х2.

T 1 1

5 где а„ 0 1 ; j = О, 1, ..., 7;

Г = Г,,В„Ы, >, g, E (О, j;. ю

1, 2, 3; х

= x;, если б; = 0

5; их =x;, еслибы, = 1.

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

Исходным для нахождения Вектора аО(Г) является вектор 4, = (у,, о о

У2. ° ° ° t У " ) — (А э 1 ю ° ° ° ю а .,) = (7), где у и

2, ..., 2 . Далее формируется послеУ «Э цовательность векторов Ч,, Ъ, М„, компоненты которых вычисляются согласно следующим рекуррентным соотношениям:.G

Z met < 4. < (21i1) 7Ъ1 41 к к- к- (и „ t У;„, t6) y (Z . ) . ° (2)

К-I ll-k гдеm=; 1=0, 1, ...,? -1;

1, 2, ..., m;

К = 1. 2, ..., n.

Компоненты вектора Н„ = (у",, у"

0 у „) совпадают с соотнетствующими коэАфициентами поляризованного конъюктивно-полиномиальногo разложения, т.е. а = у " ; j = 0, 1

2 -1.

В соответстнии с приведенным алгоритмом К-й ярус (К = 1, 2, ..., n) элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и

И-ИЛИ преобразует вектор W, в вектор Ъ „, причем работа элементов

И-ИЛИ К-го яруса описывается выражением (1), а работа элементов СЛОЖЕНИЕ

ПО МОДУЛЮ ДВА К-ro яруса — выражением (2), Преобразователь работает следующим образом.

На j-й информационный вход (j-й информационный вход (j = 1, 2, и

2 ) подается значение у;, преобразуемой логической функции F F(x<, х, ..., х„) íà (j-1)-м наборе переменных х „, х, ..., х g (фактически на информационные входы преобразователя поступают коэффициенты соверР„,(F) =a,O+ a, х, ® aixz у >х. „Ю "4Х,Ю

G. G С3 G G1 6 62 63 6

14413

3 шенной д,н.ф, функции Р). Иа i é настроечный вход (i = 1, 2, ..., и) подается -я компонента 6, вектора поляризации 6 = (G,, (7 . ..., G„ ).

На выходах преобразователя реализует

5 ся вектор коэффициентов поляризованного полиномиального разложения

Преобразователь позволяет получить 10 и

2 канонических поляризованных полиномов.

Для рассматриваемого примера значения преобразуемой функции Г = Г(х, х, х ) подаются н@ входы 28-35 соот- 15 ветственно, компоненты вектора поляризации б,, G, G> — на входы 36, 37 и 38 соответственно. На выходах

39-46 реализуются коэффициенты а, ..., a поляризованного конъюнк- 20 тивно"полиномиального разложения.

В качестве примера в таблице представлены значения коэффициентов а, ..., а полиномиальных разложений логической функции F = F(x<, х, 25 х ) = х х х V х х ч х х для восьмй возможных комбинаций компонент вектора поляризации g = (G, Gz 6 ).. . Ha выходы 28-35 преобразователя подаются коэффициенты соответственно 30

Я, ..., Q совершенной д.н.ф,, составляющие вектор значений F. ::<д ()

= (а„ са,, ..., са,) =((O,О,1,О,т, 1,O,1)).

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

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

h чество логических переменных), причем в каждом k-м ярусе элементы СЛОЖЕНИЕ

ПО МОДУЛЮ ДВА образуют 2" групп

k-!

« ° по 2 элементов в каждой (k =1, n), первый вход j-ro элемента СЛОЖЕНИЕ ПО 45

МОДУЛЮ ДВА первого яруса (j=1,2 ) соединен с (2 j-1)-м информационным входом преобразователя, 2 j-й информационный вход которого соединен с вторым входом j-ro элемента СЛОЖЕНИЕ 50

ПО МОДУЛЮ ДВА первого яруса, выход

j-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА

81 4 п-го яруса соединен с 1-м выходом преобразователя, о т л и ч а ю щ н и с я тем, что, с целью расширения функциональных возможностей за счет преоб.разования дизъюнктивной нормальной формы логических функций в канонические поляризованные полиномы, содержит и элементов НЕ и и ярусов элемен. т- тов И-ИЛИ по 2 элементов в каждом, причем в каждом k-м ярусе элементы И-ИЛИ образуют 2 " групп по 2

k-> элементов в каждой, вход k-r o элемента НЕ соединен с k-м настроечным входом преобразователя и первыми входами первой группы всех элементов

И-ИЛИ, первые входы второй группы которых соединены с выходом k-ro элемента НЕ, первый вход j-ro элемента

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

СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-Й группы

r-ro яруса Й = 1,m m 2, p

1, 2" "; r = Г,п) соединен с выхо-, дом го элемента CJIOKEHHE ПО МОДУЛЮ

ДВА (2р-1)-й группы (r-1)-го яруса и вторым входом первой группы i-ro элемента И-ИЛИ р-й группы r-го яруса, второй вход второй группы которого соединен с выходом i-го элемента

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

ДВА р-й группы r-ro яруса соединен с выходом i-ro элемента И-ИЛИ .(2р-1)-й группы (r-1)-го яруса и вторым входом первой группы (m+i)-го элемента

И-ИЛИ р-й группы r-ro яруса, второй вход второй группы которого соединен с выходом i-го элемента И-HJIH

2р-й группы (r-1)-ro яруса и вторым входом (m+1)-ro элемента СЛОЖЕНИЕ ПО

МОДУЛЮ ДВА р-й группы r-ro яруса, выход

j-ro элемента И-ИЛИ n-ro яруса является (2 " + j)-м выходом преобразователя.

1441381

Вектор поляризации

К.п.п

Коэ К ициенты к,п.п.

P (F) G, 36

G> а, 38 39

G 6

4 5

43 44

6 а

Я ат

5 а

G а

42 а

40 бт

37 х,ух х ех, " фх х Г

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

Редактор Е. Копча Техред M.Äèäûê Корректор 3. Лончакова

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

0 0 О О 1 1 1 О О 0

0 1 0 0 0 1 1 О О 0

1 0 1 1 1 1 1 О 0 О

1 1 0 1 О 1 1 О 0 О

0 0 1 О 1 1 1 0 0 О

0 1 1 О О 1 1 0 О О

1 0 0 1 1 1 1 О О О

1 1 1 1 0 1 1 0 О О

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

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

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

19х Q+ x а х х Д х, 1®х &х х®х

1Ях х-щх, х х @х х х,.