ZA

CS-150 Gates and Circuits

Basic Concepts

  • Gate: device performing a basic logical operation on electrical signals
  • Circuit: interconnection of gates to realize complex functions
  • Two circuit categories
    • Combinational: output depends only on current inputs
    • Sequential: output depends on inputs + internal state

Gate Types & Representations

  • Six common electronic gates: NOT, AND, OR, XOR, NAND, NOR
  • Three equivalent descriptions
    • Boolean expression (e.g., A \cdot B, A + B)
    • Truth table (lists all input–output combinations)
    • Logic symbol (graphical)

• Key truth-table summaries

  • NOT: \overline{A}
  • AND: output 1 only when A = B = 1
  • OR: output 1 when any input is 1
  • XOR: output 1 when inputs differ
  • NAND / NOR: inverted AND / OR

Transistors & Gate Construction

  • Transistor (NPN) behaves as voltage-controlled switch
    • Terminals: collector, base, emitter
    • Base low ⇒ no conduction; base high ⇒ conduction
  • Gate implementations
    • NOT: single transistor; base high pulls output low, base low lets V_{CC} pull high
    • AND: two transistors in series; both bases high needed for high output

Circuit Types & Descriptions

  • Boolean expression, truth table, and logic diagram apply to any circuit
  • Example: X = AB + AC implemented with two ANDs + OR
  • Equivalent forms proven via Boolean algebra, e.g., A(B + C) = AB + AC

Boolean Algebra Essentials

  • Distributive, associative, commutative, De Morgan’s
  • Used to minimize gate count and prove circuit equivalence

Adders

  • Half-adder (HA)
    • Inputs: A, B
    • Sum: A \oplus B
    • Carry: AB
  • Full-adder (FA)
    • Inputs: A, B,\; carry_{in}
    • Sum: A \oplus B \oplus carry_{in}
    • Carry-out: AB + (A \oplus B) carry_{in}
  • 8-bit ripple-carry adder ≈ 17 inputs, 9 outputs, ~40 gates

Multiplexers (MUX)

  • Selects one of many data inputs to a single output using control lines
  • For 8 inputs ⇒ 3 select lines (because 2^3 = 8)

Sequential Memory: S-R Latch

  • Stores one bit (outputs X, Y with X = \overline{Y})
  • Inputs \overline{S}, \overline{R} active-low
    • \overline{S} low ⇒ set X = 1, Y = 0
    • \overline{R} low ⇒ reset X = 0, Y = 1
  • Illegal to drive both low simultaneously

Integrated Circuits

  • Chip: silicon die containing many gates; packaged with pins
  • CPU: complex IC central to system; communicates through its pin array