6.5 Reed–Solomon and GRS Codes
139
g(x) = lcm{M
(b)
(x), M
(b+1)
(x), . . . , M
(b+δ−2)
(x)},
i.e., g(x) is the monic polynomial of smallest degree over F q having α
b
, α
b+1
,
. . . , α
b+δ−2 as zeros.
Definition 6.5.1 A Reed–Solomon (RS) code over F q is a BCH code of length n =
q − 1.
The dimension of a RS code is k = n − deg(g(x)) = n − δ + 1, and its minimum
distance coincides with its designed distance, i.e., d = n − k + 1. Thus, a RS code is
a maximum-distance-separable code. Let us next define the concept of generalized
RS code.
Definition 6.5.2 Choose n distinct elements a i of F q m and form the vector a =
(a 1 , a 2 , . . . , a n ). After this, choose n nonzero elements v i ∈ F q m and form the vector
v = (v 1 , v 2 , . . . , v n ). Then the generalized Reed–Solomon (GRS) code GRS n,k (a, v)
consists of all vectors (v 1 f (a 1 ), v 2 f (a 2 ), . . . , v n f (a n )), where f (x) ranges over all
polynomials of degree at most k − 1 with coefficients from F q m . More precisely,
GRS n,k (a, v) = {(v 1 f (a 1 ), v 2 f (a 2 ), . . . , v n f (a n ))|
f (x) ∈ F q [x], deg( f (x)) ≤ k − 1},
where 1 ≤ k ≤ n and 2 < n ≤ q
m .
The code GRS n,k (a, v) is linear over F q m and it is a MDS code with parameters
[n, k, n − k + 1] q m .
Theorem 6.5.1 The Euclidean dual GRS
⊥
n,k (a, v) of an GRS code is also the GRS
code GRS n,k (a, v) is the GRS code GRS n,n−k (a, u), where u = (u 1 , u 2 , . . . , u n ),
(u i ∈ F q m , i = 1, 2, . . . , n) and u i is given by u
−1
i = v i
j =i (a i − a j ) for all i =
1, 2, . . . , n.
6.5.2 Construction I
In this subsection, we utilize classical RS codes to obtain AQECCs. We first consider
the case q = p, where p is a prime. Assume that d ≥ 3 is a fixed integer. The
construction of p-ary quantum codes starts by finding the smallest positive integer
m such that the following inequality p
m
≥ 2d − c − 1 is satisfied, where d > c + 1
and c ≥ 1. This inequality provides the field of smallest cardinality such that each
of the RS codes (of length p
m
− 1) C 1 = [n, k 1 , d 1 ] p m , C 2 = [n, k 2 , d 2 ] p m , C
⊥
2 =
[n, k
⊥
2 , d
⊥
2 ] p m may be constructed such that d 1 = d and d
⊥
2 = d − c, respectively,
and, at the same time, providing the smallest p-ary expansion of C 1 and C 2 with
respect to the basis β of F p m over F p .
For convenience, we only construct AQECCs for c = 1, since the other cases are
analogous to this one. In other words, we construct an RS code C 1 with minimum
139
g(x) = lcm{M
(b)
(x), M
(b+1)
(x), . . . , M
(b+δ−2)
(x)},
i.e., g(x) is the monic polynomial of smallest degree over F q having α
b
, α
b+1
,
. . . , α
b+δ−2 as zeros.
Definition 6.5.1 A Reed–Solomon (RS) code over F q is a BCH code of length n =
q − 1.
The dimension of a RS code is k = n − deg(g(x)) = n − δ + 1, and its minimum
distance coincides with its designed distance, i.e., d = n − k + 1. Thus, a RS code is
a maximum-distance-separable code. Let us next define the concept of generalized
RS code.
Definition 6.5.2 Choose n distinct elements a i of F q m and form the vector a =
(a 1 , a 2 , . . . , a n ). After this, choose n nonzero elements v i ∈ F q m and form the vector
v = (v 1 , v 2 , . . . , v n ). Then the generalized Reed–Solomon (GRS) code GRS n,k (a, v)
consists of all vectors (v 1 f (a 1 ), v 2 f (a 2 ), . . . , v n f (a n )), where f (x) ranges over all
polynomials of degree at most k − 1 with coefficients from F q m . More precisely,
GRS n,k (a, v) = {(v 1 f (a 1 ), v 2 f (a 2 ), . . . , v n f (a n ))|
f (x) ∈ F q [x], deg( f (x)) ≤ k − 1},
where 1 ≤ k ≤ n and 2 < n ≤ q
m .
The code GRS n,k (a, v) is linear over F q m and it is a MDS code with parameters
[n, k, n − k + 1] q m .
Theorem 6.5.1 The Euclidean dual GRS
⊥
n,k (a, v) of an GRS code is also the GRS
code GRS n,k (a, v) is the GRS code GRS n,n−k (a, u), where u = (u 1 , u 2 , . . . , u n ),
(u i ∈ F q m , i = 1, 2, . . . , n) and u i is given by u
−1
i = v i
j =i (a i − a j ) for all i =
1, 2, . . . , n.
6.5.2 Construction I
In this subsection, we utilize classical RS codes to obtain AQECCs. We first consider
the case q = p, where p is a prime. Assume that d ≥ 3 is a fixed integer. The
construction of p-ary quantum codes starts by finding the smallest positive integer
m such that the following inequality p
m
≥ 2d − c − 1 is satisfied, where d > c + 1
and c ≥ 1. This inequality provides the field of smallest cardinality such that each
of the RS codes (of length p
m
− 1) C 1 = [n, k 1 , d 1 ] p m , C 2 = [n, k 2 , d 2 ] p m , C
⊥
2 =
[n, k
⊥
2 , d
⊥
2 ] p m may be constructed such that d 1 = d and d
⊥
2 = d − c, respectively,
and, at the same time, providing the smallest p-ary expansion of C 1 and C 2 with
respect to the basis β of F p m over F p .
For convenience, we only construct AQECCs for c = 1, since the other cases are
analogous to this one. In other words, we construct an RS code C 1 with minimum