Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2009/ii/paper-3/4h/solution
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 3 4H Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-14
Use the binary Hamming code , where the th column of the parity-check matrix is the four-digit binary expansion of , for . Thus the columns are precisely the nonzero vectors of . They include the four coordinate vectors, so and . Its code rate is therefore .
For a received word , compute its syndrome . If , report no error. Otherwise identify the unique column and flip bit . Indeed, if with , then , so this procedure recovers exactly. No column is zero and no two columns coincide; hence no nonzero codeword has Hamming weight one or two. Some three columns sum to zero, for example those indexed by , so the minimum distance is exactly three. Thus every single-bit error is corrected. The assertion requires at most one error; arbitrary multiple errors need not be detected by this procedure.
New to topics? Read the docs here!