Hybrid ARQ

Introduction to HARQ. Source: Devopedia 2021.
Introduction to HARQ. Source: Devopedia 2021.

A typical communication channel has imperfections. Packets get lost or corrupted. When the receiver detects errors, it discards the erroneous packet and requests the sender to retransmit it. This is called Automatic Repeat Request (ARQ). Error detection is usually done using Cyclic Redundancy Check (CRC) bits.

However, if errors are within certain limits, the receiver can not only detect but also correct errors. This is possible if the sender employs Error-Correcting Codes (ECCs). These include parity bits that help in correcting errors in information bits. The technique is called Forward Error Correction (FEC). FEC avoids ARQ retransmissions but parity bits are an overhead.

Hybrid ARQ is a technique the combines both ARQ and FEC. Packet errors are corrected where possible. Where not possible, retransmission is requested. First and subsequent packet transmissions are combined to increase the chance of correct decoding.

Discussion

  • What's the typical HARQ processing pipeline?
    Overview of HARQ processing pipeline. Source: Ahmed et al. 2021, fig. 1.
    Overview of HARQ processing pipeline. Source: Ahmed et al. 2021, fig. 1.

    The pipeline starts with a packet of information bits coming into the sender's HARQ entity. CRC bits are added to the information bits. Then an FEC encoder uses an ECC and maps its input to a codeword. Multiple such codewords are buffered and interleaved to protect against channel burst errors. Interleaving distributes such errors across codewords so that there's greater chance of recovering all packets. Interleaved bits are finally modulated for transmission on the channel. Modulation type and order are selected according to recent channel conditions.

    At the receiver, the demodulation and deinterleaving are followed by HARQ operation. FEC decoder uses either soft or hard decision decoding. It maps its input to closest valid codewords. A CRC check determines if the FEC decoder has got it right. If CRC check fails, a retransmission is requested.

    Combiner at the receiver combines all transmissions of the packet so that FEC has a better chance of decoding the packet correctly. Sender and receiver buffers are for retransmission and combining respectively.

  • How is Chase Combining different from Incremental Redundancy?
    Illustrating Chase Combining and Incremental Redundancy. Source: Ahmadi 2019, fig. 4.54.
    Illustrating Chase Combining and Incremental Redundancy. Source: Ahmadi 2019, fig. 4.54.

    There are two basic ways in which multiple transmissions of a packet can be combined at the receiver. The simpler method is Chase Combining (CC) in which all transmissions contain the same information and parity bits. Each transmission therefore adds to the overall packet energy.

    Incremental Redundancy (IR) is a method in which each retransmission pertains to the same information bits but contains a different subset of information and parity bits. Parity bits are also called redundancy bits. IR is therefore about progressively sending more of these bits to help the FEC decoder. Like CC, IR retransmissions add to the overall packet energy. More importantly, IR retransmissions decreases the code rate since each retransmission increases the redundancy. Implementing IR is more complex than implementing CC.

    In poor channel conditions (low SNR), CC does well but when the channel is good, parity bits take up bandwidth unnecessarily. IR is a better method since more parity bits are sent only when needed. IR's first transmission can even include only information bits.

  • What are the different types of HARQ?

    Researchers refer to three types of HARQ:

    • Type-I: In the simplest case, errors are corrected if possible. Otherwise, erroneous packets are discarded and retransmission is requested. In an alternative case, all packet transmissions are buffered and combined using Maximal Ratio Combining (MRC). The latter case is basically CC.
    • Type-II: This is basically IR in which different redundancy bits are sent with each retransmission. This can be realized via bit puncturing that effectively changes the code rate over all transmissions.
    • Type-III: In Type-II, apart from first transmission, more than one buffered version of the packet is required for decoding. In Type-III, each transmission is self-decodable. Bits common to transmissions can be chase combined. This is also called partial IR since each retransmission includes more redundancy bits.

    Some use the term Repetition Redundancy (RR) instead of Chase Combining. Chase Combining has also been called Packet Combining while Incremental Redundancy has been called Code Combining in literature.

    ARQ protocols called Stop-and-Wait, Go-Back-N and Selective Repeat are applicable to HARQ.

  • What's the difference between truncated and persistent HARQ?

    In really bad channel conditions, many HARQ retransmissions may be needed. If there's no limit on the number of retransmissions, we call it persistent HARQ. Otherwise we call is truncated HARQ. Truncated HARQ is preferred for real-time applications. The maximum can be selected based on throughput efficiency, packet delay, packet drop rate and buffer space requirements.

    Some systems may specify a deadline or maximum time limit for the retransmissions. Past this deadline, the packet is dropped and retransmissions are stopped. This is called time-truncated HARQ.

    5G New Radio doesn't specify a limit on the number of retransmissions. However, such a limit may be provided by the network equipment vendor and operator configurable. Kawser et al. have proposed truncated HARQ for 4G/LTE for UEs with poor downlink reception.

  • What's the difference between synchronous and asynchronous HARQ?
    Illustrating synchronous versus asynchronous HARQ. Source: Khan 2006, slide 39.
    Illustrating synchronous versus asynchronous HARQ. Source: Khan 2006, slide 39.

    With synchronous HARQ, the timing is regular and known in advance. For example, the time between a packet transmission and its ACK/NACK could be fixed. The time between a NACK and the next retransmission could be fixed.

    With asynchronous HARQ, timing is configurable and highly dynamic. Scheduling can be based on current channel conditions and resource requirements. Asynchronous HARQ requires additional signalling compared to synchronous HARQ.

    5G NR uses asynchronous HARQ since 5G already has a highly dynamic TDD frame structure. Moreover, 5G can operate in unlicensed spectra where resources can't be assigned in advance to support synchronous HARQ.

  • What's the difference between non-adaptive and adaptive HARQ?
    Illustrating non-adaptive versus adaptive HARQ. Source: Khan 2006, slide 41.
    Illustrating non-adaptive versus adaptive HARQ. Source: Khan 2006, slide 41.

    With non-adaptive HARQ, the modulation and coding remains the same across all transmissions of a packet. With adaptive HARQ, these can change. For example, the first transmission might have used 16-QAM but if channel quality is seen to have worsened, subsequent retransmissions could you QPSK with more radio resources allocated to accommodate the packet in the lower modulation.

    Adaptive HARQ is more common in wireless systems due to the time-varying nature of wireless channels. Adaptation depends on channel feedback from the receiver. Transmission power, modulation, code rate, bandwidth, packet length, maximum number of retransmissions, and allocated resources are some aspects that can be adapted. There are many techniques in adaptive HARQ but their objectives may differ: throughput, delay, spectral efficiency, power or reliability.

    It's been shown that adaptive truncated HARQ is a robust approach for real-time applications.

  • What codes are suitable for detecting or correcting errors in HARQ?

    Error detection is commonly done using using Cyclic Redundancy Check (CRC) bits. These are computed based on and appended to the information bits. CRC is often implemented in hardware using Linear Feedback Shift Registers (LFSRs). CRC field is typically 8-64 bits long. Since this overhead reduces overall system capacity, CRC-free alternatives to error detection have been researched. However, 4G, 5G and Wi-Fi standards have adopted CRC.

    Error-Correcting Codes (ECCs) for HARQ are typically Turbo Codes, Turbo Product Codes (TPCs), Low Density Parity Check (LDPC) Codes, and Polar Codes. At least for HARQ, these have replaced an older generation of ECCs such as convolutional, Bose–Chaudhuri–Hocquenghem (BCH) and Reed-Solomon (RS) codes.

  • How have different wireless communication protocol standards adopted HARQ?

    HARQ is widely adopted in major wireless systems:

    • 3G/UMTS: Asynchronous downlink HARQ. Synchronous uplink HARQ. Stop-and-Wait HARQ with up to 8 parallel processes. Supports both CC and IR.
    • CDMA2000: Similar to 3G/UMTS but up to 4 processes and maximum of 3 retransmissions.
    • 4G/LTE: Similar to 3G/UMTS with 8 processes in FDD and 1-15 processed in TDD. Maximum number of retransmissions can be configured. Uplink HARQ is typically non-adaptive but can be made adaptive. TTI bundling of up to 4 TTIs allows UEs to transmit all redundancy versions without waiting for feedback. HARQ operates at MAC and PHY layers.
    • 5G: Asynchronous and adaptive in both downlink and uplink. Up to 16 parallel processes, each using Stop-and-Wait.
    • WiMAX: Supports both CC and IR. Up to 16 parallel processes each in uplink and downlink, each using Stop-and-Wait. Maximum of 4 retransmissions. Asynchronous adaptive downlink HARQ. Synchronous adaptive downlink HARQ but default operation is non-adaptive HARQ.
    • IEEE 802.15.4: HARQ Type-I. Maximum of 0-7 retransmissions with 3 as default. Retransmissions also have a timing constraint.
    • Bluetooth: Synchronous HARQ Type-I.
  • What are some research initiatives on HARQ?

    Adaptive Cross-Packet HARQ (XP-HARQ) is a technique that varies the number of bits with each retransmission. A retransmission can contain bits from two packets and joint decoding happens at the receiver. Sender selects codebooks based on current channel conditions.

    Cooperative HARQ is where retransmissions can happen from a neighbouring node that managed to receive the first transmission correctly. This gives spatial diversity gain at the intended receiving node. A similar but more sophisticated idea encodes packets meant for different receiving nodes into each retransmission. This is called Network Coded HARQ (NC-HARQ).

    Designing HARQ for IoT presents new challenges. IoT devices send short packets and are often battery powered. Some IoT applications require high reliability and low delay. Type-II HARQ outperforms Type-I HARQ though the latter is simpler to implement.

    Wi-Fi uses only ARQ though there have been proposals to introduce HARQ. HARQ is being researched in many other areas as well: 5G's URLLC and mMTC use cases, Cloud RAN, NOMA and Cognitive Radio.

Milestones

1940

Van Dureen introduces the first electronic retransmission scheme to telegraphy. His method incorporates error detection via even parity. The term "automatic repeat request" itself appears in 1957. In 1961, Van Dureen publishes one of the earliest performance analysis of ARQ. By early 1960s, the term ARQ is widely accepted.

1960

At the Fourth London Symposium on Information Theory, Wozencraft and Horstein propose HARQ, although they don't use the term "HARQ". In a subsequent MIT Technical Report, they state, "The system is somewhat similar to human communication, in that typical errors are corrected, while grievous ones initiate a request for retransmission."

1974

Mandelbaum proposes Incremental Redundancy in which the first transmission contains a punctured codeword. If in error, each subsequent retransmission brings another increment of redundant bits until the receiver can successfully decode the packet.

1977
ARQ-with-Memory (MRQ) system. Source: Sindhu 1977, fig. 1.
ARQ-with-Memory (MRQ) system. Source: Sindhu 1977, fig. 1.

Sindhu proposes a a modification of ARQ in which erroneous packets are buffered at the receiver and later combined with retransmissions to improve the decoding. He calls this ARQ-with-Memory (MRQ) and the decoding procedure as Redundancy Repetition Error Correction (RRC). Essentially, this is packet combining or Type-I HARQ with hard-decision decoding.

1981

Lin and Yu propose the use of two block codes, \(C_0\) for only error detection and \(C_1\) for both error correction and detection. In their method, transmissions alternate between message bits and \(C_0\) parity bits, and \(C_1\) and \(C_0\) parity bits. Wang and Lin improve this in 1983.

1984

In a survey paper on ARQ, Lin et al. name the main types of HARQ: Type-I and Type-II. This example shows that this sort of naming was current by the mid-1980s if not earlier.

1985
Code combining as proposed by David Chase. Source: Chase 1985, fig. 1.
Code combining as proposed by David Chase. Source: Chase 1985, fig. 1.

Chase proposes code combining in which multiple receptions are weighted and combined to offer better error correcting capability. The method does maximum-likelihood decoding and soft-decision packet decoding. The original packet uses a half-rate convolutional code but with every retransmission, the effective code rate drops.

2003

Cheng et al. propose adaptive incremental redundancy in which channel state information can be used to adapt the modulation and coding for each retransmission. They analyze this for a Release 5 3G/UMTS system and find that up to 25% improvement in system throughput can be obtained under certain conditions.

Sep
2005

3GPP publishes Release 6 of 3G/UMTS specification. In poor channels where ACK/NACK feedbacks are not coming through (such as for UEs at the cell edge), a variation called autonomous or blind HARQ is employed. The sender transmits multiple versions of the packet without waiting for ACK/NACK.

2015

Kuhn et al. consider many variants of TCP over 4G satellite links in their simulations. They find that in poor channel conditions, HARQ provides up to 22% higher throughput compared to other reliability schemes regardless of the TCP variant used.

2016
ARQ at LLC and HARQ+AMC at PHY. Source: Sassioui et al. 2016, fig. 1.
ARQ at LLC and HARQ+AMC at PHY. Source: Sassioui et al. 2016, fig. 1.

Sassioui et al. analyze the interplay between AMC and HARQ. They note that in fast-fading channels HARQ is beneficial only at low SNR and counterproductive at high SNR. In such cases, ARQ at a higher layer is sufficient. In slow-fading channels, throughput gains due to HARQ are moderate particularly when AMC ignores the presence of HARQ.

2021

Nadeem et al. study the effectiveness of HARQ for 5G's URLLC use case. Whereas we have large packets in eMBB use case, HARQ for URLLC has to be analyzed in the Finite Blocklength (FBL) regime. They present results for AWGN and Rayleigh fading channels.

References

  1. 3GPP Portal. 2021. "Releases." 3GPP, October 6. Accessed 2021-12-16.
  2. Ahmadi, Sassan. 2019. "Chapter 4: New Radio Access Physical Layer Aspects (Part 2)". In: 5G NR, Academic Press. Accessed 2021-07-02.
  3. Ahmed, A., A. Al-Dweik, Y. Iraqi, H. Mukhtar, M. Naeem and E. Hossain. 2021. "Hybrid Automatic Repeat Request (HARQ) in Wireless Communications Systems and Standards: A Contemporary Survey." IEEE Communications Surveys & Tutorials, vol. 23, no. 4, pp. 2711-2752. doi: 10.1109/COMST.2021.3094401. Accessed 2021-12-17.
  4. Chase, D. 1985. "Code combining—A Maximum-Likelihood Decoding Approach for Combining an Arbitrary Number of Noisy Packets." IEEE Trans. Communications, vol. 33, no. 5, pp. 385-393, May. doi: 10.1109/TCOM.1985.1096314. Accessed 2021-12-17.
  5. Cheng, J.F., Y.P.E. Wang, and S. Parkvall. 2003. "Adaptive incremental redundancy." IEEE 58th Vehicular Technology Conference (VTC 2003-Fall), vol. 2, pp. 737-741. doi: 10.1109/VETECF.2003.1285118. Accessed 2021-12-18.
  6. Dahlman, Erik, Stefan Parkvall, and Johan Skold. 2018. "5G NR: The Next Generation Wireless Access Technology." Academic Press. Accessed 2021-02-23.
  7. ETSI. 2021a. "TS 138 321: 5G; NR; Medium Access Control (MAC) protocol specification." V16.4.0, April. Accessed 2021-07-02.
  8. ETSI. 2021b. "TS 138 331: 5G; NR; Radio Resource Control (RRC); Protocol specification." V16.4.1, April. Accessed 2021-07-02.
  9. El Bahri, M. W., Hatem Boujemaa, and Mohamed Siala. 2005. "Throughput evaluation of HARQ Schemes with Packet and Code Combining over multipath fading channels for DS-SSS." 20° Colloque sur le traitement du signal et des images, pp. 1208-1211. Accessed 2021-12-17.
  10. Jabi, Mohammed, Abdellatif Benyouss, Mael Le Treust, Etienne Pierre-Doray, and Leszek Szczecinski. 2017. "Adaptive Cross-Packet HARQ." IEEE Transactions on Communications, Institute of Electrical and Electronics Engineers, hal-01633786. Accessed 2021-12-17.
  11. Kawser, Mohammad T., Nafiz Imtiaz Bin Hamid, Md. Nayeemul Hasan, M. Shah Alam, and M. Musfiqur Rahman. 2012. "Limiting HARQ Retransmissions in Downlink for Poor Radio Link in LTE." International Journal of Information and Electronics Engineering, vol. 2, no. 5, September. Accessed 2021-12-17.
  12. Khan, Farooq. 2006. "3G Long-Term Evolution (LTE)." Slides, Samsung Telecom R&D Center, September 25. Accessed 2021-07-02.
  13. Kuhn, Nicolas, Emmanuel Lochin, J. Lacan, R. Boreli, and L. Clarac. 2015. "On the impact of link layer retransmission schemes on TCP over 4G satellite links." International Journal of Satellite Communications and Networking, hal-02543531, vol. 33, no. 1, pp.19-42. doi: 10.1002/sat.1064. Wiley. Accessed 2021-12-17.
  14. Kundaeli, Herald N. 2020. "The analysis of truncated ARQ and HARQ schemes using transition diagrams." International Journal of Engineering, Science and Technology, vol. 12, no. 2, pp. 35-51. MultiCraft Limited. Accessed 2021-12-17.
  15. Larsson, Peter. 2018. "On Performance Analysis of Retransmission Schemes with Fading Channels." Doctoral Thesis, KTH Royal Institute of Technology, Sweden, September. Accessed 2021-12-17.
  16. Larsson, P., B. Smida, T. Koike-Akino, and V. Tarokh. 2013. "Analysis of Network Coded HARQ for Multiple Unicast Flows." IEEE Transactions on Communications, vol. 61, no. 2, pp. 722-732, February. doi: 10.1109/TCOMM.2012.121112.110202. Accessed 2021-12-19.
  17. Lin, Shu, D. J. Costello, and M. J. Miller. 1984. "Automatic-repeat-request error-control schemes." IEEE Communications Magazine, vol. 22, no. 12, pp. 5-17, December. doi: 10.1109/MCOM.1984.1091865. Accessed 2021-12-18.
  18. Mandelbaum, D. 1974. "An adaptive-feedback coding scheme using incremental redundancy (Corresp.)." IEEE Transactions on Information Theory, vol. 20, no. 3, pp. 388-389, May. doi: 10.1109/TIT.1974.1055215. Accessed 2021-12-18.
  19. MathWorks. 2021. "DL-SCH HARQ Modeling." Help Center, LTE Toolbox, R2021b. Accessed 2021-12-17.
  20. Nadeem, Faisal, Yonghui Li, Branka Vucetic, and Mahyar Shirvanimoghaddam. 2021. "Analysis and Optimization of HARQ for URLLC." arXiv, v1, October 5. Accessed 2021-12-17.
  21. Ozkan, Ibrahim. 2019. "Analysis of Cooperative Hybrid ARQ with Adaptive Modulation and Coding on a Correlated Fading Channel." arXiv, v2, November 12. Accessed 2021-12-17.
  22. RFSpecialist. 2020. "5G Harq Retransmissions." Forum, Telecom Hall, November 23. Accessed 2021-12-18.
  23. Sassioui, Redouane, Mohammed Jabi, Leszek Szczecinski, Long Bao Le, Mustapha Benjillali, and Benoit Pelletier. 2016. "HARQ and AMC: Friends or Foes?" arXiv, v1, June 16. Accessed 2021-12-17.
  24. Shishir, G., R. Sonigra, N. Seshadri, and R. D. Koilpillai. 2021. "Hybrid-ARQ Protocol for Next Generation Wi-Fi Systems." International Conference on Communication Systems & Networks (COMSNETS), pp. 342-350. doi: 10.1109/COMSNETS51098.2021.9352833. Accessed 2021-12-18.
  25. Sindhu, Pradeep S. 1977. "Retransmission Error Control with Memory." IEEE Transactions on Communications, vol. 25, no. 5, pp. 473-479, May. doi: 10.1109/TCOM.1977.1093857. Accessed 2021-12-17.
  26. Vangelista, Lorenzo, and Marco Centenaro. 2018. "Performance Evaluation of HARQ Schemes for the Internet of Things." Computers, MDPI, vol. 7, no. 4:48. Accessed 2021-07-02.
  27. Wang, Yu-Ming, and Shu Lin. 1983. "A Modified Selective-Repeat Type-II Hybrid ARQ System and Its Performance Analysis." IEEE Transactions on Communications, vol. 31, no. 5, pp. 593-608, May. doi: 10.1109/TCOM.1983.1095873. Accessed 2021-12-17.
  28. Wozencraft, J. M., and M. Horstein. 1961. "Coding for Two-way Channels." Technical Report 383, MIT, January 3. Accessed 2021-07-04.

Further Reading

  1. Ahmed, A., A. Al-Dweik, Y. Iraqi, H. Mukhtar, M. Naeem and E. Hossain. 2021. "Hybrid Automatic Repeat Request (HARQ) in Wireless Communications Systems and Standards: A Contemporary Survey." IEEE Communications Surveys & Tutorials, vol. 23, no. 4, pp. 2711-2752. doi: 10.1109/COMST.2021.3094401. Accessed 2021-12-17.
  2. Mukherjee, Amitav. 2020. "Hybrid ARQ Schemes." In: Wiley 5G Ref: The Essential 5G Reference Online, John Wiley & Sons, May 16. doi: 10.1002/9781119471509.w5GRef015. Accessed 2021-12-18.
  3. Sassioui, Redouane, Mohammed Jabi, Leszek Szczecinski, Long Bao Le, Mustapha Benjillali, and Benoit Pelletier. 2016. "HARQ and AMC: Friends or Foes?" arXiv, v1, June 16. Accessed 2021-12-17.
  4. Cipriano, A. M., P. Gagneur, G. Vivier, and S. Sezginer. 2010. "Overview of ARQ and HARQ in Beyond 3G Systems." IEEE 21st International Symposium on Personal, Indoor and Mobile Radio Communications Workshops, pp. 424-429. doi: 10.1109/PIMRCW.2010.5671369. Accessed 2021-12-17.

Article Stats

Author-wise Stats for Article Edits

Author
No. of Edits
No. of Chats
DevCoins
Avatar of user arvindpdmn arvindpdmn
4
0
2166
DevCoins due to articles, chats, their likes and article hits are included.
2163
Words
1
Authors
4
Edits
0
Chats
3
Likes
9918
Hits

Cite As

Devopedia. 2021. "Hybrid ARQ." Version 4, December 20. Accessed 2024-06-25. https://devopedia.org/hybrid-arq
Contributed by
1 author

Last updated on
2021-12-20 09:55:00
networking protocol reliability

See Also

  • Automatic Repeat Request
  • Forward Error Correction
  • Soft-Decision Decoding
  • 5G NR Hybrid ARQ
  • Cyclic Redundancy Check
  • Coding Theory