Explore BrainMass

Binary Hamming code

1-Define the product, , of two binary vectors of the same length to be the vector whose ith component is the product of the ith components of and .
Show that wt ( + ) =wt ( ) +wt ( ) - 2wt ( ) . wt means weight.

2. Suppose that a binary Hamming code is modified by adding an additional check bit to each codeword. This additional check bit is chosen so that each resulting vector has even weight.

a) Show that this procedure yields a linear code. You can use problem 1 to solve this part.
b) What are the parameter [n, k, d] of this new code? Prove your assertions, in particular for d.
c) How many errors can this new code correct?
d) How many errors can this new code detect, but not necessarily correct?
Note: This new code is called the extended Hamming code. Can you explain this definition

Can you give a specific example to understand this problem.

Please see the attached file for the fully formatted problems.


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


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.

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

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 ...

Solution Summary

The Binary Hamming code is investigated. The solution is detailed and well presented. The response was given a rating of "5/5" by the student who originally posted the question.