Universal Gates & Advanced Logic Design: NAND/NOR, Multiplexers, Decoders, ALUs

TAKEAWAYS:

• NAND and NOR gates are universal, meaning any logic function can be built using only these two gates.
• Multiplexers and demultiplexers route data based on select lines, forming the backbone of data highways in CPUs and memory systems.
• Decoders convert binary inputs into unique outputs, enabling address selection in RAM and ROM chips.
• Arithmetic Logic Units (ALUs) perform arithmetic and logic operations, critical for processors like those in smartphones and IoT devices.
• State machines (sequential logic) with Mealy/Moore models are used in traffic lights, washing machines, and game controllers.
• Programmable Logic Controllers (PLDs) like PALs and FPGAs are used in industrial automation and embedded systems.

1. Universal Gates: NAND and NOR

Digital logic is not limited to AND, OR, and NOT gates. NAND and NOR gates are universal, meaning any logic function can be constructed using only these two gates. This property simplifies circuit design and reduces component count.

1.1 NAND Gate

A NAND gate is an AND gate followed by a NOT gate. Its truth table is as follows:

Logic Expression: $$A\text{ NAND }B=\overline{A\cdot B}$$

Symbol:

       A
       |
       △
      / \
     B   |
       ▽
       |
       OUT

1.2 NOR Gate

A NOR gate is an OR gate followed by a NOT gate. Its truth table is:

Logic Expression: $$A\text{ NOR }B=\overline{A+B}$$

Symbol:

       A
       |
       △
      / \
     B   |
       ▽
       |
       OUT

1.3 Why Are NAND and NOR Universal?

• NAND Gate Example: To build an AND gate using NAND gates, invert the output of a NAND gate and feed it back into another NAND gate.

  A ----┐
         △
         |
  B ----┘
         ▽
         |
         OUT ---┐
                △
                |
                OUT'
  

  The output OUT' is equivalent to $A\cdot B$.

• NOR Gate Example: Similarly, a NOR gate can be used to build an OR gate by inverting its output.

1.4 Applications of Universal Gates

• NAND Gates: Used in memory chips (e.g., SRAM) and CPUs for building flip-flops and registers.
• NOR Gates: Used in priority encoders and in designing multiplexers.

2. Advanced Combinational Logic Circuits

Combinational logic circuits are static (no memory) and depend only on current inputs. Advanced circuits include multiplexers, demultiplexers, decoders, and encoders.

2.1 Multiplexers (MUX)

A multiplexer (MUX) selects one of many input signals and forwards it to a single output line based on select lines.

2-to-1 MUX Truth Table:

Logic Expression: $$Y=S\cdot I1+\overline{S}\cdot I0$$

Symbol:

       I0
       |
       △
      / \
     S   |
       ▽
       |
       I1
       |
       Y

Example: 2-to-1 MUX Design Design a 2-to-1 MUX where the output $Y$ is selected from $I0$ or $I1$ based on select line $S$.

Solution: Using the truth table, derive the logic expression: $$Y=S\cdot I1+\overline{S}\cdot I0$$

Circuit Diagram:

flowchart LR
    I0["I0"] --> A["AND\n(S=0)"]
    I1["I1"] --> B["AND\n(S=1)"]
    S["S"] -->|"0"| A
    S -->|"1"| B
    A --> C["OR"]
    B --> C
    C --> Y["Y"]

2.2 Demultiplexers (DEMUX)

A demultiplexer (DEMUX) takes a single input and routes it to one of many output lines based on select lines.

1-to-2 DEMUX Truth Table:

Logic Expression: $$Y0=\overline{S}\cdot I$$ $$Y1=S\cdot I$$

Symbol:

       I
       |
       △
      / \
     S   |
       ▽
      / \
 Y0    Y1

2.3 Decoders

A decoder converts binary inputs into unique outputs. For example, a 2-to-4 decoder converts 2-bit inputs into 4 unique outputs.

2-to-4 Decoder Truth Table:

Logic Expression for $Y0$: $$Y0=\overline{A}\cdot \overline{B}$$

Symbol:

       A
       |
       △
      / \
     B   |
       ▽
      /|\
     Y0 Y1
     |  |
     Y2 Y3

Example: 3-to-8 Decoder Design a 3-to-8 decoder using two 2-to-4 decoders.

Solution: Connect the output of the first 2-to-4 decoder to the enable line of the second 2-to-4 decoder. The inputs $A$ and $B$ of the first decoder select one of the four outputs, which then enable the corresponding input of the second decoder.

Circuit Diagram:

flowchart LR
    A["A"] --> D1["2-to-4\nDecoder 1"]
    B["B"] --> D1
    D1 -->|"Y0"| D2["2-to-4\nDecoder 2"]
    D1 -->|"Y1"| D2
    D1 -->|"Y2"| D2
    D1 -->|"Y3"| D2
    C["C"] --> D2
    D2 --> Y0["Y0"]
    D2 --> Y1["Y1"]
    D2 --> Y2["Y2"]
    D2 --> Y3["Y3"]
    D2 --> Y4["Y4"]
    D2 --> Y5["Y5"]
    D2 --> Y6["Y6"]
    D2 --> Y7["Y7"]

2.4 Encoders

An encoder converts multiple inputs into a binary code. For example, a 4-to-2 encoder converts 4 inputs into 2-bit binary outputs.

4-to-2 Encoder Truth Table:

Logic Expression for $Y0$: $$Y0=I1+I3$$

Symbol:

       I0
       I1
       I2
       I3
       |
       △
      / \
     Y1  Y0

3. Arithmetic Logic Units (ALUs)

An ALU performs arithmetic and logic operations. It typically includes adders, subtractors, and logic gates.

3.1 Half-Adder and Full-Adder

• Half-Adder: Adds two single-bit numbers and produces a sum and carry. Truth Table:

  A	B	Sum	Carry
  0	0	0	0
  0	1	1	0
  1	0	1	0
  1	1	0	1

• Full-Adder: Adds three inputs (two bits and a carry) and produces a sum and carry. Truth Table:

  A	B	Cin	Sum	Cout
  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

Example: 4-bit Adder Design a 4-bit adder using four full-adders.

Solution: Connect the sum outputs of each full-adder to form the 4-bit sum. The carry-out of each full-adder is connected to the carry-in of the next full-adder.

Circuit Diagram:

flowchart LR
    A0["A0"] --> FA1["Full-Adder 1"]
    B0["B0"] --> FA1
    FA1 -->|"Sum"| S0["S0"]
    FA1 -->|"Cout"| FA2["Full-Adder 2"]
    A1["A1"] --> FA2
    B1["B1"] --> FA2
    FA2 -->|"Sum"| S1["S1"]
    FA2 -->|"Cout"| FA3["Full-Adder 3"]
    A2["A2"] --> FA3
    B2["B2"] --> FA3
    FA3 -->|"Sum"| S2["S2"]
    FA3 -->|"Cout"| FA4["Full-Adder 4"]
    A3["A3"] --> FA4
    B3["B3"] --> FA4
    FA4 -->|"Sum"| S3["S3"]
    FA4 -->|"Cout"| Cout["Cout"]

3.2 Subtractor

A subtractor performs subtraction using a full-adder by inverting one of the inputs and adding 1.

Example: 4-bit Subtractor Design a 4-bit subtractor using four full-adders.

Solution: Invert the minuend bits and add 1 to the least significant bit (LSB) of the subtrahend.

Circuit Diagram:

flowchart LR
    A0["A0"] --> NOT["NOT"]
    NOT --> FA1["Full-Adder 1"]
    B0["B0"] --> FA1
    FA1 -->|"Sum"| S0["S0"]
    FA1 -->|"Cout"| FA2["Full-Adder 2"]
    A1["A1"] --> NOT2["NOT"]
    NOT2 --> FA2
    B1["B1"] --> FA2
    FA2 -->|"Sum"| S1["S1"]
    FA2 -->|"Cout"| FA3["Full-Adder 3"]
    A2["A2"] --> NOT3["NOT"]
    NOT3 --> FA3
    B2["B2"] --> FA3
    FA3 -->|"Sum"| S2["S2"]
    FA3 -->|"Cout"| FA4["Full-Adder 4"]
    A3["A3"] --> NOT4["NOT"]
    NOT4 --> FA4
    B3["B3"] --> FA4
    FA4 -->|"Sum"| S3["S3"]
    FA4 -->|"Cout"| Cout["Cout"]

4. State Machines and Sequential Logic

Sequential logic circuits have memory and depend on past inputs. They include flip-flops, counters, and state machines.

4.1 State Machines

A state machine is a model of computation where the system transitions between states based on inputs and outputs.

Mealy Machine: Output depends on both state and input. Moore Machine: Output depends only on the state.

Example: Traffic Light Controller (Moore Machine) Design a state machine for a traffic light with states: Red, Green, Yellow.

State Diagram:

stateDiagram-v2
    [*] --> Red
    Red --> Green: Timer Expires
    Green --> Yellow: Timer Expires
    Yellow --> Red: Timer Expires

State Transition Table:

4.2 Counters

Counters are sequential circuits that count pulses. They can be synchronous or asynchronous (ripple).

Comparison Table:

Example: 2-bit Synchronous Up Counter Design a 2-bit synchronous up counter using JK flip-flops.

State Transition Table:

Logic Expression for JK Flip-flops: For Q0: $$J0=1$$ $$K0=1$$

For Q1: $$J1=Q0$$ $$K1=Q0$$

Circuit Diagram:

flowchart LR
    CLK["CLK"] --> FF0["JK FF\n(Q0)"]
    FF0 -->|"Q0"| FF1["JK FF\n(Q1)"]
    FF1 -->|"Q1"| FF1
    FF0 -->|"J0=1<br/>K0=1"| FF0
    FF1 -->|"J1=Q0<br/>K1=Q0"| FF1

In the Real World

1. NAND/NOR Gates in Smartphones:

   • Product: Qualcomm Snapdragon processors (used in smartphones like those from Ncell and NTC).
   • Idea: NAND gates are used to build flip-flops and registers, which are fundamental components in the CPU for storing intermediate results during computations.

2. Multiplexers in Daraz:

   • Product: Daraz’s order processing system.
   • Idea: Multiplexers route different customer orders to the appropriate warehouse or delivery center based on geographic location. For example, if a customer in Kathmandu orders an item, the MUX selects the nearest warehouse’s output line for processing.

3. Decoders in NEPSE:

   • Product: Nepal Stock Exchange (NEPSE) trading system.
   • Idea: Decoders are used to convert binary addresses into unique signals for accessing specific stocks or market data in memory. For example, a 10-bit decoder can select one of 1024 unique stocks for real-time price updates.

4. ALUs in eSewa:

   • Product: eSewa’s transaction processing.
   • Idea: ALUs perform arithmetic operations like adding transaction fees or calculating balances. For instance, when you transfer Rs. 1000 from your eSewa wallet, the ALU subtracts Rs. 1000 from your balance and adds it to the recipient’s balance, handling all calculations in binary.

5. State Machines in Pathao:

   • Product: Pathao’s ride-hailing app.
   • Idea: State machines manage the driver’s status (e.g., online, offline, busy). For example, when a driver accepts a ride request, the state machine transitions from "online" to "busy," and when the ride is completed, it transitions back to "online."

Exam Tip

• Universal Gates: Focus on how to convert basic gates (AND, OR, NOT) into NAND/NOR and vice versa. Practice designing simple circuits using only NAND or NOR gates.
• Multiplexers/Decoders: Understand their truth tables and logic expressions. Be ready to design circuits like 2-to-4 decoders or 4-to-1 multiplexers.
• ALUs: Know the difference between half-adders and full-adders. Practice designing adders and subtractors, and understand how they are used in real-world applications like financial transactions.
• State Machines: Draw state diagrams and transition tables for simple examples like traffic lights or vending machines. Highlight the difference between Mealy and Moore machines.
• Counters: Compare synchronous and ripple counters. For exam questions, always include the state diagram, state transition table, and logic expressions for flip-flops.
• Real-World Applications: Tie your answers to real-world examples like those in the "In the Real World" section. For instance, if asked about a decoder, relate it to NEPSE’s stock selection or Daraz’s order routing.