Ячейка однородной структуры Советский патент 1988 года по МПК G06F7/00 

SMf

эо

9д

со :л

Изобретение относится к автомати- |ке и вычислительной технике и пред- назначено для построения плоскостных однородных структур для вычисления произвольных нормальных формул (в том числе и скобочных), заданных в базисе И, ИЛИ, НЕ при равной доступности прямых и инверсных выходов источников информации,

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

На фиг.1 приведена функциональная схема ячейки однородной структу- ры; на фиг.2 - схема организагщи од- нородной структуры из предлагаемых |ячеек для вычисления логических фун- ;кций от п переменных, заданных в базисе И, ИЛИ, НЕ; На фиг,3 - схема 1долговременной настройки ячеек од- НОродной структуры для выполнения тре |буемых функций; на фиг.4 - пример вы- |числения булевой функции в однородной Структуре из предлагаемых йчеек,

I Ячейка однородной структуры :(фиг,1) содержит два входа 1 и 2 на- |стройки, два информационных входа 3 и 4, два информационных выхода 5 и 6, мультиплексоры 7 и 8,три элемента :И 9-1, два элемента ЗАПРЕТ 12 и 13, три элемента ИЛИ 14-16 и два триггера 17 и 18.

Однородная структура для вычисле- |ния булевых функций от К-переменных организована из ячеек однородной структуры следующим образом (фиг.2): информационные входы 20,, 20, 20д,,..,20у, однородной структуры подключены соответственно к информа- ционным входам 3 ячеек первого столбца, информационные входы 3 остальных ячеек каждой строки структуры подключены соответственно к информационным выходам 6 ячеек, являющихся соседки- ми ячейками в строке слева, информационные входы 19, 19 J, 19,...,19f, однородной структуры подключены соответственно к информационным входам 4 ячеек последней (п-й) строки структуры, информационные входы 4 остальных ячеек каждого столбца соответственно подключены к информационным выходам 5 ячеек,являющихся соседними ячейками в столбце снизу, информационные выходы однородной структуры 22, 22,,...,22п соответственно подключены к вькодам 5 ячеек первой строки структ фы в информационные вы

0

5 „ с

0

5

ходы 21,, 21,...,21„ однор.одной структуры подключены соответственно к вькодам 6 ячеек последнего (п-го) столбца, первый управляющий вход 23 однородной структуры подключен к уп- равляющим входам 2 всех ячеек первого столбца и управляющим входам 1 всех ячеек последней (п-й) строки структуры, второй управляющий вход 23 однородной структуры подключен к входам 2 всех ячеек второго столбца и входам 1 всех ячеек (п-1) строки структуры i-й управляющий вход 23; однородной структуры подключен к входам 2 всех ячеек i-ro столбца и входам 1 йсех ячеек (n-i+1) строки структуры.

Ячейка однородной структуры в зависимости от сигналов х и у, посту- . пающих на ее входы 1 и 2, реализует вычисление следующих логических функций:

с хЬ V b (z, , z b V Z, ) ;

d ye V у (z, V z v z , x (1)

X z (a V b)); zj xb V xz,; zlj ya V yz,

где z,, z - соответственно значения прямых выходов триггеров 17 и 18 ячейки однородной структуры;

z||, z - соответственно значения прямых выходов триггеров 17 и 18 ячейки,формируемых при поступлении на их входы сигналов х и и у;

а, b - соответственно значения информационньк сигналов, поступающих .на информационные входы 3 и 4 ячейки;

с, d - соответственно значения информахдаонных выходов 5 и 6 ячейки однородной структуры, формируемые в результате вьгчисления булевых функций из системы (1) ,

При поступлении на входы 1 и 2 ячейки одиородной структуры сигналов

X 1 и у « 1 в ячейке реализуется система функций;

На выкоде 5 формируется значение функций Z,(а vb), так как z а.

При поступлении на входы 1 и 2 ячейки однородной структуры сигналов х 1, у 0в ней реализуется система функций:

Изобретение относится к вычислительной технике и автоматике и может быть использовано для вычисления булевых функций. Целью изобретения является сокращение количества внешних вьгаодов. Ячейка содержит входы 1, 2 настройки, информационные входы 3, 4 и выходы 5, 6, мультиплексоры 7, 8, элементы И 9, 10, 11, элементы ЗАПРЕТ 12, 13, элементы ИЛИ 14, 15, 16, триггеры 17, 18. Поставленная цель достигается за счет запоминания состояния отдельных ячеек структуры. 4 ил. fs(cj i

(2)

Как видно из системы (2) в данном случае в ячейках однородной структуры реализуется функция коммутации сигналов с выходов а и Ь на выходы сие. При этом одновременно в триггеры 17 и 18 каяадой ячейки заносятся значения сигналов поступающих на входы а и b ячейки.

При поступлении на входы 1 и 2 ячейки однородной структуры сиг налов х«0иу 0в этой ячейке реализуется система фукнций:

Z, Zjb V

Z,

d z, z Zjjab V z. b)j (3)

2 - ij.

В этом случае триггеры 17 и 18 ячейки сохраняют свои предыдущие состояния, а на выходах сие формиру отся соответствующие значения булевых функций, переменными которых являются входные сигналы а и Ь и значения состояний триггеров 17 и 18 (z, и z) .

При поступлении на входы 1 и 2 сигналов X О, у 1 в ячейке однородной структуры реализуется система функций

с Z,Zjb V Z,

d « а:

if i

(4)

z а.

В этом случае сигнал а с информационного входа 3 поступает без изменений на выход 6 ячейки, триггер 17 сохраняет свое значение, а триггер 18 принимает значение сигнала а, поступающего с входа 3 ячейки.

с - Ь;

d z (а V Ь);

г Ь;

(5)

Т- ч.

В этом случае сигнал Ь с входа 4. поступает без изменений на выход 5, триггер 17 сохраняет свое значение, триггер 18 устанавливается в состояние, соответствуняцее состоянию входа 3, а на выходе 6 формируется значение функции z (а V Ь).

В соответствии с системами (2) - (5) фукнций в зависимости от значений состояний триггеров 17 и 18 ячейки однородной структуры и при подаче на ее входы 1 и 2 управляющих сигналов X в о, у - О.в ячейке могут быть реализованы следующие системы функций:

а) при Z, О, Zj О с Ъ;

d - а;(6)

z, - 2, ;

zi - z.

б) при z, «о, Zj с а:

(7)

50

z 2 о

(8)

zl - z

«

z 1

5

(9)

10

Рассмотренные особенности ячейки однородной структуры при организа- ции из этих ячеек однородной структуры позволяют вьшолнить долговременную настройку однородной структуры на реализацию заданной булевой функции от h переменных. При этом настрой ка однородной структуры обеспечивается путем установки триггеров 17 и 18 ячеек однородной структуры в требуемые состояния в режиме программирования функций ячеек, В результа- те такой настройки каждая ячейка однородной структуры вьшолняет одну из функций (6) - (9). В режиме вычисления значении булевой функции на настроечные входы всех ячеек однород- ной структуры подается сигнал логического О. В результате в однородной структуре реализуется пространственно развернутый интерационный процесс вычисления запрограммированой в струк туре схемы вычисления булевой функции от К переменных.

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

I.

В режиме программирования функций

ячеек однородной структуры решаемая задача заключается в.установке триггеров 17 и 18 ячеек однородной структуры в требуемые состояния. На данном этапе в однородной структуре по сути формируется комбинационная схема вычисления заданной булевой функции от К переменных из двухвходовых

элементов И и ИЛИ и двухвходовых ком

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

0 5

0

0

5

скается расположение одного каскада древовидной структуры, т.е. бдной линейной структуры из максимального количества элементов И, элементов ИЛИ и коммутационных элементов, причем один и тот же элемент может входить только в один каскад. В процессе программирования ячеек однородной структуры триггеры 17 и 18 тех ячеек, которые предназначаются для реализации элементов И древовидной структуры,устанавливаются в состояние z 1, z О, чем обеспечивается реализация в ячейке системы (8) функций, для 1Ьеализации элементов ИЛИ - системы (9) функций, для связи с последним элементом каждого каскада, за исключением каскада, соединенного с выходом схемы, - системы (7) функций, остальные ячейки настраиваются на ре ализацию системы (6) функций. В результате в однородной структуре будет сформирована комбинационная схема для вычисления заданной булевой функции от К переменных, в которой информационные кйналы сформированы из последовательностей ячеек, настроенных на выполнение коммутационных функций, а узлы преобразования информации - из ячеек, реализующих операции логического умножения и сложения двух переменных.

Установка триггеров 17 и 18 ячеек однородной структуры в устройстве выполняется следующим образо м. На группу входов 23 ,, 23 , ..., 23 у, однородной структуры (фиг.2) подается управляющий вектор п 1, 1, 1,...,1. При этом все ячейки однородной структуры настраиваются на выполнение системы (2) функций. На группу входов однородной структуры 20„ 20,..., 20 и группу входов 19i, 19,...,19 соответственно подаются двоичные вектора а и Ь, значения элементов которых соответствуют тем значениям состояний триггеров 18 ячеек п-го столбца и триггеров 17 ячеек первой строки, в которые требуется йыполнить их установку. При таком составе управляющих сигналов вектора п в соответствии с системой (2) функций выполнится установка триггеров 18 и 17 в требуемые состояния. Далее на группу входов 23,, 23,...,23„ однородной структуры подается вектор п 1, 1, 1,..., 1, 1, 0. В результате в ячейках первой строки реализуются

функции системы (А), в ячейках п-го столбца - функции системы (5), при этом в ячейке первой строки п-го столбца реализуются функции системы (3), На группу входов 20 , 202,...,20 и группу входов 19, , 192,...19п после подачи вектора по- даются одновременно векторы а и Ь, значения элементов которых соответствуют значениям триггеров 18 и 17 ячеек (n-l)-ro столбца и второй йтроки, в которые требуется их установить. В соответствии со значениями управляющих сигналов, поступающих с группы входов 23,, 234...,23f, входы 1 и 2 ячеек однородной структуры, в ячейках первой строки состояния триггеров 17 не изменятся (системы (3) и (4) функций), в ячейках п-го столбца состояния триггеров 18 не изменятся (системы (4) и (5) функ ций), в триггеры 17 ячеек второй строки соответственно будут занесены значения элементов вектора а, в триг геры 18 ячеек (п-1)-го столбца будут занесены значения элементов вектора Ь.

Далее на группу входов 23| , 23,...,23f, однородной структуры подается вектор п 1, 1, 1,..., 1, 1, О, 0. На входы 20,, 20,...,20 и входы 19|, 19,...,19 соответственно подаются векторы а и Ь.В результате, аналогично описанному, в триггеры 17 третьей строки однородной структуры будут занесены значения элементов вектора а, а в триггеры 18 (п-2)-го столбца - элементы вектора Ъ.

Процедура занесения информации в триггеры 17 и 18 остальных ячеек однородной структуры аналогична. Прич.ем при каждом последующем этапе ввода данных значение старшего разряда вектора п изменяется с 1 на Р. В результате через п тактов триггеры 17 и 18 всех ячеек будут уС тановлены в требуемое состояние (п - число столбцов в однородной структуре) , что и требуется для решения поставленной задачи. Графическая схема процесса, занесения элементов векторов а и Ь в соответствующие триггеры 18 и 17 ячеек однородной структуры показана на фиг.З, где индекс соответствует порядковому номеру вектора и Ь, подаваемых на входы 20 и 19 структуры.

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

t формировании на одном из выходов 21 однородной структуры значения этой функции после подачи на входы 19 и 20 однородной структуры значений переменных. При этом вычисляемая функ10 ция должна быть задана в базисе И, ИЛИ) НЕ. Реализация данного режима работы обеспечивается следующим образом.

Предварительно выполняется про15 граммирование ячеек однородной структуры путем установки в требуемые состояния их триггеров 17 и 18. Тем самым ячейки однородной структуры настраиваются на выполнение заданной

20 системы функций, В результате в однородной структуре формируется комбинационная схема для вычисления заданной булевой функции от К переменных. Режим программирования ячеек 25 однородной структуры на выполнение функций в соответствии со схемой вычисления булевой функции описан.

Далее на входы 23 однородной струк30 туры подается вектор п С, О, О,,,., 0,0. В результате на входы 1 и 2 всех ячеек структуры будут поданы управляющие сигналы , В этом случае каждая ячейка однородной

структуры реализует функции системы (3), т.е. в зависимости от значений z и Zj (состояний триггеров 17 и 18) в ячейках однородной структуры будут реализовываться функции из сие-

40 тем (6) - (9). Входные переменные вычисляемой булевой функции одновременно подаются на входы 19 и 20 однородной структуры следующим образом. Переменная с первым входом на4g чального элемента i-ro каскада древовидной схемы (, 2,...,К/2) подключается на вход i-й строки однородной структуры. Остальные переменные подаются на входы (К/2) столбgQ цов структуры, в которьк размещены ячейки, соответствующие элементам древовидной схемы, вторые входы которых подключены к входным переменным. Результат вычисления значения

gg функции от К переменных формируется по окончании переходных процессов в ячейках однородной структуры На вьЬсоде последнего элемента первой строки структуры.

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

(

X,X,V X,X4V ,V

V X,X,V Х,Х- V Х,Х, V X,

l

А (Xj5

x,x,j V

Чв л 12

г

«б

V X

14

V V Х,5

М 16

1риведен на фиг.4, где показаны информационные каналы, а в ячейках ука- 15 первому информационному входу ячейки,

;заны реализуемые ими функции, ;Формула изо.бретения

Ячейка, однородной структуры, со- 1держащая два мультиплексора, элемент :И, элемент ИЛИ, элемент ЗАПРЕТ,причем |первый информационный вход ячейки Подключен к первым информационным |входам первого и второго мультиплек- icopoB, первым входам первых элементов И и ИЛИ, вторые входы первых эле- ;ментов И и HJIH подключены к второму информационному входу ячейки и к второму информационному входу первого :мультиплексора, управ:1яющий вход которого соединен с первым управляющим входом второго мультиплексора, второй, третий и четвертый информационные входы которого подключены соответственно к входу логического нуля устройства, выходам первых элементов И и ИЛИ, отличающаяся тем, что, с целью сокращения количества внешних выводов структуры, в него введены два элемента И, два элемента ИЛИ, два триггера и эле20

25

син ровход второго триггера подключен к рторому входу настройки ячейки, к инверсному входу второго элемента ЗАПРЕТ, первому входу третьего элемента И, второй вход которого подключен к первому входу первого элемента И, а выход - к первому входу второго элемента ИЛИ, выход второго триггера подлкючен к управляющему входу первого мультиплексора, выход которого подключен к прямому входу первого элемента ЗАПРЕТ, второй вход второго элемента И подключен к второму информационному входу ячейки, выход второго элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого подключен к выходу первого элемента ЗАПРЕТ, а выход является первым информационным

35 выходом ячейки, выход второго мультиплексора подключен к прямому входу второго элемента ЗАПРЕТ, выход которого подключен к второму входу вто- рого элемента ИЛИ, выход второго эле40 мента ИЛИ является вторым информационным выходом ячейки.

30

мент ЗАПРЕТэ причем информационный вход первого триггера подключен к второму информационному входу ячейки, а синхровход этого триггера подключен к первому входу настройки ячейки, первому входу второго эле- мента И, первому инверсному входу первого элемента ЗАПРЕТ, выход первого триггера подключен к второму инверсному входу первого элемента ЗАПРЕТ и второму управляющему входу второго мультиплексора,информационный вход второго триггера подключен к

первому информационному входу ячейки,

син ровход второго триггера подключен к рторому входу настройки ячейки, к инверсному входу второго элемента ЗАПРЕТ, первому входу третьего элемента И, второй вход которого подключен к первому входу первого элемента И, а выход - к первому входу второго элемента ИЛИ, выход второго триггера подлкючен к управляющему входу первого мультиплексора, выход которого подключен к прямому входу первого элемента ЗАПРЕТ, второй вход второго элемента И подключен к второму информационному входу ячейки, выход второго элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого подключен к выходу первого элемента ЗАПРЕТ, а выход является первым информационным

выходом ячейки, выход второго мультиплексора подключен к прямому входу второго элемента ЗАПРЕТ, выход которого подключен к второму входу вто- рого элемента ИЛИ, выход второго элемента ИЛИ является вторым информационным выходом ячейки.

гз

Фиг. г

19

ФиеЛ