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.