CS231: Computer Architecture INotesFlip-flop input equationsStep 1: Flip-flop input equationsStep 2: Flip-flop input valuesStep 3: Find the next statesStep 3 concludedGetting the state table columns straightState diagramsSizes of state diagramsExample 1ExampleSlide 13Slide 14Slide 15Slide 16Example 2Slide 18Slide 19Slide 20Slide 21Have a great spring break!!!1CS231: Computer Architecture IFriday, March 14, 2008CS 231 Review, March 16, 20072Notes•HW6 is Due Monday, March 24–Note that this is immediately after break!•Today’s review covers:–Sequential Circuit Analysis–Sequential Circuit DesignCS 231 Review, March 16, 20073Flip-flop input equations•Finding the next states is harder. To do this, we have to figure out how the flip-flops are changing.Step 1:Find Boolean expressions for the flip-flop inputs.I.e. How do the inputs (say, J & K) to the flipflops depend on the current state and inputStep 2:Use these expressions to find the actual flip-flop input values for each possible combination of present states and inputs.I.e. Fill in the state table (with new intermediate columns)Step 3:Use flip-flop characteristic tables or equations to find the next states, based on the flip-flop input values and the present states.CS 231 Review, March 16, 20074Step 1: Flip-flop input equations•For our example, the flip-flop input equations are:J1 = X’ Q0K1 = X + Q0J0 = X + Q1K0 = X’•JK flip-flops each have two inputs, J and K. (D and T flip-flops have one input each.)CS 231 Review, March 16, 20075Step 2: Flip-flop input values•With these equations, we can make a table showing J1, K1, J0 and K0 for the different combinations of present state Q1Q0 and input X.J1 = X’ Q0J0 = X + Q1K1 = X + Q0K0 = X’Present State I nputs Flip-fl op I nputsQ1Q0X J1K1J0K00 0 0 0 0 0 10 0 1 0 1 1 00 1 0 1 1 0 10 1 1 0 1 1 01 0 0 0 0 1 11 0 1 0 1 1 01 1 0 1 1 1 11 1 1 0 1 1 0CS 231 Review, March 16, 20076Step 3: Find the next states•Finally, use the JK flip-flop characteristic tables or equations to find the next state of each flip-flop, based on its present state and inputs.•The general JK flip-flop characteristic equation is: Q(t+1) = K’Q(t) + JQ’(t)•In our example circuit, we have two JK flip-flops, so we have to apply this equation to each of them: Q1(t+1) = K1’Q1(t) + J1Q1’(t) Q0(t+1) = K0’Q0(t) + J0Q0’(t)•We can also determine the next state for each input/current state combinationdirectly from the characteristic table.J K Q(t+1) Operation0 0 Q(t) No change0 1 0 Reset1 0 1 Set1 1 Q’(t) ComplementCS 231 Review, March 16, 20077Step 3 concluded•Finally, here are the next states for Q1 and Q0, using these equations: Q1(t+1) = K1’Q1(t) + J1Q1’(t) Q0(t+1) = K0’Q0(t) + J0Q0’(t)Present State I nputs FF I nputs Next StateQ1Q0X J1K1J0K0Q1Q00 0 0 0 0 0 1 0 00 0 1 0 1 1 0 0 10 1 0 1 1 0 1 1 00 1 1 0 1 1 0 0 11 0 0 0 0 1 1 1 11 0 1 0 1 1 0 0 11 1 0 1 1 1 1 0 01 1 1 0 1 1 0 0 1CS 231 Review, March 16, 20078Getting the state table columns straight•The table starts with Present State and Inputs.–Present State and Inputs yield FF Inputs.–Present State and FF Inputs yield Next State, based on the flip-flop characteristic tables.–Present State and Inputs yield Output.•We really only care about FF Inputs in order to find Next State.•Note: the outputs occur this cycle and the next state in the next cyclePresent State I nputs FF I nputs Next State OutputsQ1Q0X J1K1J0K0Q1Q0Z0 0 0 0 0 0 1 0 0 00 0 1 0 1 1 0 0 1 00 1 0 1 1 0 1 1 0 00 1 1 0 1 1 0 0 1 01 0 0 0 0 1 1 1 1 01 0 1 0 1 1 0 0 1 01 1 0 1 1 1 1 0 0 01 1 1 0 1 1 0 0 1 1CS 231 Review, March 16, 20079State diagrams000110111/00/00/00/00/0 1/01/01/1Present State I nputs Next State OutputsQ1Q0X Q1Q0Z0 0 0 0 0 00 0 1 0 1 00 1 0 1 0 00 1 1 0 1 01 0 0 1 1 01 0 1 0 1 01 1 0 0 0 01 1 1 0 1 1•We can also represent the state table graphically with a state diagram.•A diagram corresponding to our example state table is shown below.input outputstateCS 231 Review, March 16, 200710Sizes of state diagrams000110111/00/00/00/00/0 1/01/01/1•Always check the size of your state diagrams.–If there are n flip-flops, there should be 2n nodes in the diagram.–If there are m inputs, then each node will have 2m outgoing arrows.•From each state•In our example,–We have two flip-flops, and thus four states or nodes.–There is one input, so each node has two outgoing arrows.ADBC11Example 1Sequential Circuit Analysis~Creating a State Diagram and State Table from a CircuitCS 231 Review, March 16, 200712ExampleDA = DB = Z = BAnalyze this sequential circuit…CS 231 Review, March 16, 200713ExampleDA = X'A + XYDB = X‘A + XBZ = XBPresent State I nputs FlipFlop I nputs Next State Output A B X Y DA DB A B Z 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 D Q(t+1) Operation0 0 Reset1 1 SetCS 231 Review, March 16, 200714ExamplePresent State I nputs Next State Output A B X Y A B Z 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 How many states do we need to construct a state diagram?What should we call them?CS 231 Review, March 16, 200715ExamplePresent State I nputs Next State Output DA DB X Y DA DB Z 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 1 …
View Full Document
Unlocking...