Digital Design/Boolean & State Logic

Boolean Algebra & State Logic

Master Boolean algebra, Karnaugh maps, and finite state machine design for optimal digital circuits.

🧮 Fundamental Concepts

Boolean Algebra Fundamentals

Fundamental

Mathematical foundation for digital logic design and circuit optimization.

Key Topics:

•Boolean variables and constants
•AND, OR, NOT operations
•De Morgan's theorems
•Boolean identities and laws
•Duality principle

Laws & Rules:

Identity Laws:
A + 0 = A    A · 1 = A
A + 1 = 1    A · 0 = 0

Complement Laws:
A + A' = 1   A · A' = 0
(A')' = A

De Morgan's Laws:
(A + B)' = A' · B'
(A · B)' = A' + B'

Implementation:

// Boolean algebra in Verilog
module boolean_example (
  input  logic a, b, c,
  output logic y1, y2, y3
);

// Original expression
assign y1 = a & b | a & c | b & c;

// Simplified using Boolean algebra
assign y2 = a & b | c & (a | b);

// Further optimization
assign y3 = (a & b) | (c & (a | b));

endmodule

Karnaugh Maps (K-Maps)

Intermediate

Graphical method for simplifying Boolean expressions and minimizing logic circuits.

Key Topics:

•K-map construction and layout
•Grouping minterms and maxterms
•Prime implicants identification
•Don't care conditions
•Multiple output optimization

Laws & Rules:

4-Variable K-Map Layout:
     CD
AB  00  01  11  10
00   0   1   3   2
01   4   5   7   6  
11  12  13  15  14
10   8   9  11  10

Rules:
- Group powers of 2 (1,2,4,8,16)
- Adjacent cells differ by 1 bit
- Wrap around edges
- Larger groups = simpler expressions

Implementation:

// K-map optimization example
// Original: F = A'B'C' + A'BC' + AB'C' + ABC'
// K-map shows: F = C'(A'B' + A'B + AB' + AB)
//             F = C'(A' + A)(B' + B)  
//             F = C'

module kmapped_circuit (
  input  logic a, b, c,
  output logic f
);

// Optimized expression from K-map
assign f = ~c;

// Original would be:
// assign f = (~a & ~b & ~c) | (~a & b & ~c) | 
//           (a & ~b & ~c) | (a & b & ~c);

endmodule

State Machine Design

Advanced

Systematic approach to designing finite state machines for sequential control logic.

Key Topics:

•Moore vs Mealy machines
•State diagram construction
•State encoding strategies
•State minimization techniques
•Hazard analysis and elimination

Laws & Rules:

State Machine Design Flow:
1. Problem specification
2. State diagram creation
3. State table construction  
4. State encoding (Binary/Gray/One-hot)
5. Next state logic derivation
6. Output logic derivation
7. Implementation and verification

Moore: Output = f(Present State)
Mealy: Output = f(Present State, Inputs)

Implementation:

// Traffic Light Controller FSM
typedef enum logic [1:0] {
  RED    = 2'b00,
  YELLOW = 2'b01, 
  GREEN  = 2'b10
} state_t;

module traffic_light_fsm (
  input  logic clk, rst_n,
  input  logic timer_expired,
  output logic [2:0] lights, // {red, yellow, green}
  output logic [3:0] timer_load
);

state_t current_state, next_state;

// State register
always_ff @(posedge clk or negedge rst_n) begin
  if (!rst_n)
    current_state <= RED;
  else
    current_state <= next_state;
end

// Next state logic
always_comb begin
  case (current_state)
    RED:    next_state = timer_expired ? GREEN : RED;
    GREEN:  next_state = timer_expired ? YELLOW : GREEN;
    YELLOW: next_state = timer_expired ? RED : YELLOW;
    default: next_state = RED;
  endcase
end

// Output logic (Moore machine)
always_comb begin
  case (current_state)
    RED: begin
      lights = 3'b100;
      timer_load = 4'd5; // 5 second red
    end
    GREEN: begin
      lights = 3'b001;
      timer_load = 4'd8; // 8 second green
    end
    YELLOW: begin
      lights = 3'b010;
      timer_load = 4'd2; // 2 second yellow
    end
    default: begin
      lights = 3'b100;
      timer_load = 4'd5;
    end
  endcase
end

endmodule

🔢 State Encoding Strategies

Binary Encoding

Uses minimum number of bits for state representation

Example:

State | Encoding
------|--------
S0    |   00
S1    |   01  
S2    |   10
S3    |   11

Advantages:

+Minimum flip-flops
+Simple decoder logic
+Area efficient

Disadvantages:

-Complex next-state logic
-Multiple bit changes
-Glitch prone

Best for: Area-constrained designs

Gray Code Encoding

Only one bit changes between adjacent states

Example:

State | Encoding
------|--------
S0    |   00
S1    |   01
S2    |   11
S3    |   10

Advantages:

+Reduced glitches
+Lower power
+Safer transitions

Disadvantages:

-Complex state assignment
-Still multiple bits for some

Best for: High-speed counters

One-Hot Encoding

Each state uses a unique bit position

Example:

State | Encoding
------|--------
S0    |  0001
S1    |  0010
S2    |  0100
S3    |  1000

Advantages:

+Simple decode logic
+Fast transitions
+Easy debug

Disadvantages:

-More flip-flops
-Higher area
-Power consumption

Best for: High-performance designs

🔄 State Machine Architectures

Moore Machine

Outputs depend only on current state

Block Diagram:

Input → [Next State Logic] → State Register → [Output Logic] → Output
                     ↑                        ↓
                   Clock                    Clock

Characteristics:

•Outputs synchronized to clock
•More predictable timing
•Potential extra delay
•Easier to test and debug

Typical Use: Control units, protocols

Mealy Machine

Outputs depend on current state and inputs

Block Diagram:

Input → [Next State Logic] → State Register
   ↓              ↑                        ↓
[Output Logic] ← Clock                   Clock
   ↓
Output

Characteristics:

•Faster response to inputs
•Potentially fewer states
•Asynchronous output changes
•More complex timing analysis

Typical Use: Data processing, conversion

⚡ Logic Optimization Techniques

Logic Minimization

Reduce gate count using Boolean algebra

Methods:

K-mapsQuine-McCluskeyConsensus theorem

Typical Benefit: 30-60% gate reduction

Technology Mapping

Map logic to available library cells

Methods:

NAND/NOR networksComplex gatesStandard cells

Typical Benefit: Optimal area/timing

Factorization

Factor common sub-expressions

Methods:

Algebraic factoringBoolean factoringSharing

Typical Benefit: 20-40% area reduction

Redundancy Removal

Eliminate redundant logic

Methods:

ConsensusAbsorptionSimplification

Typical Benefit: Logic cleanup

📋 State Machine Design Flow

1. Problem Analysis

Understand requirements and constraints

2. State Identification

Identify all possible system states

3. State Diagram

Create state transition diagram

4. State Table

Construct state transition table

5. State Encoding

Choose encoding strategy

6. Logic Derivation

Derive next-state and output logic

7. Optimization

Minimize logic using K-maps

8. Implementation

Code in HDL and synthesize

9. Verification

Simulate and test thoroughly

Ready to Master Boolean Logic & State Machines?

Practice logic minimization and design complex state machines with optimal encoding strategies.

Practice Boolean Problems Back to Digital Topics