7.5 QCCs from Negacyclic Codes
187
Lemma 7.5.1 ([77, Lemma 4.1]) Let n = q
2
+ 1, where q ≡ 1 mod 4 is a power
of an odd prime and suppose that s = n/2. Then the q
2 -ary cosets modulo 2n are
given by C s = {s}, C 3s = {3s} and C s−2i = {s − 2i, s + 2i}, where 1 ≤ i ≤ s − 1.
Lemma 7.5.2 ([77, Lemma 4.4]) Let n = (q
2
+ 1)/2, where q is a power of an odd
prime. Then the q
2 -ary cosets modulo 2n containing all odd integers from 1 to 2n − 1
are given by: C n = {n}, and C 2i−1 = {2i − 1, 1 − 2i}, where 1 ≤ i ≤ (n − 1)/2.
Remark 7.5.1 Let B = {b 1 , . . . , b l } be a basis of F q l over F q . If u = (u 1 , . . . , u n ) ∈
F
n
q l , then we can write the vectors u i , 1 ≤ i ≤ n, as linear combinations of the elements of B, i.e., u i = u i1 b 1 + · · · + u il b l . Consider that u
( j)
= (u 1 j , . . . , u nj ) are
vectors in F
n
q , where 1 ≤ j ≤ l. Then, if v ∈ F
n
q , it follows that v · u = 0 if and only
if v · u
( j)
= 0 for all 1 ≤ j ≤ l.
In the following theorem we construct a parity check matrix for negacyclic codes:
Theorem 7.5.1 Assume that q is a power of an odd prime, gcd(n, q) = 1, and
m = or d 2n (q). Let β be a primitive 2nth root of unity in F q m . Let b be an odd
positive integer with 1 ≤ b ≤ 2n − 1. Then a parity check matrix for the negacyclic
BCH code C of length n and designed distance δ, generated by the polynomial
g(x) = lcm{M
(b)
(x), M
(b+2)
(x), . . . , M
[b+2(δ−2)]
(x)}
is the matrix
H δ,b =
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
1
β
b
β
2b
· · ·
β
(n−1)b
1 β
(b+2)
β
2(b+2)
· · · β
(n−1)(b+2)
1 β
(b+4)
β
2(b+4)
· · · β
(n−1)(b+4)
. . .
. . .
. . .
. . .
. . .
1 β
[b+2(δ−2)]
β
2[b+2(δ−2)]
· · · β
(n−1)[b+2(δ−2)]
⎤
⎥
⎥
⎥
⎥
⎥
⎦
,
where each entry is replaced by the corresponding column of m elements from F q
and then removing any linearly dependent rows.
Proof Assume that c = (c 0 , c 1 , . . . , c n−1 ) ∈ C. We then have
c(β
b
) = c(β
b+2
) = c(β
b+4
) = · · · = c(β
[b+2(δ−2)]
) = 0;
hence,
⎡
⎢
⎢
⎢
⎢
⎢
⎣
1
β
b
β
2b
· · ·
β
(n−1)b
1 β
(b+2)
β
2(b+2)
· · · β
(n−1)(b+2)
1 β
(b+4)
β
2(b+4)
· · · β
(n−1)(b+4)
. . .
. . .
. . .
. . .
. . .
1 β
[b+2(δ−2)]
β
2[b+2(δ−2)]
· · · β
(n−1)[b+2(δ−2)]
⎤
⎥
⎥
⎥
⎥
⎥
⎦
·
⎡
⎢
⎢
⎢
⎢
⎢
⎣
c 0
c 1
c 2
. . .
c n−1
⎤
⎥
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
0
0
. . .
0
⎤
⎥
⎥
⎥
⎦
(δ−1,1)
.