# Self-Dual Normal Basis of a Galois Ring

Authors: Irwansyah; Intan Muchtadi-Alamsyah; Aleams Barra; Ahmad Muchlis
Journal: Journal of Mathematics
 (2014)

---

## Abstract

LetR
′
=
G
R
(
p
s
,
p
s
m
l
) and R
=
G
R
(
p
s
,
p
s
m
) be two Galois rings. In this paper, we show how to construct normal basis in the extension of Galois rings, and we also define weakly self-dual normal basis and self-dual normal basis for R
′ over R, where R
′ is considered as a free module over R. Moreover, we explain a way to construct self-dual normal basis using particular system of polynomials. Finally, we show the connection between self-dual normal basis for R
′ over R and the set of all invertible, circulant, and orthogonal matrices over R.


---

## Body

## 1. Introduction

Normal basis is one important type of basis over Galois fields, because it is computationally manageable. One type of normal basis which has applications in cryptography and coding theory is self-dual normal basis; see [1, 2]. Therefore, some researcher are interested in finding a way to construct self-dual normal basis over Galois fields; see [3, 4].On the other hand, as a generalization of Galois fields, Galois rings have also several connections with coding theory; see [5, 6]. Normal basis and its variants such as self-dual are also important in Galois ring, especially for computations in codes over this ring [2, 4].Given two Galois ringsR and R
′, where R
′ is an extension of R, a normal basis for R
′ over R is a basis which consists of all orbit of some α
∈
R
′ from the action of G into R
′, where G is Galois group of R
′ over R. As a consequence of the work of Kanzaki [7] and the fact that Galois ring is a local ring [8, Lemma 2], there always exists normal basis for R
′ over R.In this paper, we will show some properties of self-dual normal basis of a Galois ring similar to the properties of self-dual normal basis over finite fields. We will also explain how to get normal basis generator and self-dual normal basis generator and show a connection between the set of generators of self-dual normal basis and the set of invertible circulant and orthogonal matrices overR. Moreover, we give an application of normal basis, especially self-dual normal basis, in encoding certain cyclic codes over Z
p
k.


## 2. Normal Basis over Galois Ring

### 2.1. Some Properties of Normal Basis over Galois Ring

LetR
=
GR
(
p
s
,
p
s
m
) be a Galois ring with characteristic p
s and cardinality p
s
m. If R
′
=
GR
(
p
s
,
p
s
n
) and m
∣
n, then R is a subring of R
′. Moreover, if h
(
x
)
∈
R
[
x
] is a basic primitive irreducible polynomial with degree l, then R
[
x
]
/
(
h
(
x
)
) is a Galois ring with characteristic p
s and cardinality p
s
m
l and contains R as a subring. In other words, R
[
x
]
/
(
h
(
x
)
) is an extension of R of order l. If ξ is a root of h
(
x
) and has order p
m
l
-
1, then R
′
=
R
[
ξ
]. Define a map ϕ
:
R
′
→
R
′ where
(1)
ϕ
(
a
0
+
a
1
ξ
+
a
2
ξ
2
+
⋯
+
a
l
-
1
ξ
l
-
1
)
=
a
0
+
a
1
ξ
p
m
+
⋯
+
a
l
-
1
ξ
(
l
-
1
)
p
m
for every a
i
∈
R. We can prove that ϕ is an automorphism which left R fixed. Furthermore, ϕ generates the Galois group Gal
(
R
′
/
R
) of order l [8]. Some detailed explanations about Galois ring can be found in [8].We define normal basis ofR
′ over R as follows.Definition 1.
A normal basis ofR
′ over R is a basis which consists of the elements ϕ
k
(
α
), where k
=
0,1
,
…
,
l
-
1, for some α
∈
R
′, where R
′ is considered as a free-module over R.IfA
=
{
ϕ
k
(
α
)
∣
k
=
0,1
,
…
,
l
-
1
} is a normal basis for R
′ over R, then, for every β
∈
R
′, we can uniquely write down β as follows:
(2)
β
=
∑
k
=
0
l
-
1
‍
a
k
ϕ
k
(
α
)
for some a
k
∈
R. Therefore, we can consider β
=
(
a
0
,
a
1
,
…
,
a
l
-
1
) as an element in R
l. As an immediate consequence of the above definition, one has the following lemma.Lemma 2.
LetA
=
{
ϕ
k
(
α
)
∣
k
=
0,1
,
…
,
l
-
1
} be a normal basis for R
′ over R. If β
=
(
a
0
,
a
1
,
…
,
a
l
-
1
)
∈
R
l with respect to A, then ϕ
j
(
β
)
=
(
a
0
+
j
mod
⁡
l
,
a
1
+
j
mod
⁡
l
,
…
,
a
l
-
1
+
j
mod
⁡
l
).Proof.
Considerβ
=
∑
k
=
0
l
-
1
‍
a
k
ϕ
k
(
α
); then ϕ
j
(
β
)
=
∑
k
=
0
l
-
1
‍
a
k
ϕ
k
+
j
(
α
), because every element in R is fixed by ϕ. Thus, we have ϕ
j
(
β
)
=
(
a
0
+
j
mod
⁡
l
,
a
1
+
j
mod
⁡
l
,
…
,
a
l
-
1
+
j
mod
⁡
l
).Before we construct a normal basis in Galois ring, we need the following definition and ring homomorphism.Definition 3 (see [9]).
Letf
(
x
) be a polynomial in F
q
[
x
] with degree n, where F
q is Galois field with q elements and q is a prime power. We say f
(
x
) is a Normal Polynomial or N-Polynomial if f
(
x
) is irreducible over F
q and its roots is the generator of normal basis for F
q
n over F
q.
We define a ring homomorphism-
:
Z
p
s
→
F
p as in [8] by
(3)
-
:
Z
p
s
⟶
F
p
c
0
+
c
1
p
+
c
2
p
2
+
⋯
+
c
s
-
1
p
s
-
1
⟼
c
0
,
where 0
≤
c
i
≤
p
-
1. This ring homomorphism can be extended to the following ring homomorphism:
(4)
-
:
Z
p
s
[
x
]
⟶
F
p
[
x
]
a
0
+
a
1
x
+
a
2
x
2
+
⋯
+
a
n
x
n
⟼
a
0
¯
+
a
1
¯
x
+
⋯
+
a
n
¯
x
n
,
where a
0
,
a
1
,
…
,
a
n
∈
Z
p
s. The following theorem gives us a way to construct normal basis for GR
(
p
s
,
p
s
n
) over Z
p
s.Theorem 4.
LetZ
p
s be the ring of integers modulo p
s and let h
(
x
) be a basic primitive polynomial of degree n over Z
p
s. If α is a generator of normal basis for F
p
n
≃
F
p
[
x
]
/
(
h
(
x
)
¯
) over F
p, then α
∈
G
R
(
p
s
,
p
s
n
) is also a generator for normal basis for Galois ring G
R
(
p
s
,
p
s
n
) over Z
p
s.Proof.
As in [8] the homomorphism (4) induces the following homomorphism:
(5)
-
:
Z
p
s
[
x
]
(
h
(
x
)
)
⟶
F
p
[
x
]
(
h
(
x
)
¯
)
a
0
+
a
1
x
+
a
2
x
2
+
⋯
+
a
n
-
1
x
n
-
1
+
(
h
(
x
)
)
⟼
a
0
¯
+
a
1
¯
x
+
⋯
+
a
n
-
1
¯
x
n
-
1
+
(
h
(
x
)
¯
)
,
where the kernel of homomorphism (5) is the ideal (
p
+
(
h
(
x
)
)
). Consequently,
(6)
(
Z
p
s
[
x
]
/
(
h
(
x
)
)
)
(
p
+
(
h
(
x
)
)
)
≃
F
p
[
x
]
(
h
(
x
)
¯
)
.
From (6), α is a generator of normal basis for F
p
n over F
p and also for (
Z
p
s
[
x
]
/
(
h
(
x
)
)
)
/
(
p
+
(
h
(
x
)
)
) over F
p. Therefore, we can say that ∑
i
‍
a
i
ϕ
i
(
α
)
=
0 if and only if a
i
∈
(
p
+
(
h
(
x
)
)
) for all i.
Now, we need to show thatα is also a generator for normal basis of Z
p
s
[
x
]
/
(
h
(
x
)
) over Z
p
s. Since A
=
{
α
,
ϕ
(
α
)
,
ϕ
2
(
α
)
,
…
,
ϕ
n
-
1
(
α
)
} is already linearly independent over F
p, if we want to show that A is linearly independent over Z
p
s, we only need to prove that the the following equation over (
p
)
(7)
∑
j
=
0
n
-
1
‍
b
j
ϕ
j
(
α
)
=
0
is only satisfied by b
j
=
0 for all j. Let b
j
=
∑
k
=
1
s
-
1
‍
c
j
k
p
k, where c
j
k
∈
F
p for all k. Consider
(8)
∑
j
‍
b
j
ϕ
j
(
α
)
=
p
(
c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
+
…
+
c
n
-
1,1
ϕ
n
-
1
(
α
)
)
l
l
l
l
l
l
l
l
l
l
l
+
⋯
+
c
n
-
1,1
ϕ
n
-
1
(
α
)
)
+
ω
j
(
p
2
,
…
,
p
s
-
1
)
,
where ω
j
(
p
2
,
…
,
p
s
-
1
) is the rest terms. By (7), we have p
(
c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
) is 0 or -
ω
j
(
p
2
,
…
,
p
s
-
1
) and from the first paragraph, we can say that c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
∉
(
p
+
(
h
(
x
)
)
). Therefore, using the fact that ω
j
(
p
2
,
…
,
p
s
-
1
) the term with power of p is more than or is equal to 2, we have p
(
c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
)
=
-
ω
j
(
p
2
,
…
,
p
s
-
1
) will not be the case. Hence, p
(
c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
)
=
0, which means c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
) will be equal to 0 or p
s
-
1. Again, from the first paragraph, we have c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
≠
p
s
-
1. Consequently, we have c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
=
0, and because A is linearly independent over F
p, we have c
01
=
c
11
=
⋯
=
c
n
-
1,1
=
0 is the only solution. Continuing this process for the terms which contain p
2, p
3, and so on, we have c
j
k
=
0, for all j
,
k, is the only solution. Hence b
j
=
0, for all j, is the only solution for (7) as we hope. Because Galois ring has invariant basis number by [10, Lemma  2.6], so A
=
{
α
,
ϕ
(
α
)
,
ϕ
2
(
α
)
,
…
,
ϕ
n
-
1
(
α
)
} must be a basis.Leth
(
x
) be a basic primitive polymomial of degree n over Z
p
s and ξ is a root of h
(
x
). Based on [8, Theorem 14.8 part (ii)], we have
(9)
GR
(
p
s
,
p
s
n
)
=
{
a
0
+
a
1
p
+
a
2
p
2
+
⋯
+
a
s
-
1
p
s
-
1
∣
a
i
∈
τ
}
,
where τ
=
{
0,1
,
ξ
,
ξ
2
,
…
,
ξ
p
m
-
2
}. We call this representation as p-adic representation of the Galois ring. The next theorem gives a way to construct normal basis for extension of Galois rings in general.Theorem 5.
LetR
′
=
G
R
(
p
s
,
p
s
n
) and R
=
G
R
(
p
s
,
p
s
m
) be two Galois rings, where m
∣
n, and h
(
x
) is a basic primitive polynomial of degree d
=
n
/
m. If α is a generator of normal basis for F
p
n
≃
F
p
m
[
x
]
/
(
h
(
x
)
¯
) over F
p
m, then α
∈
G
R
(
p
s
,
p
s
n
) is also a generator for normal basis of Galois ring R
′ over R.Proof.
Leth
1
(
x
)
¯ be a primitive polynomial of degree m over F
p. Since, h
1
(
x
)
¯
¯
=
h
1
(
x
)
¯, we can take h
1
′
(
x
)
=
h
1
(
x
)
¯ a basic primitive polynomial over Z
p
s. Let ξ be a root of h
1
′
(
x
)
=
h
1
(
x
)
¯, so ξ is a primitive element of F
p
m. Therefore, by p-adic representation we have
(10)
R
(
p
+
(
h
1
′
(
x
)
)
)
≃
τ
=
F
p
m
.
Sincem
∣
n, Galois field F
p
m is a subfield of Galois field F
p
n. We have
(11)
R
′
(
p
+
(
h
(
x
)
)
)
≃
F
p
n
.
Let A
=
{
α
,
ϕ
(
α
)
,
ϕ
2
(
α
)
,
…
,
ϕ
n
-
1
(
α
)
}. In order to be a basis, we only need to show that A is linearly independent over (
p
+
(
h
1
′
(
x
)
)
). Now, consider
(12)
∑
j
=
0
n
-
1
‍
b
j
ϕ
j
(
α
)
=
0
,
where b
j
∈
(
p
+
(
h
1
′
(
x
)
)
) for all j. Using p-adic representation of R and the methods in Theorem 4, we will have b
j
=
0 for all j is the only solution and A
=
{
α
,
ϕ
(
α
)
,
ϕ
2
(
α
)
,
…
,
ϕ
n
-
1
(
α
)
} is a normal basis for R
′ over R.
LetA
=
{
α
0
,
α
1
,
…
,
α
l
-
1
} be a normal basis of R
′ over R. Let Γ
=
{
η
0
,
η
1
,
…
,
η
n
-
1
}
⊂
R
′ where
(13)
η
j
=
∑
k
=
0
n
-
1
‍
c
j
k
α
k
for some c
j
k
∈
R. Let C
=
[
c
i
j
]; based on [10, Lemma 2.6], Galois ring has invariant basis number. Therefore, the transition matrix between two basis is an invertible square matrix. We have the following characterization.Proposition 6.
Γ is a normal basis of R
′ over R if and only if C is an invertible circulant matrix.Proof.
The proof is similar to the proof of Theorem  1.6 in [9].Ifξ is a root of a basic irreducible polynomial in R
[
x
], then as in [8] we have R
′
=
R
[
ξ
]. Now, let B
=
{
β
0
,
β
1
,
…
,
β
l
-
1
}
⊂
R
′, where β
j
=
ϕ
j
(
β
0
) and
(14)
β
j
=
∑
i
=
0
l
-
1
‍
b
i
j
ξ
i
for some b
i
j
∈
R, for all j
=
0,1
,
…
,
l
-
1. Then we have the following characterization.Proposition 7.
The setB forms a normal basis for R
′ over R if and only if M
B
=
[
b
i
j
] is an invertible matrix and β
k
=
ϕ
k
(
β
0
) for all k
=
0,1
,
…
,
l
-
1.Now, letA
=
{
ϕ
k
(
α
)
∣
k
=
0,1
,
…
,
l
-
1
} be a normal basis for R
′ over R. As before, we can write down uniquely β
=
(
b
0
,
b
1
,
…
,
b
l
-
1
) and ζ
=
(
a
0
,
a
1
,
…
,
a
l
-
1
) for some a
i
,
b
i
∈
R, where i
=
0
,
…
,
l
-
1, with respect to normal basis A. We are also able to represent ω
=
ζ
·
β
=
(
c
0
,
c
1
,
…
,
c
l
-
1
), with respect to the above normal basis. Therefore, we would like to know how to write every coordinate of ω in terms of a
j and b
j. Let
(15)
ϕ
i
ϕ
j
=
∑
k
=
0
l
-
1
‍
t
i
j
(
k
)
ϕ
k
(
α
)
for some t
i
j
(
k
); then, we will have
(16)
c
k
=
∑
i
‍
∑
j
‍
a
i
b
j
t
i
j
(
k
)
=
ζ
T
k
β
,
0
≤
k
≤
l
-
1
,
where T
k
=
[
t
i
j
(
k
)
] is an l-by-l matrix over R. Then, we would like to know how many nonzero entries in every matrix in the collection {
T
k
=
(
t
i
j
(
k
)
)
}, which calledcomplexity of normal basis A.Definition 8.
Letc
A
(
k
) be the number of nonzero entries in the matrix T
k. Then, c
A
(
k
) is called the complexity of the matrix T
k. Furthermore, if c
A
=
max
⁡
k
c
A
(
k
), then c
A is called the complexity of normal basis A.
Using the generalization of homomorphism in (4) and [8, Lemma 14.31], we have that ϕ
¯ is the Frobenius automorphism in finite field F
p
m
l over F
p
m. In fact, Gal
(
R
′
/
R
) is isomorphic as a group to Gal
(
F
p
m
l
/
F
p
m
) via the above homomorphism; see [8, Theorem 14.32]. Now, consider (15)
(17)
ϕ
¯
(
ϕ
i
(
α
)
¯
ϕ
j
(
α
)
¯
)
-
r
=
(
ϕ
i
(
α
)
¯
ϕ
j
(
α
)
¯
)
p
-
m
r
=
∑
k
=
0
l
-
1
‍
t
i
j
(
k
)
¯
ϕ
k
-
r
(
α
)
¯
which implies
(18)
t
i
j
(
r
)
¯
=
t
i
-
r
,
j
-
r
(
0
)
¯
,
0
≤
r
≤
l
-
1
.
Then we will have the following result.Proposition 9.
Ifc
A
(
k
) is the complexity for T
k, then c
A
(
k
)
≥
2
l
-
1.Proof.
Note that, by Theorems4 and 5, α
¯ is also a generator of normal basis for F
p
m
l over F
p
m. Therefore, A
¯ is a normal basis for F
p
m
l over F
p
m. We will consider c
A
(
0
) first. Let c
A
0
¯ be the number of nonzero entries in T
0
¯ and let T be the multiplication table for A
¯. By Theorem  5.1 in [9], we have the number of nonzero entries in T; that is, c
A
¯, satisfies c
A
¯
≥
2
l
-
1 which implies c
A
(
0
)
¯
≥
2
l
-
1. Therefore, we have c
A
(
0
)
≥
2
l
-
1. Now, by (18), we have the conclusion for all k.From the above result, we have an immediate consequence regarding the complexity of normal basis in Galois rings as follows.Corollary 10.
For any normal basisA of R
′ over R, one has c
A
≥
2
l
-
1.


### 2.2. Self-Dual Normal Basis

A dual basis of a basis is defined using a map called trace. We define trace overR as follows:
(19)
T
R
′
/
R
(
β
)
=
∑
i
=
0
l
-
1
‍
ϕ
i
(
β
)
for every β
∈
R
′. More properties of trace function can be found in [8]. The definition of dual basis is as follows.Definition 11.
LetA
=
{
α
0
,
α
1
,
…
,
α
l
-
1
} and B
=
{
β
0
,
β
1
,
…
,
β
l
-
1
} be two bases of R
′ over R as a free-module. We say that B is a dual of A if
(20)
T
R
′
/
R
(
α
i
β
j
)
=
δ
i
j
for all i
,
j, where δ
i
j is Kronecker’s delta function.One has the following properties for dual basis which are similar to the properties in [11].Lemma 12.
IfA
=
{
α
0
,
α
1
,
…
,
α
l
-
1
} and B
=
{
β
0
,
β
1
,
…
,
β
l
-
1
} are two bases which are dual to each other, then one has the following.(1)
For everyv
∈
R
′ one has
(21)
v
=
∑
i
=
0
l
-
1
‍
T
R
′
/
R
(
α
i
v
)
β
i
=
∑
i
=
0
l
-
1
‍
T
R
′
/
R
(
β
i
v
)
α
i
.
(2)
T
R
′
/
R
(
α
i
)
T
R
′
/
R
(
β
i
)
=
1, for all i
=
0
,
…
,
l
-
1.Lemma 13.
There always exists a unique dual basis for any basis ofR
′ over R.Proof.
This lemma follows from the fact thatT
R
′
/
R is a surjective map. The rest of the proof is similar to the proof of Theorem  1.1 in [9].The following lemma is similar to [9, Corollary 1.4].Lemma 14.
IfA
=
{
α
0
,
α
1
,
…
,
α
l
-
1
} is a normal basis of R
′ over R and B
=
{
β
0
,
β
1
,
…
,
β
l
-
1
} is a dual basis for A, then B is also a normal basis.Self-dual normal basis is a normal basis which is equal to its unique dual basis. Bagio et al. [12] show that there always exist self-dual normal basis in an extension of a local ring of odd order. Therefore, there always exist self-dual normal bases of R
′ over R when l is odd, since Galois rings are local rings. Now, we will give a way to obtain self-dual normal basis generator of R
′ over R whenever |
G
| is odd, where G is the Galois group of R
′ over R.LetR
[
G
]
=
{
∑
i
=
0
l
-
1
‍
a
i
ϕ
i
∣
a
i
∈
R
}; then, we can show that R
[
G
] is an algebra over R. For v
=
∑
i
=
0
l
-
1
‍
a
i
ϕ
i, we define conjugate of v as v
¯
=
∑
i
=
0
l
-
1
‍
a
i
ϕ
-
i. The following theorem gives the generator of self-dual normal basis for R
′ over R.Theorem 15.
(1) Letα be a normal basis generator for in R
′ over R. If v
∈
R
[
G
] satisfies
(22)
v
v
¯
=
∑
i
=
0
l
-
1
‍
T
R
′
/
R
(
α
ϕ
i
(
α
)
)
ϕ
i
then v has an inverse in R
[
G
].
(2) The mappingφ
α
:
v
↦
v
-
1
∘
α gives a one-to-one correspondence between the set of solutions for (22) and the set of elements in R
′ which generate self-dual normal basis.Proof.
The proof of this theorem is similar to the proof of [4, Theorem 2.5].The following proposition gives us a way to findv which satisfies (22).Proposition 16.
Ifv
v
¯
=
∑
i
=
0
l
-
1
‍
∑
j
=
0
l
-
1
‍
a
i
a
j
ϕ
(
i
-
j
)
mod
⁡
l
=
∑
k
=
0
l
-
1
‍
b
k
ϕ
k, then
(23)
b
k
=
∑
j
=
0
l
-
1
‍
a
(
k
+
j
)
mod
⁡
l
a
j
for all k
=
0,1
,
2
,
…
,
l
-
1.Therefore, based on the previous proposition,v
∈
R
[
G
] which satisfies (22) are the solutions of the following system of polymomials:
(24)
∑
i
=
0
l
-
1
‍
a
i
2
-
T
R
′
/
R
(
α
α
)
=
0
,
∑
i
=
0
l
-
1
‍
a
i
a
(
i
+
1
)
mod
⁡
l
-
T
R
′
/
R
(
ϕ
(
α
)
α
)
=
0
,
⋮
∑
i
=
0
l
-
1
‍
a
i
a
(
i
+
k
)
mod
⁡
l
-
T
R
′
/
R
(
ϕ
k
(
α
)
α
)
=
0
,
⋮
∑
i
=
0
l
-
1
‍
a
i
a
(
i
+
l
-
1
)
mod
⁡
l
-
T
R
′
/
R
(
ϕ
l
-
1
(
α
)
α
)
=
0
.


## 2.1. Some Properties of Normal Basis over Galois Ring

LetR
=
GR
(
p
s
,
p
s
m
) be a Galois ring with characteristic p
s and cardinality p
s
m. If R
′
=
GR
(
p
s
,
p
s
n
) and m
∣
n, then R is a subring of R
′. Moreover, if h
(
x
)
∈
R
[
x
] is a basic primitive irreducible polynomial with degree l, then R
[
x
]
/
(
h
(
x
)
) is a Galois ring with characteristic p
s and cardinality p
s
m
l and contains R as a subring. In other words, R
[
x
]
/
(
h
(
x
)
) is an extension of R of order l. If ξ is a root of h
(
x
) and has order p
m
l
-
1, then R
′
=
R
[
ξ
]. Define a map ϕ
:
R
′
→
R
′ where
(1)
ϕ
(
a
0
+
a
1
ξ
+
a
2
ξ
2
+
⋯
+
a
l
-
1
ξ
l
-
1
)
=
a
0
+
a
1
ξ
p
m
+
⋯
+
a
l
-
1
ξ
(
l
-
1
)
p
m
for every a
i
∈
R. We can prove that ϕ is an automorphism which left R fixed. Furthermore, ϕ generates the Galois group Gal
(
R
′
/
R
) of order l [8]. Some detailed explanations about Galois ring can be found in [8].We define normal basis ofR
′ over R as follows.Definition 1.
A normal basis ofR
′ over R is a basis which consists of the elements ϕ
k
(
α
), where k
=
0,1
,
…
,
l
-
1, for some α
∈
R
′, where R
′ is considered as a free-module over R.IfA
=
{
ϕ
k
(
α
)
∣
k
=
0,1
,
…
,
l
-
1
} is a normal basis for R
′ over R, then, for every β
∈
R
′, we can uniquely write down β as follows:
(2)
β
=
∑
k
=
0
l
-
1
‍
a
k
ϕ
k
(
α
)
for some a
k
∈
R. Therefore, we can consider β
=
(
a
0
,
a
1
,
…
,
a
l
-
1
) as an element in R
l. As an immediate consequence of the above definition, one has the following lemma.Lemma 2.
LetA
=
{
ϕ
k
(
α
)
∣
k
=
0,1
,
…
,
l
-
1
} be a normal basis for R
′ over R. If β
=
(
a
0
,
a
1
,
…
,
a
l
-
1
)
∈
R
l with respect to A, then ϕ
j
(
β
)
=
(
a
0
+
j
mod
⁡
l
,
a
1
+
j
mod
⁡
l
,
…
,
a
l
-
1
+
j
mod
⁡
l
).Proof.
Considerβ
=
∑
k
=
0
l
-
1
‍
a
k
ϕ
k
(
α
); then ϕ
j
(
β
)
=
∑
k
=
0
l
-
1
‍
a
k
ϕ
k
+
j
(
α
), because every element in R is fixed by ϕ. Thus, we have ϕ
j
(
β
)
=
(
a
0
+
j
mod
⁡
l
,
a
1
+
j
mod
⁡
l
,
…
,
a
l
-
1
+
j
mod
⁡
l
).Before we construct a normal basis in Galois ring, we need the following definition and ring homomorphism.Definition 3 (see [9]).
Letf
(
x
) be a polynomial in F
q
[
x
] with degree n, where F
q is Galois field with q elements and q is a prime power. We say f
(
x
) is a Normal Polynomial or N-Polynomial if f
(
x
) is irreducible over F
q and its roots is the generator of normal basis for F
q
n over F
q.
We define a ring homomorphism-
:
Z
p
s
→
F
p as in [8] by
(3)
-
:
Z
p
s
⟶
F
p
c
0
+
c
1
p
+
c
2
p
2
+
⋯
+
c
s
-
1
p
s
-
1
⟼
c
0
,
where 0
≤
c
i
≤
p
-
1. This ring homomorphism can be extended to the following ring homomorphism:
(4)
-
:
Z
p
s
[
x
]
⟶
F
p
[
x
]
a
0
+
a
1
x
+
a
2
x
2
+
⋯
+
a
n
x
n
⟼
a
0
¯
+
a
1
¯
x
+
⋯
+
a
n
¯
x
n
,
where a
0
,
a
1
,
…
,
a
n
∈
Z
p
s. The following theorem gives us a way to construct normal basis for GR
(
p
s
,
p
s
n
) over Z
p
s.Theorem 4.
LetZ
p
s be the ring of integers modulo p
s and let h
(
x
) be a basic primitive polynomial of degree n over Z
p
s. If α is a generator of normal basis for F
p
n
≃
F
p
[
x
]
/
(
h
(
x
)
¯
) over F
p, then α
∈
G
R
(
p
s
,
p
s
n
) is also a generator for normal basis for Galois ring G
R
(
p
s
,
p
s
n
) over Z
p
s.Proof.
As in [8] the homomorphism (4) induces the following homomorphism:
(5)
-
:
Z
p
s
[
x
]
(
h
(
x
)
)
⟶
F
p
[
x
]
(
h
(
x
)
¯
)
a
0
+
a
1
x
+
a
2
x
2
+
⋯
+
a
n
-
1
x
n
-
1
+
(
h
(
x
)
)
⟼
a
0
¯
+
a
1
¯
x
+
⋯
+
a
n
-
1
¯
x
n
-
1
+
(
h
(
x
)
¯
)
,
where the kernel of homomorphism (5) is the ideal (
p
+
(
h
(
x
)
)
). Consequently,
(6)
(
Z
p
s
[
x
]
/
(
h
(
x
)
)
)
(
p
+
(
h
(
x
)
)
)
≃
F
p
[
x
]
(
h
(
x
)
¯
)
.
From (6), α is a generator of normal basis for F
p
n over F
p and also for (
Z
p
s
[
x
]
/
(
h
(
x
)
)
)
/
(
p
+
(
h
(
x
)
)
) over F
p. Therefore, we can say that ∑
i
‍
a
i
ϕ
i
(
α
)
=
0 if and only if a
i
∈
(
p
+
(
h
(
x
)
)
) for all i.
Now, we need to show thatα is also a generator for normal basis of Z
p
s
[
x
]
/
(
h
(
x
)
) over Z
p
s. Since A
=
{
α
,
ϕ
(
α
)
,
ϕ
2
(
α
)
,
…
,
ϕ
n
-
1
(
α
)
} is already linearly independent over F
p, if we want to show that A is linearly independent over Z
p
s, we only need to prove that the the following equation over (
p
)
(7)
∑
j
=
0
n
-
1
‍
b
j
ϕ
j
(
α
)
=
0
is only satisfied by b
j
=
0 for all j. Let b
j
=
∑
k
=
1
s
-
1
‍
c
j
k
p
k, where c
j
k
∈
F
p for all k. Consider
(8)
∑
j
‍
b
j
ϕ
j
(
α
)
=
p
(
c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
+
…
+
c
n
-
1,1
ϕ
n
-
1
(
α
)
)
l
l
l
l
l
l
l
l
l
l
l
+
⋯
+
c
n
-
1,1
ϕ
n
-
1
(
α
)
)
+
ω
j
(
p
2
,
…
,
p
s
-
1
)
,
where ω
j
(
p
2
,
…
,
p
s
-
1
) is the rest terms. By (7), we have p
(
c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
) is 0 or -
ω
j
(
p
2
,
…
,
p
s
-
1
) and from the first paragraph, we can say that c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
∉
(
p
+
(
h
(
x
)
)
). Therefore, using the fact that ω
j
(
p
2
,
…
,
p
s
-
1
) the term with power of p is more than or is equal to 2, we have p
(
c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
)
=
-
ω
j
(
p
2
,
…
,
p
s
-
1
) will not be the case. Hence, p
(
c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
)
=
0, which means c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
) will be equal to 0 or p
s
-
1. Again, from the first paragraph, we have c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
≠
p
s
-
1. Consequently, we have c
01
α
+
c
11
ϕ
(
α
)
+
c
21
ϕ
2
(
α
)
=
0, and because A is linearly independent over F
p, we have c
01
=
c
11
=
⋯
=
c
n
-
1,1
=
0 is the only solution. Continuing this process for the terms which contain p
2, p
3, and so on, we have c
j
k
=
0, for all j
,
k, is the only solution. Hence b
j
=
0, for all j, is the only solution for (7) as we hope. Because Galois ring has invariant basis number by [10, Lemma  2.6], so A
=
{
α
,
ϕ
(
α
)
,
ϕ
2
(
α
)
,
…
,
ϕ
n
-
1
(
α
)
} must be a basis.Leth
(
x
) be a basic primitive polymomial of degree n over Z
p
s and ξ is a root of h
(
x
). Based on [8, Theorem 14.8 part (ii)], we have
(9)
GR
(
p
s
,
p
s
n
)
=
{
a
0
+
a
1
p
+
a
2
p
2
+
⋯
+
a
s
-
1
p
s
-
1
∣
a
i
∈
τ
}
,
where τ
=
{
0,1
,
ξ
,
ξ
2
,
…
,
ξ
p
m
-
2
}. We call this representation as p-adic representation of the Galois ring. The next theorem gives a way to construct normal basis for extension of Galois rings in general.Theorem 5.
LetR
′
=
G
R
(
p
s
,
p
s
n
) and R
=
G
R
(
p
s
,
p
s
m
) be two Galois rings, where m
∣
n, and h
(
x
) is a basic primitive polynomial of degree d
=
n
/
m. If α is a generator of normal basis for F
p
n
≃
F
p
m
[
x
]
/
(
h
(
x
)
¯
) over F
p
m, then α
∈
G
R
(
p
s
,
p
s
n
) is also a generator for normal basis of Galois ring R
′ over R.Proof.
Leth
1
(
x
)
¯ be a primitive polynomial of degree m over F
p. Since, h
1
(
x
)
¯
¯
=
h
1
(
x
)
¯, we can take h
1
′
(
x
)
=
h
1
(
x
)
¯ a basic primitive polynomial over Z
p
s. Let ξ be a root of h
1
′
(
x
)
=
h
1
(
x
)
¯, so ξ is a primitive element of F
p
m. Therefore, by p-adic representation we have
(10)
R
(
p
+
(
h
1
′
(
x
)
)
)
≃
τ
=
F
p
m
.
Sincem
∣
n, Galois field F
p
m is a subfield of Galois field F
p
n. We have
(11)
R
′
(
p
+
(
h
(
x
)
)
)
≃
F
p
n
.
Let A
=
{
α
,
ϕ
(
α
)
,
ϕ
2
(
α
)
,
…
,
ϕ
n
-
1
(
α
)
}. In order to be a basis, we only need to show that A is linearly independent over (
p
+
(
h
1
′
(
x
)
)
). Now, consider
(12)
∑
j
=
0
n
-
1
‍
b
j
ϕ
j
(
α
)
=
0
,
where b
j
∈
(
p
+
(
h
1
′
(
x
)
)
) for all j. Using p-adic representation of R and the methods in Theorem 4, we will have b
j
=
0 for all j is the only solution and A
=
{
α
,
ϕ
(
α
)
,
ϕ
2
(
α
)
,
…
,
ϕ
n
-
1
(
α
)
} is a normal basis for R
′ over R.
LetA
=
{
α
0
,
α
1
,
…
,
α
l
-
1
} be a normal basis of R
′ over R. Let Γ
=
{
η
0
,
η
1
,
…
,
η
n
-
1
}
⊂
R
′ where
(13)
η
j
=
∑
k
=
0
n
-
1
‍
c
j
k
α
k
for some c
j
k
∈
R. Let C
=
[
c
i
j
]; based on [10, Lemma 2.6], Galois ring has invariant basis number. Therefore, the transition matrix between two basis is an invertible square matrix. We have the following characterization.Proposition 6.
Γ is a normal basis of R
′ over R if and only if C is an invertible circulant matrix.Proof.
The proof is similar to the proof of Theorem  1.6 in [9].Ifξ is a root of a basic irreducible polynomial in R
[
x
], then as in [8] we have R
′
=
R
[
ξ
]. Now, let B
=
{
β
0
,
β
1
,
…
,
β
l
-
1
}
⊂
R
′, where β
j
=
ϕ
j
(
β
0
) and
(14)
β
j
=
∑
i
=
0
l
-
1
‍
b
i
j
ξ
i
for some b
i
j
∈
R, for all j
=
0,1
,
…
,
l
-
1. Then we have the following characterization.Proposition 7.
The setB forms a normal basis for R
′ over R if and only if M
B
=
[
b
i
j
] is an invertible matrix and β
k
=
ϕ
k
(
β
0
) for all k
=
0,1
,
…
,
l
-
1.Now, letA
=
{
ϕ
k
(
α
)
∣
k
=
0,1
,
…
,
l
-
1
} be a normal basis for R
′ over R. As before, we can write down uniquely β
=
(
b
0
,
b
1
,
…
,
b
l
-
1
) and ζ
=
(
a
0
,
a
1
,
…
,
a
l
-
1
) for some a
i
,
b
i
∈
R, where i
=
0
,
…
,
l
-
1, with respect to normal basis A. We are also able to represent ω
=
ζ
·
β
=
(
c
0
,
c
1
,
…
,
c
l
-
1
), with respect to the above normal basis. Therefore, we would like to know how to write every coordinate of ω in terms of a
j and b
j. Let
(15)
ϕ
i
ϕ
j
=
∑
k
=
0
l
-
1
‍
t
i
j
(
k
)
ϕ
k
(
α
)
for some t
i
j
(
k
); then, we will have
(16)
c
k
=
∑
i
‍
∑
j
‍
a
i
b
j
t
i
j
(
k
)
=
ζ
T
k
β
,
0
≤
k
≤
l
-
1
,
where T
k
=
[
t
i
j
(
k
)
] is an l-by-l matrix over R. Then, we would like to know how many nonzero entries in every matrix in the collection {
T
k
=
(
t
i
j
(
k
)
)
}, which calledcomplexity of normal basis A.Definition 8.
Letc
A
(
k
) be the number of nonzero entries in the matrix T
k. Then, c
A
(
k
) is called the complexity of the matrix T
k. Furthermore, if c
A
=
max
⁡
k
c
A
(
k
), then c
A is called the complexity of normal basis A.
Using the generalization of homomorphism in (4) and [8, Lemma 14.31], we have that ϕ
¯ is the Frobenius automorphism in finite field F
p
m
l over F
p
m. In fact, Gal
(
R
′
/
R
) is isomorphic as a group to Gal
(
F
p
m
l
/
F
p
m
) via the above homomorphism; see [8, Theorem 14.32]. Now, consider (15)
(17)
ϕ
¯
(
ϕ
i
(
α
)
¯
ϕ
j
(
α
)
¯
)
-
r
=
(
ϕ
i
(
α
)
¯
ϕ
j
(
α
)
¯
)
p
-
m
r
=
∑
k
=
0
l
-
1
‍
t
i
j
(
k
)
¯
ϕ
k
-
r
(
α
)
¯
which implies
(18)
t
i
j
(
r
)
¯
=
t
i
-
r
,
j
-
r
(
0
)
¯
,
0
≤
r
≤
l
-
1
.
Then we will have the following result.Proposition 9.
Ifc
A
(
k
) is the complexity for T
k, then c
A
(
k
)
≥
2
l
-
1.Proof.
Note that, by Theorems4 and 5, α
¯ is also a generator of normal basis for F
p
m
l over F
p
m. Therefore, A
¯ is a normal basis for F
p
m
l over F
p
m. We will consider c
A
(
0
) first. Let c
A
0
¯ be the number of nonzero entries in T
0
¯ and let T be the multiplication table for A
¯. By Theorem  5.1 in [9], we have the number of nonzero entries in T; that is, c
A
¯, satisfies c
A
¯
≥
2
l
-
1 which implies c
A
(
0
)
¯
≥
2
l
-
1. Therefore, we have c
A
(
0
)
≥
2
l
-
1. Now, by (18), we have the conclusion for all k.From the above result, we have an immediate consequence regarding the complexity of normal basis in Galois rings as follows.Corollary 10.
For any normal basisA of R
′ over R, one has c
A
≥
2
l
-
1.


## 2.2. Self-Dual Normal Basis

A dual basis of a basis is defined using a map called trace. We define trace overR as follows:
(19)
T
R
′
/
R
(
β
)
=
∑
i
=
0
l
-
1
‍
ϕ
i
(
β
)
for every β
∈
R
′. More properties of trace function can be found in [8]. The definition of dual basis is as follows.Definition 11.
LetA
=
{
α
0
,
α
1
,
…
,
α
l
-
1
} and B
=
{
β
0
,
β
1
,
…
,
β
l
-
1
} be two bases of R
′ over R as a free-module. We say that B is a dual of A if
(20)
T
R
′
/
R
(
α
i
β
j
)
=
δ
i
j
for all i
,
j, where δ
i
j is Kronecker’s delta function.One has the following properties for dual basis which are similar to the properties in [11].Lemma 12.
IfA
=
{
α
0
,
α
1
,
…
,
α
l
-
1
} and B
=
{
β
0
,
β
1
,
…
,
β
l
-
1
} are two bases which are dual to each other, then one has the following.(1)
For everyv
∈
R
′ one has
(21)
v
=
∑
i
=
0
l
-
1
‍
T
R
′
/
R
(
α
i
v
)
β
i
=
∑
i
=
0
l
-
1
‍
T
R
′
/
R
(
β
i
v
)
α
i
.
(2)
T
R
′
/
R
(
α
i
)
T
R
′
/
R
(
β
i
)
=
1, for all i
=
0
,
…
,
l
-
1.Lemma 13.
There always exists a unique dual basis for any basis ofR
′ over R.Proof.
This lemma follows from the fact thatT
R
′
/
R is a surjective map. The rest of the proof is similar to the proof of Theorem  1.1 in [9].The following lemma is similar to [9, Corollary 1.4].Lemma 14.
IfA
=
{
α
0
,
α
1
,
…
,
α
l
-
1
} is a normal basis of R
′ over R and B
=
{
β
0
,
β
1
,
…
,
β
l
-
1
} is a dual basis for A, then B is also a normal basis.Self-dual normal basis is a normal basis which is equal to its unique dual basis. Bagio et al. [12] show that there always exist self-dual normal basis in an extension of a local ring of odd order. Therefore, there always exist self-dual normal bases of R
′ over R when l is odd, since Galois rings are local rings. Now, we will give a way to obtain self-dual normal basis generator of R
′ over R whenever |
G
| is odd, where G is the Galois group of R
′ over R.LetR
[
G
]
=
{
∑
i
=
0
l
-
1
‍
a
i
ϕ
i
∣
a
i
∈
R
}; then, we can show that R
[
G
] is an algebra over R. For v
=
∑
i
=
0
l
-
1
‍
a
i
ϕ
i, we define conjugate of v as v
¯
=
∑
i
=
0
l
-
1
‍
a
i
ϕ
-
i. The following theorem gives the generator of self-dual normal basis for R
′ over R.Theorem 15.
(1) Letα be a normal basis generator for in R
′ over R. If v
∈
R
[
G
] satisfies
(22)
v
v
¯
=
∑
i
=
0
l
-
1
‍
T
R
′
/
R
(
α
ϕ
i
(
α
)
)
ϕ
i
then v has an inverse in R
[
G
].
(2) The mappingφ
α
:
v
↦
v
-
1
∘
α gives a one-to-one correspondence between the set of solutions for (22) and the set of elements in R
′ which generate self-dual normal basis.Proof.
The proof of this theorem is similar to the proof of [4, Theorem 2.5].The following proposition gives us a way to findv which satisfies (22).Proposition 16.
Ifv
v
¯
=
∑
i
=
0
l
-
1
‍
∑
j
=
0
l
-
1
‍
a
i
a
j
ϕ
(
i
-
j
)
mod
⁡
l
=
∑
k
=
0
l
-
1
‍
b
k
ϕ
k, then
(23)
b
k
=
∑
j
=
0
l
-
1
‍
a
(
k
+
j
)
mod
⁡
l
a
j
for all k
=
0,1
,
2
,
…
,
l
-
1.Therefore, based on the previous proposition,v
∈
R
[
G
] which satisfies (22) are the solutions of the following system of polymomials:
(24)
∑
i
=
0
l
-
1
‍
a
i
2
-
T
R
′
/
R
(
α
α
)
=
0
,
∑
i
=
0
l
-
1
‍
a
i
a
(
i
+
1
)
mod
⁡
l
-
T
R
′
/
R
(
ϕ
(
α
)
α
)
=
0
,
⋮
∑
i
=
0
l
-
1
‍
a
i
a
(
i
+
k
)
mod
⁡
l
-
T
R
′
/
R
(
ϕ
k
(
α
)
α
)
=
0
,
⋮
∑
i
=
0
l
-
1
‍
a
i
a
(
i
+
l
-
1
)
mod
⁡
l
-
T
R
′
/
R
(
ϕ
l
-
1
(
α
)
α
)
=
0
.


## 3. Connection between Self-Dual Normal Basis and Orthogonal Circulant Matrices

In this section we will show that the generators of self-dual normal basis forR
′ over R are closely related to invertible, circulant, and orthogonal matrix over Galois ring R. Therefore, the enumeration of self-dual normal basis for R
′ over R is just the enumeration of the elements of the set of all invertible, circulant, and orthogonal matrices over R with suitable size. The following proposition gives the easiest way to enumerate the solutions of system (24).Proposition 17.
Solutions of the system (24) has a one-to-one correspondence with the solutions of the following system:
(25)
∑
i
=
0
l
-
1
‍
x
i
2
-
1
=
0
,
∑
i
=
0
l
-
1
‍
x
i
x
(
i
+
1
)
mod
⁡
l
-
0
=
0
,
⋮
∑
i
=
0
l
-
1
‍
x
i
x
(
i
+
k
)
mod
⁡
l
-
0
=
0
,
⋮
∑
i
=
0
l
-
1
‍
x
i
x
(
i
+
l
-
1
)
mod
⁡
l
-
0
=
0
.Proof.
Leta
∈
R
l be a solution of (24). By Proposition 16, we will have the corresponding element v
a
∈
R
[
G
], and v
a
-
1
(
α
) is a generator of self-dual normal basis by Theorem 15. Then, we can define
(26)
ψ
:
β
⟼
v
a
β
,
where β
∈
R
[
G
] is related to a solution of (25) by φ. Consider
(27)
(
v
a
β
)
β
¯
v
a
¯
=
v
a
v
a
¯
=
∑
i
=
0
l
-
1
‍
T
R
′
/
R
(
α
ϕ
i
(
α
)
)
ϕ
i
.
Consequently, the images of ψ are related to the solutions of (24). Moreover, since v
a is nonzero, we have ψ is a one-to-one correspondence. Furthermore, if θ is an element in R
[
G
] which is related to a solution of (24), then λ
=
v
a
-
1
θ satisfies
(28)
λ
λ
¯
=
v
a
-
1
θ
θ
¯
v
a
-
1
¯
=
v
a
-
1
r
v
a
-
1
¯
=
1
.
Therefore, λ is an element of R
[
G
] which is related to a solution of (25). Consequently, given θ
∈
R
[
G
] which is related to a solution of (24), then we can choose λ
=
v
a
-
1
θ such that ψ
(
λ
)
=
θ. In other words, ψ is a bijection.LetOC
(
l
,
R
) be the set of all  l-by-l  invertible, circulant, and orthogonal matrices over R
=
GR
(
p
s
,
p
s
m
). The following proposition gives the connection between the number of solutions of system (25) and |
OC
(
l
,
R
)
|.Proposition 18.
The number of solutions of system (25) is |
O
C
(
l
,
R
)
|.Proof.
The elementv
∈
R
[
G
] as in (25) satisfies
(29)
v
v
¯
=
1
.
By using the map φ, the last equation becomes C
v
C
v
t
=
I. Therefore, C
v
∈
OC
(
l
,
R
). Since every solutions of (25) is uniquely related to v which satisfies (29), we have that the number of solutions of system (25) is |
OC
(
l
,
R
)
|.The following theorem is the corollary of two previous propositions.Theorem 19.
The number of self-dual normal basis ofR
′ over R is (
1
/
l
)
|
O
C
(
l
,
R
)
|.


## 4. Encoding Cyclic Codes overZ
p
k

### 4.1. Cyclic Codes overZ
p
k, Discrete Fourier Transform, and Galois Rings

Definition 20.
A cyclic codeC over Z
p
k, where p is a prime, of length n is an ideal of residue class polynomial ring Z
p
k
[
x
]
/
(
x
n
-
1
).In [13], cyclic codes over Z
p
k were characterized using the following discrete Fourier transform (DFT).Definition 21.
Let(
n
,
p
)
=
1 and a
¯
=
(
a
0
,
a
1
,
…
,
a
n
-
1
)
∈
Z
p
k
n. The DFT of a
¯ is defined as
(30)
A
j
=
∑
i
=
0
n
-
1
‍
a
i
α
i
j
,
j
=
0,1
,
…
,
n
-
1
,
where α is a primitive nth root of unity in the Galois ring GR
(
p
k
,
p
k
r
) and r is the least integer such that n divides p
r
-
1.Note that we can calculate the inverse discrete Fourier transform by the following formula:(31)
a
i
=
∑
j
=
0
n
-
1
‍
A
j
α
-
i
j
,
0
≤
i
≤
n
-
1
.
Moreover, the vector A
¯
=
(
A
0
,
A
1
,
…
,
A
n
-
1
) is called the transform vector or spectrum of a
¯, and the components A
j, j
=
0,1
,
…
,
n
-
1, are called the DFT coefficients or spectral components of a
¯. Note that all the n-tuples of GR
(
p
k
,
p
k
r
) which are DFT vectors of some n-tuple over Z
p
k satisfy
(32)
A
p
j
=
ϕ
(
A
j
)
for all j, where ϕ is the generalized Frobenius automorphism on the Galois ring GR
(
p
k
,
p
k
r
); see [13].As we can see, the DFT mapsZ
p
k
n to a subset R
τ of GR
(
p
k
,
p
k
r
). Sundar Rajan and Siddiqi [13] show that
(33)
R
τ
≅
⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
)
,
where t is the number of conjugacy classes for the integer n and r
i are the exponents of the conjugacy classses, for all i
=
1
,
…
,
t. Therefore, by convolution property of DFT, we have
(34)
Z
p
k
[
x
]
(
x
n
-
1
)
≅
⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
)
.
Hence, a cyclic code with length n over Z
p
k consists of the inverse DFT coefficients of all vectors of the subring of GR
(
p
k
,
p
k
r
) which is isomorphic to ⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
) whose specified spectral components are the elements of ideal p
j
i
GR
(
p
k
,
p
k
r
i
), 0
≤
j
i
≤
k, for i
=
1,2
,
…
,
t. Consequently, if C is a cyclic codes over Z
p
k, then we have
(35)
C
=
⨁
i
=
1
t
p
j
i
GR
(
p
k
,
p
k
r
i
)
,
0
≤
j
i
≤
k
.
Therefore, decoding of cyclic codes over Z
p
k can be accomplished by calculating inverse DFT in the Galois ring GR
(
p
k
,
p
k
r
).


### 4.2. Encoding Algorithm

As in the previous subsection, we know that every cyclic codeC can be associated with an ideal ⨁
i
=
1
t
p
j
i
GR
(
p
k
,
p
k
r
i
), 0
≤
j
i
≤
k in ⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
). Hence, if we work in ⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
), then we can encode a cyclic code C via inverse discrete Fourier transform. Therefore, our main purpose in this part is to formulate an algorithm for calculating inverse discrete Fourier transform. Before we explain the encoding algorithm, we will need the following materials first.The following lemma is a direct consequence from the results in the last subsection.Lemma 22.
The inverse DFTa
¯ of a vector A
¯
=
(
A
0
,
A
1
,
…
,
A
n
-
1
)
∈
G
R
(
p
k
,
p
k
r
) is a vector with components in Z
p
k if and only if
(36)
A
p
j
=
ϕ
(
A
j
)
for all j
=
0,1
,
…
,
n
-
1, and
(37)
ϕ
e
(
A
j
)
=
A
j
for all j, where e is the exponent of the conjugacy class which contains j.Therefore, the DFT spectrum is determined by one spectral coefficient for each conjugacy class. Our approach on calculating inverse DFT is similar to Fumy’s approach in [2] over finite fields, but now we apply it over Galois rings.LetC
=
⨁
l
=
1
s
p
j
i
GR
(
p
k
,
p
k
r
i
l
) be an ideal in GR
(
p
k
,
p
k
r
). From the previous subsection, we can say that C is a cyclic code in spectral domain from s conjugacy classes of n. Then C must be an ideal in GR
(
p
k
,
p
k
m
), where m is a least common multiple of r
i
1
,
r
i
2
,
…
,
r
i
s.LetA
¯
=
(
A
0
,
A
1
,
…
,
A
n
-
1
) be a DFT spectrum of a vector a
¯
=
(
a
0
,
a
1
,
…
,
a
n
-
1
)
∈
Z
p
k
n. We can associate A
¯ and a
¯ with polynomials
(38)
A
(
x
)
=
∑
i
=
0
n
-
1
‍
A
i
x
i
,
a
(
x
)
=
∑
i
=
0
n
-
1
‍
a
i
x
i
,
respectively. Let B
=
{
β
0
,
β
1
,
…
,
β
m
-
1
} be a normal basis of GR
(
p
k
,
p
k
m
) over Z
p
k, where β
i
=
ϕ
i
(
β
0
). We can write every spectral coefficient as follows:
(39)
A
i
=
∑
j
=
0
m
-
1
‍
e
i
j
β
j
,
where e
i
j
∈
Z
p
k. Define
(40)
e
j
(
x
)
=
∑
i
=
0
n
-
1
‍
e
i
j
x
i
,
for
0
≤
j
≤
n
-
1
.
From Lemma 22, we will have e
j
+
1
(
x
)
=
ϕ
(
e
j
(
x
)
). Therefore, a
(
x
) can be obtained from e
0
(
x
). The following theorem is similar to [2, Theorem 1].Theorem 23.
LetD
=
{
δ
0
,
δ
1
,
…
,
δ
m
-
1
} be a basis of G
R
(
p
k
,
p
k
m
) over Z
p
k which is dual to B, and let
(41)
e
0
(
α
)
=
∑
j
=
0
m
-
1
‍
u
j
δ
j
,
where u
j
∈
Z
p
k, for all j. Then A
(
α
)
=
u
0.The following corollary is an immediate consequence of the above theorem.Corollary 24.
A
(
α
i
)
=
u
m
-
j, for 1
≤
j
≤
m and i
=
p
j.Recall that ifh
(
x
) is a monic basic irreducible polynomial over Z
p
k with minimal degree, where α is a root of h
(
x
), then Z
p
k
[
x
]
/
(
h
(
x
)
)
=
GR
(
p
k
,
p
k
deg
⁡
(
h
(
x
)
)
) with basis {
1
,
α
,
α
2
,
…
,
α
deg
⁡
(
h
)
-
1
}. Therefore, we have the following lemma.Lemma 25.
Leth
(
x
) be a monic basic irreducible polynomial with minimal degree where α
∈
G
R
(
p
k
,
p
k
r
) is a root of h
(
x
). Then, for any polynomial g
(
x
) over Z
p
k,
(42)
g
(
α
)
=
(
g
(
x
)
mod
⁡
h
(
x
)
)
(
α
)
∈
G
R
(
p
k
,
deg
⁡
(
h
(
x
)
)
)
and g
(
α
) is given in basis {
1
,
α
,
…
,
α
deg
⁡
(
h
)
-
1
} by the deg
⁡
⁡
(
h
(
x
)
) coefficients of g
(
x
)
mod
⁡
h
(
x
).Hence, we have the following algorithm to calculate inverse DFT overGR
(
p
k
,
p
k
m
) due to Fumy [2].(1)
Represent the coefficients of DFT spectrumA
(
x
) with respect to a normal basis B of GR
(
p
k
,
p
k
m
) over Z
p
k and generate the polynomial e
0
(
x
).
(2)
Reducee
0
(
x
) modulo the monic basic irreducible minimal polynomial of the nth root of unity α over Z
p
k.
(3)
Transform resulting residues into the normal basisD dual to B which yields the coefficients of polynomial a
(
x
) according to Corollary 24.Recall that, whenm is an odd integer, the Galois ring GR
(
p
k
,
p
k
m
) has self-dual normal basis over Z
p
k. Therefore, we can make the previous algorithm complete by using only one normal basis as follows.(1)
Given normal basisB, solve (25) to obtain a generator for self-dual normal basis B
′ for GR
(
p
k
,
p
k
m
) over Z
p
k.
(2)
Represent the coefficients of DFT spectrumA
(
x
) with respect to a normal basis B
′ of GR
(
p
k
,
p
k
m
) over Z
p
k and generate the polynomial e
0
(
x
).
(3)
Reducee
0
(
x
) modulo the monic basic irreducible minimal polynomial of the nth root of unity α over Z
p
k.
(4)
Transform resulting residues into basisB
′ which yields the coefficients of polynomial a
(
x
) according to Corollary 24.Note that the algorithm can only calculate some a
i which are in the scope of Corollary 24, and for the rest of a
i, we can calculate using the formula of inverse discrete Fourier transform.Example 26.
We would like to encode cyclic codes of length3 over Z
2. So, we let p
=
2, k
=
1, and n
=
3. Then we will have r
=
2, and the conjugacy classes are {
0
} and {
1,2
}. Therefore, m
=
2 and
(43)
R
τ
=
Z
2
⊕
F
2
2
.
We can show that B
=
{
ω
,
ω
+
1
}, where ω is a root of x
2
+
x
+
1, is a self-dual normal basis for F
2
2 over Z
2. Also, α
=
ω is the 3rd root of unity in F
2
2. First, if we choose ideal {
0
}
⊕
F
2
2, then every A
∈
{
0
}
⊕
F
2
2, and we can write down A
=
(
0
,
A
1
,
A
2
=
A
1
2
) for some A
i
∈
F
2
2. Let a
=
(
a
0
,
a
1
,
a
2
) be the codeword which we would like to find and A
1
=
e
10
ω
+
e
11
(
ω
+
1
); then, e
20
=
e
11 and e
21
=
e
10, because A
2
=
A
1
2 (from conjugacy property). Also, e
00
=
e
01
=
0, because A
0
=
0 which implies e
0
(
x
)
=
e
10
x
+
e
11
x
2 and e
0
(
α
)
=
e
10
ω
+
e
11
(
ω
+
1
). By Corollary 24, we have a
1
=
e
11 and a
2
=
e
10. We can calculate a
0 using inverse DFT formula, and we have a
0
=
e
11
+
e
10. Consequently, we have a
=
(
e
11
+
e
10
,
e
11
,
e
10
) and a
(
x
)
=
(
e
11
+
e
10
(
1
+
x
)
)
(
x
+
1
)
∈
〈
x
+
1
〉. Hence, our calculation gives a cyclic code C
=
〈
x
+
1
〉.Second, if we choose idealI
=
Z
2
⊕
{
0
}, then A
=
(
A
0
,
0,0
) for all A
∈
I, where A
0
∈
Z
2, because the ideal {
0
} represents the conjugacy class {
1,2
} and the ideal Z
2 represents the conjugacy class {
0
}. Since 1
=
ω
+
ω
+
1, we have e
00
=
e
01
=
A
0 and e
i
j
=
0 for i
=
1,2 and j
=
0,1. Consequently, e
0
(
x
)
=
A
0 and e
0
(
α
)
=
A
0
ω
+
A
0
(
ω
+
1
). Therefore, by similar way as before, we have a
0
=
a
1
=
a
2
=
A
0, a
=
(
A
0
,
A
0
,
A
0
), and a
(
x
)
=
A
0
(
x
2
+
x
+
1
)
∈
〈
x
2
+
x
+
1
〉. Hence, we have cyclic code C
=
〈
x
2
+
x
+
1
〉.


## 4.1. Cyclic Codes overZ
p
k, Discrete Fourier Transform, and Galois Rings

Definition 20.
A cyclic codeC over Z
p
k, where p is a prime, of length n is an ideal of residue class polynomial ring Z
p
k
[
x
]
/
(
x
n
-
1
).In [13], cyclic codes over Z
p
k were characterized using the following discrete Fourier transform (DFT).Definition 21.
Let(
n
,
p
)
=
1 and a
¯
=
(
a
0
,
a
1
,
…
,
a
n
-
1
)
∈
Z
p
k
n. The DFT of a
¯ is defined as
(30)
A
j
=
∑
i
=
0
n
-
1
‍
a
i
α
i
j
,
j
=
0,1
,
…
,
n
-
1
,
where α is a primitive nth root of unity in the Galois ring GR
(
p
k
,
p
k
r
) and r is the least integer such that n divides p
r
-
1.Note that we can calculate the inverse discrete Fourier transform by the following formula:(31)
a
i
=
∑
j
=
0
n
-
1
‍
A
j
α
-
i
j
,
0
≤
i
≤
n
-
1
.
Moreover, the vector A
¯
=
(
A
0
,
A
1
,
…
,
A
n
-
1
) is called the transform vector or spectrum of a
¯, and the components A
j, j
=
0,1
,
…
,
n
-
1, are called the DFT coefficients or spectral components of a
¯. Note that all the n-tuples of GR
(
p
k
,
p
k
r
) which are DFT vectors of some n-tuple over Z
p
k satisfy
(32)
A
p
j
=
ϕ
(
A
j
)
for all j, where ϕ is the generalized Frobenius automorphism on the Galois ring GR
(
p
k
,
p
k
r
); see [13].As we can see, the DFT mapsZ
p
k
n to a subset R
τ of GR
(
p
k
,
p
k
r
). Sundar Rajan and Siddiqi [13] show that
(33)
R
τ
≅
⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
)
,
where t is the number of conjugacy classes for the integer n and r
i are the exponents of the conjugacy classses, for all i
=
1
,
…
,
t. Therefore, by convolution property of DFT, we have
(34)
Z
p
k
[
x
]
(
x
n
-
1
)
≅
⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
)
.
Hence, a cyclic code with length n over Z
p
k consists of the inverse DFT coefficients of all vectors of the subring of GR
(
p
k
,
p
k
r
) which is isomorphic to ⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
) whose specified spectral components are the elements of ideal p
j
i
GR
(
p
k
,
p
k
r
i
), 0
≤
j
i
≤
k, for i
=
1,2
,
…
,
t. Consequently, if C is a cyclic codes over Z
p
k, then we have
(35)
C
=
⨁
i
=
1
t
p
j
i
GR
(
p
k
,
p
k
r
i
)
,
0
≤
j
i
≤
k
.
Therefore, decoding of cyclic codes over Z
p
k can be accomplished by calculating inverse DFT in the Galois ring GR
(
p
k
,
p
k
r
).


## 4.2. Encoding Algorithm

As in the previous subsection, we know that every cyclic codeC can be associated with an ideal ⨁
i
=
1
t
p
j
i
GR
(
p
k
,
p
k
r
i
), 0
≤
j
i
≤
k in ⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
). Hence, if we work in ⨁
i
=
1
t
GR
(
p
k
,
p
k
r
i
), then we can encode a cyclic code C via inverse discrete Fourier transform. Therefore, our main purpose in this part is to formulate an algorithm for calculating inverse discrete Fourier transform. Before we explain the encoding algorithm, we will need the following materials first.The following lemma is a direct consequence from the results in the last subsection.Lemma 22.
The inverse DFTa
¯ of a vector A
¯
=
(
A
0
,
A
1
,
…
,
A
n
-
1
)
∈
G
R
(
p
k
,
p
k
r
) is a vector with components in Z
p
k if and only if
(36)
A
p
j
=
ϕ
(
A
j
)
for all j
=
0,1
,
…
,
n
-
1, and
(37)
ϕ
e
(
A
j
)
=
A
j
for all j, where e is the exponent of the conjugacy class which contains j.Therefore, the DFT spectrum is determined by one spectral coefficient for each conjugacy class. Our approach on calculating inverse DFT is similar to Fumy’s approach in [2] over finite fields, but now we apply it over Galois rings.LetC
=
⨁
l
=
1
s
p
j
i
GR
(
p
k
,
p
k
r
i
l
) be an ideal in GR
(
p
k
,
p
k
r
). From the previous subsection, we can say that C is a cyclic code in spectral domain from s conjugacy classes of n. Then C must be an ideal in GR
(
p
k
,
p
k
m
), where m is a least common multiple of r
i
1
,
r
i
2
,
…
,
r
i
s.LetA
¯
=
(
A
0
,
A
1
,
…
,
A
n
-
1
) be a DFT spectrum of a vector a
¯
=
(
a
0
,
a
1
,
…
,
a
n
-
1
)
∈
Z
p
k
n. We can associate A
¯ and a
¯ with polynomials
(38)
A
(
x
)
=
∑
i
=
0
n
-
1
‍
A
i
x
i
,
a
(
x
)
=
∑
i
=
0
n
-
1
‍
a
i
x
i
,
respectively. Let B
=
{
β
0
,
β
1
,
…
,
β
m
-
1
} be a normal basis of GR
(
p
k
,
p
k
m
) over Z
p
k, where β
i
=
ϕ
i
(
β
0
). We can write every spectral coefficient as follows:
(39)
A
i
=
∑
j
=
0
m
-
1
‍
e
i
j
β
j
,
where e
i
j
∈
Z
p
k. Define
(40)
e
j
(
x
)
=
∑
i
=
0
n
-
1
‍
e
i
j
x
i
,
for
0
≤
j
≤
n
-
1
.
From Lemma 22, we will have e
j
+
1
(
x
)
=
ϕ
(
e
j
(
x
)
). Therefore, a
(
x
) can be obtained from e
0
(
x
). The following theorem is similar to [2, Theorem 1].Theorem 23.
LetD
=
{
δ
0
,
δ
1
,
…
,
δ
m
-
1
} be a basis of G
R
(
p
k
,
p
k
m
) over Z
p
k which is dual to B, and let
(41)
e
0
(
α
)
=
∑
j
=
0
m
-
1
‍
u
j
δ
j
,
where u
j
∈
Z
p
k, for all j. Then A
(
α
)
=
u
0.The following corollary is an immediate consequence of the above theorem.Corollary 24.
A
(
α
i
)
=
u
m
-
j, for 1
≤
j
≤
m and i
=
p
j.Recall that ifh
(
x
) is a monic basic irreducible polynomial over Z
p
k with minimal degree, where α is a root of h
(
x
), then Z
p
k
[
x
]
/
(
h
(
x
)
)
=
GR
(
p
k
,
p
k
deg
⁡
(
h
(
x
)
)
) with basis {
1
,
α
,
α
2
,
…
,
α
deg
⁡
(
h
)
-
1
}. Therefore, we have the following lemma.Lemma 25.
Leth
(
x
) be a monic basic irreducible polynomial with minimal degree where α
∈
G
R
(
p
k
,
p
k
r
) is a root of h
(
x
). Then, for any polynomial g
(
x
) over Z
p
k,
(42)
g
(
α
)
=
(
g
(
x
)
mod
⁡
h
(
x
)
)
(
α
)
∈
G
R
(
p
k
,
deg
⁡
(
h
(
x
)
)
)
and g
(
α
) is given in basis {
1
,
α
,
…
,
α
deg
⁡
(
h
)
-
1
} by the deg
⁡
⁡
(
h
(
x
)
) coefficients of g
(
x
)
mod
⁡
h
(
x
).Hence, we have the following algorithm to calculate inverse DFT overGR
(
p
k
,
p
k
m
) due to Fumy [2].(1)
Represent the coefficients of DFT spectrumA
(
x
) with respect to a normal basis B of GR
(
p
k
,
p
k
m
) over Z
p
k and generate the polynomial e
0
(
x
).
(2)
Reducee
0
(
x
) modulo the monic basic irreducible minimal polynomial of the nth root of unity α over Z
p
k.
(3)
Transform resulting residues into the normal basisD dual to B which yields the coefficients of polynomial a
(
x
) according to Corollary 24.Recall that, whenm is an odd integer, the Galois ring GR
(
p
k
,
p
k
m
) has self-dual normal basis over Z
p
k. Therefore, we can make the previous algorithm complete by using only one normal basis as follows.(1)
Given normal basisB, solve (25) to obtain a generator for self-dual normal basis B
′ for GR
(
p
k
,
p
k
m
) over Z
p
k.
(2)
Represent the coefficients of DFT spectrumA
(
x
) with respect to a normal basis B
′ of GR
(
p
k
,
p
k
m
) over Z
p
k and generate the polynomial e
0
(
x
).
(3)
Reducee
0
(
x
) modulo the monic basic irreducible minimal polynomial of the nth root of unity α over Z
p
k.
(4)
Transform resulting residues into basisB
′ which yields the coefficients of polynomial a
(
x
) according to Corollary 24.Note that the algorithm can only calculate some a
i which are in the scope of Corollary 24, and for the rest of a
i, we can calculate using the formula of inverse discrete Fourier transform.Example 26.
We would like to encode cyclic codes of length3 over Z
2. So, we let p
=
2, k
=
1, and n
=
3. Then we will have r
=
2, and the conjugacy classes are {
0
} and {
1,2
}. Therefore, m
=
2 and
(43)
R
τ
=
Z
2
⊕
F
2
2
.
We can show that B
=
{
ω
,
ω
+
1
}, where ω is a root of x
2
+
x
+
1, is a self-dual normal basis for F
2
2 over Z
2. Also, α
=
ω is the 3rd root of unity in F
2
2. First, if we choose ideal {
0
}
⊕
F
2
2, then every A
∈
{
0
}
⊕
F
2
2, and we can write down A
=
(
0
,
A
1
,
A
2
=
A
1
2
) for some A
i
∈
F
2
2. Let a
=
(
a
0
,
a
1
,
a
2
) be the codeword which we would like to find and A
1
=
e
10
ω
+
e
11
(
ω
+
1
); then, e
20
=
e
11 and e
21
=
e
10, because A
2
=
A
1
2 (from conjugacy property). Also, e
00
=
e
01
=
0, because A
0
=
0 which implies e
0
(
x
)
=
e
10
x
+
e
11
x
2 and e
0
(
α
)
=
e
10
ω
+
e
11
(
ω
+
1
). By Corollary 24, we have a
1
=
e
11 and a
2
=
e
10. We can calculate a
0 using inverse DFT formula, and we have a
0
=
e
11
+
e
10. Consequently, we have a
=
(
e
11
+
e
10
,
e
11
,
e
10
) and a
(
x
)
=
(
e
11
+
e
10
(
1
+
x
)
)
(
x
+
1
)
∈
〈
x
+
1
〉. Hence, our calculation gives a cyclic code C
=
〈
x
+
1
〉.Second, if we choose idealI
=
Z
2
⊕
{
0
}, then A
=
(
A
0
,
0,0
) for all A
∈
I, where A
0
∈
Z
2, because the ideal {
0
} represents the conjugacy class {
1,2
} and the ideal Z
2 represents the conjugacy class {
0
}. Since 1
=
ω
+
ω
+
1, we have e
00
=
e
01
=
A
0 and e
i
j
=
0 for i
=
1,2 and j
=
0,1. Consequently, e
0
(
x
)
=
A
0 and e
0
(
α
)
=
A
0
ω
+
A
0
(
ω
+
1
). Therefore, by similar way as before, we have a
0
=
a
1
=
a
2
=
A
0, a
=
(
A
0
,
A
0
,
A
0
), and a
(
x
)
=
A
0
(
x
2
+
x
+
1
)
∈
〈
x
2
+
x
+
1
〉. Hence, we have cyclic code C
=
〈
x
2
+
x
+
1
〉.


## 5. Conclusion

In this paper we show that the generator of normal basis over Galois rings can be constructed using the generator of normal basis over Galois fields, and weakly self-dual normal basis over Galois rings has similar properties to the one over finite fields. We also can have self-dual normal basis generator forR
′ over R simply by solving a particular system of polynomials, and the number of self-dual normal basis for R
′ over R is (
1
/
l
)
|
OC
(
l
,
R
)
|. As an application, we may use normal basis and self-dual normal basis to encode certain cyclic codes over Z
p
k.



---

*Source: 258187-2014-09-01.xml*