Interleaving is a key component of many digital communication systems involving forward error correction (FEC) coding. Interleaving the encoded symbols provides a form of time diversity to guard against localized corruption or bursts of errors. In the past the interleaving strategy was usually only weakly linked to the selected FEC scheme. Exceptions are concatenated FEC schemes such as concatenated convolutional and Reed-Solomon codes. In this case, the interleaving parameters are usually carefully selected to match the error correcting capabilities of the codes involved. Recently, interleavers have become an even more integral part of the code design itself. Such is the case for Turbo and Turbo-like codes. The problem of finding good interleavers for such codes is an on-going area of research.

CRC has developed a number of new interleaver technologies that are useful for both channel interleaving and for designing high-distance Turbo-codes. The various interleaver types and associated publications are listed below. Golden interleavers and DRP interleavers for Turbo-codes are highlighted further below.

• Golden and Dithered Golden Interleavers [CRO99b]
• High-Spread Random Interleavers [CRO00] [CROO4_Patent]
• Dithered Diagonal Interleavers [CRO00] [CROO4_Patent]
• Dithered Relative Prime (DRP) Interleavers [CRO01] [CRO02] [CRO04a] [CRO05a][CROO5_Patent]

Golden Interleavers

One problem with classical interleavers, such as row-column matrix interleavers, is that they are usually designed for a specific block size to provide a specific interleaving depth. This becomes a problem if any burst of errors ever exceeds the interleaver depth, and it is wasteful if the interleaver is over-designed (too long) and error-bursts are typically much shorter than the interleaver depth. In practice, most channels (or codes) usually generate error events of random length, and even the average length can be time varying, as well as unknown. This makes it very difficult to design an optimum interleaver using the classical approaches. What is sought is an interleaving strategy that is good for any error-burst length.

Golden interleavers provide an excellent solution to this problem. With Golden interleavers there is no concept of interleaver depth and no need to design the interleaver for a particular channel type or worst case error-burst length. Three new interleaver designs have been developed based on the golden section. They are called golden relative prime interleavers, golden interleavers, and dithered golden interleavers. These interleavers have excellent spreading properties and are useful for many applications. The first two interleavers make excellent channel interleavers, while the third has been shown to work well with Turbo-codes. For more information see [CRO99b]. For licensing information please email fec-info (at) crc.ca .

DRP Interleavers for Turbo-Codes

Dithered relative prime (DRP) interleavers are highly structured and ideal for designing low-memory interleaver banks for Turbo-codes. Each interleaver can be stored and implemented (on-the-fly if desired) using only a few parameters. The interleavers are designed to work well with both dual termination and dual tail-biting. The interleaver bank resolution is determined by the dither window size, M. For medium size blocks (i.e. K=256 to 4096) a good M value is 8, so the bank resolution is conveniently in bytes. The structure of DRP interleavers also makes it relatively easy to search the interleaver space for high distance codes. Example performance results for MPEG size packets are shown below. For a detailed description of DRP interleavers and more example performance results, see [CRO01] [CRO02] [CROO5_Patent].

Interleaver banks are currently available for 4-, 8-, and 16-state codes, with RSC (feedback, feedforward) polynomials of (7,5), (13,15), and (23,35) octal respectively. The block lengths range from 32 to 65536 data bits. The bank resolution depends on the block size, with 8-bit (byte) resolution available for most block lengths of practical interest. Additional interleaver banks can be developed as needed. For licensing information please email fec-info (at) crc.ca.

Simulation results are presented below for a conventional Turbo-code with binary antipodal signaling (e.g. BPSK or QPSK modulation). The Turbo-code consists of two parallel binary 16-state recursive systematic convolutional (RSC) codes, with (feedback, feedforward) polynomials (23, 35) octal. Dual termination was used, as described in [GUI94] [CRO98b]. The decoder used an enhanced maximum-log-a-posteriori-probability (max-log-APP) approach, with scaled extrinsic information, as described in [CRO01] [GRA98] [GRA99] [CRO00b_Patent]. It has been found that this decoding approach typically provides performance within 0.2 dB of true log-APP processing for 16-state codes. The maximum number of decoding iterations was set to 16. Early stopping was also used where the decisions before and after each half-iteration must agree 3 times in a row before stopping [GRA99].

The first figure shows the packet error rate results. The interleaver was a DRP interleaver with M=8 and K=1504 data bits (188 bytes, MPEG block size). The minimum measured (Hamming) distance for this DRP interleaver was 76. This is not necessarily the true minimum distance, but it is the lowest distance measured based on the recommended subset of worst-case input patterns to test (see [CRO01], [CRO02]). This distance occurs for input patterns of weight 6. The measured distances are much higher for patterns with lower input weights. These distance properties make the interleaver ideal for maintaining good distance with puncturing, as the figure clearly shows. The unpunctured code rate is R=1/3. Results are also shown for punctured code rates of R=2/5, 1/2, 3/5, 2/3, 3/4, 4/5, and 6/7. The second figure shows the corresponding bit error rates.

Some authors have suggested that the error flares experienced with parallel turbo coding, a phenomenon arising from their minimum distance, makes them unsuitable for applications requiring low error rates. The curves below are important because they demonstrate that excellent error flare performance can be achieved with well-designed interleavers.

Click the following figure for examples of PER performance with a DRP interleaver.

Click the following figure for examples of BER performance with a DRP interleaver.