Improved Nearly-MDS Expander Codes

DOI10.1109/TIT.2006.878232MaRDI QIDQ3548010zbMATH OpenOpenAlexFDO

Authors Ron M. Roth, Vitaly Skachek

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0601090

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Source coding (94A29) Decoding (94B35)

Abstract: A construction of expander codes is presented with the following three properties: (i) the codes lie close to the Singleton bound, (ii) they can be encoded in time complexity that is linear in their code length, and (iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace MDS outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for a significantly smaller alphabet size.

Recommendations

• Expander codes
• Codes from Expander Graphs
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• On expander codes
• Concatenated Codes: Serial and Parallel

Cited in

(9)

• Linear time decoding of regular expander codes
• Linear-time decoding of regular expander codes
• Bounds on the minimum code distance for nonbinary codes based on bipartite graphs
• The minimum distance of graph codes
• On the extendibility of near-MDS elliptic codes
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• scientific article; zbMATH DE number 515917 (Why is no real title available?)
• A combination of testability and decodability by tensor products
• Improving the Alphabet-Size in Expander-Based Code Constructions

This page was built for publication: Improved Nearly-MDS Expander Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548010)