Iterative Decoding of Classical Codes
We have developed a new method to decode intermediate length multi-step majority logic decodable (MSMLD) codes. The most famous in this class of codes are the Reed-Muller codes, which were introduced in the 1950's, and found many applications in the 1960's. MSMLD codes have typically been decoded using a very simple (sub-optimal) decoding algorithm, but they have inferior minimum distance properties when compared with BCH codes, which have now largely eclipsed them.
Background & Objective: By improving the MSMLD decoding algorithms to more closely resemble the iterative decoding algorithms that are successful with turbo-codes and low-density parity check (LDPC) codes, we have been able to improve their performance to the point where they surpass BCH codes (decoded in the standard way) on the binary symmetric channel, at least for low and moderate signal to noise ratios. In fact, in the intermediate blocklength regime, our decoding algorithms give the best known performance for rate 1/2 codes on the binary symmetric channel.
Technical Discussion: Our algorithm is a simple three-state bit-flipping algorithm. We use highly redundant parity check matrices to represent MSMLD codes. Bits decide whether they should agree with their received value, disagree, or abstain from making a decision, based on the number of parity checks that they belong to which "vote" in the various directions. For an MSMLD code of blocklength 255 and rate 1/2, we are able to decode within a few tenths of a decibel of optimal maximum likelihood decoding, and we can demonstrate that we outperform standard decoding of BCH codes down to word error rates of about one in ten trillion.
Outside Collaborations: Marc Fossorier (University of Hawaii) and Ravi Palanki (Caltech)
Contact: Jonathan Yedidia
| Technical Reports: | |
| Sparse Factor Graph Representations of Reed-Solomon and Related Codes | |
| Iterative Decoding of Multi-step Majority Logic Decodable Codes | |
| Representing Codes for Belief Propagation Decoding | |
Technology Area: Digital Communications
Modification Date: September 12, 2007
