Proof: Consider constructing from using Theorem 3. Any two coset leaders l and (l ) of must each have weight at most , by the definition of the covering radius. Consider the weight of a corresponding coset leader of , based on Theorem 3:
min | wt(a | l ), wt | (l ) | |
With some combinatorial analysis, we can also establish a recursive lower bound on the covering radius of -codes. Specifically, we shall make use of the following simple combinatorial lemma, which we provide without proof.
Proof: Following convention, we let denote the number of errors that the codes of a -family can correct. It is well-known that each vector in _{2}^{nm - 1} of weight t must be a unique coset leader for . Moreover, using our assumption about n_{0} (which also holds for n_{m}, since n_{m} n_{0}), Lemma 2 implies that
minwt(a | l), wt | (l ) | |||
The result in Theorem 4 also applies to all -families trivially seeded with the code _{d}.
If a -family is trivially seeded, then, necessarily, n_{0} = d and . Thus,
so that Theorem 4 applies to the remaining codes in the family.We now turn our attention to generating mappings which produce codes whose information rate is locally maximized. More specifically, for any code with covering radius , we will consider only generating mappings f with the property that the Hamming distance from to is exactly . We will call such mappings minimal generating mappings, and the corresponding family of codes minimal -codes, because they locally minimize length (and hence locally maximize information rate) for a given dimension and minimum-distance.
As an example, the generating mappings for the traditional lexicodes and the trellis-oriented lexicodes are both minimal. We may now easily strengthen Lemma 1 by observing in its proof that = d - for minimal -codes.
The covering radius bounds we have developed for -codes translate naturally to length bounds.