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))∈ aⁿ can be arranged in the lexicographical order (f₁<f₂<...<f_aⁿ), which can be used to define a lexicographical order on the set of all characteristic functions χ: aⁿ→ {0,1}, by identifying each function χ with a vector (χ(f₁),...,χ(f_aⁿ)). (So each code word can be identified with a 0-1 vector (χ(f₁),...,χ(f_aⁿ)).) 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 S_a≀ S_n is of order n!(a!)ⁿ and of degree aⁿ. In the next paragraph we will see how to compute this Sims-chain which is given by coset representatives of subgroups of S_a≀ S_n occurring as pointwise stabilizers of certain subsets of aⁿ.

The stabilizer of the first element f₁=(1,...,1)∈ aⁿ is S_a \ 1≀ S_n. So there are aⁿ coset representatives of S_a≀ S_n/ S_a \ 1≀ S_n 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 aⁱ elements for 0≤ i<n (i.e. the set of all elements in S_a≀ S_n which stabilize each element in {f₁,...,f_aⁱ}) we can compute the pointwise stabilizers of {f₁,...,f_ℓ} for ℓ∈ {aⁱ+1,...,aⁱ⁺¹} with the following method. The set {aⁱ+1,...,aⁱ⁺¹} can be partitioned into sets {(j-1)aⁱ+1,...,jaⁱ} for j=2,...,a. For ℓ∈ {(j-1)aⁱ+1,...,jaⁱ} the ℓ-th element f_ℓ in aⁿ 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 {f₁,...,f_ℓ} can be expressed as a direct product

(S_a \ 1≀ S_n-(i+1)) × S_a \ 2 × ⟨id⟩ ⁱ.^._.

So there are (n-i)(a-1) coset representatives of

(S_a \ 1≀ S_n-i)/ ((S_a \ 1≀ S_n-(i+1)) × S_a \ 2 × ⟨id⟩ ⁱ),^._.

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 {f₁,...,f_ℓ} is given by

(S_a \ 1≀ S_n-(i+1)) × S_a \ j × ⟨id⟩ ⁱ,^._.

and the a-j+1 coset representatives of

((S_a \ 1≀ S_n-(i+1)) × S_a \ j-1 × ⟨id⟩ ⁱ)/ ((S_a \ 1≀ S_n-(i+1)) × S_a \ j × ⟨id⟩ ⁱ)^._.

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 aⁿ given above. As a matter of fact the first code word is always f₁, 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 S₂≀ S_n classes of functions f: {0,1}ⁿ → {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}ⁿ→ {1,...,a}. Even in the case when S_a≀ S_n 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 S_a≀ S_n-orbits on the set of all functions f: {1,...,a}ⁿ→ {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

Construction of block codes