Section 9.2 Coding Theory
723
Decoding Group Codes
Now suppose that some encoding scheme has been used to encode all members of
Z
m
2 in Z
n
2 . There will be 2
m
of these code words scattered among the 2
n
binary ntuples. These code words are known to us (remember that secrecy is not the issue
here). When an n-tuple X is received, we have a process for decoding: we decode
X as the closest code word in terms of Hamming distance, making the assumption
that the fewest errors have occurred. This process is not truly an algorithm, however; there may not be a unique closest code word, and even if there is, we might
still decode incorrectly if enough errors have occurred.
Nonetheless, let’s concentrate on how to find the closest code word(s) for a
received word X. There is certainly a brute force approach; we can create an array
of all 2
m
code words and when an X is received, we just compare X to each one
in turn to find the closest code word. But wait—this requires storage for an exponential array size as well as an exponential sequential search process. Even for a
relatively modest m-value of 32, 2
32
is a very large number. But, suppose our code
is a group code generated by an n × r canonical parity-check matrix h. Then we
will ultimately be able to decode by searching an array of only 2
r
elements. In a
single-error correcting code with m = 32, r can be as low as 6 (m ≤ 2
r
− 1 − r),
and 2
6
= 64 is an acceptable search array.
Here’s how this decoding works. Recall that the set of code words equals the
kernel K of the homomorphism h induces from 3Z
n
2 , + 2 4 to the group 3Z
r
2 , + 2 4.
We therefore know that K is a subgroup of 3Z
n
2 , + 2 4 and we also know that the set
of left cosets of K in 3Z
n
2 , + 2 4 partitions the set Z
n
2 . Cosets have the form X + 2 K
where X [ Z
n
2 . Any given coset
X + 2 K = 5X + 2 C i 0 C i [ K6
K has 2
m
elements, so the size of each coset is 2
m
. Because the set of left cosets
partitions Z
n
2 , a set of size 2
n
, there must be 2
n
∙2
m
= 2
n − m
= 2
r
distinct cosets.
When a word X is received, X belongs to the coset X + 2 K. As we just noted,
each element E i of this coset has the form X + 2 C i where C i is a code word. Both E i
and C i are binary n-tuples, so they are each self-inverse (−E i = E i and − C i = C i ).
Therefore the equation
E i = X + 2 C i
(2)
can be written as
X + 2 E i = C i
(3)
From (2) we can see that 1’s in E i occur in exactly those components where
X and C i differ. Thus the weight of E i equals the distance between X and C i ,
and the closest code word to X is the one for which the corresponding E i has
minimum weight. To decode X, look for the element in the coset of X having
minimum weight and, by (3), add that element to X. The result is the code word
to which we decode X. The coset element having minimum weight is called
the coset leader, and it may not be unique. If there are two “minimum-weight”
elements in a given coset, one is chosen arbitrarily as the coset leader. This just
means that no word in this particular coset can be accurately decoded because
it has too many errors.
723
Decoding Group Codes
Now suppose that some encoding scheme has been used to encode all members of
Z
m
2 in Z
n
2 . There will be 2
m
of these code words scattered among the 2
n
binary ntuples. These code words are known to us (remember that secrecy is not the issue
here). When an n-tuple X is received, we have a process for decoding: we decode
X as the closest code word in terms of Hamming distance, making the assumption
that the fewest errors have occurred. This process is not truly an algorithm, however; there may not be a unique closest code word, and even if there is, we might
still decode incorrectly if enough errors have occurred.
Nonetheless, let’s concentrate on how to find the closest code word(s) for a
received word X. There is certainly a brute force approach; we can create an array
of all 2
m
code words and when an X is received, we just compare X to each one
in turn to find the closest code word. But wait—this requires storage for an exponential array size as well as an exponential sequential search process. Even for a
relatively modest m-value of 32, 2
32
is a very large number. But, suppose our code
is a group code generated by an n × r canonical parity-check matrix h. Then we
will ultimately be able to decode by searching an array of only 2
r
elements. In a
single-error correcting code with m = 32, r can be as low as 6 (m ≤ 2
r
− 1 − r),
and 2
6
= 64 is an acceptable search array.
Here’s how this decoding works. Recall that the set of code words equals the
kernel K of the homomorphism h induces from 3Z
n
2 , + 2 4 to the group 3Z
r
2 , + 2 4.
We therefore know that K is a subgroup of 3Z
n
2 , + 2 4 and we also know that the set
of left cosets of K in 3Z
n
2 , + 2 4 partitions the set Z
n
2 . Cosets have the form X + 2 K
where X [ Z
n
2 . Any given coset
X + 2 K = 5X + 2 C i 0 C i [ K6
K has 2
m
elements, so the size of each coset is 2
m
. Because the set of left cosets
partitions Z
n
2 , a set of size 2
n
, there must be 2
n
∙2
m
= 2
n − m
= 2
r
distinct cosets.
When a word X is received, X belongs to the coset X + 2 K. As we just noted,
each element E i of this coset has the form X + 2 C i where C i is a code word. Both E i
and C i are binary n-tuples, so they are each self-inverse (−E i = E i and − C i = C i ).
Therefore the equation
E i = X + 2 C i
(2)
can be written as
X + 2 E i = C i
(3)
From (2) we can see that 1’s in E i occur in exactly those components where
X and C i differ. Thus the weight of E i equals the distance between X and C i ,
and the closest code word to X is the one for which the corresponding E i has
minimum weight. To decode X, look for the element in the coset of X having
minimum weight and, by (3), add that element to X. The result is the code word
to which we decode X. The coset element having minimum weight is called
the coset leader, and it may not be unique. If there are two “minimum-weight”
elements in a given coset, one is chosen arbitrarily as the coset leader. This just
means that no word in this particular coset can be accurately decoded because
it has too many errors.