Error exponents for the two-user Poisson multiple-access channel

The error exponent of the two-user Poisson multiple-access channel under peak and average power constraints, but unlimited in bandwidth, is considered. First, a random coding lower bound on the error exponent is obtained, and an extension of Wyner's (1988) single-user codes is shown to be exponentially optimum for this case as well. Second, the sphere-packing bounding technique suggested by Burnashev and Kutoyants (see Probl. Inform. Transm., vol.35, no.2, p.3-22, 1999) is generalized to the case at hand and an upper bound on the error exponent, which coincides with the lower bound, is derived. Thus, this channel joins its single-user partner as one of very few for which the reliability function is known     

Error probability for block codes over channels with blockinterference

A methodology is presented to evaluate analytically the error probability for block codes over block interference channels. The proposed analysis is based on the knowledge of the moments of the bit-error probability over the interference, thus allowing, for instance, fast performance evaluation of block-coded slow frequency hopping (SFH) systems with antenna diversity over fading channels. As an example of application, slow frequency hopping multiple access (SFHMA) systems with nonideal interleaving are analyzed in the presence of fading, cochannel interference, and additive Gaussian noise     

Error probability bounds for M-PSK and M-DPSK and selective fadingdiversity channels

A method is described for obtaining tight closed-form bounds on the probability of error for M-ary phase-shift keying (M-PSK) and M-ary differential phase-shift keying (M-DPSK) on fading diversity channels. The channels exhibit doubly selective fading and have specular components. In addition, the random impulse responses of the diversity channels may be correlated; and the probability distributions for the fading on different diversity channels need not be the same. Error probability expressions are given for binary DPSK, 8-DPSK, and 16-DPSK modulation as examples of the application of the general method described     

Algebraic lower bounds on the free distance of convolutional codes

A new module structure for convolutional codes is introduced and used to establish further links with quasi-cyclic and cyclic codes. The set of finite weight codewords of an (n,k) convolutional code over F_q is shown to be isomorphic to an F_q[x]-submodule of F_q ⁿ[x], where F_q ⁿ[x] is the ring of polynomials in indeterminate x over F_q ⁿ, an extension field of F_q. Such a module can then be associated with a quasi-cyclic code of index n and block length nL viewed as an F_q[x]-submodule of F_q ⁿ[x]/langx^L-1rang, for any positive integer L. Using this new module approach algebraic lower bounds on the free distance of a convolutional code are derived which can be read directly from the choice of polynomial generators. Links between convolutional codes and cyclic codes over the field extension F_q ⁿ are also developed and Bose-Chaudhuri-Hocquenghem (BCH)-type results are easily established in this setting. Techniques to find the optimal choice of the parameter L are outlined     

Sphere-packing upper bounds on the free distance of trellis codes

Sphere-packing arguments are used to develop upper bounds on the free distance of trellis codes. A general bounding procedure is presented. Sphere packing bounds, including bounds on the density of infinite regions, packings for hypercubes, and packings on the surface of a unit sphere, are then used to produce bounds for a wide variety of trellis codes. Among the applications are convolutional codes, Ungerboeck codes for phase-shift keying and quadrature amplitude modulation, coset codes, and continuous phase modulation codes. The new bounds are significantly tighter than existing bounds in many cases of practical interest     

Upper bounds on the free distance for trellis codes combined withCPFSK signals

It is well-known that CPM schemes themselves exhibit attractive spectral efficiencies and that combining them with a rate m/(m+1) external trellis encoder with 2^m-1-level modulation results in better power-bandwidth performance. Since the free distance is a good measure of performance, the authors construct upper bounds on the ultimately achievable free distance for trellis codes of Ungerboeck type combined with constant-envelope CPFSK signals. Some encoders achieving the constructed upper bounds are also presented     

Free distance bounds for convolutional codes

The best asymptotic bounds presently known on free distance for convolutional codes are presented from a unified point of view. Upper and lower bounds for both time-varying and fixed codes are obtained. A comparison is made between bounds for nonsystematic and systematic codes which shows that more free distance is available with nonsystematic codes. This result is important when selecting codes for use with sequential or maximum-likelihood (Viterbi) decoding since the probability of decoding error is closely related to the free distance of the code. An ancillary result, used in proving the lower bound on free distance for time-varying nonsystematic codes, furnishes a generalization of two earlier bounds on the definite decoding minimum distance of convolutional codes.     

Minimum probability of error for asynchronous Gaussian multiple-access channels

Consider a Gaussian multiple-access channel shared byKusers who transmit asynchronously independent data streams by modulating a set of assigned signal waveforms. The uncoded probability of error achievable by optimum multiuser detectors is investigated. It is shown that theK-user maximum-likelihood sequence detector consists of a bank of single-user matched filters followed by a Viterbi algorithm whose complexity per binary decision isO(2^{K}). The upper bound analysis of this detector follows an approach based on the decomposition of error sequences. The issues of convergence and tightness of the bounds are examined, and it is shown that the minimum multiuser error probability is equivalent in the Iow-noise region to that of a single-user system with reduced power. These results show that the proposed multiuser detectors afford important performance gains over conventional single-user systems, in which the signal constellation carries the entire burden of complexity required to achieve a given performance level.     

Comments on `Evaluating distance spectra and performance bounds oftrellis codes on channels with intersymbol interference'

It is shown that the method presented by C. Schlegel (see ibid., vol.37, no.3, p.627-34, May 1991) for evaluating the distance spectra of trellis codes on channels with intersymbol interference is incorrect. A counterexample is presented along with comments on the feasibility of correcting the method     

Seminoisy deterministic multiple-access channels: coding theorems for list codes and codes with feedback

Whereas the average error capacity region R/sub a/ for the multiple-access channel (MAC) W: X /spl times/ Y /spl rarr/ Z has been known for a long time, very little is known about the capacity region R/sub m/ for the maximal error concept (as predicted by Ahlswede in 1971). In spite of great efforts during the past three decades even for some special examples of deterministic MAC, for which the maximal error concept coincides with the concept of unique decodability, the progress has been slow. It is known that the permission of list codes can be of great help, even if list sizes are of negligible rates (cf. the arbitrarily varying channel (AVC) and, especially, Shannon's (1948) zero-error capacity problem for the one-way channels). Therefore, it is theoretically appealing to look at their regions R/sub m,l/ for the MAC. For a nice class of deterministic MAC, which we call "seminoisy," we completely characterized R/sub m,l/. For these channels, the Y-input is determined uniquely by the output. Dueck's (1978) example with R/sub a/ /spl ne/ R/sub m/ and Vanroose's (1988) "noiseless binary switching MAC" with R/sub a/ = R/sub m/ fall into this class. Finally, for this class, the capacity region R/sub m,f/, which concerns complete feedback, equals R/sub m,l/.     

On performance bounds for space-time codes on fading channels

We evaluate truncated union bounds on the frame-error rate (FER) performance of space-time (ST) codes operating over the quasi-static fading channel and compare them with computer simulation results. We consider both ST trellis and block codes. We make the following contributions. For the case of ST trellis codes, we develop a general method, which we denote as measure spectrum analysis, that characterizes ST codeword differences and accommodates the combined influences of the ST code and channel scenario. We propose a numerical bounding method that converges in the measure spectrum to within a very small fraction of a decibel to the simulated FER over the full range of signal-to-noise ratio. In addition, we demonstrate the existence of dominant quasi-static fading error events and detail a method for predicting them. Using only this set of dominant measure spectrum elements, very rapid and tight numerical estimation of FER performance is attained.     

Minimum distance bounds for cyclic codes and Deligne's theorem

At the present time, there are very good methods to obtain bounds for the minimum distance of BCH codes and their duals. On the other hand, there are few other bounds suitable for general cyclic codes. Therefore, research Problem 9.9 of MacWilliams and Sloane (1977), The Theory of Error-Correcting Codes, asks if the bound of Deligne (1974) for exponential sums in several variables or the bound of Lang and Weil (1954), can be used to obtain bounds on the minimum distance of codes. This question is answered in the affirmative by showing how Deligne's theorem can be made to yield a lower bound on the minimum distance of certain classes of cyclic codes. In the process, an infinite family of binary cyclic codes is presented for which the bound on minimum distance so derived is as tight as possible. In addition, an infinite family of polynomials of degree 3 in 2 variables over a field of characteristic 2, for which Deligne's bound is tight, is exhibited. Finally, a bound is presented for the minimum distance of the duals of the binary subfield subcodes of generalized Reed-Muller codes as well as for the corresponding cyclic codes. It is noted that these codes contain examples of the best binary cyclic codes     

Some very simple codes for the nonsynchronized two-user multiple-access adder channel with binary inputs (Corresp.)

Some very simple codes are given for the two-user multiple-access adder channel with binary inputs that do not require word or bit synchronism between the encoders nor between the decoder and the encoders.     

On symbol error probability bounds for ISI-like channels

Some issues with Forney's upper and lower bounds (1972) for the symbol error probability in systems with memory (e.g., intersymbol interference channels) have been pointed out in the literature. We expound on these issues. For the upper bound, we show that, although the most commonly cited proofs are not logically consistent, the bound is true for more general conditions. The reasoning leading to the lower bound is shown to be flawed and, in general,to lead to invalid lower bounds. We suggest a lower bound based on Mazo's bound (1975) as an alternative     

New minimum distance bounds for certain binary linear codes

Let an [n, k, d]-code denote a binary linear code of length n, dimension k, and minimum distance at least d. Define d(n, k) as the maximum value of d for which there exists a binary linear [n, k, d]-code. T. Verhoeff (1989) has provided an updated table of bounds on d(n, k) for 1⩽k⩽n⩽127. The authors improve on some of the upper bounds given in that table by proving the nonexistence of codes with certain parameters     

Generalization of Tanner's minimum distance bounds for LDPC codes

Tanner derived minimum distance bounds of regular codes in terms of the eigenvalues of the adjacency matrix by using some graphical analysis on the associated graph of the code. In this letter, we generalize Tanner's results by deriving a bit-oriented bound and a parity-oriented bound on the minimum distances of both regular and block-wise irregular LDPC codes.     

Linear programming bounds for tree codes (Corresp.)

Two asymptotic upper bounds on the information rate of a tree code as a function of its feedback decoding minimum distance are presented. These bounds are generalizations of the linear programming bounds for binary block codes proved by McEliece et al., and they are derived from linear programming problems based on Delsarte's theory of association schemes.     

Error probability calculation for multibeam Rayleigh channels

The error probability of wide-band signals on multibeam Rayleigh fading channels is calculated in closed form using similarity transformations of Gaussian quadratic forms. It is shown how this approach can be used to calculate the error probability on arbitrary complex Gaussian channels, even when the beams are correlated. As an application example the author considers a wide-band spread-spectrum system using code-division multiple access (CDMA)     

Effective minimum free distance for convolutional codes

The minimum free distance (MFD) of convolutional error-correcting codes is a powerful and well-known parameter for indicating the behaviour of the communication system via an AWGN channel with medium and high SNR. But in many cases it happens that the MFD theory fails. The letter provides some examples where codes with a high MFD are being defeated by codes with lower MFD. Then a new method called the effective minimum free distance is introduced to achieve greater simplicity and to strengthen the MFD theory. Software simulation for some codes with constraint lengths 3 and 4 demonstrate this idea. The Viterbi decoding algorithm is used for the simulation program. The truncated generator function of a code is modified into a new, effective terms form that presents a very practical measure on the error correctability of the code.     

Very low rate convolution codes for maximum theoretical performanceof spread-spectrum multiple-access channels

A spread-spectrum multiple-access (SSMA) communication system is treated for which both spreading and error control is provided by binary PSK modulation with orthogonal convolution codes. Performance of spread-spectrum multiple access by a large number of users employing this type of coded modulation is determined in the presence of background Gaussian noise. With this approach and coordinated processing at a common receiver, it is shown that the aggregate data rate of all simultaneous users can approach the Shannon capacity of the Gaussian noise channel