# Code book for Hamming Code

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?

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

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.