Iterative joint source-channel decoding of variable-length codes using residual source redundancy

We present a novel symbol-based soft-input a posteriori probability (APP) decoder for packetized variable-length encoded source indexes transmitted over wireless channels where the residual redundancy after source encoding is exploited for error protection. In combination with a mean-square or maximum APP estimation of the reconstructed source data, the whole decoding process is close to optimal. Furthermore, solutions for the proposed APP decoder with reduced complexity are discussed and compared to the near-optimal solution. When, in addition, channel codes are employed for protecting the variable-length encoded data, an iterative source-channel decoder can be obtained in the same way as for serially concatenated codes, where the proposed APP source decoder then represents one of the two constituent decoders. The simulation results show that this iterative decoding technique leads to substantial error protection for variable-length encoded correlated source signals, especially, when they are transmitted over highly corrupted channels.     

Joint turbo decoding and estimation of hidden Markov sources

We describe a joint source-channel scheme for modifying a turbo decoder in order to exploit the statistical characteristics of hidden Markov sources. The basic idea is to treat the trellis describing the hidden Markov source as another constituent decoder which exchanges information with the other constituent decoder blocks. The source block uses as extrinsic information the probability of the input bits that is provided by the constituent decoder blocks. On the other hand, it produces a new estimation of such a probability which will be used as extrinsic information by the constituent turbo decoders. The proposed joint source-channel decoding technique leads to significantly improved performance relative to systems in which source statistics are not exploited and avoids the need to perform any explicit source coding prior to transmission. Lack of a priori knowledge of the source parameters does not degrade the performance of the system, since these parameters can be jointly estimated with turbo decoding     

On the iterative approximation of optimal joint source-channeldecoding

Joint source-channel decoding is formulated as an estimation problem. The optimal solution is stated and it is shown that it is not feasible in many practical systems due to its complexity. Therefore, a novel iterative procedure for the approximation of the optimal solution is introduced, which is based on the principle of iterative decoding of turbo codes. New analytical expressions for different types of information in the optimal algorithm are used to derive the iterative approximation. A direct comparison of the performance of the optimal algorithm and its iterative approximation is given for a simple transmission system with “short” channel codewords. Furthermore, the performance of iterative joint source-channel decoding is investigated for a more realistic system     

一种适用于Turbo译码的新型迭代停止算法

针对Turbo码迭代译码延时大的问题,本文提出了一种加速译码的新型迭代停止方法,该方法利用了两个分量译码器输出的对数似然比LLR(Logarithm Likelihood Ratio)的统计特性,简称为LCB(LLR Characters Based)算法.同现存的经典停止准则相比,在相同的比特误码率性能下,新方法有效的降低了译码平均迭代次数,加速了Turbo码译码,可应用于流媒体信号传输系统.     

Joint source-channel and multiuser decoding for Rayleigh fadingCDMA channels

We consider joint source-channel and multiuser decoding for frequency selective Rayleigh fading code-division multiple-access channels. The block source-channel encoder is defined by a vector quantizer. We investigate optimal (minimum mean-square error) decoding and “user-separated” decoding of lower complexity. The studied decoders are soft in the sense that they utilize all soft information available at the receiver. Simulations indicate significant performance gains of the introduced decoders compared with a tandem approach that uses maximum-likelihood multiuser detection plus table-lookup decoding     

On the suboptimality of iterative decoding for turbo-like and LDPC codes with cycles in their graph representation

In this paper, we focus on the suboptimality of iterative decoding on graphs with cycles, through examining the use of a reliability-based decoding algorithm for some concatenated codes with an interleaver, known as turbo-like codes. The a posteriori probabilities delivered by the iterative decoding are regarded as reliability information, and an efficient algorithm for the overall linear block code is applied at certain iterations. Simulation results show that the suboptimality of iterative decoding due to cycles can be at least partially compensated by this approach. Some insights about the potential additional coding gains achievable are investigated based on the characteristics of the constituent decoders. These characteristics are related to the nature of suboptimality in the overall iterative decoding. The effects of some code parameters and channel conditions on the behavior of iterative decoding are also studied for a better understanding of its suboptimality.     

Soft multiuser decoding for vector quantization over a CDMA channel

An approach to optimal soft decoding for vector quantization (VQ) over a code-division multiple-access (CDMA) channel is presented. The decoder of the system is soft in the sense that the unquantized outputs of the matched filters are utilized directly for decoding (no decisions are taken), and optimal according to the minimum mean-squared error (MMSE) criterion. The derived decoder utilizes a priori source information and knowledge of the channel characteristics to combat channel noise and multiuser interference in an optimal fashion. Hadamard transform representations for the user VQs are employed in the derivation and for the implementation of the decoder. The advantages of this approach are emphasized. Suboptimal versions of the optimal decoder are also considered. Simulations show the soft decoders to outperform decoding based on maximum-likelihood (ML) multiuser detection. Furthermore, the suboptimal versions are demonstrated to perform close to the optimal, at a significantly lower complexity in the number of users. The introduced decoders are, moreover, shown to exhibit near-far resistance. Simulations also demonstrate that combined source-channel encoding, with joint source-channel and multiuser decoding, can significantly outperform a tandem source-channel coding scheme employing multiuser detection plus table lookup source decoding     

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.     

Stopping Set Analysis of Iterative Row-Column Decoding of Product Codes

In this paper, we introduce stopping sets for iterative row-column decoding of product codes using optimal constituent decoders. When transmitting over the binary erasure channel (BEC), iterative row-column decoding of product codes using optimal constituent decoders will either be successful, or stop in the unique maximum-size stopping set that is contained in the (initial) set of erased positions. Let C_p denote the product code of two binary linear codes C_c and C_r of minimum distances dc and d_r and second generalized Hamming weights d₂(C_c) and d₂(C_r), respectively. We show that the size s_min of the smallest noncode- word stopping set is at least mm(d_rd₂(C_c),d_cd₂(C_r)) > d_rd_c, where the inequality follows from the Griesmer bound. If there are no codewords in C_p with support set S, where S is a stopping set, then S is said to be a noncodeword stopping set. An immediate consequence is that the erasure probability after iterative row-column decoding using optimal constituent decoders of (finite-length) product codes on the BEC, approaches the erasure probability after maximum-likelihood decoding as the channel erasure probability decreases. We also give an explicit formula for the number of noncodeword stopping sets of size s_min, which depends only on the first nonzero coefficient of the constituent (row and column) first and second support weight enumerators, for the case when d₂(C_r) < 2d_r and d₂(C_c) < 2d_c. Finally, as an example, we apply the derived results to the product of two (extended) Hamming codes and two Golay codes.     

Performance evaluation of list sequence MAP decoding

List-sequence (LS) decoding has the potential to yield significant coding gain additional to that of conventional single-sequence decoding, and it can be implemented with full backward compatibility in systems where an error-detecting code is concatenated with an error-correcting code. LS maximum-likelihood (ML) decoding provides a list of estimated sequences in likelihood order. For convolutional codes, this list can be obtained with the serial list Viterbi algorithm (SLVA). Through modification of the metric increments of the SLVA, an LS maximum a posteriori (MAP) probability decoding algorithm is obtained that takes into account bitwise a priori probabilities and produces an ordered list of sequence MAP estimates. The performance of the resulting LS-MAP decoding algorithm is studied in this paper. Computer simulations and approximate analytical expressions, based on geometrical considerations of the decision domains of LS decoders, are presented. We focus on the frame-error performance of LS-MAP decoding, with genie-assisted error detection, on the additive white Gaussian noise channel. It is concluded that LS-MAP decoding exploits a priori information more efficiently, in order to achieve performance improvements, than does conventional single-sequence MAP decoding. Interestingly, LS-MAP decoding can provide significant improvements at low signal-to-noise ratios, compared with LS-ML decoding. In this environment, it is furthermore observed that feedback convolutional codes offer performance improvements over their feedforward counterparts. Since LS-MAP decoding can be implemented in existing systems at a modest complexity increase, it should have a wide area of applications, such as joint source-channel decoding and other kinds of iterative decoding.     

Performance analysis and design criteria for finite-alphabet source-channel codes

Efficient compression of finite-alphabet sources requires variable-length codes (VLCs). However, in the presence of noisy channels, error propagation in the decoding of VLCs severely degrades performance. To address this problem, redundant entropy codes and iterative source-channel decoding have been suggested, but to date, neither performance bounds nor design criteria for the composite system have been available. We calculate performance bounds for the source-channel system by generalizing techniques originally developed for serial concatenated convolutional codes. Using this analysis, we demonstrate the role of a recursive structure for the inner code and the distance properties of the outer code. We use density evolution to study the convergence of our decoders. Finally, we pose the question: Under a fixed rate and complexity constraint, when should we use source-channel decoding (as opposed to separable decoding)? We offer answers in several specific cases. For our analysis and design rules, we use union bounds that are technically valid only above the cutoff rate, but interestingly, the codes designed with union-bound criteria perform well even in low signal-to-noise ratio regions, as shown by our simulations as well as previous works on concatenated codes.     

Iterative turbo decoder analysis based on density evolution

We track the density of extrinsic information in iterative turbo decoders by actual density evolution, and also approximate it by symmetric Gaussian density functions. The approximate model is verified by experimental measurements. We view the evolution of these density functions through an iterative decoder as a nonlinear dynamical system with feedback. Iterative decoding of turbo codes and of serially concatenated codes is analyzed by examining whether a signal-to-noise ratio (SNR) for the extrinsic information keeps growing with iterations. We define a “noise figure” for the iterative decoder, such that the turbo decoder will converge to the correct codeword if the noise figure is bounded by a number below zero dB. By decomposing the code's noise figure into individual curves of output SNR versus input SNR corresponding to the individual constituent codes, we gain many new insights into the performance of the iterative decoder for different constituents. Many mysteries of turbo codes are explained based on this analysis. For example, we show why certain codes converge better with iterative decoding than more powerful codes which are only suitable for maximum likelihood decoding. The roles of systematic bits and of recursive convolutional codes as constituents of turbo codes are crystallized. The analysis is generalized to serial concatenations of mixtures of complementary outer and inner constituent codes. Design examples are given to optimize mixture codes to achieve low iterative decoding thresholds on the signal-to-noise ratio of the channel     

Joint source-channel coding and guessing with application tosequential decoding

We extend our earlier work on guessing subject to distortion to the joint source-channel coding context. We consider a system in which there is a source connected to a destination via a channel and the goal is to reconstruct the source output at the destination within a prescribed distortion level with respect to (w.r.t.) some distortion measure. The decoder is a guessing decoder in the sense that it is allowed to generate successive estimates of the source output until the distortion criterion is met. The problem is to design the encoder and the decoder so as to minimize the average number of estimates until successful reconstruction. We derive estimates on nonnegative moments of the number of guesses, which are asymptotically tight as the length of the source block goes to infinity. Using the close relationship between guessing and sequential decoding, we give a tight lower bound to the complexity of sequential decoding in joint source-channel coding systems, complementing earlier works by Koshelev (1973) and Hellman (1975). Another topic explored here is the probability of error for list decoders with exponential list sizes for joint source-channel coding systems, for which we obtain tight bounds as well. It is noteworthy that optimal performance w.r.t. the performance measures considered here can be achieved in a manner that separates source coding and channel coding     

Low-complexity iterative joint source-channel decoding for variable-length encoded Markov sources

In this paper, we present a novel packetized bit-level decoding algorithm for variable-length encoded Markov sources, which calculates reliability information for the decoded bits in the form of a posteriori probabilities (APPs). An interesting feature of the proposed approach is that symbol-based source statistics in the form of the transition probabilities of the Markov source are exploited as a priori information on a bit-level trellis. This method is especially well-suited for long input blocks, since in contrast to other symbol-based APP decoding approaches, the number of trellis states does not depend on the packet length. When additionally the variable-length encoded source data is protected by channel codes, an iterative source-channel decoding scheme can be obtained in the same way as for serially concatenated codes. Furthermore, based on an analysis of the iterative decoder via extrinsic information transfer charts, it can be shown that by using reversible variable-length codes with a free distance of two, in combination with rate-1 channel codes and residual source redundancy, a reliable transmission is possible even for highly corrupted channels. This justifies a new source-channel encoding technique where explicit redundancy for error protection is only added in the source encoder.     

Advanced decoding algorithms for Reed-Solomon/Convolutional concatenated codes

The evaluation of the union bound for theber of Reed-Solomon/Convolutional concatenated codes indicates that their performance might largely improve through the application of soft iterative decoders. This paper presents an iterative decoding algorithm for concatenated codes consisting of an outer Reed-Solomon code, a symbol interleaver and an inner convolutional code. The performance improvement for iterative and non-iterative decoders is evaluated. Existing solutions for the different decoding stages and their interfaces are discussed and their performance is compared. A new procedure is proposed to define the feedback signal from the output of the Reed-Solomon decoder to the input of the convolutional decoder, which captures the reliability information that can be inferred from errors-and-era-suresrs decoders and includes the “state pinning” approach as a particular case. The decoding schemes are applied to the specificdvb-s concatenated code.     

基于MS估计和迭代结构的信源信道联合解码系统性能分析

该文对基于均方MS(Mean Square)误差最小准则估计的软输入信源解码和基于信源参数特性及迭代结构的维特比解码两种信源信道联合解码算法进行分析,分别给出系统性能提高的影响因子,同时与信源信道独立解码算法相比较,并推导了联合算法中的接收参数信噪比的提高幅度以及比特误码率的上限值,证明了联合解码算法的可行性和有效性。实验仿真结果表明了分析方法的正确性。     

基于HMM的信源—信道迭代联合译码

提出一种在接收端利用Turbo译码软输出,结合HMM（隐马尔可夫模型）中的Baum-Welch重估算法获取信源模型参数并进行信源-信道迭代联合译码的算法.通过含噪接收序列信道译码后的软输出对信源模型参数进行估计,并将迭代估计获得的信源精确概率结构和信道译码结合进行信源-信道联合迭代译码.同时从信息论角度提出用鉴别信息来度量估计获得的信源模型参数的精度,以及确定迭代估计终止的条件.     

Turbo decodulation: iterative combined demodulation and source-channel decoding

We propose the combination of iterative demodulation and iterative source-channel decoding as a multiple turbo process. The receiver structures of bit-interleaved coded modulation with iterative decoding (BICM-ID), iterative source-channel decoding (ISCD), and iterative source coded modulation (ISCM) are merged to one novel turbo system, in which in two iterative loops reliability information is exchanged between the three single components, demodulator, channel decoder and (softbit) source decoder. Simulations show quality improvements compared to the different previously known systems, which use iterative processing only for two components of the receiver.     

Graph-based iterative decoding algorithms for parity-concatenatedtrellis codes

We construct parity-concatenated trellis codes in which a trellis code is used as the inner code and a simple parity-check code is used as the outer code. From the Tanner-Wiberg-Loeliger (1981, 1996) graph representation, several iterative decoding algorithms can be derived. However, since the graph of the parity-concatenated code contains many short cycles, the conventional min-sum and sum-product algorithms cannot achieve near-optimal decoding. After some simple modifications, we obtain near-optimal iterative decoders. The modifications include either (a) introducing a normalization operation in the min-sum and sum-product algorithms or (b) cutting the short cycles which arise in the iterative Viterbi algorithm (IVA). After modification, all three algorithms can achieve near-optimal performance, but the IVA has the least average complexity. We also show that asymptotically maximum-likelihood (ML) decoding and a posteriori probability (APP) decoding can be achieved using iterative decoders with only two iterations. Unfortunately, this asymptotic behavior is only exhibited when the bit-energy-to-noise ratio is above the cutoff rate. Simulation results show that with trellis shaping, iterative decoding can perform within 1.2 dB of the Shannon limit at a bit error rate (BER) of 4×10^-5 for a block size of 20000 symbols. For a block size of 200 symbols, iterative decoding can perform within 2.1 dB of the Shannon limit     

Soft decoding and synchronization of arithmetic codes: application to image transmission over noisy channels

The paper addresses the issue of robust and joint source-channel decoding of arithmetic codes. We first analyze dependencies between the variables involved in arithmetic coding by means of the Bayesian formalism. This provides a suitable framework for designing a soft decoding algorithm that provides high error-resilience. It also provides a natural setting for "soft synchronization", i.e., to introduce anchors favoring the likelihood of "synchronized" paths. In order to maintain the complexity of the estimation within a realistic range, a simple, yet efficient, pruning method is described. The algorithm can be placed in an iterative source-channel decoding structure, in the spirit of serial turbo codes. Models and algorithms are then applied to context-based arithmetic coding widely used in practical systems (e.g., JPEG-2000). Experimentation results with both theoretical sources and with real images coded with JPEG-2000 reveal very good error resilience performances.