Digital logic fundamentals and Boolean algebra notes — Unit 5

The universe operates in Analog (continuous, infinite variations). Computers operate in Digital (discrete, binary steps). This unit covers the mathematical logic required to process digital signals.

⇒Positive vs Negative Logic

• Positive Logic (Standard): High voltage (+5V) = Logic 1. Low voltage (0V) = Logic 0.
• Negative Logic: High voltage (+5V) = Logic 0. Low voltage (0V) = Logic 1.

Humans count in Base-10 (Decimal). Digital hardware counts in Base-2 (Binary). To compress long binary strings for human readability, we use Octal (Base-8) and Hexadecimal (Base-16).

⇒The Bases

• Decimal (Base 10): Valid digits are 0 through 9.
• Binary (Base 2): Valid digits are 0 and 1. (Each digit is a 'bit').
• Octal (Base 8): Valid digits are 0 through 7. (Represents exactly 3 binary bits).
• Hexadecimal (Base 16): Valid digits are 0-9, followed by A, B, C, D, E, F. (A=10, F=15. Represents exactly 4 binary bits).

⇒Binary to Decimal Conversion

Multiply each bit by 2 raised to the power of its positional index, starting from index 0 on the far right.

Convert (1101)₂ to Decimal:
1*2^3  +  1*2^2  +  0*2^1  +  1*2^0
  8    +    4    +    0    +    1   =  (13)₁₀

⇒Decimal to Binary (Repeated Division)

Divide the decimal number by 2. Record the remainder. Keep dividing the quotient by 2 until you hit 0. Read the remainders from BOTTOM to TOP.

Convert 13 to Binary:
13 / 2 = 6  (Remainder 1)  ^ Read up!
 6 / 2 = 3  (Remainder 0)  |
 3 / 2 = 1  (Remainder 1)  |
 1 / 2 = 0  (Remainder 1)  |

Result: (1101)₂

⇒Binary to Hexadecimal (Grouping)

Because 16 is exactly 2^4, one Hex digit maps perfectly to four Binary bits. Group the binary bits in chunks of 4, starting from the right.

Convert (1011010111)₂ to Hex:
1. Group into 4s from the right:  10  1101  0111
2. Pad the left with zeroes:    0010  1101  0111
3. Convert each chunk:            2     D     7

Result: (2D7)₁₆

A hardware processor does not have a minus sign key. It only understands 1s and 0s. To represent negative numbers, and to perform subtraction using ADDER circuits, we use Complement arithmetic.

⇒1's Complement

Simply invert every single bit. Change all 1s to 0s, and all 0s to 1s.

Original:   1 0 1 1 0 0
1's Comp:   0 1 0 0 1 1

⇒2's Complement

The industry standard for representing negative numbers in CPUs. To find the 2's complement, first find the 1's complement, then ADD 1 to the rightmost bit (LSB).

Find 2's complement of 1 0 1 1 0 0 :
1. Invert bits (1's comp):  0 1 0 0 1 1
2. Add 1 to the end:                  + 1
                           ---------------
Result (2's comp):          0 1 0 1 0 0

If a processor needs to perform `A - B`, it simply calculates the 2's complement of B, and then ADDS it to A. This allows ALUs to do subtraction without needing dedicated subtractor hardware.

Logic gates are the physical building blocks of computers. They take one or more binary inputs and produce a single binary output based on a specific logical rule.

NAND and NOR gates are called 'Universal Gates' because you can build ANY other logic gate (AND, OR, NOT) using ONLY a massive collection of NAND gates, or ONLY NOR gates. This saves billions of dollars in chip manufacturing.

⇒NAND Gate (NOT-AND)

An AND gate followed immediately by a NOT gate. It outputs the exact opposite of an AND gate. Output is 0 ONLY if both inputs are 1. Equation: Y = (A·B)'

⇒NOR Gate (NOT-OR)

An OR gate followed by a NOT gate. Output is 1 ONLY if both inputs are 0. Equation: Y = (A+B)'

⇒Special Gates: XOR and XNOR

• XOR (Exclusive-OR): The 'Difference Detector'. Output is 1 ONLY if the inputs are DIFFERENT (0,1 or 1,0). Equation: Y = A ⊕ B
• XNOR (Exclusive-NOR): The 'Equivalence Detector'. Output is 1 ONLY if the inputs are EXACTLY THE SAME (0,0 or 1,1).

Boolean algebra is the mathematics of digital logic. We use it to take a massively complex, expensive circuit design and mathematically simplify it to use fewer gates, making the chip cheaper and faster.

⇒Fundamental Laws

• Identity: A + 0 = A, A · 1 = A
• Null/Dominance: A + 1 = 1, A · 0 = 0
• Idempotent: A + A = A, A · A = A
• Complement: A + A' = 1, A · A' = 0
• Double Negation: (A')' = A

⇒De Morgan's Theorems

The most powerful tools in digital logic for breaking long, inverted bars over an expression. The rule is: 'Break the bar, change the sign'.

Theorem 1: The complement of a product is the sum of the complements.
(A · B)' = A' + B'

Theorem 2: The complement of a sum is the product of the complements.
(A + B)' = A' · B'

Any logical truth table can be written out as a raw mathematical equation in two standard forms.

⇒Sum of Products (SOP)

We focus exclusively on the rows in the truth table where the Output is 1. We create an AND product for each of those rows, and then OR them all together.

• In SOP, an input of 1 is written as the literal (A). An input of 0 is written as the complement (A').
• Example Equation: Y = A'BC + AB'C + ABC

⇒Product of Sums (POS)

We focus exclusively on the rows where the Output is 0. We create an OR sum for each of those rows, and then AND them all together.

• In POS, the rule flips! An input of 0 is written as the literal (A). An input of 1 is written as the complement (A').
• Example Equation: Y = (A+B'+C) · (A'+B+C)

SOP is overwhelmingly preferred by engineers because it directly translates to a two-level 'AND-OR' hardware circuit layout.

Simplifying equations using Boolean algebra is tedious and prone to human error. A K-Map is a visual, graphical method to instantly find the absolute simplest, most minimized version of a logic equation.

⇒The Structure of a K-Map

A K-Map is a grid. A 3-variable equation (A, B, C) requires an 8-cell grid (2^3). A 4-variable equation requires a 16-cell grid.

• The edges of the grid are labeled using Gray Code (00, 01, 11, 10).
• Notice that 11 comes BEFORE 10. Gray code ensures that moving from one cell to an adjacent cell changes ONLY ONE single bit.
• This single-bit change is the magic that allows visual simplification to cancel out redundant variables.

⇒Plotting and Grouping Rules

• Place a '1' in the cells corresponding to the SOP terms.
• Group the 1s into geometric rectangles. The size of a group MUST be a power of 2 (1, 2, 4, 8, 16).
• Groups can overlap.
• The K-Map wraps around! You can group a cell on the far left edge with a cell on the far right edge.
• Goal: Create the LARGEST possible groups, using the FEWEST total groups.

Once the '1s' are grouped into large boxes, you generate the final, simplified equation by looking at what variables stay constant inside each group.

⇒The Extraction Rule

Look at the labels on the edges for a specific group.

If a variable changes from 0 to 1 across the group, it cancels itself out. Throw it away.
If a variable stays 1 across the whole group, write it down as normal (e.g., A).
If a variable stays 0 across the whole group, write it down as inverted (e.g., A').

⇒Don't Care Conditions (X)

In some real-world machines, certain input combinations will literally never happen (e.g., a BCD counter will never reach the number 13). We mark these impossible cells with an 'X'.

When grouping, you can choose to treat an 'X' as a 1 IF it helps you make a larger group. If it doesn't help, you can ignore it and treat it as a 0. This flexibility allows for even greater circuit simplification.

Combinational circuits are circuits where the current Output depends STRICTLY on the current Input. They have no memory. The most vital combinational circuit in a CPU's Arithmetic Logic Unit (ALU) is the Adder.

⇒The Half Adder

Adds two single binary bits (A and B). It produces a Sum (S) and a Carry (C).

• Sum (S): Output is 1 only when inputs are different (1+0=1, 0+1=1). This perfectly matches the XOR Gate. Equation: S = A ⊕ B
• Carry (C): Output is 1 only when both inputs are 1 (1+1 = 0 with a carry of 1). This perfectly matches the AND Gate. Equation: C = A · B

⇒The Full Adder

The half adder is useless for multi-bit addition because it cannot accept a carry coming from a previous column. A Full Adder adds THREE bits together: A, B, and Carry-In (Cin).

Sum = A ⊕ B ⊕ Cin
Carry-Out = (A · B) + (Cin · (A ⊕ B))

To add two 8-bit numbers together, a CPU cascades eight Full Adders in a chain, linking the Carry-Out of one to the Carry-In of the next.

A Multiplexer (MUX) is a digital switch. It has many data inputs, but only ONE output. It uses 'Select Lines' to choose exactly which input gets routed to the output.

⇒The 4-to-1 MUX

Has 4 data inputs (D0, D1, D2, D3), 1 Output (Y), and 2 Select lines (S1, S0).

⇒Applications of a MUX

• Data Routing: Connecting multiple network streams into a single outgoing fiber optic cable.
• Parallel to Serial Conversion: By rapidly sweeping through the select lines (00, 01, 10, 11), the MUX reads 4 parallel bits and shoots them out the single output pin in a rapid serial stream.
• Universal Function Generator: A MUX can be wired to implement ANY arbitrary Boolean logic function without needing individual AND/OR gates.

⇒The De-Multiplexer (De-MUX)

The exact reverse of a MUX. It takes a single data input and routes it to one of many possible outputs, based on the Select lines. Used heavily at the receiving end of a communication system to unpack a serial data stream back into parallel channels.

⇒Decoders

A decoder has 'n' inputs and '2^n' outputs. It reads a binary number on its inputs, and turns ON the single specific output pin corresponding to that decimal number.

• 2-to-4 Line Decoder: Has inputs A and B. Outputs Y0, Y1, Y2, Y3.
• If inputs are 1 and 0 (Binary for 2), only pin Y2 turns ON. All other pins stay 0.

Decoders are the heart of computer memory systems. When the CPU asks for data at memory address '10110', a massive decoder looks at those bits and physically energizes the exact row of silicon memory cells where that data is stored.

⇒End-of-Unit Verification

• Convert (110110.101)₂ into Decimal, Octal, and Hexadecimal.
• Explain how a CPU uses 2's Complement to perform subtraction.
• Draw the symbols, write the boolean equations, and generate the truth tables for AND, OR, NOT, NAND, NOR, and XOR gates.
• State De Morgan's two theorems and mathematically prove them using a truth table.
• Explain why NAND and NOR are called Universal Gates, and draw the circuit to create a NOT gate using only a NAND gate.
• Convert a given truth table into a Sum of Products (SOP) boolean expression.
• Plot a 4-variable boolean equation onto a Karnaugh Map, apply grouping rules (including overlapping and wrap-around), and extract the minimized equation.
• Explain how 'Don't Care' conditions (X) can be used to further minimize a K-Map.
• Draw the logic circuit for a Half Adder using an XOR gate and an AND gate.
• Write the Boolean equations for the Sum and Carry-Out of a Full Adder.
• Explain the working of a 4-to-1 Multiplexer with its truth table and list two practical applications.