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⋅BA \cdot B, A+BA + B)
    • Truth table (lists all input–output combinations)
    • Logic symbol (graphical)

• Key truth-table summaries

  • NOT: A‾\overline{A}
  • AND: output 11 only when A=B=1A = B = 1
  • OR: output 11 when any input is 11
  • XOR: output 11 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 VCCV_{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+ACX = AB + AC implemented with two ANDs + OR
  • Equivalent forms proven via Boolean algebra, e.g., A(B+C)=AB+ACA(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,BA, B
    • Sum: A⊕BA \oplus B
    • Carry: ABAB
  • Full-adder (FA)
    • Inputs: A,B,  carryinA, B,\; carry_{in}
    • Sum: A⊕B⊕carryinA \oplus B \oplus carry_{in}
    • Carry-out: AB+(A⊕B)carryinAB + (A \oplus B) carry_{in}
  • 8-bit ripple-carry adder ≈ 1717 inputs, 99 outputs, ~4040 gates

Multiplexers (MUX)

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

Sequential Memory: S-R Latch

  • Stores one bit (outputs X,YX, Y with X=Y‾X = \overline{Y})
  • Inputs S‾,R‾\overline{S}, \overline{R} active-low
    • S‾\overline{S} low ⇒ set X=1X = 1, Y=0Y = 0
    • R‾\overline{R} low ⇒ reset X=0X = 0, Y=1Y = 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