The complexity of error-correcting codes

DOI10.1007/BFB0036172MaRDI QIDQ5055921zbMATH OpenOpenAlexFDO

Authors 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

block lengthdecoder errorgood codelinear codeouter code

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3616338
• scientific article; zbMATH DE number 2011836
• scientific article; zbMATH DE number 512984
• A note on the decoding complexity of error-correcting codes
• Complexity of constructing codes with specified correction properties
• Kolmogorov complexity and the asymptotic bound for error-correcting codes
• scientific article; zbMATH DE number 1284420
• The decodability and correctability of codes
• A computability challenge: asymptotic bounds for error-correcting codes
• On the structure of optimal error-correcting codes

Cites work

• A Mathematical Theory of Communication
• A recursive approach to low complexity codes
• Class of constructive asymptotically good algebraic codes
• Complexity of decoders--I: Classes of decoding rules
• Computational Complexity of Fourier Transforms Over Finite Fields
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Expander codes
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Fast algorithms for the characteristic polynomial
• scientific article; zbMATH DE number 3146798 (Why is no real title available?)
• scientific article; zbMATH DE number 52032 (Why is no real title available?)
• scientific article; zbMATH DE number 53945 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3607492 (Why is no real title available?)
• scientific article; zbMATH DE number 1263215 (Why is no real title available?)
• scientific article; zbMATH DE number 3437021 (Why is no real title available?)
• scientific article; zbMATH DE number 1559526 (Why is no real title available?)
• scientific article; zbMATH DE number 1559531 (Why is no real title available?)
• scientific article; zbMATH DE number 1559532 (Why is no real title available?)
• scientific article; zbMATH DE number 3251924 (Why is no real title available?)
• scientific article; zbMATH DE number 3397423 (Why is no real title available?)
• Linear-time encodable and decodable error-correcting codes
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
• On the complexity of decoding Goppa codes (Corresp.)
• On the complexity of decoding Reed-Solomon codes (Corresp.)
• On the definition of an algorithm
• Ramanujan graphs
• The complexity of decoders--II: Computational work and decoding time
• The Computational Complexity of Continued Fractions

Cited in

(8)

• Complexity of constructing codes with specified correction properties
• Linear-time encodable and decodable error-correcting codes
• Endcoding Complexity Versus Minimum Distance
• On the Trustworthiness of Error-Correcting Codes
• scientific article; zbMATH DE number 2011836 (Why is no real title available?)
• The intractability of computing the Hamming distance
• Almost-catalytic computation
• A note on the decoding complexity of error-correcting codes

Describes a project that uses

Uses Software

• LDPC

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

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