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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (19) !11) 5 А1 (50 4 06 F 15 31

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ д " д

H ABTOPCHOMY СВИДЕТЕЛЬСТВУ ЬКЬЛ ;1.. (54) ФУНКЦИОНАЛЬНЫЙ ПРЕОБРАЗОВАТЕЛЬ (57) Изобретение относится к автоматике и вычислительной технике и пред— назначено для механизации ручных методов синтеза логических схем в авто(21) 4059721/24-24 (22) 22.04.86 (46) 23.09.87. Бюл. Nl 35 (71) Днепропетровский государственный университет им. 300-летия воссоединения Украины с Россией (72) Л.М. Голобородько и В.А. Пащен— ко (53) 681.3(088.83 (56) Ф. Саллерс. Методы обнаружения ошибок в работе ЭВМ. M. Мир, !972, с. 202.

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

Р 781822, кл. G 06 F 15/31, 1978. матизированных системах проектирования. Цель изобретения — повышение быстродействия. Устройство содержит счетчик 3, первый .коммутатор 4, блок 7 триггеров, второй коммутатор 6, группу 8 элементов НЕРАВНОЗНАЧНОСТЬ, кольцевой счетчик 5, информационные входы 1, выходы 2, вход синхронизации 9, вход 10 установки начального состояния и настроечные входы 11. Устройство позволяет вычислить коэффициЮ енты полинома Зегалкина за ll тактов.

2 з.п. ф-лы. 1 ил.

1339 183

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

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

На чертеже показана структурная схема функционального преобразоватепя.1П

Функциональный преобразователь содержит информационные входы 1, выходы 2, счетчик 3, первый коммутатор 4, 11 1 ) содержащий 2 мультиплексоров 4 -4

9 кольцевой счетчик 5, второй коммута-тор 6, содержащий 2 мультиплексоров 6 -6, блок триггеров 7,...97 группу из 2 элементов НЕРАВНОЗНАЧ—

НОСТЬ 8, вход 9 синхронизации, вход 10 установки в начальное состояние и настроечные входы 1!. .Рассмотрим реализуемый данным устройством алгоритм вычисления коэффициентов полинома Жегалкина, где каждая переменная входит или непосредственно, или с инверсией.

Пусть задана булева функция своим вектором истинности Г = (1,....,Г ), О9 92,19 где fJ может быть или нулем, или единицей (j = 0,1. ..2 " " ). Произволь- 30 ная булева функция представлена полиномом Жегалкина следующего вида:

1

Г(х 9 ° 9х ) Q Р(К 9

Kh К KO К,=O:

К )х, ... х,, (1) где 1 — знак суммы по модулю два, х. или х., или x i =(l, n), а ! 1 х, = 1, если К; = О. Величины к;

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

Чтобы получить вектор коэффициен— тов Р(К,...,К,) необходимо вектор Г умножить на п êðàòíîå прямое (кронекерово) произведение матрицы

О

О и, О О

О h h

1 О О

О 1 1

А (h ) О О

О О

h;

О О

О О

О О

1 1

О О

О О

О О

О О

О О

О О

О О

1 1, h; О 0

0 0 h, h

0 О О О

0 О О О

1 О О

О О 1 1

О О О О

О О О О

А,{h ) При и = 2 умножение вектора значе25 ний функции Г(х,...,х ) на 2 — кратное произведение матрицы A (h ) запи2 1 сывается так:

h Ь.; 0 011

О О h, Ц

О О 1 1 (0,0) (0,1)

Р (1,0)

F (1,1) 11; h10 0

0 0 hi h1

1 0 О

О О 1 1

Это соотношение можно представить как систему из четырех следующих ра— венств, записанных в скобочной форме:

F (0, 0 ) — (:Ã Ь 01 h ) }i,Оф, h 0+ b h } Ь

F(0, 1) = (-i,0 ) Ь,в(Г,ЯГ,) }, (3)

F(1,О) = (g h„(31, h„)0+If }1,0+2 h,)

Р(1, 1) = l .I ОГ,) 9 (Г O+ i ) .

40 Для n = 2 алгоритм функционирова;ния данного устройства определяется системой равенств (3).

Данное устройство позволяет вычислять коэффициенты полинома Жегалкина

45 за и тактов функционирования путем умножения вектора значений функции

f (х,...,х,) на и-кратное обыкновен—

1-1 ное произведение матрицы А (Ь ), Требуемый вид полинома Жегалкина

50 задается величинами h„,...,h храни— мыми в кольцевом счетчике 5. Величина h.(i. =- 1,h) равна единице, если соответствующая переменная х инвер-! тирована, и тождественна нулю — в

55 противном случае. (2) рассматриваемой при i = 1,.„.,п. Если переменная х. не инвертирована, то

h. = О, в противном случ- h = 1.

С целью нахождения и-кратного прямого произведения Н матрицы (2) можно воспользоваться следующим рекуррентным соотношением: где Н вЂ” м»триц» р»змером 2 x 2", 1-i -1 являющ»яся (и-1)-кратным кронекеровым произведением матрицы (2).

Кроме того, вектор коэффициентов

F(K,...,Ê ) можно получить как результат у."1ножения вектора f на и-кратное обыкновенное произведение матрицы

А,(h,). .При и = 2 и и = 3 матрица А

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

Н

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

1339583

11о«тупление импульса ня вход .0 устанавливает триггеры 7,-7, и счетчик 3 в нулевое состояние, я также обеспечивает запись в кольпевой счетЬ чик 5 п-ðàçðÿäíoão двоичного кода

h,...,}1, присутствующего на входах 11.

На вхо, 1 — 1„ функционального

1 преобразователя поданы соответственно .0 значения Г,, Г,, Г, Г булевой фун— кции, которые присутствуют в течение всех n = 2 тактов.

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

Это позволяет получить на выходах

4 -4 1 ct торые тождес Гвснн1 1 ве:1ичиня"., прис т- 20 ствующим ня их 11ервых инфорьмяцио11ных входах.

Значеиие }1 с выхода кольцевого ! счетчика 5 через управляюг1ий вход второго коммутатора 6 подается ня адрес— ные входы мультиплексоров 6,. и 6

Благодаря этому на выходях мультиплексоров 6 „ и 6 присутствуют зня— чения (:чпчГ h ) и (Г hvf } ), О 1 2 1 3 тождественные (Г }т +f г, ) и (Г& .+-"з h 30 о 1 1 1 > 1 3 соответственно.

В алгебре логики имеет место следующее тождество хну = х©о ху, которое в данном случае записывается сле— дующим образом:

ЗВ

Г4чfh = fhD+f } V h-,h. (4)

Р 1 1 1 О 1 о 1 11

Поскольку h h„= О, вь1ряжение (4) можно представить тяк:

f h,Vf. h, = Х }1 „Я Г„-h.„.

В результате на входах триггеров 7, и 7 имеем соответственно величины

О 1 1 1 >> 1;> 1

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

8 — поступают значения (f Q+f, ) и (f< fz) соответственно.

По окончанию такта на выходах

2, †.2 преобразователя, а следовательно, и ня вторых информационных входах мультиплексоров 4 -4 хранятся ! 4 соответственно значения (f, h„O+f, h,), t.Г,},ОГ,п„1, .-&)f,1, } Г,ОГ,3.

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

В результате на выходе кольцевого счетчика 5 содержится величина h >.

На выходах счетчика 3 имеем кодовую комбинацию 01, которая обеспечивает подк.но 1«н1l к выходам мультиплек—

co})o в 4 4 их В торьlх инфор11аци онньlх .> входов. Б результате на выходах 4, -4 мульт11плексорои имеем величины (".. 1,РГ, 1-,, 1 . „}1,1,1 1 h }, (Г„C7f 1, :,Я.", 1 соответствсHHo.

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

Это позволяет аналогично описанному в первом такте подать значения («f h O.: h !!т 11(:" }1 0+ h,)h ) и ((Г Q:",) h <9(f Я, )h с выходов мультиплексоров 6, и 6 1 на входы триггеров 7 и 7„ соответственно.

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

8 подяютс» зиа1сния 1 Г h(+3Г h )O+

О - я- 3 > 1 1 1

„:. 0, . 1п L О )О(0

По окон-анин такта на выходах 2 -2,, t преобразовят«.1я имеем соответственно в- 11ич>111ь!, 1 ЯГ h 1 11 (+ХГ }м()f>htjh<), ответствует системе равенства (3).

}аки1 образом, преобразователь вы-И1сляет коэфф1 гп1енты полинома Жегал— кина. за г тактов ф o p ì ó 1 а и з о б р е т е н и я

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

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

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

Редактор A. Ворович Техред М,Дидык Корректор С. Черни

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

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

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

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

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

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

3. Преобразователь по и. 1, о тл и ч а ю шийся тем, что второй

ts -! коммутатор содержит 2 мультиплексоров, причем информационные входы j-го г -1 мультиплексора (j = 1,2 ) соединены с (2, — 1)-м и 2„-м выходами первого .коммутатора, управляющие входы мультиплексоров соединены с управляю— щим входом коммутатора, )-й выход которого соединен с выходом j-го мультиплексора.