Block Codes and Error Detection Using Parity-Check Codes

1. What is Block Coding?

In block coding, the original message is divided into fixed-size blocks of k bits, called datawords.

The sender adds r redundant bits to each dataword, producing an n-bit codeword:

$$n = k+r$$

So:

Dataword                 Codeword
 k bits       +        r redundant bits
   ↓                         ↓
[ Data ]      +       [ Redundancy ]
        └──────────────┘
             n bits

For example, if:

• $k=4$
• $r=1$

then:

$$n=4+1=5$$

So a 4-bit dataword becomes a 5-bit codeword.

The important idea is that not all possible $n$-bit combinations are used as valid codewords. The unused combinations are called invalid/illegal codewords. If the receiver receives one of these invalid codewords, it knows that an error has occurred.

---

2. How Block Coding Detects Errors

The process is:

             SENDER
               |
        k-bit Dataword
               ↓
            Encoder
               ↓
        n-bit Codeword
               |
        Unreliable channel
               ↓
            RECEIVER
               |
          Error Checker
               ↓
       +-------+-------+
       |               |
   Valid codeword   Invalid codeword
       |               |
     Accept          Discard

The receiver needs to know the set of valid codewords.

If transmission changes a valid codeword into an invalid codeword, the receiver detects the error.

However, if the corrupted codeword happens to become another valid codeword, the error cannot be detected.

Example

Suppose:

Dataword	Codeword
00	000
01	011
10	101
11	110

Suppose the sender sends:

Dataword = 01
Codeword = 011

Case 1 — No error

Sent:      011
Received:  011

011 is valid → Accepted.

Case 2 — Error detected

Sent:      011
Received:  111

111 is not a valid codeword → Discarded.

Case 3 — Error not detected

Sent:      011
Received:  000

000 is a valid codeword, but it represents dataword 00.

Therefore, the error is undetected.

Note:An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected.

---

3. Hamming Distance

An important concept in block coding is Hamming distance.

The Hamming distance between two codewords is the number of bit positions in which they differ.

For example:

X = 00000
Y = 01101

    0 0 0 0 0
    0 1 1 0 1
    ↑ ↑     ↑
    3 different bits

Therefore:

$$d(X,Y)=3$$

Hamming distance can also be calculated using XOR and counting the number of 1s in the result.

---

Minimum Hamming Distance

The minimum Hamming distance ($d_{min}$) is the smallest distance between any two valid codewords.

To guarantee detection of up to s errors:

$$d_{min}=s+1$$

Therefore:

$d_{min}$	Guaranteed error detection
2	1 error
3	2 errors
4	3 errors
5	4 errors

---

4. Parity-Check Code

The parity-check code is one of the simplest and most familiar error-detecting block codes.

It is a linear block code in which:

$$n=k+1$$

That means one extra bit, called the parity bit, is added to every $k$-bit dataword.

The textbook discusses even parity.

Even parity

The parity bit is selected so that the total number of 1s in the complete codeword is even.

For example:

Dataword: 1011

There are three 1s, which is odd.

Therefore, we add:

Parity bit = 1

giving:

10111

Now there are four 1s → even.

---

5. How the Parity Bit is Calculated

For a 4-bit dataword:

a3 a2 a1 a0

the parity bit is:

$$r_0=a_3\oplus a_2\oplus a_1\oplus a_0$$

where $\oplus$ represents modulo-2 addition (XOR).

Example

Take:

Dataword = 1011

Number of 1s = 3.

Therefore:

Parity bit = 1
Codeword   = 10111

Total number of 1s = 4 → even.

---

6. Error Detection at the Receiver

The receiver receives the complete codeword and performs the same XOR operation on all bits, including the parity bit.

The result is called the syndrome.

For a simple parity-check code:

• Syndrome = 0 → no detectable error
• Syndrome = 1 → error detected

Example 1: No error

Received = 10111

Number of 1s = 4

Even → syndrome = 0

       ↓
   Accept data

Example 2: One-bit error

Suppose:

Sent:      10111
Received:  10011

The number of 1s in the received word is now 3 → odd.

Therefore:

Syndrome = 1
       ↓
Error detected
       ↓
Discard frame

---

7. What Can Parity Check Detect?

The simple parity-check code has:

$$d_{min}=2$$

Therefore, it guarantees detection of a single-bit error.

However, it cannot guarantee detection of all multiple-bit errors.

For example, if two bits change, the total parity may remain even:

Sent:      10111
Received:  01111
           ↑ ↑
       two bits changed

The number of 1s may still be even, so the error can go undetected.

Note: A parity-check code can detect an odd number of errors.

---

8. Complete Picture

              BLOCK CODING
                   |
          +--------+--------+
          |                 |
       Dataword          Redundant bits
        k bits               r bits
          |                 |
          +--------+--------+
                   ↓
              Codeword
                n bits
                   |
             Transmission
                   |
                   ↓
              Receiver
                   |
             Error Checker
                   |
            Check validity
                   |
          +--------+--------+
          |                 |
       Valid              Invalid
          |                 |
       Accept            Error detected

Key Points

• Block coding: divides data into $k$-bit datawords and adds $r$ redundant bits to form $n$-bit codewords.
• $n=k+r$.
• Invalid codewords help in error detection.
• Hamming distance measures the number of differing bit positions.
• To guarantee detection of $s$ errors: $d_{min}=s+1$.
• Parity-check code: $n=k+1$, one parity bit is added.
• In even parity, the total number of 1s must be even.
• Simple parity has $d_{min}=2$ and therefore guarantees detection of one-bit errors.
• A corrupted codeword that becomes another valid codeword can result in an undetected error.