Gilbert-Varshamov bound

Question 1

Gilbert-Varshamov bound

Answer 1

There exists a binary linear code of length n, with at most m linearly independent parity checks and minimum distance at least d, if

1 + (n−1 1) + … + (n−1 d−2) < 2m

For large n, the Gilbert-Varshamov bound indicates that good codes exist, but there is no known practical way of constructing such codes. It is also not known if long binary codes can have distances greater than indicated by the Gilbert-Varshamov bound. Short codes can have better minimum distances.

Question 2

Binary Hamming code

Answer 2

A binary Hamming code is a code whose parity check matrix has all nonzero binary m-vectors as columns.
So the length of a binary Hamming code is 2^m − 1 and the dimension is 2^m − 1 − m, since it is clear that the parity check matrix has rank m. The minimum distance is at least 3.
The columns can be ordered in different ways, a convenient method is to represent the natural numbers from 1 to 2^m − 1 as binary m-tuples.

Question 3

Extended Binary Hamming code

Answer 3

An extended binary Hamming code is obtained by adding a zero column to the parity check matrix of a Hamming code and then adding a row of all 1s.