EECS 150 - Components and Design Techniques for Digital Systems Lec 25 – Division & ECCDivision32-bit DIVIDE HARDWARE Version 1Divide Alg. Version 1Example: initial conditionExample: iter 1, step 1Example: iter 1, step 2bExample: iter 1, step 3Example: Iter 2, Steps 1,2b,3Example: Iter 3, Steps 1,2b,3Example: Iter 4, Steps 1,2a,3Example: Iter 5, Steps 1,2a,3Version 1: Division 7/2Observations on Divide Version 1DIVIDE HARDWARE Version 2Divide Alg. Version 2Example V2: 7/2 initial conditionsExample V2: 7/2 iter 1AnnouncementsObservations on Divide Version 2DIVIDE HARDWARE Version 3Divide Algorithm Version 3Observations on Divide Version 3Error Correction Codes (ECC)Correcting Code ConceptSimple Error Detection CodingHamming Error Correcting CodeHamming Code ExampleInteractive QuizSlide 30SummaryMotivation for Booth’s AlgorithmBooth Multiplier: an IntroductionRecoding (Encoding) ExampleBooth Multiplication ExampleBooth’s Alg: Implementation ApproachBooth’s Example (2 x 7)Booth’s Example (2 x -3)EECS 150 - Components and Design Techniques for Digital Systems Lec 25 – Division & ECCDavid CullerElectrical Engineering and Computer SciencesUniversity of California, Berkeleyhttp://www.eecs.berkeley.edu/~cullerhttp://www-inst.eecs.berkeley.edu/~cs15012/2/2004EECS 150, Fa04, Lec 25-div & errors2Division 1001 QuotientDivisor 1000 1001010 Dividend –1000 10 101 1010 –1000 10 Remainder (or Modulo result)•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 + Remaindersizeof(dividend) = sizeof(quotient) + sizeof(divisor)•3 versions of divide, successive refinement12/2/2004EECS 150, Fa04, Lec 25-div & errors332-bit DIVIDE HARDWARE Version 1•64-bit Divisor register, 64-bit adder/subtractor, 64-bit Remainder register, 32-bit Quotient registerRemainderQuotientDivisoradd/subShift RightShift LeftWriteControl32 bits64 bits64 bits12/2/2004EECS 150, Fa04, Lec 25-div & errors42b. Restore the original value by adding the Divisor register to the Remainder register, &place the sum in the Remainder register. Alsoshift the Quotient register to the left, setting the new least significant bit to 0.Divide Alg. Version 1n+1 steps for n-bit Quotient & Rem. Remainder Quotient Divisor00000111 0000 00100000 710 210Test RemainderRemainder < 0Remainder 01. Subtract the Divisor register from the Remainder register, and place the result in the Remainder register.2a. Shift the Quotient register to the left setting the new rightmost bit to 1.3. Shift the Divisor register right 1 bit.Done Yes: n+1 repetitions (n = 4 here)Start: Place Dividend in Remaindern+1repetition? No: < n+1 repetitions12/2/2004EECS 150, Fa04, Lec 25-div & errors5Example: initial conditionRemainder/DividendQuotientDivisoradd/subShift RightShift LeftWriteControl00000010 00000000 011112/2/2004EECS 150, Fa04, Lec 25-div & errors6Example: iter 1, step 1•1: rem <= rem – div; [7 – 32 --> -25]•Check rem <0?Remainder/DividendQuotientDivisoradd/subShift RightShift LeftWriteControl00000010 00000000 01111110 011112/2/2004EECS 150, Fa04, Lec 25-div & errors7Example: iter 1, step 2b•rem <= rem + div;•Shift Q left, bringing in 0Remainder/DividendQuotientDivisoradd/subShift RightShift LeftWriteControl00000010 00000000 011112/2/2004EECS 150, Fa04, Lec 25-div & errors8Example: iter 1, step 3•Shift div rightRemainder/DividendQuotientDivisoradd/subShift RightShift LeftWriteControl0000000100000000 011112/2/2004EECS 150, Fa04, Lec 25-div & errors9Example: Iter 2, Steps 1,2b,3•1: rem <= rem – div; [7 – 16 --> -9]•2. check rem <0? rem <= rem + div; sll Q, Q0=0•3. srl divRemainder/DividendQuotientDivisoradd/subShift RightShift LeftWriteControl0000 011100000001000000001000000012/2/2004EECS 150, Fa04, Lec 25-div & errors10Example: Iter 3, Steps 1,2b,3•1: rem <= rem – div; [7 – 8 --> -1]•2. check rem <0? rem <= rem + div; sll Q, Q0=0•3. srl divRemainder/DividendQuotientDivisoradd/subShift RightShift LeftWriteControl0000000001000000 011112/2/2004EECS 150, Fa04, Lec 25-div & errors11Example: Iter 4, Steps 1,2a,3•1: rem <= rem – div; [7 – 4 --> 3]•2. check rem <0? sll Q, Q0=1•3. shr divRemainder/DividendQuotientDivisoradd/subShift RightShift LeftWriteControl000001000000 01110000 0011000000010000001012/2/2004EECS 150, Fa04, Lec 25-div & errors12Example: Iter 5, Steps 1,2a,3•1: rem <= rem – div; [3 – 2 --> 1]•2. check rem <0? sll Q, Q0=1•3. shr divRemainder/DividendQuotientDivisoradd/subShift RightShift LeftWriteControl000000100000 00110000 0001000100110000000112/2/2004EECS 150, Fa04, Lec 25-div & errors13Version 1: Division 7/2Iteration step quotientdivisor remainder0 Initial values 0000 0010 0000 0000 01111 1: rem=rem-div 0000 0010 0000 1110 01112b: rem<0 +div, sll Q, Q0=0 0000 0010 0000 0000 01113: shift div right 0000 0001 0000 0000 01112 1: rem=rem-div 0000 0001 0000 1111 01112b: rem<0 +div, sll Q, Q0=0 0000 0001 0000 0000 01113: shift div right 0000 0000 1000 0000 01113 1: rem=rem-div 0000 0000 1000 1111 11112b: rem<0 +div, sll Q, Q0=0 0000 0000 1000 0000 01113: shift div right 0000 0000 0100 0000 01114 1: rem=rem-div 0000 0000 0100 0000 00112a: rem0 sll Q, Q0=1 0001 0000 0100 0000 00113: shift div right 0001 0000 0010 0000 00115 1: rem=rem-div 0001 0000 0010 0000 0001 2a: rem0 sll Q, Q0=1 0011 0000 0010 0000 00013: shift div right 0011 0000 0001 0000 000112/2/2004EECS 150, Fa04, Lec 25-div & errors14Observations on Divide Version 1•1/2 bits in divisor always 0 1/2 of 2n-bit adder is wasted 1/2 of 2n-bit divisor is wasted•Instead of shifting divisor to right, shift remainder to left?•1st step cannot produce a 1 in quotient bit (otherwise quotient 2n) switch order to shift first and then subtract, can save 1 iteration12/2/2004EECS 150, Fa04, Lec 25-div & errors15DIVIDE HARDWARE Version 2•32-bit Divisor register, 32-bit ALU, 64-bit Remainder register, 32-bit Quotient registerRemainderQuotientDivisoradd/subShift LeftWriteControl32 bits32 bits64 bitsShift Left12/2/2004EECS 150, Fa04, Lec 25-div & errors16Divide Alg. Version 2Remainder Quotient Divisor00000111 0000 0010 710 210 3b. Restore the original value by adding the Divisor register to the left half of the Remainder register, &place the sum in the left
View Full Document
Unlocking...