Sequential sequence estimation for trellis-coded modulation onmultipath fading ISI channels

A new receiver structure is proposed for trellis-coded modulation on multipath fading intersymbol interference (ISI) channels that permits the use of large-state trellis codes. The receiver uses a sequential sequence estimator with the Fano algorithm, and a channel estimator consisting of a fast nonrecursive start-up algorithm for training and the LMS algorithm for tracking. During the tracking mode, the channel estimates are updated dynamically by using recent tentative decisions produced by the sequential sequence estimator. This approach results in good tracking even on rapidly varying channels, and reduces the degradation in performance of the sequential sequence estimator due to channel estimation error. The effect of fading is mitigated using both implicit time diversity in the form of interleaved trellis-coded modulation and explicit antenna diversity     

Error probabilities on fading channels with intersymbolinterference and noise

Sums of infinite sequences of weighted binary random variables arise in communications problems involving signal-dependent interferences. In many cases of practical importance, the distribution functions of these sums are singular and often of Cantor type; they are continuous but do not have a density function. For this reason, special methods of calculating expectations are needed. Results of this type are derived. The method is used to compute error probabilities for differential detection of minimum shift keying, and for noncoherent detection of frequency shift keying. In each case the model assumed is a Rician fading channel     

Turbo equalization with sequential sequence estimation overmultipath fading channels

We investigate the performance of a turbo equalization scheme over frequency-selective fading channels, where a soft-output sequential algorithm is employed as the estimation algorithm. The advantage of this scheme comes from the low computational complexity of the sequential algorithm, which is only linearly dependent on the channel memory length. Simulation results of an 8-PSK trellis-coded modulation (TCM) system show that the performance of this scheme suffers approximately 2-dB loss compared with that of the turbo max-log maximum a posteriori (MAP) probability equalizer after 5 iterations     

Sequential sequence estimation for multiple-channel systems withintersymbol and interchannel interference

A vector sequential sequence estimator is proposed for multiple-channel systems with both intersymbol interference (ISI) and interchannel interference (ICI). Both finite ISI-ICI and infinite ISI-ICI are considered. The estimator consists of a multiple-dimensional whitened matched filter and a vector sequential decoder. The metric of the sequential algorithm is derived, and the algorithm's performance is analyzed. Computer simulation results for a two-dimensional finite ISI-ICI channel and a two-dimensional infinite ISI-ICI channel are presented. Analysis and simulation show that the symbol error probability of the vector sequential algorithm is essentially the same as for maximum-likelihood sequence estimation using the vector Viterbi algorithm, while its average computational complexity is much less, although computation per symbol is a random variable with the Pareto distribution. There exists a signal-to-noise ratio above which the ensemble average computation is bounded. An upper bound on this ratio is found     

Reduced-state sequence estimation for coded modulation ofintersymbol interference channels

The authors investigated the detection of trellis codes designed for channels that are intersymbol interference free when they operate in the presence of intersymbol interference. A well-structured reduced-state sequence estimation (RSSE) algorithm is described which can achieve the performance of maximum-likelihood sequence estimation (MLSE) with drastically reduced complexity. Well-defined reduced-state trellises are first constructed by merging the states of the ML supertrellis using set partitioning principles. Then the Viterbi algorithm is used to search these trellises. A special case of RSSE, called parallel decision-feedback decoding, uses the encoder trellis, yet on channels with large attenuation distortion it can provide a significantly better performance than linear equalization. The performance of RSSE is examined analytically and through simulation, and then compared to that of MLSE and ideal decision-feedback equalization. It is noted that the performance advantage of RSSE can be obtained without significantly increasing the decoding delay or complicating an adaptive implementation     

The capacity region of broadcast channels with intersymbolinterference and colored Gaussian noise

We derive the capacity region for a broadcast channel with intersymbol interference (ISI) and colored Gaussian noise under an input power constraint. The region is obtained by first defining a similar channel model, the circular broadcast channel, which can be decomposed into a set of parallel degraded broadcast channels. The capacity region for parallel degraded broadcast channels is known. We then show that the capacity region of the original broadcast channel equals that of the circular broadcast channel in the limit of infinite block length, and we obtain an explicit formula for the resulting capacity region. The coding strategy used to achieve each point on the convex hull of the capacity region uses superposition coding on some or all of the parallel channels and dedicated transmission on the others. The optimal power allocation for any point in the capacity region is obtained via a multilevel water-filling. We derive this optimal power allocation and the resulting capacity region for several broadcast channel models     

Chernoff bound for channels with infinite memory

The problem of Chernoff bounding is analyzed for symmetric channels with input alphabet of arbitrary finite size or erasure channels with no crossover errors whose memory may be described in terms of the noise sequences by an infinite ergodic irreducible aperiodic Markov chain. Necessary and sufficient conditions are described which guarantee the existence of an exponential upper bound to the probability of error for block coding. These conditions are given in terms of the transition matrix of the Markov chain. It will be observed that, although their application involves merely an inspection of the transition matrix, they are based on the topology of the Markov chain and the convergence of sequences of transition probabilities.     

Wavelet-based separating kernels for sequence estimation withunknown rapidly time-varying channels

A new method for blind maximum-likelihood sequence estimation is proposed. The unknown channel time variations are decomposed using optimal unconditional bases such as orthonormal wavelet bases. It is shown that it is possible to represent the channel in a reduced-order dimensional space by matching the scattering function of the multipath channel to its decomposition and obtain an approach to per-survivor processing that is effective in fast fading environments such as those practically found in macrocell wireless communication applications     

Constrained block codes for class-IV partial-response channels withmaximum-likelihood sequence estimation

Significant improvements in magnetic storage densities have been made feasible by the application of partial-response signaling combined with maximum-likelihood sequence estimation. To enhance the performance of this technique when applied to the class-IV partial-response channel, which is recognized as being appropriate to model the magnetic recording channel, it is often required to bound the number of consecutive zeros in the recorded data sequence and its odd and even subsequences. We investigate block codes that satisfy such a constraint. In particular, we look for a set of maximal number of fixed-length sequences such that any pair of them can be concatenated without violating the constraint. In many cases, depending on the constraint and the length of the sequences, we determine such a set, and in the remaining cases, we determine at most three candidates for it. These results are used to study the best possible constrained block codes     

On adaptive decision-feedback equalization of intersymbolinterference channels in coded modulation systems

Recently, Eyuboglu (1988) has shown that adaptive noise-predictive decision-feedback equalization (DFE) can be combined with coded modulation to achieve high-speed data transmission by periodic interleaving. In this paper, we present a new method of adaptive DFE with periodic interleaving for coded modulation systems. The method is an improved version of that proposed by Eyuboglu, where the deinterleaving operation is performed on a vector-by-vector basis, instead of a sample-by-sample basis. Unlike the original system in which the linear equalizer's coefficients can be adjusted only with hard decisions from the threshold detector, the improved structure updates the coefficients of both the linear equalizer and the noise predictor based on soft decisions from the most likely path in the soft decoder. The improved system achieves better error-rate performance than the original with a little increase in hardware complexity. As compared to another improved design reported by Zhou et al. (1990), the new structure also gains advantages in error-rate performance, hardware complexity, and throughput delay     

Formulas for linear optimal control over a finite or infinite interval

Algebraic expressions are given for the solution of the optimal-linear-regulator problem for a constant plant and quadratic performance index. They enable the time-varying or constant feedback gains and the resulting plant trajectories to be found.     

Computational complexity of sequential sequence estimation forintersymbol interference channels

The computational complexity of a sequential algorithm (SA) developed for intersymbol interference (ISI) channels is analyzed. To determine the computational complexity, the finite-state machine that models the channel and white matched filter system, of which the SA is a part, is interpreted as a special convolutional encoder followed by a binary symbol to Q-ary symbol mapping. It follows that the computational distribution is Pareto, and that there exists a computational cutoff rate R_comp. For the uncoded data considered, the rate is fixed and the R_comp criterion translates into a signal-to-noise ratio (SNR) criterion. An upper bound on SNR_comp is found analytically by assuming a uniform input distribution. Iteration equations developed by S. Arimoto (1976) are adapted to find the true SNR_comp numerically     

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     

Sequential decoding for multiple access channels

The use of sequential decoding in multiple access channels is considered. The Fano metric, which achieves all achievable rates in the one-user case, fails to do so in the multiuser case. A new metric is introduced and an inner bound is given to it achievable rate region. This inner bound region is large enough to encourage the use of sequential decoding in practice. The new metric is optimal, in the sense of achieving all achievable rates, in the case of one-user and pairwise-reversible channels. Whether the metric is optimal for all multiple access channels remains an open problem. It is noted that even in the one-user case, the new metric differs from the Fano metric in a nontrivial way, showing that the Fano metric is not uniquely optimal for such channels. A new and stricter criterion of achievability in sequential decoding is also introduced and examined     

A Bayesian maximum-likelihood sequence estimation algorithm for apriori unknown channels and symbol timing

It is shown that the optimum demodulator for the case of an a priori unknown channel and symbol timing can be approximated using a modified Viterbi algorithm (VA), in which the branch metrics are obtained from the conditional innovations of a bank of extended Kalman filters (EKFs). Each EKF computes channel and timing estimates conditioned on one of the survivor sequences in the trellis. It is also shown that the minimum-variance channel and timing estimates can be approximated by a sum of conditional EKF estimates, weighted by the VA metrics. Simulated bit error rate (BER) results and averaged-squared channel/timing error trajectories are presented, with estimation errors compared to the Cramer-Rao lower bound. The BER performance of the modified VA is also shown to be superior to that obtained using a decision-directed channel/timing estimation algorithm     

Maximum likelihood sequence estimation of CPM signals transmittedover Rayleigh flat-fading channels

A method for the sequential updating of log-likelihood functions for maximum-likelihood sequence estimation is presented. It is shown that, in a general case, this method can be implemented using Kalman filtering techniques. For the special case of Rayleigh flat fading and continuous phase modulation (CPM) signaling, this approach is shown to lead to an attractive receiver structure. This type of receiver, called the linear predictive receiver, can be implemented in the form of the Viterbi algorithm with the trellis updates being computed using a bank of finite pulse response (FIR) filter and square operations. Simulation results are presented that demonstrate the superiority of the linear predictive receiver over receivers employing differential detection, in the presence of fast fading. It is shown that the optimal linear predictive receiver does not possess an irreducible error rate for a class of Rayleigh fading channels used to model terrestrial mobile channels     

Reduced-state sequence estimation of digital sequences indispersive channels using state partitioning

A reduced-state sequence estimator for linear dispersive channels is described. The estimator is based on partitioning the set of all possible channel states in a way that defines a trellis with fewer states, and thus reduces complexity. Such a set partitioning approach provides a good performance/complexity tradeoff. The new technique is a generalisation of that described by Duel-Hallen and Heegard [1989]. The Viterbi algorithm (VA) is used to search for the best path through the reduced state trellis     

Bit error rate estimation for channels with memory

A method for deriving key parameters of a bit-error-rate (BER) estimate is presented. The method is based on a bursty channel model proposed by B.D. Fritchman (IEEE Trans. Inform. Theory, Vol. IT-13, pp.221-227, Apr. 1967). This model is used to derive the confidence levels and confidence intervals of an error-rate estimate. The theoretical results have been confirmed experimentally by using the data from a helical-scan digital magnetic-tape recorder. The experiments clearly demonstrate the inadequacy of the BER estimates based on an independent-error approach     

Error probability of reduced-state sequence estimation fortrellis-coded modulation on intersymbol interference channels

The error probability of reduced-state sequence estimation (RSSE) for trellis-coded modulation (TCM) on intersymbol interference channels is evaluated. A method based on a stack algorithm is proposed to evaluate the union bound on the error probability for ideal RSSE, which is a good approximation to the error probability of real RSSE. The stack algorithm is employed because it provides a good tradeoff between computer memory and computing time