Number Systems and Codes

In the world of digital electronics, information is represented using numbers and codes. Unlike our everyday decimal system, digital systems primarily use binary (base-2) due to the on/off states of electronic components. Understanding different number systems and codes is fundamental to comprehending how digital circuits process and store data. This section will explore the common number systems, various coding schemes, and the basic building blocks of digital logic: logic gates.

Decimal System (Base-10)

The decimal system is the number system we use daily. It is a positional numeral system with a base of 10. This means it uses ten distinct digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Each digit's position in a number represents a power of 10, starting from 10⁰ (the rightmost digit).

For example, the decimal number 573 can be broken down as follows:

573 = (5 × 10²) + (7 × 10¹) + (3 × 10⁰) 573 = (5 × 100) + (7 × 10) + (3 × 1) 573 = 500 + 70 + 3

Binary System (Base-2)

The binary system is the most important number system in digital electronics. It is a positional numeral system with a base of 2. It uses only two digits: 0 and 1. These digits are called bits (binary digits). The position of each bit represents a power of 2, starting from 2⁰ on the right.

Let's convert the binary number 10110 to its decimal equivalent:

10110₂ = (1 × 2⁴) + (0 × 2³) + (1 × 2²) + (1 × 2¹) + (0 × 2⁰) 10110₂ = (1 × 16) + (0 × 8) + (1 × 4) + (1 × 2) + (0 × 1) 10110₂ = 16 + 0 + 4 + 2 + 0 10110₂ = 22₁₀

Conversely, to convert a decimal number to binary, we use repeated division by 2 and record the remainders.

Example: Convert decimal 25 to binary.

1. 25 ÷ 2 = 12 remainder 1
2. 12 ÷ 2 = 6 remainder 0
3. 6 ÷ 2 = 3 remainder 0
4. 3 ÷ 2 = 1 remainder 1
5. 1 ÷ 2 = 0 remainder 1

Reading the remainders from bottom to top, we get 11001₂. So, 25₁₀ = 11001₂.

Octal System (Base-8)

The octal system is a positional numeral system with a base of 8. It uses eight digits: 0, 1, 2, 3, 4, 5, 6, and 7. Each position represents a power of 8. The octal system is often used as a shorthand for binary because each octal digit can represent exactly three binary digits (bits).

Conversion from octal to decimal:

Convert 345₈ to decimal:

345₈ = (3 × 8²) + (4 × 8¹) + (5 × 8⁰) 345₈ = (3 × 64) + (4 × 8) + (5 × 1) 345₈ = 192 + 32 + 5 345₈ = 229₁₀

Conversion from decimal to octal uses repeated division by 8.

Example: Convert decimal 150 to octal.

1. 150 ÷ 8 = 18 remainder 6
2. 18 ÷ 8 = 2 remainder 2
3. 2 ÷ 8 = 0 remainder 2

Reading remainders from bottom to top: 226₈. So, 150₁₀ = 226₈.

Octal to Binary Conversion: Group binary bits into threes from the right.

Example: Convert 345₈ to binary.

3₈ = 011₂ 4₈ = 100₂ 5₈ = 101₂

So, 345₈ = 011 100 101₂ = 11100101₂.

Binary to Octal Conversion: Group binary bits into threes from the right.

Example: Convert 1101101₂ to octal.

Group from the right: 1 101 101 Pad the leftmost group with zeros: 001 101 101

001₂ = 1₈ 101₂ = 5₈ 101₂ = 5₈

So, 1101101₂ = 155₈.

Hexadecimal System (Base-16)

The hexadecimal system is a positional numeral system with a base of 16. It uses sixteen distinct symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. The letters A through F represent the decimal values 10 through 15, respectively. Each position represents a power of 16. Hexadecimal is widely used in computing as a more compact representation of binary data, as each hex digit corresponds to exactly four binary digits (bits).

Hexadecimal to Decimal Conversion:

Convert A3F₁₆ to decimal:

A3F₁₆ = (A × 16²) + (3 × 16¹) + (F × 16⁰) A3F₁₆ = (10 × 256) + (3 × 16) + (15 × 1) A3F₁₆ = 2560 + 48 + 15 A3F₁₆ = 2623₁₀

Decimal to Hexadecimal Conversion: Uses repeated division by 16.

Example: Convert decimal 400 to hexadecimal.

1. 400 ÷ 16 = 25 remainder 0
2. 25 ÷ 16 = 1 remainder 9
3. 1 ÷ 16 = 0 remainder 1

Reading remainders from bottom to top: 190₁₆. So, 400₁₀ = 190₁₆.

Hexadecimal to Binary Conversion: Group binary bits into fours from the right.

Example: Convert 1A5₁₆ to binary.

1₁₆ = 0001₂ A₁₆ = 1010₂ 5₁₆ = 0101₂

So, 1A5₁₆ = 0001 1010 0101₂ = 110100101₂.

Binary to Hexadecimal Conversion: Group binary bits into fours from the right.

Example: Convert 111011001₂ to hexadecimal.

Group from the right: 1 1101 1001 Pad the leftmost group with zeros: 0001 1101 1001

0001₂ = 1₁₆ 1101₂ = D₁₆ 1001₂ = 9₁₆

So, 111011001₂ = 1D9₁₆.

Binary Coded Decimal (BCD)

8421 Code

The 8421 code is the most common form of Binary Coded Decimal (BCD). In this code, each decimal digit (0-9) is represented by its equivalent 4-bit binary number. The weights of the bits are 8, 4, 2, and 1, corresponding to their positional values.

For example:

Decimal Digit	8421 BCD Code
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001

Note that the BCD codes for 10 through 15 (1010 to 1111) are "invalid" in the 8421 BCD system, as they do not represent any single decimal digit. This is a key characteristic of BCD – it only encodes decimal digits 0-9.

To represent a decimal number like 159 in 8421 BCD, we convert each digit individually:

1 → 0001 5 → 0101 9 → 1001

So, 159₁₀ in 8421 BCD is 0001 0101 1001.

Excess-3 Code

The Excess-3 code is another type of BCD code, but it is "unweighted" and "non-positional" in the same way as 8421. Each decimal digit is represented by a 4-bit binary number that is 3 more than the normal 8421 BCD code for that digit.

To get the Excess-3 code for a decimal digit, first find its 8421 BCD code, then add 3 (binary 0011) to it.

Decimal Digit	8421 BCD	+ 3 (0011)	Excess-3 Code
0	0000	+ 0011	0011
1	0001	+ 0011	0100
2	0010	+ 0011	0101
3	0011	+ 0011	0110
4	0100	+ 0011	0111
5	0101	+ 0011	1000
6	0110	+ 0011	1001
7	0111	+ 0011	1010
8	1000	+ 0011	1011
9	1001	+ 0011	1100

An advantage of Excess-3 code is that it is self-complementing. The 9's complement of a decimal digit can be obtained by simply inverting all the bits of its Excess-3 code. For example, the Excess-3 code for 2 is 0101. Inverting the bits gives 1010, which is the Excess-3 code for 7 (2+7=9). This property is useful in arithmetic operations.

To convert from Excess-3 to decimal, subtract 3 (binary 0011) from the 4-bit code. If the result is less than 0000, it's an invalid code.

Example: Convert Excess-3 code 1010 to decimal.

1010 - 0011 = 1010 + (invert 0011) + 1 = 1010 + 1100 + 1 = 1010 + 1101 = 10111. Using 4 bits: 0111. Alternatively, 1010 is 10 in decimal. 10 - 3 = 7. So, 1010_Excess-3 = 7₁₀.

Error Detecting and Correcting Codes

Gray Code

A Gray code is a binary numeral system where two successive values differ in only one bit position. This property is extremely useful in preventing errors in digital systems, especially in mechanical encoders or communication channels where a single bit flip can lead to a large numerical error. Unlike standard binary, where going from 011 (3) to 100 (4) changes three bits, Gray codes ensure only one bit changes.

Here's a comparison of 3-bit binary and Gray codes:

Decimal	3-Bit Binary	3-Bit Gray Code
0	000	000
1	001	001
2	010	011
3	011	010
4	100	110
5	101	111
6	110	101
7	111	100

Binary to Gray Code Conversion: The most significant bit (MSB) of the Gray code is the same as the MSB of the binary number. For subsequent bits, the Gray code bit is the XOR (Exclusive OR) of the corresponding binary bit and the binary bit to its left.

Example: Convert binary 1011 to Gray code.

Binary: 1 0 1 1 Gray MSB = Binary MSB = 1 Gray bit 2 = Binary bit 1 XOR Binary bit 2 = 1 XOR 0 = 1 Gray bit 3 = Binary bit 2 XOR Binary bit 3 = 0 XOR 1 = 1 Gray bit 4 = Binary bit 3 XOR Binary bit 4 = 1 XOR 1 = 0

So, Binary 1011₂ = Gray Code 1110.

Gray Code to Binary Conversion: The MSB of the binary number is the same as the MSB of the Gray code. For subsequent bits, the binary bit is the XOR of the corresponding Gray code bit and the previously calculated binary bit.

Example: Convert Gray code 1110 to binary.

Gray Code: 1 1 1 0 Binary MSB = Gray MSB = 1 Binary bit 2 = Gray bit 2 XOR Binary bit 1 = 1 XOR 1 = 0 Binary bit 3 = Gray bit 3 XOR Binary bit 2 = 1 XOR 0 = 1 Binary bit 4 = Gray bit 4 XOR Binary bit 3 = 0 XOR 1 = 1

So, Gray Code 1110 = Binary 1011₂.

Logic Gates

Logic gates are the fundamental building blocks of digital circuits. They 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 common logic gates are AND, OR, NOT, NAND, NOR, XOR, and XNOR.

Each gate has a unique symbol and a truth table that defines its output for all possible input combinations.

NOT Gate (Inverter)

The NOT gate has a single input and a single output. It performs the logical inversion operation. If the input is HIGH (1), the output is LOW (0), and vice versa.

• Symbol: A triangle with a small circle at the output.
• Boolean Expression: Y = ¯A (Y equals NOT A)
• Truth Table:

  Input A	Output Y
  0	1
  1	0

AND Gate

The AND gate has two or more inputs and one output. The output is HIGH (1) only if all inputs are HIGH (1). Otherwise, the output is LOW (0).

• Symbol: A D-shaped symbol.
• Boolean Expression: Y = A ⋅ B (Y equals A AND B)
• Truth Table (2 inputs):

  Input A	Input B	Output Y
  0	0	0
  0	1	0
  1	0	0
  1	1	1

OR Gate

The OR gate has two or more inputs and one output. The output is HIGH (1) if at least one of the inputs is HIGH (1). The output is LOW (0) only if all inputs are LOW (0).

• Symbol: A curved symbol that looks like a shield.
• Boolean Expression: Y = A + B (Y equals A OR B)
• Truth Table (2 inputs):

  Input A	Input B	Output Y
  0	0	0
  0	1	1
  1	0	1
  1	1	1

NAND Gate

The NAND gate is a combination of an AND gate and a NOT gate. Its output is LOW (0) only if all inputs are HIGH (1). Otherwise, the output is HIGH (1). It's often called a "universal gate" because it can be used to construct any other logic gate.

• Symbol: An AND gate symbol with a small circle at the output.
• Boolean Expression: Y = ¯(A ⋅ B)
• Truth Table (2 inputs):

  Input A	Input B	Output Y
  0	0	1
  0	1	1
  1	0	1
  1	1	0

NOR Gate

The NOR gate is a combination of an OR gate and a NOT gate. Its output is HIGH (1) only if all inputs are LOW (0). Otherwise, the output is LOW (0). It is also a universal gate.

• Symbol: An OR gate symbol with a small circle at the output.
• Boolean Expression: Y = ¯(A + B)
• Truth Table (2 inputs):

  Input A	Input B	Output Y
  0	0	1
  0	1	0
  1	0	0
  1	1	0

XOR Gate (Exclusive OR)

The XOR gate has two or more inputs and one output. The output is HIGH (1) if an odd number of inputs are HIGH (1). In simpler terms for two inputs, the output is 1 if the inputs are different, and 0 if they are the same.

• Symbol: An OR gate symbol with an extra curved line at the input.
• Boolean Expression: Y = A ⊕ B (Y equals A XOR B)
• Truth Table (2 inputs):

  Input A	Input B	Output Y
  0	0	0
  0	1	1
  1	0	1
  1	1	0

XOR gates are useful for parity checking and binary addition.

XNOR Gate (Exclusive NOR)

The XNOR gate is the inverse of the XOR gate. The output is HIGH (1) if an even number of inputs are HIGH (1). For two inputs, the output is 1 if the inputs are the same, and 0 if they are different.

• Symbol: An XOR gate symbol with a small circle at the output.
• Boolean Expression: Y = ¯(A ⊕ B)
• Truth Table (2 inputs):

  Input A	Input B	Output Y
  0	0	1
  0	1	0
  1	0	0
  1	1	1

Laws of Boolean Algebra

Boolean algebra is the mathematical foundation for digital logic. It uses variables that can have only two possible values (0 or 1) and operates with logical operators like AND, OR, and NOT. The laws of Boolean algebra provide rules for simplifying and manipulating logical expressions.

Basic Laws

1. Identity Law:
   • A ⋅ 1 = A
   • A + 0 = A

   Multiplying any variable by 1 leaves it unchanged. Adding any variable to 0 leaves it unchanged.

2. Null Law (or Complement Law):
   • A ⋅ 0 = 0
   • A + 1 = 1

   Multiplying any variable by 0 results in 0. Adding any variable to 1 results in 1.

3. Idempotent Law:
   • A ⋅ A = A
   • A + A = A

   A variable ANDed with itself is itself. A variable ORed with itself is itself.

4. Complement Law:
   • A ⋅ ¯A = 0
   • A + ¯A = 1

   A variable ANDed with its complement is always 0. A variable ORed with its complement is always 1.

5. Double Negation Law:
   • ¯(¯A) = A

   The negation of a negation is the original variable.

Commutative Laws

The order of operands does not affect the result.

• A ⋅ B = B ⋅ A
• A + B = B + A

Associative Laws

The grouping of operands does not affect the result.

• (A ⋅ B) ⋅ C = A ⋅ (B ⋅ C)
• (A + B) + C = A + (B + C)

Distributive Laws

Similar to arithmetic, one operation distributes over another.

• A ⋅ (B + C) = (A ⋅ B) + (A ⋅ C)
• A + (B ⋅ C) = (A + B) ⋅ (A + C) (This one is less intuitive but crucial)

Absorption Laws

These laws simplify expressions involving AND and OR operations.

• A + (A ⋅ B) = A
• A ⋅ (A + B) = A

De Morgan's Theorems

These are very important for simplifying expressions involving inversions, especially for converting between AND/OR and NAND/NOR gates.

• ¯(A ⋅ B) = ¯A + ¯B (The complement of a product is the sum of the complements)
• ¯(A + B) = ¯A ⋅ ¯B (The complement of a sum is the product of the complements)

These theorems can be extended to more than two variables.

Combinational Circuits: Adders and Subtractors

Combinational circuits are digital circuits whose output depends only on the current input values. They do not have memory elements like flip-flops. Adders and subtractors are fundamental combinational circuits used for arithmetic operations in computers.

Half Adder

A half adder is a circuit that adds two single binary digits and produces a sum bit and a carry bit. It can only add two bits at a time and cannot handle a carry-in from a previous stage.

Inputs: A, B (the two bits to be added) Outputs: Sum (S), Carry (C)

Let's look at the truth table:

Input A	Input B	Sum (S)	Carry (C)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

From the truth table: Sum (S) = A ⊕ B (A XOR B) Carry (C) = A ⋅ B (A AND B)

Therefore, a half adder can be implemented using one XOR gate and one AND gate.

Full Adder

A full adder is a circuit that adds three single binary digits: two input bits (A and B) and a carry-in bit (C_in) from a previous stage. It produces a sum bit (S) and a carry-out bit (C_out). Full adders are used to build multi-bit adders.

Inputs: A, B, C_in Outputs: Sum (S), Carry-out (C_out)

Truth Table for a Full Adder:

Input A	Input B	Carry In (Cin)	Sum (S)	Carry Out (Cout)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

From the truth table, we can derive the Boolean expressions: Sum (S) = A ⊕ B ⊕ C_in Carry Out (C_out) = (A ⋅ B) + (C_in ⋅ (A ⊕ B)) Alternatively, C_out = (A ⋅ B) + (A ⋅ C_in) + (B ⋅ C_in)

A full adder can be constructed using two half adders and an OR gate. The first half adder adds A and B, producing S1 and C1. The second half adder adds S1 and C_in, producing the final Sum (S) and a carry C2. The final Carry-out (C_out) is the OR of C1 and C2.

Example: Adding 1011₂ and 0110₂ We use a 4-bit ripple-carry adder, where each bit position uses a full adder, and the carry-out of one stage becomes the carry-in of the next. Let A = 1011, B = 0110. C_in for the first stage is 0. Stage 1 (LSB): A=1, B=0, C_in=0. S=1, C_out=0. Stage 2: A=1, B=1, C_in=0 (from stage 1). S=0, C_out=1. Stage 3: A=0, B=1, C_in=1 (from stage 2). S=0, C_out=1. Stage 4 (MSB): A=1, B=0, C_in=1 (from stage 3). S=0, C_out=1. Result: Sum = 0001, Carry-out = 1. The final answer is 10001₂.

Half Subtractor

A half subtractor is a circuit that subtracts one binary digit from another and produces a difference bit and a borrow bit.

Inputs: A (minuend), B (subtrahend) Outputs: Difference (D), Borrow (Br)

Truth Table:

Input A	Input B	Difference (D)	Borrow (Br)
0	0	0	0
0	1	1	1
1	0	1	0
1	1	0	0

From the truth table: Difference (D) = A ⊕ B (A XOR B) Borrow (Br) = ¯A ⋅ B

Note that the difference output is the same as the sum output of a half adder. The borrow logic is different. A borrow is generated when A=0 and B=1.

Full Subtractor

A full subtractor is a circuit that subtracts three single binary digits: two input bits (A and B) and a borrow-in bit (Br_in) from a previous stage. It produces a difference bit (D) and a borrow-out bit (Br_out).

Inputs: A, B, Br_in Outputs: Difference (D), Borrow-out (Br_out)

Truth Table for a Full Subtractor:

Input A	Input B	Borrow In (Brin)	Difference (D)	Borrow Out (Brout)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Boolean Expressions: Difference (D) = A ⊕ B ⊕ Br_in Borrow Out (Br_out) = (¯A ⋅ B) + (Br_in ⋅ (¯A ⊕ B)) Alternatively, Br_out = (¯A ⋅ B) + (¯A ⋅ Br_in) + (B ⋅ Br_in)

Similar to full adders, full subtractors can be built using half subtractors. A full subtractor can be implemented using two half subtractors and an OR gate.

Subtraction using Two's Complement: A common method to perform subtraction in digital systems is by using the two's complement of the subtrahend and then adding it to the minuend. For example, to compute A - B, we compute A + (2's complement of B). The 2's complement of B is found by inverting all bits of B (1's complement) and then adding 1. Example: 1011₂ - 0110₂ A = 1011 B = 0110 1's complement of B = 1001 2's complement of B = 1001 + 1 = 1010 Now, add A and 2's complement of B: 1011 + 1010 = 10101₂ If there is a carry-out, the result is positive. The carry-out is discarded, and the result is 0101₂. This method is preferred in digital systems as it uses the same adder circuitry for both addition and subtraction.