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     

On multilevel block modulation codes

The multilevel technique for combining block coding and modulation is investigated. A general formulation is presented for multilevel modulation codes in terms of component codes with appropriate distance measures. A specific method for constructing multilevel block modulation codes with interdependency among component codes is proposed. Given a multilevel block modulation code C with no interdependency among the binary component codes, the proposed method gives a multilevel block modulation code C' that has the same rate as C, a minimum squared Euclidean distance not less than that of C, a trellis diagram with the same number of states as that of C, and a smaller number of nearest neighbor codewords than that of C . Finally, a technique is presented for analyzing the error performance of block modulation codes for an additive white Gaussian noise (AWGN) channel based on soft-decision maximum likelihood decoding. Error probabilities of some specific codes are evaluated by simulation and upper bounds based on their Euclidean weight distributions     

Suboptimum decoding of decomposable block codes

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length     

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     

Multilevel coded modulation for unequal error protection andmultistage decoding .I. Symmetric constellations

In this paper, theoretical upper bounds and computer simulation results on the error performance of multilevel block coded modulations for unequal error protection (UEP) and multistage decoding are presented. It is shown that nonstandard signal set partitionings and multistage decoding provide excellent UEP capabilities beyond those achievable with conventional coded modulation. The coding scheme is designed in such a way that the most important information bits have a lower error rate than other information bits. The large effective error coefficients, normally associated with standard mapping by set partitioning, are reduced by considering nonstandard partitionings of the underlying signal set. The bits-to-signal mappings induced by these partitionings allow the use of soft-decision decoding of binary block codes. Moreover, parallel operation of some of the staged decoders is possible, to achieve high data rate transmission, so that there is no error propagation between these decoders. Hybrid partitionings are also considered that trade off increased intraset distances in the last partition levels with larger effective error coefficients in the middle partition levels. The error performance of specific examples of multilevel codes over 8-PSK and 64-QAM signal sets are simulated and compared with theoretical upper bounds on the error performance     

Multidimensional trellis coded phase modulation using a multilevelconcatenation approach. I. Code design

The first part of this paper presents a simple and systematic technique for constructing multidimensional M-ary phase shift keying (MPSK) trellis coded modulation (TCM) codes. The construction is based on a multilevel concatenation approach. In which binary convolutional codes with good free branch distances are used as the outer codes and block MPSK modulation codes are used as the inner codes (or the signal spaces). Conditions on phase invariance of these codes are derived and a multistage decoding scheme for these codes is proposed. The proposed technique can be used to construct good codes for both the additive white Gaussian noise (AWGN) and fading channels as is shown in the second part of this paper     

On the iterative decoding of multilevel codes

Iterative decoding of multilevel coded modulation is discussed. Despite its asymptotic optimality with proper design, the error correcting capability of multilevel codes may not be fully exploited for finite block length with conventional multistage decoding. This fact stems from the suboptimality of multistage decoding giving rise to increased error multiplicity at lower index stages and the associated error propagation to higher stages. Such problems can be overcome in many situations by introducing iterative decoding which often significantly compensates the suboptimality of a staged decoder. The class of multilevel codes achieving practically important bit-error performance near the Shannon limit becomes far wider with iterative decoding     

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.     

Variable-bit-rate speech transmission using punctured convolutionalcodes

Rate (n-1)/n punctured convolutional codes are very effective in conjunction with embedded differential pulse code modulation (EDPCM) in variable-bit-rate speech transmission. The authors investigate the performance of this variable-bit-rate EDPCM system in terms of probability of bit error and audio signal-to-noise ratio (SNR) versus channel SNR in an additive white Gaussian noise and Rayleigh fading channel using soft-decision decoding for specific sets of code generators of punctured convolutional codes. The results show that different sets of code generators affect the performance in terms of both the probability of bit error and the audio SNR. Improvements were obtained in the cases of Gaussian nonfading and Rayleigh fading channels using soft-decision decoding     

Closest coset decoding of |u|u+v| codes

The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u|u+v| codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined     

Computing upper bounds to error probability of soft-decision decoding of Reed-Solomon codes based on the ordered statistics algorithm

This correspondence presents performance analysis of symbol-level soft-decision decoding of q-ary maximum-distance-separable (MDS) codes based on the ordered statistics algorithm. The method we present is inspired by the one recently proposed by Agrawal and Vardy (2000), who approximately evaluate the performance of generalized minimum-distance decoding. The correspondence shows that in our context, the method allows us to compute the exact value of the probability that the transmitted codeword is not one of the candidate codewords. This leads to a close upper bound on the performance of the decoding algorithm. Application of the ordered statistics algorithm to MDS codes is not new. Nevertheless, its advantages seem not to be fully explored. We show an example where the decoding algorithm is applied to singly extended 16-ary Reed-Solomon (RS) codes in a 128-dimensional multilevel coded-modulation scheme that approaches the sphere lower bound within 0.5 dB at the word error probability of 10/sup -4/ with manageable decoding complexity.     

Product coded modulation

This letter presents a technique of combining multilevel coded modulation and product coding to form product modulation codes which achieve low bit error rates with reduced decoding complexity. Three multistage decoding algorithms are presented, and good codes for both the additive white Gaussian noise (AWGN) and Rayleigh fading channels have been constructed     

Generalized tangential sphere bound on the ML decoding error probability of linear binary block codes in AWGN interference

The error probability of maximum-likelihood (ML) soft-decision decoded binary block codes rarely accepts nice closed forms. In addition, for long codes, ML decoding becomes prohibitively complex. Nevertheless, bounds on the performance of ML decoded systems provide insight into the effect of system parameters on the overall system performance as well as a measure of goodness of the suboptimum decoding methods used in practice. Using the so-called Gallager's first bounding technique (involving a so-called Gallager region) and within the framework of tangential sphere bound (TSB) of Poltyrev, we develop a general bound referred to as the generalized TSB (GTSB). The Gallager region is chosen to be a general hyper-surface of revolution (HSR) which is optimized to tighten the bound. The search for the optimal Gallager region is a classical problem dating back to Gallager's thesis in the early 1960s. For the random coding case, Gallager provided the optimal solution in a closed form while for the nonrandom case the problem has been an active area of research in information theory for many years. We prove that for a sphere code, the optimal HSR within the proposed GTSB is a hyper-cone. This will climax to the TSB of Poltyrev, one of the tightest bounds ever developed for binary block codes, and therefore terminates the search for a better Gallager region in the groundwork of the GTSB.     

Two algorithms for soft-decision decoding of reed-solomon codes, with application to multilevel coded modulations

In this paper two symbol-level soft-decision decoding algorithms for Reed-Solomon codes, derived form the ordered statistics (OS) and from the generalized minimum-distance (GMD) decoding methods, are presented and analyzed. Both the OS and the GMD algorithms are based on the idea of producing a list of candidate code words, among which the one having the larger likelihood is selected as output. We propose variants of the mentioned algorithms that allow to finely tune the size of the list in order to obtain the desired decoding complexity. The method proposed by Agrawal and Vardy for computing the error probability of the GMD algorithm is extended to our decoding methods. Examples are presented where these algorithms are applied to singly-extended Reed-Solomon codes over GF(16) used as outer codes in a 128-dimensional coded modulation scheme that attains good performance, with manageable decoding complexity.     

Power- and bandwidth-efficient communications using LDPC codes

We apply low-density parity-check (LDPC) codes to a bandwidth-efficient modulation scheme using multilevel coding, multistage decoding, and trellis-based signal shaping. Performance results based on density evolution and simulations are presented. Using irregular LDPC component codes of block length 10/sup 5/ and a 64-quadrature amplitude modulation signal constellation operating at 2 bits/dimension, a bit-error rate of 10/sup -5/ is achieved at an E/sub b//N/sub 0/ of 6.55 dB. At this value of E/sub b//N/sub 0/, the Shannon channel capacity, computed assuming equally likely signaling, is below 2 bits/dimension.     

Fast factorization architecture in soft-decision Reed-Solomon decoding

Reed-Solomon (RS) codes are among the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to its hard-decision counterpart, soft-decision decoding offers considerably higher error-correcting capability. The recent development of soft-decision RS decoding algorithms makes their hardware implementations feasible. Among these algorithms, the Koetter-Vardy (KV) algorithm can achieve substantial coding gain for high-rate RS codes, while maintaining a polynomial complexity with respect to the code length. In the KV algorithm, the factorization step can consume a major part of the decoding latency. A novel architecture based on root-order prediction is proposed in this paper to speed up the factorization step. As a result, the time-consuming exhaustive-search-based root computation in each iteration level, except the first one, of the factorization step is circumvented with more than 99% probability. Using the proposed architecture, a speedup of 141% can be achieved over prior efforts for a (255, 239) RS code, while the area consumption is reduced to 31.4%.     

Performance of sphere decoding of block codes

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary and q-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined over F_q (e.g. Reed- Solomon codes) and transmitted over q-ary symmetric channels is derived and used in the analysis.We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed.     

Multilevel coded modulation for unequal error protection andmultistage decoding. II. Asymmetric constellations

In this paper, multilevel coded asymmetric modulation with multistage decoding and unequal error protection (UEP) is discussed. These results further emphasize the fact that unconventional signal set partitionings are more promising than traditional (Ungerboeck-type) partitionings, to achieve UEP capabilities with multilevel coding and multistage decoding. Three types of unconventional partitionings are analyzed for asymmetric 8-PSK and 16-QAM constellations over the additive white Gaussian noise channel to introduce design guidelines. Generalizations to other PSK and QAM type constellations follow the same lines. Upper bounds on the bit-error probability based on union bound arguments are first derived. In some cases, these bounds become loose due to the large overlappings of decision regions associated with asymmetric constellations and unconventional partitionings. To overcome this problem, simpler and tighter approximated bounds are derived. Based on these bounds, it is shown that additional refinements can be achieved in the construction of multilevel UEP codes, by introducing asymmetries in PSK and QAM signal constellations     

New multistage decoding algorithm

A new multistage decoding (MSD) algorithm for multilevel codes is proposed. The algorithm uses several decisions in the first stage, if the difference in distance measure between the codeword found by standard MSD (SMSD) and the received word is greater than a certain threshold. An application of the algorithm for a coded modulation system shows that more than half of the coding gain of maximum likelihood decoding (MLD) of the modulation system over SMSD is achieved, with only two decisions in the first stage.<>     

A new multilevel coding method using error-correcting codes

A new multilevel coding method that uses several error-correcting codes is proposed. The transmission symbols are constructed by combining symbols of codewords of these codes. Usually, these codes are binary error-correcting codes and have different error-correcting capabilities. For various channels, efficient systems can be obtained by choosing these codes appropriately. Encoding and decoding procedures for this method are relatively simple compared with those of other multilevel coding methods. In addition, this method makes effective use of soft-decisions to improve the performance of decoding. The decoding error probability is analyzed for multiphase modulation, and numerical comparisons to other multilevel coding systems are made. When equally complex systems are compared, the new system is superior to other multilevel coding systems.