Opening Linear Error Correcting Codes
Linear Error Correcting Codes
- Length
- 20 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Generator matrices and subspaces
Linear error-correcting codes identify the alphabet with a finite field and take the code to be a subspace, so encoding becomes a linear map. O'Donnell starts from the generator matrix , which sends a message to the codeword by one matrix multiply. He then defines the dual code as all vectors orthogonal to every codeword. Its parity check matrix gives an efficient test of whether a received word is valid. The final part shows that minimum distance equals the least Hamming weight of a nonzero codeword and ties it to linearly dependent columns of . Lecture 11b of CS Theory Toolkit (CMU 15-750) at Carnegie Mellon assumes linear algebra, finite fields and Hamming distance.
Your comment is kept while you sign up.Sign in
Proves a linear code's minimum distance equals its least nonzero codeword weight and fewest dependent columns of .
Linear error-correcting codes identify the alphabet with a finite field and take the code to be a subspace, so encoding becomes a linear map. O'Donnell starts from the generator matrix , which sends a message to the codeword by one matrix multiply. He then defines the dual code as all vectors orthogonal to every codeword. Its parity check matrix gives an efficient test of whether a received word is valid. The final part shows that minimum distance equals the least Hamming weight of a nonzero codeword and ties it to linearly dependent columns of . Lecture 11b of CS Theory Toolkit (CMU 15-750) at Carnegie Mellon assumes linear algebra, finite fields and Hamming distance.
This lecture
Lecture 32 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.