Generalization of chase algorithms for soft decision decoding of binary linear codes

Soft decision decoding of binary linear block codes transmitted over the additive white Gaussian channel (AWGN) using antipodal signaling is considered. A set of decoding algorithms called generalized Chase algorithms is proposed. In contrast to Chase algorithms, which require alfloor (d- 1)/2 rfloorbinary error-correcting decoder for decoding a binary linear block code of minimum distanced, the generalized Chase algorithms can use a binary decoder that can correct less thanlfloor ( d - 1)/2 rfloorhard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. The performance of all proposed algorithms is asymptotically optimum for high signal-to-noise ratio (SNR). Simulation results for the(47, 23)quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.     

Asymptotic optimality of the GMD and Chase decoding algorithms

The generalized minimum distance (GMD) and Chase (1972) decoding algorithms are some of the most important suboptimum bounded distance decoding algorithms for binary linear block codes over an additive white Gaussian noise (AWGN) channel. We compute the limitation of the ratio between the probability of decoding error for the GMD or any one of the Chase decoding algorithms and that of the maximum-likelihood (ML) decoding when the signal-to-noise ratio (SNR) approaches infinity. If the minimum Hamming distance of the code is greater than 2, the limitation is shown to be equal to 1 and thus the GMD and Chase decoding algorithms are asymptotically optimum.     

A CASCADABLE PRAGMATIC BLOCK DECODING ALGORITHM EXPLOITING CHANNEL MEASUREMENT INFORMATION

The complexity of algorithms to perform soft decision decoding on block codes has impeded their inclusion in practical systems. A well-known class of algorithms for decoding block codes utilizing channel measurement information along with the algebraic properties of the code are the Chase algorithms.¹ In this paper a decoding method similar to Chase's third algorithm is presented. However, in this method, a single test pattern or alternate codeword makes up one stage of the decoder. The method uses information from the previous decoding(s) to assist in generating a test pattern. This single stage ‘Second Chance Algorithm’ can then be extended to a ‘Third Chance Algorithm’ (and beyond) to enhance performance. The method does not invoke the hard decision decoder as often as the Chase algorithms.     

Chase-type and GMD coset decodings

In this letter, Chase decoding algorithms are generalized into a family of bounded distance decoding algorithms, so that the conventional Chase algorithm-2 and Chase algorithm-3 become the two extremes of this family. Consequently, more flexibility in the tradeoffs between error performance and decoding complexity is provided by this generalization, especially for codes with large minimum distance. Finally this approach is extended to decoding with erasures     

Turbo乘积码译码算法的简化

Chase算法是Turbo乘积码(TPC)软判决译码中常采用的算法之一。分析了传统Chase算法中寻找竞争码字对译码复杂度的影响,在此基础上提出了两种新的简化译码算法,省去了寻找竞争码字的过程。仿真结果表明,简化算法在基本保持传统Chase算法译码性能的基础上,降低了译码复杂度,提高了译码速度。     

On algebraic soft-decision decoding algorithms for BCH codes

Three algebraic soft-decision decoding algorithms are presented for binary Bose-Chaudhuri-Hocquengham (BCH) codes. Two of these algorithms are based on the bounded distance (BD)+1 generalized minimum-distance (GMD) decoding presented by Berlekamp (1984), and the other is based on Chase (1972) decoding. A simple algebraic algorithm is first introduced, and it forms a common basis for the decoding algorithms presented. Next, efficient BD+1 GMD and BD+2 GMD decoding algorithms are presented. It is shown that, for binary BCH codes with odd designed-minimum-distance d and length n, both the BD+1 GMD and the BD+2 GMD decoding algorithms can be performed with complexity O(nd). The error performance of these decoding algorithms is shown to be significantly superior to that of conventional GMD decoding by computer simulation. Finally, an efficient algorithm is presented for Chase decoding of binary BCH codes. Like a one-pass GMD decoding algorithm, this algorithm produces all necessary error-locator polynomials for Chase decoding in one run     

Geometrical and performance analysis of GMD and Chase decodingalgorithms

The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N_0,eff=N₀+N _BDD. Where NBDD denotes the number of additional, non-codeword, neighbors that are generated during the (suboptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original generalized minimum distance (GMD) and Chase (1972) decoding algorithms. After careful examination of the decision regions of these algorithms, we derive an approximated probability ratio between the error contribution of a noncodeword neighbor (one of N_BDD points) and a codeword nearest neighbor. For Chase algorithm 1 it is shown that the contribution to the error probability of a noncodeword nearest neighbor is a factor of 2^d-1 less than the contribution of a codeword, while for Chase algorithm 2 the factor is 2^[d/2]-1, d being the minimum Hamming distance of the code. For Chase algorithm 3 and GMD, a recursive procedure for calculating this ratio, which turns out to be nonexponential in d, is presented. This procedure can also be used for specifically identifying the error patterns associated with Chase algorithm 3 and GMD. Utilizing the probability ratio, we propose an improved approximated upper bound on the probability of error based on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations     

Codage en quadrature simplifié et son décodage à décisions souples

We present an improved version of quadrature coding as applied to quadrature amplitude modulation and an analysis of its performance using first hard-decision decoding, then soft-decision decoding. We propose in the latter case a new algorithm which derives from the Chase algorithm but uses a threshold on the decision reliability in order to reduce its complexity. This complexity, measured by the number of translations effected, decreases as the signal-to-noise ratio increases. It approaches the hard decoding complexity while keeping a large gain with respect to it. The performance of this algorithm in terms of the threshold setting is analysed and confirmed by simulation.     

Adaptive Chase algorithm for block turbo codes

A new adaptive implementation of the Chase algorithm for binary block codes is proposed. Compared to the two efficiently used algorithms for iterative decoding, the standard Chase and Kaneko algorithms, the proposed algorithm can give the same performance with significant complexity reduction.     

Error performance analysis for reliability-based decodingalgorithms

The statistical approach proposed by Agrawal and Vardy (see ibid., vol.46, no.1, p.60-83, 2000) to evaluate the error performance of the generalized minimum distance (GMD) decoding is extended to other reliability-based decoding algorithms for binary linear block codes, namely Chase (1972) type, combined GMD and Chase type, and order statistic decoding (OSD). In all cases, tighter and simpler bounds than those previously proposed have been obtained with this approach     

Pattern-Flipping Chase-Type Decoders with Error Pattern Extracting Viterbi Algorithm over Partial Response Channels

Towards the goal of achieving better error correction performance in data storage systems, iterative soft decoding of low density parity check (LDPC) codes and soft-decision decoding of Reed-Solomon (RS) codes have started receiving increasing research attention. However, even with increased computing power, complexities of soft-decision decoding algorithms are still too high for real products which require high throughput and small hardware area. Another problem is that the performance gains of those approaches are smaller for magnetic recording channels than they are for memoryless additive white Gaussian noise (AWGN) channels. We propose a new soft-decision decoding algorithm (based on the Chase algorithm), which takes advantage of pattern reliability instead of symbol reliability or bit reliability. We also present a modified Viterbi algorithm that provides probable error patterns with corresponding reliabilities. Simulation results of the proposed algorithms over the partial response (PR) channel show attractive performance gains. The proposed algorithm dramatically reduces the number of iterations compared to the conventional Chase2 algorithm over the PR channel.     

Generalized threshold chase algorithms

 Three generalized threshold Chase algorithms called GTC Ⅰ,GTC Ⅱ and STC are proposed in this paper.They are the combination of the generalized minimum distance(GMD)decoding algorithm with the Chase algorithm.Although the decoding error probabilities of these algorithms are very close to that of the Chase algorithm,the decoding speeds are faster,especially at higher signal-to-noise ratio(SNR),hence they are of greater practical value.The results of computer simulations are given,showing the advantages of these algorithms.     

广义门限蔡斯算法

本文提出了三种广义的门限蔡斯算法:GTC Ⅰ、GTC Ⅱ和 STC。这些算法是广义最小距离译码(GMD)算法与蔡斯算法的结合,它们的译码错误概率与蔡斯算法的非常接近,但译码速度要快,特别当信噪比高时更是如此,因而有较大的实用价值。文中最后给出了计算机模拟结果,证实了这些算法的优越性。     

On Combining Chase‐2 and Sum‐Product Algorithms for LDPC Codes

This letter investigates the combination of the Chase‐2 and sum‐product (SP) algorithms for low‐density parity‐check (LDPC) codes. A simple modification of the tanh rule for check node update is given, which incorporates test error patterns (TEPs) used in the Chase algorithm into SP decoding of LDPC codes. Moreover, a simple yet effective approach is proposed to construct TEPs for dealing with decoding failures with low‐weight syndromes. Simulation results show that the proposed algorithm is effective in improving both the waterfall and error floor performance of LDPC codes.     

An efficient maximum-likelihood-decoding algorithm for linear blockcodes with algebraic decoder

A new soft decoding algorithm for linear block codes is proposed. The decoding algorithm works with any algebraic decoder and its performance is strictly the same as that of maximum-likelihood-decoding (MLD). Since our decoding algorithm generates sets of different candidate codewords corresponding to the received sequence, its decoding complexity depends on the received sequence. We compare our decoding algorithm with Chase (1972) algorithm 2 and the Tanaka-Kakigahara (1983) algorithm in which a similar method for generating candidate codewords is used. Computer simulation results indicate, for some signal-to-noise ratios (SNR), that our decoding algorithm requires less average complexity than those of the other two algorithms, but the performance of ours is always superior to those of the other two     

Fast Chase algorithm with an application in turbo decoding

Turbo product codes (TPCs) provide an attractive alternative to recursive systematic convolutional (RSC)-based turbo systems. Rather than employ trellis-based decoders, an algebraic decoder may be repeatedly employed in a low-complexity, soft-input/soft-output errors-and-erasures decoder such as the Chase algorithm. Taking motivation from efficient forced erasure decoders, this implementation re-orders the Chase algorithm's repeated decodings such that the inherent computational redundancy is greatly reduced without degrading performance. The result is a highly efficient fast Chase implementation. The algorithm presented here is principally applicable to single error-correcting codes although consideration is also given to the more general case. The new decoder's value in practical turbo schemes is demonstrated via application to decoding of the (64,57,4) extended Hamming TPC     

自适应量化测试序列数的分组Turbo码译码算法

针对分组Turbo码自适应Chase译码算法存在的缺陷,该文提出自适应量化测试序列数的分组Turbo码译码算法。该方法以测试序列数C为研究对象,依出错概率大小选择错误图样,并利用量化测试函数根据SNR的变化对测试序列数进行量化,从而达到直接控制译码复杂度的目的。仿真结果表明,所提出的译码算法保证了译码性能,并直接降低了译码复杂度。     

一种快速软判决译码的研究

本文给出一种分组码快速软判决译码—可变门限Chase算法(VTC).采用人工智能搜索技术—A^*算法,快速生成试探序列集合,并利用已经试探译码的信息,对试探序列集合进行分类,生成试探序列的等价类及其代表,并用最优门限对候选码字进行最佳测试,可实现快速软判决译码.模拟计算表明,与已有的软判决译码算法相比,该算法的译码速度更快而译码性能完全相同.     

Near-optimum decoding of product codes: block turbo codes

This paper describes an iterative decoding algorithm for any product code built using linear block codes. It is based on soft-input/soft-output decoders for decoding the component codes so that near-optimum performance is obtained at each iteration. This soft-input/soft-output decoder is a Chase decoder which delivers soft outputs instead of binary decisions. The soft output of the decoder is an estimation of the log-likelihood ratio (LLR) of the binary decisions given by the Chase decoder. The theoretical justifications of this algorithm are developed and the method used for computing the soft output is fully described. The iterative decoding of product codes is also known as the block turbo code (BTC) because the concept is quite similar to turbo codes based on iterative decoding of concatenated recursive convolutional codes. The performance of different Bose-Chaudhuri-Hocquenghem (BCH)-BTCs are given for the Gaussian and the Rayleigh channel. Performance on the Gaussian channel indicates that data transmission at 0.8 dB of Shannon's limit or more than 98% (R/C>0.98) of channel capacity can be achieved with high-code-rate BTC using only four iterations. For the Rayleigh channel, the slope of the bit-error rate (BER) curve is as steep as for the Gaussian channel without using channel state information     

Systematic redundant residue number system codes: analytical upper bound and iterative decoding performance over AWGN and Rayleigh channels

The novel family of redundant residue number system (RRNS) codes is studied. RRNS codes constitute maximum-minimum distance block codes, exhibiting identical distance properties to Reed-Solomon codes. Binary to RRNS symbol-mapping methods are proposed, in order to implement both systematic and nonsystematic RRNS codes. Furthermore, the upper-bound performance of systematic RRNS codes is investigated, when maximum-likelihood (ML) soft decoding is invoked. The classic Chase algorithm achieving near-ML soft decoding is introduced for the first time for RRNS codes, in order to decrease the complexity of the ML soft decoding. Furthermore, the modified Chase algorithm is employed to accept soft inputs, as well as to provide soft outputs, assisting in the turbo decoding of RRNS codes by using the soft-input/soft-output Chase algorithm.