Design of sequential circuits

Sequential circuits and state

Definition. A sequential circuit has memory, so its output may depend on both present inputs and stored state. A clocked synchronous circuit updates state only at designated clock events; an asynchronous circuit may respond to input changes without waiting for a clock. State is the minimum information needed to predict future behavior from future inputs.

Example. A one-bit toggle circuit remembers whether its output was 0 or 1 before the current clock edge.

Exam point. If two histories lead to the same state and the same future inputs, their future outputs must match.

Latches and level sensitivity

Definition. A latch is level-sensitive: while its enable level is active, its output can follow the input; while disabled, it holds the last value. An SR latch has set and reset controls, but one input combination may be forbidden or device-dependent. A D latch avoids that ambiguity by using a single data input and an enable.

Example. An enabled D latch with $D=1$ stores 1; after enable goes inactive it retains 1 even if $D$ changes.

Exam point. A latch is not edge-triggered; data may pass through during the active level.

SR latch behavior

Definition. In an active-high NOR SR latch, $S=1,R=0$ sets $Q=1$, and $S=0,R=1$ resets $Q=0$. With both inputs 0, the latch holds its state. With both inputs 1, both NOR outputs are forced low and complementary outputs are lost; this condition is invalid for the standard latch model.

Example. If $Q=0$ and then $S=1,R=0$, the new state is $Q=1$.

Exam point. SR input conventions differ between NOR and NAND implementations; confirm polarity.

$S$	$R$	$Q^+$	Meaning
0	0	$Q$	hold
0	1	0	reset
1	0	1	set
1	1	invalid	forbidden condition

D latch and D flip-flop

Definition. A D latch copies $D$ to $Q$ while its enable is active and stores the last value while disabled. A D flip-flop samples $D$ at its active clock edge and changes state after that edge, subject to setup and hold requirements. Both have the next-state relation $Q^+=D$ at the relevant sampling condition.

Example. If a positive-edge D flip-flop has $D=0$ just before the rising edge, its next state is 0.

Exam point. “At the edge” and “while enabled” describe different storage behavior.

Edge-triggered flip-flops

Definition. An edge-triggered flip-flop updates on a rising or falling clock transition, depending on its design. The state is stable between active edges in the ideal model. Real devices require input stability in a window around the edge, defined by setup time before and hold time after it.

Example. A positive-edge device ignores a data change that occurs well after the rising edge until the next rising edge.

Exam point. Do not treat a positive-edge device as transparent throughout the high clock level.

Characteristic equations

Definition. A characteristic equation gives a flip-flop's next state as a function of its present state and inputs. For a D flip-flop, $Q^+=D$; for a T flip-flop, $Q^+=T\oplus Q$; for a JK flip-flop, $Q^+=JQ'+K'Q$. These equations assume an active clock edge and ideal Boolean operation.

Example. A T flip-flop toggles when $T=1$ and holds when $T=0$.

Exam point. The superscript plus denotes next state, not Boolean OR.

$J$	$K$	$Q^+$ for present $Q$	Meaning
0	0	$Q$	hold
0	1	0	reset
1	0	1	set
1	1	$Q'$	toggle

Solved calculation. A JK flip-flop begins with $Q=0$ and receives $J=K=1$ for three active edges.

1. First edge toggles 0 to 1.
2. Second edge toggles 1 to 0.
3. Third edge toggles 0 to 1. Answer. The successive states after the edges are 1,0,1.

Excitation tables

Definition. An excitation table specifies the input needed to cause a desired transition from present state $Q$ to next state $Q^+$. It is used to design a circuit with a chosen flip-flop type. X marks an input value that may be either 0 or 1 for that transition.

Example. A T flip-flop must have $T=1$ for a transition 0 to 1.

Exam point. Characteristic tables map inputs to next state; excitation tables map desired transitions to inputs.

$Q$	$Q^+$	D	T	J	K
0	0	0	0	0	X
0	1	1	1	1	X
1	0	0	1	X	1
1	1	1	0	X	0

Solved calculation. Find T and JK inputs for a transition $Q=1$ to $Q^+=0$.

1. The T flip-flop toggles, so $T=1$.
2. JK reset requires $J=0,K=1$; the excitation table allows $J=X,K=1$.
3. Choose $J=0$ as a convenient legal value. Answer. $T=1$; for JK, $J=X,K=1$ (choose $J=0$).

State tables and state diagrams

Definition. A state table lists present state, input, next state, and output. A state diagram represents the same information as labeled nodes and directed edges. State bits encode abstract states into binary values; the encoding affects logic complexity but not the specified sequence of behavior.

Example. A two-state detector has states “not seen 1” and “seen 1”; an input 1 moves to the latter state.

Exam point. Clearly distinguish present-state columns from next-state columns.

Solved design. Create a Moore state table for a machine whose output is 1 only in state $S_1$, and which toggles state for input $X=1$ while holds for $X=0$.

1. Present states are $S_0,S_1$.
2. For $X=0$, next state equals present state.
3. For $X=1$, next state is the other state.
4. A Moore output depends on state only.

Present state	$X$	Next state	Output $Z$
$S_0$	0	$S_0$	0
$S_0$	1	$S_1$	0
$S_1$	0	$S_1$	1
$S_1$	1	$S_0$	1

Answer. Output is attached to the present state, so the two rows for each state share the same output.

Moore and Mealy machines

Definition. A Moore output depends only on the present state; a Mealy output depends on present state and current input. Mealy machines can sometimes use fewer states or respond within the current input interval, but their outputs may change when inputs change between clock edges. The choice depends on timing and interface requirements.

Example. A Moore detector may assert one cycle after recognizing a final input bit; a Mealy detector may assert on the transition that recognizes it.

Exam point. Read output labels: a Moore node carries output; a Mealy edge carries input/output.

Solved comparison. A detector recognizes the sequence 10. Explain the output timing for a Moore and a Mealy implementation.

1. After reading 1, the machine remembers that a possible prefix has occurred.
2. When the next bit 0 arrives, a Mealy transition can assert output on that transition.
3. A Moore machine enters a dedicated detected state whose output is 1.
4. The output is then associated with the new state and may be viewed as one state transition later depending on the sampling convention.
5. Exact cycle timing must be read from the defined output and clock convention. Answer. Mealy output is edge/transition dependent; Moore output is state dependent. The state diagram determines precise cycle alignment.

Sequence detector with overlap

Definition. A sequence detector asserts an output when the recent input history matches a target bit pattern. An overlapping detector reuses a suffix of a recognized pattern as a prefix for a later match. States represent useful matched prefixes, including the empty prefix.

Example. After recognizing 101, a trailing 1 may already be the start of another 101.

Exam point. For every state and input, retain the longest suffix that is also a prefix of the target pattern.

Solved design. Build a Moore detector for pattern 10, allowing overlap. Use states $S_0$ (no prefix), $S_1$ (seen 1), and $S_2$ (detected 10).

1. From $S_0$, input 0 stays $S_0$; input 1 moves to $S_1$.
2. From $S_1$, input 1 stays $S_1$ because the latest 1 is a possible prefix; input 0 completes 10 and moves to $S_2$.
3. From $S_2$, input 1 moves to $S_1$ because it can start a new pattern; input 0 moves to $S_0$.
4. Only $S_2$ has output 1.

Present state	Input 0: next state	Input 1: next state	Output
$S_0$	$S_0$	$S_1$	0
$S_1$	$S_2$	$S_1$	0
$S_2$	$S_0$	$S_1$	1

Answer. The transition from $S_2$ on 1 returns to $S_1$, preserving overlap.

State assignment and next-state logic

Definition. State assignment maps symbolic states to binary codes. With $N$ states, at least $\lceil\log_2 N\rceil$ flip-flops are needed for a compact binary encoding. One-hot encoding uses one flip-flop per state and can simplify next-state equations at the cost of more storage.

Example. Five states need at least three binary state bits because $2^2<5\le2^3$.