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

 

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

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

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

РЕСПУБЛИК

А1

ÄÄ SU ÄÄ.1474671 (51)4 G 06 F 15/31

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 4281167/24-24 (22) 10.07.87 (46) 23,04.89, Бюл. №- 15 (7l) Минский радиотехнический институт (72) И.П.Кобяк, В.N.Ãàëåöêèé, В.Д.Руденко и В.А .Липницкий (53) 681,327.6(088.8) (56) Авторское свидетельство СССР

1164728, кл. С 06 F 15/31, 1985.

Авторское свидетельство СССР

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

6 преобразования, реализующий вычисление функции вида f(х), (f(x)=

=а + а,х, i ... + а <,,х,...х;), блок 10 управления. Цель. изобрете-.. ния — расширение функциональных воэможностей за счет преобразования функции произвольного числа переменных из совершенной дизьюнктивной нормальной формы в полиномиальную и наоборот. В преобразователь введены счетчик 2 адреса, второй счетчик 4, блок памяти 3, второй регистр 8, блок 9 элементов НЕРАВНОЗНАЧНОСТЬ, второй блок 7 преобразования,реализующий вычисление функции вида

f „(х), (f (x)=x„f (х), K=i+1,...,m).

2 ил.

14

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

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

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

Г(x)=а,еa,х,а а х,O+ а,х„х,e... могут быть получены на основании коэффициентов совершенной дизъюнктивной нормальной формы той же функции

n - -!

f (х)= + f;(x„,õ,...,õ; ) !

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

74671 2

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

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

Преобразователь формы представления логических функций (фиг. 1) содержит первый счетчик 1, второй счетчик 2 адреса, блок 3 памяти, второй счетчик 4, первый регистр 5, первый блок 6 преобразования, реализующий вычисление функции вида f(x), (1(х)=а> & а,х, &а х О+ ... O a;,õ...x;), второй блок 7 преобразования,реализующий вычисление функции f (õ), (Й (х)=х„f(х), K=i+1,...,m), второй а, а, $! а;, Для i=0 матрица S =1. Матрица S для i переменных образуется из матрицы S для i-! переменных по следующему правилу .

$ 0

S S

S =

К(х) а,9 а,х, О атх, е...e а ; х,...х;8

Я х;,,(а,Юа,,z, 0 а „ к 9 ° . ° 0 а Ф! x ° ° x ) 9

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

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

Счетчик 2 адреса предназначен для формирования адресов блока 3 памяти.

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

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

ОЗУ выбирается из расчета преобразования функции от m переменных,,т.е. м имеется 2 -i ячеек.

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

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

5 представления логической функции.

Первый блок 6 преобразования, реализующйй вычисление функции f(x) (фиг, 2), состоит из блока элементов

И и мноroвходового элемента НЕРАВНОЗНАЧНОСТЬ. Первая группа входов блока

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

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

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

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

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

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

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

f(x)=a, а а,х, е а,х, а а,х,х,B а,к а

О а х,х,O а х,х, О+ а,х,хгх, & а,х4 N

Я> а9х 4 О+ а„х,х, О а,„х,хгх 49 а11 y++4О (j) а Х Х Х4ОО а14хгх х4 9 а Х Х гХ Х4 °

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

f (x)=a,á> а, х,Ю агхго а х,х О а х,&

B а1 х х çО а, x, x, Î а, х1х гх, О х 4(а ц З

Ю а9х, 0 а„х,а а„х,хгОа гхз@ açх 9О

9 а„x х,& а„x,x x ) °

В этом случае х=3, m=4 и блок 3 памяти хранит 2 байта коэффициентов а0 «а.1 и ag) ° i ° )а1 » которые за писываются в ОЗУ после преобразования из последовательного кода в параллельный в регистре 5, Счетчик 2 адреса в данном случае содержит один разряд, т,е. позволяет адресовать два байта памяти блока 3. Счетчик 4 содержит три разряда, так как разрядность регистра 5 в этом случае может быть равна восьми. При вычислении коэффициентов СДНФ счетчик 2 устанавливается в нулевое состояние, что позволяет адресовать ячейку памяти, содержащую коэффициенты а,...,а14, Данный вектор коэффициентов поступает на вход блока 6, на выходе которого формируется выражение, стоящее в скобках преобразованной функции. По управляющему сигналу блока 10 управления вычисленное значение через двухвходовой элемент

И второго блока 7 записывается в первый триггер регистра 8, после чего вычисленное значение умножается на переменную Х4 на трехвходовом элементе И второго блока 7 и загисывается во второй триггер регистра 8.

После этого происходит увеличение содержимого счетчика 2 на единицу.

Из блока 3 памяти на вход блока 6 считывается вектор коэффициентов а,...,а, что позволяет вычислить

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

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

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

S а,;, 474671

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

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

СДНФ в полиномиальную форму в блок

3 памяти записываются коэффициенты

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

СДНФ.

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

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

=ао ® a„x, Î+àð <9... & a;.,x ° .x;), и блок управления, причем i выходов первого счетчика подключены к входам первой группы первого блока преобразования, реализующего вычисление функции f(х), вход инкрементации первого счетчика и вход синхронизации первого регистра подключены к первому выходу блока управления, вход сброса первого счетчика подключен к второму выходу блока управления, отличающий с я тем, что, с целью расширения функциональных

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

1474671

М ь д ч

Составитель А,Доброхотов

Редактор О,Ирковецкая Техред Л.Сердюкова Корректор С.Шекмар

Заказ 1896/48 Тираж 667 Подписное

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

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

Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарина,1 1

11 l1 ч Г ина 101