Digital Techniques: Logic, Registers, Counters and Comparators
CSIR NET electronics: Boolean algebra, K-maps, magnitude comparators, flip-flops, shift registers, ripple and synchronous counters, with practice.
- 18 min
On this page · 15 sections
Prerequisites
- Semiconductor Devices: Junctions, Diodes, BJTs, FETs and Heterojunctions: CMOS inverters and transistor switches are the physical gates.
- Operational Amplifiers: the analogue comparator, which turns a voltage into a logic level.
- Binary and modular arithmetic; the pattern-spotting habits of Number, Letter and Pattern Series help with counter sequences.
The Hook: Counting Photons One Clock at a Time
Number Systems and Codes
| Code | Rule | Example |
|---|---|---|
| Binary | base 2 | \( 1011_2 = 11 \) |
| Hexadecimal | base 16, groups of 4 bits | \( 1011\,1110_2 = \text{BE}_{16} = 190 \) |
| BCD | each decimal digit in 4 bits | \( 59 = 0101\,1001 \) |
| 2’s complement | invert all bits and add 1 | \( -5 \) in 4 bits \( = 1011 \) |
| Gray code | adjacent values differ in one bit; \( g_i = b_i \oplus b_{i+1} \), MSB unchanged | binary 0110 → Gray 0101 |
An \( n \)-bit 2’s-complement number ranges from \( -2^{n-1} \) to \( 2^{n-1} - 1 \). Overflow in addition occurs when two numbers of the same sign give a result of the opposite sign. Gray code is used in shaft encoders because only one bit changes at each step, so a misread at a boundary is off by at most one count.
Boolean Algebra
| Law | AND form | OR form |
|---|---|---|
| Identity | \( A\cdot1 = A \) | \( A + 0 = A \) |
| Null | \( A\cdot0 = 0 \) | \( A + 1 = 1 \) |
| Idempotent | \( AA = A \) | \( A + A = A \) |
| Complement | \( A\bar A = 0 \) | \( A + \bar A = 1 \) |
| Absorption | \( A(A + B) = A \) | \( A + AB = A \) |
| Redundancy | \( A(\bar A + B) = AB \) | \( A + \bar AB = A + B \) |
| De Morgan | \( \overline{AB} = \bar A + \bar B \) | \( \overline{A + B} = \bar A\bar B \) |
Universal gates: NAND alone (or NOR alone) can build any function. NOT is a NAND with tied inputs; AND is NAND followed by NOT; OR is NAND of inverted inputs (De Morgan).
XOR \( A \oplus B = A\bar B + \bar AB \) is 1 when inputs differ; XNOR \( A \odot B \) is 1 when they are equal. XOR is the parity function and the sum bit of an adder; XNOR is the equality detector of a comparator.
Karnaugh maps
Arrange minterms in Gray-code order so that adjacent cells differ in one variable. Group 1s in rectangles of 1, 2, 4, 8 … cells (wrapping round the edges); each group of \( 2^k \) cells eliminates \( k \) variables. “Don’t care” cells may be included to enlarge groups.
Combinational Building Blocks
| Block | Function | Key fact |
|---|---|---|
| Half adder | \( S = A \oplus B \), \( C = AB \) | no carry in |
| Full adder | \( S = A \oplus B \oplus C_{in} \), \( C_{out} = AB + C_{in}(A \oplus B) \) | two half adders and an OR |
| Multiplexer (\( 2^n \):1) | selects one of \( 2^n \) inputs with \( n \) select lines | can realise any function of \( n \) variables (or \( n + 1 \) with the extra variable on data inputs) |
| Decoder (\( n \) to \( 2^n \)) | one output high per input code | generates all minterms; memory chip selection |
| Encoder / priority encoder | reverse of decoder | priority version reports highest active input |
| Parity generator | XOR chain | odd or even parity bit for error detection |
Digital comparators
A 1-bit comparator produces three outputs:
$$G = A\bar B \ (A > B), \qquad E = \overline{A \oplus B} = A \odot B \ (A = B), \qquad L = \bar AB \ (A < B)$$For two 4-bit numbers \( A_3A_2A_1A_0 \) and \( B_3B_2B_1B_0 \), define \( x_i = A_i \odot B_i \) (bit \( i \) equal). Compare from the most significant bit down:
$$E = x_3x_2x_1x_0$$$$G = A_3\bar B_3 + x_3A_2\bar B_2 + x_3x_2A_1\bar B_1 + x_3x_2x_1A_0\bar B_0$$$$L = \bar A_3B_3 + x_3\bar A_2B_2 + x_3x_2\bar A_1B_1 + x_3x_2x_1\bar A_0B_0$$The first unequal bit, scanning from the MSB, decides. Exactly one of \( G \), \( E \), \( L \) is 1. Comparators are cascaded for wider words by feeding the lower stage’s \( G \), \( E \), \( L \) into the next stage’s cascade inputs, which matter only when all of the higher bits are equal.
Do not confuse this digital magnitude comparator with the analogue voltage comparator (an op-amp without negative feedback), which decides whether one voltage exceeds another and is the front end of every flash ADC in A/D and D/A Converters.
Sequential Logic: Latches and Flip-Flops
A latch is level-sensitive (transparent while enabled); a flip-flop changes state only on a clock edge.
| Flip-flop | Inputs → next state \( Q^+ \) | Characteristic equation |
|---|---|---|
| SR | 00 hold, 01 reset, 10 set, 11 forbidden | \( Q^+ = S + \bar RQ \), with \( SR = 0 \) |
| D | \( Q^+ = D \) | \( Q^+ = D \) |
| JK | 00 hold, 01 reset, 10 set, 11 toggle | \( Q^+ = J\bar Q + \bar KQ \) |
| T | 0 hold, 1 toggle | \( Q^+ = T \oplus Q \) |
For design you need the JK excitation table (inputs required for a given transition; X = don’t care):
| \( Q \to Q^+ \) | \( J \) | \( K \) |
|---|---|---|
| 0 → 0 | 0 | X |
| 0 → 1 | 1 | X |
| 1 → 0 | X | 1 |
| 1 → 1 | X | 0 |
Race-around: a level-triggered JK with \( J = K = 1 \) toggles repeatedly while the clock is high if the clock pulse is longer than the propagation delay. Cures: a master–slave arrangement (master follows the inputs while the clock is high, slave copies the master when it falls) or edge triggering. Real flip-flops also need data stable for a set-up time before and a hold time after the active edge.
Registers
A register is a set of flip-flops sharing a clock, storing a word. Shift registers move the word one place per clock.
| Type | Load | Read | Clocks to load \( n \) bits |
|---|---|---|---|
| SISO (serial in, serial out) | serial | serial | \( n \) (and \( n \) more to read out) |
| SIPO | serial | parallel | \( n \) |
| PISO | parallel | serial | 1 to load, \( n \) to shift out |
| PIPO | parallel | parallel | 1 |
| Universal (bidirectional) | either | either | mode select lines choose hold, shift left, shift right, load |
Uses: serial–parallel conversion (UARTs, the serial port of a microcontroller), delay lines (an \( n \)-stage SISO delays data by \( n \) clock periods), and arithmetic: shifting a binary number left multiplies by 2, shifting right divides by 2 (with an arithmetic shift preserving the sign bit for 2’s-complement numbers).
Counters
Asynchronous (ripple) counters
Connect T flip-flops (or JKs with \( J = K = 1 \)) in a chain: the external clock drives the first, and each flip-flop’s output clocks the next. Each stage divides frequency by 2, so an \( n \)-stage ripple counter is mod-\( 2^n \) and its last output runs at \( f_{clk}/2^n \).
The weakness is accumulated delay: the last stage changes \( n\,t_{pd} \) after the clock edge. For all outputs to settle before the next edge,
$$\boxed{f_{clk,\max} = \frac{1}{n\,t_{pd}}}$$During the ripple the outputs pass through transient wrong states, which cause glitches if decoded.
Mod-\( N \) by reset: use \( \lceil\log_2N\rceil \) flip-flops and a gate that detects the count \( N \) and clears all flip-flops. A decade (mod-10) counter detects 1010 (\( Q_3 \) and \( Q_1 \) both 1) and resets; the state 1010 exists momentarily.
Synchronous counters
All flip-flops share one clock; logic decides which ones toggle. For a binary up-counter with T flip-flops, stage \( i \) toggles when all lower bits are 1:
$$T_0 = 1, \quad T_1 = Q_0, \quad T_2 = Q_0Q_1, \quad T_3 = Q_0Q_1Q_2$$All outputs change together (one \( t_{pd} \) after the edge), so there are no ripple glitches and the speed does not fall with \( n \). For a down counter, use \( \bar Q \) instead of \( Q \).
Designing a synchronous counter: write the state table, use the excitation table to find each flip-flop’s required inputs, simplify each with a K-map, and check unused states (a counter is self-starting if every unused state leads eventually into the main sequence).
Shift-register counters
| Counter | Feedback | States with \( n \) flip-flops | Remarks |
|---|---|---|---|
| Ring counter | \( Q_{last} \to D_{first} \) | \( n \) | one hot bit circulates; needs presetting to one 1 |
| Johnson (twisted ring) | \( \bar Q_{last} \to D_{first} \) | \( 2n \) | decoded with 2-input gates; glitch-free |
| Maximal-length LFSR | XOR of chosen taps \( \to D_{first} \) | \( 2^n - 1 \) | all-zero state locks up; pseudo-random sequences |
| Need | Flip-flops | Example |
|---|---|---|
| Mod-\( N \) binary or decoded counter | \( \lceil\log_2N\rceil \) | mod-12 needs 4 |
| Johnson mod-\( N \) (\( N \) even) | \( N/2 \) | mod-10 needs 5 |
| Ring mod-\( N \) | \( N \) | mod-10 needs 10 |
Frequency division
Counters in cascade multiply their moduli: a 1 MHz clock through a mod-10 counter and then a mod-8 counter gives 1 MHz / 80 = 12.5 kHz at the last output. A mod-\( N \) binary counter’s MSB is not a square wave unless \( N \) is a power of 2: in a decade counter \( Q_3 \) is high only for counts 8 and 9, a 20% duty cycle.
graph LR
A[Clock 1 MHz] --> B[Mod-10 counter]
B -->|100 kHz| C[Mod-8 counter]
C -->|12.5 kHz| D[Register latches count]
D --> E[Magnitude comparator]
E -->|count above threshold| F[Flag]Memory Tricks
Don’t Confuse
| This | With this | The difference |
|---|---|---|
| Latch | Flip-flop | level-sensitive, transparent while enabled; edge-triggered |
| Ripple counter | Synchronous counter | clock passes stage to stage, delays add, glitches; common clock, outputs change together |
| Ring counter | Johnson counter | \( Q \) fed back, \( n \) states; \( \bar Q \) fed back, \( 2n \) states |
| Magnitude comparator | Voltage comparator | digital words, outputs \( G, E, L \); analogue voltages, op-amp without feedback |
| SR forbidden state | JK toggle | \( S = R = 1 \) undefined; \( J = K = 1 \) toggles |
| Mod-\( N \) | number of flip-flops | number of states in the cycle; \( \lceil\log_2N\rceil \) for a binary counter |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper.
Level 1: Foundation
- How many flip-flops does a mod-12 binary counter need?
- How many states does a Johnson counter built from 4 flip-flops have?
- Write \( -6 \) in 4-bit 2’s complement.
Answers
- 4. \( 2^3 = 8 < 12 \leq 16 = 2^4 \).
- 8 (\( 2n \)).
- 1010. \( 6 = 0110 \); invert to 1001; add 1: 1010.
Level 2: Part B Style
Practice Q1. The function \( f(A, B, C, D) = \sum m(0, 2, 5, 7, 8, 10, 13, 15) \) simplifies to:
(a) \( A \oplus C \) (b) \( B \odot D \) (c) \( \bar B\bar D \) (d) \( B \oplus D \)
Answer: (b) B ⊙ D
Corners (0, 2, 8, 10) give \( \bar B\bar D \); the central square (5, 7, 13, 15) gives \( BD \). Sum: \( \bar B\bar D + BD = B \odot D \). (c) is only one of the two groups; (d) is the complement.
Practice Q2. A 4-bit ripple counter uses flip-flops with propagation delay 10 ns each. If all outputs must settle within one clock period, the maximum clock frequency is:
(a) 100 MHz (b) 50 MHz (c) 25 MHz (d) 6.25 MHz
Answer: (c) 25 MHz
Worst-case settling \( = 4 \times 10 = 40 \) ns, so \( f_{\max} = 1/40\ \text{ns} = 25 \) MHz. (a) is the limit for a synchronous counter (one delay); (d) divides by \( 2^4 \) as well.
Practice Q3. A 1 MHz clock drives a mod-10 counter whose most significant output drives a mod-8 counter. The frequency at the most significant output of the second counter is:
(a) 125 kHz (b) 12.5 kHz (c) 1.25 kHz (d) 55.6 kHz
Answer: (b) 12.5 kHz
Total division \( 10 \times 8 = 80 \): \( 10^6/80 = 12.5 \) kHz. (d) adds the moduli (\( 10^6/18 \)).
Practice Q4. A 4-bit serial-in parallel-out shift register \( Q_AQ_BQ_CQ_D \) is cleared to 0000. Data enter at \( Q_A \) and shift towards \( Q_D \). The serial bits 1, 1, 0, 1 are applied in that order, one per clock. After the fourth clock, \( Q_AQ_BQ_CQ_D \) is:
(a) 1101 (b) 1011 (c) 0111 (d) 1110
Answer: (b) 1011
| Clock | Input | \( Q_AQ_BQ_CQ_D \) |
|---|---|---|
| 1 | 1 | 1000 |
| 2 | 1 | 1100 |
| 3 | 0 | 0110 |
| 4 | 1 | 1011 |
The first bit entered has reached \( Q_D \). (a) is the input order, the classic reversal trap.
Level 3: Part C Style
Practice Q5. A synchronous counter uses three JK flip-flops \( A \) (MSB), \( B \), \( C \) (LSB) with
$$J_A = BC,\ K_A = 1; \qquad J_B = C,\ K_B = C + A; \qquad J_C = \bar A,\ K_C = 1$$Consider:
- Starting from 000, the counter goes 0, 1, 2, 3, 4, 0, …
- The counter is self-starting.
- From the unused state 5 (101) the next state is 6 (110).
- Output \( A \) has frequency \( f_{clk}/5 \) and is high for one clock period in five.
Which are correct?
(a) 1 and 2 only (b) 1, 2 and 4 only (c) 1, 3 and 4 only (d) 1, 2, 3 and 4
Answer: (b) 1, 2 and 4 only
Use \( Q^+ = J\bar Q + \bar KQ \).
| \( ABC \) | \( J_AK_A \) | \( J_BK_B \) | \( J_CK_C \) | Next |
|---|---|---|---|---|
| 000 | 0 1 | 0 0 | 1 1 | 001 |
| 001 | 0 1 | 1 1 | 1 1 | 010 |
| 010 | 0 1 | 0 0 | 1 1 | 011 |
| 011 | 1 1 | 1 1 | 1 1 | 100 |
| 100 | 0 1 | 0 1 | 0 1 | 000 |
| 101 | 0 1 | 1 1 | 0 1 | 010 |
| 110 | 0 1 | 0 1 | 0 1 | 000 |
| 111 | 1 1 | 1 1 | 0 1 | 000 |
- True: a mod-5 sequence. 2. True: 5 → 2, 6 → 0, 7 → 0 all enter the cycle. 3. False: 5 goes to 2. 4. True: \( A = 1 \) only in state 4.
Practice Q6. A 3-bit shift register \( Q_2Q_1Q_0 \) shifts \( Q_0 \to Q_1 \to Q_2 \) on each clock, with new \( Q_0 = Q_2 \oplus Q_1 \). It starts at 001. Consider:
- The sequence is 001, 010, 101, 011, 111, 110, 100, 001, …
- The sequence length is 7.
- If the register is ever cleared to 000 it stays there.
- Replacing the XOR by XNOR would make 111 the lock-up state.
Which are correct?
(a) 1 and 2 only (b) 1, 2 and 3 only (c) 2, 3 and 4 only (d) 1, 2, 3 and 4
Answer: (d) 1, 2, 3 and 4
1–2. From 001: new \( Q_0 = 0 \oplus 0 = 0 \), shift gives 010; then \( 0 \oplus 1 = 1 \): 101; \( 1 \oplus 0 = 1 \): 011; \( 0 \oplus 1 = 1 \): 111; \( 1 \oplus 1 = 0 \): 110; \( 1 \oplus 1 = 0 \): 100; \( 1 \oplus 0 = 1 \): 001. Seven distinct states, the maximal \( 2^3 - 1 \). True. 3. \( 0 \oplus 0 = 0 \): 000 maps to itself. True. 4. With XNOR, 111 gives \( 1 \odot 1 = 1 \) and maps to itself. True.
Practice Q7. A decade ripple counter is made from four negative-edge-triggered flip-flops \( Q_3Q_2Q_1Q_0 \), with a NAND gate on \( Q_3 \) and \( Q_1 \) driving the asynchronous clear of all four. A 50 kHz clock is applied. Consider:
- The counter cycles through 0000 to 1001.
- The state 1010 appears only momentarily.
- \( Q_3 \) is a 5 kHz square wave with 50% duty cycle.
- Decoding the count 0000 with a gate may produce narrow glitches.
Which are correct?
(a) 1 and 2 only (b) 1, 2 and 4 only (c) 1, 3 and 4 only (d) 1, 2, 3 and 4
Answer: (b) 1, 2 and 4 only
- On reaching 1010 (\( Q_3 = Q_1 = 1 \)) the NAND output goes low and clears the counter: the stable states are 0 to 9. True.
- 1010 exists only until the clear propagates. True.
- \( Q_3 \) has frequency \( 50/10 = 5 \) kHz, but it is high only for counts 8 and 9: duty cycle 20%. False.
- Ripple transitions and the brief 1010 state pass through intermediate codes; decoded outputs can glitch. True.
Quick Revision Table
| Idea | Formula or fact |
|---|---|
| 2’s complement range | \( -2^{n-1} \) to \( 2^{n-1} - 1 \) |
| Gray code | \( g_i = b_i \oplus b_{i+1} \), one bit changes per step |
| De Morgan | \( \overline{AB} = \bar A + \bar B \), \( \overline{A + B} = \bar A\bar B \) |
| Universal gates | NAND, NOR |
| 1-bit comparator | \( G = A\bar B \), \( E = A \odot B \), \( L = \bar AB \) |
| 4-bit equality | \( E = x_3x_2x_1x_0 \), \( x_i = A_i \odot B_i \) |
| JK | \( Q^+ = J\bar Q + \bar KQ \); 11 toggles |
| D, T | \( Q^+ = D \); \( Q^+ = T \oplus Q \) |
| Race-around | cured by master–slave or edge triggering |
| Shift register | \( n \) clocks to load serially; left shift ×2 |
| Ripple counter | mod-\( 2^n \); \( f_{\max} = 1/nt_{pd} \) |
| Mod-\( N \) | \( \lceil\log_2N\rceil \) flip-flops |
| Ring / Johnson / LFSR | \( n \) / \( 2n \) / \( 2^n - 1 \) states |
| Cascade | moduli multiply |
Key Takeaways
What’s Next
- A/D and D/A Converters, Microprocessors and Microcontrollers: counters, registers and comparators assembled into converters and processors.
- Operational Amplifiers: the analogue comparator and Schmitt trigger that feed logic inputs.
- Electronics and Experimental Methods (Core) overview.
- The logical-reasoning habits of Statements, Syllogisms and Arguments carry over directly to truth tables.