Expander Codes

We present a new class of asymptotically good, linear error-correcting codes based upon expander graphs. These codes have linear time sequential decoding algorithms, logarithmic time parallel decoding algorithms with a linear number of processors, and are simple to understand. We present both randomized and explicit constructions for some of these codes. Experimental results demonstrate the extremely good performance of the randomly chosen codes. >

Authors

• Michael Sipser
• Daniel A. Spielman

Keywords

• Graph theory
• Decoding
• Error correction codes
• Encoding
• Mathematics
• Contracts
• Laboratories
• Ear
• CD recording
• Satellites
• Expander Codes
• Random Graph
• Forward Error Correction
• Log Time
• Parallel Algorithm
• Linear Code
• Explicit Construction
• Decoding Algorithm
• Degree Of Variability
• Minimum Distance
• Constant Factor
• Linear Time
• Mapping Process
• Linear Constraints
• Graph Construction
• Greater Expansion
• Regular Graphs
• Low-density Parity-check Codes
• N Log N
• Family Of Codes
• Even Parity
• Efficient Decoding