Преобразователь формы представления логических функций Советский патент 1986 года по МПК G06F17/10 

1

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

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

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

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

5, первую группу элементов И 6, инфорТак как5; О при j i , то для вычисления коэффициента а, полиномиальной формы необходимы лишь первые 1 коэффициентов 1( СДНФ функции, и наоборот, для вычисления коэффициента I (; J СДНФ необходимы лишь пер- -, вые 1 коэффициентов а: полиномиальИзвестно, что коэффициенты ,

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

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

образом.

ной формы.

Покажем, что группа элемен тов И, в которой входы i -го элемента И (1 & ) соединены с выходами тех разрядов счетчика, для которых соответствующие разряды двоичного разложения числа о ,„.,... of, )2

п ,Ц имеют единичное значение,

(.СДНФ) той же функции f (х) 21 f. х . „.,

,. 35 произвольньи момент времени т фор..- :миру1от на своих выходах потенциалы,

соответствующие t -и строке матрицы 5 за исключением первого элемента строки, который всегда равен единице. 40 Обозначим выход j-го разряда счетчика ( п ) в любой момент времеполиномиальной формы представления логической функции f(х)а ®а, ((,х.@. . . (5) а, . X .х„.. . х

о (± а,| X х.. . v

могут быть получены из коэффициентов (, f(0,...,0), f, f(1,0,.. .,0), , ,„ f (1,.., , 1-) совершенной

дизъюнктивной нормальной формы )

30

,х следующим образом: /

ни i через COj (i) , а выход ( -го элемента И (1 ) - через ff; (i) . .Тогда имеем:

Для п 0 матрица . Матрица S для п переменных образуется из матрицы 5 для п-1 переменных по сле- д чтощему правилу:

5

О

Матрица S , обратная матрице S, совпадает с самой матрицей S, т.е. , поэтому обратное преобразование формы представления логической функции i(x ) из полиномиальной формы в СДНФ имеет вид:

Ji j i ii Liii yiL J f L llJJL ilLJL i LJ4 1 (

00 0 /. .. 0. 0 0 0 0 ... 00

10 0 ... 0 1 1 0 0 . ,. . 0 0

Таким образом, имеем:

.-f

j.i 3 (.) 21-1

где 5;. - элемент матрицы 5°

Так как5; О при j i , то для вычисления коэффициента а, полиномиальной формы необходимы лишь первые 1 коэффициентов 1( СДНФ функции, и наоборот, для вычисления коэффициента I (; J СДНФ необходимы лишь пер- вые 1 коэффициентов а: полиномиаль

ной формы.

соответствующие t -и строке матрицы за исключением первого элемента строки, который всегда равен единице. Обозначим выход j-го разряда счетчика ( п ) в любой момент времени i через COj (i) , а выход ( -го элемента И (1 ) - через ff; (i) . Тогда имеем:

I(iH(oo...oO(t) a:),a),

:i2(t)(oO,..Olo)(t)--COj(t, ,((oo...oi(t) CO,a)0,a)

f2 -2i (- o))CO,.,(t),,. C0j(ij,

V;() w.i(t)co.,(t)...Qj(tla},{il.

Для моментов времени i 0,1,..., 2 - 1,2 получим:

2 3

О О

О О

2-2 1

1

1 1 О

Таким образом, потенциал на выход t-го элемента И рассматриваемой группы элементов И в такте t соответствует элементу матрицы S. Так как при любом -t - элементы 5х тождественно равны единице, то элементы И группы 11 устройства формируют в такте i на своих выходах потенциалы, соответствующие i; -и строке матрицы 5 ().

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

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

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

С появлением высокого потенциала на входе 8, т.е. с приходомi-го

1

1

О 1

О

о

о о

1 О

1 1

.0 о

25

тактового импульса,- состояние счетчика увеличивается на единицу и на выходах элементов И группы 11 формируются потенциалы, соответствюущие 4.-и строке матрицы 5 . Если на информационном входе 7 устройства на- .ходится низкий потенциал, T.e. f(tT 0, то на выходе элемента И 1 формируется низкий потенциал, который, в свою очередь, приводит к формированию низких потенциалов на выходах демультиплексора 2, что обеспечивает режим хранения информации в регистре 4. Это эквивалентно записи в t-ю 30 ячейку регистра 4 нуля. Если на вход 7 устройства подан высокий потенциал, T.e.i( t)1, то на выходе элемента И-1 формируется высокий потенциал, поступающий на информационньш

5 вход демультиплексора 2, на адресные входы которого подаются сигналы с выходов счетчика 3. При этом на t -м выходе демультиплексора 2 формирует- ся высокий потенциал, который пода0 ется на t -и установочньш вход реги- ст;ра 2 и формирует на его t -м выходе высокий потенциал, т.е. в t -ю ячейку регистра 2 записывается единица. Следовательно, по переднему фронту .

5 i-ro тактового импульса вt -ю ячейку регистра 2 заносится-t-и коэффициент СДНФ, и, таким образом, в первых t ячейках этого регистра хранятся значения первых t коэффициентов

0 СДНФ.

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

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

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

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

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

В этом случае устройство работае также, как и в предыдущем случае. Отличие состоит в том, что в такте t на вход 7 устройства подается коэффициент а полиномиальной формы представления логической функции i(x, на выходе 10 устройства формируется коэффициент i(i СДНФ той же самой функции.

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

Преобразователь формы представления логических функций, содержаВНИИПИ Заказ 3707/49

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

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

rt

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

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

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