Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 18:09, 31 January 2019

Revision as of 18:13, 31 January 2019

Line 28:

:<math>

\begin{align}

P & = \Pr_{\text{random }G} (\text{linear code generated by } G\text{ has distance} < d) \\[6pt]

& = \Pr_{\text{random }G} (\text{there exists a non-zero codeword } y \text{ in a linear code generated by }G\text{ such that } \operatorname{wt}(y) < d) \\[6pt]

&= \Pr_{\text{random }G} \left (\text{there exists } 0 \neq m \in \mathbb{F}_q^k \text{ such that } \operatorname{wt}(mG) < d \right )

\end{align}

Line 52:

:<math>\Pr_{\text{random }G} (mG = y) = q^{-n}</math>

Let <math>\textoperatorname{Vol}_q(r,n)</math> is a volume of Hamming ball with the radius <math>r</math>. Then:<ref>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]</ref>

: <math> P \leqslant q^k W = q^k \left ( \frac{\textoperatorname{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>

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