Opening Hamming Code and Hadamard Code
Hamming Code and Hadamard Code
- Length
- 22 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Hamming code definition
The Hamming code and the Hadamard code form a dual pair of binary linear error-correcting codes with opposite trade-offs between rate and distance. O'Donnell defines the Hamming code through a parity check matrix whose columns are all the nonzero binary vectors. Its high rate, minimum distance of three and single-error correction follow, and radius-one Hamming balls partition the space, making it a perfect code. The Hadamard code arrives as its dual, with the encoding map read as evaluation of linear polynomials. Every two distinct codewords then sit at distance exactly , proved via matrix orthogonality, the Schwartz-Zippel lemma and a random-variable argument.
Your comment is kept while you sign up.Sign in
Builds the Hamming code from all nonzero binary columns, then proves its dual, the Hadamard code, has distance .
The Hamming code and the Hadamard code form a dual pair of binary linear error-correcting codes with opposite trade-offs between rate and distance. O'Donnell defines the Hamming code through a parity check matrix whose columns are all the nonzero binary vectors. Its high rate, minimum distance of three and single-error correction follow, and radius-one Hamming balls partition the space, making it a perfect code. The Hadamard code arrives as its dual, with the encoding map read as evaluation of linear polynomials. Every two distinct codewords then sit at distance exactly , proved via matrix orthogonality, the Schwartz-Zippel lemma and a random-variable argument.
This lecture
Lecture 33 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.