Diagram of functional elements

circuit of functional elements, network of functional elements

A mathematical model of real objects, related to information processing, in which intermediate results may be used several times. These objects include, for example, electron-tube schemes, neural networks and certain forms of computing algorithms. This is one of the basic classes of control systems (cf. Control system). A diagram of functional elements can be considered as an automaton without memory.

Mathematically, a diagram of functional elements can be defined as an oriented graph without cycles with its edges and vertices marked; its set of vertices can be divided into two subsets. The vertices of one of these are called the inputs of the diagram. No edges can lead to these vertices, and each of them is ascribed a letter of the alphabet of variables $ X = \{ x _ {1} \dots x _ {n} \} $. The vertices of the other subset are ascribed letters of the alphabet $ {\mathcal E} = \{ \phi _ {1} ( {} ) \dots \phi _ {m} ( {} ) \} $ of functional symbols.

The alphabet $ {\mathcal E} $ is in a one-to-one correspondence with a set of functions $ \overline {\mathcal E} \; = \{ \phi _ {1} ( {} ) \dots \phi _ {m} ( {} ) \} $. Certain vertices of the graph are distinguished and are called the outputs of the diagram. A vertex at which (numbered) edges come together and which is ascribed the symbol $ \phi _ {i} $ from $ {\mathcal E} $( its valency is equal to the number of edges coming together) is called the functional element $ E \phi _ {i} $. The other ends of the edges that are incident to this vertex are the inputs of $ E \phi _ {i} $, while the vertex itself is the output of $ E \phi _ {i} $. For every given assignment $ \widetilde \sigma $ at the inputs of $ E \phi _ {i} $, the value of $ \phi _ {i} $ on $ \widetilde \sigma $ is realized at the output of $ E \phi _ {i} $( i.e. at the vertex $ \phi _ {i} $); thus, the functional element $ E \phi _ {i} $ realizes the function $ \phi _ {i} $. Hence every diagram of functional elements realizes certain functions at their outputs. The set of functional elements that corresponds to the alphabet $ {\mathcal E} $, from which diagrams of functional elements are constructed, is called the basis $ B _ {\mathcal E} $. The set of all diagrams of functional elements, constructed using functional elements from $ B _ {\mathcal E} $, is called the set of diagrams of functional elements in the basis $ B _ {\mathcal E} $. If $ \overline {\mathcal E} \; $ is complete, then $ B _ {\mathcal E} $ is complete, and a diagram of functional elements in $ B _ {\mathcal E} $ can realise any function. It is further assumed that the variables from $ X $ take the values $ 0, 1 $, and that $ \overline {\mathcal E} \; $ is a subset of the functions of the algebra of logic. The results for this type of bases are most complete.

Figure: d031570a

The diagram in the basis $ \{ \&, \lor , {} ^ {-} \} $( see Fig.) is an example of a diagram of functional elements. Its inputs are the vertices $ x _ {1} $ and $ x _ {2} $, its output the vertex $ E _ {\&} ( a _ {4} ) $, and at it the function

$$ ( x _ {1} \lor x _ {2} ) \& \overline{ {x _ {1} \& x _ {2} }}\; ,\ \ \textrm{ i.e. } \ x _ {1} \overline{x}\; _ {2} \lor \overline{x}\; _ {1} x _ {2} , $$

is realized.

An equivalent definition of a diagram of functional elements can also be given in terms of equalities. For the example in the figure, such a system can be written down in the following way:

$$ a _ {1} = x _ {1} \lor x _ {2} ,\ \ a _ {2} = x _ {2} \& x _ {2} , $$

$$ a _ {3} = \overline{a}\; _ {2} ,\ a _ {4} = a _ {1} \& a _ {3} = x _ {1} \overline{x}\; _ {2} \lor \overline{x}\; _ {1} x _ {2} . $$

Functional elements in $ B _ {\mathcal E} $ are usually ascribed non-negative numbers, called the weights (or complexities) of the functional elements of the basis. By the complexity of a diagram of functional elements one understands the sum of the weights of all functional elements that are present in this diagram. The minimum complexity that is sufficient for the realization of every Boolean function in $ n $ variables by a diagram of functional elements in any finite basis (with non-zero weights) is asymptotically equal to $ \rho 2 ^ {n} /n $( see [1]), where $ \rho $ is a constant independent of the basis (see Synthesis problems). The minimum complexity that is sufficient for the realization by a diagram of functional elements of a system $ F $ of functions dependent on the same variables is asymptotically equal to

$$ \rho \frac{ \mathop{\rm log} _ {2} | F | }{ \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} | F | } , $$

where $ | F | $ is the number of functions in $ F $ and $ \rho $ is a constant calculated for the basis (see [2]).

According to the number of inputs that can be associated with an output of an arbitrary functional element one can single out so-called diagrams of functional elements without output branching, or formulas, from the class of diagrams of functional elements (the output of each functional element of such a diagram can only have one input associated with it). Unlike formulas, diagrams of functional elements of general form can be considered as calculation diagrams which take intermediate results into account. For formulas, the minimum complexity necessary for the realization of every Boolean function in $ n $ variables by a formula in any finite basis (with non-zero weights) is asymptotically equal to $ \rho 2 ^ {n} / \mathop{\rm log} n $, where $ \rho $ is a constant depending on the basis (for a comparison with contact $ \pi $- schemes, see Contact scheme). For bases that contain elements with zero weights, the complexities of diagrams of functional elements behave differently (see, for example, [5]).

Furthermore, the problem of synthesis of diagrams in infinite bases is of interest. The most completely studied case is the one in which the elements of the basis realise threshold functions. A Boolean function $ f( x _ {1} \dots x _ {n} ) $ is a threshold function if there are real numbers $ w _ {1} \dots w _ {n} $ and $ h $ such that

$$ \tag{* } w _ {1} x _ {1} + \dots + w _ {n} x _ {n} \geq h $$

if and only if $ f( x _ {1} \dots x _ {n} ) = 1 $. A functional element that realizes a threshold function is called a threshold element. Diagrams of functional elements in a basis of threshold elements are called diagrams of threshold elements. Two types of such bases are usually studied: 1) the weights of the threshold elements are equal to 1; or 2) the weight of a threshold element is equal to the sum of the absolute values of all coefficients $ w _ {i} $( given the condition that the threshold functions are defined by the integer inequality (*)). For all these bases asymptotic estimates have been obtained for the complexity of diagrams of threshold elements: 1) $ 2( 2 ^ {n} /n) ^ {1/2} $( see [6]); and 2) $ 2 ^ {n} /n $( see [7]).

The path between the input and output of a diagram of functional elements is called a chain. The number of vertices of the chain, apart from the input, is called the length of the chain. The maximum length of a chain in a diagram of functional elements is called the depth of the diagram. The minimum depth of a diagram of functional elements (or of a formula) that is sufficient for the realization of every Boolean function in $ n $ variables in the basis $ \{ \&, \lor, {} ^ {-} \} $ is equal to

$$ n - \mathop{\rm log} _ {2} \mathop{\rm log} _ {2} n+ O( 1) $$

(see [8]).

Apart from weights, the functional elements of the basis can be ascribed non-negative numbers, called delays. By the delay of a chain one means the sum of the delays of the functional elements in it. By the delay of a diagram of functional elements one means the maximum delay of the chains of this diagram. The concepts of a delay (for unit delays of the basis) and the depth of diagrams of functional elements, generally speaking, do not coincide (see [9]).

The power of a diagram can also be taken as the complexity of the diagram. The power of a diagram of functional elements on an assignment $ \widetilde \sigma $ of input variables is the number of its functional elements the outputs of which are equal to 1. The power of a diagram of functional elements $ S $ is the maximum of its powers on $ \widetilde \sigma $ for all possible $ \widetilde \sigma $. The minimal power that is sufficient for the realization of every Boolean function in $ n $ variables by a diagram of functional elements in an arbitrary finite basis is of an order no less than $ n $ and no more than $ 2 ^ {n} /n $( see [10], ).

References

[1]	O.B. Lupanov, "A method of circuit synthesis" Izv. Vuzov. Radiofizika , 1 : 1 (1958) pp. 120–140 (In Russian)
[2]	O.B. Lupanov, "An approach to systems synthesis" Probl. Kibernet. , 14 (1963) pp. 31–110 (In Russian)
[3a]	O.B. Lupanov, "Complexity of formula realization of functions of logical algebra" Probl. Cybernetics , 3 (1962) pp. 782–811 Probl. Kibernet. , 3 (1960) pp. 61–80
[3b]	O.B. Lupanov, "A class of circuits of functional elements" Probl. Kibernet. , 7 (1962) pp. 61–114 (In Russian)
[4]	E.I. Nechiporuk, "On the complexity of networks in certain bases containing nontrivial elements with zero weights" Probl. Kibernet. , 8 (1962) pp. 123–160 (In Russian)
[5]	O.B. Lupanov, "On synthesis of circuits of threshold elements" Probl. Kibernet. , 26 (1973) pp. 109–140 (In Russian)
[6]	E.Yu. Zakharova, "On synthesis of circuits of threshold elements" Probl. Kibernet. , 9 (1963) pp. 317–319 (In Russian)
[7]	S.B. Gashkov, "On the depth of Boolean functions" Probl. Kibernet. , 34 (1978) pp. 265–268 (In Russian)
[8]	V.M. Khrapchenko, "Distinction and likeness between delay and depth" Probl. Kibernet. , 35 (1979) pp. 141–168 (In Russian)
[9]	O.B. Lupanov, "On circuits of functional elements with delays" Probl. Kibernet. , 23 (1970) pp. 43–81 (In Russian)
[10]	M.N. Vaintsvaig, "On power of circuits of functional elements" Dokl. Akad. Nauk SSSR , 139 : 2 (1961) pp. 320–323 (In Russian)
[11a]	O.M. Kasim-Zade, "On a complexity measure for gate networks" Probl. Kibernet. , 38 (1981) pp. 117–179 (In Russian)
[11b]	O.M. Kasim-Zade, "On simultaneous minimization of the complexity and the power of gate networks" Probl. Kibernet. , 33 (1978) pp. 215–220 (In Russian)
[12]	J.E. Savage, "The complexity of computing" , Wiley (Interscience) (1976)

🛠️ This page contains images that should be replaced by better images in the SVG file format. 🛠️