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

Итоб1 г.тение птносится к автоматике и вычислительной технике и предназначено для построения плоскостных однородныхструктур, реализующих про извольные (в том числе любые скобочные) нормальные формулы из Ъ букв, заданные в базисе И, ИЛИ, НЕ, при равной доступности прямых и инверсных выходов источников информации. Известна ячейка однородной структуры, содержащая элементы И, ИЛИ, НЕ СП. Недостатком известной структуры, построенной на базе такой ячейки, является то, что она не позволяет реализовать произвольные формулы ука занного класса. При ее использовании нормальные формулы в базисе И, ИЛИ, НЕ должны предварительно быть преобразованы в базис двухместных опера- 20

ций И-НЕ, что приводит к большому числу ячеек в однородной структуре. Наиболее близкой по технической сущности к предлагаемой является ячейка, содержащая элементы И, ИЛИ, ЗАПРЕТ, причем пять входов ячейки подключены к соответствующим входам логических элементов, а на двух выходах известной ячейки обеспечивается формирование заданных функциональ-30 ных зависимостей. Известная ячейка предназначена для построения линейных однородных структур, реализующих произвольные дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ) из Ь букв, произвольные скобочные формы при , а также больщой класс скобочных форм для , при равной доступности прямых и инверсных выходов, источников информации 2J.

Недостатком данной ячейки является большое число внешних выводов, а также то, что однородная структура, построенная на ее основе, не универ.сальна в рассматриваемом классе формул при IT 7 11.

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

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

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

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

Ячейка путем настройки реализует следующие системы формул:

1. При ,

2.При z,1

3.При z., 1, z,,0

. 4. При z.| 1 , z,, 1

(фиг.2г)

в общем случае для реализации произвольной нормальной формулы из fi букв, заданнай в базисе И, ИЛИ, НЕ при равной доступности прямых и инверсных выходов источников информавторой информационные входы ячейки подключены к информационньм входам первого мультиплексора, настроечный вход которого подключен к второму настроечному входу ячейки, выход первого мультиплексора подключен к прямому входу элемента ЗАПРЕТ, выход которого является первым выходом ячейки, второй выход которой подключен к выходу второго мультиплексора, настроечные входы которого подключены к первому и второму настроечным входам ячейки соответственно, информационные входы второго мультиплексора подключены к первому информационному входу ячейки, к нулевой шине ячейки, к выходам элементов И и ИЛИ соответственно. На фиг.1 приведена функциональная схемаячейки, на фиг.2 - коммутациЗАПРЕТ 7, ryльтиплeкcop 8 с двумя информационными и одним настроечным входами, г гультиплексор 9 с четырьмя информационными и двумя настроечными входами, два выхода 10 и 11. Структура ячейки описывается системой формул: .,,,,4() ,Z2va z 22vOz Z2vO (a,z 2 ции, строится древовидная схема двухвходовых элементов И и ИЛИ, которая и вкладывается в плоскостную однородную структуру из ячеек, представляющую собой прямоугольник. При этом коммутационные и функциональные возможности ячейки позволяют разместить в каждом столбце структуры один двухвходовой элемент древовидной схе мы (число элементов в схеме равно t)-), а в каждом столбце - один каскад схемы. Под каскадом понимается линейная однородная структура из мак симального количества элементов И и ИЛИ, входящая в древовидную схему, причем каждый элемент такой схемы входит только в один каскад. При этом ячейки структуры, соответствующие элементам И древовидной схемы, настраиваются на реализацию системы 3, соответствующие элементам ИЛИ - на реализацию системы 4. Каждая ячейка структуры, связанная с последним элементом каждого каскада, за исключением каскада,, соединенного с выходом схемы,.настраивается на вы полнение системы 2. Остальные ячейки структуры должны реализовать систему 1 . Входные переменные подаются на од нородную структуру следующим образом Переменная с первым входом началь ного элемента -гб (i 1,2,.. . , каскада древовидной схемы, подключается на вход 1-и строки структуры. Остальные переменные подаются на вхо ды f столбцов структуры, в которых размещаются ячейкк, соответствующие элементам древовидной схемы, вторые входы которых подключе ны к входам переменным. Выходная переменная снимается с выхода первой строки структуры. Число ячеек в однородной структуре определяется соотношением L(ti-1|K,

fO

ФигЦ где К - число каскадов в древовидной схеме. Число каскадов, на которые может, быть разбита древовидная схема,реализующая нормальную формулу из А, букв в рассматриваемом базисе, определяется соотношением ji«., , где tj3- символ округления д6 ближайшего меньшего целого. Поэтому справедливо утверждение. Произвольная нормальная формула ; из Ъ букв, заданная в базисе И, ИЛИ, НЕ, при равной доступности прямых и инверсных выходов источников информации реализуется в плоскостной,однородной структуре из ( ячеек. При этом для реализации формулы, требующей числа ячеек, определяемого верхней оценкой, число столбцов в однородной структуре равно h-1, а число строк - y-I На фиг.З приведена древовидная схема с вьщёленными каскадами, реализующая формулу у () (x2vx)v() () (i-,l7)(i1 (-te 1 :,2)( которая при вложении в однородную структуру требует числа ячеек, определяемого верхней оценкой: о На фиг.4 приведена однородная структура, настроенная на реализацию древовидной схемы, приведенной на фиг.З. Таким образом, предлагаемая ячейка по сравнению с известной обеспечивает сокращение числа внешних выходов (6 вместо 7) при более широких функциональных возможностях.

i«

Xif

9 kf

f 0

s xg

У2 X

ЯЧЕЙКА ОДНОРОДНОЙ СТРУКТУРЫ, содержащая элементы ЗАПРЕТ, И и .ИЛИ, причем первый и второй информационные входы ячейки подключены к входам элементов И и ИЛИ соответственно, первый настроечный вход ячейки подключен к инверсному входу элемента ЗАПРЕТ, отличающаял л ш р 8 с я тем, что, с целью сокращения числа внешних выводов, ячейка содержит дополнительно два мультиплексора причем первый и второй информационные входы ячейки подключены к информационным входам первого мультиплексора, настроечный вход которого подключен к второму настроечному входу ячейки, выход первого мультиплексора подключен к прямому входу элемента ЗАПРЕТ, выход которого является первым выходом ячейки, второй выход которой подключен к выходу второго мультиплексора, настроечные входы ко§ торого подключены к первому и второму настроечным входам ячейки соответст(Л венно, информационные входы второго мультиплексора подключены к первому информационному входу ячейки, к нулевой шине ячейки, к выходам элемен§ тов И и ИЛИ соответственно. f1 HS 4 5 -J