Combinational and sequential circuits compared

• Combinational ciruit
• Behavior:  Output values depend (essentially) ONLY on the present input values. (Neglecting gate delays).
• Cartoon model of gate delay: "Bill" watches the inputs and sets the output switch according to the truth table.
• Structure: Acyclic network of gates:  There is never a sequence of 1 or more gates that are connected in a cycle.
Definition of cycle: G₁, G₂, ..., G_n with an output of G_i connected to an input of G_i+1 for 1<=i<=n-1 AND an output of G_n connected to an input of G₁.
• An acyclic structure guarantees the ciruit has combinational behavior.
• Sequential circuit
• Behavior: The output can depend on past as well as present input values.
• Cycle examples: 1 gate and 3 gates.
• 2 input NAND gate with feedback connection:
• Truth table analysis leads to a contradiction.
• Oscillation occurs in reality when gate delay is taken into account.
• Cross connected NOR gates
• Implement the "SR latch"
• Timing diagram analysis.
• Output when inputs S=0 and R=0 depend on current state.
• Introduction to a state transition table: output and new state depend on old state in addition to current input.

• Reading reference:  Patterson and Hennessy Appendix B.

• Combinational and Sequential systems compared more:

Combinational system function: compute Boolean functions; no memory  (except for gate delays)
Combinational system structure: Acyclic :  No directed cycles.
Combinational system formation rules: Begin with any number of NOT, OR or AND gates. Connect outputs to inputs:
(a) Never connect two outputs.
(b) Never form a directed cycle.
Sequential systems generally do have memory.  In general, computers do computation and have memory.
Memory contents:
• Depends of past "experience," which is called history.
• Is called state.  The idea of modeling by a set of states is crucial to this and other computer science subjects!
• Current state plus inputs Determine   new state plus outputs.
• Example of forming an exclusive OR implementation by applying the formation rules.
• What if you violate formation rule (a)? On the one hand, the behavior of the theoretical model can be contradictory, so no behavior exists.  Practically, you can always wire gates together any way you want in a laboratory (such as PHY454). In some gate families, this causes disaster.  This really can happen if different interface cards plugged into a computer try to access memory at once:  They might both burn out.  In others, wiring two outputs together results in a well defined function such as AND or OR.  That is called a "wired AND" or "wired OR".  Digital design engineers who want to keep their jobs better know these details for the family they are using!
• What if you violate formation rule (b), so that there are feedback paths?

As described in lecture 06, the circuit could oscillate.  You can build an oscillator on purpose this way.  When you do that, it is a good idea to use an RC (resistor-capacitor) or crystal coupling in the feedback path so that you can make the oscillator's frequency be what you choose.  We will avoid oscillating circuits in this course.
Also as described for the two cross connected NOR gates in last lecture, the circuit could remember.  The output then depends on PAST inputs as well as current inputs.  The system has STATE.
• The "D transparent latch": C is clock input, D is data input, output Q reflects the state, Q follows D when C=1, and Q equals the D value when C was last 1 when C=0.  Inplemented with RS latch driven by 2 AND gates. Symbol for D transparent latch. Qbar output.
• Problematic attempt to build a 1 bit counter from a transparent D latch.
• What clock frequency means, clock frequency is called "Megahertz" by people who don't know what it means, Hertz (clock cycles per second) and Megahertz (millions of clock cycles per second) are units used to measure clock frequency.  This is the significance of the clock frequency numbers used in computer advertisements, such as "700 Megahertz"
• The 1 bit counter built from a clocked D latch will oscillate at an uncontrolled rate if the time during when C=1 is too long.  "Too long" is longer than the total gate delay within the D latch plus propagation time through the feedback path.
• In real computers, transitions of state are orchestrated by a clock signal.  The clock is like an orchestra conductor who keeps time, so all players strike their instruments at about the same time.
• D flip-flop with falling edge trigger:  Build with two transparent D latches in master-slave configation.  Input to the slave follows the external D input when C=1 and then slave ignores its input.  When C=0, the slave reflects the data from the master but the master ignores external input D.  Symbol for D flip-flop.  Difference between "flip-flop" and "latch".
• Timing diagram that explains master-slave implementation of the D flip-flop.
• How to analyze a sequential circuit: Example from section 1-7 of Mano, done first without outputs.
• Lay out state transition table:  Left side columns for inputs and current state.  Right hand side column for new state.
• For each row, analyze combinational gates to determine current inputs to the flip-flops.
• For each row, write the new state of each flip-flop based on that flip-flop's inputs and that flip-flop's operation.
• Example begun with rows X=0,A=0,B=0 and X=1,A=0,B=0.  X is the input variable and A, B are the state variables.

• Sequential systems have state.  Role of state in Patterson and Hennessy's problem B.21, why 4 states are needed, implementation using a mechanical stepper switch.  State assignment means choosing what combination of 0s and 1s stored in each flip-flop corresponds to each state.  It's solution is somewhat arbitrary but it affects the efficiency of the combinational part of the sequential system.
• Conclusion analysis example: one more state transition table line (row 011) of Mano's example.
• Separation  of sequential system into memory and combinational parts.
• State transition diagram: Meaning of node (circle) labels, arc (directed edge or arrow) input (and output) labels, related to our table.
• Timing of state transitions and propagation of signals through the combinational system.
• PH appendix figs. B.10 and B.11
• This course uses synchronous systems only.  All flip-flops can be assumed to change states at the same time.  The same clock signal goes to all the flip-flops' clock inputs, and the clock signal is not connected to anything else.  Real computer engineers carefully  design clock generation and transmission networks so that the clock signals arrive at all the the flip-flops "close enough" in time so that the computer works correctly under this assumption.
• Master-Slave and Edge triggered flip-flop timing diagrams.  Setup and hold times, general idea of safety factors in engineering and its relevance to personal computer clock frequencies and the practice of overclocking.  (That's the practice of deliberately setting your computer's clock frequency higher than the frequency the CPU and other circuits were designed for, in a sometimes misguided effort to obtain higher performance.)
• Recall of progression from RS latch to transparent latch to flip-flop and the motivation for the well defined state change point called the clock tick.   Clocking disciplines prevent oscillation or instability when signal changes propagate through the combinational system faster than in the maximum time.

Design of 2 bit counter built from D flip-flops: State transition diagram, state assignment, excitation table generated, synthesis of logic to drive D inputs done with Karnaugh maps.

Design method steps: Given state diagram or specification (named states, transitions, outputs)

1. Invent state encoding.  (State name -> bit string)
2. Draw transition table.
3. Apply excitation table for the kind of flip-flops used to calculate the flip-flop inputs for each row.

Critical: Label the flip-flops.  (Remarks on labels on machinery parts and unrealistic science fiction movies.)
4. Design combinational circuit whose inputs are (present state code,external input) and outputs are the flip-flop inputs.
5. If outputs are required, design combinational circuit to generate them.  Usual CPU control systems have outputs that depend only on current state, not on external inputs.

Shortcut: Multiplexor built with 2 AND gates and an OR gate to make a D flip-flop keep its old state when input X=0.

Master-slave JK flip-flop

1. Built from transparent SR latch and transparent D latch.
2. Analysis
3. Description by characteristic table.
4. Description by state transition table compared to characteristic table.  Both are used for analysis
5. Excitation table  used for design.  It specifies  "don't care" values for some cases.

Design of 2-bit counter with JK flip-flops (ref. Mano) note K-maps with don't cares and combinational circuits simpler than those from D flip-flop design.

4 bit counting done with JK flip-flops and carry chain.

Related first to adding 1 to binary numerals.  Observe how carries behave.

Use of J=K=1 to make JK flip-flop "flip" and J=K=0 to make it keep previous state.

• 4-bit counter with carry chain, carry chain described separately.

Practice problem: Relate Manos' fig 2-10 with fig 2-11 and PH section 4.3 (on addition of binary numerals, with carrying).  Compare to the combinational word adder built with full adders.
• Block diagram (outer view) of 4 bit counter.  New data inputs. Function table.
• CSI333 covered programmer visible or architectural registers.  In CSI404, we say a register is a group of flip-flops.
• Practical flip-flops have asynchronous clear and often asynchronous preset inputs.  Reset control function preformed when a computer is turned on.
• Negative logic is used for clear, preset and often enable inputs.  Notation: bar or *.  Logic "False" means perform indicated function.
• State transition diagram for the 4 bit counter, with state encoding described.
• State transition table for the 4 bit counter.
• Hardware description language description:

S := reg[4]; Count := input signal;
if( Count == 1 ) then S <- S + 1;
(Registers keep old contents if no statements to change them is enabled.)
• 4 bit counter implemented with combinational 4 bit incrementer.
• Abbreviations of bundles of wires by "/ number" notation.  Such bundles are called busses.
• Shift to refinements of combinational logic (next topic).

 CSI404 Home Page