Design and performance of turbo Gallager codes

The most powerful channel-coding schemes, namely, those based on turbo codes and low-density parity-check (LDPC) Gallager codes, have in common the principle of iterative decoding. However, the relative coding structures and decoding algorithms are substantially different. This paper shows that recently proposed novel coding structures bridge the gap between these two schemes. In fact, with properly chosen component convolutional codes, a turbo code can be successfully decoded by means of the decoding algorithm used for LDPC codes, i.e., the belief-propagation algorithm working on the code Tanner graph. These new turbo codes are here nicknamed "turbo Gallager codes." Besides being interesting from a conceptual viewpoint, these schemes are important on the practical side because they can be decoded in a fully parallel manner. In addition to the encoding complexity advantage of turbo codes, the low decoding complexity allows the design of very efficient channel-coding schemes.     

Turbo码概率-代数联合解码算法

Turbo码采用修正的BAHL et al.算法实现解码.这是一种基于软值的概率迭代解码算法.本文在保持Turbo码迭代软解码算法优点的基础上,充分利用Turbo码编码器结构这一确知条件,结合代数解码原理,提出了一种Turbo码概率-代数联合解码算法.该算法结合了概率解码和代数解码的优点,又有效避免了误差传播的发生,使Turbo码的纠错性能在原经典算法的基础上得到进一步的提高.该算法不仅为降低Turbo码的比特误码率和误差地板值提供了一种新的研究途径,而且因其更好的纠错性能而具有十分明显的实用价值.仿真实验结果显示,在比特误码率(BER)为10^-3~10^-4时,与经典Turbo码解码算法相比,采用该算法能获得0.1dB左右的编码增益.     

Analysis and Design of Power-Efficient Coding Schemes With Parallel Concatenated Convolutional Codes

Analysis and Design of Power-Efficient Coding Schemes With Parallel Concatenated Convolutional Codes In the low signal-to-noise ratio regime, the performance of concatenated coding schemes is limited by the convergence properties of the iterative decoder. Idealizing the model of iterative decoding by an independence assumption, which represents the case in which the codeword length is infinitely large, leads to analyzable structures from which this performance limit can be predicted. Mutual information-transfer characteristics of the constituent coding schemes comprising convolutional encoders and soft-in/soft-out decoders have been shown to be sufficient to characterize the components within this model. Analyzing serial and parallel concatenations is possible just by these characteristics. In this paper, we extend the method of extrinsic information transfer charts that is limited to the case of a concatenation of two component codes, to the case of multiple turbo codes. Multiple turbo codes are parallel concatenations of three or more constituent codes, which, in general, may not be identical and may not have identical code rates. For the construction of low-rate codes, this concept seems to be very favorable, as power efficiencies close to the Shannon limit can be achieved with reasonable complexity.     

Capacity-approaching codes: can they be applied to the magnetic recording channel?

Digital signal processing and coding are increasingly being recognized as a cost-efficient approach in achieving substantial areal density gains while preserving the high reliability of disk drives, although historically advances in head and media technologies have been the main driving force behind areal density growth. The recent advances in capacity-approaching codes hold the promise to push the areal density to the ultimate limit. Various configurations regarding the interplay between soft detection and soft decoding through an iterative process, as it applies to the magnetic recording channel, are presented. In particular, the state of the art in turbo and turbo-like coding, including LDPC coding, is reviewed, and the serial concatenation of these coding schemes with inner generalized PR channels in a turbo equalization structure is described. Finally, an attempt is made to assess the performance and limitations of these AWGN channel-capacity-approaching codes when applied to the magnetic recording channel.     

Low-rate channel coding with complex-valued block codes

This paper addresses aspects of channel coding in orthogonal frequency-division multiplexing-code-division multiple access (OFDM-CDMA) uplink systems where each user occupies a bandwidth much larger than the information bit rate. This inherent bandwidth expansion allows the application of powerful low-rate codes under the constraint of low decoding costs. Three different coding strategies are considered: the combination of convolutional and repetition codes, the code-spread system consisting of one single very low-rate convolutional code and a serial concatenation of convolutional, Walsh-Hadamard and repetition code. The latter scheme is improved by combining the Walsh-Hadamard codes with an additional M-phase-shift keying modulation resulting in complex-valued Walsh-Hadamard codes (CWCs). Analytical performance evaluations will be given for these codes for the first time. The application of CWCs as inner codes in a serial code concatenation is also addressed. We derive a symbol-by-symbol maximum a posteriori decoding algorithm in the complex signal space in order to enable iterative decoding for the entire code. A comprehensive performance analysis by simulation of all the proposed coding schemes shows that the Walsh-Hadamard-based schemes are the best choice for low-to-medium system load. Note that even for fully loaded OFDM-CDMA systems, the concatenation with an inner complex-valued Walsh-Hadamard code leads to a bit-error rate less than 10/sup -5/ for an E/sub b//N/sub 0/ of about 6 dB.     

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.     

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     

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     

Product accumulate codes: a class of codes with near-capacity performance and low decoding complexity

We propose a novel class of provably good codes which are a serial concatenation of a single-parity-check (SPC)-based product code, an interleaver, and a rate-1 recursive convolutional code. The proposed codes, termed product accumulate (PA) codes, are linear time encodable and linear time decodable. We show that the product code by itself does not have a positive threshold, but a PA code can provide arbitrarily low bit-error rate (BER) under both maximum-likelihood (ML) decoding and iterative decoding. Two message-passing decoding algorithms are proposed and it is shown that a particular update schedule for these message-passing algorithms is equivalent to conventional turbo decoding of the serial concatenated code, but with significantly lower complexity. Tight upper bounds on the ML performance using Divsalar's (1999) simple bound and thresholds under density evolution (DE) show that these codes are capable of performance within a few tenths of a decibel away from the Shannon limit. Simulation results confirm these claims and show that these codes provide performance similar to turbo codes but with significantly less decoding complexity and with a lower error floor. Hence, we propose PA codes as a class of prospective codes with good performance, low decoding complexity, regular structure, and flexible rate adaptivity for all rates above 1/2.     

Turbo decoding as an instance of Pearl's “beliefpropagation” algorithm

We describe the close connection between the now celebrated iterative turbo decoding algorithm of Berrou et al. (1993) and an algorithm that has been well known in the artificial intelligence community for a decade, but which is relatively unknown to information theorists: Pearl's (1982) belief propagation algorithm. We see that if Pearl's algorithm is applied to the “belief network” of a parallel concatenation of two or more codes, the turbo decoding algorithm immediately results. Unfortunately, however, this belief diagram has loops, and Pearl only proved that his algorithm works when there are no loops, so an explanation of the experimental performance of turbo decoding is still lacking. However, we also show that Pearl's algorithm can be used to routinely derive previously known iterative, but suboptimal, decoding algorithms for a number of other error-control systems, including Gallager's (1962) low-density parity-check codes, serially concatenated codes, and product codes. Thus, belief propagation provides a very attractive general methodology for devising low-complexity iterative decoding algorithms for hybrid coded systems     

Noncoherent iterative decoding of spectrally efficient coded modulations

In this paper, we consider possible solutions for noncoherent decoding of concatenated codes with spectrally efficient modulations. Two main classes of schemes are considered. A first class is obtained by concatenating parallel coding schemes with differential encoding. A second class considers serially concatenated coding structures and possible schemes derived from turbo trellis coded modulation (t-tcm), which do not employ differential encoding. In the first case, at the receiver side we consider separate detection and decoding, while in the second case we consider joint detection and decoding. The major problem connected with such an iterative decoding procedure is that taking into account an augmented channel memory leads to an intolerable trellis size, and hence to an impractical decoding complexity. Reduced-complexity techniques suited to iterative decoding become fundamental, and we consider a recently proposed state-reduction technique. This way, the performance of a coherent receiver is approached, by keeping the number of receiver states fixed.     

IEEE802.16e中的BTC码编译码方案

介绍了BTC码的基本概念以及IEEE802.16e协议中的BTC编码方案,给出BTC迭代译码、每次行/列SISO译码以及扩展Hamming子码的硬判决译码方案,给出基于该译码方案的仿真结果.     

Coded modulation in the block-fading channel: coding theorems and code construction

We consider coded modulation schemes for the block-fading channel. In the setting where a codeword spans a finite number N of fading degrees of freedom, we show that coded modulations of rate R bit per complex dimension, over a finite signal set /spl chi//spl sube//spl Copf/ of size 2/sup M/, achieve the optimal rate-diversity tradeoff given by the Singleton bound /spl delta/(N,M,R)=1+/spl lfloor/N(1-R/M)/spl rfloor/, for R/spl isin/(0,M/spl rfloor/. Furthermore, we show also that the popular bit-interleaved coded modulation achieves the same optimal rate-diversity tradeoff. We present a novel coded modulation construction based on blockwise concatenation that systematically yields Singleton-bound achieving turbo-like codes defined over an arbitrary signal set /spl chi//spl sub//spl Copf/. The proposed blockwise concatenation significantly outperforms conventional serial and parallel turbo codes in the block-fading channel. We analyze the ensemble average performance under maximum-likelihood (ML) decoding of the proposed codes by means of upper bounds and tight approximations. We show that, differently from the additive white Gaussian noise (AWGN) and fully interleaved fading cases, belief-propagation iterative decoding performs very close to ML on the block-fading channel for any signal-to-noise ratio (SNR) and even for relatively short block lengths. We also show that, at constant decoding complexity per information bit, the proposed codes perform close to the information outage probability for any block length, while standard block codes (e.g., obtained by trellis termination of convolutional codes) have a gap from outage that increases with the block length: this is a different and more subtle manifestation of the so-called "interleaving gain" of turbo codes.     

Codes defined on graphs

Low-density parity-check codes, turbo codes, and indeed most practically decodable capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but, more important, they structure the operation of the sum-product decoding algorithm (or one of many possible variations), which can be used for iterative decoding. Such coding schemes have the potential to approach channel capacity, while maintaining reasonable decoding complexity. In this tutorial article we review factor graphs, which can be used to describe codes and the joint probability distributions that must be dealt with in decoding. We also review the sum-product algorithm, and show how this algorithm leads to iterative decoding algorithms for codes defined on graphs.     

Certain generalizations of concatenated codes--Exponential error bounds and decoding complexity

New coding and decoding schemes based on concatenated codes are proposed. The new coding schemes are potentially superior to Forney's original concatenation scheme in the sense that for discrete memoryless channels the former has a smaller upper bound on the probability of decoding error for the same order of decoding complexity.     

基于MSK和LT码的联合迭代译码算法

传统的简单级联编码调制系统在译码时会造成软信息损失.提出了一种基于MSK和LT码的联合软迭代译码算法,设计了算法的系统模型.利用LT码的软译码和MSK调制的SISO算法,进行联合软迭代译码,提高了编码调制系统的性能.仿真结果表明:在误码率为10-4时,提出的算法比传统的简单级联编码调制算法约有1.5 dB的编码增益.     

Noncoherent iterative (turbo) decoding

Previously, noncoherent sequence detection schemes for coded linear and continuous phase modulations have been proposed, which deliver hard decisions by means of a Viterbi algorithm. The current trend in digital transmission systems toward iterative decoding algorithms motivates an extension of these schemes. In this paper, we propose two noncoherent soft-output decoding algorithms. The first solution has a structure similar to that of the well-known algorithm by Bahl et al. (1974), whereas the second is based on noncoherent sequence detection and a reduced-state soft-output Viterbi algorithm. Applications to the combined detection and decoding of differential or convolutional codes are considered. Further applications to noncoherent iterative decoding of turbo codes and serially concatenated interleaved codes are also considered. The proposed noncoherent detection schemes exhibit moderate performance loss with respect to corresponding coherent schemes and are very robust to phase and frequency instabilities     

Incremental frequency, amplitude and phase tracker (IFAPT) forcoherent demodulation over fast flat fading channels

The incremental frequency amplitude and phase tracker (IFAPT) is a recursive algorithm that estimates the parameters of piecewise-linear approximation to assumed continuous narrow-band signals. The parameters are amplitude, phase, and their respective slopes. The simple, recursive nature of IFAPT enables its direct interaction with recursive algorithms, such as the Viterbi and the BCJR in the APP SISO module, used for iteratively decoding concatenated codes. An augmented APP (A ²P²)-module, containing IFAPT and BCJR algorithms, is here applied to iterative decoding serial concatenated convolutional codes under Rayleigh fading conditions with diversity reception. The bit-error rate under Rayleigh fading with dual diversity reception at E _bT/N₀=6 dB and f_dT_s=10^-2 is 10^-4, where E _bT is the total mean energy per bit in both diversity branches, f_d is the Doppler frequency, and T_s the symbol time     

Iterative decoding of space-time differentially coded unitary matrix modulation

Noncoherent communication over the Rayleigh flat fading channel with multiple transmit and receive antennas is investigated. Codes achieving bit error rate (BER) lower than 10/sup -4/ at bit energy over the noise spectral density ratio (E/sub b//N/sub 0/) of 0.8 to 2.8 dB from the capacity limit were found with coding rates of 0.5 to 2.25 bits per channel use. The codes are serial concatenation of a turbo code and a unitary matrix differential modulation code. The receiver is based on a high-performance joint iterative decoding of the turbo code and the modulation code. Information-theoretic arguments are harnessed to form guidelines for code design and to evaluate performance of the iterative decoder.     

Serial concatenation of block and convolutional codes

Parallel concatenated coding schemes employing convolutional codes as constituent codes linked by an interleaver have been proposed in the literature as `turbo codes'. They yield very good performance in connection with simple suboptimum decoding algorithms. The authors propose an alternative scheme consisting in the serial concatenation of block or convolutional codes and evaluate its average performance in terms of bit error probability