A class of error-correcting codes invented by Bose, Chaudhuri, and
Hocquenghem became popular in the early 1960s. One can find a
primitive binary BCH code of any desired length of the form
*n* = 2^{m} - 1, and any desired designed
distance *d*. The dimension of this code, *k*, is not easy
to determine, even in the asymptotic limit when *d* and *n*
go to infinity in a fixed ratio, *u* = *d/n*.
Henry Mann first investigated this enumerative combinatorial problem
and solved it for values of the form
*u* = 2^{-k}. Berlekamp solved it for
all values of *u*, and showed that
*k* ~ *n*^{s(u)}, where
*s*(*u*) is the singular function shown in the figure. For
all values of *u* in the open interval between 0 and 1, it is
defined by some interesting manipulations on the binary expansion of
*u*. Quite in addition to its surprising appearance as the
solution to an applied problem, the singular function
*s*(*u*) has some unusual mathematical properties: The
Hausdorf dimension of the set of points in the subinterval
(*a*, *b*) at which the function is not differentiable
is *s*(*a*). However, the derivative *s'*(0) turns out
to be -1/ln 4, and this fact is crucial to answering another
important question: if one requires that *k* and *n*
approach infinity in a fixed ratio
*R* = *k*/*n*, then the distance of the
corresponding BCH code is
*d* ~ 2*n* (ln *R*^{-1}) / lg
*n*. Technicalities proliferate because one can define the
distance in at least three slightly different ways: the design
distance, the Bose distance, or the actual distance. The answers
differ only in higher order terms.

*Algebraic Coding Theory*, McGraw-Hill, 1968; revised edition,
Aegean Park Press, Laguna Hills, CA, 1984.
See Chapter 12.

*"Long Primitive Binary BCH Codes Have Distance d* ~ 2*n* ln *R*^{-1}/ln *n* ...", IEEE Trans Inform Theory, **IT18**:415-426 (1972); Math. Rev. 48-13447.