Cryptography Reference
In-Depth Information
•
Calculate the accumulated metric associated with each node
s
i
,
μ
(
i,
s
i
)
.
It is equal to the accumulated metric associated with the survivor path
arriving in
s
i
:
μ
(
i,
s
i
)=min
s
i−
1
(
λ
(
T
(
i,
s
i−
1
,
s
i
)))
.
•
Initialization (instant i =0):
The initialization values of the metrics
μ
when commencing the algorithm
depend on the initial state
s
of the encoder:
μ
(0
,
s
)=+
=
s
0
and
μ
(0
,
s
0
)=0
. If this state is not known, all the metrics are initialized to the
same value, typically 0. In this case, the decoding of the beginning of the frame
is less ecient since the accumulated metrics associated with each branch at
instant 1 depend only on the branch itself. The past cannot be taken into
account since it is not known:
λ
(
T
(1
,
s
0
,
s
1
)) =
d
(
T
(1
,
s
0
,
s
1
))
.
∞
if
s
•
Calculating the decisions (instant i=k):
At instant
k
, if the final state of the encoder is known, the maximum likeli-
hood path is the survivor path coming from the node corresponding to the final
state of the encoder. The decoded sequence is given by the series of values of
d
i
,
i
ranging from 1 to
k
, stored in the memory associated with the maximum
likelihood path. This operation is called
trellis traceback
.
If the final state is not known, the maximum likelihood path is the survivor
path coming from the node with minimum accumulated metric. In this case,
the problem is similar to the one mentioned for initialization: the decoding of
the end of the frame is less ecient.
When the sequence transmitted is long, or even infinite in length, it is not
possible to wait for the whole transmitted binary sequence to be received to
begin the decoding operation. To limit the decoding latency and the size of
memory necessary to memorize the survivor paths, the trellis must be truncated.
Observing the algorithm unfold, we can note that by tracing back suciently in
time from instant
i
, the survivor paths coming from the different nodes of the
trellis nearly always converge towards a same path. In practice, memorizing the
survivors can therefore be limited to a time interval of duration
l
.Itisthen
sucient to do a trellis traceback at each instant
i
over a length
l
in order to
take the decision on the data
d
i−l
. To decrease the complexity, the survivors
are sometimes memorized on an interval higher than
l
(for example
l
+3). The
number of trellis traceback operations is then decreased (divided by 3 in our
example) but each of the tracebacks provides several decisions (
d
i−l
,d
i−l−
1
and
d
i−l−
2
, in our example).
The higher the code memory and coding rate are, the greater the value of
l
must be. We observe that, for a systematic code, values of
l
corresponding to
the production by the encoder of a number of redundancy symbols equal to 5
times the constraint length of the code are sucient. As an example, for coding
rate
R
=1
/
2
, we typically take
l
equal to
5(
ν
+1)
.
