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

(51)4 6 06 Р 15/3 ГОСУДАРСТВЕННЫЙ КОМИТЕПО ИЗОБРЕТЕНИЯМ И ОТНРЫТПРИ ГКНТ СССР ПИСАНИЕ ИЗОБРЕТЕНИ(54) ПРЕОБРАЗОВАТЕ ЛЕНИЯ ЛОГИЧЕСКИХ Ф (57) Изобретение о тике и вычислител образователь соде ЛЬУНКЦИИ РМЫ П Вносой ся к автом нике. Пр вый счет ит п АВТОРСКОМУ СВИДЕТЕПЬСТ нскии радиотехнический и чик 1, первый регистр 5, первый блок6 преобразования, реализующий вычисление функции вида й(х), (Е(х)==а + а,х,+ а;х,х.,),. иблок 10 управления. Цель изобрения - расширение функциональныхможностей за счет преобразованияфункции произвольного числа переменных из совершенной дизьюнктивнойнормальной формы в полиномиальную инаоборот, В преобразователь введенысчетчик 2 адреса, второй счетчик 4,блок памяти 3, второй регистр 8,блок 9 элементов НЕРАВНОЗНАЧНОСТЪ,второй блок 7 преобразования,реализующий вычисление функции вида(х), И к(х)=хй(х), К=+1ш),14Изобретение относится к автоматике и вычислительной технике и можетбыть использовано для преобразования Формы представления логическихфункций из совершенной дизъюнктивнойнормальной формы в полиномиальную инаоборот в автоматизированных системах проектирования цифровых устройств,Цель изобретения - расширениефункциональных возможностей за счетпреобразования функции произвольного,числа переменных из совершеннойдизъюнктивной нормальной формы в полиномиальную и наоборот,Известно, что коэффициенты а -а .полиномиальной формы представлениялогической ФункцииГ(х)=а,еа,х,а агхгО+ а хх Е,.могут быть получены на основании коэффициентов совершенной дизъюнктивной нормальной формы той же Функциий(х)=Е;(х,х х,)74671 2 10 15 20 25 30 т.е, добавление одной переменной увеличивает длину многочлена в 2 ра. за, но вынесение за скобки добавляемой переменной позволяет представить полиномиальную Функцию в виде суммы однородных многочленов, различающихся только индексами при коэффициентах, Поэтому процесс вычисления может производиться поэтапно путем вычисления многочленов х-й степени, умножения их на дополнительнуюпеременную с последующим суммированием,На фиг, 1 приведена структурнаясхема преобразователя формы представления логических функций; на фиг,2 общий принцип построения основныхблоков преобразователя и их взаимосвязи.Преобразователь Формы представления логических функций (фиг. 1)содержит первый счетчик 1, второйсчетчик 2 адреса, блок 3 памяти, второй счетчик 4, первый регистр 5,первый блок 6 преобразования, реализующий вычисление функции вида Е(х),И(х) =ао 9 а,х, ю агх гОфО а;,хх;),второй блок 7 преобразования,реализующий вычисление Функции Г(х),Ир,(х)=хй(х) К=1+1ш) второйа,а,Ба;,Для 3.=0 матрица Б=1. Матрица Б для 1 переменных образуется из матрицы Б " для - переменных по следующему правилу: 40 Б" 0 1(х) а,9 а,х,6 агхгее аг;,х,х;Е55Ях;,(агФаг;,х 9 а,;,гхгЭО Э а;,х,х;),Известные технические решения по зволяют строить преобразователи логических функций для числа переменных ш с х. В случае, когда ш3., возникает необходимость. разработки нового устройства, Однако для ш ) а . 50 переменных (например, ш=д+1) полиномнальная функция может быть представлена в виде регистр, 8, блок 9 элементов НЕРАВНОЗНАЧНОСТЬ и блок 10 управления,Первый регистр 5 (Фиг. 2) представляет собой сдвиговый регистр,предназначенный для последовательнойзаписи -разрядного двоичного вектора коэффициентов полиномиальнойфункции.Счетчик 2 адреса предназначен дляФормирования адресов блока 3 памяти,Счетчик построен по схеме с последовательным переносом. Выход последовательного переноса, свидетельствующий об окончании перебора адресовблока 3 памяти, формирует сигнал,принимаемый блоком управления,Блок 3 памяти (фиг, 2) необходимдля хранения различных коэффициентовмногочлена от 1-переменных, ЕмкостьОЗУ выбирается из расчета преобразования Функции от ш переменных, т,е.мимеется 2 -х ячеек.Второй счетчик 4 (фиг. 2) предназначен для подсчета количества инФормации, поступающей в первый регистр 5. При заполнении регистра формируется сигнал переполнения, поступающий на блок 10 управления, 1474671Первый счетчик 1 предназначен дляподачи на схему преобразователя кодовых комбинаций, необходимых дляосуществления преобразования формы5представления логической функции.Первый блок 6 преобразования реализующИй вычисление функции Г(х)(фиг, 2), состоит из блока элементовИ и многовходового элемента НЕРАВНОЗНАЧНОСТЬ, Первая группа входов блока6 предназначена для подачи функцийсчета с соответствующих выходов счетчика 1, На входы второй группы подается информация с выходов блока 3 па мяти. Эти сигналы являются сигналамиразрешения подключения элементов И квходам элемента НЕРАВНОЗНАЧНОСТЬ,причем к входам 1-го элемента И подсоединены выходы счетчика 1, весакоторых представляют собой двоичныелогарифмы оъ соответствующих элементов двоичного разложения номера 3.Второй блок 7 преобразования, реализующий выиисление функции Г(х) 25(фиг, 2), служит для логического умножения,Второй регистр 8 (фиг, 2)предназ 1 начен для хранения промежуточных результатов, полученных в процессеитеративного вычисления функции, Информационные входы триггеров данного регистра соединены вместе и подключены к выходу второй комбинационной схемы. Управление записью в соответствующий триггер регистра осуществляется сигналом блока 1 О управления, Выходы регистра являютсявходами блока 9 элементов НЕРАВНОЗНАЧНОСТЬ.Блок 9 элементов НЕРАВНОЗНАЧНОСТЬ(фиг. 2) представляет собой наборстандартных двухвходовых элементовбулевой алгебры и предназначен длясуммирования по модулю два промежуточных результатов (полиномов отх-переменных) с целью вычислениякоэффициентов полинома от заданногочисла переменных, Выходы блока 9 являются выходами преобразователя,Блок 10 управления предназначендля формирования управляющих и синхронизирующих сигналов, необходимыхдля работы преобразователя, В составблока входят микропрограммное устройство управления, состоящее из регистра адреса и ПЗУ, двухвходовыеэлементы И, синхронные КБ-триггеры,дешифратор, генератор тактовых импульсов и другиелогические элементы, а также элементы коммутации ииндикации,Преобразователь работает следую-.щим образом,Пусть требуется преобразоватьполиномиальную функцию в СДНФ. Ипусть функция четырех переменныхимеет видЕ(х)=а, В а,х, е а,х, а а,х,хЭ а,х аО+ а Х,Х,О а Х,Х,О+ а,х,х х,йа,х, ыЯ а х х 4 О+ а 1 хх 4 О а х хх 49 а 1 х х 4 Оя а х х х 4 Оф а 4 ххх 4 (Э а х х х х 4Преобразуют функцию к следующемувиду:Е(х)=а,8 а, Х,О+ ахо а 1 х,х О+ а, х 9Ы ах,х,Оа,х,х,О а,х,х х,О+ х,(ацЗЮ ах, О ах,а ах,х О ах, Э ах,хО9 ах х, 9 ах, х,х ) .В этом случае 1=3, в=4 и блок 3 памяти хранит 2 байта коэффициентов а а, и аа которые записываются в ОЗУ после преобразования из последовательного кода в параллельный в регистре 5, Счетчик 2 адреса в данном случае содержит один разряд, т,е. позволяет адресовать два байта памяти блока 3. Счетчик 4 содержит три разряда, так как разрядность регистра 5 в этом случае может быть равна восьми, При вычислении коэффициентов СДНФ счетчик 2 устанавливается в нулевое состояние, что позволяет адресовать ячейку памяти, содержащую коэффициенты аа,. Данный вектор коэффициентов поступает на вход блока 6, на выходе которого формируется выражение, стоящее в скобках преобразованной функции. По управляющему сигналу блока 10 управления вычисленное значение через двухвходовой элемент И второго блока 7 записывается в первый триггер регистра 8, после чего вычисленное значение умножается на переменную Х 4 на трехвходовом элементе И второго блока 7 и загисывается во второй триггер регистра 8. После этого происходит увеличение содержимого счетчика 2 на единицу, Из блока 3 памяти на вход блока 6 считывается вектор коэффициентов а а , что позволяет вычислить5 1 соответствующую часть полиномиальной функции г(х), Данная часть функции через блок 7 записывается в первый триггер регистра 8, Ддухвходовой элемент НЕРАВНОЗНАЧНОСТЬ формирует значение функции Г(х) путем суммирования ее обеих частей, хранимых в триггерах регистра 8, Такое преобразование осуществляется для всех 2 наборов переменных, подаваемых с выхода счетчика 1, что. позволяет вычислить все 2 коэффициента СДНФ,Рассмотрим преобразование СДНФ в полиномиальную форму. В данном случае учитывается тот факт, что преобразование функции из СДНФ в полиномиальную и из полиномиальной в СДНФ обратимо, т,е. а,;, 474 б 71 10 15 20 25 возможностей за счет преобразованияфункции произвольного числа переменных из совершенной дизъюнктивнойнормальной формы в полиномиальную инаоборот, в него введены счетчик адреса, второй счетчик, блок памяти,второй блок преобразования, реализующий вычисление функций Г (х)(Х,(х)=хГ(х), К=з.+1 в), второйрегистр, блок элементов НЕРАВНОЗНАЧНОСТЬ, причем вход последовательнойзаписи первого регистра являетсявходом преобразователя, информационные выходы первого регистра подключены к информационным входам коэффициентов блока памяти, адресные входы которого подключены к выходамсчетчика адреса, информационные выходы блока памяти подключены к входамкоэффициентов первого блока преобразования, реализующего вычислениефункции Е(х), +1 ш, выходы первого счетчика и выход первого блокапреобразования, .реализующего вычисление функции Е(х), подключены кблока управления,55 Следовательно, схемы для прямого и обратного преобразований эквиваленты, т.е. в случае преобразования СДНФ в полиномиальную форму в блок 3 памяти записываются коэффициенты СДНФ, а функционирование устройства осуществляется, как и в случае преобразования полиномиальной формы в СДНФ,Формула из обретенияПреобразователь формы представления логических функций, содержащий первый счетчик, первый регистр, первый блок преобразования, реализующий вычисление функций Г(х) (Е(х)= =а9 а х, О+ а хЫ Э а;., х, х; ), и блок управления, причемвыходов первого счетчика подключены к входам первой группы первого блока преобразования, реализующего вычисление функции К(х), вход инкрементации первого счетчика и вход синхронизации первого регистра подключены к первому выходу блока управления, вход сброса первого счетчика подключен к второму выходу блока управления, отличающийся тем, что, с целью расширения функциональных 30 35 40 45 50 ичформационным входам первой группывторого блока преобразования, реализующего вычисление функций Г (х),выход которого подключен к информационным входам второго регистра,входы синхронизации которого подключены к управляющим выходам первойгруппы блока управления, информационные выходы второго регистра подключены к соответствующим входамблока элементов НЕРАВНОЗНАЧНОСТЬ,выходы которого подключены к информационным входам второй группы второгоблока преобразования, реализующеговычисление функции, и являются выходами преобразователя, кроме того,вход управления записью блока памяти,входы инкрементации и сброса счетчика адреса и второго счетчика подключены к управляющим выходам второйгруппы блока управления, а выходы переноса первого и второго счетчикови счетчика адреса подключены к управляющим входам блока управления,входы разрешения группы второго блока преобразования, реализующего вычисление функций Гк(х), подключенык управляющим выходам первой группы1474671 Составитель А,Доброхактор О,йрковецкая Техред Л,Сердюкова Корректор С.Шекма Производственно-издательский комбинат Патент , г. Ужгород, ул. Гагарина,м 11 Г ина 101 аказ 1896/48 НИИПИ Госуда Тираж 667 венного комитета по 113035, Москва, Жзобретения РаушскаяПодписноеи открытиям при ГКНТ ССб., д, 4/5