CPE/EE 422/522 Advanced Logic Design L16Review: State Machine ChartsComponents of SM chartsSM BlocksEquivalent SM BlocksEquivalent SM Charts for Comb NetworksBlock with FeedbackSlide 8Converting a State Graph to an SM ChartNetworks for Arithmetic OperationsSlide 11State Graphs for Control NetworksConstraints on Input LabelsConstraints on Input Labels (cont’d)Slide 15Block Diagram of a Binary MultiplierMultiplication ExampleState Graph for Binary MultiplierBehavioral VHDL ModelBehavioral VHDL Model (cont’d)Multiplier Control with CounterMultiplier Control with Counter (cont’d)Slide 23Operation of a Multiplier Using CounterArray MultiplierArray Multiplier (cont’d)Slide 27Multiplication of Signed Binary NumbersSlide 292’s Complement MultiplierState Graph for 2’s Complement MultiplierFaster MultiplierState Graph for Faster MultiplierBehavioral Model for Faster MultiplierSlide 35Command File and SimulationTest Bench for Signed MultiplierCPE/EE 422/522Advanced Logic DesignL16Electrical and Computer EngineeringUniversity of Alabama in Huntsville14/01/19 UAH-CPE/EE 422/522 AM 2Review: State Machine Charts•SM chart or ASM (Algorithmic State Machine) chart•Easier to understand the operation of digital system by examining of the SM chart instead of equivalent state graph•SM chart leads directly to hardware realization14/01/19 UAH-CPE/EE 422/522 AM 3Components of SM charts14/01/19 UAH-CPE/EE 422/522 AM 4SM BlocksSM chart is constructed from SM blocksState S1 is entered => Z1 and Z2 become 1if X1=0 Z3 and Z4 become 1if X1=1 and X3=0 Z5 become 114/01/19 UAH-CPE/EE 422/522 AM 5Equivalent SM Blocks14/01/19 UAH-CPE/EE 422/522 AM 6Equivalent SM Charts for Comb Networks14/01/19 UAH-CPE/EE 422/522 AM 7Block with Feedback14/01/19 UAH-CPE/EE 422/522 AM 8Equivalent SM Blocks14/01/19 UAH-CPE/EE 422/522 AM 9Converting a State Graph to an SM Chart14/01/19 UAH-CPE/EE 422/522 AM 10Networks for Arithmetic OperationsCase Study: Serial Adder with Accumulator14/01/19 UAH-CPE/EE 422/522 AM 11Networks for Arithmetic OperationsSerial Adder with Accumulator14/01/19 UAH-CPE/EE 422/522 AM 12State Graphs for Control Networks•Use variable names instead of 0s and 1s–E.g., XiXj/ZpZq•if Xi and Xj inputs are 1, the outputs Zp and Zq are 1 (all other outputs are 0s)–E.g., X = X1X2X3X4, Z = Z1Z2Z3Z4•X1X4’/Z2Z3 == 1 - - 0 / 0 1 1 014/01/19 UAH-CPE/EE 422/522 AM 13Constraints on Input Labels•Assume: I – input expression => we traverse the arc when I=1Assures that at most one input label can be 1 at any given timeAssures that at least one input label will be 1 at any given time1 + 2: Exactly one label will be 1 => the next state will be uniquely defined for every input combination14/01/19 UAH-CPE/EE 422/522 AM 14Constraints on Input Labels (cont’d)14/01/19 UAH-CPE/EE 422/522 AM 15Networks for Arithmetic OperationsCase Study: Serial Parallel MultiplierNote: we use unsigned binary numbers14/01/19 UAH-CPE/EE 422/522 AM 16Block Diagram of a Binary MultiplierAd – add signal // adder outputs are stored into the ACCSh – shift signal // shift all 9 bits to rightLd – load signal // load multiplier into the 4 lower bits of the ACC and clear the upper 5 bits14/01/19 UAH-CPE/EE 422/522 AM 17Multiplication Example14/01/19 UAH-CPE/EE 422/522 AM 18State Graph for Binary Multiplier14/01/19 UAH-CPE/EE 422/522 AM 19Behavioral VHDL Model14/01/19 UAH-CPE/EE 422/522 AM 20Behavioral VHDL Model (cont’d)14/01/19 UAH-CPE/EE 422/522 AM 21Multiplier Control with Counter•Current design: control part generates the control signals (shift/add) and counts the number of steps•If the number of bits is large (e.g., 64),the control network can be divided intoa counter and a shift/add control14/01/19 UAH-CPE/EE 422/522 AM 22Multiplier Control with Counter (cont’d)Add-shifts control: tests St and M and generates the proper sequence of add and shift signalsCounter control: counter generates a completion signal K that stops the multiplier after the proper number of shiftshave been completed14/01/19 UAH-CPE/EE 422/522 AM 23Multiplier Control with Counter (cont’d)• Increment counter each time a shift signal is generated• Generate K after n-1 shifts occured14/01/19 UAH-CPE/EE 422/522 AM 24Operation of a Multiplier Using Counter14/01/19 UAH-CPE/EE 422/522 AM 25Array Multiplier• What do we need to realize Array Multiplier?• AND gates = ?• FA = ?• HA = ?14/01/19 UAH-CPE/EE 422/522 AM 26Array Multiplier (cont’d)14/01/19 UAH-CPE/EE 422/522 AM 27Array Multiplier (cont’d)•Complexity of the N-bit array multiplier–number of AND gates = ?–number of HA = ?–number of FA = ?•Delay–tg – longest AND gate delay–tad – longest possible delay through an adder14/01/19 UAH-CPE/EE 422/522 AM 28Multiplication of Signed Binary Numbers•How to multiply signed binary numbers?•Procedure–Complement the multiplier if negative–Complement the multiplicand if negative–Multiply two positive binary numbers–Complement the product if it should be negative•Simple but requires more hardware and timethan other available methods14/01/19 UAH-CPE/EE 422/522 AM 29Multiplication of Signed Binary Numbers•Four cases–Multiplicand is positive, multiplier is positive–Multiplicand is negative, multiplier is positive–Multiplicand is positive, multiplier is negative–Multiplier is negative, multiplicand is negative•Examples–0111 x 0101 = ?–1101 x 0101 = ?–0101 x 1101 = ?–1011 x 1101 = ?•Preserve the sign of the partial product at each step•If multiplier is negative, complement the multiplicand before adding it in at the last step14/01/19 UAH-CPE/EE 422/522 AM 302’s Complement Multiplier14/01/19 UAH-CPE/EE 422/522 AM 31State Graph for 2’s Complement Multiplier14/01/19 UAH-CPE/EE 422/522 AM 32Faster Multiplier •Move wires from the adder outputs one position to the right =>add and shift can occur at the same clock cycle14/01/19 UAH-CPE/EE 422/522 AM 33State Graph for Faster Multiplier14/01/19 UAH-CPE/EE 422/522 AM 34Behavioral Model for Faster Multiplier14/01/19 UAH-CPE/EE 422/522 AM 35Behavioral Model for Faster Multiplier14/01/19 UAH-CPE/EE 422/522 AM 36Command File and Simulation14/01/19 UAH-CPE/EE 422/522 AM 37Test Bench for Signed