1
$\begingroup$

Question 1

Consider a repetition code to detect $m$ errors. What is the smallest repetition parameter $k$ (i.e., the number of repetitions per bit) it should be used so that the code can always detect $m$ errors?

To be clear I know that you need $k=2m+1$ to correct errors, I am asking what is $k$ if you only want to detect errors. I know the answer is $m+1$.

I read some articles about Hamming codes but I didn't understand the explanation. I also read this post but it wasn't helpful enough: Hamming distance required for error detection and correction

Question 2

Let a code make 3 repetitions and add a parity bit to the message. For example, $1010$ is encoded as $111 \; 000 \; 111 \; 000 \; 0$. How many (maximum) errors can this code identify? How many can it fix?

(The answer is fix one and identify three but I don't understand why.)

$\endgroup$

1 Answer 1

1
$\begingroup$
  • Question 1: Suppose $k$ is fixed. Then, if any group of repeated $k$ bits is flipped, the error is not detected, so we need $k \ge m + 1$. On the other hand, if $k = m + 1$, then any combination of $m$ errors will be detected because at least $k$ bits must be flipped (i.e, the whole group of $k$ repetitions) in order to arrive at a valid code word.
  • Question 2: The reasoning is similar. One bit errors can be fixed because of the parity bit. Two bit errors cannot because flipping the parity bit and any other repetition bit yields a word $w'$ with Hamming distance $2$ from the original code word $w$; from it, flipping the other two repetition bits yields a valid code word $w''$ which also has Hamming distance $2$ to $w'$, so the error cannot be corrected. The argument for identifying up to three errors is similar: at least four bits must be flipped to arrive at $w''$ from $w$ (as before), and anything less than that will not yield a valid code word.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.