Hybrid automatic repeat request

Last updated April 26, 2024

Hybrid automatic repeat request (hybrid ARQ or HARQ) is a combination of high-rate forward error correction (FEC) and automatic repeat request (ARQ) error-control. In standard ARQ, redundant bits are added to data to be transmitted using an error-detecting (ED) code such as a cyclic redundancy check (CRC). Receivers detecting a corrupted message will request a new message from the sender. In Hybrid ARQ, the original data is encoded with an FEC code, and the parity bits are either immediately sent along with the message or only transmitted upon request when a receiver detects an erroneous message. The ED code may be omitted when a code is used that can perform both forward error correction (FEC) in addition to error detection, such as a Reed–Solomon code. The FEC code is chosen to correct an expected subset of all errors that may occur, while the ARQ method is used as a fall-back 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 re-transmission is requested by the receiver, similar to ARQ.^[1]

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.^[2]

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 of 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 from 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 re-transmissions 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 re-transmitted 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 re-transmission contains the same information (data and parity bits). The receiver uses maximum-ratio combining 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 coding. One could think of every re-transmission as adding extra energy to the received transmission through an increased Eb/N0.
Incremental redundancy: every re-transmission contains different information than the previous one. Multiple sets of coded bits are generated, each representing the same set of information bits. The re-transmission typically uses a different set of coded bits than the previous transmission, with different redundancy versions generated by puncturing the encoder output. Thus, at every re-transmission the receiver gains extra information.

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 re-transmitted. In partial incremental redundancy, the systematic bits are always included so that each re-transmission 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 puncturing 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.^[3]

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 codes.

Applications

HARQ is used in HSDPA and HSUPA which provide high speed data transmission (on downlink and 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". It is also used in Evolution-Data Optimized and LTE wireless networks.

Type I Hybrid ARQ is 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.

Related Research Articles

<span class="mw-page-title-main">Checksum</span> Data used to detect errors in other data

A checksum is a small-sized block of data derived from another block of digital data for the purpose of detecting errors that may have been introduced during its transmission or storage. By themselves, checksums are often used to verify data integrity but are not relied upon to verify data authenticity.

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.

A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption. CRCs can be used for error correction.

Automatic repeat request (ARQ), also known as automatic repeat query, is an error-control method for data transmission that uses acknowledgements and timeouts to achieve reliable data transmission over an unreliable communication channel. ARQ is appropriate if the communication channel has varying or unknown capacity. If the sender does not receive an acknowledgment before the timeout, it re-transmits the message until it receives an acknowledgment or exceeds a predefined number of retransmissions.

In telecommunication, a longitudinal redundancy check (LRC), or horizontal redundancy check, is a form of redundancy check that is applied independently to each of a parallel group of bit streams. The data must be divided into transmission blocks, to which the additional check data is added.

In telecommunications, a transmission system is a system that transmits a signal from one place to another. The signal can be an electrical, optical or radio signal. The goal of a transmission system is to transmit data accurately and efficiently from point A to point B over a distance, using a variety of technologies such as copper cable and fiber-optic cables, satellite links, and wireless communication technologies.

In telecommunications, node-to-node data transfer is the movement of data from one node of a network to the next. In the OSI model it is handled by the lowest two layers, the data link layer and the physical layer.

The data link layer, or layer 2, is the second layer of the seven-layer OSI model of computer networking. This layer is the protocol layer that transfers data between nodes on a network segment across the physical layer. The data link layer provides the functional and procedural means to transfer data between network entities and may also provide the means to detect and possibly correct errors that can occur in the physical layer.

A parity bit, or check bit, is a bit added to a string of binary code. Parity bits are a simple form of error detecting code. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit octets (bytes), although they can also be applied separately to an entire message string of bits.

Radio Data System (RDS) is a communications protocol standard for embedding small amounts of digital information in conventional FM radio broadcasts. RDS standardizes several types of information transmitted, including time, station identification and program information.

<span class="mw-page-title-main">Coding theory</span> Study of the properties of codes and their fitness

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.

In coding theory, an erasure code is a forward error correction (FEC) code under the assumption of bit erasures, which transforms a message of k symbols into a longer message with n symbols such that the original message can be recovered from a subset of the n symbols. The fraction r = k/n is called the code rate. The fraction k’/k, where k’ denotes the number of symbols required for recovery, is called reception efficiency. The recovery algorithm expects that it is known which of the n symbols are lost — unlike forward error correction codes.

Selective Repeat ARQ or Selective Reject ARQ is a specific instance of the automatic repeat request (ARQ) protocol used to manage sequence numbers and retransmissions in reliable communications.

Link adaptation, comprising adaptive coding and modulation (ACM) and others, is a term used in wireless communications to denote the matching of the modulation, coding and other signal and protocol parameters to the conditions on the radio link. For example, WiMAX uses a rate adaptation algorithm that adapts the modulation and coding scheme (MCS) according to the quality of the radio channel, and thus the bit rate and robustness of data transmission. The process of link adaptation is a dynamic one and the signal and protocol parameters change as the radio link conditions change—for example in High-Speed Downlink Packet Access (HSDPA) in Universal Mobile Telecommunications System (UMTS) this can take place every 2 ms.

AMTOR is a type of telecommunications system that consists of two or more electromechanical teleprinters in different locations that send and receive messages to one another. AMTOR is a specialized form of RTTY protocol. The term is an acronym for Amateur Teleprinting Over Radio and is derived from ITU-R recommendation 476-1 and is known commercially as SITOR developed primarily for maritime use in the 1970s. AMTOR was developed in 1978 by Peter Martinez, G3PLX, with the first contact taking place in September 1978 with G3YYD on the 2m Amateur band. It was developed on homemade Motorola 6800-based microcomputers in assembler code. It was used extensively by amateur radio operators in the 1980s and 1990s but has now fallen out of use as improved PC-based data modes are now used and teleprinters became out of fashion.

In coding theory, fountain codes are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. The term fountain or rateless refers to the fact that these codes do not exhibit a fixed code rate.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.

<span class="mw-page-title-main">High Speed Packet Access</span> Communications protocols

High Speed Packet Access (HSPA) is an amalgamation of two mobile protocols—High Speed Downlink Packet Access (HSDPA) and High Speed Uplink Packet Access (HSUPA)—that extends and improves the performance of existing 3G mobile telecommunication networks using the WCDMA protocols. A further-improved 3GPP standard called Evolved High Speed Packet Access was released late in 2008, with subsequent worldwide adoption beginning in 2010. The newer standard allows bit rates to reach as high as 337 Mbit/s in the downlink and 34 Mbit/s in the uplink; however, these speeds are rarely achieved in practice.

NACK-Oriented Reliable Multicast (NORM) is a transport layer Internet protocol designed to provide reliable transport in multicast groups in data networks. It is formally defined by the Internet Engineering Task Force (IETF) in Request for Comments (RFC) 5740, which was published in November 2009.

ARQ-M, short for Automatic Repeat reQuest, Multiplex, is a radio telegraphy protocol used to reliably forward telex messages over partially reliable radio links. It is a low-speed system designed to match the performance of landline telex systems and allow those messages to be forwarded over long distances using shortwave radios. The first ARQ-M link was built in the Netherlands, and began exchanging messages with a counterpart in New York in 1947.

References

↑ Comroe/Costello 1984, p. 474
↑ Comroe/Costello 1984, pp. 474–5
↑ Frenger, P.; S. Parkvall; E. Dahlman (October 2001). "Performance comparison of HARQ with Chase combining and incremental redundancy for HSDPA". Vehicular Technology Conference, 2001. VTC 2001 Fall. IEEE VTS 54th. Vol. 3. Piscataway Township, New Jersey: IEEE Operations Center. pp. 1829–1833. doi:10.1109/VTC.2001.956516. ISBN 0-7803-7005-8.