The complexity of error-correcting codes

DOI10.1007/BFb0036172OpenAlexW1568745098MaRDI QIDQ5055921

Daniel A. Spielman

Publication date: 9 December 2022

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0036172

zbMATH Keywords

linear codegood codeblock lengthdecoder errorouter code

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05) Decoding (94B35)

Related Items (1)

The intractability of computing the Hamming distance

Uses Software

• LDPC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Fast algorithms for the characteristic polynomial
• Ramanujan graphs
• Expander codes
• Linear-time encodable and decodable error-correcting codes
• The Computational Complexity of Continued Fractions
• A recursive approach to low complexity codes
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• On the complexity of decoding Reed-Solomon codes (Corresp.)
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
• On the complexity of decoding Goppa codes (Corresp.)
• Computational Complexity of Fourier Transforms Over Finite Fields
• On the definition of an algorithm
• Complexity of decoders--I: Classes of decoding rules
• The complexity of decoders--II: Computational work and decoding time
• Class of constructive asymptotically good algebraic codes

This page was built for publication: The complexity of error-correcting codes