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