Bài giảng Digital Electronics - Bài 2 - Pham Ngoc Nam

Course contents Digital design Combinatorial circuits: without status Sequential circuits: with status FSMD design: hardwired processors Language based HW design: VHDL 1 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 2 Design of Combinatorial Circuits Minimization of Boolean functions Karnaugh map Minimization with the Karnaugh map Don’t care conditions Quine-McCluskey Technology mapping Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 3 Design of Combinatorial Circuits Minimization of Boolean functions Karnaugh map Minimization with the Karnaugh map Don’t care conditions Quine-McCluskey Technology mapping Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 4 Karnaugh map Motivation: Assume: F=xy’z+xy’z’ Cost =  (fan-in) complete circuit = (2)+(3)+(3)+(2) = 10 Delay Assume: relative gate delay NAND or NOR or NOT = 0.6 + fan-in * 0.4 Delay =  (gate-delay) critical path = 1 + (1.8+1) + (1.4+1) = 6.2 x y z F=xy’z+xy’z’ 5 Karnaugh map Motivation: F =xy’z+xy’z’ =xy’(z+z’) =xy’ The value of z hence does not matter Cost =  (fan-in) complete circuit = (1+2) = 3 i.o. 10 Delay Assume: relative gate delay NAND or NOR or NOT = 0.6 + fan-in * 0.4 Delay =  (gate-delay) critical path = 1 + (1.4+1) = 3.4 i.o. 6.2 x y z F 6 Karnaugh map Minimization via manipulation of Boolean expressions is clumsy: no method exists to select the theorems such that we are sure to obtain the minimum cost Is it possible to see in the truth table which input value does not matter? We indeed see easily that the value of F equals 1 for x=1 and y=0 irrespective of the value of z We however see this easily only for z, since only for z the lines z=0 and z=1 for equal x and y are consecutive 7 Karnaugh map A Karnaugh map contains the same information as a truth table (each square is a minterm), but neighboring squares differ only in the value of 1 variable!! x’ x x 0 1 x’y’ x’y xy’ xy x 0 1 y 0 1 x’y’z’ x’y’z xy’z’ xy’z x 0 1 yz 00 01 x’yz x’yz’ xyz xyz’ 11 10 x y z x’z (y does not matter) x’y’z x’yz xy’z’ xyz’ xz’ (y does not matter) xy’z’ xy’z xy’ (z does not matter) 8 Karnaugh map m 0 m 1 x 0 1 m 0 m 1 m 2 m 3 x 0 1 y 0 1 0 1 4 5 x 0 1 yz 00 01 3 2 7 6 11 10 x y z 9 Karnaugh map 0 1 4 5 xy 00 01 zw 00 01 3 2 7 6 11 10 x z w 12 13 8 9 15 14 11 10 11 10 y 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 Fill out from truth table 10 Karnaugh map 1 0 0 1 xy 00 01 zw 00 01 0 0 1 0 11 10 x z w 0 1 1 0 1 0 0 1 11 10 y Minimize F=x’y’z’w’+x’yz’w+x’yzw+xy’z’w’+xy’zw’+xyz’w+xyzw F= yw + xy’w’ + y’z’w’ 11 Karnaugh map Implement F=x’y’z’w’+x’yz’w+x’yzw+xy’z’w’+xy’zw’+xyz’w+xyzw x y z w F Cost = 4*(1) + 7*(4) + 1*(7) = 39 Delay = 1 + (2.2+1) + (3.4+1) = 8.6 12 Karnaugh map Implement F=yw+xy’w’+y’z’w’ x y z w Cost = 3*(1) + {1*(2)+2*(3)} + 1*(3) = 14 i.p.v. 39 Delay = 1 + (1.8+1) + (1.8+1) = 6.6 i.p.v. 8.6 F 13 Karnaugh map 0 xy 00 01 zw 00 01 11 10 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 18 19 17 16 22 23 21 20 30 31 29 28 26 27 25 24 xy 11 10 10 11 01 00 00 01 11 10 x y z w x z w v y Differs from course book F(v,x,y,z,w) 14 Karnaugh map 0 xy 00 01 zw 00 01 11 10 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 18 19 17 16 22 23 21 20 30 31 29 28 26 27 25 24 xy 11 10 10 11 01 00 00 01 11 10 x y z w x z w v y 40 41 43 42 44 45 47 46 36 37 39 38 32 33 35 34 58 59 57 56 62 63 61 60 54 55 53 52 50 51 49 48 10 11 01 00 x y 10 11 01 00 x y u F=(u,v,x,y,z,w) Differs from course book 15 Design of Combinatorial Circuits Minimization of Boolean functions Karnaugh map Minimization with the Karnaugh map Don’t care conditions Quine-McCluskey Technology mapping Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 16 Minimization with the Karnaugh map Determine all prime implicants Determine all essential prime implicants Search for minimal coverage Create the Karnaugh map Truth table or canonical form 17 Minimization with the Karnaugh map Step 1: Create Karnaugh map w x y z 1 1 F=x’y’z’+wz+xyz+w’y F= x’y’z’ +wz+xyz+w’y F=x’y’z’+ wz +xyz+w’y 1 1 1 1 1 1 F=x’y’z’+wz+ xyz +w’y 1 1 1 1 1 1 F=x’y’z’+wz+xyz+ w’y 1 1 1 1 1 1 Rule: - Take product term per product term and indicate where in the Karnaugh map it equals 1 18 Minimization with the Karnaugh map Step 2: Determine all prime implicants 1 1 1 1 1 1 1 1 1 1 w x y z 1 1 w’x’z’ x’y’z’ 1 1 w’y yz 1 1 1 1 1 1 1 1 wz 1 1 1 1 wx’y’ 1 1 1 1 Rule: - Analyze each 1-minterm - Determine the largest sub-cube(s) that contain(s) the minterm and add them to the list of prime implicants (without adding an already listed sub-cube ) 19 Minimization with the Karnaugh map Step 3: Determine all essential prime implicants 1 1 1 1 1 1 1 1 1 1 w x y z w’x’z’ x’y’z’ w’y yz wz wx’y’ 1 1 wz w’y Rule: - Search for 1-minterms that are only contained in 1 prime implicant - Indicate this prime implicant as essential 20 Minimization with the Karnaugh map Step 4: Search minimal coverage w’x’z’ x’y’z’ w’y yz wz wx’y’ 1 1 1 1 1 1 1 1 1 1 w x y z 1 1 1 1 1 1 1 1 1 2 0 1 1 1 x’y’z’ F min =x’y’z’+w’y+wz Rule: - Goal: search for the smallest set of (as big as possible) prime implicants that contain all 1-minterms - Take all essential prime implicants as initial list - Repeatedly add a prime implicant to the list that contains the largest number of not yet covered 1-minterms. When there are two that contain the same number of not yet covered 1-minterms, make a random choice. - Such a strategy is known as Greedy strategy : at each decision point, take the best choice without looking to future implications - This does not always lead to a global optimum 21 Minimization with the Karnaugh map Original:F=x’y’z’+w’y+xyz+wz MinimalF min =x’y’z’+w’y+wz wxyz wxyz Cost=4*1+2*3+2*2+1*4=18 Cost =4*1+1*3+2*2+1*3=14 =22% cheaper Delay =(1)+(.6+3*.4+1) +(.6+4*.4+1)=7 Delay =(1)+(.6+3*.4+1) +(.6+3*.4+1)=6.6 =6% faster 22 Minimization with the Karnaugh map Example 2: F(v,w,x,y,z) 23 Minimization with the Karnaugh map Realisation as sum of 1-minterms: F=  (6,7,10,11,14,15,21,23,25,27,29,31) v w x y z Cost=(5*1)+(12*(5+1))+(1*(12+1))=90 Delay=(.6+1*.4)+(.6+5*.4+1)+(.6+12*.4+1)=11 24 Minimization with the Karnaugh map MinimisationStep 1: Create Karnaugh map 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 w x y z z v 25 Minimization with the Karnaugh map MinimisationStep 2: determine all prime implicants 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 w x y z z v 26 1 1 1 1 1 1 1 1 Minimization with the Karnaugh map MinimisationStep 3: Determine all essential prime implicants 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 w x y z z v 1 1 1 1 F 1min2 =v’xy+v’wy+vxz+vwz Is already the minimum coverage 27 Minimization with the Karnaugh map Realisation of F 1min2 =v’xy+v’wy+vxz+vwz v w x y z Cost=1+(4*(3+1))+(1*(4+1))=22 (76% cheaper) Delay=(.6+1*.4)+(.6+3*.4+1)+(.6+4*.4+1)=7 (34% faster) 28 Minimization with the Karnaugh map Realisation in more than two layers F =v’xy+v’wy+vxz+vwz =v’y(x+w)+vz(x+w) =(x+w)(v’y+vz) v w x y z Cost =(1*1)+(5*(2+1))=16 (82% cheaper) Delay =(.6+1*.4)+(.6+2*.4+1) +(.6+2*.4+1)+(.6+2*.4+1) =8.2 (25% faster) 29 Minimization with the Karnaugh map Dual minimisationStep 1: Create the Karnaugh map 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 w x y z z v 30 Minimization with the Karnaugh map Dual minimisationStep 2: Determine all prime implicants 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 w x y z z v 31 Minimization with the Karnaugh map Dual minimisationStep 3: Determine all essential prime implicants 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 w x y z z v 0 0 0 0 0 0 0 0 0 0 Is already the minimum coverage F 0min2 =(v+y)(w+x)(v’+z) 32 Minimization with the Karnaugh map Realisation of F 0min2 =(v+y)(w+x)(v’+z) v w x y z Cost=(1*1)+(3*(2+1))+(1*(3+1))=14 (84% cheaper) Delay=(.6+1*.4)+(.6+2*.4+1)+(.6+3*.4+1)=6.2 (44% faster) 33 Minimization with the Karnaugh map Summary Area/time trade-off We’ll see that, depending on the technology mapping, we will eventually obtain for an ASIC realisation: OR-AND-INV Cost = 11 (Rel. cost=12%) Delay = 4 (Rel. delay=36%) NOR Cost = 10 (Rel. cost=11%) Delay = 4.2 (Rel. delay=38%) 34 Design of Combinatorial Circuits Minimization of Boolean functions Karnaugh map Minimization with the Karnaugh map Don’t care conditions Quine-McCluskey Technology mapping Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 35 Don’t care conditions Incompletely specified Boolean function BCD  7-segment a b c d e f g 36 Don’t care conditions Step 1: Create Karnaugh maps 1 0 1 1 0 1 1 1 x x x x 1 1 x x 1 1 1 1 1 0 1 0 x x x x 1 1 x x 1 1 1 0 1 1 1 1 x x x x 1 1 x x 1 0 1 1 0 1 0 1 x x x x 1 1 x x 1 0 0 1 0 0 0 1 x x x x 1 0 x x 1 0 0 0 1 1 0 1 x x x x 1 1 x x 0 0 1 1 1 1 0 1 x x x x 1 1 x x x x y y z z z z w w w w a b c d e f g 37 Don’t care conditions Step 2: determine all prime implicants 1 0 1 1 0 1 1 1 x x x x 1 1 x x 1 1 1 1 1 0 1 0 x x x x 1 1 x x 1 1 1 0 1 1 1 1 x x x x 1 1 x x 1 0 1 1 0 1 0 1 x x x x 1 1 x x 1 0 0 1 0 0 0 1 x x x x 1 0 x x 1 0 0 0 1 1 0 1 x x x x 1 1 x x 0 0 1 1 1 1 0 1 x x x x 1 1 x x x x y y z z z z w w w w a b c d e f g 38 Don’t care conditions Step 3: Determine all essential prime implicants 1 0 1 1 0 1 1 1 x x x x 1 1 x x x y z w a Complete coverage 1 1 1 0 1 1 1 1 x x x x 1 1 x x z w c Complete coverage 1 0 1 1 0 1 0 1 x x x x 1 1 x x z w d Complete coverage 1 0 0 1 0 0 0 1 x x x x 1 0 x x x y e Complete coverage 1 0 0 0 1 1 0 1 x x x x 1 1 x x f Complete coverage 0 0 1 1 1 1 0 1 x x x x 1 1 x x g Incomplete coverage 1 1 1 1 1 0 1 0 x x x x 1 1 x x z w b Complete coverage 39 Don’t care conditions Step 4: Determine minimum coverage 0 0 1 1 1 1 0 1 x x x x 1 1 x x g Selection of the cube that realises the remaining minterm: - Select all cubes that realise the minterm and are already essential for another function; in this case, both are already essential - Select that cube that appears in the smallest number of other functions to keep the fan-out as low as possible 40 Don’t care conditions Note down the standard form 1 0 1 1 0 1 1 1 x x x x 1 1 x x x y z w a y’w’ z yw x a=y’w’+z+yw+x 41 1 1 1 1 1 0 1 0 x x x x 1 1 x x z w b Don’t care conditions Note down the standard form y’w’ z yw x a=y’w’+z+yw+x z’w’ zw b=y’+z’w’+zw y’ 42 1 1 1 0 1 1 1 1 x x x x 1 1 x x z w c Don’t care conditions Note down the standard form y’w’ z yw x a=y’w’+z+yw+x y’ z’w’ zw b=y’+z’w’+zw z’ w y c=z’+w+y 43 1 0 1 1 0 1 0 1 x x x x 1 1 x x z w d Don’t care conditions Note down the standard form y’w’ z yw x a=y’w’+z+yw+x y’ z’w’ zw b=y’+z’w’+zw z’ w y c=z’+w+y y’w’ y’z yz’w zw’ x d=y’w’+y’z+yz’w+zw’+x 44 1 0 0 1 0 0 0 1 x x x x 1 0 x x x y e Don’t care conditions Note down the standard form z yw x a=y’w’+z+yw+x y’ z’w’ zw b=y’+z’w’+zw z’ w y c=z’+w+y y’z yz’w zw’ d=y’w’+y’z+yz’w+zw’+x y’w’ y’w’ zw’ e=y’w’+zw’ 45 1 0 0 0 1 1 0 1 x x x x 1 1 x x f Don’t care conditions Note down the standard form z yw x a=y’w’+z+yw+x y’ z’w’ zw b=y’+z’w’+zw z’ w y c=z’+w+y y’z yz’w zw’ d=y’w’+y’z+yz’w+zw’+x e=y’w’+zw’ z’w’ yz’ yw’ x f=z’w’+yz’+yw’+x y’w’ 46 0 0 1 1 1 1 0 1 x x x x 1 1 x x g Don’t care conditions Note down the standard form z yw x a=y’w’+z+yw+x y’ z’w’ zw b=y’+z’w’+zw z’ w y c=z’+w+y y’z yz’w zw’ d=y’w’+y’z+yz’w+zw’+x e=y’w’+zw’ yz’ yw’ f=z’w’+yz’+yw’+x yz’ y’z yw’ x g=y’z+yz’+yw’+x y’w’ 47 Don’t care conditions xyzw a c b d e f g 48 Don’t care conditions Cost when realising as ( 1-minterms): a: 4*1+8*(4+1)+1*(8+1)=53 b: 4*1+8*(4+1)+1*(8+1)=53 c: 4*1+9*(4+1)+1*(9+1)=59 d: 4*1+7*(4+1)+1*(7+1)=47 e: 4*1+4*(4+1)+1*(4+1)=29 f: 4*1+6*(4+1)+1*(6+1)=41 g: 4*1+7*(4+1)+1*(7+1)=47 Cost for minimal 2-layer-implementation Invertors: 4*1=4 AND-gates: 8*(2+1)+1*(3+1)=28 OR-gates: 1*(2+1)+2*(3+1)+3*(4+1) +1*(5+1)=32 329 (100%) 64 (19%) 49 Don’t care conditions Delay when realising as ( 1-minterms): Critical path=c (9-input OR) c: (1)+(.6+4*.4+1)+(.6+9*.4+1)=9.4 (100%) Delay for minimal 2-layer-implementation Critical path=d (3-input AND & 5-input OR) d: (1)+(.6+3*.4+1)+(.6+5*.4+1)=7.4 (79%) 50 Design of Combinatorial Circuits Minimization of Boolean functions Karnaugh map Minimization with the Karnaugh map Don’t care conditions Quine-McCluskey Technology mapping Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 51 Quine-McCluskey Method with Karnaugh map OK for human minimisation : visually oriented no guarantee for optimum solution Computer method Quine-McCluskey table oriented leads to optimum solution is the basis of all CAD circuit design tools hardly doable by hand 52 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Gate arrays: NAND, NOR Custom library: AOI, OAI, PLA FPGA Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 53 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Gate arrays: NAND, NOR Custom library: AOI, OAI, PLA FPGA Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 54 Technology Mapping:Gate Arrays Properties of the methodology followed: When minimizing 1-minterms: INV-AND-OR When minimizing 0-maxterms: INV-OR-AND Any function can be realized in two layers of logic with this methodology The fan-in of the gates can become arbitrary large Properties of gate arrays: They only contain m -input NAND or m -input NOR gates Technology mapping is: Translating a circuit consisting of INV-AND-OR to one with only m -input NAND Dual: INV-OR-AND  m -input NOR 55 Technology Mapping:Gate Arrays Design flow: Conversion Replace each AND and OR by NAND or NOR Optimisation Eliminate double inversions Replace each n -input AND (OR) by a few m -input ANDs (ORs), with m < n Decomposition Retiming Try to make all input-output delays equal 56 Technology Mapping:Gate Arrays Conversion rules (based on the laws of De Morgan): = (xy)’ = (x’ + y’) = (x+y)’ = (x’y’) Optimisation rule: = (x’)’ = x 57 Technology Mapping:Gate Arrays Conversion rules in practice: The realisation with only NAND or only NOR is faster: we save an invertor per gate! 58 Technology Mapping:Gate Arrays Realisation of an invertor: = 59 Technology Mapping:Gate Arrays Decomposition: = = 60 Technology Mapping:Gate Arrays Retiming (delay optimisation): try to make the delay from each input to the output equal Example: AND-OR implementation obtained from Karnaugh minimisation 61 Technology Mapping:Gate Arrays Example (first possible decomposition in 3-input NAND): = Delay = (.6+3x.4)+(1)+(.6+3x.4)+ (.6+3x.4)+(1)+(.6+3x.4) = 9.2 62 Technology Mapping:Gate Arrays Example (second possible decomposition in 3-input NAND): = Delay = (.6+3x.4)+(1)+(.6+3x.4)+ (.6+3x.4) = 6.4 (70%) 63 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Gate arrays: NAND, NOR Custom library: AOI, OAI, PLA FPGA Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 64 Technology Mapping:Custom Library ASICs have AOI en OAI: small and fast! For small functions ( not in course book ): Realise the inverse function with AND-OR or OR-AND Example: realise again following function: F=  (6,7,10,11,14,15,21,23,25,27,29,31) Realisation as sum of 1-minterms: cost = 90; delay = 11 Minimal realisation as OR-AND: cost = 14 (16%); delay = 6.2 (56%) 65 Technology Mapping:Custom Library F=  (6,7,10,11,14,15,21,23,25,27,29,31)  F’=  (0,1,2,3,4,5,8,9,12,13,16,17,18,19,20, 22,24,26,28,30) 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 w x y z z v F’ v w x y z F’ F w x y z F Cost=(5*1)+6=11 (12%) Delay=1+(.6+6*.4)=4 (36%) 66 Technology Mapping:Custom Library For large functions: Transform to NAND or NOR Realise as AND-OR or OR-AND Replace repeatedly 2 layers of gates off critical path by AOI/OAI Determine critical path Replace repeatedly 2 layers of gates on critical path by AOI/OAI 67 Technology Mapping:Custom Library F=w’z’+z(w+y) Realise with AND and OR y z w F Cost=14 Delay=7.2 Transform to NAND and NOR y z w F Cost=? Delay=? Transform to NAND and NOR y z w F Cost=11 (79%) Delay=5.2 (72%) Determine the critical path y z w F Cost=11 (79%) Delay=5.2 (72%) Replace 2 gates on critical path by AOI y z w F Cost=? Delay=? Replace 2 gates on critical path by AOI y z w F Cost=10 (71%) Delay=5.6 (78%) Replace 2 gates on critical path by AOI (2e possibility) y z w F Cost=? Delay=? Replace 2 gates on critical path by AOI (2e possibility) y z w F Cost=10 (71%) Delay=3.8 (53%) Analyze the other path y z w F Cost=10 (71%) Delay=3.8 (53%) Analyze the other path y z w F Cost=9 (64%) Delay=3.8 (53%) 68 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Gate arrays: NAND, NOR Custom library: AOI, OAI, PLA FPGA Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 69 Technology Mapping:PLA PLA is an AND-plane with large fan-in followed by an OR-plane with large fan-in Technology mapping: realisation as AND-OR, without the necessity for decomposition 70 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Gate arrays: NAND, NOR Custom library: AOI, OAI, PLA FPGA Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 71 Technology Mapping:FPGA CLB is 2 functions of 4 variables or 1 function of 5 variables Technology mapping is similar as for custom design but i.o. AOI/OAI we search for sub-circuits of 4 or 5 variables, first on the critical path, next on the other paths For FPGAs technology mapping is done by automatic tools (see next slide); when prototype: no hand optimalisation, when final product: hand optimalisation beneficial. Also for ASICs automatic tools exist, hand optimalisation is beneficial BCD 7-segment: create 7 truth tables i.f.o. 4 variables: the rest is done by the tools 72 Technology mapping:FPGA Technology mapping 73 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks (Adder, ALU, MUX, ) 74 Correct timing behavior:Hazard-free design 1 1 1 1 x y z x y z y’ a b F x y y’ z a b F 1 x y z y’ a b F 1 1 0 1 2 3 4 5 6 x y z y’ a b F x y z y’ a b F x y z y’ a b F x y z y’ a b F x y z y’ a b F x y z y’ a b F Static 1-hazard 75 Correct timing behavior:Hazard-free design The hazard condition causes an unwanted glitch! Static 1-hazard: the output had to stay 1 but became briefly 0 Cause: different delay in two paths Solution: see next slide 76 Correct timing behavior:Hazard-free design 1 1 1 1 x y z x y z y’ a b F c 1 x y y’ z a b F 0 1 2 3 4 5 6 c x y z y’ a b F c x y z y’ a b F c 1 1 x y z y’ a b F c x y z y’ a b F c x y z y’ a b F c 77 Correct timing behavior:Hazard-free design Dynamic hazard: the output had to switch (eg. from 1 to 0) but switched several times (bvb. 1  0  1  0) Cause: different delay in multiple paths Example: see next slide 78 x’ x’’ a F x’ x’’ a F x Correct timing behavior:Hazard-free design Statically equivalent to: x F x’’ 0 1 2 3 4 5 6 7 8 9 x x’ a F x’ x’’ a F x’ x’’ a F x’ x’’ a F x’ x’’ a F x’ x’’ a F x’ x’’ a F x’ x’’ a F x’ x’’ a F x’ x’’ a F x’ x’’ a F 79 Correct timing behavior:Hazard-free design Hazards are hard to detect by hand: importance of simulation The danger for hazards increases when rise times and fall times are not equal Are hazards a problem? For synchronous circuits, they are not Unless they control the clock of a memory element For asynchronous circuits, they always are a problem This is why asynchronous design is heavily demotivated for FPGAs (the delay of the different paths is only known after APR-Automatic Placement and Routing) 80 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 81 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 82 Ripple-carry adders Half adder 0 0 0 1 x i y i c i+1 0 1 1 0 x i y i s i x i y i c i+1 s i HA x i y i c i+1 s i 1 CLB 83 Ripple-carry adders Full adder 1 1 1 1 c i x i y i c i+1 1 1 1 1 c i x i y i s i x i y i c i c i+1 s i 1 CLB 84 Ripple-carry adders Full adder: alternative implementation y i 1 1 1 1 c i x i y i s i 1 1 1 1 c i x i c i+1 x i y i c i c i+1 s i 1 gate less, larger delay from x i &y i to c i+1 , same delay from c i to c i+1 FA x i y i c i c i+1 s i 85 Ripple-carry adders 4-bit ripple-carry adder FA x 0 y 0 c 0 =0 c 1 s 0 FA x 1 y 1 c 2 s 1 FA x 2 y 2 c 3 s 2 FA x 3 y 3 c 4 s 3 Critical path: x 0 or y 0 to c 4 : 1 XOR + 4 AND + 4 OR In principal 1 CLB per bit Because of special circuitry (dedicated carry chain): 1 CLB per 2 bits 86 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 87 Carry-look-ahead adders Ripple-carry adder is slow because the critical path x 0 to c n+1 is long Speed-up is possible by computing for example c 4 directly (in principle in 2 layers of logic) from c 0 , x 0 x 3 en y 0 y 3 . Hence the name Carry-look-ahead How is this done? See exercises and course book 4-bit CLA c i x ii+3 y ii+3 s ii+3 c i+4 88 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 89 Adder-subtractors FA x 0 y 0 c 0 c 1 f 0 FA x 1 y 1 c 2 f 1 FA x 2 y 2 c 3 f 2 FA x 3 y 3 c 4 f 3 S Adder/ subtractor X Y F S C out overflow Only for 2-complement!!! 90 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 91 Multipliers A 1-bit by 1-bit multiplier:C = B • A b 0 a 0 a 0 b 0 A 1-bit by 1-bit multiplier is hence an AND gate a 0 b 0 c 0 92 Multipliers A 2-bit by 2-bit multiplier:C = B • A a 0 b 0 b 0 a 0 b 1 a 1 a 0 b 1 a 1 b 0 a 1 b 1 c 0 c 1 c 2 c 3 Each of these terms is a 1-bit by 1-bit multiplier: AND b 0 b 1 a 0 b 0 b 1 a 1 HA HA c 0 c 1 c 2 c 3 93 Multipliers A 4-bit by 3-bit multiplier: cost=O(n 2 ) b 0 b 1 a 0 b 2 b 3 b 0 b 1 a 1 b 2 b 3 4-bit adder 0 b 0 b 1 a 2 b 2 b 3 4-bit adder c 0 c 1 c 2 c 3 c 4 c 5 c 6 s 0 s 1 s 2 s 3 c out s 0 s 1 s 2 s 3 c out 94 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 95 Logic units Goal: implement a unit that can realise all 16 Boolean functions of 2 bits The unit has two inputs X and Y and 4 select bits S 3 S 2 S 1 S 0 that select the wanted function The coding of the select bits is identical to the function number in the table of possible Boolean functions 96 Logic units 97 Logic units S 0 S 1 S 2 S 3 x i y i f i LU x i y i f i S 0..3 98 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 99 Arithmetic-logic units Goal: build a unit that realises 4 arithmetic operations (addition, subtraction, increment and decrement) and 4 logic operations (AND, OR, INV, identity) Realisation principle: use an adder in front of which we place a modifier circuit (Arithmetic-Logic Extender) This principle has already been applied for the 2-complement adder/subtractor: this was an adder in front of which we placed an exor circuit to allow for subtraction 100 Arithmetic-logic units FA FA FA FA FA a 0 b 0 a 1 b 1 a 2 b 2 a 3 b 3 a 4 b 4 f 0 f 1 f 2 f 3 f 4 S C out S selects the function to be executed: 0=addition, 1=subtraction 101 Arithmetic-logic units M M selects the type of operation: 0=logic, 1=arithmetic S 0 and S 1 select the operation FA a 0 b 0 f 0 ALE FA a 1 b 1 f 1 ALE FA a 2 b 2 f 2 ALE FA a 3 b 3 f 3 ALE FA a 4 b 4 f 4 ALE C out S 01 X Y 102 Arithmetic-logic units 103 Arithmetic-logic units 1 1 M S 1 S 0 c 0 M S 1 c 0 104 Arithmetic-logic units 1 1 1 M S 1 S 0 X 1 1 1 1 1 a i b i 1 1 1 1 1 1 1 1 S 1 S 0 b a S 0 S 1 M X 105 Arithmetic-logic units b i M S 1 S 0 Y a i 1 1 1 1 1 1 1 1 S 1 S 0 b a S 0 S 1 M Y 106 Arithmetic-logic units M FA a 0 b 0 f 0 ALE FA a 1 b 1 f 1 ALE FA a 2 b 2 f 2 ALE FA a 3 b 3 f 3 ALE FA a 4 b 4 f 4 ALE C out S 01 X Y 107 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 108 Decoders E A 1 A 0 C 3 C 2 C 1 C 0 Decoder C 3..0 A 1..0 E 2 CLB 109 Decoders Decoder C 3..0 A 1..0 E Decoder C 7..4 A 1..0 E Decoder C 11..8 A 1..0 E Decoder C 15..12 A 1..0 E Decoder A 3..2 E 110 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 111 Selectors D 3 D 2 D 1 D 0 S 1 S 0 Y 4-to-1 MUX D 3..0 S 1..0 Y In principle: 2-to-1 MUX is 1/2 CLB Due to special provisions: 4-to-1 MUX is 1 CLB 112 Selectors D 3 D 2 D 1 D 0 Y Decoder S 1 S 0 Alternative implementation 113 Selectors 4-to-1 selector S 3..2 4-to-1 selector D 7..4 S 1..0 4-to-1 selector D 11..8 S 1..0 4-to-1 selector D 15..12 S 1..0 4-to-1 selector D 3..0 S 1..0 Y 114 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 115 Buses Problem with high fan-in MUX: fan-in OR gate too big all inputs have to be routed to 1 central location: substantial routing delay and difficult routing Solution: bus with tristate drivers Decoder D 3 D 2 D 1 D 0 S 1 S 0 Y 116 Buses In an FPGA (lab session) a limited number of tristate buffers is foreseen, connected to horizontal long lines. It is possible to indicate for a certain signal that we prefer to map it to a long line. Note that a Boolean signal already can have 4 different values: 0: the logical signal “0” 1: the logical signal “1” x: don’t care Z: high-impedant Simulations will allow to visualize each of the 4 different values 117 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 118 Priority encoders 0 D 2 D 3 D 1 D 0 Any 0 0 0 0 D 2 D 3 D 1 D 0 A 1 1 1 1 1 1 1 1 1 1 1 D 2 D 3 D 1 D 0 A 0 119 Priority encoders 0 D 2 D 3 D 1 D 0 Any 0 0 0 0 D 2 D 3 D 1 D 0 A 1 1 1 1 1 1 1 1 1 1 1 D 2 D 3 D 1 D 0 A 0 D 3 D 0 Any A 1 A 0 Priority encoder D 3..0 A 1..0 Any 1 1/2 CLB 120 Priority encoders Priority encoder D 3..0 Priority encoder D 7..4 Priority encoder D 11..8 Priority encoder D 15..12 Priority encoder A 3..2 Any 4-to-1 MUX A 1 4-to-1 MUX A 0 121 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 122 Magnitude comparators 1 1 1 1 1 1 y 1 x 1 x 0 y 0 G 1 1 1 1 1 1 y 1 x 1 x 0 y 0 L 123 x 1 x 0 y 1 y 0 Magnitude comparators 1 1 1 1 1 1 y 1 x 1 x 0 y 0 G 1 1 1 1 1 1 y 1 x 1 x 0 y 0 L G L Comp X i Y i G i L i G i+1 L i+1 1 CLB 124 Magnitude comparators Comp x 1 y 1 Comp x 2 y 2 Comp x 3 y 3 Comp x 4 y 4 Comp x 5 y 5 Comp x 6 y 6 Comp x 7 y 7 x 0 y 0 G L Comp x 1 y 1 x 2 y 2 Comp x 3 y 3 x 4 y 4 Comp x 5 y 5 x 6 y 6 Comp x 7 y 7 x 0 y 0 Comp Comp Comp G L 125 Magnitude comparators Simpler circuits are used for comparison with constants!! y=1 when X=0 X y y=1 when X=255 y=1 when X>=64 X y y=1 when X<192 x 7 x 6 y y=1 when X is even x 0 y x 7 x 6 y X is 8 bits 126 Design of Combinatorial Circuits Minimization of Boolean functions Technology mapping Correct timing behavior Basic RTL building blocks Ripple-carry adders Carry-look-ahead adders Adder/subtractors Multipliers Logic units Arithmetic-logic units Decoders Selectors Buses Priority encoders Magnitude comparators Shifters and rotators 127 Shifters and rotators Shifter: An input word is shifted m positions to the left or to the right m bits disappear at one side m bits are created at the other side For an arithmetic shift (word = 2-complement) For a left shift m zeros are shifted in from the right For a right shift m times the MSB is shifted in from the left (for 2-complement) For a logic shift It is possible to indicate which value is shifted in m bit left shift is multiplication with 2 m m bit right shift is division by 2 m 128 Shifters and rotators Rotator: An input word is shifted m positions to the left or to the right The bits that drop-off at one side, are shifted back in at the other side 129 Shifters and rotators d 0 d 1 d 2 d 3 S 2 S 1 S 0 L-in R-in 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX M M y 3 y 2 y 1 y 0 S 2 : 0=no shift,1=shift S 1 : 0=left,1=right S 0 : 0=shift,1=rotate 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX M M y 3 y 2 y 1 y 0 S 2 : 0=no shift ,1=shift S 1 : 0=left ,1=right S 0 : 0=shift ,1=rotate 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX M M y 3 y 2 y 1 y 0 S 2 : 0=no shift, 1=shift S 1 : 0=left ,1=right S 0 : 0=shift ,1=rotate 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX M M y 3 y 2 y 1 y 0 S 2 : 0=no shift, 1=shift S 1 : 0=left ,1=right S 0 : 0=shift, 1=rotate 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX M M y 3 y 2 y 1 y 0 S 2 : 0=no shift, 1=shift S 1 : 0=left, 1=right S 0 : 0=shift ,1=rotate 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX 4-to-1 MUX M M y 3 y 2 y 1 y 0 S 2 : 0=no shift, 1=shift S 1 : 0=left, 1=right S 0 : 0=shift, 1=rotate 130 Shifters and rotators M M M M M M M M M M M M M M M M M M M M M M M M S 0 S 1 S 2 8-bit barrel left rotator 131