7.5 QCCs from Negacyclic Codes
189
by expanding each entry as a column vector with respect to some F q 2 -basis β of
F q 4 (already done, since H 1 is a submatrix of H 2 ) and then removing one linearly
dependent row. From Lemma 7.5.1, this new matrix H C 1 has rank 2i − 1, so C 1 has
dimension n − 2i + 1. From the BCH bound for negacyclic codes, the minimum
distance d 1 of C 1 satisfies d 1 ≥ 2i, so C 1 is an [n, n − 2i + 1, 2i] q 2 MDS code.
Hence, its Hermitian dual code has dimension 2i − 1.
Let C 0 be the negacyclic BCH code of length n over F q 2 generated by the minimal
polynomial M
(s+2i)
(x). Then C 0 is an [n, n − 2, d 0 ≥ 2] q 2 code. A parity check
matrix H C 0 of C 0 is given by expanding the entries of the matrix
H 0 =
1 α
(s+2i)
α
2(s+2i)
· · · α
(n−1)(s+2i)
with respect to β (already done, since H 0 is a submatrix of H 2 ).
Further, let us construct the convolutional code V generated by the reduced basic
(according to Theorem 7.1.1 Item (a)) generator matrix
G(D) = ˜
H C 1 + ˜
H C 0 D,
where ˜
H C 1 = H C 1 and ˜
H C 0 is obtained from H C 0 by adding zero-rows at the bottom such that ˜
H C 0 has the number of rows of H C 1 in total. By construction, V is a
unit-memory convolutional code of dimension 2i − 1 and degree δ V = 2. We know
that the Hermitian dual V
⊥ h of V has dimension n − 2i + 1 and degree 2. By Theorem 7.1.1 Item (c), the free distance of V
⊥ h is bounded by min{d 0 + d 1 , d 2 } ≤
d
⊥ h
f ≤ d 2 , where d i is the minimum distance of the code C i = {v ∈ F
n
q | v ˜
H
t
C i
= 0}.
From construction one has d 2 = 2i + 2, d 1 = 2i and d 0 ≥ 2, so V
⊥ h has parameters
(n, n − 2i + 1, 2; 1, 2i + 2) q 2 . It is easy to see that V
⊥ h is MDS.
We can also construct optimal convolutional codes of length n = (q
2
+ 1)/2,
where q is an odd prime power.
Theorem 7.5.3 Let n = (q
2
+ 1)/2, where q is a power of an odd prime. Then
there exists an (n, n − 2i + 2, 2; 1, 2i + 1) q 2 MDS convolutional code, where 2 ≤
i ≤ (n − 1)/2.
Proof Left to exercise.
Exercise 7.5.1 Show Theorem 7.5.3.
Theorem 7.5.4 Let n = (q
2
+ 1)/2, where q ≥ 5 is a power of an odd prime. Then
there exists a MDS convolutional code with parameters (n, n − 2i + 1, 2; 1, 2i +
2) q 2 , where 2 ≤ i ≤
(n−1)
2
− 1.
Proof Consider that C 2 , C 1 and C 0 are negacyclic BCH codes of length n over
F q 2 generated, respectively, by g 2 (x) = =M
(n)
(x)M
(n+2)
(x) · · · · · M
(n+2i)
(x),
g 1 (x) = =M
(n)
(x)M
(n+2)
(x) · · · · · M
(n+2i−2)
(x) and g 0 (x) = =M
(n+2i)
(x).
Applying the same procedure given in the proofs of Theorems 7.5.2 and 7.5.3, the
result follows.
189
by expanding each entry as a column vector with respect to some F q 2 -basis β of
F q 4 (already done, since H 1 is a submatrix of H 2 ) and then removing one linearly
dependent row. From Lemma 7.5.1, this new matrix H C 1 has rank 2i − 1, so C 1 has
dimension n − 2i + 1. From the BCH bound for negacyclic codes, the minimum
distance d 1 of C 1 satisfies d 1 ≥ 2i, so C 1 is an [n, n − 2i + 1, 2i] q 2 MDS code.
Hence, its Hermitian dual code has dimension 2i − 1.
Let C 0 be the negacyclic BCH code of length n over F q 2 generated by the minimal
polynomial M
(s+2i)
(x). Then C 0 is an [n, n − 2, d 0 ≥ 2] q 2 code. A parity check
matrix H C 0 of C 0 is given by expanding the entries of the matrix
H 0 =
1 α
(s+2i)
α
2(s+2i)
· · · α
(n−1)(s+2i)
with respect to β (already done, since H 0 is a submatrix of H 2 ).
Further, let us construct the convolutional code V generated by the reduced basic
(according to Theorem 7.1.1 Item (a)) generator matrix
G(D) = ˜
H C 1 + ˜
H C 0 D,
where ˜
H C 1 = H C 1 and ˜
H C 0 is obtained from H C 0 by adding zero-rows at the bottom such that ˜
H C 0 has the number of rows of H C 1 in total. By construction, V is a
unit-memory convolutional code of dimension 2i − 1 and degree δ V = 2. We know
that the Hermitian dual V
⊥ h of V has dimension n − 2i + 1 and degree 2. By Theorem 7.1.1 Item (c), the free distance of V
⊥ h is bounded by min{d 0 + d 1 , d 2 } ≤
d
⊥ h
f ≤ d 2 , where d i is the minimum distance of the code C i = {v ∈ F
n
q | v ˜
H
t
C i
= 0}.
From construction one has d 2 = 2i + 2, d 1 = 2i and d 0 ≥ 2, so V
⊥ h has parameters
(n, n − 2i + 1, 2; 1, 2i + 2) q 2 . It is easy to see that V
⊥ h is MDS.
We can also construct optimal convolutional codes of length n = (q
2
+ 1)/2,
where q is an odd prime power.
Theorem 7.5.3 Let n = (q
2
+ 1)/2, where q is a power of an odd prime. Then
there exists an (n, n − 2i + 2, 2; 1, 2i + 1) q 2 MDS convolutional code, where 2 ≤
i ≤ (n − 1)/2.
Proof Left to exercise.
Exercise 7.5.1 Show Theorem 7.5.3.
Theorem 7.5.4 Let n = (q
2
+ 1)/2, where q ≥ 5 is a power of an odd prime. Then
there exists a MDS convolutional code with parameters (n, n − 2i + 1, 2; 1, 2i +
2) q 2 , where 2 ≤ i ≤
(n−1)
2
− 1.
Proof Consider that C 2 , C 1 and C 0 are negacyclic BCH codes of length n over
F q 2 generated, respectively, by g 2 (x) = =M
(n)
(x)M
(n+2)
(x) · · · · · M
(n+2i)
(x),
g 1 (x) = =M
(n)
(x)M
(n+2)
(x) · · · · · M
(n+2i−2)
(x) and g 0 (x) = =M
(n+2i)
(x).
Applying the same procedure given in the proofs of Theorems 7.5.2 and 7.5.3, the
result follows.