Digital Logic Fundamentals: Arithmetic Operations and Boolean Algebra
This covers the core arithmetic operations in digital logic, which are fundamental to how computers process data.
1. Binary Arithmetic
Binary arithmetic uses only the digits 0 and 1. The key difference from decimal arithmetic is that a carry is generated when the sum reaches 2 (which is 10_2).
A. Binary Addition
| Rule | Description |
|—|—|
| 0 + 0 | 0 (Carry 0) |
| 0 + 1 | 1 (Carry 0) |
| 1 + 0 | 1 (Carry 0) |
| 1 + 1 | 0 (Carry 1 to the next position) |
| 1 + 1 + 1 | 1 (Carry 1 to the next position) |
B. Binary Subtraction
Standard binary subtraction follows the same borrowing rules as decimal subtraction, where borrowing from the next column adds 2 (or 10_2) to the current column.
C. Binary Multiplication
Binary multiplication is straightforward, consisting primarily of shifted binary additions.
* If the multiplier bit is 1, copy the multiplicand.
* If the multiplier bit is 0, write a row of zeros.
* Shift each successive line one position to the left.
* Add all the partial products.
D. Binary Division
Binary division is performed using a process similar to decimal long division:
* Compare the divisor with the partial dividend.
* If the divisor is smaller than or equal to the partial dividend, write 1 in the quotient and subtract the divisor from the partial dividend.
* If the divisor is larger, write 0 in the quotient and bring down the next bit.
* Repeat until all bits of the dividend are used.
2. Binary Subtraction using Complements
To simplify hardware design, subtraction (A – B) is converted into an addition problem (A + (-B)) using the complement of the subtrahend (B).
A. Using 1’s Complement
* Find the 1’s complement of the subtrahend (B).
* Add the minuend (A) and the 1’s complement of B.
* Check the carry-out (end-around carry):
* If a carry-out of 1 is generated, add this carry back to the least significant bit (LSB) of the result. The result is positive.
* If no carry-out is generated, the result is negative. Take the 1’s complement of the sum to get the magnitude and prepend a negative sign.
B. Using 2’s Complement (Standard Method)
* Find the 2’s complement of the subtrahend (B).
* Add the minuend (A) and the 2’s complement of B.
* Check the carry-out:
* If a carry-out of 1 is generated, discard it. The remaining result is the final, positive answer.
* If no carry-out is generated, the result is negative. Take the 2’s complement of the sum to get the magnitude and prepend a negative sign.
3. Arithmetic with BCD Representation (Binary-Coded Decimal)
BCD represents each decimal digit (0-9) using a 4-bit binary code (e.G., 45_{10} = 0100\ 0101_{\text{BCD}}).
A. BCD Addition
The process must ensure that the final result in each 4-bit group remains a valid BCD digit (0-9).
* Add the BCD numbers using standard binary addition, group by group (4 bits at a time).
* Apply Correction (if necessary): If the sum of any 4-bit group is:
* Greater than 9 (i.E., 1010_2 through 1111_2): Add 6 (0110_2) to that 4-bit group to skip the 6 invalid BCD codes and generate the correct carry to the next digit.
* A carry-out of 1 is generated from that 4-bit group: Add 6 (0110_2) to the group to correct the sum.
* Propagate any generated carry to the next 4-bit group.
B. BCD Subtraction
BCD subtraction is usually performed using the 9’s complement or 10’s complement of the subtrahend to convert it into an addition problem, similar to how 1’s and 2’s complement work for binary.
* 9’s Complement Method:
* Find the 9’s complement of the subtrahend (by subtracting each BCD digit from 9).
* Add the minuend and the 9’s complement.
* Perform an end-around carry (add the final carry-out back to the LSB group).
* 10’s Complement Method:
* Find the 10’s complement of the subtrahend (9’s complement + 1).
* Add the minuend and the 10’s complement.
* Discard the final carry-out.
This is a comprehensive overview of Boolean Algebra, the mathematical foundation of all digital logic and computer science.
1. Boolean Algebra Postulates and Basic Theorems
Boolean algebra operates on binary variables (which can only be 0 or 1) and defines three basic logical operations: AND (\cdot)
, OR (+), and NOT (‘ or \bar{}).
A. Boolean Postulates (Axioms)
These are the fundamental rules that define the algebraic system:
| Postulate | AND (\cdot) | OR (+) |
|—|—|—|
| Closure | X \cdot Y is in \{0, 1\} | X + Y is in \{0, 1\} |
| Identity | X \cdot 1 = X | X + 0 = X |
| Commutative | X \cdot Y = Y \cdot X | X + Y = Y + X |
| Distributive | X \cdot (Y + Z) = X \cdot Y + X \cdot Z | X + (Y \cdot Z) = (X + Y) \cdot (X + Z) |
| Complement | X \cdot X’ = 0 | X + X’ = 1 |
B. Basic Boolean Theorems
These theorems are derived from the postulates and are crucial for simplifying expressions.
| Theorem | AND Form | OR Form |
|—|—|—|
| Idempotence | X \cdot X = X | X + X = X |
| Null Elements | X \cdot 0 = 0 | X + 1 = 1 |
| Involution | (X’)’ = X | |
| Absorption | X \cdot (X + Y) = X | X + (X \cdot Y) = X |
| De Morgan’s | (X \cdot Y)’ = X’ + Y’ | (X + Y)’ = X’ \cdot Y’ |
| Associative | X \cdot (Y \cdot Z) = (X \cdot Y) \cdot Z | X + (Y + Z) = (X + Y) + Z |
2. Boolean Expressions, Functions, and Truth Tables
* Boolean Expression: An algebraic expression formed by combining binary variables and constants (0, 1) using the Boolean operators. * Example: F = A \cdot B’ + C
* Boolean Function: An output variable defined by a Boolean expression. For n input variables, there are 2^{2^n} possible Boolean functions. * Truth Table: A tabular listing of all possible combinations of input variables and the resulting output value(s) of the function.
3. Canonical Representation of Boolean Expressions
Any Boolean function can be expressed in two standard, or “canonical,” forms.
A. Sum-of-Products (SOP) -* Definition: A sum of minterms. A minterm is an AND term that includes all input variables, where each variable is either complemented or uncomplemented.
* Property: A minterm evaluates to 1 for exactly one combination of the input variables.
* Notation: F(A, B, C) = \sum (m_i), where i is the decimal value corresponding to the input combination where F=1.
* Example: A’ B C + A B’ C’ + A B C is a SOP.
B. Product-of-Sums (POS)
* Definition: A product of maxterms. A maxterm is an OR term that includes all input variables, where each variable is either complemented or uncomplemented.
* Property: A maxterm evaluates to 0 for exactly one combination of the input variables.
* Notation: F(A, B, C) = \prod (M_i), where i is the decimal value corresponding to the input combination where F=0.
* Example: (A+B’+C) \cdot (A’+B+C’) \cdot (A’+B’+C’) is a POS.
4. Simplification using Boolean Postulates & Theorems
The goal of simplification is to reduce the number of literal terms and operators, resulting in a simpler, cheaper, and faster logic circuit.
* Example (Simplification using the Absorption theorem):
(Factoring using the Distributive Postulate)
(Using the Complement Postulate: X+X’=1)
(Using the Identity Postulate: X\cdot 1 = X)
5. Karnaugh Maps (K-Maps)
The K-Map is a graphical method for simplifying Boolean expressions by representing the truth table in a grid. It is an extremely efficient method for functions with up to four or five variables.
A. K-Map Procedure (Up to Four Variables)
* Map the Function: Place 1s in the cells corresponding to the minterms where the function output is 1. (Use a 2×2 for 2 variables, 2×4 or 4×2 for 3 variables, and 4×4 for 4 variables). The cells must be labeled using Gray Code (only one bit changes between adjacent cells).
* Group the 1s: Form the largest possible rectangular groups of 2^n (1, 2, 4, 8, 16) adjacent cells containing 1s. Adjacency includes wrapping around the edges (top/bottom, left/right).
* Derive the Product Terms: For each group, determine the product term (prime implicant) by identifying the variables that remain constant within the group (variables that change are eliminated).
* Form the Sum-of-Products: Sum all the derived product terms.
B. Handling Don’t Care Conditions (d or X)
* Definition: A Don’t Care condition occurs when the input combination will logically never happen, or when the system output for that combination is irrelevant.
* In K-Maps: Don’t Care conditions are marked with an ‘X’ or ‘d’ in the corresponding cell.
* Usage: Treat the Don’t Care cells as either a 0 or a 1 to create the largest possible groups of 1s. If an ‘X’ is not needed to make a larger group, treat it as a 0. This maximizes simplification.