5.1 BCH Codes—Part I
71
where (q
a i − 1)
−1 denotes the multiplicative inverse of (q
a i − 1) modulo n.
We know that the last system has a solution if and only if
[ j − ( j − 1)q
a j ](q
a j − 1)
−1 ≡ [i − (i − 1)q
a i ](q
a i − 1)
−1
mod n
for all i, j = 2, . . . , r and
(q
a 1 − 1)
−1 ≡ [i − (i − 1)q
a i ](q
a i − 1)
−1
mod n
for all i = 2, . . . , r . This fact means that
n|[( j − ( j − 1)q
a j )(q
a j − 1)
−1 − (q
a 1 − 1)
−1 ]
for every j = 2, . . . , r , i.e., n| gcd(t 2 , . . . , t r ), where
t j = [( j − ( j − 1)q
a j )(q
a j − 1)
−1 − (q
a 1 − 1)
−1 ]
for all j = 2, . . . , r .
Let C be the cyclic code whose defining is the q-coset C x . From construction,
the defining set of C, i.e., the coset C x , contains the sequence x, x + 1, . . . , x + r
of r + 1 consecutive integers. From the BCH bound, the minimum distance d of C
satisfies d ≥ r + 2. Since |C x | = m
∗ , C has dimension n − m
∗ . We then obtain an
[n, n − m
∗
, d ≥ r + 2] q code, as required.
If the code length is prime we have the following particular case of Theorem 5.1.10.
Corollary 5.1.4 Let q ≥ 3 be a prime power and n > m be a prime number such
that gcd(q, n) = 1, where m = ord n (q) ≥ r + 2 and 1 ≤ r, a 1 , a 2 , . . . , a r < m are
integers. Assume that n| gcd(t 2 , . . . , t r ), where t j = [( j − ( j − 1)q
a j ) (q
a j − 1)
−1
−
(q
a 1 − 1)
−1
] for every j = 2, . . . , r and a 1 , a 2 , . . . , a r are integers such that 1 ≤
a 1 + a 2 + · · · + a r < m (the operations are performed modulo n). Then there exists
an [n, n − m
∗
, d ≥ r + 2] q cyclic code.
Proof Notice that since n is prime, it follows that gcd(q
a i − 1, n) = 1 for every
i = 1, 2, . . . , r , because a 1 , a 2 , . . . , a r < m. We next apply Theorem 5.1.10 to obtain
the desired result.
In order to proceed further, we will denote by C −x the coset of −x, where −x is
taken modulo n. With this notation we have the following result.
Theorem 5.1.11 Assume all hypotheses of Theorem 5.1.10 hold. Let C be the cyclic
code with defining set C x , where C x is a coset containing r + 1 consecutive integers.
If C x = C −x then there exists an [[n, n − 2m
∗
, d ≥ r + 2]] q quantum code.
Proof From [4, Lemma 1], C contains its Euclidean dual code C
⊥ . The dimension
and the minimum distance of the corresponding quantum code follow directly from
Theorem 5.1.10 and from Lemma 5.1.6.
71
where (q
a i − 1)
−1 denotes the multiplicative inverse of (q
a i − 1) modulo n.
We know that the last system has a solution if and only if
[ j − ( j − 1)q
a j ](q
a j − 1)
−1 ≡ [i − (i − 1)q
a i ](q
a i − 1)
−1
mod n
for all i, j = 2, . . . , r and
(q
a 1 − 1)
−1 ≡ [i − (i − 1)q
a i ](q
a i − 1)
−1
mod n
for all i = 2, . . . , r . This fact means that
n|[( j − ( j − 1)q
a j )(q
a j − 1)
−1 − (q
a 1 − 1)
−1 ]
for every j = 2, . . . , r , i.e., n| gcd(t 2 , . . . , t r ), where
t j = [( j − ( j − 1)q
a j )(q
a j − 1)
−1 − (q
a 1 − 1)
−1 ]
for all j = 2, . . . , r .
Let C be the cyclic code whose defining is the q-coset C x . From construction,
the defining set of C, i.e., the coset C x , contains the sequence x, x + 1, . . . , x + r
of r + 1 consecutive integers. From the BCH bound, the minimum distance d of C
satisfies d ≥ r + 2. Since |C x | = m
∗ , C has dimension n − m
∗ . We then obtain an
[n, n − m
∗
, d ≥ r + 2] q code, as required.
If the code length is prime we have the following particular case of Theorem 5.1.10.
Corollary 5.1.4 Let q ≥ 3 be a prime power and n > m be a prime number such
that gcd(q, n) = 1, where m = ord n (q) ≥ r + 2 and 1 ≤ r, a 1 , a 2 , . . . , a r < m are
integers. Assume that n| gcd(t 2 , . . . , t r ), where t j = [( j − ( j − 1)q
a j ) (q
a j − 1)
−1
−
(q
a 1 − 1)
−1
] for every j = 2, . . . , r and a 1 , a 2 , . . . , a r are integers such that 1 ≤
a 1 + a 2 + · · · + a r < m (the operations are performed modulo n). Then there exists
an [n, n − m
∗
, d ≥ r + 2] q cyclic code.
Proof Notice that since n is prime, it follows that gcd(q
a i − 1, n) = 1 for every
i = 1, 2, . . . , r , because a 1 , a 2 , . . . , a r < m. We next apply Theorem 5.1.10 to obtain
the desired result.
In order to proceed further, we will denote by C −x the coset of −x, where −x is
taken modulo n. With this notation we have the following result.
Theorem 5.1.11 Assume all hypotheses of Theorem 5.1.10 hold. Let C be the cyclic
code with defining set C x , where C x is a coset containing r + 1 consecutive integers.
If C x = C −x then there exists an [[n, n − 2m
∗
, d ≥ r + 2]] q quantum code.
Proof From [4, Lemma 1], C contains its Euclidean dual code C
⊥ . The dimension
and the minimum distance of the corresponding quantum code follow directly from
Theorem 5.1.10 and from Lemma 5.1.6.