Interleaving
From Wikipedia, the free encyclopedia
Interleaving in computer science is a way to arrange data in a non-contiguous way in order to increase performance.
It is used in:
Interleaving is mainly used in data communication, multimedia file formats, radio transmission (for example in satellites) or by ADSL. Historically, interleaving has also been used in ordering block storage on hard disks. The term multiplexing is sometimes used to refer to the interleaving of digital signal data.
Interleaving is also used for multidimensional data structures, see Z-order (curve).
[edit] Interleaving in data transmission
Today, interleaving is mainly used in digital data transmission technology, to protect the transmission against burst errors. These errors overwrite a lot of bits in a row, but seldom occur. Interleaving is used to solve this problem. All data is transmitted with some control bits (independently from the interleaving), such as error correction bits, that enable the channel decoder to correct a certain number of altered bits. If a burst error occurs, and more than this number of bits is altered, the codeword cannot be correctly decoded. So the bits of a number of codewords are interleaved and then transmitted. That way, a burst error affects only a correctable number of bits in each codeword, so the decoder can decode the codewords correctly.
Let's take a look at an example. We apply an error correcting code so that the channel codeword has four bits and one-bit errors can be corrected. The channel codewords are put into a block like this: aaaabbbbccccddddeeeeffffgggg.
Consider transmission without interleaving:
Error-free transmission: aaaabbbbccccddddeeeeffffgggg transmission with a burst error: aaaabbbbccc____deeeeffffgggg
The codeword cddd is altered in three bits, so it cannot be decoded (decoding failure) or might be decoded into a wrong codeword (false decoding). Which of the two happens depends on the error correcting code applied.
Now, let's do the same with interleaving:
Error-free transmission: abcdefgabcdefgabcdefgabcdefg transmission with a burst error: abcdefgabcd____bcdefgabcdefg
De-interleaved transmission with one burst error: aa_abbbbccccdddde_eef_ffg_gg
In each of the codewords aaaa, eeee, ffff, gggg only one bit is altered, so our one-bit-error-correcting-code can decode everything correctly.
Of course, latency is added by this, because we cannot send the second bit of codeword a before awaiting the first bit of codeword gggg. See also graphical Representation of interleaving.
[edit] Disadvantages of interleaving
- Latency is increased when interleaving is used to improve error performance. This is because the entire interleaved block must be received before the critical data can be returned.
