7.3 Constructions of Optimal QCCs
171
H 0 =
⎡
⎢
⎢
⎢
⎣
1 α
a
· · ·
· · · α
(n−1)a
1 α
(a−1)
· · ·
· · · α
(n−1)(a−1)
. . .
. . .
. . .
. . .
. . .
1 α
(a−i+1)
α
2(a−i+1)
· · · α
(n−1)(a−i+1)
⎤
⎥
⎥
⎥
⎦
and
H 1 =
1 α
(a−i)
α
2(a−i)
· · · α
(n−1)(a−i)
,
respectively, where H 0 is obtained from the matrix H C 1 by rearranging rows and H 1 is
derived from H C also by rearranging rows. Hence, it follows that rk(H 0 ) ≥ rk(H 1 ).
Let V be the convolutional code generated by the reduced basic (according to
Theorem 7.1.1 Item (a)) generator matrix
G(D) = ˜
H 0 + ˜
H 1 D,
where ˜
H 0 = H 0 and ˜
H 1 is obtained from H 1 by adding zero-rows at the bottom such
that ˜
H 1 has the number of rows of H 0 in total. By construction, V is a unit-memory
convolutional code of dimension 2i and degree δ V = 2.
Let V
⊥ be the Euclidean dual of V . We know that V
⊥ has dimension n − 2i
and degree 2. By Theorem 7.1.1 Item (c), the free distance of V
⊥ is bounded by
min{d 0 + d 1 , d} ≤ d
⊥
f ≤ d, where d i is the minimum distance of the code C i = {v ∈
F
n
q | v ˜
H
t
i = 0}. From construction one has d = 2i + 3, d 0 = 2i + 1 and d 1 ≥ 2, so
V
⊥ is an (n, n − 2i, 2; 1, 2i + 3) q code.
Recall that the generalized (classical) Singleton bound [145] of an (n, k, γ; m,
d f ) q convolutional code is given by
d f ≤ (n − k)[[γ/k + 1] + γ + 1.
Replacing the values of the parameters of V
⊥ in the above inequality it follows that
V
⊥ is a MDS convolutional code. The proof is complete.
Let us now present an illustrative example.
Example 7.3.1 According to Theorem 7.3.2, let q = 16, n = q + 1 = 17 and a =
8. Assume C 2 is an [17, 11, 7] 16 MDS code generated by M
(8)
(x) M
(7)
(x)M
(6)
(x).
The cosets of C 2 are {8, 9}, {7, 10} and {6, 11}. Let C 1 be the (cyclic) MDS code
generated by the product of the minimal polynomials M
(8)
(x)M
(7)
(x); C 1 has parameters [17, 13, 5] 16 . Finally, suppose C is [17, 15, d ≥ 2] 16 cyclic code generated by
M
(6)
(x). In this case, i = 2. We then form the convolutional code V generated by
G(D) = ˜
H 0 + ˜
H 1 D, where ˜
H 0 = H 0 and ˜
H 1 is obtained from H 1 by adding zerorows at the bottom such that ˜
H 1 has the number of rows of H 0 in total. The matrix
H 0 is the parity check matrix of C 1 (up to permutation of rows) and H 1 is the parity check matrix of C. We know that V is an (17, 4, 2; 1, d f ) 16 code; V
⊥ is an
(17, 13, 2; 1, d
⊥
f ) 16 code, where min{d 0 + d 1 , d} ≤ d
⊥
f ≤ d, where d 0 = 5, d 1 ≥ 2
171
H 0 =
⎡
⎢
⎢
⎢
⎣
1 α
a
· · ·
· · · α
(n−1)a
1 α
(a−1)
· · ·
· · · α
(n−1)(a−1)
. . .
. . .
. . .
. . .
. . .
1 α
(a−i+1)
α
2(a−i+1)
· · · α
(n−1)(a−i+1)
⎤
⎥
⎥
⎥
⎦
and
H 1 =
1 α
(a−i)
α
2(a−i)
· · · α
(n−1)(a−i)
,
respectively, where H 0 is obtained from the matrix H C 1 by rearranging rows and H 1 is
derived from H C also by rearranging rows. Hence, it follows that rk(H 0 ) ≥ rk(H 1 ).
Let V be the convolutional code generated by the reduced basic (according to
Theorem 7.1.1 Item (a)) generator matrix
G(D) = ˜
H 0 + ˜
H 1 D,
where ˜
H 0 = H 0 and ˜
H 1 is obtained from H 1 by adding zero-rows at the bottom such
that ˜
H 1 has the number of rows of H 0 in total. By construction, V is a unit-memory
convolutional code of dimension 2i and degree δ V = 2.
Let V
⊥ be the Euclidean dual of V . We know that V
⊥ has dimension n − 2i
and degree 2. By Theorem 7.1.1 Item (c), the free distance of V
⊥ is bounded by
min{d 0 + d 1 , d} ≤ d
⊥
f ≤ d, where d i is the minimum distance of the code C i = {v ∈
F
n
q | v ˜
H
t
i = 0}. From construction one has d = 2i + 3, d 0 = 2i + 1 and d 1 ≥ 2, so
V
⊥ is an (n, n − 2i, 2; 1, 2i + 3) q code.
Recall that the generalized (classical) Singleton bound [145] of an (n, k, γ; m,
d f ) q convolutional code is given by
d f ≤ (n − k)[[γ/k + 1] + γ + 1.
Replacing the values of the parameters of V
⊥ in the above inequality it follows that
V
⊥ is a MDS convolutional code. The proof is complete.
Let us now present an illustrative example.
Example 7.3.1 According to Theorem 7.3.2, let q = 16, n = q + 1 = 17 and a =
8. Assume C 2 is an [17, 11, 7] 16 MDS code generated by M
(8)
(x) M
(7)
(x)M
(6)
(x).
The cosets of C 2 are {8, 9}, {7, 10} and {6, 11}. Let C 1 be the (cyclic) MDS code
generated by the product of the minimal polynomials M
(8)
(x)M
(7)
(x); C 1 has parameters [17, 13, 5] 16 . Finally, suppose C is [17, 15, d ≥ 2] 16 cyclic code generated by
M
(6)
(x). In this case, i = 2. We then form the convolutional code V generated by
G(D) = ˜
H 0 + ˜
H 1 D, where ˜
H 0 = H 0 and ˜
H 1 is obtained from H 1 by adding zerorows at the bottom such that ˜
H 1 has the number of rows of H 0 in total. The matrix
H 0 is the parity check matrix of C 1 (up to permutation of rows) and H 1 is the parity check matrix of C. We know that V is an (17, 4, 2; 1, d f ) 16 code; V
⊥ is an
(17, 13, 2; 1, d
⊥
f ) 16 code, where min{d 0 + d 1 , d} ≤ d
⊥
f ≤ d, where d 0 = 5, d 1 ≥ 2