Interleaving - Interleaving in Error-correction Coding

Interleaving in Error-correction Coding

Interleaving is frequently used in digital communication and storage systems to improve the performance of forward error correcting codes. Many communication channels are not memoryless: errors typically occur in bursts rather than independently. If the number of errors within a code word exceeds the error-correcting code's capability, it fails to recover the original code word. Interleaving ameliorates this problem by shuffling source symbols across several code words, thereby creating a more uniform distribution of errors.

The analysis of modern iterated codes, like turbo codes and LDPC codes, typically assumes an independent distribution of errors. Systems using LDPC codes therefore typically employ additional interleaving across the symbols within a code word.

For turbo codes, an interleaver is an integral component and its proper design is crucial for good performance. The iterative decoding algorithm works best when there are not short cycles in the factor graph that represents the decoder; the interleaver is chosen to avoid short cycles.

Interleaver designs include:

• rectangular (or uniform) interleavers (similar to the method using skip factors described above)
• convolutional interleavers
• random interleavers (where the interleaver is a known random permutation)
• S-random interleaver (where the interleaver is a known random permutation with the constraint that no input symbols within distance S appear within a distance of S in the output).
• Another possible construction is a contention-free quadratic permutation polynomial (QPP). It is used for example in the 3GPP Long Term Evolution mobile telecommunication standard.

In multi-carrier communication systems, additional interleaving across carriers may be employed to mitigate the effects of prohibitive noise on a single or few specific carriers (e.g., frequency-selective fading in OFDM transmission).