5.2 BCH Codes—Part II
79
Proof It follows directly from Theorem 5.2.1.
In what follows, we introduce the concept of complementary coset, after showing
some interesting properties of them.
Definition 5.2.1 Let C s = {s, qs, q
2 s, q
3 s, . . . , q
m s −1 s} be a q-coset with representative s. A complementary coset of C s is a q-ary coset given by C r = {r, qr, q
2 r, q
3 r,
. . . , q
m r −1 r } with representative r , containing an element q
l r , where 0 ≤ l ≤ m r − 1,
such that s + q
l r ≡ 0 mod (q
m
− 1).
Proposition 5.2.2 establishes some properties of complementary cosets.
Proposition 5.2.2 Let C s = {s, qs, q
2 s, q
3 s, . . . , q
m s −1 s} be a q-ary coset modulo
n = q
m
− 1. Then the following hold:
(i) For each q-ary coset C s given, there exists only one complementary coset of
C s , denoted by C s ;
(ii) The cyclotomic coset and its complementary coset have the same cardinality;
(iii) Defining the operation C s ⊕ C r = {s + q
l r, sq + (q
l r )q, . . . , sq
m s −1
+
(q
l r )q
m s −1
} one has C s ⊕ C s = C 0 = {0};
(iv) If C r is the complementary coset of C s then L s = L r ;
(v) C s = C.
Proof (i) Let C s be a coset. Assume that
C r 1 = {r 1 , qr 1 , q
2 r 1 , q
3 r 1 , . . . , q
m r 1 −1 r 1 },
C r 2 = {r 2 , qr 2 , q
2 r 2 , q
3 r 2 , . . . , q
m r 2 −1 r 2 }
are two complementary cosets of C s with representatives r 1 and r 2 , respectively.
From definition of complementary coset, there exist two elements q
l r 1 , 0 ≤
l ≤ m r 1 − 1 and q
t r 2 , 0 ≤ t ≤ m r 2 − 1 such that s + q
l r 1 ≡ 0 mod n and s +
q
t r 2 ≡ 0 mod n, and so q
l r 1 ≡ q
t r 2 mod n. Checking the latter equivalence we
obtain one of the following three cases: r 1 ≡ r 2 mod n; r 1 ≡ r 2 q
t mod n, where
0 ≤ t ≤ m r 2 − 1; r 2 ≡ r 1 q
l mod n, where 0 ≤ t ≤ m r 2 − 1. In each of them it
follows that C r 1 = C r 2 . Therefore each coset has only one complementary coset
as well.
(ii) Let C s be the coset containing s given by
C s = {s, sq, sq
2
, sq
3
, . . . , sq
m s −1
}.
Suppose that C s has cardinality m s . Consider the q-ary coset containing the
element n − s, where n = q
m
− 1, and denote it by C [n−s] . Without considering
the order one has
C [n−s] = {n − s, [n − s]q, [n − s]q
2
, . . . , [n − s]q
m l −1
}.
79
Proof It follows directly from Theorem 5.2.1.
In what follows, we introduce the concept of complementary coset, after showing
some interesting properties of them.
Definition 5.2.1 Let C s = {s, qs, q
2 s, q
3 s, . . . , q
m s −1 s} be a q-coset with representative s. A complementary coset of C s is a q-ary coset given by C r = {r, qr, q
2 r, q
3 r,
. . . , q
m r −1 r } with representative r , containing an element q
l r , where 0 ≤ l ≤ m r − 1,
such that s + q
l r ≡ 0 mod (q
m
− 1).
Proposition 5.2.2 establishes some properties of complementary cosets.
Proposition 5.2.2 Let C s = {s, qs, q
2 s, q
3 s, . . . , q
m s −1 s} be a q-ary coset modulo
n = q
m
− 1. Then the following hold:
(i) For each q-ary coset C s given, there exists only one complementary coset of
C s , denoted by C s ;
(ii) The cyclotomic coset and its complementary coset have the same cardinality;
(iii) Defining the operation C s ⊕ C r = {s + q
l r, sq + (q
l r )q, . . . , sq
m s −1
+
(q
l r )q
m s −1
} one has C s ⊕ C s = C 0 = {0};
(iv) If C r is the complementary coset of C s then L s = L r ;
(v) C s = C.
Proof (i) Let C s be a coset. Assume that
C r 1 = {r 1 , qr 1 , q
2 r 1 , q
3 r 1 , . . . , q
m r 1 −1 r 1 },
C r 2 = {r 2 , qr 2 , q
2 r 2 , q
3 r 2 , . . . , q
m r 2 −1 r 2 }
are two complementary cosets of C s with representatives r 1 and r 2 , respectively.
From definition of complementary coset, there exist two elements q
l r 1 , 0 ≤
l ≤ m r 1 − 1 and q
t r 2 , 0 ≤ t ≤ m r 2 − 1 such that s + q
l r 1 ≡ 0 mod n and s +
q
t r 2 ≡ 0 mod n, and so q
l r 1 ≡ q
t r 2 mod n. Checking the latter equivalence we
obtain one of the following three cases: r 1 ≡ r 2 mod n; r 1 ≡ r 2 q
t mod n, where
0 ≤ t ≤ m r 2 − 1; r 2 ≡ r 1 q
l mod n, where 0 ≤ t ≤ m r 2 − 1. In each of them it
follows that C r 1 = C r 2 . Therefore each coset has only one complementary coset
as well.
(ii) Let C s be the coset containing s given by
C s = {s, sq, sq
2
, sq
3
, . . . , sq
m s −1
}.
Suppose that C s has cardinality m s . Consider the q-ary coset containing the
element n − s, where n = q
m
− 1, and denote it by C [n−s] . Without considering
the order one has
C [n−s] = {n − s, [n − s]q, [n − s]q
2
, . . . , [n − s]q
m l −1
}.