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

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]:
I_4 | P
G rows: 1000 | 110
0100 | 101
0010 | 011
0001 | 111
P rows: 110, 101, 011, 111Here G is 4 x 7, and a row message gives c = uG. The compatible H = [P^T | I_3] is:
P^T | I_3
H rows: 1101 | 100
1011 | 010
0111 | 001The 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 = 0p_2 = u_1 XOR u_3 XOR u_4 = 1 XOR 1 XOR 1 = 1p_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).

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 = 0s_2 = c_1 XOR c_3 XOR c_4 XOR c_6 = 1 XOR 1 XOR 1 XOR 1 = 0s_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 |
|
|
|
|
|
|
|
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.

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:
Confirm whether messages are row or column vectors.
Write every operation as XOR over
GF(2).Keep bit positions labelled above the columns of
H.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
Hcolumns. Here010means position 6 becauseh_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 = 000proves no error: it proves only that the received vector is a codeword. Adding weight-3 codeword1110000to1011010gives different valid word0101010, also with zero syndrome.Turning
d_min = 3into two-error correction: detection usesd_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.
Keep learning
Linear Block Codes MCQs: 12 Solved Questions with Explanations
Attempt 12 linear block code questions, nine of them previous-year, then check each answer with short working on Hamming codes, parity, XOR closure and syndrome decoding.
BCD and Special Codes Explained: 8421, Excess-3, Gray Code and Worked Examples
Learn how to encode, decode and add BCD values, use 2421 and Excess-3 correctly, and convert between binary and Gray code through checked examples.
BCD & Special Codes MCQs: 12 Solved Questions with Explanations
Work through 12 previous-year MCQs on digit-wise BCD, Excess-3 correction and Gray-code conversion, from GATE, ISRO, DSSSB and UGC NET, each solved step by step.
2-D Transformations and Viewing in Computer Graphics: Matrices, Rotation, and Worked Examples
Build 2-D transformations from column vectors to homogeneous matrices, then work through pivot rotation, composite order, and viewport mapping.





