Устройство для арифметического разложения логических функций

 

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

СОЦИАУ1ИСТИЧЕСНИХ

РЕСПУБЛИН

„„SU„, 1633388

А1 (51) 5 Г 06 & 5<(00, 7!00

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Щ2. t

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР (21) 4670<>90.-г. " 9 (72) Х!.Fi.Лвгуль, В. И. Суирун, В.!!. Костене«>«п! и !!.Л.!.гор<>В (53) F>R1.3(0RR,R) (56) ухлрев .Л., трог«»пико Л.!()., 1 !«яерко R,!1. С><стог!и е- к!ip. »polr<.с—

cnph! для обработки <:иг»лл в. — . !инск, 19RR, с. 102 — t 05, рис..4. <. 1

Лвторско< CJ!Jl;I< т«,JJ ств< (.(:0p

М 1 20351 1, ! . Г 06 7/38, 19R « . (54) УСТ!>ОС!СтБ(1;(г!!! Лр!!<«Ф!!.ТИ

РЛЗЛОЖЕ!!ИЯ ЛОП(У(!Е!(И! (.>7) ИЗОбр ЕT p JIJIC от И<,сптС я К F

---

использовано для построения 3Г!! и спецпро«\pcñорoв с сисTp«r<>J< к< млид выcокоГО >jpоВ»я орис<«тнpовл>!«««Jx lr J к. «ассы ре«<«аем«>х злллч. !(ель lr «Г>р<.те»ия расг<«ирение облл- и испсг(F,çorçërrr!JJ. устр ойс т Во для ариА«<ети>! еского ра зложепия логических <унк«цгй! JJ »времен»ых содержит с « Jlr J., l, дог>и< >рлтор 2, >> ! элемент И 3, ? — 1 ком;J>i г1T<>p< ч1 типа И-ИЛИ, триггер 5, 2 — 1, регпст, и ров б, 2 " вычитателей 7, три упг< рав««яюг<иx входа R-1(1,:? ии<>ормацион— ных Входов 1 1 . Устр ойст во работа ет следуюг(иг! образом. !!л и««Аор<: ) — I „блиlrà истинности рлзплглемой логической Ау««кции и пере««енных V, «Jo пер— вый уира вляюг!ий вход 8 подается им»у .ьс, по задке, гу Лр<»<т . коорого происходит оби,ление C <етчикл, на вгорой управляюг!«««! Вход 9 — и«!пуг«ьс, переводя!<(««(! счс чик В < !вредное состояниp Jr<) тpEтий $JTpлвляю(!«JJ! Вхoil

10 — импу. гьс, по зл! Jl< «г Лро»ту кото2 рого происходит запись и««формации в триггер > и в регrrcFphr б. После вь«полне««ия и такт«FJ работ«! устройства В триггере 5 Jr ? — 1 регистрах 6 будут з аписа ны ко.> 1>ицис «гты з ри<1>ме т ич сс кого Jr or! «!»Р."«л .»о гине с F;o Ji Av«JK !!Jr«r

4 ил., табл .

1633388

K -О х если (, = 1, 1

1, если ок, = О, и, ро + 8«x + р х + -1

/а(с) / 2 °

45 х = 1 — x; х y У хну = х+ у — x ° p

x y=x+y — ?xy

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

Цель изобретения — расширение области использования за счет возможности ариАметического разложения логических Аункцнй.

На фиг,1 представлена структурная схема устройства для ариАметического разложения логических Аункций при

n = 3; на Аиг.2 — Аункциональная схе- 15 ма первого коммутатора при п = 3; на фиг. 3 — Аункциональная схема второго коммутатора при п = 3;на Аиг.4 — операционный rpaA алгоритма ариАметического разложения логических функций для рассматриваемого примера.

Ус тр ой ст во (Аиг . 1 ) содержит сч етчик 1, дениАрлтор 2, элемент И 3, 2 — 1=7 коммутаторов 4 «-4 у, тригг ер и Ь -1

5, 2 — 1=7 регистров, 6„-6т, 2 = 4 25 вычитателя 7 « — 74, вход 8 разрешения обнуления, вход 9 разрешения счета, тактовый вход 10, ? = 8 информациони ных входов 11 « — 118 .

Первый к оимут а тор (Аиг . 2) с одержи т 30 четыре элемента ?1-И11И 17 « — 17.4, п +

+ 1 = 4 упрлвляю1(их входа 131 — 134, три группы инАормационных входов

14 « — 144, 15 « — 15,, и 16 « — 16г и четыре выхода 17 « — 174.

Второй коммутатор {Аиг.3) содержит четыре элемента И 18 « — 184, элемент

И-ИЛИ 19, элемент HF. 20, управляюг(»гй вход 21, инАормлционный вход 22, группу инАорилционных входов 23 »

24<> пять выходов 24 1 — 24>, Принцип работы устройства основан на замене логических операций ариАметическими.

Очевидно, имеет место где х, уЕ10,1)

Если в некотором выражении логической функции К сделать замену логических операций ариАметическими согласно (1), то после приведения подобных членов получаем лриАметический полином Г{F) Аункции F.

В общем случае для логической функЦии n HepeHeHIIhlx F = F (х,, х ...,x„) ариАметический полинои имеет вид

2"- < и ("(Р) = ; р»(° ) ) х (2) где 1. (К) = { сК1, uK<...., I-K 1 и-разрядный двоичный эквивалент числа К,т. е ï п-.1

К = (,K 7: для любой

1 =1 переменной x ° (i = 1, 2,...,n) имеет место

g(F) = (р р1 ... 8äï. I3 вектор коэфАициентов лриАиети 1еског и полннома .

Как следует из <7), полинои (:(F) при п = 3 имеет вид

+ 8 x x + p x1 + 8 x x +

Рбхгх Ггх х хз

Следует также отметить, что р„E 0,1j, а конъюнкция ранга I: (г — 1, 2,...,и) имеет коэААнциент л((), для которого спрлвед гидо

Кроие того, нетрудно устлнов»гть,,и

2-1 что ? р; = F =- (1,1...1) н Р, ?.=о

g; (mod 7), где Р; — коэд»Аиг(иРнт

i-го слагаемого пог1иномл 7(егллкинл

P(F) функции F u i = О, 1,..., 7."-1.

Исходным для нахождения вектор» коэффициентов лриАиетичecxol о п<1линома ((Г) логической Аунк пни

F (x 1 х ° ° е хп ) ЯВ11ЯРTcЯ РР тл1)1111 на истиннос ги (») (F) = ((д„(1,..., (1),,), где Я, — значение F нл i-»I

1633388 наборе значений переменных х<,-< х„и = 0,1,...,2"-1.

Метод нахождения вектора я (Г) заключается в следуюг<ем: п«злагаем,что

Н = (h<, hо,...,}< <«) =(«)(f ), формируем последовательность векторов, 2 И

Н,...,II, где ко<<поненть< нектоpB =- (h «, h2, .. «}l <«) Вьг<исляются

2> «2<« по формулам

1 <-<

h = h

2«

1 I - -< <-<

}1 =h }1 (2i i «1

И-< j -< где m= 2, i = 0,1,..., тогда Il = В(Г) .

Счетчик 1 имеет разрядность,рав- 20 ную r > 1о}; (п+1) Г, где п — количество переменннх рязлагяемой логической функции. Состояние счетчика определяется дешифратором 7., который преобразует позицг<онный двоичный код состоя в 25 ния счетчика в унитарный код Hë своем вь<ходе. Сигнал ня < -и (1 = 1, 2,..., п+1) выходе дешифряторя ? обеспечивав ет подключение с оотве Тс Tвую< р<х компое-< нент вектора II к входам регистров, 30 непосредственно запись в которые происходит в момент окон <я ния тя ктовь<х импульсов, подяюгп<хся H;l тактовьп< вход 10.

Триггер 5 и регистры 6 < — 67 служат

35 для хранения компонент векторов II (I = 1,2,...,п+1) . Поскольку h =Оп, ето для хранения этого компонента достаточно одного триггера, состояние которого в процессе работы не изменя- 40 ется . Занесение информации в триггер 5 осуществляется в начале работы устройства после обну.".ения счетчика 1 по заднему фронту первого тактового импульса, подаваемого на так- 45 товый вход 10 устройства. В качестве триггера 5 в устройстве может быть использован синхронный двухступенчатый D-TðHããåð. Компоненты векторов

Н > (кроме h<, ) представляют собой це— лые числа как полог<итpJlbíûå, т,.. и отрицательные, где < = 1,?,...,n

<1ля хранения в регистрах и вь<полнения операции вычитания компоненты

<< (j = 1 2,...,n; р = ? 3,...,? ) йредставляются в дополнительном коде, причем под знак отводится один разряд.

С учетом знакового разряда и соотношения (3) разрядность регистров для хранения результатов проиелуточнь<х вычислений и коэффициентов 8 будет равна п+1, бит,разрядность ре— гистра для хранения коэффициентов

g 2„— и+2 бит. Тяк, дпя рассматриваемого примера (и = 3, фиг.1) разрядность регистров 6 « — 6 равна 4 бит, разрядность регистра б — 5 бит.

Регистры строятся ня основе двух ступенчатых синхронных триггеров, запись информации в которые осуществляется по заднему фронту тактовых импульсов, подаваемых на тактовый вход 10.

Вычитатели 7 < — 7«< имеют разрядность, рави ю p;l çðÿä Hîñòè соответствующих регистров, подключаемых к их входам, прич с и в вычитании учаcTRуют все разрядь<, включая знаковый.

При этом элеи из знакового разряда блокируется (т. е. не используется), чем достигается автоматическое формирование дог<олнительного кода разрядности, начиняя с и ер ногo такта вычислений. Внчита тели комбинационные, параллельного типа.

Коммутаторы 4 < — 4z классические, типа И-ИЛИ. Ifx упрявляюгп<е входы соединены с соответствуюг<ими выходами дегп<фряторя 2, а инфо рмяционнне — с г«шкодами соответствуюгпгх регистровв и выпита тел ей . Подключение входон/вь<ходов коммутаторов следует из операционного графа алгоритма (фиг. 4) с учетом его и-тактовой реалии — « зации на одном столбце из 2 вычитателей. Соединение второй группы .информационных входов коммутаторов при разрешающем сигнале ня втором, третьем и четвертом выходах дешифраторя 2 (соответственно состояния счетчика 0...01...0...10,0...11) отмечено на фиг,1. Коммутаторы по управляющим входам являются (и+1) -канальными, канальность по информационным входам определяется разрядностью соответствую<цих регистров.

В качестве примера на фиг.2 представлена функционяльпяя схема первого .коммутатора 4, содеряаг<его четыре элемента И-IUIII 12 < — 17 (по числу разрядов регистра 6):n+1 4 управляющих входа 13 < — 13, на которые подаются соответственно сигналы

Ъ„,..., Ъ с выходов денифратора 2, где i (i = О, 1, 2, 3) — сигнал на (i+1) м выходе делифрятора 2, сооТветствуюг<ий состоянию i счетчика 1.

1633388 отсюда

+ 2 хлх2х ъ

35

45

Н

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

Н

При Ь = 1 к входам коммутатора

4 подключаются выходы 141 — 14, вычитателя 7; при Ь = 1 — выходы

15 — 154. нычитателя 73 при Ь z = 1

5 выходы 16 — 164 регистра 66. Выходы

17 — 174 коммутатора 46 соединены с информЛционными входами регистра 6 .

Коммута т орн 4 < — 4 g имеют а пал огичную структуру. Несколько отличается структура коммутатора 4 > (Аиг.3), поскольку вторая группа его инАормационных входов 23 < — ?3 < соединена только с выходами внчитателя 7, Управляющий вход 21 коммутатора соединен с первым выходом дешифратора 2.

При этом при Ь = 1 обеспечивается подключение инАормационного входа 72 первой группы к младшему разряду регистра 6, в которнй по первому тактовому импульсу заносится компонент

ОЭт вектора Н . При Ь, Ч Ь Ч Ь = 1 (что эквивалентно h = 1) вторая группа информационных входов ?3

23< подключается к выходам 24 < — 24> коммутатора, тем самым обеспечивая запись информации в регистр 6 т с выходов вычитателя 7ц по заднему Аронту второго, третьего и четвертого тактовых импульсов, подаваемых на вход 10.

Как следует из Аиг.2 и 3, запись вектора Я(Р) в регистры 6 < — 6> осуществляется таким образом,что компонент Я (с = 1, 2,...,7) записывается в младший разряд регистра 6, в остальные разряды которого записывают— ся нули, т. е. содеркимое регистра 6z равно (OOOQz, причем старший разряд регистра — знаковьп .

В качестве примера использования

Аормул (4) рассмотрим последовательность шагов для построения полинома

G(F) логической Аункции трех перем нных Г = F(xt, х, х ), заданной таблицей истинности Я(Р) = (О, 1, О, 1, 1, О, О, 1) .

В tàêîì случае имеем следующую последовательность векторов: н - (0,1,0,0,1-1,-1,,1)9 (0,1,0,0,1 -2, -1,7), g(F) = (О 1 0 О 1 -2, — 1,2) и

С(Г) = х з + х, — 2х,хз — х,х +

Операционный граА алгоритма ариАметического разложения логических

Аункций при и = 3 представлен на

Аиг.4. Вершини графа соответствуют выполнению операций вычитания. функционирование устройства основано на п-тактной реализации операционного графа алгоритма, причем на 1-м (j

1, 2,...,п) такте устройство преобразует вектор Н " в вектор Н>

Работу устройства рассмотрим подробно на примере etn построения при

n = 3 (Аиг 1).

На вход разрешения обнуления подается импульс, по заднему фронту которого происходит обнуление счетчика 1. При этом на первом выходе дешифратора 2 появляется сигнал логической единицы, разрешавг ий прием ин— формации в триггер 5 и регистры

6, -6 через коммутаторы 4, -4, с ин-формационных входов 11< — 118 устройства, на которые подаются соответственно компонептн СĄ— Я вектора зна— чений преобразуемой логической Аункции трех переменных. На тактовый вход

10 подается тактовый импульс, по зад нему фронту которого непосредственно значения 43Π— Я с информационных входов 111 — 11> у< тройства заносятся в триггер 5 и регистры 6 — 6 . Отметим, что в тригт ере 5 и регистрах

6 — 6 будет следующее распределени е и нформа ции:

5о "î "î "î 6, бо о 6

Л1 Л Л2 Л6 11з Лт Л htt (Ю ) (Иа) (ut) (Я ) (u ) (Z ) (1 з) (ò ) Очевидно, на выходах внчитателей

7 — 71 буду сАормированы н дополнительном коде соответственно кам-! поненты h,...,Л вектора Н

На вход 9 разрешения счета пода— ется импульс, переводящий счетчик 2 в очередное состояние (счетчик переходит из состояния О... 00 в состояние

0...01) . ° На втором выходе дешифрато1633388

Ь2 ббз 67з

Номер такта

Состояние

Состояние счетчика

63 6

6, бб

67 триггера

0903 0039

Ьо Ьо

6 3

03 "31 0991

I (4

0391

0001

Ь р

h(9991

0000

h70

0091

Ью

1111 (Ь, 1111

0991

0990

9000

0000 (Ьь

Ьт

h, 0939

0303 0091

z 2

Ь4 hy

0001

0331

h(10

Ь

0010

hhz

Ьг

0991 0000 0009 0001

1110 1111 з

Ь8

Ьт

Э 3

Ь4 Ь ра 2 появляется сигнал, разрешающий через коммутаторы 4 (— 4 7 запись компонент вектора H в регистры 6, 6> Непосредственно эта запись про5 исходит по заднему фронту второго тактового импульса, подаваемого на тактовый вход (О.

Распределение информации г, триггере 5 и в регистрах 6 (— 6 у следующее:

5 6(бг бз 64 6 66 67

1 (1 f ((I (Ьз Ьг h4 Ь Ь Ь6 Ь8

Далее работа устройства происходит аналогичным образом. На вход 9 разрешения счета подается очередной импульс, переводяк(ий счетчик 1 из состояния 0...01 в состояние 0...10.

На третьем выходе дег(ифратора 2 появляется разрешаюг(ий сигнал и по заднему фронту тактового импульса, поступившего с тактового входа 10, компоненты вектора Н заносятся в реги Z стры 6 „— 6 .

Распределение информации в триггере 5 и в регистрах 61 -6 т имеет вил

Работа устройства может быть также пояснена с помо((ьи приводимой „бли50 цы, в которой представлено содержимое регистр(6 1 -67 на каждом такте вычислений. Содержимое регистров фиксируется на момент окончания соответствующего тактового импульса, поступившего на вход 10 (эти импульсы поступают после установки счетчика 1 в очередное состояние 00, 01, 5 6, бг 63 64 65 66 67

С приходом третьего импульса на вход

9 разрешения счета счетчик 1 переходит из состояния 0...10 в состояние

0...11.На четвертом выходе дешиАратора 2 появляется разрешаюций сигнал и по окончании тактового импульса на тактовом входе 1О в регистры 6

6 будут записаны компоненты векто7 ра Н, которые и являются коэффициентами арифметическо(о полинома:

53 6(з бгз бз 643 63 3

Ьг h Ь4. h Ь6 Ьт h8 (go) (g1) (1г) (83 ° (g4) (83) (6) (7) Лри произвольном значении п устройство работает аналогично.

Таблица работы устройства для рассматриваемого примера:

Содержимое регистров

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

F = F(x<, х, x,,), у которой M (F)

Из таблицы следует:

1633388

go

gt = h?- = (0001)z = 1„,;

82 — h Ыоою а 01р

h, = (0000), = О„,;

К Ь5 (0 0 1 )Я. 1 1р 1 (1010)2 пр = — 2,о е

Г = гг = (1111) г 4оп

3 (1001)г „ = 1 8 (0010) 2 2 1о °

Тогда g(F) = (О, 1,0,0, 1,-2,-1, 2) . формула изобретения

Устройство для арифметического разложения логических функций, содержащее и вычитателей (п — количество переменных разлагаемой логической функции) 2п регистров, и коммутаторов и триггер, причем тактовый вход

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

35 разложения логических функций, оно с одержит счетчик, д енифрат ор, эл емент

И, дополнительно с (2п + 1)-го по п (2 — 1)-й регистров, с (n + 1)-го

l1 по (2 — 1)-A кпммутаторпв, с (п +

+ 1)-го по (?" ) выгитатепей, причем вход установки в "О" счетчика соединен с входом разрешения обнуления устройства, вход разрешения счета которого соединен с входом разрешения счета счетчика, выход которого соединен с входом деггифратора, выход которого соединен с управляю Гим входом 1 гo коммутатора (1 = 1, 2 " "— 1) и первым входом элемента ll, выход которого соединен с тактовым входом триггера, второй вход элемента И cîåäèíåí с тактовыми входами

i-го регистра, первый информационный вход устройства соединен с информационным входом триггера (1 + 1)-A информационный вход устройства соединен с первым информационным входом i-го коммутатора, выход которого соединен с информационным входом i-гп регистра, выход триггера соединен с входом вычитаемого первого вы гитателя, вход уменьшаемого которого соединен с выходом первого регистра, вход вычитаемого (j + 11-гп влгчитателя (j

1, 2" — 1) соединен с выходом

2 -го регистра, вход уменыяаемого (1 + 1) г о Внчитателя спРдггнен с Рьг ходом (2 j + 1)-гп регистра, второй информагГионный вход f -го коммутатпра (11 = 1, 2 " — 2) соединен с выходами j-го вычитателя и 21-го регистра, второй информационный вход (2 — 1)— го коммутатора соединен с вьгходом (2 )-го вычитателя.

n-(1633388

1 ао а, аг

©6 в, 1633388

h"1

hs

Заказ 617 тираж 400 Подписное

BHHHIIH Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Произв ьцственно-издательский комбинат "Патент", r, Ужгород, ул, Гагарина, 101

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

Редактор С.Пекарь техред М.Дидык Корректор Т.Малец

Й

9з