### Paper Menu >>

### Journal Menu >>

Circuits and Systems, 2013, 4, 466-471 Published Online November 2013 (http://www.scirp.org/journal/cs) http://dx.doi.org/10.4236/cs.2013.47061 Open Access CS Two Analytical Methods for Detection and Elimination of the Static Hazard in Combinational Logic Circuits Mihai Grigore Timis, Alexandru Valachi, Alexandru Barleanu, Andrei Stan Automatic Control and Computer Engineering Faculty, Technical University Gh.Asachi, Iasi, Romania Email: mtimis@tuiasi.ro, avalachi@tuiasi.ro, abarleanu@tuiasi.ro, andreis@tuiasi.ro Received August 18, 2013; revised September 18, 2013; accepted September 26, 2013 Copyright © 2013 Mihai Grigore Timis et al. This is an open access article distributed under the Creative Commons Attribution Li- cense, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT In this paper, the authors continue the researches described in [1], that cons ists in a comparative study o f two methods to eliminate the static hazard from logical functions, by using the form of Product of Sums (POS), static hazard “0”. In the first method, it used the consensus theorem to determine the cover term that is equal with the product of the two residual implicants, and in the second method it resolved a Boolean equation system. The authors observed that in the second method the digital hazard can be earlier detected. If the Boolean equation system is incompatible (doesn’t have solutions), the considered logical function doesn’t have the static 1 hazard regarding the coupled variable. Using the lo- gical computations, this method permits to determine the needed transitions to eliminate the digital hazard. Keywords: Combinational Circuits; Static Hazard; Logic Design; Boolean Functions 1. Introduction Under certain conditions, on the output of the logical signals may occur unwanted transitions. These transition s are known as glitches. The logic glitch is a kind of un- wanted noise presenting inthe output signal that can ini- tiate an uncontrollable process. In the next level there is an input signal [2]. We can distinguish three types of noise that is intro- duced in CLC (Combinational Logic Circuits), called ha- zards (Static, Dynamic and Function Hazards). In the following we consider only the stat ic hazard pro- blem in combinational logic systems, called static hazard “0”. Static 1 hazard, also called SOP (Sum of Products) hazard—a glitch that occurs in otherwise steady-state 1 output signal from SOP logic; Static 0 hazard, also called POS (Product of Sums) hazard—a glitch that occurs in otherwise steady-state 0 output signal from POS logic. Static Hazards in Two-Level Combinational Logic Circuits (Consensus Method [2]). We will initially define: Coupled variable; a variable input is complemented within a term of function and un complemented in an- other term of the same function. Coupled term; one of two terms containing only one coupled variable. Residue; the part of a coupled term that remains after removing the coupled variable. Hazard cover (or consensus term). The RPI (Redundant Prime Implicant) required to eli- minate the static hazards: AND the residues of coupled p-term to ob tain the SOP hazard cover, OR the residues of coupled s-term to obtain the POS hazard cover. POS example: any logic function can be described as: 01ii yexex where 01211 11211 ,,,,0,,, ,,,,1,,, nni i nni i eyxxx xx eyxxx xx 0 0 (1) Sometimes, the same function can be describes as: ii yaxbxc (2) Using the (1) form, we can say: 0 1 eac ebc (2.1) M. G. TIMIS ET AL. 467 Using the algorithm described in [3], if , the expression from (2), (2.1) doesn’t present static hazard in relation with the cab i x input, and if a = b = 0, then results c = 0. The condition to have static hazard in relation with the i x input, is when a = b = 0 and c = 1. The consensus method [4] consists of determination of coupled terms, then by removing the coupled variables we obtain residual values. That meaning the (2) equation can be written like: ii yaxbxcab (3) It can be observed that the expression of the function is multiplied by the sum of residual values, the new expres- sion presents static hazard in relation with the i x input. We proposed as example the 4 inputs logic function: 43210 0 ,,,, 1,3,6,7,9,11,14,17,19,20,25,27,28 0,5,10,16,2 3,2 4,29,31 yyxxxxx R R (4) Using the Quine-McCluskey minimization method we obtain the equation from (5) and also the residual values determined by 0 x input: 432141020 4210 yxxxxxxxxx xxxx 414210 2 242410412124 axxxxxx bx abxxxxxxxxxxxxx 1 (5) The expression of no static hazard in relation with 0 x input: 432141020 42 10421 yxxxxxxxxx xx xxxxx (6) 2. Method of Resolving of Boolean Equations [5] In this paragraph we apply the consensus method [5] and the method of solving some specific Boolean equations. If ii yaxbx c, by resolving the next system equations it can be determined the vectors input values which presents static hazard. 0 0 1 a b c (7) If the (7) system has no solution, the function doesn’t presents static hazard in relation with i x . Therefore, the expression of the function becomes: 414210 2 4321 0 0 1 axxxxxx bx cx x x x (8) Therefore, 20x imposes the reduction of the sys- tem to: 41 0xx or 41 1xx So, the solution is: 4 3 2 1 1 0 0 x x x x (8.1) So, the function will hav e hazard at commutation 43210 100001000116 17 110 00110 012425 xxxxx So, in the POS relation will be added the multiplied prime implicant 42 x 1 xx. The function will have the same expression like in (7). 3. Static Hazards in Two-Level Combinational Logic Circuits We will consider two analytical methods to detect and eliminate this type of hazard: (A) Consensus method [1] We will initially define: Coupled variable; a variable input is complemented within a term of function and un complemented in an- other term of the same function. Coupled term; one of two terms containing only one coupled variable. Residue; the part of a coupled term that remains after removing the coupled variable. Hazard cover (or consensus term). The RPI (Redundant Prime Implicant) required to eliminate the static hazards: AND the residues of coupled p-term to obtain the SOP hazard cove r, OR the residues of coupled s-term to obtain the POS hazard cover. Example 1. Lets consider the logic function 2101 2,3,5,7fxxx R. a) SOP example: will be determined the prime impli- cants using Veitch-Karnaugh or Quine-McCluskey me- thods, as: 21 10 20 2,3 3,7 5,7 Axx Bxx Cxx (9) One of the minimal equations is: Open Access CS M. G. TIMIS ET AL. 468 21 20 y AC xxxx (10) where we have : coupled variable: 2 x coupled terms: 2120 , x xx x residues: , 10 x x consensus term: 10 x x Therefore, the logic expression that has no static haz- ard in relation to 2 x variable is: 21 2010 y xx xxxx (11) b) POS example: will be determined the prime impli- cants using Veitch-Karnaugh or Quine-Mc Cluskey me- thods, as: 21 10 20 0, 1 0,4 4,6 ax x bxx cx x (12) One of the minimal equations is: 21 20 10 yxxxx xx (13) where we have : coupled variable: 2 x coupled terms: 202 ,1 x xx x residues: , 10 x x consensus term: 10 x x The equation (13) shows no static 0 hazard. Example 2. Let’s consider the function of four varia- bles . 3210 10,1,2,5,6,7,8,9,10,14yfxxxxR SOP hazard: will be determined the prime implicants using Quine-McCluskey method, as: 310 310 320 321 310 21 20 10 1, 5 2,6 5,7 6,7 10,14 0, 1,8,9 0,2,8, 10 2,6, 10,1 4 Axxx Bxxx Cxxx Dxxx Exxx Fxx Gxx Hxx (14) Applying the Patrick method [6], going from prime implicants table will be determined all SOP solutions . Let’s consider the logical variables attached to the prime implicants as follows: 0, if 0, the A prime implicant is present in the logical function expres- sion, otherwise 0 (A prime implicant is not pre- sent in the logical function expression), etc. i ppA1p 0p Therefore, considering the correspondence 1 pB , ,3,4, 5, 62 pCpDpEpFpG , , in the table illustrated in Table 1 is shown the 7 pH Table 1. The SOP coverage table. dec. equiv.0 125 6 7 8 9 1014 pi p0 11 p1 1 1 p2 1 1 p3 1 1 p4 1 1 p5 11 1 1 p6 11 1 1 p7 1 1 1 1 Patrick coverage: It writes the coverage equation: 5605167 02 13723 565467 47 1 pp pp ppp pp ppp pp pppppp pp (15) Simplifications are made by using the laws of Boolean algebra: the redundance law, the iden tity law and the dis- tributive law. 5167 137 47 20 23 5713674 203 5714346 203 57 145 3456 203 1 or 1 or 1 or 1 pppp ppp pp pp pp ppppp pp ppp ppppppp ppp ppppp pppp ppp (16) A version of the optimal solution corresponds to 572 ppp triplet, i.e. 3210 21 10320 ,,,yfxxxx FHC xx xxxxx (17) The cost of this function in SOP implementation is: 2110320 310CyCx xCxxCxx x (It was considered the variables , ii x x, available at input). It can verify that any other coverage has a higher cost. For example, the coverage which cor- responds to 5703 pp p p 21 10310321 yFHAD x xxxxxxxxx (18) Open Access CS M. G. TIMIS ET AL. 469 has the cost . 114Cy 4. The Static Hazard Elimination (B) The consensus method We apply the same method as in [7], only that it has a strong computing nature. Any logic function can be written as: 01ii y ex ex (11), where 01211 ,,,,0,,, nni i eyxxx xx 0 0 , 11211 ,,,,1,,, nni i eyxxx xx . Obviously, if ii y ax bx c ebcee (12), then , . 0 eac1 If we add the term to relation (11), the function presents no hazard towards 01 i x . In terms of the consensus method, the term that covers the static 1 hazard is 01 eeac bccab (19), therefore for the form (11) will be , and for the form (12), . 01 ee ab Considering the second example, we will have: hazard in relation to the input 0 x : 21 10320 y FHCxxxxxxx (20), where 012112 132213221 01123 221 321 21 , , exxxxx exxxxxxxx eex xxxxx x xx xxFD (21) By adding F D term to relation (14), it obtains: 2110 320 321 yFHC FD x xxxxxxxxx (22) hazard in relation to the input 1 x : 02320230 10 32 320032 0123003220 exxxxxxx e x xx xxxx xx eex xxxxxxxG (23) Therefore, the expression of the function becomes: 21 10320 32120 yFHCDG x xxxxxx xxx xx (24) hazard in relation to the input 2 x : 010101 1303110 exxxxxx exxxxxx 0 Therefore, 01103 0311 0 310310 10 10 310 eex xxxxx xx xxxxxx xx xxxxxH A (25) The expression of the function becomes: 21 10320 321 20 310 320321 10 yFHCDGA xx xxxxx x xx xxxxx x xxxxxxx t (26) hazard in relation to the input 3 x : 0202110 exxxxxxt , where 21 1020310 txxxxxxxxx 1 et 012 02110 eexxxxxxtt t (27) so that remains the same expression (20), which has no hazards in relation to 3 x . From the relation (20), it sees that the expression of the function without SOP hazards contains all prime im- plicants without B and E. (C) The method of solving of some Boolean equations [8] A logic function can be written as: ii y ax bx c (28) where 12110 121 10 ,,,,0,,, ,,,,1,,,. nni i nni i ac fxxxxx bc fxxxxx , According to a theorem from [8], a logic function ex- pressed as SOP, presents a static hazard in the situation 1 ii xx , a situation deducted by solving the following system of logical equations: 1 1 0 a b c (29) We return to the same function, (14): 21 10320 y FHCxx xxxxx . hazard in relation to the input 0 x : 10 32021 y xx xxxxx (30) Open Access CS M. G. TIMIS ET AL. 470 The function will present SOP hazard, if 1 32 21 1 1 0 x xx xx (31) Therefore, 3, , , which imposes a hazard at commutation 0x21x11x 3210 0110 0111, x xxx which imposes the adding of the prime implicant to function. 6,7D The function becomes 2110 320 321 yFHCD x xxxxxxxxx (32) hazard in relation to the input 1 x : 2 2 032 0 320 3 1 0 1 or 0 0 ax x bx xx x cxxx x (33) Therefore, we will have hazards in the following cases: 3210 00000010 0,2 1000 10108,10 xxxx The previous commutations are equivalent to the implicant . 0,2,8, 10G The function becomes 21 10320 321 20 yFHCDG x xxxxxx xxx xx (34) hazard in relation to the input 2 x : 10 3 30 31 100 1 1 0 1 and 0,1 axx x bxxxx cxxxx (35) We will have the solution: 3 1 0 0 0 1 x x x (35.1) The corresponding commutation is: 3210 00010101 1,5 xxxx . Therefore, the term is added to the func- tion. 1, 5A And therefore: y FHCDGA (36) hazard in relation to the input 3 x : 21 10320 32120 310 yxxxx xxx x xx xxxxx (37) 202110 21 1020 1 0 0 axx xxxx b cxxxx xx (38) Because one of the terms is zero, we have no hazards in relation to that variable. ,ab 5. Conclusions The contribution of the authors consists in that by analysis of two methods of detection/elimination of the static hazard, insisting of the POS method for the logic function which wasn’t analyzed in [1]. The boolean equation [2,3], presents some advantages instead the consensus methods, the most important to determine the transactions which causes static hazard. It concludes that the classical method of the 70s, the method of solving some specific Boolean equations [4], presents some advantages compared to consensus method [5], which has a strong heuristic nature. In the first method it used the consensus theorem to determine the cover term that is equal with the product of the two residual implicants [6], and in the second method it resolved a Boolean equation system [7]. The authors observed that in the second method the digital hazard can be earlier detected. If the Boolean equation system is incompatible (doesn’t have solutions), the considered lo- gical function doesn’t have the static 1 hazard regarding the coupled variable. Using the logical comp utations , this method permits to determine the needed transitions to eliminate the digital hazard. From the both methods, we can observe that static 1 hazard can be removed by adding the prime implicants step by step. The same method with the same conclusions was ap- plied to the static 0 hazard (POS), using the duality theo- rem [8,9]. The authors observed that in the second method the digital hazard can be earlier detected. If the Boolean equa- tion system is incompatible (doesn’t have solutions), the considered logical function doesn’t have the static 1 haz- ard regarding the coupled variable. Using the logical com- Open Access CS M. G. TIMIS ET AL. Open Access CS 471 putations, this method permits to determine the needed transitions to eliminate the digital hazard. REFERENCES [1] “The Comparative Study of Two Analytical Methods for Detection and Elimination of the Static Hazard in Com- binational Logic Circuits,” 2011 15th International Con- ference on System Theory, Control and Computing (ICSTCC), Sinaia, 14-16 Octomber 2011, pp. 1-4. [2] R. F. Tinder, “Engineering Digital Design,” Academic Press, Waltham, 2010. [3] Ch. Roth, “Fundamentals of Logic Design,” West Publi- shing Company, Eagan, 1999. [4] J. P. Perrin, M. Denouette and E. Daclin, “Systems Lo- giques,” Tome 1 Dunord, Paris, 1997. [5] E. T. Ringkjob, “A Method for Detection and Elimination of Static Hazards in Factored Combinational Switching Circuits,” Syracuse University, New York, 2013. [6] J. A. McCormick, “Detection and Elimination of Static Hazards in Multilevel XOR-SOP/EQV-POS Functions,” Washington State University, Pullman, 2013. [7] K. Raj, “Digital Systems Principles and Design,” Pearson Education India, Upper Saddle River, 2013. [8] Al. Valachi, R. Silion, V. Onofrei and Fl. Hoza, “Analy- sis, Synthesis and Verificati on of Digital Logic Systems,” Ed. Nord-Est, Iasi, 1993. [9] O. Ursaru and C. Aghion, “Multilevel Inverters with Im- bricated Switching Cells, PWM and DPWM-Controlled,” Electronics and Electrical Engineering, Kaunas, 2010. |