Abstract
Using expander graphs, we construct a new family of asymptotically good, linear error-correcting codes. These codes have linear time sequential decoding algorithms and logarithmic time parallel decoding algorithms that use a linear number of processors. We present both randomized and explicit constructions of these codes. Experimental results demonstrate the good performance of the randomly chosen codes.
Keywords
Expander graphLinear codeDecoding methodsLuby transform codeBlock codeExpander codeComputer scienceLogarithmAlgorithmConcatenated error correction codeTurbo codeList decodingConstruct (python library)BCJR algorithmTornado codeSerial concatenated convolutional codesRaptor codeSequential decodingReed–Muller codeMathematicsTheoretical computer science
Affiliated Institutions
Related Publications
A note off two binary signaling alphabets
A generalization of Hamming's single error correcting codes is given along with a simple maximum likelihood detection scheme. For small redundancy these alphabets are unexcelled...
Channel coding with multilevel/phase signals
A coding technique is described which improves error performance of synchronous data links without sacrificing data rate or requiring more bandwidth. This is achieved by channel...
Publication Info
- Year
- 1996
- Type
- article
- Volume
- 42
- Issue
- 6
- Pages
- 1710-1722
- Citations
- 920
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
920
OpenAlex
Cite This
M. Sipser,
Daniel A. Spielman
(1996).
Expander codes.
IEEE Transactions on Information Theory
, 42
(6)
, 1710-1722.
https://doi.org/10.1109/18.556667
Identifiers
- DOI
- 10.1109/18.556667