Why is an interleaver often placed between an outer block code and an inner convolution code?

Question

It seems that when doing FEC with a concatenated-code, an interleaver is often placed between the outer block code and the inner convolution code. The explanations I've seen say that this is because the convolution decoder often has errors in bursts.

However, if we assume that we're using a Reed-Solomon decoder with 8-bit symbols, then spreading the bursts onto multiple blocks would seem to increase errors rather than decrease them. What am I missing that explains why this interleaving is good?

Rough idea of the decode and encode process:

• Encode:

$$\boxed{\textrm{Data}}{\longrightarrow}\boxed{\textrm{RS Encoder}}{\longrightarrow}\boxed{\textrm{Interleaver}}{\longrightarrow}\boxed{\textrm{Convolution Encoder}}{\longrightarrow} \boxed{\textrm{Modulator}}$$

• Decode:

$$\boxed{\textrm{Demodulator}}{\longrightarrow}\boxed{\textrm{Convolution Decoder}}{\longrightarrow}\boxed{\textrm{De-interleaver}}{\longrightarrow}\boxed{\textrm{RS Decoder}}{\longrightarrow}\boxed{\textrm{Data}}$$

Answer 1

As the other answers mention, the use of FEC results in post-decoding errors occurring in bursts. Indeed, this happens regardless of whether the code is a convolutional code or a block code. With a $(n,k)$ block code, the decoder output ($k$ bits) from the decoding of one received word is (hopefully with high probability) completely correct, or it has an unknown number of errors in it that can be regarded as a burst error of length $k$. With a convolutional code, the decoder output is mostly correct as the decoder finds the correct path through the trellis, but occasionally the decoder's chosen path deviates from the correct path and later rejoins the correct path during which time there is a burst of errors. In contrast to block codes, there can be multiple isolated burst errors (of variable lengths) in a single transmission using a convolutional code. Also, the number of data bits in a single transmission is far larger than the typical values of $k$ for a block code.

The idea behind a concatenated coding scheme is that with an inner code suited to the physical channel, and an outer code over a very large symbol alphabet, we can make the burst errors in the inner decoder output look like a single symbol error to the outer code. This is important because the outer code should be a very high rate code because the net rate is product of the inner code rate (more or less determined by the channel and the link budget) and the outer code rate. Unfortunately, outer codes over very large alphabets are very expensive to implement, and so interleaved Reed-Solomon codes over smaller alphabets (often GF$(2^8)$ ) are used (with interleaving at the symbol level, as Jim Clay points out). Because of the interleaving, the burst errors in the inner decoder output become single symbol (byte) errors in the received words of the interleaved Reed-Solomon code.

All the above is mostly a rehash of what the answers by Bryan and Jim Clay have already said, but I wish to point out the following.

Interleaved Reed-Solomon codewords can be decoded much more efficiently and with smaller delay if they are not de-interleaved first.

A Reed-Solomon decoder that can decode interleaved codewords is different from the off-the-shelf standard Reed-Solomon decoders that are available, and the use of such a decoder might not be feasible if the development team does not have control of this aspect of the design. But, if such a decoder is used, the de-interleaver can be moved from the between the inner decoder and outer decoder to just after the outer decoder. The de-interleaver is also smaller since it has to deinterleave a $K\times L$ array instead of a $N \times L$ array (for a $(N.K)$ Reed-Solomon code interleaved to depth $L$.

If a delay-scaled Reed-Solomon encoder is used along with the Reed-Solomon decoder for interleaved codewords described above, the interleaver at the transmitter and the de-interleaver at the receiver can be eliminated entirely.

The output of the delay-scaled encoder (see also this paper which is unfortunately behind a paywall) is a set of interleaved Reed-Solomon codewords, but is not the same sequence of bytes that one would get from doing a standard Reed-Solomon encoding followed by interleaving. So, no further interleaving is necessary. The output of the interleaved Reed-Solomon decoder is the same byte sequence in the same order that went into the delay-scaled Reed-Solomon encoder, and so no de-interleaving is necessary at the decoder, either.

Answer 2

Block codes (such as the Reed-Solomon you mentioned) have the ability to detect and correct a certain number of errors that is tied directly to the properties of that code (minimum Hamming distance for example). By passing on burst errors from the inner-channel, this may put too many errors in a single block than the code is capable of correcting. If, however, we spread these errors to multiple block codes, then each respective block code will hopefully have a small number of errors it's capable of correcting. As an example with probably unrealistic numbers (these type of setups are often used with massive convolutional codes), if your block code is capable of correcting 1 error, and you get a burst of 4 errors, then you will have 1 block with 4 errors, 1 block with 3 and 1 block with 1, or 2 blocks with with 2 errors. In all scenarios, we have an uncorrectable error if we don't do any interleaving. However, if we can interleave such that we guarantee bursts of 4 errors will be spread in 4 blocks, then we can correct all errors and all is well.

Answer 3

I think the part that you are missing is that the burst of errors out of the convolutional decoder is (or at least should be) a rare event. Thus, every once in a while there will be a burst of errors, but most of the time there are no errors coming out of the convolutional decoder.

If there wasn't an interleaver whenever a burst of errors occurred one or two blocks (depending on where the burst occurred relative to the block boundaries) would be swamped with errors while their neighbors would have no errors. The interleaver spreads the errors out so that they are "shared" between many blocks, making them manageable by all the blocks.