Устройство для арифметического разложения логических функций Советский патент 1991 года по МПК G06F5/00 G06F7/00 

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

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

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

Устройство (фиг.1) содержит счетчик 1, дешифратор 2, элемент И 3, коммутаторов 4,,-4, триггер 5, регистров, 6,,-6т, 2h H 4 вычитателя 7 4 - , вход 8 разрешени обнуления, вход 9 разрешения счета, тактовый вход 10, .п 8 информационных входов 11 - 11g.

Первый коммутатор (фиг.2) содержи четыре элемента И-ИЛИ 12 - 12, п + управлямпих входа 13 - 134, три группы информационных входов

- 15, и 16д 16 4 и

Ч

14 4 - 14ц, 15, - иц и i о 4 четыре пыхода 17 4 - 174Йторой коммутатор (фиг.З) содержи четыре элемента И 18 4 - 1&4 элемент И-ИЛИ 19, элемент НЕ 20, управляющий вход 21, информационный вход 22, группу информационных входов 23 - 24S, пять выходов 24 4 - 245.

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

Очевидно, имеет место

добных членов получаем арифметический полином 0(F) функции F.

В общем случае для логической функции п переменных F F (х,, х„,... ...,хл) арифметический полином имеет вид

2П-.

ОкG(F) 8К. П х , (2)

К - 0 -

где (К) (Ск,, с«2 ,..., n-разрядный двоичный эквивалент числа К,т.е„

.

К о К 2 : для любой

переменной x;(i 1, 2,...,п) имеет место

Ь:

х , если Јk ;

1,

25

1, если Ik; О,

g(F) (р,0, ри , . . . , р,.,1 - вектор коэффициентов арифметического полинома .

Как следует из (2), полином f,(F) при п 3 имеет вид

fi(F) Р,0 + + Г, г 2 +

+ 85Х2ХЭ + Р 4Х1 + Р. +

+ R6xrx2. + «тх1хгхзСледует также отметить, что р,0Ј ,l}, а конъюнкция ранга с (г 1, 2,...,п) имеет коэффициент а (О, для которого справпдчичо

45

/а(с)/ и 21

И)

х У;

(1)

- 2х у

€{0,1}.

где х

Если в некотором выражении логической функции F сделать замену логических операций арифметическими согласно (1), то после приведения почто

Кроме того, нетрудно установить, В ; F (1.1...1) и р.

g j (nod 2), где PJ - коэффициент i-ro слагаемого полинома } огалкиня P(F) функции F и i 0,1,...,.

Исходным для нахождения вектора коэффициентов арифметического полинома 0(F) логической функции F F(x,, x, ...,xn) является се гаПии- на истинное ги U)(F) (с00, Сд}, , . . . , C0,jp(}, где G); - тначенне F на i-м

наборе значений переменных х хп и i 0,1,...,.

Н

Метод нахождения вектора g(F) заключается в следующем: полагаем,что

(h( Ьг, ....) CO(F), формируем последовательность векторов

,- иг ч И

.| , и ,...,Н , где компоненты некто- pa HJ - (h ,, hЈ,...,hJn) по формулам

)

h2i m 4-t

hJ ,Н

( + t (2Ul)m+t

- h

11 m+ f

где

2

n-j

i 0,1...

1,2...

in

,m

, 2--,.

1,2, . . . ,n

тогда H g(F) .

Счетчик 1 имеет разрядность,равную г (n+1)Ј, где п - количество переменных разлагаемой логической функции. Состояние счетчика определяется дешифратором 2, который преобразует позиционный двоичный код состояния счетчика в унитарный код на своем выходе. Сигнал на 1-м (1 1,2,..., п-Н) выходе дешифратора 2 обеспечивает подключение соответствующих компонент вектора II к входам регистров, непосредственно запись в которые происходит в момент окончания тактовых импульсов, подающихся на тактовый вход 10.

25

Триггер 5 и регистры 6, для хранения компонент

40

о 7 служат векторов II

(1 1, 2, .. ., п+1) . Поскольку h, W0, то для хранения зтого компонента достаточно одного триггера, состояние которого в процессе работы не изменяется . Занесение информации в триггер 5 осуществляется в начапе работы устройства после обну. ения счетчика 1 по заднему-фронту первого тактового импульса, подаваемого на тактовый вход 10 устройства. В качестве триггера 5 в устройстве может быть использован синхронный двухступенчатый D-триггер. Компоненты векторов HJ (кроме h() представляют собой целые числа как положительные, т. и отрицательные, где j 1,2,...,п. Для хранения в регистрах и выполнения

операции вычитания компоненты hj, (j 1,2,...,n; p 2,3,...,2 ) представляются в дополнительном коде, причем под знак отводится один разряд. С учетом знакового разряда и соотношения (3) разрядность регистров для

i , хранения результатов промежуточных

вычислений и коэффициентов р р п,

будет равна п+1, бит,разрядность регистра для хранения коэффициентов gnh - п+2 бит. Так, для рассматриваемого примера (п 3, фиг.1) разрядность регистров 6 ( - 6g равна 4 бит, вычисляютсяразрядность регистра 67 - 5 бит.

ЮРегистры строятся на основе двух

ступенчатых синхронных триггеров, запись информации в которые осуществляется по заднему фронту тактовых импульсов, подаваемых на тактовый (4) 15 вход 10.

Вычитатели 1 - 14 имеют разрядность, равную разрядности соответ- ствукяцих регистров, подключаемых к их входам, причем в вычитании уча - 20 ствуют все разряды, включая знаковый. При этом заем из знакового разряда блокируется (т.е. не используется), чем достигается автоматическое формирование дополнительного кода разрядности, начиняя с первого такта вычислений. Вычитатели комбинационные, параллельного типа.

Коммутаторы k - 4-j классические, типа И-ИЛИ. Их управляющие входы соединены с соо ветствукп-рн-ги выходами дешифратора 2, а информационные - с выходами соответствующих регистров и вычитателей. Подключение входов/выходов коммутаторов следует из операционного графа алгоритма (фиг. 4) с учетом его n-такт овой реапи- зации на одном столбце из вычитателей. Соединение второй группы-информационных входов коммутаторов при разрешающем сигнале на втором, третьем и четвертом выходах дешифратора 2 (соответственно состояния счетчика 0...01...0...10,0...11) отмечено на фиг . 1. Коммутаторы по управляю- 45 щим входам являются (п+1)-канальными, канальноеть по информационным входам определяется разрядностью соответствующих регистров.

В качестве примера на фиг.2 пред- 50 ставлена функциональная схема первого коммутатора 4, содержаг(его четыре элемента И-ИЛИ 12 ( - 124 (по числу разрядов регистра 6) управляющих входа 134 134 на которые 55 подаются соответственно сигналы

30

Ь0,...,ЬЭ с выходов дешифратора 2, где i (i 0, 1, 2, 3) - сигнал на (i+D-м выходе дешифратора 2, соответствующий состоянию i счетчика 1.

Ь0,...,ЬЭ с выходов дешифратора 2, где i (i 0, 1, 2, 3) - сигнал на (i+D-м выходе дешифратора 2, соответствующий состоянию i счетчика 1.

При bj 1 к входам коммутатора

4, подключаются выходы 14, - 14 о п

вычитателя 7 ; при Ь 1 - выходы 15 - 15 вычитателя при Ь3 1 выходы 16( - 16 регистра 6б. Выходы 17 1 4 коммутатора 46 соединены с информационными входами регистра 6

Коммутаторы 4 - 45 имеют аналогичную структуру. Несколько отлича- ется структура коммутатора 4, (Фиг.З поскольку вторая группа его информационных входов 23 4 - 235 соединена только с выходами вычитателя 7.. Управляющий вход 21 коммутатора соеди- нен с первым выходом дешифратора 2. При этом при Ь0 1 обеспечивается подключение информационного входа 22 первой группы к младшему разряду регистра 6, в который по первому так-

товому импульсу заносится компонент h° С07 вектора Н° . При b, V b2V Ь3 1 (что эквивалентно Ь0 1) вторая группа информационных входов 23, - 235 подключается к выходам 24 ц - 24 5 коммутатора, тем самым обеспечивая запись информации в регистр 6 - с выходов вычитателя 7Ч по заднему фронту второго, третьего и четвертого тактовых импульсов, подаваемых на вход 10.

Как следует из фиг.2 и 3, запись вектора CO(F) в регистры 6 ц - 67 осуществляется таким образом,что компонент. С0г(с 1, 2,...,7) записывается

в младший разряд регистра 6, в остальные разряды которого записываются нули, т.е. содержимое регистра 6г равно 000с0г, причем старший разряд регистра - знаковый.

В качестве примера использования формул (4) рассмотрим последовательность шагов для построения полинома G(F) логической функции трех переменных F F(x, x, хэ), заданной таблицей истинности CO(F) ( О, 1, О, 1, 1, 0, 0, 1).

I

В таком случае имеем следующую

последовательность векторов:

Н Н4

8 (0,1,0,1,1,0,0,1); (0,1,0,1,1,1,0,0);

Н

I

(0,1,0,0,1-1,-1,,1);

Н (0,1,0,0,1 -2, -1,2),

g(F) (0,1,0,0,1 -2, -1,2) G(F) х3 + х , - 2х,хэ - , + 2 х„хгхг

Q ; 0

5

0

5

0

Операционный граф алгоритма арифметического разложения логических функций при п 3 представлен на фиг.4. Вершины графа соответствуют выполнению операций вычитания. Функционирование устройства основано на n-тактной реализации операционного графа алгоритма, причем на j-м (J - 1, 2,...,п) такте устройство преобразует вектор Н в вектор II1.

Работу устройства рассмотрим подробно на примере его построения при п 3 (фиг.1).

На вход разрешения обнуления подается импульс, по заднему фронту которого происходит обнуление счетчика 1. При этом на первом выходе дешифратора 2 появляется сигнал логической единицы, разрешающий прием информации в триггер 5 и .регистры 6., -67 через коммутаторы 4, -4, с ин-- формационных входов 11 , - 11g устройства, на которые подаются соответственно компоненты CJ0- u)7 вектора значений преобразуемой логической функции трех переменных. На тактовый вход 10 подается тактовый импульс, по зад1- нему фронту которого непосредственно значения С00 - Ь)7 с информационных входов 11, - 11g устройства заносятся в триггер 5 и регистры 64 - 67. Отметим, что в триггере 5 и регистрах 6 - 6 7 будет следующее распределение информации:

45

6,

(оо) (сэ4) (со,)

(Q9) (СО,) (С04) (W3) (G)7)

50

Очевидно, на выходах вьгштателей

Л

5

7). будут сформированы в дополнительном коде соответственно компоненты hj,...,hg вектора Нг.

На вход 9 разрешения счета подается импульс, персводяшдй счетчик 2 в очередное состояние (счетчик переходит из состояния 0... 00 в состояние 0...01).4 На втором выходе дертифрлтоpa 2 появляется сигнал, разрешающей через коммутаторы 4 , - 4 запись компонент вектора Н1 в регистры 6, - 6Г. Непосредственно эта запись происходит по заднему фронту второго тактового импульса, подаваемого на тактовый вход 10.

Распределение информации г триггере 5 и в регистрах 6 - 67 следую- щее:

62 63

.1 , (

64 6

67

в

Далее работа устройства происходит аналогичным образом. На вход 9 разрешения счета подается очередной импульс, переводяг(ий счетчик 1 из состояния 0...01 в состояние 0...10. На третьем выходе дешифратора 2 появляется разрешающей сигнал н по заднему фронту тактового импульса, поступившего с тактового входа 10, компоненты вектора II заносятся в регистры 6 1 - 67.

Распределение информации в триггере 5 и в регистрах (S -6 7 имеет вид

Работа устройства мохе г быть также

пояснена с помощью приводимой блицы, в которой представлено содержимо регистра 6 -67 на каждом такте вычислений. Содержимое регистров фиксируется на момент окончания соответствующего тактового импульса, поступившего на вход 10 эти импульсы поступают после установки счетчика 1 в очередное состояние 00, 01,

е

2

63 6 6у 6б Ь24 hZ h h

67

ь в

С приходом третьего импульса на вход 9 разрешения счета счетчик 1 переходит из состояния 0...10 в состояние 0...11.На четвертом выходе дешифра- тора 2 появляется разрешаюрдей сигнал и по окончании тактового импульса

на тактовом входе 10 в регистры 6, - 67 будут записаны компоненты вектора Н3, которые и являются коэффици- ентами арифметическото полинома:

3, Ь43

Ч

20

Н2 Ь3 Ь4

(ge)(g,) (йг) (р,}) (g) (RS) (gfi) (87)

При произвольном значении п уст- 25 ройство работает аналогично.

Таблица работы устройства для рассматриваемого примера: ,

10, 11). Числа в регистрах 6 ( - 6Г представлены в дополнительном коде, причем первый (старший) разряд - знаковый. В качестве примера таблица отражает работу устройства на рассмотренном примере разложения в арифметический полином логической функции F F(x,, х2, х,), у которой СО (F) (0, 1, 0, 1, 1, 0, 0, 1). Из таблицы следует:

0;

(0001)г 1 (0000)4 О (0000)г О (0001)4 1

(П10)гдоп (Ю10)гг,р - 210 ; 3

1633388

to

10

10

10

10

15

, h- (1111) г Аоп

(Ю01)г Пр -1

ю

Й(0010) 2 2,0.

Тогда g(F) (0,1,0,0,1,-2,-1,2).

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

Устройство для арифметического разложения логических функций, содержащее п вычитателей (п - количество переменных разлагаемой логич -ской функции) 2п регистров, п коммутаторов и триггер, причем тактовый вход k-ro регистра (k 1,2п) соединен с тактовым входом устройства, отличающееся тем, что, с целью расширения области использования за счет возможности арифметического разложения логических функций, оно содержит счетчик, дешифратор, элемен И, дополнительно с (2п + 1)-го по

12

5

0

5

0

(2П -пО-й

по (2 - 1)-и коммутаторов, с

5

регистров, с (п 1)-го

(п +

+ 1)-го по (2РЧ) вычитателей, причем вход установки в О счетчика соединен с входом разрешения обнуления устройства, вход разрешения счета которого соединен с входом разрешения счета счетчика, выход которого соединен с входом дешифратора, выход которого соединен с управляющим входом i-ro коммутатора (i 1, 2П - 1) и первым входом элемента 1, чыход которого соединен с тактовым входом триггера, второй вход элемента И соединен с тактовыми входами 1-го регистра, первый информационный вход устройства соединен с информационным входом триггера (1 1)-й информационный вход устройства соединен с первым информационным входом 1-го коммутатора, выход которого соединен с информационным входом 1-го регистра, выход триггера соединен с входом вычитаемого первого вычнтателя, вход уменьшаемого которого соединен с выходом первого регистра, вход вы- читаемого (i + 1)-го вычитателя (j - 1, 2П - 1) соединен г. выходом 2j-ro регистра, вход уменьшаемого (l + 1)-го вычитателя соединен с выходом (2j +1)-го регистра, второй ин- формационный вход J1 -го коммутатора ( jj1 1, 2 п - 2) соединен с выходами i-го вычитателя и 2j--ro регистра, второй информационный вход (2 - 1)- го коммутатора соединен с выходом (2П )-го вычитлтеля.

7ДISm

22Е

Ofc. Е

Т2,

77;

Т

/2,

772

а/

с

3Дз

7V 75

7

777 Т

77,

J2V

QJ

to. 2

Фиг. 5

А

Фиг b