Capacity-achieving codes for finite-state channels with maximum-likelihood decoding

Codes on sparse graphs have been shown to achieve remarkable performance in point-to-point channels with low decoding complexity. Most of the results in this area are based on experimental evidence and/or approximate analysis. The question of whether codes on sparse graphs can achieve the capacity of noisy channels with iterative decoding is still open, and has only been conclusively and positively answered for the binary erasure channel. On the other hand, codes on sparse graphs have been proven to achieve the capacity of memoryless, binary-input, output-symmetric channels with finite graphical complexity per information bit when maximum likelihood (ML) decoding is performed. In this paper, we consider transmission over finite-state channels (FSCs). We derive upper bounds on the average error probability of code ensembles with ML decoding. Based on these bounds we show that codes on sparse graphs can achieve the symmetric information rate (SIR) of FSCs, which is the maximum achievable rate with independently and uniformly distributed input sequences. In order to achieve rates beyond the SIR, we consider a simple quantization scheme that when applied to ensembles of codes on sparse graphs induces a Markov distribution on the transmitted sequence. By deriving average error probability bounds for these quantized code ensembles, we prove that they can achieve the information rates corresponding to the induced Markov distribution, and thus approach the FSC capacity.     

Low-complexity bit-interleaved coded DAPSK for Rayleigh-fading channels

We analyze the achievable performance of bit-interleaved coded differential amplitude and phase-shift keying (DAPSK) systems over frequency nonselective Rayleigh-fading channels with suboptimal differential detection assuming an ideal bit interleaving. The suboptimal differential detection in this work refers to the bit metric calculation based only on the difference between two consecutive symbols, in contrast to more complex maximum-likelihood (ML)-based differential detection, which makes use of all the observed consecutive symbols for its metric calculation in channel decoding. As benchmarks of coded system performance, we analyze the average mutual information (AMI) and cutoff rate of this system. Exact probability density functions of the suboptimal differential detector outputs are derived for this purpose. Comparative studies suggest that the performance loss of the suboptimal approach is in fact noticeable. Therefore, we also develop a low-complexity receiver structure in the framework of suboptimal differential detection that can approach the performance of ML-based system by suitably incorporating the amplitude statistics of received symbols. The theoretical framework developed in this paper is also confirmed by simulations using convolutional and turbo codes.     

Capacity analysis for finite-state Markov mapping of flat-fading channels

In this paper, time-varying flat-fading channels are modeled as first-order finite-state Markov channels (FSMC). The effect of this modeling on the channel information capacity is addressed. The approximation accuracy of the first-order memory assumption in the Markov model is validated by comparing the FSMC capacity with the channel capacity assuming perfect state information at the receiver side. The results indicate that the first-order Markovian assumption is accurate for normalized Doppler frequencies f/sub d/T /spl lsim/ 0.01, in amplitude-only quantization of the channel gain for noncoherent binary signaling. In phase-only and joint phase and amplitude quantization of the channel gain for coherent binary signaling, the first-order Markovian assumption is accurate for f/sub d/T /spl lsim/ 0.001. Furthermore, the effect of channel quantization thresholds on the FSMC capacity is studied. In high signal-to-noise ratio (SNR) conditions, nonuniform two-level amplitude quantization scheme outperforms equiprobable quantization method by 0.8-1.5 dB.     

Iterative multiuser detection for coded CDMA signals in AWGN andfading channels

A new iterative receiver for joint detection and decoding of code division multiple access (CDMA) signals is presented. The new scheme is based on a combination of the minimum mean square error (MMSE) criterion and the turbo processing principle by Hagenauer (see Proc. Int. Symp. Turbo Codes and Related Topics, Brest, France, p.1-9, 1997). The complexity of the new scheme is of polynomial order in the number of users. The new scheme is applicable to two situations: (a) when the receiver is capable of decoding the signals from all users and (b) when the receiver is only capable of decoding the signals from a subset of users. In the first scenario, we establish that the proposed receiver achieves superior performance to the iterative soft interference cancellation technique under certain conditions. On the other hand, in the second scenario, we argue that the proposed receiver outperforms both the iterative soft interference canceler and the iterative maximum a posteriori (MAP) receiver because of its superior near-far resistance. For operation over fading channels, the estimation of the complex fading parameters for all users becomes an important ingredient in any multiuser detector. In our scheme, the soft information provided by the decoders is used to enhance this estimation process. Two iterative soft-input channel estimation algorithms are presented: the first is based on the MMSE criterion, and the second is a lower-complexity approximation of the first. The proposed multiuser detection algorithm(s) are suitable for both terrestrial and satellite applications of CDMA     

Noncoherent maximum-likelihood block detection of orthogonalNFSK-LDPSK signals

This paper investigates the noncoherent block detection of orthogonal N frequency-shift keying (FSK)-L differential phase shift keying (DPSK) signals transmitted over the additive white Gaussian noise channel, based on the principle of maximum-likelihood (ML) sequence estimation. By virtue of a union bound argument, asymptotic upper bounds for the bit error probability of the developed ML block receiver are derived and verified by simulation. It is analytically shown that the noncoherent NFSK-LDPSK ML block receiver performs comparably with the ideal coherent NFSK-L phase shift keying (PSK) receiver for L = 2 and 4, as the observation block length is large enough. Furthermore, substantial performance improvement can be achieved by the ML block detection of the NFSK-LDPSK signal with L > 2 by increasing the observation block length     

Decoding of low-density parity-check codes over finite-state binary Markov channels

We propose a modified algorithm for decoding of low-density parity-check codes over finite-state binary Markov channels. The proposed approach clearly outperforms systems in which the channel statistics are not exploited in the decoding, even when the channel parameters are not known a priori at the decoder.     

Markov chain model in maximum-likelihood sequence detection for free-space optical communication through atmospheric turbulence channels

In free-space optical communication links using intensity modulation and direct detection (IM/DD), atmospheric turbulence-induced intensity fluctuations can significantly impair link performance. Communication techniques can be applied to mitigate turbulence-induced intensity fluctuations (i.e., signal fading) in the regime in which the receiver aperture D/sub 0/ is smaller than the fading correlation length d/sub 0/ and the observation interval T/sub 0/ is smaller than the fading correlation time /spl tau//sub 0/. If the receiver has knowledge of the joint temporal statistics of the fading, maximum-likelihood sequence detection (MLSD) can be employed, but at the cost of high computational complexity. We introduce a single-step Markov chain (SMC) model for the fading correlation and use it to derive two low-complexity, suboptimal MLSD algorithms based on per-survivor processing (PSP). Simulations are presented to verify the SMC model and the performance improvement achieved using these suboptimal per-survivor processing (PSP) algorithms.     

Fast simulation of diversity Nakagami fading channels using finite-state Markov models

We designed a multi-channel Nakagami fading simulator by modeling the received combined signal-to-noise ratio as a finite-state Markov chain, following a previously proposed approach. Our model generates directly the error process at the output of a diversity receiver and can emulate selection, maximal-ratio, and equal-gain combining. As the order of diversity increases, the savings in computational complexity improve linearly with respect to a traditional waveform simulator. The level crossing rates of the simulated envelope are shown to be very close to their theoretical values. The simulator's performance is also evaluated in terms of the accuracy of the obtained bit error rates, for both uncoded and coded systems. The simulator speeds up the performance evaluation of high-rate communication links where a high number of samples is needed.     

Suboptimal maximum-likelihood multiuser detection of synchronousCDMA on frequency-selective multipath channels

We propose a signal processing technique, based on the estimate-maximize algorithm, in order to perform multiuser code-division multiple-access (CDMA) detection. This algorithm iteratively seeks for the maximum-likelihood solution. The resulting structure is a successive interference cancellation scheme which can be applied to both synchronous and asynchronous CDMA. Higher performance than similar methods is obtained from using deterministic annealing and multiple stages. A soft output is defined, and the signal-to-noise ratio in the soft output of the detector is measured for predicting performance with an outer code with soft input decoder. The new receiver is applied to the problem whereby in a synchronous CDMA system the orthogonality of the codes is destroyed by a frequency-selective channel, caused by multipath fading. This nonlinear technique is shown to perform much better than the minimum mean-square-error linear solution and several other algorithms. The algorithm lends itself to an efficient DSP or VLSI implementation. We evaluate the performance by simulations with coherent quadrature phase-shift keying modulation, known channel and long random Rayleigh multipath. In most cases, we set the number of users equal to the processing gain for maximal throughput. The results are also presented in the form of outage probabilities for random Rayleigh multipath against required fading margin     

Low-complexity blind detection of DS/CDMA signals: auxiliary-vectorreceivers

A fresh look on the design of practical low-complexity direct-sequence code-division multiple-access (DS/CDMA) receivers is proposed from the Wiener reconstruction-filter point of view. The natural outcome is the emergence of a new class of linear scalar-parameterized auxiliary-vector receivers (filters). Then, the blind optimization of these receivers in the maximum signal-to-interference-plus-noise-ratio (SINR) sense becomes a straightforward procedure. The conceptual and computational simplicity of this general approach promises immediate practical utility. This new generation of receivers exhibits minimal optimization requirements and near-matched-filter (MF) operational complexity. Yet, theoretical arguments supported by numerical and simulation results included in this work suggest that the blind auxiliary-vector receiver compares favorably, both complexity-wise and performance-wise, to multiuser (MU) detectors such as the minimum output energy (MOE) and the decorrelating receiver (although the latter utilizes the assumed known spreading codes of all interfering users)     

Low-complexity blind multiuser detection of DS-CDMA signal in dispersive channels

The problem of blind multiuser detection in dispersive channels of Code-Division Multiple-Access (CDMA) in the presence of both Multiple-Access Interference (MAI) and In-terSymbol Interference (ISI) is considered. In practice, it is showed that by incorporating the desired user's signature waveform and the auxiliary vector, the information of the user can be identified using the suboptimal subspace method. The major contribution of this paper is to propose a minimum-mean-square-error detector with the suboptimal subspace-based blind technique for joint suppression of MAI and ISI in the dispersive CDMA channels.     

Equilibrium distribution of finite-state Markov processes

Very simple methods are presented for computing equilibrium distributions of finite-state Markov processes in continuous time and in discrete time, namely Markov chains. These use the APL domino function which takes a least-squares approach which is efficient with systems of up to 50 states and probably more. This approach can also be used to solve for mean interval occupancies. It is not suggested that the least-squares solution be implemented in traditional languages like Fortran simply for the purpose of finding equilibrium distributions, for which the state reduction method is simpler. However, if APL is available the methods described provide accurate and extremely simple solutions for discrete or continuous-time models. More importantly, the APL domino function leads to a powerful and simple computation of mean interval occupancies and, hence, availabilities     

Low-complexity blind carrier frequency recovery for OFDM signals over frequency-selective radio channels

This paper introduces a blind (i.e., data independent) algorithm for carrier frequency offset recovery in an orthogonal frequency-division multiplexing (OFDM) receiver operating over frequency-selective fading channels. The main idea behind this algorithm is to exploit the time-frequency-domain exchange inherent to the modulation scheme. Due to this feature, a carrier frequency offset has a similar impact on OFDM as a clock timing offset has in a quadrature amplitude modulation (QAM) system. The scheme we propose is a variant of Oerder-Meyr's (1988) feedforward clock recovery. Its performance is assessed by simulation, and the results are compared to those obtained from Van de Beek-Sandell-Borjesson's (1997) frequency synchronizer, which bears comparable complexity. The new scheme is shown to outperform the latter over frequency-selective fading channels, notably at medium to high signal-to-noise ratios. We also evaluated the efficiency of two different (time domain and frequency domain) offset correction strategies embedded in a particular OFDM receiver.     

Low-complexity feedforward symbol timing estimator using conditional maximum-likelihood principle

A low complexity feedforward symbol-timing estimator based on the conditional maximum-likelihood principle is proposed. An approximation is applied to the Fourier series expansion of the conditional maximum-likelihood function such that implementation complexity is greatly reduced. It is shown that the proposed estimator can be viewed as a generalization of the well-known square nonlinearity estimator proposed by Oerder and Meyr in 1988. Simulation results show that the performance of the proposed estimator is very close to the conditional Cramer-Rao bound and is better than that of the square nonlinearity estimator.     

Low-complexity LDPC coded BICM-ID with orthogonal modulations

A low-complexity low density parity check (LDPC) coded bit-interleaved coded modulation with iterative decoding (BICM-ID) scheme with orthogonal modulations is proposed. With a novel mapping strategy of coded bits to symbols, the proposed scheme is equivalent to a generalised LDPC code with Hadamard constraints and thus orthogonal demodulation can be merged into the iterative LDPC decoding process, resulting in a simpler implementation and a lower computational complexity.     

Universal decoding for finite-state channels

Universal decoding procedures for finite-state channels are discussed. Although the channel statistics are not known, universal decoding can achieve an error probability with an error exponent that, for large enough block length (or constraint length in case of convolutional codes), is equal to the random-coding error exponent associated with the optimal maximum-likelihood decoding procedure for the given channel. The same approach is applied to sequential decoding, yielding a universal sequential decoding procedure with a cutoff rate and an error exponent that are equal to those achieved by the classical sequential decoding procedure.     

Convolutional coding for finite-state channels

We propose new decoders for decoding convolutional codes over finite-state channels. These decoders are sequential and utilize the information about the channel state sequence contained in the channel output sequence. The performance of these decoders is evaluated by simulation and compared to the performance of memoryless decoders with and without interleaving. Our results show that the performance of these decoders is good whenever the channel statistics are such that the joint estimate of the channel state sequence and the channel input sequence is good, as, for example, when the channel is bursty. In these cases using even a partial search decoder such as the Fano decoder over the appropriate trellis is nearly optimal. However, when the information between the output sequence and the sequence of channel slates and inputs diminishes, the memoryless decoder with interleaving outperforms even the optimal decoder which knows the channel state     

Generalised Viterbi algorithm for trellis coded signals transmittedthrough broadband wireless channels

A receiver structure is proposed for trellis coded signals transmitted through broadband wireless channels based on the generalised Viterbi algorithm (GVA). Simulation results show that the proposed receiver structure is suitable for high bit rate wireless applications and gives close to optimal performances with reasonable complexity     

Feedback capacity of finite-state machine channels

We consider a finite-state machine channel with a finite memory length (e.g., finite length intersymbol interference channels with finite input alphabets-also known as partial response channels). For such a finite-state machine channel, we show that feedback-dependent Markov sources achieve the feedback capacity, and that the required memory length of the Markov process matches the memory length of the channel. Further, we show that the whole history of feedback is summarized by the causal posterior channel state distribution, which is computed by the sum-product forward recursion of the Bahl-Cocke-Jelinek-Raviv (BCJR) (Baum-Welch, discrete-time Wonham filtering) algorithm. These results drastically reduce the space over which the optimal feedback-dependent source distribution needs to be sought. Further, the feedback capacity computation may then be formulated as an average-reward-per-stage stochastic control problem, which is solved by dynamic programming. With the knowledge of the capacity-achieving source distribution, the value of the capacity is easily estimated using Markov chain Monte Carlo methods. When the feedback is delayed, we show that the feedback capacity can be computed by similar procedures. We also show that the delayed feedback capacity is a tight upper bound on the feedforward capacity by comparing it to tight existing lower bounds. We demonstrate the applicability of the method by computing the feedback capacity of partial response channels and the feedback capacity of run-length-limited (RLL) sequences over binary symmetric channels (BSCs).