Research on Multicovering Radii of Codes

Error correcting codes are essential tools in modern communication, making it possible to communicate over noisy media such as radio waves. Physical storage media for computers can also be considered as noisy media. The covering radii of codes have been the subject of hundreds of papers over the past several decades. This quantity is related to several important parameters of codes such as minimal distance. The multi-covering radius of a code is a new notion I resently discovered that generalizes the covering radius. Understanding it is likely to lead to a greater understanding of codes in general. It is, in fact, quite surprising that it has not been discovered previously.

An error correcting code of length n is a set C of vectors in n -dimensional space over GF(2) . The covering radius of a code C is the smallest integer r such that every vector in GF(2)^n is within distance r of at least one code word in C. This notion plays a crucial role in coding theory and has been the subject of hundreds of papers over the past two decades (The notion of covering radius also arises in horserace betting pools. Some of the earliest results in the area were found by nonmathematicians and published in betting pool magazines!.) A critical step in the proof of one of the existence theorems in my paper On the Existence of Secure Keystream Generators requires the existence of a code with small covering radius each of whose code words can be generated by a fast feedback register. The Reed-Muller codes satisfy these requirements. This gives a result that says there exists a family of sequences that resists all attacks of the type studied, in the sense that each attack is wrong on close to half the bits for infinitely many sequences in the family.

A stronger result would say that every attack fails on all but finitely many of the sequences. It would then be possible for a cryptographer to choose a sequence that resists any given finite set of attacks. To prove such a result one needs a code with small {\em multicovering radius}. If m is a positive integer, then the m-covering radius of C is the smallest integer r such that for every set {v1,...,vm} in GF(2)^n , there is a vector c in C such that the distance from every vi to c is at most r . Surprisingly, this is a new concept, previously unstudied by coding theorists. In the paper The Multicovering Radii of Codes I have initiated its study. This paper describes the basic properties of multicovering radii and gives several lower and upper bounds. A natural question is, for a given r , m , and n , what is the smallest code whose m -covering radius is at most r ? As it turns out, there may be no such code. For example, if m\ge 2 , it is necessary that r be at least n/2 . In fact, the minimal r for which such a code exists is the m-covering radius of C=GF(2)^n . I have derived tight asymptotic bounds on these radii. I also derived tight asymptotic bounds on the m-covering radii of Hamming codes.