= Coding theory
{wiki}
Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In <channel coding>, messages are mapped to separated <codewords>, so a corrupted word can still be recognized as coming from one particular message. In <lossless source coding>, a <prefix code> instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.
The simplest error-correction example sends $0$ as $000$ and $1$ as $111$. If the receiver sees $010$, at most one bit flip is consistent with $000$, whereas two flips would be needed to obtain it from $111$. A <repetition code> therefore recovers the original by taking the <majority function> of the received <bits>. The <Hamming distance> between the valid <codewords> is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.
The central tradeoff is between <code rate> and <minimum distance>. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The <Hamming bound> counts disjoint error neighborhoods, while <linear codes> turn encoding and error detection into computations with <matrices> over <finite fields>. These connections explain why <combinatorics>, <linear algebra>, and <probability theory> all enter the subject.
Richard W. Hamming's \i[Error Detecting and Error Correcting Codes] appeared in the \i[Bell System Technical Journal] in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.https://zoo.cs.yale.edu/classes/cs323/doc/Hamming.pdf[Hamming, Error Detecting and Error Correcting Codes, 1950]{ref}
Back to article page
