 |
 |
 |
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
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
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
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
|
|
|
 |
 |
 |
Random
generation of block codes |
 |
 |