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     

The smallest list for the arbitrarily varying channel

The capacity of the discrete memoryless arbitrarily varying channel (AVC) is investigated for deterministic list codes with fixed list size L. For every AVC with positive random code capacity C_r , a nonnegative integer M called the symmetrizability is defined. For the average probability of error criterion, it is shown that the list capacity is given by C(L)=C_r for L>M and C(L)=0 otherwise. Bounds are given which relate C_r and M. Also, explicit formulas for C(L) are given for a family of noiseless, additive AVCs     

Linear codes for sources and source networks: Error exponents, universal coding

For Slepian-Wolf source networks, the error exponents obtained by Körner,Marton, and the author are shown to be universally attainable by linear codes also. Improved exponents are derived for linear codes with "large rates." Specializing the results to simple discrete memoryless sources reveals their relationship to the random coding and expurgated bounds for channels with additive noise. One corollary is that there are universal linear codes for this class of channels which attain the random coding error exponent for each channel in the class. The combinatorial approach of Csiszár-Körner-Marton is used. In particular, all results are derived from a lemma specifying good encoders in terms of purely combinatorial properties.     

Two proofs of Pinsker's conjecture concerning arbitrarily varyingchannels

M.S. Pinsker (1990) conjectured the following theorem: for an arbitrary varying channel (AVC), every rate below the random code capacity is achievable with deterministic list codes of constant list size, if the average error criterion is used. Two proofs of this theorem are given     

Good codes can be produced by a few permutations

Our main result is that good codes, even those meeting the random coding bound, can be produced with relatively few (linear in the block length) permutations from a single codeword. This cutdown in complexity may be of practical importance. The motivation for looking at such codes came from Ahlswede's covering lemma, which makes it possible to build correlated source codes from channel codes via permutations. In Appendix I we show that the problem of finding the best error exponents for coding sources with full side information at the decoder, which has received attention in the recent literature, can easily be reduced to the familiar one for the discrete memoryless channel (DMC). Finally, in Appendices II and III we give rather precise double exponentially small bounds on the probabilities that a randomly chosen code will fail to meet the random coding or expurgated bound for the DMC. According to these results, good codes are hard to miss if selected at random. This also explains why good codes of a Iow complexity (such as those produced by     

An iterative code construction for the broadcast channel with degraded message sets (Corresp.)

Ahlswede and Dueck introduced an iterative method for constructing codes for the discrete memoryless channel that meet the random coding bound. Their codes are constructed by making a relatively few permutations of a single codeword. In this correspondence their idea is extended to the broadcast channel with degraded message sets. The codes constructed here have average error probabilities below the error bounds derived by Körner and Sgarro.     

Performance Bounds for Unequal Error Protecting Turbo Codes

In many communications systems, data can be divided into different importance levels. For these systems, unequal error protection (UEP) techniques are used to guarantee lower BER for the more important classes. In particular, if the precise characteristics of the channel are not known, UEP can be used to recover the more important classes even in poor receiving conditions. In this paper, we derive bounds on the performance of unequal error protecting turbo codes. These bounds serve as an important tool in predicting the performance of these codes. In order to derive the bounds, we introduce the notion of UEPuniform interleaver which is a random interleaver that does not change the order of classes in the turbo code frame. We also present a method to derive the weight enumerating function for UEP turbo codes.     

Error Probability of Asynchronous Spread Spectrum Multiple Access Communication Systems

Several approaches for the evaluation of upper and lower bounds on error probability of asynchronous spread spectrum multiple access communication systems are presented. These bounds are obtained by utilizing an isomorphism theorem in the theory of moment spaces. From this theorem, we generate closed, compact, and convex bodies, where one of the coordinates represents error probability, while the other coordinate represents a generalized moment of the multiple access interference random variable. Derivations for the second moment, fourth moment, single exponential moment, and multiple exponential moment are given in terms of the partial cross correlations of the codes used in the system. Error bounds based on the use of these moments are obtained. By using a sufficient number of terms in the multiple exponential moment, upper and lower error bounds can be made arbitrarily tight. In that case, the error probability equals the multiple exponential moment of the multiple access interference random variable. An example using partial cross correlations based on codes generated from Gold's method is presented.     

Bounds on the maximum-likelihood decoding error probability oflow-density parity-check codes

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent     

Error Exponents for Recursive Decoding of Reed–Muller Codes on a Binary-Symmetric Channel

Error exponents are studied for recursive decoding of Reed-Muller (RM) codes and their subcodes used on a binary-symmetric channel. The decoding process is first decomposed into similar steps, with one new information bit derived in each step. Multiple recursive additions and multiplications of the randomly corrupted channel outputs plusmn1 are performed using a specific order of these two operations in each step. Recalculated random outputs are compared in terms of their exponential moments. As a result, tight analytical bounds are obtained for decoding error probability of the two recursive algorithms considered in the paper. For both algorithms, the derived error exponents almost coincide with simulation results. Comparison of these bounds with similar bounds for bounded distance decoding and majority decoding shows that recursive decoding can reduce the output error probability of the latter two algorithms by five or more orders of magnitude even on the short block length of 256. It is also proven that the error probability of recursive decoding can be exponentially reduced by eliminating one or a few information bits from the original RM code     

An error correcting scheme for defective memory

A scheme for storing information in a memory system with defective memory ceils using "additive" codes was proposed by Kuznetsov and Tsybakov. When a source message is to be stored in a memory with defective cells, a code vectorxmasking the defect pattern of the memory is formed by adding a vector defined by the message and the defect pattern to the encoded message, and thenxis stored. The decoding process does not require the defect information. Considerably better bounds on the information rate of codes of this type which are capable of masking multiple defects and correcting multiple temporary errors are presented. The difference between the upper and lower bounds approaches the difference between the known best upper and lower bounds for random error correcting linear codes as the word length becomes large. Examples of efficient codes for masking double or fewer defects and correcting multiple temporary errors are presented.     

Estimation of the error performance objectives for satellite communication systems

We consider the physical layer error performance parameters and design criteria for digital satellite systems established by ITU‐R Recommendation S.1062, where the performance objectives are given in terms of the bit error rate (BER) divided by the average number of errors within a cluster. It is well known that errors on satellite links employing forward error correction (FEC) schemes tend to occur in clusters. The resulting block error rate is the same as if it was caused by randomly occurring bit errors with an error‐event ratio of BER/α, where α is the average number of errors within a cluster. The factor, α, accounts for the burstiness of the errors and also represents the ratio between the BER and the error‐event ratio. This paper proposes theoretical methods to estimate the factor, α. Using the weight distributions of the FEC codes, we derive a set of expressions for the factor, α, as well as their compact lower bounds. We present lower bounds for various FEC schemes including binary BCH codes, block turbo codes, convolutional codes, and turbo codes. The simulation results show that the proposed lower bounds are good estimates in the high signal‐to‐noise ratio region. Copyright © 2008 John Wiley & Sons, Ltd.     

General random coding bounds: AWGN channels to MIMO fading channels

Random coding bounds are obtained for multiple-input multiple-output (MIMO) fading channels. To derive the result in a compact and easy-to-evaluate form, a series of combinatorial codeword enumeration problems are solved for input-constrained MIMO fading channels. The bounds obtained in this paper are shown useful as performance prediction measures for MIMO systems which employ turbo-like block codes as the outer code to derive the space-time inner code. The error exponents for MIMO channels are also derived from the bounds, and then compared with the classical Gallager error exponents as well as the channel capacities. The random coding bounds associated with the maximum likelihood receiver exhibit good match with the extensive system simulation results obtained with a turbo-iterative receiver.     

Bounds on the error probability ofml decoding for block and turbo-block codes

The performance of either structured or random turbo-block codes and binary, systematic block codes operating over the additive white Gaussian noise (Awgn) channel, is assessed by upper bounds on the error probalities of maximum likelihood (Ml) decoding. These bounds on the block and bit error probability which depend respectively on the distance spectrum and the input-output weight enumeration function (Iowef) of these codes, are compared, for a variety of cases, to simulated performance of iterative decoding and also to some reported simulated lower bounds on the performance ofMl decoders. The comparisons facilitate to assess the efficiency of iterative decoding (as compared to the optimalMl decoding rule) on one hand and the tightness of the examined upper bounds on the other. We focus here on uniformly interleaved and parallel concatenated turbo-Hamming codes, and to that end theIowefs of Hamming and turbo-Hamming codes are calculated by an efficient algorithm. The usefulness of the bounds is demonstrated for uniformly interleaved turbo-Hamming codes at rates exceeding the cut-off rate, where the results are compared to the simulated performance of iteratively decoded turbo-Hamming codes with structured and statistical interleavers. We consider also the ensemble performance of ‘repeat and accumulate’ (Ka) codes, a family of serially concatenated turbo-block codes, introduced by Divsalar, Jin and McEliece. Although, the outer and inner codes possess a very simple structure: a repetitive and a differential encoder respectively, our upper bounds indicate impressive performance at rates considerably beyond the cut-off rate. This is also evidenced in literature by computer simulations of the performance of iteratively decodedRa codes with a particular structured interleaver.     

On Randomized Linear Network Codes and Their Error Correction Capabilities

Randomized linear network code for single source multicast was introduced and analyzed in Ho et al. (IEEE Transactions on Information Theory, October 2006) where the main results are upper bounds for the failure probability of the code. In this paper, these bounds are improved and tightness of the new bounds is studied by analyzing the limiting behavior of the failure probability as the field size goes to infinity. In the linear random coding setting for single source multicast, the minimum distance of the code defined in Zhang, (IEEE Transactions on Information Theory, January 2008) is a random variable taking nonnegative integer values that satisfy the inequality in the Singleton bound recently established in Yeung and Cai (Communications in Information and Systems, 2006) for network error correction codes. We derive a bound on the probability mass function of the minimum distance of the random linear network code based on our improved upper bounds for the failure probability. Codes having the highest possible minimum distance in the Singleton bound are called maximum distance separable (MDS). The bound on the field size required for the existence of MDS codes reported in Zhang, (IEEE Transactions on Information Theory, January 2008) and Matsumoto (arXiv:cs.IT/0610121, Oct. 2006) suggests that such codes exist only when field size is large. Define the degradation of a code as the difference between the highest possible minimum distance in the Singleton bound and the actual minimum distance of the code. The bound for the probability mass function of the minimum distance leads to a bound on the field size required for the existence of network error correction codes with a given maximum degradation. The result shows that allowing minor degradation reduces the field size required dramatically.     

Capacity and decoding rules for classes of arbitrarily varyingchannels

The capacity of an arbitrarily varying channel (AVC) is considered for deterministic codes with the average probability of error criterion and, typically, subject to at state constraint. First, sufficient conditions are provided that enable relatively simple decoding rules such as typicality, maximum mutual information, and minimum distance, to attain capacity. Then the (possibly noisy) OR channels and group adder channels are studied in detail. For the former the capacity is explicitly determined and shown to be attainable by minimum-distance decoding. Next, for a large class of addictive AVCs, in addition to providing an intuitively suggestive simplification of the general AVC capacity formula, it is proven that capacity can be attained by a universal decoding rule. Finally, the effect of random state selections on capacity is studied. The merits and limitations of a previous mutual information game approach are also discussed     

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.     

Performance analysis of linear multiuser detectors for randomlyspread CDMA using Gaussian approximation

The performance of a linear decorrelating detector (LDD) and a minimum mean square error (MMSE) detector is analyzed for random spreading waveforms. The performance of the LDD and MMSE detectors is expressed in terms of the so-called near-far resistance, defined by a reciprocal of a diagonal component of inverse matrix. For random code division multiple access, which employs random spreading waveforms, the near-far resistance can be regarded as a random variable. Many papers have dealt with the analysis of multiuser detectors for random spreading sequences. In most cases, however, these analyses derived only the expectations or bounds for the near-far resistance. In this paper, we directly derive the approximate probability density function (PDF) of the near-far resistance and corresponding bit error rate expression for random spreading sequences. It is based on Gaussian approximation of the cross correlation between any two randomly generated spreading codes. The resulting PDF turned out to be a reversed-and-scaled version of chi-square distribution. The approximate expressions, both the PDF and the corresponding bit error rate expression, were verified via Monte Carlo simulations. The results showed that the approximation is quite close to the simulation results when the number of users is less than half the processing gain     

Performance bounds for trellis-coded modulation on time-dispersivechannels

The performance of trellis-coded modulation (TCM) on additive white Gaussian noise channels is well understood, and tight analytical bounds exist on the probability of the Viterbi decoder making a decision error. When a channel is also time-dispersive, the performance of TCM systems has been studied mainly by simulation. However, simulation is limited to symbol error probabilities greater than 10^-6 and is not a particularly useful tool for designing codes. Tight analytical bounds on the error probability of TCM on time-dispersive channels are required for a more thorough study of performance. Moreover, the design of good codes and optimum metrics for time-dispersive channels requires tight analytical bounds. In this paper we derive analytical upper bounds, which, although requiring numerical techniques for tractable evaluation, are tight for a wide range of time-dispersive channel conditions. The bounds are based on a union bound of error events that leads to a summation of pairwise error probabilities, which are themselves upper bounded     

关于线性分组码的不可检错误概率

本文给出了检错好码的定义,证明了GF(2)上的(n,k)线性分组码为检错好码的充要条件是其对偶码也为检错好码。文中还得到了关于检错好码的一系列新的结果。对二元(n,k)线性分组码,我们给出了不可检错误概率新的下限。这些限只与n和k有关,而与码的重量结构无关。