Chapter 3 Notes: Boolean Algebra and Digital Logic

Historical Introduction to Boolean Logic

• Foundational Theory by George Boole: In the late 19th century, George Boole proposed that logical thought could be represented through mathematical equations. This idea was controversial at the time, as philosophers and mathematicians questioned the notion that human thought could be encapsulated and manipulated like algebraic formulas.

• Modern Computers as Implementations: Contemporary computers are physical implementations of Boole's work, specifically his "Laws of Thought."

• Early Pioneers: John Atanasoff and Claude Shannon were among the first researchers to recognize the direct connection between Boolean logic and electronic switching circuits.

• Historical Perception: In the middle of the 20th century, computers were referred to as "thinking machines" and "electronic brains." While modern society accepts computers as ubiquitous, the early fear of these machines persists in some contexts today.

Fundamentals of Boolean Algebra

• Definition: Boolean algebra is a mathematical system tailored for manipulating variables that can take one of exactly two values.

  • In Formal Logic: The values are "True" and "False."

  • In Digital Systems: The values are represented as "On" and "Off," $1$ and $0$, or "High" and "Low."

• Boolean Expressions: Created by performing logical operations on Boolean variables.

• Primary Boolean Operators:

  • AND: Known as the Boolean product. Its output is $1$ only if all inputs are $1$.

  • OR: Known as the Boolean sum. Its output is $1$ if at least one input is $1$.

  • NOT: Known as the complement. It reverses the input value ($1$ becomes $0$, and $0$ becomes $1$).

• NOT Operator Designations: The NOT operation is represented by a prime mark ($x'$), an overbar ($\bar{x}$), or an "elbow" ($\neg x$).

• Boolean Function Components: A Boolean function consists of at least one Boolean variable, at least one Boolean operator, and at least one input from the set $\{0, 1\}$. The output is always a member of the set $\{0, 1\}$.

Truth Tables and Precedence

• The Truth Table: A complete description of a Boolean operator or function, showing the output for every possible combination of inputs.

• Evaluation of Subparts: When evaluating complex functions, truth tables often include extra (shaded) columns for sub-expressions to simplify the process.

• Rules of Precedence: Similar to standard arithmetic, Boolean operations follow a specific order of operations:

  1. NOT: Highest priority.

  2. AND: Second priority.

  3. OR: Lowest priority.

Boolean Identities and Simplification

• Motivation for Simplification: Digital computers implement Boolean functions via circuits. Simpler functions result in smaller circuits, which are cheaper to build, consume less power, and operate faster.

• Basic Identities:

  • Identity Law: $x + 0 = x$ and $x \times 1 = x$.

  • Null Law: $x + 1 = 1$ and $x \times 0 = 0$.

  • Idempotent Law: $x + x = x$ and $x \times x = x$.

  • Inverse Law: $x + x' = 1$ and $x \times x' = 0$.

• Algebraic Identities (Familiar Laws):

  • Commutative Law: $x + y = y + x$ and $xy = yx$.

  • Associative Law: $(x + y) + z = x + (y + z)$ and $(xy)z = x(yz)$.

  • Distributive Law: $x(y + z) = xy + xz$ and $x + (yz) = (x + y)(x + z)$.

• Useful Complex Laws:

  • Absorption Law: $x + (xy) = x$ and $x(x + y) = x$.

  • Double Complement Law: $(x')' = x$.

  • DeMorgan’s Law:

    • $(x + y)' = x'y'$

    • $(xy)' = x' + y'$

    • General Application: To find the complement of any function, replace each variable with its complement and swap all ANDs with ORs (and vice versa).

Canonical Forms of Boolean Expressions

• Logical Equivalence: Different Boolean expressions are logically equivalent if they produce identical truth tables.

• Canonical (Standardized) Forms: Used by designers to eliminate confusion.

  • Sum-of-Products (SOP): ANDed variables are ORed together. Example: $F(x, y, z) = xy + xz + yz$.

  • Product-of-Sums (POS): ORed variables are ANDed together. Example: $F(x, y, z) = (x + y)(x + z)(y + z)$.

  • Conversion via Truth Table: To find the SOP form, identify the input combinations where the function equals $1$, list those product terms (minterms), and OR them together.

Logic Gates: Physical Implementations

• Definition: A gate is an electronic device that produces a result based on two or more input values. Physically, gates consist of one to six transistors but are treated as single units by designers.

• Basic Gates:

  • AND/OR/NOT Gates: Direct physical implementations of the basic Boolean operators.

  • XOR (Exclusive OR) Gate: Returns true ($1$) only if the values of the inputs differ. Represented by the symbol $\oplus$. For $n$ inputs, the output is $1$ if the number of $1$s is odd.

• Universal Gates:

  • NAND and NOR: These are termed "universal" because they are inexpensive to manufacture, and any Boolean function can be constructed using only NAND or only NOR gates.

• Multi-Input Gate Rules (for n inputs):

  • AND: All $n$ inputs must be $1$ for the output to be $1$.

  • OR: Only one of the $n$ inputs must be $1$ for the output to be $1$.

  • NAND: If any of the inputs are $0$, the output is $1$.

  • NOR: If all $n$ inputs are $0$, the output is $1$.

  • XOR: If the number of inputs equal to $1$ is odd, the output is $1$.

Karnaugh Maps (Kmaps)

• Origins: Invented in 1953 by Maurice Karnaugh, a telecommunications engineer at Bell Labs, while designing telephone circuits.

• Purpose: A graphical method for visualizing and simplifying Boolean expressions, which is less error-prone than using identities.

• Terminology:

  • Kmap: A matrix of rows and columns representing function output values.

  • Minterm: A product term containing all of the function's variables exactly once (either complemented or not).

• Kmap Structure: Each cell in a Kmap corresponds to a line in the function's truth table. For three variables ($x, y, z$), the columns ($yz$) follow a pattern that is not a standard binary sequence to ensure adjacency.

• Simplification Rules:

  1. Groups can only contain $1$s.

  2. Groups must be formed at right angles (no diagonals).

  3. The number of $1$s in a group must be a power of $2$ ($1, 2, 4, 8, \dots$).

  4. Groups must be as large as possible.

  5. Groups can overlap.

  6. Groups can wrap around the sides of the Kmap (edges are adjacent).

Don’t Care Conditions

• Definition: Sets of inputs that can never occur in a real circuit (e.g., certain patterns in a 7-segment LED display for a calculator).

• Representation: Identified by an "X" in the Kmap cell.

• Usage: In simplification, designers are free to include or ignore X values to create the largest possible power-of-two groupings, thereby further simplifying the circuit.

Combinational Logic

• Description: Circuits where the output is produced almost instantly when input values are applied. They do not have memory.

• Common Components:

  • Half Adder: Finds the sum of two bits. Sum is calculated via XOR; Carry is calculated via AND.

  • Full Adder: Includes a Carry-in bit for multi-bit addition.

  • Ripple-Carry Adder: Multiple full adders connected in series. The carry bit "ripples" from one adder to the next (though modern systems use more efficient designs).

  • Decoder: Uses $n$ inputs to enable one of $2^n$ output locations. Useful for memory addressing.

  • Multiplexer (MUX): Selects a single output from several inputs based on control lines. To select from $n$ inputs, $\log_2(n)$ control lines are needed.

  • Shifter: Moves bits of a nibble (or word) to the left or right.

Sequential Logic and State-Based Circuits

• Description: Circuits where the output depends on both current inputs and the current state (memory) of the circuit.

• The Clock: A special circuit that sends electrical pulses to sequence events. State changes only occur when the clock "ticks."

  • Edge-Triggered: Logic changes on the rising (highest voltage) or falling (lowest voltage) edge of the pulse.

  • Level-Triggered: Logic changes when the clock reaches its highest or lowest absolute voltage level.

• Feedback: The mechanism for memory where the output is looped back into the input.

Flip-Flops

• SR Flip-Flop (Set/Reset): The most basic sequential unit. It has an unstable state when both $S$ and $R$ are $1$.

• JK Flip-Flop: A modified SR flip-flop that is stable for all input combinations, including when both inputs are $1$ (this toggles the state).

• D Flip-Flop (Data): The fundamental unit of computer memory. The output changes only when the input $D$ changes at the clock pulse; otherwise, it remains stable.

Finite State Machines (FSMs)

• Components: A set of nodes (states) and arcs (transitions).

• Moore Machine: Outputs are associated with the nodes (states) themselves.

• Mealy Machine: Outputs are associated with the transitions (arcs) between states.

• Algorithmic State Machines (ASM): Invented by Christopher Clare to address the timing and complex signal interaction limitations of Moore and Mealy machines.

• Applications: Used in stateful applications like microwave ovens, 4-bit registers, and binary counters.

Advanced Logic Applications: Convolutional Coding

• PRML Code: Partial Response Maximum Likelihood. Used in data storage.

• Convolutional Encoder: A system where two symbols are output for every one symbol input (a $1/2$ convolutional code).

• Viterbi Decoding: Uses a lattice diagram to plot state transitions and identify the path of "maximum likelihood" to correct erroneous strings (e.g., correcting an erroneous received string like $10\,10\,11\,11$ back to the likely original string).

Digital Circuit Design Methodologies

• Digital Analysis: Exploring the relationship between given circuit inputs and their resulting outputs.

• Digital Synthesis: Creating logic diagrams from the requirements of a truth table.

• Physical Realities: Designers must account for propagation delays (the time it takes for a circuit to stabilize after input changes).

• Design Tools: Designers use specialized software like VHDL (VHSIC Hardware Description Language) and Verilog.

• Principle of Equivalence: Software is a collection of algorithms that can be implemented in hardware; hardware is often preferred for simple, specialized algorithms requiring maximum speed.

• Embedded Systems: Small, special-purpose computers found in everyday objects, requiring an understanding of both logic circuits and specialized programming.