Author :
Sipser, M. ; Spielman, Daniel A.
Author_Institution :
Dept. of Math., MIT, Cambridge, MA, USA
fDate :
11/1/1996 12:00:00 AM
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 :
error correction codes; graph theory; linear codes; random processes; sequential decoding; asymptotically good linear error-correcting codes; expander codes; expander graphs; explicit constructions; linear time sequential decoding algorithms; logarithmic time parallel decoding algorithms; randomized constructions; randomly chosen codes; Algorithm design and analysis; Bipartite graph; Circuits; Computational modeling; Decoding; Error correction codes; Fault tolerance; Graph theory; Linear code; Parity check codes;
Journal_Title :
Information Theory, IEEE Transactions on
