In coding theory, the bound of parameters such as rate R, relative distance, block length, etc. is usually concerned. Here Gilbert–Varshamov bound theorem claims the lower bound of the rate of the general code. Gilbert–Varshamov bound is the best in terms of relative distance for codes over alphabets of size less than 49.
Contents
Gilbert–Varshamov bound theorem
Theorem: LetHere
The above result was proved by Edgar Gilbert for general code using the greedy method as here. For linear code, Rom Varshamov proved using the probabilistic method for the random linear code. This proof will be shown in the following part.
High-level proof:
To show the existence of the linear code that satisfies those constraints, the probabilistic method is used to construct the random linear code. Specifically the linear code is chosen randomly by choosing the random generator matrix
Formal proof:
By using the probabilistic method, to show that there exists a linear code that has a Hamming distance greater than
We know that the linear code is defined using the generator matrix. So we use the "random generator matrix"
Recall that in a linear code, the distance equals the minimum weight of the non-zero codeword. Let
The last equality follows from the definition: if a codeword
By Boole's inequality, we have:
Now for a given message
Let
Due to the randomness of
Let
By choosing
Finally
Comments
- The Varshamov construction above is not explicit; that is, it does not specify the deterministic method to construct the linear code that satisfies the Gilbert–Varshamov bound. The naive way that we can do is to go over all the generator matrices
G of sizek n over the fieldF q - We also have a Las Vegas construction that takes a random linear code and checks if this code has good Hamming distance. Nevertheless, this construction has the exponential running time.