   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  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
 p(f Î w) = 1 a
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
 ćç č An m ö÷ ř (y,p)
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) (). 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