Hybrid ARQ
Encyclopedia
Hybrid automatic repeat request (Hybrid ARQ or HARQ) is a combination of high-rate forward error-correcting coding
, and ARQ error-control for detectable-but-uncorrectable errors. In standard ARQ, redundant bits are added to data to be transmitted using an error-detecting code such as cyclic redundancy check
(CRC). In Hybrid ARQ, a code is used that can perform both forward error correction
(FEC) in addition to error detection (ED) (such as Reed-Solomon code, Convolutional code
or Turbo code
), to correct a subset of all errors while relying on ARQ to correct errors that are uncorrectable using only the redundancy sent in the initial transmission. As a result Hybrid ARQ performs better than ordinary ARQ in poor signal conditions, but in its simplest form this comes at the expense of significantly lower throughput in good signal conditions. There is typically a signal quality cross-over point below which simple Hybrid ARQ is better, and above which basic ARQ is better.
In a more sophisticated form, Type II HARQ, the message originator alternates between message bits along with error detecting parity bits and only FEC parity bits. When the first transmission is received
error free, the FEC parity bits are never sent. Also, two consecutive transmissions can be combined for error correction if neither is error free (Comroe/Costello 1984, pp. 474-5).
To understand the difference between Type I and Type II Hybrid ARQ, consider the size of ED and FEC added information: error detection typically only adds a couple bytes to a message, which is only an incremental increase in length. FEC, on the other hand, can often double or triple the message length with error correction parities. In terms of throughput, standard ARQ typically expends a few percent of channel capacity for reliable protection against error, while FEC ordinarily expends half or more of all channel capacity for channel improvement.
In standard ARQ a transmission must be received error free on any given transmission for the error detection to pass. In Type II Hybrid ARQ, the first transmission contains only data and error detection (no different than standard ARQ). If received error free, it's done. If data is received in error, the second transmission will contain FEC parities and error detection. If received error free, it's done. If received in error, error correction can be attempted by combining the information received from both transmissions.
Only Type I Hybrid ARQ suffers capacity loss in strong signal conditions. Type II Hybrid ARQ does not, because FEC bits are only transmitted on subsequent retransmissions as needed. In strong signal conditions, Type II Hybrid ARQ performs with as good capacity as standard ARQ. In poor signal conditions, Type II Hybrid ARQ performs with as good sensitivity as standard FEC.
Several variants of the two main methods exist. For example, in partial Chase combining only a subset of the bits in the original transmission are retransmitted. In partial incremental redundancy, the systematic
bits are always included so that each retransmission is self-decodable.
An example of incremental redundancy HARQ is HSDPA: the data block is first coded with a punctured 1/3 Turbo code
, then during each (re)transmission the coded block is usually punctured further (i.e. only a fraction of the coded bits are chosen) and sent. The punctuation pattern used during each (re)transmission is different, so different coded bits are sent at each time. Although the HSDPA standard supports both chase combining and incremental redundancy, it has been shown that incremental redundancy almost always performs better than chase combining, at the cost of increased complexity, though.
HARQ can be used in stop-and-wait
mode or in selective repeat
mode. Stop-and-wait is simpler, but waiting for the receiver's acknowledgment reduces efficiency. Thus multiple stop-and-wait HARQ processes are often done in parallel in practice: when one HARQ process is waiting for an acknowledgment, another process can use the channel to send some more data.
There are other forward error correction codes that can be used in an HARQ scheme besides Turbo codes, e.g. extended irregular repeat-accumulate (eIRA) code and Efficiently-Encodable Rate-Compatible (E2RC) code, both of which are Low Density Parity Check Code
.
respectively for mobile phone networks such as UMTS, and in the IEEE 802.16-2005 standard for mobile broadband wireless access, also known as "mobile WiMAX"
.It also has been used in 3GPP Long Term Evolution
.
Type I Hybrid ARQ is also used in ITU-T
G.hn
, a high-speed Local area network
standard that can operate at data rates up to 1 Gbit/s over existing home wiring (power lines
, phone lines and coaxial cables
). G.hn uses CRC-32C
for Error Detection, LDPC
for Forward Error Correction and Selective Repeat
for ARQ.
HARQ is generally implemented in hardware, rather than in software.
Forward 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....
, and ARQ error-control for detectable-but-uncorrectable errors. In standard ARQ, redundant bits are added to data to be transmitted using an error-detecting code such as cyclic redundancy check
Cyclic redundancy check
A cyclic redundancy check is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data...
(CRC). In Hybrid ARQ, a code is used that can perform both forward error correction
Forward 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....
(FEC) in addition to error detection (ED) (such as Reed-Solomon code, Convolutional code
Convolutional code
In telecommunication, a convolutional code is a type of error-correcting code in which* each m-bit information symbol to be encoded is transformed into an n-bit symbol, where m/n is the code rate and...
or 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...
), to correct a subset of all errors while relying on ARQ to correct errors that are uncorrectable using only the redundancy sent in the initial transmission. As a result Hybrid ARQ performs better than ordinary ARQ in poor signal conditions, but in its simplest form this comes at the expense of significantly lower throughput in good signal conditions. There is typically a signal quality cross-over point below which simple Hybrid ARQ is better, and above which basic ARQ is better.
Simple Hybrid ARQ
The simplest version of HARQ, Type I HARQ, adds both ED and FEC information to each message prior to transmission. When the coded data block is received, the receiver first decodes the error-correction code. If the channel quality is good enough, all transmission errors should be correctable, and the receiver can obtain the correct data block. If the channel quality is bad, and not all transmission errors can be corrected, the receiver will detect this situation using the error-detection code, then the received coded data block is rejected and a retransmission is requested by the receiver, similar to ARQ (Comroe/Costello 1984, pp. 474).In a more sophisticated form, Type II HARQ, the message originator alternates between message bits along with error detecting parity bits and only FEC parity bits. When the first transmission is received
error free, the FEC parity bits are never sent. Also, two consecutive transmissions can be combined for error correction if neither is error free (Comroe/Costello 1984, pp. 474-5).
To understand the difference between Type I and Type II Hybrid ARQ, consider the size of ED and FEC added information: error detection typically only adds a couple bytes to a message, which is only an incremental increase in length. FEC, on the other hand, can often double or triple the message length with error correction parities. In terms of throughput, standard ARQ typically expends a few percent of channel capacity for reliable protection against error, while FEC ordinarily expends half or more of all channel capacity for channel improvement.
In standard ARQ a transmission must be received error free on any given transmission for the error detection to pass. In Type II Hybrid ARQ, the first transmission contains only data and error detection (no different than standard ARQ). If received error free, it's done. If data is received in error, the second transmission will contain FEC parities and error detection. If received error free, it's done. If received in error, error correction can be attempted by combining the information received from both transmissions.
Only Type I Hybrid ARQ suffers capacity loss in strong signal conditions. Type II Hybrid ARQ does not, because FEC bits are only transmitted on subsequent retransmissions as needed. In strong signal conditions, Type II Hybrid ARQ performs with as good capacity as standard ARQ. In poor signal conditions, Type II Hybrid ARQ performs with as good sensitivity as standard FEC.
Hybrid ARQ with soft combining
In practice, incorrectly received coded data blocks are often stored at the receiver rather than discarded, and when the retransmitted block is received, the two blocks are combined. This is called Hybrid ARQ with soft combining (Dahlman et al., p. 120). While it is possible that two given transmissions cannot be independently decoded without error, it may happen that the combination of the previously erroneously received transmissions gives us enough information to correctly decode. There are two main soft combining methods in HARQ:- Chase combining: every retransmission contains the same information (data and parity bits). The receiver uses maximum-ratio combiningMaximal-ratio combiningIn telecommunications, maximal-ratio combining is a method of diversity combining in which: the signals from each channel are added together, the gain of each channel is made proportional to the rms signal level and inversely proportional to the mean square noise level in that channel. different...
to combine the received bits with the same bits from previous transmissions. Because all transmissions are identical, Chase combining can be seen as additional repetition codingRepetition codeIn coding theory, the repetition code is one of the most basic error-correcting codes. In order to transmit a message over a noisy channel that may corrupt the transmission in a few places, the idea of the repetition code is to just repeat the message several times. The hope is that the channel...
. One could think of every retransmission as adding extra energy to the received transmission through an increased Eb/N0. - Incremental redundancy: every retransmission contains different information than the previous one. Multiple sets of coded bits are generated, each representing the same set of information bits. The retransmission typically uses a different set of coded bits than the previous transmission, with different redundancy versions generated by puncturingPuncturingIn coding theory, puncturing is the process of removing some of the parity bits after encoding with an error-correction code. This has the same effect as encoding with an error-correction code with a higher rate, or less redundancy...
the decoder output. Thus, at every retransmission the receiver gains extra knowledge.
Several variants of the two main methods exist. For example, in partial Chase combining only a subset of the bits in the original transmission are retransmitted. In partial incremental redundancy, the systematic
Systematic code
In coding theory, a systematic code is any error-correcting code in which the input data is embedded in the encoded output. Conversely, in a non-systematic code the output does not contain the input symbols....
bits are always included so that each retransmission is self-decodable.
An example of incremental redundancy HARQ is HSDPA: the data block is first coded with a punctured 1/3 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...
, then during each (re)transmission the coded block is usually punctured further (i.e. only a fraction of the coded bits are chosen) and sent. The punctuation pattern used during each (re)transmission is different, so different coded bits are sent at each time. Although the HSDPA standard supports both chase combining and incremental redundancy, it has been shown that incremental redundancy almost always performs better than chase combining, at the cost of increased complexity, though.
HARQ can be used in stop-and-wait
Stop-and-wait ARQ
Stop-and-wait ARQ is a method used in telecommunications to send information between two connected devices. It ensures that information is not lost due to dropped packets and that packets are received in the correct order. It is the simplest kind of automatic repeat-request method...
mode or in selective repeat
Selective Repeat ARQ
Selective Repeat ARQ / Selective Reject ARQ is a specific instance of the Automatic Repeat-Request protocol used for communications.-Concept:...
mode. Stop-and-wait is simpler, but waiting for the receiver's acknowledgment reduces efficiency. Thus multiple stop-and-wait HARQ processes are often done in parallel in practice: when one HARQ process is waiting for an acknowledgment, another process can use the channel to send some more data.
There are other forward error correction codes that can be used in an HARQ scheme besides Turbo codes, e.g. extended irregular repeat-accumulate (eIRA) code and Efficiently-Encodable Rate-Compatible (E2RC) code, both of which are Low Density Parity Check Code
Low-density parity-check code
In information theory, a low-density parity-check code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel, and is constructed using a sparse bipartite graph...
.
Applications
HARQ is used in HSDPA and HSUPA which provides high speed data transmission on downlink and uplinkUplink
A telecommunications link is generally one of several types of information transmission paths such as those provided by communication satellites to connect two points on earth.-Uplink:...
respectively for mobile phone networks such as UMTS, and in the IEEE 802.16-2005 standard for mobile broadband wireless access, also known as "mobile WiMAX"
WiMAX
WiMAX is a communication technology for wirelessly delivering high-speed Internet service to large geographical areas. The 2005 WiMAX revision provided bit rates up to 40 Mbit/s with the 2011 update up to 1 Gbit/s for fixed stations...
.It also has been used in 3GPP Long Term Evolution
3GPP Long Term Evolution
3GPP 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...
.
Type I Hybrid ARQ is also used in ITU-T
ITU-T
The ITU Telecommunication Standardization Sector is one of the three sectors of the International Telecommunication Union ; it coordinates standards for telecommunications....
G.hn
G.hn
G.hn is the common name for a home network technology family of standards developed under the International Telecommunication Union's Standardization arm and promoted by the HomeGrid Forum...
, a high-speed Local area network
Local area network
A local area network is a computer network that interconnects computers in a limited area such as a home, school, computer laboratory, or office building...
standard that can operate at data rates up to 1 Gbit/s over existing home wiring (power lines
Power line communication
Power line communication or power line carrier , also known as power line digital subscriber line , mains communication, power line telecom , power line networking , or broadband over power lines are systems for carrying data on a conductor also used for electric power transmission.A wide range...
, phone lines and coaxial cables
Ethernet over coax
Ethernet over Coax is a family of technologies that supports the transmission of Ethernet frames over coaxial cable.- History :The first Ethernet standard, known as 10BASE5 in the family of IEEE 802.3, specified baseband operation over coaxial cable...
). G.hn uses CRC-32C
Cyclic redundancy check
A cyclic redundancy check is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data...
for Error Detection, LDPC
Low-density parity-check code
In information theory, a low-density parity-check code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel, and is constructed using a sparse bipartite graph...
for Forward Error Correction and Selective Repeat
Selective Repeat ARQ
Selective Repeat ARQ / Selective Reject ARQ is a specific instance of the Automatic Repeat-Request protocol used for communications.-Concept:...
for ARQ.
HARQ is generally implemented in hardware, rather than in software.
Further reading
also available as preprint.- Erik Dahlman, Stefan Parkvall, Johan Sköld, Per Beming, "3G Evolution - HSPA and LTE for Mobile Broadband", 2nd edition, Academic Press, 2008, ISBN 978-0-12-374538-5, pp. 119-123