A direct geometrical method for bounding the error exponent for anyspecific family of channel codes. I. Cutoff rate lower bound for blockcodes

A direct, general, and conceptually simple geometrical method for determining lower and upper bounds on the error exponent of any specific family of channel block codes is presented. It is considered that a specific family of codes is characterized by a unique distance distribution exponent. The tight linear lower bound of slope -1 on the code family error exponent represents the code family cutoff rate bound. It is always a minimum of a sum of three functions. The intrinsic asymptotic properties of channel block codes are revealed by analyzing these functions and their relationships. It is shown that the random coding technique for lower-bounding the channel error exponent is a special case of this general method. The requirements that a code family should meet in order to have a positive error exponent and at best attain the channel error exponent are stated in a clear way using the (direct) distance distribution method presented     

Error probability and free distance bounds for two-user tree codes on multiple-access channels

Two-user tree codes are considered for use on an arbitrary two-user discrete memoryless multiple-access channel (MAC). A two-user tree Is employed to achieve true maximum likelihood (ML) decoding of two-user tree codes on MAC's. Each decoding error event has associated with it a configuration indicating the specific time slots in which a decoding error has occurred for the first user alone, for the second user alone, or for both users simultaneously. Even though there are many possible configurations, it is shown that there are five fundamental configuration types. An upper bound on decoding error probability, similar to Liao's result for two-user block codes, is derived for sets of error events having a particular configuration. The total ML decoding error probability is bounded using a union bound first over all configurations of a given type and then over the five configuration types. A two-user tree coding error exponent is defined and compared with the corresponding block coding result for a specific MAC. It is seen that the tree coding error exponent is larger than the block coding error exponent at all rate pairs within the two-user capacity region. Finally, a new lower bound on free distance for two-user codes is derived using the same general technique used to bound the error probability.     

Error probability for repeat request systems with convolutionalcodes

A new decoding algorithm based on the modified Viterbi algorithm for repeat request systems is considered. A new asymptotic error probability bound is derived. It is shown that the error exponent for convolutional coding can be related to the exponent for block coding by a graphical method known as inverse concatenation construction     

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     

A new universal random coding bound for the multiple-access channel

The minimum average error probability achievable by block codes on the two-user multiple-access channel is investigated. A new exponential upper bound is found which can be achieved universally for all discrete memoryless multiple-access channels with given input and output alphabets. It is shown that the exponent of this bound is greater than or equal to those of previously known bounds. Moreover, examples are given where the new exponent is strictly larger     

Upper bounds on sequential decoding performance parameters

This paper presents the best obtainable random coding and expurgated upper bounds on the probabilities of undetectable error, oft-order failure (advance to depthtinto an incorrect subset), and of likelihood rise in the incorrect subset, applicable to sequential decoding when the metric biasGis arbitrary. Upper bounds on the Pareto exponent are also presented. TheG-values optimizing each of the parameters of interest are determined, and are shown to lie in intervals that in general have nonzero widths. TheG-optimal expurgated bound on undetectable error is shown to agree with that for maximum likelihood decoding of convolutional codes, and that on failure agrees with the block code expurgated bound. Included are curves evaluating the bounds for interesting choices ofGand SNR for a binary-input quantized-output Gaussian additive noise channel.     

The random coding bound is tight for the average code (Corresp.)

The random coding bound of information theory provides a well-known upper bound to the probability of decoding error for the best code of a given rate and block length. The bound is constructed by upper-bounding the average error probability over an ensemble of codes. The bound is known to give the correct exponential dependence of error probability on block length for transmission rates above the critical rate, but it gives an incorrect exponential dependence at rates below a second lower critical rate. Here we derive an asymptotic expression for the average error probability over the ensemble of codes used in the random coding bound. The result shows that the weakness of the random coding bound at rates below the second critical rate is due not to upperbounding the ensemble average, but rather to the fact that the best codes are much better than the average at low rates.     

Coding theorems for the nonsynchronized channel

Capacity and error bounds are derived for a memoryless binary symmetric channel with the receiver having no a priori information as to the starting time of the code words. The channel capacity is the same as the capacity of the synchronized channel. For all rates below capacity, the minimum probability of error for the nonsynchronized channel decreases exponentially with the code-block length. For rates near channel capacity, the exponent in the upper bound on the probability of error for the nonsynchronized channel is the same as the corresponding exponent for the synchronized channel. For low rates, the largest exponent obtained for the nonsynchronized channel with conventional block coding is inferior to the exponent obtained for the synchronized channel. Stronger results are obtained for a new form of coding that allows for a Markov dependency between successive code words. Bounds on the minimum probability of error are obtained for unconstrained binary codes and for several classes of parity-check codes and are used to obtain asymptotic distance properties for various classes of binary codes. At certain rates there exist codes whose minimum distance, in the comma-free sense, is not only greater than one, but is proportional to the block length.     

Bounds on the decoding error probability of binary linear codes viatheir spectra

Bounds on the error probability of maximum likelihood decoding of a binary linear code are considered. The bounds derived use the weight spectrum of the code and they are tighter than the conventional union bound in the case of large noise in the channel. The bounds derived are applied to a code with an average spectrum, and the result is compared to the random coding exponent. The author shows that the bound considered for the binary symmetrical channel case coincides asymptotically with the random coding bound. For the case of AWGN channel the author shows that Berlekamp's (1980) tangential bound can be improved, but even this improved bound does not coincide with the random coding bound, although it can be very close to it     

On the reliability function of the ideal Poisson channel withnoiseless feedback

A coding scheme for the channel under peak power and average power constraints on the input is presented, and its asymptotic error exponent is shown to coincide, at all rates below capacity, with the sphere packing error exponent, which, for the case at hand, is known to be unachievable without feedback for rates below the critical rate. An upper bound on the error exponent achievable with feedback is also derived and shown, under a capacity reducing average power constraint, to coincide with the error exponent achieved by the proposed coding scheme; in such a case the coding scheme is asymptotically optimal. Thus, the ideal Poisson channel, limited by a capacity-reducing average power constraint, provides a nontrivial example of a channel for which the reliability function is known exactly both with and without feedback. It is shown that a slight modification of the coding scheme to one of random transmission time can achieve zero-error probability for any rate lower than the ordinary average-error channel capacity     

A low-rate bound on the reliability of a quantum discrete memoryless channel

We extend a low-rate improvement of the random coding bound on the reliability of a classical discrete memoryless channel (DMC) to its quantum counterpart. The key observation that we make is that the problem of bounding below the error exponent for a quantum channel relying on the class of stabilizer codes is equivalent to the problem of deriving error exponents for a certain symmetric classical channel.     

Improved error exponent for time-invariant and periodicallytime-variant convolutional codes

An improved upper bound on the error probability (first error event) of time-invariant convolutional codes, and the resulting error exponent, is derived. The improved error bound depends on both the delay of the code K and its width (the number of symbols that enter the delay line in parallel) b. Determining the error exponent of time-invariant convolutional codes is an open problem. While the previously known bounds on the error probability of time-invariant codes led to the block-coding exponent, we obtain a better error exponent (strictly better for b>1). In the limit b→∞ our error exponent equals the Yudkin-Viterbi (1967, 1971, 1965) exponent derived for time-variant convolutional codes. These results are also used to derive an improved error exponent for periodically time-variant codes     

Distance distribution of binary codes and the error probability of decoding

We address the problem of bounding below the probability of error under maximum-likelihood decoding of a binary code with a known distance distribution used on a binary-symmetric channel (BSC). An improved upper bound is given for the maximum attainable exponent of this probability (the reliability function of the channel). In particular, we prove that the "random coding exponent" is the true value of the channel reliability for codes rate R in some interval immediately below the critical rate of the channel. An analogous result is obtained for the Gaussian channel.     

Guessing subject to distortion

We investigate the problem of guessing a random vector X within distortion level D. Our aim is to characterize the best attainable performance in the sense of minimizing, in some probabilistic sense, the number of required guesses G(X) until the error falls below D. The underlying motivation is that G(X) is the number of candidate codewords to be examined by a rate-distortion block encoder until a satisfactory codeword is found. In particular, for memoryless sources, we provide a single-letter characterization of the least achievable exponential growth rate of the ρth moment of G(X) as the dimension of the random vector X grows without bound. In this context, we propose an asymptotically optimal guessing scheme that is universal both with respect to the information source and the value of ρ. We then study some properties of the exponent function E(D, ρ) along with its relation to the source-coding exponents. Finally, we provide extensions of our main results to the Gaussian case, guessing with side information, and sources with memory     

Universally optimum block codes and convolutional codes with maximum likelihood decoding

A new proof is presented for the existence of block codes whose error probability under maximum likelihood decoding is bounded asymptotically by the random coding bound universally over all discrete memoryless channels. On the basis of this result, the existence of convolutional codes with universally optimum performance is shown. Furthermore the existence of block codes which attain the expurgated bound universally over all discrete memoryless channels is proved under the use of maximum likelihood decoding.     

A comparison of known codes, random codes, and the best codes

This paper calculates new bounds on the size of the performance gap between random codes and the best possible codes. The first result shows that, for large block sizes, the ratio of the error probability of a random code to the sphere-packing lower bound on the error probability of every code on the binary symmetric channel (BSC) is small for a wide range of useful crossover probabilities. Thus even far from capacity, random codes have nearly the same error performance as the best possible long codes. The paper also demonstrates that a small reduction k-k˜ in the number of information bits conveyed by a codeword will make the error performance of an (n,k˜) random code better than the sphere-packing lower bound for an (n,k) code as long as the channel crossover probability is somewhat greater than a critical probability. For example, the sphere-packing lower bound for a long (n,k), rate 1/2, code will exceed the error probability of an (n,k˜) random code if k-k˜>10 and the crossover probability is between 0.035 and 0.11=H^-1(1/2). Analogous results are presented for the binary erasure channel (BEC) and the additive white Gaussian noise (AWGN) channel. The paper also presents substantial numerical evaluation of the performance of random codes and existing standard lower bounds for the BEC, BSC, and the AWGN channel. These last results provide a useful standard against which to measure many popular codes including turbo codes, e.g., there exist turbo codes that perform within 0.6 dB of the bounds over a wide range of block lengths     

Capacity and error exponent for the direct detection photonchannel. II

For pt.I see ibid., vol.34, no.6, p.1449-61 (1980). The discussion of the capacity and error exponent of the direct detection optical channel is continued. The channel input in a T-second interval is a waveform satisfying certain peak and average power constraints for the optical signals. The channel output is a Poisson process with an intensity parameter that accounts for the dark-current component. An upper bound is obtained on the error exponent which coincides with the lower bound. Thus, this channel is one for which the error exponent can be known exactly     

衰落信道上TAS/MRC的错误指数

使用梅哲-G 函数,推导了Nakagami-m 衰落发射天线选择（TAS）/最大比合并（MRC）系统的随机编码错误指数（RCEE）、遍历容量、截止速率、删改指数的精确表达式。计算结果表明,Nakagami-m衰落TAS/MRC系统的错误指数与信道衰落参数、信道编码速率、收发天线数目、信道相干时间等因素有关。信道衰落系数越大、编码速率越大、收发天线数目越多,通信系统的RCEE越大,相应的译码错误概率越小,系统的通信可靠性越高。对于给定译码错误概率的MIMO无线通信系统,可以通过计算系统的RCEE来估计信道所需的编码长度、收发天线数目、信道相干时间和空间衰落相关时的编码需求。     

A hierarchy of codes for memoryless channels (Corresp.)

Channel block codes are shown to have a fine hierarchical structure with respect to the expurgated exponent. Another hierarchy with respect to the random coding exponent is also discussed.     

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.