Unit 2: Number Systems & Boolean Algebra

2.1 Number System

Digital computers represent all kinds of data, including numbers, letters, and symbols, in binary numbers. A number system defines a set of values to represent quantity. The base or radix of a number system is the total number of unique digits used in that system.

• Decimal (Base-10): Uses 10 digits (0-9). This is the system we use in daily life.
• Binary (Base-2): Uses 2 digits (0 and 1). This is the language of computers.
• Octal (Base-8): Uses 8 digits (0-7).
• Hexadecimal (Base-16): Uses 16 symbols (0-9 and A-F, where A=10, B=11, ..., F=15).

2.2 Boolean Algebra and Logic Gates

Boolean Algebra

Boolean Algebra, developed by George Boole, is a branch of algebra in which the values of the variables are the truth values true (1) and false (0). It is fundamental to the design of digital circuits.

Logic Gates

A logic gate is an electronic circuit that performs a basic Boolean function, resulting in a single binary output. The fundamental logic gates are:

• AND Gate: Output is 1 only if all inputs are 1. Expression: Y = A . B
• OR Gate: Output is 1 if at least one input is 1. Expression: Y = A + B
• NOT Gate (Inverter): Output is the complement of the input. Expression: Y = A' or Y = Ā

Other important gates include:

• NAND Gate: AND followed by NOT. It is a universal gate.
• NOR Gate: OR followed by NOT. It is also a universal gate.
• XOR Gate (Exclusive OR): Output is 1 if the inputs are different.
• XNOR Gate (Exclusive NOR): Output is 1 if the inputs are the same.

2.3 Simplification of Boolean Functions - Map Method

The Karnaugh Map (K-Map) is a graphical method used to simplify Boolean algebra expressions. It helps to minimize the number of logic gates required in a digital circuit.

Two-Variable Map

A 2-variable K-map has 2² = 4 cells. The map is used to simplify functions of two variables, say A and B.

Example: Simplify F(A,B) = Σm(1, 2, 3)

1. Draw the 2-variable K-map.
2. Place 1s in the cells corresponding to the minterms (1, 2, 3).
3. Group adjacent 1s. We can form two groups of two.
4. The simplified expression is the sum of the terms for each group: F = A + B.

Three-Variable Map

A 3-variable K-map has 2³ = 8 cells. Remember the Gray code sequence (00, 01, 11, 10) for the column headers to ensure only one bit changes between adjacent cells.

2.4 Product of Sums (POS) Simplification

So far, we have discussed Sum of Products (SOP) by grouping 1s. We can also simplify expressions in Product of Sums (POS) form by grouping the zeros (0s) in the K-map.

SOP (Sum of Products): Grouping 1s to get a minimal sum of product terms. (e.g., AB + C'D) POS (Product of Sums): Grouping 0s to get a minimal product of sum terms. (e.g., (A+B) . (C'+D))

To get the POS form from a K-map:

1. Group the 0s.
2. Write the sum term for each group (remember to complement the variables compared to SOP).
3. The final expression is the product of these sum terms.

2.5 NAND and NOR Implementation

NAND and NOR gates are known as universal gates because any Boolean function can be implemented using only NAND gates or only NOR gates.

• NOT using NAND: Tie both inputs of a NAND gate together.
• AND using NAND: A NAND gate followed by a NOT gate (which is another NAND gate).
• OR using NAND: Invert both inputs and then feed them to a NAND gate (using De Morgan's theorem).

2.6 Don't Care Condition

In some logic circuits, there are certain input combinations for which the output value does not matter. These are called "don't care" conditions, represented by an 'X' or 'd' in the K-map.

Benefit: Don't care conditions can be treated as either 0 or 1, whichever helps in forming a larger group of 1s, leading to a more simplified expression.

Rule: Use a don't care ('X') to form a larger group if possible, but you don't have to group all the 'X's.

2.7 The Tabulation Method (Quine-McCluskey)

The Quine-McCluskey (QM) method is a tabular method of simplification that is more suitable for programming than the K-map method, especially for functions with a large number of variables.

Step 1: Determination of Prime Implicants

1. List all minterms in binary form.
2. Group the minterms based on the number of 1s in their binary representation.
3. Compare each minterm with minterms in the next group. If they differ by only one bit, they can be combined. The differing bit is replaced with a dash (-).
4. Repeat this process until no more combinations can be made.
5. The terms that could not be combined further are the Prime Implicants (PIs).

Step 2: Selection of Essential Prime Implicants

1. Create a Prime Implicant chart with PIs as rows and the original minterms as columns.
2. Place an 'X' in a cell if the PI covers that minterm.
3. Find columns with only one 'X'. The PIs corresponding to these rows are Essential Prime Implicants (EPIs). They must be part of the final solution.
4. Select the EPIs and cover all the minterms they account for.
5. If any minterms remain uncovered, select a minimum number of other PIs to cover them.