Error-Correcting Codes

Error-Correcting Codes#

Sections#

Resources#

https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes1.pdf

https://www.ams.org/journals/bull/1999-36-03/S0273-0979-99-00783-1/S0273-0979-99-00783-1.pdf

YouTube#

Ben Eater

  • [ y ] Ben Eater. (2020). “What is error correction? Hamming codes in hardware”. YouTube.

  • [ y ] Ben Eater. (2018). “Error detection: Parity checking”. YouTube.

  • [ y ] Ben Eater. (2018). “Reliable data transmission”. YouTube.

3Blue1Brown

  • [ y ] Grant Sanderson. (2020). “Hamming codes and error correction”. YouTube.

  • [ y ] Grant Sanderson. (2020). “Hamming codes part 2, the elegance of it all”. YouTube.

more

  • [ y ] 11-23-2023. Primal Space. “Voyager’s 15 Billion Mile Software Update”.

Texts#

FCCT 1990 Hill, Raymond. A First Course in Coding Theory. Clarendon Press: Oxford Applied Mathematics and Computing Science Series.

ECFF 1992 Pretzel, Oliver. Error-Correcting Codes and Finite Fields. Oxford University Press Applied Mathematics and Computing Science Series.

  • Ball, Simeon. (2020). A Course in Algebraic Error-Correcting Codes.

  • Berlekamp, Elwyn R. (2015). Algebraic Coding Theory.

  • Bierbrauer, Jurgen. (2016). Introduction to Coding Theory.

  • Biggs, Norman L. Codes: An Introduction to Information Communication and Cryptography. Springer Undergraduate Mathematics Series.

  • Blahut, Richard E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press.

  • Brzezinski, Juliusz. (2018). Galois Theory Through Exercises. Springer.

  • Csiszár, Imre & János Körner. (2011). Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press.

  • Golomb, Solomon W., Robert E. Peile, & Robert A. Scholtz. (1994). Basic Concepts in Information Theory and Coding: The Adventures of Secret Agent 00111. Springer.

  • Hamming, Richard W. (1985). Coding and Information Theory.

  • Huffman, W. Cary. & Vera Pless. (2010). Fundamentals of Error-Correcting Codes. Cambridge University Press.

  • Humphreys, J. F. & M. Y. Prest. (2004). Numbers, Groups, and Codes, 2nd Ed. Cambridge University Press.

  • Jones, Gareth A. & J. Mary Jones. (2000) Information and Coding Theory. Springer Undergraduate Mathematics Series.

  • MacWilliams, F. J. & N. J. A. Sloane. (1977). The Theory of Error-Correcting Codes.

  • Moon, Todd K. (2021). Error Correction Coding: Mathematical Methods and Algorithms. Wiley.

  • Moser, Stefan M. & Po-Ning Chen. (2012). A Student’s Guide to Coding and Information Theory. Cambridge University Press.

  • Neubauer, Andre. (2007). Coding Theory: Algorithms, Architectures, and Applications. Wiley.

  • Peterson, W. Wesley. (1972). Error-Correcting Codes. 2nd Ed. MIT Press.

  • Pierce, John R. (1980). An Introduction to Information Theory: Symbols, Signals, and Noise. Dover.

  • Reza, Fazlollah M. (1994). An Introduction to Information Theory. Dover.

  • Roman, Steven. (1997). Introduction to Coding and Information Theory. Springer Undergraduate Texts in Mathematics.

  • Roman, Steven. (1992). Coding and Information Theory. Springer Graduate Texts in Mathematics.

  • Roth, Ron. (2006). Introduction to Coding Theory. Cambridge University Press.

  • Sanvicente, Emilio. (2019). Understanding Error Control Coding. Springer.

  • Stepanov, Serguei A. (1999). Codes on Algebraic Curves. Springer.

  • Sweeney, Peter. (2002). Error Control Coding: From Theory to Practice. Wiley.

  • Tomlinson et al. (2017). Error-Correction and Decoding: Bounds, Codes, Decoders, Analysis, and Applications. Springer Signals and Communication Technology.

  • Trappe, Wade & Lawrence Washington. (2005). Introduction to Cryptography with Coding Theory. Pearson.

  • Van Lint, J. H. (1999). Introduction to Coding Theory, 3rd Ed. Springer Graduate Texts in Mathematics.

Figures#

  • [ w ] 1951----- Berrou, Claude

  • [ w ] --------- Canteaut, Anne

  • [ w ] 1923-2001 Elias, Peter

  • [ w ] 1917-2016 Fano, Robert

  • [ w ] 1923-2013 Gilbert, Edgar

  • [ w ] 1932-2016 Golomb, Solomon

  • [ w ] 1887-1969 Gray, Frank

  • [ w ] 1865-1963 Hadamard, Jacques

  • [ w ] 1941----- Hagenauer, Joachim

  • [ w ] 1915-1998 Hamming, Richard

  • [ w ] 1888-1970 Hartley, Ralph

  • [ w ] 1925-1999 Huffman, David

  • [ w ] 1936-2023 Lempel, Abraham

  • [ w ] 1935-2017 Levenshtein, Vladimir

  • [ w ] --------- Luby, Michael

  • [ w ] 1924-2008 Muller, David

  • [ w ] 1923-2012 Reed, Irving

  • [ w ] 1916-2001 Shannon, Claude

  • [ w ] 1964----- Shokrollahi, Amin

  • [ w ] 1930-1996 Solomon, Gustave

  • [ w ] 1927-1999 Varshamov, Rom

  • [ w ] 1935----- Viterbi, Andrew

  • [ w ] 1925-2009 Wozencraft, John

  • [ w ] 1931-2023 Ziv, Jacob

Terms#

  • [ w ] Arithmetic Coding

  • [ w ] Asymmetric Numeral System

  • [ w ] Automatic Repeat Request (ARQ)

  • [ w ] Backward Channel

  • [ w ] Ball

  • [ w ] BCH Code

  • [ w ] BCJR Algorithm

  • [ w ] Binary-Coded Decimal

  • [ w ] Binary Asymmetric Channel

  • [ w ] Binary Code

  • [ w ] Binary Entropy Function

  • [ w ] Binary Erasure Channel

  • [ w ] Binary Symmetric Channel

  • [ w ] Bit Error Rate

  • [ w ] Bit Rate

  • [ w ] Bit Rate Reduction

  • [ w ] Bit Slip

  • [ w ] Block Code

  • [ w ] Burst Error

  • [ w ] Burst Error-Correcting Code

  • [ w ] Burst Mode

  • [ w ] Burst Transmission

  • [ w ] Cayley Table

  • [ w ] Channel Capacity

  • [ w ] Channel Coding

  • [ w ] Chen-Ho Encoding

  • [ w ] Code

  • [ w ] Code Rate

  • [ w ] Code Word

  • [ w ] Coding Theory

  • [ w ] Comma Code

  • [ w ] Comma-Free Code

  • [ w ] Communication Channel

  • [ w ] Concatenated Code

  • [ w ] Consistent Overhead Byte Stuffing

  • [ w ] Context-Adaptive Binary Arithmetic Coding

  • [ w ] Context-Adaptive Variable-Length Coding

  • [ w ] Convolutional Code

  • [ w ] Coset

  • [ w ] Coset Leader

  • [ w ] Cryptography

  • [ w ] Cyclic Code

  • [ w ] Cyclic Redundancy Check (CRC)

  • [ w ] Cyclic Redundancy Check, Computation

  • [ w ] Data Compression

  • [ w ] Data Signaling Rate

  • [ w ] Decoding

  • [ w ] Deletion Channel

  • [ w ] ECC Memory

  • [ w ] Elias Bassalygo Bound

  • [ w ] Elias Delta Coding

  • [ w ] Elias Gamma Coding

  • [ w ] Elias Omega Coding

  • [ w ] Entropy Coding

  • [ w ] Entropy Rate

  • [ w ] Erasure Code

  • [ w ] Error Detection and Correction

  • [ w ] Error Floor

  • [ w ] Error-Correcting Code (ECC)

  • [ w ] Error-correcting codes with feedback

  • [ w ] Expander Code

  • [ w ] Fibonacci Coding

  • [ w ] Forward Error Correction (FEC)

  • [ w ] Fountain Code

  • [ w ] Generalized Minimum-Distance Decoding

  • [ w ] Gilbert-Varshamov Bound

  • [ w ] Golay Code

  • [ w ] Golomb Coding

  • [ w ] Goppa Code

  • [ w ] Gray Code

  • [ w ] Griesmer Bound

  • [ w ] Hadamard Code

  • [ w ] Hamming (7, 4)

  • [ w ] Hamming Bound

  • [ w ] Hamming Code

  • [ w ] Hamming Distance

  • [ w ] Hamming Weight

  • [ w ] Huffman Coding

  • [ w ] Hybrid Automatic Repeat Request (HARQ)

  • [ w ] Information Rate

  • [ w ] Information Theory

  • [ w ] Iterative Viterbi Decoding

  • [ w ] Johnson Bound

  • [ w ] Justesan Code

  • [ w ] Las Vegas Algorithm

  • [ w ] Levenshtein Coding

  • [ w ] Levenshtein Distance

  • [ w ] Line Code

  • [ w ] Linear Code

  • [ w ] Linear-Feedback Shift Register (LFSR)

  • [ w ] Link Adaptation

  • [ w ] List Decoding

  • [ w ] Locally Decodable Code

  • [ w ] Locally Testable Code

  • [ w ] Long Code

  • [ w ] Low-Density Parity-Check (LDPC) Code

  • [ w ] LT Code

  • [ w ] LZ77/LZ78

  • [ w ] Markov Chain

  • [ w ] Maximum Likelihood Decoding

  • [ w ] Minimum Distance Decoding

  • [ w ] Multidimensional Parity-Check Code

  • [ w ] Nearest Neighbor Decoding

  • [ w ] NegaFibonacci Coding

  • [ w ] Noisy-Channel Coding Theorem

  • [ w ] Noisy Channel Model

  • [ w ] Online Code

  • [ w ] Packet Erasure Channel

  • [ w ] Parity Bit

  • [ w ] Parity Check Matrix

  • [ w ] Perfect Code

  • [ w ] Plotkin Bound

  • [ w ] Polar Code

  • [ w ] Polynomial Code

  • [ w ] Prefix Code

  • [ w ] Punctured Code

  • [ w ] Range Coding

  • [ w ] Raptor Code

  • [ w ] Reed-Muller Code

  • [ w ] Reed-Solomon Code

  • [ w ] Repeat-Accumulate Code

  • [ w ] Repetition Code

  • [ w ] Return Channel

  • [ w ] Sardinas-Patterson Algorithm

  • [ w ] Segal’s Law

  • [ w ] Self-Clocking Signal

  • [ w ] Self-Synchronizing Code

  • [ w ] Sequential Decoding

  • [ w ] Serial Concatenated Convolutional Code

  • [ w ] Shannon-Fano-Elias Coding

  • [ w ] Shannon-Hartley Theorem

  • [ w ] Shannon’s Theorem

  • [ w ] Shannon’s Source Coding Theorem

  • [ w ] Singleton Bound

  • [ w ] Slepian Array

  • [ w ] Soft-Decision Decoder

  • [ w ] Soft-In Soft-Out Decoder

  • [ w ] Source Coding

  • [ w ] Standard Array

  • [ w ] Symbol Rate

  • [ w ] Syndrome

  • [ w ] Syndrome Decoding

  • [ w ] Systematic Code

  • [ w ] Ternary Golay Code

  • [ w ] Tornado Code

  • [ w ] Trellis

  • [ w ] Triple Modular Redundancy

  • [ w ] Turbo Code

  • [ w ] Unary Coding

  • [ w ] Universal Code

  • [ w ] Variable-Length Code

  • [ w ] Varicode

  • [ w ] Viterbi Algorithm

  • [ w ] Viterbi Decoder

  • [ w ] Word

  • [ w ] Wozencraft Ensemble

  • [ w ] Z Channel

  • [ w ] Zyablov Bound