Efficiently Decodable Low-Rate Codes Meeting Gilbert-Varshamov Bound

摘要

We demonstrate a probabilistic construction of binary linear codes meeting the Gilbert-Varshamov bound (with overwhelming probability) for rates up to about 10~(-4), together with polynomial time algorithms to perform encoding and decoding up to half the distance. This is the first such result (for some positive rate) with polynomial decoding complexity; previously a similar result (up to rate about 0.02) was known with sub-exponential time decoding (Zyablov and Pinsker, 1981).