Related Concepts: 2.01 BCD & Weighted Digital Codes | 2.02 Excess-3 Code & Self-Complementing Logic | 2.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

Major Exam Theory Question (PYQ 2018 — 04 marks)

Question (verbatim): Explain the differences between error detecting codes and error correcting codes.

The 2017 paper instead asked you to simply “Define Error detection code” as one item inside a 10-mark multi-part definitions question.

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!}$

---

3.1 Design: 4-Bit Even Parity Checker

Major Exam Design Problem (PYQ 2015, 2020, 2023, 2024 — 8 to 12 marks)

Question (verbatim): Design a combinational circuit to check for even parity of four bits. A logic-1 output is required when the four bits do not constitute an even parity.

Read the specification carefully. All four bits $A,B,C,D$ are received bits — this is not a 3-data-plus-1-parity split. The output $F$ must be 1 when the word fails the even-parity test, i.e. when the number of 1s is odd.

Step 1: Truth Table

$A$	$B$	$C$	$D$	No. of 1s	Parity	$F$
0	0	0	0	0	even	0
0	0	0	1	1	odd	1
0	0	1	0	1	odd	1
0	0	1	1	2	even	0
0	1	0	0	1	odd	1
0	1	0	1	2	even	0
0	1	1	0	2	even	0
0	1	1	1	3	odd	1
1	0	0	0	1	odd	1
1	0	0	1	2	even	0
1	0	1	0	2	even	0
1	0	1	1	3	odd	1
1	1	0	0	2	even	0
1	1	0	1	3	odd	1
1	1	1	0	3	odd	1
1	1	1	1	4	even	0

$F=\sum m(1,2,4,7,8,11,13,14)$

Step 2: K-Map — and Why It Refuses to Simplify

       CD
  AB \ 00   01   11   10
    +----+----+----+----+
 00 |  0 |  1 |  0 |  1 |
    +----+----+----+----+
 01 |  1 |  0 |  1 |  0 |
    +----+----+----+----+
 11 |  0 |  1 |  0 |  1 |
    +----+----+----+----+
 10 |  1 |  0 |  1 |  0 |
    +----+----+----+----+

Every 1 is surrounded on all four sides by 0s — a perfect checkerboard. No two 1s are ever adjacent, so no pair, quad or octet can be formed. The function is already minimal in SOP form, and that SOP needs eight 4-input AND gates plus an 8-input OR gate.

Step 3: The XOR Realisation

A checkerboard K-map is the visual signature of an XOR/XNOR function. Reading it as such:

$\mathbf{F}=\mathbf{A}\oplus \mathbf{B}\oplus \mathbf{C}\oplus \mathbf{D}$

This collapses ~9 gates down to three 2-input XOR gates cascaded:

  A ---+
       |--[ XOR ]---+
  B ---+            |
                    |--[ XOR ]---+
  C -----------------+           |
                                 |--[ XOR ]--- F
  D ------------------------------+

Exam Hack: Spot the Checkerboard Instantly

Any function whose minterms are the odd-parity set is an XOR chain; the even-parity set is an XNOR chain. You do not need to draw the K-map at all — but do draw it anyway, because “show that no grouping is possible” is where the marks for justifying the XOR form live.

Watch the polarity trap: if a paper instead says “logic-1 output when the bits DO constitute even parity”, the answer flips to $F=(A\oplus B\oplus C\oplus D{)}^{\prime }$, an XNOR chain. Four papers so far have used the “do not constitute” wording — read it twice.

---

4. Design: 3-Bit Odd Parity Generator & 4-Bit Checker

Major Exam Design Problem (PYQ 2022 — 08 marks; 2025 — 10 marks)

Question (verbatim, 2022): Derive the circuits for a three-bit parity generator and four-bit parity checker 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)$ — again a checkerboard, so this is the exact inverse of a 3-input XOR function {an XNOR, which outputs 1 when the count of 1s is even}:

$\mathbf{P}=\overline{(\mathbf{x}\oplus \mathbf{y}\oplus \mathbf{z})}$

Built as two 2-input XOR gates followed by an inverter (or an XOR feeding an XNOR).

---

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:

$\mathbf{C}=\overline{(\mathbf{x}\oplus \mathbf{y}\oplus \mathbf{z}\oplus \mathbf{P})}$ Implemented by cascading three 2-input XOR gates followed by an inverter.

Generator vs. Checker — one gate apart

The odd-parity generator and the odd-parity checker are the same XNOR structure; the checker simply has one extra input (the received parity bit $P$). If you can draw one, you can draw the other in ten seconds. Compare against the even-parity checker in §3.1, which is a plain XOR chain with no inverter.

---

5. Critical Limitations of Parity Error Checking

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 Index for this note

Question (as asked)	Years	Marks	Solved in
Define error detection code (inside a multi-part definitions question)	2017	part of 10	§Abstract, §1
Explain the differences between error detecting codes and error correcting codes	2018	4	§1
Design a combinational circuit to check for even parity of four bits; logic-1 when the bits do not constitute even parity	2015, 2020, 2023, 2024	8–12	§3.1
Derive circuits for a 3-bit parity generator and 4-bit parity checker using an odd parity bit	2022, 2025	8–10	§4

Pattern to notice: the 4-bit even-parity checker is one of the most repeated design questions in the whole paper — four appearances in ten years, worth up to 12 marks, and the wording never changes. It is also the cheapest to answer: truth table → checkerboard K-map → XOR chain. Roughly fifteen minutes of practice locks in a guaranteed block of marks.

The Hamming code material in §6 has not appeared in a past paper. It is included because it is the natural answer to “how would you correct rather than merely detect”, and because §5.1 compares the two — but do not spend heavy revision time on it before the repeated parity questions above are automatic.