Interleaving

Entanglement, offset or English interleaving (from English to interleave ',' overlap ') is an optimization technique in data transmission or storage. The data are arranged in a specific order to achieve a higher throughput.

Interleaving is used today mainly used for data communication in the radio communication ( for example, satellite links ) or even when the ADSL technique on the Internet. Formerly interleaving in the arrangement of blocks on disks of importance.

Bit interleaving for multi-dimensional data structures: see Z- curve.

Be interleaved disks and hard drives

The technique of interleaving has been used previously for hard disks because the plates had to spin faster to build up the necessary air cushion between the plate and head when the read data could be processed.

Until a data block transfer is completed the additional blocks were already rushing away under the read-write head. Had the blocks just in ascending order from 1 to n written to disk, so you should now have after the access of a block always to wait almost a complete revolution until the following block will appear again under the SL- head. Since this would slow down the data throughput, it has described the sectors in a different order. This is specified with the interleave factor so-called, how many revolutions of the disk stack needs to run to read a single data track. At 8 blocks and one interleave factor of 3, the blocks would be stored, for example, in the sequence 1 4 7 2 5 8 3 6, there are between two logically consecutive sectors thus always two other blocks. This gives the disk controller enough time to transmit and to get the new data, the data of one block to main memory. It takes three turns of the plate stack until the entire data track is read or written.

Today on hard drives of the interleave factor of 1 is used exclusively, which means that there will be no more interleaving instead. The hard disk controllers have enough buffer memory to read an entire data track at a time or to write. In addition, so-called " double buffering " is used, that is, while the content of a buffer is being transferred to the main memory, the other buffer with data from the hard disk can be filled.

Interleaving in the data transmission

Today, the interleaving is in digital data transmission mainly used to secure the data transmission against so-called burst errors. It makes use of the property this error exploit that, although when they occur, destroying a large number of contiguous bits, but are relatively rare. For all data ( regardless of the interleaving ) also transferred additional error correction information with which you can correct single bit errors. Now occurs on a burst error, but is not just a bit but, for example a group of 10 bits changed. This amount can not be corrected. By interleaving to do now from this burst errors artificially a greater amount of single bit errors by the data to be transferred bit by bit dragged out. But be transmitted in parallel multiple independent data. For example, to transfer a data packet with a length of 512 bits (including parity), so these could be divided for example into 16 32-bit groups. Well not the first group is first completely, and then the second, and so transferred, but it will be out the first bit transmitted from all groups, then all the second bits and so on. Fallen now 10 contiguous bits, so falling in 10 of the 16 data packets from one bit, but they are reconstructed, since all the other 31 bits are unchanged in the groups with errors.

The transmitter must bring only in this nested form the data. Achieving this goal requires all available data to be interleaved. In the example above, you can not send the 16 bit if the data block has arrived complete in the transmit buffer. According to the recipient, the data can bring in the right order again only when the package is delivered complete. Since this total delay only twice as long as the sending and receiving of the data packet takes this disadvantage for most practical situations is irrelevant. Where it gets there on low latency to interleaving can prove to be an enormous disadvantage.

A known example of this type of coding is used in the CD. Scratches on the CD surface cause burst errors that must be corrected by interleaving. For this so-called Cross Interleaved Reed-Solomon Code (CIRC ) see compact disc in the article " error correction ".

It is given a data block with the contents aaaabbbbccccddddeeeeffffgggg. First, the transmission without interleaving:

Error-free transmission: aaaabbbbccccddddeeeeffffgggg Transmission with a burst error: aaaabbbbccc____deeeeffffgggg Now, the same data with interleaving:

Error-free transmission: abcdefgabcdefgabcdefgabcdefg Transmission with a burst error: abcdefgabcd____bcdefgabcdefg De - interleaved transmission with a burst error: aa_abbbbccccdddde_eef_ffg_gg Although now the absence of a, e, f and g are one bit, but this can be corrected because only one bit and not the entire sequences cccc, and dddd is lost.

When encoding the interleavings have to wait for the first g, 7 Series before the first cycle can be completed:

Original: aaaabbbbccccddddeeeeffffgggg                       ^ ^ ^ ^ ^ ^ ^ The marked characters here are the first that need to be sent. But that g can not be sent before it has arrived at the encoder. Similarly, when decoding:

Interleaved: abcdefgabcdefgabcdefgabcdefg                       ^ ^ ^ ^ Until aaaa can be completely decoded, you have to wait until the last mark -price "a" because the information was previously so not completely transferred.

The interleaving process is very related to the multiplexing method. The main difference is that the multiplex method transfers the data usually a plurality of data sources for cost savings over a line, whereas only logical data units of the same data source to be transported in otherwise the same manner as in the multiplexed interleaved over the lead in interleaving.

Benefits by the interleaving

• The communication is secured against rare burst errors. Therefore, the bit error can be reduced to a few bits, because the burst error only slight impact on the user data in an interleaved data stream (see above). In this way, the redundancy is reduced (the more bit errors can correct a code is, the more redundant points have to be inserted, see, Hamming distance ).

Disadvantages by the interleaving

• The latency increases.
• During decoding, a sufficiently large buffer is required.

Latency critical applications

Especially real-time systems may be adversely affected by the interleaving because even prolong reaction times in addition to other factors now by the interleaving. This notice most online players in action-heavy games, since in the ADSL technology for the transmission between the DSLAM and the user's modem usually takes place interleaving. This interleaving can turn off the customer's request for that Internet service provider, this option is called A., FastPath. While this is more frequent packet losses for this purpose are those that get through, the faster to. For file downloads, the advantages and disadvantages cancel each other approximately as arrived by the lower latency data packets of a TCP connection can be confirmed earlier already, but this advantage is more than offset by the slightly higher packet loss rate.

• Transmission technology
• Telecommunications
• Storage medium