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.
Also, the complexity, required cost and effort for error correction mechanism of the communication can be reduced by employing interleaving method since that the data errors can be controlled to reasonable range.
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 message: aaaabbbbccccddddeeeeffffgggg Transmission with a burst error: aaaabbbbccc____deeeeffffgggg
The codeword dddd 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: aaaabbbbccccddddeeeeffffgggg Interleaved: abcdefgabcdefgabcdefgabcdefg Transmission with a burst error: abcdefgabcd____bcdefgabcdefg Deinterleaved with a 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.
For one more example, if we got a meaningful sentence like: ThisIsAExampleForInterleaving. And, if the correction mechanism of the communication can correct maximum 7-bit burst errors. Let us see the sentence without interleaving.
Consider transmission without interleaving:
Error-free transmission: ThisIsAExampleForInterleaving
transmission with a burst error: ThisIsA_______ForInterleaving
We can find that the word "Example" is lost and can not be recovered.
Same as above, we do it again with interleaving.
Consider transmission with interleaving:
Error-free transmission: TIxlreaghsaeIrviAmFnlisEpoten transmission with a burst error: TIxlrea_______viAmFnlisEpoten De-interleaving: T_isI_AEx_mpl_For_nte_leavin_
No single word is completely lost and it is easy to recover them.
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 twofold 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.
