0
$\begingroup$

For a natural nuber $d$ there are $N=2^d-1$ non-zero vectors in $\mathbb F_2^d$. Now I take these as the columns of a $d\times N$ matrix $S$. The kernel of $S$ is then the code book for a Hamming code $c:\mathbb F_2^{N-d}\rightarrow \mathbb F_2^N$ (Is this a clear result or is there anything to prove?)

$S$ is the Syndrome, we can use it to check whether a vector $x\in\mathbb F^N$ is a code word by cheking $Sx=0$ or not.

My question is why is each of these Hamming codes a 1-error correcting-code?

$\endgroup$
1
  • $\begingroup$ By the way, I believe the word "syndrome" typically refers to $Sx$, not $S$. $\endgroup$
    – apt1002
    Nov 25, 2013 at 1:34

1 Answer 1

0
$\begingroup$

Suppose you have a valid message $x \in F_2^N$, i.e. $Sx = 0$. Suppose you modify it in one place to obtain $y$. Then $Sy = Sz$ where $z = y + x$. So we can restrict the question to messages with the form of $z$, i.e. messages which consists entirely of zeros apart from a single one.

Let the position of the error be $1 \leq n \leq N$. Then $Sz$ is a binary representation of $n$, because all the columns of $S$ are different. This allows us to find the error and correct it.

There are only $2^d$ possible values of $Sx$. One of these (zero) is interpreted as an indication that there are no errors, while the rest are interpreted as single errors. Therefore, if we receive a message with more than one error in it, we will certainly decode it incorrectly.

This proves that the code is a perfect 1-error-correcting code.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer, unfortunately I have less than 15 reputation points so I cant upvote your answer, sry. $\endgroup$
    – TI Jones
    Nov 25, 2013 at 1:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .