Cryptography Reference
In-Depth Information
In reply to this question, estimation theory tells us that to minimize the
error probability in this case, the equalization and decoding operations must
be performed jointly, following the maximum likelihood criterion. Conceptu-
ally, implementing the optimal receiver then amounts to applying the Viterbi
algorithm, for example, on a "super-trellis" simultaneously taking into account
the constraints imposed by the code, the channel and the interleaver. However,
the "super-trellis" has a number of states that increases exponentially with the
size of the interleaver, which excludes a practical implementation of the optimal
receiver. It is therefore legitimate to question the feasibility of such a receiver
in the absence of an interleaver. Historically, this question has been asked in
particular in the context of data transmission over twisted-pair telephone ca-
bles (voice-band modems). These systems implement error correction coding
in Euclidean space (trellis coded modulations), without interleaving, and the
telephone channel is a typical example of a frequency-selective, time-invariant
channel. Assuming an encoder with
S
states, a constellation of
M
points and
a discrete channel with
L
coecients, the studies undertaken in this context
have shown that the corresponding "super-trellis" has exactly
S
(
M/
2)
L−
1
states
[11.13]. It is then easy to verify that in spite of the absence of an interleaver, the
complexity of the optimal receiver again rapidly becomes prohibitive, whenever
we wish to transmit a high rate of information (with modulations having a large
number of states) or when we are confronted with a channel having large delays.
To counter the unaffordable complexity of the optimal receiver, the solution
commonly adopted in practice involves performing the equalization and decoding
operations disjointly, sequentially in time. If we again take the example of GSM,
the received data are thus first processed by an MLSD equalizer. The estimated
sequence provided by the equalizer is then transmitted, after deinterleaving, to
a Viterbi decoder. The permutation function then plays a twofold role in this
context: not only combating slow fading on the channel, but also dispersing
error packets at the input of the decoder. This strategy presents the advantage
of simplicity of implementation, since the total complexity is then given by the
sum of the individual complexities of the equalizer and the decoder. However, it
necessarily leads to loss in performance compared with the optimal receiver since
the equalization operation does not exploit all the available information. To be
more precise, the estimation sent by the equalizer will not necessarily correspond
to a valid coded sequence since the equalizer does not take into account the
constraints imposed by the code. The performance of the disjoint solution can be
improved when we introduce the passing of weighted (probabilistic) information
instead of an exchange of binary data between the equalizer and the decoder. By
propagating a reliability measure on the decisions of the equalizer, the decoder
thus benefits from additional information to produce its own estimation of the
message, and we benefit from a correction gain generally of the order of several
dB (see for example [11.28, 11.23] or Chapter 3 in [11.15]). Despite this, the
