Block Coding in Data Communications

1. Principles of Block Coding

In Block Coding, a continuous message stream is divided into blocks of $k$ bits, called Datawords. To each $k$ -bit dataword, $r$ redundant bits are added, producing an $n$ -bit block called a Codeword where:

n = k + r \quad (n > k)

Such an error-control code is designated as an $(n, k)$ Block Code.

                +---------------------------------------+
                |    k Data Bits    |   r Parity Bits   |
                +---------------------------------------+
                |<------------ n Codeword Bits -------->|

Valid vs. Invalid Codewords:

Total possible $k$ -bit datawords: $2^k$ .
Total possible $n$ -bit patterns: $2^n$ .
Number of Valid Codewords: Exactly $2^k$ (one unique codeword for each dataword).
Number of Invalid Patterns: $2^n - 2^k$ .

  All Possible 2^n Bit Patterns
  +-----------------------------------------------------------+
  |  Valid Codewords (2^k)                                   |
  |  [ C1 ]   [ C2 ]   [ C3 ]   [ C4 ] ...                    |
  |                                                           |
  |  Invalid Codewords (2^n - 2^k)                           |
  |  (X)   (X)   (X)   (X)   (X)   (X)   (X)   (X)   (X)      |
  +-----------------------------------------------------------+

Error Detection Principle:
1. The sender transmits a valid codeword $C \in \{2^k\}$ .
2. If transmission noise alters $C$ into an invalid pattern (one of the $2^n - 2^k$ unused states), the receiver immediately flags an Error Detected.
3. Undetected Error: If corruption alters $C$ into another valid codeword, the receiver accepts it as valid data, failing to detect the corruption.

2. Linear Block Codes

A block code is called a Linear Block Code if and only if the bitwise exclusive-OR (modulo-2 addition $\oplus$ ) of any two valid codewords yields another valid codeword in the codebook:

C_1 \oplus C_2 = C_3 \quad (\text{where } C_1, C_2, C_3 \text{ are valid codewords})

Generator Matrix ( $G$ ) and Parity Check Matrix ( $H$ ):

For an $(n, k)$ systematic linear block code:

Generator Matrix $G$ of dimension $k \times n$ :

G = [I_k \mid P]

(where $I_k$ is a $k \times k$ identity matrix and $P$ is a $k \times (n-k)$ parity submatrix).
Codeword generation:

C = D \cdot G

Parity Check Matrix $H$ of dimension $(n-k) \times n$ :

H = [P^T \mid I_{n-k}]

A received vector $Y$ is valid if and only if:

Y \cdot H^T = 0

Syndrome Decoding ( $S$ ):

The receiver multiplies the received $n$ -bit vector $Y$ by the transpose of $H$ :

S = Y \cdot H^T

If $S = 0$ : No detectable error occurred; strip redundant bits to extract data.
If **$S
eq 0 $**: An error occurred. The value of$ S $(called the **Syndrome**) directly matches a column in$ H$, pinpointing the exact bit index that flipped!

3. Physical Layer Block Line Codes: 4B/5B and 8B/10B

In physical-layer digital transmission, long sequences of consecutive 0s or 1s cause baseline wander and loss of clock synchronization. Physical block coding maps $m$ -bit groups to $n$ -bit symbols ( $m < n$ ) to ensure frequent voltage transitions.

       Input Data (4 bits) ──> [ 4B/5B Encoder ] ──> Output Symbol (5 bits) ──> NRZ-I
          (16 values)             (Re-mapped)               (32 patterns)

1. 4B/5B Encoding (Fast Ethernet — 100Base-TX):

Maps each 4-bit data nibble ( $2^4 = 16$ data values) to a 5-bit code pattern ( $2^5 = 32$ possible symbols).
Guarantees no more than three consecutive 0s in the output stream, preventing clock drift when modulated via NRZ-I.
Unused 5-bit symbols are reserved for control (Start Delimiter J/K, End Delimiter T/R, Idle I).
Efficiency: $\frac{4}{5} = 80\%$ .

2. 8B/10B Encoding (Gigabit Ethernet — 1000Base-X):

Maps 8-bit bytes ( $256$ values) to 10-bit symbols ( $1024$ patterns).
Maintains DC Balance (equal count of 0s and 1s using Running Disparity $\pm 1$ ).
Efficiency: $\frac{8}{10} = 80\%$ .

4. Key Exam Questions & Numericals

In a (7, 4) linear block code, how many valid codewords and how many invalid patterns exist?
- $k = 4$ , $n = 7$ .
- Valid codewords = $2^k = 2^4 = 16$ .
- Total patterns = $2^n = 2^7 = 128$ .
- Invalid patterns = $128 - 16 = 112$ .
What defines a Linear Block Code?
- The modulo-2 XOR sum of any two valid codewords in the codebook must produce another valid codeword from the same codebook.
Why is 4B/5B encoding combined with NRZ-I in Fast Ethernet?
- NRZ-I transitions on bit 1 but produces no transition on bit 0. A long run of zeros would cause the receiver's clock to lose synchronization. 4B/5B ensures that no pattern produces more than three consecutive zeros, guaranteeing frequent clock recovery transitions.

Block Coding