   Random generation of block codes 
Random generation of block codes
For many parameter values n, m and a there are far too many
representatives in order to compute complete lists. In these situations
we can apply the
so called DixonWilf algorithm [2]
for generating block codes uniformly at random.
I.e. given the isometry class w of a block code
then the probability that a randomgenerated block code f
lies in w equals
where a is the total number of isometry classes
of [n,m] block codes.
The DixonWilf algorithm says:
Theorem:
In order to generate [n,m] block codes over the alphabet
A uniformly at random, first compute a,
the number of isometry classes of [n,m] block codes over A.
Then choose a conjugacy class C of S_{A} wr S_{n} with probability
p(C): = 
 C 
ê ê
ê


æ ç
è


A^{n}
m


ö ÷
ø

(y,p)


ê ê
ê


n!( A!)^{n!}a

, 

where
is the set of fixed points
of an arbitrary element (y,p) of C acting on all msets
of A^{n}.
Finally construct a characteristic function c: A^{n} > {0,1}
of an [n,m] block code that takes values 0 or 1 on the
cycles of (y,p)ÎC which are distributed uniformly at random.
In a first step this algorithm
has to compute the cycle index
of S_{A} wr S_{n} as described above in order to compute a.
Then it must determine the conjugacy classes of the acting group
which is the complete monomial group of degree n over S_{A}.
These conjugacy classes can be described by integer matrices (a_{i,k})
holding the cycle types of the cycleproducts
of (y,p) ([12]).
In other words, a matrix having n columns
and as many rows as S_{A} has
conjugacy classes corresponds to a conjugacy class of S_{A} wr S_{n}
if and only if
å_{i,k}a_{ik}=n.
In the next step the probabilities
of the conjugacy classes can be computed.
Finally the construction of the characteristic functions of block codes
which are fixed points of the chosen element (y,p)
in the chosen conjugacy class C
must be organized such that it produces only functions of weight m.
In order to minimize the amount of work before the algorithm actually
starts to generate block codes it is useful to start the generation
at once after having computed the information on the first conjugacy
class,
and evaluate further conjugacy classes and their probabilities only
if required. This means we have to compute p(C_{i}) only if the
random number (lying in [0,1[)
determining which conjugacy class to choose
exceeds å_{j=1}^{i1}p(C_{j}).
The efficiency of this method heavily depends on the numbering of the
conjugacy classes. So this numbering should be chosen such that
p(C_{i})³p(C_{i+1}) which leads to C_{1}={ id } .
In the computer algebra system SYMMETRICA there are all kinds of
routines implemented
in order to compute orbit transversals of block codes
or to generate them uniformly at random.
harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001
   Random generation of block codes 