This paper presents a stochastic method for soft decision decoding of binary linear block codes. An efficient algorithm is developed and investigated based on a special nonlinear regression model. Numerical results using BCH codes and turbo codes with code dimension up to 191 are considered.
Iterative decoding methods have gained interest, initiated by the results of the so-called "turbo" codes. The theoretical description of this decoding, however, seems to be difficult. Therefore, we study the iterative decoding of block codes. First, we discuss the iterative decoding algorithms developed by Gallager (1962), Battail et al. (1979), and Hagenauer et al. (1996). Based on their results, we propose a decoding algorithm which only uses parity check vectors of minimum weight. We give the relation of this iterative decoding to one-step majority-logic decoding, and interpret it as gradient optimization. It is shown that the used parity check set defines the region where the iterative decoding decides on a particular codeword. We make plausible that, in almost all cases, the iterative decoding converges to a codeword after some iterations. We derive a computationally efficient implementation using the minimal trellis representing the used parity check set. Simulations illustrate that our algorithm gives results close to soft decision maximum likelihood (SDML) decoding for many code classes like BCH codes. Reed-Muller codes, quadratic residue codes, double circulant codes, and cyclic finite geometry codes. We also present simulation results for product codes and parallel concatenated codes based on block codes.
In this paper we present an efficient new soft-decision decoding algorithm suitable to be applied to any binary cyclic codes. The idea behind our decoding algorithm is the exploitation of the cyclic property available on the most popular linear block codes which are cyclic codes. Numerical results for the proposed algorithm are presented; the plotted curves show that the performances of our decoder are relatively better than the performances of OSD-1 (Ordered Statistic Decoding) and Chase type II algorithm.
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.
The authors present a novel and efficient maximum-likelihood soft-decision decoding algorithm for linear block codes. The approach used here converts the decoding problem into a search problem through a graph that is a trellis for an equivalent code of the transmitted code. A generalized Dijkstra's algorithm, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to reduce drastically the search space and to make the decoding efforts of this decoding algorithm adaptable to the noise level. For example, for most real channels of the 35 000 samples tried, simulation results for the (128,64) binary extended BCH code show that the proposed decoding algorithm is fifteen orders of magnitude more efficient in time and in space than that proposed by Wolf (1978). Simulation results for the (104, 52) binary extended quadratic residue code are also given.>
This paper presents an approach to soft-decision decoding for a (n, k) binary linear block code. This approach achieves near-optimal to optimal performance for any signal-to-noise ratio value. The proposed decoding is based on the reordering of the received symbols according to their reliability measure and can be applied to any binary linear code. The basic idea is to generate a sequence of codewords such that there will be a high probability that the next codeword is closer to the received vector. In this algorithm the information provided by the soft-decisions is used to generate information sets utilized in decoding. A fast procedure checks whether a given set of k positions is an information set. A sequence of codewords is reconstructed using a sequence of information sets. Each codeword reconstructed is compared with the received word and the closest one is selected. Hence, the decoding algorithm is an iterative procedure designed to enhance the performance of the usual soft-decision decoding, since with each iteration of the procedure, real vectors successively closer to the received vector are examined. A high performance stop rule is utilized to reduce the number of generated information sets, stopping the decoding process when a codeword is closest to the received sequence.
Based on the notion of supercodes, we propose a two-phase maximum-likelihood (ML) soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the priority-first search algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees to find the ML decision with a constant complexity per information bit at high signal-to-noise ratios (SNRs). Simulations on the extended BCH code of n = 64 and k = 24 show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive ML decoding [1] when the SNR per information bit is 8 dB.