© P.Prinetto - all rights reserved Version 1.0 7.1.17.1 – Logic level sequential design (1)ECE 465Logic level sequential design (1)Paolo PRINETTOPolitecnico di Torino (Italy)University of Illinois at Chicago, IL (USA)[email protected]@uic.eduwww.testgroup.polito.itLecture 7.127.1 Goal• This lecture is the former part of a group of 2 lectures (split just for sake of manageability) aiming at presenting the sequence of steps to be performed in the manual synthesis of sequential networks.37.1 Prerequisites • Modules 2, 4, and 647.1 Homework • Students are invited to try to solve the proposed exercises by themselves, before looking at the proposed solutions.57.1 Further readings • Students interested in making a reference to a text book on the arguments covered in this lecture can refer, for instance, to:− M. Morris Mano, C.R.Kime: “Logic and Computer Design Fundamentals,” 2nd edition updatedPrentice Hall, Upple Saddle River, NJ (USA), 2001, (chapter 4, pp. 201-224)or to67.1 Further readings (cont’d)− J. P. Hayes:“Introduction to Digital Logic Design,”Addison Wesley, Reading, MA (USA), 1994, (chapter 7, pp. 490-555)© P.Prinetto - all rights reserved Version 1.0 7.1.27.1 – Logic level sequential design (1)ECE 46577.1 Outline• Global overview• RT level formalization87.1 Global overviewWe shall present the overall set of steps first.97.1 Goalbehavior structure physicalsystemRTlogicdeviceLogic level SynthesisUser'sRequirements107.1 behavior structure physicalsystemRTlogicdeviceRT levelformalizationManual synthesisUser'sRequirements117.1 behavior structure physicalsystemRTlogicdeviceRT levelformalizationManual synthesisAims at finding a representation of the temporal evolution of the states of the systemUser'sRequirements127.1 behavior structure physicalsystemRTlogicdeviceRT levelformalizationManual synthesisAims at finding a representation of the temporal evolution of the states of the systemA,0 B,0D,1C,0reset10011100STGUser'sRequirements© P.Prinetto - all rights reserved Version 1.0 7.1.37.1 – Logic level sequential design (1)ECE 465137.1 behavior structure physicalsystemRTlogicdeviceStateminimizationManual synthesis147.1 behavior structure physicalsystemRTlogicdeviceStateminimizationManual synthesisAims at minimizing the global number of states157.1 behavior structure physicalsystemRTlogicdeviceStateminimizationManual synthesisAims at minimizing the global number of states01ABA 0BBD 0CBA 1DCA 0presentstatesxUSTTnextstates167.1 behavior structure physicalsystemRTlogicdeviceManual synthesisState encoding177.1 behavior structure physicalsystemRTlogicdeviceManual synthesisState encodingAims at encoding each state, assigning it a binary value to be stored in the state register187.1 behavior structure physicalsystemRTlogicdeviceManual synthesisState encodingAims at encoding each state, assigning it a binary value to be stored in the state register01ABA 0BBD 0CBA 1DCA 0presentstatesxUSTTnextstates© P.Prinetto - all rights reserved Version 1.0 7.1.47.1 – Logic level sequential design (1)ECE 465197.1 behavior structure physicalsystemRTlogicdeviceManual synthesisState encodingAims at encoding each state, assigning it a binary value to be stored in the state register0100 01 00 001 01 10 011 01 00 110 11 00 0y[1:0]xUY[1:0]01ABA 0BBD 0CBA 1DCA 0presentstatesxUSTTnextstates207.1 behavior structure physicalsystemRTlogicdeviceManual synthesisState encoding0100 01 00 001 01 10 011 01 00 110 11 00 0y[1:0]xUY[1:0]Y[1] = x’y[1]y[0]’ + xy[1]’y[0]Y[0] = x’U = y[1]y[0]217.1 behavior structure physicalsystemRTlogicdeviceLibrary bindingManual synthesis227.1 behavior structure physicalsystemRTlogicdeviceLibrary bindingManual synthesisAims at generating a structural representation at the logic level237.1 behavior structure physicalsystemRTlogicdeviceManual synthesisY[1] = x’y[1]y[0]’ + xy[1]’y[0]Y[0] = x’U = y[1]y[0]Library binding247.1 behavior structure physicalsystemRTlogicdeviceLibrary bindingManual synthesisState registerCLKPrimary Output networkresetPIsPOsNext State networkY[1] = x’y[1]y[0]’ + xy[1]’y[0]Y[0] = x’U = y[1]y[0]© P.Prinetto - all rights reserved Version 1.0 7.1.57.1 – Logic level sequential design (1)ECE 465257.1 A deeper analysisWe are now going to examine each step more in details.Each step will be analyzed referring to a same example.267.1 Outline• Global overview⇒RT level formalization277.1 behavior structure physicalsystemRTlogicdeviceRT levelformalizationRT level formalizationAims at finding a representation of the temporal evolution of the states of the systemUser'sRequirements287.1 User'sRequirementsbehavior structure physicalsystemRTlogicdeviceRT levelformalizationRT level formalizationAims at finding a representation of the temporal evolution of the states of the systemUsually represented by:• state transition graph (STG) • state transition table (STT).297.1 State Transition GraphsThe State Transition Graph is a labeled ordered graph:G ( V, E, L(E) )where:• V represents the set of states S307.1 State Transition GraphsThe State Transition Graph is a labeled ordered graph:G ( V, E, L(E) )where:• V represents the set of states SEach node has out-degree 2k, k being the # of PIs© P.Prinetto - all rights reserved Version 1.0 7.1.67.1 – Logic level sequential design (1)ECE 465317.1 State Transition GraphsThe State Transition Graph is a labeled ordered graph:G ( V, E, L(E) )where:• V represents the set of states S• Eij= (Vi,Vj) ∈ E if it exists a value of PIs (PIij) forcing the transition from Sito Sj• L(Eij) = PIijare the labels associated with edges and represent the transition conditions.327.1 STG drawingIn the manual synthesis, it’s convenient to clearly distinguish between:• the STGs of Moore machines • the STGs of Mealy machines.337.1 STG drawingIn the manual synthesis, it’s convenient to clearly distinguish between:• the STGs of Moore machines • the STGs of Mealy machines.Each state must include:• a label, to identify the state itself• the values the POs assume in that state.347.1 A, 01Example of a state diagram of a Moore machine0B, 0C, 1357.1 Example of a state diagram of a Moore machineA, 001State labelB, 0C, 1367.1 Example of a state diagram of a Moore