Joint signal detection and parameter estimation in multiusercommunications

The problem of simultaneously detecting the information bits and estimating signal amplitudes and phases in a K-user asynchronous direct-sequence spread-spectrum multiple-access communication system is addressed. The joint maximum-likelihood (ML) estimator has a computational complexity that is exponential in the total number of bits transmitted and thus does not represent a practical solution to the problem. An estimator that combines a suboptimum tree-search algorithm with a recursive least-squares estimator of complex signal amplitude is considered. The complexity of this estimator is O(K²) computations per decoded bit, and its performance is very close to that of the joint ML receiver. This receiver has the advantage that the transmitted signal powers and phases are extracted from the received signal in an adaptive fashion without using a test sequence     

Performance analysis of RS-coded M-ary FSK forfrequency-hopping spread spectrum mobile radios

Decoding performance of Reed-Solomon (RS) coded M-ary FSK with noncoherent detection in a frequency-hopping spread spectrum mobile radio channel is theoretically analyzed. Exact formulas and an approximate one for evaluating word error rates (WERs) of error correction and error-and-erasure correction schemes on decoding the RS codes are derived. It is shown that with K symbol erasure and C symbol error detection, RS coded M-ary FSK achieves the equivalent diversity order of (K+1)(C+1)     

A convolutional single-parity-check concatenated coding scheme forhigh-data-rate applications

The coding scheme uses a set of n convolutional codes multiplexed into an inner code and a (n,n-1) single-parity-check code serving as the outer code. Each of the inner convolutional codes is decoded independently, with maximum-likelihood decoding being achieved using n parallel implementations of the Viterbi algorithm. The Viterbi decoding is followed by additional outer soft-decision single-parity-check decoding. Considering n=12 and the set of short constraint length K=3, rate 1/2 convolutional codes, it is shown that the performance of the concatenated scheme is comparable to the performance of the constraint length K=7, rate 1/2 convolutional code with standard soft-decision Viterbi decoding. Simulation results are presented for the K=3, rate 1/2 as well as for the punctured K=3, rate 2/3 and rate 3/4 inner convolutional codes. The performance of the proposed concatenated scheme using a set of K=7, rate 1/2 inner convolutional codes is given     

Coded asynchronous CDMA and its efficient detection

In this paper, receiver design and performance analysis for coded asynchronous code-division multiple access (CDMA) systems is considered. The receiver front-end consists of the near-far resistant multiuser detector known as the projection receiver (PR). The PR performs multiple-access interference resolution and is followed by error-control decoding. The output of the projection receiver yields the appropriate metric (i.e., soft information) for decoding of the coded sequences. An expression for the metric is derived that allows the use of a standard sequence decoder (e.g., Viterbi algorithm, M-algorithm) for the error-control code. It is then shown that the metric computer has an elegant adaptive implementation based on an extension of the familiar recursive least squares (RLS) algorithm. The adaptive PR operates on a single sample per chip and achieves a performance virtually identical to the algebraic PR, but with significantly less complexity. The receiver performance is studied for CDMA systems with fixed and random spreading sequences, and theoretical performance degradations with regard to the single-user bound are derived. The near-far resistance of the PR is also proven, and demonstrated by simulation     

A new Reed-Solomon code decoding algorithm based on Newton'sinterpolation

A Reed-Solomon code decoding algorithm based on Newton's interpolation is presented. This algorithm has as main application fast generalized-minimum-distance decoding of Reed-Solomon codes. It uses a modified Berlekamp-Massey algorithm to perform all necessary generalized-minimum-distance decoding steps in only one run. With a time-domain form of the new decoder the overall asymptotic generalized-minimum-distance decoding complexity becomes O(dn), with n the length and d the distance of the code (including the calculation of all error locations and values). This asymptotic complexity is optimal. Other applications are the possibility of fast decoding of Reed-Solomon codes with adaptive redundancy and a general parallel decoding algorithm with zero delay     

BER analysis of convolution coded QDPSK, in digital mobile radio

The bit error rate (BER) performance of convolutional coded quaternary differential phase-shift keying (QDPSK) with Viterbi decoding is theoretically investigated in Rayleigh fading environments. The probability density functions of the path and branch metric values of Viterbi decoding are derived. The BERs after decoding due to additive white Gaussian noise and cochannel interference are theoretically analyzed. Rate 1/2 codes and their symbol punctured high-rate codes are considered, and the symbol positions for deletion to minimize the BER after decoding are presented for the codes with a constraint length K=3-7. It is shown that Viterbi decoding considerably reduces the desired signal-to-interference power ratio as well as the signal energy per information bit-to-noise power spectrum density ratio necessary to achieve a certain BER. The spectrum efficiency of the cellular mobile radio system, achievable by the use of the symbol punctured codes, is also evaluated     

Multiuser signal detection using sequential decoding

The application of sequential decoding to the detection of data transmitted over the additive white Gaussian noise channel by K asynchronous transmitters using direct-sequence spread-spectrum multiple access (DS/SSMA) is considered. A modification of R.M. Fano's (1963) sequential-decoding metric, allowing the messages from a given user to be safely decoded if its E_b/N₀ exceeds -1.6 dB, is presented. Computer simulation is used to evaluate the performance of a sequential decoder that uses this metric in conjunction with the stack algorithm. In many circumstances, the sequential decoder achieves results comparable to those obtained using the much more complicated optimal receiver     

Multiuser receivers for code-division multiple-access systems withtrellis-based modulation

A code-division multiple-access (CDMA) communication system is studied where a trellis-based scheme is used for data encoding and modulation. The signature sequences (spreading codes), which are assigned to the direct-sequence spread-spectrum (DS/SS) modulator according to the encoding rule, are taken from a biorthogonal set. We derive the optimum detector by maximizing the likelihood ratio. In addition to the optimum multiuser detector with very high computational complexity, we present a multistage detector and a scheme based on a reduced tree search algorithm. The error probability is evaluated by deriving upper and lower bounds as well as by Monte Carlo simulations. We show that the optimum receiver is near-far resistant. The results from the numerical examples indicate that the suboptimum detectors are also capable of alleviating the near-far problem     

Optimization of signal sets for partial-response channels. II.Asymptotic coding gain

For Pt. I see ibid., vol.37, no.5, p.1327-141 (1991). For a linear, time-invariant, discrete-time channel with a given transfer function H(f), and information rate R bits/ T, where T is the symbol interval, an optimal signal set of length K is defined to be a set of 2^RK inputs of length K that maximizes the minimum l₂ distance between pairs of outputs. The author studies the minimum distance between outputs, or equivalently, the coding gain of optimal signal sets as K→∞. He shows how to estimate the coding gain, relative to single-step detection, of an optimal signal set length K when K is large     

Near-optimum detection in synchronous code-division multiple-accesssystems

Communication networks using code division multiple access (CDMA) include applications where several packets of information are transmitted synchronously and simultaneously over a common channel. Consideration is given to the problem of simultaneously demodulating every packet from such a transmission. A nonlinear detection scheme based on a linear complexity multistage multiple-access interference rejection algorithm is studied. A class of linear detectors is considered as constituting the first stage for the multistage detector. A bit-error probability comparison of the linear and multistage detectors is undertaken. It is shown that the multistage detectors are capable of achieving considerable improvements over the linear detectors, particularly in near-far situations, i.e., in the demodulation of weak signals in the presence of strong interfering signals. This problem has been of primary concern for currently operational CDMA systems     

Capacity of frequency-hop spread-spectrum multiple-accesscommunication systems

The information theoretic capacity is considered. In order to account for independent encoding and decoding and private (to the sender and receiver) hopping patterns, an interference channel model is adopted with K sender-receiver pairs with the ith receiver only interested in the message transmitted by the ith sender. Both synchronous and asynchronous hopping patterns are investigated. Although the channel exhibits memory in the latter case, it is possible to compute the capacity region. The asymptotic normalized sum capacity is also computed     

Upper bounds on the probability of sequences emitted byfinite-state sources and on the redundancy of the Lempel-Ziv algorithm

An upper bound on the probability of a sequence drawn from a finite-state source is derived. The bound is given in terms of the number of phrases obtained by parsing the sequence according to the Lempel-Ziv (L-Z) incremental parsing rule, and is universal in the sense that it does not depend on the statistical parameters that characterize the source. This bound is used to derive an upper bound on the redundance of the L-Z universal data compression algorithm applied to finite-state sources, that depends on the length N of the sequence, on the number K of states of the source, and, eventually, on the source entropy. A variation of the L-Z algorithm is presented, and an upper bound on its redundancy is derived for finite-state sources. A method to derive tighter implicit upper bounds on the redundancy of both algorithms is also given, and it is shown that for the proposed variation this bound is smaller than for the original L-Z algorithm, or every value of N and K     

Closest coset decoding of |u|u+v| codes

The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u|u+v| codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined     

The effect of asynchronism on the total capacity of Gaussianmultiple-access channels

The degradation due to complete asynchronism (at the codeword and symbol levels) in the total capacity, maximum rate-sum, of white Gaussian multiple-access channels is investigated. It is shown that asynchronism reduces the total capacity of a K-user channel by at most a factor of K. Moreover, this bound is achieved, in asymptotically high signal-to-noise ratios, by the TDMA signaling strategy. When the signaling strategies are optimally designed to maximize the asynchronous total capacity under bandwidth constraints, the authors find that in a two-user channel: (1) for a certain set of signal-to-noise ratios there is no degradation due to asynchronism, (2) for any bandwidth and signal-to-noise ratios the asynchronous total capacity is at least 88% of the synchronous total capacity, and (3) asynchronism has a vanishing small effect on total capacity for both low and high signal-to-noise ratios     

A general decoding technique applicable to replicated filedisagreement location and concatenated code decoding

Code symbols are treated as vectors in an r-dimensional vector space F^r over a field F. Given any ( n, k) linear block code over F with minimum distance d, it is possible to derive an (n, k) code with symbols over F^r, also with minimum distance d, which can correct any pattern of d-2 or fewer symbol errors for which the symbol errors as vectors are linearly independent. This is about twice the bound on the number of errors guaranteed to be correctable. Furthermore, if the error vectors are linearly dependent and d-2 or fewer in number, the existence of dependence can always be detected. A decoding techinque is described for which complexity increases no greater than as n ³, for any choice of code. For the two applications considered, situations are described where the probability of the error patterns being linearly dependent decreases exponentially with r     

On the decoding of algebraic-geometric codes

A decoding algorithm for algebraic-geometric codes arising from arbitrary algebraic curves is presented. This algorithm corrects any number of errors up to [(d-g-1)/2], where d is the designed distance of the code and g is the genus of the curve. The complexity of decoding equals σ(n³) where n is the length of the code. Also presented is a modification of this algorithm, which in the case of elliptic and hyperelliptic curves is able to correct [(d-1)/2] errors. It is shown that for some codes based on plane curves the modified decoding algorithm corrects approximately d/2-g/4 errors. Asymptotically good q-ary codes with a polynomial construction and a polynomial decoding algorithm (for q⩾361 on some segment their parameters are better than the Gilbert-Varshamov bound) are obtained. A family of asymptotically good binary codes with polynomial construction and polynomial decoding is also obtained, whose parameters are better than the Blokh-Zyablov bound on the whole interval 0<σ<1/2     

A delay independent decorrelating detector for quasi-synchronousCDMA

The decorrelating detector is a near-far resistant linear joint detector for a code-division multiple-access (CDMA) system. It consists of a bank of matched filters followed by a decorrelating matrix. For proper operation, both the matched filter bank and the decorrelating matrix require knowledge of the delays of all users. The delays are due to the different propagation times from each user to the base station. Delay estimation is a weak link in this system since it is complex and prone to error. The proposed decorrelating detector does not require exact knowledge of the user delays, but instead requires that the delays be bounded to a fraction of a symbol interval. The delays are naturally bounded in this way in many microcell and picocell systems where the round trip propagation time is small compared to the symbol interval. The new delay independent decorrelating detector is shown to be near-far resistant and, through appropriate spreading code selection, to experience a modest 3 dB signal-to-noise ratio (SNR) loss relative to orthogonal access schemes. It is also shown to limit capacity to a maximum of 50% of the spreading gain when the delays are bounded by a single chip interval. The complexity is similar to the conventional correlating receiver which is far less complex than the joint detection schemes proposed to date     

Multiuser detection in asynchronous CDMA frequency-selective fading channels

Multipath fading severely limits the performances of conventional code division multiple-access (CDMA) systems. Since every signal passes through an independent frequency-selective fading channel, even modest cross-correlations among signature sequences may induce severe near-far effects in a central multiuser receiver. This paper presents a systematic approach to the detection problem in CDMA frequency-selective fading channels and proposes a low complexity linear multiuser receiver, which eliminates fading induced near-far problem.We initially analyze an optimal multiuser detector, consisting of a bank of RAKE filters followed by a dynamic programming algorithm and evaluate its performance through error probability bounds. The concepts of error sequence decomposition and asymptotic multiuser efficiency, used to characterize the optimal receiver performance, are extended to multipath fading channels.The complexity of the optimal detector motivates the work on a near-far resistant, low complexity decorrelating multiuser detector, which exploits multipath diversity by using a multipath decorrelating filter followed by maximal-ratio combining. Analytic expressions for error probability and asymptotic multiuser efficiency of the suboptimal receiver are derived that include the effects of multipath fading, multiple-access interference and signature sequences correlation on the receiver's performance.The results indicate that multiuser detectors not only alleviate the near-far problem but approach single-user RAKE performance, while preserving the multipath diversity gain. In interference-limited scenarios multiuser receivers significantly outperform the RAKE receiver.This paper was presented in part at the Twenty-Sixth Annual Conference on Information Sciences and Systems, Princeton, NJ, March 1992 and MILCOM'92, San Diego, CA, October 1992. This work was performed while author was with the Department of Electrical and Computer Engineering, Northeastern University, Boston, USA.     

A differentially coherent receiver for minimum shift keying signal

The author extends to the case of minimum-shift-keying (MSK) modulation the differentially coherent reception theory established for phase-shift-keying modulation. A novel differentially coherent detector for MSK is thus derived. The receiver filter is equivalent to the cascade of a matched filter and an equalizer in order to suppress inherent intersymbol interference. It is shown that performance can be improved when the delay between signals, multiplied by the differential detector, is increased from one to M bit time intervals. This decreases the effect of noise correlation and, thus, the bit error probability. The bit error probability of the proposed receiver is calculated. It is found that almost all potential improvement due to the delay M is obtained with M=3     

The axisymmetric modes in a longitudinal inhomogeneous SELFOC fiber

The authors consider the propagation characteristics and mode conversion of axisymmetric modes in an imperfect SELFOC fiber with longitudinal gradually varying dielectric constant K=ϵ/ϵ₀=K₀-K ₂(z)r². An analytic solution which is expressed in terms of generalized Laguerre polynomials is found