Cryptography Reference
In-Depth Information
8.4.4 The Hartmann-Nazarov algorithm
Hartmann et al. [8.8] used the properties of duality to describe a maximum
likelihood decoding method for linear codes. Initially, only a hard decision was
provided by the algorithm. Hagenauer [8.7] then took up these ideas in order
to make available the extrinsic values necessary for turbo decoding. Finally,
Nazarov and Smolyaninov [8.13] showed how to reduce the complexity cost by
using the fast Hadamard transform. This paragraph summarizes these three
reference articles.
Let
r
=(
r
1
, ..., r
n
)
be the received word. The code used is a linear code of
length
n
and dimension
k
of a generating matrix
G
=
{
g
ij
,
0
≤
i<k,
0
≤
j<n
}
and parity control matrix
H
=
. We assume that
the transmission has been done on a channel perturbed by a Gaussian noise with
null mean and variance equal to
σ
2
.
Putting
ρ
l
=
{
h
ij
,
0
≤
i<n
−
k,
0
≤
j<n
}
tanh(
r
l
/σ
2
)
, we show that the LLR maximum likelihood of
the
l
-th bit in the frame is:
−
LLR
l
=ln
1
C
(
l
)
1+
C
(
l
)
−
(8.2)
with:
1+
F
D
(
h
l
)
F
D
(0)
+
1
C
(
l
)=
ρ
l
2
1
2
ρ
l
F
D
(
h
l
)
F
D
(0)
−
where
h
l
is the
l
-th column of the parity control matrix and function
F
D
is such
that
D
ν
(
l
)exp
jπ
2
n−k
−
1
n−k−
1
F
D
(
h
l
)=
ν
m
h
ml
ν
=0
m
=0
n
−
m
=0
k
−
1
ν
m
2
m
),
ν
m
is the
m
-th bit of the binary representation of integer
ν
(
ν
=
and:
n−
1
(
ρ
l
)
t
ν
(
l
)
D
ν
(
l
)=
l
=0
t
ν
(
l
)
being the
l
-th bit of the
ν
-th vector of the dual of the code, that is, therefore:
t
ν
(
l
)=
n−k−
1
mod 2 =
ν
m
h
ml
ν, h
l
mod 2
m
=0
The calculation of
D
ν
(
l
)
normally requires
n
multiplications. But using the
dual code and applying a fast Hadamard transform, it is possible to lower this
cost to one term of the order of
n
−
k
multiplications. If the coding rate is
