Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 01:07, 9 May 2011

Revision as of 05:49, 9 May 2011

Line 20:

We know that the linear code is defined using the [[generator matrix]]. So we use the "random generator matrix" <math>G</math> as a mean to describe the randomness of the linear code. So a random generator matrix <math>G</math> of size <math>kn</math> contains <math>kn</math> elements which are chosen independently and uniformly over the field <math>\mathbb{F}_q</math>.

Recall that in a linear code, the distance = the minimum weight of the non-zero codeword. This fact is one of the [[Linear_codeLinear code|properties of linear code]].

Denote <math>wt(y)</math> be the weight of the codeword <math>y</math>.

Line 29:

Therefore <math>P = Pr_{Random G}</math> [there exists a [[vector]] <math>m \in \mathbb{F}_q^k \backslash \{ 0\}</math> such that <math>wt(mG)</math> < <math>d</math>]

By [[Booles_inequalityBooles inequality|Union Bound]], we have:

<math>P \le \sum\limits_{m \in \mathbb{F}_q^k \backslash \{ 0\} } {Pr_{random\;G} } [wt(mG)</math> < <math>d</math>]

Line 52:

(The later inequality comes from [http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf the upper bound of the Volume of Hamming ball])

Then

Line 67 ⟶ 66:

# 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 <math>G</math> of size <math>kn</math> over the field <math>\mathbb{F}_q</math> and check if that linear code has the satisfied Hamming distance. That leads to the exponential time algorithm to implement it.

# We also have a [[Las_Vegas_algorithmLas Vegas algorithm|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.

==See Alsoalso==

# [http://en.wikipedia.org/wiki/Gilbert%E2%80%93Varshamov_bound Gilbert-Varshamov bound due to Gilbert construction for the general code]

# [[Hamming_boundHamming bound|Hamming Bound]]

# [http://en.wikipedia.org/wiki/Probabilistic_method Probabilistic method]

Line 79 ⟶ 78:

# [http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/ Coding Theory's Notes: Gilbert-Varshamov Bound. Venkatesan �Guruswami]

[[Category:Error Detection and Correction Code]]

{{Uncategorized|date=May 2011}}