Codes, cryptography and algorithms · Maths EE idea · Solid
Correcting errors with Hamming codes
A research question to start from
How do Hamming codes detect and correct single-bit errors, and why are they the most efficient codes that can?
A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.
Why it works as a maths EE
Linear algebra over {0,1} with a sharp optimality result (perfect codes).
Mathematics you would need
- Binary arithmetic
- Parity-check matrices
- Hamming distance
- The sphere-packing bound
Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.
One possible line of attack
- Build the (7,4) code and its parity-check matrix.
- Prove it corrects one error.
- Prove the sphere-packing bound and show Hamming codes meet it.
Scope and difficulty
Solid. Solid.
Pitfalls
- Engineering focus.
- Code tables without proofs.
Where to start reading
Search a library catalogue or a university's open lecture notes for: Hamming code parity check matrix; sphere packing bound perfect code. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).
Make it your EE
Similar ideas
- Check digits: which errors do they catch?Codes & algorithmsAccessible
- Sharing a secret in publicCodes & algorithmsSolid
- Breaking substitution ciphers with statisticsCodes & algorithmsAccessible
- Why the fast Fourier transform is fastCodes & algorithmsAmbitious
All codes, cryptography and algorithms ideas · the full ideas library