Report

ELEC 256 / Saif Zahir Counters An (up/down) k-bit counter produces a sequence of k-bit binary numbers in a response to a COUNT pulse. A k-bit counter can have up to 2k different states 7 10 P 163 T 15 2 RCO CLK 6 QD 11 D CLK 5 12 C QC 4 13 B QB 3A 14 QA 9 LOAD 1 0 1 1 CLR 0 CLR 1 0 1 0 Example: 74163 4-bit synchronous counter LogicWorks Timing Simulation 200 400 CLK CLR QA QB QC QD 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 1 UBC / 2000 QD QC QB QA ELEC 256 / Saif Zahir Design of a 3-Bit Up-Counter Present C B A Next C+ B+ A+ 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 FF inputs TC TB TA 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 000 100 001 101 010 110 011 111 Next-state Logic CB 00 A 0 1 1 1 01 11 10 1 1 1 1 1 1 TA=1 CB 00 A 0 0 1 1 01 11 10 0 0 0 1 1 1 CB 00 A 0 0 1 TB=A 0 01 11 10 0 0 0 1 1 0 TC=AB UBC / 2000 ELEC 256 / Saif Zahir Design of a 3-Bit Up-Counter Flipflop input equations 1 TA = 1 TB = A TC = AB S 1 T S Q T S Q B T Q C A R R R Count \Reset 200 A 0 1 0 1 0 1 0 1 B 0 0 1 1 0 0 1 1 C 0 0 0 0 1 1 1 1 CLK UBC / 2000 ELEC 256 / Saif Zahir Design of a 3-Bit Up-Counter Use D flipflops Present C B A Next C+ B+ A+ 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 CB 00 A 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 01 11 10 1 1 1 0 0 0 da = A FF inputs DC DB DA 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 CB 00 A 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 01 11 10 1 1 0 0 0 1 000 100 001 101 010 110 011 111 CB 00 A 0 0 1 db = Ab + aB 0 01 11 10 0 1 1 1 0 1 dc = cB+cA+Cba UBC / 2000 ELEC 256 / Saif Zahir Up-Counter Using D Flipflops AB S D S Q D S Q B D Q C A R R R Count \Reset da = A db = Ab + aB dc = cB+cA+Cba T-FF realization is more efficient - requires less additional combinational logic UBC / 2000 ELEC 256 / Saif Zahir Complex-Counter Design Procedure 1. From specification, draw state-transition diagram to show the desired sequence to be realized by counter. 2. Choose flipflop type, then use FF excitation-table to derive next-state and FF-input equations. • Example: Design the following 5-state counter PS C B A 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 NS C+ B+ A+ 0 X 0 1 X 1 0 X 1 X 1 0 X 1 0 X 0 X 1 1 X 0 0 X 110 FF-inputs TC TB TA 0 X 0 1 X 0 1 X 1 X 0 1 X 1 1 X 000 010 0 X 1 0 X 1 0 X 101 011 Using K-maps: Remark: The states that do not appear in the counter squence are treated as don’t care’s! UBC / 2000 tc = Ac + aC tb = a + B + c ta = AbC + Bc ELEC 256 / Saif Zahir Self-Starting Counters In previous example, a problem may arise of the counter starts in one of the unused states (001, 100, or 111). Since these states were used as don’t-cares, then depending on how these don’t cares were used, counter may exhibit unwanted behavior. 001 111 000 000 110 110 100 001 010 010 101 101 111 011 011 100 Bad Design Counter may sequence through unwanted states forever (unless, reset). Better Design: If starts in an unwanted state, counter will go (atmost after one clock-cycle) into its normal state sequence. UBC / 2000 ELEC 256 / Saif Zahir Self-Starting Counters PS C B A 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 NS C+ B+ A+ 0 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 FF-inputs TC TB TA 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 Another possible state diagram for a self-starting counter 0 0 1 0 1 1 0 0 000 110 001 101 111 010 011 100 Next-state Logic CB 00 A 0 0 1 1 01 11 10 0 1 1 1 0 0 tc = Ac + aC CB 00 A 0 1 1 1 01 11 10 0 1 1 1 1 1 CB 00 A 0 0 1 tb = a + B + c 0 01 11 10 1 0 1 0 0 1 ta = AbC + Bc UBC / 2000 ELEC 256 / Saif Zahir Counter Design with RS Flipflops • Example: Design the 5-state self-starting counter using RS flipflops PS NS FF-inputs RC SC C B A C+ B+ A+ 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 X 0 1 X 1 0 X CB 1 X 1 0 X 1 0 X 00 01 11 10 0 X X 1 X 1 X 0 X 0 00 01 11 10 0 0 0 0 X 1 X 1 X X A CB A 0 X 1 1 X 0 0 X X X X 0 X 0 1 X CB RB SB 0 X 0 1 X X 0 X 0 X 0 1 X 0 1 X 00 01 11 10 0 0 0 1 X 1 X 1 X 0 00 01 11 10 0 1 X 0 X 1 X 0 X 1 A CB A RA SA 1 X X 0 X 1 0 X X X 0 0 X 1 X X CB RS-FF excitation table 0 X 1 X X 0 0 X Q 0 0 1 1 00 01 11 10 0 X 0 X X 1 X 0 X 1 00 01 11 10 0 0 1 0 X 1 X X X 0 A CB A UBC / 2000 Q+ 0 1 0 1 R S X 0 0 1 1 0 0 X tc = A tb = ab+ac ta = c sc = a sb = B sa = bC ELEC 256 / Saif Zahir Counter Design with JK Flipflops • Example: Design the 5-state self-starting counter using JK flipflops PS NS FF-inputs JC KC C B A C+ B+ A+ 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 X 0 1 X 1 0 X 00 01 11 10 0 0 0 X X 1 X 1 X X 00 01 11 10 0 X X 1 X 1 X X X 0 CB A CB A 1 X 1 0 X 1 0 X 0 X 1 1 X 0 0 X 0 X 0 1 X X X X CB JB KB X X X X X 0 1 X 1 X X X X 1 X X 00 01 11 10 0 1 X X X 1 X X X 1 00 01 11 10 0 X 0 1 X 1 X 1 X X A CB A JA KA X X 0 1 X X 1 X 0 X 1 X X X 0 X CB JK-FF excitation table X X X 0 X 1 X X Q 0 0 1 1 00 01 11 10 0 0 1 0 X 1 X X X X 00 01 11 10 0 X X X X 1 X 0 X 1 A CB A UBC / 2000 Q+ 0 1 0 1 J 0 1 X X K X X 1 0 jc = a jb = 1 ja = bC kc = A kb = a + c ka = C ELEC 256 / Saif Zahir Counter Design and Timing JK-FF Realization 1 0 C S J Q C KR Q 1 S J Q C KR Q B S J Q C KR Q CLK A RESET 1 0 Timing Diagram 200 400 CLK RESET C B A UBC / 2000 ELEC 256 / Saif Zahir Storage Registers S=1 D3 D K-bit storage register can be realized by the parallel connection of K D-type flipflops RS or JK flipflops can be used instead as long as they implement the D-FF function! Q Q3 R S=1 D2 D Q Q2 R S=1 171 CLK CLR D3 D2 D1 D0 D1 D Q3 Q R Q2 S=1 Q1 D0 Q0 CLK TTL 74171 package: Quadruple D-type Flipflop with Clear Q1 D Q R CLR UBC / 2000 Q0 ELEC 256 / Saif Zahir Registers with Input Enable 171 CLK In the 74171, register contents may change with every positive clock edge. 377 Q3 CLR CLK EN Q2 D3 D2 D1 D0 D7 D6 D5 D4 D3 D2 D1 D0 Q1 Q0 In the 74377, registers contents change (after the psoitive edge of CLK) only if EN is asserted (EN=0) Potential use of 377 packages in a computer system • Only one of the two 74377 chips can READ from data bus at a time, Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0 Data Bus 2:1 0 MUX 1 Select System Clock D 0 D EN 7 D 0 74377 D EN 7 74377 UBC / 2000 ELEC 256 / Saif Zahir Registers with Output Enables 374 CLK H G F E D C B A QH QG QF QE QD QC QB QA Tri-State Buffers CLK The 74374 8-bit register has tri-stated outputs, which are enabled by the OE input D7 D6 D5 D4 D3 D2 D1 D0 Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0 \OE OE Potential use of 374 packages in a computer system • Only one of the two 74374 chips can WRITE to data bus at a time. Data Bus 2:1 0 MUX 1 Select System Clock Q A Q OE H 74374 Input Data UBC / 2000 Q A Q OE H 74374 Input Data ELEC 256 / Saif Zahir Shift Registers 4-Bit Shift-register FF1 FF0 Serial input IN D Q Q0 D Q FF2 Q1 D Q FF3 Q2 D CLK Correct Operation, assuming positive edge triggered FF 100 IN Q0 Q1 Q2 Q3 Clk UBC / 2000 Q Q3 Serial output ELEC 256 / Saif Zahir Shift Registers Quad right-shift circular shift register using JK flipflops + \RESET J K S Q Q1 J K R S Q R Q2 J K S Q Q3 J K R S Q Q4 R + \RESET Shift When RESET=0, Q1 = 1, Q2 = Q3 = Q4 =0 \RESET = 1 \RESET = 0, Clk \RESET = 0, Clk \RESET = 0, Clk \RESET = 0, Clk \RESET = 0, Clk . . . . . . . Q1 1 0 0 0 1 0 . . Q2 0 1 0 0 0 1 . . Q3 0 0 1 0 0 0 . . Q4 0 0 0 1 0 0 . . Also called Ring Counter UBC / 2000 ELEC 256 / Saif Zahir Shift-Registers with Parallel Load IN.0 IN.1 IN.2 IN.3 2:1 MUX 0 SI 1 S D Q 0 1 S Q0 D Q 0 1 S Q1 D Q 0 1 S Q2 D Q shift/L CLK SI = serial input Operation - following positive edges of CLK: if shift/L = 1 --> right-shift function is enabled (Q0 <-- SI, Qi <-- Qi-1) if shift/L = 0 --> parallel-load function is enabled (Qi <-- IN.i ) UBC / 2000 Q3 ELEC 256 / Saif Zahir Bidirectional Shift-Register SRI SLI 0 1 S D Q 0 1 S Q0 D Q 0 1 S Q1 D Q 0 1 S Q2 D Q Q4 r/L Shift SRI: serial right input SLI: serial left input Operation - following positive edges of CLK: if r/L = 1 --> right-shift function is enabled (Q0 <-- SRI, Qi <-- Qi-1) if r/L = 0 --> left-shift function is enabled (Q4 <-- SLI, Qi <-- Qi+1) UBC / 2000 ELEC 256 / Saif Zahir Finite State machine (FSM) Design • FSMs are sequential machines that can have only a fixed number of states. • Counters are FSMs in which the outputs and the states are identical • In general the outputs and next states of an FSM are functions of the inputs and present states. • The specification of output functions leads to two types of FSMs: – Mealy machines: outputs are functions of inputs and present states – Moore machines: outputs are functions of present states only Inputs X Combinational logic for outputs and nextstates Outputs Z R Moore Machine Mealy Machine CLK Inputs X Combinational logic for next-states only State register R CLK UBC / 2000 Comb. logic for outputs Outputs Z ELEC 256 / Saif Zahir Sequential Parity Checker Circuit that counts the 1’s in a bit-serial input stream. Odd-parity circuit: asserts its output when input stream contains an odd number of 1’s Even-parity circuit: asserts its output when input stream contains an even number of 1’s Odd-parity sequential machine State-transition table NS = PS xor IN OUT = PS PS 0 0 1 1 input 0 1 0 1 NS 0 1 1 0 0 Output 0 0 1 1 Even [0] 1 1 Odd [1] CLK = 1 2 3 4 5 6 7 8 9 10 IN = 0 1 0 1 1 0 0 1 1 0 OUT = 0 0 1 1 0 1 1 1 0 1 Example of input/ouput streams Reset 0 + 1 0 IN D Clk Realization using a D-FF (a single T-FF can be used instead) UBC / 2000 S Q CRQ RESET Q ELEC 256 / Saif Zahir Finite State machine Design Design Procedure – Understand problem » input-output behavior » define states – Obtain an abstract representation of the FSM » state diagrams, state tables – Perform state minimization – Perform state assignment:In an FSM with N=2n states, n state variables are needed to encode each state (i.e. each state is encoded by n bits) – Choose flipflop types to implement the FSM: use flipflop excitation tables to derive the flipflop input equations. » JK flipflops tend to reduce gate-count » D flipflops tend to simplify design process – Implement the FSM: use K-maps or Boolean logic to simplify next-state (or flipflop input) equations; simplify output equations UBC / 2000 ELEC 256 / Saif Zahir A Simple Vending Machine Problem Statement: • Vending machine delivers a package of gum after receiving 15 cents in coins • Machine has a single coin slot and accepts nickels (N) and dimes only (D) • Machine does not give back change; inserting 2 dimes returns one package only Vending machine controller design Coin Sensor N Vending Machine FSM D OPEN Package Release Mechanism RESET CLK FSM must remember the total amount that has been received, and release a gum package when 15 cents (or 20) have been received. The machine sensor will reject any unknown coins UBC / 2000 ELEC 256 / Saif Zahir A Simple Vending Machine Reset Constructing a state-diagram Possible states S0: initial (0 cents) state S1: received 5 cents S2: received 10 cents S3: received 15+ cents S0 [0 ¢] N S1 [5 ¢] N State-Encoding: • The 4 states of the machine must be encoded in binary. • Since we have four states, we need two bits to encode each state (each bit is called a state-variable) D S2 [10¢] N,D S3 [15¢] Possible encodings State S0 S1 S2 S3 Q1 0 0 1 1 Q0 0 1 0 1 State S0 S1 S2 S3 Q1 0 1 1 0 Q0 1 1 0 0 UBC / 2000 D ELEC 256 / Saif Zahir A Simple Vending Machine PS inputs Q1 Q0 D N D-FF implementation D1= Q1+, D0= Q0+ Q1Q0 DN Q1 0 0 1 1 0 1 1 1 Q1Q0 DN N X X X X D 1 1 1 D 1 Q1Q0 DN D 0 1 0 0 0 1 0 X X X X 0 0 1 0 1 1 0 1 0 1 1 X X X X 1 1 1 Q1 K-Map for D0 Q1 0 0 0 Q1 K-Map for D1 Q1 N 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 NS outputs Q1+ Q0+ OPEN 0 0 1 X 0 1 1 X 1 1 1 X 1 1 1 X 0 1 0 X 1 0 1 X 0 1 1 X 1 1 1 X d1 = q1 + d + nq0 N d0 = nq1 + nQ0 + Nq0 + dq1 open = q1+ q0 Q1 K-Map for OPEN UBC / 2000 0 0 0 X 0 0 0 X 0 0 0 X 1 1 1 X ELEC 256 / Saif Zahir Vending Machine FSM Implementation FSM Implementation with D flipflops Flipflop (next-state) equations d1 = q1 + d + nq0 (Moore machine) d0 = nq1 + nQ0 + Nq0 + dq1 open = q1+ q0 Q1 D D1 Q0 N D Q Q1 \Q0 N OPEN Q0 N D Q1 N D0 Q1 D CLK \RESET UBC / 2000 Q Q0 ELEC 256 / Saif Zahir FSM Design for a Vending Machine JK-FF Implementation PS inputs Q1 Q0 D N 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 NS Q1+ Q0+ 0 0 1 X 0 1 1 X 1 1 1 X 1 1 1 X 0 1 0 X 1 0 1 X 0 1 1 X 1 1 1 X FF J1 K1 J0 K0 outputs OPEN 0 0 1 X 0 1 1 X X X X X X X X X 0 1 0 X X X X X 0 1 1 X 0 0 0 X 0 0 0 X 0 0 0 X 0 0 0 X 1 1 1 X j1 = d + nq0 j0 = nQ0 + dq1 X X X X X X X X 0 0 0 X 0 0 0 X X X X X 0 1 0 X X X X X 0 0 0 X k1 = 0 k0 = nQ1 open = q1+ q0 UBC / 2000 ELEC 256 / Saif Zahir Vending Machine FSM Implementation FSM implementation with JK flipflops j1 = d + nq0 (Moore Machine) open = q1+ q0 k1 = 0 j0 = nQ0 + dq1 k0 = nQ1 D J Q0 N 0 Q Q1 K OPEN \Q0 N J Q Q1 D K \Q1 N CLK \RESET UBC / 2000 Q0 ELEC 256 / Saif Zahir Moore and Mealy Machines: State Diagrams Reset Reset S0 [0] ND/0 Reset OPEN N ND S1 [0] D Reset/0 Reset/0 S0 ND/0 Reset/0 N/0 S1 ND/0 N D/0 N/0 OPEN D S2 [0] N,D S2 D/1 ND D/1 N/1 S3 [1] ND/0 S3 Reset • Complete Moore machine state diagram for vending machine • Outputs are associated with states (graph nodes) Reset/1 • Complete Mealy machine state diagram for vending machine • Outputs are associated with inputs along transition arcs UBC / 2000 ELEC 256 / Saif Zahir Moore and Mealy Machines: State Tables Vending Machine Example PS inputs Q1 Q0 D N S0 S1 S2 S3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 NS outputs Q1+ Q0+ OPEN 0 0 1 X 0 1 1 X 1 1 1 X 1 1 1 X 0 1 0 X 1 0 1 X 0 1 1 X 1 1 1 X 0 0 0 X 0 0 0 X 0 0 0 X 1 1 1 X PS inputs Q1 Q0 D N S0 S1 S2 S3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 NS outputs Q1+ Q0+ OPEN 0 0 1 X 0 1 1 X 1 1 1 X 1 1 1 X 0 1 0 X 1 0 1 X 0 1 1 X 1 1 1 X 0 0 0 X 0 0 0 X 0 1 1 X 1 1 1 X Moore machine state table Mealy machine state table Outputs are associated with states (graph nodes) Outputs are change with inputs UBC / 2000 ELEC 256 / Saif Zahir Binary string Recognizers Example: Construct an FSM that receives a bit-serial binary input W and asserts its output Z whenever its input string has at least two 1’s in sequence. Solution: (1,a) - Input-output behavior CLK W Z 1 2 3 4 5 6 7 8 9 A B C D 0 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 (1.b) - Define states (Moore model) S0: received 0 (most recently) S1: received 1 (most recently) S2: received two 1’s in sequence Z=0 Z=0 Z=1 0 (2) - State diagram (Moore model) S0 (Z=0) W=0 1 S1 (0) 0 UBC / 2000 1 S2 (1) 1 ELEC 256 / Saif Zahir Binary string Recognizers Example: Binary string recognizer (3) - State assignment: 3 states means that we need two bits to represent each state State S0 S1 S2 Q1 0 0 1 D1 Q0 0 1 1 CLK D0 CLK IN W 0 1 0 1 0 1 0 1 NS OUT Q1+ Q0+ Z 0 0 0 0 1 0 0 0 0 1 1 0 x x x x x x 0 0 1 1 1 1 Q Q1 W PS Q1 Q0 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 D FF D1 D0 0 0 0 1 0 0 1 1 x x x x 0 0 1 1 d1 = wq0 d0 = wq0 + wQ1 z = q1 UBC / 2000 R D Q R Q0 Z ELEC 256 / Saif Zahir Binary string Recognizers Example: Binary string recognizer (1.b) - Define states (Mealy model) S0: received 0 (most recently) S1: received at least one 1 (most recently) 1/1 (2) - State diagram (Mealy model) S0 1/0 (3) - State assignment (S0 := 0 , S1 := 1) PS Q 0 0 1 1 IN W 0 1 0 1 NS OUT Q+ Z 0 0 1 0 0 0 1 1 W=0/Z=0 D 0 1 0 1 T 0 1 1 0 J 0 1 X X Z=WQ D=W T=W xor Q J=W K=W 0/0 K X X 1 0 Z W Output D-FF: T-FF: JK-FF: S1 D CLK \RESET UBC / 2000 Q ELEC 256 / Saif Zahir Analysis of FSMs Problem Given the hardware schematic of a sequential machine, determine its state behavior and output functions. Example: Analyze the following sequential circuit Solution: 1- Find JK input equations ja = x jb = x z=b X \B X ka = xB kb = x A J 2- Compute next-state equations J K CLK \RESET a+ = ja A + Ka a = xA + (X+b)a b+ = jb B + Kb b = xB + (XA+Xa)b AB 00 01 11 10 0 0 0 1 1 1 1 1 1 0 X AB 00 01 11 10 0 0 0 1 0 1 1 1 0 1 X K-map for A+ A K X \A X Q UBC / 2000 K-map for B+ Q Z=B ELEC 256 / Saif Zahir FSM Analysis AB 00 01 11 10 0 0 0 1 1 1 1 1 1 0 X S0 S1 S2 S3 A B 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 X 0 1 0 1 0 1 0 1 A+ 0 1 0 1 1 0 1 1 B+ 0 1 0 1 0 1 1 0 More Machine: output isf function of present state only, Z=B Z (=B) 0 0 1 1 0 0 1 1 X=0 AB 00 01 11 10 0 0 0 1 0 1 1 1 0 1 X X=1 S0 Z=0 K-map for A+ S3 Z=1 1 0 S1 Z=1 UBC / 2000 1 K-map for B+ 1 S2 Z=0 0 0 ELEC 256 / Saif Zahir Sequential (Bit-Serial) Adder Design Sequential adder operation to add two numbers A=ak ak-1 . . . a1 a0 and B=bk bk-1 . . . b1 b0 - start by adding a0 and a0 - output sum bit s0 and store carry bit c0 so that it is added to bits a1 and b1 in the next clock cycle - repeat the procedure for bits ai and bi (output si and store carry bit ci) Z Clock cycle 4 3 2 1 1 0 0 1 1 1 1 0 LSB SUM A 0 1 0 1 0 0 0 1 B Direct Design 0 0 1 0 Implement design using a combinational logic block that generates next-state and output functions, and a storage Present state element (D-FF) to store present state Mealy Model C Next state 1 Q S D QRC CLK \CLR UBC / 2000 ELEC 256 / Saif Zahir Sequential Adder Design using Formal Methods AB=11/Z=0 Inputs: A, B Output: Z=SUM RESET States (last carry bit): S0: carry was 0 S1: carry was 1 PS Q IN A B NS Q+ 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 01/0 10/0 11/1 S1 00/0 01/1 10/1 OUT Z D 0 1 1 0 1 0 0 1 S0 0 0 0 0 1 1 1 1 FF J K 0 0 0 1 x x x x x x x x 1 0 0 0 00/1 AB 00 01 11 10 0 0 0 1 0 1 X X Q AB 00 Q 01 0 X X 1 1 0 X X 11 K-map for J 10 X X K-map for K 0 0 Z = A xor B xor Q D= Q j = ab UBC / 2000 k = AB ELEC 256 / Saif Zahir Moore Machine Realization of Sequential Adder More states are required for Moore Model S0: S1: S2: S3: C=0 and Z=0 (C=carry, Z:sum) C=0 and Z=1 C=1 and Z=0 C=1 and Z=1 Two flipflops are needed to implement the Moore Model sequential adder State Diagram 00 S0 Z=0 RESET Ex.: Implement this state diagram using D, flipflops and JK flipflops 11 01 10 S2 Z=0 11 01 10 00 01 10 11 00 01 10 S0 Z=0 00 S2 Z=0 11 UBC / 2000