AP05_2.vp 1 Introduction The trivial logic arrays dealt with here [1,2] (Fig. 1.) are: � PLA (programmable logic array) with programma- ble input and output matrices, � PAL (programmable array logic) with a program- mable input matrix and a given output matrix, � ROM (read only memory) a given input matrix (is given through an address decoder) and a program- mable output matrix. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 27 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 2/2005 Trivial Logic Arrays J. Bokr, V. Jáneš This paper deals with matrix modelling of trivial logic arrays (PLA, PAL, ROM) and the design of the above array as structural models of static and dynamic logic objects. Keywords: cartesian product of matrices, PLA, PAL, ROM, canonical decomposition, states coding, states coding of Miller or Liu, substitute input variable. a) b) e) c) d) Fig. 1: Trivial logic arrays: a) block diagram, b) labelling; examples of logic arrays: c) PLA, d) PAL, e) ROM, where × and � mean the programmable and given positions, respectively y x x x x x x y x x x x x x 1 1 2 3 1 2 3 2 1 2 3 1 2 3 � � � � y x x x x y x x x x 1 1 2 1 3 2 1 2 2 3 � � � � y x x x x x x y x x x x 1 1 3 1 2 1 3 2 2 3 1 3 � � � � � The input matrix has either conjunctors (& - AND) or in- verse disjunctors {� – NAND). The output matrix has either disjunctors {1 � OR) or inverse disjunctors (NOR). The paper deals with matrix analysis and synthesis of triv- ial logic arrays. 2 Cartesian product of Boolean matrices The Cartesian product M (OP) (op) M of Boolean matrices � � � � � �M q h mij: : ,1, 2, , 1, 2, , 0, 1� � �� i j � � � � � �M : , , , , , , , : ,1 2 1 2 0 1� � �h p j k jk� m denotes a Boolean matrix � � � � � �M OP op q p i k ik( )( ) : , , , , , , , : ,M 1 2 1 2 0 1� � �� � where �ik ij jk OP j m op� � �� � �� ( ) m and (OP) and (op) are Boolean operators. Example 1: Let a system {y1, y2} of Boolean functions y1, y2 be given � � � �� �y1 2 0 1 40 1, , ,y � � � � � � � : Write the system {y1, y2} as matrices {cndf (y1), cndf (y2)}, where cndf denotes a canonical normal disjunctive formula. Note that ( )x x� �0 and ( )x x� �1 : 3 Structural model of a static logic object Let � � � �� j m m jx x x y: , , : , , ,0 1 0 1 1 2 � � be a Boolean func- tion and the literal x� be � �x x x� � � �� � �( , )0 1 , where x x0 � and x x1 � . Note that the function �j can be expressed as cnd cndf x x xj m m j j m( ) , , , ( , , , ) � � � � � � � � � � � � � � 1 2 1 2 1 2 1 1 2 � � � or as ndf (a normal disjunctive formula) ndf x x x Kj j j jk i ij j j jk j j jk( ) , , , � � � � � � � � �� � 1 2 1 2 1 2 � � , where Kij is a normal conjunct on � �X x x x x x xm m� 1 1 2 2, , , , , ,� or finally expressed as mndf (�j) (minimal ndf ). Let the symbol K denote a set of conjuncts Kij from ndf (�j). Let � � � �0 1 0 1, , , ,m n � be a finite automaton model of a binary static logic object where � is the vector output function � �� �� �� � � � � � � � 0 1 0 1 , ,n m � � � �� : , , : , , , , , ,0 1 0 1 1 2 1 2 m n m nx x x y y y� � � represented by a system � �� j j n �1 of components, output functions � � � �� j m m jx x x y: , , : , , ,0 1 0 1 1 2 � � . Let Min (Mout) be the input (output) matrix of the given static object, i.e.: � � � � � �M , , , K , , , m ,in : :1 2 1 2 2 0 1� �� r s, � 0 for x Ks ijs � � , r s, � 1 for x Ks s ij � � , � � � � � �M , , , K , , , n ,out : :1 2 1 2 0 1� �� r s, � 0 for K ndfij j� ( )� , r s, � 1 for K ndfij j� ( )� . 28 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 2/2005 Czech Technical University in Prague x1 x2 x3 x4 y1 y2 1 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 � � � �y y x x x x1 2 1 2 3 4 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 1 , , , , &� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � T x x x x & , , , & 0 1 1 1 1 0 0 0 1 0 1 1 2 3 4 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 � � � � � � � � � � � � � � � � � � � � & � � � � � � � � � � � � � � � � � ( ) ( ) ( ) ( ) ( ) ( ) ( x x x x x x x 1 2 3 4 1 2 3 1 0 0 1 0 1 � � � � � � � � � 0 0 1 0 0 1 0 0 0 4 1 2 3 4 1 2 3 ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( x x x x x x x x ) ( ) ( ) ( ) ( ) ( ) & x x x x x 4 1 2 3 4 0 0 1 1 1 0 � � � � � � � � � � � � � � � � � � � � � � 1 1 1 1 0 0 0 1 0 � � � � � � � � � � � � � � � � � � � � � � � � � � �x x x x x x x x x x x x x x x x x x x x 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4� � � � � � � � � � � � � � � � � � � � � � � � � � � & [ 0 1 1 1 1 0 0 0 1 0 1 2 3 4 1x x x x x x2 3 4 1 2 3 4 1 2 3 4 1 2 3 4x x x x x x x x x x x x x x� �, ] If � �XT s, , m X s x: , :1 2 2� � for s k� �2 1, s xs� for s k� 2 (k m� �0 1 2 1, , , ,� ), then for the trivial logic array M the following are valid [ , , , ] ( & & ) &y y y M X Mn T 1 2 � � �in out , [ , , , ] ( & & ) &y y y M X Mn T 1 2 � � �in out , where X x x x x x xm m� [ , , , , , , ]1 1 2 2 � . The total capacity (area) C(M) (bit) of trivial logic array M can be written as C M C M C M m n K( ) ( ) ( ) ( )� � � �in out 2 . Example 2: Design a PLA (Min, Mout) modeled system of out- put functions y x x x x x x x x1 1 2 3 1 2 3 3 3� � � � �( ) ( ) � � y x x x x x x x x2 1 2 1 2 3 1 2 3� � � �( ) � and determine its capacity � �� �� � � �x x x x x x x x1 2 1 2 1 2 1 2, . Hence M in � 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 2 2 3 3 1 2� � � � � � � � � � � � � � � � � � � � � � x x x x x x x x � � x x x x x x x x x 1 2 1 2 1 2 3 3 3 � � � M y out � � � � � � � � � � � � � � � � � � � � � � � 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 y x x x x x x x x x x x 2 1 2 1 2 1 2 1 2 3 3 3 � � � � and Fig. 2 can be constructed. Since [ , , ]y y1 2 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 � � 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 2 2 3 3 � � � � � � � � � � � � � � � � � � � � � � x x x x x x � � � � & & x x x x x x 1 1 2 2 3 3 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � � � � � � � � � � � �� � � T & & 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 � � � � � � � � � � � � � � � � � � � � � � � � � y y x x x x x x x 1 2 3 3 1 2 3 1 2 � � �� ��[ � x x1 2 ] and C M( ) � � � � � �2 4 6 3 6 66. The starting point for designing Min and Mout trivial logic array matrices is a system of tables� �� j j n �1 (ROM) or a com- pressed form [2] (PLA, PAL) of it, including the correspond- ing record of the cndf ({�j}) of the group function or the ndf ({�j}) of the component functions of �j. Example 3: The following system of functions can also be written as )* including the group cndf or ndf: cndf ( , , ) ( ) ( ) ( )y y y x x x y y x x x y x x x y y x 1 2 3 1 2 3 1 2 1 2 3 1 1 2 3 1 2� � � � � 1 2 3 1 1 2 3 3 1 2 3 3x x y x x x y x x x y( ) ( ) ( )� � © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 29 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 2/2005 Fig. 2: PLA from Example 2 x1 x2 x3 y1 y2 y3 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 – – – 1 0 1 – 0 1 1 1 0 0 0 0 1 1 1 – 0 1 x1 x2 x3 y1 y2 y3 0 – 0 1 1 0 0 – 1 1 0 0 1 1 0 0 0 0 1 – 1 – 0 1 or ndf ( , , ) ( ) ( ) ( )y y y x x y y x x y x x y1 2 3 1 3 1 2 1 3 1 1 3 3� � � . )* Note that the undetermined values of function arguments need to be interpreted as both zeroes and ones, whereas the undetermined values of functions are very difficult, uninter- esting, or even impossible, to determine and their delivery is motivated by the maximal rate of their utility. If the system � �� j j n �1 is also given by the system � �cndf y j j n ( ) �1 , then it is to be decided whether to realise ROM by means of the cndf y j( ) array or the cndf y j( ) array. If, therefore, for the Hamming weight wH (yj) of the function �j – w yH j m( ) ! 2 2 holds, then naturally we work with use cndf y j( ) or otherwise we do with cndf y j( ) . Since cndf y j( ) or cndf y j( ) are very complicated systems in practice – the systems of (�j) functions are systems consisting of tens or hundreds of functions depending on tens or hun- dreds of arguments – the classic minimisation procedures are not applicable on cndf y j( ) or cndf y j( ) . With advantage, however, the Quine and McCluske method of minimising � �cndf y j j n ( ) �1 systems can be used, under the condition that the definition of the undetermined values of functions �j of system � �� j j n �1 will be suitably defined and the covering table [2] will be not constructed. In this way, we will obtain a subminimal group ndf y y yn( , , , )1 2 � – see Example 4. The so called ‘Harvard’ approach to systems� �� j j n �1 [3, 4] can be applied with advantage in designing logic arrays. Let us deal, without loss of generality, only on the system � �� �1 1 2 2 1 2( , , , ), ( , , , )x x x x x xm m� � and regard one of the functions as an argument of the other function and this, of course, affects the complexity of the conception logic array. For instance, let us write y y x x x x x xm m2 2 1 1 2 2 1 2� � � ( , , , , ) ( , , , )� �� � . Example 4: Let y1 00010111� and y2 00010110� , that is y x x x x x1 1 2 3 1 2� � �( ) and y x x x x x x x x2 1 2 3 1 2 3 2 3� � �( ) or also y y x x x2 1 1 2 3� since: Example 5: Let us consider the system� �� j j�1 3 from Exam- ple 3. Then, w yH ( )1 4� , w y w yH H( ) ( )2 3 2� � , i.e., y x x x x x x x x x x x x1 1 2 3 1 2 3 1 2 3 1 2 3� � � � , y x x x x x x2 1 2 3 1 2 3� � , y x x x x x x3 1 2 3 1 2 3� � , since 2 2 4 3 � , and so y x1 1� , y y x2 1 3� � , y y x3 1 3� � . Example 6: Let there be a static logic object by means of a product (input) matrix and a sum (output) matrix. Min � 1 2 3 4 5 6 7 8 9 10 11 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � x x x x x x x x x x1 1 2 2 3 3 4 4 5 5 Mout � 1 2 3 4 5 6 7 8 9 10 11 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � y y y y y y y1 2 3 4 5 6 7 Let the rows of the input (output) matrix be compatible if each of them contains at least one common input literal (one common output function). Since the relation of compatibility of rows is their relation of tolerance, on the set of rows of the matrix it defines the covering ��� � ��� �� �C i C ix i y imax max� �111 111 with all maximal classes: ��� � � �� � � �� � C i C x y max m , , , , , , , , , , , , , , � " # $ % & ' 1 2 4 5 7 8 3 6 9 10 3 10 11 5 7 10 ��� � � �� �� �� �� �� �� �ax , , , , , , , , , , , , , , , ,i � 2 3 5 8 10 4 5 8 10 3 9 10 11 5 7 6 9 Since the rows within the input (output) matrix correspond to the sets of input literals (output functions): 30 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 2/2005 Czech Technical University in Prague According to ��� � ��� �� �C i C ix ymax max we get to the cover- ing on the set of input variables (output functions) of all maxi- mum classes: � � � �� �� � � � C x x x x x x x C y x j j y k k max max , , , , , � � � � � � � � � 1 5 1 2 3 3 4 5 1 7 � � � �� � � ( ( (( (( " # $ % & ' � � � � � � y y y y y y y y y 1 2 3 1 3 4 5 6 7 , , , , , , , , i.e., we obviously obtain sparse matrices Min � 2 4 7 5 1 8 10 3 11 9 6 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � x x x x x x x x x x1 1 2 2 3 3 4 4 5 5 Mout � 2 4 7 5 1 8 10 3 11 9 6 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � y y y y y y y1 2 3 4 5 6 7 The matrices Min (Mout) are represented by submatrices Min1 2 4 7 5 1 8 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 � � � � � � � � � � � � � � � � � � � � � x x x x x x1 1 2 2 3 3 , Mout � � � � � � � � � � � � � � � � � � � � � ( 2 4 7 5 1 8 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 y y y1 2 3( ( � � � � � � � � � � �� � � � � � � � � � � �� Min2 � � � � � � � � � 10 3 11 9 6 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 � � � � � � � � x x x x x x3 3 4 4 5 5 where y y y1 1 1� ( � (( and y y y3 3 3� ( � (( which leads to saving the capacity of matrices Min1, Min2 (Mout1, Mout2) compared to the capacity of Min (Mout). 4 Structural model of a dynamic logic object Let us consider a trivial block diagram of canonic compo- sition of a dynamic logic object – like that in Fig. 3, where the substitute ) [5] is a parallel register consisting of “mem- ory ” modules Mk (Fig. 5.) modeled with finite automata � �� �0 1 0 1 2, , , , �k where �k are the transition functions � � � � � ��k k k k kq e e q: , , , : ,0 1 0 1 0 1 2 1 2� (� , where qk and (qk are the affiliate state and the substitute state, respectively. Let � �M M� or � � � �* � */ m m or , where M is a set and m its element (m M� ). The finite automaton model or the given binary dynamic object is to be an ordered sextuple � � � � � �0 1 0 1 0 1, , , , , , ,m p n � where the vector of transitional function � �� � � � � �� �� � � �0 1 0 1 0 1, , ,p p m and the output function are © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 31 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 2/2005 Rows Stimuli Responses 1 {x1, x2} {y2} 2 {x1} {y3} 3 {x4, x5} {y3, y4} 4 {x1} {y1} 5 {x1, x3} {y1, y2, y3} 6 {x5} {y5, y7} 7 {x1, x3} {y2} 8 {x1, x2} {y1, y3} 9 {x5} {y4, y5} 10 { x3, x4, x5} {y1, y3, y4} 11 {x4} {y4, y6} Fig. 3: “Memory” module Mk � �� � � � � �� �� �� �� � � �0 1 0 1 0 1, , ,n p m , respectively � � � � � � : , , , : : , 0 1 0 1 0 1 1 2 1 2 1 2 p m p p m pq q q x x x q q q � ( ( (� � � � � � � �� � � � � � � : , , , : : , , , , , 0 1 0 1 0 1 1 2 1 2 1 2 p m n p m nq q q x x x y y y � � � � � when � � � � : , , , , , , , , q q q x x x q e e q e e q p m p 1 2 1 2 1 1 11 21 2 2 12 22 � � � � �� � � � �p p pe e, ,1 2 having in mind that the vector exciting function E sought for � �� � � � � �� �E p p m � � � � � � � � 0 1 2 0 1 0 1 , , , � � � � � �E q q q x x x e e e e e p m p p m p : , , , : : , 0 1 0 1 0 1 1 2 1 2 11 21 12 22 1 � � � � � e p2 represented by the system � � 12 1k k p � of components driving functions � � � � � � 12 2 1 2 1 2 1 2 0 1 0 1 0 1k p m p m k kq q q x x x e e : , , , , � � � � � � found according to the function +, and � and is represented by the system� �� j j n �1 of the component input functions � � � �� � � � � � � j p m n p m jq q q x x x y : , , , : : , . 0 1 0 1 0 1 1 2 1 2 � � � � Let � �� �M M M Min out outext outint� , be the input (output, out- put external, output internal) matrix, (respectively) of the given dynamic object, i.e., � � � � � � � �M K m p r s t x q in for : , , , , , , , , , , : , , , 1 2 1 2 2 1 2 2 0 1 0 � � � � � � s s� t ij t ij K r s t x q K � � � t s t s � � , , , ,� 1 for � � � � � � � �M K n n r s K ij out ext for : , , , , , , , , , , : , 1 2 1 2 2 1 2 2 0 1 0 � � � � � �ndf r s K ndf j ij j ( ), , ( ) � �� 1 for � � � � � � �M K p r t K ndf Eij k out int for : , , , , , , , : , ( ) 1 2 1 2 2 0 1 0 12 � � � � � , , ( ) .r t K ndf Eij k� 1 12for � If in addition, � �QT tp Q t q: , , , :1 2 2� for t k� �2 1, t qt� for t k k p� � �2 0 1 2 1( , , , , )� for the logic array M of the given dynamic object there holds � �y y y M X Q Mn T 1 2, , , & & &� � � � � � � � � � � � � � �in out ext, � �y y y M X Q Mn T 1 2, , , & & &� � � � � � � � � � � � � � �in out ext, � �e e e e e e M X Qp p T 11 21 12 22 1 2, , , , , , & & &� � � � � � � � � � � � � � �in Mout int , � �e e e e e e M X Qp p T 11 21 12 22 1 2, , , , , , & & &� � � � � � � � � � � � � � �in Mout int , where � �X x x x x x xm m T � 1 1 2 2, , , , , ,� and � �Q q q q q q qp p T � 1 1 2 2, , , , , ,� . It can be recommended to use reduced exciting matrices of “memory” modules [2, 5], i.e., a matrix with actual state transitions only (except for the delay element and D flip-flop circuit): 32 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 2/2005 Czech Technical University in Prague Fig. 4: Block diagram of canonical composition on logic array qk (qk Dk 0 0 1 1 0 1 0 1 0 1 0 1 � � � � � � � � � � � � Rk Sk Dk Lk Jk K k Tk 1 0 � � � 1 1 � � � 1 0 � � � 1 1 � � � 1 0 � � � 1 1 � � � 1 1 � � � � � � The total capacity (area) C(M) (bit) of the logic array M is expressed as � �C M C M C M C M m p n p K( ) ( ) ( ) ( ) ( ) .� � � � � � �in out ext out int 2 2 Example 7: Design a PLA by means of an operating table (Table 1a) and use a synchronous flip-flop RS as a binary substitutor. It seems suitable to modify the operating table and add the excitation RS flip-flop (Table 1b). According to Table 1b) we obtain y q q x q q x q q x� � �1 2 1 2 1 2 as well as R q q1 1 2� R q q x2 1 2� S q q x1 1 2� S q q x q q x2 1 2 1 2� � Hence Min � � � � � � � � � � � � � � � � � 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 x x q q q q q q x q q x q q x q q x q q 1 1 2 2 1 2 1 2 1 2 1 2 1 2 M y out ext � � � � � � � � � � � � � � � � � 1 1 0 1 0 M R S R out int � � � � � � � � � � � � � � � � � 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 2 S2 Determine the capacity PLA: C M( ) ( )� � � �6 1 4 5 55 bits. Since the number of logical array input ports is usually markedly higher than the number of rows of input as well as exciting columns, the area of the input matrix Min is unneces- sarily large. Replace, therefore, the input variables by suitable substitutes. Example 8: Given a synchronous logic object (Table 2a) by an operating table (Table 2b), create a table with a minimal num- ber of columns denoted by substitution variables si( , , )i �1 2 3 – Table 2c [6]. Hence � � � �s a p p d p pi � � � �( ) ( ) ( ) ( )1 2 3 5 , � �s c p p e p b p2 4 6 1 2� � � �( ) ( ) ( ) ( ), s c3 � , where �� � �p q qq: , :� 1 6 0 1 0� if the object is not in the state q, in the opposite case q 1. “Substitution” variables define on the alphabet state��q q�1 6 partition {{1, 2}, {3, 5}, {4, 6}} (the permutations of row elements of Table 2c can also helpful). If Miller’s state coding [7] transferred on synchronous logic objects [2] is used, and if the elementary substitute will be D flip-flop, we obtain w( )1 0� for the state. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 33 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 2/2005 a) ( (q q y1 2 q1q2 x 0 1 0 0 01/1 00/0 0 1 01/1 10/0 1 0 00/0 01/1 b) q1 q2 x ( (q q1 2 y Rk, Sk 0 0 0 0 1 1 S2 1 0 0 0 – 0 1 0 0 1 1 – 1 1 0 0 S1, R2 1 0 0 0 0 0 R1 1 0 1 1 R1, S2 Table 1: a) the operating table, b) the modified operating table from Example 7 a) q x y (q 1 a � 2 c � 5 e 6 2 a � 2 b � 4 d � – 3 b � – d � 5 4 c 3 5 a � – d � 4 6 c 5 e � – Table 2: a) flow table, b) operating table, c) table of substitution variables from Example 8 34 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 2/2005 Czech Technical University in Prague b) q1 q2 q3 s y1 y2 (q1 (q2 (q3 Dk 1 0 1 s1 0 0 0 0 1 D3 c 0 0 0 0 0 � s2 1 0 0 1 1 D2, D3 0 0 1 s1 0 0 0 0 1 D3 s2 1 1 0 1 0 D2 � 0 1 � � 1 0 0 � 0 1 � � s1 0 0 0 0 � 0 0 1 0 1 0 1 0 D1 s2 0 0 0 0 � 0 0 � � s1 0 0 0 1 0 D2 0 1 1 1 0 0 0 0 � s2 0 1 � � � c) q s1 s2 s3 1 a e c 2 a b – 3 d – – 4 – c – 5 d – – 6 – c – Weights w( )1 0� , w w( ) ( )3 6 1� � , w w( ) ( )2 4 2� � , w ( )5 3� w q q( ) ( )� (� , where � ( )(q is the characteristic function of the set� �( (q q� ( ) of the state binary code �� � �i i� 1 6 30 1 5 000 3 100 6 011 4 010 2 001 1 101 , : , , , , , , � � � � � � which is a reasonable compromise: Note, in addition, that the states of one and the same class {1, 2}, {3, 5}, {4, 6} of the partition {{1, 2}, {3, 5}, {4, 6}} is to be coded also with respect to the neighbouring coding, where a heuristic procedure lead to the reduction number of rows of the array matrices, i.e.: s q q q q q q a q q q q q q d q q a q q d 1 1 2 3 1 2 3 2 2 3 1 2 3 2 3 2 3 � � � � � � � ( ) ( ) , s c3 � , s q q q q q q c q q q e q q q b q q c q q q e 2 1 2 3 1 2 3 1 2 3 1 2 3 2 3 1 2 3 � � � � � � � ( ) � q q q b1 2 3 . Let the input binary code be � � � �a b c d a b c d e , , , , : , , , , 0 1 000 001 010 011 100 3 � � � � � i.e.: s x x x q q x x x q q s x x x q q x x x q q q 1 1 2 3 2 3 1 2 3 2 3 2 1 2 3 2 3 1 2 3 1 2 � � � � , 3 1 2 3 1 2 3� x x x q q q ; q3 q2 q1 5 4 6 2 3 � � 1 � �hence s s1 2 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 , � 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 1 2 2 3 3 � � � � � � � � � � � � � � � � x x x x x x q1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 q q q q q x x x x x x q q q q q q & & � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � T s & 1 0 1 0 0 1 0 1 0 1 1 s x x x q q x x x q q x x x q q q x x x q q q 2 1 2 3 2 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 1 2 � � � � �� �3 . Example 9: Given an asynchronous logic object (Table 3a) by an operating table (Table 3b), create a table with a minimal number of columns denoted by “substitute” variable ,i (i �1, 2, 3) – (Table 3c). Since � �1 2� �a b, and � 3 � c, let us discuss just the parallel coding of states �� � �q q� 1 6 50 1, according to Liu [2]. In the case of single stimuli a, b, c, the noncritical pairs of state transitions on the state alphabet��q q�1 6 define � � �� �� �1 2 3 4 5 6, , , , , , � � �� �� �� �1 4 2 3 5 6, , , , , , � � �� �� �� �1 2 3 4 5 6, , , , , . Hence for the separation state components [2] we obtain a state code (Table 3d), again with an obvious effort to achive the least possible number (Table 3e) of state components q ( , , )j �1 2 3 and the least possible w DH j( ) exciting weight Dj. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 35 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 2/2005 Let us code the responses according to Miller again. This can also be used with advantage in coding reactions of asynchron- ous objects: � � � �� � � � � � , , , , : : , , , , 0 1 00 01 10 11 2 � � � � since the response weights are w ( )� � 5, w ( )� � 4, w ( ) � 3 and w ( )� �1. For excitation and reactions we can write: D q q q s1 1 2 3 2� D q q q q q q s q q q s q q s q q q s2 1 2 3 1 2 3 2 1 2 3 1 2 3 2 1 2 3 1� � � � �( ) D q q q s q q q s q q q s q q s q q q s3 1 2 3 1 1 2 3 2 1 2 3 1 2 3 1 1 2 3 2� � � � � y q q q q q q q q q q q q s q q q q s1 1 2 3 1 2 3 1 2 3 1 2 3 2 1 2 2 3 2� � � � � �( ) ( ) y q q q s q q q q q q q q q s q q q s q q2 1 2 3 1 1 2 3 1 2 3 1 2 3 2 1 2 3 1 1� � � � � �( ) ( 3 1 2 3 2� q q q s) . Hence � �y y D D D1 2 1 2 3 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 1 , , , , � 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � q q1 2 2 3 3 1 1 2 2 1 1 2 2 3 3 1 1 2 2 q q q q s s s s q q q q q q s s s s & & � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � T & 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 2 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � y y D D D2 3 � �Hence � � �, , , � � � � � � � � � 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0� � � � � � � � � � � � � � � � � � � � � � � � x x x x x x x x x x x x 1 1 2 2 3 3 1 1 2 2 3 3 & & � � � � � � � � � � � � � � � � � � � � � � � � � � T & 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 � � � � � � � � � � � � � � � � � � � �� 36 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 45 No. 2/2005 Czech Technical University in Prague a) q x (q 1 a 1 b 4 c 2 2 a 1 b 3 c 2 3 a 1 b 3 c 3 4 a 4 b 4 c 3 5 a 4 b 6 c 5 b) q q q1 2 3 x x1 2 ( ( (q q q1 2 3 Dk 0 0 0 0 0 0 0 0 – 0 1 0 0 1 D5 1 0 0 1 0 D3 0 1 0 0 0 0 0 0 – 0 1 0 1 1 D3, D5 1 0 0 1 0 D3 0 1 1 0 0 0 0 0 – 0 1 0 1 1 D3, D5 1 0 0 1 1 D3, D5 0 0 1 0 0 0 0 1 D5 0 1 0 0 1 D5 1 0 0 1 1 D3, D5 1 0 0 0 0 0 0 1 D5 0 1 1 1 0 D1, D3 1 0 1 0 0 D1 Table 3: a) transition table, b) operating table, c) table of input “substitute” variables, d) state code table, e) state code table with a mini- mum state code words from Example 9 � �D D D1 2 3 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 , , � 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � q q q q q q q q q q q q 1 1 2 2 3 3 1 1 2 2 3 3 � � � � � � � � � � � � � � � & & � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � & 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � D D D1 2 3 c) q �1 �2 �3 1 a b c 2 a b c 3 a b c 4 a b c 5 a b c 6 a b c d) x a b c q q1 q2 q3 q4 q5 1 0 0 0 0 0 2 0 0 1 0 0 3 0 0 1 0 1 4 0 0 0 0 1 5 1 1 – 1 – 6 1 1 – 1 – e) q q1 q2 q3 1 0 0 0 2 0 1 0 3 0 1 1 4 0 0 1 5 1 0 0 6 1 1 0 5 Conclusions In [8], we find exact, theoretically demanding and quite elaborate optimization algorithms both according to state coding (Miller’s economic coding and Liu’s parallel coding) and by the number rows of matrices of the matrix structural model of the dynamic logic object. If the number of states of the dynamic object is large, it is suitable to apply a simple block decomposition [2, 9] and design the structural model of the matrix as a composition of matrix structural models of individual blocks. References [1] Liebig, H., Thome, S.: Logischer Entwurf digitaler Systeme. Berlin -…- Tokio: Springer, 1996. [2] Bokr, J., Jáneš, V.: Logické systémy. Praha: Vydavatelství ČVUT, 1999. [3] Pospelov, D. A.: Logičeskie metody analiza schem. Moskva: Energija, 1974. [4] Šalyto, A. A.: Logičeskoe upravlenie. Metody apparatnoj i pro- grammnoj realizaciji algoritmov. Sankt Peterburg, 2000. [5] Bokr, J.: Kánonická dekompozice. Acta Elektrotechnica et Informatica, Vol. 4 (2004), No. 1, p. 60–65. [6] Baranov, S. I., Sinev, V. N.: Avtomaty i programmiruemye matricy. Minsk: Vyšejšaja škola, 1980. [7] Miller, R. E.: “Switching Theory”. Sequential Circuits and Machines, Vol. II. (Translated into Russian), Moskva: Nauka, 1971. [8] Ačasova, S. M.: Algoritmy sinteza avtomatov na program- mirujemych matricach. Moskva: Radio i svjaz, 1987. [9] Bokr, J.: “Prostá bloková dekompozice”. Slaboproudý ob- zor, sv. 52 (1991), č. 3–4, p. 80–83. 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. phone: +420 224 357 289 e-mail: janes@fel.cvut.cz Department of Computer Science and Engineering Czech Technical University in Prague Faculty of Electrical Engineering Karlovo nám.13 121 35 Praha 2, Czech Republic © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 37 Czech Technical University in Prague Acta Polytechnica Vol. 45 No. 2/2005