726
Modeling Arithmetic, Computation, and Languages
At this point we have traded one difficulty for another, namely, How do we
find the list of 2
r
coset leaders? This isn’t always easy to do. In Example 27, the
“brute force” involved writing all 2
n
= 32 binary 5-tuples, computing the 32 syndromes to group the 5-tuples into 8 cosets, and then reviewing the 4 members of
each coset to find the coset leader. In two cosets, there was a tie for coset leader,
and one value was picked arbitrarily in each case.
But—if the code is a perfect single-error correcting code, then the coset leaders are easy to find. Recall that in a perfect code, m = 2
r
− 1 − r, and because
r = n − m, it is also true that n = 2
r
− 1. The n rows of the matrix h are r-tuples
that are the binary representations of the numbers 1, 2, … , 2
r
− 1 (there’s no 0 r
row in h). The code word 0 n is the coset leader corresponding to the syndrome 0 r .
Any other syndrome is a binary r-tuple representing a digit d, 1 ≤ d ≤ 2
r
− 1.
The value d is also represented by a row of h, say, row q. The coset leader for this
syndrome is the binary n-tuple with a 1 in component q and 0s elsewhere. In this
case there is no ambiguity about the coset leader, and every received word is at
most distance 1 from a code word.
example 28
A (7, 4) code is a perfect code for which r = 3. One matrix generating such a
code is
h = G
1 1 0
1 0 1
0 1 1
1 1 1
1 0 0
0 1 0
0 0 1
W
Given the syndrome 101, the row of h that represents this binary number is
row 2. The coset leader for this syndrome is therefore 0100000 (a 1 in component 2,
0s elsewhere). You can check that (0100000)h = 101. The table of coset leaders
and the corresponding syndromes is partially filled in here.
Coset leaders
Syndromes
0000000
000
001
010
011
100
0100000
101
110
111
A received word of 1001100 has a syndrome of (1001100)h = 101, so it is decoded as
1001100 + 2 0100000 = 1101100
Modeling Arithmetic, Computation, and Languages
At this point we have traded one difficulty for another, namely, How do we
find the list of 2
r
coset leaders? This isn’t always easy to do. In Example 27, the
“brute force” involved writing all 2
n
= 32 binary 5-tuples, computing the 32 syndromes to group the 5-tuples into 8 cosets, and then reviewing the 4 members of
each coset to find the coset leader. In two cosets, there was a tie for coset leader,
and one value was picked arbitrarily in each case.
But—if the code is a perfect single-error correcting code, then the coset leaders are easy to find. Recall that in a perfect code, m = 2
r
− 1 − r, and because
r = n − m, it is also true that n = 2
r
− 1. The n rows of the matrix h are r-tuples
that are the binary representations of the numbers 1, 2, … , 2
r
− 1 (there’s no 0 r
row in h). The code word 0 n is the coset leader corresponding to the syndrome 0 r .
Any other syndrome is a binary r-tuple representing a digit d, 1 ≤ d ≤ 2
r
− 1.
The value d is also represented by a row of h, say, row q. The coset leader for this
syndrome is the binary n-tuple with a 1 in component q and 0s elsewhere. In this
case there is no ambiguity about the coset leader, and every received word is at
most distance 1 from a code word.
example 28
A (7, 4) code is a perfect code for which r = 3. One matrix generating such a
code is
h = G
1 1 0
1 0 1
0 1 1
1 1 1
1 0 0
0 1 0
0 0 1
W
Given the syndrome 101, the row of h that represents this binary number is
row 2. The coset leader for this syndrome is therefore 0100000 (a 1 in component 2,
0s elsewhere). You can check that (0100000)h = 101. The table of coset leaders
and the corresponding syndromes is partially filled in here.
Coset leaders
Syndromes
0000000
000
001
010
011
100
0100000
101
110
111
A received word of 1001100 has a syndrome of (1001100)h = 101, so it is decoded as
1001100 + 2 0100000 = 1101100