Section 9.2 Coding Theory
727
S e c t i o n 9 . 2 review
tecHniQueS
• Find the kernel of a given homomorphism from a
group 3G, # 4 to a group 3H, + 4.
• Given a canonical n × r parity-check matrix h,
write the set of binary m-tuples that h encodes and
write the code word for each one.
• Given m such that Z
m
2 is to be encoded as a singleerror correcting code, find a canonical parity-check
matrix to generate the code.
• Given a canonical n × r parity-check matrix h for a
perfect code, be able to decode a received n-tuple by
computing its syndrome and finding its coset leader.
main iDeaS
• If f is a homomorphism from a group 3G, # 4 to a
group 3H, + 4, then f (G) is a subgroup of 3H, + 4
and the kernel K (the set of all elements in G mapping to i H ) is a subgroup of 3G, # 4.
• If 3S, + 4 is a subgroup of the group 3G, + 4, then
the set of left cosets of S in G forms a partition of G.
• The error-detecting and error-correcting capabilities of a binary code are functions of the minimum
distance of the code.
• In a group code, the minimum distance is the minimum weight of the nonzero code words.
• A parity-check matrix h can be used to generate a
group code, in which case the minimum distance of
the code can be determined from h.
• A canonical n × r parity-check matrix provides an
easy procedure to encode Z
m
2 in Z
n
2 where m = n − r.
• For a group code generated by an n × r paritycheck matrix h, each word X in Z
n
2 is decoded
by using its syndrome to locate the coset in Z
n
2 to
which X belongs and adding the coset leader to X.
If the code is a perfect code, the coset leader can be
determined from h.
W
W
exeRciSeS 9.2
1. Let f be a homomorphism from a group 3G, # 4 to a group 3H, + 4. Prove that 3 f (G), + 4 is a subgroup of
3H, + 4.
2. Let f be a homorphism from the group 3Z, + 4 to the group 3Z, + 4 given by f (x) = 2x.
a. Verify that f is a homorphism.
b. Is f an isomorphism? Prove or disprove.
c. What is the subgroup 3 f (Z), + 4 of 3Z, + 4?
3. The function f defined by f (x) = x # 8 2 is a homomorphism from 3Z, + 4 to 3Z 8 , + 8 4. Find the kernel K.
4. The function f defined by f (x) = x # 8 4 is a homomorphism from 3Z 12 , + 12 4to 3Z 8 , + 8 4. Find the kernel K.
5. A function f: Z × Z S Z is defined by f (x, y) = x + y.
a. Prove that f is a homomorphism from the group 3Z × Z, + 4 (where + means componentwise addition) to the group 3Z, + 4.
b. Find the kernel K.
6. Let F be the set of all functions f: R S R. For f, g [ F, let f + g be defined as follows: For
x [ R, ( f + g)(x) = f (x) + g(x).
a. Prove that 3F, + 4 is a group.
b. Let a [ R. Define a function a: F S F by a( f ) = f (a). Prove that a is a homorphism from 3F, + 4 to
3R, + 4.
c. Find the kernel K.
7. Let S = 50, 4, 86. Then 3S, + 12 4 is a subgroup of 3Z 12 , + 12 4. Find the members of the left coset 7 + 12 S.
8. Let S = 5i,(2, 3)6. Then 3S, + 4 is a subgroup of the symmetric group 3S 3 , + 4. Find the members of the left
coset (1, 2, 3) + S and the right coset S + (1, 2, 3). Explain this result.
727
S e c t i o n 9 . 2 review
tecHniQueS
• Find the kernel of a given homomorphism from a
group 3G, # 4 to a group 3H, + 4.
• Given a canonical n × r parity-check matrix h,
write the set of binary m-tuples that h encodes and
write the code word for each one.
• Given m such that Z
m
2 is to be encoded as a singleerror correcting code, find a canonical parity-check
matrix to generate the code.
• Given a canonical n × r parity-check matrix h for a
perfect code, be able to decode a received n-tuple by
computing its syndrome and finding its coset leader.
main iDeaS
• If f is a homomorphism from a group 3G, # 4 to a
group 3H, + 4, then f (G) is a subgroup of 3H, + 4
and the kernel K (the set of all elements in G mapping to i H ) is a subgroup of 3G, # 4.
• If 3S, + 4 is a subgroup of the group 3G, + 4, then
the set of left cosets of S in G forms a partition of G.
• The error-detecting and error-correcting capabilities of a binary code are functions of the minimum
distance of the code.
• In a group code, the minimum distance is the minimum weight of the nonzero code words.
• A parity-check matrix h can be used to generate a
group code, in which case the minimum distance of
the code can be determined from h.
• A canonical n × r parity-check matrix provides an
easy procedure to encode Z
m
2 in Z
n
2 where m = n − r.
• For a group code generated by an n × r paritycheck matrix h, each word X in Z
n
2 is decoded
by using its syndrome to locate the coset in Z
n
2 to
which X belongs and adding the coset leader to X.
If the code is a perfect code, the coset leader can be
determined from h.
W
W
exeRciSeS 9.2
1. Let f be a homomorphism from a group 3G, # 4 to a group 3H, + 4. Prove that 3 f (G), + 4 is a subgroup of
3H, + 4.
2. Let f be a homorphism from the group 3Z, + 4 to the group 3Z, + 4 given by f (x) = 2x.
a. Verify that f is a homorphism.
b. Is f an isomorphism? Prove or disprove.
c. What is the subgroup 3 f (Z), + 4 of 3Z, + 4?
3. The function f defined by f (x) = x # 8 2 is a homomorphism from 3Z, + 4 to 3Z 8 , + 8 4. Find the kernel K.
4. The function f defined by f (x) = x # 8 4 is a homomorphism from 3Z 12 , + 12 4to 3Z 8 , + 8 4. Find the kernel K.
5. A function f: Z × Z S Z is defined by f (x, y) = x + y.
a. Prove that f is a homomorphism from the group 3Z × Z, + 4 (where + means componentwise addition) to the group 3Z, + 4.
b. Find the kernel K.
6. Let F be the set of all functions f: R S R. For f, g [ F, let f + g be defined as follows: For
x [ R, ( f + g)(x) = f (x) + g(x).
a. Prove that 3F, + 4 is a group.
b. Let a [ R. Define a function a: F S F by a( f ) = f (a). Prove that a is a homorphism from 3F, + 4 to
3R, + 4.
c. Find the kernel K.
7. Let S = 50, 4, 86. Then 3S, + 12 4 is a subgroup of 3Z 12 , + 12 4. Find the members of the left coset 7 + 12 S.
8. Let S = 5i,(2, 3)6. Then 3S, + 4 is a subgroup of the symmetric group 3S 3 , + 4. Find the members of the left
coset (1, 2, 3) + S and the right coset S + (1, 2, 3). Explain this result.