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.     

Improved image decoding over noisy channels using minimummean-squared estimation and a Markov mesh

Joint source-channel (JSC) decoding based on residual source redundancy is a technique for providing channel robustness to quantized data. Previous work assumed a model equivalent to viewing the encoder/noisy channel tandem as a discrete hidden Markov model (HMM) with transmitted indices the hidden states. We generalize this HMM-based (1-D) approach for images, using the more powerful hidden Markov mesh random field (HMMRF) model. While previous state estimation methods for HMMRFs base estimates on only a causal subset of the observed data, our new method uses both causal and anticausal subsets. For JSC-based image decoding, the new method provides significant benefits over several competing techniques.     

衰落信道下的格形码设计

衰落信道下ＴＣＭ好码的设计准则是使有效码长度最长，同时使其对应路径的欧几里德距离乘积最大。本文首先从理论上得到有效码长度与卷积编码器的状态数，并行输入数之间的关系。提出了一种能达到最大自由长的状态转移图－标准拓扑篱笆图的概念，在此基础上，对衰落信道下采用速率为（２／３）８ＰＳＫ信号集合时的ＴＣＭ好码进行搜索，与文献中已有码相比，利用准则判别和进行蒙特－卡洛模拟都说明了新码在抗衰落方面的良好性能。     

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     

The Design of Predictive Trellis Waveform Coders Using the Generalized Lloyd Algorithm

Trellis source codes consist of a finite-state machine decoder and a trellis search algorithm, such as the Viterbi algorithm, as the encoder. The encoder experiments with a local copy of the decoder and determines the best channel path map in the sense that it will yield the smallest average distortion between the source sequence and the reproduction sequence given the codebook. In this paper we present a coding system and a design algorithm for predictive trellis coding. Results obtained via simulation are compared for trellis and predictive trellis codes designed for first-order autoregressive sources with Gaussian and Laplacian innovations and for sampled speech. On a random source which models speech, simulation results of the predictive and nonpredictive trellis codes designed by the generalized Lloyd algorithm and those obtained by other researchers are compared. Issues related to computational complexity, the effects of initial codebook selection, training sequence segmentation, search length, channel errors, and algorithm convergence are addressed.     

A new algebraic algorithm for generating the transfer function of atrellis encoder

A new algebraic method to compute the transfer function of a trellis encoder with scalar labeling is outlined. This method is not difficult to implement and is found to be more efficient than conventional methods for encoders with a large number of states     

Joint source and noisy channel trellis encoding (Corresp.)

In a trellis encoding communication system the decoder is a time-invariant nonlinear filter with finite memory (sliding-block code), and the encoder is a trellis search algorithm matched to the decoder. A coding theorem is established for a trellis encoding of a stationary and ergodic source over a discrete memoryless noisy channel which shows that such communication systems can perform arbitrarily close to the source distortion-rate function evaluated at the channel capacity.     

Codes based on a trellis cut-set transformation. I. Rotationallyinvariant codes

Let a trellis section 𝒯 generate a trellis code 𝒞. We study two trellis sections based on 𝒯, a “cut-set” trellis section 𝒯_cs and a “differential encoder” trellis section 𝒯_de. We show that 𝒯 can be transformed to a cut-set trellis section 𝒯_cs, which is equivalent to 𝒯 in the sense that both 𝒯 and 𝒯 _cs generate 𝒞 and both 𝒯 and 𝒯_cs have the same decoding complexity. A differential encoder trellis section is equivalent to the trellis section obtained by following 𝒯 with a differential encoder. It is shown that both 𝒯_cs and 𝒯_de have inverse transform trellis sections. A differential encoder trellis section generates a rotationally invariant (RI) code in a particularly simple and straightforward way. But an RI code need not have a differential encoder trellis section. However, for all of the RI codes examined here, we show that the cut-set trellis section can be arranged into a differential encoder trellis section. This means that these codes can be decomposed into an encoder followed by a differential encoder. Further we show that when 𝒯 is formed using a linear binary convolutional encoder and a mapping by set partitioning, then 𝒯 followed by a differential encoder gives an RI code which in some cases is as good as the best previously known codes, after applying the inverse transform to 𝒯_de     

Block and trellis codes for the binary (1-D) partial responsechannel with simple maximum likelihood decoders

We consider block and convolutional codes for improving the reliability of data transmission over the binary precoded noisy (1-D) partial response channel. We concentrate on a class of codes for which the maximum likelihood decoder, matched to the encoder, precoder, and the channel has the same trellis structure as the encoder. Thus, doubling the number of states due to the channel memory is avoided, We show that the necessary and sufficient condition to belong to this class is that all codewords be of the same parity. The Reed-Muller and Golay codes belong to this class     

Minimal transmitter complexity design of analytically describedtrellis codes

G. Ungerboeck's (1982) design rules for a class of bandlimited codes called trellis codes are reviewed. His design of the trellis is based on a set partitioning of the signal constellation, and he realized these trellis codes by a convolutional encoder followed by a mapping rule from the coder output to modulation symbols. R. Calderbank and J.E. Mazo (1984) showed how to realize trellis codes for one-dimensional signal sets in a single-step, easily derived, nonlinear transformation with memory on a sliding block of source symbols. The design rules that give a signal (state) specification in a trellis that yields the Calderbank-Mazo transformation with the smallest number of terms are presented. This gives a minimal transmitter complexity design. It is shown how to realize the Ungerboeck from the Calderbank-Mazo form, and as a result a step-by-step, search-free design procedure for trellis codes is presented. Two additional design rules are presented and applied to two examples by analytically designing two trellis codes. A simple procedure for converting an analytic code expression to a convolutional encoder realization is discussed. The analytic designs of a 4-D code and a 2-D code are presented     

On Minimality of Convolutional Ring Encoders

Convolutional codes are considered with code sequences modeled as semi-infinite Laurent series. It is well known that a convolutional code C over a finite group G has a minimal trellis representation that can be derived from code sequences. It is also well known that, for the case that G is a finite field, any polynomial encoder of C can be algebraically manipulated to yield a minimal polynomial encoder whose controller canonical realization is a minimal trellis. In this paper we seek to extend this result to the finite ring case G = BBZpr by introducing a so-called ldquo p-encoderrdquo. We show how to manipulate a polynomial encoding scheme of a noncatastrophic convolutional code over BBZpr to produce a particular type of p-encoder (ldquominimal p -encoderrdquo) whose controller canonical realization is a minimal trellis with nonlinear features. The minimum number of trellis states is then expressed as p ^gamma, where gamma is the sum of the row degrees of the minimal p -encoder. In particular, we show that any convolutional code over BBZpr admits a delay-free p -encoder which implies the novel result that delay-freeness is not a property of the code but of the encoder, just as in the field case. We conjecture that a similar result holds with respect to catastrophicity, i.e., any catastrophic convolutional code over BBZpr admits a noncatastrophic p-encoder.     

New TCM codes for 4PSK-2PSK modulation

The authors present some new multi-dimensional (3-D, 4PSK-2PSK) and 180° rotationally invariant trellis codes that combined with the demodulator (which locks onto the 2PSK signal of the 3-D signal set) allows robust operation at low signal to noise ratios. Examples of the codes are presented for 2, 4, 8, 16 and 32 states. The codes achieve a coding gain of 1.76 dB (for two encoder states) to 5.44 dB (for 42 encoder states) compared to uncoded BPSK. Distance profiles of the codes are shown     

Adaptive Trellis Encoding of Discrete-Time Sources with a Distortion Measure

An adaptive trellis-encoding scheme, using the Viterbi algorithm for trellis search and the Kalman algorithm for adaptive adjustment, is described. The encoder is comprised of a fixed precoder and a time-varying trellis coder in tandem. The source decoder is timevarying with the time-varying part being represented by a feed forward finite-state machine (FSM). Adaptive trellis encoding requires the presence of a local FSM to monitor the adaptive encoding operation. The absence of the source signal at the decoder requires the transmission of a side-information for the mechanization of the adaptive operation of the source decoder. The transmission rate of the proposed adaptive trellis-encoding scheme is(1 + 1/K_{p})/Mbits per source symbol, whereMis the block size which the precoder maps source symbols onto an intermediate signal set before trellis coding and Kpis the update period. Results obtained in the encoding of iid binary, autoregressive, and video sources are presented.     

Structural analysis of convolutional codes via dual codes

A linear correspondence is developed between the states of a rate-k/nconvolutional encoderGand the states of a corresponding syndrome formerH^T, whereHis an encoder of the code dual to the code generated byG. This correspondence is used to find an expression for the number of all-zero paths of lengthtauin the code trellis; the answer depends only on the constraint lengths of the dual code. A partial answer to the resynchronization problem also falls out of this development.     

A trellis code construction and coding theorem for stationary Gaussian sources (Corresp.)

For stationary discrete-time Gaussian sources and the squared-error distortion measure, a trellis source code is constructed. The encoder consists of a Karhunen-Loeve transform on the source output followed by a search on a trellis structured code, where the decoder is a time-variant nonlinear filter. The corresponding code theorem is proved using the random coding argument. The proof technique follows that of Viterbi and Omura, who proved the trellis coding theorem for memoryless sources. The resultant coding scheme is implementable and applicable at any nonzero rate to a stationary Gaussian source with a bounded and continuous power spectrum. Therefore. for stationary sources, it is more general than Berger's tree coding scheme, which is restricted to autoregressive Gaussian sources in a region of high rate (low distortion).     

Performance of Reduced State S–T Trellis Coded MC-CDMA Systems

In this paper, performance of reduced state space-time trellis coded multi carrier code division multiple access (STTC-MC-CDMA) system is evaluated and compared with the performance of original state STTC-MC-CDMA system. The optimum decoding scheme, i.e., maximum likelihood sequence estimation is employed which uses Viterbi algorithm for decoding STTC code. To simplify the implementation of the STTC decoder, the number of states is reduced by reducing the constraint length of the STTC encoder using generating function technique. In this technique, the generator matrix of STTC code is minimized to reduce the number of states of S–T trellis decoder. It is observed that the performance loss in terms of frame error rate of the reduced state STTC-MC-CDMA system is negligible compared to the original state STTC-MC-CDMA system. It is also noted that by using the reduced state technique the STTC decoder can be made faster since it is having lower computational complexity.     

Development of an acoustic-phonetic hidden Markov model forcontinuous speech recognition

The techniques used to develop an acoustic-phonetic hidden Markov model, the problems associated with representing the whole acoustic-phonetic structure, the characteristics of the model, and how it performs as a phonetic decoder for recognition of fluent speech are discussed. The continuous variable duration model was trained using 450 sentences of fluent speech, each of which was spoken by a single speaker, and segmented and labeled using a fixed number of phonemes, each of which has a direct correspondence to the states of the matrix. The inherent variability of each phoneme is modeled as the observable random process of the Markov chain, while the phonotactic model of the unobservable phonetic sequence is represented by the state transition matrix of the hidden Markov model. The model assumes that the observed spectral data were generated by a Gaussian source. However, an analysis of the data shows that the spectra for the most of the phonemes are not normally distributed and that an alternative representation would be beneficial     

Sequence MAP decoding of trellis codes for Gaussian and Rayleighchannels

This paper considers the use of sequence maximum a posteriori (MAP) decoding of trellis codes. A MAP receiver can exploit any “residual redundancy” that may exist in the channel encoded signal in the form of memory and/or a nonuniform distribution, thereby providing enhanced performance over very noisy channels, relative to maximum likelihood (ML) decoding. The paper begins with a first-order two-state Markov model for the channel encoder input. A variety of different systems with different source parameters, different modulation schemes, and different encoder complexities are simulated. Sequence MAP decoding is shown to substantially improve performance under very noisy channel conditions for systems with low-to-moderate redundancy, with relative gain increasing as the rate increases. As a result, coding schemes with multidimensional constellations are shown to have higher MAP gains than comparable schemes with two-dimensional (2-D) constellations. The second part of the paper considers trellis encoding of the code-excited linear predictive (CELP) speech coder's line spectral parameters (LSPs) with four-dimensional (4-D) QPSK modulation. Two source LSP models are used. One assumes only intraframe correlation of LSPs while the second one models both intraframe and interframe correlation. MAP decoding gains (over ML decoding) as much as 4 dB are achieved. Also, a comparison between the conventionally designed codes and an I-Q QPSK scheme shows that the I-Q scheme achieves better performance even though the first (sampler) LSP model is used     

Bandwidth-efficient noncoherent Trellis-coded MPSK

In this letter, we propose a novel bandwidth-efficient noncoherent trellis-coded MPSK scheme, in which a particularly designed differential encoder is added in front of the trellis encoder. With this differential encoder, trellis-coded MPSK proposed by Ungerboeck is no longer noncoherently catastrophic and thus achieves better error performance. Moreover, new trellis codes which, for the proposed scheme, have better bit error rates than Ungerboeck's codes are found by computer searches.     

Design of ring convolutional trellis codes for MAP decoding of MPEG-4 images

We propose a trellis-coded modulation system using continuous-phase frequency-shift keying (CPFSK) and ring convolutional codes for transmitting the bits generated by an embedded zerotree wavelet encoder. Improved performance is achieved by using maximum a posteriori decoding of the zerotree symbols, and ring convolutional trellis codes are determined for this decoding method. The CPFSK transmitter is decomposed into a memoryless modulator and a continuous phase encoder over the ring of integers modulo 4; the latter is combined with a polynomial convolutional encoder over the same ring. In the code design process, a search is made of the combined trellis, where the branch metrics are modified to include the source transition matrix. Simulation results of image transmission are provided using the optimized system, including mismatched channel cases.