Class Note for ENGIN 112 at UMass(38)
Class Note for ENGIN 112 at UMass(38)
Popular in Course
Popular in Department
This 18 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 12 views.
Reviews for Class Note for ENGIN 112 at UMass(38)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
ENGIN 112 Intro to Electrical and Computer Engineering Lecture 25 State Reduction and Assignment g RHODE ISLAND ENGIN112 LE State Reduction and Assignment oemberu 2003 Overview Important to minimize the size of digital circuitry Analysis of state machines leads to a state table or diagram In many cases reducing the number of states reduces the number of gates and flops This is not true 100 of the time In this course we attempt state reduction by examining the state table Other more advanced approaches possible Reducing the number of states generally reduces complexuty ENGN112 L25 State Reduction and Assignment October 31 2003 Finite State Machines Example Edge Detector Bit are received one at a time one per cycle gt such as 000111010 time CLK IN OUT Design a circuit that asserts its output for one cycle when the input bit stream changes from 0 to 1 Try two different solutions ENGN112 L25 State Reduction and Assignment October 31 2003 State Transition Dia ram Solution A ENGN112 L25 State Reduction and Assignment ZERO ONE IN PS NS OUT 0 00 00 0 00 01 0 a a 0 11 00 0 1 11 11 O October 31 2003 Solution A circuit derivation ZER01 CHANGE ONE 0 1 F l N81 FF PS NsO IN FF PS ENGN112 L25 State Reduction and Assignment PS 00 01 H 10 0 IN 0 O NS1N PS0 1 0 1 1 PS 00 01 H 10 IN 0 0 0 0 39 N30 IN 1 1 1 1 PS 00 01 H 10 IN 0 O 1 O 39 OUT E 1PSO 1 0 0 October 31 2003 Solution B Output depends non only on PS but also on input IN N0 OUT0 Let ZEROO N1 OUT1 N0 NS IN OUT IN PS OUT0 NS IN FF Ps 3 OUT0 0 OUT What s the intuition about this solution ENGN112 L25 State Reduction and Assignment October 31 2003 Edge detector timing diagrams CLK IN OUT solution A OUT solution B Solution A output follows the clock Soution B output changes with input rising edge and Is asynchronous wrt the clock ENGN112 L25 State Reduction and Assignment October 31 2003 FSM Comparison Solution A Moore Machine output function only of PS maybe we state synchronous outputs no glitching one cycle delay full cycle of stable output CLK IN OUT 39 ENGN112 L25 State Reduction and Assignment OUT C Solution B Mealy Machine output function of both PS amp input maybe fewer states asynchronous outputs if input glitches so does output output immediately available output may not be stable long enough to be useful CLK I u l I f nquot October 31 2003 FSM Reca Moore Machine Mealy Machine input value input valueoutput values STATE output values inpms 4quot CL inputs 4 a outputs CL present slate next slate present stat FF next state FF 4 CL Wamputs Both machine types allow onehot implementations ENGINHZ L25 Slate Reduclinn and Assignment 0dnher31 znna FSM Optimization State Reduction Motivation lower cost fewer flipflops in one hot implementations possibly fewer flip flops in encoded implementations more don t cares in next state logic fewer gates in next state logic Simpler to design with extra states then reduce later ENGN112 L25 State Reduction and Assignment Example Odd parity checker October 31 2003 Moore machine State Reduction Row Matching is based on the statetransition table If two states have the same output and both transition to the same next state or both transition to each other or both selfloop then they are equivalent Combine the equivalent states into a new renamed state Repeat until no more states are combined State Transition Table NS output PS x0 x1 I SO SO S1 0 S1 S1 82 1 SZ 82 S1 0 ENGN112 L25 State Reduction and Assignment October 31 2003 FSM Optimization Merge state 32 into SO Eliminate 32 New state machine shows same IIO behavior State Transition Table NS PS I x0 x1 I E SO S1 0 S1 S1 80 1 output ENGN112 L25 State Reduction and Assignment Example Odd parity 1 checken O 1 1 October 31 2003 1 RowMatchin Exam le um State Transition Table 00 NS output 1000 PS x0 x1 x0 x1 00 00 10 1 m 00 EMGIMHZ L25 Side Rmu lnn mu Assmnmm O nhu 31 2m Row Matchin Exam le NS output PS x0 x1 x0 x1 a a b 0 0 b c d 0 0 c a d 0 0 d e f 0 1 e a f 0 1 f e f 0 1 NS output PS x0 x1 x0 x1 a a b 0 0 b c d 0 0 c a d 0 0 d e d 0 1 e a d 0 1 mom 112 L25 5m Rmudmn Ind A mmml Reduced State Transition Dia ram WU 00 00 1 1 v 00 00 M V 0mm 11 2am State Reduction 0 The row matching method is not guaranteed to result in the optimal solution in all cases because it only looks at pairs of states For example 0 Another more complicated method guarantees the optimal solution Implication table method See Mano chapter 9 not responsible for chapter 9 material ENGN112 L25 State Reduction and Assignment October 31 2003 Encoding State Variables Option 1 Binary values 000 001 010 011 100 Option 2 Gray code 000 001 011 010 110 Option 3 One hot encoding One bit for every state Only one bit is a one at a given time For a 5state machine 00001 00010 00100 01000 10000 ENGN112 L25 State Reduction and Assignment October 31 2003 State Transition Dia ram Solution B IN PS NS OUT ZERO o 01 01 o IN1 CHANGE0 1o 01 1 ONE 0 oo 01 o 1 oo oo o How does this change the combinational logic ENGN112 L25 State Reduction and Assignment October 31 2003 Summary Important to create smallest possible FSMs This course use visual inspection method Often possible to reduce logic and flip flops State encoding is important Onehot coding is popular for flip flop intensive designs A fume ENGIN112 L25 State Reductlon and Asslgnment October312003
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'