Digital Logic Design: K-Maps, Gates, and Memory Systems

Posted on Aug 26, 2026 in Systems Computer Engineering

Karnaugh Map (K-Map) Fundamentals

Karnaugh Map (K-Map) is a graphical method used to simplify Boolean expressions and logical functions. It is mainly used in digital electronics and computer science to reduce a complex Boolean expression into a simpler form. A K-Map represents the values of a Boolean function in the form of a table or cells. By grouping the adjacent cells containing 1 or 0, unnecessary variables can be eliminated and a simple Boolean expression can be obtained.

K-Map helps in designing simple and efficient digital circuits because it reduces the number of logic gates required in a circuit. It is an easier method of Boolean simplification compared to solving long Boolean algebra expressions.

K-Map stands for Karnaugh Map. It was developed by Maurice Karnaugh. It provides a visual way to simplify Boolean expressions.

A K-Map consists of a number of cells. Each cell represents a minterm of the Boolean function. The number of cells depends on the number of variables.

For example:

• 2 variables → 4 cells
• 3 variables → 8 cells
• 4 variables → 16 cells

The cells are arranged in Gray code order, so that adjacent cells differ in only one variable.

The main idea of K-Map is to place 1 in the cells where the output of the Boolean function is 1. Then, adjacent 1s are grouped together. These groups are used to obtain the simplified Boolean expression.

Example: Consider the Boolean function:

F(A, B) = Σ(1, 3)

The K-Map for two variables is:

Here, the cells containing 1 are adjacent, so we can make one group of two cells.

Both selected cells have B = 1, while the value of A changes from 0 to 1.

Therefore, A is eliminated and only B remains.

Simplified expression:

F = B

Thus, the original Boolean function F(A, B) = Σ(1, 3) is simplified to: F = B

Rules of K-Map

The important rules for grouping in K-Map are:

1. We group adjacent 1s when simplifying a function in SOP (Sum of Products) form.
2. The number of cells in a group must be a power of 2, such as 1, 2, 4, 8, 16, etc.
3. We should always try to make the largest possible group.
4. Cells can be grouped horizontally or vertically.
5. Diagonal cells cannot be grouped together.
6. The first and last rows or columns are also considered adjacent.
7. A cell can be included in more than one group if it helps in getting a simpler expression.
8. After making the groups, the variables that change within a group are eliminated.
9. The variables that remain constant are included in the simplified expression.

Advantages of K-Map

• It makes Boolean expression simplification easier.
• It reduces the number of logic gates.
• It reduces the complexity of digital circuits.
• It helps in designing faster and more efficient circuits.
• It is easier to understand than lengthy Boolean algebra calculations.

Data Types and Number Systems

A data type defines the type of data that can be stored and processed by a computer or program. It tells the computer what kind of value a variable can store. Common data types are Integer, Float, Character, and Boolean.

Number System

A number system is a method of representing numbers using a specific set of digits. In computer science, the main number systems are Decimal, Binary, Octal, and Hexadecimal.

1. Decimal Number System

The Decimal Number System has base 10 and uses ten digits from 0 to 9. It is the number system commonly used by humans.

Example:
245 = 2 × 10² + 4 × 10¹ + 5 × 10⁰

2. Binary Number System

The Binary Number System has base 2 and uses only two digits, 0 and 1. It is the basic number system used by computers.

Example:
1011₂ = 1 × 2³ + 0 × 2² + 1 × 2¹ + 1 × 2⁰ = 11₁₀

3. Octal Number System

The Octal Number System has base 8 and uses digits from 0 to 7.

Example:
157₈ = 1 × 8² + 5 × 8¹ + 7 × 8⁰ = 111₁₀

4. Hexadecimal Number System

The Hexadecimal Number System has base 16. It uses digits 0–9 and A–F, where A = 10, B = 11, …, F = 15.

Example:
2A₁₆ = 2 × 16¹ + 10 × 16⁰ = 42₁₀

Logic Gates: NOR, NAND, and XOR

1. NOR Gate

Definition: The NOR gate is an OR gate followed by a NOT gate. It gives 1 only when all inputs are 0.

Boolean Expression: Y = (A + B)’

Diagram: A, B → OR → NOT → Y

2. NAND Gate

Definition: The NAND gate is an AND gate followed by a NOT gate. It gives 0 only when all inputs are 1.

Boolean Expression: Y = (A · B)’

Diagram: A, B → AND → NOT → Y

3. XOR Gate

Definition: The XOR (Exclusive-OR) gate gives 1 when the inputs are different and 0 when they are the same.

Boolean Expression: Y = A ⊕ B

Diagram: A, B → XOR → Y

Flip-Flops and R-S Circuit Operations

A Flip-Flop is a basic digital memory circuit that can store one bit of binary data (0 or 1). It has two stable states and can change its state according to the input signals. Flip-flops are widely used in registers, counters, and memory circuits.

Types of Flip-Flops

1. R-S (Reset-Set) Flip-Flop
2. J-K Flip-Flop
3. D (Data) Flip-Flop
4. T (Toggle) Flip-Flop

The R-S Flip-Flop is a basic flip-flop having two inputs: R (Reset) and S (Set), and two outputs Q and Q̅. It is used to store one bit of information.

Diagram

       ±—————————±
 S ———›|         |———› Q
       |  R-S    |
 R ———›| Flip-Flop|———› Q̅
       ±—————————±

Truth Table

Logic Gates: Diagrams and Truth Tables

Logic Gates are basic electronic circuits used in digital electronics to perform logical operations on one or more binary inputs (0 and 1) and produce a single binary output. They are the basic building blocks of digital circuits and computers.

Types of Logic Gates

The main logic gates are: AND, OR, NOT, NAND, NOR, XOR, and XNOR.

1. AND Gate

Definition: The AND gate gives output 1 only when all inputs are 1.

Expression: Y = A · B

Diagram: A, B → AND → Y

2. OR Gate

Definition: The OR gate gives output 1 when any one or both inputs are 1.

Expression: Y = A + B

Diagram: A, B → OR → Y

3. NOT Gate

Definition: The NOT gate gives the opposite or complement of the input.

Expression: Y = A̅

Diagram: A → NOT → Y

4. NAND Gate

Definition: The NAND gate is an AND gate followed by NOT. It gives 0 only when all inputs are 1.

Expression: Y = (A · B)̅

5. NOR Gate

Definition: The NOR gate is an OR gate followed by NOT. It gives 1 only when all inputs are 0.

Expression: Y = (A + B)̅

6. XOR Gate

Definition: The XOR gate gives output 1 when the inputs are different.

Expression: Y = A ⊕ B

7. XNOR Gate

Definition: The XNOR gate gives output 1 when the inputs are the same.

Expression: Y = A ⊙ B

Computer Memory Types and Classifications

Memory is the storage unit of a computer that is used to store data, instructions, and results for processing. It allows the CPU to access the required information quickly. Memory is mainly divided into Primary Memory and Secondary Memory.

Types of Memory

1. Primary Memory

Primary memory is the main memory of a computer. It is directly accessed by the CPU and is faster than secondary memory.

• RAM (Random Access Memory): Temporary memory used to store data and programs currently being used. It is volatile, so data is lost when power is turned off.
• ROM (Read Only Memory): Stores permanent instructions required to start and operate the computer. It is non-volatile.

2. Secondary Memory

Secondary memory is used for permanent storage of data and programs. It has a larger storage capacity but is slower than primary memory.

Examples: Hard Disk (HDD), SSD, Pen Drive, Memory Card, CD/DVD.

Key Differences

Multiplexers and De-Multiplexers

1. Multiplexer (MUX)

A Multiplexer (MUX) is a digital circuit that selects one input from many input lines and sends the selected input to a single output line. The selection is controlled by select lines. It is also called a Data Selector.

Diagram

        I0 ———±
        I1 ———|
        I2 ———|  MUX ———› Y
        I3 ———|
             |
        S0,S1 —› Select Lines

For a 4-to-1 MUX, the number of select lines is 2. Formula: Number of Select Lines = log&sub2;(Number of Inputs)

4-to-1 MUX Selection Table

2. De-Multiplexer (DEMUX)

A De-Multiplexer (DEMUX) is a digital circuit that takes one input and sends it to one of many output lines. The required output line is selected using select lines. It is also called a Data Distributor.

Diagram

                 ±——› Y0
                 |
Input ———› DEMUX |——› Y1
                 |
                 |——› Y2
                 |
                 ±——› Y3
                    ^
                 S0,S1
              Select Lines

1-to-4 DEMUX Selection Table

Sequential Circuits and Universal Gates

(a) Sequential Circuit

A Sequential Circuit is a digital circuit whose output depends on both the present input and the previous state (past output) of the circuit. It contains memory elements such as flip-flops to store previous information.

Examples: Counters, Registers, Shift Registers.

Key Point: Sequential Circuit = Input + Previous State → Output

(b) Universal Gates

NAND and NOR gates are called Universal Gates because any basic logic gate such as AND, OR, and NOT can be constructed using only NAND gates or only NOR gates.

They are widely used in digital circuit design because complete logic circuits can be built using a single type of gate.

Key Point: NAND + NOR = Universal Gates

(c) ROM

ROM (Read Only Memory) is a type of non-volatile memory used to store data and instructions permanently. The data stored in ROM is not lost when the power is switched off. ROM is commonly used to store boot instructions and firmware.

Types: PROM, EPROM, EEPROM.

Key Point: ROM = Permanent / Non-volatile Memory

(d) Register

A Register is a group of flip-flops used to store binary data temporarily. Each flip-flop stores one bit, so a register with 8 flip-flops can store 8 bits of data. Registers are used inside the CPU for temporary storage and data transfer.

Examples: Data Register, Address Register, Shift Register.

Key Point: Register = Group of Flip-Flops → Stores Binary Data