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

Изобретение относится к автомати ке и вычислительной технике и может быть использовано для преобразования форыы представления логических функций из совершенной дизъюнк тивной нормальной в полиноми альну|р и наоборот, например, в авт матизированных системах проектирова ния цифровых устройств, Целью изобретения является повыш ние его быстродействия. На чертеже представлена структур предлагаемого устройства. Устройство содержит п-разрядный двоичный счетчик 1, группу из 2 элемента И 2, управляемых счетн триггера 3, элемент И 4, демультиплексор 1 на 2, 5, 2 -разрядный статический регистр 6, элемент НЕРАВНОЗНАЧНОСТЬ 7, информационный вхо 8 устройства, выход 9 подачи такто вых импульсов, вход 10 начальной установки устройства , выход 11 ус ройства. .-. В устройстве используются стандартные функциональные блоки, промышпенно выпускаемые в виде интегр ных схем. Устройство работает следующим, об разом.. 1 Как известно, коэффициенты а - aj, полиномиальной формы представления логической функции )-ао©о(,х,©агХ.1©а,х,Х20--.@012п /1могут быть получены из коэффициенто f(D) f(0,...,0), f(,, f(l,0,...0).. «f (1,. .., 1) совершенной дизъюнктивной нормальной формы (СДНФ) той ) - функции f (Х)21 с) х х. следующм образом: Для пЧ) матрица . Матрица s для п переменных образуется из матрицы S для п-1 переменных по следукяцему правилу: ,п-( Например, матрица S имеет вид 10000000 1IOOGQOO 10100000 1 I 1 10000 10001000 11001 100 10101010. Ill 111 n Матрица (S) , обратная матрице , совпадает с самой матрицей S, .е. (ST S , поэтому обратное реобразование формы представления огической функции f(X) из полиномильной формы в СДНФ имеет вид:. Таким образом, имеем y.j-n-i ; ) Sj - элемент матрицы S Таккак S,; 0 при , то для S вычисления а необходимы лишь первые i коэффициентов f (j ) СДНФ функции, и наоборот, для вычисления коэффициента f(i) СДНФ функции необходимы лишь первые. коэффициентов а полиномиальной формы, 2. Покажем, что управляемые тригг еры, соединенные между собой таким образом, что выход каждого предьщущего триггера соединен с управлякмцим входом (V-входом) поеледзпощего триггера, на управляющий вход первого триггера подана логическая единица, счетные входы (Т-входы) триггеров соединеньг между собой и подключены квходу подачи тактовых импульсов и все триггеры в исходном положении находятся в нулевом состоянии, в каждый тактовый момент времени t формируют на своих выходах потенциалы, соответствующие элементам t-й.строки матрицы S (О t ). Обозначим состояние j-ro тригге-. ра (1 j 1) в такте t через Qj(t). TV-триггер функционирует в соответствии с уравнением Q(t+) T(t)V(t)®Q(t), поэтокгу для нашего случая имеем Q.(t+l)T(t)Q;,(t)® (t). : Отсюда получаем следующие значения Qj(t): Таким образом, состояние j-ro триггера в такте t соответствует эле 1енту матрицы S. Так как при любом t элементы S тождественно равны единице, то рассмотренная схе ма из управляемых счетных триггеров формирует в такте t потенциалы, соответствующие t-й строке матршда. S . 3. Исходное положение устройст.ва, обеспечиваемое подачей сигнала Начальная установка устройства на вход 10 устройства, следующее: триггеры 3 находятся в единичном состоянии, счетчик 1 и все ячейки регистра 6 находятся в нулевом состоянии. 3.1, Преобразование формы пред, ставления логических функций из СДНФ в полиномиальную. , Рассмотрим работу устройства в па узе между t-1-м и t-м тактовыми импульсами. Счетчик 1 находится в состоянии t. На выходах триггеров 3 сфо мированы потенциалы, соответствукщие t-1-и строке матрицы s. Низкий поте циал с входа 9 устройства поступает на один из входов элемента И 4 и формирует на его выходе низкий потенциал, который поступает на управляющий вход демультиплексора 5 и фор мирует на его выходах низкие потенциалы независимо от состояния его ад ресных входов, что обеспечивает резкя хранения информации для регистра 6, При этом в первых t -1 ячейках регистра 6 хранятся соответствующие коэффициенты СДНФ, а в остальных яче ках - нули. На выходе 11 устройства сохраняется потенциал, соответству-; ющий t -I -му коэффициенту полиномиальной формы. На вход 8 устройства подается потенциал, соответствующий. t-му коэффициенту СДНФ, С появлением высокого потенциала на входе 9 устройства (т.е. с tipHxo-; дом t-ro тактового импульса) состояние счетчика 1 не изменится, а на выходах триггеров 3 сформируются потенциалы, соответствуищие t-й строке матрицы S. Если на информационном входе 8 устройства находится низкий потенциал, то на выходе элемента И 4 формируется низкий потенциал, который, в свою очередь, приводит к. формированию низких потенциалов на выходах- демультиплексора 5, что обеспечивает режим хранения информации в регистре 6, Это эквивалентно записи в t- ячейку регистра 6 нуля. Если на вход 8 устройства подан высокий потенциал, то на выходе элемента И 4 формируется высокий потенциал-, который подается на информационный вход демультиплексора о, на адресные вход которого подаются сигна1ш с выходов счет-, чика 1. При этом на t-м выходе демультиплексора 5 формируется высокий потенциал, который подается на tru установочный вход регистра 6 и формирует на его t-м выходе высокий потенциал, что эквивалентно записи в ячейку регистра 6 единицы. Следовательно, по переднему фронту t-ro тактового импульса в t-ю ячейку регистра 6 заносится t-й коэффициент СДНФ и, таким образом, в первых ячейках этого регистра хранятся первых t коэффициентов СДНФ. .Сигналы с выходов триггеров 6, соответствующие элементам t-й строи матрищл S , и сигналы с выходов

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

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

Таким образом, в такте t на вход устройства 8 подается коэффициент f(t) СДНФ функции f(X), а на выходе

II устройства формируется коэффициент at полиномиальной формы представления этой же самой функции, С подачей 2 тактоЕ;ых импульсов

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

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

В этом случае устройство работает так же, как и в предьщущем случае. Отличие состоит в том, что в

такте t на вход 8 устройства подается коэффициент ,а полиномиальной .формь представления логической функции f(X), а на выходе II устройства формируется коэффициент

(t) СДНФ той же самой функции.

ПРЕОБРАЗОВАТЕЛЬ ФОРМЫ ПРЕДСТАВЛЕИШ ЛОГИЧЕСКИХ ФУНКЦИЙ, содержав ий счетчик, группу элементов И, группу счетных триггеров ,0тл и чающийся тем, что, с це-. лью повышения быстродействия, в него введены элементы И,демультиплексор, регистр, элемент НЕРАВНОЗНАЧНОСТЬ, причем информационный вход преобразователя соединен с первым входом элемента И, выход которого соединен с информационным входомдемультиплексора, выходы разрядов счетчика соединены соответственно с адресными входами демультиплексора, выходы которого соединены с информационными входами соответствующих разрядов регистра, первый выход которого соединен с первым входом элемента НЕРАВНОЗНАЧНОСТЬ, а остальные