Random errors and burst errors
An interleaver is there because of the way errors arrive, not because of the code itself. Two patterns matter.
Random errors. Error locations are independent. A channel that does this has no memory: an error in one position says nothing about the next.
Burst errors. Errors arrive in runs. A deep fade is the usual example. The channel has memory, and a code that was designed for scattered errors spends its whole correction budget on one fade.
What the interleaver does
The practical remedy is to keep a code that is good at scattered errors, and to permute the symbols so that a burst is scattered before the decoder sees it. The two constructions in wide use are the block interleaver and the convolutional interleaver.
A block interleaver is filled row by row with \(L\) codewords of length \(n\), and emptied column by column. A burst of \(L\) transmitted symbols, or fewer, then hits each codeword in at most one position. The decoder sees \(L\) single errors instead of one run of \(L\). The depth \(L\) has to cover the longest burst you are willing to design for. The price is delay: the receiver cannot start until a whole block has arrived, and on a voice channel that pause is obvious.
A convolutional interleaver avoids storing the whole block. It still has to be filled before the first symbol comes out, and that initial delay remains. Sklar notes that the memory is about half of the block interleaver’s [1]. Either way, a jammer who knows the permutation can aim at it. Randomizing the order, the subject of the following article, is the usual answer.
There is a real objection from the coding side. A burst has structure, and a code designed for bursts can use that structure. Interleaving throws the structure away and then asks a random-error code to clean up. Viterbi’s look at a pulse-jammed channel is the counterexample that settled the argument for most links: using the burst structure was not enough, and interleaving was still required [2]. A burst-error code still wins on delay, because it can do the same job with a shorter interleaver.
A depth-4 block, written out
Four codewords of five symbols, filled by rows and read by columns. A burst of four channel symbols lands in four different codewords.
import numpy as np
codewords = np.arange(20).reshape(4, 5) # 4 codewords, 5 symbols each
transmitted = codewords.T.ravel() # column by column
print("rows (codewords)", codewords.tolist())
print("on the channel ", transmitted.tolist())
received = transmitted.copy()
received[3:7] = -1 # a burst of 4
restored = received.reshape(5, 4).T
print("after deinterleave")
for i, row in enumerate(restored):
print(i, row.tolist(), "errors", int(np.sum(row < 0)))
References
[1] B. Sklar, Digital Communications, 2nd ed., Prentice Hall, 2001.
[2] A. J. Viterbi, “Spread spectrum communications: myths and realities,” IEEE Communications Magazine, vol. 17, no. 5, pp. 11–18, May 1979.
See also
[1] Block interleaver design for Reed–Solomon codes
[2] Random interleavers