Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 22:10, 31 August 2016

Revision as of 04:44, 1 September 2016

Line 36:

</math>

The last equality follows from the definition: if a 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>.

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

Line 42:

: <math>P \leqslant \sum_{0 \neq m \in \mathbb{F}_q^k} \Pr_{\text{random }G} (wt(mG) < d)</math>

Now for a given message <math>0 \neq m \in \mathbb{F}_q^k,</math> we want to compute

:<math>W = \Pr_{\text{random }G} (wt(mG) < d).</math>

Line 50:

: <math>W = \sum_{\{y \in \mathbb{F}_q^n |\Delta (0,y) \leqslant d - 1\}} \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_{\text{random }G} (mG = y) = q^{ - n}</math>

Line 75:

==References==

{{Reflist}}

# [http://www.cse.buffalo.edu/~atri/courses/coding-theory/ Lecture 11: Gilbert–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]