Covering radius is a geometric parameter of a code. A (binary) code $C$ is a subset of $V\coloneq{F}\sb 2\sp n$; the covering radius $R(C)$ of $C$ is the least integer $r$ such that the spheres of radius $r$ in the Hamming metric centered at the points of $C$ cover $V$. A good covering code is one with a small covering radius. The authors explain that applications of covering radius occur in data compression, decoding of errors and erasures, broadcasting in interconnection networks, football pools, write-once memories, speech coding, cellular telecommunications, and subset sums and Cayley graphs.

In Chapter 2, Basic Facts, the authors reorganize and massage Kleitman's proof [D. J. Kleitman, J. Combinatorial Theory 1 (1966), 209--214; MR 34 #78] of the conjecture of Erdos that in $V$ every subset of diameter $2r<n$ has size bounded above by that of the sphere of radius $r$. Here they have new results on the sizes of intersections and unions of triples of spheres.

The book has a full account of all aspects of covering radius. After introductory sections on finite fields and codes, one almost never finds a theorem stated without proof. The proofs are leisurely and complete. The book could thus be useful for beginners and experts alike.

Normality, too complicated to define in this review, allows construction of good covering codes by the amalgamated direct sum construction, both introduced in 1985 by R. L. Graham and N. J. A. Sloane [IEEE Trans. Inform. Theory 31 (1985), no. 3, 385--401; MR 87c:94048]. Although there are abnormal nonlinear codes, there are no known abnormal binary linear codes. The question remains: is every binary linear code normal? The authors devote a whole chapter to normality and its offshoots.

The least covering radius of any $[n,k]$ code is denoted $t[n,k]$. Introduced in the 1985 survey [G. D. Cohen et al., op. cit.], this function is thoroughly discussed in Chapter 5, which ends with 14 pages on the construction due to A. A. Davydov [Problemy Peredachi Informatsii 26 (1990), no. 4, 38--55; MR 92b:94038], whose codes yield several new upper bounds on $t$, stated in terms of the related function $l$. For redundancy $m$ and covering radius $r, l(m,r)$ is the smallest value of $n$ such that there is a binary linear $[n,n-m]$ code of covering radius $r$. Example: $m>10$ implies $l(4m,4)<47·2\sp {(m-4)}$. The length function $l$ was introduced in 1989 by R. A. Brualdi, V. S. Pless and R. M. Wilson [IEEE Trans. Inform. Theory 35 (1989), no. 1, 99--109; MR 90g:94016].

Chapter 6 studies lower bounds on the size of nonlinear codes with given length and covering radius. The method of excess counting---seeing whether points are necessarily covered more than once---is applied to the case $R=1$ and also a little to the general case. Interestingly, as we find from the notes at the chapter's end, the first results using this method are due to S. M. Johnson [Utilitas Math. 1 (1972), 121--140; MR 46 #3350]. Later researchers independently rediscovered the method---and carried it further. Johnson also introduced [in S. M. Johnson, op. cit.] the "pair-covering inequality", which is basic to the method of linear inequalities discussed at length here, and also rediscovered in recent years. There is a table of bounds for $n\le33$ and $R\le10$.

Chapter 7 studies lower bounds on $t[n,k]$ and $l(m,R)$ for linear codes. The methods have gone from computer searches to elaborate, sometimes elegant, proofs of nonexistence of specific codes. For example, R. Struik [IEEE Trans. Inform. Theory 40 (1994), no. 5, 1406--1416; MR 95h:94034] proved that there is no binary $[33,24]$ code with $R=2$. This result implies that $t[33,24]>2$. There are tables of $t[n,k]$ and of $l(m,R)$ for $R$ up to 63, although the results in the chapter are confined to $R=2$ and 3.

The authors focus their investigations of upper bounds on several specific questions, such as: What is the largest covering radius among all linear $[n,k,d]$ codes? Covering radii of subcodes and relations with the dual weight spectrum are treated, including a nice proof of the Delsarte theorem mentioned above, extended from the linear case of [S. N. Litsyn and A. A. Tietavainen, European J. Combin. 17 (1996), no. 2-3, 265--270; MR 97e:94013] to the general case here.

In discussing Reed-Muller codes the authors prove a new result, Theorem 9.2.16, that a binary self-complementary code of length $n$ and dual distance 3 or greater has norm $\lfloor n-\sqrt{n-1}\rfloor$. The earlier version of the result, in [R. L. Graham and N. J. A. Sloane, IEEE Trans. Inform. Theory 31 (1985), no. 3, 385--401; MR 87c:94048], applied only to first-order Reed-Muller codes. They also give a new proof for McLoughlin's determination [A. M. McLoughlin, SIAM J. Appl. Math. 37 (1979), no. 2, 419--422; MR 81a:94034] of the covering radius of $RM(m-3,m)$.

After a short chapter, mostly on BCH codes, they devote a chapter to perfect codes, proving that any nontrivial perfect code over $F\sb q$ has the parameters of one of the well-known perfect codes. Then they discuss at length the still-unsolved problem of finding all the (nonlinear) perfect codes of covering radius 1.

The hoary sphere bound is a poor upper bound on the packing radius but a good lower bound on the covering radius. In fact, after normalizing by dividing these radii and the bound by the length of the code, the authors show that asymptotically "virtually all codes have covering radius achieving" the sphere bound. They prove this result for linear codes as well. At the end of Section 12.3, they write "So, in contrast to error-correcting codes, for coverings the best asymptotic bound is achieved constructively."

Next comes a chapter titled "Weighted Coverings". In this concept, all the vectors at a given distance from the center of the covering sphere are assigned a weight. "If several such spheres intersect in a point, we define the density at that point as the sum of the weights of the corresponding layers. A code is called a weighted covering if the density at each point is at least one." If the density is exactly 1 at each point, the code is called a perfect weighted covering code. A Lloyd theorem is proved for such codes. These ideas are applied in later chapters. Chapter 14, Multiple Coverings, treats codes that cover every vector in the ambient space at least some prescribed number of times. The chapter includes constructions, tables, and a section on multiple coverings of "deep holes" (vectors at maximum distance from the code).

Football pools occupy a brief chapter, bringing in mixed coverings (ternary-binary, to allow for ties and cases where one of the three outcomes can be ruled out). Interestingly, the first appearance of the ternary Golay code predated Golay's publication by a good year. A Finnish devotee of football pools thought it up in list form (!) and published it in 1947. The story is told here. The reviewer's conjecture is that the binary $[7,4,3]$ perfect code must have been known to the football poolers well before that. A. M. Gleason once said that he had been told of the latter code by a school chum "in the eighth grade" as a system for betting. That would have been in the early 1930s.

A tiling of ${F}\sb 2\sp n$ is a pair $(V,A)$ of subsets of the space such that $V+A={F}\sb 2\sp n$ and $(V+V)\cap(A+A)=\{{0}\}$. They remark in the notes that "tilings of ${F}\sb 2\sp n$ with arbitary bodies correspond to perfect codes correcting an arbitrary set of errors". They present a number of results on tilings, including a characterization of all tiles $(V)$ of size at most 8. To each tiling is associated a perfect binary code of length $\vert V\vert -1$. They generalize the Lloyd theorem to cover tiles.

Chapter 17 applies covering ideas to the problem of reusing a "write-once" memory (WOM), such as a laser disk, which can be pitted but not "unpitted". It comes down to finding "the worst way [to shorten] a linear code, as far as covering radius is concerned". In an example they show that the $[23,12,7]$ Golay code can be used to do 3 writings of 11 bits each on a 23-bit WOM. What is actually written is a coset leader, of low weight; the system goes to the syndrome of that coset as the information. This example is generalized.

The next class of applications arises from viewing the cosets of a code as vertices of a (Cayley) graph. The covering radius is the diameter of the graph. Constrained memories are, e.g., WOMs, write-isolated memories ("WIMs; no change of two consecutive positions is allowed when updating"), and others. The final class of applications is in Chapter 19, Heterodox Coverings, where, e.g., all spheres in the covering might have different radii. Several other kinds of coverings are also considered here. Applications to correction or detection of physical failures in networks and to cryptography are mentioned in the notes.

The final chapter, on complexity, includes a discussion of "derandomization", which has applications also to VLSI testing.

This excellent book is smoothly written, with leisurely proofs and good motivation. There are a few new results in it, but the authors were too modest to mark them as new for the reader. I do have one complaint: the authors' grating neologisms "upperbound" and "upperestimate" (used as verbs) should be "bound above". As nouns they should be two words.

The authors have obviously paid careful attention to their writing; there is a uniform style, fluid and clear, with no jarring changes from one chapter to the next. The paper is of excellent quality; the margins could be bigger. It would be hard to imagine a better, more thorough, up-to-date, and authoritative treatment of covering codes than the one we find in this book.

Revenir à la page d'accueil
Revenir en haut de la page