Computer arithmeticsSlide 3-1Chapter 3Computer ArithmeticsTopics:• Adder• Multiplier• Division •ALUComputer arithmeticsSlide 3-2Basic data types, operations Signed, unsigned integer numbers Floating point numbers Bit vectorsConsider Bit vectors firstComputer arithmeticsSlide 3-3Bit vectorsInstruction sets offer instructions for manipulating bit vectors shift operations test Bit i, set Bit i, clear Bit i copy Bits, search for patternsComputer arithmeticsSlide 3-4Shifting operationsOperation: shift an operand by kdigits to the left/rightComputers offer two types of shift operations Logic shift Arithmetic shiftComputer arithmeticsSlide 3-5Shifting instructionssrl/sll(shift right/left logical)•Shift by kdigits• Fill empty digits with “0“• Used to implement multiplication/division of unsigned numberssra/sla(shift right/left arithmetic)•Shift by kdigits• Arithmetic shift preserves sign bit:sra: copy MSB into empty digitssla: do not shift MSBComputer arithmeticsSlide 3-6),,...,(),...,( 002011aaaasllnn−−=),...,,(),...,(110110aaaasrlnn−−=),...,,(),...,( 0031011aaaaaslannn−−−=),...,,(),...,(111011aaaaasrannn−−−=One Bit shifting instructionsComputer arithmeticsSlide 3-7sra1(an-1,…,a0) = (an-1, an-1,…,a1)[sra1(an-1,…,a0)] = ⎣[an-1,…,a0]/2⎦sra: implements division by 2 without remaindersla1(an-1,…,a0) = (an-1, an-3,…,a0,0)sla: implements multiplication by 2Arithmetic shift by one Bitfloor(x): largest integer being smaller or equal than xComputer arithmeticsSlide 3-8Arithmetic Shift by 1 BitObservation: Integer multiplication and division by 2ncan beimplement by performing shiftsHow to realize shift operations in hardware?•[sla1(an-1,…,a0)] = 2 x [an-1,…,a0]if an-1= an-2•sla1sets an overflow - flag if an-1≠ an-2Computer arithmeticsSlide 3-9Implementing shift operations in HardwareMUX01MUX01MUX01MUX01c0d0s0c1d1c2d2cn-1dn-1...How to implement shift by nBit?2 : 1 – multiplexer: shift by 0 or 1 Bitn: 1 – multiplexer: shift by 0, 1, …, n-1 BitsBarrel-shifter implementing logic left shift by 1 or 0 BitBarrel-shifter: logic circuit for performing shifting operations Computer arithmeticsSlide 3-10Arithmetic Operations Addition  Subtraction  Comparison Multiplication DivisionNote:Hardware performing arithmetic operations must provide a mechanism for detecting overflows, e.g. to set the overflow status BitComputer arithmeticsSlide 3-11Half AdderExample: circuit for adding two 1-Bit numbersHalf adder:Input signals: a, bOutput signals: s (sum), co (carry out)abHalf addersco1011010101100000cosbaComputer arithmeticsSlide 3-12Full AdderExample: circuit for three 1-Bit numbersFull adder:Input signals: a, b, ci(carry in)Output signals: s (sum), co (carry out)1111110011101010100110110010100110000000coscibaabciFull adderscoXOR3 - gate a b c sComputer arithmeticsSlide 3-13Ripple-Carry-Addera3b3s3ci,3a2b2s2ci,2co,2a1b1s1ci,1co,1a0b0s0co,3co,0Full adder Full adder Full adder Half adder001101011000111Example: 4-bit adderAn n - Bit adder can be build using one half adder and n -1 full adders.Carry “ripples” through chain of adders: ”ripple carry adder“Overflow detection for unsigned numbers: overflow if co,3= 1Delay increases linearly with number of adders!Computer arithmeticsSlide 3-14Overflow detection for numbers in 2’s complementAddition A + B: consider carryinand carryoutfor last columnA: 0 …B: 0 …0 00 … ⇒ O.K.Observation: the result is correct if carry-in and carry-out for the lastcolumn have the same value!1. A≥0, B≥0A: 0 …B: 0 …0 11 … ⇒ overflowA: 1 …B: 1 …1 11 … ⇒ O.K.2. A<0, B<0A: 1 …B: 1 …1 00 … ⇒ overflowA: 0 …B: 1 …0 01 … 3. A≥0, B<0: overflow cannot occur!A: 0 …B: 1 …1 10 …Computer arithmeticsSlide 3-15Addition/Subtraction Hardware for Two’s Complementa - b = a + (-b)a b s + a b co+ cia b + a b+ 0 1 add/subtract a3b3b30 1 a2b2b20 1 a1b1b10 1 a0b0b0s3Overflow Subtraction implemented by adding the two’s complement of bsubtract = 1⇒ adds 1 cicicocococis s s s2s1s0MuxMux Mux MuxComputer arithmeticsSlide 3-16Carry-Select AdderProblem of large ripple-carry-adders:Time for calculating the carry out of the final adder grows linearly with the size of the adderCarry-Select Adder:Basic Idea:Split numbers into blocks. For each block perform 2 additions in parallel:1. one assuming that the carry input is 02. one assuming that the carry input is 1When the carry is finally available the correct results are selectedComputer arithmeticsSlide 3-17b4a4b5a5b6a6b7a7b0a0b1a1b2a2b3a3c0s3s2s1s0s7s6s5s4c8b4a4b5a5b6a6b7a7b0a0b1a1b2a2b3a3c0s3s2s1s0c4s7s6s5s4c8b4a4b5a5b6a6b7a7b4a4b5a5b6a6b7a710b0a0b1a1b2a2b3a3c0s3s2s1s0c4s4s5s6s7b4a4b5a5b6a6b7a7b4a4b5a5b6a6b7a7c810b0a0b1a1b2a2b3a3c0s3s2s1s0c4Carry-Select AdderSimple Carry-Select Adder:Data arrival time (tar) of c8assuming unit delay for full adders and multiplexers:Ripple carry: tar= 8Carry select: tar= 5 Computer arithmeticsSlide 3-18Carry-Select AdderFor further speedup large adders can be divided into more than two parts:c12: tar= 6Roughly twice the hardware effort of a ripple carry adders4s5s6s7b4a4b5a5b6a6b7a7b4a4b5a5b6a6b7a7c810b0a0b1a1b2a2b3a3c0s3s2s1s0c4s8s9s10s11b8a8b9a9b10a10b11a11b8a8b9a9b10a10b11a11c1210Computer arithmeticsSlide 3-19Carry-Lookahead Addersi= ai⊕ bi⊕ cici+1= aibi+ aici+ bici= aibi+ ci(ai+ bi)= aibi+ ci(ai⊕ bi)Carry generate: gi= aibiCarry propagate: pi= ai⊕bigenerates carry ciif a = b = 1 carryinis propagated to carryout if a⊕bcarryoutcan be expressed using generate and propagate: ci+1= gi+ cipiBasic Idea: calculate carry-signal for each stage directly from the input signals (and not from the carries of the predecessor stages)Computer arithmeticsSlide 3-20Carry-LookaheadBoolean equations for determining carry signals:c1= g0+ p0c0c2= g1+ p1c1= g1+ p1g0+ p1p0c0c3= g2+ p2c2= g2+ p2g1+ p2p1g0+ p2p1p0c0c4= g3+ p3c3= g3+ p3g2+ p3p2g1+ p3p2p1g0+ p3p2p1p0c0…Each equation can be implemented using two levels of logic gatesTwo-level circuit for calculating cnrequires an AND gate with n + 1 inputs!Computer arithmeticsSlide 3-21Carry-LookaheadCircuits for calculating carry signalsNumber of gate input growscibiaic0c0c0c0p0p0p0p0g0g0g0g0c1p1p1p1p1p1p1g1g1g1c2p2p2p2p2p2p2g2g2c3p3p3p3p3g3c4Circuit for calculating generate, propagate, and sumpigisici+1= aibi+ ci(ai⊕ bi) si= ai⊕ bi⊕ ciComputer arithmeticsSlide 3-22Carry-LookaheadIn general not more