 |  |  | 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 Dixon-Wilf 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 random-generated block code f
lies in w equals
where a is the total number of isometry classes
of [n,m] block codes.
The Dixon-Wilf 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 SA wr Sn with probability
|
p(C): = |
|
| C| |
ê
ê
ê
|
|
æ
ç
è
|
|
An
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 m-sets
of An.
Finally construct a characteristic function c: An -> {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 SA wr Sn 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 SA.
These conjugacy classes can be described by integer matrices (ai,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 SA has
conjugacy classes corresponds to a conjugacy class of SA wr Sn
if and only if
åi,kaik=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(Ci) only if the
random number (lying in [0,1[)
determining which conjugacy class to choose
exceeds åj=1i-1p(Cj).
The efficiency of this method heavily depends on the numbering of the
conjugacy classes. So this numbering should be chosen such that
p(Ci)³p(Ci+1) which leads to C1={ 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 |