Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 06:10, 5 November 2019

Revision as of 17:21, 3 December 2019

Line 66:

# 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–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.

#For sufficiently large non-prime q and for certain ranges of the variable δ, the Gilbert-Varshamov bound is improved by the [[Tsfasman-Vladut-Zink bound]].<ref>{{Cite journal|last=Stichtenoth|first=H.|date=2006|title=Transitive and self-dual codes attaining the Tsfasman-Vla/spl breve/dut$80-Zink bound|url=http://ieeexplore.ieee.org/document/1624655/|journal=IEEE Transactions on Information Theory|volume=52|issue=5|pages=2218–2224|doi=10.1109/TIT.2006.872986|issn=0018-9448|via=}}</ref>

==See also==