Interleaving

In any real communication system, noise does not always arrive as isolated random bit errors. Channels such as fading wireless links, magnetic storage media, and powerline communications frequently produce burst errors, where a sequence of consecutive bits is corrupted together. Most standard error-correcting codes are designed to correct random, independent errors and perform very poorly when errors cluster in bursts.

Interleaving is the technique used to convert burst error channels into equivalent random error channels, allowing standard error-correcting codes to work effectively. This is a core topic in digital communications for GATE and university exams because it appears in the context of convolutional codes, turbo codes, LDPC codes, and OFDM systems.

Core Concept Explanation

An error-correcting code with minimum distance d_min can correct up to t = floor((d_min - 1)/2) random errors per codeword. If a burst of length b corrupts b consecutive bits in a single codeword and b is greater than t, the code cannot correct it. Interleaving solves this by spreading the bits of each codeword across many symbol positions before transmission.

There are two main types. Block interleaving writes n codewords into an m x n matrix row by row, then transmits column by column. A channel burst of length b then affects at most one bit per row (one bit per codeword) when b is less than or equal to m. The de-interleaver at the receiver fills the matrix column by column and reads out row by row, restoring original codeword order.

Convolutional interleaving (also called cross-interleaving) uses a bank of shift registers of varying lengths. Input symbols are routed to registers of lengths 0, T, 2T, 3T, ... and read out in sequence. This achieves the same burst error spreading as block interleaving but with half the end-to-end delay and the same memory, making it preferred in real-time applications.

Mathematical Expression

For a block interleaver of depth d (rows) and span L (columns, equal to codeword length), the total interleaver size is d times L symbols. The maximum correctable burst length is b_max = d times t, where t is the single-error-correcting capability of the code. The total delay introduced is 2 times d times L symbol periods (factor of 2 accounts for both interleaver and de-interleaver).

For a convolutional interleaver with d branches and inter-branch delay T, the equivalent burst correction capability is the same as a block interleaver of depth d. However, the total memory required is d times (d-1) times T / 2 symbols (compared to d times L for the block case), and the one-way latency is d times (d-1) times T / 2 symbol periods, exactly half the round-trip delay of the equivalent block interleaver.

Practical Understanding

Interleaving is ubiquitous in modern systems. GSM mobile telephony uses block interleaving over 8 bursts, spreading each 456-bit coded speech block across 8 time slots. The CD audio standard uses cross-interleaved Reed-Solomon coding (CIRC) which employs two levels of interleaving to handle scratches and dropouts. LTE and 5G use random interleaving within turbo and LDPC encoders respectively to randomize error patterns.

There is an inherent tradeoff between interleaving depth and latency. Deep interleaving provides better burst error correction but introduces larger delays, which is unacceptable for voice telephony (where end-to-end delay must stay below about 150 ms). Data applications can tolerate larger delays, enabling deeper interleaving and more robust burst error protection.

Given:
Block interleaver, depth d = 8 rows, codeword length L = 40 bits per row
Error-correcting code: t = 2 (can correct up to 2 random errors per codeword)

Why this formula applies:
Block interleaver spreads burst errors; max correctable burst = d * t

Formula:
b_max = d * t
Total delay = 2 * d * L (symbols)

Substitution:
b_max = 8 * 2 = 16 bits
Total interleaver memory = d * L = 8 * 40 = 320 bits
Total delay = 2 * 8 * 40 = 640 symbol periods

Calculation:
A burst of up to 16 consecutive bit errors can be corrected.
The interleaver/de-interleaver together introduce 640 symbol periods of delay.

Final Answer:
Maximum correctable burst length = 16 bits, total system delay = 640 symbol periods

Exam Tip: For block interleaving, always remember b_max = d times t, where d is the interleaving depth and t is the per-codeword correcting capability. The total delay is 2 times d times L, not d times L, because both the interleaver AND the de-interleaver each contribute d times L symbol periods of delay.

• Block interleaver: writes codewords row by row, transmits column by column; depth d, span L, total memory d times L.
• Maximum correctable burst length with block interleaving: b_max = d times t.
• Total end-to-end delay for block interleaving: 2 times d times L (interleaver + de-interleaver).
• Convolutional interleaver uses shift registers of lengths 0, T, 2T, ... (d-1)T; achieves same burst correction with half the delay.
• Random interleavers are used in turbo codes and LDPC codes to maximize the spread of error events through the decoder.

Quick Revision

• Purpose: convert burst error channel into equivalent random error channel for standard codes.
• Block interleaver: m x n matrix, write rows, transmit columns; b_max = d * t.
• Delay formula: total delay = 2 * d * L symbol periods.
• Convolutional interleaver: same burst correction as block, but delay is halved; preferred for real-time voice.
• Deeper interleaving = handles longer bursts but more latency; fundamental tradeoff.
• Exam trap: total delay is 2dL not dL; both interleaver and de-interleaver contribute equally.
• Applications: GSM (block), CD audio CIRC (convolutional), LTE turbo (random), 5G LDPC (random).