Digital Logic Circuits and Components
Digital logic circuits form the fundamental building blocks of all modern digital systems, including computers. They operate on discrete values, typically represented as binary digits: 0 (low voltage) and 1 (high voltage). Understanding these circuits is crucial for comprehending how computers process information. This unit will delve into the core concepts, starting with the most basic elements: logic gates.
Logic Gates
Logic gates are electronic circuits that perform basic logical operations on one or more binary inputs to produce a single binary output. These operations are based on Boolean algebra. The most fundamental logic gates are AND, OR, and NOT gates.
1. AND Gate
An AND gate produces an output of 1 only if all of its inputs are 1. Otherwise, the output is 0. It represents the logical conjunction.
Truth Table for a 2-input AND gate:
| Input A | Input B | Output (A AND B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The Boolean expression for an AND gate is typically written as $A \cdot B$ or $AB$.
2. OR Gate
An OR gate produces an output of 1 if at least one of its inputs is 1. The output is 0 only if all inputs are 0. It represents the logical disjunction.
Truth Table for a 2-input OR gate:
| Input A | Input B | Output (A OR B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The Boolean expression for an OR gate is typically written as $A + B$.
3. NOT Gate (Inverter)
A NOT gate has a single input and a single output. The output is the inverse (complement) of the input. If the input is 0, the output is 1, and if the input is 1, the output is 0.
Truth Table for a NOT gate:
| Input A | Output (NOT A) |
|---|---|
| 0 | 1 |
| 1 | 0 |
The Boolean expression for a NOT gate is typically written as $\overline{A}$ or $A'$.
4. NAND Gate
A NAND (NOT-AND) gate is equivalent to an AND gate followed by a NOT gate. Its output is 0 only when all inputs are 1; otherwise, it is 1.
Truth Table for a 2-input NAND gate:
| Input A | Input B | Output (A NAND B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The Boolean expression is $\overline{A \cdot B}$.
5. NOR Gate
A NOR (NOT-OR) gate is equivalent to an OR gate followed by a NOT gate. Its output is 1 only when all inputs are 0; otherwise, it is 0.
Truth Table for a 2-input NOR gate:
| Input A | Input B | Output (A NOR B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
The Boolean expression is $\overline{A + B}$.
6. XOR Gate (Exclusive OR)
An XOR gate produces an output of 1 if an odd number of inputs are 1. For two inputs, it outputs 1 if the inputs are different, and 0 if they are the same.
Truth Table for a 2-input XOR gate:
| Input A | Input B | Output (A XOR B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The Boolean expression is $A \oplus B$, which can be expanded as $A\overline{B} + \overline{A}B$.
7. XNOR Gate (Exclusive NOR)
An XNOR gate produces an output of 1 if an even number of inputs are 1. For two inputs, it outputs 1 if the inputs are the same, and 0 if they are different. It is the inverse of the XOR gate.
Truth Table for a 2-input XNOR gate:
| Input A | Input B | Output (A XNOR B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The Boolean expression is $\overline{A \oplus B}$ or $A \odot B$, which can be expanded as $A B + \overline{A}\overline{B}$.
Boolean Algebra
Boolean algebra is a branch of algebra in which the values of the variables are the truth values, most commonly TRUE and FALSE. It is used to analyze and simplify digital logic circuits. Key concepts include variables, constants, and logical operators (AND, OR, NOT).
Basic Laws and Theorems
These are essential for simplifying Boolean expressions.
- Commutative Laws: $A + B = B + A$; $A \cdot B = B \cdot A$
- Associative Laws: $(A + B) + C = A + (B + C)$; $(A \cdot B) \cdot C = A \cdot (B \cdot C)$
- Distributive Laws: $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$; $A + (B \cdot C) = (A + B) \cdot (A + C)$
- Identity Laws: $A + 0 = A$; $A \cdot 1 = A$
- Complement Laws: $A + \overline{A} = 1$; $A \cdot \overline{A} = 0$
- Idempotent Laws: $A + A = A$; $A \cdot A = A$
- Null Laws (or Annulment Laws): $A + 1 = 1$; $A \cdot 0 = 0$
- Absorption Laws: $A + (A \cdot B) = A$; $A \cdot (A + B) = A$
- De Morgan's Laws: $\overline{A + B} = \overline{A} \cdot \overline{B}$; $\overline{A \cdot B} = \overline{A} + \overline{B}$
- Double Negation Law: $\overline{\overline{A}} = A$
- Consensus Theorem: $AB + \overline{A}C + BC = AB + \overline{A}C$
Boolean Expressions
A Boolean expression is an expression involving binary variables, constants (0 and 1), and logical operators. For example, $F(A, B, C) = A\overline{B} + \overline{A}C$.
Sum of Products (SOP) and Product of Sums (POS): These are standard forms for Boolean expressions.
- SOP: An expression where terms are ORed together, and each term is an ANDed product of literals. Example: $A\overline{B}C + \overline{A}BC$.
- POS: An expression where terms are ANDed together, and each term is an ORed sum of literals. Example: $(A+\overline{B}+C)(\overline{A}+B+C)$.
Map Simplifications (Karnaugh Maps)
Karnaugh maps (K-maps) are a graphical method used for simplifying Boolean algebra expressions. They are particularly effective for expressions with up to 4 or 5 variables. A K-map is a grid where each cell represents a minterm (for SOP) or a maxterm (for POS) of the Boolean function. Adjacent cells (horizontally or vertically, with wrap-around) differ by only one variable.
Steps for Simplification using K-maps (SOP):
- Create the K-map: Draw a grid based on the number of variables. For $n$ variables, the grid has $2^n$ cells. Label the rows and columns with Gray codes to ensure adjacent cells differ by only one bit.
- Fill the K-map: Place a '1' in the cells corresponding to the minterms for which the function is true (usually from a truth table or given expression). Place '0's in the other cells.
- Group the 1s: Group adjacent 1s in powers of two (1, 2, 4, 8, ...). Groups must be rectangular or square. Wrap-around is allowed. Aim for the largest possible groups, and try to cover all 1s with the minimum number of groups. A 1 can be part of multiple groups.
- Derive the simplified expression: For each group, identify the variables that remain constant within that group. If a variable is constant as 0, use its complemented form ($\overline{A}$); if it's constant as 1, use its uncomplemented form ($A$). If a variable changes within the group, it is eliminated. The simplified SOP expression is the OR of the terms derived from each group.
Example: Simplify $F(A, B, C) = \sum m(1, 3, 6, 7)$ using a 3-variable K-map.
The minterms are: $001, 011, 110, 111$.
| A\BC | 00 (0) | 01 (1) | 11 (3) | 10 (2) | ||||
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | ||||
| 1 | 0 | 1 | 1 | 0 | ||||
In the K-map:
- Minterm 1 ($001$): $A=0, B=0, C=1$
- Minterm 3 ($011$): $A=0, B=1, C=1$
- Minterm 6 ($110$): $A=1, B=1, C=0$
- Minterm 7 ($111$): $A=1, B=1, C=1$
Grouping the 1s:
- Group 1: Minterms 1 and 3 (cells $A=0, BC=01$ and $A=0, BC=11$). Here, $A=0$ is constant, $B$ changes, $C=1$ is constant. Term: $\overline{A}C$.
- Group 2: Minterms 3 and 7 (cells $A=0, BC=11$ and $A=1, BC=11$). Here, $A$ changes, $B=1$ is constant, $C=1$ is constant. Term: $BC$.
- Group 3: Minterms 6 and 7 (cells $A=1, BC=10$ and $A=1, BC=11$). Here, $A=1$ is constant, $B=1$ is constant, $C$ changes. Term: $AB$.
The simplified SOP expression is $F = \overline{A}C + BC + AB$.
Combinational Circuits
Combinational circuits are digital circuits for which the output at any time depends only on the current input values. They do not have memory elements; they cannot store past states. Examples include logic gates, adders, subtractors, multiplexers, decoders, and encoders.
1. Adders
Adders are combinational circuits that perform the arithmetic addition of binary numbers.
- Half Adder: Adds two single binary digits. It has two inputs (A, B) and two outputs: Sum (S) and Carry (C).
- $S = A \oplus B$
- $C = A \cdot B$
- Full Adder: Adds three single binary digits (two input bits and a carry-in bit). It has three inputs (A, B, Carry-In) and two outputs: Sum (S) and Carry-Out (Cout). A full adder can be constructed using two half adders and an OR gate.
- $S = A \oplus B \oplus C_{in}$
- $C_{out} = (A \cdot B) + (A \cdot C_{in}) + (B \cdot C_{in})$ or $C_{out} = (A \cdot B) + C_{in}(A \oplus B)$
Multiple full adders can be cascaded to form ripple-carry adders for adding multi-bit numbers.
2. Subtractors
Subtractors perform binary subtraction. Similar to adders, they can be half subtractors and full subtractors. Subtraction can be implemented using addition with the help of 2's complement.
3. Multiplexers (MUX)
A multiplexer is a combinational circuit that selects one of several input signals and forwards it to a single output line. It has $2^n$ data inputs, $n$ select lines, and one output. The select lines determine which input is connected to the output.
A 2-to-1 MUX has 2 data inputs ($I_0, I_1$), 1 select line (S), and 1 output (Y).
- If $S=0$, $Y = I_0$.
- If $S=1$, $Y = I_1$.
A 4-to-1 MUX has 4 data inputs ($I_0, I_1, I_2, I_3$), 2 select lines ($S_1, S_0$), and 1 output (Y).
- If $S_1S_0=00$, $Y = I_0$.
- If $S_1S_0=01$, $Y = I_1$.
- If $S_1S_0=10$, $Y = I_2$.
- If $S_1S_0=11$, $Y = I_3$.
4. Demultiplexers (DEMUX)
A demultiplexer performs the reverse operation of a multiplexer. It takes a single input line and routes it to one of several output lines. It has one data input, $n$ select lines, and $2^n$ output lines. The select lines determine which output line receives the input data.
A 1-to-2 DEMUX has 1 data input (D), 1 select line (S), and 2 outputs ($Y_0, Y_1$).
- If $S=0$, $Y_0 = D$, $Y_1 = 0$.
- If $S=1$, $Y_0 = 0$, $Y_1 = D$.
5. Decoders
A decoder is a combinational circuit that converts coded input into a specified coded output. The most common type is a binary decoder, which converts a $n$-bit binary input into $2^n$ unique outputs. Only one output line is active (high) for each unique input combination.
A 2-to-4 decoder has 2 inputs ($A, B$) and 4 outputs ($D_0, D_1, D_2, D_3$).
- If $AB=00$, $D_0=1$, others are 0.
- If $AB=01$, $D_1=1$, others are 0.
- If $AB=10$, $D_2=1$, others are 0.
- If $AB=11$, $D_3=1$, others are 0.
Decoders are used in memory addressing, instruction decoding, and code conversion.
6. Encoders
An encoder performs the reverse function of a decoder. It takes $2^n$ input lines and produces an $n$-bit binary output code. Only one input line is active at a time.
An Octal-to-Binary Encoder (8-to-3) has 8 input lines ($D_0$ to $D_7$) and 3 output lines ($A_2, A_1, A_0$). If input $D_i$ is active, the output represents the binary code for $i$.
- $A_0 = D_1 + D_3 + D_5 + D_7$
- $A_1 = D_2 + D_3 + D_6 + D_7$
- $A_2 = D_4 + D_5 + D_6 + D_7$
Sequential Circuits
Sequential circuits are digital circuits whose output depends not only on the present input but also on the past sequence of inputs. This is achieved by using memory elements, which store the state of the circuit. Sequential circuits are the basis for memory and state machines. They are classified into two types: synchronous and asynchronous.
1. Flip-Flops
Flip-flops are the fundamental memory elements in sequential circuits. They are bistable multivibrators, meaning they have two stable states and can store one bit of information. They change their state based on clock signals and input data.
- SR Flip-Flop: Has two inputs, Set (S) and Reset (R), and two outputs (Q and $\overline{Q}$).
- If $S=1, R=0$, the flip-flop is set to state 1 ($Q=1$).
- If $S=0, R=1$, the flip-flop is reset to state 0 ($Q=0$).
- If $S=0, R=0$, the state remains unchanged (hold state).
- If $S=1, R=1$, this is an invalid or forbidden state, leading to an unpredictable output.
- D Flip-Flop (Data or Delay Flip-Flop): Has one data input (D) and a clock input (CLK). The output Q takes the value of D when the clock edge occurs. It effectively stores the input value.
- On the active clock edge, $Q_{next} = D$.
- JK Flip-Flop: Has two inputs, J and K, and a clock input. It is a more versatile version of the SR flip-flop.
- If $J=0, K=0$, the flip-flop holds its state.
- If $J=1, K=0$, the flip-flop is set ($Q_{next}=1$).
- If $J=0, K=1$, the flip-flop is reset ($Q_{next}=0$).
- If $J=1, K=1$, the flip-flop toggles its state (changes to the opposite of its current state).
- T Flip-Flop (Toggle Flip-Flop): Has one input T and a clock input. If $T=0$, the flip-flop holds its state. If $T=1$, the flip-flop toggles its state. It can be derived from a JK flip-flop by connecting J and K together ($J=K=T$).
- $Q_{next} = T \oplus Q$.
Flip-flops can be edge-triggered (changing state on the rising or falling edge of the clock pulse) or level-triggered (changing state when the clock level is high or low). Edge-triggered flip-flops are more common in modern designs to avoid timing issues.
2. Registers
A register is a group of flip-flops used to store a binary word. A register consisting of $n$ flip-flops can store an $n$-bit word. Registers are used to hold data temporarily within a digital system, such as in the CPU for holding instructions or data being processed.
- SISO (Serial-In, Serial-Out) Register: Data is shifted in one bit at a time and shifted out one bit at a time.
- SIPO (Serial-In, Parallel-Out) Register: Data is shifted in serially, but all bits can be read out in parallel. This is useful for converting serial data to parallel data.
- PISO (Parallel-In, Serial-Out) Register: Data is loaded in parallel into the flip-flops, and then shifted out serially.
- PIPO (Parallel-In, Parallel-Out) Register: Data is loaded in parallel and can be read out in parallel. This is the simplest form of register.
- Shift Registers: Registers where data can be shifted from one flip-flop to another are called shift registers. They are commonly used for serial-to-parallel conversion, parallel-to-serial conversion, and arithmetic operations like multiplication and division by powers of 2.
For example, a 4-bit PIPO register using four D flip-flops would have each D input connected to a separate data line ($D_0, D_1, D_2, D_3$) and all clock inputs connected to a common clock signal. When the clock pulse arrives, the data present on the input lines is latched into the flip-flops.
3. Counters
Counters are sequential circuits that count the number of clock pulses applied to them. They are essentially registers whose contents increment or decrement in a predictable sequence. Counters are widely used for timing, frequency division, and sequencing operations.
- Asynchronous (Ripple) Counters: In these counters, the output of one flip-flop serves as the clock input for the next flip-flop. This creates a "ripple" effect as the changes propagate through the flip-flops. They are simpler to design but can be slower due to propagation delays.
- Synchronous Counters: In synchronous counters, all flip-flops are driven by a common clock signal. Logic gates are used to control the state transitions of each flip-flop based on the current count. They are faster and more reliable than ripple counters.
Counters can be designed to count up (incrementing), count down (decrementing), or count in a specific sequence (e.g., BCD counters, Johnson counters, Ring counters).
Example: A 3-bit synchronous up-counter using JK flip-flops. Let the flip-flops be $FF_2, FF_1, FF_0$, where $FF_0$ is the least significant bit. The state transitions depend on the current count. For an up-counter:
- $FF_0$ toggles on every clock pulse. So, $J_0=K_0=1$.
- $FF_1$ toggles only when $FF_0$ is 1. So, $J_1=K_1=Q_0$.
- $FF_2$ toggles only when both $FF_0$ and $FF_1$ are 1. So, $J_2=K_2=Q_0Q_1$.
Memory Unit
The memory unit is a crucial component of a computer system that stores data and instructions. It is essentially a large collection of storage cells, each capable of storing one bit of information. These cells are organized into words, and each word has a unique address.
Types of Memory
- RAM (Random Access Memory):
- SRAM (Static RAM): Uses flip-flops to store each bit. It is faster than DRAM but more expensive and less dense. It does not need to be refreshed.
- DRAM (Dynamic RAM): Uses capacitors to store each bit. Capacitors leak charge over time, so DRAM needs to be periodically refreshed. It is slower but cheaper, denser, and consumes less power per bit than SRAM.
- ROM (Read-Only Memory):
- PROM (Programmable ROM): Can be programmed once by the user.
- EPROM (Erasable Programmable ROM): Can be erased using ultraviolet light and reprogrammed.
- EEPROM (Electrically Erasable Programmable ROM): Can be erased and reprogrammed electrically, byte by byte.
- Flash Memory: A type of EEPROM that can be erased and programmed in blocks, making it faster for writing. It is non-volatile.
- Cache Memory: A small, very fast memory located between the CPU and main memory. It stores frequently accessed data and instructions to reduce access time. It is usually implemented using SRAM.
- Virtual Memory: A memory management technique that allows the system to use secondary storage (like a hard drive) as an extension of main memory when RAM is full.
Memory Organization
Memory is organized as a grid of cells, where each cell stores a bit. These cells are grouped into words. A $N \times M$ memory has $N$ locations, and each location stores $M$ bits. The address bus determines which location is accessed, and the data bus carries the data to or from that location.
For example, a memory with 16 address lines can access $2^{16} = 65,536$ locations. If each location stores 8 bits (1 byte), the total memory size is $65,536 \times 8$ bits, or 64 KB.
Memory Read and Write Operations
- Read Operation: The CPU places the address of the desired memory location on the address bus. It then asserts the read signal. The memory unit retrieves the data from that location and places it on the data bus for the CPU to read.
- Write Operation: The CPU places the address of the desired memory location on the address bus and the data to be written on the data bus. It then asserts the write signal. The memory unit stores the data from the data bus into the specified location.