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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для преобразования формы представления логических функций и совершенной дизъюнктивной нормальной формы в полиномиальную и наоборот. Целью изобретения является уцрощение. Преобразователь содержит элемент И, демультиплексор, счетчик, регистр, .элемент НЕРАВНОЗНАЧНОСТЬ, первую и вторую группы элементов И. Упрощение преобразователя достигается за счет использования вместо триггеров элемента И, причем входы каждого I -го элемента И (1 i и ) соединены с теми выходами разрядов счетчика, номера которых совпадают с номерами единичных позиций двоичного разложения числа i . 1 ил. (О 416 ю ;о 00

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

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

РЕСПУБЛИК (5ц 4 С 06 F 15/31 с

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

13.: 13

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ образования формы представления логических функций и совершенной дизъюнктивной нормальной формы в полиномиальную и наоборот.

Целью изобретения является упрощение.

Преобразователь содержит элемент

И, демультиплексор, счетчик, регистр, .элемент НЕРАВНОЗНАЧНОСТЬ, первую и вторую группы элементов И.

Упрощение преобразователя достигается за счет использования вместо триггеров элемента И, причем входы каждого I --го элемента И (1 1 2"-1) соединены с теми выходами разрядов счетчика, номера которых совпадают с номерами единичных позиций двоичного разложения числа 1. 1 ил.

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21). 3788687/24-24 .(22) 06.09.84 (46) 07.07,86. Бюл. № 25 (71) Харьковский ордена Ленина авиационный институт им. Н.Е. Жуковского (72) Н.Т. Березюк, M.Ф. Холодный, В.Ю. Ларченко и К.К. Фурманов (53) 681.325(088.8). (56) Авторское свидетельство СССР

¹ 781822, кл. С 06 F 15/51, 1978.

Авторское свидетельство СССР № 1164728, кл. С 06 F 15/31, 1983. (54) ПРЕОБРАЗОВАТЕЛЬ ФОРМЫ ПРЕДСТАВЛЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для пре„„SU„;, 1242984 А 1

1242984

f, f(„ а, f о аг Для q =О матрица 5 =1. Матрица 5« для и переменных образуется из мати-< рицы g для и -1 переменных по следующему правилу.

5 О п о и-< бп-<

Матрица 6, обратная матрице 8 совпадает с самой матрицей 5, т.е.

5 = Ы, поэтому обратное преобразование формы представления логической функции 1(1<) из полиномиальной формы в СДНФ,имеет вид:

50 (ы,Ю <<„,«1 ... ид1 и,д1

О О О, ... О. О

1 О О ... 0

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

Ф

Цель изобретения — упрощение уст- !0 ройства.

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

Устройство содержит элемент И 1, демультиплексор 2, регистр 4, счетчик 3, элемент НЕРАВНОЗНАЧНОСТЬ

5, первую группу элементов И 6, информационный вход 7 преобразователя, тактовый вход 8 преобразователя, 20 вход 9 начальной установки устройства, выход 10 устройства, вторую группу элементов И 11 °

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

Известно, что коэффициенты à -a „, о 2"-< полиномиальной формы представления логической функции f(x)=a aa,х, ®

Яа х,Яа х,х Q +... Q а „, х,х ... х„ могут быть получены йз "коэффициентов fp=- f (О,...,О), f, =f (1, О,...,О), f(< и,> =f (1,...,1) совершенной дизъюнктивной нормальной формы

} 2" 1 (.СДНФ) той же функции f (õ)=, f . х х, 1 ...,хц следующим образом:

f(,, Э (г"-i)

Таким образом, имеем: где 5; — элемент матрицы 5 .

Так как5, = 0 при j ) i то для вычисления коэффициента а; полиномиальной формы необходимы лишь первые коэффициентов 1(} СДНФ функции, и наоборот, для вычисления коэффициента 1(;} СДНФ необходимы лишь пер< вые > коэффициентов а полиномиаль3 ной формы.

Покажем, что группа элементов И, в которой входы < -го элемента И (1 (2 — 1) соединены с выходами тех разрядов счетчика, для которых соответствующие разряды < ; двоичного разложения числа = с(„,с «<...с <) и ,<- < а; 2 имеют единичное значение, = < в произвольный момент времени 1 формируют на своих выходах потенциалы, соответствующие <. -й строке матрицы и

5 за исключением первого элемента строки, который всегда равен единице.

Обозначим выход j --ro разряда счетчика (1 } и ) в любой момент времени через ю (), а выход 1 -го элемента И (1 1 2 -1) — через «; Н) ,Тогда имеем:

T «,(t) = « (pp,„p<) (t) = <<1 (t)

,{1) = 1< (po„. oio)(t} = у,®, q(t} = 1< (oo °, 0<<) (t) = Я (1} Я, (t)

Ф

"2 ()-««)Я= И)Я И}„,Ы (} < 2«.1(< } = {1< -., «) Ct) = 6) <1 (t) u > < (t) СлЗ, (} Сд< {Ц, Для моментов времени { = 0,1,..., 2 - 1,2 получим: и

1«() «тМ () " «2«.<(t) 1< «.<{ )

О О О ... О О

1 О О,... О О

1242984

О О 1 0 о о и

2-21

2 — 1 1 п о о

° ° ° 1 о

1 1.О О

1 1 1 1

° ° ° 1

2 О О о о о - о

2 0 О ... 1

3 О О ... 1

Таким образом, потенциал на выход -го элемента И рассматриваемой груп пы элементов И в такте т, соответству ет элементу5 .матрицы S . Так как и

1j при любом элементы 5 тождественно но равны единице, то элементы И груп пы 11 устройства формируют в такте на своих выходах потенциалы, сооти ветствующие 1 -й строке матрицы 5 (ОМ 2"-1).

В исходном положении устройства, которое обеспечивается подачей сигна ла Начальная установка устройства на вход 9 устройства, счетчик 3 и все ячейки регистра 4 находятся в нулевом состоянии.

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

Рассмотрим работу устройства в паузе между 1 -1-м и 1 -м тактовыми импульсами. Низкий потенциал с входа

8 устройства поступает на один из входов элемента И 1 и формирует на

его выходе низкий потенциал, который поступает на управляющий вход демультиплексора 2 и формирует на его выходах низкие потенциалы независимо от состояния адресных входов, что обеспечивает режим хранения информации для регистра 4. При этом в первых 4 — 1 -х ячейках регистра 4 хранятся соответствующие коэффициенты СДНФ, а в остальных ячейках нули. Счетчик 3 находится в -1-м состоянии. На выходе 10 устройства сохраняется потенциал, который соответствует -1-му коэффициенту полиномиальной формы, а на вход 7 подается потенциал, соответствующий

1 -му коэффициенту СДНФ, С появлением высокого потенциала на входе 8, т.е. с приходом 4 --ro тактового импульса, состояние счетчика увеличивается на единицу и на выходах элементов И группы !1 формируются потенциалы, соответствюущие п

4 и строке матрицы 5 . Если на информационном входе 7 устройства на.ходится низкий потенциал, т.е. t7= — О, то на выходе элемента И 1 формируется низкий потенциал, который, в свою очередь, приводит к формированию низких потенциалов на выходах демультиплексора 2, что обеспечивает режим хранения информации в регистре

4. Это эквивалентно записи в 1 -ю

З0 ячейку регистра 4 нуля. Если на вход

7 устройства подан высокий потенциал, т. е. f (Ц =1, то на выходе элемента И- 1 формируется высокий потенциал, поступающий на информационный

З5 вход демультиплексора 2, на адресные входы которого подаются сигналы с выходов счетчика 3. При этом íà t -м выходе демультиплексора 2 формирует- ся высокий Потенциал, который пода40 ется на ь -й Установочный вход регистра 2 и формирует íà его t -м выходе высокий потенциал, т.е. в 1 -ю ячейку регистра 2 записывается единица.

Следовательно, по переднему фронту .

45 f,-го тактового импульса a f. -ю ячейку регистра 2 заносится -й коэффициент СДНФ, и, таким образом, в первых 1 ячейках этого регистра хранятся значения первых т коэффициентов

50 СДНФ.

Потенциалы с выходов элементов И группы 11, соответствующие t -й строке матрицы 5, и потенциалы с выходов и регистра 2, соответствующие первым членам.СДНФ, логически перемножаются на соответствующих элементах

И группы 6. Полученные произведения суммируются элементом НЕРАВНОЗНАЧ1242984

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

ВНИИПИ Заказ 3707/49

Произв.-полигр. пр-тие, r. Ужгород, уп. Проектная, 4

НОСТЬ 5 и вычисленное значение т,-ro, коэффициента полиномиальной формй передается на выход 10 устройства, где оно сохраняется до прихода следующего тактового импульса.

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

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

Таким образом, в такте t на вход

7 устройства подается коэффициент

1(Ц СДНФ функции k(x), на выходе 10 устройства формируется коэффициент д полиномиальной формы представ.— ления этой же самой функции, С подачей 2 тактовых импульсов процесс преобразования логической функции. их СДНФ в полиномиальную форму заканчивается, Преобразование формы представления логических функций из полиномиальной формы в СДНФ, В этом случае устройство работает также, как и в предыдущем случае.

Отличие состоит в том, что в такте

1 на вход 7 устройства подается коэффициент п полиномиальной фор-мы представления логической функции1(х), на выходе 10 устройства формируется коэффициент 1(1) СДНФ той же самой функции, 1

Формула изобретения

Преобразователь формы представления логических функций, содержащий элемент И, демультиплексор, счет чик, регистр, элемент НЕРАВНОЗНАЧ

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

2"-1 разрядов регистра соединены с первыми входами соответствующих элементов И первой группы, выходы которых соединены с входами элемента

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

< j с2 — 1) соединены с теми выходами разрядов счетчика, номера которых совпадают с номерами единичных поI зиций двоичного разложения числа 1, а .вторые входы элементов И первой группы подключены к выходам элементов И второй группы соответственно,