724
Modeling Arithmetic, Computation, and Languages
tHeoRem on synDroMEs AnD CosEts
Let h be an n × r parity-check matrix generating a group code K. Then for
X, Y [ Z
n
2 , X and Y are in the same left coset of K in 3Z
n
2 , + 2 4 if and only if X and
Y have the same syndrome.
Summary: To decode a received n-tuple X, find the coset to which X belongs and
add that coset’s leader to X.
example 26
Consider the code of Example 21. Here n = 5 and K = 500000, 01111, 10101,
110106. Suppose the 5-tuple X = 11011 is received. Because the set of code
words is so small, we can easily pick out the closest code word, which is 11010.
We would decode X as 11010. (From Example 23 we know that the canonical
matrix h for this code is 5 × 3, so r = 3. Knocking off the three check bits, the
original information bits were 11.)
Now let’s try our decoding procedure. The elements of X ’s coset are
11011 + 2 00000 = 11011
11011 + 2 01111 = 10100
11011 + 2 10101 = 01110
11011 + 2 11010 = 00001
The coset leader (the element of minimum weight in this coset) is clearly 00001.
Adding this to X we get
11011 + 2 00001 = 11010
and we decode X to 11010, as before.
But we haven’t really solved the efficiency problem. To find all the elements
of X’s coset requires adding all the code words to X, which still requires knowing
all 2
m
code words. For a better approach, we need one new idea.
Definition synDroME
In the group code generated by an n × r parity-check matrix h, for any X [ Z
n
2 ,
the r-tuple X # h is the syndrome of X.
The syndrome is useful because of the following theorem.
Proof: Suppose X and Y are in the same left coset of K in 3Z
n
2 , + 2 4. Then
Y = X + 2 C i for some C i [ K, and Y # h = (X + 2 C i ) # h = X # h + 2 C i # h (because multiplication by h is a homomorphism) = X # h + 2 0 r (because C i is in
the kernel of this homomorphism) = X # h. Therefore Y # h = X # h and X and Y
have the same syndrome.
Now suppose that Y # h = X # h. Then Y # h + 2 X # h = 0 r , or
( Y + 2 X ) # h = 0 r , which makes Y + 2 X a code word C i in K. If Y + 2 X = C i ,
then Y = X + 2 C i and Y and X are in the same coset. End of proof.
Modeling Arithmetic, Computation, and Languages
tHeoRem on synDroMEs AnD CosEts
Let h be an n × r parity-check matrix generating a group code K. Then for
X, Y [ Z
n
2 , X and Y are in the same left coset of K in 3Z
n
2 , + 2 4 if and only if X and
Y have the same syndrome.
Summary: To decode a received n-tuple X, find the coset to which X belongs and
add that coset’s leader to X.
example 26
Consider the code of Example 21. Here n = 5 and K = 500000, 01111, 10101,
110106. Suppose the 5-tuple X = 11011 is received. Because the set of code
words is so small, we can easily pick out the closest code word, which is 11010.
We would decode X as 11010. (From Example 23 we know that the canonical
matrix h for this code is 5 × 3, so r = 3. Knocking off the three check bits, the
original information bits were 11.)
Now let’s try our decoding procedure. The elements of X ’s coset are
11011 + 2 00000 = 11011
11011 + 2 01111 = 10100
11011 + 2 10101 = 01110
11011 + 2 11010 = 00001
The coset leader (the element of minimum weight in this coset) is clearly 00001.
Adding this to X we get
11011 + 2 00001 = 11010
and we decode X to 11010, as before.
But we haven’t really solved the efficiency problem. To find all the elements
of X’s coset requires adding all the code words to X, which still requires knowing
all 2
m
code words. For a better approach, we need one new idea.
Definition synDroME
In the group code generated by an n × r parity-check matrix h, for any X [ Z
n
2 ,
the r-tuple X # h is the syndrome of X.
The syndrome is useful because of the following theorem.
Proof: Suppose X and Y are in the same left coset of K in 3Z
n
2 , + 2 4. Then
Y = X + 2 C i for some C i [ K, and Y # h = (X + 2 C i ) # h = X # h + 2 C i # h (because multiplication by h is a homomorphism) = X # h + 2 0 r (because C i is in
the kernel of this homomorphism) = X # h. Therefore Y # h = X # h and X and Y
have the same syndrome.
Now suppose that Y # h = X # h. Then Y # h + 2 X # h = 0 r , or
( Y + 2 X ) # h = 0 r , which makes Y + 2 X a code word C i in K. If Y + 2 X = C i ,
then Y = X + 2 C i and Y and X are in the same coset. End of proof.