02 Chapter 2 - Digital Codes & Error Detection (Merged)

Chapter 2: Digital Codes & Error Detection - Complete Study Notes

NotebookLM Ingestion Compilation

This merged document contains all 4 study notes for Chapter 2: Digital Codes & Error Detection from ECE 2103 Digital Electronics (Sharif Sir).

---

2.01 BCD & Weighted Digital Codes

What is a Digital Code?

A Digital Code is a system of rules that assigns a unique pattern of binary bits (0s and 1s) to represent numbers, letters, symbols, or control commands.

Unlike pure binary number systems used for arithmetic, binary codes are engineered for specialized digital tasks such as decimal displays, error detection, data transmission, and mechanical position sensing.

graph TD
    Codes[Binary Digital Codes] --> Weighted[Weighted Positional Codes]
    Codes --> NonWeighted[Non-Weighted Codes]
    
    Weighted --> BCD8421[BCD / 8421 Code]
    Weighted --> W2421[2421 Self-Comp Code]
    Weighted --> W5211[5211 Code]
    Weighted --> W8421N[84-2-1 Negative Weight Code]
    
    NonWeighted --> XS3[Excess-3 Self-Comp Code]
    NonWeighted --> Gray[Gray Code / Single-Bit Change]
    NonWeighted --> ErrorCtrl[Parity / Error Control Codes]

---

1. What is BCD (Binary Coded Decimal)?

Concept: BCD Definition

Binary Coded Decimal (BCD) is a class of binary encodings where each decimal digit of a number is represented by a fixed number of bits (usually four).

In standard 8421 BCD, each decimal digit (0 through 9) is directly replaced by its equivalent 4-bit binary nibble.

• Decimal: $185_{10}$
• BCD: $\underset{1}{\underbrace{0001}}\underset{8}{\underbrace{1000}}\underset{5}{\underbrace{0101}}⟹(000110000101{)}_{\text{BCD}}$

Why do we use BCD?

1. Decimal Display Drivers: Devices like calculators and digital clocks use 7-segment displays. Directly mapping 4-bit BCD nibbles to display segment controllers is much simpler than converting a pure binary number into decimal components.
2. Financial Precision: In binary floating-point representations, decimal fractions like $0.1$ cannot be represented exactly (leading to rounding errors: $0.1+0.2\ne 0.3$). BCD represents each decimal digit exactly, preventing precision loss in financial transactions.

---

2. BCD Addition Mechanics

Because a 4-bit binary group can represent 16 states ($0$ to $15$), but BCD only permits 10 states ($0$ to $9$), standard binary addition can yield invalid states.

The BCD Addition Rule:

1. Add the two BCD digits using standard binary addition.
2. Check the sum of each 4-bit nibble:
   • Case A: Sum $\le 9$ and no carry generated $⟹$ The sum is a valid BCD digit.
   • Case B: Sum $>9$ OR an intermediate carry is generated $⟹$ The sum is invalid. Add $6_{10}=0110_2$ to that nibble to skip the 6 invalid states, and add the resulting carry to the next higher-order nibble.

Step-by-Step Addition Examples:

Example 1: BCD Addition with Sum $\le 9$ (Valid)

Add $4$ and $3$:

4_{10} \to & 0100 & (\text{BCD}) \\ +3_{10} \to & 0011 & (\text{BCD}) \\ \hline & 0111 & (\text{Binary Sum} = 7_{10} \le 9) \end{array}$$ Since the sum is $\le 9$ and no carry was generated, the result is valid: **$0111_{\text{BCD}} = 7_{10}$**.

Example 2: BCD Addition with Sum $>9$ (Correction Needed)

Add $6$ and $7$:

6_{10} \to & 0110 & (\text{BCD}) \\ +7_{10} \to & 0111 & (\text{BCD}) \\ \hline \text{Binary Sum} \to & 1101 & (\text{Equal to } 13_{10} > 9 \implies \text{Invalid}) \\ \text{Add } 6 \to & +0110 & (\text{Correction Factor}) \\ \hline \text{Result} \to & \mathbf{1 \ 0011} & (\text{Carry generated to next nibble}) \end{array}$$ Expressed as 4-bit groups: $\mathbf{0001\ 0011_{\text{BCD}}} = 13_{10}$.

---

3. Distinction Between a Number System and a Code

Major Exam Theory Question (2018 - 4 Marks)

Question: Explain the fundamental differences between a Number System and a Code.

Aspect	Binary Number System	Binary Code
Fundamental Purpose	Designed for mathematical computation and quantitative representation.	Designed for human interface, data transmission, and hardware control.
Bit Position Weighting	Bit positions follow strict powers of 2 ($2^n,\dots ,2^2,2^1,2^0$).	Bit positions may have non-standard weights ($5,2,1,1$) or no weights at all.
Arithmetic Suitability	Directly supports standard addition, subtraction, and multiplication.	Unsuitable for direct arithmetic without specialized hardware conversion.
Bit Efficiency	Highly efficient; utilizes all $2^n$ binary combinations continuously.	Contains invalid/unused states {e.g., BCD skips 6 states out of 16}.
Representation Example	$12_{10}=1100_2$	$12_{10}=00010010_{\text{BCD}}$

---

4. Weighted Positional Codes

A digital code is classified as Weighted if each bit position in a 4-bit group is assigned a fixed numerical weight ($w_3,w_2,w_1,w_0$). The represented decimal digit $D$ is calculated as: $D=(d_3\cdot w_3)+(d_2\cdot w_2)+(d_1\cdot w_1)+(d_0\cdot w_0)$

Comparison Table of Major 4-Bit Weighted Codes:

Decimal Digit	8421 (Standard BCD)	2421 Code	5211 Code	84-2-1 Code
0	0000	0000	0000	0000
1	0001	0001	0001	0111
2	0010	0010	0011	0110
3	0011	0011	0100	0101
4	0100	0100	0101	0100
5	0101	1011	1000	1011
6	0110	1100	1001	1010
7	0111	1101	1011	1001
8	1000	1110	1100	1000
9	1001	1111	1111	1111

Terminology & Concept Breakdown

• 8421 (BCD): The standard Binary Coded Decimal system. Uses standard binary weights for digits 0 to 9. States 1010 to 1111 ($10$ to $15$) are invalid.
• 2421 Code: A weighted self-complementing code where the sum of bit weights equals $9$.
• 5211 Code: A weighted code where the MSB carries a weight of $5$.
• 84-2-1 Code: A negative-weight code where the last two bits carry negative weights ($-2$ and $-1$).

4.2 Differences between Weighted and Non-Weighted Codes

Feature	Weighted Codes	Non-Weighted Codes
Bit Value Weighting	Each bit position is assigned a specific numerical weight ($w_i$).	Bits have no position weights; the value depends strictly on pattern rules.
Mathematical Evaluation	$D=\sum d_i{w}_i$.	Cannot be converted to decimal via standard sum of products.
Examples	8421 (BCD), 2421, 5211, 84-2-1.	Excess-3, Gray Code.
Arithmetic Logic	Simple arithmetic correction rules can be applied (e.g. $+6$ in BCD).	Complex arithmetic correction rules; Gray code is not suitable for direct addition.
Primary Applications	Display drivers, calculators, and ALU input interfaces.	Rotary encoders (Gray) and self-complementing math simplifications (Excess-3).

---

5. Alphanumeric Codes: The ASCII Standard

Foundational Concept (Outside Direct PYQ Scope)

Alphanumeric representation via standard ASCII is a foundational computer organization topic that is rarely tested directly as calculation problems in ECE 2103 examinations, but is required context for digital systems.

Digital computers must process text, punctuation, and control symbols in addition to numbers. Alphanumeric Codes assign binary codes to represent characters. The most popular standard is ASCII (American Standard Code for Information Interchange).

5.1 Standard ASCII (7-Bit Code)

• Bit Count: Dedicated 7-bit word format ($b_6{b}_5{b}_4{b}_3{b}_2{b}_1{b}_0$).
• State Space: Represents $2^7=128$ distinct characters (from decimal $0$ to $127$).
• Encoding Split:
  • Printable Characters ($32\dots 126$): Includes digits 0-9, letters a-z and A-Z, punctuation, and mathematical symbols.
  • Non-Printable Control Characters ($0\dots 31$ and $127$): Used for physical device control (e.g., Carriage Return CR, Line Feed LF, Backspace BS, Null NUL).

5.2 Extended ASCII (8-Bit Code)

• Bit Count: 8-bit word format.
• State Space: Represents $2^8=256$ characters. The upper 128 characters (decimal $128\dots 255$) represent special graphic characters, symbols, and foreign alphabet characters.

5.3 Hardware Storage & Parity Integration

In physical computer memory, data is organized in 8-bit bytes. Standard 7-bit ASCII characters are stored in 8-bit bytes by setting the most significant bit (MSB) to either:

• 0 (default padding).
• A Parity Bit (for simple error detection during transmission).

---

6. PYQ Numerical Solution: 5211 Code Conversion [PYQ 2018]

Major Exam Problem: Convert $(605{)}_{10}$ into 5211 Weighted Code (2018 - 8 Marks)

Solution:

To convert a multi-digit decimal number into 5211 code, convert each decimal digit independently into its corresponding 4-bit 5211 code group from the lookup table:

1. Digit 6: $5211⟹5(1)+2(0)+1(0)+1(1)=6⟹1001_2$
2. Digit 0: $5211⟹5(0)+2(0)+1(0)+1(0)=0⟹0000_2$
3. Digit 5: $5211⟹5(1)+2(0)+1(0)+1(0)=5⟹1000_2$

$\text{Final 5211 Code Result: }(100100001000{)}_{\text{5211}}■$

---

7. PYQ Master Puzzle: The 12-Bit Register Decoder [PYQ 2022]

PYQ Master Puzzle (2022): The 12-Bit Register Decoder

Question: The state of a 12-bit register is 100010010111. What is its content if it represents: (i) Three decimal digits in BCD? (ii) Three decimal digits in the excess-3 code? (iii) Three decimal digits in the 8-4-2-1 code? (iv) A binary number?

Solution Methodology: First, divide the 12-bit string into three 4-bit nibbles: 1000, 1001, 0111.

(i) As BCD (Standard 8421): Evaluate each 4-bit block directly into decimal.

• 1000 = 8
• 1001 = 9
• 0111 = 7
• Answer: 897

(ii) As Excess-3 Code: Excess-3 is generated by adding 3 (0011) to the decimal digit. To decode it, subtract 3 from each nibble.

• 1000 (8) - 3 = 5
• 1001 (9) - 3 = 6
• 0111 (7) - 3 = 4
• Answer: 564

(iii) As 8, 4, -2, -1 Code: Apply the specific mathematical weights to each bit in the nibble: $(8\times B_3)+(4\times B_2)-(2\times B_1)-(1\times B_0)$.

• 1000 $\to 8(1)+4(0)-2(0)-1(0)$ = 8
• 1001 $\to 8(1)+4(0)-2(0)-1(1)$ = 7
• 0111 $\to 8(0)+4(1)-2(1)-1(1)\to 4-2-1$ = 1
• Answer: 871

(iv) As a pure Binary Number: Evaluate the entire 12-bit string as a single base-2 integer.

• $100010010111_2=(1\times 2^{11})+(1\times 2^7)+(1\times 2^4)+(1\times 2^2)+(1\times 2^1)+(1\times 2^0)$
• $=2048+128+16+4+2+1$
• Answer: 2199 $■$

---

Past Year Questions (PYQs)

• [PYQ 2018]: Explain the difference between a Number System and a Code. (04 Marks)
• [PYQ 2018]: Convert decimal numbers into 5211 weighted code (e.g., $(605{)}_{10}$). (08 Marks)
• [PYQ 2019]: Conversions for BCD, 2421, 5211, and 84-2-1 codes. (08 Marks)
• [PYQ 2022]: 12-Bit Register Decoder puzzle (100010010111 in BCD, Excess-3, 8-4-2-1, Binary). (10 Marks)

---

Related Concepts: 01 BCD & Weighted Digital Codes | 03 Gray Code & Code Conversions | 04 Error Control, Parity Generators & Checkers

2.02 Excess-3 Code & Self-Complementing Logic

What is a Self-Complementing Code?

A 4-bit binary code is defined as Self-Complementing if the 1’s complement {bitwise inversion: $0\to 1,1\to 0$} of any decimal digit’s code word yields the exact code word of its 9’s decimal complement ($9-N$).

$\text{Code}(9-N)=\overline{\text{Code}(N)}$

graph LR
    subgraph Self-Complementing Symmetry
        D2[Decimal Digit 2: 0101] -->|Bitwise Inversion| InvD2[1's Comp: 1010]
        InvD2 -->|Equals| D7[Decimal Digit 7 = 9 - 2: 1010]
    end

---

---

1. What is Excess-3 Code?

[concept] Concept: Excess-3 Definition Excess-3 (XS-3) is a non-weighted binary code. Each decimal digit $N$ (0 through 9) is represented by the 4-bit binary value of $N+3$.

• Decimal: $4_{10}$
• Excess-3 representation: $4+3=7_{10}=0111_{\text{XS-3}}$

1.1 Differences: Standard BCD (8421) vs. Excess-3 (XS-3)

Feature	Standard BCD (8421)	Excess-3 (XS-3)
Weighting	Weighted positional code (weights: $8,4,2,1$).	Non-weighted code (each representation is $N+3$).
Self-Complementing	No (e.g. 1’s complement of BCD 1 [0001] is 1110, which is invalid, not BCD 8).	Yes (bitwise inversion of XS-3 $N$ yields XS-3 $(9-N)$).
Zero Representation	0000 (equal to electrical zero/disconnected state).	0011 (prevents false line fault detection).
Arithmetic Carry Rule	Add 0110 ($+6$) if sum $>9$ or carry is generated.	Add 0011 ($+3$) if carry is generated; subtract 0011 ($-3$) if no carry is generated.
Unused States	States 1010 to 1111 ($10\dots 15$) are invalid.	States 0000 to 0010 ($0\dots 2$) and 1101 to 1111 ($13\dots 15$) are invalid.

Why do we use Excess-3?

1. Simplified Subtraction (Self-Complementing): The primary advantage of Excess-3 is that the 1’s complement of an Excess-3 digit is the Excess-3 representation of its 9’s complement (e.g. 1’s complement of 0100 [1] is 1011 [8]). This makes subtraction circuits in early decimal calculators incredibly simple to design.
2. Transmission Reliability: Unlike standard BCD where $0$ is represented by 0000 (which is indistinguishable from a line disconnection or fault), the smallest valid Excess-3 code word is 0011 (decimal 0). This prevents signal transmission line faults from being misread as valid data.

---

2. Excess-3 Addition Mechanics

Because Excess-3 values always have an extra offset of $3$ built-in, adding two Excess-3 digits yields: $\text{Raw Sum}=(N_1+3)+(N_2+3)=(N_1+N_2)+6$

To restore the correct Excess-3 bias of $+3$:

• Case A: A carry is generated (Sum $>9$) $⟹$ Add 0011 ($+3$) to correct the sum nibble.
• Case B: No carry is generated (Sum $\le 9$) $⟹$ Subtract 0011 ($-3$) (or add 1101) to correct the sum nibble.

Step-by-Step Addition Examples:

Example 1: Excess-3 Addition with Sum $\le 9$ (No Carry)

Add $2$ and $3$ in Excess-3:

• $2_{\text{XS-3}}=0101$
• $3_{\text{XS-3}}=0110$

0101 & (2 + 3 = 5) \\ +0110 & (3 + 3 = 6) \\ \hline 1011 & (\text{Raw Binary Sum} = 11_{10} \to \text{No Carry}) \\ -0011 & (\text{No Carry} \implies \text{Subtract } 3) \\ \hline \mathbf{1000} & (\text{Corrected Sum} = 8_{10} \implies 5_{\text{decimal}} \text{ in XS-3}) \end{array}$$ **Final Answer:** **$1000_{\text{XS-3}}$** (corresponds to $5_{10}$).

Example 2: Excess-3 Addition with Sum $>9$ (Carry Generated)

Add $6$ and $5$ in Excess-3:

• $6_{\text{XS-3}}=1001$
• $5_{\text{XS-3}}=1000$

1001 & (6 + 3 = 9) \\ +1000 & (5 + 3 = 8) \\ \hline \mathbf{1} \ 0001 & (\text{Raw Binary Sum} \to \text{Carry generated!}) \\ +0011 & (\text{Carry generated} \implies \text{Add } 3 \text{ to sum nibble}) \\ \hline \mathbf{1} \ 0100 & (\text{Carry is pushed to next nibble}) \end{array}$$ Grouped into 4-bit nibbles: $\mathbf{0100\ 0100_{\text{XS-3}}}$ (corresponds to $11_{10}$ in decimal).

---

3. Mathematical Proof: Excess-3 is a Self-Complementing Code

Major Exam Proof (2021, 2023, 2025 - 8 to 10 Marks)

Question: Prove mathematically that Excess-3 (XS-3) code is a self-complementing code.

Step-by-Step Proof:

1. Definition of Excess-3 Code: The Excess-3 code word for any decimal digit $N$ ($0\le N\le 9$) is constructed by adding $3_{10}=0011_2$ to its standard 4-bit binary equivalent: $\text{XS-3}(N)=N+3$

2. Evaluating the 9’s Complement of $N$ ($9-N$): The Excess-3 code word for the 9’s complement of $N$ is: $\text{XS-3}(9-N)=(9-N)+3=12-N$

3. Evaluating the 1’s Complement of $\text{XS-3}(N)$: Taking the bitwise 1’s complement of a 4-bit number is mathematically equivalent to subtracting it from $15_{10}$ ($1111_2$): $\overline{\text{XS-3}(N)}=15-\text{XS-3}(N)$ Substituting $\text{XS-3}(N)=N+3$: $\overline{\text{XS-3}(N)}=15-(N+3)=15-N-3=12-N$

4. Comparing Results: $\text{XS-3}(9-N)=12-N$ $\overline{\text{XS-3}(N)}=12-N$ $\therefore \text{XS-3}(9-\mathbf{N})=\overline{\text{XS-3}(\mathbf{N})}■$

---

4. The Mathematics of Self-Complementing Weighted Codes

Unlike Excess-3 (which is non-weighted), many weighted 4-bit codes (like $2421$, $84\text{-}2\text{-}1$) are also self-complementing. There is a strict mathematical constraint on the weights of such codes.

The Self-Complementing Weight Theorem

For a weighted 4-bit binary code with weights $(w_3,w_2,w_1,w_0)$ to be self-complementing, the sum of its individual weights must equal exactly 9:

${\sum }_{i=0}^3{w}_i=w_3+w_2+w_1+w_0=9$

Algebraic Proof:

1. Let the code representation of a decimal digit $d$ be $B=b_3{b}_2{b}_1{b}_0$. Its value is: $d=w_3{b}_3+w_2{b}_2+w_1{b}_1+w_0{b}_0$
2. For the code to be self-complementing, the 9’s complement ($9-d$) must be represented by the bitwise inverted word $B^{\prime }=b_3^{\prime }{b}_2^{\prime }{b}_1^{\prime }{b}_0^{\prime }$: $9-d=w_3{b}_3^{\prime }+w_2{b}_2^{\prime }+w_1{b}_1^{\prime }+w_0{b}_0^{\prime }$
3. Add the two equations together: $d+(9-d)=w_3(b_3+b_3^{\prime })+w_2(b_2+b_2^{\prime })+w_1(b_1+b_1^{\prime })+w_0(b_0+b_0^{\prime })$
4. Since $b_i+b_i^{\prime }=1$ (as one bit is always 0 and the other is 1): $9=w_3(1)+w_2(1)+w_1(1)+w_0(1)$ $w_3+w_2+w_1+w_0=9■$

Verification of Common Codes:

• $2421$ Code: $2+4+2+1=9$ $⟹$ Self-complementing.
• $84\text{-}2\text{-}1$ Code: $8+4+(-2)+(-1)=9$ $⟹$ Self-complementing.
• $8421$ BCD Code: $8+4+2+1=15\ne 9$ $⟹$ Not self-complementing.

---

5. Complete 9’s Complement Symmetry Table

Decimal Digit ($N$)	BCD (8421)	Excess-3 Code ($\text{BCD}+3$)	1’s Comp of XS-3	9’s Comp Digit ($9-N$)	XS-3 Code of ($9-N$)
0	0000	0011	1100	9	1100
1	0001	0100	1011	8	1011
2	0010	0101	1010	7	1010
3	0011	0110	1001	6	1001
4	0100	0111	1000	5	1000
5	0101	1000	0111	4	0111
6	0110	1001	0110	3	0110
7	0111	1010	0101	2	0101
8	1000	1011	0100	1	0100
9	1001	1100	0011	0	0011

---

5. Design: BCD to Excess-3 Code Converter

Major Exam Design Problem (2018 - 10 Marks)

Question: Design a combinational logic circuit to convert a 4-bit BCD input ($A,B,C,D$) to a 4-bit Excess-3 code output ($W,X,Y,Z$).

Boolean Function Derivation (K-Map Simplification):

• Inputs: $A,B,C,D$ (Don’t care conditions $X=d(10,11,12,13,14,15)$).
• Outputs: $W,X,Y,Z$.

1. Output $Z$ (LSB): $Z={\mathbf{D}}^{\prime }$
2. Output $Y$: $Y=CD+C^{\prime }{D}^{\prime }=(\mathbf{C}\oplus \mathbf{D}{)}^{\prime }$
3. Output $X$: $X=B^{\prime }C+B^{\prime }D+B{C}^{\prime }{D}^{\prime }=\mathbf{B}\oplus (\mathbf{C}+\mathbf{D})$
4. Output $W$ (MSB): $W=A+BC+BD=\mathbf{A}+\mathbf{B}(\mathbf{C}+\mathbf{D})$

---

Past Year Questions (PYQs)

• [PYQ 2017, 2021, 2023, 2025]: Define self-complementary code. (04 Marks)
• [PYQ 2021, 2023, 2025]: Prove mathematically that Excess-3 code is a self-complementary code. (08-10 Marks)
• [PYQ 2018]: Design a BCD to Excess-3 code converter circuit. (10 Marks)

---

Related Concepts: 2.01 BCD & Weighted Digital Codes | 2.02 Excess-3 Code & Self-Complementing Logic | 2.04 Error Control, Parity Generators & Checkers

2.03 Gray Code & Code Conversions

What is Gray Code?

Gray Code (also called Reflected Binary Code) is an $N$-bit non-weighted binary coding system. Its defining property is that only one bit changes state (from 0 to 1 or 1 to 0) between any two consecutive values.

---

1. Physical Significance: Why Use Gray Code?

Standard binary numbers are ideal for math, but they cause severe glitches when interfacing with the physical world due to simultaneous multi-bit transitions:

A. Rotary Shaft Encoders (Position Sensing)

Optical sensors read angular position from coded disks:

• The Binary Problem: Transitioning from decimal 3 (011) to 4 (100) requires three bits to flip at once. Due to microscopic mechanical misalignments, the sensors will not trigger at the exact same instant. For a fraction of a millisecond, the processor might read an erroneous state like 111 (decimal 7) or 010 (decimal 2), leading to positioning errors.
• The Gray Code Solution: Transitioning from 3 (010 in Gray) to 4 (110 in Gray) flips only the MSB. The sensor is physically guaranteed to read either 3 or 4, with no intermediate erroneous states.

B. Low-Power VLSI Design

In high-speed integrated circuits, flipping bus lines charges/discharges parasitic capacitances, consuming dynamic power. By using Gray code, the average number of bit transitions (switching activity) is minimized, lowering power consumption.

---

2. 4-Bit Gray Code Lookup Table

Notice how the codes reflect. The second half is the mirror image of the first half (excluding the MSB).

Decimal Value	Standard Binary	Gray Code
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

---

3. Conversion Algorithms and Flows

Conversions between pure binary and Gray code are performed using the Exclusive-OR (XOR, $\oplus$) operator.

3.1 Binary-to-Gray Conversion

Binary-to-Gray Conversion Flow:
Binary:  B3 -------> B2 -------> B1 -------> B0
         |           |           |           |
         |           XOR         XOR         XOR
         v           v           v           v
Gray:    G3          G2          G1          G0

1. The MSB of the Gray code is identical to the MSB of the binary number: $G_{MSB}=B_{MSB}$
2. Each subsequent Gray bit is found by XORing the corresponding binary bit with the binary bit to its left: $G_i=B_i\oplus B_{i+1}(\text{for }i=N-2,\dots ,0)$

Binary-to-Gray Conversion: Convert Binary $1011$ to Gray

1. $G_3=B_3=1$
2. $G_2=B_3\oplus B_2=1\oplus 0=1$
3. $G_1=B_2\oplus B_1=0\oplus 1=1$
4. $G_0=B_1\oplus B_0=1\oplus 1=0$

Result: $1110_{\text{Gray}}$

---

3.2 Gray-to-Binary Conversion

Gray-to-Binary Conversion Flow:
Gray:    G3          G2          G1          G0
         |           ^           ^           ^
         |           |           |           |
         v           XOR         XOR         XOR
Binary:  B3 -------> B2 -------> B1 -------> B0

1. The MSB of the binary number is identical to the MSB of the Gray code: $B_{MSB}=G_{MSB}$
2. Each subsequent binary bit is found by XORing the previously calculated binary bit with the next Gray code bit: $B_i=B_{i+1}\oplus G_i(\text{for }i=N-2,\dots ,0)$

Gray-to-Binary Conversion: Convert Gray $1110$ to Binary

1. $B_3=G_3=1$
2. $B_2=B_3\oplus G_2=1\oplus 1=0$
3. $B_1=B_2\oplus G_1=0\oplus 1=1$
4. $B_0=B_1\oplus G_0=1\oplus 0=1$

Result: $1011_2$

---

4. Hardware Implementation

To design a combinational circuit that converts a 4-bit Gray code input ($G_3{G}_2{G}_1{G}_0$) to a 4-bit Binary output ($B_3{B}_2{B}_1{B}_0$), we map the Gray-to-Binary recurrence relations:

$B_3=G_3$ $B_2=G_3\oplus G_2$ $B_1=B_2\oplus G_1$ $B_0=B_1\oplus G_0$

This maps directly to a cascade of three XOR gates:

graph LR
    G3[Input G3] --> B3[Output B3]
    G3 --> XOR1[XOR Gate 1]
    G2[Input G2] --> XOR1
    XOR1 --> B2[Output B2]
    
    B2 --> XOR2[XOR Gate 2]
    G1[Input G1] --> XOR2
    XOR2 --> B1[Output B1]
    
    B1 --> XOR3[XOR Gate 3]
    G0[Input G0] --> XOR3
    XOR3 --> B0[Output B0]

---

Past Year Questions (PYQs)

• [PYQ 2017]: Define Reflected code. (04 Marks)
• [PYQ 2018]: Convert $(605{)}_{10}$ into Gray code. (12 Marks)
  • Solution: Convert $605$ to binary: $1001011101_2$. Perform binary-to-gray:
    • $G_9=B_9=1$
    • $G_8=1\oplus 0=1$
    • $G_7=0\oplus 0=0$
    • $G_6=0\oplus 1=1$
    • $G_5=1\oplus 0=1$
    • $G_4=0\oplus 1=1$
    • $G_3=1\oplus 1=0$
    • $G_2=1\oplus 1=0$
    • $G_1=1\oplus 0=1$
    • $G_0=0\oplus 1=1$
    • Gray Code: $1101110011$
• [PYQ 2024]: Design a 4-bit reflected code to binary converter circuit using XOR gates. (10 Marks)

---

Related Concepts: 01 BCD & Weighted Digital Codes | 02 Excess-3 Code & Self-Complementing Logic | 03 Gray Code & Code Conversions

2.04 Error Control, Parity Generators & Checkers

Error Control Concepts

During serial data transmission over noisy communication channels, electromagnetic interference can cause bit inversion errors {$0\to 1$ or $1\to 0$}.

To safeguard data integrity, systems employ Error Control Codes by appending redundant check bits to transmitted data packets.

---

1. Error Detecting vs. Error Correcting Codes [PYQ 2017, 2018]

Major Exam Theory Question (2017, 2018 - 4 Marks)

Question: Explain the fundamental differences between Error Detecting codes and Error Correcting codes.

Parameter	Error Detecting Codes	Error Correcting Codes
Primary Function	Detects the presence of errors during transmission.	Detects the error AND automatically determines its bit location to correct it.
Action on Error	Flags error to receiver; requires retransmission.	Automatically corrects error without requesting retransmission.
Redundancy Overhead	Low overhead; requires few redundant bits {e.g., 1 parity bit}.	High overhead; requires multiple redundant check bits {e.g., Hamming distance}.
Implementation Complexity	Simple hardware {cascaded XOR gates}.	Complex logic {syndrome decoders & bit-flipping networks}.
Standard Examples	Parity bits, Checksums, CRC.	Hamming Code, Reed-Solomon Code, BCH Code.

---

2. Parity Architecture & Operation

graph LR
    subgraph Transmitter End
        DataTx[Data Bits: x y z] --> GenXOR[Parity Generator Logic]
        GenXOR --> Packet[Transmitted Packet: x y z P]
    end
    
    Packet -->|Serial Channel| RxPacket[Received Packet: x' y' z' P']
    
    subgraph Receiver End
        RxPacket --> CheckXOR[Parity Checker Logic]
        CheckXOR -->|C = 0| NoError[No Error Detected]
        CheckXOR -->|C = 1| ErrorDet[Bit Error Flagged!]
    end

---

3. Even Parity Generator & Checker

• Even Parity Rule: The parity bit $P$ is generated so that the total count of 1s in $(x,y,z,P)$ is always EVEN.
• 3-Bit Generator (Transmitter): $P=x\oplus y\oplus z$
• 4-Bit Checker (Receiver): $C=x\oplus y\oplus z\oplus P$
  • $C=0⟹\text{No Error}$
  • $C=1⟹\text{Error Detected!}$

---

4. Design: 3-Bit Odd Parity Generator & 4-Bit Checker [PYQ 2022, 2025]

Major Exam Design Problem (2022 - 8 Marks, 2025 - 10 Marks)

Question: Design a 3-bit parity generator and 4-bit parity checker circuit using an odd parity bit.

Part A: 3-Bit Odd Parity Generator (Transmitter)

• Logic Rule: Generates $P$ such that total 1s in $(x,y,z,P)$ is ODD. If $(x,y,z)$ has an even number of 1s, $P$ must be 1.

Truth Table:

Input Message ($x,y,z$)	Generated Odd Parity Bit ($P$)
0 0 0	1
0 0 1	0
0 1 0	0
0 1 1	1
1 0 0	0
1 0 1	1
1 1 0	1
1 1 1	0

Boolean Function:

The minterms for $P$ are $\Sigma m(0,3,5,6)$, which is the exact inverse of a 3-input XOR function {an XNOR function}: $P=(x\oplus y\oplus z{)}^{\prime }=x\oplus y\odot z$

---

Part B: 4-Bit Odd Parity Checker (Receiver)

• Logic Rule: Evaluates received bits $(x,y,z,P)$. If total 1s is EVEN, an error has occurred $⟹$ Error output $C=1$.

Boolean Function:

$C=(x\oplus y\oplus z\oplus P{)}^{\prime }=x\odot y\odot z\odot P$ Implemented by cascading three 2-input XNOR gates.

---

5. Critical Limitations of Parity Error Checking [PYQ 2018]

Limitations of Simple Parity

1. Odd-Bit Error Detection Only: Parity can ONLY detect an odd number of bit errors {1, 3, 5 flipped bits}.
2. Fails on Even-Bit Errors: If an even number of bits flip {e.g., 2 bits change state}, total parity remains unchanged, and $C$ remains $0$ {error undetected}.
3. No Correction Capability: Parity indicates that an error occurred, but cannot identify which bit flipped.

5.1 Differences: Parity Codes vs. Hamming Codes

Feature	Simple Parity Codes	Hamming Codes (e.g., 7-bit)
Primary Capability	Error detection only.	Single-bit error detection AND correction.
Error Detection Limit	Detects only odd numbers of bit errors ($1,3,5\dots$). Fails on even errors.	Detects up to 2-bit errors (with SEC-DED), corrects 1-bit errors.
Error Correction Limit	Zero (requires retransmission).	Corrects exactly one flipped bit.
Bit Overhead	Minimal (exactly 1 parity bit added, regardless of data size).	Higher ($3$ parity bits for $4$ data bits, $4$ for $11$ data bits).
Syndrome Decoder Complexity	Very low (cascaded XOR/XNOR gates).	Medium (decoder logic to calculate error position syndrome).
Typical Use Cases	Short-distance transmission, memory buses.	ECC memory, satellite communications, network packets.

---

6. Master Tutorial: 7-Bit Hamming Code Error Control

To overcome the limitations of simple parity, Richard Hamming developed a method to locate and correct a single-bit error by using overlapping parity sets.

6.1 Bit Allocation Schema

A 7-bit Hamming code contains 4 data bits ($D_3,D_5,D_6,D_7$) and 3 redundant parity bits ($P_1,P_2,P_4$). The parity bits are positioned at indices that are powers of 2.

7-Bit Codeword Positions:
    1      2      3      4      5      6      7
+------+------+------+------+------+------+------+
|  P1  |  P2  |  D3  |  P4  |  D5  |  D6  |  D7  |
+------+------+------+------+------+------+------+
  2^0    2^1    Data   2^2    Data   Data   Data

The binary weight of each position determines which parity bits check it:

• Position 3 ($011_2$) is checked by $P_1$ (LSB=1) and $P_2$ (middle=1).
• Position 5 ($101_2$) is checked by $P_1$ (LSB=1) and $P_4$ (MSB=1).
• Position 6 ($110_2$) is checked by $P_2$ (middle=1) and $P_4$ (MSB=1).
• Position 7 ($111_2$) is checked by $P_1$, $P_2$, and $P_4$.

---

6.2 Parity Generator (Transmitter End)

Assuming even parity, each parity bit is calculated by XORing the data bits in its check set:

• $P_1$ checks positions with LSB = 1 ($1,3,5,7$): $P_1=D_3\oplus D_5\oplus D_7$
• $P_2$ checks positions with middle bit = 1 ($2,3,6,7$): $P_2=D_3\oplus D_6\oplus D_7$
• $P_4$ checks positions with MSB = 1 ($4,5,6,7$): $P_4=D_5\oplus D_6\oplus D_7$

Worked Example: Encode Data 1100 ($D_7{D}_6{D}_5{D}_3$)

Given data bits: $D_7=1,D_6=1,D_5=0,D_3=0$.

1. Calculate Parities:
   • $P_1=0\oplus 0\oplus 1=1$
   • $P_2=0\oplus 1\oplus 1=0$
   • $P_4=0\oplus 1\oplus 1=0$
2. Construct Codeword:
   • $P_1=1$ (Bit 1)
   • $P_2=0$ (Bit 2)
   • $D_3=0$ (Bit 3)
   • $P_4=0$ (Bit 4)
   • $D_5=0$ (Bit 5)
   • $D_6=1$ (Bit 6)
   • $D_7=1$ (Bit 7)
   Codeword: 1100001

---

6.3 Parity Checker & Error Correction (Receiver End)

Upon receiving the 7-bit codeword, the receiver computes three check bits ($C_1,C_2,C_4$):

$C_1=P_1\oplus D_3\oplus D_5\oplus D_7$ $C_2=P_2\oplus D_3\oplus D_6\oplus D_7$ $C_4=P_4\oplus D_5\oplus D_6\oplus D_7$

The check bits form the Syndrome Word ($C_4{C}_2{C}_1$):

• Syndrome $=000_2$ (Decimal 0): No error occurred during transmission.
• Syndrome $\ne 000_2$ (Decimal $k$): A single-bit error occurred at bit position $k$. To correct the error, simply invert bit $k$.

Worked Example: Correcting a Bit Error

Suppose the received codeword is 1110001 (the 3rd bit flipped from 0 to 1 during transmission).

1. Extract received bits:
   • $P_1=1,P_2=0,D_3=1,P_4=0,D_5=0,D_6=1,D_7=1$.
2. Calculate Check Bits:
   • $C_1=1\oplus 1\oplus 0\oplus 1=1$
   • $C_2=0\oplus 1\oplus 1\oplus 1=1$
   • $C_4=0\oplus 0\oplus 1\oplus 1=0$
3. Evaluate Syndrome: $C_4{C}_2{C}_1=011_2=3_{10}$
4. Correction: Bit position 3 is incorrect. Flip Bit 3 ($D_3$) from 1 to 0. The corrected codeword is 1100001, and the recovered data is 1100.

---

7. Past Year Questions (PYQs)

• [PYQ 2017]: Define Error Detection Code. (04 Marks)
• [PYQ 2018]: Differences between Error Detecting and Error Correcting codes. (04 Marks)
• [PYQ 2015, 2020, 2023, 2024]: 4-bit even parity checker design. (08 Marks)
• [PYQ 2022, 2025]: Design 3-bit generator & 4-bit checker using odd parity bit. (08 to 10 Marks)

---