Функциональный преобразователь Советский патент 1985 года по МПК G06F17/14 

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

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

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

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

Это -устройство реализуется с меньшими аппаратурными затратами, однако также позволяет найти для данной булевой функции тольк такой ее полином Жегалкина, в котором все переменные не инвертированы.

Наиболее близким по технической сущности к изобретению является анализатор спектра, состоящий из счетчика и последовательно соединенных каналов, каждьш из которых содержит блок .задержки и арифметический блок, . который содержит последовательно соединенны элемент И и сумматор по модулю два 2.

Это устройство реализуется с меньшими аппаратурными затратами, однако также позволяет найти для данной булевой функции . только такой ее полином Жегалкина, в котором все переменные не инвертированы.

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

Поставленная цель достигается тем, что функциональный преобразователь, содержащий первую группу из п (2 -размер преобразования) элементов зaдepжJки, п арифметических 15локов причем 1-й(1,п) арифметический блок содержит первый элемент И и сумматор по модулю два, первый вход которого подклчен к выходу элемента И, первьш вход которого подключен к выходу i-ro элемента задержки первой группы, блок управления, содержащий счетчик, прямой выход i-ro(,n) разряда которого подключен к второму входу первого элемента И i-ro арифметического блока, введены вторая группа из п элементов задержки, в i-й арифметический блок - второй и третий элементы И, а в блок управйения - п элементов И, п элементов И-НЕ и п триггеров, причем в i-м арифметическом блоке второй и третий нходы сумматора по модулю два подключены к выходам соответственно второго и третьего элементов И, первые входы которых подключены к выходам соответственно i-ro элемента И--НЕ и i-ro элемент И блока управления, первые входы которых подключены к выходу i-ro триггера блока управления, прямой и инверсный выходы i-ro разряда счетчика блока управления подключены к вторым входам соответственно i-ro элемента И-НЕ и i-ro элемента И блока управления, выход сумматора по модулю два j-ro (j 1,n-1) арифметического блока подключен к второму входу третьего элемента И (j+l)-ro арифметического блока и входу (j+1) -го элемента задержки второй группы, выход которого подключен .ко второму входу второго элемента И (j+1)го арифметического блока и входу (j+1)-го элемента задержки первой группы, выход сумматора по модулю два п-го арифметического блока является информационным выходом преобразователя, второй вход второго элемента И первого арифметического блока соединен с входом первого элемента задержки первой группы и подключен к выходу первого элемента задержки второй группы, вход которого соединен с вторым входом третьего элемента И первого арифметического блока и является информационным входом преобразователя.

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

Функциональный преобразователь состоит из блока 5щравления 1, элементов задеря ки 2;|, ,.. 2п и 3,), ...3, арифметических блоков 4,(, ...4f|, каждый из которых содержит элементы И 5, 6 и 7 и сумматор 8 по модулю два, блок управления 1 состоит из п-разрядного счетчика 9, триггеров lOj,, ... 10., элементов И-НЕ 1Ц, ... 1Ци элементов И 12, ... 12„. Выходы 13, ...13„, ... 14,... 14(,, 15;,... 15. блока управления 1 подключены соответствегшо к входам элементов 5, 6 и 7 арифметических блоков 4, ... 4.

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

Рассмотрим аглоритм вычисления коэффициентов полинома Жегалкина, реализуемого устройством. Пусть задана булева функция своим вектором истинности t (f,..., fgi.,), где fj может быть или нулем, или единицей (} О, ). Произвольная булева функция представима полиномом Жегалкина следующего вида iUn,.,.,...ipiч.(0 где 2 - знак суммы по модулю два, х i Это или х; или х (,...n), а 1, если K;j :0. Величины F(k ,..., k) могут быть или нулями, или единицами. Поскольку каждая переменная х входит в (1) или непосредственно, или со знако.м инверсии,то всего существует 2 различных полиномо вида (1), причем если все переменные не инвертированы, то имеем традиционный полипом Жегалкина, коэффициенты которого могут быть вычислены с помощью устройства-прототипа. Например, при п 2 и х„ х„, х - имеем полином f(Xj,x,)F(0,0)ffiF{0,l).. F(l,0) x,©F(l,l)Xj Чтобы получить-вектор J oэффициeнтoв F(k, ... k), необходимо вектор f умножить на п-кратное прямое (кронекерово) произведение матрицы при i 1,...п. Если переменная не инвертирована, то hi О, в противном, случае hi 1 С целью нахождения п-кратного прямого произведения Н матриц (2) можно воспользоваться следующим рекурсивным соотнршеиием п-, Ь,н„.Л ,., ь„н„.И, где Н|. - матрица размерюм 2 х 2 , являющаяся (п-1)-кратным кронекеровым про изведением матриц (2), рассматриваемых при i 1,... п-1. При п 2 умножение вектору значений функции f (х,...,х) на матрицу Н записывается так Это соотношение можно представить как систему из четырех следующих равенств, записанных в скобочной форме F(0,0) (fo ®0 © h, f,)®0©h,(fj®0®h,p, F(0,l)-(h, f©fo®0)®0®h2(h, f,®f2©0), (3) F(l,0)h2 (, f)®(f(90 ® h, )@0, F (, 1) h (h f,@fj Ф 0) €t (R, f, Ф 0 0)®0 Для n 2 алгоритм функционирования данного устройства определяется системой равенств (3). Данное устройство позволяет вычислять коэф| финиенты полинома ЖЕгалкина булевых функций даже тогда, когда их векторыистинности длины 2 подаются на вход непосредственно друг за другом. Последовательность их 2 нулей и ; единиц - коэффициентов полинома Жегалкинавырабатывается с задержкой на 2 -1 тактов по отношению к Лектору истинности, т е. коэффициент формируется в том же такте, в котором на вход поступает последнее значение булевой функции. Требуемый вид полинома Жегалкина задается величинами h ,..., h, хранимыми соответственно в триггерах 10, ... 10 и равными единице, если соответствующие неременные х,..., Xj инвертированы, и тождественными нулю в противном случае. Рассмотрим функционирование данного устройства для п 2, что описывается системой равенств (3). В первом такте счетчик 9 блока управления 1 находится в нулевом состоянии (00), на входе устройства присутствует послед ее значение fl булевой функции двух переменных, элементы задержки 2 и 3 хранят соот- . ветственно f и f,, а элемент задержки 2 содержит fg 0 h, f, в первом своем разряде и fg ® h,f во втором. В первом и втором . разрядах элемента задержки 32 имеем результаты обработки вектора истинности предыдущей булевой функции f ® iS соответственно. Нулевой потенциал с выхода 13t блока управления I подается через вход элемента И 5 на вход сумматора 8 по модулю арифметического блока 4 . Нуль в младшем ряде счетчика 9 обеспечивает елиничный потен циал на выходе 14 блока управления 1 и, следовательно, на входе элемента Н 6 ариф- метического блока 4(. Благедаря этому величина f через вход элемента И 6 поступает на вход сумматора 8 по модулю два. Сигнал с инверсного выхода первого разряда счетшка 9 обеспечивает прохождение величины 1ъ с выхода триггера 10 через вход элемента И 12 ; выход 15 блока управления 1 на вход элемента И 7 арифметического блока 4| вследствие чего f со входа функционального преобразователя умножается на h. и поступает на вход сумматора 8 по модулю два арифметического блока 4 . Следовательно, на выходе арифметического блока 4 имеем величину fj® h fj. Эта величина умножается элементом И 7 рифметического блока 4у на h и подается а вход сумматора по модулю два 8, hg посS1тупает на вход элемента И 7 с выхода триггера через вход элемента ТЛ 12„ выход 15л блока управлетшя 1 благодаря наличию еднничного потенциала на nimepcном выходе второго разряда счетчика 9. Логический нуль с выхода 13 блока управления 1 подается через вход элемента И 5 на вход сумматора 8 по модулю два арифметического блока 4з,. Благодаря потенциалу логического нуля на прямом выходе второго разряда счетчика 9 имеем единицу на выходе 14, блока управления 1, что обеспечивает прохождение на вход сумматора 8 по модулю два через вход элемента И 6 арифметического блока 4 величины fo®h f с выхода второго разряда элемента задержки 2. На выходе устройства имеем ( f & п-(f. и) h f). По окончанию такта элементы задержки и 3f хранят fj и fn соответственно. В первом и втором разрядах элемента задержки 2 имеем f Э hj f и . fo & li , а также f @ h. 2 ч 2. ® t первом и втором разрядах элемента задержки 3 Во втором такте первое значение f новой булевой функции поступает ira вход функциопального преобразователя. Благодаря наличию единицы в младше разряде счетчика 9 на выходе элемента И-НЕ И, имеем величину h. , которая через выход 14 ( блока управления 1 поступает на вход элемента И 6, где умножается на величину f j с выхода элемента задержки 2f. Полученный результат подается на вход гчгклхлатлгча пп R nnvmn ппя Я япнгЬллятмирг-.тггчгп сумматора по модулю два 8 арифметического блока 4. На другой вход сумматора 8 по модулю два через вход элемента И 5 с выхода элемента задержки 3 поступает величина f. На соответствующем входесумматора 8 по модулю два арифметического блока 4 имеем нуль, поступающий с инверсного выхода первого разряда счетчика 9 через вход элемента И 12/.выход 15, блока управлеМшя 1 и вход элемента И 7. В результате на выходе арифметического блока 4, полу, / чаем величину Поскольку во втором такте, также как и в первом, второй разряд счетчика 9 содержит 1гуль, то на входы сумматора 8 по модулю . два арифметического блока 4 поступают соответствснно нуль, сигнал с выхода элемента задержки 2 2. - fg, ® h, f, и велишна с выхода первого канала - fj ® h. fo умножаемая элементом И 7 на велитану h, которая подается с выхода триггера 102 через вход эл.смента 12 и выход 15 ч блока уп- . равления 1. На выходе устройства во втором такте имеем ( fgiSh, f,) ® ® 30По окончании второго такта величины и f засыпаются в элементы задержки 2, и 3|. соответственно. Элемент задержки 2содержит f @ h, fj в первом своем разряде и fn® h. f/ во втором. В первом и втрром разряде элемента задержки 3 имеем fQ(, и fg®h f., соответственно. В третьем такте содержимое счетчика 9 . составляет (10). Поэтому на выходах 13, 14 „, 15 15 и 132. 1, и п ил, 14-я, J устройства управления 1 имеем 0,1 h и 1, h О, соответственно. Сумматор 8 по модулю два арифметического блока 4 осуществляет сложение величины f с выхода элемента задержки 2 с величиной f ,, подаваемой па вход функционального преобразователя, которая предварительно умножается на h посредством элемента И 7. В результате на выходе арифметического блока 4 имеем foSh f. Сумматор по модулю два 8 арифметического блока 4 выполняет сложение величин fQ®h f., и f с выходов элементов задержки 3 и 22, соответственно, причем величина предварительно умножается на h2 с помощью элемента И 6 арифметического- блока 4 . Следовательно, в третьем такте на выходе функ- о ционального преобразователя имеем (f © h д )© /ir /х/г,и .J:( eb2(f,®h,fp. При переходе к четвертому такту в элементы задержки 2,| и 3 засылаются величины f и f J соответственно. В первом разряде элемента задержки 22 имеем , f,, а во втором разряде © 1 - В первом и втором разрядах элемен а задержки 3 содержатся величины f®h уч... .. - .г л J соответственно. В четвертом такте на входе функционального преобразователя присутствует значение f новой булевой функции, а счетчик 9 содержит (11). Единичные потенциалы с прямых выходов счетчика 9 поступают через выходы 131 и 13 устройства унравления 1 на входы „ арифметических блоков 4 и 4. Благодаря этому на входы сумматоров 8 по модулю два арифметических блоков 4 н 4 подаются величины и fi©h, f -с .выходов элементов задерх ки 3 и 22 соответственно. На выходах 14 и 14 блока управления 1 имеем величины h и h соответСтвенно, которые поступают на входы элементов И 6 .арифметических блоков 4 и 4 В результате f, и f с выходов элементов Задержки 2 и И 2 умножаются соответственно на h и Ъ„ посредством элементов И 6 и поступают на входы сумматоров 8 по модулю два арифметических блоков 4 4 и 4 2- Сигналы логического нуля с инверсных выходов счетчика 9 через входы

элементов И 2 и 12 поступают на входы 15/ и 15д блока управления 1, а затем через входы злементов И 7 - на вход сумматора 8 по модулю два арифметических блоков 4х и 4. Таким образом, в четвертом такте на выходах арифметических блоков 4 и 4 имеем величины R, f, и (fg® h ) @ ®hp(f®li fj) соответственно.

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

ФУНКЦИОНАЛЬНЫЙ ПРЕОБРАЗОВАТЕЛЬ, содержащий первую группу из п

2п

п

I

/II

Риг.1