Random generation of linear codes

Random generation of linear codes

In this section we want to demonstrate how the Dixon-Wilf-algorithm can be used in order to generate linear codes distributed over all isometry classes uniformly at random. Actually this algorithm was first developed for the random generation of unlabelled graphs (cf. [3]). Before describing it in all details for an arbitrary group action we need some more notions: The stabilizer of x∈ X under the action of a group G is the subgroup

G_x := {g∈ G | gx=x}

of G, whereas the set of fixed points of g∈ G is the subset

X_g := {x∈ X | gx=x}

of X. The set of all G-orbits in X will be denoted by

G\\X := {G(x) | x∈ X}.

Theorem: The Dixon-Wilf-algorithm. Let G be a finite group acting on a finite set X. Choose a conjugacy class C of G with the probability

p(C) := |C|⋅ |X_g|

|G|⋅ |G\\X|
, for an arbitrary g∈ C.

Pick any g∈ C and determine at random a fixed point x of g. Then the probability that x lies in a given orbit ω∈ G\\X is equal to 1/|G\\X|, i. e. it does not depend on the special choice of ω. So the output of this algorithm is distributed uniformly at random over all G-orbits on X.

Now we are in a position to apply this algorithm to the group action (*) describing the isometry classes of linear codes. The conjugacy classes of the operating group, which is a direct product of two groups, can be described as pairs of the conjugacy classes of the two factors. So each conjugacy class C is a direct product C=C_P × C_S of a conjugacy class C_P in PGL_k(q) and a conjugacy class C_S in S_n. Furthermore we will use T_nkq as an abbreviation for the cardinality |PGL_k(q) × S_n\\(PG_k-1(q))ⁿ|. In other words T_nkq is the number of all isometry classes of linear (n,l)-codes without 0-columns for l≤ k.

Corollary: Let n and k≤ n be positive integers. The following algorithm computes generator matrices Γ of linear (n,l)-codes over GF(q) for l≤ k uniformly at random:
Choose a conjugacy class C of PGL_k(q) × S_n with the probability

p(C) := |C|⋅ |(PG_k-1(q))ⁿ_(A,π)|

|S_n|⋅ |PGL_k(q)| ⋅ T_nkq
, for an arbitrary pair (A,π)∈ C,

where (PG_k-1(q))ⁿ_(A,π) is the set of all fixed points of (A,π) in (PG_k-1(q))ⁿ, i. e. the set of all functions Γ∈ (PG_k-1(q))ⁿ which fulfill A⋅ Γ=Γ o π. Then pick any (A,π)∈ C and generate a fixed point Γ of (A,π) uniformly at random.

In order to apply this algorithm we want to take a closer look at it. The order of S_n is given by n!, the order of PGL_k(q) equals [q]_k/(q-1) where [q]_k is the order of GL_k(q) given by

[q]_k=(q^k-1)(q^k-q)...(q^k-q^k-1).

For the computation of T_nkq consult one of the articles [8][5][4][6]. So we can compute the denominator in p(C).

For computing the nominator we must know the conjugacy classes of S_n and of PGL_k(q). Each conjugacy class of S_n can be described by a cycle type λ of length n. Such a cycle type λ is a sequence of nonnegative integers (λ₁,...,λ_n) such that

ni
∑
i=1
⋅ λ_i=n.

The conjugacy class of S_n corresponding to λ consists of all permutations of cycle type λ. These are

n!

∏ _i i^λ_i⋅ λ_i!

permutations.

In order to describe the conjugacy classes of PGL_k(q) we first investigate the conjugacy classes of GL_k(q). Two projectivities in PGL_k(q) given in form of matrices A and B are conjugate in PGL_k(q) if and only if there is a matrix R∈ GL_k(q) and α∈ GF(q)^* such that R⋅ B⋅ R^-1=α⋅ A. Whereas the two matrices A and B are conjugate in GL_k(q) if and only if there is a matrix R∈ GL_k(q) such that R⋅ B⋅ R^-1=A. As a consequence each conjugacy class in PGL_k(q) splits into (at most q-1) conjugacy classes in GL_k(q). Let A be a regular k × k-matrix over GF(q). The conjugacy class C_P(A) of the projectivity induced by A consists of all the matrices in the union

∪ _{α∈
GF(q)^*} C_G(α⋅ A)

of conjugacy classes in GL_k(q).

In [7] (but also in many text books on Algebra) the conjugacy classes in GL_k(q) are described by the Jacobi normal forms, which are block diagonal matrices of blocks strongly related to monic polynomials.

Let f=∑_i=0^dκ_ixⁱ, κ_d=1 be a monic polynomial over GF(q), then the companion matrix C(f) of f is given by

C(f): =

⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝

...

−κ₀

...

−κ₁

...

−κ₂

^··_·

...

−κ_d−2

...

−κ_d−1

⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠

For an integer r≥ 1 the hypercompanion matrix H(f^r) of f^r is an rd × rd-matrix given as a block matrix

H(f^r): =

⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝

C(f)

...

E_1d

C(f)

...

E_1d

C(f)

...

^··_·

...

C(f)

...

E_1d

C(f)

⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠

⎫
⎪
⎪
⎪
⎬
⎪
⎪
⎪
⎭

r−times,

where

E_1d:=(e_ij)_{1 ≤ i,j ≤
d} is givenby e_ij=

⎧
⎪
⎨
⎪
⎩

if (i,j)=(1,d)

else.

A complete list of all Jacobi normal forms, i. e. a complete set of representatives of the conjugacy classes in GL_k(q) can be computed in the following way:

Theorem: Let {f₁,...,f_{t_k}} be the set of all monic irreducible polynomials over GF(q) of degree deg(f_i)≤ k which are different from the polynomial f=x. Compute all solutions γ=(γ₁,...,γ_{t_k}) of

t_k
∑
i=1
γ_i⋅ deg(f_i)=k.

For each solution γ determine all possible combinations λ=(λ⁽¹⁾,...,λ^(t_k)) of cycle types λ⁽ⁱ⁾ of length γ_i. From each choice of λ we compute a normal form

N_λ := diag (D(f₁,λ⁽¹⁾),...,D(f_{t_k},λ^(t_k))),

which is a block diagonal matrix of blocks of the form

D(f_i,l⁽ⁱ⁾): = diag(

C(f_i),...,C(f_i)
l⁽ⁱ⁾₁-times
,

H(f_i²),...,H(f_i²)
l⁽ⁱ⁾₂-times
,...,

H(f_i^g_i),...,H(f_i^g_i)
l⁽ⁱ⁾_{g_i}-times
).

For computing the size of a conjugacy class we can use the following method by Kung (cf. [12]):

Theorem: Let f be a monic irreducible polynomial of degree d over GF(q), and let λ be a cycle type of length γ. For 1≤ i≤ γ determine numbers m_i by

m_i := i
∑
j=1
j⋅ λ_j + γ
∑
j=i+1
i⋅ λ_j.

Then the size of the centralizer of D(f,λ) in GL_{d⋅ γ}(q) is given by

b(d,λ) := γ
∏
i=1
λ_i
∏
j=1
(q^d⋅
m_i-q^{d⋅ (m_i-j)}).

This formula proves that the size of the centralizer of D(f,λ) depends only on the degree d and on the cycle type λ, but not on the special choice of the irreducible polynomial.

The number of matrices in the conjugacy class of the normal form in (*) is given by

|C_G(N_λ)|= [q]_k

∏ _i=1^t_kb(deg(f_i),λ⁽ⁱ⁾)
.

In order to write down explicitly the Jacobi normal forms in GL_k(q) it is necessary to know all the monic irreducible polynomials over GF(q) of degree d≤ k. For certain parameters there are complete lists of these polynomials available. Moreover it is possible to compute irreducible polynomials from so called Lyndon words which will be described now. Any given total order of the elements in GF(q) can be used for defining a lexicographic order on GF(q)^d. The cyclic group C_d of order d generated by π := (1,2,...,d) acts on GF(q)^d by a cyclic shift,

v:=(κ₁,...,κ_d)

π
→

π(v): = (κ_d,κ₁, ...,κ_d−1).

A vector v∈ GF(q)^d is called acyclic if its orbit C_d(v) consists of d pairwise different vectors. An acyclic vector v is a Lyndon word if and only if it is the smallest vector in the orbit C_d(v).

Let σ:GF(q^d)→ GF(q^d) be the Frobenius automorphism τ↦ σ(τ) := τ^q. There exist elements β∈ GF(q^d) such that the set

{β,σ(β),..., σ^d-1(β)}

is a basis of GF(q^d) over GF(q), which is called a normal basis of GF(q^d). Then each element τ of GF(q^d) can uniquely be written as

τ= d
∑
i=1
κ_i⋅ β_i, β_i := σ^i-1 (β), κ_i∈ GF(q),

and we can identify τ with its coefficient vector (κ₁,...,κ_d). Applying the Frobenius automorphism to τ is the same as applying the cyclic shift π to its coefficient vector.

A monic irreducible polynomial f of degree d over GF(q) has d different roots in GF(q^d). It is the minimal polynomial of each of its roots over GF(q). If τ∈ GF(q^d) is a root of f then all the other roots, which are called conjugates of τ, are obtained by applying the Frobenius automorphism to τ, i. e. the set of roots is given by

{σⁱ(τ) | 0≤ i≤ d-1}.

Then the minimal polynomial f of τ (and of each of its conjugates) over GF(q) is given by

f= d-1
∏
i=0
(x-σⁱ(τ)).

Using a normal basis of GF(q^d) the coefficient vector of τ (and so the coefficient vector of each root of f) must be an acyclic vector.

The other way round, if τ∈ GF(q^d) has an acyclic coefficient vector with respect to a normal basis over GF(q), then the minimal polynomial over GF(q) of τ is a monic irreducible polynomial of degree d.

Since each monic irreducible polynomial of degree d over GF(q) occurs as a minimal polynomial of certain elements of GF(q^d), we only have to find all elements with an acyclic coefficient vector for determining all irreducible polynomials of degree d over GF(q). The Frobenius automorphism collects d conjugate elements, which are the roots of the same irreducible polynomial over GF(q), and which correspond to one C_d-orbit on the set of acyclic coefficient vectors. So we described a one to one correspondence between the set of all Lyndon words of length d over GF(q) and the set of all monic irreducible polynomials of degree d over GF(q).

In order to find the set of all conjugacy classes in PGL_k(q) we have to determine which conjugacy classes in GL_k(q) must be merged in order to get a conjugacy class in PGL_k(q). So for each normal form N_λ (cf. (*)) and each α∈ GF(q)^* we must determine the normal-form of α⋅ N_λ. For doing this it is enough to determine the normal forms of α⋅ C(f) and α⋅ H(f^r) of monic irreducible polynomials f=∑_i=0^d κ_ixⁱ. It is easy to deduce that these normal forms are given by the companion or hypercompanion matrices C(f_α) and H(f_α^r) of the polynomial

f_α := d
∑
i=0
α^d-iκ_ixⁱ,

which is again a monic and irreducible polynomial of degree d over GF(q). It is irreducible since the roots of f_α are of the form α⋅ τ, where τ is a root of f, so the roots of f_α form a set of d conjugates in GF(q^d).

From each conjugacy class in PGL_k(q) we can choose a representative in form of a matrix, since we know the Jacobi normal-forms, from which we can compute a permutation representation on PG_k-1(q).

Coming back to the description of the algorithm we finally have to investigate the set of all functions f∈ Y^X which fulfill ρ o f o π^-1=f for given permutations π of X and ρ of Y. This set of fixed points Y^X_(ρ,π) can be described in the following way: Choose from each cycle of length ℓ in the cycle decomposition of π one element x; this element must be mapped by f onto an element y which lies in a cycle of length dividing ℓ in the cycle decomposition of ρ. By f o πⁱ(x)=ρⁱ o f(x) the function f is defined on the whole cycle of x. When λ=λ(π) denotes the cycle type of the permutation π, i. e. there are λ_i cycles of length i in the cycle decomposition of π, then

|Y^X_(ρ,π)|= |X|
∏
i=1
|Y_ρⁱ|^λ_i,

where Y_ρⁱ is the set of all fixed points of ρⁱ in Y.

This finishes the description of the algorithm for the random generation of linear codes. It was implemented in the computer algebra system SYMMETRICA [15] for the generation of linear codes over prime fields, i. e. for q is a prime. In order to minimize the amount of work before the algorithm actually starts to generate codes it is useful to start the generation at once after having computed the information on the first conjugacy class, and evaluate further conjugacy classes and their probabilities only if required. This means we have to compute p(C_i) only if the random number (lying in [0,1[) determining which conjugacy class to choose exceeds ∑_j=1^i-1p(C_j).

n k S_nk2 d_2 1 2 3 4 5 6 7 8 9

15 5 62812 7 5.5 31.4 29.6 29.3 4.1 0.1 >0

16 5 160106 8 3.9 24.1 26.8 34.7 9.8 0.7 >0 >0

17 5 401824 8 2.8 18.2 22.8 36.6 16.9 2.7 0.01 >0

18 5 992033 8 1.9 13.8 18.7 35.0 23.7 6.8 0.1 >0

19 5 2.406329 8 1.3 10.0 15.0 31.6 27.9 13.1 1.0 0.02

20 5 5.730955 9 1.0 7.4 11.7 27.2 29.4 19.9 3.4 1.1 .

15 6 350097 6 7.0 42.7 33.2 16.7 0.3 >0

16 6 1.413251 6 4.4 32.1 33.4 27.9 2.1 0.01

17 6 5.708158 7 2.7 23.1 29.7 36.7 7.5 0.2 >0

18 6 22.903161 8 1.8 16.1 24.4 40.2 16.5 1.0 >0 .

19 6 90.699398 8 1.0 11.0 18.6 38.7 26.2 4.4 0.02 .

20 6 352.749035 8 0.7 7.4 13.7 33.6 33.2 11.1 0.3 >0

15 7 901491 5 9.6 57.7 28.0 4.67 >0

16 7 5.985278 6 5.9 44.8 36.0 13.2 0.07 .

17 7 41.175203 6 3.4 31.9 36.9 26.7 1.1 >0

18 7 287.813284 7 2.0 21.6 32.2 38.4 5.8 0.02 .

19 7 2009.864185 8 1.1 13.9 25.2 43.6 15.7 0.4 . .

20 7 13848.061942 8 0.7 8.8 18.2 41.6 27.9 2.8 .

15 8 957357 4 14.8 71.3 13.6 0.3

16 8 10.174566 5 8.8 61.2 27.3 2.7 .

17 8 119.235347 6 5.0 46.3 38.1 10.5 >0 .

18 8 1482.297912 6 2.8 31.6 40.1 24.9 0.5 .

19 8 18884.450721 7 1.5 20.3 34.6 39.3 4.2 >0 .

20 8 240477.821389 8 0.8 12.6 26.1 46.5 13.9 0.1 . .

15 9 428260 4 23.9 73.4 2.6 >0

16 9 6.592538 4 14.6 74.5 10.8 0.1

17 9 123.424635 5 8.2 64.1 26.1 1.5 .

18 9 2647.026212 6 4.5 47.8 39.5 8.2 >0 .

19 9 61154.777955 6 2.4 32.1 42.7 22.5 0.2 .

20 9 1.453217.697135 7 0.8 12.6 26.1 46.5 13.9 0.1 >0 .

15 10 94177 4 36.5 63.4 0.1 .

16 10 1.778699 4 24.0 74.5 1.5 >0

17 10 46.354490 4 8.2 64.2 26.1 1.5

18 10 1564.547344 4 8.0 66.8 24.4 0.8

19 10 62319.506255 5 4.3 49.8 40.0 5.9 >0

20 10 2.702716.939976 6 2.3 33.0 45.2 19.4 >0 .

Distribution (in %) of the minimum distance of binary linear (n,k)-codes.

Finally we want to present some results about the distribution of the minimum distance among binary linear codes of given parameters n and k which were generated uniformly at random using the algorithm above. For each pair of parameters (n,k) we were computing the minimum distance of 500000 codes of length n and dimension ≤ k. The results are collected in table 1. S_nk2 indicates the number of isometry classes of linear (n,k)-codes over GF(2) without 0-columns. Furthermore d₂=d₂(n,k) stands for the maximal value that occurs as the minimum distance of linear (n,k)-codes over GF(2). Tables of d_q(n,k) can be found in [2]. In the right half of table 1 for each d≤ d₂(n,k) the percentage of codes with minimum distance d is indicated. We can deduce that in general the percentage of codes with maximal minimum distance is very small. In some cases indicated with "." in table 1 there was even no code with parameters (n,k,d) produced after having generated 500000 codes.

Acknowledgment: The author wants to thank both Prof. Adalbert Kerber and Prof. Jens Schwaiger for their guidance and support while preparing this article.

harald.fripertinger "at" uni-graz.at, November 17, 2011

Random generation of linear codes