Information about 5.digital design - arithmetic circuits

Human representation Humans use a signed-magnitude system: we add + or - in front of a magnitude to indicate the sign. Example:+2,-3,+10,-15.

Unsigned integer representation 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 carries 0 1 1

Signed integer representation Signed magnitude One’s complement Two’s complement

Signed integer representation(Cont.) Signed magnitude Humans use a signed-magnitude system: we add + or - in front of a magnitude to indicate the sign. We could do this in binary as well, by adding an extra sign bit to the front of our numbers. A “1” in the high-order bit (or left-most bit) indicates a negative number and the rest of the remaining bits represent the number itself. Ex: +1 and -1 in an 8-bit word would be 0 0 0 0 0 0 0 1 (+1) 1 0 0 0 0 0 0 1 (-1)

Signed integer representation(Cont.) Signed magnitude addition(Cont.) 1 1 1 1 carries 0 1 0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0

Signed integer representation(Cont.) Signed magnitude addition(Cont.) Overflow Overflow in signed numbers occurs when the sign of the result is incorrect. The sign bit is used only for the sign, so we can’t carry into it. 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 carries 1 1 (79) 1 1 (99) 1 0 (50) 79 + 99 =/= 50

Signed integer representation(Cont.) Signed magnitude subtraction 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 2 borrows 0 1 1 (99) 1 1 1 (79) 1 0 0 (20) 99 – 79 = 20

Signed integer representation(Cont.) One’s complement A different approach, one’s complement, negates numbers by complementing each bit of the number. We keep the sign bits: 0 for positive numbers, and 1 for negative. The sign bit is complemented along with the rest of the bits. Examples: 11012 = 1310 0 1101 = +1310 1 0010 = -1310 (a 4-bit unsigned number) (a positive number in 5-bit one’s complement) (a negative number in 5-bit one’s complement) 01002 = 410 0 0100 = +410 1 1011 = -410 (a 4-bit unsigned number) (a positive number in 5-bit one’s complement) (a negative number in 5-bit one’s complement)

Signed integer representation(Cont.) One’s complement(Cont.) Flip the bits for all negative numbers. The last carry is added to the sum. 1 1 0 1 0 1 1 1 carries 0 1 0 1 1 1 (23) 1 1 0 1 1 0 (-9) 0 0 1 1 0 1 + 1 0 0 0 0 1 1 1 0 (14) 1 0 1 0

Signed integer representation(Cont.) Two’s complement Flip the bits for all negative numbers. Add 1. 23 = 00010111 -23 = 11101000 + 1 = 11101001 0 0 0 0 1 0 0 1 (9) 1 1 1 0 1 0 0 1 (-23) 1 1 1 1 0 0 1 0 (-14) Two other equivalent ways to negate two’s complement numbers: - You can subtract an n-bit two’s complement number from 2n. - You can complement all of the bits to the left of the rightmost 1. Why 2’s-Complement Is the Universal Choice?

Half and full adder Half Adder A B S C 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Full Adder A B C0 A B S C C1 S

Adder Ci 0 0 0 0 1 1 1 1 1 0011 + 0011 0110 A 0 0 1 1 0 0 1 B 0 1 0 1 0 1 1 Co 0 0 0 1 0 1 1 S 0 1 1 0 1 0 1 A B Cin S A B Cin A B A B Ci A B Ci A B Ci A B Ci Co S Co S Co S Co S Cout Unfortunately this has a very large propagation time for 32 or 64 bit adds

Carry look-ahead adder Carry look-ahead logic Si= Ai xor Bi xor Ci Ci+1= Ai Bi + Ai Ci + Bi Ci = Ai Bi + Ci (Ai + Bi) -Gi = Ai Bi -Pi = Ai + Bi Ci+1= Gi + Ci Pi Re-express the carry logic as follows: – C1 = G0 + P0 C0 – C2 = G1 + P1 C1 = G1 + P1 G0 + P1 P0 C0 – C3 = G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0 – C4 = G3 + P3 C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 C0

Carry Look-ahead adder(Cont.) Carry Look-ahead implementation Adder with propagate and generate outputs Ai Bi Pi @ 1 gate delay Ci Si @ 2 gate delays increasingly complex logic for carries Gi @ 1 gate delay C0 P0 G0 C0 P0 P1 G0 P1 G1 C1 C2 C0 P0 P1 P2 G0 P1 P2 G1 P2 G2 C0 P0 P1 P2 P3 G0 P1 P2 C3 P3 G1 P2 P3 G2 P3 G3 C4

Carry look-ahead adder(Cont.) Carry look-ahead implementation(Cont.) Cin Cin A0 B0 S0 @2 C1 @2 + A1 B1 A0 B0 A2 B2 + A3 B3 S0 @2 + S1 @4 + S2 @4 + S3 @4 C1 @3 A1 B1 S1 @3 C2 @4 + + C2 @3 A2 B2 S2 @5 C3 @6 + C3 @3 S3 @7 Cout @8 A3 B3 C4 @3 C4 @3

Carry look-ahead adder(Cont.) Cascaded carry look-ahead logic 4 four-bit adders with internal carry lookahead Second level carry lookahead unit extends lookahead to 16 bits 4 4 4 4 4 4 4 4 A[15-12] [15-12] B C12 4-bit Adder P G 4 S[15-12] @8 @2 P3 C16 C4 @4 @3 G3 A[11-8] B[11-8] C8 4-bit Adder P G 4 S[11-8] @8 @2 @5 C3 P2 @3 G2 A[7-4] B[7-4] C4 4-bit Adder P G 4 S[7-4] @7 @5 C2 @2 P1 @3 G1 A[3-0] B[3-0] C0 4-bit Adder @0 P G 4 S[3-0] @4 @4 C1 @2 P0 @3 G0 C0 Lookahead Carry Unit P3-0 G3-0 @3 @5 C0 @0

Carry-select adder Redundant hardware to make carry calculation go faster – Compute two high-order sums in parallel while waiting for carry-in – One assuming carry-in is 0 and another assuming carry-in is 1 – Select correct result once carry-in is finally computed C8 1 C8 five 2:1 mux 4-bit adder [7:4] 4-bit adder [7:4] 0 1 0 1 0 C8 S7 10 S6 1 0 1 0 S5 S4 adder high adder low C4 C0 4-Bit Adder [3:0] S3 S2 S1 S0

Adder/subtractor Use an adder to do subtraction thanks to 2s complement representation – A – B = A + (– B) = A + B' + 1 – Control signal selects B or 2s complement of B A2 B2B2' A3 B3B3' 0 1 A B Sel A1 B1B1' 0 1 Sel B A A0 B0B0' 0 1 Sel B A 0 1 Sel B A Cout Cin Cout Cin Cout Cin Sum Sum Sum Sum S3 Overflow Cout Cin S2 S1 S0 Add' Subtract

Adder/subtractor(Cont.)

Serial adder Serial operations: slower, smaller. Parallel operations: faster but requires more chip area The circuit shown uses two shift registers for operands A(3:0) and B(3:0). A full adder, and one more flip flop (for the carry) is used to compute the sum. The result is stored in the a register and the final carry in the flip-flop Load/Right Shift Registers Serial In A FA A3 A2 A1 A0 B Parallel Load Cin Serial In Sum Cout B3 B2 B1 B0 Parallel Load (Clock and Load/Shift Control not shown) Q D CP With the operands and the result in shift registers, a tree of full adders can be used to add a large number of operands. Used as a common digital signal processing technique.

Multiplication 01001101 10110011 ( 7710) (17910) 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 (13,78310)

Multiplication(Cont.) Signed multiplication Remember for 2’s complement numbers MSB has negative weight: N 2 X xi 2i xn 1 2 n 1 i 0 ex: -6 = 110102 = 0•20 + 1•21 + 0•22 + 1•23 - 1•24 = 0 + 2 + 0 + 8 - 16 = -6 Therefore for multiplication: a) subtract final partial product b) sign-extend partial products

Multiplication(Cont.) Signed multiplication(Cont.) multiplicand 1101 (-3) multiplier * 1011 (-5) + 1111 1101 +(-3) + + 111 11010 +(-6) - Note: 2s complement Sign extension 00 000000 1 1101000 -(-24) 00001111 (15) product of 2 n-bit numbers is an 2n-bit number – sum of n n-bit partial products

Multiplication(Cont.) Combinational multiplier A3 A1 A0 B3 B2 B1 B0 A2 B0 A2 B0 A1 B0 A0 B0 A3 B1 A2 B1 A1 B1 A0 B1 A3 B2 A2 B2 A1 B2 A0 B2 A3 B3 S7 A2 A2 B3 A1 B3 A0 B3 S6 S5 S4 S3 S2 S1 S0

Multiplication(Cont.) Array multiplier Generates all n partial products simultaneously. b3 0 b2 0 b1 0 b0 0 Each row: n-bit adder with AND gates a0 0 bj P0 sum in a1 ai 0 P1 a2 0 P2 a3 carry out FA carry in sum out 0 P3 P7 P6 P5 P4 What is the critical path?

Multiplication(Cont.) Carry-save• additionthree numbers, Example: sum Speeding up multiplication is a matter of speeding up the summing of the partial products. “Carry-save” addition can help. Carry-save addition passes (saves) the carries to the output, rather than propagating them. carry-save add carry-propagate add 310 = 0011, 210 = 0010, 310 = 0011 310 0011 + 210 0010 c 0100 = 410 s 0001 = 110 carry-save add 310 0011 c 0010 = 210 s 0110 = 610 1000 = 810 In general, carry-save addition takes in 3 numbers and produces 2. Whereas, carry-propagate takes 2 and produces 1. With this technique, we can avoid carry propagation until final addition

Multiplication(Cont.) Carry-save circuits CSA FA c sc FA sc FA sc FA sc FA sc FA sc FA sc FA 0 x2 sc CSA When adding sets of numbers, carry-save can be used on all but the final sum. Standard adder (carry propagate) is used for final sum. x1 CSA x0 CSA CPA

Multiplication(Cont.) Array multiplier using carry-save adder b3 0 b2 0 b1 0 b0 0 bj a0 0 0 0 sum in 0 0 ai P0 a1 0 0 P1 a2 0 0 carry out P2 a3 0 P3 1 0 P7 P6 P5 P4 Fast carrypropagate adder FA sum out carry in

Multiplication(Cont.) Array multiplier using carry-save adder(Cont.) Another representation Sum In X Cin Building block: full adder + and Y FA A B CO CI S A3 B0 Sum Out Cout B1 A3 B1 C B2 A3 B2 C B3 S S C S S S A3 B3 A2 B3 A1 B3 S S S C C S S C S A0 B1 C S A0 B2 C S S C P7 A0 B0 A0 B3 S A1 B0 A1 B1 A1 B2 C A0 C A2 B1 A2 B2 C S A1 A2 B0 A3 B0 C Add CPA A2 P6 P5 P4 P3 P2 4 x 4 array of building blocks P1 P0

Multiplication(Cont.) Signed array multiplier b3 0 b2 0 b1 0 b0 0 a0 Implicit Sign extension 0 P0 a1 0 P1 a2 0 P2 - - - - a3 0 P3 P7 P6 P5 P4

Multiplication(Cont.) “Shift and Add” multiplier P B n-bit shift registers + n-bit adder 0 1 0 A n-bit register Cost n, = n clock cycles. What is the critical path for determining the min clock period? Sums each partial product, one at a time. In binary, each partial product is shifted versions of A or 0. Control Algorithm: 1. P 0, A multiplicand, B multiplier 2. If LSB of B==1 then add A to P else add 0 3. Shift [P][B] right 1 4. Repeat steps 2 and 3 n-1 times. 5. [P][B] has product.

Multiplication(Cont.) “Shift and Add” signed multiplier P B n-bit shift registers + n-bit adder 0 1 0 A n-bit register Signed extend partial product at each stage Final step is a subtract

Multiplication(Cont.) Multiplication by constant

Multiplication(Cont.) Multiplication using subtraction 7*6=(-8+1)*6 0111*0110=(1000-0001)*0110

0001001 000100 00010 0001 000 00 0 Division 1000 1001010 1 1 10 10 101 100 1010 1001 1000 1000 10 At each step, determine one bit of the quotient – If current “remainder” larger than division, subtract and set Q bit to 1 – Otherwise, bring down a bit of the dividend and set Q bit to 0 Dividend = Quotient x Divisor + Remainder

Comparators

ALU ALU stands for: Arithmetic Logic Unit ALU is a digital circuit that performs Arithmetic (Add, Sub, . . .) and Logical (AND, OR, NOT) operations.

ALU(Cont.) Typical schematic symbol of an ALU A and B: the inputs to the ALU (operands) R: Output or Result F: Code or Instruction from the Control Unit (as op-code) D: Output status; it indicates cases A such as: •carry-in •carry-out, •overflow, F •division-by-zero •And . . . B ALU R D

ALU(Cont.) ALU example

Please read about: Booth multiplier. Modified Booth multiplier. Wallace multiplier.

thanks digital design

Arithmetic Functions and Circuits Chapter 5. Digital Circuits 2 Overview Iterative combinational circuits ... ENG241 Digital Design Week #5 Arithmetic ...

Read more

... "ENG241 Digital Design Week #5 Arithmetic Circuits ... Arithmetic Functions and Circuits Chapter 5. Digital Circuits 2 Overview Iterative combinational ...

Read more

EECS 141 – S02 Arithmetic Circuits ... 5 Digital Integrated Circuits Arithmetic © Prentice Hall 2000 ... Bit-Sliced Design Bit 3 Bit 2 Bit 1

Read more

Arithmetic Building Blocks Chapter 11 Rabaey. ... Bit-Sliced Design Bit 3 Bit 2 Bit 1 ... Digital Integrated Circuits Arithmetic © Prentice Hall 1995

Read more

5 Digital Kommunikationselektronik, TNE027 Lecture on VHDL 17 S <= Sum(15 DOWNTO 0) ; The lower 16 bits of Sum are assigned to S. Overflow <= Sum(16) XOR X ...

Read more

Representations are crucial to an engineer's design of digital circuits. ... The bits from the microprogram control the arithmetic logic unit, ...

Read more

© Digital Integrated Circuits2nd Arithmetic Circuits Digital Integrated Circuits A Design Perspective ... 5 © Digital Integrated Circuits2nd Arithmetic ...

Read more

EECS 141 – F01 Arithmetic Circuits ... Bit-Sliced Design Bit 3 Bit 2 Bit 1 ... 5 Digital Integrated Circuits Arithmetic © Prentice Hall 2000

Read more

Arithmetic circuits form an important class of circuits in ... multiplier circuits and ... can be implemented as shown in figure 5.5. DIGITAL SYSTEM DESIGN 5.8

Read more

A Design Perspective Arithmetic Circuits Jan M. Rabaey Anantha Chandrakasan Borivoje Nikolic ... 5 © Digital Integrated Circuits2nd Arithmetic Circuits

Read more

## Add a comment