Cryptography Reference
In-Depth Information
Sub-optimal PNP algorithms (
Δ
>
1
)
In the state of the art there are three algorithms for
Δ
>
1 concerning the PNP.
Min-sum or BP-Based algorithm (
Δ=2
)
This algorithm proposed by Fossorier
et al.
[9.20] requires no computations in
the PNP. Indeed, the authors suggest approximating parity processing algorithm
(9.22) by:
⎧
⎨
|
Z
j,p
|
=
Min
j
∈
J
(
p
)
/j
(
|
L
j
,p
|
)
(9.33)
sign
(
Z
j,p
)=
sign
(
L
j
,p
)
⎩
j
∈J
(
p
)
/j
Only the computation of the magnitude changes: it is approximated by excess by
the minimum of the magnitudes of the messages entering the PNP. Processing
in the PNP therefore involves only computing the sign and sorting the two
lowest magnitudes of the input messages. Note that this approximation makes
the iterative decoding processing independent of the knowledge of the level of
noise
σ
2
of the channel. The loss in performance is of the order of around 1 dB
compared to the
BP
algorithm.
This approximation by excess of the Min-Sum algorithm can however be
compensated by simple methods.
It is thus possible to reduce the value of
|
Z
j,p
|
by assigning it a multiplicative factor A strictly lower than 1. It is also
possible to subtract from it an offset B (B
>
0), taking the precaution, however,
of saturating the result to zero if the result of
|
Z
j,p
|−
B
is negative. The value
c
is therefore:
|
|
Z
j,p
|
|
Z
j,p
|
of
corrected
c
=
A
Z
j,p
|
×
max(
|
Z
j,p
|−
B,
0)
(9.34)
sign
(
Z
j,p
)=
sign
(
L
j
,p
)
j
∈
J
(
p
)
/j
These two variants of the Min-sum algorithm are called
Offset BP-based
and
Normalized BP-Based
[9.10] respectively. The optimization of coecients
A
and
B
enables decoders to be differentiated. They can be constant or variable
according to the signal to noise ratio, the degree of the parity constraint, or the
processed iteration number, etc.
min
algorithm
(Δ =
λ
+1)
This algorithm was presented initially by Hu
et al.
[9.27, 9.28] then re-
formulated independently by Guilloud
et al.
[9.24]. Function
f
, defined by
Equation (9.35), is such that
f
(
x
)
is large for low
x
, and low when
x
is large.
Thus, the sum in (9.35) can be approximated by its
λ
highest values, that is to
say, by the
λ
lowest values of
λ
−
. Once the set denoted
J
λ
(
p
)
of minima
λ
is
obtained, the PNP will calculate
Δ=
λ
+1
distinct magnitudes:
|
L
j,p
|
⎛
⎞
f
(
x
)=ln tanh
x
2
⎝
⎠
|
Z
j,p
|
=
f
f
|
L
j
,p
|
with
(9.35)
j
∈
J
λ
(
p
)
/j
