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

 

. Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с системой команд высокого уровня, ориентированной на класс логико-комбинаторных задач. Цель изобретения - повышение быстродействия устройства для арифметического разложения симметрических булевых функций. Поставленная цель достигается тем, что устройство для арифметического разложения симметрических булевых функций п аргументов содержит п+1 группу вычитателей, вход константы логического нуля,- п+1 входов .. п+1 выходов первой группы и п+1 выходов второй группы. Устройство работает следующим образом. На входы устройства подаются компоненты двоичного кода л (f) разлагаемой симметрической булевой функции (xi, X2Хп). На выходах первой группы формируются компоненты вектора р (f), являющиеся коэффициентами положительного поляризованного арифметического полинома G(f) функции f, а на выходах второй группы - компоненты векторов A (f), являющиеся коэффициентами отрицательно поляризованного арифметического полинома H(f). 1 ил.

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

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

РЕСПУБЛИК (я)з G 06 F 7/00

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21} 4677108/24 (22) 11,04.89 (46) 07,02.92. Бюл. ¹ 5 (72) Л.Б.Авгуль, В,П.Супрун, Э.К.Мачикенас и Н.А.Егоров (53) 681.3(088.8) (56) Авторское свидетельство СССР

¹ 1633388, кл. G 06 F 7/00, G 06 F 7/38, 30.03.89.

Кухарев Г.А., Тропченко А.Ю., Шмерко В.П. Систолические процессоры для обработки сигналов. — Минск: Белоруссия, 1988, с. 101 — 105, рис. 4.4.12, (54) УСТРОЙСТВО ДЛЯ АРИФМЕТИЧЕСКОГО РАЗЛОЖЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ (57).Изобретение относится к вычислительной технике и предназначено для использования в ЭВМ и спецпроцессорах с системой команд высокого уровня, ориентированной на класс логико-комбинаторных задач. Цель изобретения — повышение быстродействия

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

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

На чертеже представлена схема устройства для арифметического разложения с.б.ф, при n = 5, Устройство содержит и-2(1-1) вычитателей 1-5 первой группы. и-2(1-1) вычитателей

6-10 второй группы и-2(2-1) вычитателей 1113 третьей группы, и-2(2-1) вычитателей 1416 четвертой группы, и-2(3-1) вычитатель 17. Ж 1711147 А1 устройства для арифметического разложения симметрических булевых функций. Поставленная цель достигается тем, что устройство для арифметического разложения симметрических булевых функций и аргументов содержит и+1 rpynny вычитателей, вход константы логического нуля; и+1 входов„п+1 выходов первой группы и и+1 выходов второй группы. Устройство работает следующим образом. На входы устройства подаются компоненты двоичного кода л (f) разлагаемой симметрической булевой функции f=f(x>, х2,..., xn) На выходах первой группы формируются компоненты вектора р (0. являющиеся коэффициентами положительного поляризованного арифметического полинома G(f) функции f, а на выходах второй группы — компоненты векторов А (f), являющиеся коэффициентами отрицательно поляризованного арифметического полинома H(f). 1 ил. (пятой группы, и-2(3-1) вычитатель 18 шестой группы, и+1 входов 19-24, вход 25 константы логического нуля, и+1 выходов 26-3 I первой группы, и+1 выходов 32-37 второй группы.

Пусть f=f(x>. т..., х} — с,б.ф. и аргументов х1, х2 " xn и л(т} = (o л1...„2тп) двоичный код f, где ztj — значение f на (любом) наборе значений и аргументов с i единицами, I-0,1, .„и, Поскольку f — с.б.ф., то в ее арифметической- .йолином G(f) аргументы x>, xz,. „хл входят "симметрично".

Следовательно, полином G(f) однозначно задается (и+1)-разрядным вектором p (F) =

- фЪ. р1, .../Ъ}, гдеpi - целочисленный коэф-. фициент, приписанный (всем), слагаемым ранга i полинома G(f). i=0,1...„п. Вместе с

1711147 тем для с.б,ф. f существует еще один арифметический полином H(f). в котором все аргуМЕНТЫ Х1, Х2,..., Хп ПОЛЯРИЗОВаНЫ ОтРИЦатЕЛЬНО (считается, что в полиноме G(f) аргументы поляризованы положительно), т.е. аргумен- 5 тЫ Х1, X2,..., Xn ВХОдят В H(f) ТОЛЬКО С ОтрИцанием. По аналогии с G(f) полинам H(f) также может быть однозначно задан (и+1)РазРЯдным вектоРом k(f) (Ло. Л1...,, Лп),. причем область определения целочис- 10 ленных коэффициентов 4 совпадает с областью определения коэффициентов р и имеет место

I@I 2, li4I 2, где i=0,1,..., n, 15

Полиномы G(f) и H(f) в общем виде можно записать следующим образом:

G(f) = po +p1 (Х1+Х2+ +Xn)+

Р2 (Х 1Х2+ . +Х1Хп+Х2ХЗ+ +Xn-1хп)+...

+ Pn X 1X2...Xn, H(f)=- Ло + Л1 (x1+x2+...+õn)+

+ Л2 (X1X2+...+Х1xn+ X2X3+... 4xn-1Хп)+...

+ Лп Х1Х2... Xп

Поскольку арифметические полимоны

G(f) и Н(1) однозначно определяются векторамир()=(р,,р1, ...,р,) и Л{1)=(Л,Л1,. „Л,), то задача арифметического разложения с.б.ф. f сводится к преобразованию вектора x(f) e векторы p (f) и Л (().

Указанные преобразования заключаются в формировании последовательности векторов В, В,..., В", где В = 7г(1), а значениЯ компонент вектоРа В =(/jо,P, ..., ф) вычисляются по формуле

Po P +1, Pi — 1 где i=0,1,..., n-j; j=1.2„, и.

Тогда

p(f j = фо, /4, / о, jC, „Д)

Л({) = фп + 1 j>n, / п — 1 / п — 2...;Д (1) 45 где

f ,В

-и /io, если и четное; о—

Д, если и нечетное.

Пример. Пусть и=-4 и с.б.ф. f=f(x1, х2, 50 хз, x4) задана вектором 7т(1}=(0,1, 1,0, 1), Последовательность векторов имеет вид

В = (0,1, 1,0, 1);

В = (1,0, -1,1);

В = (-1, -1,2);

В, = (0,3);

В = (3). о 1 и

Векторы В, В „., В" образуют треугольную таблицу с основанием Р, которая для данного примера имеет вид р.=О 1 1 О 1«Ло

Р1 = 1 0 -1 1 = Л1

p2= 1 -1 2= Л2 рз=О 3= Лз

p-, = -=3--L

Отсюда следует, что p(f) = (0,1, -1. 0,3):

Л (f) = (1, -1,2, -3,3).

Следовательно, G(f)=(X1+X2+X3+X4) (Х1Х2+Х1ХЗ+Х1Х4+

+ Х2XЗ+X2X4+XЗX4)+ЗХ1X2XЗХ4;

H(f)= i -(х1+х2+х З+х4)+2(х1х2+х1хЗ+

+ Х1Х4+Х2ХЗ+Х2Х4+ХЗХ4)- 3(Х1Х2ХЗ+

+ Х1Х2Х4+Х1ХЗХ4+Х2ХЗХ4)+ЗХ1Х2ХЗХ4

Устройство работает следующим образом..

На i-й (i=1,2„„, и+1) вход устройства подается (и)-я компонента 7гь1 вектора v(f) раЗЛаГаЕМОй фуНКцИИ f=f{X1, X2„... Хп), На ВЫходах первой группы формируются компоненты вектора p (f), на выходах второй группы — компоненты вектора Л (f).

Так, если на входы 19-25 устройства подать соответственно компоненты ло ...

1т вектора л (1)=(0,1, 0,1, 1,0), на выходах 2631 первой группы формируются соответственно компоненты оо ... р5 вектораp(f}=(0,1, -2,4, -7,10), на выходах 32-37 второй группы — соответственно компоненты Ло ... Ъ вектора Л (f)=(0,1, -1,0, 3, -10).

Разрядность вычитателей определяется числом разрядов, необходимых для представления максимально возможного по абсолютной величине коэффициента арифметического полимона, Тогда с учетом знакового разряда разрядность вычитателей равна n+1. Причем для представления операндов (данных с промежуточных вычислений или окончательных результатов) используется дополнительный код, который формируется автоматически при условии блокирования сигнала заема из старшего (знакового) разряда вычитателей.

Следовательно, на входы вычитателей первой группы подан (п+1)-разряднь1й код

Î0...0а, в котором первый (старший) разряд знаковый. На выходе этих вычитателей числа (положительные и отрицательные) уже представлены в дополнительном коде.

Здесь используется тот факт, что результат выполнения операций вычитания над дополнительными кодами чисел всегда дает разность. представленную в дополнитель1711147

"о"

Вход 25

00000

Pv л5

Вход 21 Вход 22 Вход 23 Вход 24

000000 000001 000001 000000= 50

"о И(Вход 19 Вход 20

Р,=ОООООО ООООО

Выход выч. 5 !

»11!

Выход выч.4

000000

Выход вый.3

000001

Выход выч,2

1 1 1 1 1 1

Выход выч.l

$(=000001

Выход выч. 8

111111

Выход выч.10

000001=9(Выход выч,9

1»1» -=?l, Выход выч.7

000010

Выход выч.6

32=1»»0

Выход выч.13

000000

Выход выч.12

i » 10!

Выход выч. » . =000!00

Выход Выход выч.!5 выч.16

0000» = A4 000000=?л5

Выход выч.14 4 =1 1 1 001

Выход выч.17 р5 -О О 1 О 1 О

Выход выч.18

110110= Ф 5

Ро =000000 =О „; P t =000001, =1„;

Р =(11» 102jgon =-2 <о Ру =000100 =4 (o, p4 =$» 1001q)hon 7(о, p5 — — 001010 =10(o, Яо --ОООООС =; % л =000001 g -1 ло

% =(11i! i!Ä„,„=-10; Л+ =000000 =0«.,, =0000» -3(о, Ъ5 =(i10»01 =-10(д .

Отсюда ном коде, если заем из знакового разряда заблокирован (не используется).

В каждой четной группе использованы дополнительные вычитатели, на входы уменьшаемого которых подаются сигналы логического нуля, т.е. (n+1)-разрядные коды

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

Устройство для арифметического разложения симметрических булевых функций, содержащее вычитатели, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, вычитатели образуют и+1 группу (n — количество аргументов разлагаемой симметрической булевой функции), (2r-1)-я и 2г-я (r=1,2.... )n/2() из которых содержат по п -2(г-1) еычитателей, первый вход устройства соединен с входом вычитаемого первого вычитателя первой группы и первым выходом первой группы выходов устройства, i-й вход устройства (i 2, 3,..., n) соединен с входом вычитаемого i-го вычитателя первой группы и входом уменьшаемого (i-1)-го вычитателя первой группы, (n+1)-й вход устройства соединен с входом уменьшаемого п-го вычитателя первой группы и первым выходом второй группы выходов устройства, выход первого вычитателя (1-1)-й группы соединен с i-м выходом

00.....0. Назначение этих вычитателей состоит в изменении знаков соответствующих коэффициентов согласно (1)

Пример процесса формирования ком5 понент векторовp(f) и k(f) из вектора л (f)=(0,1, 0,1, 1,0) устройством: первой группы выходов устройства и входом вычитаемого первого вычитателя 1-й группы, выход первого вычитателя и-й группы соединен с (и+1)-м выходом первой группы выходов устройства, выход k-го вычитателя р-й группы (k=2, 3„... и-р; р=1, 2,..., n-2) соединен с входом уменьшаемого

k-ro вычитателя (р+1)-й группы и входом еычитаемого (k-1)-го вычитателя (р+1)-й группы. выход (и-i+2)ro еычитателя (i-1)-й группы соединен с входом уменьшаемого (и-i+1)-ro вычитателя i-й группы, вход вычитаемого (n-2(r-1))-го вычитателя 2r-й группы соединен с выходом (n-2(r-1))-го вычитателя (2г-1)-й группы, вход уменьшаемого (и-2(г-1))-го вычитателя 2r-й группы соединен с входом константы логического нуля, а выход — с (г+1)-м выходом второй группы выходов устройства, ()n/2(+!+1)-й выход второй группы выходов устройства соединен с выходом (n-2l+1)-го вычитателя

2l-й группы (l=1, 2„„)(n-1)/2().

1711147

Составитель В, Сорокин

Техред M.Mîðãåíòàë Корректор Н. Король

Редактор И. Шмакова

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

Заказ 340 Тираж Подписное

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

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