Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 19:18, 26 May 2011

Revision as of 05:39, 27 May 2011

Line 1:

In [[coding theory]], the bound of parameters such as rate <math>''R</math>'', relative distance, [[block length]], etc. is usually concerned. Here [[Gilbert-VarshamovGilbert–Varshamov bound|Gilbert-VarshamovGilbert–Varshamov Boundbound Theoremtheorem]] claims the lower bound of the rate of the general code. More interestingly, Gilbert-VarshamovGilbert–Varshamov bound is the best in term of relative distance for codes over alphabets of size less than 49.

==Gilbert–Varshamov bound theorem==

==Gilbert-Varshamov Bound Theorem==

'''Theorem:''' Let <math>q \ge 2</math>. For every <math>0 \le \delta </math> < <math> 1 - \frac{1}{q}</math>, and 0 < <math> \varepsilon \le 1 - H_q (\delta )</math>, there exists a code with rate <math>R \ge 1 - H_q (\delta ) - \varepsilon </math>, and relative distance <math>\delta</math>.

Line 8:

<math>H_q(x) = xlog_q(q-1)-xlog_qx-(1-x)log_q(1-x)</math>.

The above result was proved by [[Edgar Gilbert]] for general code using the [[greedy method]] as [[Gilbert-VarshamovGilbert–Varshamov bound|here]]. For [[linear code]], Varshamov proved using the [[probabilistic method]] for the random linear code. This proof will be shown in the following part.

'''''High level proof:'''''

Line 27:

Also if codeword <math>y</math> belongs to a linear code generated by <math>G</math>, then <math>y = mG</math> for some vector <math>m \in \mathbb{F}_q^k</math>.

Therefore <math>P = \Pr_{\text{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 [[BoolesBoole's inequality|Union Bound]], we have:

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

Now for a given message <math>m \in \mathbb{F}_q^k \backslash \{ 0\}</math>, we want to compute <math>W = Pr_{Random\;G} [wt(mG)</math> < <math>d]</math>

Line 41:

Using this fact, we can come up with the following equality:

: <math>W = \sum\limits_{all\;text{all }y \in \mathbb{F}_q^n \text{s.t.\; }\Delta (0,y) \le d - 1} {\Pr_{random\;text{random }G} [mG = y]}</math>

Due to the randomness of <math>G</math>, <math>mG</math> is a uniformly random vector from <math>\mathbb{F}_q^n</math>.

So <math>\Pr_{random\;text{random }G} [mG = y] = q^{ - n}</math>

Let <math>Vol_q\text{Vol}_q(r,n)</math> is a Volumevolume of Hamming ball with the radius <math>r</math>. Then:

: <math>W = \frac{Vol_q\text{Vol}_q(d-1,n)}{q^n} \le \frac{Vol_q\text{Vol}_q(\delta n,n)}{q^n} \le \frac{q^{nH_q(\delta)}}{q^n}</math>

(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])

Line 55:

Then

: <math> P \le q^k \cdot W \le q^k \frac{q^{nH_q(\delta)}}{q^n} = q^k q^{-n(1-H_q(\delta))}</math>

By choosing <math>k = (1-H_q(\delta)-\varepsilon)n</math>, the above inequality becomes

: <math> P \le q^{-\varepsilon n}</math>

Finally <math>q^{ - \varepsilon n} \ll 1</math>, which is exponentially small in n, that is what we want before. Then by the probabilistic method, there exists a linear code <math>C</math> with relative distance <math>\delta</math> and rate <math>R</math> at least <math>(1-H_q(\delta)-\varepsilon)</math>, which completes the proof.

Line 65:

==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-VarshamovGilbert–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 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 also==

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

# [[Hamming bound|Hamming Bound]]

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

==References==

# [http://www.cse.buffalo.edu/~atri/courses/coding-theory/ Lecture 11: Gilbert-VarshamovGilbert–Varshamov Bound. Coding Theory Course. Professor Atri Rudra]

# [http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf Lecture 9: Bounds on the Volume of Hamming Ball. Coding Theory Course. Professor Atri Rudra]

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

[[Category:Coding theory]]