DOC PREVIEW
Berkeley ELENG 42 - Lecture Notes

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 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 27 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 27 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 27 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 27 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 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

PowerPoint PresentationFinite State MachinesBlock diagramTiming diagram for synchronous FSMA computer as a FSMState Transition tablesDefining State MachinesDefining State Machines: TableDefining State Machines: State DiagramState Machines: State ResponseFacts About State MachinesDeterministic vs NondeterministicFSMs in programsImplementing Sequential LogicSequential CircuitsCircuits with FeedbackMemory with Cross-coupled GatesTiming BehaviorR-S Latch AnalysisGated R-S LatchClocksClocks (cont’d)Cascading LatchesMaster-Slave StructureThe Catching ProblemD Flip-FlopEdge-Triggered Flip-Flops11/10/2004 EE 42 fall 2004 lecture 30 1Lecture #30 Finite State Machines•Last lecture: –CMOS fabrication–Clocked and latched circuits•This lecture:–Finite State Machines11/10/2004 EE 42 fall 2004 lecture 30 2Finite State Machines•The digital model we are looking at is an implementation of a finite state machine.•A FSM has several states, corresponding to the values of each of the registers. Inputs into the machine are combined with the current state of the machine to determine the next state of the machine.•Most complex digital systems are made from one or more finite state machines, because they can be more easily analyzed than asynchronous digital logic11/10/2004 EE 42 fall 2004 lecture 30 3Block diagramThis is a block diagram of a particular kind of FSM. (a Mealy machine with delayed outputs)Inputs (N)outputsClockCurrent state of the system: Q(M)ClockCombinatorialLogicRegister(N+M edge triggered flip-flops)11/10/2004 EE 42 fall 2004 lecture 30 4Timing diagram for synchronous FSMClockInputsStateOutputLogic11/10/2004 EE 42 fall 2004 lecture 30 5A computer as a FSM•A computer could be viewed as a FSM,•or you could view just the CPU as a FSM, accesses from the main memory as outputting addresses, followed by input of data from the memory, etc.•A CPU might also be viewed as several interacting FSMs.–An accumulator–A memory interface unit–An instruction sequencer11/10/2004 EE 42 fall 2004 lecture 30 6State Transition tablesIt is implicit that transitions occur only at discrete times (such as clock edges)State Input Next state Output(received 6 bits so far)Next bit Received 7 bits so farnone(received 7 bits so far)Next bit Have received byteThe byte received11/10/2004 EE 42 fall 2004 lecture 30 7Defining State MachinesExample: Suppose I am playing a game by tossing a coin.If I toss 3 heads in a row, I win.If I toss a tail before tossing three heads, I lose.States = {0_heads, 1_head, 2_heads}Inputs = {head, tail, absent}Outputs = {win, lose, absent}initialState = 0_heads11/10/2004 EE 42 fall 2004 lecture 30 8Defining State Machines: TableThis state machine can be defined using a table:(s(n+1), y(n)) = update(s(n), x(n))x(n) = head x(n) = tails(n) = 0_headss(n) = 1_heads(n) = 2_headsOutput absent means that there is no output at this transitionThere is a more visually appealing way to define theupdate function: a state diagram.(1_head, absent) (0_heads, lose)(2_heads, absent)(0_heads, lose)(0_heads, win)(0_heads, lose)11/10/2004 EE 42 fall 2004 lecture 30 9Defining State Machines: State DiagramTo create a state diagram for a state machine, first draw circles representing the states.0_heads1_head 2_headsFor each combination of input and state, draw an arrow from the current state to the next state.Label the arrow with the input and output that create the transition as shown: “input/output” head / absent head / absent tail / losetail / losetail / losehead / win11/10/2004 EE 42 fall 2004 lecture 30 10State Machines: State ResponseThe state response is sequence of states resulting from a particular input sequence.Example: Find the state response and output sequence forx =0_heads1_head 2_headshead / absent head / absent tail / losetail / losetail / losehead / win tail head head tail11/10/2004 EE 42 fall 2004 lecture 30 11Facts About State Machines•The state machines addressed here are called Mealy machines. Mealy machines generate outputs during state transitions. •Moore machines generate output while the system is in a particular state (output depends on state only).•Each transition and output depends only on the current state and current input. •Previous input elements only affect the transitions and output insofar as they determine the current state.•A transition will be defined for every possible combination of input and current state.11/10/2004 EE 42 fall 2004 lecture 30 12Deterministic vs Nondeterministic•For the state machines studied in this lecture, there is exactly one possible transition for each combination of current state and input. These state machines are called deterministic.•Sometimes it is useful to model a system using a state machine that has more than one possible transition for each combination of current state and input. These state machines are called non-deterministic.11/10/2004 EE 42 fall 2004 lecture 30 13FSMs in programs•The finite state machine model can be useful in the design of software as well as the design of hardware.•If a program is responding to external events, which are not happening in a controlled order, a FSM description of the program can describe its high level operation better than sequential descriptions.11/10/2004 EE 42 fall 2004 lecture 30 14Implementing Sequential Logic•Sequential Circuits–Simple circuits with feedback–Latches–Edge-triggered flip-flops•Timing Methodologies–Cascading flip-flops for proper operation–Clock skew•Asynchronous Inputs–Metastability and synchronization•Basic Registers–Shift registers11/10/2004 EE 42 fall 2004 lecture 30 15Sequential Circuits•Circuits with Feedback–Outputs = f(inputs, past inputs, past outputs)–Basis for building "memory" into logic circuits•State is memory•State is an "output" and an "input" to combinational logic•Combination storage elements are also memory11/10/2004 EE 42 fall 2004 lecture 30 16X1X2•••XnswitchingnetworkZ1Z2•••ZnCircuits with FeedbackNeed to stop values from cycling around endlessly11/10/2004 EE 42 fall 2004 lecture 30 17RSQQ'RSQR'S'QQQ'S'R'Memory with Cross-coupled Gates•Cross-coupled NOR gates–Similar to inverter pair, with capability to force output to 0 (reset=1) or 1 (set=1)•Cross-coupled NAND gates–Similar to inverter pair, with capability to force output to 0 (reset=0) or 1 (set=0)11/10/2004 EE 42 fall 2004 lecture 30 18ResetHoldSet SetResetRaceRSQ\Q100Timing


View Full Document

Berkeley ELENG 42 - Lecture Notes

Documents in this Course
Lecture 1

Lecture 1

25 pages

Lecture 2

Lecture 2

20 pages

Lecture 3

Lecture 3

21 pages

Midterm 1

Midterm 1

20 pages

Load more
Download Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?