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

 

Союз Советских

Соцналистнчвсных рвсяублмн

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ iii 957217 (6l ) Дополнительное к авт. санд-ву— (22) Заявлено 3 . 2. 80 (2! )3228988/!8-24 с присоединением заявки,йе— (23) Приоритет—

Опубликовано 07. 09. 82. Бюллетень М 33

Дата опубликования описания 07.09.82 (53)N. Кл.

G 06 F 35/3!

9кудэратееллый комитет

СССР вю делам изебретеннх и отхрытн!! (53) УДК68!.325 (088.8} (72) Авторы изобретения

Э. В. Лысенко, И.Т. Скибенко, В.А. Дергачев и В.Ф. Огородов (7! ) Заявитель

Харьковский ордена Ленина авиационный институт им. Н. Е. Жуковского

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

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

t0

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

tS

Наиболее близким к предлагаемому является функциональный преобразователь, содержащий вход исходных данных, выход результата, двоичный счетчик, мультиплексор, преобразователь кодов, блок формирования результата причем вход исходных данных соединен с информационными входами мультиплек- сора, выходы двоичного счетчика сое2 динены с управляющими входами мультиплексора и с входами преобразователя кодов, выходы, преобразователя кодов соединены с информационными входами блока формирования результата, выход мультиплексора соединен с управляющим входом блока формирования результата, выход которого образует выход результата t2).

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

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

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

Значение выходной информации в шине результата соответствует значениям

1 коэффициентов А„ следующим образом:

1"й группе разрядов выхода 2 ставится. в соответствие и-разрядное двоичное число, соответствующее десятичному эквиваленту числа 1- 1 (так как нумерация выводов идет с номера "1"). В рассматриваемом двоичном коде К переменных входят в прямой форме и (и- К) в инверсной (К = О, n}. Значение сигнала "1" на 1- и группе разрядов выхода 2 соответствует вхождению в канонический многочлен конъюнкции из К букв, входящих в двоичный код в прямом виде, например, для п=3 получаем„, Ф

Вывод

000

Х3 х хх

Х1 хх

X„X, 113

001

010

4

5 б

011

100

101

110

3 95721 код канонического многочлена и блок формирования результата, информационный и управляющий входы которого соединены соответственно с выходами преобразователя двоичного кода в код канонического i 5 йногочлена и мультиплексора, управ.ляющий вход которого соединен с выхо. дом разрядов первого счетчика, информационный вход мультиплексора соеди-! нен с входом преобразователя, выход ФО которого соединен с выходом блока формирования результата, дополнительно введены блок сумматоров по модулю два, второй счетчик и генератор импульсов, выход которого соединен 15 со счетным входом первого счетчика. выход переполнения .которого соединен со счетным входом второго счетчика, выход разрядов которого соединен с первь|м входом блока сумматоров по мо-.20 дулю два, второй вход которого соединен с выходом рязрядов первого счетчика, выход блока сумматоров по модулю два соединен с входом преобразователя двоичного кода в код каноничес- 25 кого многочлена.

На, чертеже дана блок-схема, устройства.

Устройство включает вход 1 преобразователя, выход 2 преобразователя, 36 счетчик 3, мультиплексор- 4, преобразователь 5 двоичного кода в код канонического многочлена, блок 6 формирования результата, блок 7 сумматоров по модулю два, счетчик 8 и генератор. 9 импульсов.

Рассмотрим назначение элементов схемы.

Вход 1 (исходных данных) имеет 2" разрядов. Исходная логическая .Функция задается в виде таблицы истинности. Значения функций на двоичных наборах подаются на соответствующие разряды входа 1 (исходных данных}, значение Функций на 1-м наборе пода- 45 ется на i+1 разряд входа 1.

Выход 2 (результата) имеет 2 разрядов и предназначен для выдачи рет зультата. Канонический многочлен в общем случае имеет вид

Г(Х„, Х,...,X„) = А Q+A„X„Q+

Х Q+...A

Если на выходе 2 двоичный код

l0l001101, это соответствует каноническому многочлену вида

Двоичный код Соответствую щая конъюнкция

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

Счетчики 3 и 8 обеспечивают подсчет поступающих на его вход импульсов. В данном преобразователе применен счетчик суммирующего типа и может быть выполнен по любой известной схеме для формирования и- разрядного двоичного слова, соответствующего количеству поданных на его вход импульсов. йультиплексор 4 имеет и управляюIl щих входов, 2 информационных входов, 5 9572 один выход и предназначен для выбора соответствующего разряда из информационного двоичного кода на основании управляемого двоичного кода и выдачи его значения на выход мультиплексора.

Преобразователь 5 двоичного кеда в код канонического многочлена со3 .; n — К держит и элементов НЕ и,г Сп эла- 16 ! к=2 ментов И, входы которых соединены с выходами элементов НЕ, выходы эле.ментов И являются выходами преобразователя, входами которого являются !s входы элементов НЕ.

Блок 6 формирования результата предназначен для хранения и сложения по модулю 2 промежуточных многочлеll и нов и содержит 2 -1 элементов И и 2 щ триггеров, причем входы элементов И соединены с управляющим входом и соот ветствующими информационными входами.

Блок 7 сумматоров по модулю два предназначен для инвертирования 2З сигналов, поступающих с выходов,. первого счетчика, в соответствии со значениями сигналов, поступающих с второго счетчика. Если обозначить сигналы первой группы входов o,,вто-за рой группы входов Ъ, то выходной сигнал описывается логической функцией и 1„О+Ъ;, j=! n.

В основе работы устройства лежит тождественное преобразование вида

1(Х,,Х2,,X„) f (X, Х,...,X;, ...Х„) .

3f 40

Обозначим Х; через, Х, тогда получаем т(Х, Х,...,Х„,...,X„). Это приведет к преобразованию исходной таблицы истинности и в общем случае к различному виду канонического многочлепа. Для и входных переменных суще .=вует 2" возможных инверсий входных переменных. Номера инвертируемых пер=.менных генерирует второй счетчик

8., Если сигнал на его выходах 00...0, то схема работает, как прототип.

Устройство работает следующим об- . разом.

Значение исходной функции на всех двоичных наборах (в порядке возрастакия номеров) подается на вход. Счетчик 3 формирует последовательность двричных наборов. Эти наборы преобразуются в соответствии со значением!

7 d выходных сигналов счетчика 8 е новые наборы в блоке 7. Для каждого из них в преобразователе 5 определяется вид промежуточного многочлена. Если на рассматриваемом наборе исходная функция принимает значение "1" (сигнал на выходе мультиплексора 4 равен."!"1, то промежуточный многочлен записывается в блок 6 формирования результата, где производится его суммирование по модулю два с результатом предыдущего суммирования (в исходном состоянии содержимое триггеров ОО ° ..О). По окончании 2" тактов на выходах блока 6, образующих выход 2, получаем результат преобразования.

Этот процесс повторяется для различных значений выходных сигналов счетчика 8, полученные результаты сравниваются с целью выбора лучшего по заданным критериям. Например, критерий минимального числа букв соот-. ветствует минимальному числу интегральных микросхем при построении схемы по каноническому многочлену.

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

Функциональный преобразователь, содержащий первый счетчик, мультиплексор, преобразователь двоичного кода в код канонического многочлена и блок формирования результата, информационный и управляющий входы которого соединены соответственно с выходами преобразователя двоичного кода в код канонического многочлена и мультиплексора, управляющий вход которого соединен с выходом разрядов первого счетчика, информационный вход мультиПлексора соединен с входом преобразователя, выход которого соединен с выходом блока формирования результата, отличающийся тем, что, с целью расширения класса решаемых задач за счет возможности воспроизведения различных вариантов представления логических функций в виде канонического многочлена, в неСоставитель А. Зорин редактор А. Мотыль Техред С.Мигунова .Корректор

Д. Бокшан

Тираж 731 Подписное

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

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

Заказ 6600/38

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

7 957217 го введены блок сумматоров по моду- разователя двоичного кода в код канолю два, второй счетчик и генератор нического многочлена. импульсов, выход которого. соединен Источники информации, со счетным входом первого счетчика, принятые во внимание при экспертизе выход переполнения которого соединен 5 1. Авсаркисян Г. C Брайловссо счетным входом второго счетчика., кий Г. С. Представление логических выход разрядов которого соединен с функций в виде полиномов Жегалкина. первым входом блока сумматоров по - "Автоматика и вычислительная технимодулю два, второй вход которого со- . ка", 1975, К 6, с. 6-10. единен с выходам разрядов первого >4 2. Авторское свидетельство СССР счетчика, выход блока сумматоров йо по заявке 11 2719920/18-24, модулю два соединен с входом преоб- кл. G 06 F 15/31, 1979 (прототип).