Модуль для вычисления логических производных Советский патент 1992 года по МПК G06F7/04 

X

причем X(q)Ј{0, k-1}, q 0, kn-1. Тем самым определяются позиции элементов вектора

емую выражением

k-1 ) R kn -i + 1 T | kn-i +1 , t o

И)

т.е. матрица R kn - i + 1 получается в результате суммирования единичных мат(t kn-l-)

риц kn-i+1 О )M4HOro 5

сдвига (t 0, k-1) размерности x х kn4+1).

Выражения (2), (3) и (4) являются математическими моделями функционирования модуля в первом режиме.10

П р и м е р 1. Пусть данные заданы многозначной функци§Ј| алгебры логики в виде вектора значений X 122100220 т(, ). Тогда в соответствии с соотношением (2) векторы значений логических производных по первой и второй переменным с мно- гократным циклическим отрицанием соответственно равны

Изобретение относится к вычислительной технике и может быть использовано для синтеза и анализа цифровых автоматов, диагностики цифровых устройств и сжатия данных. Цель изобретения - расширение функциональных возможностей за счет логической обработки многозначных данных. Модуль для вычисления логических производных содержит узел 1 управления, два коммутатора 2 и 3, сумматор по модулю 4, два сдвиговых регистра 5 и 6. В зависимости от режима работы модульдюзволяет вычислять вектор значений д X/dxi логической производной по i-й переменной с многократным логическим отрицанием, либо вектор значений смешанной логической производной i-ro порядка по переменным с многократным циклическим отрицанием. 1 з.п. ф-лы, 10 ил., 5 табл.

где матрицы R-jJ и Rs сформированы согласно выражениям (3) и (4) следующим образом:

«J

Rji I3f-i®R3a-t 7 V

I „

2 Х I ,2 - Ь2

rf3)

I( -J/ T -

32 +I72

) I3i

, , r

III

FI I

II I

II I I I I 1 I l I I

(mod3)

(mod3)

J2)

I,2-t®R,2-2 1 Ij ®R31

4, 3

40

iw Д w d (. -,1 - 2 1,1 -1,1+I,-|-1,1 .

45

55

На фиг. 6 показаны операционны графы вычисления векторов значений dX/dxi и d X/d X2 логических производных по переменным xi и Х2 с многократным циклическим отрицанием для многозначной функции алгебры логики, рассмотренной в примере.

Необходимо отметить, что вектор значений д X/d Xi логической производной по i-й переменной х; с многократным циклическим отрицанием сострит из набора векторов Xi(, k ) размерности , образующих группы из k равных векторов (фиг. 10), что позволяет вычислять не все значения логической производной д f(X)/3 xi, а лишь k различных векторов, и используется в модуле для упрощения процесса вычислений.

Существует возможность вычисления смешанной логической производной i-ro порядка по переменным с циклическим отрицанием (второй режим):

ДО

X

д xi д Х2 ... д Xi

(1) Rk

J2)

(5)

х X (mod k), где i n.

Покажем вычислительные особенности реализации данной математической модели на примере.

Приме р 2. Для многозначной функции алгебры логики, заданной вектором значений X 120102010 1, вычисление смешанной производной второго порядка по переменным xi и Х2 с многократным циклическим отрицанием производится в соответствии с математической моделью (5)

На фиг. 7 показан операционный граф вычисления вектора значений логической 55 производной второго порядка по переменным xi и ха с многократным циклическим- отрицанием многозначной функции алгеб- ды логики, заданной вектором значений X 120101010 т(, ). В табл. 2 приве-

0

5

0

5

30

35

55

дены векторы значений логических производных второго порядка по переменным xi и Х2 с многократным циклическим отрицанием, а также логические производные второго порядка некоторых многозначных функций алгебры логики при k 3 и n 2.

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

Модуль для вычисления логических производных (фиг. 1) содержит узел 1 управления, первый и второй коммутаторы 2 и 3, сумматор 4 по модулю, первый и второй сдвиговые регистры 5 и 6, вход 7 признака режима узла управления, вход 8 признака пуска/останова узла управления, первый и второй информационные входы 9 и 10, выход 11 признака режима узла управления, выход 12 признака пуска/останова узла управления, выход 13 текущего значения элемента вектора, выход 14 значения производной, информационный выход 15, тактовый выход 16 узла управления, первый и второй управляющие выходы 17 и 18 узла управления, первый и второй информационные входы 19 и 20 второго коммутатора, первый, второй и третий выходы 21, 22 и 23 второго коммутатора, первый и второй управляющие входы 24 и 25 второго коммутатора.

Узел 1 управления предназначен для формирования управляющих сигналов, обеспечивающих синхронную работу модуля в обоих режимах вычисления.

Узел управления (фиг. 2) содержит суммирующий счетчик 26, шифратор кодоз 27, два Т-триггера 28 и 29, элемент ИЛИ 30, коммутатор 31, элемент 32 задержки, генератор импульсов 33, первый, второй и третий выходы 34, 35 и 36 шифратора кодов.

Таблица истинности шифратора кодов 27 приведена в табл. 3.

Элемент 32 задержки предназначен для задержки сигнала, поступающего на вход, на время Дт (k-1), где f - частота следования импульсов на выходе генератора импульсов 33).

Суммирующий счетчик 26 с коэффициентом счета 2s (S Iog2((k-2) + ) предназначен для подсчета числа тактов работы узла 1 управления.

Первый режим работы узла 1 управления определяется нулевым уровнем сигнала, который подается на вход 7 признака режима узла управления в момент времени to (фиг. 8). Во втором режиме работы на вход 7 признака режима узла 1 управления в момент времени to подается сигнал одиночного уровня (фиг. 9).

В первом режиме сигнал нулевого уровня передается в момент времени to на выход 11 признака режима узла управления, откуда может поступать на вход 7 признака режима узла управления следующего модуля, и определяет режим его работы. Одновременно сигнал с входа 7 признака режима поступает на управляющий вход первого коммутатора 2 и на управляющий вход коммутатора 31, вследствие чего информация на выход коммутатора 31 передается с входа 8 признака пуска/останова узла управления. Одновременно сигнал пуска, подаваемый на вход 8 признака пуска/останова узла управления, поступает на вход генератора 33 импульсов. При этом сигнал пуска поступает через элемент ИЛИ 30 на вход установки в О суммирующего счетчика 26, после чего счетчик устанавливается в состояние 0 0...0 и на входы установки в О первого и второго Т-триггеров 28 и 29.

Начиная с момента времени to генератор 33 импульсов формирует последовательность импульсов, которые поступают на тактовый выход 16 узла управления и на счетный вход суммирующего счетчика 26.

В момент времени t(k-2)knM, когда на выходах суммирующего счетчика 26 формируется двоичный эквивалент числа (k-2) + , на выходе 34 шифратора кодов 27 формируется сигнал единичного уровня, поступающий на информационный вход первого Т-триггера 28, на выходе которого формируется сигнал единичного уровня, который сохраняется в последующие такты работы.

В момент времени tq (q (k-2) + выходах суммирующего счетчика 26 формируется двоичный эквивалент числа (k-2) + + + 1, на выходе 35 шифратора кодов 27 формируется сигнал 1, который поступает на информационный вход второго Т-триггера 29, на выходе которого формируется сигнал единичного уровня, сохраняющийся в последующие такты работы модуля.

Таким образом, на выходах первого 28 и второго 29 Т-триггеров сохраняются сигналы 1, которые поступают соответственно на второй и первый управляющие выходы 18 и 17 узла управления до момента времени tm (m (k-2) + ).

В момент времени tm на выходах суммирующего счетчика 26 формируется двоичный эквивалент числа (k-2) + + 1. На выходе 36 шифратора кодов 27 формируется

сигнал единичного уровня, который поступает на первый вход элемента ИЛИ 30. С выхода элемента ИЛИ 30 сигнал 1 поступает на вход установки в О суммирующего счетчика 26 и входы установки в О первого

и второго триггеров 28 и 29. Вследствие этого на первом и втором управляющих выходах 17 и 18 узла управления формируются сигналы нулевого уровня.

Описанный цикл работы узла 1 управления повторяется раз и заканчивается в момент времени m

Начиная с момента времени по tp(p kM ((k-2)kn4 + 2kn4 + (k-2)kn + kn ) функционирование узла 1 управления аналогично его функционированию с момента времени to no tq.

В момент времени tp на вход 8 признака пуска/останова узла управления подается сигнал останова, по которому через элемент

ИЛИ 30 производится обнуление суммирующего счетчика 26, а также первого и второго Т-триггеров 28 и 29, Во втором режиме с входа 7 признака режима узла 1 управления в момент времени to поступает сигнал 1

(фиг. 9). В результате на выход 12 признака пуска/останова передается задержанный сигнал с входа 8 признака пуска/останова узла управления. В остальном работа узла 1 управления во втором режиме аналогична

его функционированию в первом режиме.

Сумматор 4 по модулю предназначен для суммирования по модулю k данных, поступающих на входы первого и второго слагаемых.

Второй коммутатор 3 (фиг. 3) содержит два элемента НЕ 37 и 38, пять элементов И 39-43 и два элемента ИЛИ 44 и 45.

Схемы информационных потоков через второй коммутатор 3 показаны на фиг. 4.

Сдвиговые регистры 5 предназначены для хранения и формирования исходных данных и результатов промежуточных вычислений.

Сдвиговые регистры 6 предназначены для хранения и формирования результатов вычислений элементов вектора значений ЗХ/д X, Ы/д Х1...3 xi логической производной.

Рассмотрим работу устройства при вычислении логических производных по переменным с циклическим отрицанием функции алгебры логики f(X) в соответствии с выраже- ниями (2) и (5).

Введем следующие обозначения: пусть д X/ д xi Y, где Y Y(o)Y(1)...Y(k 1) т; ЭХ/Эхг-2,где2-р °Ґ1 Г: 5 Э(2) Х/Эхт 3X2-Q, гдеО д(о)Ч(1)...)т.

Пусть необходимо вычислить логические производные по переменным Xi и Хг с многократным циклическим отрицанием функции двух переменных f(X) xi Х2 л Х2 при k 3, заданной вектором значений X 01211221 .

Структурная схема устройства для данного случая (k 3, п 2) показана на фиг. 5.

Функционирование устройства в первом режиме поясняет табл. 4, а во втором режиме - табл. 5.

В первом режиме на вход 7 признака режима узла 1i управления подается сигнал нулевого уровня. По сигналу пуска, поступающему на вход 8 признака пуска/останова узла.11 управления, элемент ы вектора значений X 0 1 2 1 1 2 2 1 подаются на первый информационный вход 9 первого модуля, на первый информационный вход первого коммутатора 2i и через выход текущего значения элемента вектора13i первого модуля на первый информационный вход 92 второго модуля.

В первом такте работы устройства первый элемент 0 вектора X передается через первые коммутаторы 2i и 22 на входы первого слагаемого сумматоров по модулю три 4i и 42. Одновременно на входы второго слагаемого сумматора по модулю три 4t и 42 с выходов первых сдвиговых регистров 5i и 52 поступают данные, значения которых равны нулю. Вследствие этого первый элемент 0 вектора X с выходов сумматоров по модулю три 4i и 42 передается на первые информационные входы 19i и 192 вторых коммутаторов 3i и 32, функционирующих в режиме А (фиг. 4). С первых выходов 211 и 212 вторых коммутаторов 3i и первый элемент х 0 0 вектора значений Гпоступает на информационные входы сдвиговых регистров 5i и 52, во втором такте работы устройства первый элемент Х 0 вектора X передается с выходов первого сдвигового регистра 52 второго модуля на вход второго слагаемого сумматора по модулю три 42. Одновременно на вход первого слагаемого сумматора по модулю три 42 через первый коммутатор 2 поступает второй элемент х t 1 вектора X. На выходе сумматора по модулю три 42 формируется промежуточный результат + х 1 1 (mod 3), который записывается в первый сдвиговый регистр

.

.-,

5

10

15

20

25

30

40

45

52 второго модуля. Второй коммутатор 32 во- втором такте работы устройства функционирует в режиме В (фиг. 4). Во втором такте работы производится запись второго элемента X 1 в первый сдвиговый регистр 5i. этом первый элемент вектора значений X сдвигается на один разряд в сторону старших разрядов на сдвиговом регистре 5ч.

В третьем такте работы устройства первый промежуточный результат Х + Х 1 (mod 3) с выходов первого сдвигового регистра 52 второго модуля поступает на вход второго слагаемого сумматора по модулю три 42. Одновременно на вход первого слагаемого сумматора по модулю три 42 подается третий элемент х 2 2 вектора X. В результате на выходе сумматора по модулю три 42 формируется первый элемент.0 Х(о) + Х(1) + Xй 0 (mod 3) вектора В Х/Э Х2. Через второй коммутатор 32, функционирующий в режиме С (фиг. 4), первый элемент Z вектора д X/d X2 записывается во второй сдвиговый регистр 62 и одновременно поступает на информационный вход 152 устройства. В третьем такте происходит запись четвертого элемента Х 2 вектора X в первый сдвиговый регистр 52 второго модуля.

В четвертом такте работы на информационном выходе 152 устройства формируется второй элемент. z 1) Х(о) + Х(1) + Х(2) О (mod 3) вектора д Х/3 Х2.

Одновременно происходит запись второго элемента вектора д X/d X2 во второй сдвиговый регистр 62. В пятом такте функционирования устройства в первом модуле

формируется промежуточный результат х(о) + Х(3) 1 (mod 3) а во втором модуле

промежуточный результат Х + Х 2 (mod 3), которые записываются в первые сдвиговые регистры 5i и 52 соответственно.

В пятом такте на информационном выходе 152 устройства формируется третий элемент 2® Х(о) + Х(1) + Xй 0 (mod 3) вектора дХ/дх2, а на информационном выходе 151 - первый элемент Y(o) Х(о) + Х(3) + + Х{6) 0 (mod 3) вектора ЭХ/Зхь

50

55

В последующих тактах работы на информационном выходе 152 устройства ются элементы вектора значений дХ/дх2 логической производной. Причем девятый элемент zf Х(6) + Х( } + Х(8) 1 (mod 3) вектора д Х/д Х2 поступает на информационный выход 152 устройства на одиннадцатом такте функционирования (табл. 4).

Таким образом, на информационном выходе 152 устройства формируется вектор

значений - 0 00 1 1111 логической

ЙХ2 ПРОИЗВОДНОЙ фуНКЦИИ f(X) Х1 Х2 - Х2 ПО

переменной Х2 с многократным циклическим отрицанием.

Аналогично на информационном выходе 15i устройства формируется вектор значений Э Л/д xi 0 0 2 0 0 2 О О логической производной функции f(X) xi / ха по переменной xi с многократным циклическим отрицанием. Его последний элемент Х{2) + Х15) + Х(8) 2 (mod 3) поступает на информационный выход 15i устройства на пятнадцатом такте работы. В пятнадцатом такте на вход 12i признака пуска/останова передается на вход 82 признака пуска/останова узла 12 управления и определяет конец работы устройства.

Во втором режиме исходные данные элементы вектора значений X поступают на второй информационный вход 1СИ и через первый коммутатор 2т передаются на вход первого слагаемого сумматора по модулю три 4i, На вход признака режима 1 узла 1i управления -подается сигнал единичного уровня, который определяет функционирование устройства во втором режиме.

Функционирование устройства во втором режиме в целом аналогично функционированию его в первом режиме. Отличие функционирования второго модуля заключается в том, что он начинает функционировать на седьмом такте работы устройства. Это обусловлено тем, что сигнал пуска поступает на вход 82 признака пуска/останова узла 12 управления на седьмом такте работы устройства. Исходными данными для второго модуля является результат вычислений первого модуля - вектор значений д Х/9 xi 00200200 , элементы которого поступают на второй информационный вход 102 второго модуля.

Во втором режиме работы на информационном выходе 152 устройства формируется вектор значений r2 X/d xi д Х2 2 2 2 2 2 2 2 2 смешанной логической

ПРОИЗВОДНОЙ фуНКЦИИ f(X) Х1 Х2АХ2 ПО

переменным с многократным циклическим отрицанием.

На пятнадцатом такте работы устройства на вход 8 признака пуска/останова узла 1 управления подается сигнал останова, который через элемент задержки 32 узла 1т управления поступает на вход 82 признака пуска/останова узла 12 управления на двадцать первом такте и определяет конец работы устройства.

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

сумматор по модулю, выход которого соединен с первым информационным входом второго коммутатора, первый выход которого соединен с информационным входом первого сдвигового регистра, второй информационный вход модуля соединен с вторым информационным входом первого коммутатора, выход которого соединен с входом первого слагаемого сумматора по модулю, вход второго слагаемого которого соединен

с выходом первого сдвигового регистра, вход разрешения сдвига которого соединен с входом разрешения сдвига второго сдвигового регистра и тактовым выходом узла управления, первый и второй управляющие

выходы которого соединены соответственно с первым и вторым управляющими входами второго коммутатора, второй выход которого соединен с информационным входом второго сдвигового регистра, выход которого

соединен с вторым информационным входом второго коммутатора, третий выход которого соединен с выходом значения производной и информационным выходом модуля, выход признака пуска/останова которого соединен с выходом признака пуска/останова узла управления, выход признака режима которого соединен с выходом признака режима модуля, вход признака режима которого соединен с входом признака режима узла управления и управляющим входом первого коммутатора, первый информационный вход которого соединен с выходом текущего значения элемента вектора модуля, вход признака пуска/останова которого

соединен с входом признака пуска/останова узла управления.

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

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

Таблица 1

Таблица 2

Таблица 3

А А А В В В С С

с

А А А Б В В

ХМ

хМ

xw х(«

х«

х(61 х(0

хси

У «О

О

о о Xе

у«

X +Х

) х(.)

xw

Лхм

Av

/0)

x«

xw

xw

Лх Л

Лх«

Лх(5)

YP)

Y(fl Yw

Y« ,0)

„«)

Y()

rw

fp)

Y(o)

Yw „w

Y«

Y(0

Y( V( V(

v(

Y(,

vf

YC

(il

vw

Y( ,W

,(6) (Cr) ,«)

A В С A В С. A В С А В С А Б С

ХЙ

ХМ

х(Ч хед

х(4,

х(4 х(7) „(1

х« xV

xw

хЧх о

х(6) (

хСо)

Лх«

z(o)

хи (4)

X16

хЧх(7 ,-.«

Х(о)

Лх(11

х«) x4xw

)(6i

- Z

№

7М

z(«

z(fl

2од

z«

,(о)

z«

7W

z«

,(«)

2« Z0)

ZW

zw

Z(0

,(5l

,(7) .(Si

-g

со о en

oo

X

x«

xw

Xu5

() хй)

x« x№

X1 )

„W

„«О

v(o)

Лх 5

„w

,0

fw

г«

„№

,г

,«)

,Сб)

qW а)

1й5 о«1

,м ,(6)

q(o1 q(0 qftl q«J q(«1 ,( q« ,W „(8)

-J CO О

а

18 77 Фиг.2

п

22

27

лог..О Лог Я

20

Режим A

ъ

8,

з,- ,л Йог.

2,25

23

«-ZL

/

22

20 Режим В

Лог.7 Йог/

24

25

23

2/

3

22

Р&ЖИИ С

2 /22

5/

Фиг. 5

/52

х

-X

V,

SzSt.

- У

Фиг. 7

1 i

2 i

i

г. {

/

modt5

2

L 1

modJ

fx

-VrСигнол пуска

Си

Сигналы пуска-останоба, узла управления //+/

Второй управляющий Выход 18 узла управления

первый управляющий выход 17 узла управления

Выход ЗЬ

шифратора ко- доП / . . Выход 35

шифратора ко- до827

Выход 36 шшрратора кодов27

,

&-2)i

-Vr-ttиСигнал останова

-я-if

1т

лМ & -т

Фиг. 8

4

S;

& Ј

I

QJ

Г

:Г Ј

Ц

У И Ij

4

-j

ы о y

Фиг. 10