MAP symbol decoding in channels with error bursts

We analyze the forward-backward algorithm for the maximum a posteriori (MAP) decoding of information transmitted over channels with memory and propose a suboptimal forward-only algorithm. We assume that both the information source and channel are described using hidden Markov models (HMMs). The algorithm lends itself to parallel implementation and pipelining. We apply the algorithm to MAP decoding of symbols which were trellis-code modulated and transmitted over channels with error bursts     

A BEM-based detector for CPM signals transmitted over frequency-flat fading channels

In this paper, the expectation-maximization (EM) algorithm for maximum a posteriori (MAP) estimation of a random vector is applied to the problem of symbol detection for continuous phase modulation signals transmitted over time-selective Rayleigh-fading channels. This results in a soft-in-soft-out detection algorithm suitable for iterative detection/decoding schemes. Simulation results show that the error performance provided by the proposed solution is very close to that of a MAP detector endowed with an ideal knowledge of the channel state both in uncoded and coded transmissions.     

A class of generalized LDPC codes with fast parallel decoding algorithms

Given the Tanner graph of a generalized low-density parity-check (GLDPC) code, the decoding complexity is mainly dominated by the decoding algorithm of subcodes. In this paper, we propose a class of GLDPC codes with fast parallel decoding algorithm. The parity-check matrices of the newly constructed subcodes are composed of several square matrices, which can be viewed as elements of a finite field. Therefore the FFT-based a posteriori probability (APP) algorithm for nonbinary codes can be applied to decode the subcodes. When compared with the trellis-based APP algorithm, the FFT-based APP algorithm can be implemented in parallel and has lower complexity. Simulation results show that the proposed GLDPC codes perform well on AWGN channels.     

Modification of the MAP algorithm for memory savings

It is usually assumed that all state metric values are necessary in the maximum a posteriori (MAP) algorithm in order to compute the a posteriori probability (APP) values. This work extends the mathematical derivation of the original MAP algorithm and shows that the log likelihood values can be computed using only partial state metric values. By processing N stages in a trellis concurrently, the proposed algorithm results in savings in the required memory size and leads to a power efficient implementation of the MAP algorithm in channel decoding. The computational complexity analysis for the proposed algorithm is presented. Especially for the N=2 case, we show that the proposed algorithm halves the memory requirement without increasing the computational complexity.     

On turbo code decoder performance in optical-fiber communication systems with dominating ASE noise

In this paper, we study the effects of different ASE noise models on the performance of turbo code (TC) decoders. A soft-decoding algorithm, the Bahl, Cocke, Jelinek, and Raviv (BCJR) decoding algorithm, is generally used in TC decoders. The BCJR algorithm is a maximum a posteriori probability (MAP) algorithm, and is very sensitive to noise statistics. The Gaussian approximation of ASE noise is widely used in the study of optical-fiber communication systems, and there exist standard TCs for additive white Gaussian noise (AWGN) channels. We show that using a MAP decoding algorithm based on the Gaussian noise assumptions, however, may significantly degrade the TC decoder performance in an optical-fiber channel with non-Gaussian ASE noise. To take full advantage of TC, accurate noise statistics in optical-fiber transmissions should be used in the MAP decoding algorithm.     

A dynamic programming algorithm for simultaneous phase estimation and data decoding on random-phase channels

The problem of simultaneously estimating phase and decoding data symbols from baseband data is posed. The phase sequence is assumed to be a random sequence on the circle, and the symbols are assumed to be equally likely symbols transmitted over a perfectly equalized channel. A dynamic programming algorithm (Viterbi algorithm) is derived for decoding a maximum {em a posteriori} (MAP) phase-symbol sequence on a finite dimensional phase-symbol trellis. A new and interesting principle of Optimality for simultaneously estimating phase and decoding phase-amplitude coded symbols leads to an efficient two-step decoding procedure for decoding phase-symbol sequences. Simulation results for binary,8-ary phase shift keyed (PSK), and 16-quadrature amplitude shift keyed (QASK) symbol sets transmitted over random walk and sinusoidal jitter channels are presented and compared with results one may obtain with a decision-directed algorithm or with the binary Viterbi algorithm introduced by Ungerboeck. When phase fluctuations are severe and when occasional large phase fluctuations exist, MAP phase-symbol sequence decoding on circles is superior to Ungerboeck's technique, which in turn is superior to decision-directed techniques.     

Low-complexity iterative decoding with decision-aided equalizationfor magnetic recording channels

Turbo codes are applied to magnetic recoding channels by treating the channel as a rate-one convolutional code that requires a soft a posteriori probability (APP) detector for channel inputs. The complexity of conventional APP detectors, such as the BCJR algorithm or the soft-output Viterbi algorithm (SOVA), grows exponentially with the channel memory length. This paper derives a new APP module for binary intersymbol interference (ISI) channels based on minimum mean squared error (MMSE) decision-aided equalization (DAE), whose complexity grows linearly with the channel memory length, and it shows that the MMSE DAE is also optimal by the maximum a posteriori probability (MAP) criterion. The performance of the DAE is analyzed, and an implementable turbo-DAE structure is proposed. The reduction of channel APP detection complexity reaches 95% for a five-tap ISI channel when the DAE is applied. Simulations performed on partial response channels show close to optimum performance for this turbo-DAE structure. Error propagation of the DAE is also studied, and two fixed-delay solutions are proposed based on combining the DAE with the BCJR algorithm     

A per-survivor phase-estimation algorithm for detection of PSKsignals

An expectation-maximization (EM) technique for maximum a posteriori (MAP) estimation of a random parameter is employed to devise a per-survivor phase-tracking algorithm for phase-shift-keyed signals transmitted over channels with phase jitter. Simulation results show that the proposed algorithm can provide substantial performance gains over recursive and nonrecursive phase estimators in the presence of a strong phase jitter     

Speech-to-Lip Movement Synthesis by Maximizing Audio-Visual Joint Probability Based on the EM Algorithm

In this paper, we investigate a Hidden Markov Model (HMM)-based method to drive a lip movement sequence with input speech. In a previous study, we have already investigated a mapping method based on the Viterbi decoding algorithm which converts an input speech signal to a lip movement sequence through the most likely HMM state sequence using audio HMMs. However, the method can result in errors due to incorrectly decoded HMM states. This paper proposes a method to re-estimate visual parameters using HMMs of audio-visual joint probability using the Expectation-Maximization (EM) algorithm. In the experiments, the proposed mapping method results in a 26% error reduction when compared to the Viterbi-based algorithm at incorrectly decoded bilabial consonants.     

Low complexity decision-aided decoder for turbo DPSK

A new decision-aided soft a posteriori probability (APP) algorithm for iterative differential phase-shift keying (DPSK) signal demodulation/decoding in a Rayleigh flat-fading channel is presented. Compared with conventional APP algorithms for iterative DPSK, the new algorithm results in considerably lower decoding cost yet can achieve nearly the same performance     

The max-log list algorithm (MLLA)-a list-sequence decoding algorithm that provides soft-symbol output

We present a soft decoding algorithm for convolutional codes that simultaneously yields soft-sequence output, i.e., list sequence (LS) decoding, and soft-symbol output. The max-log list algorithm (MLLA) introduced in this paper provides near-optimum soft-symbol output equal to that of the max-log maximum a posteriori (MAP) probability algorithm. Simultaneously, the algorithm produces an ordered list containing LS-MAP estimates. The MLLA exists in an optimum and a suboptimum version that are different in that the optimum version produces optimum LS-MAP decoding for arbitrary list lengths, while the suboptimum low-complexity version only provides the MAP, the second-order MAP, and the third-order MAP sequence estimates. For lists with more than three elements, MAP decoding is not guaranteed, but the LS decoding is close to the optimal. It is demonstrated that the suboptimum/optimum MLLA can be used to obtain the combination of soft-symbol and soft-sequence outputs at lower complexity than a previously published algorithm. Furthermore, the suboptimum MLLA is well suited for operation in an iterative list (turbo) decoder, since it is obtained by only minor modifications of the well-known Max-Log-MAP algorithm frequently used for decoding of the component codes of turbo codes. Another potential area of application for the suboptimum/optimum MLLA is joint source-channel LS decoding. Estimates of complexity and memory use, as well as performance evaluations of the suboptimum/optimum MLLA, are provided in this paper.     

Layered MAP algorithm for MIMO ISI channels

The layered maximum a posteriori （L-MAP） algorithm has been proposed to detect signals under frequency selective fading multiple input multiple output （MIMO） channels. Compared to the optimum MAP detector, the L-MAP algorithm can efficiently identify signal bits, and the complexity grows linearly with the number of input antennas. The basic idea of L-MAP is to operate on each input sub-stream with an optimum MAP sequential detector separately by assuming the other streams are Gaussian noise. The soft output can also be forwarded to outer channel decoder for iterative decoding. Simulation results show that the proposed method can converge with a small number of iterations under different channel conditions and outperforms other sub-optimum detectors for rank-deficient channels.     

Computation of Posterior Marginals on Aggregated State Models for Soft Source Decoding

Optimum soft decoding of sources compressed with variable length codes and quasi-arithmetic codes, transmitted over noisy channels, can be performed on a bit/symbol trellis. However, the number of states of the trellis is a quadratic function of the sequence length leading to a decoding complexity which is not tractable for practical applications. The decoding complexity can be significantly reduced by using an aggregated state model, while still achieving close to optimum performance in terms of bit error rate and frame error rate. However, symbol a posteriori probabilities can not be directly derived on these models and the symbol error rate (SER) may not be minimized. This paper describes a two-step decoding algorithm that achieves close to optimal decoding performance in terms of SER on aggregated state models. A performance and complexity analysis of the proposed algorithm is given.     

Sequence detection and channel state estimation over finite stateMarkov channels

A useful model for general time-varying channels is a finite state Markov chain. In this paper, maximum likelihood sequence estimation (MLSE) for signals over finite state Markov channels (FSMCs) is studied. Also studied is the maximum a posteriori (MAP) channel state estimation. When coded signals with interleaving are transmitted, the channel estimates can be used to make soft-decision decoding. The error performance of the proposed sequence and channel state estimation schemes are evaluated through computer simulations. The effect of channel modeling error is also discussed     

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     

Expectation maximization algorithms for MAP estimation of jumpMarkov linear systems

In a jump Markov linear system, the state matrix, observation matrix, and the noise covariance matrices evolve according to the realization of a finite state Markov chain. Given a realization of the observation process, the aim is to estimate the state of the Markov chain assuming known model parameters. Computing conditional mean estimates is infeasible as it involves a cost that grows exponentially with the number of observations. We present three expectation maximization (EM) algorithms for state estimation to compute maximum a posteriori (MAP) state sequence estimates [which are also known as Bayesian maximum likelihood state sequence estimates (MLSEs)]. The first EM algorithm yields the MAP estimate for the entire sequence of the finite state Markov chain. The second EM algorithm yields the MAP estimate of the (continuous) state of the jump linear system. The third EM algorithm computes the joint MAP estimate of the finite and continuous states. The three EM algorithms optimally combine a hidden Markov model (HMM) estimator and a Kalman smoother (KS) in three different ways to compute the desired MAP state sequence estimates. Unlike the conditional mean state estimates, which require computational cost exponential in the data length, the proposed iterative schemes are linear in the data length     

Iterative reduced-complexity multiuser detection based on Chase decoding for synchronous turbo-coded CDMA system

The conventional multiuser detector (MUD) based on the a posteriori probability (APP) algorithm has an exponential computational complexity in terms of the number of users. In this paper, we propose a low-complexity iterative multiuser receiver for synchronous turbo-coded code-division multiple-access (CDMA) systems. The proposed receiver is based on the Chase decoding algorithm that was previously used to decode turbo product codes. Simulation results show that the proposed receiver can significantly reduce the computational complexity with slight performance degradation compared with the APP MUD over highly correlated channels. Moreover, in this paper, we develop a numerical approach to analyze the convergence behavior of iteratively decoded CDMA channels based on density evolution technique. Analytical results are presented and shown to provide a reasonable match with what is observed in simulation.     

Finite dimensional smoothers for MAP state estimation of bilinearsystems

In this paper, we present two finite-dimensional iterative algorithms for maximum a posteriori (MAP) state sequence estimation of bilinear systems. Bilinear models are appealing in their ability to represent or approximate a broad class of nonlinear systems. Our iterative algorithms for state estimation are based on the expectation-maximization (EM) algorithm and outperform the widely used extended Kalman smoother (EKS). Unlike the EKS, these EM algorithms are optimal (in the MAP sense) finite-dimensional solutions to the state sequence estimation problem for bilinear models. We also present recursive (on-line) versions of the two algorithms and show that they outperform the extended Kalman filter (EKF). Our main conclusion is that the EM-based algorithms presented in this paper are novel nonlinear filtering methods that perform better than traditional methods such as the EKF     

BEM-based SISO detection of orthogonal space-time block codes over frequency flat-fading channels

The expectation-maximization algorithm for maximum a posteriori (MAP) estimation of a random vector is applied to the problem of detection of orthogonal space-time block codes over time-selective Rayleigh fading channels. This results in a soft-in soft-out detection algorithm suitable for iterative detection/decoding schemes. Simulation results show that the error performance of the proposed detection algorithm is very close to that of a MAP detector endowed with an ideal knowledge of the channel state if the fading rate is not too fast.