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 th e binary symmetric channel (BSC) is small for a wide range of useful crosso ver probabilities. Thus even far from capacity, random codes have nearly th e same error performance as the best possible long codes. The paper also de monstrates that a small reduction k - (k) over tilde in the number of infor mation bits conveyed by a codeword mill make the error performance of an (n , (k) over tilde) random code better than the sphere-packing lower bound fo r an (n, k) code as long as the channel crossover probability is somewhat g reater than a critical probability. For example, the sphere-packing lower b ound for a long (n, k),rate 1/2, code will exceed the error probability of an (n, (k) over tilde) random code if k - (k) over tilde > 10 and the cross over probability is between 0.035 and 0.11 = H-1(1/2). Analogous results ar e presented for the binary erasure channel (BEC) and the additive white Gau ssian noise (AWGN) channel. The paper also presents substantial numerical e valuation of the performance of random codes and existing standard lower bo unds for the BEG, BSC, and the AWGN channel. These last results provide a u seful 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 boun ds over a,vide range of block lengths.