I. Mullayeva
On the weight structure of cyclic codes over GF (q) , q > 2 .
Abstract
The interrelation between the cyclic structure of an ideal, i.e.,
a cyclic code over Galois field GF (q) , q > 2 , and its classes of
proportional elements is considered. This relation is used in order
to define the code’s weight structure. The equidistance conditions
of irreducible nonprimitive codes over GF(q) are given. Besides
that, the minimum distance for some class of nonprimitive cyclic
codes is found.
The relation of proportionality for elements of algebra An , consisting
of polynomials in x over Galois field GF (q) , modulo polynomial xn − 1 ,
is the equivalence relation [1]. Therefore An falls into several disjoint sub-
sets and every such subset contains all elements which are proportional
to each other. These subsets will be called the classes of proportionality.
Let z(x) 6= 0 be some vector of An . If α1 = 1, α2, . . . , αq−1 are all dif-
ferent elements of the multiplicative group GF (q)∗ of the field GF (q) ,
then the following q − 1 vectors
α1z(x), α2z(x), . . . , αq−1z(x) (1)
are some different and proportional to each other elements of An . The set
of vectors (1) is closed under the multiplication by the elements of the
group GF (q)∗ . Hence the set (1) represents some class of proportional
elements, which will be denoted by Pz(x) . Because of an arbitrary choice
for z(x) , every nonzero class consists of q− 1 elements of the form (1) .
Consequently An contains (q
n − 1)/(q − 1) different nonzero classes.
Evidently all elements of one class have the same period [2, 3] or the
same order [8]. Clearly, the supporting sets [2] of vectors, entering into
the same class of proportionality, are similar too. Hence, the Hamming
weight is also the same for all vectors of one class. Thus, we can say that
any proportionality class Pz(x) , Pz(x) ⊂ An , has its order, its supporting
set and its Hamming weight. Obviously, any proportionality class of An
is characterizied by its unique monic polynomial.
Now consider an ideal J , J ⊂ An , i.e., some cyclic code over GF (q) ,
having the following generator g(x) = (xn − 1)/h(x) [7], where h(x) is
some parity-check polynomial of degree m , having some order n , n =
ord(h(x)) [8]. Below we suppose that q > 2 and gcd(n, q) = 1 .
It’s also known [3, 4, 10] that any ideal is partitioned into several
disjoint subsets, that is cycles, under the multiplication of ideal’s vectors
http://arxiv.org/abs/0704.1091v1
by x . On the other hand, some ideal J , as a subspace of An , consists of
(qm−1)/(q−1) nonzero proportionality classes. Obviously, the existence
of two different partitions into some disjoint subsets of any ideal assumes
a certain dependence between proportionality classes and cycles of ideal.
Further, any ideal J ⊂ An is the direct sum of minimal ideals [2, 8]
Ji, (2)
where Ji is some minimal ideal, having an irreducible parity-check poly-
nomial hi(x) of degree mi and of order ni , ni = ord(hi(x)) , 1 ≤ i ≤ t .
This implies that the following polynomial
h(x) =
hi(x), (3)
is the parity-check polynomial of J and n , n = lcm(n1, n2, . . . , nt) ,
is the order of h(x) [8]. It should be stressed that under the condition
gcd(n, q) = 1 the polynomial (3) has no repeated factors [8].
Remark 1 . It is worth mentioning that the number n can be some
number of either the primitive form n = qm − 1 or of the nonprimitive
form n 6= qm−1 . In the first case, we have some cyclic primitive code and
the second case corresponds to a certain cyclic nonprimitive code [11].
Let us stress that n 6= qm − 1 if and only if ni 6= q
mi − 1 , 1 ≤ i ≤ t .
But if there is at least one primitive polynomial among the polynomials
hi(x) , 1 ≤ i ≤ t , then n = q
m − 1 .
Furthermore, applying the theory of linear recurring sequences [8, 12]
to elements of an ideal, we obtain that every element of some ideal J ⊂
An is characterized by its unique minimal polynomial. Denote by C the
set of all elements of J , having the same minimal polynomial c(x) . The
set C is either some minimal ideal Ji , 1 ≤ i ≤ t , or a certain subset of
all such elements of J , whose characteristic polynomial of the smallest
degree coincides with c(x) . In the general case, the polynomial c(x) is
equal to the product of some k , 1 ≤ k ≤ t , polynomials from t different
prime divisors of h(x) . Thus,
c(x) =
hij (x), 1 ≤ k ≤ t. (4)
This means that any element of C has the same period or the same order
nc = ord(c(x)) , nc ≤ n , nc|n .
Lemma 1 . For the set C , C ⊂ J , having some minimal polynomi-
al c(x) in terms of (4) , the following equality takes place
nc · sc = Rc · (q − 1), (5)
where sc is the number of all cycles, and Rc is the number of all pro-
portionality classes of C .
Proof. The set C is closed under two different operations. The first
operation is the cyclic shift of vector and the second one is the multipli-
cation of vectors by elements of group GF (q)∗ . Hence equality (5) can
be obtained by the counting of the number of all elements, belonging to
C , via the two different ways. The lemma is proved.
Theorem 1 . Any cycle {z(x)} of ideal (2) , having some period nz ,
nz|n , consists of dz subsets. The first element of each such subset is
proportional to z(x) . Every such subset contains rz nonproportional to
each other vectors, i.e., nz = rz · dz , dz|(q − 1) . And the number rz is
the index of the subgroup, belonging to GF (q)∗ , of order dz in the group
of the roots of unity, having the least possible order.
Proof. Let rz , 1 ≤ rz ≤ nz , is the smallest natural number such
that the following equality holds
xrz · z(x) = α · z(x)mod(xnz − 1), (6)
where α is some element of GF (q)∗ . Then the following rz vectors of
cycle {z(x)}
z(x), x · z(x), ..., xr
−1 · z(x) (7)
are some non–proportional to each others vectors because, assuming the
inverse, we should be able to decrease the number rz , but it is impossible.
Hence the set of elements (7) belongs to the following rz classes of
proportionality
Pz(x), Pxz(x), . . . , ..., Pxrz−1z(x). (8)
Since xnzz(x) = z(x) in the ring An and also, considering (6) , we
see that Pz(x) = Pxrz z(x) = Pxnz z(x) . This means that the cycle {z(x)}
belongs to the classes (8) and every such class contains dz vectors,
dz = nz/rz , 1 < dz ≤ q − 1 . In terms of equality (6) the following
different vectors z(x), xrzz(x), x2rzz(x), . . . , x(dz−1)rzz(x) of class Pz(x)
can be represented as α0z(x), αz(x), . . . , αdz−1z(x) . This implies that
α0 = 1, α, α2, . . . , αdz−1 are the different elements of group GF (q)∗ .
Since xnzz(x) = xrzdzz(x) = αdzz(x) = z(x) , we see that αdz = 1 .
This yields that dz is the order of element α in GF (q)
∗ . Consequently,
dz|q − 1 , 1 ≤ dz ≤ q − 1 .
Finally, under the condition gcd(n, q) = 1 the polynomial xn − 1
has n different roots in GF (qh) field, where h is the multiplicative or-
der of q modulo n [8]. Denote by E(n) the multiplicative group of n - th
roots of unity over GF (q) . Let ξ ∈ E(n) be some n - th primitive root of
unity. Then the following set of elements ξ0 = 1, ξ, ξ2, . . . , ξnz−1, . . . , ξn−1
represents the group E(n) . Since nz|n , we have E(nz) ⊂ E(n) , where
E(nz) is the multiplicative group of nz -th roots of unity. Moreover,
taking into account the isomorphism of the groups, having the same or-
der [9], we can state that the subgroup {α} , {α} ⊂ GF (q)∗ , of order dz
belongs to E(nz) because dz|nz .
As mentioned above, nz is the period of z(x) , so that nz is the small-
est divisor of n such that the following congruence xrz ≡ αmod(xnz −1)
takes place. Hence E(nz) is the smallest group of n - th roots of uni-
ty, which contains {α} . Since α = ξrz , we see that the following el-
ements ξrzdz = 1, ξrz , ξ2rz , . . . , ξ(dz−1)rz represent the subgroup {α} in
the group E(nz) . Besides that, the decomposition of E(nz) relative to
the subgroup {α} consists of rz different cosets. Thus, the number rz
is the index of subgroup {α} in the group of roots of unity, having the
smallest possible order. The theorem is proved.
Remark 2 . Notice that when a parity-check polynomial of code is
some primitive polynomial of degree m and of order n = qm−1 , m > 1 ,
then r = R = (qm − 1)/(q − 1) and d = q − 1 . (see [2], [7]).
Corrollary 1 . The period nz , nz = rz·dz ,of element z(x) , z(x) ∈ J ,
equals dz , dz|(q − 1) , 1 ≤ dz ≤ (q − 1) ,if and only if the cycle {z(x)}
is contained in one class of proportionality.
Corollary 2 . All code words of any cyclic code, havinq some length
n over GF (q) , fall into some equal-weight subsets and every such subset
includes all proportional to each other cycles.
Besides that, consider some minimal ideal J , J ⊂ An , having an
irreducible nonprimitive parity-check polynomial h(x) of degree m and
of order n , n 6= qm−1 , i.e., some irreducible code of nonprimitive length.
Remark 3 . The degree m of the polynomial h(x) coincides with
the multiplicative order h of the number q modulo n [8]. Also, the order
n of the polynomial h(x) is some divisor of qh−1 . This means that the
order n can change in the following limits 1 < n < qh−1 , n 6= q − 1 . If
1 < n < q − 1 , i.e., n 6= q − 1 , then some minimal ideal J , J ⊂ An , of
dimention one contains only one nonzero class of proportyonality. Con-
sequently, n = d , 1 < d < q − 1 , d|q − 1 .
Theorem 2 . Any cycle of minimal ideal J , J ⊂ An , having some
parity-check polynomial h(x) of degree m , m > 1 , and of order n ,
n 6= qm − 1 , is contained in r proportionality classes, 1 ≤ r ≤ R , r|R ,
R = (qm − 1)/(q − 1) . Every such class consists of d , 1 ≤ d ≤ (q − 1) ,
different vectors of cycle, and
d = gcd(q − 1, n), r = n/d. (9)
Proof. All elements of minimal ideal J , J ⊂ An , have the same order
n , n = ord(h(x)) . Applying the theorem 1 to some element f(x) ,
f(x) ∈ J , we have n = rf ·df , df |(q−1) , 1 ≤ rf ≤ n , 1 ≤ df ≤ (q−1) ,
and also the following equality
xrf · f(x) = γ · f(x), (10)
where γ is some element of GF (q)∗ . Evidently, if either rf = 1 , i.e.,
df = n , or rf = n and df = 1 , then equalities (9) take place. Hence,
below we suppose that 1 < rf < n , 1 < df < q − 1 , and therefore
q − 1 < n < qm − 1 .
Taking into account (9) , we have df ≤ d . Let us show that the strong
unequality df < d is impossible. Indeed, if df < d , then the subgroup
{γ} , where γ is the element from equality (10) , belongs to some group
of n -th roots of unity, having the order d , because df |d . Since d|(q−1) ,
we see that the subgroup {γ} belongs to GF (q)∗ . This means that the
cycle {f(x)} is contained in one class of proportionality, i. e., rf = 1 .
But this fact contradicts to the condition rf > 1 . This implies that the
strong unequality df < d is impossible. Hence df = d . Because of an
arbitrary choice of f(x) we can conclude that equalities (9) take place
for any element of J . The theorem is proved [6].
Remark 4 . It is necessary to note that the theorem 2 is valid only
for irreducible codes of non–primitive length except Reed-Solomon codes
of length n = q − 1 as it was shown above. In the case of irreducible
codes of primitive length n , n = qm− 1 , m > 1 , the theorem 2 will be
valid if and only if gcd(m, q − 1) = 1 . Indeed, when the last condition
takes place, then gcd((qm − 1)/(q − 1), q − 1) = 1 [7]. Thus, d = q −
1 = gcd(qm − 1, q − 1) that is d = gcd(n, q − 1) . It follows that the
theorem 2 holds.
Remark 5 . Notice that under the condition gcd(m, q − 1) = 1 the
number r from (9) has no divisors of (q−1) except 1 , so gcd(r, q − 1) = 1 .
This means that gcd(r, d) = 1 . Hence, considering the fact that r|R and
also, taking into account (9) and the following equality s = R(q−1)/n ,
we have r = gcd(R, n) . Besides that, if either one from the two numbers
n and q− 1 does not contain multiple prime divisors or the same prime
divisors of these numbers have the same degrees under the decomposi-
tion of both n and q − 1 , then the following equalities r = gcd(R, n) ,
gcd(r, d) = 1 also take place.
Corollary 3 . Both the number r and the number d are the same
numbers of all irreducible divisors of polynomial xn − 1 over GF (q) ,
having the same order.
Corollary 4 . The number R , R = (qm−1)/(q−1) , of proportional-
ity classes, of some irreducible code K ,having some length n , n 6= (qm−
1) , n = d · r , over GF (q) field, consists of some v different subsets.
And every such subset contains r equal-weight proportionality classes,
i.e., R = v · r . Besides that, every subset includes b equal-weight cycles,
b = (q − 1)/d , 1 < b ≤ (q − 1) . So that the number of all cycles for K
equals s = v · b and gcd(r, b) = 1 .
Proof. According to the theorem 2 any cycle of code K is contained
in r , r|R , proportionality classes. Therefore the number v = R/r gives
us the common quantity of different subsets of J , each of which consists
of r classes, i.e., R = v · r . The number b , b = (q−1)/d , is the number
of all different equal-weight cycles, contained in every such subset, which
consists of some r classes. Hence the number of all cycles for K is equal
to s = v · b . Since d = gcd(q− 1, n) we see that gcd(r, b) = 1 . Actually,
assuming the inverse, we would have been able to decrease the number
d , but it’s impossible. The corollary is proved.
Corollary 5 . The irreducible nonprimitive code K is some equidis-
tant code if s = b .Besides that, the last equation is equivalent to the
following ones: r = R or gcd(s, R) = 1 .
Remark 6 . Note that the condition s = b was obtained in [14, 15],
but only for some subclass of irreducible nonprimitive codes and under
the following additional restriction gcd(b,m) = 1 .
Corollary 6 . The weight of any element, belonging to some irre-
ducible nonprimitive code K of length n over GF (q) , is multiple of the
number d , d = gcd(q − 1, n) .
Proof. The weight of any element z(x) , z(x) ∈ K , of order n ,
n = ord(h(x)) , is equal to the number of such j , 0 ≤ j ≤ n − 1 , for
which the polynomial xj · z(x) has the following degree n−1 . According
to the theorem 2 , the number of such polynomials for the cycle z(x) ,
having degree n − 1 , is equal to wr · d , where wr is the number of
polynomials, having degree n − 1 , among the first r cyclic shifts of
z(x) , and d = gcd(q − 1, n) . The corollary is proved.
In addition, consider some ideal J , J ⊂ An , of the form (2) , having
the parity-check polynomial h(x) in terms of (3) .
Theorem 3 .If the following condition gcd(h, q− 1) = 1 , where h is
the multiplicative order of number q mod n , takes place, then any cycle
of set C , C ⊂ J , having some minimal polynomial of the form (4) ,
is contained in rc proportionality classes, rc|Rc , and every such class
includes dc , dc|q − 1 , elements of cycle, that is nc = rc · dc , nc =
ord(c(x)) , where Rc is the number of all proportionality classes of set
C , and
rc = gcd(Rc, nc), dc = gcd(q − 1, nc). (11)
Proof. It is sufficient to consider the case k = 2 because the general case
can be obtained by the induction. Thus assume that c(x) = h1(x)·h2(x) ,
where hi(x) is of degree mi and of order ni , ni = q
mi − 1 , 1 ≤ i ≤ 2 ,
is a certain prime miltiplier of c(x) . It is known [8], that the number
mi , 1 ≤ i ≤ 2 , equals either h or some divisor of this number. Hence,
taking into account the theorem 2 , and also remarks 4 and 5 , we have
ni = ri ·di , where ri = gcd(Ri, ni) , di = gcd(q−1, ni) , gcd(ri, q−1) = 1 ,
1 ≤ ri ≤ Ri , 1 ≤ di ≤ q − 1 , and Ri = (q
mi − 1)/(q − 1) , where Ri is
the number of all proportionality classes of minimal ideal Ji , 1 ≤ i ≤ 2 .
Therefore the order nc , nc = lcm(n1, n2) = n1 · n2/gcd(n1, n2) of the
polynomial c(x) can be rewritten as
nc = r1 d1 · r2 d2/gcd(r1d1 · r2d2). (12)
Since gcd(ri, q − 1) = 1 , we have gcd(ri, d1 · d2) = 1 , 1 ≤ i ≤ 2 . Thus
gcd(r1r2, d1d2) = 1 . Hence gcd(gcd(r1, r2), gcd(d1, d2)) = 1 so that (12)
may be represented in the following form
nc = (r1 r2/gcd(r1, r2)) · (d1 d2/gcd(d1, d2)). (13)
Thus, nc = lcm(r1, r2) · lcm(d1, d2) . Now by rc and dc we denote
lcm(r1, r2) and lcm(d1, d2) , respectively. Thus nc = rc·dc and gcd(rc, dc) =
1 . Since dc|q− 1 and gcd(rc, q− 1) = 1 , we obtain dc = gcd(q− 1, nc) .
Considering (5) , it follows that nc|(Rc · (q − 1)) . Hence we have rc =
gcd(Rc, nc) . Consequently the order nc of any element of set C is equal
to the product of two relatively prime numbers, i.e., nc = rc · dc , where
rc = lcm(r1, r2) = gcd(Rc, nc) and dc = lcm(d1, d2) = gcd(q − 1, nc) .
Furthermore, applying the theorem 1 to some element a(x) ∈ C of
period nc = ra · da , we have
xra · a(x) = θa(x), (14)
where θ ∈ GF (q)∗ is some element of order da , and ra is the smallest
natural number such that equality (14) takes place. Notice that the
subgroup {θ} has the order da , da < dc . If dc = 1 , then da = 1 and
nc = ra = rc = gcd(Rc, nc) , so that equalities (11) hold. For this reason
below we suppose that dc > 1 . If under this condition the number rc
is equal to one, then nc = dc= gcd(q − 1, nc) and the theorem is valid.
Therefore below we suppose that both rc > 1 and dc > 1 .
Evidently, da ≤ dc . Now let us show that the inequality da < dc is
not possible. Indeed, if da < dc , then we come to the following conclusion.
The subgroup {θ} , where θ is the element from equality (14) , belongs
to some subgroup of GF (q)∗ , having the order dc , because da|dc . Since
dc is some divisor of nc , then, considering the uniqueness of subgroups,
having the same order, the subgroup {θ} belongs to some group of dc -
th roots of unity. This implies that the smallest group of roots of unit,
containing {θ} , has an order, which either less or equals dc . Thus, both
the period of a(x) and the order of c(x) must be either less or equal to
dc . This yields that the order of c(x) must be some divisor of q−1 . But
this fact contradicts the condition rc > 1 . Hence the inequality da < dc
is impossible so that da = dc and ra = rc . Because of an arbitrary choice
of a(x) equalities (11) take place for any element of set C . The theorem
is proved.
Corollary 7 . The order nc of reducible factor c(x) of polynomial
xn − 1 , having some degree m over GF (q) , is some divisor of num-
ber qm − 1 , if gcd(h, q − 1) = 1 , where h is the multiplicative order of
number q mod n .
Remark 7 . In terms of condition gcd(h, q − 1) = 1 , where h is the
multiplicative order of number q mod n , the theorem 3 is valid for
cyclic codes of both the primitive and the nonprimitive length. Also,
taking into consideration the remark 5 , the order of any reducible factor
of the polynomial (xn − 1) over GF (q) of degree m , is some divisor of
the number (qm − 1) , if gcd (h, q − 1) = 1 .
Theorem 4 . Any cycle of set C , C ⊂ J , having some minimal
polynomial c(x) of the type (4) and of order nc = lcm(n1, n2, . . . , nk) ,
where ni 6= q
mi − 1 , 1 ≤ i ≤ k , is contained in rc , rc|Rc , 1 ≤ rc ≤ Rc ,
classes of proportionality and every such class includes dc , 1 ≤ dc ≤
q − 1 , elements of cycle, where Rc is the number of all proportionality
classes of C , and
dc = gcd(q − 1, nc), rc = nc/dc. (15)
Proof. It is sufficient to assume that k = 2 because the general case can
be obtained by the induction. This implies that c(x) = h1(x)h2(x) , where
hi(x) is some prime divisor of equality (3) , having some degree mi , and
of order ni , ni 6= q
mi − 1 , 1 ≤ i ≤ 2 . This yields that the theorem 2
holds for the minimal ideal Ji , 1 ≤ i ≤ 2 .
Evidently, if one of the two numbers, i.e., either dc or rc is equal
to one, then equalities (15) hold. For this reason below we assume that
both rc > 1 and dc > 1 .
Let z(x) be some vector of set C . According to the theorem 1 some
cycle {z(x)} ⊂ C is contained in rz classes and every such class includes
dz different elements of this cycle. Thus nc = rz dz , 1 ≤ dz ≤ q − 1 ,
dz|q−1 , 1 ≤ rz ≤ nc . And in addition, the following equality takes place
xrz · z(x) = β z(x), (16)
where β is some element of GF (q)∗ and the subgroup {β} , {β} ⊂
GF (q)∗ , has the order dz . Evidently, dz ≤ dc . Let us show that the
number dz can not be smaller than dc . Assume the inverse, i.e. let dz
be less than dc . Since at least one of the two numbers ether r1 or r2 is
not equal to one, we see that at least one of the numbers ni , 1 ≤ i ≤ 2 ,
is more than q−1 , as was established in the theorem 2. This means that
nc = lcm(n1, n2) > (q − 1). (17)
Further, since dz|dc , we see that the subgroup {β} of order dz belongs to
some subgroup of GF (q)∗ , having the order dc , where β is the element
from equality (16) . Due to the uniqueness of groups, having the same
order, the subgroup {β} belongs to the group of dc -th roots of unity
because dc|nc . It follows that the smallest group of the roots of unity,
which contains the subgroup {β} , has the order less or equals to dc .
This implies that both the period of z(x) and the order of c(x) is some
divisor of q − 1 . But this fact contradicts to (17) . It follows that our
assumption is not true, so that dz = dc , and rz = rc .
Besides that, since the number dc is the same number for every cycle
of set C , we see that every subset, consisting of rc proportionality class-
es, contains the same number of cycles, which is equal to bc = q − 1/dc .
Moreover, since dc = gcd(q − 1, nc) , we obtain gcd(bc, rc) = 1 . Hence,
taking into account the following equality sc = Rc(q − 1)/nc , which fol-
lows from (5) , we see that rc is some divisor of Rc and sc = vcbc , where
vc is equal to Rc/rc . The theorem is proved.
Corollary 7 . (Equidistance signs of the subset C , C ⊂ J , having
some minimal polynomial of the form (4) .)
All vectors of the subset C , C ⊂ J , having some minimal polynomial
c(x) of order nc = lcm(n1, n2, ..., nk) , ni 6= q
mi − 1 , 1 ≤ i ≤ k , k > 1 ,
have the same weight if at least one of the following conditions holds: 1.
sc = bc , 1 < bc ≤ q − 1 , 2. rc = Rc , 3. gcd(sc, Rc) = 1 .
Corollary 8 . The order of the reducible factor c(x) of the polynomial
xn−1 over GF (q) , having some degree m , is some divisor of the number
qm− 1 , if the decomposition of the polynomial c(x) into prime multiples
does not contain any primitive polynomial.
Remark 8 . Note that corollaries (6) and (8) show us in what cases
corollary 3.4 from [8] takes place for some reducible polynomial of the
degree m over GF (q) .
Also, consider some cyclic code, having the following parity-check
polynomial
h(x) =
hi(x), (18)
where hi(x) is an irreducible polynomial over GF (q) , q > 2 , of degree
mi and of order ni = (q
mi − 1)/bi , bi|q − 1 , 1 ≤ bi ≤ q − 1 , 1 ≤ i ≤ t ,
gcd(mi, mj) = 1 and gcd(bi, bj) = 1 , provided i 6= j , 1 ≤ i, j ≤ t , so
that the order n of h(x) equals n = lcm(n1, n2, ..., nt) .
It is worth mentioning that in [14] and [15] the following cases of
polynomial (18) have been considered. Namely t = 1 and t = 2 , and
besides that, with some additional restrictions, which can be omitted.
Also, some particular case of polynomial (18) , that is provided bi = 1
for all i , 1 ≤ i ≤ t , was obtained in [16]. But there are some unnecessary
restrictions in this paper too. Also, there are some mistakes in that paper.
Namely, the order of the product for some two polynomials from (18)
was defined incorrectly in [16].
Finally, using the results obtained above, we have found the minimal
distance of code, having the parity-check polynomial (18) , (see [17]).
Denote by M the set of degrees for the polynomials hi(x) , 1 ≤ i ≤ t ,
from the eq. (18) that is M = (m1, m2, ..., mt) . Let the number m
denote the degree of polynomial h(x) , i. e., m = m1+m2+ ...+mt . By
Mj,k , 1 ≤ j ≤ C
t , 1 ≤ k ≤ t − 1 , denote j
,s k -subset of M , where
Ckt is the binomial coefficient.
Thus Mj,k = (mj1, mj2 , ..., mjk) , 1 ≤ j ≤ C
t , 1 ≤ k ≤ t − 1 . At
last, denote by mj,k the sum of degrees, from the subset Mj,k , so that
mj,k = mj1 +mj2 + ... +mjk , 1 ≤ j ≤ C
t , 1 ≤ k ≤ t− 1 . It is obvious
that 1 ≤ mjk < m . Let us remark that provided k = 1 the number
mj,k = mj,1 = mj and 1 ≤ j ≤ t because C
t = t .
Theorem 5 .The minimal distance of code, having the parity-check
polynomial (18) , has the following form
dmin = q
m−1 −
qmj,1−1 −−
qmj,2−1 − ...−−
qmj,t−1−1, t ≥ 2,
dmin = q
m−1(q − 1)/b, t = 1, 1 ≤ b ≤ q − 1,
dmin = q
m−1(q − 1), t = 1, b = 1.
In conclusion I should like to express my sincere gratitude to L.A.Bassaligo,
M.I. Boguslavskii and E.T. Akhmedov for helping me to correct some
mistakes in the original version of my paper.
References
[1] Van der Waerden B.L. Algebra, vol. 1 , 1976 .
[2] Macwilliams F. J., Sloane N. J. A. The theory of error-correcting
codes, North-Holland, Amsterdam, Sixth Printing, 1988 .
[3] Nili H. Matrixschaltungen zur codierung und decodierung von Grup-
pen codes, Archiv der elektrishen ubertragung, Band 18 , Het. 9 ,
1964 , S. 555− 564 .
[4] Macwilliams F.J. The structure and properties of binary cyclic al-
phabets, Bell System Tech. J., 44 , 303− 332 , 1965 .
[5] Mullayeva Iren I. Dependence between cyclic structure of ide-
al J , J ⊂ An and proportionality classes of algebra An =
GF (q)[x]/(Xn−1) , AZNIINTI, Deposited scient. works, N 1(5) , p.
15 , Baku, Azerb., 1994 .
[6] Mullayeva I.I. Interdependence between cyclic and weight structure
of codes over GF(q) and its classes of proportyonality. RAS, Prob-
lems of Information Transmition, v. 41 , No. 2 , 2005 .
[7] Peterson W. W., Weldon E.J. Error - correcting codes, 2 nd, ed.,
M.I.T. Press, Cambridge, Mass., 1972 .
[8] Lidl R., Niderreiter H. Finite fields, Addison-Wesley Publ. Com.,
Massachusetts, 1983 .
[9] Kurosch. Higher algebra, 1962 .
[10] Elspas B. The theory of autonomous linear sequential networks, IRE
Transactions on circuit theory, CT- 6 , N 1 , March ( 1959 ), 45−60 .
[11] Richard E. Blahut. Theory and practice of error control codes,
Addison-Wesley Publ. Com., Massachusetts, 1984 .
[12] Zierler N. Linear recurring sequences, J. Soc. Ind. Appl. Math., 7
( 1959 ), N 1 , 45− 60 .
[13] Oganesyan S., Tairyan V., Yagdzyan V. Decomposition of cyclic
codes into equel-weight classes, Probl. of Control and Inform. Th.,
3 ( 1974 ), N 2 , 117− 125 .
[14] Clark W. E. Equidistant cyclic codes over GF(q), Discrete Math.,
17 ( 1977 ), N 2 , 139− 141 .
[15] Oganesyan S.,Yagdzyan V., Tairyan V. On a class of optimal cyclic
codes, Proc. 2 nd Int. Symp. on Inform. Theory, Tsahkadzor, Arme-
nia, USSR, 1971 , Budapest: Acad. Kiado, 1973 , 219− 224 .
[16] Tenengolts G. M. A new class of cyclic error-corecting codes, Proc.
3 nd Confr. on Coding and Transm. Inform., Soviet Un., Ugegorod,
1967 , 18− 28 .
[17] Mullayeva Iren I. Equidistance criterion of cyclic subset for ideal J ,
of algebra An = GF (q)[x]/(x
n−1) , consisting of polynomials mod-
ulo xn − 1 over Galois field GF (q) , q > 2 , AZNIINTI, Deposited
scient. works, N2(6) , p. 16 , Baku, Azerbaijan, 1994 .

  The interrelation between the cyclic structure of an ideal, i.e., a cyclic
code over Galois field $GF(q)$, $q>2$, and its classes of proportional elements
is considered. This relation is used in order to define the code's weight
structure. The equidistance conditions of irreducible nonprimitive codes over
GF(q) are given. Besides that, the minimum distance for some class of
nonprimitive cyclic codes is found.

I. Mullayeva
On the weight structure of cyclic codes over GF (q) , q > 2 .
Abstract
The interrelation between the cyclic structure of an ideal, i.e.,
a cyclic code over Galois field GF (q) , q > 2 , and its classes of
proportional elements is considered. This relation is used in order
to define the code’s weight structure. The equidistance conditions
of irreducible nonprimitive codes over GF(q) are given. Besides
that, the minimum distance for some class of nonprimitive cyclic
codes is found.
The relation of proportionality for elements of algebra An , consisting
of polynomials in x over Galois field GF (q) , modulo polynomial xn − 1 ,
is the equivalence relation [1]. Therefore An falls into several disjoint sub-
sets and every such subset contains all elements which are proportional
to each other. These subsets will be called the classes of proportionality.
Let z(x) 6= 0 be some vector of An . If α1 = 1, α2, . . . , αq−1 are all dif-
ferent elements of the multiplicative group GF (q)∗ of the field GF (q) ,
then the following q − 1 vectors
α1z(x), α2z(x), . . . , αq−1z(x) (1)
are some different and proportional to each other elements of An . The set
of vectors (1) is closed under the multiplication by the elements of the
group GF (q)∗ . Hence the set (1) represents some class of proportional
elements, which will be denoted by Pz(x) . Because of an arbitrary choice
for z(x) , every nonzero class consists of q− 1 elements of the form (1) .
Consequently An contains (q
n − 1)/(q − 1) different nonzero classes.
Evidently all elements of one class have the same period [2, 3] or the
same order [8]. Clearly, the supporting sets [2] of vectors, entering into
the same class of proportionality, are similar too. Hence, the Hamming
weight is also the same for all vectors of one class. Thus, we can say that
any proportionality class Pz(x) , Pz(x) ⊂ An , has its order, its supporting
set and its Hamming weight. Obviously, any proportionality class of An
is characterizied by its unique monic polynomial.
Now consider an ideal J , J ⊂ An , i.e., some cyclic code over GF (q) ,
having the following generator g(x) = (xn − 1)/h(x) [7], where h(x) is
some parity-check polynomial of degree m , having some order n , n =
ord(h(x)) [8]. Below we suppose that q > 2 and gcd(n, q) = 1 .
It’s also known [3, 4, 10] that any ideal is partitioned into several
disjoint subsets, that is cycles, under the multiplication of ideal’s vectors
http://arxiv.org/abs/0704.1091v1
by x . On the other hand, some ideal J , as a subspace of An , consists of
(qm−1)/(q−1) nonzero proportionality classes. Obviously, the existence
of two different partitions into some disjoint subsets of any ideal assumes
a certain dependence between proportionality classes and cycles of ideal.
Further, any ideal J ⊂ An is the direct sum of minimal ideals [2, 8]
Ji, (2)
where Ji is some minimal ideal, having an irreducible parity-check poly-
nomial hi(x) of degree mi and of order ni , ni = ord(hi(x)) , 1 ≤ i ≤ t .
This implies that the following polynomial
h(x) =
hi(x), (3)
is the parity-check polynomial of J and n , n = lcm(n1, n2, . . . , nt) ,
is the order of h(x) [8]. It should be stressed that under the condition
gcd(n, q) = 1 the polynomial (3) has no repeated factors [8].
Remark 1 . It is worth mentioning that the number n can be some
number of either the primitive form n = qm − 1 or of the nonprimitive
form n 6= qm−1 . In the first case, we have some cyclic primitive code and
the second case corresponds to a certain cyclic nonprimitive code [11].
Let us stress that n 6= qm − 1 if and only if ni 6= q
mi − 1 , 1 ≤ i ≤ t .
But if there is at least one primitive polynomial among the polynomials
hi(x) , 1 ≤ i ≤ t , then n = q
m − 1 .
Furthermore, applying the theory of linear recurring sequences [8, 12]
to elements of an ideal, we obtain that every element of some ideal J ⊂
An is characterized by its unique minimal polynomial. Denote by C the
set of all elements of J , having the same minimal polynomial c(x) . The
set C is either some minimal ideal Ji , 1 ≤ i ≤ t , or a certain subset of
all such elements of J , whose characteristic polynomial of the smallest
degree coincides with c(x) . In the general case, the polynomial c(x) is
equal to the product of some k , 1 ≤ k ≤ t , polynomials from t different
prime divisors of h(x) . Thus,
c(x) =
hij (x), 1 ≤ k ≤ t. (4)
This means that any element of C has the same period or the same order
nc = ord(c(x)) , nc ≤ n , nc|n .
Lemma 1 . For the set C , C ⊂ J , having some minimal polynomi-
al c(x) in terms of (4) , the following equality takes place
nc · sc = Rc · (q − 1), (5)
where sc is the number of all cycles, and Rc is the number of all pro-
portionality classes of C .
Proof. The set C is closed under two different operations. The first
operation is the cyclic shift of vector and the second one is the multipli-
cation of vectors by elements of group GF (q)∗ . Hence equality (5) can
be obtained by the counting of the number of all elements, belonging to
C , via the two different ways. The lemma is proved.
Theorem 1 . Any cycle {z(x)} of ideal (2) , having some period nz ,
nz|n , consists of dz subsets. The first element of each such subset is
proportional to z(x) . Every such subset contains rz nonproportional to
each other vectors, i.e., nz = rz · dz , dz|(q − 1) . And the number rz is
the index of the subgroup, belonging to GF (q)∗ , of order dz in the group
of the roots of unity, having the least possible order.
Proof. Let rz , 1 ≤ rz ≤ nz , is the smallest natural number such
that the following equality holds
xrz · z(x) = α · z(x)mod(xnz − 1), (6)
where α is some element of GF (q)∗ . Then the following rz vectors of
cycle {z(x)}
z(x), x · z(x), ..., xr
−1 · z(x) (7)
are some non–proportional to each others vectors because, assuming the
inverse, we should be able to decrease the number rz , but it is impossible.
Hence the set of elements (7) belongs to the following rz classes of
proportionality
Pz(x), Pxz(x), . . . , ..., Pxrz−1z(x). (8)
Since xnzz(x) = z(x) in the ring An and also, considering (6) , we
see that Pz(x) = Pxrz z(x) = Pxnz z(x) . This means that the cycle {z(x)}
belongs to the classes (8) and every such class contains dz vectors,
dz = nz/rz , 1 < dz ≤ q − 1 . In terms of equality (6) the following
different vectors z(x), xrzz(x), x2rzz(x), . . . , x(dz−1)rzz(x) of class Pz(x)
can be represented as α0z(x), αz(x), . . . , αdz−1z(x) . This implies that
α0 = 1, α, α2, . . . , αdz−1 are the different elements of group GF (q)∗ .
Since xnzz(x) = xrzdzz(x) = αdzz(x) = z(x) , we see that αdz = 1 .
This yields that dz is the order of element α in GF (q)
∗ . Consequently,
dz|q − 1 , 1 ≤ dz ≤ q − 1 .
Finally, under the condition gcd(n, q) = 1 the polynomial xn − 1
has n different roots in GF (qh) field, where h is the multiplicative or-
der of q modulo n [8]. Denote by E(n) the multiplicative group of n - th
roots of unity over GF (q) . Let ξ ∈ E(n) be some n - th primitive root of
unity. Then the following set of elements ξ0 = 1, ξ, ξ2, . . . , ξnz−1, . . . , ξn−1
represents the group E(n) . Since nz|n , we have E(nz) ⊂ E(n) , where
E(nz) is the multiplicative group of nz -th roots of unity. Moreover,
taking into account the isomorphism of the groups, having the same or-
der [9], we can state that the subgroup {α} , {α} ⊂ GF (q)∗ , of order dz
belongs to E(nz) because dz|nz .
As mentioned above, nz is the period of z(x) , so that nz is the small-
est divisor of n such that the following congruence xrz ≡ αmod(xnz −1)
takes place. Hence E(nz) is the smallest group of n - th roots of uni-
ty, which contains {α} . Since α = ξrz , we see that the following el-
ements ξrzdz = 1, ξrz , ξ2rz , . . . , ξ(dz−1)rz represent the subgroup {α} in
the group E(nz) . Besides that, the decomposition of E(nz) relative to
the subgroup {α} consists of rz different cosets. Thus, the number rz
is the index of subgroup {α} in the group of roots of unity, having the
smallest possible order. The theorem is proved.
Remark 2 . Notice that when a parity-check polynomial of code is
some primitive polynomial of degree m and of order n = qm−1 , m > 1 ,
then r = R = (qm − 1)/(q − 1) and d = q − 1 . (see [2], [7]).
Corrollary 1 . The period nz , nz = rz·dz ,of element z(x) , z(x) ∈ J ,
equals dz , dz|(q − 1) , 1 ≤ dz ≤ (q − 1) ,if and only if the cycle {z(x)}
is contained in one class of proportionality.
Corollary 2 . All code words of any cyclic code, havinq some length
n over GF (q) , fall into some equal-weight subsets and every such subset
includes all proportional to each other cycles.
Besides that, consider some minimal ideal J , J ⊂ An , having an
irreducible nonprimitive parity-check polynomial h(x) of degree m and
of order n , n 6= qm−1 , i.e., some irreducible code of nonprimitive length.
Remark 3 . The degree m of the polynomial h(x) coincides with
the multiplicative order h of the number q modulo n [8]. Also, the order
n of the polynomial h(x) is some divisor of qh−1 . This means that the
order n can change in the following limits 1 < n < qh−1 , n 6= q − 1 . If
1 < n < q − 1 , i.e., n 6= q − 1 , then some minimal ideal J , J ⊂ An , of
dimention one contains only one nonzero class of proportyonality. Con-
sequently, n = d , 1 < d < q − 1 , d|q − 1 .
Theorem 2 . Any cycle of minimal ideal J , J ⊂ An , having some
parity-check polynomial h(x) of degree m , m > 1 , and of order n ,
n 6= qm − 1 , is contained in r proportionality classes, 1 ≤ r ≤ R , r|R ,
R = (qm − 1)/(q − 1) . Every such class consists of d , 1 ≤ d ≤ (q − 1) ,
different vectors of cycle, and
d = gcd(q − 1, n), r = n/d. (9)
Proof. All elements of minimal ideal J , J ⊂ An , have the same order
n , n = ord(h(x)) . Applying the theorem 1 to some element f(x) ,
f(x) ∈ J , we have n = rf ·df , df |(q−1) , 1 ≤ rf ≤ n , 1 ≤ df ≤ (q−1) ,
and also the following equality
xrf · f(x) = γ · f(x), (10)
where γ is some element of GF (q)∗ . Evidently, if either rf = 1 , i.e.,
df = n , or rf = n and df = 1 , then equalities (9) take place. Hence,
below we suppose that 1 < rf < n , 1 < df < q − 1 , and therefore
q − 1 < n < qm − 1 .
Taking into account (9) , we have df ≤ d . Let us show that the strong
unequality df < d is impossible. Indeed, if df < d , then the subgroup
{γ} , where γ is the element from equality (10) , belongs to some group
of n -th roots of unity, having the order d , because df |d . Since d|(q−1) ,
we see that the subgroup {γ} belongs to GF (q)∗ . This means that the
cycle {f(x)} is contained in one class of proportionality, i. e., rf = 1 .
But this fact contradicts to the condition rf > 1 . This implies that the
strong unequality df < d is impossible. Hence df = d . Because of an
arbitrary choice of f(x) we can conclude that equalities (9) take place
for any element of J . The theorem is proved [6].
Remark 4 . It is necessary to note that the theorem 2 is valid only
for irreducible codes of non–primitive length except Reed-Solomon codes
of length n = q − 1 as it was shown above. In the case of irreducible
codes of primitive length n , n = qm− 1 , m > 1 , the theorem 2 will be
valid if and only if gcd(m, q − 1) = 1 . Indeed, when the last condition
takes place, then gcd((qm − 1)/(q − 1), q − 1) = 1 [7]. Thus, d = q −
1 = gcd(qm − 1, q − 1) that is d = gcd(n, q − 1) . It follows that the
theorem 2 holds.
Remark 5 . Notice that under the condition gcd(m, q − 1) = 1 the
number r from (9) has no divisors of (q−1) except 1 , so gcd(r, q − 1) = 1 .
This means that gcd(r, d) = 1 . Hence, considering the fact that r|R and
also, taking into account (9) and the following equality s = R(q−1)/n ,
we have r = gcd(R, n) . Besides that, if either one from the two numbers
n and q− 1 does not contain multiple prime divisors or the same prime
divisors of these numbers have the same degrees under the decomposi-
tion of both n and q − 1 , then the following equalities r = gcd(R, n) ,
gcd(r, d) = 1 also take place.
Corollary 3 . Both the number r and the number d are the same
numbers of all irreducible divisors of polynomial xn − 1 over GF (q) ,
having the same order.
Corollary 4 . The number R , R = (qm−1)/(q−1) , of proportional-
ity classes, of some irreducible code K ,having some length n , n 6= (qm−
1) , n = d · r , over GF (q) field, consists of some v different subsets.
And every such subset contains r equal-weight proportionality classes,
i.e., R = v · r . Besides that, every subset includes b equal-weight cycles,
b = (q − 1)/d , 1 < b ≤ (q − 1) . So that the number of all cycles for K
equals s = v · b and gcd(r, b) = 1 .
Proof. According to the theorem 2 any cycle of code K is contained
in r , r|R , proportionality classes. Therefore the number v = R/r gives
us the common quantity of different subsets of J , each of which consists
of r classes, i.e., R = v · r . The number b , b = (q−1)/d , is the number
of all different equal-weight cycles, contained in every such subset, which
consists of some r classes. Hence the number of all cycles for K is equal
to s = v · b . Since d = gcd(q− 1, n) we see that gcd(r, b) = 1 . Actually,
assuming the inverse, we would have been able to decrease the number
d , but it’s impossible. The corollary is proved.
Corollary 5 . The irreducible nonprimitive code K is some equidis-
tant code if s = b .Besides that, the last equation is equivalent to the
following ones: r = R or gcd(s, R) = 1 .
Remark 6 . Note that the condition s = b was obtained in [14, 15],
but only for some subclass of irreducible nonprimitive codes and under
the following additional restriction gcd(b,m) = 1 .
Corollary 6 . The weight of any element, belonging to some irre-
ducible nonprimitive code K of length n over GF (q) , is multiple of the
number d , d = gcd(q − 1, n) .
Proof. The weight of any element z(x) , z(x) ∈ K , of order n ,
n = ord(h(x)) , is equal to the number of such j , 0 ≤ j ≤ n − 1 , for
which the polynomial xj · z(x) has the following degree n−1 . According
to the theorem 2 , the number of such polynomials for the cycle z(x) ,
having degree n − 1 , is equal to wr · d , where wr is the number of
polynomials, having degree n − 1 , among the first r cyclic shifts of
z(x) , and d = gcd(q − 1, n) . The corollary is proved.
In addition, consider some ideal J , J ⊂ An , of the form (2) , having
the parity-check polynomial h(x) in terms of (3) .
Theorem 3 .If the following condition gcd(h, q− 1) = 1 , where h is
the multiplicative order of number q mod n , takes place, then any cycle
of set C , C ⊂ J , having some minimal polynomial of the form (4) ,
is contained in rc proportionality classes, rc|Rc , and every such class
includes dc , dc|q − 1 , elements of cycle, that is nc = rc · dc , nc =
ord(c(x)) , where Rc is the number of all proportionality classes of set
C , and
rc = gcd(Rc, nc), dc = gcd(q − 1, nc). (11)
Proof. It is sufficient to consider the case k = 2 because the general case
can be obtained by the induction. Thus assume that c(x) = h1(x)·h2(x) ,
where hi(x) is of degree mi and of order ni , ni = q
mi − 1 , 1 ≤ i ≤ 2 ,
is a certain prime miltiplier of c(x) . It is known [8], that the number
mi , 1 ≤ i ≤ 2 , equals either h or some divisor of this number. Hence,
taking into account the theorem 2 , and also remarks 4 and 5 , we have
ni = ri ·di , where ri = gcd(Ri, ni) , di = gcd(q−1, ni) , gcd(ri, q−1) = 1 ,
1 ≤ ri ≤ Ri , 1 ≤ di ≤ q − 1 , and Ri = (q
mi − 1)/(q − 1) , where Ri is
the number of all proportionality classes of minimal ideal Ji , 1 ≤ i ≤ 2 .
Therefore the order nc , nc = lcm(n1, n2) = n1 · n2/gcd(n1, n2) of the
polynomial c(x) can be rewritten as
nc = r1 d1 · r2 d2/gcd(r1d1 · r2d2). (12)
Since gcd(ri, q − 1) = 1 , we have gcd(ri, d1 · d2) = 1 , 1 ≤ i ≤ 2 . Thus
gcd(r1r2, d1d2) = 1 . Hence gcd(gcd(r1, r2), gcd(d1, d2)) = 1 so that (12)
may be represented in the following form
nc = (r1 r2/gcd(r1, r2)) · (d1 d2/gcd(d1, d2)). (13)
Thus, nc = lcm(r1, r2) · lcm(d1, d2) . Now by rc and dc we denote
lcm(r1, r2) and lcm(d1, d2) , respectively. Thus nc = rc·dc and gcd(rc, dc) =
1 . Since dc|q− 1 and gcd(rc, q− 1) = 1 , we obtain dc = gcd(q− 1, nc) .
Considering (5) , it follows that nc|(Rc · (q − 1)) . Hence we have rc =
gcd(Rc, nc) . Consequently the order nc of any element of set C is equal
to the product of two relatively prime numbers, i.e., nc = rc · dc , where
rc = lcm(r1, r2) = gcd(Rc, nc) and dc = lcm(d1, d2) = gcd(q − 1, nc) .
Furthermore, applying the theorem 1 to some element a(x) ∈ C of
period nc = ra · da , we have
xra · a(x) = θa(x), (14)
where θ ∈ GF (q)∗ is some element of order da , and ra is the smallest
natural number such that equality (14) takes place. Notice that the
subgroup {θ} has the order da , da < dc . If dc = 1 , then da = 1 and
nc = ra = rc = gcd(Rc, nc) , so that equalities (11) hold. For this reason
below we suppose that dc > 1 . If under this condition the number rc
is equal to one, then nc = dc= gcd(q − 1, nc) and the theorem is valid.
Therefore below we suppose that both rc > 1 and dc > 1 .
Evidently, da ≤ dc . Now let us show that the inequality da < dc is
not possible. Indeed, if da < dc , then we come to the following conclusion.
The subgroup {θ} , where θ is the element from equality (14) , belongs
to some subgroup of GF (q)∗ , having the order dc , because da|dc . Since
dc is some divisor of nc , then, considering the uniqueness of subgroups,
having the same order, the subgroup {θ} belongs to some group of dc -
th roots of unity. This implies that the smallest group of roots of unit,
containing {θ} , has an order, which either less or equals dc . Thus, both
the period of a(x) and the order of c(x) must be either less or equal to
dc . This yields that the order of c(x) must be some divisor of q−1 . But
this fact contradicts the condition rc > 1 . Hence the inequality da < dc
is impossible so that da = dc and ra = rc . Because of an arbitrary choice
of a(x) equalities (11) take place for any element of set C . The theorem
is proved.
Corollary 7 . The order nc of reducible factor c(x) of polynomial
xn − 1 , having some degree m over GF (q) , is some divisor of num-
ber qm − 1 , if gcd(h, q − 1) = 1 , where h is the multiplicative order of
number q mod n .
Remark 7 . In terms of condition gcd(h, q − 1) = 1 , where h is the
multiplicative order of number q mod n , the theorem 3 is valid for
cyclic codes of both the primitive and the nonprimitive length. Also,
taking into consideration the remark 5 , the order of any reducible factor
of the polynomial (xn − 1) over GF (q) of degree m , is some divisor of
the number (qm − 1) , if gcd (h, q − 1) = 1 .
Theorem 4 . Any cycle of set C , C ⊂ J , having some minimal
polynomial c(x) of the type (4) and of order nc = lcm(n1, n2, . . . , nk) ,
where ni 6= q
mi − 1 , 1 ≤ i ≤ k , is contained in rc , rc|Rc , 1 ≤ rc ≤ Rc ,
classes of proportionality and every such class includes dc , 1 ≤ dc ≤
q − 1 , elements of cycle, where Rc is the number of all proportionality
classes of C , and
dc = gcd(q − 1, nc), rc = nc/dc. (15)
Proof. It is sufficient to assume that k = 2 because the general case can
be obtained by the induction. This implies that c(x) = h1(x)h2(x) , where
hi(x) is some prime divisor of equality (3) , having some degree mi , and
of order ni , ni 6= q
mi − 1 , 1 ≤ i ≤ 2 . This yields that the theorem 2
holds for the minimal ideal Ji , 1 ≤ i ≤ 2 .
Evidently, if one of the two numbers, i.e., either dc or rc is equal
to one, then equalities (15) hold. For this reason below we assume that
both rc > 1 and dc > 1 .
Let z(x) be some vector of set C . According to the theorem 1 some
cycle {z(x)} ⊂ C is contained in rz classes and every such class includes
dz different elements of this cycle. Thus nc = rz dz , 1 ≤ dz ≤ q − 1 ,
dz|q−1 , 1 ≤ rz ≤ nc . And in addition, the following equality takes place
xrz · z(x) = β z(x), (16)
where β is some element of GF (q)∗ and the subgroup {β} , {β} ⊂
GF (q)∗ , has the order dz . Evidently, dz ≤ dc . Let us show that the
number dz can not be smaller than dc . Assume the inverse, i.e. let dz
be less than dc . Since at least one of the two numbers ether r1 or r2 is
not equal to one, we see that at least one of the numbers ni , 1 ≤ i ≤ 2 ,
is more than q−1 , as was established in the theorem 2. This means that
nc = lcm(n1, n2) > (q − 1). (17)
Further, since dz|dc , we see that the subgroup {β} of order dz belongs to
some subgroup of GF (q)∗ , having the order dc , where β is the element
from equality (16) . Due to the uniqueness of groups, having the same
order, the subgroup {β} belongs to the group of dc -th roots of unity
because dc|nc . It follows that the smallest group of the roots of unity,
which contains the subgroup {β} , has the order less or equals to dc .
This implies that both the period of z(x) and the order of c(x) is some
divisor of q − 1 . But this fact contradicts to (17) . It follows that our
assumption is not true, so that dz = dc , and rz = rc .
Besides that, since the number dc is the same number for every cycle
of set C , we see that every subset, consisting of rc proportionality class-
es, contains the same number of cycles, which is equal to bc = q − 1/dc .
Moreover, since dc = gcd(q − 1, nc) , we obtain gcd(bc, rc) = 1 . Hence,
taking into account the following equality sc = Rc(q − 1)/nc , which fol-
lows from (5) , we see that rc is some divisor of Rc and sc = vcbc , where
vc is equal to Rc/rc . The theorem is proved.
Corollary 7 . (Equidistance signs of the subset C , C ⊂ J , having
some minimal polynomial of the form (4) .)
All vectors of the subset C , C ⊂ J , having some minimal polynomial
c(x) of order nc = lcm(n1, n2, ..., nk) , ni 6= q
mi − 1 , 1 ≤ i ≤ k , k > 1 ,
have the same weight if at least one of the following conditions holds: 1.
sc = bc , 1 < bc ≤ q − 1 , 2. rc = Rc , 3. gcd(sc, Rc) = 1 .
Corollary 8 . The order of the reducible factor c(x) of the polynomial
xn−1 over GF (q) , having some degree m , is some divisor of the number
qm− 1 , if the decomposition of the polynomial c(x) into prime multiples
does not contain any primitive polynomial.
Remark 8 . Note that corollaries (6) and (8) show us in what cases
corollary 3.4 from [8] takes place for some reducible polynomial of the
degree m over GF (q) .
Also, consider some cyclic code, having the following parity-check
polynomial
h(x) =
hi(x), (18)
where hi(x) is an irreducible polynomial over GF (q) , q > 2 , of degree
mi and of order ni = (q
mi − 1)/bi , bi|q − 1 , 1 ≤ bi ≤ q − 1 , 1 ≤ i ≤ t ,
gcd(mi, mj) = 1 and gcd(bi, bj) = 1 , provided i 6= j , 1 ≤ i, j ≤ t , so
that the order n of h(x) equals n = lcm(n1, n2, ..., nt) .
It is worth mentioning that in [14] and [15] the following cases of
polynomial (18) have been considered. Namely t = 1 and t = 2 , and
besides that, with some additional restrictions, which can be omitted.
Also, some particular case of polynomial (18) , that is provided bi = 1
for all i , 1 ≤ i ≤ t , was obtained in [16]. But there are some unnecessary
restrictions in this paper too. Also, there are some mistakes in that paper.
Namely, the order of the product for some two polynomials from (18)
was defined incorrectly in [16].
Finally, using the results obtained above, we have found the minimal
distance of code, having the parity-check polynomial (18) , (see [17]).
Denote by M the set of degrees for the polynomials hi(x) , 1 ≤ i ≤ t ,
from the eq. (18) that is M = (m1, m2, ..., mt) . Let the number m
denote the degree of polynomial h(x) , i. e., m = m1+m2+ ...+mt . By
Mj,k , 1 ≤ j ≤ C
t , 1 ≤ k ≤ t − 1 , denote j
,s k -subset of M , where
Ckt is the binomial coefficient.
Thus Mj,k = (mj1, mj2 , ..., mjk) , 1 ≤ j ≤ C
t , 1 ≤ k ≤ t − 1 . At
last, denote by mj,k the sum of degrees, from the subset Mj,k , so that
mj,k = mj1 +mj2 + ... +mjk , 1 ≤ j ≤ C
t , 1 ≤ k ≤ t− 1 . It is obvious
that 1 ≤ mjk < m . Let us remark that provided k = 1 the number
mj,k = mj,1 = mj and 1 ≤ j ≤ t because C
t = t .
Theorem 5 .The minimal distance of code, having the parity-check
polynomial (18) , has the following form
dmin = q
m−1 −
qmj,1−1 −−
qmj,2−1 − ...−−
qmj,t−1−1, t ≥ 2,
dmin = q
m−1(q − 1)/b, t = 1, 1 ≤ b ≤ q − 1,
dmin = q
m−1(q − 1), t = 1, b = 1.
In conclusion I should like to express my sincere gratitude to L.A.Bassaligo,
M.I. Boguslavskii and E.T. Akhmedov for helping me to correct some
mistakes in the original version of my paper.
References
[1] Van der Waerden B.L. Algebra, vol. 1 , 1976 .
[2] Macwilliams F. J., Sloane N. J. A. The theory of error-correcting
codes, North-Holland, Amsterdam, Sixth Printing, 1988 .
[3] Nili H. Matrixschaltungen zur codierung und decodierung von Grup-
pen codes, Archiv der elektrishen ubertragung, Band 18 , Het. 9 ,
1964 , S. 555− 564 .
[4] Macwilliams F.J. The structure and properties of binary cyclic al-
phabets, Bell System Tech. J., 44 , 303− 332 , 1965 .
[5] Mullayeva Iren I. Dependence between cyclic structure of ide-
al J , J ⊂ An and proportionality classes of algebra An =
GF (q)[x]/(Xn−1) , AZNIINTI, Deposited scient. works, N 1(5) , p.
15 , Baku, Azerb., 1994 .
[6] Mullayeva I.I. Interdependence between cyclic and weight structure
of codes over GF(q) and its classes of proportyonality. RAS, Prob-
lems of Information Transmition, v. 41 , No. 2 , 2005 .
[7] Peterson W. W., Weldon E.J. Error - correcting codes, 2 nd, ed.,
M.I.T. Press, Cambridge, Mass., 1972 .
[8] Lidl R., Niderreiter H. Finite fields, Addison-Wesley Publ. Com.,
Massachusetts, 1983 .
[9] Kurosch. Higher algebra, 1962 .
[10] Elspas B. The theory of autonomous linear sequential networks, IRE
Transactions on circuit theory, CT- 6 , N 1 , March ( 1959 ), 45−60 .
[11] Richard E. Blahut. Theory and practice of error control codes,
Addison-Wesley Publ. Com., Massachusetts, 1984 .
[12] Zierler N. Linear recurring sequences, J. Soc. Ind. Appl. Math., 7
( 1959 ), N 1 , 45− 60 .
[13] Oganesyan S., Tairyan V., Yagdzyan V. Decomposition of cyclic
codes into equel-weight classes, Probl. of Control and Inform. Th.,
3 ( 1974 ), N 2 , 117− 125 .
[14] Clark W. E. Equidistant cyclic codes over GF(q), Discrete Math.,
17 ( 1977 ), N 2 , 139− 141 .
[15] Oganesyan S.,Yagdzyan V., Tairyan V. On a class of optimal cyclic
codes, Proc. 2 nd Int. Symp. on Inform. Theory, Tsahkadzor, Arme-
nia, USSR, 1971 , Budapest: Acad. Kiado, 1973 , 219− 224 .
[16] Tenengolts G. M. A new class of cyclic error-corecting codes, Proc.
3 nd Confr. on Coding and Transm. Inform., Soviet Un., Ugegorod,
1967 , 18− 28 .
[17] Mullayeva Iren I. Equidistance criterion of cyclic subset for ideal J ,
of algebra An = GF (q)[x]/(x
n−1) , consisting of polynomials mod-
ulo xn − 1 over Galois field GF (q) , q > 2 , AZNIINTI, Deposited
scient. works, N2(6) , p. 16 , Baku, Azerbaijan, 1994 .
