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

 

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

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

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

РЕСПУБЛИК

А1 (51)5 G 06 F 7/00

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

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

ПРИ ГННТ СССР (21) 4639260/24 (22) 17.01.89 (46) 07.01.91. Бвл. Р 1 (71) Кишиневский политехнический институт им. С.Лазо (72) Ю,А.Пушняк, И.А.Мардаре и В.Л.Олейник (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

Р 1532912, кл. G 06 F 7/00, 1988.

Ийформационные системы. Табличная обработка информации./Под ред. Е.П.Балашова и В.Б.Смолова. — Л.: Энергоатомиздат, 1985, с. 98. (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЩЙ (57) Изобретение относится к автома-.. тике и вычислительной технике и пред„„80„„1619247

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

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

1 табл.

1619247

35 у (2,) оу(6) х <(1,1) i 0 х (4,3) х<(3,2) х4(7,5)

\.. 0 у (8,) у (11,) х (5,4) уб(9 ) Изобретение относится к автоматике и вычислительной технике и предназначено для реализации m çíà÷íûõ логических Аункций от и двоичных переменных

r в системах логического управления и распознавания образцов.

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

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

Устройство (Аиг. I ) содержит денифратор 1, дне группы триггеров 2 и 3, два мультиплексора 4 и 5, два регистра 6 и 7, блок Я памяти констант, блок 9 управления, вход 10 признака готовности аргумента, вход 11 номера аргумента, вход 12 значения аргумента, вход 13 начальной установки, 25 тактовый вход 14, вход 15 запуска, выход 16 признака блокировки готовности аргумента, выход 17 признака окончания обработки, группу информационных выходов 18 и выход 19 инверсного значения младшего разряда регистра 6.

Блок 9 управления (Аиг.2) содержит триггер 20, элемент ИЛИ-I1E ?1, два элемента ИПИ 27 и 23, три элемента

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

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

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

Например, пусть логическая функцття задана системой секвенций вида х2 - у1, у †(000000)

Х2х,х у, у =(101010)

2х, х зх Ф у, уз (010101)2 х2 х1 х хат -à j4 у y4 = (1 1 001 1 )z х х,х — у, у =(001100)z х2х1х — уп ь у6 — (1)1111)2

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

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

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

Первая строка содержит признак неконечной вершитты (F.=О) с индексом Х=1, соответствующего аргументу с номером (010), т.е. аргументу х, вторая строка содержит признак конечной вершины (F.=1), н которой представлено значение функции 000000.

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

По сигнагту единичного уровня, по," ступающего с входа 13 начальной установки, производится обнуление счетчика 36 и триггера 20, что приводит к запре у прохождеттття тактовых импульсов, через элемент И 25, на выходах элементов НЕ 30 и 31 формируются уровни лог,"1", разрешающие прохождение сигналов через элемент

И-HE 28. По сигналу едитптчного уровня, поступающего на вход 15 запуска на выходе элемента НЕ 34 формируется сигнал нулевого уровня, поступа"пщий на вход установки в единицу триггера

20, а также на входы установки в поль триггеров группы 2 и 3 и регистра 6.

На выходе 19 инверсного значения младшего разряда регистра 6 устано" вится уровень лог."1", этим обеспе161924 чивается выбор первой строки (с адревом 00...01) блока 8 памяти констант, полученная информация передается на информационные входы регистра 7. На выходе триггера 20 сформирован сигнал лог.. "1", разрешающий прохождение тактовых импульсов через элемент И 25 на первый счетный вход счетчика 36, а также на вторые входы элементов

И-НЕ 27 — 29 и элемента И 26 .

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

18, информация с первых (младших) m< разрядов выходов регистра 7 поступает 20 на управляющие (адресные) входы мультиплексоров 4 и 5, информация остальных ш разрядов. регистра 7 поступает на информационные входы, кроме младшего регистра 6. Значение старшего 25 разряда регистра 7 поступает на вход признака конечной вершины блока 9 управления. По перепаду импульса, поступающего на первый счетный вход (C ) счетчика 36, на первом выходе счетчика устанавливается уровень лог."1" на втором выходе счетчика сохранится уровейь лог. "0", на выходе. элемента

HE 30 устанавливается уровень лог."0", на выходе элемента НЕ 31 сохраняется уровень лог. "1"., этим обеспечивает35 ся разрешение прохождения сигналов через элементы И-НЕ 27, 29 и запрет прохождения сигналов через элемент

И-HE 28 и элемент И 26.

Следующий (второй) тактовый им" пульс, прошедший через элемент 25, поступает на первый счетный вход, счетчика 36, на вторые входы элементов И-НЕ 27 — 29 на второй вход элеt

45 мента И 26. На первый вход элемента

И-НЕ 28 с выхода элемента HE 30 по ступает сигнал нулевого уровня, запрещающий прохождение тактового импульса через элемент И-НЕ 28. На первый вход элемента И 26 с второго выхода счетчика 36 поступает сигнал нулевого уровня, запрещающий прохождение тактового импульса через элемент И 26.

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

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

Кроме того, сигнал единичного уровня с выхода элемента И 35 проходит через элементы ИДИ 22 и 23 и сбрасывает счетчик 36, а также через элемент ИЛИ-НЕ 21 обнуляет триггер 20, запрещая тем самым дальнейшее прохождение через элемент И 25 тактовых импульсов. На этом цикл обработки (определения значения функции для данного набора значений аргументов) заканчивается. Если же значение старшего . разряда регистра 7 равно лог. "0", то прохождение тактового импульса через элемент И-НЕ 27 блокируется, сброса счетчика 36, триггера ?О, а также выработки признака окончания обработки не происходит. Если при этом на входе

10 признака готовности аргумента установлен уровень лог. "1", то на входе 12 значения аргумента устанавливается значение очередного аргумента, подлежащего обработке, номер (двоичный код) которого представлен информацией на входе номера аргумента 11.

В этом случае на третий вход элемента .

И-НЕ 29 поступает сигнал лог. "1".

Тактовый импульс через элемент И-НЕ 29 поступает на вход элемента НЕ 33 и на управляющий вход дешифратора 1. На

i-м выходе дешифратора 1 формируется сигнал. единичного уровня, поступающий на тактовый вход i-х триггеров. группы триггеров 2 и 3.

Информация с входа 12 значения аргумента roñòóïàåò на объединенные информационные входы триггеров 2. Информация с входа 10 признака готовности аргумента поступает на объединенные информационные входы триггера 3. На выходе элемента HF. 33 блока 9 управления формируется сигнал лог. который поступает на выход 16 призна7 4

1619?47 ка блокировки готовности аргумента, Если же на входе 10 признака готовности аргумента установлен уровень лог. "0" то прохождение тактового им° у

5 пульса через элемент И-HH 29 блокируется, запись информации в группы триггеров ? и 3 не происходит. Сигнал при э на ка бл окир о вки г от ов нос ти ар гумента не вырабатывается.

Кроме того, по перепаду импульса, поступающего на первый счетный вход

С „счетчика 36, на первом выходе счетчика 36 формируется сигнал лог."0", на втором выходе счетчика 36 устанав-1> ливается сигнал лог. "1", этим обеспечиваются разрешение прохождения сигналов через элемент И 26 и запрет прохождения сигналов через элементы

И-НЕ 2? — 29.

Третий тактовый импульс через элемент И 25 поступает на первый счетный вход (C1) счетчика 36, на вторые входы элементов И-НЕ 27 — 29, на второй вход элемента И 26. Прохождение так- 25 тового импульса через элементы И-НЕ

27 — 29 запрещено. Тактовый импульс проходит через элемент И 26 (на первый вход которого подан сигнал лог."1" с второго выхода счетчика 36) . Сигнал 30 единичного уровня-поступает на первый вход элемента И 24 и через элемент

ИЛИ 23 поступает на входы обнуления (Rg и Rz) счетчика 36. На второй вход элемента И 24 поступает сигнал с выхода мультиплексора 5, уровень которого определяется содержимым i-го триггера группы триггеров 3 (номер i определяется двоичным кодом, постулающим на управляющие входы мульти- 40 плексора 5). Если содержимое i-ro триггера группы триггеров 3 равно лог."0", то это означает, что значес ипе i-го аргумента erne не поступало на вход 12 значения аргумента. В этом 45 случае на втором входе элемента И 24 присутствует уровень лог."0", запрещающий прохожпение тактового импульса через элемент И 24. Если же на втором входе элемента И 24 присутствует сиг<ал лог."1" (т.е. значение i ãî аргумента уже поступило), то тактовый им" пульс пройдет через элемент И 24 и в виде импульса единичного уровня поступает на тактовый вход регистра 6.

На первый (мпадший) информационный

S5 вход регистра 6 информация поступает с выхода мультиплексора 4. Уровень сигнала на выходе мультиплексора 4 определяется содержимым i-го триггера группы триггеров 2 (т.е. значением i-ro аргумента). На остальные информационные входы регистра 6 поступает информация со старших m разрядов группы выходов регистра 7, которая представляет двоичный код индекса Х. По приходу тактового импульса эга информация записывается в регистр

6 и далее поступает на адресные входы блока 8 памяти констант. Тем самым производится адресация следующей (i -й) строки блока 8 памяти констант, адрес i которой определяется в соответствии с выражением i» =2 Õ,"+Ñ,, где I> - индекс текущей строки (вершины дерева); С, — значение аргумента, соответствующего i-й строке (вершине дерева).

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

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

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

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

Адрес ячейки

Содержимое блока памяти констант

Признак конечной вершины

1+my+m ) 1 1 ш2

1-m

0001

0011

0101

0111

1001

10 10

1011

061

011

101

101

001

111, 0

0

0

0

1

001

011

011

101

011

1i i выход старшего разряда первого регистра соединен с входом признака окончания текущей итерации блока управления, вход запуска которого соединен с первым управляющим входом устройства, выход признака окончания обработки которого соединен с выходом признака окончания обработки блока управления, о т л и ч а ю щ е е с я тем, 10 что, с целью увеличения производительности путем обеспечения обработки последовательно поступающих аргументов параллельно с их приемом, оно содержит второй мультиплексор, две группы t5 триггеров и дешифратор, причем адресные входы дешифратора соединены с входом номера аргумента устройства, вход признака готовности аргумента которого соединен с информационными входами триггеров первой группы и входом признака готовности аргумента блока управления, вход признака номера аргумента которого соединен с выходом первого мультиплексора, информационные входы которого соединены с входами триггеров первой гв гппы, тактовый вход i-го триггера (i=1 2, n — количество аргументов) первой группы соединен с тактовым входом д-ro триггера З0 второй группы и с -м выходом дешифратора, .управляющий вход которого соединен с выходом признака готовности аргумента блока управления, первый выход разрешения записи которого соединен с тактовым входом первого регистра, выходы младших разрядов которого соединены с управляющими входами первого и второго мультиплексоров, инФормационные входы последнего иэ которых соединены с выходами триггеров второй группы, информационные входы которых соединены с входом значения аргумента устройства, выход второго мультиплексора соединен с младшим информационным входом второго регистра, остальные информационные входы которого соединены с выходами разрядов значения индекса первого регистра, выход сброса блока управления соединен с входами установки в "0" триггеров первой и второй групп и входом обнуления второго регистра, инверсный выход младшего разряда которого соединен с младшим адресным входом блока памяти констант, остальные адресные входы которого соединены с прямыми выходами старших разрядов второго регистра, тактовый вход которого соединен с вторым выходом разрешения записи блока управления, тактовый вход которого соединен с тактовым входом устройства, второй управляющий вход которого соединен с входом начальной установки блока управления, выход признака блокировки результата которого соединен с выходом признака блокировки результата устройства.

Индекс (I) Номер аргумента

1619247

Фие.2

l 61924 7 дх. 70

&. 75

8Ьм34

° Е у °

Вх. Ю

8ьи.5. Вьи.Z

8их.29 дыха

8ь®2Ф

8bN 17

Составитель Б. Сорокин

Редактор А.Мотыль Техред Л. Сердюкова Корректор Л. Бескид

Тираж /

Заказ 47

Подписное

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

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

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