Gilbert–Varshamov bound for linear codes: Difference between revisions

Revision as of 16:23, 9 November 2020

Revision as of 06:50, 19 February 2021

Line 64:

==Comments==

# 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. TheA naive way that we can doapproach is to gosearch over all the generator matrices <math>G</math> of size <math>kn</math> over the field <math>\mathbb{F}_q</math> andto check if thatthe linear code hasassociated to <math>G</math> achieves the satisfiedpredicted Hamming distance. ThatThis leadsexhaustive tosearch therequires exponential timeruntime algorithmin tothe implementworst itcase.

# WeThere also haveexists a [[Las Vegas algorithm|Las Vegas construction]] that takes a random linear code and checks if this code has good Hamming distance. Nevertheless, but this construction also has thean exponential running timeruntime.

#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|journal=IEEE Transactions on Information Theory|volume=52|issue=5|pages=2218–2224|doi=10.1109/TIT.2006.872986|issn=0018-9448}}</ref>