Coding theory studies how information can be represented so that errors can be detected or corrected after transmission or storage. This cheat sheet helps students connect binary arithmetic, modular arithmetic, and distance ideas to real systems such as barcodes, memory, internet packets, and digital communication. It is useful because even one flipped bit can change a message, so reliable systems need built-in ways to check data.
Key Facts
- A binary codeword is a string of 0s and 1s, and a code is a set of allowed codewords.
- The Hamming distance d(x, y) between two equal-length binary strings is the number of positions where they differ.
- A code can detect up to s errors if its minimum distance satisfies d_min >= s + 1.
- A code can correct up to t errors if its minimum distance satisfies d_min >= 2t + 1.
- An even parity bit is chosen so the total number of 1s in the transmitted word is even.
- A simple checksum often uses modular arithmetic, such as check value = sum of data values mod n.
- The redundancy of a code is r = n - k, where k is the number of message bits and n is the total number of transmitted bits.
- The rate of a block code is R = k/n, so higher rate means less redundancy but usually weaker error protection.
Vocabulary
- Codeword
- A codeword is an allowed transmitted string that represents data after adding any required check or redundancy bits.
- Hamming Distance
- Hamming distance is the number of positions in which two equal-length strings have different symbols.
- Minimum Distance
- Minimum distance is the smallest Hamming distance between any two distinct codewords in a code.
- Parity Bit
- A parity bit is an extra bit added to make the total number of 1s either even or odd.
- Checksum
- A checksum is a value computed from data and sent with it so the receiver can test whether an error likely occurred.
- Redundancy
- Redundancy is extra information added to a message to help detect or correct errors.
Common Mistakes to Avoid
- Confusing error detection with error correction is wrong because detecting an error only says something changed, while correcting an error identifies the most likely original message.
- Forgetting that Hamming distance only compares equal-length strings is wrong because each position must match with exactly one position in the other string.
- Using d_min >= t + 1 for correction is wrong because correcting t errors requires d_min >= 2t + 1 to separate codewords enough.
- Assuming one parity bit can detect every error is wrong because even parity fails when an even number of bits are flipped.
- Ignoring modular wraparound in checksums is wrong because checksum calculations often use remainders, so values must be reduced mod n.
Practice Questions
- 1 Find the Hamming distance between 101101 and 100111.
- 2 A code has minimum distance d_min = 5. How many errors can it detect, and how many errors can it correct?
- 3 Add an even parity bit to the 7-bit message 1101001, placing the parity bit at the end.
- 4 Explain why adding redundancy can make communication more reliable even though it increases the number of bits sent.
Understanding Coding Theory & Error Detection
Redundancy is not a mistake or wasted space. It is planned evidence about what the original data should have been. A receiver uses that evidence to decide whether a received block still makes sense.
Parity is the smallest example. It works well for a single changed bit because the total count of ones changes from even to odd, or the reverse. Its weakness is important.
If two bits flip, the total can return to the expected parity. The receiver then accepts damaged data.
This shows a central idea in coding theory. A check can be simple, fast, and useful without catching every possible error.
Checksums use a broader summary of data than a single parity bit. A device can split a message into numbers, add them, then keep a remainder after division by a chosen number. The receiver repeats the same calculation.
Matching results give some confidence that the data arrived intact. A mismatch signals corruption. Different messages can sometimes produce the same checksum, so a match is not proof of perfection.
This is called a collision. Real systems choose checksum methods based on the kinds of errors they expect. A file transferred across a network may need a stronger check than a short product code typed by a person.
Distance ideas explain why some codes can repair errors rather than only report them. Picture every allowed binary word as a point in a large grid. A transmission error moves the point away from its intended location by changing bit positions.
If the allowed points are far apart, a received word near one point can be assigned back to that point with confidence. If two allowed points are too close, the same damaged word may be equally plausible as either original message. Correction then becomes unsafe.
Error correction is therefore not magic. It depends on enough extra bits and a decoding rule that identifies the most likely valid word.
The tradeoff between protection and efficiency appears in everyday technology. Memory modules use error correcting codes because a wrong stored bit can affect a calculation. QR codes include spare patterns so part of the image can be scratched or hidden.
Mobile links add protection because radio signals can fade or be disturbed. More checking bits make transmissions longer, use more storage, and may require more processing. Fewer checking bits save space but leave less room for recovery.
When studying, separate detection from correction, and test examples by changing one bit, then two bits. Track exactly which checks still fail. This makes the limits of each method much clearer.