Codes and Algorithms for Majority Decoding
Richard E. Blahut · Cambridge University Press eBooks · 2003
Majority decoding is a method of decoding by voting that is simple to implement and is extremely fast. However, only a small class of codes can be majority decoded, and usually these codes are not as good as other codes. Because code performance is usually more important than decoder simplicity, majority decoding is not important in most applications. Nevertheless, the theory of majority-decodable codes provides another well-developed view of the subject of error-control codes. The topic of majority decoding has connections with combinatorics and with the study of finite geometries. Most known codes that are suitable for majority decoding are cyclic codes or extended cyclic codes. For these codes, the majority decoders can always be implemented as Meggitt decoders and characterized by an especially simple logic tree for examining the syndromes. Thus one can take the pragmatic view and define majority-decodable codes as those cyclic codes for which the Meggitt decoder can be put in a standard simple form. But in order to find these codes, we must travel a winding road. Reed–Muller codes Reed–Muller codes are a class of linear codes over GF (2) that are easy to describe and have an elegant structure. They are an example of a code that can be decoded by majority decoding. For these reasons, the Reed–Muller codes are important even though, with some exceptions, their minimum distances are not noteworthy. Each Reed–Muller code can be punctured to give one of the cyclic Reed–Muller codes that were studied in Section 6.7.