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

1I339S83

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

Цель изобретения - повышение родействия.

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

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

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

Пусть задана булев а функция своим вектором истинности f (f,.. ..,f ) , где fj может быть или нулем, или единицей (j О, 1 ,. . . , ). Произволь- 30 нал булева функция представлена полиномом Жегалкина следующего вида:

где Н - матрица являющаяся (п-1) произведением ма

Кроме того, в F(K ,. . .,К , ) можн зультат умножения ное обыкновенное A|(h). При п

При п 2 умн ний функции f(х ное произведение сывается так:

F (0,0) F (0,1) F (1,0)

h h

F ( I , 1 ) J о Это соотношени как систему из ч т венств, записанны F(0,.0) . F( 0, 1 ) :t;® F(l,0) h

g ... . F(K,...,

к 0

где 1°- знак суммы по модулю два, х.

или X

или X,.:, i ( 1 , . ., 5 п)

х.у 1, если К; 0. Величины

1

F(K ,.,.,К) могут быть или нулями, или единицами.

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

L 1 1

(2)

рассматриваемой при i

,п. Если

переменная х. не инвертирована, то -hj Oj в противном случае h 1.

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

h Н

Н

h

h Н

п

Н ,

д (h ) имеет вид

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

Кроме того, вектор коэффициентов F(K ,. . .,К , ) можно получить как результат умножения вектора f на п-крат- ное обыкновенное произведение- матрицы A|(h). При п 2 и п 3 матрица А

При п 2 умножение вектора значений функции f(х ,...jX ) на 2-крат ное произведение матрицы A(hj ) записывается так:

0

F (0,0) F (0,1) F (1,0)

h h: 00 h;

p 0

h; h,

0 0

11

О

F ( I , 1 ) J о О 1 1 J LO О 1 1 Ъ Это соотношение можно представить как систему из четырех следующих ра- венств, записанных в скобочной форме: F(0,.0) ., h,l F( 0, 1 ) :t;® f, h20Lfa©f jl h (3) F(l,0) h,©f, ,©f; h,

F(l,-l) ;f;©f,. 0 Для n 2 алгоритм функционирова- :ния данного устройства определяется .системой равенств (3).

Данное устройство позволяет вычислять коэффициенты полинома Жегалкина 5 за п тактов функционирования путем умножения вектора значений функции f(x ,...,х) на п-кратное обыкновенное произведение матрицы Aj(hj).

Требуемый вид полинома Жегалкина 0 задается величинами h,.,.,h , хранимыми в кольцевом счетчике 5. Величи- ,h) равна единице, если

инвертирована, и тождественна нулю - в 5 противном случае.

на h.(i

соответствующая переменная хРассмотрим функционирование данного устройства для п 2, что описывается системой равенств (3).

Поступление импульса на устанавливает триггеры чик 3 в нулевое состояние,

7,-7,

вход 10

и счет- а также

обеспечивает запись в кольцевой счетчик 3

h,..

дах 1

На

п,h

разрядного двоичного кода присутствующего на вхофуНКЦИОНШ1ЬНОГО

входы 1 -1,| преобразователя поданы соответственн значения :Г„ , f. , Г. , f.

булевой фун- течение

-0 - ( - Г) -1,

кции, которые присутствуют в всех п 2 тактов.

Кодовая комбинация (00) с выхода счетчика 3 поступает через управляющие входы первого коммутатора 4 на адресные входы мультиплексоров Это позволяет получить па выходах

4 -i 1

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

Значение h с выхода кольцевого счетчика 5 через управляющий вход второго коммутатора 6 подается на адресные входы мультиплексоров 6,- и 6,,

Благодаря этому на выходах -1уль- типлексоров 6 и б присутствуют значения (,hJ и (fjjb., тохсдественные (., h, ) I5

.f.f,,}

(f,h,,h, соответственно.

(f -fa -f.h

г) л 3

В алгебре ло1 ики имеет место следующее тождество xvy х@г0хл., кото-рое в данном случае записывается следующим образом;

-h,h (4 4} можf .h V f h,

01 1-1

Поскольку h h

f.h,©f, , 0,

вьфалсение HO представить так:

f h,Vf h, ,h, .

В результате на входах триггеров и 1 Р1меем соответственно величины f h,©f h и

f,h,©f,i, На входы триггеров 1

и 7.

с ВЫХОДОВ элементов НЕРАВНОЗНАЧНОСТЬ 8, и 8 - поступают значения (f ©f, ) и

С f -I- f ) J- 2,1

По

2,-2

но, и на вторыз информационных входах мультиплексоров 4-4 хранятся

соответственно, окончанию такта на выходах , , преобразователя, а следовательсоответственно значения Г.Ь©Г , ,©f,hl, f@f ,, r.f,®f,l.

При переходе к второму такту содержимое кольцевого счетчика 5 сдвигается в сторону младших разрядов. В результате на выходе кольцевого счетчика 5 содержится величина hj.

На выходах счетчика 3 имеем кодовую комбинаци о 01, которая обеспечивана выходах 4 -4

ет подк; ючен 1е к выходам мультиплексоров 4 |-4 их вторых информационных входов. В результате мультиплексоров имеем величины h,K i;h,f.,hj ,,l , 1 соотз етственно .

Величина h , с выхода кольцевого счетчика 5 через управляющий вход второго коммутатора 6 подается на адресные входы мультиплексоров 6 -6 . Это позволяет аналогично описанному в первом такте подать значения

(,@f, h,lll,,h,©f h,lhj И

5

Q 1

( f,l ho ©Lf, с выходов кгультиплёксоров 6, и 6 п на входы триггеров 7 и 7 , соответственно.

На входы триггеров 7, и 7 с выходов элементов НЕРАВНОЗНАЧНОСТЬ 8, и

0

подаются значения L. Гг,,г1,н i;©f 0 f2®Kl.

По окопча1П1И такта на выходах преобразователя имеем соответственно величины ( -: Ji,©f, h,,,lhj,),

(. :ih,,© , (Cf;h©f, h, ©

©if2,h,6)i,h,J) , (i;®f, ), что CO-. ответствует системе равенства (З).

TaKiii-i образом, преобразователь вычисляет коэффициенты полинома Жегалк и н а 3 а п т а к т о в .

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

1 Функциональнъш преобразователь, содерлсащий счетчик, первый коммутатор и блок триггеров, причем выходы счетчика соединены с управляющими входами первого коммутатора, информационные ВХО11Ы первой груцпы которого соединены с информационными входами преобразователя, выходы которого соедих е«ы с выходами блока триггеров, о т л и ч а ю щ и и с я тем, что, с целью повышения быстродействия, он содержит второй коммутатор, кольцевой счетчик и группу элементов НЕРАВНО- ЗI-1 ШOCTЬ. причем вход установки .начального состояния преобразователя соединен с входами сброса счетчика и блока триггеров и входом разрешения записи кольцевого счетчика, выход которого соединен с управляющим входом второго кoм rs тaтopa, выходы ко-- торого соединены с информационными входами с первого по 2 -й блока триггеров, информационные входы с ( т1) по 2 -и KOTOpoi o соединены с выходами элементов НЕРАВНОЗНАЧНОСТЬ группы, входы которых соединеныны попарно с выходами первого коммутатора , информационные входы второй группы которого соединены с выходами блока триггеров, тактовый вход которого соединен с входом синхронизации преобразователя, входами синхронизации счетчика и кольцевого счетчика 5 информационные входы которого соединены с настроечными входами преобразователя, информационные входы второго ко1У1мутатора соединены попарно с выходами первого коммутатора,

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

Редактор А, Ворович

Составитель О. Березикова

Техред М.Дидык Корректор С. Черни

Заказ 4224/40 Тираж 670Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, , Раушская наб,, д. 4/5

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

ра, остальные входы i-ro мультиплексора соединены с 1-м информационным входом второй группы коммутатора, i-й выход которого соединен с выходом i-ro мультиплексора, управляющие входы которого соединены с управляющими входами коммутатора.

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

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