Многофункциональный логический модуль Советский патент 1991 года по МПК G06F7/00 

11

13

1л

/4

0-1

оэ о

vi ел ю

Изобретение относится к вычислительной технике и может быть использовано при построении многофункциональных устройств цифровой обработки информации и узлов промышленной автоматики. Цель изобретения - упрощение многофункционального логического модуля при вычислении симметрических булевых функций. Модуль содержит элемент ИЛИ 1, сдвиговый регистр 2, демультиплексор 3, шифратор 4, блок 5 вычисления элементарных симметрических булевых функций, триггер 6, элемент И 7, счетчик 8. На информационные входы модуля поступают двоичные переменные X₁, X₂,..., X_N, а в сдвиговый регистр заносится двоичный код φ(F) реализуемой симметрической булевой функции F = F(X₁, X₂,..., X_N). В течение N + 1 тактового цикла на выходе модуля реализуется значение функции F, определяемой двоичным кодом φ F. 1 з.п. ф-лы, 1 табл., 2 ил.

фиг.1

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

Цель изобретения - упрощение многофункционального логического модуля при вычислении симметрических булевых функций (СБФ).

На фиг.1 представлена структурная схема многофункционального логичес- кого модуляJ на фиг.2 - функциональная схема блока вычисления элементарных СБФ (ЭСБФ), входящего в состав модуля.

Модуль содержит элемент ИЛИ 1, сдвиговый регистр 2, демультиплек- сор 3, шифратор 4, блок 5 вычисления ЭСБФ, триггер 6, элемент И 7, счетчик 8, группу информационных входов 9, вход 10 настройки, первый 11 и второй 12 входы сброса модуля соответственно, тактовый вход 13 и выход 14.

Блок вычисления ЭСБФ содержит п элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (п количество аргументов ревизуемых ЭСБФ)1 мажоритарный элемент 16 с порогом п, мажоритарньй элемент 17 с порогом п+1 (имеет только инверсный выход), элемент И 18, п информационных входов , п-1 настроечных входов 20(-20,1.1 , вход 21 запрета и выход 22.

Модуль работает следующим образом.

Известно, что произвольная СБФ п аргументов F F (Х, Х„, ... может быть однозначно представлена в виде

V

F fiX Vfr

n

FnV

(1)

и i При этом

где - элементарные (или фундаментальные) СБФ от п аргументов,1цЈ{0,1J

Таким образом, имеет место взаимнооднозначное соответствие между СБФ F F (Хр Х, ...,Х„) и (п + 1)-разрядным двоичным кодом /IT(F) (1Г0 /

ъ

г

,,...

П

Из (I) следует также, что

F - MF,

где дизъюнкция берется по всем которых 1ГК 1,

(2) К, дл

Поскольку все ЭСБФ F взаимно

ор

0

5

0

5

0

тогональны, то на заданном наборе двоичных переменных Х(, Х, , Х значение логической единицы принимает не более одной ЭСБФ из множества РМ« Следовательно, для вычисления произвольной СБФ (Xf,X2,,..,Х) от и аргументов Х„, Х„,..., X , заданной посредством своего двоичного кода 1 (F) , можно предложить следующую процедуру: вычислять последовательно значения ЭСБФ из fFhjHa данном наборе аргументов Х, Х, ...,ХП до получения единичного значения и тогда F 1 на данном наборе, либо до полного перебора всех ЭСБФ из fFnV и тогда F 0, так как на данное наборе все слагаемые в (2) равны нулю. Модуль содержит сдвиговый регистр 2, в который заносится код « (F) реализуемой СБФ F F (X,, Хг,..., Хп). Через демультиплексор 3 значение старшего разряда регистра 2 - значение очередного компонента /5Tj двоичного кода 1T(F) управляет работой шифратора 4, формирующего код настройки блока 5 вычисления ЭСБФ: если /|Г 1 , шифратор 4 настраивает блок 5 на вычисление функции F|J, значение которой на данном наборе фиксируется в триггере 6, если И | 0,. работа шифратора 4 и последующих узлов блокируется. Затем в сдвиговом регистре 2 осуществляется кольцевой сдвиг информаци на один разряд и производится аналогичный анализ компонента ; . Работа продолжается либо до перебора всех компонент двоичного кодаТ(Р), если F 0 на данном наборе аргу0

5

ментов X

Хп, либо до полу п

чения единичного значения функции, запоминаемого в триггере 6. При этом сигнал с инверсного выхода триггера 6 запрещает поступление тактовых импульсов через элемент И 7 на вход модуля и свидетельствует о завершении вычисления значения F на данном наборе. Счетчик 8 в процессе работы указывает номер анализируемого компонента Т;,

Многофункциональный логический модуль работает следующим образом.

Перед началом работы подаются импульсы на первый 11 и второй 12 входы сброса модуля, которые обнуляют сдвиговый регистр 2, триггер 6 и счетчик 8. Далее осуществляется настройка модуля на реализацию СБФ

5166

F F (X4, X, ...,Xn), заданной своим двоичным кодом Т (F) („ , Iff , Ч 2. /и ц ) в сопровождении серии из п+1 тактовых импульсов, подаваемых на тактовый вход 13, на вход 10 настройки поступают последовательно значения компонентов 1Г0 ,(, ,..., . ../|Г„. В результате этого в (п+1)-м разрядном сдвиговом регистре 2 записывается Kofl iTCF), причем в старшем разряде, соединенном с входом демультиплексора 3, входом запрета блока 5 вычисления ЭСБФ и входом элемента ИЛИ 1 имеет место значение 1Г0, а в младшем - значение IT . Модуль счета счетчика 8 равен п+1, Очевидно, разрядность счетчика равна г J + 1), поэтому после подачи указанной серии из п+1 тактовых импульсов счетчик 8 снова переходит в нулевое состояние, код которого указывает двоичный номер компонента 1 вектора IT (F) , подключенного к входу демультиплексора 3. Поскольку счетный вход счетчика 8 соединен .с тактовым входом сдвигового регистра 2, то всегда г-разт рядный двоичный код i состояния счетчика 8 указывает номер компонента , находящегося в данный момент з старшем разряде сдвигового регистра 2. После занесения кода (Р) в сдвиговый регистр 2 модуль готов к работе. На п шин группы информационных входов 9 модуля подаются двоичные аргументы X., Х,...,

fi

В течение (п+1)-го тактового цикла подготовки модуля к работе триггер 6 находится в нулевом состоянии и единичный сигнал с его инверсного выхода, подаваемый на вход элемента И, разрешает прохождение тактовых импульсов с тактового входа 13 на тактовый вход сдвигового регистра 2 и счетный вход счетчика 8. Это . обеспечивается тем, что во время занесения в сдвиговый регистр 2 кода ii(F) на входе запрета блока 5 вычис ления ЭСБФ присутствует сигнал старшего разряда предварительно обнуленного сдвигового регистра 2. Этот нулевой сигнал и запрещает формирование сигнала логической единицы на выходе блока 5 во время подготовки модуля к работе,

Демультиплексор 3 имеет п+1 выход (с нулевого по п-й), один инфор752 6

мационный вход, связанный с выходом старшего разряда сдвигового регистра 2, и г + l) адресных входов, на которые поступают сигналы с соответствующих разрядов счетчика 8. При этом при кольцевом сдвиге информации в сдвиговом регистре 2 в процессе вычисления СБФ F F (X,,

0 ft) B старшем разряде последовательно присутствуют компоненты 1Г Д, ,..., %, ,1Г0 , if, ,... и, таким образом, значения этих компонентов в такой же последовательности имеют

c место на выходах демультиплексора 3: нулевом, первом,..., n-м, нулевом, первом,и т.д.

Блок 5 вычисления ЭСБФ имеет п информационных входов, на которые с

20 информационных входом 9 модуля поступают параллельно двоичные переменные Xj, Хг,..., X п реализуемой СБФ F F (X,, Х,..., Xh), и п-1 настроечных входов, на которые поступает

1,2

25 код настройки V (U ,, U

..., U;M,) с выходов шифратора 4, где i 6, 1,..., n; в {О, 1 и S 1, 2,.,.,п-1. Функции шифратора 4 заключаются в преобразовании

Зо сигнала логической единицы на i-м входе (, 1,., .., п) в (п-1)-и разрядный вектор V на выходе. Следовательно, шифратор 4 имеет п+1 входов и п-1 выходов. Поскольку выходы демультиплексора 3 соединены с соответствующими входами шифратора 4, одновременно на входах шифратора может действовать не более одного сигнала логической единицы, поэтому всегда

лп будет однозначное соответствие между сигналом /ir 1, действующим на 1-й вход шифратора 4, и вектором V, настраивающим блок 5 на вычисление ЭСБФ Р „ (i 0, 1п).

45

В исходном состоянии в старшем

разряде сдвигового регистра 2 находится компонент 1ГВ вектора (F), счетчик 8 обнулен. На нулевом вы- 5( ходе демультиплексора 3 также присутствует сигнал 1Г0 .

Если/й () 1, шифратор 4 формирует

вектор настройки Vй (UB(t, U0(2

о VM настраивающ| и Спок 5 на реализацию функции F°. Значение FЈ на данном наборе аргументов X,, Х,...., Хл с выхода блока 5 подается на информационный вход триггера 6. По переднему фронту первого син-

хроимпульса рабочей серии, поступившего на тактовый вход 13 модуля, значение F6 записывается в одноступенtt , , чатый триггер о (.в качестве такого

триггера может быть выбран, например, синхронный D-триггер). Если

w

Fu 1 на данном наборе аргументов, а следовательно F F (X,,, Х,. ., х«) 1 на данном наборе, сиг- с инверсного выхода триггера 6 дальнейшее поступление синхроимпульсов на тактовый вход 13 блокируется. Значение реализуемой функции F равно логической единице и зафиксировано в триггере 6.

Если О (ЭСБФ F® не входит в (k) или F° 0 на данном наборе), то по переднему фронту первого рабочего синхроимпульса нулевое состоя- триггера 6 подтвердится, если /Stn 1. то значение старшего разряда

гдвигового регистра 2, подаваемое на вход запрета блока 5, заблокирует efo выходной сигнал.

В обоих случаях или /я0

1)

по заднему фронту первого синхроимпульса в сдвиговом регистре 2 произойдет кольцевой сдвиг информации (в старший разряд запишется значение j, в младший (Го ), а состояние счетчика 8 увеличится на единицу и укажет номер компонента , векто- pa iT (F), находящегося в данный момент в старшем разряде сдвигового регистра 2. При этом на первом выходе демультиплексора 3 присутствует сигнал и при 1 шифратор 4 на- страивает блок 5 на реализацию функции F

Если после подачи первого рабочего синхроимпульса триггер 6 остался в нулевом состоянии, подается следующий рабочий синхроимпульс, по переднему фронту которого в триггер 6 записывается значение F на данном наборе аргументов Х, Хо,..., Х (при 1), либо подтверждается нулевое состояние триггера 6 (при , if. 0). По заднему фронту этого синхроимпульса также производится кольцевой сдвиг информации в сдвиговом регистре 2 и увеличение содержимого счетчика 8 на единицу. Если после второго такта триггер 6 остался в нулевом состоянии, подается третий синхроимпульс, по переднему фронту которого в триггер 6 заносится значение ЭСБФ F на данном наборе (при

1), либо подтверждается нулевое состояние триггера. По заднему фронту синхроимпульса также происходит кольцевой сдвиг информации в сдвиговом регистре 2 и увеличение содержимого счетчика 8 на единицу.

Вычисление значения СБФ F F(X4, Х,..., Х) на данном наборе аргументов продолжается либо до фиксации в триггере 6 единичного значения (это указывает, что F 1 на данном наборе аргументов), либо до окончания рабочей серии из п+1 тактовых импуль5 сов, подаваемых на тактовый вход 13. В последнем случае значение F определяется состоянием триггера 6 после окончания (п+1)-го тактового импульса.

Q Для вычисления значения заданной СБФ F F (Xf, Xz, .,., Х„) на другом наборе аргументов на информационные входы 9 модуля подаются новые значения аргументов X,, Хг,..., Х,

5 триггер 6 обнуляется подачей импульса на второй вход 12 сброса, а на тактовый вход 13 подается очередная рабочая серия из п+1 тактового импульса (последовательно импульс за импуль0 с°м либо до фиксации в триггере 6 единичного значения, либо до окончания всей серии импульсов),

Если значение (X,Х,,..,X|J было вычислено досрочно (единичное значение F было зафиксировано в триггере.6 за 1 t«cn+1 тактовых импульсов), нет необходимости заканчивать текущую серию из п+1 рабочих тактовых импульсов. Триггер 6 обнуляется, а новое значение аргументов Xj, X,..., Xw сопровождается очередной серией тактовых импульсов. При этом, очевидно, начинается анализ не с компонента

функции F при о .,

та U-t (и соответствующей функции при 11ц. 1). Таким образом, среднее время вычисления СБФ (X,Хг,..., ..., Хп) составит величину

И о (и соответствующей V О,

а с компонен(п-Н) л о;

(3)

где v- период тактовых импульсов.

Коды настройки Vм (U.,.,, U; 2, U;,) и соответствующие им реализуемые ЭСБФ F (i О, 14) для

блока 5 (фиг. 2) при п 4 представлены в таблице (значение сигнала на

входе 21 запрета равно при этом логической единице).

Как следует из фиг.1 и 2, на вход 21 запрета блока 5 вычисления ЭСБФ поступает значение компонента с выхода старшего разряда сдвигового регистра 2. Очевидно, если fr; 0, то в соответствии с (2) значение F на данном наборе аргументов X,, Х,..., ...,Хп игнорируется вследствие появления нулевого сигнала на выходе 2 блока 5, соединенного с информационным входом триггера 6.

Структуру шифратора 4 рассмотрим на примере для п 4.Для этого воспользуемся таблицей настроек блока 5

Введем следующие обозначения: пусть а - сигнал на i-м выходе де- мультиплексора 3 (и соответственно на i-м входе шифратора 4) , bj - сигнал на j-м выходе шифратора 4, соединенного с настроечным входом блока 5, где , 1, ..., 4 и j 1, 2, 3.

20;

Как следует из таблицы настроек

a 0V a ,V а,

ii

агу а.

Таким образом, как следует из (4), при п 4 шифратор 4 состоит из двух элементов ИЛИ на три входа каждый.

Если учесть ортогональность сигналов на входах шифратора 4, то

Ь( аф, Ь. а.

2

Ьэ a0V (5) следует, что шифратор 4 может быть построен также на основе двух двухвходовых элементов ИЛИ-НЕ.

Дополнительным положительным эффектом изобретения является более высокое быстродействие.

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

10

15

661752 О

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

20

25

35

40

50

первым входом элемента И, второй вход которого соединен с инверсным выходом мажоритарного элемента с порогом п+1,

Х2. ХЬ Х4

1ОО

101

111

О01

000

5

вход запрета блока соединен с третьим входом элемента И, выход которого соединен с выходом блока.

- Х1 Х2 У5 4 X, XZX, X XjXgXyV Х(ХгХъХ У

V X Хл X л.

X, X2. V X, XaJf,X X, X2. V X,X4X5X.V Х,

X(X2X,X +УХ,ХгХэХ4У XtX2XjX4V

vx, Х1Хгхзх4

Ha

дл.6

18

122