Random generation of block codes Top Enumeration of block codes Construction of block codes

Construction of block codes

Now let me draw your attention to the construction of transversals of block codes. For doing this it is convenient to identify the alphabet A with the set a := {1,...,a}. Then the elements f=(f(0),...,f(n-1))∈ an can be arranged in the lexicographical order (f1<f2<...<fan), which can be used to define a lexicographical order on the set of all characteristic functions χ: an→ {0,1}, by identifying each function χ with a vector (χ(f1),...,χ(fan)). (So each code word can be identified with a 0-1 vector (χ(f1),...,χ(fan)).) Then we may choose the lexicographically smallest element in the orbit of a block code C (given by its characteristic function) as the canonic representative of this orbit. In order to apply the standard algorithm of orderly generation combined with Read's method of recursion [1][19] and learning techniques [7] as described in [12] we have to compute the Sims-chain [20] of the operating group, which can be quite time consuming using a general algorithm, since Sa Sn is of order n!(a!)n and of degree an. In the next paragraph we will see how to compute this Sims-chain which is given by coset representatives of subgroups of Sa Sn occurring as pointwise stabilizers of certain subsets of an.

The stabilizer of the first element f1=(1,...,1)∈ an is Sa \ 1 Sn. So there are an coset representatives of Sa Sn/ Sa \ 1 Sn given by (ψ,id), where ψ is a function from n to {id,(1,2),(1,3),...,(1,a)}. Having computed the pointwise stabilizers of the first ai elements for 0≤ i<n (i.e. the set of all elements in Sa Sn which stabilize each element in {f1,...,fai}) we can compute the pointwise stabilizers of {f1,...,f} for ℓ∈ {ai+1,...,ai+1} with the following method. The set {ai+1,...,ai+1} can be partitioned into sets {(j-1)ai+1,...,jai} for j=2,...,a. For ℓ∈ {(j-1)ai+1,...,jai} the ℓ-th element f in an is of the form

f=(1,...,1,j,...)..
starting with n-i-1 entries of 1 followed by j in the (n-i)-th position and an arbitrary sequence of length i. Depending on j we have: If j=2, then the pointwise stabilizer of {f1,...,f} can be expressed as a direct product
(Sa \ 1 Sn-(i+1)) × Sa \ 2 × ⟨id⟩ i...
So there are (n-i)(a-1) coset representatives of
(Sa \ 1 Sn-i)/ ((Sa \ 1 Sn-(i+1)) × Sa \ 2 × ⟨id⟩ i),..
given by (ψ,π), where π∈ {id,(n-i,1),...,(n-i,n-i-1)}, ψ(k)=id for k ≠ n-i and ψ(n-i)∈ {id,(2,3),(2,4),...,(2,a)}.

For 3≤ j≤ a the pointwise stabilizer of {f1,...,f} is given by

(Sa \ 1 Sn-(i+1)) × Sa \ j × ⟨id⟩ i,..
and the a-j+1 coset representatives of
((Sa \ 1 Sn-(i+1)) × Sa \ j-1 × ⟨id⟩ i)/ ((Sa \ 1 Sn-(i+1)) × Sa \ j × ⟨id⟩ i)..
are given in the form (ψ,id), where ψ(n-i)∈ {id,(j,j+1),...,(j,a)} and ψ(k)=id for k ≠ n-i.

Because of the fact that the lexicographically smallest element of an orbit is chosen to be the canonic representative of it, the minimal distance of a code can be read from the canonic representative in a very comfortable way. It is the Hamming distance between the first and the second word in the code (with respect to the numbering of the elements of an given above. As a matter of fact the first code word is always f1, and the second code word is of the form (1,...,1,2,...,2) with at least one occurrence of 2. So the minimal distance is the number of 2's in the second code word of the canonic representative. This fact is very useful for recursively constructing all [n,m] block codes of given minimal distance.

In addition to this let me point out that in the case a=2 the S2 Sn classes of functions f: {0,1}n → {0,1} correspond to classes of boolean functions or switching circuits. See for instance [21] or [8].

Harrison and High [9] counted classes of Post-functions under various group actions. These functions are functions f: {1,...,a}n→ {1,...,a}. Even in the case when Sa Sn is acting on the domain of these functions, the number of representatives is growing rather fast. Using the homomorphism principle and the method of surjective resolution [12] it is possible to compute a transversal of Post functions, from a transversal of Sa Sn-orbits on the set of all functions f: {1,...,a}n→ {1,...,a-1}. Iterating this process we can start constructing the classes of Post functions from a transversal of block codes.


harald.fripertinger "at" uni-graz.at, May 10, 2016

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