SU1092492A1

SU1092492A1 - Cell of monogeneous structure

Info

Publication number: SU1092492A1
Application number: SU833554691A
Authority: SU
Inventors: Валерий Леонидович Артюхов; Анатолий Абрамович Шалыто
Original assignee: Предприятие П/Я А-3500
Priority date: 1983-02-18
Filing date: 1983-02-18
Publication date: 1984-05-15

Abstract

ЯЧЕЙКА ОДНОРОДНОЙ СТРУКТУРЫ , содержаща элементы ЗАПРЕТ, И и .ИЛИ, причем первый и второй информационные входы чейки подключены к входам элементов И и ИЛИ соответственно , первый настроечный вход чейки подключен к инверсному входу элемента ЗАПРЕТ, отличающа л л ш р 8 с тем, что, с целью сокращени числа внешних выводов, чейка содержит дополнительно два мультиплексора причем первый и второй информационные входы чейки подключены к информационным входам первого мультиплексора , настроечный вход которого подключен к второму настроечному входу чейки, выход первого мультиплексора подключен к пр мому входу элемента ЗАПРЕТ, выход которого вл етс первым выходом чейки, второй выход которой подключен к выходу второго мультиплексора, настроечные входы ко§ торого подключены к первому и второму настроечным входам чейки соответст (Л венно, информационные входы второго мультиплексора подключены к первому информационному входу чейки, к нулевой шине чейки, к выходам элемен§ тов И и ИЛИ соответственно. f1 HS 4 5 -JA cell of a uniform structure containing the elements BAN, AND, OR. The first and second information inputs of the cell are connected to the inputs of the AND and OR elements, respectively, the first configuration input of the cell is connected to the inverse input of the BAN element, which is , in order to reduce the number of external outputs, the cell contains two additional multiplexers, the first and second information inputs of the cell being connected to the information inputs of the first multiplexer, the configuration input of which is connected to the second tuner to the primary input of the cell, the output of the first multiplexer is connected to the direct input of the BANGE element, the output of which is the first output of the cell, the second output of which is connected to the output of the second multiplexer, the configuration inputs of which are connected to the first and second configuration inputs of the cell, respectively ( the information inputs of the second multiplexer are connected to the first information input of the cell, to the zero bus of the cell, to the outputs of the AND and OR elements, respectively. f1 hs 4 5 -j

Description

Итоб1 г.тение птноситс к автоматике и вычислительной технике и предназначено дл построени плоскостных однородныхструктур, реализующих про извольные (в том числе любые скобочные ) нормальные формулы из Ъ букв, заданные в базисе И, ИЛИ, НЕ, при равной доступности пр мых и инверсных выходов источников информации. Известна чейка однородной структуры , содержаща элементы И, ИЛИ, НЕ СП. Недостатком известной структуры, построенной на базе такой чейки, вл етс то, что она не позвол ет реализовать произвольные формулы ука занного класса. При ее использовании нормальные формулы в базисе И, ИЛИ, НЕ должны предварительно быть преобразованы в базис двухместных опера- 20 Itto1 is a subdivision of automation and computing technology and is intended for building planar homogeneous structures that implement arbitrary (including any bracket) normal formulas of letter b, given in the basis of AND, OR, NOT, with equal accessibility of direct and inverse outputs sources of information. A well-known cell of a homogeneous structure containing the elements AND, OR, NOT JV. A disadvantage of the known structure built on the basis of such a cell is that it does not allow the realization of arbitrary formulas of this class. When using it, the normal formulas in the basis AND, OR, must NOT first be converted into the basis of two-place operations.

ций И-НЕ, что приводит к большому числу чеек в однородной структуре. Наиболее близкой по технической сущности к предлагаемой вл етс чейка, содержаща элементы И, ИЛИ, ЗАПРЕТ, причем п ть входов чейки подключены к соответствующим входам логических элементов, а на двух выходах известной чейки обеспечиваетс формирование заданных функциональ-30 ных зависимостей. Известна чейка предназначена дл построени линейных однородных структур, реализующих произвольные дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ) из Ь букв, произвольные скобочные формы при , а также больщой класс скобочных форм дл , при равной доступности пр мых и инверсных выходов, источников информации 2J. tions is NOT, which leads to a large number of cells in a homogeneous structure. The closest to the technical nature of the proposed is a cell containing the elements AND, OR, BAN, with five cell inputs connected to the corresponding inputs of logic elements, and two outputs of the well-known cell provide the formation of the specified 30 functional dependencies. The known cell is designed to build linear homogeneous structures that implement arbitrary disjunctive and conjunctive normal forms (DNF and CNF) of b letters, arbitrary bracket forms for, as well as a large class of bracket forms for equal availability of direct and inverse outputs, information sources 2J .

Недостатком данной чейки вл етс большое число внешних выводов, а также то, что однородна структура, построенна на ее основе, не универ .сальна в рассматриваемом классе формул при IT 7 11.The disadvantage of this cell is the large number of external conclusions, as well as the fact that the homogeneous structure built on its basis is not universal in the class of formulas under consideration at IT 7.11.

Целью изобретени вл етс сокращение числа внешних выводов чейки.The aim of the invention is to reduce the number of external terminals of the cell.

Поставленна цель достигаетс тем, что чейка однородной структуры содержаща элементы ЗАПРЕТ, И и РШИ, причем первый и второй информационные входы чейки подключены к входам элементов И и ИЛИ соответственно, первьш настроечный вход чейки подключен к инверсному входу элемента ЗАПРЕТ, содержит дополнительно два мультиплексора, причем первьш иThe goal is achieved by the fact that the homogeneous structure cell containing the BAN, AND and RSHI elements, the first and second information inputs of the cell are connected to the inputs of the AND and OR elements, respectively, the first configuration input of the cell contains an additional two multiplexers, first and

онные и функциональные схемы, реализуем1з1е чейкой путем настройки j на фиг.З - пример реализации формулы древовидной схемой; на фиг.4 - пример реализации формулы древовидной схемой в однородной структуре.One-dimensional and functional diagrams, implemented by a cell by adjusting j in FIG. 3 — an example of the implementation of a formula with a tree diagram; figure 4 is an example of the implementation of the formula tree with a homogeneous structure.

Ячейка (фиг.) содержит два информационных 1 и 2 и два настроечных 3 и 4 входа, элементы И 5, ИЛИ 6,The cell (fig.) Contains two informational 1 and 2 and two tuning 3 and 4 inputs, elements AND 5, OR 6,

Ячейка путем настройки реализует следующие системы формул:The cell, by tuning, implements the following formula systems:

1. При , 1. When

2.При z,12.When z, 1

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

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

(фиг.2г) (figg)

в общем случае дл реализации произвольной нормальной формулы из 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,In the general case, to implement an arbitrary normal formula of fi letters, specified in the basis of AND, OR, NOT with equal availability of direct and inverse outputs of the source information sources, the information inputs of the cell are connected to the information inputs of the first multiplexer, the configuration input of which is connected to the second configuration input of the cell, the output of the first multiplexer is connected to the direct input of the BANCH element, the output of which is the first output of the cell, the second output of which is connected to the output of the second multiplexer, tuning in Which odes are connected to the first and second tuning inputs of the cell, respectively, the information inputs of the second multiplexer are connected to the first information input of the cell, to the zero bus of the cell, to the outputs of the AND and OR elements, respectively. Figure 1 shows the functional circuit diagram of the cell, figure 2 shows the switching signal PROCEDURE 7, an optical cluster 8 with two informational and one tuning inputs, g the multiplexer 9 with four informational and two tuning inputs, two outputs 10 and 11. The structure of the cell is described by the system of formulas: . ,,,, 4 (), Z2va z 22vOz Z2vO (a, z 2c, builds a tree diagram of the two-input elements AND and OR, which is embedded in a planar homogeneous cell structure, which is a rectangle. cell capabilities allow times estit in each column structure one two-input element tree scheme we (the number of elements in the circuit is equal to t) -), and in each column, - a cascade circuit. A cascade is a linear homogeneous structure of the maximum number of AND and OR elements included in a tree diagram, each element of such a scheme included in only one cascade. At the same time, the cells of the structure corresponding to the elements AND of the tree diagram are tuned to the implementation of system 3, the corresponding elements of OR — to the implementation of system 4. Each cell of the structure associated with the last element of each cascade, except for the cascade connected to the output of the circuit, is tuned for the completion of system 2. The remaining cells of the structure must implement system 1. The input variables are fed to a uniform structure as follows. The variable with the first input of the initial element is gb (i 1,2, ..., cascade of the tree, is connected to the input of the 1st row of the structure. The remaining variables are fed to the inputs f of the structure columns in which the cells are placed corresponding to the elements of the tree diagram, the second inputs of which are connected to the inputs of variables. The output variable is removed from the output of the first line of the structure. The number of cells in a homogeneous structure is determined by the ratio L (ti-1 | K,

fOfO

ФигЦ где К - число каскадов в древовидной схеме. Число каскадов, на которые может, быть разбита древовидна схема,реализующа нормальную формулу из А, букв в рассматриваемом базисе, определ етс соотношением ji«., , где tj3- символ округлени д6 ближайшего меньшего целого. Поэтому справедливо утверждение. Произвольна нормальна формула ; из Ъ букв, заданна в базисе И, ИЛИ, НЕ, при равной доступности пр мых и инверсных выходов источников информации реализуетс в плоскостной,однородной структуре из ( чеек. При этом дл реализации формулы, требующей числа чеек, определ емого верхней оценкой, число столбцов в однородной структуре равно h-1, а число строк - y-I На фиг.З приведена древовидна схема с вьщёленными каскадами, реализующа формулу у () (x2vx)v() () (i-,l7)(i1 (-te 1 :,2)( котора при вложении в однородную структуру требует числа чеек, определ емого верхней оценкой: о На фиг.4 приведена однородна структура, настроенна на реализацию древовидной схемы, приведенной на фиг.З. Таким образом, предлагаема чейка по сравнению с известной обеспечивает сокращение числа внешних выходов (6 вместо 7) при более широких функциональных возможност х.Figs where K is the number of cascades in the tree diagram. The number of cascades into which a tree can be broken up that implements a normal formula of A, the letters in the basis considered, is determined by the relation ji ", where tj3 is the rounding symbol e6 of the nearest smaller integer. Therefore, the statement is true. Arbitrary normal formula; of letters, given in the basis of AND, OR, NOT, with equal availability of direct and inverse outputs of information sources is implemented in a planar, homogeneous structure of (cells. At the same time, to implement a formula requiring the number of cells defined by the upper estimate, the number of columns in a homogeneous structure is equal to h-1, and the number of lines is yI. In FIG. 3, a tree diagram with advanced cascades is presented, implementing the formula y () (x2vx) v () () (i-, l7) (i1 (-te 1: , 2) (which, when invested in a homogeneous structure, requires the number of cells determined by the upper estimate: o on homogeneous structure which is tuned to the realization of a tree circuit of fig.Z. Thus, the cell A proposed compared with known allows reducing the number of external output (6 instead of the 7) for broader functional capabilities of x.

i«i "

XifXif

9 kf9 kf

f 0f 0

s xgs xg

У2 XY2 X

Claims

A HOMOGENEOUS STRUCTURE CELL containing the BAN, AND and. OR elements, with the first and second information inputs of the cell connected to the inputs of the AND and OR elements, respectively, the first tuning input of the cell connected to the inverse input of the BAN element, distinguishing -.

in order to reduce the number of external outputs, the cell contains two additional multiplexers, the first and second information inputs of the cell connected to the information inputs of the first multiplexer, the tuning input of which is connected to the second tuning input of the cell, the output of the first multiplexer is connected to the direct input element BAN, whose output is the first output of the cell, the second output of which is connected to the output of the second multiplexer, the tuning inputs of which are connected to the first and second settings th inputs of the cell, respectively, the second multiplexer data inputs connected to the first data input of the cells to the zero cell bus to the outputs of the AND and OR, respectively.

§ | a a e b

SO y>