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.     

Performance evaluation of superorthogonal turbo codes in AWGN andflat Rayleigh fading channels

Turbo codes are parallel concatenated codes whose performance in the additive white Gaussian noise (AWGN) channel has been shown to be near the theoretical limit. In this paper, we describe a low-rate superorthogonal turbo code that combines the principles of low-rate convolutional coding and that of parallel concatenation. Due to the bandwidth expansion, this code outperforms the ordinary turbo code both in AWGN and especially in fading channels. Thus, superorthogonal turbo codes are suited mainly for spread-spectrum applications. For the purposes of iterative decoding, we concisely describe the connection between the optimal maximum a posteriori symbol estimation and suboptimal soft-output decoding based on sequence estimation. The suboptimal decoder produces outputs that can directly be used as additive metrics at successive decoding iterations, without the need for estimating channel noise variance. Simulation results in AWGN and flat Rayleigh fading channels are also presented, along with analytical upper bounds of bit- and frame-error probabilities     

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.     

A Decoding Algorithm for Turbo Product Codes Using Optimality Test and Amplitude Clipping

This paper presents an iterative soft-input/soft-output (SISO) decoderfor product code using optimality test and amplitude clipping. A modifiedexpression for computing the soft-output of SISO decoder is proposed.The correlation discrepancy is employed to provide an optimality teston the decision codeword. The optimality test is performed in rowand column decoding to evaluate the reliability of row and columndecision codewords. Based on the optimality test, the variable reliabilityfactor is introduced for optimization of turbo decoding. A stoppingcriterion with very little performance degradation is also designedfor turbo decoding of product codes by using the optimality test.Besides, the amplitude clipping is employed to improve the performanceof turbo product code. Simulation results on the performance of theintroduced SISO decoder are presented.     

A soft-input soft-output APP module for iterative decoding ofconcatenated codes

Concatenated coding schemes consist of the combination of two or more simple constituent encoders and interleavers. The parallel concatenation known as “turbo code” has been shown to yield remarkable coding gains close to theoretical limits, yet admitting a relatively simple iterative decoding technique. The recently proposed serial concatenation of interleaved codes may offer superior performance to that of turbo codes. In both coding schemes, the core of the iterative decoding structure is a soft-input soft-output (SISO) a posteriori probability (APP) module. In this letter, we describe the SISO APP module that updates the APP's corresponding to the input and the output bits, of a code, and show how to embed it into an iterative decoder for a new hybrid concatenation of three codes, to fully exploit the benefits of the proposed SISO APP module     

Design and decoding of optimal high-rate convolutional codes

This correspondence deals with the design and decoding of high-rate convolutional codes. After proving that every (n,n-1) convolutional code can be reduced to a structure that concatenates a block encoder associated to the parallel edges with a convolutional encoder defining the trellis section, the results of an exhaustive search for the optimal (n,n-1) convolutional codes is presented through various tables of best high-rate codes. The search is also extended to find the "best" recursive systematic convolutional encoders to be used as component encoders of parallel concatenated "turbo" codes. A decoding algorithm working on the dual code is introduced (in both multiplicative and additive form), by showing that changing in a proper way the representation of the soft information passed between constituent decoders in the iterative decoding process, the soft-input soft-output (SISO) modules of the decoder based on the dual code become equal to those used for the original code. A new technique to terminate the code trellis that significantly reduces the rate loss induced by the addition of terminating bits is described. Finally, an inverse puncturing technique applied to the highest rate "mother" code to yield a sequence of almost optimal codes with decreasing rates is proposed. Simulation results applied to the case of parallel concatenated codes show the significant advantages of the newly found codes in terms of performance and decoding complexity.     

Application of efficient Chase algorithm in decoding of generalized low-density parity-check codes

We consider the iterative decoding of generalized low-density (GLD) parity-check codes where, rather than employ an optimal subcode decoder, a Chase (1972) algorithm decoder more commonly associated with "turbo product codes" is used. GLD codes are low-density graph codes in which the constraint nodes are other than single parity-checks. For extended Hamming-based GLD codes, we use bit error rates derived by simulation to demonstrate this new strategy to be successful at higher code rates. For long block lengths, good performance close to capacity is possible with decoding costs reduced further since the Chase decoder employed is an efficient implementation.     

Refinements and asymptotic performance of bandwidth-efficient turbo product codes

In this letter, a turbo product code (TPC) is combined with multilevel modulations (8-phase-shift keying and 16-quadrature amplitude modulation). The component codes are Bose-Chaudhuri-Hocquengem (BCH) or extended BCH. We derive soft-input/soft-output modules based on the dual code, with exact Euclidean metrics, and we show that the iterative TPC decoder gains no advantage in performance from this. Next, we evaluate asymptotic approximations for maximum-likelihood (ML) decoding from a combinatorial approach that can be applied to any bit-interleaved multilevel modulated code, once the first term (or terms) of the Hamming weight spectrum are known. For the TPCs and modulations studied in this letter, random bit interleaving before modulation leads to improved ML asymptotes. Simulations confirm that this advantage is maintained also under iterative decoding.     

An efficient decoding algorithm for block turbo codes

An efficient soft-input soft-output iterative decoding algorithm for block turbo codes (BTCs) is proposed. The proposed algorithm utilizes Kaneko's (1994) decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decisions using reliability calculations. Three different schemes for reliability calculations incorporating different levels of approximation are suggested. The algorithm proposed here presents a major advantage over existing decoding algorithms for BTCs by providing ample flexibility in terms of performance-complexity tradeoff. This makes the algorithm well suited for wireless multimedia applications. The algorithm can be used for optimal as well as suboptimal decoding. The suboptimal versions of the algorithm can be developed by changing a single parameter (the number of error patterns to be generated). For any performance, the computational complexity of the proposed algorithm is less than the computational complexity of similar existing algorithms. Simulation results for the decoding algorithm for different two-dimensional BTCs over an additive white Gaussian noise channel are shown. A performance comparison of the proposed algorithm with similar existing algorithms is also presented     

Serial concatenation of interleaved convolutional codes andM-ary continuous phase modulations

We consider the serial concatenation of a convolutional code and a continuous phase modulation separated by a random interleaver. It is shown that the continuous phase modulator has the same behavior as a recursive systematic convolutional code in serial turbo codes. The interleaver gain produced by the modulator and the random interleaving depends only on the minimum Hamming distance of the outer code. A soft-input soft-output detection algorithm is described and applied in an iterative joint detection-decoding scheme. Simulated performance over Gaussian and Rayleigh channels shows a dramatic gain over both uncoded modulation and classic detection cases.     

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     

Reduced-Complexity Turbo Equalization for Turbo Coded MIMO/OFDM Systems

1IntroductionTowards wireless systems Beyondthe3G(B3G),it isa great challenge for the physical layer to support high-speed transmissioninthe mobile environment to providecomfortable Internet access.Multiple Input MultipleOutput(MI MO)technique is effectiv…     

Low-Complexity High-Rate Reed--Solomon Block Turbo Codes

This letter considers high-rate block turbo codes (BTC) obtained by concatenation of two single-error-correcting Reed-Solomon (RS) constituent codes. Simulation results show that these codes perform within 1 dB of the theoretical limit for binary transmission over additive white Gaussian noise with a low-complexity decoder. A comparison with Bose-Chaudhuri-Hocquenghem BTCs of similar code rate reveals that RS BTCs have interesting advantages in terms of memory size and decoder complexity for very-high-data-rate decoding architectures.     

Complexity Reduction in SISO Decoding of Block Codes

SISO decoding for block codes can be carried out based on a trellis representation of the code. However, the complexity entailed by such decoding is most often prohibitive and thus prevents practical implementation. This paper examines a new decoding scheme based on the soft-output Viterbi algorithm (SOVA) applied to a sectionalized trellis for linear block codes. The computational complexities of the new SOVA decoder and of the conventional SOVA decoder, based on a bit-level trellis, are theoretically analyzed and derived for different linear block codes. These results are used to obtain optimum sectionalizations of a trellis for SOVA. For comparisons, the optimum sectionalizations for Maximum A Posteriori (MAP) and Maximum Logarithm MAP (Max-Log-MAP) algorithms, and their corresponding computational complexities are included. The results confirm that the new SOVA decoder is the most computationally efficient SISO decoder, in comparisons to MAP and Max-Log-MAP algorithms. The simulation results of the bit error rate (BER) performance, assuming binary phase -- shift keying (BPSK) and additive white Gaussian noise (AWGN) channel, demonstrate that the performance of the new decoding scheme is not degraded. The BER performance of iterative SOVA decoding of serially concatenated block codes shows no difference in the quality of the soft outputs of the new decoding scheme and of the conventional SOVA.     

Soft-Output BEAST Decoding With Application to Product Codes

A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximate a posteriori probabilities (APPs) of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using extrinsic information transfer (EXIT) charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the Bahl–Cocke–Jelinek–Raviv (BCJR) decoder with a substantially lower computational complexity.      

Bandwidth-efficient turbo trellis-coded modulation using puncturedcomponent codes

We present a bandwidth-efficient channel coding scheme that has an overall structure similar to binary turbo codes, but employs trellis-coded modulation (TCM) codes (including multidimensional codes) as component codes. The combination of turbo codes with powerful bandwidth-efficient component codes leads to a straightforward encoder structure, and allows iterative decoding in analogy to the binary turbo decoder. However, certain special conditions may need to be met at the encoder, and the iterative decoder needs to be adapted to the decoding of the component TCM codes. The scheme has been investigated for 8-PSK, 16-QAM, and 64-QAM modulation schemes with varying overall bandwidth efficiencies. A simple code choice based on the minimal distance of the punctured component code has also been performed. The interset distances of the partitioning tree can be used to fix the number of coded and uncoded bits. We derive the symbol-by-symbol MAP component decoder operating in the log domain, and apply methods of reducing decoder complexity. Simulation results are presented and compare the scheme with traditional TCM as well as turbo codes with Gray mapping. The results show that the novel scheme is very powerful, yet of modest complexity since simple component codes are used     

Soft-input decoder for decoding of internally channel coded fiber-optic CDMA communication systems

We propose using a soft-input decoder for the decoding of internally convolutional coded Poisson noise-dominated fiber-optic code-division multiple-access (CDMA) communication systems using optical orthogonal codes. We first compute the coded symbol log-likelihoods at the output of the Poisson noise-dominated channel, which is then used by a soft-input maximum-likelihood decoder, for a fiber-optic CDMA system assuming both on-off keying and binary pulse position modulation schemes. Furthermore, we develop a discrete soft-output channel model for a Poisson noise-dominated channel, with which we evaluate the upper bound on the bit error probability of the internally coded Poisson noise-dominated fiber-optic CDMA system using a soft-input decoder. It is shown that the soft-input decoder significantly outperforms the hard-input decoder. Furthermore, the performance of the soft-input decoder is also evaluated in the presence of different values of dark current.     

Data width requirements in SISO decoding with module normalization

This letter studies the numerical properties of log-MAP-based soft-input soft-output decoding. The ranges of the differences between the path metrics, the soft output, and the complete information are derived. Since the log-MAP algorithm is functionally dependent only upon the differences between path metrics, not their magnitudes, a module normalization technique that is automatically implemented in two's complement arithmetic can be used to accommodate overflow of the path metrics. An expression for the minimum internal data width of a soft-input soft-output decoder that employs the module normalization technique is derived. As an application, the minimum internal data width of a decoder for the turbo code used in third-generation mobile communication systems is determined     

Iterative Source-Channel Decoding With Markov Random Field Source Models

We propose a joint source-channel decoding approach for multidimensional correlated source signals. A Markov random field (MRF) source model is used which exemplarily considers the residual spatial correlations in an image signal after source encoding. Furthermore, the MRF parameters are selected via an analysis based on extrinsic information transfer charts. Due to the link between MRFs and the Gibbs distribution, the resulting soft-input soft-output (SISO) source decoder can be implemented with very low complexity. We prove that the inclusion of a high-rate block code after the quantization stage allows the MRF-based decoder to yield the maximum average extrinsic information. When channel codes are used for additional error protection the MRF-based SISO source decoder can be used as the outer constituent decoder in an iterative source-channel decoding scheme. Considering an example of a simple image transmission system we show that iterative decoding can be successfully employed for recovering the image data, especially when the channel is heavily corrupted.     

Multiple serial and parallel concatenated single parity-check codes

Single parity-check (SPC) codes are applied in both parallel and serial concatenated structures to produce high-performance coding schemes. The number of concatenations or stages, M, is increased to improve system performance at moderate-to-low bit-error rates without changing the overall code parameters (namely, code rate and code block length). Analytical bounds are presented to estimate the performance at high signal-to-noise ratios. The SPC concatenated codes are considered with binary phase-shift keying and with 16-quadrature amplitude modulation bit-interleaved coded modulation on the additive white Gaussian noise channel and the independent Rayleigh fading channel. Simulations show that the four-stage serial or parallel concatenated SPC codes can, respectively, outperform or perform as well as 16-state turbo codes. Furthermore, decoding complexity is approximately 9-10 times less complex than that of 16-state turbo codes. The convergence behavior of both serial and parallel concatenated SPC codes is also discussed.