Устройство для арифметического разложения логических функций
Иллюстрации
Показать всеРеферат
СОЮЗ СОВЕТСНИХ
СОЦИАУ1ИСТИЧЕСНИХ
РЕСПУБЛИН
„„SU„, 1633388
А1 (51) 5 Г 06 & 5<(00, 7!00
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Щ2. t
ГОСУДАРСТВЕННЫЙ НОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ
ПРИ ГННТ СССР (21) 4670<>90<?4 (22) 30.03.89 (46) 07.03.91. Лг>.-г. " 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! Вхoil10 — импу. гьс, по зл! 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з