Construction of block codesTopIntroductionEnumeration 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 012345678910
1111
211211
3113363311
4114619275056745650
5115104713147213263779901319963
6116161034973253197351208436814743.561696
711723203160618435221778277376333.297380375.158732
8118323734647910282074059 51.107344 1245.930065 28900.653074
9119436491232040415416.957301805.174011 38921.1138421.816451.773537
101110561079304931646000124.72714811244.522420 1.063289.20451498.630203.059528

 

Number of classes of [n,m] block codes over an alphabet of size 3.
n\m 012345678910
11111
21124554211
31131034105321846198440237074
4114201441245124731202131067757 8.508432 60.801152
51153549011075334678 10.274578 293.142769 7563.157341 176207.637611
611657147082918 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 012345678910
111111
2112410132326322623
31131055254164310164634883648431930906
4114202233227771942097080 57.796870 1502.295684 36065.804158
511535759329702877651 311.400852 34630.385050 3.667889.498353 360.865277.628727
6116572309292103 90.647411 37593.032352 16.429342.163157 6925.787777.638463 2.729333.815881.686935

harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001

Construction of block codesTopIntroductionEnumeration of block codes