Функциональный преобразователь

 

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

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

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

РЕСПУБЛИН (l9(SU(II) 4(51) G 06 F 15/332 и

° ь 1 (ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3652364/24 — 24 (22) 17.10.83 (46) 15.02.85. Бюл. И 6 (72) В. А. Пащенко (71) Днепропетровский ордена Трудового

Красного Знамени государственный университет им. 300-летия воссоединения Украины с Россией (53) 681.32 (088.8) (56) 1. Авторское свидетельство СССР

1(1О 781822, кл. G 06 F 15/31, 1979.

2. Авторское свидетельство СССР N 1001107, кл. G 06 F 15/332, !982 (прототип). (54) (57) ФУНКЦИОНАЛЬНЫЙ ПРЕОБРАЗОВА— п

ТЕЛЬ, содержащий первую группу из п (2— размер преобразования) элементов задержки, и арифметических блоков, причем i-й (i=1,п) арифметический блок содержит первый элемент И и сумматор по модулю два, первый вход которого подключен к выходу первого элемента И, первый вход которого подключен к выходу i-го элемента задержки первой группы, блок управления, содержащий счетчик, прямой выход i-ro (i=1,n) разряда которого подключен к второму входу первого элемента И i-ro арифметического блока, о тличающийся тем,что,сцелью расширения функциональных возможностей за счет реализации полинома Жегалкина заданного вида, в который каждая переменная входит непосредственно или с инверсией, в преобразователь введены вторая группа нэ и элементов задержки, в 1-й арифметический блок — второй и третий элементы И, а в блок управления — nэлементов И,,и элементов И вЂ” HE и птриггеров,,причем в i-м арифметическом блоке второй и третий входы сумматора чо модулю два подключены к выходам соответственно второго и третьего элементов И, первые входы которых подключены к выходам соответственно i-го элемента И вЂ” НЕ и i-го элемента И блока управления, первые входы которых подключены к выходу i-го триггера блока управления, прямой. и инверсный выходы i-го разряда счетчика блока управления подключены к вторым входам соответственно i-ro элемента И вЂ” HE .и i-го элемента И блока управления, выход сумматора по 3 модулю два j-го (j= 1,п — 1) арифметического блока подключен к второму входу третьего элемента И (j+1)-го арифметического блока и входу (j+1) ãî элемента задержки. второй группы, выход которого подключен к второму входу второго элемента И (j+1)-ãî арифметического блока и входу (j+1)-го элемента задержки первой группы, выход сумматора по модулю два и-го арифметического блока является информационным выходом преобразователя, второй вход второго элемента И первого арифметического блока соединен. с входом первого элемента задержки первой группы и подключен к выходу первого элемента задержки второй группы, вход которого соединен с вторым входом третьего элемента И первого арифметического блока и является информационным входом преобразователя.!

1401

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

1 ния) элементов задержки, и арифметических блоков, причем I-й(=1,п) арифметический блок содержит первый элемент И и сумматор по модулю два, первый вход которого подключен к выходу элемента И, первый вход которого подключен к выходу i-го элемента задержки первой группы, блок управления, содержащий счетчйк, прямой выход i-ro(i=1,n) разряда которого подключен к второму входу первого элемента И i-ro арифметического 55 блока, введены вторая группа из и элементов задержки, в i-й арифметический блок — второй и третий элементы И, а в блок управле1

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

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

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

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

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

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

30 2 ния — и элементов И, и элементов И -IIE и и триггеров, причем в i-м арифметическом блоке второй и третий входы сумматора по модулю два подключены к выходам соответственно второго и третьего элементов И, первые входы которых подключены к выходам соответственно i-го элемента И--H}.; и

i-ro элемент И блока управления, первые входы которых подключены к выходу I-lo триггера блока управления, прямой и инверсный выходы i-го разряда счетчика блока управления подключены к вторым входам соответственно i-го элемента И вЂ” НЕ и !-го элемента И блока управления, выход сумматора по модулю два )-го (j = 1,n — 1) арифметического блока подключен к второму входу третьего элемента И (j+1)-го арифметического блока и входу (j+1) -го элемента задержки второй группы, выход которого подключен .ко второму входу второго элемента И (j+I)го арифметического блока и входу ()+1)-ro элемента задержки первой группы, выход сумматора по модулю два и-го арифметического блока является информационным выходом преобразователя, второй вход второго элемента И первого арифметического блока соединен с входом первого элемента задержки первой группы и подключен к выходу первого элемента задержки второй группы, вход которого соединен с вторым входом третьего элемента И первого арифметического блока и является информационным входом преобразователя.

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

Функциональный преобразователь состоит из блока управления 1, элементов задержки

2,, 2, и 3, ...3,, арифметических блоков 41, ...4п, каждый из которых содержит элементы И 5, 6 и 7 и сумматор 8 по модулю два, блок управления 1 состоит из и-разрядного счетчика 9, триггеров 10», ... 10,, элементов И вЂ” НЕ 11„, ... 11„и элементов

И 12,, ... 12„. Выходы 13.1, ...13, ... 14,...

14п, 1 5„,... 15„,блока управления 1 подключены соответственно к входам элементов

5, 6 и 7 арифметических блоков 41, ... 4>.

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

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

î ï ((-(Нп

hn H((-(35

F (0,0)

F (0,1)

F (1,0)

F (1,1) },и

1h(}7

16,67

1 Б, }(7

62 7 г

Ь2

h„

Fil

h, h, fo

f( (3) 2

3 1 1401

Пусть задана булева функция своим вектором истинности t = (f т2(), где может быть или нулем, или единицей (} = О, 1,...,2" ), Произвольная булева функция представима полиномом Жегалкина следующего вида (Ь..., ., =Х .., K F(k „,„,,4,) x„" ... х"„,(<)

"((= 0 K (= O и, где — знак суммы по модулю цва, х, это или х; или x (I=1,...n), à g ь 1, если К„ =О. Величины F(k„,..., k(} могут быть

10 или нулями, или единицами.

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

Например, при и = 2и х = х, х,-х имеем полином 20

} (, x ) = F (0 0)(Q F (0,1) . х (F (1,0) х79Е (1,1) ха х .

Чтобы получить вектор коэффициентов F(k», ... !((), необходимо вектор f умножить íà и-кратное прямое (кронекерово) произведение матрицы () (2) при i =1,...n. Если переменная х, не инвертирована, то hi =О, в противном. случае hi = 1

С целью нахождения и-кратного прямого про-, . изведения Н матриц (2) можно воспользоваться следующим рекурсивным соотношением

n-( где Н, — матрица размером 2 х 2 являющаяся (n — 1) -кратным кронекеровым произведением матриц (2), рассматриваемых при

i=1,...n — 1.

При и = 2 умножение вектора значений функции f (х,...,х„) на матрицу Н записывается

1 и так

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

F(0,0) =(f, 9 0 0+ }i()®0 ® h7(f790®h, fQ, F(0,1) — (и(f Ы Ф 90)90 З и (h 1 О+1 90), (3)

F(1,0)= h2 (Ф ЭОЫ }(й, )Я(Ф 90 9 h()®0, Р(1,1)=h2(h fief, ЕО)а(Б,,аУО)ао

30 4

Для п = 2 алгоритм функционирования данного устройства определяется системой равенств (3).

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

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

Требуемый вид полинома Жегалкнна задается величинами h l,..., hn, хранимыми соответственно в триггерах 10, ... 10п и равными единице, 1 если соответствующие переменные х,},..., х,„ инвертированы и тождественными нулю в про) тивном случае.

Рассмотрим функционирование данного устройства для n = 2, что описывается системой равенств (3).

В первом такте счетчик 9 блока управления

l,находится в нулевом состоянии (00),навходе устройства присутствует последнее значение f> булевой функции двух переменных, элементы задержки 2! и 3! хранят соот-, l ветственно f> и f,, а элемент задержки 22 содержит 1 О+ й(1„в первом своем разряде и 1 О+ h(f во втором. В первом и втором (1 разрядах элемента задержки 37 имеем результаты обработки вектора истинности предыдущей булевой функции 1 96 13 и Ф 9 }(,Ф. соответственно.

Нулевой потенциал с выхода 13» блока управления 1 подается через вход элемента

И 5 на вход сумматора 8 по модулю арифметического блока 4 . Нуль в младшем раз». ряде счетчика 9 обеспечивает елиничный потек циал на выходе 14„блока управления 1 и, следовательно, на входе элемента И 6 арифметического блока 4г. Благодаря этому вели( чина f через вход элемента И 6 поступает на вход сумматора 8 по модулю два. Сигнал с инверсного выхода первого разряда счетчика 9 обеспечивает прохождение величины }1} с выхода триггера 10 через вход элемента

И 12,выход 15} блока управления 1 на вход элемента И 7 арифметического блока 4

9 вследствие чего f со входа функционального преобразователя умножается на h и поступает на вход сумматора 8 по модулю два арифметического блока 4 . Следовательно, на выходе арифметического блока 4} имеем величину

f2 9 hf f3

Эта величина умножается элементом И 7 арифметического блока 4 íà h и подается на вход сумматора по модулю два 8, h2 пос1140130 тупает на вход элемента И 7 с выхода триггера 10ч через вход элемента И 122 и выход lS блока управления 1 благодаря наличию единичного потенциала на инверсном выходе второго разряда счетчика 9. Логический нуль с выхода 13< блока управления 1 подается через вход элемента И S на вход сумматора 8 по модулю два арифметического блока 4(. Благодаря потенциалу логического нуля на прямом выходе второго 10 разряда счетчика 9 имеем единицу на выходе 14, блока управления 1, что обеспечивает прохождение на вход сумматора 8 по модулю два через вход элемента И 6 арифмети-! ( ческого блока 42 величины 1о Я h, f с 15 выхода второго разряда элемента задержки !

2,. На выходе устройства имеем (f Оh„ô

®п (f, 9 h, t ).

По окончанию такта элементы задержки 24 (( и 3 хранят f> и 1 соответственно. В пер- 20 вом и втором разрядах элемента задержки 2

I (( имеем 28 "1 f> и о О h< 1, а также

F I

f> 0 1 f> и f2 9 h< f Ч B первом N втором разрядах элемента задержки 3 . (!

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

Благодаря наличию единицы в младшем разряде счетчика 9 на выходе элемента

И вЂ” НЕ 11 имеем величину h которая через выход 14(блока управления 1 поступает на вход элемента И 6, где умножается ( на величину flI с выхода элемента задержки

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

35 блока 4 . На другой вход сумматора 8 по модулю два через вход элемента И 5 с выхода элемента задержки 3 поступает величина f . .На соответствующем входе сумматора

8 по модулю два арифметического блока 44 имеем нуль, поступающий с инверсного выхода первого разряда счетчика 9 через вход элемента И 12 (выход 15< блока управле ния 1 и вход элемента И 7. В результате на выходе арифметического блока 4 полу-! («Р1, f

Поскольку во втором такте, также как и в первом, второй разряд счетчика 9 содержит нуль, то на входы сумматора 8 по модулю . два арифметического блока 4 поступают соответствснно нуль, сигнал с выхода элемента ! задержки 22 — f> 8 h1 f(и величина с вы( хода первого канала — f ® hl f3 умножае2 мая элементом И 7 на велип ну h2, которая подается с выхода триггера 10 через вход эп.емента 12 и выход 15чблокауп- . равпения 1. На выходе устройства во втором такте имеем (f<9h, f,) (-(h2 (f F((h< fq), По окончании второго такта величины и 1 засыпаются в элементы задержки 2, (F и 3 соответственно. Элемент задержки 2 ! содержит 1 9 h < f в первом своем разряде ! ( и f20 6 f во втором. В первом и втором ! разряде элемента задержки 3.(имеем f0(3h„fI (( и f0 9 h1 f соответственно.

В третьем такте содержимое счетчика 9 составляет (10). Поэтому на выходах 13,, 14(, 153 и 132 14, 15 устройства управления l имеем 0,1 h и 1, h2 О, соответственно. Сумматор 8 по модулю два арифметического блока 4, осуществляет сложение величины f0 с выхода элемента задержt (! ки 2(с величиной f, подаваемой на вход функционального преобразователя, которая предварительно умножается на h посредством элемента И 7. В результате на выходе арифметического блока 4! имеем f08 h„f<. Сум-! ((( матор по модулю два 8 арифметического бпо-! ка 42выполняет сложение величин 1 Фh I f„и (I

f 2 0 h > f > с выходов элементов задержки 32

1 I и 22, соответственно, причем величина 1 96„f> предварительно умножается íà hZ с помощью элемента И 6 арифметического блока 4 . Следовательно, в третьем такте на выходе функ-- . ! ционапьного преобразователя имеем (1 Q+(h „фО+

8Ti2(f 0+h1 )

При переходе к четвертому такту в элементы (((( задержки 21 и 3 засыпаются величины 1„и соответственно. В первом разряде элемента за(! (( держки 22 имеем 9Ь, 11, а во втором разряде(- (f<9h fq. В первом и втором разрядах элемен-! ! та задержки 31 содержатся величины f 8h1 ! (2 и f<9h 1„соответственно.

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

Ц новой булевой функции, а счетчик 9 содержит (Il). Единичные потенциалы с прямых выходов счетчика 9 поступают через выходы

13< и 132 устройства управления 1 на входы элемента И 5 арифметических блоков 4 и 4 . г

Благодаря этому на входы сумматоров 8 по модулю два арифметических блоков 4 и 4 н подаются величины f u f & h „1 с выходов элементов задержки 3 и 22 соответственно. На выходах 14 и 142 блока управления 1 имеем величины Б< и h2 соответ,ственно, которые поступают на входы элементов И 6 арифметических блоков 4 и 4 . и (1

В результате 1, и fq9h< f > c выходов элементов задержки 2 и И 2 умножаются соответственно íà h< и h посредством элементов И б и поступают на входы сумматоров 8 по модулю два арифметических блоков 4 < и 42. Сигналы логического нуля с инверсных выходов счетчика 9 через входы

7 114О1ЗО 8 элементов И 12 и 12 поступают на входы Технико-экономический эффект от использова15 и 15 блока управления 1, а затем ния функционального преобразователя состоит в

1 Я через входы элементов И 7 — на вход сумма- возможности автоматизировать нроцссснахождетора 8 по модулю два арифметических блоков ния для данной булевой функции и переменных не

4 и 4 . Таким образом в четвертом такте 5 только единственного полинома Жегалкина, в коЯ

) на выходах арифметических блоков 4 и 4 тором всепеременные не инвертированы, но и любоимеем величины f Þ h, Ф, и (Фо9 h f) О+ го из 2" возможных полиномов,отличающихся друг

0+) h (f 9h 1 ) соответственно. г от друта способом инвертирования переменных.

1И01З0

Фиг.2

14ff

15п

ВНИИПИ Заказ 265/38 Тираж 710 Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4