 |  |  | 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 wr 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 wr Sn acts on the set of all m-subsets or more generally
on the powerset
2(An)
of An.
For enumerating the isometry classes of block codes
each [n,m] code C can be identified with its characteristic
function
cC:An -> {0,1}
cC(f)=1 if fÎC, cC(f)=0 if
f not Î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 wr Sn. In short it is the coefficient
of xm in
Z(SA wr 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@kfunigraz.ac.at,
last changed: January 23, 2001
| | | Enumeration of block codes |