TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

Digital Foundations: From Bits to Boolean Logic

Module 01 — Foundations | Digital IC Design Series
01 Foundations

Digital Foundations: From Bits to Boolean Logic

Every chip you will ever design — from a tiny microcontroller to a billion-transistor SoC — rests on ten foundational ideas covered in this module. Master these and everything that follows clicks into place.

Your progress

0 / 10 topics
Number systems
Boolean algebra
Combinational logic
Sequential logic
Logic families
K-maps
Binary arithmetic
Data representation
Logic gates
Digital waveforms

01 / 10 Number Systems & Codes

Digital circuits work exclusively with two voltage levels: high and low — represented as 1 and 0. Understanding how numbers and text map to these bits is the first step into hardware design.

Binary (Base 2)

Uses digits 0 and 1. Each position is a power of 2. Example: 1011₂ = 11₁₀ (8+0+2+1).

Hexadecimal (Base 16)

Compact representation: 4 bits → 1 hex digit. 0xAB = 1010 1011₂ = 171₁₀. Used everywhere in HDL.

Octal (Base 8)

3 bits → 1 octal digit. Less common today but found in older assembly and file permissions. 017₈ = 1111₂.

BCD (Binary Coded Decimal)

Each decimal digit stored in 4 bits: 42 → 0100 0010. Used in displays and financial ICs.

Gray Code

Consecutive values differ by exactly one bit. Critical in ADCs and shaft encoders to eliminate glitches during transitions.

ASCII / Unicode

Character encoding. 'A' = 0x41 = 65₁₀ = 0100 0001₂. Matters when designing UART/SPI communication logic.

Key insight: Gray code is the reason rotary encoders work reliably. When a shaft rotates, the mechanical contact never causes two bits to change simultaneously — eliminating false position readings.
DecimalBinaryHexBCDGray
0000000000 00000000
1000110000 00010001
2001020000 00100011
7011170000 01110100
101010A0001 00001111
151111F0001 01011000

Interview questions

Convert 0xC5 to binary and decimal.

Binary: C = 1100, 5 = 0101 → 1100 0101₂

Decimal: 12×16 + 5 = 192 + 5 = 197₁₀

Why is Gray code preferred over binary in encoders?

In a standard binary counter, transitioning from 3 (011) to 4 (100) requires three bits to change simultaneously. In physical hardware, bits never change at exactly the same instant — there is always skew. This produces intermediate invalid values (e.g., 000, 010, 110) during the transition, which cause wrong position reads.

Gray code ensures only one bit changes between any two adjacent values, so there is no ambiguous intermediate state, even with imperfect timing.

What is the difference between BCD and binary representation of 99?

Binary: 99 = 0110 0011 (8 bits, compact)

BCD: 9 → 1001, 9 → 1001 = 1001 1001 (8 bits here, but needs more bits for larger numbers)

BCD wastes space (unused patterns 1010–1111 per nibble) but makes decimal display logic trivial — each nibble drives a 7-segment decoder directly. That's why cash registers and digital clocks often use BCD internally.

Practice problems

Easy Convert 0b10110111 to hex and decimal.
Binary: 1011 0111 → Hex: 0xB7 → Decimal: 11×16 + 7 = 183
Medium Write the 4-bit Gray code sequence for 0–7 and explain the construction rule.
0→0000, 1→0001, 2→0011, 3→0010, 4→0110, 5→0111, 6→0101, 7→0100.
Rule: MSB of Gray = MSB of binary. For each subsequent bit: G[i] = B[i] XOR B[i-1]. This guarantees only 1-bit Hamming distance between adjacent codes.
Hard Design a 3-bit binary-to-Gray code converter in Verilog. Verify for all 8 inputs.
verilog
module bin_to_gray (
  input  [2:0] bin,
  output [2:0] gray
);
  assign gray = bin ^ (bin >> 1);
endmodule
The expression bin ^ (bin >> 1) implements the XOR rule in one line. Verify: bin=3'b110 (6) → gray = 110 ^ 011 = 101 (correct: Gray for 6 is 0101).

02 / 10 Boolean Algebra & Logic

Boolean algebra is the mathematical language of digital circuits. Every logic gate, multiplexer, and FSM is ultimately an expression in Boolean algebra — and reducing these expressions directly reduces transistor count and power.

AND

Output 1 only when all inputs are 1. Symbol: A·B or AB.

OR

Output 1 when any input is 1. Symbol: A+B.

NOT

Inverts the input. Symbol: Ā or ~A.

NAND

NOT-AND. Universal gate — any Boolean function can be built with NAND alone. CMOS-efficient.

NOR

NOT-OR. Also universal. NOR-based synthesis common in older technologies.

XOR

Output 1 when inputs differ. A⊕B. Core of adders, parity checkers, and Gray code converters.

Key theorems to internalize:

  • Identity: A·1 = A, A+0 = A
  • Null: A·0 = 0, A+1 = 1
  • Idempotent: A·A = A, A+A = A
  • Complement: A·Ā = 0, A+Ā = 1
  • De Morgan's: (AB)' = A'+B' and (A+B)' = A'·B'
  • Absorption: A+AB = A, A(A+B) = A
De Morgan's theorem is used daily in synthesis. To push an inversion through a gate, flip AND↔OR and complement all signals. This lets you convert between NAND and NOR implementations to match your cell library.
verilog — Boolean identities in practice
// De Morgan's: ~(A & B) == ~A | ~B
assign nand_out = ~(a & b);
assign demorgan = (~a) | (~b);   // identical result

// XOR using basic gates: A^B = (A|B) & ~(A&B)
assign xor_out  = (a | b) & ~(a & b);

// Simplify: F = A'B + AB' + AB → F = A + B  (Absorption + OR)
assign f        = a | b;

Interview questions

Prove De Morgan's theorem for (A+B)' using a truth table.
ABA+B(A+B)'A'B'A'·B'
0001111
0110100
1010010
1110000

Columns (A+B)' and A'·B' are identical → theorem proven.

Why is NAND called a "universal gate"?

A gate is universal if it can implement any Boolean function by itself. NAND can realize NOT (A NAND A = A'), AND (NAND then NOT), and OR (NOT both inputs then NAND). Since NOT, AND, OR form a functionally complete set, NAND alone is sufficient for any circuit. It is also the most area-efficient gate in CMOS because it requires fewer transistors than an equivalent AND gate (which needs a NAND + inverter anyway).

Practice problems

Easy Simplify: F = AB + A'B + AB'
F = AB + A'B + AB'
= B(A+A') + AB' (factor B)
= B·1 + AB' (complement law)
= B + AB' (identity)
= B + A (absorption: B+AB' = B+A)
Medium Implement XOR using only 4 NAND gates.
Let G1 = NAND(A,B), G2 = NAND(A,G1), G3 = NAND(B,G1), G4 = NAND(G2,G3).
Then G4 = A⊕B. Verify: A=1,B=0 → G1=1, G2=0, G3=1, G4=NAND(0,1)=1 ✓
Hard Write a Verilog module that verifies all 16 possible Boolean functions of 2 inputs using a 4-bit select.
verilog
module bool16 (
  input        a, b,
  input  [3:0] sel,
  output reg   f
);
  always @(*) begin
    case (sel)
      4'd0:  f = 0;         // FALSE
      4'd1:  f = a & b;     // AND
      4'd2:  f = a & ~b;    // A and not-B
      4'd3:  f = a;         // A
      4'd4:  f = ~a & b;    // not-A and B
      4'd5:  f = b;         // B
      4'd6:  f = a ^ b;     // XOR
      4'd7:  f = a | b;     // OR
      4'd8:  f = ~(a | b);  // NOR
      4'd9:  f = ~(a ^ b);  // XNOR
      4'd10: f = ~b;        // NOT-B
      4'd11: f = a | ~b;    // A implies B
      4'd12: f = ~a;        // NOT-A
      4'd13: f = ~a | b;    // B implies A
      4'd14: f = ~(a & b);  // NAND
      4'd15: f = 1;         // TRUE
    endcase
  end
endmodule

03 / 10 Combinational Logic Basics

A combinational circuit's output depends only on its current inputs — there is no memory, no clock, no state. The output changes whenever inputs change, after a propagation delay.

Formal definition: A circuit is combinational if and only if it has no feedback paths and no state elements (latches/flip-flops). Every path from input to output is purely combinational.

All combinational circuits can be described as a sum of minterms (SOP) or product of maxterms (POS):

  • SOP (Sum of Products): OR of AND terms. F = A'B + AB'C. Maps to AND-OR logic.
  • POS (Product of Sums): AND of OR terms. F = (A+B)(A'+C). Maps to OR-AND logic.
  • Choose whichever has fewer terms to minimize gate count.
verilog — SOP vs POS
// F = Σm(1,2,5,6) for 3-input function
// SOP: F = A'B'C + A'BC' + AB'C' ... (from minterms)
// Simplified SOP (after K-map): F = B⊕C — just one XOR gate!
module comb_example (
  input  a, b, c,
  output f
);
  assign f = b ^ c;   // simplified combinational expression
endmodule

// IMPORTANT: in always blocks, list ALL inputs in sensitivity list
always @(a or b or c)    // or use: always @(*)
begin
  case ({a,b,c})
    3'b000: f = 0;
    3'b001: f = 1;
    // ...
  endcase
end
Common mistake: In an always @(*) block for combinational logic, every output variable must be assigned in every branch. Missing assignments create unintended latches — a sequential element that silently corrupts your combinational intent.

Interview questions

What is the difference between a minterm and a maxterm?

A minterm is a product (AND) of all variables where the function output is 1. If F=1 at input {A=1,B=0,C=1}, the minterm is AB'C.

A maxterm is a sum (OR) of all variables where the function output is 0. If F=0 at {A=0,B=0,C=0}, the maxterm is (A+B+C).

SOP = OR of minterms; POS = AND of maxterms. Both represent the same function — choose the one with fewer terms.

How does synthesis handle a missing else in an if statement inside always @(*)?

If you write if (sel) out = a; without an else, the synthesis tool asks: "what is 'out' when sel=0?" Since no assignment is given, it must hold the previous value — which requires a latch. The tool infers a level-sensitive latch, creating an unintended sequential element. Always provide an else branch or a default assignment before the if statement to prevent this.

Practice problems

Easy Write an SOP expression for a 2-input XNOR gate. Simplify it.
XNOR truth table: F=1 when A=B. Minterms: m0(A'B') and m3(AB). SOP: F = A'B' + AB. This is already minimal — it cannot be simplified further because A and B are not adjacent in the K-map.
Hard Write a Verilog always block for a 4:1 MUX that avoids latch inference. Verify with sel=2'b10.
verilog
module mux4 (
  input      [3:0] d,
  input      [1:0] sel,
  output reg       y
);
  always @(*) begin
    y = 1'b0;      // default — prevents latch inference
    case (sel)
      2'b00: y = d[0];
      2'b01: y = d[1];
      2'b10: y = d[2];
      2'b11: y = d[3];
    endcase
  end
endmodule
For sel=2'b10, y = d[2]. The default assignment y=0 ensures no latch inference even if case were incomplete.

04 / 10 Sequential Logic Basics

Unlike combinational circuits, sequential circuits have memory. The output depends on current inputs and previous state. Two flavors:

  • Synchronous sequential: State changes only on a clock edge. Predictable, synthesizable, preferred in digital design.
  • Asynchronous sequential: State changes immediately on input change. Harder to design, faster, used in specific areas (async FIFOs, handshake circuits).
verilog — synchronous D flip-flop
module dff (
  input      clk, rst_n, d,
  output reg q
);
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) q <= 1'b0;   // async reset
    else        q <= d;
  end
endmodule
Rule of thumb: Use non-blocking assignments (<=) in clocked always blocks. Use blocking assignments (=) in combinational always blocks. Mixing them is one of the most common sources of simulation/synthesis mismatches.

Interview questions

What is the difference between synchronous and asynchronous reset?

Synchronous reset: Reset is sampled at the clock edge. if (rst) q <= 0; inside a clocked always block. Glitch-immune, but requires the clock to be running. Standard in most ASIC flows.

Asynchronous reset: Reset takes effect immediately, independent of clock. Coded as posedge clk or posedge rst in the sensitivity list. Faster response, but removal of reset must be synchronized to the clock to avoid metastability — requiring a "reset synchronizer."

05 / 10 Logic Families (Overview)

A logic family defines the technology used to build gates — affecting speed, power, noise margins, and drive strength.

TTL (74xx series)

Bipolar transistors. Fast, but high static power. 5V supply. Common in legacy boards; now mostly obsolete for new designs.

CMOS

Complementary MOS pairs. Near-zero static power, scales well. Dominant in all modern digital ICs. VDD from 5V down to 0.6V in advanced nodes.

LVTTL / LVCMOS

Low-voltage variants (3.3V, 2.5V, 1.8V). Interface standard for FPGAs and modern SoCs.

ECL (Emitter-Coupled Logic)

Extremely fast (sub-ns), but very high power. Used in fiber optic transceivers and RF applications.

For ASIC designers: The cell library your foundry provides (e.g., TSMC 28nm standard cells) is the "logic family." You choose drive strengths, not gate types.

06 / 10 K-Maps & Simplification

The Karnaugh map (K-map) is a graphical method to minimize Boolean expressions by visually grouping 1s (for SOP) or 0s (for POS) into the largest possible power-of-2 groups.

  • Groups must be rectangular and of size 1, 2, 4, 8, 16...
  • Cells are arranged in Gray code order so adjacent cells differ by 1 bit.
  • Larger groups → fewer literals → simpler logic.
  • Don't cares (X) can be included or excluded — always use them if they reduce the expression.
In practice: For logic beyond 6 variables, tools like Espresso (used inside synthesis engines) replace K-maps. But understanding K-maps trains the intuition for recognizing and simplifying logic by eye — critical during RTL reviews.

Interview questions

Simplify F(A,B,C,D) = Σm(0,1,2,4,5,6,8,9,10) using a 4-variable K-map.

Grouping the minterms on a 4×4 K-map: The 8-cell group covering m(0,1,2,4,5,6,8,9,10) reduces to F = A'+ B'C' + B'D'. Further simplification: F = A' + B'(C'+D') = A' + B'·(CD)'. Always verify by plugging in maxterms (cells not in the group).

07 / 10 Binary Arithmetic (Add, Sub, Mul)

Every ALU starts here. Hardware arithmetic is not the same as pencil-and-paper arithmetic — overflow, carry propagation delay, and two's complement representation are all physical constraints.

Half adder

Adds 2 bits. Sum = A⊕B, Carry = A·B. No carry-in.

Full adder

Adds 3 bits (A, B, Cin). Sum = A⊕B⊕Cin, Cout = majority(A,B,Cin). Chainable for N-bit adders.

Ripple carry adder

Simplest N-bit adder: chain N full adders. Carry "ripples" through — delay grows as O(N). Slow for large N.

Carry look-ahead

Pre-computes carries in parallel using Generate (G=AB) and Propagate (P=A⊕B). O(log N) delay. Standard in ALU designs.

Two's complement subtraction

A − B = A + (~B) + 1. Invert B, add 1, then add to A. One adder handles both addition and subtraction.

Overflow detection

For signed addition: overflow if Cin to MSB ≠ Cout from MSB. In Verilog: overflow = Cin_msb ^ Cout.

verilog — parameterized carry look-ahead adder
module cla_adder #(parameter N=8) (
  input  [N-1:0] a, b,
  input          cin,
  output [N-1:0] sum,
  output         cout, overflow
);
  wire [N:0] c;
  assign c[0] = cin;

  genvar i;
  generate
    for (i=0; i<N; i=i+1) begin : fa_loop
      assign sum[i] = a[i] ^ b[i] ^ c[i];
      assign c[i+1] = (a[i] & b[i]) | (c[i] & (a[i] ^ b[i]));
    end
  endgenerate

  assign cout     = c[N];
  assign overflow = c[N] ^ c[N-1];  // signed overflow
endmodule

08 / 10 Data Representation (Signed, Unsigned)

The same bit pattern means different things depending on its representation. This is one of the most common sources of bugs in RTL.

Unsigned

Range: 0 to 2ᴺ−1. All bits are magnitude. reg [7:0] a holds 0–255.

Two's complement (signed)

MSB is sign bit (1=negative). Range: −2ᴺ⁻¹ to 2ᴺ⁻¹−1. 8'hFF = −1. Arithmetic works correctly without special cases.

Sign extension

Widening a signed value: replicate the MSB. 8'b1011_0010 → 16'b1111_1111_1011_0010. Verilog: use $signed() cast.

Fixed-point

Integer hardware representing fractions: Q4.4 = 4 integer bits + 4 fractional bits. Scale by 2⁴=16 implicitly. Common in DSP datapaths.

verilog — signed arithmetic pitfall
module signed_demo;
  reg signed [7:0] a = -5;     // 8'hFB
  reg        [7:0] b = 8'hFB;  // 251 unsigned
  reg signed [15:0] prod_s;
  reg        [15:0] prod_u;

  initial begin
    prod_s = a * $signed(b);    // −5 × −5 = 25 ✓
    prod_u = a * b;             // 251 × 251 = wrong ✗
    $display("signed=%0d, unsigned=%0d", prod_s, prod_u);
  end
endmodule
Always declare intent: In Verilog, reg signed and explicit $signed() casts control whether operations treat values as signed or unsigned. Forgetting this is an extremely common RTL bug — the simulator will not warn you.

09 / 10 Logic Gates & Circuits

Gates are the atomic units of digital hardware. In CMOS, every gate is built from complementary NMOS/PMOS transistor pairs — and gate count directly determines area, power, and timing.

CMOS inverter

1 PMOS (pull-up) + 1 NMOS (pull-down). When input=0, PMOS ON → output=VDD. When input=1, NMOS ON → output=GND. Near-zero static power.

CMOS NAND

2 PMOS in parallel (pull-up) + 2 NMOS in series (pull-down). Output=0 only when both inputs=1. 4 transistors total.

Fan-out

Number of gate inputs driven by one output. Each additional load adds capacitance and slows the output. Synthesis tools insert buffers when fan-out exceeds cell limits.

Propagation delay (tpd)

Time from input change to output reaching 50% of VDD. Composed of: gate delay + wire delay. Limits maximum clock frequency.

Silicon insight: NAND gates are preferred over AND+NOT in CMOS because AND = NAND + inverter (more transistors, more delay). Standard cell libraries favor NAND/NOR-based implementations. Your synthesis tool knows this — but so should you, for critical path hand-optimization.

10 / 10 Digital Waveforms

A digital waveform is the time-domain plot of a signal's voltage level. Reading and interpreting waveforms in a simulator (ModelSim, VCS, Verilator) is a core skill — most debugging happens here.

  • Rise time / fall time: Time for signal to transition between 10%–90% of VDD. Not instantaneous in real silicon.
  • Setup time (tsu): Data must be stable this long before the clock edge.
  • Hold time (th): Data must remain stable this long after the clock edge.
  • Clock-to-Q (tCQ): Delay from clock edge to output of flip-flop becoming valid.
  • Glitch: A narrow unwanted pulse caused by unequal propagation delays through different paths. Visible in waveforms; can trigger unintended state changes.
verilog — reading waveforms: testbench skeleton
module tb_foundations;
  reg  clk = 0, a, b;
  wire out;

  dut u_dut (.clk(clk), .a(a), .b(b), .out(out));

  always #5 clk = ~clk;  // 100 MHz clock (10ns period)

  initial begin
    $dumpfile("wave.vcd");    // generate VCD for GTKWave
    $dumpvars(0, tb_foundations);
    a = 0; b = 0; #12;
    a = 1;          #10;
    b = 1;          #10;
    a = 0;          #10;
    $finish;
  end
endmodule
GTKWave tip: Always dump $dumpvars(0, tb) with depth=0 to capture all hierarchical signals. When a glitch appears in simulation, zoom to the nanosecond range — the cause is almost always a race condition in your combinational logic.

Interview questions

What happens if setup time is violated?

If data changes too close to the clock edge (within the setup time window), the flip-flop samples an indeterminate value — neither a clean 0 nor a 1. This is called metastability. The flip-flop output can oscillate or settle to an unpredictable level, potentially causing incorrect behavior in the downstream logic. Static timing analysis (STA) ensures all paths meet setup (and hold) time margins with sufficient slack.

Complete series

01 Foundations
02 Combinational design
03 Sequential design
04 FSM & control design
05 Data path design
06 Memory & storage
07 Clocking & reset
08 Verilog HDL fundamentals
09 Advanced HDL design
10 Verification fundamentals
11 On-chip bus & interfaces
12 Low power design
13 DFT basics
14 Physical design aware
15 Advanced topics

Post a Comment

0 Comments

Your comments will be moderated before it appears here.

Post a Comment (0)

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!