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

 

ПРЕОБРАЗОВАТЕЛЬ ФОРМЫ ПРЕДСТАВЛЕИШ ЛОГИЧЕСКИХ ФУНКЦИЙ, содержав ий счетчик, группу элементов И, группу счетных триггеров ,0тл и чающийся тем, что, с це-. лью повышения быстродействия, в него введены элементы И,демультиплексор , регистр, элемент НЕРАВНОЗНАЧНОСТЬ , причем информационный вход преобразователя соединен с первым входом элемента И, выход которого соединен с информационным входомдемультиплексора , выходы разрядов счетчика соединены соответственно с адресными входами демультиплексора, выходы которого соединены с информационными входами соответствующих разрядов регистра, первый выход которого соединен с первым входом элемента НЕРАВНОЗНАЧНОСТЬ, а остальные

28 А

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

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

РЕСПУБЛИН (1О> (11

4(5l) (06 F 15/31 °

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

ГЮ ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTMA (21) 3574626/24-24 (22) 04.04.83 (46) 30,06.85. Бил, Ф 24 (72) В.IO.Ларченко, M.Ф,Холодный, Н.Г.Коробков и К.К,Фурманов (7 1) Харьковский ордена Ленина авиационный институт им. H.Е.Жуковского (53) 681.32(088.8) (56) Авторское свидетельство СССР по заявке 1Р 3546096, кл, G 06 P 5/00, 1983.

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

И 781822, кл. G 06 Р 15/31, !978. адресными входами демультиплексора, выходы которого соединены с информационными входами соответствующих разрядов регистра, первый выход которого соединен с первым входом элемента НЕРАВНОЗНАЧНОСТЬ, а остальные (2" — l) выходов — с первыми входами соответствующих элементов И группы, Ч-вход первого счетного триггера соединен с шиной логической единицы,. Ч -вход i -то счетного триггера группы соединен с выходом (i — 1) -го счетного триггера группы . ф 2,2" -1), выходы счетных триггеров группы соединены с вторыми входами элементов И группы, выходы которых соединены с соответствующими входами элемента НЕРАВНОЗНАЧНОСТЬ, тактовый вход преобразователя соединен с счетным входом счетчика, Т вЂ входа счетных триггеров группы и с вторым входом элемента И, вход начальной установки преобразователя соединен с установочными входами счетчика, счетных триггеров группы и регистра, выход элемента

НЕРАВНОЗНАЧНОСТЬ соединен с выходом преобразователя. (54) (57) ПРЕОБРАЗОВАТЕЛЬ ФОРЖ1 ПРЕДСТАВЛЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ, содержащий счетчик, группу элементов

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

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

728 2

Например, матрица S имеет вид

1 164

) 1110000

l1003lOO

И)11111

$ х 3 в СДНФ им ет вид. (o}

-о"-11 с ким о бразом, имее

Та

В устройстве используются стандартные функциональные блоки, промышленно выпускаемые в виде интеграль. ных схем. а а, д ) 1) °

И- I и-tS S

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

На чертеже представлена структура предлагаемого устройства.

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

8 устройства, выход 9 подачи тактовых импульсов, вход 10 начальной установки устройства, выход 11 устройства.

Устройство работает следующим, об30 разом, 1, Как известно, коэффициенты а, — а полиномиальной формы представлейия логической функции

1 х )=а,са,х,Оа,Х,Оа,Х,Х,О 8а „,х,...х„ могут быть получены из коэффициентов й(„) = f (О)... ) О), Е(„) х f (1) 0, ° . .О)..., Й(Е(1,...,1) совершенной дизъюнктивной нормальной формы. (СДНФ) той же40

n . ° "в

2 1 . функции f (Х) =, f() х1х2 ° хл ! 1=0 следующм образом:

Для и О матрица S S 1. Матрица

S для и переменных образуется из

ll - 1 матрицы S для и-1 переменных по следующему правилу:

SA1 О

Иатрица (8"), обратная матрице

S, совпадает с самой матрицей S т.е. (S") S, поэтому обратное преобразование формы представления логической функции f(Õ) из полиномиальной формы Ъ

Уп 1 2"- а, =, 8„) 1,) <(,, ;K 8;; ) =о,, ) j «о где 8; - элемент матрицы S".

Так как 813 -О при j>it то дйя вычисления а; необходимы лишь первые

i коэффициентов й()) СДНФ функции и наоборот, для вычисления коэффициента f (i) СДНФ функции необходимы лишь первые.i коэффициентов а полиномиальной формы.

2. Покажем, что управляемые триггеры, соединенные между собой таким образом, что выход каждого предыдущего триггера соединен с управляющим входом (V-входом) последующего триггера, на управляющий вход первого триггера подана логическая единица, счетные входы. (Т-входы) триггеров соединены между собой и подключены к входу подачи тактовых импульсов и все триггеры в исходном положении находятся в нулевом состоянии, в каждый тактовый момент времени t формируют на своих выходах потенциалы, соответствующие элементам t-й. строки матри,.цы S" (О it = 2"-1) .

Обозначим состояние j-ro триггера (1 j 2"- 1) в такте t через

g1(t). TV-триггер функционирует в соответствии с уравнением g(t+3) =

=T(t)V(t)9Q(t), поэтому для нашего случая имеем Я (+1)хТ(й)Я q(t) О+

g+ Я1 ().

Отсюда получаем следующие значения g1(t):

1164728 а () 2 3 4

0 0

0 .

0

0

4

2 -1

2

0

Таким образом, состояние j-го триггера в такте t соответствует элементу S< матрицы $ . Так как при

1 любом t элементы Б тождественно равны единице, то рассмотренная схема из управляемых счетных триггеров формирует в такте t потенциалы, сои ответствующие t-й строке матрицы. 8

3, Исходное положение устройст.ва, обеспечиваемое подачей сигнала

"Начальная установка устройства" на вход 10 устройства, следующее: триггеры 3 находятся в единичном состоянии, счетчик 1 и все ячейки

30 регистра 6 находятся в нулевом состоянии

3. 1. Преобразование формы представления логических функций из 35

СДНФ в,полиномиальную.

Рассмотрим работу устройства в паузе между t-I-м и t†- м тактовыми импульсами. Счетчик 1 находится в состоянии t. На выходах триггеров .3 сфор-40 мированы потенциалы, соответствующие

t-1 -й строке матрицы $", Низкий потенциал с входа 9 устройства поступает на один из входов элемента И 4 и формирует на его выходе низкий по- 45 тенциал, который поступает на управляющий вход демультиплексора 5 и формирует на его выходах низкие потенциалы независимо от состояния его адресных входов, что обеспечивает реяым50 ,хранения информации для регистра 6 .

При этом в первых t 1 ячейках регистра 6 хранятся соответствующие коэффициенты СДНФ, а в остальных ячейках — нули. На выходе 11 устройства . у сохраняется потенциал, соответству- ющий 1 -I-му коэффициенту полиномиальной формы. На вход 8 устройства 7 . °, 2 — 2 I 2 1 подается потенциал, соответствующий . -му коэффициенту СДНФ, С появлением высокого потенциала на входе 9 устройства (т.е. с йрихо- дом t-ro тактового импульса) состояние счетчика 1 не изменится, а на выходах триггеров 3 сформируются потенциалы, соответствующие й-й строке матрицы $ ..Если иа информационном и входе 8 устройства находится низкий потенциал, то на выходе элемента И 4 формируется низкий потенциал, который, в свою очередь; приводит к формированию низких потенциалов на выходах демультиппексора 5, что обеспечивает режим хранения информации в регистре б„ Это эквивалентно записи в t-ю ячейку регистра 6 нуля. Если иа вход 8 устройства подан высокий потенциал, то на выходе элемента И 4 формируется высокий потенциал; который подается на информационный вход демультиплексора. 6 на адресные входу которого подаются сигналы с выходов счетчика 1. При этом на й-м выходе демультиплексора 5 формируется высокий потенциал, который подается на й-й установочный вход регистра 6 и формирует Hà его tM выходе высокий потенциал, что эквивалентно записи в ячейку регистра 6 единицы. Следовательно, по переднему фронту t-ro тактового импульса в t-ю ячейку регистра 6 заносится t-й коэффициент

СДНФ и, таким образом, в первых ячейках этого регистра хранятся первых

t коэффициентов СДНФ.

Сигналы с выходов триггеров 6, соответствующие элементам й-Й строки матрицы $, и сигналы с выходов

1164728 регистра б, соответствующие первым

t коэффициентам СДНФ, логически перемножаются на соответствующих элементах И 2. Полученные произведения суммируются элементом НЕРАВНОЗНАЧНОСТЬ 7 и вычисленное значение

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

По заднему фронту данного тактового импульса на выходе элемента

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

3, а счетчик 1 переходит в +1-е состояние.

Таким образом, в такте на вход устройства 8 подается коэффициент

f(t) СДНФ функции f(X), а на выходе

11 устройства формируется коэффициент а полиномиальной формы представления этой же самой функции.

С подачей 2" тактовых импульсов

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

СДНФ в полиномиальную форму за. канчивается, 3.2. Преобразование. формы представления логических функций иэ полиномиальной формы в СДНФ, В этом случае устройство работает так же, как и в предыдущем случае. Отличие состоит н том, что в такте t на вход 8 устройства подается коэффициент at полиномиальной .формы представления логической функции f(X), а на выходе 11 устройства формируется коэффициент

20 f(t) СДНФ той же самой функции.

1164728

Заказ 4188/46 Тираж 210

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

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

«

«Я

Филиал ПШ1 "Патент", г, Ужгород, ул,. Проектная, 4

Подписное

Составитель И.Пчелинцев

Редакто Л Ав д р . враменко ТехредИ.Гергель КорректоР Е.Снрохман ю