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

05

S

N5

4ь KJ

316

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

Цель изобретения - увеличение производительности устройства за счет обеспечения обработки последова тельно поступающих аргументов параллельно с их приемом.

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

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

та, вход 13 начальной установки,

тактовьй вход 14, вход 15 запуска, выход 16 признака блокировки готовности аргумента, выход 17 признака окончания обработки, группу информационных выходов 18 и выход 19 инверсного значения младшего разряда регистра 6.

Блок 9 управления (фиг.2) содержит триггер 20, элемент ИЛИ-НЕ 21, два элемента ИЛИ 22 и 23, три элемента

,(1,0

У(25)

uy«(6,)

О, л, /1П ч

Хх,(3,2)Г NiO.

.) 4(11,)

х3(5,4):7

У6,)

Числа в скобках означают соответственно номер и индекс вершины, причем для, конечных вершин индекс I не указывается.

В таблице адресов приведено содержимое ячеек блока 8 памяти констант.

Первая строка содержит признак неконечной вершины () с индексом , соответствующего аргументу с номером

(010)Ј , т.е.

аргументу х2, вторая

строка содержит признак конечной вершины (), в которой представлено значение функции 000000.

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

По сигналу единичного уровня, по.- ступающего с входа 13 начальной

И 24-26, три элемента И-НЕ 27-29, шесть элементов НЕ 30-35 и счетчик 36.

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

Блок 8 служит для задания в табличной форме реализуемой логической функции. Каждая используемая строка, блока 8 соответствует вершине некоторого двоичного дерева, задающего логическую функцию. Старший (1+m +m) разряд строки указывает тип вершины; если он содержит логическую единицу, то это означает, что вершина конечная, при этом разряды , строки содержат код значения функции, если старший разряд строки содержит лог.О, то

вершина является неконечной, при этом младшие пц разрядов строки содержат номер (двоичный код) соответствующего ей аргумента, а остальные - двоичный код индекса I, определяющего положение вершины в двоичном дереве.

25

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

0

х2 -

Х X X а

| X 3X4- Х Х| X 3X4.

ХЈХ, X, -i

у, ,у,(000000)г

.у2,у (101010)

Уэ,у, (010101)г

Уф.У(И0011)2

у

-Уб

У5 (001100)2 У6 (1П111)г

5

Ее можно представить в виде двоичного дерева

uy«(6,)

х3(5,4):7

5

0

5

У6,)

установки, производится обнуление счетчика 36 и триггера 20, что приводит к запрету прохождения тактовых импульсов через элемент И 25, на выходах элементов НЕ 30 и 31 формируются уровни лог. М, разрешающие прохождение сигналов через элемент И-НЕ 28. По сигналу единичного уровня, поступающего на вход 15 запуска на выходе элемента НЕ 34 формируется сигнал нулевого уровня, поступагстЕий на вход установки в единицу триггера 20, а также на входы установки в ноль триггеров группы 2 и 3 и регистра 6. На выходе 19 инверсного значения младшего разряда регистра 6 установится уровень лог.1, этим обеспечивается выбор первой строки (с адре- вом 00...01) блока 8 памяти констант, полученная информация передается на информационные входы регистра 7. На выходе триггера 20 сформирован сигнал лог. 1, разрешающий прохождение тактовых импульсов через элемент И 25 на первый счетный вход счетчика 36, а также на вторые входы элементов И-НЕ 27 - 29 и элемента И 26.

На выходе элемента НЕ 32 формируется сигнал лог. 1, поступающий на тактовый вход регистра 7, чем обеспечивается запись информации в этот регистр. Информация с выходов разрядов, кроме старшего регистра, поступает на группу информационных выходов 18, информация с первых (младших) га разрядов выходов регистра 7 поступает на управляющие (адресные) входы мультиплексоров 4 и 5, информация остальных т2 разрядов регистра 7 поступает на информационные входы, кроме младшего регистра 6. Значение старшего разряда регистра 7 поступает на вход признака конечной вершины блока 9 управления. По перепаду импульса, поступающего на первый счетный вход (С) счетчика 36, на первом выходе счетчика устанавливается уровень лог. 1 , на втором выходе счетчика сохранится уровень лог. О, на выходе элемента НЕ 30 устанавливается уровень лог.О, на выходе элемента НЕ 31 сохраняется уровень лог. 1, этим обеспечивается разрешение прохождения сигналов через элементы И-НЕ 27, 29 и запрет прохождения сигналов через элемент И-НЕ 28 и элемент И 26.

Следующий (второй) тактовый импульс, прошедший через элемент 25, поступает на первый счетный вход счетчика 36, на вторые входы элемен- . тов И-НЕ 27 - 29, на второй вход элемента И 26, На первый вход элемента И-НЕ 28 с выхода элемента НЕ 30 по- Ступает сигнал нулевого уровня, за- пр ёщающий прохождение тактового имульса через элемент И-НЕ 28. На первый, вход элемента И 26 с второго выхода счетчика 36 поступает сигнал нуевого уровня, запрещающий прохождение тактового импульса через элемент И 26. На первые входы элементов И-НЕ 27 t 29 с первого выхода счетчика 36 поступает сигнал единичного уровня. На третий вход элемента И-НЕ 27 поступает значение старшего разряда регист0

5

0

5

0

5

0

5

0

5

ра 7. Если значение старшего разряда регистра 7 равно лог. 1, то информация на выходах, кроме старшего регистра 7, представляет искомое значение функции. В этом случае на третий вход элемента И-НЕ 27 поступает сигнал лог.1, тактовый импульс, поступивший на второй вход элемента - И-НЕ 27 с выхода элемента И 25, проходит через элемент И-ИЕ 27, через элемент НЕ 35 и формируется сигнал единичного уровня на выходе 17 признака окончания обработки 17, сообщая внешнему устройству об окончании обработки.

Кроме того, сигнал единичного уровня с выхода элемента И 35 проходит через элементы ИЛИ 22 и 23 и сбрасывает счетчик 36, а также через элемент ИЛИ-НЕ 21 обнуляет триггер 20, запрещая тем самым дальнейшее прохождение через элемент И 25 тактовых импульсов. На этом цикл обработки (определения значения функции для данного набора значений аргументов) заканчивается. Если же значение старшего . разряда регистра 7 равно лог. О, то прохождение тактового импульса через элемент И-НЕ 27 блокируется, сброса счетчика 36, триггера 20, а также выработки признака окончания обработки не происходит.Если при этом на входе 10 признака готовности аргумента установлен уровень лог. 1, то на входе 12 значения аргумента устанавливается значение очередного аргумента, подлежащего обработке, номер (двоичный код) которого представлен информацией на входе номера аргумента 11. В этом случае на третий вход элемента И-НЕ 29 поступает сигнал лог. 1. Тактовый импульс через элемент И-НЕ 29 поступает на вход элемента НЕ 33 и на управляющий вход дешифратора 1. На i-м выходе дешифратора 1 формируется сигнал единичного уровня, поступающий на тактовый вход 1-х триггеров группы триггеров 2 и 3.

Информация с входа 12 значения аргумента поступает на объединенные информационные входы триггеров 2. Информация с входа 10 признака готовности аргумента поступает на объединенные информационные входы триггера 3. На выходе элемента НЕ 33 блока 9 управления формируется сигнал лог. 1, который поступает на выход 16 признака блокировки готовности аргумента. Если же на входе 10 признака готовности аргумента установлен уровень лог. О, то прохождение тактового импульса через элемент И-НЕ 29 блокируется, запись информации в группы триггеров 2 и 3 не происходит. Сигнал признака блокировки готовности аргумента не вырабатывается.

Кроме того, по перепаду импульса, поступающего на первый счетный вход С, счетчика 36, на первом выходе счетчика 36 формируется сигнал лог.О, на втором выходе счетчика 36 устанавливается сигнал лог. 1, этим обеспечиваются разрешение прохождения сигналов через элемент И 26 и запрет прохождения сигналов через элементы И-НЕ 27 - 29.

Третий тактовый импульс через элемент И 25 поступает на первый счетный вход (С,() счетчика 36, на вторые входы элементов И-НЕ 27 - 29, на второй вход элемента И 26. Прохождение так- тового импульса через элементы И-НЕ 27 - 29 запрещено. Тактовый импульс проходит через элемент И 26 (на первый вход которого подан сигнал лог. М с второго выхода счетчика 36). Сигнал единичного уровня- поступает на первый вход элемента И 24 и через элемент ИЛИ 23 поступает на входы обнуления (Кл и R2) счетчика 36. На второй вход элемента И 24 поступает сигнал с выхода мультиплексора 5, уровень которого определяется содержимым 1-го триггера группы триггеров 3 (номер i определяется двоичным кодом, поступающим на управляющие входы мульти- плексора 5). Если содержимое 1-го триггера группы триггеров 3 равно лог.О, то это означает, что значение i-ro аргумента еще не поступало па вход 12 значения аргумента. В этом случае на втором входе элемента И 24 присутствует уровень лог.О, запрещающий прохождение тактового импульса через элемент И 24. Если же на втором входе элемента И 24 присутствует сиг- нал лог. М (т.е. значение 1-го аргумента уже поступило), то тактовый импульс пройдет через элемент И 24 и в виде импульса единичного уровня поступает на тактовый вход регистра 6. На первый (младший) информационный вход регистра 6 информация поступает с выхода мультиплексора 4. Уровень сигнала на выходе мультиплексора 4

Q Q

5

5

определяется содержимым 1-го триггера группы триггеров 2 (т.е. значением 1-го аргумента). На остальные информационные входы регистра 6 поступает информация со старших т разрядов группы выходов регистра 7, которая представляет двоичный код индекса I. По приходу тактового импульса эга информация записывается в регистр 6 и далее поступает на адресные входы блока 8 памяти констант. Тем самым производится адресация следующей (i1 -и) строки блока 8 памяти констант, адрес 1 которой определяется в соответствии с выражением i .|, где I - индекс текущей строки (вершины дерева); С - значение аргумента, соответствующего i-й строке (вершине дерева).

Кроме того, сигнал единичного уровня поступает на входы обнуления (R и RЈ) счетчика 36. На первом и втором выходах счетчика 36 устанавливаются уровни лог. О, на выходах элементов НЕ 30, 31 - уровни лог. 1. Тем самым будет вновь разрешено прохождение очередного тактового импульса через элемент И-НЕ 28 и блокируется прохождение тактового импульса через элементы И-НЕ 27,29 и И.26. Очередной тактовьй импульс будет первым относительно вновь выбранной строки блока 8 памяти констант. Работа устройства завершается после прихода второго тактового импульса на t-м цикле, если старший (Hitu+ia) разряд выбранной строки блока 8 памяти констант будет равен лог. М (т.е. если будет достигнута конечная вершина двоичного дерева, содержащая значение функции).

Таким образом, в предлагаемом устройстве обработка значений аргументов производится по мере их поступления и начинается (а иногда и заканчивается) до поступления всех значений аргументов .

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

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

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

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

5

5

0

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

Изобретение относится к автоматике и вычислительной технике и предназначено для реализации га-значных логических функций от п двоичных переменных в системах логического управления и распознавания образцов. Цель изобретения - повышение производительности устройства путем обеспечения обработки последовательно поступающих аргументов параллельно с их приемом.. Устройство содержит дешифратор 1, две группы триггеров 2 и 3, два мультиплексора 4 и 5, два регистра 6 и 7, блок 8 памяти констант, блок 9 управления. В устройстве обработка аргументов производится по мере их поступления и начинается, а при определенных условиях заканчивается до поступления всех значений аргументов. 3 ил., 1 табл. (Л

0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011

001 000 010 011 100 101 101 010 110 001

111

010 000 001 011 011 010 100 101 011 100

111

Фие.2

Фиг.З