| | | **Construction of block codes** |

# Construction of block codes

Now let me draw your attention to the construction of
transversals of block codes.
For doing this it is convenient to identify the alphabet
*A* with the set __a__:={1,...,a} .
Then the elements *f=(f(0),...,f(n-1))Î*__a__^{n} can be arranged in the lexicographical order
*(f*_{1}<f_{2}<...<f_{an}), which can be used to define a lexicographical
order on the set of all characteristic functions
*c:*__a__^{n} -> {0,1} , by
identifying each function *c* with a vector
*(c(f*_{1}),...,c(f_{an})).
(So each code word can be identified with a 0-1 vector
*(c(f*_{1}),...,c(f_{an})).)
Then we may choose the lexicographically smallest element
in the orbit of a
block code *C* (given by its characteristic function) as the
*canonic representative* of this orbit. In order to apply the
standard algorithm of *orderly generation* combined with
*Read's method of recursion*
[1][19]
and *learning techniques* [7] as described in
[12]
we have to compute the *Sims-chain* [20]
of the operating group, which can be quite
time consuming using a general algorithm, since *S*_{a} wr S_{n}
is of order *n!(a!)*^{n} and of degree *a*^{n}.
In the next paragraph we will see how to compute
this Sims-chain which is given by coset representatives of subgroups
of *S*_{a} wr S_{n} occurring as pointwise stabilizers of
certain subsets of __a__^{n}.
The *stabilizer* of the first element
*f*_{1}=(1,...,1)Î__a__^{n}
is *S*_{a \ 1} wr S_{n}. So there are *a*^{n} *coset representatives* of * S*_{a} wr S_{n}/
S_{a \ 1} wr S_{n} given by *(y, id )*, where
*y* is a function from
__n__ to *{ id ,(1,2),(1,3),...,(1,a)} *.
Having computed the pointwise stabilizers of the first *a*^{i} elements
for *0£i<n* (i.e. the set of all elements in *S*_{a} wr S_{n}
which stabilize each element in *{f*_{1},...,f_{ai}} )
we can compute the pointwise stabilizers of
*{f*_{1},...,f_{l }} for
*l Î{a*^{i}+1,...,a^{i+1}} with the following method.
The set *{a*^{i}+1,...,a^{i+1}} can be partitioned into sets
*{(j-1)a*^{i}+1,...,ja^{i}} for *j=2,...,a*.
For *l Î{(j-1)a*^{i}+1,...,ja^{i}} the *l *-th element
*f*_{l } in __a__^{n} is of the form

*f*_{l }=(1,...,1,j,...)

starting with *n-i-1* entries of 1 followed by *j* in the *(n-i)*-th
position and an arbitrary sequence of length *i*.
Depending on *j* we have:
If *j=2*, then the pointwise stabilizer of
*{f*_{1},...,f_{l }} can be expressed as a direct product
*(S*_{a \ 1} wr S_{n-(i+1)})´S_{a \ 2}´á id ñ^{i}.

So there are *(n-i)(a-1)* coset representatives of
*(S*_{a \ 1} wr S_{n-i})/
((S_{a \ 1} wr S_{n-(i+1)})´S_{a \ 2}´á id ñ^{i}),

given by *(y,p)*, where *pÎ{ id ,(n-i,1),...,(n-i,n-i-1)} *, *y(k)= id * for *k¹n-i* and
*y(n-i)Î{ id ,(2,3),(2,4),...,(2,a)} *.
For *3£j£a* the pointwise stabilizer of
*{f*_{1},...,f_{l }} is given by

*(S*_{a \ 1} wr S_{n-(i+1)})´S_{a \ j}´á id ñ^{i},

and the *a-j+1* coset representatives of
*((S*_{a \ 1} wr S_{n-(i+1)})´S_{a \ j-1}´á id ñ^{i})/
((S_{a \ 1} wr S_{n-(i+1)})´S_{a \ j}´á id ñ^{i})

are given in the form *(y, id )*, where
*y(n-i)Î{ id ,(j,j+1),...,(j,a)} *
and *y(k)= id * for *k¹n-i*.
Because of the fact that the lexicographically smallest element of
an orbit
is chosen to be the canonic representative of it, the *minimal
distance* of a code can be read from the canonic representative
in a very comfortable way. It is the *Hamming distance*
between the first and the second word in the code (with respect to
the numbering of the elements of __a__^{n} given above.
As a matter of fact the first code word is always *f*_{1}, and the
second code word is of the form *(1,...,1,2,...,2)* with
at least one occurrence of 2. So the minimal distance is the number of
*2*'s in the second code word of the canonic representative. This
fact is very useful for recursively constructing all *[n,m]* block
codes of given minimal distance.

In addition to this let me point out that in the case *a=2* the
*S*_{2} wr S_{n} classes of functions *f:{0,1} *^{n}
-> {0,1}
correspond to classes of *boolean functions* or
*switching circuits*. See for instance [21] or
[8].

Harrison and High [9]
counted classes of *Post-functions* under various group actions. These functions
are functions *f:{1,...,a} *^{n} -> {1,...,a} .
Even in the case when
*S*_{a} wr S_{n} is acting on the domain of these functions,
the number of representatives is growing rather fast. Using the
*homomorphism principle* and the method of
*surjective resolution* [12]
it is possible to compute a transversal
of Post functions, from a transversal of *S*_{a} wr S_{n}-orbits
on the set of all functions
*f:{1,...,a} *^{n} -> {1,...,a-1} .
Iterating this process we can start constructing the classes of
Post functions from a transversal of block codes.

harald.fripertinger@kfunigraz.ac.at,

last changed: January 23, 2001

| | | **Construction of block codes** |