Interleaving and MLSE

Interleaving

Interleaving rearranges the order of coded bits before transmission so that a burst of errors caused by a deep fade is spread out into isolated single errors after de-interleaving. Error-correcting codes can correct scattered errors easily but fail on long bursts, so interleaving gives time diversity without adding redundancy.

Block interleaver (m rows × n columns): bits are written into the array row by row and read out column by column. The receiver de-interleaver does the reverse.

 Write by rows →         Read by columns ↓
  1   2   3   4          out: 1 5 9 13 2 6 10 14
  5   6   7   8               3 7 11 15 4 8 12 16
  9  10  11  12
 13  14  15  16

Suppose a fade wipes out 4 consecutive transmitted bits, e.g. 1, 5, 9, 13. After de-interleaving they appear in different rows (code words), each with only one error, which the decoder can correct.

 Channel burst: [1 5 9 13]   (4 bits in a row)
 After de-interleave:
  X  2  3  4
  X  6  7  8      one error per code word
  X 10 11 12
  X 14 15 16

The interleaving depth must exceed the burst length, but larger depth adds delay; speech systems therefore limit delay to around 40 ms (GSM interleaves over 8 bursts).

Maximum Likelihood Sequence Estimation (MLSE)

MLSE is a non-linear equalizer that, instead of deciding symbols one by one, chooses the whole data sequence that is most likely to have produced the received signal. It treats the ISI channel as a finite-state machine and uses the Viterbi algorithm to search efficiently.

r(t)->[Matched ]->[ MLSE (Viterbi) ]-> data
      [ filter ]        ^
           |            |
           +->[Channel estimator]
               (from training)

1. A training sequence lets the channel estimator find the channel impulse response, which spans the current symbol plus L earlier symbols (channel memory L).
2. The trellis then has M^L states (M = alphabet size). For each received sample the Viterbi algorithm computes path metrics (squared distance between the received sample and the expected noise-free output) for every state transition.
3. Only the best ("survivor") path into each state is kept.
4. After enough samples the survivor with the minimum total metric gives the most likely transmitted sequence.

MLSE is optimal in the sense of minimizing sequence error probability and handles severe ISI, but complexity grows exponentially with channel length. GSM uses a Viterbi (MLSE) equalizer covering about 4 bit periods (≈ 15 µs) of delay spread.