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

4ik 4

00

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

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

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

Преобразователь содержит четыре элемента 1-4 СЛОЖЕНИЕ ПО МОДЮЛЮ ДВА первого яруса, четыре элемента 5-8 СЛОЖЕНИЕ ПО модуле. ДВА второго яруса четыре элемента 9-12 СЛОЖЕНИЕ ПО модулю ДВА третьего яруса, четыре элемента 13-16 И-ИЛИ первого яруса, четыре элемента 17-20 И-ИЛИ второго яруса, четыре элемента 21-24 И-ИЛИ третьего яруса, три элемента НЕ 25- 27, восемь информационных входов 28-35 преобразователя, три настроечных входа 36-38 преобразователя, восемь выходов 39-46 преобразователя

Логическую функцию F F (х, х, ..., х„) можно задавать посредством 2 -разрядного булева вектора ее значений (О (F) ((Од, (О, , ..., tOjn.i ) где СО, - значение F на i-M наборе (i О, 1, ..., 2 -1). Канонический поляризованный полином Рх-СГ) логической функции F задается 2 -разрядным вектором - вектор коэффициентов ) (а, а, . ., ,, , ), где а 1 тогда и толь тогда, когда слагаемое , v ..., ху (0 Кб п) входит , в Pp(F) и J,, J2, .- JK номера единичных компонент д.оичного п-раз рядного эквивалента числа j.

Здевь вектор G ( G, ,G , .. ., G является двоичным вектором поляризации полинома. Причем G ; О тогда и только тогда, когда аргумент xj(i 1,2, ... п) входит в слагаемые полинома РГГ(Г) без отрицания. Одна часть аргументов функции F входит н полином только без отрицания, а другая - только с отрицанием. При п к.п.п. функции F в общем случае име вид

Pc;(F) a x J ®a xJ ©a x ; .ф I ® , ,

где aj е o,l|; j О, 17;

G (G-, ,61 ,ff,) ; G; е fo,. i 1, 2, 3; Х| x;, если CJ; О

и X X;, если G; 1.

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

Исходным для нахождения вектора a(3:(F) являет.ся вектор % (у,

У°, ..., ) (СОд , 0}

, (, где у СО;.,, i 1, 2, ..., 2 . Далее формируется последовательность векторов W, , Wj, . .. , W(,, компоненты которых вычисляются согласно следующим рекуррентным соот- нощениям:

30

УГ.П.,± Уа;т+-Ь С к У(.,,., ;(1)

У(а;ч.0т+. y2;m4t®y(i;M)v,t 2)

5

0

5

0

5

где m 2

К-1

i О, 1,

-1;

т;

t 1, 2, .

К 1. 2, о . , п. ..

Компоненты вектора W,, (y J , У1 У2.) совпадают с соответствующими коэффициентами поляризованного конъюктивно-полиномиального разложения, т.е. а у| ; j О, 1

.

В соответствии с приведенным алгоритмом К-й ярус (К 1, 2, .,., п) элементов-СЛОЖЕНИЕ ПО МОЩТШ} ДВА и И-ИЛИ преобразует вектор Wi, , в I

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

Преобразователь работает следующим образом.

На j-й информационный вход (j-й информационный вход (j 1, 2, ..., 2 ) подается значение преобразуемой логической функции F F(Xf, ..., Xj) на (j-l)-M наборе пере(Ф

нктически

менных х, Xj, .,.,

на информационные входы преобразователя поступают коэффициенты совер3U413814

гаенной д.н.ф. функции F). На i-й п-го яруса соединен с j-м выходом пре- настроечный вход (i 1 , 2, , .. , п) образователя, отличающийся подается i-я компонента G; вектора тем, что, с целью расширения функци- поляризации G (О,, 0 , .. ., ff ) . . ональных возможностей за счет преоб- На выходах преобразователя реализует-i разования дизъюнктивной нормальной ся вектор коэффициентов поляризован- формы логических функций в каноничес- ного полиномиального разложения кие поляризованные полиномы, содер- a,(F) (Яд, а,, ..., ., ) ясит п элементов НЕ и п ярусов элеменПреобразователь позволяет получить .Q тов И-ИЛИ по 2 элементов в каж- 2 канонических поляризованных поли- дом, причем в каждом К-м ярусе злемен- номов.ты И-ИЛИ образуют групп по 2

Для рассматриваемо го примера зна- элементов в каждой, вход k-ro эле- чения преобразуемой функции F Г(х,, мента НЕ соединен с k-м настрое {ным Xj, х) подаются на входы 28-35 соот- ig входом преобразователя и первыми вхо- ветственно, компоненты вектора поля- дами первой группы всех элементов ризации G, , G , ff 43 входы 36, И-ИЛИ, первые входы второй группы ко 37 и 38 соответственно. На выходах торых соединены с выходом k-ro эле- 39-А6 реализуются коэффициенты мента НЕ, первый вход j-го элемента зР, ..., а поляризованного конъюнк-2о СЛОЖЕНИЕ ПО МОДУЛЮ ДВА первого яруса тивно-полиномиального разложения. . соединен с вторым входом первой групВ качестве примера в таблице пред- пы j-ro элемента И-ИЛИ первого яруса, ставлены значения коэффициентов второй вход второй группы которого а, ..., а полиномиальных разложе- соединен с вторым входом j-ro элемен- ний логической функции F F(x,, х, 25 та СЛОЖЕНИЕ ПО МОДУЛЮ ДВА первого Xj) X, X X V x, x,Xj для восьми яруса, первый вход i-ro элемента возможных комбинаций компонент векто- СЛОЖЕНИЕ ПО МОДУЖ1 ДВА р-й группы ра поляризации G (, , 6, С, ) . г-го яруса (1 1 ,mj m 2 , р На выходы 28-35 преобразователя пода- 1, 2 ; г 2,ri) соединен с вых,о-. ются коэффициенты соответственно зо 1то элемента СЛОЖЕНИЕ ПО МОДУЛЮ Qp, ..., О, совершенной д.н.ф., со- ДВА (2р-1)-й группы (r-l)-ro яруса и ставляюР1ие вектор значений F : со () - вторым входом первой группы i-ro ((Х)о СО, , ...,«7) ((0,0,1 ,0, Т, элемента И-ИЛИ р-й группы г-го яруса, 1,0,0).второй вход второй группы которого

,,. соединен с выходом i-ro элемента

Формула изобретения 35 ложЕНИЕ ПО МОДУЛЮ ДВА 2р-й группы

Преобразователь формы представления (r-l)-ro яруса и вторым входом i-ro логических функций, содержащий п яру- - элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА сов элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА Р-й группы г-го яруса, первьй вход по 2 элементов в каждом (п - коли-4о (m+i)-r o элемента СЛОЖЕНИЕ ПО МОДУЛЮ чество логических переменных), причем ДВА р-й группы г-го яруса соединен с в каждом k-M ярусе элементы СЛОЖЕНИЕ выходом i-ro элемента И-ИЛИ .(2р-1)-й ПО МОДУЛЮ ДВА образуют. групп группы (r-l)-ro яруса и вторым вхо- по элементов в каждой (Е 1, п), дом первой группы (m+i)-ro элемента первый вход j-ro элемента СЛОЖЕНИЕ ПО 5 И-ИЛИ р-й группы г-го яруса, второй МОДУЛЮ ДВА первого яруса (j 1,2. ) в Код второй группы которого соеди- соединен с (2 j-1)-M информационным йен с выходом i-ro элемента И-ИЛИ входом преобразователя, 2 j-й инфор- 2р-й группы (r-l)-ro яруса и вторым мационный вход которого соединен с входом (т+1)-го элемента СЛОЖЕНИЕ ПО вторым входом j-ro элемента СЛОЖЕНИЕ до ОДУЛО ДВА р-й группы г-го яруса,выход ПО МОДУЛЮ ДВА первого яруса, выход j-ro элемента И-ИЛИ п-го яруса является j-ro элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА ( + J)-M выходом преобразователя.

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