 |
 |
 |
Enumeration of
block codes |
Enumeration of block codes
Usually when enumerating or constructing under the action in form
of the exponentiation we can apply Lehmann's Lemma
([14],[15]) which reduces the action of
a wreath product H≀XG on
YX to the action of the group G on the set of all
functions from X into the set of all orbits of H on Y. As a matter
of fact it can't be applied in this situation since
SA≀ Sn acts on
the set of all m-subsets or more generally on the powerset
of An. For enumerating the isometry classes of block
codes each [n,m] code C can be identified with its
characteristic function
| χC(f)=1 if
f∈ C, χC(f)=0 if
f∉ C,.. |
which fulfils |f-1({1})|=m. The other way round, each
function f from An to {0,1} with |f-1({1})|=m
is the characteristic function of an [n,m] block code over A. Using
Pólya's Theorem [18] we can determine the number of
classes of block codes:
Theorem: The number of classes of [n,m] block
codes over the alphabet A is the coefficient of xm in
the expansion of the substitution xi := 1+xi
into the cycle index of the exponentiation
SA≀ Sn. In short
it is the coefficient of xm in
| Z(SA≀ Sn,An|xi :=
1+xi)... |
It is well known how to compute the cycle index of the
exponentiation from the cycle indices of SA and
Sn. See [11][17][16]. Using the computer
algebra system SYMMETRICA [22] the following tables were
computed:
Number of classes of [n,m] block codes over an
alphabet of size 2.
| n\m |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
| 2 |
1 |
1 |
2 |
1 |
1 |
|
|
|
|
|
|
| 3 |
1 |
1 |
3 |
3 |
6 |
3 |
3 |
1 |
1 |
|
|
| 4 |
1 |
1 |
4 |
6 |
19 |
27 |
50 |
56 |
74 |
56 |
50 |
| 5 |
1 |
1 |
5 |
10 |
47 |
131 |
472 |
1326 |
3779 |
9013 |
19963 |
| 6 |
1 |
1 |
6 |
16 |
103 |
497 |
3253 |
19735 |
120843 |
681474 |
3.561696 |
| 7 |
1 |
1 |
7 |
23 |
203 |
1606 |
18435 |
221778 |
2773763 |
33.297380 |
375.158732 |
| 8 |
1 |
1 |
8 |
32 |
373 |
4647 |
91028 |
2074059 |
51.107344 |
1245.930065 |
28900.653074 |
| 9 |
1 |
1 |
9 |
43 |
649 |
12320 |
404154 |
16.957301 |
805.174011 |
38921.113842 |
1.816451.773537 |
| 10 |
1 |
1 |
10 |
56 |
1079 |
30493 |
1646000 |
124.727148 |
11244.522420 |
1.063289.204514 |
98.630203.059528 |
Number of classes of [n,m] block codes over an
alphabet of size 3.
| n\m |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
| 2 |
1 |
1 |
2 |
4 |
5 |
5 |
4 |
2 |
1 |
1 |
|
| 3 |
1 |
1 |
3 |
10 |
34 |
105 |
321 |
846 |
1984 |
4023 |
7074 |
| 4 |
1 |
1 |
4 |
20 |
144 |
1245 |
12473 |
120213 |
1067757 |
8.508432 |
60.801152 |
| 5 |
1 |
1 |
5 |
35 |
490 |
11075 |
334678 |
10.274578 |
293.142769 |
7563.157341 |
176207.637611 |
| 6 |
1 |
1 |
6 |
57 |
1470 |
82918 |
7.194272 |
664.545445 |
57778.060974 |
4.570181.600483 |
327.615878.641570 |
Number of classes of [n,m] block codes over an
alphabet of size 4.
| n\m |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
| 2 |
1 |
1 |
2 |
4 |
10 |
13 |
23 |
26 |
32 |
26 |
23 |
| 3 |
1 |
1 |
3 |
10 |
55 |
254 |
1643 |
10164 |
63488 |
364843 |
1930906 |
| 4 |
1 |
1 |
4 |
20 |
223 |
3227 |
77194 |
2097080 |
57.796870 |
1502.295684 |
36065.804158 |
| 5 |
1 |
1 |
5 |
35 |
759 |
32970 |
2877651 |
311.400852 |
34630.385050 |
3.667889.498353 |
360.865277.628727 |
| 6 |
1 |
1 |
6 |
57 |
2309 |
292103 |
90.647411 |
37593.032352 |
16.429342.163157 |
6925.787777.638463 |
2.729333.815881.686935 |
harald.fripertinger "at" uni-graz.at, May 10,
2016
|
|
|
 |
 |
 |
Enumeration of
block codes |
 |
 |