Binary Hamming code

Solution Preview

---

Please see the attached file for the complete solution.
Thanks for using BrainMass.

1) Say we have a binary vector x of length n, then we define the weight of the
vector as simply the number of ones in the vector:

Now say we have 2 binary vectors x and y what is (here is addition modulo 2)

Let means complement i.e. and then

But

So
Where x*y means the vector whose ith entry is

Hamming Codes

Recall some facts about linear block codes.
We take our original source vector x and construct a codeword out of it, y

Vectors y and x are related by: where G is the generator matrix.

The matrix G is said to be in standard form if it looks like:

Where is the k by k identity matrix.
P is a matrix that is (n-k) by k.

Now define the parity check matrix, H (which is n by (n-k)):

Recall that Hy=0 if and only if y is a code word, this is very useful.

Well those are linear block codes, what are binary Hamming codes?
Well in a binary Hamming code all the columns of H are filled with all the distinct nonzero binary vectors. They are characterized by the number s=n-k (the height of H), e.g.

s=2
s=3
s=4
Hopefully you can see that in the last example every possible non zero 4 bit vector is present in the columns of H. But also there is still the identity matrix at the far right hand side.

How wide is H? Well it contains all non zero s length vectors, there are such vectors, but we ignore the all zero vector so the width of H is , but the width of H is n so

by definition
so

Now what properties does a binary Hamming code have?
It's only useful as a code if you can correct errors that may occur in the transmission of the codeword. If you receive a vector, you would compare it to all the codewords and see which one was 'closest' and then pick that one and work out what the original source was. Looking at where all the code words are, you will realize that the likeliest place were you could 'incorrectly' decode a vector is where the code ...