Ячейка однородной структуры

 

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

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

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

РЕСПУБЛИК

А1 ((9) (ll) SU

Ш4 G06 F 7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АЮТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4183097/24-24 (22) 19.01.87 (46) 23.08.88. Бюп. N - 3 1 (71) Северо-Западный заочный политехнический институт (72) В.С.Князьков, Т.В.Волченская, В.В.Тепляков и В.Н.Егоров (53) 681.32(088.8) (56) Авторское свидетельство СССР

11) 798804, кл . С 06 F 7/00, 1978.

Авторское свидетельство СССР

У 1092492, кл. G 06 F 7/00, 1983. (54) ЯЧЕЙКА ОДНОРОДНОЙ СТРУКТУРЫ (57) Изобретение относится к вычислительной технике и автоматике и может быть использовано для вычисления булевых функций, Целью изобретения является сокращение количества внешних выводов. Ячейка содеркит входы

1, 2 настройки, инФормационные входы

3, 4 и выходы 5, 6, мультиплексоры

7, 8, элементы И 9, 10, 11, элементы ЗАПРЕТ 12, 13, элементы ИЛИ 14, 15, 16, триггеры 17, 18. Поставлен— ная цель достигается эа счет запоминания состояния отдельных ячеек структуры. 4 ил.

1418695

Изобретение относится к автомати:ке и вычислительной технике и пред назначено для построения плоскостнык однородных структур для вычисления произвольных нормальных формул (в том числе и скобочных), заданных в базисе И, ИЛИ, HE при равной доступности лрямык и инверсных выходов источ ников информации, !О

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

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

:структуре из предлагаемых яч еек . 25

Ячейка однородной структуры (фиг,1) содержит два входа 1 и 2 на,,стройки, два информационных входа 3 и 4, два информационных выхода 5 и

6, мультиплекс оры 7 и 8, три эл емента 30

И 9-1 ), дга элемента ЗАПРЕТ 12 и 13, три элемента ИЛИ 14-16 и два триггера

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

20 у 20, однородной структуры подключены соответственно к информа- 4 ционным входам 3 ячеек первого столб— ца, информационные входы 3 остальных ячеек каждой строки структуры подключены соответственно к информационным выходам 6 ячеек, являющихся соседни- 45 ми ячейками в строке слева, информационные входы 19„19, 19...,19„ однородной структуры подключены соответственно к информационным входам 4 ячеек последней (п-й) строки струк50 туры, информационные входы 4 остальных ячеек каждого столбца соответственно подключены к информационным выходам 5 ячеек, являющихся соседними ячейками в столбце снизу, информаци-;

55 онные выходы однородной структуры

22<, 22,...,22„ соответственно подключены к выходам 5 ячеек первой строки структуры в информационные выc=õÜ÷Ü(z,,zЬчzza);

d =уечу (г i ач г г аЬч z,х (1) х z (аЧЬ));

z< = хЬ

V xz,;

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

z — соответственно значения

2 прямых выходов триггеров 17 и 18 ячейки,формируемых при поступлении на их входы сигналов х и где z,, I г,, и у; соответственно значения информационнык сигналов, поступающих на информационные входы 3 и 4 ячейки; соответственно значения информационных выходов

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

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

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

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

1418695 с * b 1;

d a ° 1;

z = Ь ° 1; г а ° 1, (2) сЬ; а-z,(av Ь);

z -b

I Ф

10 (5) I г .,= г,, 25!

2 = Е ° с b; (6) d a; г г °

1 ! 1 Э

2 2 1

1 с а

6 О

45 с=zzbч zга; да; г г °

1 1 ° (7) г, =г

1 ю (4) 1 г 22 с 0; (8) d а ° Ь;

z г

1 f Э х 1 и у 1 в ячейке реализуется система функций:

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

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

x О и у О в этой ячейке реализуется система фукнций: с zz b÷ гz а;

d z,z ач i,z аЬч 212„(ачЬ);(3)

z z,;

30

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

И 22) °

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

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

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

На выходе 5 формируется значение фукнций z, (а vb), так как г а, При поступлении на входы 1 и 2 ячейки однородной структуры сигналов х 1, у = О в ней реализуется система функций:

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

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

a) при z 0, 2 0 б) приz, -О, г 1 в) приг, 1, 220

1418695

z f z

r) приz, =1, к =1 с=О; (9) с1=аЪ b;

z =г

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

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

18 ячеек однородной структуры в требуемые состояния в режиме программирования функций ячеек. В результате такой настройки каждая ячейка однородной структуры выполняет одну из функций (б) — (9). В режиме вычисления значения булевой функции на настроечные входы всех ячеек однородной структуры подается сигнал логического "0" . В результате в однородной структуре реализуется пространственно развернутый интерационный процесс вычисления запрограммированой в струк- 5 туре схемы вычисления булевой функции от К переменных.

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

Установка триггеров 17 и 18 ячеек однородной структуры в устройстве выполняется следующим образом. На группу входов 23,, 23,..., 23 „однородной структуры (фиг.2) подается управляющий вектор n = 1, 1, 1,..., 1.

Прн этом все ячейки однородной структуры настраиваются на выполнение

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

1418695 функции системы (4), в ячейках и-го столбца — функции системы (5), при этом в ячейке первой строки n-ro столбца реализуются функции системы (3) ° На группу входов 20,, 20 ...,,20> и группу входов 19,, 19,...,19„ после подачи вектора подаются одновременно векторы а и b значения элементов которых соответствуют значениям триггеров 18 и 17 ячеек (и-1)-го столбца и второй

Строки, в которые требуется их уста- новить. В соответствии со значениями управляющих сигналов, поступающих с группы входов 23, 23,...,23 на входы 1 и 2 ячеек однородной структуры, в ячейках первой строки состояния триггеров 17 не изменятся (системы (3) и (4) функций), в ячейках и-го столбца состояния триггеров 18 не изменятся (системы (4) и (5) функций), в триггеры 17 ячеек второй строки соответственно будут занесены значения элементов вектора а, в триггеры 18 ячеек (n-1)-ro столбца будут занесены значения элементов вектора Ъ.

Далее на группу входов 23,, 23<,...,23 „ однородной структуры подается вектор n = 1, 1, 1,...,1, t, О, О. На входы 20,, 20д,...,20 и входы 19,, 19,...,19„ соответственно подаются векторы а и b.В результате, аналогично описанному, в триггеры 17 третьей строки однородной структуры будут занесены значения элементов вектора а, а в триггеры

18 (n-2)-ro столбца — элементы вектора Ъ.

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

Причем при каждом последующем этапе ввода данных значение старшего разряда вектора и изменяется с "1" на

"О" ° В результате через и тактов триггеры 17 и 18 всех ячеек будут установлены в требуемое состояние (пчисло столбцов в однородной структуре), что и требуется для решения поставленной задачи. Графическая схема процесса занесения элементов векторов а и Ь в соответствующие триггеры 18 и 17 ячеек однородной структуры показана на фиг.3, где индекс соответствует порядковому номеру вектора а и Ь, подаваемых на входы 20 и 19 структуры.

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

20 однородной структуры значений переменных. При этом вычисляемая функция должна быть задана в базисе И, ИЛИ, HF.. Реализация данного режима

10 работы обеспечивается следующим образом.

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

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

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

35 структуры реализуе Функции системы (3), т,е. в зависимости от значений

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

1418695

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

5 (х<х ч х<х4ч х х Ч х x4v ч х хi Ч х х ч х х v х4 х } (Х Х<< Х Х< Ч Х «Х<< Ч Х<р Х< Ч 10

Vx x

«< ><> V Х<> Х<< У Х 4 Х<> Ч Х<4 Х< ) приведен на фиг.4, где показаны информационные каналы, а в ячейках ука- 16 заны реализуемые ими функции.

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

Ячейка. однородной структуры, содержащая два мультиплексора, элемент 20

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

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

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

1418695 гг

П в

Е

Фиг.У

Н= Е

li>- -I

0 = I

Пс=Е

Пу= I

@=Х

07 =1

0 Е

I I Х I I

Е I I

Е I Е I Е

I I I 1

? Е

I I

14!8695

- Составитель М.Силин

Редактор С.Пекарь Техред А. Кравчук Корректор М.Пожо

Заказ 4153/45 Тираж 704

Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4