Cryptography Reference
In-Depth Information
Suppose that the above codeword
c
is sent through the channel and received
as
r
=(
r
1
,...,r
n
). then we define the
error vector
to be
−
e
=
r
c
=(
e
1
,...,e
n
)
.
Thus, when we want to decode, the decoder must determine from
r
the codeword
c
, if an error occurs, which will be the case when
e
j
= 0 for any
j
=1
,
2
,...,n
.
However, it turns out that there is a veryelegant means for accomplishing this
task as follows. The first thing that we note, as a motivator, is that if
P
is the
paritycheck matrix for the code, then
c
P
t
=
0.
In the following, we need to employsome group theoryof a basic kind. The
reader needing a refresher on the concept of cosets and related notions should
consult Appendix A, especiallyDefinition A.37 on page 488. The following
employs the fact that any linear code is an additive subgroup of a suitable
q
.
F
Syndromes
:If
P
is a parity-check matrix for a linear [
n,k
]-code
C
, then
for any
x
q
, the 1
∈
F
×
(
n
−
k
) row vector,
S
(
x
)=
x
P
t
,
is called the
syndrome of
x
.
It is a basic fact that
S
(
x
)=
0 if and onlyif
x
∈
C
. A pleasant feature
of the syndrome is that it depends solely upon the error pattern and not the
message itself. The receiver, who detects
e
=
0 , will know both
r
and
e
,so
will be able to determine
c
. To see that the syndrome's dependence is only on
the error pattern, consider the following:
S
(
r
)=
r
P
t
=(
c
+
e
)
P
t
=
c
P
t
+
e
P
t
=
e
P
t
since
c
P
t
=
0.
The syndrome is a valuable piece of information about
e
, but we can do
better. There is a limitation since for a given
S
(
r
)
n
−
q
, the collection of
∈
F
solutions
e
P
t
=
S
(
r
) forms a coset of the code
C
in
q
of the form, for a fixed
F
value of
e
, given by
C
+
e
=
{
c
+
e
:
c
∈
C
}
.
It follows that two vectors are in the same coset if and onlyif theyhave the
same syndrome. Hence, there is a one-to-one correspondence between the cosets
and the syndromes.
Here we are viewing
F
q
as an additive group of
q
elements and
C
is a subgroup
of the direct product
q
, of which
C
+
e
is a coset.
11.10
Since the
cardinalityof each coset is
q
k
, and there are
q
n
−
k
cosets of
C
in total, given
that there are
q
n
−
k
syndromes, then the receiver has to distinguish among the
q
k
possibilities for
e
. We need another concept to simplifythe process.
Earlier we spoke about the weight of a binaryvector being the number of
nonzero elements appearing in it. If we select a vector of minimum weight in
F
×···×
F
q
11.10
It is for this reason that linear codes are often called
group codes
.
Search WWH ::
Custom Search