Interleaving
From Wikipedia, the free encyclopedia
 |
This article or section needs copy editing for grammar, style, cohesion, tone or spelling. You can assist by editing it now. A how-to guide is available. |
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
Interleaving is used in digital data transmission technology to protect the transmission against burst errors. These errors overwrite a lot of bits in a row, so a typical error correction scheme that expects errors to be more uniformly distributed can be overwhelmed. Interleaving is used to help stop this from happening.
Data is often transmitted with error control bits that enable the receiver to correct a certain number of errors that occur during transmission. If a burst error occurs, too many errors can be made in one code word, and that codeword cannot be correctly decoded. To reduce the effect of such burst errors, the bits of a number of codewords are interleaved before being transmitted. This way, a burst error affects only a correctable number of bits in each codeword, and the decoder can decode the codewords correctly.
This method is popular because it is a less complex and cheaper way to handle burst errors than directly increasing the power of the error correction scheme.
Let's 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 either it cannot be decoded at all (decoding failure) or it might be decoded into the 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 code words: aaaabbbbccccddddeeeeffffgggg Interleaved: abcdefgabcdefgabcdefgabcdefg Transmission with a burst error: abcdefgabcd____bcdefgabcdefg Received code words after deinterleaving: 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 will decode everything correctly.
Of course, latency is increased by interleaving because we cannot send the second bit of codeword aaaa before awaiting the first bit of codeword gggg.
For a different example, consider a meaningful sentence like: ThisIsAnExampleOfInterleaving, and suppose we get a burst error corrupting six letters. First, let us see what the sentence looks like without interleaving.
Consider transmission without interleaving:
Original/transmitted sentence: ThisIsAnExampleOfInterleaving
Received sentence with a burst error: ThisIs______pleOfInterleaving
We find that the term "AnExample" is lost or unintelligible.
Now we repeat this example but interleave the sentence prior to transmission. The message is interleaved by transmitting every fourth letter starting at the first letter, then every fourth letter starting at the second, an so on. To make the message a multiple of four letters, three dots have been added to the end. (This is an example of block interleaving.)
Consider transmission with interleaving:
Transmitted sentence: ThisIsAnExampleOfInterleaving... Error-free transmission: TIEpfeaghsxlIrv.iAaenli.snmOten. Received sentence with a burst error: TIEpfe______Irv.iAaenli.snmOten. Received sentence after deinterleaving: T_isI_AnE_amp_eOfInterle_vin_...
No single word is completely lost and it is easy to recover them.
See also graphical Representation of interleaving.
[edit] Disadvantages of interleaving
Use of interleaving techniques increases Latency. This is because the entire interleaved block must be received before the critical data can be returned.
