Cryptography Reference
In-Depth Information
qualified as the coset leader. The random choice of
0010
as coset leader shows
that we obtain the same coset in either case since choice of the latter would just
be a permutation of the third-row elements.
)
The parity check matrix is
P
=
1110
0101
,
and since vectors in the same coset have the same syndrome, we may look at
the received vector
r
, calculate its syndrome
S
(
r
)=
r
P
t
, then find the position
in the row. Since
r
=
c
+
a
where
c
is some codeword and
a
is the coset leader
for the row, then we have a means for decoding
r
, namely,
c
=
r
a
. Hence,
the decoding is the vector sitting at the top of the column in which
r
sits. For
instance, if
r
=(1
,
0
,
1
,
1)
, then
S
(
r
)=(1
,
1)
, and this represents the fourth
row, with coset leader
a
=(0
,
0
,
0
,
1)
. The value at the top of the column in
which
r
sits is
c
=(1
,
0
,
1
,
0)
. Indeed,
−
r
−
a
=(1
,
0
,
1
,
1)
−
(0
,
0
,
0
,
1) = (1
,
0
,
1
,
0) =
c
.
In fact, since all we use from the array is the coset leader and calculation of
the syndrome of the received vector, then these two columns are all that need
be stored on a computer, for instance, making this an e
?
cient mechanism for
decoding. These two columns make up an array called the
syndrome look-up
table
, which in our case is given by the following:
Coset Leader Syndrome
(0
,
0
,
0
,
0)
(0
,
0)
(0
,
1
,
0
,
0)
(1
,
1)
,
(0
,
0
,
1
,
0)
(1
,
0)
(0
,
0
,
0
,
1)
(0
,
1)
Now we formalize the decoding illustrated in Example 11.10.
Syndrome Decoding
The following algorithm for the decoding of a linear [
n,k
]-code
C
, needs
far fewer iterations than anynearest neighbour decoding scheme, where one
searches for the nearest codeword to a received vector. In what follows
P
is
assumed to be the parity-check matrix for
C
.
1. For a received vector
r
, calculate the syndrome
S
(
r
)=
r
P
t
.
2. Find
S
(
r
) in the second column of the syndrome look-up table, and find its
coset leader
a
in the first column.
3. Decode via
c
=
r
−
a
.
Search WWH ::
Custom Search