Hybrid Automatic Repeat Request (HARQ)

Hybrid ARQ

A Hybrid ARQ system consists of combination of error control mechanism namely Forward Error Correction and Automatic Repeat Request. The function of FEC is to reduce the frequency of retransmission by correcting error pattern which occur most frequently. This increases the system throughput. In case of less frequent error occurrences which can be detected but not corrected, the receiver requests for retransmission. This in turn increases the reliability. Thus a proper combination of FEC and ARQ provides higher reliability than an FEC system alone and higher throughput than the system with only ARQ as error control mechanism. Hybrid ARQ is an important dynamic tool for maintaining QoS in modern wireless systems.

Hybrid ARQ involves an encoded forward link for error correction and detection and a feedback link for possible retransmission. At the transmitter, parity bits are added to the data block to detect and correct errors. In case the receiver is not able to correct these errors, the data block is transmitted again. For each received data block the receiver either sends an ACK (data block is received or decoded successfully) or a NACK (data block is un-decodable). The transmitter responds to a NACK by re-transmitting the information. Based on the retransmission strategy Hybrid ARQ can be classified as either type-I or type-II Hybrid ARQ.

Types of Hybrid ARQ

• Type I Hybrid ARQ
  
• Type II Hybrid ARQ
  

Type I Hybrid ARQ

In this mechanism FEC scheme used is capable of simultaneously detecting and correcting the error. When the decoder receives the packet, it first detects the error. In the instance that the error is detected, the decoder corrects the error provided the number of error is within the designed error correcting capability of the code and delivers the corrected packet to the user. In the instance the error is uncorrectable; the receiver rejects the packets and asks for retransmission. When the re-transmitted codeword is received the receiver once again tries to correct the error, if any. In case it is not able to correct the error it once again asks for retransmission. This continues till the codeword is successfully decoded. We observe that in this scheme the decoder must be able to detect and correct the received packet with error pattern. This technique asks for much more robust coding then a simple codeword with only error detection capability. This increases the overhead for each transmission. The advantage of using type-I scheme lies in the instance of high channel error rate. It provides higher throughput then corresponding scheme. This is because the error correction capability of the code will reduce the transmission frequency. On the flip side in the case of low channel error rate the re-transmissions in pure ARQ scheme is infrequent, this would lead to lower throughput in type-I scheme as compared to ARQ scheme.

Type-II Hybrid ARQ

Type-I HARQ scheme does not suit time varying channel because of the fixed code word and ARQ protocol used. An alternate scheme which suits time varying channel is Type-II Hybrid ARQ scheme. In this scheme the first transmitted packet need not contain parity bits for error correction. In the subsequent re-transmissions contains the parity for error correction. This method is also known as Incremental Redundancy. On the first transmission attempt only parity bits for error detection is appended to the message like in the basic ARQ scheme. In case of detected error in the received words, it is stored in receiver buffer and a retransmission request is sent to the transmitter. The retransmission is not the original codeword but block of parity bits based on the original codeword and error correcting code. When the retransmission containing parity bit is received it is used to correct the previously erroneously received codeword. If the error correction fails another retransmission request is sent. Based on the strategy and error correcting code being used, the transmitter can retransmit the original codeword or another parity block can be retransmitted. This process continues until the original codeword is decoded successfully.

Schemes in brief

Type I hybrid ARQ

• Discard erroneous received code word.
  
• Retransmit until packet correctly received or until pre-set number of retransmissions is achieved.
  
• Small buffer size required but an inefficient scheme.
  

Type II hybrid ARQ

• Store erroneous received code word.
  
• Optimally combine with retransmitted code word.
  
• Exploit incremental redundancy concept
  
• Effective Code rate is gradually lowered until packet is decoded correctly.
  
• System adapts to varying channel conditions.
  
• Larger buffer size required than Type-I but is a very efficient
  

Techniques proposed for HARQ

Source:Methods of Packet combining in HARQ system over Bursty Channel

The techniques described below works for burst channel and for the system that employs RS coding and bounded distance error coding and erasure coding. At the transmitter the data is encoded with an (n,k) singly extended RS code and configured into packet which contains N codeword's each. The Rx uses bounded distance error and erasure correction decoder with correction diameter de. With this pattern any error pattern is correctable by decoder provided 2t+e de. A decoding error occurs if the input error is within the diameter of some other codeword and a decoding failure occurs otherwise. The constant de can be chosen to be any value between zero and n-k, inclusive. The channel is assumed to be slowly changing with constant symbol error and erasure probabilities throughout the transmission of single packet. These probabilities can vary between packet transmissions. The channel is assumed to have L states; each state having its own error probability and erasure probability. There is a fixed probability of channel being in one of the states

1-2-3 Restart combining: The name of the scheme comes from the fact that after each 3 retransmissions, all the previous information are discarded and fresh decoding starts. Packet combining follows following rules

Two Packets :

Ist Packet	IInd Packet	Decoded packets
Codeword A	Codeword A	Codeword A
Codeword A	Codeword B	Decoding Failure(DF)
DF	Codeword B	Codeword B
DF	DF	DF

Three Packets:

Ist Packet	IInd Packet	IIIrd Packet	Decoded packets
Codeword A	Codeword A	X	Codeword A
Codeword A	Codeword B	Codeword C	DF
Codeword A	DF	DF	Codeword A

If any decoding failure exists within the combined packet then retransmission is needed

Performance Analysis shows that packet combining provides significant gain in throughput and reduction in error probability when compared with a system that does not employ combining

Source: An ARQ scheme with Packet Combining

In this scheme the receiver stores the erroneously received packets in the buffer. The receiver requests for retransmission in this case. If the retransmitted codeword is successfully decoded, the stored packet is discarded. However, if the second packet is also received erroneously then the two received copies are XORed to locate the errors in block together. The decision process then involves a brute force bit by bit inversion of located error position and checking for correctness using checksum. This operation fails if there is at least one bit position in which both copies have an error i.e. double error. In this case further retransmissions are requested and the procedure is repeated until the correct packet is retrieved. The probability of successful retrieval at Lth attempt is

1–i=1L–1P(r)T(p)+(1–T(p))(1–ad(L))

where a_d(L) is the conditional probability that, provided Lth copy is error, it has double errors with all the preceding L-1 copies in the buffer. The throughput is given by

T(p)=1E(L)

The upper limit of throughput is when a(L) is considered negligible (i.e no double error occurs)

TU(p)=12–T(p)

The complexity of the bit inversion procedure is given by

N=2(2npe)–2

From the above formula we see that even for the medium sized packets and at moderate BER random fluctuation of te channel may make bit inversion extremely complex. To make this algorithm implementable, an upper limit of computational complexity may be defined. The total number of 1's exceed Nmax the pair is discarded and either a new pair is chosen or retransmission is sought. The above scheme is suitable for small packet size |Different variant of the above described can be used like using the maximum likelihood estimate of the erroneously received packet and then further decoding the estimated packet.

Source: Analysis of a Type II Hybrid ARQ Scheme with Code Combining

In type-II Hybrid ARQ Code Combining technique two codes are used. An (n, k) block code, denoted C0, is used for error detection, and convolution code, C1(2, 1, m), is used for error correction. Let (G1(X), G2(X)) be the two generator polynomials of C1. Let Viterbi decoding be used. When a message is ready for transmission, it is first encoded into a codeword Z(X) in C0. The sequence Z(X) is then transformed into two sequences

P1(X)=Z(X)G1(X) and P2(X)=Z(X)G2(X) , each (n +m) bits long.

The 2(n+m) bit sequence obtained by interleaving P1(X) and P2(X) is a code sequence for Z(X) based on the rate 1/2 convolution code C1. Depending on hybrid ARQ strategy, the transmitter may alternately send the sequences P1(X) and P2(X). A correct reception occurs if the most recent received sequence is declared error-free

or if the combination of the two most recent received

Sequences' corresponding to P1(X) and P2(X) contains an error pattern correctable by C1. With code combining, transmissions also alternate between the two sequences P1(X) and P2(X), but the decoder for error correction operates on a combination of all received sequences, that is, a combination of the two first received sequences corresponding to P1(X) and P2(X), together with their repeated copies. This means that the receiver keeps all received sequences detected in error relative to a given codeword I(X) until final and correct reception occurs. Thus, if after the two sequences P1(X) and P2(X) have been transmitted once without successful decoding, then the sequence P1(X) is repeated by the transmitter, but both earlier received sequences corresponding to the first transmitted sequences P1(X) and P2(X), denoted P1(1)(X) and P2(1)(X) respectively, are saved for subsequent decoding attempts. Let the received sequence correspond to the repeated sequence P1(X) be denoted P1(2)(X). If P1(2)(X) is declared error-free, then the message is recovered and delivered to the user. Otherwise, the sequence P1(1)(X), P2(1)(X) and P1(2)(X) are interleaved together, forming a combined sequence which is considered as a received sequence to a codeword for Z(X), based on repetition code (3, 1, m)with generator polynomials (G1(X) ,

G2(X), G1(X)) . The combined sequence is processed by the

Viterbi-decoder. Should detected errors still

Remain, then the sequence P2(X) is repeated by the transmitter. Let P2(2)(X) be the received sequence. Again, error detection operation is performed on Pf(X). If P2(2)(X) is declared error-free, then the message is recovered and delivered to the user. If P2(2)(X) is detected in error, then it is combined with earlier received sequences P1(1)(X), P2(1)(X)and P1(2)(X), forming a sequence, which is now considered as issued from a repetition code (4,1, m) with generator polynomials (G1(X) , G2(X), G1(X), G2(X)). The combined sequence is processed again by the Viterbi decoder for an error correction attempt. Alternating with a repetition of sequences P1(X) and P2(X), this procedure is continued until it is correct and final recovery of the message occurs. Successive repetitions of sequences P1(X) and P2(X) and operation of code combining yield a family of repetition codes of decreasing rates 1/(2+i), i = 1, 2, . . . . These codes correspond to repetition codes of decreasing rates, obtained by alternately duplicating the two generator polynomials of the original rate 1/2 code (G1(X) , G2(X)). Two possible families of repetition codes of decreasing rates can be obtained, depending on which of the two generator polynomials G1(X) , G2(X) is duplicated first. Flow chart below depicts the basic principle describe above






In order to optimize the performance of the type II hybrid ARQ strategy with code combining, one should select the best of the two families of repetition codes of decreasing rates or, equivalently, order the two sequences P1(X) and P2(X) for successive repetitions, according to their contribution in the increase of the free distances of the resulting repetition codes. It has been shown numerically and through simulation that with channel degradation the throughput degrades drastically without code combining. At even high channel error rate a significant throughput is achieved with code combining.

Merits

Hybrid ARQ enables fine tuning of the effective code rate. Also enables additional gains by soft combing of packets from the original and subsequent packets prior to the decoding attempt

Fast link adaptation provides an initial estimate for the redundancy required for reliable transmission

Categories: Wireless