Функциональный преобразователь Советский патент 1988 года по МПК G06F17/10 

10

15

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

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

На фиг. 1 показана функциональная схема преобразователя; на фиг. 2 и 3- :схемы блока элементов; НЕРАВНОЗНАЧ- НОСТЬ и коммутатора при .

Функциональный преобразователь содержит информационные входы 1, выходы 2, счетчик 3, коммутатор А, содержащий 2 мультиплексоров 4)-4jh, 20 блок 5 элементов НЕРАВНОЗНАЧНОСТЬ, содержащий групп по 2 элеменТов НЕРАВНОЗНАЧНОСТЬ, блок триггеров 6, вход 7 синхронизации, вход 8 установки в начальное состояние и настро- 25 ечные входы 9.

Рассмотрим реализуемый предлагаемым устройством алгоритм вычисления коэффициентов полинома Жегалкина, ,Где каждая переменная входит или непо- 30 Средственно, или с инверсией. Пусть 9адана булева функция своим вектором истинности f(fo,. .. jfjo.,), где f; моет быть или нулем, или единицей (j «0,1 ,... ,). Произвольная булева ункция представлена полиномом Жегал ина следующего вида: 1.

1388890

f(x,,:

itX

где х; х

Вели или нул

Чтоб 3;ов F(k f умнож (кронек цы

рассмат перемен , в

С це прямого можно в куррент

Нп

35

где Н При

функции

записыв

,)---ZF(4k,)

K,0

(1)

где знак суммы по,модулю два; х; или х;, или x (,...,n); х 1 , если k; 0;

Величины F(kni...,k,) могут быть или нулями, или единицами.

Чтобы получить вектор коэффициен- 3;ов F(k,... ,k,), необходимо вектор f умножить на п-кратное прямое (кронекеровское) произведение матрицы

ГЬ;ьП Ь J j

(2)

рассматриваемой при ,...,п. Если переменная Xj не инвертирована, то , в противном случае

С целью нахождения п-кратного прямого произведения Н„ матрицы (2) можно воспользоваться следующим рекуррентным соотношением:

ь.н„., h, н„.,

пН„.,1

Hh-, J )

где Н, - матрица размером 2 2 , являющаяся (п-1)-кратным кронекеровским произведением матрицы (2). При умножение вектора значений

функции Г(х„,...,х) на матрицу Н„

записывается так:

Изобретение относится к автоматике и вычислительной технике и предназначено для.проектирования логических схем.Цель изобретения - расширение функциональных возможностей за счет нахождения любого из 2 полиномиальных представлений булевой функции. Преобразователь содержит /Г информационные входы 1, выходы 2, счетчик 3, коммутатор 4, блок элементов НЕРАВНОЗНАЧНОСТЬ 5, блок триггеров 6, вход синхронизации 7, вход установки в локальное состояние 8, настроечные входы 9. Преобразователь вычисляет коэффициенты таких полиномиальных представлений булевой функции, в которых переменные входят не только непосредственно, но и со знаком инверсии. Б зависимости от выбранного способа инвертирования переменных, задаваемого кодом счетчика, коммутатор осуществляет перестанов из компонент в векторе истинности булевой функции, подаваемом на информационные входы. Блок элементов НЕРАВНОЗНАЧНОСТЬ формирует коэффициенты полинома выбранного вида, которые по завершении такта заносятся в блок триггеров, откуда снимается результат. 2 з.п. ф-лы, 3 ил. J (Л к 00 оо 00 со о

Это соотнощение можно представить

как систему следующих равенств:

F(0,0,0)h,hih,fo®hihah, f,®h,hih, fj®h,h,,h,f,, f4©h,,fseh,,fg€

®h,hjh, f,j „

(0,0,1 )h,,®h,h,if,®h,hifj®h,hj.fs®h,hif4®h,,hjf5©h3hjfsfflh,hj.f-, ;

F(0,l ,0)hjh, fjShjh. f,®h,,h, fi®h,h, f.,©h,h, f4®h,h, Гу©Ь,Ь,, f ;

:r(0,1J1 )h,fo®hsf,©h,f2®l,f,®h,f ®h ify©h,f«®h,f, ; .34

F(l,0,0)h5li,fo®hjh,f,.fi®liih,f,®h,h,f4®h,,h, fy©hjh,f,®hih, f ;

(1 ,0,1 )H2fo®hjf,®hi:ra®h,.f,®hif4a)E fs®hjf6®hzf7 i

Fd ,l,0)-h,fo€)h, f,©h,f4©h,f,®h,f4©h.fs®h,fe®h.f-, ;

F( I , 1 , 1 )fo® f,ffif j®f,®f ®f: f6©f7 .-

Для алгоритм функционирования определяется системой равенств (З).

Функциональный преобразователь 2

держит группу из

входов, причем

как систему следующих равенств:

Функциональный преобразователь со- 2

держит группу из

входов, причем

31388890

порядок подключения входов Nj(Ng . и номера N, (. . .NaL) входа J-ro 0,) этой группы к информационным (,2 -О мультиплексора, где

п-1 (п1{-It (О

N,+...+2-N +К „ .

(5)

©N;:, i(r;)

входам коммутатора описывается выражением вида

Получение двоичного представления (4) номеров входов функционального преобразователя из двоичных представле- Здесь значения N и N являются «ий номеров мультиплексоров и номе DM компонентами двоичного представле- .Q ров входов мультиплексоров при ния порядкового номера N(,. .К« ) иллюстрируется таблицей.

000001010011100101110111

001000011010101100111по

010011000001по111100101

011010011000111по101100

100101по 111.000001010011

101100111по001000011010 по111100101010011000001 111по101100011010001000

Предлагаемое устройство позволяет вычислять коэффициенты полинома Жегал- кина за один такт функционирования путем умножения вектора значений функции Г(х„,..,х,) на матрицу Н„.

Требуемый вид полинома Жегалкина задается величинами hr,,. .. ,h,, хранимыми в счетчике 3. Величина h;(i 1,п) равна единице, если соответствующая переменная х; инвертирована, и тождественна нулю в противном слу- чае.

После занесения в счетчик 3 определенной комбинации величин h„,...,h, с входов 9 начинается подсчет синхроимпульсов и на выходах счетчика 3 последовательно появляются различные комбинации величин Ь„...Ь,. Это позволяет осуществить вычисление любых из 2 полиномиальных представлений . булевой функции, начиная с заданного

I, h,h2h,fo®h5h2h,f,®h3h2h,f,j®h,hjh, 1 НзЕгК , f,.-fo©ii,hjh, f,@E,hjh, . 15 й зй 2.й , Г5(©Й ,й. гЬ, f,, fo@li,hili, ,hih, f,®h,hih,,h-,f,®ff,h5,h, , f4@h,hj.h, fy©h,hjii, Гб©й,Ь.,Ь, ,Г5®Й5КгЬ, ,hih,f,®fi,hzh,

п-1 (п1{-It (О

N,+...+2-N +К „ .

(5)

35

40

45

которое определяется заносимой комбинацией hh,...,h,. Полученные результаты сравниваются с целью выбора лучшего по заданным критериям (например, критерий минимального числа единиц в полиноме Жегалкина, обеспечивающий минимум аппаратных средств).

Рассмотрим функционирование предлагаемого устройства для , описываемое системой равенств (З).

На входы IQ-I, функционального преобразователя соответственно п€)да- ются значения f;, ,f, ,f jf, ,f jfj-j . fg jfy булевой функции.

Комбинация величин hj, h, h, с выхода счетчика 3 поступает через управляющие входы коммутатора 4 на адресные входы мультиплексоров 4(-4g Сигналы на выходах с мультиплексоров 4,-4g задаются следующими выражениями соответственно:

f3®h,h2h,,,f5®h,h3,h,f6©h,;h2h,f7; f2©h,hjfi, fs®hJЯ2h,fд®hэh,JH,f,©h,,fв; f,©h,hih, f6©h,,,f4©h3hih/f5. ; , f,®h,fi.,h,f6®h,h,,h,f6@h,hjh,f4 ; f7©h,hih,fo©h,hih, f,©h,hih, f Shjhjh, f, ; f6®h,hj.S, f,®h,li2h,fo®h,lizh, f,®h,,fi ;

50

513888906

,,1т , fpffihjh.h, ,,f4®h3h,h, f;®h,h,h, fi®h,h, h, f,®h,hih, fo®h,h,h,f, ; .ih,f,©h,h,,,h,fe©hjhjh fsfflh., , f ,®h,h,h, fi®h,h,h, f,, f ;

где операция логического ИЛИ заменена суммой по модулю дв-а благодаря следующему.

В алгебре Жегалкина имеет место тождество xvy x®y®xy, которое превращается в , если х и у предста- ш НЕРАВНОЗНАЧНОСТЬ имеют место величи- вляют собой конъюнкции, содержаоц е .

(hjh2h,,hih,f,®h,,f,,f,©h,hih, Гф®Ь,, , Гб©Ь,Ь Ji, f, ), (h,h2fo®h,ijf,©h.,hzf,,h jfg®h,h2f6®h, ); (h,h2h,fj©h,,, fo©h,hji, f,©h,h,h, Гб®ЬзЬгЬ, f,®h,h,,h, f4.®h,h.,h, f ); (h,h.jf2®h,h f3©h-5b,,fo®h5hzfi®h,h,fg©h,,h,tf4®h3hj,f5-); (h,h5h,,h2h,,hih,f6©h,hjh.fr©h,h.,h, fo®h,, f,®h,h,,h, fj©h,h,h,f3 ); (h,h2f4®h,h,f5.0h,hjfg®h2h f7®h,hjf(,ffih,hif,©h,hif2®h,h.if, ); (h,hih, f6®h,hih,f7®h,h2b, , , ,, f,®h,h.,h, fo©h,h.,h, f, ); (h,h f6®h5hifT®h,,h,,,,h.jf,,fflh3h2f,®h,hjfo®h,h,,f, )

соответственно.

Это позволяет на выходах второй группы элементов НЕРАВНОЗНАЧНОСТЬ и

(h,hah, ,hih, f,©h,, , f,®h,h,,h, ,hjh, fy®h,hih, fg®h,,f );

(h;hifoeh,hif,eh,, hifi®h,hifj©h,h,. f4®h,hify®h,hzf6®h,hif );

(hjh, ,fj©hjh,f,®h,-h, Гэ©Ь,Ь, f4®h,h, fgffihjh, fsfflhjh, f );

(h,,f,®h,f2®h9:f5®h,f4©h,:fs®h.,fg®h3f;);

(h,bih; f4 0h,,®h,, f6©h,, f,®h,, 4®h,h.jh, f,®h,hjh, f,jiBh,h.,h, f, );

(h,h5f4@h,hjfs®h.jhzfg®h,hjfr®h,h,fo®h,hif,®h,,hifs ).;

(h.jh, ,,ih, fs®h,h, ,h, fo©h,h, fj®h,h, f,®h,h, f,, );

(h,f4®h5fs©h,f6©h5f,,®h,fj,®h,f3 ).

Ha входы триггеров 6( -69 с выходов НОСТЬ поступают значения

третьей группы элементов НЕРАВНОЗНАЧI ,, -

(hjh-ih, fo@h,,®h,h2h, f2®h,h.ih, , f4@h,h.ih, f5-fflh,h5, h, , f ); (hjhjfp® hjhif,a)hjh54©h3h f,.,hjf4©h,hi.fs©h5hife®h,h2f7 ); (h,h, ,f,, , f,®h,h, f.®h5h, fy@h,h, fg®h,h, f, ); (h, fo® h,f,©h,f.j©h,f,,f,«h3f6©h f, ); (hjh, , f,, fi®hjh, ,ih,f4©hih, , fgShjh, f ); (h,,fo®hifi©hifi©hzf,0h,f ®hify©hif6®hjf ); .(h, fo®h, f,®h, fz®h, f5®h,f4@h,f5eh,f6®h;-f,);

( f, & f j® f ,© f Ц.® f y® f 6 ® f 7 )

соответственно.

В результате по окончании такта на выходах 2,-29 преобразователя хра- нятся значения, определяемые системой равенств (З),

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

содержащий счетчик, коммутатор, блок триггеров и блок элементов НЕРАВНОпрямое и инверсное значения некоторой переменной, например h, f(,®h, f, -h, .f, .

Ha выходах первой группы, a также на входах второй группы элементов

25

на входах третьей группы элементов НЕРАВНОЗНАЧНОСТЬ получить соответственно значения:

ЗНАЧНОСТЬ, причем.информационные входы преобразователя соединены с информационными входами коммутатора, управляющие входы которого соединены с выходами счетчика, вход синхронизации которого соединен с входом синхронизации преобразователя и тактовых входом блока триггеров, выходы которого соединены с выходами преобразователя, вход установки в начальное состояние которого соединен с входом

сброса блока триггеров, информационные входы которого соединены с выхо-. дом блока элементов НЕРАВНОЗНАЧНОСТЬ, входы которого соединены с выходами коммутатора, о т ли чающи и - с я тем, что, с целью расширения функциональных возможностей за счет нахождения любого из 2 полиномиальных представлений булевой функции, настроечные входы преобразователя соединены с информационными входами счетчика, вход разрешения записи которого соединен с входом установки в начальное состояние преобразователя .

5

0

и 2J-M входами блока, входы J-ro элемента К-й группы (,п) соединены с соответствующими выходами элементов НЕРАВНОЗНАЧНОСТЬ (К-1)-й группы и входами блока, с первого по 2 -и выходы блока соединены соответственно с первым входом блока, выходами элементов НЕРАВНОЗНАЧНОСТЬ с первой по (п-1)-ю группы, выходы элементов НЕРАВНОЗНАЧНОСТЬ п-й группы соединены с ( + 1)-го по выходами блока,

3. Преобразователь по п. 1, отличающийся тем, что коммутатор содержит 2 Мультиплексоров, причем управляющие входы коммутатора соединены с управляющими входами мультиплексоров, выхода которых соединены с выходами коммутатора, информационные входы которого соединены с соответствующими информационными входами мультиплексоров.