References Top Construction of block codes 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 ω of a block code then the probability that a random-generated block code f lies in ω equals
p(f∈ ω)=.. 1

α
..
where α 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 α, the number of isometry classes of [n,m] block codes over A. Then choose a conjugacy class C of SA Sn with probability
p(C):=
|C||
An
m



(ψ,π) 
|

n!(A!)n!α
,
where

An
m



(ψ,π) 
is the set of fixed points of an arbitrary element (ψ,π) of C acting on all m-sets of An. Finally construct a characteristic function χ: An→ {0,1} of an [n,m] block code that takes values 0 or 1 on the cycles of (ψ,π)∈ C which are distributed uniformly at random.
In a first step this algorithm has to compute the cycle index of SA Sn as described above in order to compute α. 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 (ψ,π) ([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 Sn if and only if
..

i,k
aik=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 (ψ,π) 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 "at" uni-graz.at, May 10, 2016

References Top Construction of block codes Uni-Graz Mathematik UNIGRAZ online Random generation of block codes Valid HTML 4.0 Transitional Valid CSS!