Linear Block Codes Explained: Generator Matrices, Syndromes and a Solved (7,4) Example

Follow one message through a systematic (7,4) code, from generator-matrix encoding to syndrome decoding. The same example also makes minimum distance and error limits concrete.

KnowledgeGate Team

Exam prep & CS education

Updated 14 Nov 20266 min read
Linear Block Codes Explained: Generator Matrices, Syndromes and a Solved (7,4) Example

The notation G, H, (n,k) and d_min becomes concrete when one message passes through encoding and correction. A binary (7,4) example builds a codeword, checks it, locates a flipped bit from its syndrome, and derives its detection and correction strength. CS Fundamentals supplies the wider Computer Networks path. Hamming Distance in Error Control develops pairwise distance and parity-position decoding; generator and parity-check matrices instead encode a message algebraically and map each single-bit error to an H column.

Linear block codes turn k message bits into n-bit codewords

A binary block code maps each k-bit message to an n-bit codeword. It is linear if it contains the all-zero word and is closed under XOR. With a rank-k generator, its codewords form a k-dimensional subspace of GF(2)^n.

In (n,k), n is codeword length, k is message length, redundancy is n - k, there are 2^k messages and codewords, and the code rate is R_c = k/n.

For a (7,4) code, redundancy is 7 - 4 = 3. There are 2^4 = 16 codewords among 2^7 = 128 possible seven-bit vectors, and R_c = 4/7, approximately 0.571.

This data-link-layer coding protects a block against bit errors. It does not assign network addresses, the separate job in IP Addressing and Subnetting Explained.

Generator matrix G and parity-check matrix H describe the same code

Treat messages as row vectors. Use the systematic form G = [I_4 | P]:

Code
          I_4 | P
G rows: 1000 | 110
        0100 | 101
        0010 | 011
        0001 | 111

P rows: 110, 101, 011, 111

Here G is 4 x 7, and a row message gives c = uG. The compatible H = [P^T | I_3] is:

Code
          P^T | I_3
H rows: 1101 | 100
        1011 | 010
        0111 | 001

The 3 x 7 matrix is compatible because GH^T = I_4 P + P I_3 = P + P = 0 in GF(2). Thus every generated codeword satisfies Hc^T = 0. Some books use H = [-P^T | I]; in binary arithmetic, -P^T = P^T.

Linear block code encoding worked example: message 1011

Take u = [1,0,1,1]. Because G is systematic, the first four bits of the codeword remain 1011. The parity vector is p = uP:

  • p_1 = u_1 XOR u_2 XOR u_4 = 1 XOR 0 XOR 1 = 0

  • p_2 = u_1 XOR u_3 XOR u_4 = 1 XOR 1 XOR 1 = 1

  • p_3 = u_2 XOR u_3 XOR u_4 = 0 XOR 1 XOR 1 = 0

Thus p = 010, so c = [u | p] = 1011010.

Cross-check with the generator rows selected by the 1s in u:

c = g_1 XOR g_3 XOR g_4 = 1000110 XOR 0010011 XOR 0001111 = 1011010.

For v = 0110, c(v) = g_2 XOR g_3 = 0110110 and u XOR v = 1101, while:

c(u) XOR c(v) = 1011010 XOR 0110110 = 1101100 = c(1101).

Generator matrix G with rows 1, 3 and 4 XORed to encode u = 1011, giving parity 010 and the codeword 1011010.

Syndrome decoding worked example: locate and correct bit 6

First check the transmitted c = 1011010:

  • s_1 = c_1 XOR c_2 XOR c_4 XOR c_5 = 1 XOR 0 XOR 1 XOR 0 = 0

  • s_2 = c_1 XOR c_3 XOR c_4 XOR c_6 = 1 XOR 1 XOR 1 XOR 1 = 0

  • s_3 = c_2 XOR c_3 XOR c_4 XOR c_7 = 0 XOR 1 XOR 1 XOR 0 = 0

Hence s = Hc^T = 000, and c is valid.

Now flip transmitted bit 6 from 1 to 0. The received word is r = 1011000, and Hr^T = 010. Label the columns of H by bit position:

Position

1

2

3

4

5

6

7

Column of H

110

101

011

111

100

010

001

Since r = c XOR e_6, the locator rule is:

Hr^T = Hc^T XOR He_6^T = 000 XOR h_6 = h_6 = 010.

The syndrome matches column 6. Flip that bit to recover 1011010; its syndrome returns to 000, and the systematic message is 1011.

Syndrome table linking H columns to bit positions: s = 010 matches column 6, so flipping bit 6 restores 1011010.

Minimum distance tells you what the code can detect and correct

For a linear code, d_min is the minimum Hamming weight among non-zero codewords. Every column of H is non-zero, ruling out weight 1. All columns are distinct, so no weight-2 vector has zero syndrome. Thus d_min >= 3. Since codeword g_1 = 1000110 has weight 3, d_min <= 3, and therefore d_min = 3.

The code guarantees detection of d_min - 1 = 2 bit errors and correction of t = floor((d_min - 1)/2) = 1 bit error. Detecting two does not mean correcting two.

For example, flip positions 1 and 2 of c = 1011010 to get r_2 = 0111010. Its syndrome is:

h_1 XOR h_2 = 110 XOR 101 = 011 = h_3.

A one-error decoder flips bit 3 and outputs the wrong codeword 0101010, whose syndrome is 000. The double error was detectable before the false assumption caused miscorrection.

How exams test generator matrices, syndromes and code distance

Question forms include finding redundancy, rate or codeword count from (n,k); encoding with G; deriving H; testing GH^T = 0; validating a received vector; locating one error; finding d_min; and deriving detection and correction limits.

Use this four-step routine:

  1. Confirm whether messages are row or column vectors.

  2. Write every operation as XOR over GF(2).

  3. Keep bit positions labelled above the columns of H.

  4. After correction, recompute the syndrome.

For a quick check, w = 1011000 gives Hw^T = 010. It is not a codeword and, assuming one error, position 6 is corrected.

Practise the same matrix and syndrome calculations with KnowledgeGate's Linear Block Codes question set.

TCP vs UDP: Transport Layer Explained is an adjacent concept, but it covers a different layer and problem.

Linear block code traps and the correction for each

  • Decimal addition: use modulo 2, so 1 XOR 1 = 0.

  • Wrong orientation: check dimensions. Here [1 x 4][4 x 7] gives [1 x 7].

  • Reading the syndrome as a position: match labelled H columns. Here 010 means position 6 because h_6 = 010, not decimal 2.

  • Correcting every non-zero syndrome: this needs a one-error promise. A double error can also produce a column syndrome.

  • Saying s = 000 proves no error: it proves only that the received vector is a codeword. Adding weight-3 codeword 1110000 to 1011010 gives different valid word 0101010, also with zero syndrome.

  • Turning d_min = 3 into two-error correction: detection uses d_min - 1; correction uses half with the floor.

Linear block codes in the short version, then the next step

The chain is u -> c = uG -> r = c XOR e -> s = Hr^T -> locate a promised single error -> correct -> verify syndrome 000. In this binary convention, G = [I_k | P], H = [P^T | I_(n-k)], GH^T = 0, while d_min gives detection up to d_min - 1 and correction up to floor((d_min - 1)/2).

Try this before reading the answer: encode u = 0101, then flip bit 4 and find the syndrome. Answer: p = 010, c = 0101010, r = 0100010, and syndrome 111 = h_4, so correcting bit 4 restores 0101010.

If you want Computer Networks sequenced with other core CS subjects, Computer Science Fundamentals for Placements by Sanchit Sir includes Computer Networks and DLL: Error Control as part of the curriculum.