Design of Digital Systems II Combinational Logic Design Practices (3) Moslem Amiri, Vaclav Prenosil Embedded Systems Laboratory Faculty of Informatics, Masaryk University Brno, Czech Republic amiriOmail.muni.cz prenosilOfi.muni.cz Fall, 2014 Exclusive-OR and Exclusive-NOR Gates • An XOR gate is a 2-input gate whose output is 1 if its inputs are different X®Y = X'-Y + X-Y' • An XNOR gate is a 2-input gate whose output is 1 if its inputs are the same Table 1: Truth table for XOR and XNOR functions. X Y X®Y (X ® Y)' 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 2/70 Exclusive-OR and Exclusive-NOR Gates (a) X. (b) x. >l -lT>j Figure 1: Multigate designs for the 2-input XOR function: (a) AND-OR; (b) three-level NAND. Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 3/70 Exclusive-OR and Exclusive-NOR Gates Figure 2: Equivalent symbols for (a) XOR gates; (b) XNOR gates. » As seen in Fig. 2, any two signals (inputs or output) of an XOR or XNOR gate may be complemented without changing resulting logic function Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 4/70 Parity Circuits (a) IN ODD (b) _r ODD Figure 3: Cascading XOR gates: (a) daisy-chain connection; (b) tree structure. 5/70 Parity Circuits • Fig. 3 • (a) is an odd-parity circuit • Its output is 1 if an odd number of its inputs are 1 • (b) is also an odd-parity circuit, but it is faster • If output of either circuit is inverted, we get an even-parity circuit Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 6/70 Parity Circuits: The 74x280 9-Bit Parity Generator 74x280 (a) (b) 8 A B C D EVEN E F ODD G H I 5 9 10 11 12 6 13 1 2 4 ■ ODD Figure 4: The 74x280 9-bit odd/even parity generator: (a) logic diagram, including pin numbers for a standard 16-pin dual in-line package; (b) traditional logic symbol. Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 7/70 Parity Circuits: Parity-Checking Applications • A parity bit is used in error-detecting codes to detect errors in transmission and storage of data • In an even-parity code, parity bit is chosen so that total number of 1 bits in a code word is even • Parity circuits like 74x280 are used both to generate correct value of parity bit when a code word is stored or transmitted, and to check parity bit when a code word is retrieved or received Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 8/70 Parity Circuits: Parity-Checking Applications D[0:7] ODD U2 U3 Memory Chips READ WRITE DINO DIN1 DIN2 DIN3 DIN4 DIN5 DIN6 DIN7 PIN DOUTO D0UT1 D0UT2 D0UT3 D0UT4 D0UT5 D0UT6 D0UT7 POUT D01 3 D02 4 D03 5 D04 6 D05 7 D06 8 D07 9 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Figure 5: Parity generation and checking for an 8-bit-wide memory. 9 Parity Circuits: Parity-Checking Applications • In Fig. 5, to store a byte into memory • Specify an address • Place byte on D[0-7] • Generate its parity bit on PIN • Assert WR • '280's ODD output is connected to PIN, so that total number of Is stored is even • In Fig. 5, to retrieve a byte • Specify an address • Assert RD • A 74x541 drives byte onto D bus, and '280 checks its parity • If parity of 9-bit word is odd during a read, ERROR signal is asserted Moslem Amiri, Vaclav Přenosi Design of Digital Systems II Fall, 2014 10 / 70 Exclusive-OR Gates and Parity Circuits in Verilog Table 2: Dataflow-style Verilog module for a 3-input XOR device. module Vrxor3(A, B, C, Y); input A, B, C; output Y; assign Y = A " B " C; endmodule Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 11 / 70 Exclusive-OR Gates and Parity Circuits in Verilog Table 3: Behavioral Verilog program for a 9-input parity checker. module Vrparity9(I, EVEN, ODD); input [1:9] I; output EVEN, ODD; reg p, EVEN, ODD; integer j; always @ (I) begin p = 1'bO; for Cj =1; j <= 9; j = j+1) if (I[j]) p = "p; else p = p; ODD = p; EVEN = ~p; end endmodule Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 Exclusive-OR Gates and Parity Circuits in Verilog • ASIC and FPGA libraries contain two- and three-input XOR and XNOR functions as primitives • In CMOS ASICs, these primitives are realized very efficiently at transistor level using transmission gates • Fast and compact XOR trees can be built using these primitives • Typical Verilog synthesis tools are not smart enough to create an efficient tree structure from a behavioral program like Tab. 3 • Instead, we can use a structural program to get exactly what we want • Tab. 4 Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 13 / 70 Exclusive-OR Gates and Parity Circuits in Verilog Table 4: Structural Verilog program for a 74x280-like parity checker. module Vrparity9s(I, EVEN, ODD); input [1:9] I; output EVEN, ODD; wire Yl, Y2, Y3, Y3N; Vrxor3 Ui (I[l], I [2] , I [3] , Yl) ; Vrxor3 U2 (I [4], I [5] , I [6] , Y2); Vrxor3 U3 (I [7], I [8] , I [9] , Y3) ; assign Y3N = ~Y3; Vrxor3 U4 (Yl, Y2, Y3, ODD); Vrxor3 U5 (Yl, Y2, Y3N, EVEN); endmodule EVEN ■ ODD ■ rO»1 Moslem Amiri, Václav Přenosil Design of Digital Systems Comparators • A comparator is a circuit that compares two binary words and indicates whether they are equal • Magnitude comparators interpret their input words as signed or unsigned numbers and also indicate an arithmetic relationship (greater or less than) between words Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 15 / 70 Comparators: Comparator Structure • XOR or XNOR gates may be viewed as 1-bit comparators (a) AO BO Figure 6: Comparators using XOR gates: (a) 1-bit comparator; (b) 4-bit comparator. • We can build an n-bit comparator using n XOR gates and an n-input OR gate • Wider OR functions can be obtained by cascading individual gates • A faster circuit is obtained by arranging gates in a tree-like structure • Using NORs and NANDs in place of ORs makes circuit even faster 16 / 70 Comparators: Comparator Structure • Comparators can also be built using XNOR gates • A 2-input XNOR gate produces a 1 output if its two inputs are equal a A multibit comparator can be constructed using one XNOR gate per bit, and AN Ding all of their outputs together • Output of AND function is 1 if all of individual bits are pairwise equal • n-bit comparators in this subsection are called parallel comparators • They look at each pair of input bits simultaneously and deliver 1-bit comparison results in parallel to an n-input OR or AND function Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 17 / 70 Comparators: Iterative Circuits • An iterative circuit contains n identical modules, each of which has both primary inputs and outputs and cascading inputs and outputs • Left-most cascading inputs are called boundary inputs and are connected to fixed logic values • Right-most cascading outputs are called boundary outputs and usually provide important information primary inputs _A_ cascading input CI module CO PO boundary inputs cascading output Pl„-1 CI module CO PO Cp C„. 6 • • • = CI module CO PO boundary outputs PO„ PO, primary outputs Figure 7: General structure of an iterative combinational circuit. 18 / 70 Comparators: Iterative Circuits • Iterative circuits are suited to problems that can be solved by an iterative algorithm O Set Cq to its initial value and set / to 0 @ Use C-, and PI; to determine values of PO; and C-,+\ 0 Increment / O If / < n, go to step 2 Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 19 / 70 Comparators: An Iterative Comparator Circuit • To compare two n-bit values X and Y O Set EQ0 to 1 and set / to 0 © If EQj is 1 and Xj and Y-, are equal, set EQ,+i to 1, else set EQ,+i to 0 © Increment / 0 If / < n, go to step 2 (b) EQN Figure 8: An iterative comparator circuit: (a) module for one bit; (b) complete circuit. Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 20 / 70 Comparators: An Iterative Comparator Circuit • Parallel comparators are preferred over iterative ones • Iterative comparators are very slow • Cascading signals need time to "ripple" from leftmost to rightmost module • Iterative circuits that process more than one bit at a time (using modules like 74x85, discussed next) are much more likely to be used in practical designs Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 21 / 70 Comparators: Standard MSI Magnitude Comparators • 74x85 is a 4-bit comparator which provides a greater-than output (AGTBOUT) and a less-than output (ALTBOUT) as well as an equal output (AEQBOUT) • '85 also has cascading inputs (AGTBIN, ALTBIN, AEQBIN) for combining multiple '85s to create comparators for more than four bits 74x85 10 12 11 15 ALTBIN ALTBOUT AEQBIN AEQBOUT AGTBIN AGTBOUT AO BO A1 B1 A2 B2 A3 B3 Figure 9: Traditional logic symbol for the 74x85 4-bit comparator. Moslem Amiri, Vaclav Přenosi Design of Digital Systems II Fall, 2014 22 / 70 Comparators: Standard MSI Magnitude Comparators ALTBIN ALTBOUT AEQBIN AEQBOUT AQTBIN AQTBOUT AO BO A1 B1 A2 B2 A3 B3 XD[011] YD[011] ALTBIN ALTBOUT AEQBIN AEQBOUT AQTBIN AQTBOUT AO BO A1 B1 A2 B2 A3 B3 ALTBIN ALTBOUT AEQBIN AEQBOUT AQTBIN AQTBOUT AO BO A1 B1 A2 B2 A3 B3 Figure 10: A 12-bit comparator using 74x85s. Moslem Amiri, Vaclav Přenosi Design of Digital Systems II Fall, 2014 23 / 70 Comparators: Standard MSI Magnitude Comparators • Cascading inputs are defined so outputs of an '85 that compares less-significant bits are connected to inputs of an '85 that compares more-significant bits • For each '85 AGTBOUT = (A > B) + (A = B) ■ AGTBIN AEQBOUT = (A = B) ■ AEQBIN ALTBOUT = (A< B) + (A = B) ■ ALTBIN Arithmetic comparisons can be expressed using normal logic expressions, e.g., (A > B) = A3 • ß3'+ (A3 © ß3)' • Al ■ B2'+ (A3 © ß3)' • (A2 © B2)' • Al • Bl'+ (A3 © ß3)' • (A2 © B2)' • (>U © ßl)' • Ad • ßO' Moslem Amiri, Vaclav Prenosil Design of Digital Systems II Fall, 2014 24 / 70 Comparators: Standard MSI Magnitude Comparators 74x682 Figure 11: Traditional logic symbol for the 74x682 8-bit comparator. Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 25 / 70 Comparators: Standard MSI Magnitude Comparators 30 30 Figure 12: Logic diagram for the 74x682 8-bit comparator, including pin numbers for a standard 20-pin dual in-line package. 26 / 70 Comparators: Standard MSI Magnitude Comparators • In Fig. 12 o Top half of circuit checks two 8-bit input words for equality • PEQQ.L output is asserted if all eight input-bit pairs are equal • Bottom half of circuit compares input words arithmetically • PGTQ_L is asserted if P[7-0] > Q[7-0] • 74x682 does not have cascading inputs and a "less than" output • However, any desired condition can be formulated as a function of PEQQ_L and PGTQ_L outputs Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 27 / 70 Comparators: Standard MSI Magnitude Comparators 74x682 PEQQ O PGTQ O PNEQ 74x04 74x04 '■Oct 74x00 £> U3 PEQQ PGTQ PGEQ PLEQ 74x08 PLTQ U1 U4 Figure 13: Arithmetic conditions derived from 74x682 outputs. Moslem Amiri, Václav Přenosi Design of Digital Systems II 28 / 70 Comparators in HDLs • Comparing two bit-vectors for equality or inequality is done in an HDL program, in relational expressions using operators such as "==" and " i =" • Given relational expression " (A==B)", where A and B are bit vectors each with n elements, compiler generates the logic expression {{At © fii) + {A2 © B2) + • • • + {An © Bn))' • In a PLD, this is realized as a complemented sum of 2n product terms ■ B[+A[ ■ Si) + {A2-B'2 + A2-B2) + --- + (An -B'n + A'n- B„))' • Logic expression for " (A!=B)" is complement of the ones above Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 29 / 70 Comparators in HDLs • Given relational expression " (A" comparators are identical • Logic expressions for ">=" and "<=" are complements of expressions for "<" and ">" Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 30 / 70 Comparators in Verilog • Verilog has built-in comparison operators: >, >=, <, <=, ==, ! = • These operators can be applied to bit vectors • Bit vectors are interpreted as unsigned numbers with the MSB on left, regardless of how they are numbered • Verilog-2001 also supports signed arithmetic • Verilog matches up operands of different lengths, by adding zeros on left • Equality and inequality checkers are small and fast a Built from n XOR or XNOR gates and an n-input AND or OR gate • Checking for greater-than or less-than a The number of product terms needed for an n-bit comparator grows exponentially, on order of 2", when comparator is realized as a two-level sum of products • A two-level sum-of-products realization is possible only for small values of n (4 or less) • For larger values of n, compiler may synthesize a set of smaller comparator modules, along the lines of 74x85 and 74x682 parts, whose outputs may be cascaded or combined to create larger comparison result Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 31 / 70 Comparators in Verilog Table 5: Verilog module with functionality similar to 74x85 magnitude comparator. module Vr74x85(A, B, AGTBIN, ALTBIN, AEQBIN, AGTBOUT, ALTBOUT, AEQBOUT); input [3:0] A, B; input AGTBIN, ALTBIN, AEQBIN; output AGTBOUT, ALTBOUT, AEQBOUT; reg AGTBOUT, ALTBOUT, AEQBOUT; always <8 (A or B or AGTBIN or ALTBIN or AEQBIN) if CA == B) begin AGTBOUT = AGTBIN; ALTBOUT = ALTBIN; AEQBOUT = AEQBIN; end -else if (A > B) begin AGTBOUT = I'M; ALTBOUT = I'bO; AEQBOUT = 1'bO; end else begin AGTBOUT = 1'bO; ALTBOUT = I'bl; AEQBOUT = I'M; end endmodule ALTBIN ALTBOUT AEQBIN AEQBOUT AGTBIN AGTBOUT • Module of Tab. 5 does not perform an explicit check for A B) begin AGTBOUT = l'bl; ALTBOUT = 1'bO; AEQBOUT else if CA < B) begin AGTBOUT = 1'bO; ALTBOUT = l'bl; AEQBOUT else begin AGTBOUT = l'bx; ALTBOUT = l'bx; AEQBOUT endmodule BOUT = AEQBIN; end - 1'bO; end = 1'bO; end = l'bx; end ALTBIN ■ AEQBIN AGTBIN ALTBOUT -AEQBOUT -AGTBOUT - Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 33 / 70 Comparators in Verilog Table 7: Verilog comparator module with cascading from more to less significant stages. module Vr74x85r(A, B, AGTBIN, ALTBIN, AEQBIN, AGTBOUT, ALTBOUT, AEQBOUT); input [3:0] A, B; input AGTBIN, ALTBIN, AEQBIN; output AGTBOUT, ALTBOUT, AEQBOUT; reg AGTBOUT, ALTBOUT, AEQBOUT; always © (A or B or AGTBIN or ALTBIN or AEQBIN) if (AGTBIN) begin AGTBOUT = I'M; ALTBOUT = 1'bO; AEQBOUT = 1'bO; end else if (ALTBIN) begin AGTBOUT = 1'bO; ALTBOUT = l'bl; AEQBOUT = 1'bO; end else if (AEQBIN) begin AGTBOUT = (A > B) ? l'bl : 1'bO ; AEQBOUT - (A — B) ? l'bl : 1'bO; ALTBOUT = "AGTBOUT k "AEQBOUT; end else begin AGTBOUT = l'bx; ALTBOUT = l'bx; AEQBOUT = l'bx; end endmodule ALTBIN AEQBIN AGTBIN ALTBOUT -AEQBOUT -AGTBOUT - » With a series of if-else statements, compiler synthesizes priority logic • It checks the first condition, and only then the second, and so on • We can use a case statement instead Moslem Amm, Vaclav rrenosil TJesign ot Digital byst Systems II Fall, 2014 34 / 70 Comparators in Verilog Table 8: Verilog comparator module using a case statement. module Vr74x8Erc(A, B, AGTBIN, ALTBIK, AEQBIN, AGTBOUT, ALTBOUT, AEQBOUT); input [3:0] A, B; input AGTBINa ALTBIN, AEQBIN; output AGTBOUT, ALTBOUT, AEQBOUT; reg AGTBOUT, ALTBOUT, AEQBOUT; always ® (A or B or AGTBIN or ALTBIK or AEQBIN) case ({AGTBIN, ALTBIN, AEQBIN}) 3'blOO: begin AGTBOUT = I'M; ALTBOUT = 1'bO; AEQBOUT 3'b010: begin AGTBOUT = 1'bO; ALTBOUT = l'bl; AEQBOUT 3'bOOl: begin AGTBOUT = (A > B) ? l'bl : 1'bO ; AEQBOUT = (A == B) ? l'bl : 1'bO; ALTBOUT = "AGTBOUT k "AEQBOUT; end default: begin AGTBOUT = l'bx; ALTBOUT = l'bx; AEQBOUT endcase endmodule 1'bO; 1'bO; end end ALTBIN AEQBIN AGTBIN ALTBOUT AEQBOUT AGTBOUT Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 35 / 70 Comparators in Verilog Table 9: Verilog comparator module using continuous assignments. module Vr74x85re(A, E, AGTBIN, ALTBIN, AEQBIN, AGTBOUT, ALTBOUT, AEQBOUT); input [3:0] A, B; input AGTBIN, ALTBIN, AEQBIN; output AGTBOUT, ALTBOUT, AEQBOUT; assign AGTBOUT = AGTBIN | (AEQBIN & ( (A > B) ? 1'bl : 1'bO ) ); assign AEQBOUT = AEQBIN & ((A == B) ? l'bl : 1'bO) ; assign ALTBOUT = "AGTBOUT Si "AEQBOUT; endmodule ALTBIN AEQBIN AGTBIN ALTBOUT AEQBOUT AGTBOUT Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 36 / 70 Adders, Subtractors, and ALUs • The same addition rules and therefore the same adders are used for both unsigned and two's-complement numbers • An adder can perform subtraction as addition of minuend and complemented subtrahend • But we can also build subtracter circuits that perform subtraction directly • ALUs perform addition, subtraction, or any of several other operations according to an operation code supplied to device 37 / 70 Adders, Subtractors, and ALUs: Half Adders & Full Adders • A half adder adds two 1-bit operands X and Y, producing a 2-bit sum HS = X®Y = X ■ V + X' ■ Y CO = X ■ Y (HS = half sum, and CO = carry-out) • To add operands with more than one bit, we must provide for carries between bit positions » Building block for this operation is called a full adder S = X © Y © ON = X ■ Y' ■ CIN' + X' ■ Y ■ CIN' + X' Y' ■ CIN + X Y ■ CIN COUT = X Y + X ■ CIN +Y ■ CIN Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 38 / 70 Adders, Subtractors, and ALUs: Half Adders & Full Adders CIN ■ (a) ■COUT (b) (c) full adder í • CIN COUT I I X Y COUT CIN S Figure 14: Full adder: (a) gate-level circuit diagram; (b) logic symbol; (c) alternate logic symbol suitable for cascading. Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 39 / 70 Adders, Subtractors, and ALUs: Ripple Adders • A ripple adder is a cascade of n full-adder stages, each of which handles one bit, to add two n-bit binary words x3 y3 x2 y2 x, y, x0 y0 J—L i t t I J__l X Y X Y X Y X Y COUT CIN c3 COUT CIN c2 COUT CIN COUT CIN S S S S 1 s3 1 s2 1 S1 I s0 Figure 15: A 4-bit ripple adder. • cq is normally set to 0 Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 40 / 70 Adders, Subtractors, and ALUs: Ripple Adders • A ripple adder is slow • In worst case, a carry must propagate from least significant full adder to most significant one • E.g., adding 11... 11 and 00 ... 01 • Total worst-case delay tADD — txYCout + {n — 2) • tdnCout + tdnS • txYCout'- delay from X or Y to COUT in least significant stage • tcinCout- delay from CIN to COUT in middle stages • tans' delay from CIN to S in most significant stage Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 41 / 70 Adders, Subtractors, and ALUs: Subtractors • Binary subtraction is performed similar to binary addition, but using borrows (b;n and bout) between steps, and producing a difference bit d » When subtracting y from x x > y + bin —> bout = 0 x < y + bin —> bout = 1 d = x - y - bjn + 2bout Table 10: Binary subtraction table. bin X y bout d 0 0 0 0 0 0 0 i 1 1 0 1 0 0 1 0 1 i 0 0 1 0 0 1 1 1 0 i 1 0 1 1 0 0 0 1 1 i 1 1 Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 42 / 70 Adders, Subtractors, and ALUs: Subtractors • Logic equations for a full subtracter D = X © Y © BIN BOUT = X' ■ Y + X' ■ BIN + Y ■ BIN • Manipulating logic equations above BOUT = X' ■ Y + X' ■ BIN + Y BOUT' = (X + Y') ■ (X + BIN') = X-Y' + X- BIN' + Y' D = X © y © BIN = X © Y' © BIN' 9 Comparing with equations for a full adder, we can build a full subtractor from a full adder • Any n-bit adder circuit can be made to function as a subtractor by complementing subtrahend and treating carry-in and carry-out signals as borrows with opposite active level • BIN ■{Y' + BIN') ■ BIN' Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 43 / 70 Adders, Subtractors, and ALUs: Subtractors (a) (b) 1 1 X Y X Y 5 74x999 COUT CIN 3 BOUT BIN S D (c) X Y 74x999 BOUT BIN |CH D (d) X Y 74x999 BOUT BIN |0> D b_L„_. X Y 74x999 -0| BOUT BIN |0-D b_L„_: X Y 74x999 -0| BOUT BIN |0-D T Figure 16: Subtracter design using adders: (a) full adder; (b) full subtracter; (c) interpreting 74x999 as a full subtracter; (d) ripple subtracter. Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 44 / 70 Adders, Subtractors, and ALUs: Carry-Lookahead Adders • A faster adder than ripple can be built by obtaining each sum output Si = x; © y; © c; with just two levels of logic • This can be accomplished by expanding q in terms of xo — x,_i, yo - y-,-1, and c0 • More complexity is introduced by expanding XORs • We can keep XORs and design c,- logic using ideas of carry lookahead x y, s, x0 —— Carry Lookahead Logic Figure 17: Structure of one stage of a carry-lookahead adder. Moslem Amiri, Vaclav Prenosil Design of Digital Systems II 45 / 70 Adders, Subtractors, and ALUs: Carry-Lookahead Adders • Adder stage / is said to generate a carry if it produces a c/+i = 1 independent of inputs on xo — x,-_i, yo — yv-i, and cq • This happens when both of addend bits of that stage are 1 gi = Xi ■ yv • Adder stage / is said to propagate carries if it produces a c/+i = 1 in presence of an input combination of xo — x,-_i, yo — yv-i, and Co that causes a q = 1 • This happens when at least one of addend bits of that stage is 1 Pi = Xi + yv • Carry output of a stage can be written as q+i = gv + p/ • q Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 46 / 70 Adders, Subtractors, and ALUs: Carry-Lookahead Adders • To eliminate carry ripple, we recursively expand c-, term for each stage and multiply out to obtain a two-level AND-OR expression ci = go + Po • Co C2 = gl + Pi • Ci = gi +Pi • (go +Po • c0) = gl + Pi • go + Pi • Po • c0 C3 = g2 + P2 • C2 = g2 + P2 • (gl + Pi • gO + Pi • PO • C0) = g2 + P2 • gl + P2 • Pi • gO + P2 • Pi • PO • C0 C4 = g3 + P3 • C3 = g3 + P3 • (g2 + P2 • gl + P2 • Pi • gO + P2 • Pi • PO • C0) = g3 + P3 • g2 + P3 • P2 • gl + P3 • P2 • Pi • gO + P3 • P2 • Pi • PO • C0 Hence, "Carry Lookahead Logic" in Fig. 17 has three levels of delay; one for generate and propagate signals, and two for SOPs shown Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 47 / 70 Adders, Subtractors, and ALUs: MSI Adders • 74x283 uses carry-lookahead technique 74x283 7 CO AO BO 5 SO 4 6 3 A1 B1 A2 B2 A3 B3 S1 1 2 14 S2 13 15 12 S3 10 11 9 C4 Figure 18: Traditional logic symbol for the 74x283 4-bit binary adder. Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 48 / 70 Adders, Subtractors, and ALUs: MSI Adders • 74x283 • It produces g- and p'r since inverting gates are faster o Manipulating half-sum equation hs; — X, © y\ = X,- • y! + x- ■ y, = X) ■ y\ + X) ■ x\ + x\ ■ y, + y, ■ y\ = (*i + yi) ■ (x- + y-) = {xj + y) • fa ■ y/)' = Pi ■ g'i Thus, an AND gate with an inverted input is used instead of an XOR gate to create each half-sum bit Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 49 / 70 Adders, Subtractors, and ALUs: MSI Adders • 74x283 • It creates carry signals using an INVERT-OR-AND structure (= AND-OR-INVERT), which has same delay as a single inverting gate c;+i = ft + Pi ■ ci = Pi ■ gi + Pi ■ ci = Pi ■ (gi + ci) (pi is always 1 when gj is 1) ci = PO ■ (ft + Co) Q = Pi ■ (gi + ci) = Pi • (ft + Po • (go + co)) = Pi • (gi + Po) ■ (gi + go + c0) C3 = P2 ' (g2 + C2) = P2 ' (g2 + Pi ' (ft + Po) ' (ft + ft + C0)) = Pi ■ (ft + Pi) • (ft + ft + Po) • (ft + ft + ft + c0) C4 = P3 ' (ft + C3) = p3 ' (ft + Pi ■ (ft + Pi) ' (ft + ft + Po) ' (ft + ft + ft + C0)) = P3 ' (ft + Pi) ■ (ft + ft + Pi) ' (ft + ft + ft + Po) • (ft + ft + ft + go + co) Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 50 / 70 Adders, Subtractors, and ALUs: MSI Adders Adders, Subtractors, and ALUs: MSI Adders • Propagation delay from CO input to C4 output of '283 is very short, same as two inverting gates • As a result, fast group-ripple adders with more than four bits can be made by cascading carry outputs and inputs of '283s • Total propagation delay from CO to C16 in Fig. 20 is same as that of eight inverting gates 52 / 70 Adders, Subtractors, and ALUs: MSI Adders CO AO SO BO A1 S1 B1 A2 S2 B2 A3 S3 B3 C4 C4 74x283 CO AO SO BO A1 S1 B1 A2 S2 B2 A3 S3 B3 C4 CO AO SO BO A1 S1 B1 A2 S2 B2 A3 S3 B3 C4 CO AO SO BO A1 S1 B1 A2 S2 B2 A3 S3 B3 C4 Figure 20: A 16-bit group-ripple adder. Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 53 / 70 Adders, Subtractors, and ALUs: MSI ALUs • An arithmetic and logic unit (ALU) is a combinational circuit that can perform any of a number of different arithmetic and logical operations on a pair of fa-bit operands • The operation to be performed is specified by a set of function-select inputs 54 / 70 Adders, Subtractors, and ALUs: MSI ALUs Table 11: Functions performed by the 74x181 4-bit ALU. Inputs S3 S2 SI so M = = 0 (arithmetic) M = = 1 (logic) 0 0 0 0 F = A minus 1 plus CIN F = Ä 0 0 0 1 F = A ■ B minus 1 plus CIN F = A'+ B' 0 0 1 0 F = A ■ B' minus 1 plus CIN F = A'+ B 0 0 1 1 F = 1111 plus CIN F = 1111 0 1 0 0 F = A plus (A + B1) plus CIN F = A' -B' 0 1 0 1 F = A ■ B plus (A + S') plus CIN F = B' 0 1 1 0 F = A minus B minus 1 plus CIN F = A m B' 0 1 1 1 F = A+B' plus CIN F = A+B' 1 0 0 0 F = A plus (A + B) plus CIN F = A'■ B 1 0 0 1 F = A plus B plus CIN F = Am B 1 0 1 0 F = A ■ B' plus (A + B) plus CIN F = B 1 0 1 1 F = A+B plus C/M F = A+B 1 1 0 0 F = d plus A plus C/M F = 0000 1 1 0 1 F = /l • B plus /l plus C/M F = A-B' 1 1 1 0 F = /l • S' plus A plus C/M F = A-B 1 1 1 1 F = /l plus C/M F = A Figure 21: Logic symbol for the 74x181 4-bit ALU. Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 55 / 70 Adders, Subtractors, and ALUs: MSI ALUs (a) 74x381 5 50 51 G 6 7 ' 52 P 14 1 0 CIN AO FO BO A1 F1 B1 A2 F2 B2 A3 F3 B3 8 3 4 9 1 2 11 19 18 12 17 16 Figure 22: Logic symbols for 4-bit (b) 74x382 5 50 51 52 OVR CIN COUT AO FO BO A1 F1 B1 A2 F2 B2 A3 F3 B3 13 6 7 15 14 3 8 4 9 1 2 11 19 18 12 17 16 (a) 74x381; (b) 74x382. Moslem Amiri, Vaclav Prenosil Design of Digital Systems II Fall, 2014 56 / 70 Adders, Subtractors, and ALUs: MSI ALUs Table 12: Functions performed by the 74x381 and 74x382 4-bit ALUs. Inputs S2 SI so Function 0 0 0 F = 0000 0 0 1 F = B minus A minus 1 plus CIN 0 1 0 F = A minus B minus 1 plus CIN 0 1 1 F = A plus B plus CIN 1 0 0 F = A®B 1 0 1 F = A + B 1 1 0 F = A - B 1 1 1 F = 1111 Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 57 / 70 Adders, Subtractors, and ALUs: MSI ALUs • '381 provides group-carry-lookahead outputs while '382 provides ripple carry and overflow outputs Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 58 / 70 Adders, Subtractors, and ALUs: Group-Carry Lookahead • '181 and '381 provide group-carry-lookahead outputs that allow multiple ALUs to be cascaded without rippling carries between 4-bit groups • Like 74x283, ALUs use carry lookahead to produce carries internally • However, they also provide G_L and P_L outputs that are carry-lookahead signals for entire 4-bit group • G_L output is asserted if ALU produces a carry-out whether or not there is a carry-in G± = (g3 + p3 • g2 + P3 • P2 • gl + P3 • P2 • Pi • go)' • P_L output is asserted if ALU produces a carry-out if there is a carry-in P-L = (p3 • p2 • Pi • Po)' Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 59 / 70 Adders, Subtractors, and ALUs: Group-Carry Lookahead • When ALUs are cascaded, group-carry-lookahead outputs may be combined in just two levels of logic to produce carry input to each ALU • A lookahead carry circuit performs this operation 74x182 13 3 4 1 2 14 15, 5 6. CO GO C1 PO G1 P1 C2 G2 C3 P2 G3 G P3 P 12 10 7 Figure 23: Logic symbol for the 74x182 lookahead carry circuit. Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 60 / 70 Adders, Subtractors, and ALUs: Group-Carry Lookahead 1 ~B3 II, » Fa, Figure 24: A 16-bit ALU using group-carry lookahead. Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 61 / 70 Adders, Subtractors, and ALUs: Group-Carry Lookahead • '182's carry equations • '182 realizes each of these equations with one level of delay—an INVERT-OR-AND gate q+i = Si + Pi ■ q = (gy + Pi) ■ {gi + q) CI = (G0 + PO) • (GO + CO) C2 = (Gl + PI) • (Gl + GO + PO) • (Gl + GO + CO) C3 = (G2 + P2) • (G2 + Gl + PI) • (G2 + Gl + GO + PO) •(G2 + G1 + G0+C0) Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 62 / 70 Adders, Subtractors, and ALUs: Group-Carry Lookahead • When more than four ALUs are cascaded, they may be partitioned into "supergroups," each with its own '182 • E.g., a 64-bit adder would have four supergroups, each containing four ALUs and a '182 • G_L and P_L outputs of each '182 can be combined in a next-level '182, since they indicate whether the supergroup generates or propagates carries G± = ((G3 + P3) • (G3 + G2 + P2) • (G3 + G2 + Gl + PI) •(G3 + G2 + G1 + G0))' P± = (PO • PI • P2 • P3)' Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 63 / 70 Adders, Subtractors, and ALUs: Adders in Verilog • Verilog has built-in addition (+) and subtraction (—) operators for bit vectors • Bit vectors are considered to be unsigned or two's-complement signed numbers • Actual addition or subtraction operation is exactly the same for either interpretation of bit vectors • Since exactly the same logic circuit is synthesized for either interpretation, Verilog compiler does not need to know how we are interpreting bit vectors • Only handling of carry, borrow, and overflow conditions differs by interpretation, and that is done separately from addition or subtraction itself Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 64 / 70 Adders, Subtractors, and ALUs: Adders in Verilog Table 13: Verilog program with addition of both signed and unsigned numbers. module Vradders(A, B, C, D, S, T, OVFL, COUT); input [7:0] A, B, C, D; output [7:0] S, T; output OVFL, COUT; // 3 and OVFL — signed interpretation assign S = A + B; assign OVFL = (A[7]==B[7]) && (S[7] !=A[7] ); // T and COUT — unsigned interpretation assign {COUT, T} = C + D; endmodule Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 65 / 70 Adders, Subtractors, and ALUs: Adders in Verilog Figure 25: Two ways to synthesize a selectable addition: (a) two adders and a selectable sum; (b) one adder with selectable inputs. Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 66 / 70 Adders, Subtractors, and ALUs: Adders in Verilog • Addition and subtraction are expensive in terms of number of gates required • Most Verilog compilers attempt to reuse adder blocks whenever possible • Tab. 14 is a Verilog module that includes two different additions • Fig. 25(a) shows a circuit that might be synthesized • However, many compilers are smart enough to use approach (b) • An n-bit 2-input multiplexer is smaller than an n-bit adder Table 14: Verilog module that allows adder sharing. module Vraddersh(SEL, A, B, C, D, S); input SEL; input [7:0] A, B, C, D; output [7:0] S; reg [7:0] S; always ® (SEL, A, B, C, D) if (SEL) S = A + B; else S = C + D; endmodule Moslem Amiri, Václav Přenosi Design of Digital Systems II Fall, 2014 67 / 70 Adders, Subtractors, and ALUs: Adders in Verilog Table 15: Alternate version of Tab. 14, using a continuous-assignment statement. module Vraddersc(SEL, A, B, C, D, S); input SEL; input [7:0] A, B, C, D; output [7:0] S; assign S = (SEL) ? A + B ; C + D; endmodule • A typical compiler should synthesize the same circuit for either module of Tab. 14 or 15 Moslem Amiri, Václav Přenosil Design of Digital Systems II Fall, 2014 68 / 70 Adders, Subtractors, and ALUs: Adders in Verilog Table 16: An 8-bit 74x381-like ALU. module Vr74x381(S, A, B, CIN, F, G_L, P_L)j input [2:0] S; input [7:0] A, B; CIN; output [7:0] F; output G_L, P_L; rsg [7:0] F; reg G_L, P_L, GG, GP; reg [7:0] G, P; integer i; always <§ (S or A or B or CIN or G or P or GG or GP) begin for Ci - 0; i <- 7; i - i + 1) begin G[i] = A[i] & B[i] ; P[i] = A [I] | B[i]; end GG = G[0] ; GP = P[0] ; for Ci = 1; i <= 7; 1 = 1 + 1) GG - G[i] (GG & P [i] ) i SP - P[i] k GP; end G_L = 'GG; p L = "GP; case (S) 3'dO F - 8 bO; 3'dl F = B - A - 1 + CIN; 3'd2 F = A - E - 1 + CIN; 3'd3 F - A + B + CIN; 3'd4 F = A ' E; 3'd5 F - A 1 B; 3'd6 F = A 4 B; 3'd7 F - 8 bllllllll; default: F 8'bO; endcase Inputs end endmodule S2 SI so Function 0 0 0 F = 0000 0 0 1 F = B min us A minus 1 plu CIN 0 1 0 F = A min us B minus 1 plu CIN 0 1 1 F = A plus B plus CIN 1 0 0 F = AtBB 1 0 1 F = A+B 1 1 0 F = AB 1 1 1 F = 1111 Fall, 2014 69 / 70 References % John F. Wakerly, Digital Design: Principles and Practices (4th Edition), Prentice Hall, 2005. 70 / 70