Long Nonbinary Codes Exceeding the Gilbert - Varshamov Bound for any Fixed Distance

2004/06/21 by Sergey Yekhanin, Yekhanin, Sergey, Ilya Dumer +1 · 1 citation
Computer Science · #Coding theory and cryptography #Cooperative Communication and Network Coding #Error Correcting Code Techniques

paper · pdf · doi:10.48550/arxiv.cs/0406039

Abstract

Let A(q,n,d) denote the maximum size of a q-ary code of length n and distance d. We study the minimum asymptotic redundancy ρ(q,n,d)=n-log_q A(q,n,d) as n grows while q and d are fixed. For any d and q<=d-1, long algebraic codes are designed that improve on the BCH codes and have the lowest asymptotic redundancy ρ(q,n,d) <= ((d-3)+1/(d-2)) log_q n known to date. Prior to this work, codes of fixed distance that asymptotically surpass BCH codes and the Gilbert-Varshamov bound were designed only for distances 4,5 and 6.

Cited by

• Bounds on Codes Correcting Transpositions of Consecutive Symbols

Related

• Nonlinear Codes with Low Redundancy
• A generalisation of the Gilbert-Varshamov bound and its asymptotic evaluation
• Asymptotically optimal constant weight codes with even distance
• Proof of tightness of Varshamov - Gilbert bound for binary codes
• An Upper Bound on the Minimum Distance of LDPC Codes over GF(q)