Multistage decoding of multilevel block M-PSK modulationcodes and its performance analysis

Multistage decoding of multilevel block multilevel phase-shift keying (M-PSK) modulation codes for the additive white Gaussian noise (AWGN) channel is investigated. Several types of multistage decoding, including a suboptimum soft-decision decoding scheme, are devised and analyzed. Upper bounds on the probability of an incorrect decoding of a code are derived for the proposed multistage decoding schemes. Error probabilities of some specific multilevel block 8-PSK modulation codes are evaluated and simulated. The computation and simulation results for these codes show that with multistage decoding, significant coding gains can be achieved with large reduction in decoding complexity. In one example, it is shown that the difference in performance between the proposed suboptimum multistage soft-decision decoding and the single-stage optimum decoding is small, only a fraction of a dB loss in SNR at the block error probability of 10^-6     

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.     

A concatenated coded modulation scheme for error control

A concatenated coded modulation scheme is presented for error control in data communications. The scheme is achieved by concatenating a Reed-Solomon outer code and a bandwidth efficient block inner code for M-ary phase-shift keying (PSK) modulation. Error performance of the scheme is analyzed for an additive white Gaussian noise (AWGN) channel. It is shown that extremely high reliability can be attained by using a simple M-ary PSK modulation inner-code and a relatively powerful Reed-Solomon outer code. Furthermore, if an inner code of high effective rate is used, the bandwidth expansion required by the scheme due to coding will be greatly reduced. The scheme is particularly effective for high-speed satellite communications for large file transfer where high reliability is required. A simple method is also presented for constructing block codes for M-ary PSK modulation. Soome short M-ary PSK codes with good minimum squared Euclidean distance are constructed. These codes have trellis structure and hence can be decoded with a soft-decision Viterbi decoding algorithm. Furthermore, some of these codes are phase invariant under multiples of 45° rotation     

Noncoherent block-coded MPSK

For coherent detection, block-coded modulation is a bandwidth efficient scheme. In this paper, we propose theorems about the error performance of block-coded modulation using M-ary phase-shift keying (MPSK) for noncoherent detection. Based on these theorems, we propose a novel block-coded modulation scheme for noncoherent detection called noncoherent block-coded MPSK. The proposed scheme provides flexible designs of noncoherent block codes with different code rate, block length and error performance. Good noncoherent block codes can be easily obtained by properly choosing binary linear block codes as the component codes. Moreover, noncoherent block codes of this new scheme can be decoded by multistage decoding, which has the advantage of low complexity and satisfactory error performance. In this paper, two algorithms of multistage decoding for noncoherent detection are proposed as well. The error performance of some designed codes and decoding algorithms is verified by computer simulation.     

Soft-decision list decoding of hermitian codes

This paper proposes the first complete soft-decision list decoding algorithm for Hermitian codes based on the Koetter- Vardy's Reed-Solomon code decoding algorithm. For Hermitian codes, interpolation processes trivariate polynomials which are defined over the pole basis of a Hermitian curve. In this paper, the interpolated zero condition of a trivariate polynomial with respect to a multiplicity matrix M is redefined followed by a proof of the validity of the soft-decision scheme. This paper also introduces a new stopping criterion for the algorithm that tranforms the reliability matrix ? to the multiplicity matrix M. Geometric characterisation of the trivariate monomial decoding region is investigated, resulting in an asymptotic optimal performance bound for the soft-decision decoder. By defining the weighted degree upper bound of the interpolated polynomial, two complexity reducing modifications are introduced for the soft-decision scheme: elimination of unnecessary interpolated polynomials and pre-calculation of the coefficients that relate the pole basis monomials to the zero basis functions of a Hermitian curve. Our simulation results and analyses show that soft-decision list decoding of Hermitian code can outperform Koetter-Vardy decoding of Reed-Solomon code which is defined in a larger finite field, but with less decoding complexity.     

Bit-error probability for maximum-likelihood decoding of linearblock codes and related soft-decision decoding methods

In this correspondence, the bit-error probability P_b for maximum-likelihood decoding of binary linear block codes is investigated. The contribution P_b(j) of each information bit j to P_b is considered and an upper bound on P_b(j) is derived. For randomly generated codes, it is shown that the conventional approximation at high SNR P_b≈(d_H/N).P_s, where P_s represents the block error probability, holds for systematic encoding only. Also systematic encoding provides the minimum P_b when the inverse mapping corresponding to the generator matrix of the code is used to retrieve the information sequence. The bit-error performances corresponding to other generator matrix forms are also evaluated. Although derived for codes with a generator matrix randomly generated, these results are shown to provide good approximations for codes used in practice. Finally, for soft-decision decoding methods which require a generator matrix with a particular structure such as trellis decoding, multistage decoding, or algebraic-based soft-decision decoding, equivalent schemes that reduce the bit-error probability are discussed. Although the gains achieved at practical bit-error rates are only a fraction of a decibel, they remain meaningful as they are of the same orders as the error performance differences between optimum and suboptimum decodings. Most importantly, these gains are free as they are achieved with no or little additional circuitry which is transparent to the conventional implementation     

Soft-decision decoding of Reed-Muller codes as generalized multipleconcatenated codes

Constructs Reed-Muller codes by generalized multiple concatenation of binary block codes of length 2. As a consequence of this construction, a new decoding procedure is derived that uses soft-decision information. The algorithm is designed for low decoding complexity and is applicable to all Reed-Muller codes. It gives better decoding performance than soft-decision bounded-distance decoding. Its decoding complexity is much lower than that of maximum-likelihood trellis decoding of Reed-Muller codes, especially for long codes     

基于校验子的Turbo乘积码仿真研究

针对Turbo乘积码译码延时的问题,提出一种基于校验子的Turbo乘积码译码算法(S-TPC),该算法根据校验子的值采取不同方式对每行(列)进行译码,节省了一部分校验子为0的码字的硬判决译码运算量。仿真结果表明,S-TPC(32,26)在迭代4次时,能在不降低译码性能的情况下,减少近50%的计算量。     

A modified concatenated coding scheme, with applications tomagnetic data storage

When a block modulation code is concatenated with an error-correction code (ECC) in the standard way, the use of a modulation code with long block lengths results in error propagation. This article analyzes the performance of modified concatenation, which involves reversing the order of modulation and the ECC. This modified scheme reduces the error propagation, provides greater flexibility in the choice of parameters, and facilitates soft-decision decoding, with little or no loss in transmission rate. In particular, examples are presented which show how this technique can allow fewer interleaves per sector in hard disk drives, and permit the use of more sophisticated block modulation codes which are better suited to the channel     

Fast generalized minimum-distance decoding of algebraic-geometryand Reed-Solomon codes

Generalized minimum-distance (GMD) decoding is a standard soft-decoding method for block codes. We derive an efficient general GMD decoding scheme for linear block codes in the framework of error-correcting pairs. Special attention is paid to Reed-Solomon (RS) codes and one-point algebraic-geometry (AG) codes. For RS codes of length n and minimum Hamming distance d the GMD decoding complexity turns out to be in the order O(nd), where the complexity is counted as the number of multiplications in the field of concern. For AG codes the GMD decoding complexity is highly dependent on the curve in consideration. It is shown that we can find all relevant error-erasure-locating functions with complexity O(o₁nd), where o₁ is the size of the first nongap in the function space associated with the code. A full GMD decoding procedure for a one-point AG code can be performed with complexity O(dn²)     

Multilevel trellis MPSK modulation codes for the Rayleigh fadingchannel

The multilevel coding technique is used for constructing multilevel trellis M-ary phase-shift-keying (MPSK) modulation codes for the Rayleigh fading channel. In the construction of a code, all the factors which affect the code performance and its decoding complexity are considered. The error performance of some of these codes based on both one-stage optimum decoding and multistage suboptimum decoding has been simulated. The simulation results show that these codes achieve good error performance with small decoding complexity     

Reduced Complexity Interpolation Architecture for Soft-Decision Reed–Solomon Decoding

Reed-Solomon (RS) codes are one of the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to hard-decision decoding, soft-decision decoding offers considerably higher error-correcting capability. The Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain, while maintaining a complexity polynomial with respect to the code word length. In the KV algorithm, the interpolation step dominates the decoding complexity. A reduced complexity interpolation architecture is proposed in this paper by eliminating the polynomial updating corresponding to zero discrepancy coefficients in this step. Using this architecture, an area reduction of 27% can be achieved over prior efforts for the interpolation step of a typical (255, 239) RS code, while the interpolation latency remains the same     

Block error correcting codes using finite-field wavelet transforms

This paper extends the popular wavelet framework for signal representation to error control coding. The primary goal of the paper is to use cyclic finite-field wavelets and filter banks to study arbitrary-rate L-circulant codes. It is shown that the wavelet representation leads to an efficient implementation of the block code encoder and the syndrome generator. A formulation is then given for constructing maximum-distance separable (MDS) wavelet codes using frequency-domain constraints. This paper also studies the possibility of finding a wavelet code whose tail-biting trellis is efficient for soft-decision decoding. The wavelet method may provide an easy way to look for such codes.     

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     

Applications of algebraic soft-decision decoding of Reed-Solomon codes

Efficient soft-decision decoding of Reed-Solomon (RS) codes is made possible by the Koetter-Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami-Sudan (GS) list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate RS(255,239) code, 2-3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored, which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queueing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required.     

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.     

Interlevel‐correlated orthogonal space–time block codes based on the expanded signal constellation

Orthogonal space–time block codes provide full diversity with a very simple decoding scheme. However, they do not provide much coding gain. For a given space–time block code, we combine several component codes in conjunction with set partitioning of the expanded signal constellation according to the coding gain distance (CGD) criterion. By providing proper interlevel coding between adjacent blocks, we can design an orthogonal space–time block code with high rate, large coding gain, and low decoding complexity. The error performance of an example code is compared with some codes in computer simulation. These codes are compared based on the situation of the same transmission rate, space diversity order, and state complexity of decoding trellis. Copyright © 2010 John Wiley & Sons, Ltd.     

Exponential error bounds for algebraic soft-decision decoding of Reed-Solomon codes

Algebraic soft-decision decoding of Reed-Solomon codes is a promising technique for exploiting reliability information in the decoding process. While the algorithmic aspects of the decoding algorithm are reasonably well understood and, in particular, complexity is polynomially bounded in the length of the code, the performance analysis has relied almost entirely on simulation results. Analytical exponential error bounds that can be used to tightly bound the performance of Reed-Solomon codes under algebraic soft-decision decoding are presented in this paper. The analysis is used in a number of examples and several extensions and consequences of the results are presented.     

Applications of Algebraic Soft-Decision Decoding of Reed–Solomon Codes

Efficient soft-decision decoding of Reed–Solomon codes is made possible by the Koetter–Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami–Sudan list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate (RS 9225,239) Reed–Solomon code, 2–3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queuing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required.     

Soft-decision decoding applied to the generalized type-II hybridARQ scheme

A generalized hybrid automatic-repeat-request (GH-ARQ) scheme using hard-decision decoding and variable depth (redundancy) for adaptive error control in digital communications systems has recently been proposed by S.D. Morgera and H. Krishna (see Digital Signal Processing over Finite Fields: Applications to Communications and Algebraic Coding Theories. New York: Academic, 1988). An important feature of the GH-ARQ scheme is that variable depth and, consequently, variable minimum distance, is possible with a single encoder/decoder configuration. The present authors use binary PSK signaling, an additive white Gaussian noise (AWGN) channel, and several relevant code parameter choices in computer simulations to illustrate the improvement in throughput efficiency when soft-decision decoding is used in the GH-ARQ method. From the computational complexity standpoint, the use of GH-ARQ soft-decision decoding is feasible, since the code lengths used are relatively short. Comparison of simulation results is also made to the soft-decision ARQ scheme of G. Benelli (see ibid., vol.COM-33, p.285-8, Mar. 1985)