Cryptography Reference
In-Depth Information
In Example 11.10, if we receive
r
=(1
,
0
,
0
,
0), then
S
(
r
)=(1
,
0), which is
in the third row of the second column of the syndrome look-up table, which has
coset leader
a
=(0
,
0
,
1
,
0). Hence, we decode via
c
=
r
−
a
=(1
,
0
,
0
,
0)
−
(0
,
0
,
1
,
0) = (1
,
0
,
1
,
0)
,
which we see is the entryat the top of the column of the Slepian arrayin which
r
sits.
The general process of syndrome decoding for a linear [
n,k
]-code
C
is illus-
trated as follows.
The notation
a
will denote the decoder's act of calculating the syndrome
S
(
r
) and associating
it with the coset leader
a
for the row in which it sits from the syndrome look-up
table. The following illustration (Diagram 11.3) complements Diagram 11.2 on
page 449.
S
(
r
)
↔
Syndrome Decoding
Diagram 11.3
N
O
I
S
Y
Received
Message
c
=(
c
1
,...,c
k
)
decoded word
received vector
−−−−−−−−−−−−−→
r
=(
r
1
,...,r
n
)
Decoder
S
(
r
)
−−−−−−−−−−−−→
r
↔
a
C
H
A
N
N
E
L
a
=
c
=(
c
1
,...,c
n
)
−
Now we turn to a well-known collection of linear codes. These are important
in removing noise, for instance, from long-distance telephone calls. First we need
the notion of
single-error-correcting codes
, which are codes capable of correcting
all error patterns of weight no bigger than 1. The following are single-error-
correcting codes that are easyto employfor encoding and decoding.
The Hamming Codes
Although the codes we discuss herein maybe defined over any
F
q
(see page
596), we confine our focus to the binarycase for ease of presentation and overall
simplicityof elucidation.
Search WWH ::
Custom Search