18.2.1CS150 Newton/PisterOutlinem Last time:Ü Review State Tables & State Transition DiagramsÜ Implementation Using D Flip-FlopsÜ Machine EquivalenceÜ Incompletely Specified MachinesÜ State Assignment & State Coding SchemesÜ Design Example: Assign Codes to StatesÜ Design Example: Implement Using D flip-flopsÜ Design Example: Implement Using T flip-flopsm This lecture:Ü Sequential ExamplesÜ Arithmetic Examples8.2.2CS150 Newton/PisterExample 1: Sequential Design"(1) A sequential network has one input and oneoutput. The output becomes 1 and remains 1thereafter when at least two zeros and at least twoones have occurred as inputs, regardless of theorder of occurrence. Draw a state graph (Mooretype) for the network (9 states are sufficient). Yourfinal state graph should be neatly drawn with nocrossed lines."8.2.3CS150 Newton/PisterExample 1: Sequential DesignSo0S80S10S50S20S60S30S70S410000000011111111*8.2.4CS150 Newton/PisterExample 2: State Assignment & J/K Implementation"(2) The following state table is to be implemented using J-K flip-flops and logic gates (format of next-state entries is (next-state,output))."Presentinput inputState x=0 x=1a a,0 e,0b c,0 b,1c a,0 f,0d c,0 b,1e f,0 e,0f a,0 f,08.2.5CS150 Newton/PisterExample 2: State Assignment & J/K Implementation"(a) Find a good state assignments using the three guidelines mentioned in class. (Do not reduce the table first). Try to satisfy as many of the adjacency conditions as possible."Adjacency conditions:Rule 1: "States which have the same next-state for a given input should be given adjacent assignments." {f, c}, {d, b}, Rule 2: "States which are the next-states of the same states should be given adjacent assignments." 2*{a, f}, 2*{c, b}, {e, f}, {a, e}Output: "States which have the same output for a given input should be given adjacent assignments." Not of any value in this case; one input & one output almost everything would need to be adjacent! Lowest priority anyway.8.2.6CS150 Newton/PisterExample 2: State Assignment & J/K Implementation• The following assignment satisfies all of theadjacency conditions except {e,f}:Q1Q2Q300 01 11100105731462A FCEB D28.2.7CS150 Newton/PisterExample 2: State Assignment & J/K Implementation"(b) Using this assignment, derive the.J-K flip-flopinput equations and output equations. Expressthem in a form that contains the minimum numberof literals."Next-StateLogicJ/KFlip FlopsQQ'JKPIsPOsQn+1Qn8.2.8CS150 Newton/PisterGuidelines for Determining Flip-Flop InputEquations from Next-State MapTypeInputD DT ENS-R SRJ-K JK Qn = 0Qn+1=0 Qn+1=1 0 1 0 1 0 1 * 0 0 1 * * Qn = 1Qn+1=0 Qn+1 =1 0 1 1 0 0 * 1 0 * * 1 0Rules for forming input map fromnext-state map (2)Qn =0 half Qn =1 halfno change no changeno change complementno change replace 1s with *sreplace 0s with *s complementno change fill in with *sfill in with *s complementm Notes:(1) * = "don't care"(2) Always copy *s from next-state map to input map first(3) For S, Qn=1 half and R, Qn=0 half, fill remaining entries with0s.8.2.9CS150 Newton/PisterFlip-Flop Input Equations From Next-State Map: ExampleABQn00 01 11 1001057314620000111*ABQn00 01 11 1001057314620000111*ABQn00 01 11 1001057314620010111*ABQn00 01 11100105731462000011**ABQn00 01 11 10010573146200*011**ABQn00 01 1110010573146200**11**ABQn00 01 11100105731462***011**Qn+1 next-state mapD input mapT input mapSRJKS-R input mapJ-K input map8.2.10CS150 Newton/PisterExample 2: State Assignment & J/K Implementation• J1 = XQ2', K1 = Q2Q3' + XQ3'• J2 = X'Q1 + Q3, K2 = X'Q3'• J3 = 0, K3 = X'• Z = XQ38.2.11CS150 Newton/PisterExample 3: Arithmetic"(3) Design a parallel binary multiplier whichmultiplies two 3-bit binary numbers to for a 6-bitproduct. This multiplier is to be a combinationalnetwork consisting of an array of 1-bit full addersand AND gates only (no flip-flops).(a) Show a schematic diagram.(Hint: The AND gatescan be used to multiply by 0 or 1 and the fulladders can be used to add 2 bits plus a carry. Sixfull adders are required.)(b) Demonstrate you multiplier works by showingthe values on all internal outputs (outputs ofadders and outputs of AND gates) whenmultiplying 111 by 111. "8.2.12CS150 Newton/PisterExample 3: Arithmetic38.2.13CS150 Newton/PisterExample 3: Arithmetic"(c) Using exactly 5 bits, express the following numbers in 2's-complement form:(a) 12 = __ __ __ __ __(b) -13 = __ __ __ __ __(c) 31 = __ __ __ __
View Full Document