We now construct
a family of cyclefree codes that attain the bound of Theorem 3.6
with equality, for all values of n and k. The construction
is quite simple: as in Section 3.3,
we start with the singleparitycheck code
_{k+1} of dimension k,
and repeat the symbols of
_{k+1} until a code
of length n
is obtained. It is obvious that the dimension of
is k, and
by Lemma 3.4 this code is cyclefree. The minimum distance of
will depend on the sequence of symbol repetitions.
The idea is to
repeat each symbol in
_{k+1} equally often and as much as possible.
For example, for n = 13 and k = 3, we obtain the following
paritycheck matrix in reduced canonical form (0 bits have been
intentionally replaced with blank spaces to accentuate the structure
of the matrix):
which defines a (13, 3, 6) cyclefree code.
In general, the number of symbols to be repeated is k + 1,
while the number of positions available is n  (k + 1).
Write:
n  (k + 1) = a(k + 1) + b
where a, b are integers, and
0bk. This
decomposition of the number of available positions
means that in our construction exactly k  b + 1 symbols
of
_{k+1} will be repeated
times, while the remaining b symbols of
_{k+1}
will be repeated a + 1 times. If bk  1, then
at least two symbols of
_{k+1} are repeated
exactly a times. Since
_{k+1} contains
a codeword of weight 2 in every two positions,
the minimum distance of the resulting code
is
If b = k, then only one symbol in
_{k+1}
is repeated a times, while all the other
symbols are repeated a + 1 times. In this
case, the minimum distance of
is
d = 2 + a + (a+1) = 2 + 1 
(9) 
Notice that b = k if and only if
n + 1 0 mod (k + 1).
Hence it follows from (3.17) and (3.18) that the
code
constructed in this manner
attains the bound of Theorem 3.6 with equality.
Figure 3.6 schematically shows two alternative cyclefree Tanner
graphs for codes resulting from this construction (compare the Tanner graph
in Figure 3.6a with Figure 3.2b).
Figure 3.6:
Two alternative Tanner graphs for optimal cyclefree codes.

We point out that although cyclefree codes obtained by
repeating symbols in
_{k+1} have the highest possible
minimum distance, they are not the only codes with this property. For example, consider the following
paritycheck matrix in reduced canonical form:
It is easy to see that this matrix defines a (13, 3, 6) cyclefree
code
, whose distance attains the bound of Theorem 3.6 with equality.
This code was obtained by repeating symbols in a (5, 3, 2) code.
It can be readily verified that
is not equivalent to
the (13, 3, 6) cyclefree code
, defined by the paritycheck
matrix in (3.16) and obtained by repeating symbols
in
_{4}. For instance,
contains the allone codeword,
while
does not.
http://people.bu.edu/trachten