|
==Gilbert–Varshamov bound theorem==
:'''Theorem:''' Let <math>q \geqslant 2</math>. For every <math>0 \leqslant \delta < 1 - \tfrac{1}{q}</math> and <math>0 < \varepsilon \leqslant 1 - H_q (\delta ),</math> there exists a <math>q</math>-ary linear code with rate <math>R \geqslant 1 - H_q (\delta ) - \varepsilon </math> and relative distance <math>\delta.</math>
Here <math>H_q</math> is the ''q''-ary entropy function defined as follows:
: <math>H_q(x) = x\log_q(q-1)-x\log_qx-(1-x)\log_q(1-x).</math>
The above result was proved by [[Edgar Gilbert]] for general codecodes using the [[greedy method]] as [[Gilbert–Varshamov bound|here]]. For [[linear code]], [[Rom Varshamov]] proved usingrefined the [[probabilisticresult method]]to forshow the randomexistence of a linear code. ThisThe proof will be shown inuses the following[[probabilistic partmethod]].
'''''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 choosingpicking the [[random generator|random]]a generator matrix <math>G \in \mathbb{F}_q^{k \times n}</math> inwhose whichentries theare element israndomly chosen uniformlyelements over the fieldof <math>\mathbb{F}_q^n </math>. AlsoThe theminimum [[Hamming distance]] of thea linear code is equal to the minimum weight of thea [[Codenonzero word (communication)|codeword]]., Soso in order to prove that the linear code generated by <math>G</math> has Hammingminimum distance <math>d</math>, weit willsuffices to show that for any <math>m \in \mathbb{F}_q^k \smallsetminus \left\{ 0 \right\}, \operatorname{wt}(mG) \ge d</math> . ToWe prove that, wewill prove the opposite one; that is, the probability that thethere linearexists codea generatednonzero bycodeword <math>G</math>of has the Hamming distanceweight less than <math>d</math> is exponentially small in <math>n</math>. Then by the probabilistic method, there exists thea linear code satisfying the theorem.
'''''Formal proof:'''''
By using the probabilistic method, to show that there exists a linear code that has a Hamming distance greater than <math>d</math>, we will show that the [[probability]] that the random linear code having the distance less than <math>d</math> is exponentially small in <math>n</math>.
We know that theThe linear code is defined usingby theits [[generator matrix]]., Sowhich we usechoose theto "randombe generatora matrix"random <math>Gk \times n</math> asgenerator amatrix; meanthat to describe the randomness of the linear code. Sois, 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 equals the minimum weight of thea non-zerononzero codeword. Let <math>\operatorname{wt}(y)</math> be the weight of the codeword <math>y</math>. So
:<math>
:<math>\Pr_{\text{random }G} (mG = y) = q^{-n}</math>
Let <math>\operatorname{Vol}_q(r,n)</math> isbe athe volume of a [[Hamming ball]] with the radius <math>r</math>. Then:<ref>The later inequality comes from [httphttps://www.cse.buffalo.edu/~faculty/atri/courses/coding-theory/lectures/lect9.pdf the upper bound of the Volume of Hamming ball] {{Webarchive|url=https://web.archive.org/web/20131108081414/http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect9.pdf |date=2013-11-08 }}</ref>
: <math> P \leqslant q^k W = q^k \left ( \frac{\operatorname{Vol}_q(d-1,n)}{q^n} \right ) \leqslant q^k \left ( \frac{q^{nH_q(\delta)}}{q^n} \right ) = q^k q^{-n(1-H_q(\delta))}</math>
| 