6.5 Reed–Solomon and GRS Codes
141
From construction, it follows that C 2 ⊂ C 1 . We know that C
⊥
2 is equivalent to the
code C 3 generated by
g 3 (x) = (x
( p
m −1)
− 1)/g 2 (x) =
α i ∈A
(x − α
i
).
The minimum distance of C
⊥
2 is equal to d − 1, because C 3 is an RS code with
minimum distance d − 1.
Let β be a basis of F p m over F p and let β
⊥ its dual basis. Let us consider the codes
C 1 , C 2 and C
⊥
2 constructed above. Since C 2 ⊂ C 1 , then β(C 2 ) ⊂ β(C 1 ). Because
C 1 has minimum distance d, it follows from Item (i) of Lemma 6.5.1 that β(C 1 ) has
minimum distance greater than or equal to d. The code C
⊥
2 has minimum distance
d − 1. From Item (ii) of Lemma 6.5.1 (applied to C
⊥
2 ) we have [β(C 2 )]
⊥
= β
⊥
(C
⊥
2 ).
Since β
⊥ is a basis of F p m over F p , applying again Item (i) of Lemma 6.5.1, to the
code β
⊥
(C
⊥
2 ), it follows that this code has minimum distance greater than or equal
to d − 1; hence, [β(C 2 )]
⊥ also has minimum distance greater than or equal to d − 1.
Again, from Item (i) of Lemma 6.5.1, the codes β(C 1 ), β(C 2 ) and [β(C 2 )]
⊥ are linear.
The code β(C 1 ) has dimension K 1 = m( p
m
− d) and K 2 = m(d − 2). Applying the
CSS construction we have an AQECC with the required parameters. The proof is
complete.
Let us recall Lemma 4.3.1 of Sect. 4.3
Lemma 6.5.2 Let C = [n, k, d] q m be a linear code over F q m , where q is a prime
power. Let C
⊥ be the dual of the code C. Then the dual code of the q-ary expansion
β(C) of the code C with respect to the basis β is the q-ary expansion β
⊥
(C
⊥
) of the
dual code C
⊥ with respect to β
⊥ .
Hence, by applying the previous result one can extend in a natural way
Theorem 6.5.2.
Theorem 6.5.3 Let q be a prime power. Then there exists an
[[N = m(q
m
− 1), K = m(q
m
− 2d + c + 1), d z ≥ d/d x ≥ (d − c)]] q
AQECC, where d > c + 1, and c ≥ 1, m ≥ 1 are integers.
Proof For c = 1 the proof is that of Theorem 6.5.2. The cases when c > 1 is similar
to such proof and we omit it.
Example 6.5.1 We now construct an 7-ary AQECC with d z ≥ 10 and d x ≥ 9 (c =
1). The codes C 1 , C 2 and C
⊥
2 have length 48 because 2d − 2 = 18 ≤ 7
2 . Let C 1 , C 2
and C
⊥
2 be the codes generated, respectively, by
g 1 (x) = (x − 1)(x − α) · · · (x − α
8
),
g 2 (x) = (x − 1)(x − α) · · · (x − α
39
),
g
⊥
2 (x) = (x − α
40
)(x − α
41
) · · · (x − α
47
).
141
From construction, it follows that C 2 ⊂ C 1 . We know that C
⊥
2 is equivalent to the
code C 3 generated by
g 3 (x) = (x
( p
m −1)
− 1)/g 2 (x) =
α i ∈A
(x − α
i
).
The minimum distance of C
⊥
2 is equal to d − 1, because C 3 is an RS code with
minimum distance d − 1.
Let β be a basis of F p m over F p and let β
⊥ its dual basis. Let us consider the codes
C 1 , C 2 and C
⊥
2 constructed above. Since C 2 ⊂ C 1 , then β(C 2 ) ⊂ β(C 1 ). Because
C 1 has minimum distance d, it follows from Item (i) of Lemma 6.5.1 that β(C 1 ) has
minimum distance greater than or equal to d. The code C
⊥
2 has minimum distance
d − 1. From Item (ii) of Lemma 6.5.1 (applied to C
⊥
2 ) we have [β(C 2 )]
⊥
= β
⊥
(C
⊥
2 ).
Since β
⊥ is a basis of F p m over F p , applying again Item (i) of Lemma 6.5.1, to the
code β
⊥
(C
⊥
2 ), it follows that this code has minimum distance greater than or equal
to d − 1; hence, [β(C 2 )]
⊥ also has minimum distance greater than or equal to d − 1.
Again, from Item (i) of Lemma 6.5.1, the codes β(C 1 ), β(C 2 ) and [β(C 2 )]
⊥ are linear.
The code β(C 1 ) has dimension K 1 = m( p
m
− d) and K 2 = m(d − 2). Applying the
CSS construction we have an AQECC with the required parameters. The proof is
complete.
Let us recall Lemma 4.3.1 of Sect. 4.3
Lemma 6.5.2 Let C = [n, k, d] q m be a linear code over F q m , where q is a prime
power. Let C
⊥ be the dual of the code C. Then the dual code of the q-ary expansion
β(C) of the code C with respect to the basis β is the q-ary expansion β
⊥
(C
⊥
) of the
dual code C
⊥ with respect to β
⊥ .
Hence, by applying the previous result one can extend in a natural way
Theorem 6.5.2.
Theorem 6.5.3 Let q be a prime power. Then there exists an
[[N = m(q
m
− 1), K = m(q
m
− 2d + c + 1), d z ≥ d/d x ≥ (d − c)]] q
AQECC, where d > c + 1, and c ≥ 1, m ≥ 1 are integers.
Proof For c = 1 the proof is that of Theorem 6.5.2. The cases when c > 1 is similar
to such proof and we omit it.
Example 6.5.1 We now construct an 7-ary AQECC with d z ≥ 10 and d x ≥ 9 (c =
1). The codes C 1 , C 2 and C
⊥
2 have length 48 because 2d − 2 = 18 ≤ 7
2 . Let C 1 , C 2
and C
⊥
2 be the codes generated, respectively, by
g 1 (x) = (x − 1)(x − α) · · · (x − α
8
),
g 2 (x) = (x − 1)(x − α) · · · (x − α
39
),
g
⊥
2 (x) = (x − α
40
)(x − α
41
) · · · (x − α
47
).