Expander codes
Michael Sipser, Daniel A. Spielman · IEEE Transactions on Information Theory · 1996
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.
Cited by 931 works. doi:10.1109/18.556667
Authors
References
- The Design and Analysis of Computer Algorithms
- The Theory of Error-Correcting Codes
- Low-Density Parity-Check Codes
- A recursive approach to low complexity codes
- Eigenvalues and expanders
- Ramanujan graphs
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Linear-time encodable and decodable error-correcting codes
- Explicit Concentrators from Generalized N -Gons
- Explicit construction of linear sized tolerant networks