This chapter explores the critical role of decoding techniques in ensuring reliable communication over noisy channels. It discusses the role of various cost functions, which are essential for evaluating how closely a received signal corresponds to potential codewords. The chapter helps the reader to learn about the factors influencing the error rate of linear codes, providing a comprehensive understanding of how different parameters affect the reliability of communication. It explores advanced decoding techniques, including maximum a posteriori/maximum-likelihood (ML) decoding, reliability-based universal decoding, recursive decoding, message-passing algorithms, and tree/trellis-based search methods. Since the soft-decision ML decoding of the trivial codes is simple, a computationally efficient decoder for Reed–Muller codes can be obtained, based on computing the soft information for constituent codes and hard-decision on trivial codes.
This chapter explores the critical role of decoding techniques in ensuring reliable communication over noisy channels. It discusses the role of various cost functions, which are essential for evaluating how closely a received signal corresponds to potential codewords. The chapter helps the reader to learn about the factors influencing the error rate of linear codes, providing a comprehensive understanding of how different parameters affect the reliability of communication. It explores advanced decoding techniques, including maximum a posteriori/maximum-likelihood (ML) decoding, reliability-based universal decoding, recursive decoding, message-passing algorithms, and tree/trellis-based search methods. Since the soft-decision ML decoding of the trivial codes is simple, a computationally efficient decoder for Reed–Muller codes can be obtained, based on computing the soft information for constituent codes and hard-decision on trivial codes.
Maximum likelihood (ML) decoding is the optimal error-correction method but is NP-hard in general, implying that there would be no polynomial-time ML decoding algorithm that capable of decoding arbitrary linear codes. Consequently, researchers have developed a variety of ML decoding algorithms with different characteristics so that they can be used in a complementary manner. Although many modern codes such as Turbo, LDPC, and Polar codes, can be efficiently decoded without ML algorithms, there remains continual demand for developing new ML decoding algorithms and evaluating ML decoding performance in various contexts. In this study, we propose an ML decoding algorithm applicable to general non-binary linear codes, formulated as a generalization of the adaptive and recursive ML decoding algorithm previously developed for binary codes. The proposed algorithm is implemented and applied to Generalized Reed-Muller codes, and its computational complexity of soft-decision ML decoding is discussed and compared with the complexity of the Viterbi decoder, in terms of the number of addition-equivalent operations, to demonstrate the efficiency of the approach. The substantial reduction in decoding complexity enables us performing practical decoding simulation of some classes of Generalized Reed-Muller codes. This paper also shows numerical evaluation results of the error-correcting capabilities of the codes, providing insights into their performance under optimal decoding conditions.
The design and implementation of error correcting codes has long been informed by two fundamental results: Shannon’s 1948 capacity theorem, which established that long codes use noisy channels most efficiently; and Berlekamp, McEliece, and Van Tilborg’s 1978 theorem on the NP-completeness of decoding linear codes. These results shifted focus away from creating code-independent decoders, but recent low-latency communication applications necessitate relatively short codes, providing motivation to reconsider the development of universal decoders. We introduce a scheme for employing binarized symbol soft information within Guessing Random Additive Noise Decoding, a universal hard detection decoder. We incorporate codebook-independent quantization of soft information to indicate demodulated symbols to be reliable or unreliable. We introduce two decoding algorithms: one identifies a conditional Maximum Likelihood (ML) decoding; the other either reports a conditional ML decoding or an error. For random codebooks, we present error exponents and asymptotic complexity, and show benefits over hard detection. As empirical illustrations, we compare performance with majority logic decoding of Reed-Muller codes, with Berlekamp-Massey decoding of Bose-Chaudhuri-Hocquenghem codes, with CA-SCL decoding of CA-Polar codes, and establish the performance of Random Linear Codes, which require a universal decoder and offer a broader palette of code sizes and rates than traditional codes.
Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes
This dissertation deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. We present three new decoding algorithms: $MA\sp*D,\ H\sp*,$ and Directed Search. The first algorithm, $MA\sp*D,$ is an instance of Algorithm $A\sp*$ that conducts heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search through a code tree. $MA\sp*D$ takes into consideration more properties of the code and is considerably more efficient than the original $A\sp*$ decoding algorithm presented by Han, Hartmann, and Chen in 1993. The second algorithm, $H\sp*,$ is a new decoding algorithm that determines the value of every component of a minimum-cost codeword by estimating the cost of the minimum-cost codeword, which has a fixed value at one of the k most reliable, linearly independent bit positions. The suboptimal version of this algorithm is combined with other decoding algorithms to reduce the search space during the decoding process. The third algorithm, Directed Search, is designed to enhance the performance of soft-decision decoding by searching in continuous space. This approach explores the search space between a given vector and the received vector and finds the codeword closest to the received vector in the space explored. We also present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. It hybridizes $MA\sp*D,\ H\sp*,$ and Directed Search algorithms, utilizing their strengths to make the decoding more efficient. Simulation results for this hybrid algorithm are presented for the (104,52) binary-extended quadratic residue code and for the (128,64), the (256, 131), and the (256, 139) binary-extended BCH codes. This hybrid algorithm can efficiently decode the (104,52) binary extended quadratic residue code and the (128,64) code for any signal-to-noise ratio and has near-optimal to optimal performance. Previously, no practical decoder could decode these two codes with such a performance for all signal-to-noise ratio ranges.
We present novel decoding schemes for hard and soft decision decoding of block codes using the minimal weight codewords of the dual code. The decoding schemes will be described for cyclic codes where polynomials can be used, however, the modification for non-cyclic codes is possible and straight forward. The hard decision decoding calculates syndrome polynomials which are the product of the received polynomial with dual codewords. Proper cyclic shifts of these syndrome polynomials are obtained and the non-zero positions are counted componentwise for these shifts. The values of this counting are a reliability measure and can be used for locating the error and also the non-error positions. This reliability measure is the basis for various variants of hard decision decoding algorithms. Decoding schemes with iterative error reduction are possible as well as information set decoding using the inherent reliability information of the measure even if there is no reliability information from the channel. Further, we will show how reliability information from the channel can be included in order to obtain soft decision decoding schemes. We derive the relation between bit flipping, believe propagation, and majority logic decoding to the novel schemes. As examples to illustrate the functioning we use BCH and Reed-Muller codes as examples for binary codes, and RS codes for non-binary codes. Besides the Plotkin construction we recall a known result that Reed-Muller codes punctured by one position are cyclic and thus, are equivalent to special cases of BCH codes. Simulation results for hard and soft decision decoding will be given for several examples and compared with results from literature. Finally, we analyze the soft decision decoding of the Plotkin construction and derive that one of the two codes uses a 3 dB better channel (also known as channel polarization).
In many modern communication systems, the full benefits of error-correction coding are only realised if the decoder is able to utilise soft decision decoding. In this chapter, we give both approximate and exact bounds on the performance of soft decision decoding compared to hard decision decoding. The effects of soft decision quantisation are explored as a function of the number of quantisation levels. Examples are given of the different performance achieved using soft and quantised soft decision decoding for (100,50) and (200,100) binary codes. A modified version of the near maximum likelihood decoder, the Dorsch decoder described in Chap. 15 , is presented for hard decision decoding. The performance improvements achieved by the decoder, compared to bounded distance decoding, are evaluated for some BCH codes. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.