Digital Signal Processing Reference
In-Depth Information
a particular state sequence or a path
s
[
k
]
for which the probability of the channel
observations sequence
r
[
k
]
given
s
[
k
]
is maximum, i.e.
s
[
k
]=
arg max
s
[
k
]
P
(
r
[
k
]
|
s
[
k
]) =
arg max
s
[
k
]
P
(
r
[
k
]
|
s
[
k
])
P
(
s
[
k
]) =
arg max
s
[
k
]
P
(
r
[
k
]
,
s
[
k
])
(21)
assuming that each state sequence is equally likely. Assuming further that the noise
samples are conditionally independent, we can write
L
r
k
=
0
P
(
s
[
k
+
1
]
|
s
[
k
])
L
r
k
=
0
P
(
r
[
k
]
|
s
[
k
+
1
]
,
s
[
k
])
,
(
[
]
,
s
[
]) =
P
r
k
k
and define the
branch metric
λ
(
b
[
k
]) =
−
ln
P
(
s
[
k
+
1
]
|
s
[
k
])
−
ln
P
(
r
[
k
]
|
b
[
k
]=
{
s
[
k
+
1
]
,
s
[
k
]
}
)
to quantify the likelihood that a given state transition occurred. Then, we obtain the
log probability of any state sequence, or path, as a sum of branch metrics along the
state transitions in that path,
L
r
k
=
0
λ
(
b
[
k
])
,
L
(
s
[
k
]) =
−
ln
(
P
(
r
[
k
]
,
s
[
k
]) =
which is also referred to as the path metric. The label
S
is used to designate
the shortest path (the path with the smallest path metric) through the trellis ending
in state
s
(
s
[
k
])
[
k
]
, which is known as a
survivor path
since all longer paths also ending in
state
s
[
k
]
are discarded. The path metric of the survivor path ending in state
s
[
k
]
is
S
labeled
M
.
able/valid state transitions
b
(
s
[
k
])
,i.e.
M
(
s
[
k
]) =
L
(
(
s
[
k
]))
have equal probability. The Viterbi algorithm is now
a dynamic programming approach to finding the path through the trellis of smallest
accumulated branch metric.
MLSE implementation in high-speed links brings up a number of practical
considerations. First, the link needs to be ADC-based. This constraint is no longer
a major issue for data-rates in the 10 Gb/s range today though power considerations
may preclude their use in many back-plane applications in the short-term. Second,
since the data is continuously transmitted, it will be necessary, for latency reasons,
to output bit decisions as the data is processed. This is called the
sliding window
version of the Viterbi algorithm, which requires a
finite look-back
window of length
D
. It is desirable to make the look-back window as long as possible, in order to
exist at time
k
[
k
]
D
when processing at time
k
. However, the storage requirements and
complexity of the algorithm per output symbol will increase linearly in
D
.Wehave
−
