Asymptotically optimal soft decision decoding algorithms for Hamming codes

Asymptotically optimal soft decision decoding algorithms for d = 3 and d = 4 Hamming codes are given and analysed. Only error sequences with probability exponent larger than that of maximum-likelihood decoding are corrected. Upper bounds on the block error probability for the Gaussian channel are given.     

Soft-decision decoding of binary linear block codes using reducedbreadth-first search algorithms

The article discusses soft-decision decoding of binary linear block codes using the t-algorithm and its variants. New variants of the basic algorithm are presented that reduce the decoding complexity using a threshold adaptive to the signal-to-noise ratio and address the variable decoding complexity by either limiting the memory or using a generalized M-algorithm with a nonconstant state profile     

Algebraic analog decoding of linear binary codes

Bit-by-bit soft-decision decoding of binary cyclic codes is considered. A significant reduction in decoder complexity can be achieved by requiring only that the decoder correct all analog error patterns which fall within a Euclidean sphere whose radius is equal to half the minimum Euclidean distance of the code. Such a "maximum-radius" scheme is asymptotically optimum for the additive white Gaussian noise (AWGN) channel. An iterative extension of the basic algebraic analog decoding scheme is discussed, and performance curves are given for the (17,9), (21,11), and (73,45) codes on the AWGN channel.     

Comparison of decoding algorithms of binary linear block codes inRayleigh fading channels with diversity reception

The word error probability of binary linear block codes is evaluated in Rayleigh fading channels with diversity reception for three decoding algorithms: error correction (EC), error/erasure correction (EEC), and maximum likelihood (ML) soft decoding algorithms. The performance advantage of EEC over EC in the required average SNR decreases as the number of diversity channels increases. The performance advantage of EEC over EC does not depend on the specific value of word error probability although the advantage of ML soft decoding over EC increases for lower word error probability     

On maximum likelihood soft decoding of some binary self-dual codes

Efficient algorithms are derived for maximum likelihood (ML) soft-decision decoding of some binary self-dual codes. A family of easily decodable self-dual codes is derived by modifying a known F₂₄, which has a weight distribution resembling that of the [24, 12, 8] Golay code G₂₄. The ML decoding of F₂₄ is accomplished by only 227 real additions, compared to 651 required for G₂₄, yet the error rates of the two decoders are similar for moderate noise conditions     

MAP algorithms for decoding linear block codes based onsectionalized trellis diagrams

The maximum a posterioriprobability (MAP) algorithm is a trellis-based MAP decoding algorithm. It is the heart of turbo (or iterative) decoding that achieves an error performance near the Shannon limit. Unfortunately, the implementation of this algorithm requires large computation and storage. Furthermore, its forward and backward recursions result in a long decoding delay. For practical applications, this decoding algorithm must be simplifled and its decoding complexity and delay must be reduced. In this paper, the MAP algorithm and its variation's, such as log-MAP and max-log-MAP algorithms, are first applied to sectionalized trellises for linear block codes and carried out as two-stage decodings. Using the structural properties of properly sectionalized trellises, the decoding complexity and delay of the MAP algorithms can be reduced. Computation-wise optimum sectionalizations of a trellis for MAP algorithms are investigated. Also presented in this paper are bidirectional and parallel MAP decodings     

Belief propagation decoding of Reed-Solomon codes; a bit-level soft decision decoding algorithm

In this article we propose the application of Belief Propagation (BP) algorithm as a novel bit-level soft decision decoding (SDD) technique for Reed-Solomon (RS) codes. A brief tutorial on Belief Propagation algorithm is presented. A central issue in the application of BP algorithm to decoding RS codes is the construction of a sparse parity check matrix for the binary image of the code. It is demonstrated that Vardy's technique may be applied to find a sparse parity check matrix for RS codes. However, this technique is not applicable to all cases. The BP algorithm is applied to two test codes. In one case, simulation models show that the BP algorithm outperforms the hard decision Euclidean decoding by more than 2 dB of additional coding gain. The results with the second test code are not as promising.     

Maximum likelihood soft decoding of binary block codes and decodersfor the Golay codes

Maximum-likelihood soft-decision decoding of linear block codes is addressed. A binary multiple-check generalization of the Wagner rule is presented, and two methods for its implementation, one of which resembles the suboptimal Forney-Chase algorithms, are described. Besides efficient soft decoding of small codes, the generalized rule enables utilization of subspaces of a wide variety, thereby yielding maximum-likelihood decoders with substantially reduced computational complexity for some larger binary codes. More sophisticated choice and exploitation of the structure of both a subspace and the coset representatives are demonstrated for the (24, 12) Golay code, yielding a computational gain factor of about 2 with respect to previous methods. A ternary single-check version of the Wagner rule is applied for efficient soft decoding of the (12, 6) ternary Golay code     

Two decoding algorithms for tailbiting codes

The paper presents two efficient Viterbi decoding-based suboptimal algorithms for tailbiting codes. The first algorithm, the wrap-around Viterbi algorithm (WAVA), falls into the circular decoding category. It processes the tailbiting trellis iteratively, explores the initial state of the transmitted sequence through continuous Viterbi decoding, and improves the decoding decision with iterations. A sufficient condition for the decision to be optimal is derived. For long tailbiting codes, the WAVA gives essentially optimal performance with about one round of Viterbi trial. For short- and medium-length tailbiting codes, simulations show that the WAVA achieves closer-to-optimum performance with fewer decoding stages compared with the other suboptimal circular decoding algorithms. The second algorithm, the bidirectional Viterbi algorithm (BVA), employs two wrap-around Viterbi decoders to process the tailbiting trellis from both ends in opposite directions. The surviving paths from the two decoders are combined to form composite paths once the decoders meet in the middle of the trellis. The composite paths at each stage thereafter serve as candidates for decision update. The bidirectional process improves the error performance and shortens the decoding latency of unidirectional decoding with additional storage and computation requirements. Simulation results show that both proposed algorithms effectively achieve practically optimum performance for tailbiting codes of any length.     

一种基于Chase的RS码代数软判决译码算法

为了提高RS码的纠错性能,本文提出了一种基于Chase的代数软判决译码算法,称为Chase-ASD.该算法充分利用了接收比特的可信度信息,但运算复杂度较高.针对该算法运算复杂度高的问题,本文进一步给出了简化的Chase-ASD算法.仿真结果表明,提出的Chase-ASD和简化的Chase-ASD算法均可比原ASD算法提供更多的译码增益.     

Graph-based iterative decoding algorithms for parity-concatenatedtrellis codes

We construct parity-concatenated trellis codes in which a trellis code is used as the inner code and a simple parity-check code is used as the outer code. From the Tanner-Wiberg-Loeliger (1981, 1996) graph representation, several iterative decoding algorithms can be derived. However, since the graph of the parity-concatenated code contains many short cycles, the conventional min-sum and sum-product algorithms cannot achieve near-optimal decoding. After some simple modifications, we obtain near-optimal iterative decoders. The modifications include either (a) introducing a normalization operation in the min-sum and sum-product algorithms or (b) cutting the short cycles which arise in the iterative Viterbi algorithm (IVA). After modification, all three algorithms can achieve near-optimal performance, but the IVA has the least average complexity. We also show that asymptotically maximum-likelihood (ML) decoding and a posteriori probability (APP) decoding can be achieved using iterative decoders with only two iterations. Unfortunately, this asymptotic behavior is only exhibited when the bit-energy-to-noise ratio is above the cutoff rate. Simulation results show that with trellis shaping, iterative decoding can perform within 1.2 dB of the Shannon limit at a bit error rate (BER) of 4×10^-5 for a block size of 20000 symbols. For a block size of 200 symbols, iterative decoding can perform within 2.1 dB of the Shannon limit     

用于Turbo迭代译码的近似Log-MAP算法研究

本文运用逼近论,研究Log-MAP算法的近似算法.本文提出了校正函数的一阶、二阶和三阶逼近多项式,并对近似式的逼近精度进行了分析和比较.本文将近似Log-MAP算法用于WCDMA turbo译码器中,对译码器在AWGN信道和平坦慢衰落信道上的纠错性能进行了仿真.仿真结果表明：一阶近似Log-MAP算法将Max-Log-MAP turbo译码器的纠错性能改进了0.2~0.3dB,二阶及三阶近似Log-MAP算法与原Log-MAP算法性能等价,优于Max-Log-MAP 算法0.3~0.5dB.     

Efficient decoding algorithms for generalized Reed-Muller codes

Previously, a class of generalized Reed-Muller (RM) codes has been suggested for use in orthogonal frequency-division multiplexing. These codes offer error correcting capability combined with substantially reduced peak-to mean power ratios. A number of approaches to decoding these codes have already been developed. Here, we present low complexity, suboptimal alternatives which are inspired by the classical Reed decoding algorithm for binary RM codes. We simulate these new algorithms along with the existing decoding algorithms using additive white Gaussian noise and two-path fading models for a particular choice of code. The simulations show that one of our new algorithms outperforms all existing suboptimal algorithms and offers performance that is within 0.5 dB of maximum-likelihood decoding, yet has complexity comparable to or lower than existing decoding approaches     

Bounds on the decoding error probability of binary linear codes viatheir spectra

Bounds on the error probability of maximum likelihood decoding of a binary linear code are considered. The bounds derived use the weight spectrum of the code and they are tighter than the conventional union bound in the case of large noise in the channel. The bounds derived are applied to a code with an average spectrum, and the result is compared to the random coding exponent. The author shows that the bound considered for the binary symmetrical channel case coincides asymptotically with the random coding bound. For the case of AWGN channel the author shows that Berlekamp's (1980) tangential bound can be improved, but even this improved bound does not coincide with the random coding bound, although it can be very close to it     

Inversionless decoding of binary BCH codes

The iterative algorithm for decoding binary BCH codes presented by Berlekamp and, in an alternative form, by Massey is modified to eliminate inversion. Because inversion in a finite field is time consuming and requires relatively complex circuitry, this new algorithm should he useful in practical applications of multiple-error-correcting binary BCH codes.     

Errors-and-erasures decoding of binary majority-logic-decodable codes

The decoder of a binary majority-logic decodable code can be modified to enable the correction of erasures as well as errors. The changes required in both type-I and type-II decoders are described and compared in terms of increases in decoder complexity and internal clock rates.     

Parallel decoding of binary BCH codes

A parallel decoding procedure for the BCH codes is introduced, which is particularly useful for decoding BCH codes with small error-correcting capability. The high regularity inherent in the scheme enable it to be easily implemented with VLSI circuits.<>     

An adaptive two-stage algorithm for ML and sub-ML decoding of binary linear block codes

Two distinct codeword-searching procedures based on iterative bounded-distance decoding (BDD) are combined to form an adaptive two-stage maximum-likelihood (ML) decoder for binary linear block codes. During the first stage of the algorithm, a tight upper bound on an error likelihood metric ("discrepancy") is established iteratively for the ML codeword. First-stage processing requires sorting and storage. Adaptive switching to the second stage removes the sorting and storage requirements and allows to rule out redundant BDDs efficiently. Second-stage processing accounts for all codewords with discrepancy lower bound below the upper bound of the ML codeword and guarantees ML performance. In addition, the proposed two-stage algorithm is inherently tunable for controlled suboptimum operation. Under sub-ML operation, the overall scheme can be interpreted as a generalization of the Chase (1972) algorithm. Simulation studies for the (24,12,8) extended Golay and the (64,30,14) and (128,64,22) extended Bose-Chaudhuri-Hocquenghem (BCH) codes illustrate and support these theoretical developments.     

Soft decision decoding of Reed-Solomon codes

This paper presents a maximum-likelihood decoding (MLD) and a suboptimum decoding algorithm for Reed-Solomon (RS) codes. The proposed algorithms are based on the algebraic structure of the binary images of RS codes. Theoretical bounds on the performance are derived and shown to be consistent with simulation results. The proposed suboptimum algorithm achieves near-MLD performance with significantly lower decoding complexity. It is also shown that the proposed suboptimum, algorithm has better performance compared with generalized minimum distance decoding, while the proposed MLD algorithm has significantly lower decoding complexity than the well-known Vardy-Be'ery (1991) MLD algorithm.