Expander codes

M. Sipser, Daniel A. Spielman

IEEE Transactions on Information Theory · 1996 · 942 citations · 14 references

Concepts

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.

References

14