Blog

Combinational logic 3. Combinational Logic 3.1 Boolean Implementation of Arithmetic Functions ELEE08015 Digital System Design 2 1 Additional Reading: Textbook (Donzellini et. al.): Section 2.1, 2.2, 2.3, 3.6, 3.9.1, 3.9.2, 3.9.3 Note that the material presented in the course notes, videos, and exercise sets should be considered as the main source for notations, formulations, and design principles while the textbook material should be only considered as complementary. Combinational logic Carry = A . B Sum = A . B +A . B = A⊕B Combinational Logic for Binary addition ● Suppose we want to design a circuit to add two single bit numbers A and B – 0 and 1 now signify numerical values zero andone A B Carry Sum 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 Truth table Boolean expression ELEE08015 Digital System Design 2 2 Combinational logic Sum = A . B + A . B Binary Half Adder ● Logic gate implementations of binary half adder: B A Sum Sum Carry Carry A B Equivalent to: Carry = A . B Sum = A⊕B ELEE08015 Digital System Design 2 3 Combinational logic Full addition ● Add two unsigned n-bit binary natural numbers: n 1 :0 n 1 n 2 1 0A = {A , A , … A , A } and Bn 1 : 0 = {B n 1 , B n 2 , … B1 , B0 } representing An 1 2 n 1 + An 2 n 2 1 1 02 + … + A 2 + A 2 0 and Bn 1 2 n 1 + Bn 2 n 2 1 1 02 + … + B 2 + B 2 0 ELEE08015 Digital System Design 2 4 Combinational logic 4-bit Full Addition Example ● Add two unsigned 4-bit binary natural numbers: A3 :0 = {A3 , A2 , A1 , A0} and B 3 :0 = {B 3 , B 2 , B1 , B0} representing and Example: A 3 2 1 0 3 :0 = 11D = {1, 0, 1, 1} = 1×2 + 0×2 + 1×2 + 1×2 B 3 2 1 0 3 :0 = 7D = {0, 1, 1, 1} = 0×2 + 1×2 + 1×2 + 1×2 A3 23 + A2 22+ A1 21 + A0 20 B3 23 + B2 22+ B1 21 + B0 20 ELEE08015 Digital System Design 2 5 Combinational logic ● Example: 11 + 7 = 18 D D D ● ● ● ● ● Full addition requires input carry and output carry Addends are 4-bits, but result requires 5-bits (overflow) 1 bit Full Addition 4 3 2 1 01● 8 = {1, 0, 0, 1, 0 }= 1× 2 + 0× 2 + 0× 2 + 1× 2 + 0× 2 D ELEE08015 Digital System Design 2 6 A B Cin Cout Sum 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 Full Adder Truth Table: Combinational logic Synthesising Truth Table: Karnaugh map ELEE08015 Digital System Design 2 7 A Karnaugh map is a table of cells with each cell representing one minterm (or maxterm). Maps for two variables have four cells, for three variables eight cells, for four variables sixteen cells and so on. The cells are laid out so that moving from one cell to any adjacent cell results in a change in one variable, i.e., hamming distance of 1 between codewords. Where a minterm is to be included in the logic function a 1 is written in the cell. Otherwise a 0 is written in or it is left blank. Don’t cares can be also included and treated as 1 or 0 as appropriate! Thus, any two adjacent cells that both contain a 1 represent terms that differ in one variable and can be combined as: !. # + !. %# = !. # + %# = ! The map can be inspected for groups of ones and their minimised form can be written. The minimisation relies on combining adjacent 1s into groups as large as possible of given the group has a size of power of 2 and a rectangular shape. Note that the maps have cyclic property and thus the groups can be rolls over from left end to the right and so on. BC A 00 01 11 10 0 1 1 0 1 1 1 1 0 0 A.C B 3-variable Karnaugh Map Combinational logic Karnaugh Map ELEE08015 Digital System Design 2 8 Consider the following map for two variables. All four minterms are present and given a truth table can be entered in the map. Now assume the Kmap for truth table below: B A 0 1 0 A.B A.B 1 A.B A.B Truth table Truth table applied to map A B F 0 0 1 0 1 1 1 0 0 1 1 1 B A 0 1 0 1 1 1 0 1 We can now draw loops round groups of 1s in the map to represent the mimimised terms. F = A.B +A.B +A.B = A.B +B. A +A( ) = A.B +B = A +BB A Hence F = A + B directly from the map. We know how to reduce the function using Boolean algebra too:B A 0 1 0 1 1 1 0 1 Combinational logic A B Cin Cout 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 C in B C in 00 01 11 10 A B 0 0 0 1 0 1 0 1 1 1 A C in Truth table Karnaugh map A B C = A B+A C + B C out in in Boolean expression Karnaugh map for Cout ELEE08015 Digital System Design 2 9 Combinational logic Karnaugh map for Sum 0 1 0 1 1 0 1 0 C in 00 01 11 10 0 1 A B Cin Sum 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 Karnaugh map A B Truth table Boolean expression Sum = A B C i n +A B C i n +A B C i n + A B C i n ELEE08015 Digital System Design 2 10 Combinational logic Simplified expression for Sum ● Using Boolean algebra: ELEE08015 Digital System Design 2 11 Combinational logic Full adder circuit #1 A B C in Sum C out Sum = A ⊕ B ⊕ Cin C = A B + A C + B C out in in ELEE08015 Digital System Design 2 12 Combinational logic Full adder circuit #2 Sum = A ⊕ B ⊕ C in C = A B + A C + B C out in in C = A B + (A ⊕ B ) . C out in ● Full adder can be made from 2-half adders and a 2- input OR gate C A B in C out C out Sum Sum C in A B Sum Half Adder Carry Sum Half Adder Carry ELEE08015 Digital System Design 2 13 Combinational logic 4-bit ripple carry adder Full addition of A3 :0 = {A3 , A2 , A1 , A0} and B3 :0 = {B3 , B2 , B1 , B0} generating S 3 :0 = {S3 , S 2 , S1 , S 0} A 3 B 3 A 2 B 2 A 1 B 1 A 0 B 0 + S 0 + S 1 + S 2 + S 3 C in C out Sum is generated as the carry ripples through the chain of adders ELEE08015 Digital System Design 2 14 Full adder symbol + An Bn CinCout Sn Combinational logic Ripple Carry Adder Delay ● ● ● Depends on number of logic stages traversed Function of applied input signals A and B n-1 : 0 n-1 : 0 – For some input signals no rippling occurs – For other signals, carry has to ripple from the least significant bit (lsb) to the most significant bit (msb) Critical Path: worst case propagation delay over all possible input patterns ELEE08015 Digital System Design 2 15 Combinational logic Ripple Carry Adder Critical Path ● ● ● Critical path occurs when – Carry generated at the lsb position propagates all the way to the msb position – Carry consumed at msb position to produce the sum Propagation delay from Cin to Cout : tcarry Propagation delay from Cin to Sum: tsum Assume that both the delay from input signals A0 (or B0) to Cout,0 for the lsb, and the Cin to Cout delay for all other bits equal to tcarry . ELEE08015 Digital System Design 2 16 Adder Truth Table: Carry Status A B Cin Cout Sum Carry Status 0 0 0 0 0 Delete 0 0 1 0 1 Delete 0 1 0 0 1 Propagate 0 1 1 1 0 Propagate 1 0 0 0 1 Propagate 1 0 1 1 0 Propagate 1 1 0 1 0 Generate 1 1 1 1 1 Generate – Critical path length linearly proportional to N – increasingly significant for adders with wide data paths – Priority is to optimise tcarry rather than tsum as tsum has minor influence on total delay, tadder . Combinational logic Example: Critical Path Derive values of inputs An-1:0 and Bn-1:0 so that worst case delay is obtained for ripple carry adder – Carry generated in lsb position. If Cin,0 is 0, both A0 and B0 = 1 (see truth table, Generate Carry Status row) – All other stages in Propagate mode (see truth table), hence either Ai = 1 or Bi= 1 – Set up a 0 → 1 transition on the msb sum bit:achieved by setting both An-1:0 and Bn-1:0 to 0 (or 1). ELEE08015 Digital System Design 2 17 For an 8-bit addition the following values of A7:0 and B7:0 set up a worst case delay: A = { 0, 0, 0, 0, 0, 0, 0, 1}, B= { 0, 1, 1, 1, 1, 1, 1, 1} Carry ripples through addition: Combinational logic Subtraction ● Use ripple carry adder to perform subtraction by taking advantage of the following observation: ● ● ● ● Create the code for -B from the input +B and then add to A to (-B) Use two’s complement notation to represent negative numbers. S = A B is the same as S = A+ ( B) ELEE08015 Digital System Design 2 18 Two’s Complement code mapping for 4-bit codewords: Decimal 2’s Complement Decimal 2’s Complement 0 0000 0 0000 1 0001 -1 1111 2 0010 -2 1110 3 0011 -3 1101 4 0100 -4 1100 5 0101 -5 1011 6 0110 -6 1010 7 0111 -7 1001 8 – -8 1000 Combinational logic Forming the Two’s Complement #1 ● Given a decimal number M , form an n-bit two’s D complement representation: ● ● ● ● ● D M negative: write the n-bit binary code M n 1 :0 = { mn 1 , mn 2 , … ,m1 , m0} Check that n is large enough to represent M : D 2 n 1 ≤ M < 2n 1 D M positive: write the n-bit binary code M D n-1: 0 n2 M D∣ ∣ ELEE08015 Digital System Design 2 19 Combinational logic Example: Method #1 ● ● ● ● ● Form the 5-bit two's complement M for -12 : Check range of 5-bit two's complement number: 24 ≤ M < 24 D 16 ≤ MD < 16 Number is negative, so two' complement code is: n2 M D∣ ∣ 52 12 D∣ ∣ = 32D D D 12 = 20 = 10100 4: 0 D ELEE08015 Digital System Design 2 20 Combinational logic Forming the Two's Complement #2 ● ● ● Alternative method to previous example. Same method as before except when M negative D M negative: D – write the n-bit binary code M for ∣M D∣ n-1: 0 – invert all bits of M (i.e. take the one's complement) n-1: 0 – add 1 to the result of the complement operation giving two's complement result ELEE08015 Digital System Design 2 21 Combinational logic Example: Method #2 ● ● ● ● ● Form the 5-bit two's complement M for -12 : 4: 0 D Check range of 5-bit two's complement number: 2 4 ≤ M < 24 D 16 ≤ MD < 16 Number is negative, so two's complement code is: ∣M D ∣= ∣ 12D∣= 12D = 01100 take the complement: 10011 add 1: 10011 +1 = 10100 ELEE08015 Digital System Design 2 22 Combinational logic Two's Complement Properties ● ● Two's complement negative numbers have 1 as their most significant bit Any two's complement number can have its sign changed by complementing and adding 1. ELEE08015 Digital System Design 2 23 Two's Complement Addition Use 4-bit two's complement numbers. Number range: ● ● i.e. -8 to +7 Add +3 to +4 : D D – result correct! 2 n 1 ≤ M D < 2 n 1 2 3 ≤ M < 23 D 8 ≤ MD < 8 Combinational logic Another Addition Example ● ● Use 4-bit two's complement numbers. Add +5 to +6 : D D – result out of 4-bit two's complement range – result interpreted as a two's complement number is -5 which is incorrect! D – overflow has occurred out of range ELEE08015 Digital System Design 2 24 Combinational logic Further Examples despite overflow! despite overflow! out of range ELEE08015 Digital System Design 2 25 Combinational logic Two's Complement Overflow ● Two overflow cases – negative numbers: ● ● – and positive numbers: – ● Overflow detected by noting msb has changed: out of range out of range Overflow = An 1 Bn 1 Sn 1 + An 1 Bn 1 S n 1 ELEE08015 Digital System Design 2 26 Combinational logic Overflow A B Cin Cout Sum Overflow 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 0 Overflow = Cin ⊕ Cout ● Overflow signal truth table aids logic simplification: ELEE08015 Digital System Design 2 27 Combinational logic Binary Subtraction ● ● ● Any two's complement number can have its sign changed by complementing and adding 1. ELEE08015 Digital System Design 2 28 4-bit Subtracter A 3 B 3 A 2 B 2 A 1 B 1 A 0 B 0 C = 1 in,0 C out,3 + + + + S S S S 3 2 1 0 Overflow – Complement the bits of B and add 1 to form -B anduse the full adder to perform A + (-B) i.e. subtraction. Combinational logic 1-bit Adder/Subtracter ● Use an Ex-OR gate as a selectable inverter: + A n B n S n C in C out bit invert bit invert B n Ex-OR 0 0 0 0 1 1 1 0 1 1 1 0 ELEE08015 Digital System Design 2 29 Combinational logic 4-bit Adder/Subtracter A 3 A 2 A 1 A 0 C out,3 + S 3 + S 2 + S 1 + S 0 B 3 B 2 B 1 B 0 Overflow bit invert bit = 0 :adder invert bitinvert = 1 : subtracter ELEE08015 Digital System Design 2 30 Combinational logic 3. Combinational Logic 3.2 CMOS Implementation of Boolean Functions ELEE08015 Digital System Design 2 31 Additional Reading: Textbook (Donzellini et. al.): Sections 2.4 and 2.5 Textbook (Ashenden): Section B1.5 Note that the material presented in the course notes, videos, and exercise sets should be considered as the main source for notations, formulations, and design principles while the textbook material should be only considered as complementary. Combinational logic CMOS technology ● Complementary Metal Oxide Semiconductor technology (CMOS) – dominant integrated circuit technology – implements digital circuits with high noise immunity and low static power consumption – implements analogue circuits and image sensors – technology development over many decades has provided ever smaller transistors – current microprocessors contain hundreds of millions of CMOS logic gates (transistors) on a single chip. ELEE08015 Digital System Design 2 32 Combinational logic Switches in CMOS technology ● ● Two fundamental transistor/switch types: NMOS and PMOS transistors. NMOS transistor – ON/closed when control G = hi – Poor conduction if A/B signals hi – Good conduction of A/B signals lo – Hence used in pull-down networks. – ● NMOS transistors cannot be used to connect to V dd G A B ELEE08015 Digital System Design 2 33 Combinational logic Switches in CMOS technology ● PMOS transistor – ON/closed when control G = lo – Good conduction if A/B signals hi – Hence used in pull-up networks. – Poor conduction of A/B signals lo ● ● PMOS transistors cannot be used to connect to 0V. G A B ELEE08015 Digital System Design 2 34 Combinational logic CMOS inverter (NOT gate) ● ● M1 M2 out out in in in hi: M1 OFF, M2 ON, out lo in lo: M1 ON, M2 OFF, out hi V dd 0V R1 SW 0 V dd R0 0V SW 1 out ELEE08015 Digital System Design 2 35 Combinational logic CMOS inverter waveforms ● ● ● ● Ideal input signal Output signal with propagation delay, rise and fall time. Virtually no power consumption for static signals. Power consumed when signals change. V dd 0V V dd 0V Imax 0 A out in I time (S) ELEE08015 Digital System Design 2 36 Combinational logic CMOS NAND gate #1 ● Output F lo (connected to 0V) only when both inputs are hi. A B F 0 0 1 0 1 1 1 0 1 1 1 0 F = A . B FA B F B A V dd 0V Pull up network ELEE08015 Digital System Design 2 37 Combinational logic CMOS NAND gate #2 ● Output F hi (connected to V ) dd when either input is lo. A B F 0 0 1 0 1 1 1 0 1 1 1 0 FA B F A B V dd 0V Pull down network ELEE08015 Digital System Design 2 38 Combinational logic CMOS NAND gate #3 ● Complete circuit – When PMOS transistors connect F to V , NMOS dd transistors do not connect to 0V (and vice-versa). – No short circuit between V dd and 0V. F V dd 0V A B F = A . B ELEE08015 Digital System Design 2 39 Combinational logic 3-input CMOS NAND gate A B C F 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 V dd F A B C F = A . B . C 0V ELEE08015 Digital System Design 2 40 Combinational logic CMOS NOR gate #1 F BA V dd 0V Pull up network ● Output F lo (connected to 0V) when either inputs is hi. A B F 0 0 1 0 1 1 1 0 1 0 0 0 A B F F = A + B ELEE08015 Digital System Design 2 41 Combinational logic CMOS NOR gate #2 ● Output F hi (connected to V ) dd when both inputs are lo. B A V dd A B F 0 0 1 0 1 0 1 0 0 1 1 0 A B F F Pull down network 0V ELEE08015 Digital System Design 2 42 Combinational logic CMOS NOR gate #3 ● Complete circuit – When PMOS transistors connect F to V , NMOS dd transistors do not connect to 0V (and vice-versa). – No short circuit between V dd and 0V. V dd B A F F = A + B 0V ELEE08015 Digital System Design 2 43 Combinational logic ELEE08015 Digital System Design 2 44 3-input CMOS NOR gate V dd B A F C A B C F 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 F = A + B + C 0V Combinational logic CMOS AND gate ● Not possible to implement AND function with simple pull-up and pull-down network B A V dd F A B F FA B 0V ELEE08015 Digital System Design 2 45 Combinational logic CMOS OR gate ● Not possible to implement OR function with simple pull-up and pull-down network V dd FB A A B F FA B 0V ELEE08015 Digital System Design 2 46 Combinational logic Number of transistors per gate ● ● ● Different gates require different numbers of transistors: – 4 transistors for 2-input NAND and 2-input NOR – 6 transistors for 2-input AND and 2-input OR Therefore in a CMOS implementation of a Boolean expression it is more efficient to use NAND/NOR gates De Morgan's laws can usually be used to convert expressions into forms using NAND and NOR. ELEE08015 Digital System Design 2 47 Combinational logic Example #1 ● Define the minimum number of CMOS transistors required to implement the following Boolean expression using NOR-only design: F = A . B Apply De Morgan F = A + B A B F 8 transistors 6 transistors A B F ELEE08015 Digital System Design 2 48 Combinational logic Example #2 ● F = A . B + C . D Minimise the number of CMOS transistors required using NAND-only design: Apply De Morgan F = A . B . C . D A B C F A B C F D D 18 transistors 12 transistors ELEE08015 Digital System Design 2 49 Combinational logic NAND versus NOR ● ● ● ● ● PMOS transistors have less drive strength than NMOS transistors (for a given geometry) – a majority carrier mobility issue NAND gates: PMOS in parallel, NMOS in series NOR gates: PMOS in series, NMOS in parallel NOR gate slower: weaker PMOS transistors in series (whereas in parallel in a NAND gate). NAND gate faster than a NOR gate and typically occupies less area than a NOR gate. ELEE08015 Digital System Design 2 50 Combinational logic General CMOS gates ● ● ● Complex CMOS gates may be constructed for general logic functions The gate is composed of two networks – A pull-down network composed of NMOS transistors connecting the output to 0V – A pull-up network composed of PMOS transistors connecting the output to V dd The gate may have an inverter after the pull- down/pull-up gate. ELEE08015 Digital System Design 2 51 Combinational logic General CMOS gates n n inputs n inputs 0V V dd Pull up network n PMOS out (o u t. ) n NMOS Pull down network in ELEE08015 Digital System Design 2 52 ● ● Equal number of NMOS and PMOS transistors Every NMOS transistor has an equivalent PMOS transistor connected to the same input Series pull-down NMOS correspond to parallel pull-up PMOS Parallel pull-down NMOS correspond to series pull-up PMOS Combinational logic Important rule ● ● M1 M2 outin PMOS transistors cannot be used to connect to 0V NMOS transistors cannot be used to connect to V V dd Wrong !! 0V dd ELEE08015 Digital System Design 2 53 Combinational logic Boolean expression must be of the form: F = (SOP) Bar over whole term indicates an inverter is not needed at output of pull-up/pull-down network No bar indicates the need for an inverter at the output of the pull-up/pull-down network – Use inverse of the SOP expression to derive the pull- up/pull-down network SOP: Sum Of Products Form of Boolean expression ● ● ● ● ELEE08015 Digital System Design 2 54 Combinational logic F = (A.B)+C Pull-down network implementation: – Connect F to 0V when A is hi AND B is hi OR C is hi Example #1 ● Sketch a CMOS transistor network to implement the Boolean expression: ● ● B A V dd 0V F C Pull up network ELEE08015 Digital System Design 2 55 Combinational logic F = (A+B).C Connect F to V when A is lo dd Example #1 (continued) ● Pull-up network: rearrange expression using De Morgan: ● ● OR B is lo AND C is lo. V dd BA C F Pull down network 0V ELEE08015 Digital System Design 2 56 Combinational logic F = (A.B)+C Example #1 (continued) ● Complete gate V ddBA C F A C B 0V ELEE08015 Digital System Design 2 57 Combinational logic F = (A+B).C Pull-down network implementation: – Connect F to 0V when A is hi OR B is hi AND C is hi Example #2 ● Sketch a CMOS transistor network to implement the Boolean expression: ● ● A B V dd 0V F C Pull up network ELEE08015 Digital System Design 2 58 Combinational logic F = (A.B)+C Example #2 (continued) ● Pull-up network: rearrange expression using De Morgan: ● ● dd Connect F to V when A is lo AND B is lo OR C is lo. V dd F B A C Pull down network 0V ELEE08015 Digital System Design 2 59 Combinational logic F = (A+B).C Example #2 (continued) ● Complete gate V dd 0V F B A C BA C ELEE08015 Digital System Design 2 60