Interleaving
Encyclopedia
In computer science
and telecommunication
, interleaving is a way to arrange data
in a non-contiguous way to increase performance.
It is typically used:
Interleaving is also used for multidimensional data structures, see Z-order (curve)
.
Historically, interleaving was used in ordering block storage on disk-based storage devices such as the floppy disk
and the hard disk
. The primary purpose of interleaving was to adjust the timing differences between when the computer was ready to transfer data, and when that data was actually arriving at the drive head to be read. Interleaving was very common prior to the 1990s, but faded from use as processing speeds increased. Modern disk storage is not interleaved.
Interleaving was used to arrange the sectors in the most efficient manner possible, so that after reading a sector, time would be permitted for processing, and then the next sector in sequence is ready to be read just as the computer is ready to do so. Matching the sector interleave to the processing speed therefore accelerates the data transfer, but an incorrect interleave can make the system perform markedly slower.
Data to be written or read is put into a special region of reusable memory referred to as a buffer. When data needed to be written, it was moved into the buffer, and then written from the buffer to the disk. When data was read, the reverse took place, transferring first into the buffer and then moved to where it was needed. Most early computers were not fast enough to read a sector, move the data from the buffer to somewhere else, and be ready to read the next sector by the time that next sector was appearing under the read head.
When sectors were arranged in direct serial order, after the first sector was read the computer may spend the time it takes for three sectors to pass by before it is ready to receive data again. However with the sectors in direct order, sector two, three, and four have already passed by. The computer doesn't need sectors 4, 5, 6, 7, 8, 9, or 1, and must wait for these to pass by, before reading sector two. This waiting for the disk to spin around to the right spot slows the data transfer rate.
To correct for the processing delays, the ideal interleave for this system would be 1:4, ordering the sectors like this: 1 8 6 4 2 9 7 5 3. It reads sector 1, processes for three sectors whereby 8 6 and 4 pass by, and just as the computer becomes ready again, sector two is arriving just as it is needed.
Sometimes the interleave is expressed as a "skip factor",
the number of physical sectors between consecutive logical sectors.
A skip factor of 0 places the sectors sequentially—1 2 3 4 5 6 ... .
Modern disk storage does not need interleaving since the buffer space is now so much larger. Data is now more commonly stored as clusters which are groups of sectors, and the data buffer is sufficiently large to allow all sectors in a block to be read at once without any delay between sectors.
. Many communication channels are not memoryless: errors typically occur in bursts rather than independently. If the number of errors within a code word
exceeds the error-correcting code's capability, it fails to recover the original code word. Interleaving ameliorates this problem by shuffling source symbols across several code words, thereby creating a more uniform distribution
of errors.
The analysis of modern iterated codes, like turbo code
s and LDPC codes, typically assumes an independent distribution of errors. Systems using LDPC codes therefore typically employ additional interleaving across the symbols within a code word.
For turbo codes, an interleaver is an integral component and its proper design is crucial for good performance. The iterative decoding algorithm works best when there are not short cycles in the factor graph
that represents the decoder; the interleaver is chosen to avoid short cycles.
Interleaver designs include:
In multi-carrier
communication systems, additional interleaving across carriers may be employed to mitigate the effects of prohibitive noise on a single or few specific carriers (e.g., frequency-selective fading in OFDM transmission).
Error-free message: aaaabbbbccccddddeeeeffffgggg
Transmission with a burst error: aaaabbbbccc____deeeeffffgggg
The codeword cddd is altered in four bits, so either it cannot be decoded at all or it might be decoded incorrectly
.
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 one-bit error-correcting-code will decode everything correctly.
Transmission without interleaving:
Original transmitted sentence: ThisIsAnExampleOfInterleaving
Received sentence with a burst error: ThisIs______pleOfInterleaving
The term "AnExample" ends up mostly unintelligible and difficult to correct.
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 word is completely lost and the missing letters can be recovered with minimal guesswork.
. This is because the entire interleaved block must be received before the packets can be decoded. Also interleavers hide the structure of errors; without an interleaver, more advanced decoding algorithms can take advantage of the error structure and achieve more reliable communication than a simpler decoder combined with an interleaver.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and telecommunication
Telecommunication
Telecommunication is the transmission of information over significant distances to communicate. In earlier times, telecommunications involved the use of visual signals, such as beacons, smoke signals, semaphore telegraphs, signal flags, and optical heliographs, or audio messages via coded...
, interleaving is a way to arrange data
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
in a non-contiguous way to increase performance.
It is typically used:
- In error-correction coding, particularly within data transmissionData transmissionData transmission, digital transmission, or digital communications is the physical transfer of data over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical fibres, wireless communication channels, and storage media...
, disk storageDisk storageDisk storage or disc storage is a general category of storage mechanisms, in which data are digitally recorded by various electronic, magnetic, optical, or mechanical methods on a surface layer deposited of one or more planar, round and rotating disks...
, and computer memoryComputer storageComputer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
. - For multiplexingMultiplexingThe multiplexed signal is transmitted over a communication channel, which may be a physical transmission medium. The multiplexing divides the capacity of the low-level communication channel into several higher-level logical channels, one for each message signal or data stream to be transferred...
of several input data over shared media. In telecommunicationTelecommunicationTelecommunication is the transmission of information over significant distances to communicate. In earlier times, telecommunications involved the use of visual signals, such as beacons, smoke signals, semaphore telegraphs, signal flags, and optical heliographs, or audio messages via coded...
, it is implemented through dynamic bandwidth allocationDynamic bandwidth allocationDynamic bandwidth allocation is a technique by which traffic bandwidth in a shared telecommunications medium can be allocated on demand and fairly between different users of that bandwidth. This is a form of bandwidth management, and is essentially the same thing as statistical multiplexing...
mechanisms, where it may particularly be used to resolve quality of serviceQuality of serviceThe quality of service refers to several related aspects of telephony and computer networks that allow the transport of traffic with special requirements...
and latencyLatency (engineering)Latency is a measure of time delay experienced in a system, the precise definition of which depends on the system and the time being measured. Latencies may have different meaning in different contexts.-Packet-switched networks:...
issues. In streaming mediaStreaming mediaStreaming media is multimedia that is constantly received by and presented to an end-user while being delivered by a streaming provider.The term "presented" is used in this article in a general sense that includes audio or video playback. The name refers to the delivery method of the medium rather...
applications, it enables quasi-simultaneous reception of input streams, such as videoVideoVideo is the technology of electronically capturing, recording, processing, storing, transmitting, and reconstructing a sequence of still images representing scenes in motion.- History :...
and audioSoundSound is a mechanical wave that is an oscillation of pressure transmitted through a solid, liquid, or gas, composed of frequencies within the range of hearing and of a level sufficiently strong to be heard, or the sensation stimulated in organs of hearing by such vibrations.-Propagation of...
. - For improved access performance in computer memoryComputer memoryIn computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...
and computer data storage. Examples include non-contiguous storage patterns in disk storageDisk storageDisk storage or disc storage is a general category of storage mechanisms, in which data are digitally recorded by various electronic, magnetic, optical, or mechanical methods on a surface layer deposited of one or more planar, round and rotating disks...
, interleaved memoryInterleaved memoryInterleaved memory is a technique for compensating the relatively slow speed of DRAM. The CPU can access alternative sections immediately without waiting for memory to be cached. Multiple memory banks take turns supplying data....
, and page coloring memory allocation strategies.
Interleaving is also used for multidimensional data structures, see Z-order (curve)
Z-order (curve)
In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a space-filling curve which maps multidimensional data to one dimension while preserving locality of the data points. It was introduced in 1966 by G. M. Morton...
.
Interleaving in disk storage
Floppy disk
A floppy disk is a disk storage medium composed of a disk of thin and flexible magnetic storage medium, sealed in a rectangular plastic carrier lined with fabric that removes dust particles...
and the hard disk
Hard disk
A hard disk drive is a non-volatile, random access digital magnetic data storage device. It features rotating rigid platters on a motor-driven spindle within a protective enclosure. Data is magnetically read from and written to the platter by read/write heads that float on a film of air above the...
. The primary purpose of interleaving was to adjust the timing differences between when the computer was ready to transfer data, and when that data was actually arriving at the drive head to be read. Interleaving was very common prior to the 1990s, but faded from use as processing speeds increased. Modern disk storage is not interleaved.
Interleaving was used to arrange the sectors in the most efficient manner possible, so that after reading a sector, time would be permitted for processing, and then the next sector in sequence is ready to be read just as the computer is ready to do so. Matching the sector interleave to the processing speed therefore accelerates the data transfer, but an incorrect interleave can make the system perform markedly slower.
Example
Information is commonly stored on disk storage in very small pieces referred to as sectors or blocks. These are arranged in concentric rings referred to as tracks across the surface of each disk. While it may seem easiest to order these blocks in direct serial order in each track, such as 1 2 3 4 5 6 7 8 9, for early computing devices this ordering was not practical.Data to be written or read is put into a special region of reusable memory referred to as a buffer. When data needed to be written, it was moved into the buffer, and then written from the buffer to the disk. When data was read, the reverse took place, transferring first into the buffer and then moved to where it was needed. Most early computers were not fast enough to read a sector, move the data from the buffer to somewhere else, and be ready to read the next sector by the time that next sector was appearing under the read head.
When sectors were arranged in direct serial order, after the first sector was read the computer may spend the time it takes for three sectors to pass by before it is ready to receive data again. However with the sectors in direct order, sector two, three, and four have already passed by. The computer doesn't need sectors 4, 5, 6, 7, 8, 9, or 1, and must wait for these to pass by, before reading sector two. This waiting for the disk to spin around to the right spot slows the data transfer rate.
To correct for the processing delays, the ideal interleave for this system would be 1:4, ordering the sectors like this: 1 8 6 4 2 9 7 5 3. It reads sector 1, processes for three sectors whereby 8 6 and 4 pass by, and just as the computer becomes ready again, sector two is arriving just as it is needed.
Sometimes the interleave is expressed as a "skip factor",
the number of physical sectors between consecutive logical sectors.
A skip factor of 0 places the sectors sequentially—1 2 3 4 5 6 ... .
Modern disk storage does not need interleaving since the buffer space is now so much larger. Data is now more commonly stored as clusters which are groups of sectors, and the data buffer is sufficiently large to allow all sectors in a block to be read at once without any delay between sectors.
Interleaving in error-correction coding
Interleaving is frequently used in digital communication and storage systems to improve the performance of forward error correcting codesForward error correction
In telecommunication, information theory, and coding theory, forward error correction or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels....
. Many communication channels are not memoryless: errors typically occur in bursts rather than independently. If the number of errors within a code word
Code word
In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning...
exceeds the error-correcting code's capability, it fails to recover the original code word. Interleaving ameliorates this problem by shuffling source symbols across several code words, thereby creating a more uniform distribution
Uniform distribution (continuous)
In probability theory and statistics, the continuous uniform distribution or rectangular distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by...
of errors.
The analysis of modern iterated codes, like turbo code
Turbo code
In information theory, turbo codes are a class of high-performance forward error correction codes developed in 1993, which were the first practical codes to closely approach the channel capacity, a theoretical maximum for the code rate at which reliable communication is still possible given a...
s and LDPC codes, typically assumes an independent distribution of errors. Systems using LDPC codes therefore typically employ additional interleaving across the symbols within a code word.
For turbo codes, an interleaver is an integral component and its proper design is crucial for good performance. The iterative decoding algorithm works best when there are not short cycles in the factor graph
Factor graph
In probability theory and its applications, a factor graph is a particular type of graphical model, with applications in Bayesian inference, that enables efficient computation of marginal distributions through the sum-product algorithm...
that represents the decoder; the interleaver is chosen to avoid short cycles.
Interleaver designs include:
- rectangular (or uniform) interleavers (similar to the method using skip factors described above)
- convolutional interleavers
- random interleavers (where the interleaver is a known random permutation)
- S-random interleaver (where the interleaver is a known random permutation with the constraint that no input symbols within distance S appear within a distance of S in the output).
- Another possible construction is a contention-free quadratic permutation polynomialPermutation polynomialIn mathematics, a permutation polynomial is a polynomial that acts as a permutation of the elements of the ring, i.e. the map x \mapsto g is one-to-one...
(QPP). It is used for example in the 3GPP Long Term Evolution3GPP Long Term Evolution3GPP Long Term Evolution, usually referred to as LTE, is a standard for wireless communication of high-speed data for mobile phones and data terminals. It is based on the GSM/EDGE and UMTS/HSPA network technologies, increasing the capacity and speed using new modulation techniques...
mobile telecommunication standard.
In multi-carrier
Carrier wave
In telecommunications, a carrier wave or carrier is a waveform that is modulated with an input signal for the purpose of conveying information. This carrier wave is usually a much higher frequency than the input signal...
communication systems, additional interleaving across carriers may be employed to mitigate the effects of prohibitive noise on a single or few specific carriers (e.g., frequency-selective fading in OFDM transmission).
Example
Transmission without interleaving:Error-free message: aaaabbbbccccddddeeeeffffgggg
Transmission with a burst error: aaaabbbbccc____deeeeffffgggg
The codeword cddd is altered in four bits, so either it cannot be decoded at all or it might be decoded incorrectly
Falsing
In telecommunications, falsing describes a decoder assuming that it is detecting a valid input when one is not present. This is also known as a false decode...
.
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 one-bit error-correcting-code will decode everything correctly.
Transmission without interleaving:
Original transmitted sentence: ThisIsAnExampleOfInterleaving
Received sentence with a burst error: ThisIs______pleOfInterleaving
The term "AnExample" ends up mostly unintelligible and difficult to correct.
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 word is completely lost and the missing letters can be recovered with minimal guesswork.
Disadvantages of interleaving
Use of interleaving techniques increases latencyLatency (engineering)
Latency is a measure of time delay experienced in a system, the precise definition of which depends on the system and the time being measured. Latencies may have different meaning in different contexts.-Packet-switched networks:...
. This is because the entire interleaved block must be received before the packets can be decoded. Also interleavers hide the structure of errors; without an interleaver, more advanced decoding algorithms can take advantage of the error structure and achieve more reliable communication than a simpler decoder combined with an interleaver.