DOC PREVIEW
UIC ECE 465 - Logic level sequential design

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

© P.Prinetto - all rights reserved Version 1.0 7.2.17.2 – Logic level sequential design (2)ECE 465Logic level sequential design (2)Paolo PRINETTOPolitecnico di Torino (Italy)University of Illinois at Chicago, IL (USA)[email protected]@uic.eduwww.testgroup.polito.itLecture 7.227.2 Goal• This lecture is the latter 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.2 Prerequisites • Lecture 7.147.2 Homework • Students are invited to try to solve the proposed exercises by themselves, before looking at the proposed solutions57.2 Further readings • See Lecture 7.167.2 Further readings (cont’d)• In particular, students interested in sequentiallogic minimization algorithms are invited to refer to − G. De Micheli: “Synthesis and Optimization of digitalcircuits,”McGraw-Hill, Inc, New York, NJ, USA, 1994, (chapters 9, pp. 441-503)© P.Prinetto - all rights reserved Version 1.0 7.2.27.2 – Logic level sequential design (2)ECE 46577.2 Outline• State minimization• State encoding• Library binding87.2 behavior structure physicalsystemRTlogicdeviceStateminimizationState minimizationAims at minimizing the global number of states97.2 Equivalent statesTwo states are equivalentiff for every possible input combination:• The corresponding POs are the same• The corresponding next states are equal or equivalent107.2 ExamplesA ≡ B A,0 B,0CD0110117.2 ExamplesIf (C ≡ D) and (E ≡ F) then A ≡ B A,0 B,0EF001DC1127.2 NoteState minimization algorithms are outside the scope of the course.© P.Prinetto - all rights reserved Version 1.0 7.2.37.2 – Logic level sequential design (2)ECE 465137.2 State minimization• If states A and B proved to be equivalent, you can simplify the STG by merging them.• This practically means, either:− Deleting either A or B (let’s assume, for instance, of deleting B)− Redirecting to A all the edges that leaded to Bor− Merging them into a new state− Erasing redundant edges.147.2 ExampleA ≡ B.A,0 B,0CD0110XYZ0110157.2 DeletingLet’s delete BA,0 B,0CD0110XYZ0110167.2 DeletingLet’s delete BA,0CD01XYZ0110177.2 DeletingLet’s redirect the edgesA,0CD01XYZ0110187.2 DeletingState Y can be simplifiedA,0CD01XYZ01-© P.Prinetto - all rights reserved Version 1.0 7.2.47.2 – Logic level sequential design (2)ECE 465197.2 MergingLet’s merge A and B A,0 B,0CD0110XYZ0110207.2 MergingLet’s merge A and B A,0 B,0CD0110XYZ0110217.2 MergingA_B, 0CD01XYZ0110227.2 MergingA_B, 0CD01XYZ01-Let’s erase redundant edges237.2 Tabular representationAt this stage of the synthesis process, it’s convenient translating the STG into an equivalent tabular representation, based on two tables:• the State Transition Table (STT)• the Primary Output Table (POT).Both tables have:• as many rows as the states are• 2# PIcolumns.247.2 State Transition TablePIPSNSjiThe cell (i, j) stores the value of the next state of the state i when the PI's get the value j.© P.Prinetto - all rights reserved Version 1.0 7.2.57.2 – Logic level sequential design (2)ECE 465257.2 Primary Output TablePIPSPOjiThe cell (i, j) stores the value of the PO’s when the machine is the state i and the PI's get the value j.267.2 POT of Moore machinesPI−PSPO277.2 POT of Mealy machinesPIPSPO287.2 Solution010R,0 0,0010,101,0reset10011001297.2 Solution010A,0A,0B,0B,0D,1D,1C,0C,0reset10011100R,0 0,0010,101,0reset10011001307.2 Solution01ABCDPSxNS U010A,0A,0B,0B,0D,1D,1C,0C,0reset10011100© P.Prinetto - all rights reserved Version 1.0 7.2.67.2 – Logic level sequential design (2)ECE 465317.2 Solution01A B A 0BCDPSxNS U010A,0A,0B,0B,0D,1D,1C,0C,0reset10011100327.2 Solution01A B A 0B B C 0C D A 0D B A 1PSxNS U010A,0A,0B,0B,0D,1D,1C,0C,0reset10011100337.2 Outline• State minimization⇒State encoding• Library binding347.2 behavior structure physicalsystemRTlogicdeviceState encodingState encodingAims at determining the binary representation of the states, i.e., at assigning each state a binary value to be stored in the state register357.2 behavior structure physicalsystemRTlogicdeviceState encoding01ABA 0BBD 0CBA 1DCA 0presentstatesxUSTTnextstates367.2 behavior structure physicalsystemRTlogicdeviceState encoding0100 01 00 001 01 10 011 01 00 110 11 00 0y[1:0]xUY[1:0]01ABA 0BBD 0CBA 1DCA 0presentstatesxUSTTnextstates© P.Prinetto - all rights reserved Version 1.0 7.2.77.2 – Logic level sequential design (2)ECE 465377.2 behavior structure physicalsystemRTlogicdeviceState encoding0100 01 00 001 01 10 011 01 00 110 11 00 0y[1:0]xUY[1:0]STT387.2 behavior structure physicalsystemRTlogicdeviceState encoding0100 01 00 001 01 10 011 01 00 110 11 00 0y[1:0]xUY[1:0]STTY[1] = x’y[1]y[0]’ + xy[1]’y[0]Y[0] = x’U = y[1]y[0]397.2 behavior structure physicalsystemRTlogicdeviceState encodingSTTY[1] = x’y[1]y[0]’ + xy[1]’y[0]Y[0] = x’U = y[1]y[0]Output functionState transition function407.2 State variablesThe minimum number N of required state variables (i.e., of flip-flops) is always:N = log2# states 417.2 Assignment choicesThe total number SA of nonequivalent state assignments with N states and Q state variables is given by:(2Q -1)!(2Q -N)! Q!SA = 427.2 State encoding strategies• No practical way is known to find the state assignment providing a minimum cost implementation.• The most widely adopted strategies are the following:− random− one-hot− heuristic-based.© P.Prinetto - all rights reserved Version 1.0 7.2.87.2 – Logic level sequential design (2)ECE 465437.2 Random encoding• Encoding is performed in a random way• It’s the most widely used in manual design.447.2 Solution (random) 01001A B A 0B B C 0C D A 0D B A 1PSxNS U457.2 Solution (random) state encodingA00B01C10D1101001A B A 0B B C 0C D A 0D B A 1PSxNS U467.2 One-hot encoding• It uses one flip-flop per state, instead of the minimum # log2# states • For each state just the corresponding state variable is set to 1, while all the other ones are set to 0.477.2 Solution (one-hot)01001A B A 0B B C 0C D A 0D B A 1PSxNS U487.2 Solution (one-hot)01001A B A 0B B C 0C D A 0D B A 1PSxNS Ustate


View Full Document
Download Logic level sequential design
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Logic level sequential design and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Logic level sequential design 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?