Interleaving
Entanglement , offset or English interleaving (from English to interleave , 'nest', 'overlap') is an optimization technique for data transmission or storage. The data is arranged in a specific order in order to achieve a higher throughput .
Today, interleaving is mainly used for wireless data communication (for example on satellite links ) or for ADSL technology on the Internet . In the past, interleaving was also important when arranging blocks on hard drives.
Bit interleaving for multi-dimensional data structures: see Z curve .
Interleaving of floppy disks and hard disks
The technique of interleaving was previously used for hard disks , as the disks had to rotate faster than the read data could be processed to build up the necessary air cushion between the disk and the head. Because even before the complete transfer of a data block, other blocks had already swept away under the read / write head. If you had simply written the blocks to the disks in ascending order from 1 to n, you would always have to wait almost a complete revolution after accessing a block until the next block reappears under the SL head. Since this would slow down the data throughput extremely, the sectors were written in a different order. The so-called interleave factor is used to specify how many revolutions the disk stack must perform in order to read in a single data track . With 8 blocks and an interleave factor of 3, for example, the blocks would be stored in the order 1 4 7 2 5 8 3 6, so there are always two other blocks between two logically consecutive sectors. This gives the hard disk controller enough time to transfer the data of a block to the main memory or to fetch the new data. It takes three revolutions of the disk stack until the entire data track is read or written.
Today, only the interleave factor 1 is used for hard disks, which means that there is no longer any interleaving. The hard disk controllers have enough buffer memory to read or write an entire data track at once. In addition, so-called double buffering is used, which means that while the content of one buffer memory is being transferred to the main memory, the other buffer can be filled with data from the hard disk.
Interleaving in data transmission
Today, interleaving is mainly used in digital data transmission to protect data transmission from so-called burst errors . This makes use of the property of these errors that, although they destroy a large number of contiguous bits when they occur, they are relatively rare. Additional error correction information is transmitted with all data (regardless of interleaving), with which individual bit errors can be corrected. If a burst error now occurs, it is not just one bit, but a group of e.g. B. ten bits changed. This amount can no longer be corrected. Interleaving now artificially turns this burst error into a larger amount of single bit errors by lengthening the data to be transmitted bit by bit. For this, several independent data are transmitted in parallel. For example, if a data packet with a length of 512 bits is to be transmitted (including error correction data), it could be divided into 16 32-bit groups, for example. Now the first group is not completely transmitted first, and then the second, etc., but rather the first bits from all groups are transmitted first, then all second bits and so on. If ten contiguous bits fail, then 10 of the 16 data packets each lose one bit, which can, however, be reconstructed because all the other 31 bits in the groups with errors have remained unchanged.
The sender must first convert the data into this nested form. To do this, however, all data that are to be nested must be available. In the example above, the 16th bit can only be sent when the data block has completely arrived in the send buffer. Accordingly, the recipient can only put the data back in the correct order when the package has arrived in full. Since this only delays twice as long as it takes to send or receive the data packet, this disadvantage is irrelevant for most practical situations. When it comes to low latencies, however, interleaving can turn out to be a huge disadvantage.
A well-known example of this type of coding is used on the CD . Scratches on the CD surface cause burst errors which have to be corrected by interleaving. For this so-called Cross Interleaved Reed Solomon Code (CIRC) see Compact Disc in the article "Error correction" .
Let there be a data block with the content aaaabbbbccccddddeeeeffffgggg. First the transmission without interleaving:
Fehlerfreie Übertragung: aaaabbbbccccddddeeeeffffgggg Übertragung mit einem Burstfehler: aaaabbbbccc____deeeeffffgggg
Now the same data with interleaving:
Fehlerfreie Übertragung: abcdefgabcdefgabcdefgabcdefg Übertragung mit einem Burstfehler: abcdefgabcd____bcdefgabcdefg
De-Interleavte Übertragung mit einem Burstfehler: aa_abbbbccccdddde_eef_ffg_gg
Now one bit each of a, e, f and g is missing, but this can be corrected because only one bit and not the entire sequences cccc and dddd are lost.
When coding the interleaving, you have to wait for the first g before the first 7 cycle can be completed:
Original: aaaabbbbccccddddeeeeffffgggg
^ ^ ^ ^ ^ ^ ^
The characters marked here are the first to be sent. However, the g cannot be sent before it has reached the encoder. Analogous to decoding:
Interleaved : abcdefgabcdefgabcdefgabcdefg
^ ^ ^ ^
Until aaaa can be completely decoded, you have to wait until the last marked "a", because the information was not completely transmitted beforehand.
The interleaving process is very much related to the multiplex process . The main difference is that the multiplex method usually transmits data from several data sources over one line to save costs, while with interleaving only logical data units of the same data source are otherwise interleaved over the line in the same way as with multiplexing.
Advantages through interleaving
- Communication is secured against rare burst errors.
- Bit error protection can therefore be reduced to a few bits, since burst errors have only a small effect on the user data in the case of an interleaved data stream (see above). In this way, the redundancy is reduced (the more bit errors a code should be able to correct, the more redundant places have to be inserted, see Hamming distance ).
- No additional data has to be transferred for this backup, so the data rate is retained.
Disadvantages of interleaving
- The latency increases.
- A sufficiently large buffer is required for decoding.
Latency critical applications
Real-time systems in particular are negatively affected by interleaving, as it increases reaction times. This has an effect, for example, in ADSL technology with action-heavy online games , since interleaving is normally used for the transmission between the DSLAM and the user's modem . At the request of a customer, the Internet provider can switch off interleaving for this customer , this option is called i. A. FastPath . This means that packet losses occur more frequently , but those that get through arrive all the faster. In the case of file downloads, the advantages and disadvantages can roughly cancel each other out, since the lower latency means that data packets arriving on a TCP connection can be confirmed earlier, but this advantage is offset by the slightly higher packet loss rate.