数字电路设计经典资料课件

Outline•Introduction(1，2，3，4)•Combinational Logic Design(3，5)•Sequential Logic Design(6，7，8)•Memory & PLD(9)•Summary1/Finite State Machines Design•Concept of Finite State Machine •Counters (7)•Basic FSM Design Approach (8)–FSM Design Procedure–Other State Reduction Method–Other State Assignment–FSM Partitioning2/Understand the problem•From the word specifications•Counters–Enumerate the sequence•General FSM–Try some input sequences–Under what conditions FSM transitionsbetween states–The various outputs are asserted4/Obtain an abstract representationof the FSM•Constructing a state table or state diagram, which is an abstract model of the network behavior–No standard technique–Define a prior set of states needed by thenetwork to preserve the information regardingthe past history of inputs•Initial state•Additional states: none of the defined statesadequately describes the information to bepreserved at some point in time5/Perform State Minimization•By means of state reduction technique •Determining equivalent pairs of states •Obtaining the equivalence classes ofstates•Constructing the minimal state table6/Algorithm for Determiningequivalent pairs of states •Construct an implication table•Place a×, √, or next states in every cell •Inspect all state pair entries in the implication table•Repeat Step 3 until all cells are inspected8/Assignment Method•Sequential Encoding–Binary Up-Counting Order–Gray•Random Encoding•One-hot Encoding•Output-Oriented Encoding•Heuristic Methods10/Guidelines Based on Next Stateand Inputs/Outputs•Highest Priority–States with the same next state for a given inputtransition should be given adjacent assignments •Medium Priority–Next states of the same state should be givenadjacent•Lowest Priority–States with the same output for a given input shouldbe given adjacent assignments•Initial state is assigned with 00 011/Implement the FSM•After state assignment, an excitation tableis constructed based on the flip-flop typesto be used in the realization•From the excitation table, the excitationand output expressions for the network are determined•The logic diagram is drawn12/Moore & Mealy Machines•Mealy–The outputs from a Mealy sequential networkare a function of both the external inputs andthe present state•Moore–The outputs from a Moore sequential networkare only a function of the present state13/Moore & Mealy Outputs•Moore Outputs are synchronous with the clock–Have a disciplined timing methodology •Mealy Outputs are asynchronous because they can change in response to any changes in the inputs–Synchronous variation16/Comparison of the Two Machine Types•Moore–Synchronous–More states•Mealy–reduced state count–asynchronous20/Two Major Issues with Mealy Machine• The output logic of Mealy machines can cause glitches on the output • The output can change asynchronously to the clock– Sometimes be an advantage – The circuit can react quickly to an input change rather than having to wait for the next clock edge to advance the state21/Timing Diagramclock x y Q1 Q2 zA B D C A Cz = xQ1 + Q1Q2DACA? 1 1 0 1 1 1 0??? 1 1 022/Mealy; The values of the external input variables only at the triggering time of the clock signal are considered;Synchronous Mealy MachineCombinational Logic to Compute Outputs Combinational Logic to Compute Next State Re- Outputs gister Current State RegisterI n p u t s23/Finite State Machines Design• Concept of Finite State Machine • Counters (7) • Basic FSM Design Approach (8)– FSM Design Procedure – Other State Reduction Method – Other State Assignment – FSM Partitioning24/Other State Reduction Method• Implication Chart • Row matching– Combine the two approaches – Firstly, row matching quickly reduces the number of states – Then, implication chart, now working with fewer states, finds the equivalent states missed by row matching more rapidly• Equivalent states in the presence of don’t cares • When state minimization doesn’t help25/Implication Chart MethodPresent Next State State x=0 x=1 A* B C D E F G A D F D B G A B C E F G C F Output x=0 x=1 0 0 0 0 0 0 0 0 1 0 0 0 1 026/Row Matching• Get the state transition table with multiple next-state and output columns based on the input combinations • Examine the rows of the state transition table to find any with identical next-state and output values—Row Matching • Continue matching rows until any can’t be no longer combined—Row-matching Iteration27/Modeling the sequence detector• The FSM produce a 1 output if and only if the current input and the previous three inputs correspond to either of the sequences 0110 or 1010. The machine returns to the reset state after each and every 4-bit sequence x=0010 0110 1100 1010 0011 z=0000 0001 0000 0001 000028/A*: reset B: input 0 received C: input 1 receivedState tableD: input 00 received E: input 01 received F: input 10 received G: input 11 received0/0 BA1/01/0 0/0 1/0 0/0 D E F G 0/0 1/0 0/0 1/0 0/0 1/0 0/0 1/0 H I J K 0/1 L M 0/1 N OCH: input 000 received I: input 001 received J: input 010 received K: input 011 received L: input 100 received M: input 101 received N: input 110 received O: input 111 received29/Input Sequence Reset 0 1 00 01 10 11 000 001 010 011 100 101 110 111Present State A B C D E F G H I J K L M N ONext State x=0 x=1 B C D E F G H I J K L M N O A A A A A A A A A A A A A A A AOutput x=0 x=1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0Row Matching Iteration (1)Advantages of Implication Chart•Be Straightforward•Be efficiently implemented in software35/Equivalent states in the presenceof don’t cares•If having don’t care, the problem becomes much more difficult–Input don’t cares•The state can be chosen to transition for aninput combination that is impossible•Merging more states–Output don’t cares•More problematic•Two methods rely on output patterns as acentral part of determining stateequivalence36/When state minimization doesn’t help•Advantages of State Minimization–Allow us to build smaller finite state machineswith less flip-flops and less logic•The logic equations themselves can become more complex as we fit more states into a smaller number bits–用更少的位数表示更多的状态–逻辑函数本身更复杂–Leading to a less efficient realization38/Edge Detector FSM•Moore•Detect when consecutive inputs change from 0 to 1•Output a 1 when detecting this “rising edge”in our input dream39/Minimizing states isn’t always the best thing•Leading a larger and non-obvious implementation•State Reduction is still an art•Not Straightforward as we mentioned introducing Row-matching and Implication TableQ1+=XQ1Q0’+XQ1’Q0 Q0+=XQ1’Q0’Z=Q1’Q0Q1+=Q0Q0+=XZ=Q1’Q044/Finite State Machines Design•Concept of Finite State Machine •Counters (7)•Basic FSM Design Approach (8)–FSM Design Procedure–Other State Reduction Method–Other State Assignment–FSM Partitioning45/Assignment Method•Sequential Encoding–Binary Up-Counting Order–Gray•Random Encoding•One-hot Encoding•Output-Oriented Encoding•Heuristic Methods–Minimum Bit-Change Heuristic–Guidelines based on next-state andinput/outputs46/Traffic Light Controller•As long as no vehicle is detected on the farm road, the lights should remain green in the highway direction•If a vehicle is detected on the farm road, the highway lights should change from green to yellow to red,allowing the farm road lights to become green•The farm road lights stay green only as long as a vehicle is detected on the farm road and never longer than a set interval so as not to block traffic flow along the highwayfor too long•Then farm road lights change from green to yellow to red, allowing the highway lights to return to green•Even if vehicles are waiting to cross the highway, the highway should remain green for a minimum amount oftime48/49/Inputs & Outputs & States •Inputs–Reset: Place controller in initial state–C: Detects vehicle on farm road in either direction –TS: short timer interval has expired–TL: long timer interval has expired•Outputs–ST: Reset timer and start timing long & short intervals –H 1H 0:Light at Highway–F 1F 0:Light at Farm RoadStates•HG: Highway green (farm road red)•HY: Highway yellow (farm road red)•FG: Farm road green (highway red)•FY: Farm road yellow (highway red)50/。