Section 7.10 − Datapaths Page 1 of 57.10 DatapathsDatapaths are used in all standard processor and ASIC implementations to perform complex numerical computationor data manipulations.A datapath consists of some temporary storage in addition to arithmetic, logic, and shift units.Example:∑==1001iixsumsum = 0loop:for i = 1 to 100sum = sum + xend looploop:The selector selects either 0 or some outside data as the left operand for the ALU.The right operand for the ALU is always the content of the accumulator.The accumulator is a shift register with a parallel load.SelectorS10AccumulatorS1S0ILIR0ALUMABS1S0Clk123456780InputDatapath schematicInputselectALUcontrolsShiftvaluesAccumulatorcontrolsOutputenable8765432109-bit control wordSection 7.10 − Datapaths Page 2 of 5A more complex datapathSelectorS10ShifterS2S1ILIR0ALUMABS1S023"0"45619InputS01"0"Bus ABus BResult Bus8xmregisterfileRAAREA REBRABWAWE16-18151112-148-107OutputClkInEALUoperationsShiftoperationsReadaddress BOE876543219018 17 16 15 14 13 12 1119 10Readaddress AWriteaddress20-bit control wordMS1S0ALU operstions000Complement A001AND0 1 0 XOR011OR1 0 0 Decrement A101Add1 1 0 Subtract1 1 1 Increment AALU operationsS2S1S0Shift operstions000Pass001Pass010Not used011Not used1 0 0 Shift left1 0 1 Rotate left110Shift right1 1 1 Rotate rightShift operationsSection 7.10 − Datapaths Page 3 of 5Example: A one’s counter that will count the number of 1’s in an input data word and return the result aftercompletion.The one’s-counter controller (FSM) has:• Two input signals, Start and Data = 0, and one output signal, Done.• Eight states• On each clock cycle, the FSM will supply 20 control signals in thecontrol word.DataMaskR1:R2:OcountTempR3:R4:Register assignments0s1s2s3s4s5s6s7Mask = 1Data = 0Start = 1Data = InputOcount = 0Temp = Data AND MaskOcount = Ocount + TempData = Data >> 1Output = OcountStart = 0Done = 1FSMQQnextD000011100111D Flip-Flop excitation table1. Data := input2. Ocount := 03. Mask := 1While Data ≠ 0 repeat4. Temp := Data AND Mask5. Ocount := Ocount + Temp6. Data := Data >> 1End while7. Output := OcountAlgorithm for one’s countControlwordsIEWriteaddressReadaddress AReadAddress BALUoperationShifteroperationOE11R1XXXX020R300AddPass030R20 X Increment Pass 040R4R1R2AND Pass 050R3R3R4Add Pass 060R1R10 Add Shift right 070None R30AddPass1Control words for one’s counterRepeatWhile Data ≠ 0Start, Data=0States Q2 Q1 Q000 01 10 11s00 0 0 0 0 0 0 0 0 0 0 1 0 0 1s10 0 1 0 1 0 0 1 0 0 1 0 0 1 0s20 1 0 0 1 1 0 1 1 0 1 1 0 1 1s30 1 1 1 0 0 1 0 0 1 0 0 1 0 0s41 0 0 1 0 1 1 0 1 1 0 1 1 0 1s51 0 1 1 1 0 1 1 0 1 1 0 1 1 0s61 1 0 1 0 0 1 1 1 1 0 0 1 1 1s71 1 1 0 0 0 0 0 0 0 0 0 0 0 0Next-state tableSection 7.10 − Datapaths Page 4 of 5Using D flip-flops to implement the next-state table, the resulting implementation table is the same as the originalnext-state table.Figure 7.30 (a) Output logic tableWrite address Read address A Read address B ALU ShifterState Q2 Q1 Q0IE WA2 WA1 WA0 WE RA2 RA1 RA0 RE RB2 RB1 RB0 RE M S1 S0S2 S1 S0OEs00 0 0 0 X X X 0 X X X 0 X X X 0 X X X X X X 0s10 0 1 1 0 0 1 1 X X X 0 X X X 0 X X X X X X 0s20 1 0 0 0 1 1 1 X X X 0 X X X 0 1 0 1 0 0 0 0s30 1 1 0 0 1 0 1 X X X 0 X X X 0 1 1 1 0 0 0 0s41 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 0 0s51 0 1 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 0 0 0 0s61 1 0 0 0 0 1 1 0 0 1 1 X X X 0 1 0 1 1 1 0 0s71 1 1 0 X X X 0 0 1 1 1 X X X 0 1 0 1 0 0 0 1Figure 7.30 (b) Output equations0102120101012021012012QQQQQQWEQQQQWAQQQQWAQQWAQQQIE′+′+′=′+′=′+=′′=′′=1001210QREARAAQRAARAA====12001020QQREBRABQRABQRAB′==′==01200121200210101QQQOESQQQSSSQQSQQM==′===′=+=00011110Data=000110001000 010000 0100001451011100 011100 0113276001 01001089011100 011101112 13 141510100001101 110101 1100001451011000 100000 1113276101 11011089111000 100101112 13 1415Q2 = 0 Q2 = 1Q0Q1StartQ2(next), Q1(next), Q0(next)Figure 7.29 (a) Karnaugh Map representation020101201200101201102120122)0()()0()()(QQDataQQStartQQQQQQnextQQQDataQQQQQnextQQQQQQQQnextQ′=+′′+′′+′′=′=+′′+′=′+′+′=Figure 7.29 (b) Next-state equationsSection 7.10 − Datapaths Page 5 of 5Example: Question 7.20: For the datapath in Figure 7.26, develop a field-insertion algorithm and control words forall the statements. Assume that the datapath is 8 bits wide and that the field-insertion algorithm inserts the fourleast-significant bits of the source word into the middle of the destination word: for example, your field-insertion algorithm should take two words, A=a7a6a5a4a3a2a1a0 and B=b7b6b5b4b3b2b1b0, and generate theresultant word C=b7b6a3a2a1a0b1b0 by replacing b5b4b3b2 with a3a2a1a0.Solution:CtrwordsIEWriteaddressReadaddress AReadaddress BALUoperationShifteroperationOE Comment Register content11 R1X X X X 0 Load A a7a6a5a4a3a2a1a020 R1R10 Add Shift left 0 Shift left A 4 bits a3a2a1a0000030 R1R10 Add Shift left 040 R1R10 Add Shift left 050 R1R10 Add Shift left 060 R1R10 Add Rotate right 0 Rotate right A 4 bits 0000a3a2a1a070 R1R10 Add Rotate right 080 R1R10 Add Rotate right 090 R1R10 Add Rotate right 010 1 R2X X X X 0 Load B b7b6b5b4b3b2b1b011 0 R2R20 Add Rotate right 0 Rotate right B 2 bits b1b0b7b6b5b4b3b212 0 R2R20 Add Rotate right 013 0 R2R20 Add Shift right 0 Shift right B 4 bits 0000b1b0b7b613 0 R2R20 Add Shift right 013 0 R2R20 Add Shift right 013 0 R2R20 Add Shift right 014 0 R2R20 Add Rotate left 0 Rotate left B 4 bits b1b0b7b6000015 0 R2R20 Add Rotate left 016 0 R2R20 Add Rotate left 017 0 R2R20 Add Rotate left 018 0 R1R1R2OR Pass 0A ← A OR Bb1b0b7b6a3a2a1a019 0 R1R10 Add Rotate left 0 Rotate left A 2 bits b7b6a3a2a1a0b1b020 0 R1R10 Add Rotate left 021 0 None R10 Add Pass 1 Output AControl words for the field-insertion