ANY CODE OF WHICH WE CANNOT THINK IS GOOD

A central paradox of coding theory has been noted for many years, and concerns the existence and construction of the best codes. Virtually every linear code is “good” in the sense that it meets the Gilbert-Varshamov bound on distance versus redundancy. Despite the sophisticated constructions for codes derived over the years, however, no-one has succeeded in demonstrating a constructive procedure that yields such codes over arbitrary symbol fields. A quarter of a century ago, Wozencraft and Reiffen, in discussing this problem, stated that “we are tempted to infer that any code of which we cannot think is good.” Using the theory of Kolmogorov complexity, we show the remarkable fact that his statement holds true in a rigorous mathematical sense: any linear code that is truly random, in the sense that there is no concise way of specifying the code, is good. Furthermore, random selection of a code that does contain some constructive pattern results, with probability bounded away from zero, in a code that does not meet the Gilbert-Varshamov bound regardless of the block length of the code. In contrast to the situation for linear codes, it is shown that there are effectively random nonlinear codes which have no guarantee on distance. In addition, it is shown that the techniques of Kolmogorov complexity can be used to derive typical properties of classes of codes in a novel way. © 1990 IEEE