Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 00:42, 29 May 2011

Revision as of 00:44, 29 May 2011

Line 37:

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_Pr}_{\text{Randomrandom }G} [\text{there exists a vector }m \in \mathbb{F}_q^k \backslash \{ 0\}\text{ such that }wt(mG) < d]</math>

By [[Boole's inequality]], we have:

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

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

Denote <math>\Delta(m_1,m_2)</math> be a Hamming distance of two messages <math>m_1</math> and <math>m_2</math>

Line 51:

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

: <math>W = \sum\limits_{\text{all }y \in \mathbb{F}_q^n \text{s.t. }\Delta (0,y) \le d - 1} {{\Pr_Pr}_{\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_Pr}_{\text{random }G} [mG = y] = q^{ - n}</math>

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