Data Representation, Digital Logic, and Logic Gates

Data Representation in Digital Computers

• Binary Representation:
  • Digital computers represent all forms of data—including numbers, text, images, and sound—using binary digits: $0$ and $1$.
  • Bit:
  • A bit is defined as a single binary digit, taking the value of either $0$ or $1$.
  • Byte:
  • A byte is defined as a group of $8$ bits.
  • Calculation example: A group of $3$ bytes equals $3 \times 8 = 24$ bits.
  • Character Encoding:
  • In ASCII encoding, the 8-bit binary sequence $01000001$ represents the uppercase letter A.

Analog and Digital Signals

• Nature of Signals:
  • A signal functions to carry information from one physical location to another.
  • Noise is defined as unwanted interference that disturbs a signal during transmission or processing.
• Comparison Between Analog and Digital Signals:
  • Signal Variation:
  • Analog signals change continuously and can take any value within a continuous range.
  • Digital signals use discrete, distinct levels. Modern computers typically operate using two voltage levels representing $0$ and $1$.
  • Concrete Examples:
  • An example of an analog signal is the sound waves produced by a human voice.
  • An example of a digital signal is the electrical signaling transmitted between computer components.
  • Susceptibility to Interference:
  • Analog signals are more affected by noise.
  • Digital signals are generally more resistant to noise.

Digital Logic and Fundamental Logic Gates

• Definition of a Logic Gate:
  • A logic gate is an electronic circuit that performs a specific logical operation on binary inputs to produce a single binary output.
• Standard Gate Types, Expressions, and Output Rules:
  • AND Gate:
  • Boolean expression: $F = A \cdot B$
  • Output rule: Produces an output of $1$ only when both inputs are $1$.
  • OR Gate:
  • Boolean expression: $F = A + B$
  • Output rule: Produces an output of $1$ when at least one input is $1$.
  • NOT Gate (Inverter):
  • Boolean expression: $F = \overline{A}$
  • Output rule: Reverses the input value (inverts $0$ to $1$, and $1$ to $0$).
  • NAND Gate:
  • Boolean expression: $F = \overline{A \cdot B}$
  • Output rule: Produces an output of $0$ only when both inputs are $1$.
  • NOR Gate:
  • Boolean expression: $F = \overline{A + B}$
  • Output rule: Produces an output of $1$ only when both inputs are $0$.
  • XOR Gate (Exclusive OR):
  • Boolean expression: $F = A \oplus B$
  • Output rule: Produces an output of $1$ when the two inputs are different from each other.
• Universal Gates:
  • NAND and NOR are classified as universal gates.
  • Either NAND gates alone or NOR gates alone can be combined to construct any other type of logic gate.

Truth Tables and Input Combinations

• Function of Truth Tables:
  • A truth table provides an exhaustive tabular listing of every possible input combination alongside its corresponding logic output.
• Input-to-Combination Scaling:
  • For a system with $n$ binary inputs, the total number of unique input combinations is given by $2^n$.
  • $1$ input yields $2^1 = 2$ combinations.
  • $2$ inputs yield $2^2 = 4$ combinations.
  • $3$ inputs yield $2^3 = 8$ combinations.
• Combined Truth Table for Two-Input Gates:
  • Input combination $A = 0$, $B = 0$:
  • AND output: $0$
  • OR output: $0$
  • NAND output: $1$
  • NOR output: $1$
  • XOR output: $0$
  • Input combination $A = 0$, $B = 1$:
  • AND output: $0$
  • OR output: $1$
  • NAND output: $1$
  • NOR output: $0$
  • XOR output: $1$
  • Input combination $A = 1$, $B = 0$:
  • AND output: $0$
  • OR output: $1$
  • NAND output: $1$
  • NOR output: $0$
  • XOR output: $1$
  • Input combination $A = 1$, $B = 1$:
  • AND output: $1$
  • OR output: $1$
  • NAND output: $0$
  • NOR output: $0$
  • XOR output: $0$
• Truth Table for the Single-Input NOT Gate:
  • Input $A = 0$ yields output NOT $A = 1$.
  • Input $A = 1$ yields output NOT $A = 0$.

Boolean Algebra Principles and Laws

• Operational Foundations:
  • Boolean algebra relies on binary values $0$ and $1$ alongside logical operators to represent and simplify digital circuits.
  • Operator definitions:
  • The centered dot symbol $\cdot$ denotes the logical AND operation.
  • The plus symbol $+$ denotes the logical OR operation.
  • An overbar denotes the logical NOT operation (inversion/complement).
  • Note on Boolean addition: The expression $1 + 1 = 1$ holds true because $+$ represents the logical OR operator rather than standard arithmetic addition.
• Evaluation Example:
  • Expression to evaluate: $F = A + (B \cdot C)$
  • Given input assignments: $A = 0$, $B = 1$, $C = 0$
  • Step-by-step substitution: $F = 0 + (1 \cdot 0) = 0 + 0 = 0$
• Fundamental Algebraic Laws:
  • Identity Law:
  • AND form: $A \cdot 1 = A$
  • OR form: $A + 0 = A$
  • Null Law / Domination Law:
  • AND form: $A \cdot 0 = 0$
  • OR form: $A + 1 = 1$
  • Idempotent Law:
  • AND form: $A \cdot A = A$
  • OR form: $A + A = A$
  • Complement Law:
  • AND form: $A \cdot \overline{A} = 0$
  • OR form: $A + \overline{A} = 1$
  • Commutative Law:
  • AND form: $A \cdot B = B \cdot A$
  • OR form: $A + B = B + A$
  • Associative Law:
  • AND form: $(A \cdot B) \cdot C = A \cdot (B \cdot C)$
  • OR form: $(A + B) + C = A + (B + C)$
  • Absorption Law:
  • AND form: $A \cdot (A + B) = A$
  • OR form: $A + (A \cdot B) = A$
  • Double Complement / Involution Law:
  • Inverting a variable twice returns its original state: $\overline{\overline{A}} = A$
  • Distributive Laws:
  • Distributing AND over OR: $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
  • Distributing OR over AND: $A + (B \cdot C) = (A + B) \cdot (A + C)$
  • De Morgan's Laws:
  • Negated AND expression: $\overline{A \cdot B} = \overline{A} + \overline{B}$
  • Negated OR expression: $\overline{A + B} = \overline{A} \cdot \overline{B}$
  • Operational procedure: Change AND to OR (or OR to AND) and invert/complement each individual term when eliminating an overbar across an entire grouped expression.

Simplification of Boolean Expressions

• Purpose of Algebraic Simplification:
  • Simplifying Boolean expressions directly decreases the number of logic gates and wiring required to fabricate physical hardware circuits.
• Worked Derivation Example:
  • Initial Boolean function:
  • $F = (A \cdot B) + (A \cdot \overline{B})$
  • Factoring using the Distributive Law:
  • $F = A \cdot (B + \overline{B})$
  • Substituting using the Complement Law ($B + \overline{B} = 1$):
  • $F = A \cdot 1$
  • Reducing using the Identity Law ($A \cdot 1 = A$):
  • $F = A$

Implementation and Circuit Conversion

• Gate Mapping Procedure:
  • To construct physical circuits from Boolean equations, map each mathematical operator directly to its corresponding logic gate symbol.
• Worked Mapping Examples:
  • Composite Expression $F = (A \cdot B) + \overline{C}$:
  • Step 1: Use an AND gate to combine inputs $A$ and $B$.
  • Step 2: Use a NOT gate to invert input $C$, yielding $\overline{C}$.
  • Step 3: Route the outputs of both the AND gate and the NOT gate into an OR gate to produce $F$.
  • Inverted Product Expression $F = A \cdot \overline{B}$:
  • Invert variable $B$ first using a NOT gate.
  • Combine the inverted output $\overline{B}$ with input $A$ using an AND gate.

Karnaugh Maps (K-Maps) and Optimization

• Functional Overview:
  • A Karnaugh map (K-map) provides a visual, diagrammatic approach for minimizing Boolean logic expressions by identifying and clustering adjacent groups of $1$s.
• Sizing Configurations:
  • Two-variable maps contain $4$ square boxes.
  • Three-variable maps contain $8$ square boxes.
• Strict Grouping Rules:
  • Rule 1 (Group sizes): Group sizes must always be integer powers of two, such as $1$, $2$, $4$, $8$, and so forth.
  • Rule 2 (Geometry): Groups must only form rectangular or square clusters.
  • Rule 3 (Adjacency direction): Adjacent elements connect horizontally or vertically; grouping diagonally is strictly prohibited.
  • Rule 4 (Maximal size): Each formed group must be made as large as mathematically possible.
  • Rule 5 (Complete coverage): Every $1$ in the matrix must be included in at least one group; groups are permitted to overlap.
  • Rule 6 (Wrap-around property): The opposing outer edges of the map are considered adjacent and connect continuously.
  • Rule 7 (Zero exclusion): Boxes containing $0$ must never be included inside a grouping of $1$s.
• Formulating Simplified Terms from Groups:
  • If a variable remains constantly at logic $1$ across the entire group: Retain the uncomplemented variable (e.g., $A$).
  • If a variable remains constantly at logic $0$ across the entire group: Retain the complemented variable (e.g., $\overline{A}$).
  • If a variable alternates between $0$ and $1$ within the group: Eliminate the variable from the resulting term entirely.
• Gray Code Order:
  • In a three-variable map, column coordinates must follow Gray code ordering:
  • Sequence: $00$, $01$, $11$, $10$
  • Under this system, only a single binary bit transitions between adjacent neighboring columns, which extends continuously between the first and last column.
• Three-Variable K-Map Worked Example:
  • Grid Layout (Rows represent input $A$, Columns represent input pair $BC$):
  • Top row ($A = 1$): $0$ (at $00$), $1$ (at $01$), $1$ (at $11$), $0$ (at $10$)
  • Bottom row ($A = 0$): $0$ (at $00$), $1$ (at $01$), $1$ (at $11$), $0$ (at $10$)
  • Grouping Execution:
  • The four adjacent $1$s occupying the center columns ($01$ and $11$) form a single quad group of size $4$.
  • Variable Analysis:
  • Variable $A$ toggles between $1$ and $0$ (eliminated).
  • Variable $B$ toggles between $0$ (in column $01$) and $1$ (in column $11$) (eliminated).
  • Variable $C$ maintains a constant value of $1$ across all four cells.
  • Minimized Boolean result: $F = C$

The Principle of Duality

• Core Axiom:
  • If any given Boolean algebraic identity is mathematically valid, its corresponding dual statement is guaranteed to be true.
• Transformation Procedure to Find the Dual:
  • Swap all AND operators with OR operators ($\cdot \leftrightarrow +$).
  • Swap all OR operators with AND operators ($+ \leftrightarrow \cdot$).
  • Swap every binary constant $0$ with $1$, and every $1$ with $0$.
  • Maintain all variable identities and existing complement bars unchanged.
  • Maintain identical precedence groupings and parentheses.
  • Critical distinction: Duality does not invert or complement the logical variables themselves.
• Standard Duality Pairings:
  • Identity Pair 1:
  • Base identity: $A + 0 = A$
  • Dual expression: $A \cdot 1 = A$
  • Identity Pair 2:
  • Base identity: $A + 1 = 1$
  • Dual expression: $A \cdot 0 = 0$
  • Identity Pair 3:
  • Base identity: $A + \overline{A} = 1$
  • Dual expression: $A \cdot \overline{A} = 0$
  • Identity Pair 4:
  • Base identity: $A + B = B + A$
  • Dual expression: $A \cdot B = B \cdot A$

Real-World Applications of Logic Gates

• Functional Sectors and Implementations:
  • Computers and Calculators:
  • Utilized to execute arithmetic operations and digital logical comparisons.
  • Digital Memory Circuits:
  • Utilized to store individual binary bits through sequential circuit configurations such as flip-flops.
  • Security and Alarm Systems:
  • Utilized to trigger alarms based on inputs collected from physical environmental sensors.
  • Automatic Control Systems:
  • Utilized to govern and automate mechanical or electrical devices based on predefined conditional inputs.
• Real-World Logic Scenarios:
  • Industrial AND Application:
  • A factory machine operates only when both safety conditions are simultaneously satisfied: the safety guard is fully closed AND the start button is depressed.
  • Building Security OR Application:
  • An alarm activates if any intrusion sensor trips: when the door sensor detects danger OR the window sensor detects danger.