AP06_1.vp 1 Introduction The procedure in the design of logical structural models with multiplexors might seem to be complete. It appears, however, that the Artjuchov-Shalyto extension of the Boolean function, which models the performance of a multiplexor, leads to its mere “setting”, and the generalised model of the multiplexor performance makes it possible to design structural models with multiplexors according to the disjoint decomposition of the given Boolean function. 2 Boolean function Let the Boolean function f x x x ym m:{ , } { , }: , , ,0 1 0 1 1 2� � � be given. If we denote the set { }xi i m �1 of the function f argu- ments by the symbol X, we can write f (X) instead of f (x1, x2, …, xm). Let us also write f (xi � �i) instead of f (x1, x2, …, xi�1, �i, xi�1, …, xm), where �i � {0, 1}. We require the function f (X)to be minimal with respect to the number of arguments, i.e., not to contain fictive arguments; the argument xi is called fictive if f (xi � 0) � f (xi � 1). The term Hamming weight wH of the function f – wH f – denotes the value of the arithmetic expression w f X fH m m m ( ) ( , , , ) , , , { , } � � � � � � � � � � � 1 2 0 11 2 Let x x x� � � � � � �� � � 0 1 ; each Boolean function f (X) can be expressed by means of a canonic normal disjunctive formula – cndf f (X) f X x x x f m m m m m( ) ( , , , ) , , , { , } � � � � � �� � � � � � � � � 1 2 1 2 0 1 1 2 1 2� . Then, if w fH m 2 2 or w fH m � 2 2, or if w fH m � 2 2, it is preferable to write down the respective cndf f (X) or cndf f X( ), or to apply the Artjuchov-Shalyto extension of the func- tion f (X) [1] f X x x f x x f x f X x x f x x f x i i i i i i i i i ( ) ( ) ( ) ( ) ( ) ( � � � � � � � � � 0 1 0 i � 1) the validity of which can be easily confirmed by supplying 0 or 1 for xi. Let a dichotomy {X1, X0}be given on a set of X arguments x1, x2, , xm without loss of generality, such that X1 � {x1, x2, …, xn} and X0 � {xn � 1, xn � 2, …, xm}, where n < m. Let the simple k-multiple (k < n) disjoint decomposition of the function f (X) be called the composition f X X X X Xk( ) ( ), ( ), , ( ),� � � � �1 1 2 1 1 0� . The construction of the simple k-multiple (k < n) disjoint decomposition of function f (X) can be easily done by means of a decomposition by map[2, 3]. 3 Multiplexor The term multiplexor (MX) [2, 4, 5] denotes a logical ob- ject modeled both in a parametrical and an algebraic way. See Fig.1, where Ar (r � 1, 2, …, k) and dj ( j � 0, 1, …, 2 k�1) are the respective adjustable address-, and data-input ports: y MX X X X g X g X g X k k � � ( ( ), ( ), , ( ) ( ), ( ), , ( � � �1 1 2 1 1 0 0 1 0 2 1 � � 0 0 2 1 1 1 2 1 1 0 1 2 ) ( ) ( ) ( ) ( ) ) � � � � � j k j k kX X X g X� � �� � � � © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 57 Czech Technical University in Prague Acta Polytechnica Vol. 46 No. 1/2006 Logical Structural Models with Multiplexors J. Bokr, V. Jáneš The paper deals with the use of multiplexors in designing logical structural models.. The applications can be preferably used in designing morphology on EFGA chips and other programmable structures. Illustrative examples are included. Keywords: Boolean function, Artjuchov–Shalyto extension, Shannon extension, Boolean function decomposition, multiplexor. Fig. 1: a) Schematic diagram of a multiplexor, b) structural model of a multiplexor where j k r k r r k � � � � �� � � �1 2 1 2� . 4 Multiplexor and the Boolean function Let us provide the output port MX with an element of anticoincidence such that y Y z� � , where z x xi i�{ , , , }0 1 – see Fig. 2. Let us design a multiplexor modelled by the func- tion f (X): y z MX x x x g g gm m m � � � � � � � � ( ), , , , , , , , , { , } 1 2 0 1 2 1 0 11 2 � � � � � m mx x x fm m1 2 1 2 1 2� � � � � �� ( , , , ).� Hence g fj m� �( , , , )� � �1 2 , where j m i m i i m � � � � � �� � � �1 2 1 2, , , . If it is more suitable to construct y � cndf f X( ) or y � cndf f X( ), – see Par. 2 –, then the respective z � 0 or z � 1, for y � �f X( ) 0 or y � �f X( ) 1. If one cannot decide whether to construct f (X) or f X( ), then if w f X w f XH H m m m m( ) ( ), , , , , ,� � � � � �1 2 1 22 2 2 2� � or w f X w f XH H m m m m( ) ( ), , , , , ,� � � � � �1 2 1 22 2 2 2� � � then z x� 1 and y � � � �x f x x f x1 1 1 10 1( ) ( ) or z x� 1 and y � � � �x f x x f x1 1 1 10 1( ) ( ) respectively. Example 1: Construct a multiplexor realizing the function f (x1, x2, x3) � 0001 0111. Since w fH � �4 2 2 3 , as well as w f X w f XH H m m ( ) ( ) , , , , , ,� � � � � �1 2 1 24 4 1 3 � � � � , we obtain z x� 1 and since f x x x MX x x x x MX x ( , , ) ( , , , , , , , , , ) ( , 1 2 3 1 2 3 1 1 0 0 0 1 0 1 1 1� � � � x x d d d d d d d d2 3 0 1 2 3 4 5 6 7, , , , , , , , ) we obtain d0 � d1 � d2 � d5 � d6 � d7 � 0 and d3 � d4 � 1, i.e. y � MX x x x( , , , , , , , , , )1 2 3 0 0 0 1 1 0 0 0 , which is certainly a simpler setting of MX than that of d0 � d1 � d2 � d4 � 0 and d3 � d5 � d6 � d7 � 1. 5 Multiplexor and the simple k-multiple disjoint decomposition Let f x x x X X X Xm k( , , , ) ( ), ( ), , ( ),1 2 1 1 2 1 1 0� �� � � � � where X x x xn1 1 2� { , , , }� and X x x xn n m0 1 2� � �{ , , , }� , be a simple k-multiple (k < n) disjoint decomposition of the function f x x xm( , , , )1 2 � . Let there be �r rx r k� �( , , , )1 2 � with k � n and let us construct the Shannon extension of the given function according to the arguments x x xn1 2, , ,� , without loss of generality f x x x x x x f m n n n( , , , ) ( , , , , , , 1 2 1 2 1 2 1 2 1 2 � �� � � � � �� � � � � � � � � n n mx x, , , ).�1 � And further let f x x x MX x x x g g gm n j n n ( , , , ) , , , , , ,( )1 2 1 2 0 1 2 1 0 2 � � �� � � � � � �1 1 2 1 2x x x gn jn � � � � ; hence g f x x xj n n n m� � � �( , , , , , , , )� � �1 2 1 2 � , where j n i n i i n � � � � � �� � � �1 2 1 2 . Note that the selection of arguments according to which the Shannon extension of the given function f x x xm( , , , )1 2 � is done depends completely on the view of the designer, and there is no reason to distinguish the development qualita- tively according to the ‘left-side’ arguments x1, x2, …, xn or ‘right-side’ arguments x x xn n m� �1 2, , ,� of the function f, as stated in [1]. Example 2: Let the function y � � (5, 6, 7, 10, 11, 19, 21, 23, 26, 27, 30, 31) be given; design a structural model with MX according to the Shannon development extension of the given function both according to arguments x1, x2, x3 and according to arguments x4, x5, i.e., according to y � �MX x x x h h h MX x x g g g g( ) ( ), , , , , , , , ,1 2 3 0 1 7 4 5 0 1 2 3� . Thus, let us construct decomposition maps (Fig. 3.) hence 58 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 1/2006 Czech Technical University in Prague Fig. 2: Multiplexor and the element of the sum modulo 2 – M2 Fig. 3: Decomposition maps of the function from Example 2 y � � � � � � � x x x x x x x x x x x x x x x x 1 2 3 1 2 3 4 5 1 2 3 4 1 2 3 1 0 0 ( ) ( ) ( ) ( ) x x x x x x x x x x x x x x x x x 2 3 4 5 1 2 3 4 5 1 2 3 4 1 2 3 4 ( ) ( ) ( ) ( ) � � � � � as well as y � � � � � � � � x x x x x x x x x x x x x x x x x 4 5 4 5 2 3 4 5 1 2 2 3 2 3 4 5 0( ) ( ) ( ) ( 1 2 3 2 3� �x x x x ). Hence the structural models from Fig. 4. Note that in Fig. 4b) a ROM module is suggested and in Fig. 4c) the struc- ture is realized only with multiplexer modules. Let a simple k-multiple disjoint decomposition f x x x X X X Xm k( , , , ) ( ), ( ), , ( ),1 2 1 1 2 1 1 0� �� � � � � be given, where � will be termed an outer function and the functions �1 (i � 1, 2, …, k) will be denoted inner functions. And, further, let f x x x MX X X X g g g m k k ( , , , ) ( ), ( ), , ( ) , , , 1 2 1 1 2 1 1 0 1 2 � � � � � � � � �1 Hence g X X X Xj k� � � �1 1 2 1 1 0( ), ( ), , ( ),� , where j n i n i i n � � � � � �� � � �1 2 1 2, , , . Example 3: Construct a structural model with MX according to the decomposition y � � � �( )( , , ), ( , , ), ,1 1 2 3 2 1 2 3 4 5x x x x x x x x of the function y from Example 2. According to the decompo- sition map (Fig. 5) we obtain �1 1 2 3 1 2 2 3( , , )x x x x x x x� � �2 1 2 3 1 2 3 2 3( , , )x x x x x x x x� � for the inner functions. Since y � MX g , g , g , g( ),� �� � 0 1 2 3 we obtain y � � � � �� � � � � � � �� � � �2 4 2 2 4 5 2 4 50( ) ( ) ( ) ( )x x x x x and hence the structural model in Fig. 6. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 59 Czech Technical University in Prague Acta Polytechnica Vol. 46 No. 1/2006 Fig. 4: Structural model with MX from Example 2 Fig. 5: Decomposition map of the function from Example 3 6 Conclusions The multiplexer appears to be a very helpful MSI module. The design of structural models is sufficiently simple and suit- able also for the implementation of logical functions on chips provided with FPGA or FPD. References [1] Šalyto, A. A.: Metody apparatnoj i programmnoj realizacii algoritmov. Nauka, Sankt-Peterburg 2000. [2] Bokr, J., Jáneš,V.: Logické systémy. Vydavatelství ČVUT, Praha 1999. [3] Bokr.J.: “Sovmestnaja dekompozicija sistem bulevych funkcij.” Avtomatika i vyčislitelnaja technika, 2000, No. 2, p. 38–44. [4] Frištacký, N. at al..: Logické systémy. Bratislava/Praha, ALFA/SNTL 1986. [5] Liebig, H., Thome, S.: Logischer Entwurf digitaler Systeme. Springer, Berlin – Tokio 1996. Doc. Ing. Josef Bokr, CSc. e–mail: bokr@kiv.zcu.cz Department of Information and Computer Science University of West Bohemia Faculty of Applied Sciences Universitní 22 306 14 Pilsen, Czech Republic Doc. Ing. Vlastimil Jáneš, CSc. e–mail: janes@fd.cvut.cz Department of Control and Telematics Czech Technical University in Prague Faculty of Transportation Sciences Konviktská 20 110 00 Prague 1, Czech Republic 60 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 46 No. 1/2006 Czech Technical University in Prague Fig. 6: Structural model with MX prescribed by the decomposition from Example 3