Soft Decision Decoding of Recursive Plotkin Constructions Based on Hidden Code Words

The Plotkin construction combines two codes to a code of doubled length. It can be applied recursively. The class of Reed-Muller (RM) codes is a particular example. Exploiting a property of the code words constructed by the recursive Plotkin construction, we present novel soft-decision decoders. These are based on the decoding of hidden code words which are inherent contained in the constructed code words and can be uncovered by adding particular parts of the overall code word. The main idea is to use more than one decoding variant where each variant starts with the decoding of a different hidden code word. Given the decision of this first hidden code word allows error cancellation for the remaining decoding. The final decoding decision selects the best of the decisions of the used variants. The more variants are used the closer the performance gets to the maximum-likelihood (ML) decoding performance. This is verified by an ML-bound for the cases where the ML performance is not known. The decoding algorithms use only additions, comparisons, and sign operations. Further, due to the recursive structure, only relatively short codes have to be decoded, thus, the decoding complexity is very low. We also present a new decoder for first-order RM codes with low complexity. In addition, we introduce two novel classes of half-rate codes based on recursive Plotkin constructions with RM codes. We show that the novel soft decision decoders can also be applied to recursive Plotkin constructions with BCH codes and to particular classes of generalized concatenated codes (GCC).