Digital Electronics: Complete Revision Notes

What is Digital Electronics?

An analog signal varies continuously and can take infinitely many values (for example a sinusoid). A digital signal takes only two discrete levels, conventionally interpreted as logic 0 (LOW) and logic 1 (HIGH). Modern computing is built on digital logic because of its noise immunity, ease of storage, programmability, and the predictability of binary arithmetic.

Advantages and Disadvantages of Digital Systems

Digital systems dominate modern design for several reasons:

• Noise immunity: small voltage variations do not change the interpreted logic state.
• Accuracy and precision: any desired precision is achievable simply by adding more bits.
• Easy storage: data can be retained on memory devices indefinitely.
• Reproducibility: identical inputs always produce identical outputs.
• Programmability: functionality can be changed in software.
• Integration: VLSI places millions of gates on a single chip.
• Low cost: mass production reduces per-unit cost.

Positional Number Systems

The weight of a digit at position \(i\) is \(r^i\).

Binary Number System

Example. Convert \((1011.101)_2\) to decimal:

Decimal to Binary Conversion

Example. Convert \((25.375)_{10}\) to binary. For the integer part, successive division of 25 by 2 gives remainders \(1,0,0,1,1\) read bottom-up, so \((25)_{10} = (11001)_2\). For the fraction:

so \((0.375)_{10} = (0.011)_2\). Combining: \(\boxed{(25.375)_{10} = (11001.011)_2}\).

Octal and Hexadecimal

Example. For \((10110101.11010)_2\):

• Octal: \(\underbrace{010}_{2}\,\underbrace{110}_{6}\,\underbrace{101}_{5}.\underbrace{110}_{6}\,\underbrace{100}_{4} = (265.64)_8\)
• Hex: \(\underbrace{1011}_{B}\,\underbrace{0101}_{5}.\underbrace{1101}_{D}\,\underbrace{0000}_{0} = (\text{B5.D0})_{16}\)

Binary Addition and Subtraction

Example. Adding \((1011)_2 + (1101)_2\) yields \((11000)_2 = (24)_{10}\), which checks out since \(11 + 13 = 24\).

Signed Number Representations

1. Sign-magnitude: MSB is the sign, the remaining bits are the magnitude. Range \(-(2^{n-1}-1)\) to \(+(2^{n-1}-1)\); two zeros (\(+0\) and \(-0\)).
2. 1's complement: invert all bits to negate. Same range as sign-magnitude; two zeros.
3. 2's complement: 1's complement plus 1 (most widely used). Range \(-2^{n-1}\) to \(+(2^{n-1}-1)\); a unique zero.

2's Complement Arithmetic

For example, the 2's complement of \(01100100\) is \(10011100\) (scanning from the right, keep the trailing \(00\), invert the rest). Subtraction uses \(A - B = A + [B]_{2'c}\). To compute \(7 - 5\) in 4 bits: \(7 = 0111\), \([5]_{2'c} = 1011\), and \(0111 + 1011 = \underline{1}0010\); discarding the carry gives \(0010 = (+2)_{10}\).

Classification of Binary Codes

Binary codes fall into three broad families: weighted codes (BCD/8421, 2421, 5211), non-weighted codes (Gray code, Excess-3), and error-detecting/correcting codes (parity, Hamming).

BCD and Excess-3 Codes

The BCD (8421) code maps each decimal digit to its 4-bit binary value, with weights 8, 4, 2, 1. The Excess-3 code is formed by adding \(0011\) to the BCD value (\(\text{XS-3} = \text{BCD} + 0011\)) and is self-complementing.

Gray Code (Reflected Binary)

Error Detection and Correction Codes

A parity bit is an extra bit added to make the total number of 1s even (even parity) or odd (odd parity). For example, the data \(1011001\) contains four 1s, so the even-parity bit is 0 and the odd-parity bit is 1.

The code distance \(d\) is the minimum number of bit positions in which two valid codewords differ. A code with distance \(d\) detects \(d-1\) errors and corrects \(\lfloor (d-1)/2 \rfloor\) errors. The Hamming(7,4) code has \(d = 3\): it detects 2-bit errors and corrects single-bit errors.

Hamming(7,4) — Worked Example

Encode the 4 data bits \(D = d_3 d_2 d_1 d_0 = 1011\) using even parity. The parity bit \(p_1\) (position 1) covers positions 1,3,5,7; \(p_2\) (position 2) covers 2,3,6,7; and \(p_3\) (position 4) covers 4,5,6,7.

Computing the parity bits:

giving the codeword \(0\,1\,1\,0\,0\,1\,1\). At the receiver, the syndrome \(S = s_3 s_2 s_1\) is recomputed: if \(S = 000\) there is no error; otherwise \(S\) read in binary points directly to the erroneous bit position.

Fundamentals

The three basic operations are:

• AND (\(\cdot\) or \(\wedge\)): output is 1 if and only if all inputs are 1.
• OR (\(+\) or \(\vee\)): output is 1 if at least one input is 1.
• NOT (\(\overline{X}\) or \(X'\)): output is the complement of the input.

Boolean Laws and Theorems

Absorption and Consensus Theorems

Proof of \(A + \bar{A}B = A + B\):

Duality Principle and Canonical Forms

A minterm \(m_i\) is a product term in which every variable appears exactly once (complemented or not); for \(n\) variables there are \(2^n\) minterms. A maxterm \(M_i\) is a sum term in which every variable appears once. They are related by \(m_i = \overline{M_i}\) and \(M_i = \overline{m_i}\).

SOP and POS Forms

The Sum of Products (SOP) form is the sum of the minterms where \(F = 1\): \(F = \sum m(i_1, i_2, \ldots)\). The Product of Sums (POS) form is the product of the maxterms where \(F = 0\): \(F = \prod M(j_1, j_2, \ldots)\).

This gives \(F = \sum m(1,2,4,5,7) = \bar{A}\bar{B}C + \bar{A}B\bar{C} + A\bar{B}\bar{C} + A\bar{B}C + ABC\) in SOP form, and \(F = \prod M(0,3,6) = (A+B+C)(A+\bar{B}+\bar{C})(\bar{A}+\bar{B}+C)\) in POS form.

Basic Logic Gates

The fundamental gates are AND (\(Y = A\cdot B\)), OR (\(Y = A + B\)) and NOT (\(Y = \bar{A}\)). Combining inversion with AND/OR gives NAND (\(Y = \overline{A\cdot B}\)) and NOR (\(Y = \overline{A+B}\)). The exclusive-OR gate produces \(Y = A\oplus B\).

Truth Tables and Universal Gates

The key identities for universal implementation are \(\bar{A} = \overline{A \cdot A} = \overline{A + A}\) (tie the inputs together), \(A \cdot B = \overline{\overline{A \cdot B}}\), and \(A + B = \overline{\bar{A} \cdot \bar{B}}\) (De Morgan).

NAND-only and NOR-only Implementations

Because NAND and NOR are universal, any function can be built from one gate type alone. Using NAND gates: NOT needs 1 gate, AND needs 2, OR needs 3, and XOR needs 4.

The NOR-only construction is the dual: swap AND with OR, using \(A+B = \overline{\overline{A+B}}\) and \(AB = \overline{\bar{A}+\bar{B}}\).

XOR Properties and Applications

XOR is used in parity generation and checking, the sum bit of binary adders, equality detection in comparators, controlled inverters and cryptography (the Vernam cipher). As a controlled inverter, \(Y = A \oplus C\): when \(C = 0\) the output equals \(A\); when \(C = 1\) the output is \(\bar{A}\).

Karnaugh Maps

The 2-variable map is a \(2\times2\) grid of minterms \(m_0\ldots m_3\); the 3-variable map is a \(2\times4\) grid with the column headings ordered \(00,01,11,10\); and the 4-variable map is a \(4\times4\) grid with both rows and columns in Gray-code order.

K-Map Simplification Rules

The size of a group determines how many variables are eliminated: a group of \(2^k\) cells removes \(k\) variables, leaving \(n-k\) literals. Important terminology: an implicant is any product term that makes \(F = 1\); a prime implicant (PI) cannot be combined into a larger group; and an essential PI covers at least one minterm covered by no other PI.

K-Map Example

Simplify \(F(A,B,C,D) = \sum m(0,1,2,5,8,9,10)\). Plotting the 1s and grouping reveals a four-corner group, a vertical pair group and a small group:

The four corners give \(\bar{B}\bar{D}\), the group \(\{m_0,m_1,m_8,m_9\}\) gives \(\bar{B}\bar{C}\), and the group \(\{m_1,m_5\}\) gives \(\bar{A}\bar{C}D\), yielding

Don't-Care Conditions and Hazards

A hazard is a momentary, unwanted output transition caused by unequal gate delays. The three types are static-1 (output should stay 1 but dips to 0), static-0 (output should stay 0 but spikes to 1), and dynamic (multiple transitions during a single intended change).

A static-1 hazard arises when two adjacent 1-cells are covered by different prime implicants; during the input transition neither group asserts, producing a glitch. It is removed by adding a redundant prime implicant that bridges the groups: for \(F = AB + \bar{A}C\), the hazard-free form is \(F_{HF} = AB + \bar{A}C + BC\). Static-0 hazards (in POS form) are removed by adding a redundant maxterm, and dynamic hazards require multi-level optimisation.

Quine–McCluskey Method

The procedure is: (1) list all minterms and don't-cares in binary, grouped by the number of 1s; (2) compare adjacent groups and combine terms differing in one bit (mark the eliminated bit with “−”); (3) repeat until no further combination is possible; (4) the unchecked terms are the prime implicants; (5) build a prime-implicant chart; and (6) select the essential PIs, using Petrick's method if needed for a minimum cover.

Worked Example — Combining Steps

Minimise \(F(A,B,C,D) = \sum m(0,1,2,5,6,7,8,9,10,14)\). After grouping by the number of 1s and combining adjacent terms, the size-four groups (quads) that emerge are:

Prime-Implicant Chart and Final Result

From the PI chart, \(m_9\) appears only in \(P_1\) and \(m_{14}\) only in \(P_3\), so both are essential. Together \(P_1\) and \(P_3\) cover everything except \(\{5,7\}\), which is covered by \(P_5\). The minimised SOP is therefore

Combinational vs Sequential Circuits

Half Adder

A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

\[ S = A \oplus B \qquad C = AB \]

Full Adder

A full adder (FA) adds three bits (\(A + B + C_{in}\)) and can be cascaded to build \(n\)-bit adders.

A	B	\(C_{in}\)	S	\(C_{out}\)
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Equations

\[ S = A \oplus B \oplus C_{in} \qquad C_{out} = AB + (A\oplus B)C_{in} \]

Ripple-Carry and Carry-Look-Ahead Adders

A ripple-carry adder (RCA) cascades \(n\) full adders, with each carry rippling to the next stage.

The carry-look-ahead adder (CLA) computes all carries in parallel using generate and propagate signals: \(G_i = A_i B_i\), \(P_i = A_i \oplus B_i\), with \(C_{i+1} = G_i + P_i C_i\) and \(S_i = P_i \oplus C_i\). The carry equations expand as:

Subtractor Circuits

A half subtractor computes \(A - B\) with difference \(D = A \oplus B\) and borrow \(B_{out} = \bar{A}B\). A full subtractor has \(D = A \oplus B \oplus B_{in}\) and \(B_{out} = \bar{A}B + \bar{A}B_{in} + BB_{in}\). Note that the difference equation matches that of the full adder; only the borrow logic differs.

4-bit Adder/Subtractor Circuit

Multiplexer (MUX)

MUXes are used for data routing, function implementation, and parallel-to-serial conversion. Two \(2^n\):1 MUXes plus one 2:1 MUX form a \(2^{n+1}\):1 MUX.

Implementing Functions Using a MUX

There are two methods. Method 1 uses a \(2^n\):1 MUX for an \(n\)-variable function, with the inputs set to the minterm values (0 or 1). Method 2 (more efficient) uses a \(2^{n-1}\):1 MUX, with \(n-1\) variables as selects and data inputs drawn from \(\{0, 1, X_n, \bar{X_n}\}\).

Demultiplexer and Decoder

A DEMUX routes one input to one of \(2^n\) outputs — the inverse of a MUX. A decoder converts \(n\) input lines to \(2^n\) output lines with exactly one HIGH per input combination; each output is a minterm, \(Y_i = m_i\).

Encoders

Comparators and Parity Generators

A 1-bit magnitude comparator produces \(A = B:\ \overline{A \oplus B}\), \(A \gt B:\ A\bar{B}\), and \(A \lt B:\ \bar{A}B\).

An \(n\)-bit comparator compares from MSB to LSB:

The IC 7485 is a 4-bit cascadable magnitude comparator. A parity generator/checker uses \(P_{even} = D_1 \oplus D_2 \oplus \cdots \oplus D_n\) and \(P_{odd} = \overline{D_1 \oplus D_2 \oplus \cdots \oplus D_n}\); the checker flags an error when the received parity differs from the computed parity.

Code Converters

The binary-to-Gray converter uses \(G_i = B_i \oplus B_{i+1}\). A BCD-to-seven-segment decoder drives the seven segments (a–g) of a display from a BCD input.

For example, segment \(a\) is on for digits \(\{0,2,3,5,6,7,8,9\}\), so \(a = \sum m(0,2,3,5,6,7,8,9)\); after K-map reduction (with don't-cares for 10–15) this becomes \(a = A + C + B\bar{D} + \bar{B}D\). The driver IC 7447 produces active-LOW outputs for common-anode displays, while the 7448 drives common-cathode displays.

Introduction to Sequential Circuits

The two memory-element types are the latch (level-sensitive, transparent when enabled) and the flip-flop (edge-triggered, changing only at a clock edge). The clock is a periodic timing reference with period \(T\), frequency \(f = 1/T\), duty cycle \(D = (T_{high}/T)\times 100\%\), and finite rise/fall times.

SR Latch (NOR and NAND)

The SR latch built from cross-coupled NOR gates is active-HIGH; the cross-coupled feedback is what gives the latch its memory.

Adding an enable line via two AND gates in front produces a gated SR latch, transparent only when EN = 1.

D and JK Flip-Flops

The D flip-flop is a data latch with a clock; it eliminates the forbidden SR state, with \(Q_{next} = D\). The JK flip-flop is the universal flip-flop.

Latch Circuits from NAND Gates

The active-LOW SR latch uses two cross-coupled NAND gates: \(\bar{S}\bar{R} = 11\) holds, \(01\) sets, \(10\) resets, and \(00\) is forbidden. A gated D latch adds two front-end NAND gates that gate the input with the enable: when EN = 1 the output follows \(D\) (transparent), and when EN = 0 it holds.

T Flip-Flop and Flip-Flop Conversion

The T (toggle) flip-flop holds when \(T = 0\) and toggles when \(T = 1\), with \(Q_{next} = T \oplus Q = T\bar{Q} + \bar{T}Q\). Flip-flop conversion uses the source flip-flop's excitation table to find the inputs required for each desired transition.

For example, to build a D flip-flop from a JK: set \(J = D\) and \(K = \bar{D}\).

Timing Parameters of Flip-Flops

Metastability: if \(t_{su}\) or \(t_h\) is violated, the output may oscillate or settle to an undefined value for an unbounded time. A two-flip-flop synchroniser mitigates this: the first flip-flop may go metastable, but the second has nearly a full clock period to settle, giving a mean-time-between-failures of \(\text{MTBF} = e^{t_r/\tau}/(T_w f_{clk} f_{data})\).

Setup and Hold Time

Shift Registers

The four shift-register types, based on how data enters and leaves, are SISO (serial-in serial-out), SIPO (serial-in parallel-out), PISO (parallel-in serial-out) and PIPO (parallel-in parallel-out). Shifting \(n\) bits in serially takes \(n\) clock cycles.

Ring Counter and Johnson Counter

A ring counter circulates a single 1 around the register: with \(n\) flip-flops it has \(n\) unique states (e.g. \(1000 \to 0100 \to 0010 \to 0001 \to 1000\)) and needs no output decoder, though it uses flip-flops inefficiently. A Johnson (twisted-ring) counter feeds back the complemented last output, giving \(2n\) unique states with \(n\) flip-flops (e.g. \(0000 \to 1000 \to 1100 \to 1110 \to 1111 \to 0111 \to 0011 \to 0001 \to 0000\)).

A bare ring counter has illegal states (such as all-zeros); self-correcting variants detect and force a legal state, typically using a NOR over all flip-flop outputs to re-seed the single 1.

Asynchronous (Ripple) Counters

In a ripple counter each flip-flop's output drives the clock of the next stage, so transitions ripple through and accumulate delay.

Synchronous Counters

In a synchronous counter all flip-flops share the same clock; combinational logic determines when each toggles, so outputs change simultaneously without glitches and \(f_{max} = 1/(t_{pd} + t_{comb})\) is independent of \(n\).

The general design steps are: state diagram → state table → excitation table → K-maps for the flip-flop inputs → circuit.

MOD-N Counter Design

Designing a MOD-6 synchronous counter (states 0–5) with JK flip-flops, the present-state/next-state table together with the JK excitation table yields, after K-map simplification:

Up/Down and Presettable Counters

An up/down counter chooses direction with a control \(M\): \(M = 0\) counts up with \(T_i = Q_0 Q_1 \cdots Q_{i-1}\); \(M = 1\) counts down with \(T_i = \bar{Q_0}\bar{Q_1}\cdots\bar{Q_{i-1}}\). Combined, \(T_i = \bar{M}(Q_0 Q_1 \cdots Q_{i-1}) + M(\bar{Q_0}\bar{Q_1}\cdots\bar{Q_{i-1}})\).

Common IC counters include the 7490 (decade/MOD-10), 7493 (4-bit binary), 74161/163 (4-bit synchronous with parallel load) and 74192/193 (4-bit up/down BCD/binary).

FSM Types: Moore and Mealy

Moore machines have simpler, synchronous outputs but generally more states; Mealy machines have fewer states and respond faster, but their outputs are asynchronous and may glitch.

FSM Design Procedure

1. Problem statement → identify inputs and outputs.
2. Draw the state diagram.
3. Form the state table.
4. State assignment: binary encoding.
5. Choose the flip-flop type.
6. Derive the next-state and output equations using K-maps.
7. Draw the logic circuit.

State minimisation combines equivalent states (those producing the same outputs for every input sequence) using row-matching, the implication table, or the partition method.

Sequence Detector Example: “1011” (Overlapping)

The goal is to output \(Z = 1\) whenever the input stream matches 1011, with overlap allowed (e.g. \(11011011\) contains two matches).

In the Moore machine, \(S_0\) means no match, \(S_1\)=“1”, \(S_2\)=“10”, \(S_3\)=“101”, and \(S_4\)=“1011” (where \(Z = 1\)). The Mealy machine reuses the last 1 of a match for overlap and asserts the output the same clock cycle the matching bit arrives, one cycle earlier than the Moore machine.

Mealy State Table and Trace

With the encoding \(T_0=00\), \(T_1=01\), \(T_2=10\), \(T_3=11\) (two D flip-flops), tracing the input \(11011011\) produces \(Z = 1\) at \(t = 5\) and \(t = 8\) — the two overlapping matches. After K-map reduction the implementation equations are

requiring two D flip-flops plus a small amount of combinational logic, with \(Z\) being a single 3-input AND.

Overview of Logic Families

TTL vs CMOS Characteristics

CMOS Logic Implementation

The dual-network rules are: series NMOS ↔ parallel PMOS, and parallel NMOS ↔ series PMOS. An \(n\)-input NAND or NOR uses \(2n\) transistors; the CMOS inverter uses 2 (one PMOS and one NMOS).

CMOS Inverter VTC and Power Dissipation

The five operating regions are: (1) \(V_{in} \lt V_{Tn}\): NMOS off, PMOS linear, \(V_{out} = V_{DD}\); (2) \(V_{Tn} \lt V_{in} \lt V_M\): NMOS saturated, PMOS linear; (3) \(V_{in} = V_M\): both saturated (the transition); (4) \(V_M \lt V_{in} \lt V_{DD}-|V_{Tp}|\): NMOS linear, PMOS saturated; (5) \(V_{in} \gt V_{DD}-|V_{Tp}|\): PMOS off, \(V_{out} = 0\).

TTL Gate Structure and Open Collector

A standard TTL NAND uses a multi-emitter input transistor, a phase splitter, and a totem-pole output stage.

Tristate Logic and Interfacing

A transmission gate (NMOS and PMOS in parallel) passes a full logic 0 and a full \(V_{DD}\) with no threshold drop and is bidirectional. For interfacing, a TTL \(V_{OH}\) of 2.4 V may miss the CMOS \(V_{IH}\) of \(0.7V_{CC}\), so a pull-up resistor is added when driving CMOS from TTL; the reverse direction is usually direct. Fan-out is \(\min(I_{OL}/I_{IL},\,I_{OH}/I_{IH})\).

Memory Classification

Semiconductor memory divides into two broad families: volatile memory (RAM), which loses its contents when power is removed, and non-volatile memory (ROM), which retains data without power. RAM splits into SRAM and DRAM; ROM spans MROM, PROM, EPROM, and EEPROM/Flash.

RAM: SRAM versus DRAM

DRAM variants: SDRAM (synchronous, clocked); DDR SDRAM (double data rate, both clock edges); and the successive generations DDR2, DDR3, DDR4, and DDR5.

ROM Types

Programmable Logic Devices

CPLD (Complex PLD) combines multiple PLD blocks with interconnect on one chip. An FPGA (Field-Programmable Gate Array) is an array of configurable logic blocks (CLBs) with programmable interconnect and I/O blocks, programmed using an HDL such as VHDL or Verilog.

PLA Structure

The following architecture implements \(F_1 = AB + \bar{A}C\) and \(F_2 = AB + BC\), sharing the product term \(AB\) across both outputs.

Digital-to-Analog Converters

Types. The binary-weighted resistor DAC uses resistors \(R, 2R, 4R, \ldots, 2^{n-1}R\), but requires a wide range of precise values. The R-2R ladder DAC needs only two resistor values and is the popular choice. A segmented DAC combines both approaches for high resolution.

Analog-to-Digital Converters

The quantization error is \(\epsilon_q = \pm V_{LSB}/2 = \pm V_{FS}/2^{\,n+1}\).

Sampling and the Nyquist Criterion

Aliasing occurs when \(f_s \lt 2f_m\): high-frequency components fold back as lower frequencies. It is prevented by an anti-aliasing filter (a low-pass filter) placed before the ADC.

Hardware Description Languages

The two main HDLs are VHDL (VHSIC Hardware Description Language — strongly typed and verbose) and Verilog (C-like syntax, more concise, popular in industry).

Levels of abstraction: (1) gate level — direct gate instantiation; (2) dataflow — Boolean equations via assign statements; (3) behavioral — high-level algorithmic description using always/process blocks; (4) structural — hierarchical composition of modules.

Design flow: specification → HDL coding → simulation → synthesis → place & route → implementation.

Verilog: 2-to-1 Multiplexer

The same multiplexer expressed in three modelling styles — all synthesise to identical hardware.

Gate level

module mux2to1(input a, b, sel, output y);
  wire w1, w2, nsel;
  not (nsel, sel);
  and (w1, a, nsel);
  and (w2, b, sel);
  or  (y, w1, w2);
endmodule

Dataflow

module mux2to1(input a, b, sel, output y);
  assign y = sel ? b : a;
endmodule

Behavioral

module mux2to1(input a, b, sel, output reg y);
  always @(*) begin
    if (sel) y = b;
    else     y = a;
  end
endmodule

Verilog: D Flip-Flop and Counter

D flip-flop (positive edge, asynchronous reset)

module dff(input clk, rst, d, output reg q);
  always @(posedge clk or posedge rst) begin
    if (rst) q <= 1'b0;
    else     q <= d;
  end
endmodule

4-bit up-counter

module counter4(input clk, rst, output reg [3:0] count);
  always @(posedge clk or posedge rst) begin
    if (rst) count <= 4'b0000;
    else     count <= count + 1;
  end
endmodule

VHDL: Equivalent Examples

2-to-1 MUX (dataflow)

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
entity mux2to1 is
  port(a, b, sel : in  STD_LOGIC;
       y         : out STD_LOGIC);
end mux2to1;
architecture dataflow of mux2to1 is
begin
  y <= b when sel = '1' else a;
end dataflow;

D flip-flop (process style)

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
entity dff is
  port(clk, rst, d : in  STD_LOGIC;
       q           : out STD_LOGIC);
end dff;
architecture behav of dff is
begin
  process(clk, rst) begin
    if rst='1' then q <= '0';
    elsif rising_edge(clk) then q <= d;
    end if;
  end process;
end behav;

Verilog versus VHDL: VHDL is strongly typed and verbose; Verilog is C-like and concise. Both are IEEE standards. SystemVerilog, a Verilog superset, dominates verification today.

Must-Remember Numerical Formulas

Flip-Flop Conversion Summary

Common Tricky Questions

Boolean Algebra Identities (Quick Reference)

Number System Conversions Summary

Mealy versus Moore: Quick Comparison

GATE-Level Conceptual Pitfalls

Timing Analysis Examples

Practice Problems

1. Convert \((ABC.D)_{16}\) to binary, octal, and decimal.
2. Express \(-45\) in 8-bit sign-magnitude, 1's complement, and 2's complement.
3. Simplify \(F = \sum m(0,1,3,5,7,8,9,11,15) + \sum d(6,14)\).
4. Design a MOD-12 synchronous counter using T flip-flops.
5. Implement \(F = \bar{A}BC + AB\bar{C} + ABC\) using only NAND gates.
6. Design an overlapping "1011" sequence detector using both Moore and Mealy machines.
7. Convert an SR flip-flop to a JK flip-flop.
8. For a 16-bit ripple adder with \(t_{pd}=3\) ns per full adder, find the maximum operating frequency.
9. Design a 4-to-1 MUX using 2-to-1 MUXes.
10. Find the minimum number of flip-flops required for a MOD-50 counter.

Binary Multiplication

Example: \(1101 \times 1011\):

So \(13 \times 11 = 143 = (10001111)_2\).

Booth's Multiplication Algorithm

For each multiplier bit pair \((Q_i, Q_{i-1})\):

Booth's Algorithm — Worked Example

Compute \((+4)\times(-3)\) with the 4-bit Booth algorithm. Multiplicand \(M = +4 = 0100\), so \(-M = 1100\); multiplier \(Q = -3 = 1101\); initialise \(A = 0000\) and \(Q_{-1}=0\).

Final \(AQ = 11110100_2 = -12\), confirming \(+4\times -3 = -12\). Modified (bit-pair) Booth examines three bits at a time, halving the iteration count to \(n/2\).

Binary Division

BCD Adder Circuit

The correction condition is

where \(K\) is the carry from the binary adder and \(Z_3 Z_2 Z_1 Z_0\) is the binary sum.

IEEE 754 Floating-Point Representation

Special values: zero (\(E=0, M=0\), signed \(\pm 0\)); infinity (\(E=\) all 1s, \(M=0\)); NaN (\(E=\) all 1s, \(M\neq 0\)); denormalised (\(E=0, M\neq 0\)). The single-precision range is approximately \(1.4\times 10^{-45}\) to \(3.4\times 10^{38}\).

1's Complement Arithmetic

If a carry is generated at the MSB, add it back to the LSB (end-around carry) and the result is positive; if there is no carry, the result is negative and remains in 1's complement form.

Decoder and Multiplexer Expansion

To build a 3-to-8 decoder from two 2-to-4 decoders, use the MSB \(A_2\) as the select/enable: when \(A_2=0\) the first decoder drives \(Y_0\)–\(Y_3\), and when \(A_2=1\) the second drives \(Y_4\)–\(Y_7\). For a 4-to-16 decoder from two 3-to-8 decoders, use \(A_3\) as the enable selector and feed \(A_2 A_1 A_0\) to both.

Function Implementation Using Decoders

For \(F(A,B,C) = \sum m(1,3,5,7)\), use a 3-to-8 decoder and OR together outputs \(Y_1, Y_3, Y_5, Y_7\). For multiple outputs, a single decoder serves all functions with one OR gate per output.

Hazard-Free Design: Worked Example

Consider \(F = AB + \bar{A}C\). A static-1 hazard appears when \(B=C=1\) and \(A\) transitions: because of gate delays, both \(AB\) and \(\bar{A}C\) may momentarily be 0, producing a brief glitch on \(F\).

Master-Slave JK Flip-Flop

Operation. When the clock is HIGH the master is enabled and follows JK while the slave is disabled; when the clock is LOW the master latches and the slave copies it to the output. The drawback is "1s catching": if the input glitches to 1 during the master phase, the master captures it. The solution is to use true edge-triggered flip-flops.

Edge-Triggered versus Level-Triggered

Clock Skew, Jitter, and Gating

Clock gating disables the clock to unused logic to save dynamic power, with \(P_{saved} \propto \alpha C V^{2} f\cdot(\text{fraction gated})\). Skew is reduced by H-tree distribution, balanced buffers, clock meshes, and PLL-based deskewing.

Asynchronous Sequential Circuits

Key concepts. A stable state has present = next (no change); an unstable state transitions. A primitive flow table has one stable state per row; a merged flow table combines equivalent states. A cycle is a sequence of unstable states leading to a stable state, acceptable only if it terminates uniquely.

Asynchronous Design: State Assignment

Techniques include shared-row state assignment (inserting an intermediate row), one-hot encoding (one flip-flop per state, no races), and multiple-row assignment (several codes per state). The Huffman design procedure is: state diagram → primitive flow table; merge equivalent states; race-free state assignment; derive excitation and output equations; check for static, dynamic, and essential hazards.

ASM (Algorithmic State Machine) Charts

The three basic symbols are the state box (rectangle, listing Moore-type outputs), the decision box (diamond, testing input conditions), and the conditional output box (oval, for Mealy-type outputs that depend on the input). An ASM block is a state box plus all decision and conditional boxes reachable from it before the next state box.

Pipelining Basics

Latency versus throughput: latency is \(k\cdot(t_s + t_{reg})\) and increases, while throughput (operations per second) increases. Hazards — data, control, and structural — are handled by forwarding, stalling, and branch prediction.

Schmitt Trigger

Applications include noise immunity and false-trigger rejection, sine-to-square wave conversion, switch debouncing, and waveform shaping. Example ICs are the 7414 (hex inverter) and 4093 (CMOS).

555 Timer

In the standard astable configuration the duty cycle exceeds 50%; for \(\leq 50\%\), place a diode across \(R_2\).

Sample and Hold Circuit

R-2R Ladder DAC

Advantages over the weighted-resistor DAC: only two resistor values (easier to fabricate), scalable to any number of bits, and better matching in monolithic ICs.

Successive Approximation (SAR) ADC

The MSB-first algorithm: set the MSB to 1 (others 0) and feed the SAR value to the DAC; if \(V_{DAC} \gt V_{in}\) clear that bit, otherwise keep it; move to the next bit and repeat for \(n\) cycles.

Dual-Slope and Sigma-Delta ADC

A dual-slope (integrating) ADC integrates the input for a fixed time \(T_1\), then integrates \(-V_{ref}\) until the integrator returns to zero; the de-integration time \(T_2\) gives \(V_{in} = V_{ref}\cdot T_2/T_1\). It is used in digital multimeters for its accuracy and excellent noise rejection, at the cost of speed.

A sigma-delta (\(\Sigma\Delta\)) ADC uses oversampling (\(f_s \gg\) Nyquist); noise shaping pushes quantisation noise to high frequencies, a digital low-pass filter removes the shaped noise, and the result is high resolution (16–24 bits) at moderate speeds.

Dynamic CMOS Logic

Operation. A single clock \(\phi\) controls two phases: in the precharge phase (\(\phi=0\)) the output is charged to \(V_{DD}\) through a PMOS; in the evaluate phase (\(\phi=1\)) the NMOS pull-down network evaluates the inputs.

Advantages: fewer transistors (\(n+2\) versus \(2n\) for an \(n\)-input gate) and faster operation (smaller capacitance). Problems: charge leakage (the output loses charge over time), charge sharing (output-node charge redistributes onto internal nodes), and the inability to cascade directly (glitches cause errors).

Domino Logic and Pass-Transistor Logic

Properties: only non-inverting functions are directly implementable; it is very fast (used in high-performance CPUs); and all outputs are glitch-free during evaluation.

PTL drawbacks: a threshold-voltage drop through an NMOS (it passes a weak 1), and signal degradation through cascaded switches. The solution is a transmission gate (NMOS and PMOS in parallel) or level restoration. A transmission gate passes a full \(V_{DD}\) and a full ground, is bidirectional, and is used in multiplexers and latches.

Noise Margin Analysis

Levels. \(V_{OH}\) is the minimum output voltage for logic 1 and \(V_{OL}\) the maximum for logic 0; \(V_{IH}\) is the minimum input voltage recognised as 1 and \(V_{IL}\) the maximum recognised as 0; the undefined region is \(V_{IL}\lt V_{in}\lt V_{IH}\). Typical TTL values: \(V_{OH}=2.4\) V and \(V_{IH}=2.0\) V give \(NM_H = 0.4\) V.

Propagation Delay, Rise and Fall Times

Factors affecting delay: load capacitance (\(t_{pd}\propto C_L\)); supply voltage (\(t_{pd}\propto 1/V_{DD}\), roughly); transistor size (wider transistors lower \(t_{pd}\)); and temperature (higher temperature raises \(t_{pd}\)).

Fan-in and Fan-out Effects

Typical limits: in CMOS, practical fan-in is \(\leq 4\) (beyond which multi-level logic is used); in TTL it is limited by transistor \(\beta\) and base currents. Delay scaling with fan-in \(n\) in CMOS: series NMOS gives \(t_{pd}\propto n^{2}\) (roughly, from series resistance plus capacitance), while parallel PMOS gives \(t_{pd}\propto n\).

High fan-out solutions: buffer chains, clock trees, and wire-sizing.

Memory Interfacing: Detailed Example

Design a \(16\text{K}\times 8\) memory using \(4\text{K}\times 8\) chips. The number of chips needed is \(16\text{K}/4\text{K}=4\); each chip needs 12 address lines (\(2^{12}=4\text{K}\)); the total address space needs 14 lines (\(2^{14}=16\text{K}\)); the upper 2 bits \(A_{13}A_{12}\) select the chip through a 2-to-4 decoder; and the lower 12 bits \(A_{11}\ldots A_0\) go to all chips in parallel.

Cache Memory Basics

Mapping techniques: direct mapping sends each main-memory block to exactly one cache line; fully associative allows any block in any line (flexible but slow to search); set associative is the compromise, mapping a block to a set of lines.

Replacement policies include LRU (least recently used), FIFO, and random. Write policies are write-through (update both cache and memory) and write-back (update cache, mark dirty).

Cache Mapping — Visual Comparison

For direct mapping with \(2^{n}\) main-memory blocks, \(2^{c}\) cache lines, and \(2^{b}\) bytes per block, the address splits into a tag of \(n-c-b\) bits, an index of \(c\) bits, and an offset of \(b\) bits.

Content-Addressable Memory (CAM)

Each cell contains comparison logic plus storage. Binary CAM stores 0 or 1; ternary CAM (TCAM) stores 0, 1, or X (don't care). Applications include network routers (IP lookup, MAC tables), cache tag arrays, the translation lookaside buffer (TLB), pattern matching, and database accelerators.

FPGA Architecture Detail

LUT-based implementation: a \(k\)-input LUT can implement any Boolean function of \(k\) variables (typically 4- or 6-input); the truth table is stored in SRAM with the inputs acting as the address. Programming types are SRAM-based (volatile, reprogrammable; Xilinx/Altera), Flash-based (non-volatile), and antifuse (one-time programmable).

Testing and Stuck-At Faults

Test generation relies on controllability (the ability to set a line to a desired value) and observability (the ability to propagate an effect to a primary output); the D-algorithm performs path sensitisation for automatic test-pattern generation (ATPG).

Design for testability (DFT) techniques: scan chains convert flip-flops into a shift register for test access; BIST (built-in self-test) uses an LFSR to generate patterns and a MISR to compress responses; and boundary scan (JTAG, IEEE 1149.1) enables board-level testing.

Linear Feedback Shift Register (LFSR)

An \(n\)-bit LFSR with a primitive polynomial generates a sequence of length \(2^{n}-1\) (every state except all-zeros).

Applications: BIST test vectors, CRC computation, data whitening, and stream ciphers.

Advanced Topics Formula Summary

Advanced Topics: Tricky Q&A

More Practice Problems (Advanced)

1. Multiply \((-5)\times(+3)\) using the 4-bit Booth algorithm; show each iteration.
2. Represent \(-0.15625\) in IEEE 754 single-precision format.
3. Design a 555 astable for 1 kHz with 60% duty cycle; find \(R_1\), \(R_2\), \(C\).
4. Given \(V_{OH}=3.3\) V, \(V_{OL}=0.3\) V, \(V_{IH}=2.0\) V, \(V_{IL}=0.8\) V, find \(NM_H\) and \(NM_L\).
5. A 12-bit SAR ADC with a 10 MHz clock: find the conversion time.
6. A 4-stage pipeline with \(t_s=10\) ns, \(t_{reg}=1\) ns: find throughput and speedup.
7. Design a \(32\text{K}\times 16\) memory using \(8\text{K}\times 8\) chips. How many chips?
8. Cache hit ratio \(h=0.95\), \(T_c=2\) ns, \(T_m=50\) ns: find \(T_{avg}\).
9. 3-bit LFSR (taps 3, 2): list the full sequence starting from 001.
10. Implement \(F=\bar{A}B+AC\) using (a) a 4:1 MUX, (b) a 3-to-8 decoder + OR gate.
11. Show that a transmission gate passes a full \(V_{DD}\) and full ground, unlike a single NMOS switch.
12. Derive the condition for hazard-free SOP via adjacent-1 analysis.
13. CMOS NAND with \(C_L=50\) fF, \(V_{DD}=1.8\) V, \(I_D=100\,\mu\)A: estimate \(t_{pd}\).
14. Find the oversampling ratio of a \(\Sigma\Delta\) ADC for 24 dB gain (first-order).
15. Draw an ASM chart for a traffic-light controller (Green–Yellow–Red).

GATE-Level Master Formula Sheet

What You Have Mastered

Recommended Textbooks

1. Morris Mano & Michael Ciletti — Digital Design, 5th/6th edition, Pearson.
2. R. P. Jain — Modern Digital Electronics, Tata McGraw-Hill.
3. Thomas L. Floyd — Digital Fundamentals, Pearson.
4. Ronald J. Tocci — Digital Systems: Principles and Applications, Pearson.
5. A. Anand Kumar — Fundamentals of Digital Circuits, PHI.
6. A. Anand Kumar — Switching Theory and Logic Design, PHI.
7. Malvino & Leach — Digital Principles and Applications, McGraw-Hill.
8. Stephen Brown & Zvonko Vranesic — Fundamentals of Digital Logic with Verilog Design.
9. Jan Rabaey — Digital Integrated Circuits: A Design Perspective, Pearson.
10. Samir Palnitkar — Verilog HDL: A Guide to Digital Design and Synthesis.