Self-Assessment Quiz: Coding Theory — Error-Correcting Codes

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

The Hamming distance between two equal-length strings is:

A) the number of 1s in the longer string B) the number of positions at which they differ C) the absolute difference of their values as binary numbers D) the number of positions at which they agree

Question 2

Over $\mathrm{GF}(2)$, the Hamming distance $d(x, y)$ equals:

A) $\operatorname{wt}(x) - \operatorname{wt}(y)$ B) $\operatorname{wt}(x) + \operatorname{wt}(y)$ C) $\operatorname{wt}(x \oplus y)$ D) $\operatorname{wt}(x \land y)$

Question 3

A code has minimum distance $d_{\min} = 5$. The largest number of errors it is guaranteed to detect is:

A) 2 B) 3 C) 4 D) 5

Question 4

A code has minimum distance $d_{\min} = 5$. The largest number of errors it is guaranteed to correct (under nearest-codeword decoding) is:

A) 1 B) 2 C) 3 D) 4

Question 5

To correct all error patterns of weight $\le t$, a code's minimum distance must satisfy:

A) $d_{\min} \ge t$ B) $d_{\min} \ge t + 1$ C) $d_{\min} \ge 2t$ D) $d_{\min} \ge 2t + 1$

Question 6

The triple-repetition code $\{\texttt{000}, \texttt{111}\}$ has rate:

A) $1$ B) $1/2$ C) $1/3$ D) $3$

Question 7

In $\mathrm{Hamming}(7,4)$, the parity bits are placed at positions $1, 2, 4$ specifically so that:

A) the codeword is easier to print B) the syndrome, read as a binary number, equals the position of the flipped bit C) the data bits stay contiguous D) the rate is maximized

Question 8

The syndrome of a received word in a linear code is computed as:

A) $G m^{\mathsf T}$ where $G$ is the generator matrix B) $H y^{\mathsf T}$ where $H$ is the parity-check matrix C) the Hamming distance to the nearest codeword D) the XOR of all the data bits

Question 9 (True/False, justify)

True or false: For a linear code, the minimum distance equals the minimum weight of a nonzero codeword. Justify in one sentence.

Question 10

A $\mathrm{Hamming}(7,4)$ receiver computes syndrome $s_4 s_2 s_1 = 110$. It should:

A) accept the word as error-free B) flip position 3 C) flip position 6 D) request a retransmission

Question 11

The reason a $d_{\min} = 3$ code cannot simultaneously correct 1 error and detect 2 is:

A) it has no parity-check matrix B) a double error produces a nonzero syndrome that points at a third position, so the decoder silently miscorrects C) the rate is too low D) double errors are impossible on a binary symmetric channel

Question 12

A linear code over $\mathrm{GF}(2)$ is, by definition:

A) any code whose codewords are sorted B) a subspace of $\mathrm{GF}(2)^n$ (contains $\mathbf{0}$; closed under XOR) C) a code with exactly two codewords D) a code in which every codeword has even weight

Question 13 (True/False, justify)

True or false: Adding redundancy to a code can increase its rate. Justify in one sentence.

Question 14

The Singleton bound states that for an $[n, k]$ code, $d_{\min} \le$:

A) $n - k$ B) $n - k + 1$ C) $n + k - 1$ D) $2(n - k)$

Question 15

A Reed–Solomon code beats burst errors because it:

A) flips bits faster than the channel B) counts errors in multi-bit symbols, so a long bit-burst spans only a few symbol-errors C) uses a smaller alphabet than binary D) ignores any block with more than one error

Question 16

The minimum distance of a Reed–Solomon $[n, k]$ code is exactly $n - k + 1$ because a nonzero polynomial of degree $< k$ over a field has at most $k - 1$:

A) coefficients B) terms C) roots D) evaluations

Question 17

Reed–Solomon must be defined over a true field such as $\mathrm{GF}(2^8)$, not over $\mathbb{Z}_{256}$, because $\mathbb{Z}_{256}$:

A) has too few elements B) has zero divisors, so a degree-$d$ polynomial can have more than $d$ roots and the distance bound collapses C) cannot represent bytes D) has no multiplicative identity

Question 18 (Short answer)

State the two threshold theorems as a pair: the minimum-distance condition to detect up to $t$ errors, and the condition to correct up to $t$ errors.

Question 19 (Short answer)

In the linear-algebra view, the minimum distance of a code equals the smallest number of columns of which matrix that are linearly dependent? Why does this immediately give $d_{\min}(\mathrm{Hamming}(7,4)) = 3$?

Question 20 (Short answer)

A code with minimum distance $d$ detects how many errors, and corrects how many? Give both formulas in terms of $d$.

Answer Key

Topics to review by question