   On exponential error bounds for random codes on the BSCG. David Forney, Jr.1 IntroductionIn this note we will revisit the development of exponential error bounds for random codes onthe binary symmetric channel (BSC).This is a very old problem, whose solution has been well known since the classic work ofShannon [S48], Elias [E55, E56], Fano [F61] and Gallager [G63, G65, G68]. However, somefeatures of this solution that were doubtless known to these early researchers do not appear instandard texts such as [G68], [B87] or [CT91], and appear to be little known today. As thedevelopment of “random-like” capacity-approaching codes has reawakened interest in this topic,our aim is to provide a clean, modern development that would not be inappropriate in a firstcourse on information theory and coding.1.1 Random code ensembles and typical codesIn this section we introduce the appropriate random code ensemble (RCE) for the BSC, and alsothe random linear code ensemble (LCE). We then discuss the properties of the typical linearcode (TRC) from the RCE, and the typical linear code (TLC) from the LCE. In particular, wenote that whereas the distance distributions of the RCE or LCE and the TLC are exponentiallyidentical for distances above the Gilbert-Varshamov (GV) distance, they are radically differentbelow the GV distance.Shannon [S48] introduced the idea of a random code ensemble in which every symbol in everycodeword is chosen independently at random according to some input distribution p(x).On the BSC, the input alphabet is binary, and by symmetry the optimum input distributionis equiprobable. A binary code of length N and rate R is a set of M = eNRbinary N-tuples.In a binary equiprobable random code ensemble of length N and rate R, the variables are theNM binary symbols {x(i)k, 1 ≤ i ≤ N } of the M = eNRcodewords {x(i), 0 ≤ i ≤ M − 1},which are independent and identically distributed (iid) random variables chosen according to anequiprobable {12,12} distribution.In this case the probability that a given random codeword x of length N will be at Hammingdistance d = Nδ from an arbitrary binary N -tuple b isPr{dH(x, b) = d} =µNd¶µ12¶dµ12¶N−d≈ e−ND(δ||12),where the exponent D(δ||12) is the Kullback-Leibler (KL) divergenceD(δ||12) = δ logδ12+ (1 − δ) log1 − δ12,logarithms are natural, and the symbol “≈” denotes exponential equality; i.e.,limN→∞−1Nlog Pr{dH(x, b) = d} = D(δ||12).1    By the general properties of divergences, the exponent D(δ||12) is strictly convex and has aminimum of 0 at δ =12. It may alternatively be written asD(δ||12) = log 2 − H(δ),where H(δ) = −δ log δ −(1 − δ) log(1 − δ) is the entropy of a binary variable with probabilities{δ, 1 − δ}.Let x be an arbitrary codeword, and letN(δ) denote the average number of the remainingM − 1 ≈ eNRcodewords x0such that dH(x0, x) = Nδ. ThenN(δ) = (M − 1) Pr{dH(x0, x) = Nδ} ≈ eN(R−D(δ||12)). (1.1)The exponent R−D(δ||12) ofN(δ) is plotted in Figure 1. It is strictly concave and symmetricalabout δ =12. It is nonnegative for δGV(R) ≤ δ ≤12, where the (relative) Gilbert-Varshamovdistance δGV(R) is defined as the δ ≤12at which the exponent is 0; i.e., as the solution ofD(δGV(R)||12) = R. (1.2)It is negative for 0 ≤ δ < δGV(R).0 δGV(R)121RtlcrceFigure 1. Exponents of average distance distribution N(δ) for random code ensemble (RCE)and of typical distance distribution Ntyp(δ) for typical linear code (TLC).If we choose a code at random from the random code ensemble, then for δGV(R) ≤ δ ≤12it ishighly likely that there will be Ntyp(δ) ≈N(δ) codewords x0at distance Nδ from an arbitrarycodeword x. On the other hand, for 0 ≤ δ < δGV(R), it is highly likely that there will be nocodewords at distance Nδ from an arbitrary codeword x; i.e., Ntyp(δ) = 0. Therefore in Figure1 we indicate that the exponent of Ntyp(δ) goes to −∞ below δGV(R). In short, it is highlylikely that in a typical random code the minimum distance between an arbitrary codeword andall other codewords will be NδGV(R). For δGV(R) ≤ δ ≤12, there will almost certainly beexponentially many codewords at distance N δ.Notice that the distribution considered here is not the usual distance distribution of a code,but rather the distance distribution from a given codeword (or from any random binary word) toall other codewords. For our development of RCE bounds, this will actually be the distributionof interest. For random linear codes, we get the same distribution, and moreover the distancedistribution from a given codeword is also the distance distribution from every codeword.For our typical code bounds, we will restrict consideration to linear codes in order to ensurethat the typical distance distribution Ntyp(δ) is the same for all codewords. Typical randomcodes do not have this property. In fact, as Barg has recently shown [B01b], whereas the typicalminimum distance from a given codeword in a random code is NδGV(R), as shown in Figure 1,the typical minimum distance of the whole random code is much less than NδGV(R).2  In our subsequent development, we will find the correct error exponents ERCE(R) and ETLC(R)for the random code ensemble and typical linear code, respectively. We will find that thedifference in distance distribution exponents illustrated in Figure 1 is reflected in a differencebetween ERCE(R) and ETLC(R), but only at low rates.1.2 Summary of results and remarksFor the benefit of the reader who may be wondering what of interest can possibly be said atthis date about this old problem, we now summarize our main results and remarks. We donot believe that any of them are new, but on the other hand we believe that most experts ininformation theory and coding will not have previously appreciated at least some of these points.1. It is easy to find the correct error exponent ERCE(R) of the RCE via an output-centeredanalysis that does not explicitly involve the distance distributionN(δ). The correct exponentis given byERCE(R) =½R0− R, 0 ≤ R ≤ Rcrit;Esp(R), Rcrit≤ R ≤ C,(1.3)where R0= log 2 −log(1 + 2pp(1 − p)) is the pairwise error exponent of a BSC with crossoverprobability p, Rcritis the rate at which δGV(Rcrit) = τcrit(p) (given below in (1.8)), Esp(R)denotes the so-called sphere-packing exponent,Esp(R) = D(δGV(R)||p), (1.4)and C (the channel capacity) is the rate at which δGV(C) = p