Section 9.2 Coding Theory
717
Definition CosEt
Let 3S, + 4 be a subgroup of a group 3G, + 4. Then for x [ G, sets of the form
x + S = 5x + s 0 s [ S6 are called left cosets of S in G. Sets of the form
S + x = 5s + x 0 s [ S6 are called right cosets of S in G.
Of course, if G is commutative, then left cosets and right cosets are identical.
example 19
Let S = 50, 2, 4, 66. Then 3S, + 8 4 is a subgroup of 3Z 8 ,+ 8 4. The left coset
5 + 8 S = 55 + 8 0, 5 + 8 2, 5 + 8 4, 5 + 8 66 = 55, 7, 1, 36.
PrACtiCe 37
a. Verify that 5 + 8 S = 1 + 8 S = 3 + 8 S = 7 + 8 S.
b. Compute the left coset 2 + 8 S. What are its other names?
■
For 3S, + 4 any subgroup of a group 3G, + 4, we can define a binary relation r
on G as follows:
x r y 4 y belongs to x + S, x’s left coset of S in G
Then x r y, which is equivalent to y belonging to x + S, means y can be written as
x + s for some element s [ S. It turns out that r is an equivalence relation on G:
Reflexive property: x r x because x = x + i G . (Because S is a subgroup of G, the
identity i G of G is an element of S.)
Symmetric property: if x r y then y = x + s for some s [ S. Then, because S is
a subgroup, −s is in S and x = y + (−s), which puts x in the same coset as
y, that is y r x.
Transitive property: if x r y and y r z then y = x + s 1 for some s 1 [ S and
z = y + s 2 for some s 2 [ S. Therefore, z = y + s 2 = (x + s 1 ) + s 2 =
x + (s 1 + s 2 ), which means z is in x’s left coset so x r z.
We have proved the following result.
tHeoRem on CosEt PArtitions
Let 3S, + 4 be a subgroup of a group 3G, + 4. Then the set of left cosets of S in G
forms a partition of G. One of these cosets is i G + S = S.
This coset partition will play a key role in decoding our group codes. But first,
we need to see how we actually create group codes.
Generating Group Codes
Suppose we know how to turn any m-bit binary message into an n-bit code word
where m < n, and we also know how to reverse this process. There is then a set of
n-bit code words, one for each m-bit binary string. An n-bit code word is transmitted and the received message is also a binary n-tuple. Two cases can occur:
717
Definition CosEt
Let 3S, + 4 be a subgroup of a group 3G, + 4. Then for x [ G, sets of the form
x + S = 5x + s 0 s [ S6 are called left cosets of S in G. Sets of the form
S + x = 5s + x 0 s [ S6 are called right cosets of S in G.
Of course, if G is commutative, then left cosets and right cosets are identical.
example 19
Let S = 50, 2, 4, 66. Then 3S, + 8 4 is a subgroup of 3Z 8 ,+ 8 4. The left coset
5 + 8 S = 55 + 8 0, 5 + 8 2, 5 + 8 4, 5 + 8 66 = 55, 7, 1, 36.
PrACtiCe 37
a. Verify that 5 + 8 S = 1 + 8 S = 3 + 8 S = 7 + 8 S.
b. Compute the left coset 2 + 8 S. What are its other names?
■
For 3S, + 4 any subgroup of a group 3G, + 4, we can define a binary relation r
on G as follows:
x r y 4 y belongs to x + S, x’s left coset of S in G
Then x r y, which is equivalent to y belonging to x + S, means y can be written as
x + s for some element s [ S. It turns out that r is an equivalence relation on G:
Reflexive property: x r x because x = x + i G . (Because S is a subgroup of G, the
identity i G of G is an element of S.)
Symmetric property: if x r y then y = x + s for some s [ S. Then, because S is
a subgroup, −s is in S and x = y + (−s), which puts x in the same coset as
y, that is y r x.
Transitive property: if x r y and y r z then y = x + s 1 for some s 1 [ S and
z = y + s 2 for some s 2 [ S. Therefore, z = y + s 2 = (x + s 1 ) + s 2 =
x + (s 1 + s 2 ), which means z is in x’s left coset so x r z.
We have proved the following result.
tHeoRem on CosEt PArtitions
Let 3S, + 4 be a subgroup of a group 3G, + 4. Then the set of left cosets of S in G
forms a partition of G. One of these cosets is i G + S = S.
This coset partition will play a key role in decoding our group codes. But first,
we need to see how we actually create group codes.
Generating Group Codes
Suppose we know how to turn any m-bit binary message into an n-bit code word
where m < n, and we also know how to reverse this process. There is then a set of
n-bit code words, one for each m-bit binary string. An n-bit code word is transmitted and the received message is also a binary n-tuple. Two cases can occur: