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

4ь

4ь О

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

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

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

f(х)а 0©а ,х ,) a-jx -г© asXtX 4©

.о.Х;

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

f(X) I f ;(Xl

ire

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

...,Xj)

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

; - о

,i- si-,

Известные технические решения позволяют строить преобразователи логических функций для числи переменных m4i. В случае, когда , возникает необходимость разработки нового устройства. Однако для m i переменных (например, ) полиномиальная функция может быть представлена в виде

f (х)а0© а,х,© агх,Ф . ..© а.х, ...х-® 55 ®х;„(аг;Фа2;,х,® . ..©- t ,мх,. ..X;),

5

0

5

0

5

0

5

0

55

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

На фиг. 1 приведена структурная схема преобразователя формы представления логических функций; на фиг.2- общий принцип построения основных блоков преобразователя и их взаимосвязи.

Преобразователь формы представления логических функций (фиг. 1) содержит первый счетчик 1, второй счетчик 2 адреса, блок 3 памяти, второй счетчик 4, первый регистр 5, первый блок 6 преобразования, реализующий вычисление функции вида f(x), (f (x)a0©a1x, ©агхг©... © аг,.,х,. ,х;), второй блок 7 преобразования,реализующий вычисление функции Јк(х), (f k(x)xKf (x) , ,... ,m) , второй регистр .8, блок 9 элементов НЕРАВНОЗНАЧНОСТЬ и блок 10 управления.

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

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

Блок 3 памяти (фиг. 2) необходим для хранения различных коэффициентов многочлена от i-nвременных. Емкость ОЗУ выбирается из расчета преобразования функции от m переменных, т.е. имеется 2 -i ячеек.

Второй счетчик 4 (фиг. 2) предназначен для подсчета количества информации, поступающей в первый регистр 5. При заполнении регистра формируется сигнал переполнения, поступающий на блок 10 управления.

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

Первый блок 6 преобразования, реализующий вычисление функции f(х) (фиг. 2), состоит из блока элементов И и многовходового элемента НЕРАВНО- ЗНАЧНОСТЬ. Первая группа входов блок 6 предназначена для подачи функций счета с соответствующих выходов счетчика 1. На входы второй группы подается информация с выходов блока 3 па мяти. Эти сигналы являются сигналами разрешения подключения элементов И к входам элемента НЕРАВНОЗНАЧНОСТЬ, причем к входам j-ro элемента И подсоединены выходы счетчика 1, веса которых представляют собой двоичные логарифмы отв соответствующих элементов двоичного разложения номера j.

Второй блок 7 преобразования, реализующий вынисление функции f k(x) (фиг. 2), служит для логического умножения .

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

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

Блок 10 управления предназначен для формирования управляющих и синхронизирующих сигналов, необходимых для работы преобразователя. В состав блока входят микропрограммное устройство управления, состоящее из регистра адреса и ПЗУ, двухвходовые элементы И, синхронные RS-триггеры, дешифратор, генератор тактовых им-

JQ (5 20

25

-JQ . 0

5

35

0

5

пульсов и другие -логические элементы, а также элементы коммутации и индикации.

Преобразователь работает следующим образом.

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

f(х)а0 © а, © а,х7 ® аэх,хг@ачхз э ® а5х, agx4x3 9 а7х,хахэ ± aexf Ј S аэх1х4© амхгх4© atzxsx4© © а,5х ,х5х4© а,4хгх3х4 © a(Jx,xtx 3x4.

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

f (x)a0@ а, х,® агхг® а3х,) а4х 3© & а5х(х3©аь х1х3@ хДае© & а9х, © а,0х 7ffl а„х,х1©а,гх3© а13х,х3© © а14хгх3© а,5х,).

В этом случае , и блок 3 памяти хранит 2 байта коэффициентов ас,...,а7 и а Ј,..., а,5, которые записываются в ОЗУ после преобразования из последовательного кода в параллельный в регистре 5. Счетчик 2 адреса в данном случае содержит один разряд, т.е. позволяет адресовать два байта памяти блока 3. Счетчик 4 содержит три разряда, так как разрядность регистра 5 в этом случае может быть равна восьми. При вычислении коэффициентов СДНФ счетчик 2 устанавливается в нулевое состояние, что позволяет адресовать ячейку памяти, содержащую коэффициенты ад,... ,а(5. Данный вектор коэффициентов поступает на вход блока 6, на выходе которого формируется выражение, стоящее в скобках преобразованной функции. По управляющему сигналу блока 10 управления вычисленное значение через двухвходовой элемент И второго блока 7 записывается в первый триггер регистра 8, после чего вычисленное значение умножается на переменную х4 на трехвходовом элементе И второго блока 7 и записывается во второй триггер регистра 8. После этого происходит увеличение содержимого счетчика 2 на единицу. Из блока 3 памяти на вход блока 6 считывается вектор коэффициентов а0,...,аг, что позволяет вычислить

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

т „

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

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

Формула изобретения Преобразователь формы представления логических функций, содержащий первый счетчик, первый регистр, первый блок преобразования, реализующий вычисление функций f(x) (f(x) а0 © а,,х 1 ©аах г®... ,.. .х ;), и блок управления, причем i выходов первого счетчика подключены к входам первой группы первого блока преобразования, реализующего вычисление функции f(x), вход инкрементации первого счетчика и вход синхронизации первого регистра подключены к первому выходу блока управления, вход сброса первого счетчика подключен к второму выходу блока управления, отличающийся тем, что, с целью расширения функциональных

5

0

5

возможностей за счет преобразования функции произвольного числа переменных из совершенной дизъюнктивной нормальной формы в полиномиальную и наоборот, в него введены счетчик адреса, второй счетчик, блок памяти, второй блок преобразования, реализующий вычисление функций f x-(x) (fх(х)х«Ј(x), ,...,m), второй регистр, блок элементов НЕРАВНОЗНАЧНОСТЬ, причем вход последовательной записи первого регистра является входом преобразователя, информационные выходы первого регистра подключены к информационным входам коэффициентов блока памяти, адресные входы которого подключены к выходам счетчика адреса, информационные выходы блока памяти подключены к входам коэффициентов первого блока преобразования, реализующего вычисление функции f(x), i+l,...,m, выходы первого счетчика и выход первого блока преобразования, .реализующего вычисление функции f(x), подключены к информационным входам первой группы второго блока преобразования, реализующего вычисление функций f k(x),

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

Изобретение относится к автоматике и вычислительной технике. Преобразователь содержит первый счетчик 1, первый регистр 5, первый блок 6 преобразования, реализующий вычисление функции F (X) (F (X) = A₀ + A₁X₁ + ... + A₂^I_-1 X₁ ... X_I), и блок 10 управления. Цель изобретения - расширение функциональных возможностей за счет преобразования функции произвольного числа переменных из совершенной дизъюнктивной нормальной формы в полиномиальную и наоборот. В преобразователь введены счетчик 2 адреса, второй счетчик 4, блокпамяти 3, второй регистр 8 и блок 9 элементов НЕРАВНОЗНАЧНОСТЬ. 2 ил.