Special Topics in Digital Logic: Encoders, Decoders, Multiplexers, Demultiplexers, ROM, PLA, PAL, and Memory Hierarchy

Key Components and Their Roles

Digital logic circuits are the building blocks of modern computing systems. While earlier units covered basic gates, combinational circuits, and sequential circuits, Unit 8 dives into specialized components that enable efficient data routing, storage, and processing. These components are widely used in:

• Data communication (e.g., multiplexers in Ncell’s network switching).
• Memory systems (e.g., ROM in eSewa’s transaction validation).
• Control units (e.g., decoders in Daraz’s order processing).

Let’s break down each component with real-world ties, design procedures, and visual representations.

1. Encoders: Converting Signals to Binary Codes

Definition

An encoder is a combinational circuit that converts multiple input signals (usually unary or decimal) into a binary code. It reduces the number of input lines while preserving the information.

How It Works

• Takes n input lines (each representing a unique signal) and produces m output lines (binary code), where $2^m\ge n$.
• Example: A 3-to-8 line encoder converts 3 decimal inputs (0, 1, 2) into an 8-bit binary code (e.g., 00000001 for input 1).

Real-World Example: eSewa’s Transaction Priority System

eSewa processes thousands of transactions per second. To prioritize payments (e.g., emergency vs. routine), an encoder assigns binary codes to transaction types:

• 001 → Emergency payment (highest priority).
• 010 → Bill payment (medium priority).
• 100 → Routine transfer (lowest priority). This binary code is then used by a priority encoder to route transactions to the fastest available server.

Design Procedure

1. Truth Table: List all possible input combinations and their corresponding binary outputs.
2. Simplify Boolean Expressions: Use Karnaugh Maps (K-Maps) or Boolean algebra to minimize the circuit.
3. Draw Logic Diagram: Use AND/OR gates to implement the simplified expressions.

Example: 3-to-8 Line Encoder

Assume inputs I0, I1, I2 (only one can be 1 at a time). The output is a 3-bit code Y2Y1Y0.

Truth Table:

Boolean Expressions:

• $Y2=I2$
• $Y1=I1$
• $Y0=I0$

Logic Diagram:

flowchart LR
    A["I2"] --> B["Y2"]
    C["I1"] --> D["Y1"]
    E["I0"] --> F["Y0"]
    B --> G["Output: Y2Y1Y0"]
    D --> G
    F --> G

Advantages

• Reduces wiring complexity.
• Enables efficient data compression.

Disadvantages

• Only one input can be active at a time (no ambiguity allowed).

2. Decoders: Binary Codes to Signals

Definition

A decoder does the opposite of an encoder: it converts binary inputs into a single active output line. It expands n input lines into 2^n output lines.

How It Works

• Takes a binary input (e.g., 2-bit → 4 outputs).
• Only one output line is active (1) for a given input combination.
• Used in memory addressing, display drivers (7-segment displays), and control units.

Real-World Example: Ncell’s Network Routing

Ncell’s base stations use decoders to route calls to specific towers. For example:

• A 2-bit decoder (00, 01, 10, 11) activates one of four antennas based on the call’s origin code.
• If the input is 10, only the third antenna (D2) is enabled to transmit the signal.

Design Procedure

1. Truth Table: List all input combinations and their corresponding active output.
2. Minimize Logic: Use K-Maps or Boolean algebra to simplify.
3. Implement with Gates: Typically uses AND gates followed by an OR gate (or a priority encoder for hierarchical decoding).

Example: 2-to-4 Line Decoder

Inputs: A1A0 → Outputs: D3D2D1D0 (only one D is 1).

Truth Table:

Boolean Expressions:

• $D0=\overline{A1}\cdot \overline{A0}$
• $D1=\overline{A1}\cdot A0$
• $D2=A1\cdot \overline{A0}$
• $D3=A1\cdot A0$

Logic Diagram:

flowchart LR
    A["A1"] --> B["AND1"]
    A --> C["AND2"]
    D["A0"] --> B
    D --> E["AND3"]
    F["NOT A1"] --> G["AND4"]
    G --> H["OR"]
    B --> H
    C --> I["AND5"]
    I --> H
    E --> J["AND6"]
    J --> H
    G --> K["AND7"]
    K --> L["OR"]
    L --> H
    H --> M["Outputs: D3D2D1D0"]

Advantages

• Simple and fast.
• Used in memory chip addressing (e.g., RAM/ROM).

Disadvantages

• Output lines increase exponentially with input bits ($2^n$ outputs for n inputs).

3. Multiplexers (MUX): Data Selectors

Definition

A multiplexer (MUX) is a combinational circuit that selects one of many input lines and routes it to a single output line based on select lines.

How It Works

• n data inputs → m select lines → 1 output.
• Used in data routing, ALU design, and communication systems.

Real-World Example: Google’s Data Center Traffic Routing

Google’s data centers use multiplexers to route queries to the fastest available server. For example:

• A 4:1 MUX selects one of four servers (D0-D3) based on the load balance signal (S1S0).
• If S1S0 = 10, the output comes from D2 (the least busy server).

Design Procedure

1. Truth Table: List all select line combinations and their corresponding data input.
2. Boolean Expression: The output is a sum of products (SOP) of selected inputs.
3. Logic Diagram: Use AND gates for each data input and an OR gate for the final output.

Example: 4:1 Multiplexer

Inputs: D0, D1, D2, D3 | Select Lines: S1, S0 | Output: Y

Truth Table:

Boolean Expression: $$Y=\overline{S1}\cdot \overline{S0}\cdot D0+\overline{S1}\cdot S0\cdot D1+S1\cdot \overline{S0}\cdot D2+S1\cdot S0\cdot D3$$

Logic Diagram:

flowchart LR
    A["D0"] --> B["AND1"]
    C["D1"] --> D["AND2"]
    E["D2"] --> F["AND3"]
    G["D3"] --> H["AND4"]
    I["NOT S1"] --> B
    I --> D
    J["S1"] --> F
    J --> H
    K["NOT S0"] --> B
    K --> F
    L["S0"] --> D
    L --> H
    B --> M["OR"]
    D --> M
    F --> M
    H --> M
    M --> N["Y"]

Advantages

• Reduces wiring complexity.
• Enables time-sharing of a single communication line.

Disadvantages

• Output depends on select lines (no memory).

4. Demultiplexers (DEMUX): Data Distributors

Definition

A demultiplexer (DEMUX) is the reverse of a MUX: it takes one input and routes it to one of many outputs based on select lines.

How It Works

• 1 input → m select lines → n outputs (only one output is active).
• Used in memory writing, LED display drivers, and signal routing.

Real-World Example: Daraz’s Order Fulfillment

Daraz uses demultiplexers to route orders to different warehouses. For example:

• A 1:4 DEMUX takes an order signal and routes it to one of four warehouses (W0-W3) based on the region code (S1S0).
• If S1S0 = 11, the order goes to W3 (Kathmandu warehouse).

Design Procedure

1. Truth Table: Define which output is active for each select line combination.
2. Boolean Expression: Each output is an AND of the input and the select condition.
3. Logic Diagram: Use AND gates for each output line.

Example: 1:4 Demultiplexer

Input: D | Select Lines: S1, S0 | Outputs: W0, W1, W2, W3

Truth Table:

Boolean Expressions:

• $W0=\overline{S1}\cdot \overline{S0}\cdot D$
• $W1=\overline{S1}\cdot S0\cdot D$
• $W2=S1\cdot \overline{S0}\cdot D$
• $W3=S1\cdot S0\cdot D$

Logic Diagram:

flowchart LR
    A["D"] --> B["AND1"]
    A --> C["AND2"]
    A --> D["AND3"]
    A --> E["AND4"]
    F["NOT S1"] --> B
    F --> C
    G["S1"] --> D
    G --> E
    H["NOT S0"] --> B
    H --> D
    I["S0"] --> C
    I --> E
    B --> J["W0"]
    C --> K["W1"]
    D --> L["W2"]
    E --> M["W3"]

Advantages

• Efficient for broadcasting one signal to multiple destinations.
• Used in memory chip writing.

Disadvantages

• Only one output can be active at a time.

5. Read-Only Memory (ROM): Preprogrammed Logic

Definition

ROM is a non-volatile memory where data is pre-programmed during manufacturing and can only be read (not modified). It stores fixed data or logic functions.

How It Works

• Acts as a hardwired combinational circuit.
• Used to implement logic functions, lookup tables (LUTs), and firmware.

Real-World Example: eSewa’s Transaction Validation

eSewa uses ROM to store valid transaction codes (e.g., 001 = valid, 010 = fraud). When a transaction is processed:

1. The transaction code is fed into the ROM’s address lines.
2. The ROM outputs 1 if the code is valid, 0 otherwise.

Types of ROM

Design Procedure

1. Truth Table: Define the logic function to be implemented.
2. Map to ROM: Each input combination is an address, and the output is the stored data.
3. Implement: Use a ROM chip with the pre-loaded data.

Example: ROM for a 2-Input AND Gate

Truth Table:

ROM Implementation:

• Address Lines: A1A0 (inputs).
• Output: Y (stored data).
• ROM Contents:
  • Address 00 → 0
  • Address 01 → 0
  • Address 10 → 0
  • Address 11 → 1

Real Picture of a ROM Chip:

Advantages

• Fast access (no computation needed).
• Reliable (no moving parts).

Disadvantages

• Fixed data (cannot be modified easily).
• Expensive for large storage.

6. Programmable Logic Arrays (PLA) and Programmable Array Logic (PAL)

Definition

• PLA: A programmable AND-OR array where both the AND plane (product terms) and OR plane (sum terms) are programmable.
• PAL: Similar to PLA, but only the AND plane is programmable, while the OR plane is fixed.

How They Work

• PLA: Used for complex logic functions where both product terms and sums can be customized.
• PAL: Used for simpler functions where the OR structure is predefined.

Real-World Example: NEPSE’s Stock Market Logic

NEPSE’s trading system uses PALs to implement priority-based order matching. For example:

• If a buy order arrives, the PAL checks:
  • Is the price ≥ ask price? (AND term).
  • Is the quantity ≥ minimum? (OR term).
• The output triggers the trade execution.

Comparison Table: ROM vs. PLA vs. PAL

Example: PLA for a Full Adder

A full adder can be implemented using a PLA with:

• Inputs: A, B, Cin (3 inputs).
• Product Terms: All possible minterms (8 terms).
• Sum Terms: Sum = A⊕B⊕Cin, Cout = AB + BCin + ACin.

PLA Structure:

flowchart LR
    A["Inputs: A, B, Cin"] --> B["AND Plane (Programmable)"]
    B --> C["OR Plane (Programmable)"]
    C --> D["Outputs: Sum, Cout"]

Advantages of PLA/PAL

• Reduces chip count (combines multiple gates).
• Easily reprogrammable (unlike ROM).

Disadvantages

• Slower than ROM for simple lookups.
• Complex programming required.

7. Memory Hierarchy: From Registers to Disk

Definition

Memory hierarchy organizes storage devices by speed, cost, and capacity, balancing performance and cost. It includes:

1. Registers (fastest, smallest).
2. Cache (small, fast).
3. RAM (moderate speed, moderate size).
4. ROM (non-volatile, fixed data).
5. Secondary Storage (slowest, largest: HDD, SSD, Cloud).

Real-World Example: Google’s Data Center Memory

Google uses a multi-level memory hierarchy:

• Registers/Cache: Store frequently accessed data (e.g., search query results).
• RAM: Temporary storage for active processes.
• SSD/HDD: Long-term storage for user data.
• Cloud Storage: Backup and archival.

Memory Hierarchy Diagram:

flowchart TD
    A["Registers\n(~ns access)"] --> B["Cache\n(~µs access)"]
    B --> C["RAM\n(~ms access)"]
    C --> D["ROM\n(Non-volatile)"]
    D --> E["SSD/HDD\n(~ms-ms access)"]
    E --> F["Cloud Storage\n(slowest, largest)"]

Key Trade-offs

Locality Principles

1. Temporal Locality: Recently accessed data is likely to be accessed again (e.g., loop variables in code).
2. Spatial Locality: Data near recently accessed data is likely to be needed (e.g., loading a row in a database table).

Example: Kathmandu Traffic Light Control

A traffic light system uses memory hierarchy:

• Registers: Store current light state (red/green).
• RAM: Store traffic patterns (peak hours vs. off-peak).
• ROM: Store fixed rules (e.g., "green for 30s, red for 20s").
• EEPROM: Store historical data for analytics.

In the Real World

1. eSewa’s Transaction Validation

   • Uses ROM to store valid transaction codes and PAL for priority-based processing.
   • Example: If a user sends 001 (emergency payment), the ROM outputs 1 (valid), and the PAL routes it to the fastest server.

2. Ncell’s Network Routing

   • Uses multiplexers to combine multiple calls onto a single transmission line.
   • Example: A 4:1 MUX selects the strongest signal among four base stations to avoid interference.

3. Daraz’s Order Fulfillment

   • Uses demultiplexers to route orders to warehouses based on region codes.
   • Example: If S1S0 = 11, the order goes to the Kathmandu warehouse (W3).

4. Google’s Data Centers

   • Uses memory hierarchy to balance speed and cost:
     • Cache: Stores frequent search queries.
     • RAM: Holds active user sessions.
     • SSD/HDD: Stores user data and logs.

5. NEPSE’s Trading System

   • Uses PAL to implement priority-based order matching:
     • If Buy Price ≥ Ask Price AND Quantity ≥ Minimum, execute the trade.

Exam Tip

This unit is highly visual and often tested with:

1. Design Questions: Expect to draw logic diagrams for encoders, decoders, MUX/DEMUX, and ROM/PLA.

   • Example: "Design a 3-to-8 line decoder with its truth table and logic diagram."
   • Key: Always show input-output relationships clearly.

2. Truth Tables and Boolean Expressions:

   • Memorize standard forms (e.g., MUX output is a sum of products).
   • Example: "Write the Boolean expression for a 4:1 MUX."

3. Real-World Applications:

   • Relate components to Nepali systems (eSewa, Ncell, Daraz) or global tech (Google, WhatsApp).
   • Example: "How would you use a demultiplexer in Pathao’s ride allocation system?"

4. Memory Hierarchy:

   • Compare speed, cost, and volatility of different memory types.
   • Example: "Why does a computer use cache instead of directly accessing RAM?"

5. Short Definitions:

   • Be ready for 1-mark definitions:
     • "What is a PLA?" → "A programmable AND-OR array where both planes are configurable."
     • "Difference between ROM and RAM." → "ROM is non-volatile and fixed; RAM is volatile and rewritable."

Final Checklist Before the Exam

• Can you draw the logic diagram for a 3-to-8 decoder?
• Do you know the Boolean expression for a 4:1 MUX?
• Can you explain how eSewa uses ROM for transaction validation?
• Are you familiar with the memory hierarchy trade-offs?
• Can you design a PLA for a simple logic function (e.g., full adder)?