Counters, Shift Registers & Combinational MSI Subsystems

1. Working Principle of Asynchronous (Ripple) Counters

An asynchronous counter (or ripple counter) consists of a cascade of toggle flip-flops (T or JK flip-flops with $J=K=1$) where only the first flip-flop ($FF_0$) is clocked by the external master clock. Each subsequent flip-flop $FF_{i+1}$ is clocked by the output ($Q_i$ or $\bar{Q}_i$) of the preceding stage:

• Negative Edge-Triggered Up-Counter: Clocking $FF_{i+1}$ from output $Q_i$ causes $FF_{i+1}$ to toggle whenever $Q_i$ transitions from $1 \to 0$, creating a standard binary count sequence ($0, 1, 2, \dots, 2^n - 1$).
• Negative Edge-Triggered Down-Counter: Clocking $FF_{i+1}$ from inverted output $\bar{Q}_i$ creates a downward counting sequence ($2^n - 1, \dots, 1, 0$).

2. Propagation Delay Accumulation & Maximum Operating Frequency

Because each flip-flop must wait for the preceding stage to settle, the total propagation delay accumulates linearly with the number of stages $n$:

To avoid false count sampling, the clock period $T_{\text{clk}}$ must be strictly greater than this accumulated delay:

For an 8-bit ripple counter with $t_{pd} = 15\text{ ns}$, $t_{\text{total}} = 120\text{ ns}$, capping clock speed below $8.3\text{ MHz}$. During the transient settling window, intermediate invalid states produce severe false output "glitches".

3. Truncated Modulus Counters (MOD-N Counters)

An $n$-stage binary counter naturally recycles after $2^n$ counts (natural modulus $MOD = 2^n$). To construct a counter with an arbitrary modulus $N < 2^n$ (e.g., a decade / BCD counter with $MOD = 10$ using $n = 4$ flip-flops):

1. Identify the binary representation of target modulus $N$. For $N = 10_{10} = 1010_2$, bits $Q_3 = 1$ and $Q_1 = 1$.
2. Connect $Q_3$ and $Q_1$ to the inputs of an asynchronous NAND gate, and connect the NAND output to the active-LOW asynchronous Clear ($\overline{CLR}$) pins of all four flip-flops.
3. As soon as the counter reaches state $1010_2$, the NAND gate output goes LOW, instantaneously resetting all flip-flops to $0000_2$. The state $1010_2$ persists for only a few nanoseconds (the clear propagation delay), yielding a stable 10-state sequence ($0$ through $9$).

1. The Synchronous Architecture Advantage

In a synchronous counter, all flip-flops are connected to the same common master clock signal. All state transitions occur simultaneously across all stages at the active clock edge. Propagation delay is independent of counter bit length, being limited solely to a single flip-flop delay plus one combinational gating level:

2. Formal Step-by-Step Synthesis Algorithm

1. State Diagram & State Transition Table: Formulate the sequence of present states $Q_n$ and required next states $Q_{n+1}$.
2. Select Flip-Flop Type: Typically JK or D flip-flops. Reference the Excitation Table:

   Transition ($Q_n \to Q_{n+1}$)	Required $J$	Required $K$	Required $D$	Required $T$
   $0 \to 0$	$0$	$\times$	$0$	$0$
   $0 \to 1$	$1$	$\times$	$1$	$1$
   $1 \to 0$	$\times$	$1$	$0$	$1$
   $1 \to 1$	$\times$	$0$	$1$	$0$

3. K-Map Derivation of Flip-Flop Excitation Inputs: Plot $J_i, K_i$ (or $D_i$) as functions of present state variables $Q_k$, exploiting Don't Care states to obtain minimal Boolean equations.
4. Lockout Verification: Analyze unassigned or unused states. If electrical noise drops the counter into an unused state, it must self-recover back to the valid sequence within a finite number of clock cycles rather than circulating indefinitely in a parasitic lockout cycle.

1. Shift Register Functional Topologies

A shift register is an array of cascaded flip-flops configured such that stored binary data moves laterally by one bit position on each clock pulse. The four fundamental operational topologies are:

1. Serial-In Serial-Out (SISO): Data bits enter sequentially one bit per clock pulse and exit sequentially from the final stage. Requires $n$ clock cycles to load and $n$ clock cycles to read out an $n$-bit word. Acts as an accurate time delay line.
2. Serial-In Parallel-Out (SIPO): Data is shifted in serially; once filled after $n$ clock pulses, all $n$ bits are read out simultaneously in parallel. Fundamental to UART serial communication receivers.
3. Parallel-In Serial-Out (PISO): Data is loaded in parallel simultaneously via combinational steering gates, then shifted out serially one bit at a time. Fundamental to UART serial communication transmitters.
4. Parallel-In Parallel-Out (PIPO): Universal high-speed buffer register. Loads and reads $n$ bits simultaneously in a single clock cycle.

2. The Universal Bidirectional Shift Register

A 4-bit Universal Shift Register (e.g., standard 74HC194 IC) incorporates four 4-to-1 multiplexers at the inputs of each D flip-flop, controlled by two mode select lines $(S_1, S_0)$:

• $S_1 S_0 = 00$: Hold / No Change ($D_i = Q_i$).
• $S_1 S_0 = 01$: Shift Right ($D_i = Q_{i-1}$, with $D_3 = \text{Serial Input Right}$).
• $S_1 S_0 = 10$: Shift Left ($D_i = Q_{i+1}$, with $D_0 = \text{Serial Input Left}$).
• $S_1 S_0 = 11$: Parallel Load ($D_i = I_i$).

3. Cyclic Shift Counters: Ring & Johnson Counters

1. Ring Counter: Formed by circulating the serial output of the final stage directly back into the serial input of the first stage ($D_0 = Q_{n-1}$):
   $$\text{Initial State: } 1000_2 \longrightarrow 0100_2 \longrightarrow 0010_2 \longrightarrow 0001_2 \longrightarrow 1000_2$$
   A single circulating '1' decodes directly into $n$ mutually exclusive timing pulses with zero decoding gates, but utilizes only $n$ states out of $2^n$ available states ($MOD = n$).
2. Johnson (Twisted Ring / Moebius) Counter: Formed by feeding back the inverted output of the final stage into the first stage ($D_0 = \bar{Q}_{n-1}$):
   $$\text{States: } 0000 \to 1000 \to 1100 \to 1110 \to 1111 \to 0111 \to 0011 \to 0001 \to 0000$$
   An $n$-stage Johnson counter produces $2n$ states ($MOD = 2n$). Adjacent states differ by only a single bit (unit distance), enabling completely glitch-free decoding with simple 2-input AND gates.

1. Binary Decoders

A decoder is an MSI combinational circuit with $n$ input lines and up to $2^n$ unique output lines. It decodes an $n$-bit binary input code by activating exactly one output line corresponding to that input minterm:

• 3-to-8 Line Decoder (74138 IC): Three inputs $(A_2, A_1, A_0)$ select one of 8 active-LOW outputs ($\bar{Y}_0$ through $\bar{Y}_7$). Contains active-LOW enable inputs ($\bar{E}_1, \bar{E}_2, E_3$) used to cascade multiple decoders into large memory address decoding trees.
• Universal Logic Realization: Because each output of an active-LOW decoder produces an individual minterm $\bar{m}_i = \overline{A B C}$, any arbitrary Boolean function in SOP form can be implemented simply by feeding the appropriate decoder outputs into an external NAND gate (since $\overline{\bar{m}_1 \cdot \bar{m}_4} = m_1 + m_4$).

2. Encoders & Priority Encoders

An encoder performs the inverse operation: it accepts $2^n$ input lines (where only one line is asserted at any time) and outputs an $n$-bit binary code. If multiple inputs can be asserted simultaneously, standard encoders fail.

A Priority Encoder (e.g., 74148 IC) resolves input contention by asserting the binary code of the highest-priority active input, ignoring all lower-priority inputs. It also generates an active Group Select ($GS$) signal indicating whether any valid input is active, forming the foundation of CPU interrupt request (IRQ) controllers.

3. BCD-to-7-Segment Display Drivers (7447 IC)

Drives numerical LED/LCD displays containing seven planar segments labeled $a, b, c, d, e, f, g$. Translates 4-bit BCD input $(D, C, B, A)$ into 7 segment drive signals. For common-anode LED displays, the 7447 provides open-collector active-LOW outputs ($a=0$ lights the segment), incorporating lamp test ($LT$) and automatic zero-blanking inputs ($RBI, RBO$).

1. Multiplexers (Data Selectors)

A Multiplexer (MUX) is a combinational switching subsystem that directs binary information from one of $2^n$ data input channels ($I_0, I_1, \dots, I_{2^n-1}$) to a single output line $Y$, selected by $n$ control select lines ($S_{n-1}, \dots, S_0$):

2. Implementing Arbitrary Logic Functions Using Multiplexers

A $2^n$-to-1 multiplexer can implement any arbitrary Boolean function of $n+1$ variables without requiring any external logic gates:

1. Assign $n$ variables to the MUX select lines $(S_{n-1}, \dots, S_0)$.
2. Express the remaining $(n+1)$-th variable $Z$ as the data input $I_k$ for each select combination. For each minterm pair, $I_k$ will evaluate to either $0$, $1$, $Z$, or $\bar{Z}$.

Multiplexers thus function as universal, software-configurable look-up tables (LUTs), forming the core logic fabric of modern Field-Programmable Gate Arrays (FPGAs).

3. Demultiplexers (DEMUX)

A Demultiplexer takes a single data input line and routes it to one of $2^n$ output lines selected by $n$ address lines. A binary decoder with an enable input is functionally identical to a demultiplexer (the enable acts as the serial data input).