Cryptography Reference
In-Depth Information
This decoding procedure is applicable when the number of codewords is not
too high. In the presence of a large number of codewords we can use a Chase
algorithm whose principle is to apply the above decoding procedure and restrict
the search space to a subset of codewords.
Chase algorithm
The Chase algorithm is a sub-optimal decoding procedure that uses the max-
imum
a posteriori
likelihood criterion but considers a very reduced subset of
codewords. To determine this subset of codewords, the Chase algorithm works
in the following way.
•
•
Step 1: The received word
r
, made up of analogue symbols, is transformed
into a word with binary symbols
z
0
=(
z
00
···
z
0
j
···
z
0
n−
1
)
by threshold-
ing,
z
0
j
=
sgn
(
r
j
)
with the following convention:
sgn
(
x
)=1
if
x
0
=0
if
x<
0
The binary word
z
0
is then decoded by a hard decision algorithm other
than the maximum
a posteriori
likelihood algorithm (we will present algo-
rithms for decoding block codes later). Let
c
0
be the codeword obtained.
•
Step 2: Let
j
1
,j
2
,
···
,j
t
be the positions of the least reliable symbols, that
is, such that the
|
r
j
|
amplitudes are the smallest.
2
t
1
words
e
i
are built by forming all the non-null binary combina-
tions possible on positions
j
1
,j
2
,
−
···
,j
t
.
On the positions other than
j
1
,j
2
,
,j
t
, the symbols of
e
i
are set to zero. Recall that
t
is the correc-
tion capability of the code.
···
Step 3: Each of the
2
t
•
−
1
words
e
i
is used to define the words
z
i
with:
z
i
=
z
0
+
e
i
A hard decoder processes the words
z
i
to obtain at most
2
t
1
codewords
c
i
. Note that the word at the output of the algebraic decoder is not
always a codeword and only codewords will be considered when applying
the decision criterion.
−
•
Step 4: The maximum
a posteriori
likelihood rule is applied to the subset
of the codewords
c
i
created in the previous step.
