HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
A simple and efficient hybrid ARQ mechanism for Wimax
---
Abstract
The motivation for this paper is to propose a reliable error control mechanism that can provide high end to end throughput. The scheme proposed here is based on the principle of Type-II Hybrid ARQ mechanism. We chose Type-II Hybrid ARQ mechanism for the error control for the simple reason that Type-I Hybrid ARQ uses a more conservative approach for transmission, as the code must be able to correct and detect the error reducing the throughput. In this scheme error correcting parity bits are only transmitted only when needed. The channel is inherently assumed to have a low level of ambient noise, with intermittent bursty noise which is significantly higher. Thus the initial coding has just enough capacity to detect and correct the error caused due to ambient noise. If there is burst noise, this noise is detectable, but not correctable. On detection of uncorrectable error due to burst noise the transmitter transmits parity bits that has error correcting capability, thus making the codeword robust . This second transmission uses an invertible code, but only transmits the error correcting bits. Since the number of error correcting bits are the same as the number of message bits for a (k,2k) code, the retransmission can be conveniently transmitted in a standard message block, without requiring fragmentation. The invertibility of the code further enhances the throughput as this gives the flexibility to the decoder to decode the message just on the basis of parity bits independent of the message. Thus, when the parity block is received, it is used to recover the originally transmitted data block either by inversion or by decoding operation. The repetitions of the parity block and the data blocks are alternately stored in the receiver buffer for error correction until the data is recovered. The proposed hybrid ARQ scheme provides both high system throughput and high system reliability.
Introduction
Wireless channel is prone to error due to noise, attenuations and fading. Achieving reliable transmission with optimum throughput level remain as a challenge. Most wireless systems have adopted error combating scheme in both physical layer (e.g. equalizers, error correction coding, spread spectrum techniques and diversity techniques) and data link layer(e.g. retransmission error correction and error detection frame length control). We shall talk about error control coding in data link layer to achieve reliable communication over a wireless link. Error control scheme can be broadly classified into two types ARQ and FEC.
In classic ARQ, reliability is achieved by retransmission of lost data. FEC on the other hand adds redundancy to facilitate recovery of the lost information. ARQ techniques offer reliability when channel conditions deteriorate, but throughput suffers due to frequent retransmissions. In comparison, FEC techniques offer a constant throughput but reliability depends upon the code rate. The lower the code rate, the better the performance, but throughput is lower as well.
Proper combination of these two techniques can overcome their respective drawbacks. A hybrid of FEC and ARQ scheme known as Hybrid ARQ can be used to better the throughput and reliability performances. H-ARQ schemes are very adaptive and flexible in nature. The retransmission protocol helps in maximizing the the probability of correct delivery in dynamically changing environment, ensuring improved throughput. 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 if data block is decoded successfully or a NAK if data block is un-decodable. The transmitter responds to a NAK by re-transmitting the information. Based on the retransmission strategy hybrid ARQ can be classified as either type-I or type-II hybrid ARQ.
Type-I hybrid ARQ
Type-I hybrid ARQ involves an error correction and detection code over each data block. When errors are detected in a coded block error detection the receiver attempts to correct them (error correction). Depending upon the channel conditions and error pattern errors are either correctable or not. The receiver accepts the coded block if the error pattern is correctable and sends an ACK. If not, the receiver rejects the coded block and transmits a NAK. The transmitter then retransmits the coded frame. This continues until data is successfully decoded. Type-I hybrid ARQ is most suitable when the channel stays stationary i.e. constant error rates. Thus a code can be designed intelligently to overcome errors over the channel. If the channel quality fluctuates wildly one is wasting parity bits when the channel is good, while sending many retransmissions when the channel is bad.
Type-II hybrid ARQ
The basic principle with of the type -II ARQ scheme is it starts the transmission with a high code rate with minimal detection/correction capability and if a retransmission is required only the extra redundant symbols are transmitted (incremental redundancy). Thus, the throughput for this scheme will be better than a simple ARQ scheme for bad channel conditions.
In this scheme error correcting parity bit is sent to the receiver only after the error has been detected in the initial transmission by the receiver. Thus message is coded with parity bit only meant for error detection, and possibly minimal error correction. In the case the received codeword has error the receiver stores the erroneous message in buffer. The receiver then instructs the transmitter to transmit the parity block for the original message and an error detecting and error correcting code. When the parity block is received it is used to correct error in erroneous message that is stored in receiver buffer. If the error correction is successful the corrected message is sent to sink, else, another retransmission request is sent to the transmitter. The second retransmission can be a parity block or original codeword. The choice of the right code and proper retransmission strategy may help in achieving a very high performance values.
The proposed scheme
The scheme proposed is based on parity data retransmission strategy using rate convolution (maximum likelihood) decoder. The error detecting code C_0_ (n,k) is used which can be a simple cyclic code. Error correcting coded C_1_ used is half rate (2,1,m) convolutional code with memory order m. The decoder uses Viterbi algorithm. Let G_1_(x) and G_2_(x) be the generator polynomial associated with the convolutional code C_1_.
When the k message bit arrives at the coder for transmission, the error detecting code C_0_ encodes the k message bit sequence into n bit codeword I(x). The convolution encoder further encodes the n bit message into two sequence P _1_(x)= I(x)G _1_(x) and P_2_(x)= I(x)G_2_(x) each of (n+m) bits which can be interleaved to form 2*(n+m) bits codeword. In the proposed scheme during the first transmission P_1_(x) is transmitted while the sequence P_2_(x) is stored in transmit buffer. Let P_1_'(x) be the received sequence corresponding P_1_(x). P_1_(x) is divided by G_1_(x), let R _1_(x) and I _1_(x) be the remainder and the quotient. If R _1_(x) =0; I _1_(x) is checked against convolution code C_0_ . If syndrome S(x) is zero I _1_(x) is assumed error free and is delivered to the sink after deleting n-k parity bit.
If R_1_(x) 0; or S(x) 0 errors are detected. The receiver sends the NAK to the transmitter and stores P_1_(x) in receiver buffer. The transmitter sends P _2_(x) to the receiver. Let P_2_(x) be the received sequence corresponding P _2_(x). P_2_(x) is divided by G_2_(x), let R_2_(x) and I_2_(x) be the remainder and the quotient. If R_2_(x) =0; I _2_(x) is checked against convolution code C_0_. If syndrome S(x) is zero I_2_(x) is assumed error free and is delivered to the sink after deleting n-k parity bit and deletes P_1_(x) from the receiver.
If R_2_(x) 0; or S(x) 0 errors are detected, P _2_(x) together with previously stored P_1_(x) are decoded with half rate convolutional decoder C _1_ viterbi decoder. Let I(x) be the decoded sequence. I(x) is detected using C_0_ . If syndrome S(x) is zero I(x) is assumed error free and is delivered to the sink after deleting n-k parity bit. If S(x)=0, errors are detected, P _1_(x) replaced by P_2_(x) in the receiver buffer and receiver sends another NAK to the transmitter. The transmitter then would transmit P_1_(x). The alternate transmission of P_1_(x) and P_2_(x) shall continue until I(x) is finally recovered.
The proposed scheme with invertible code
Alternatively, we can use the above scheme with invertible code for more robust H-ARQ performance. In this scheme two linear codes are used in this scheme: one is a high rate (n, k) code C_0_ , designed for error detection only, and the other is a half-rate invertible (2k , k) code C_1_ designed for simultaneous error correction and error detection.
Let the message be made of n codeword containing k information bits and n-k parity bits. Let (D, Q) be the transmitted codeword using C_0_ error detecting code where D represents the k message part and Q represents the n-k parity part. Also, the transmitter computes the k parity-check bits, denoted P(D), based on the message D and the half rate invertible (2k,k) code C_1_. Thus, (D, P(D)) is a codeword in C_1_. The k-bit parity block P(D) is not transmitted, but stored in the retransmission buffer of the transmitter for later use.
Let (D, Q) be the received codeword when (D, Q) is transmitted. On receiving (D,Q ), the receiver computes the syndrome based on C_0_. If the syndrome is zero, then (D,Q ) is assumed to be error-free. If the syndrome is nonzero, the presence of errors in (D,Q ) is detected. The erroneous message (D,Q ) is saved in the receiver buffer and a negative acknowledgment (NAK) is sent to the transmitter.
On receiving this NAK, the transmitter encodes the k-bit parity block P(D) into a codeword (P(D),Q_1_) of n bits based on the error-detecting code C_0_, where Q_1_ denotes the n - k parity-check digits for P(D). Let (P(D),Q_1_') denote the received code when (P(D),Q_1_) is transmitted. The receiver checks the syndrome of the received codeword. If the syndrome of the received codeword is zero. The message D is recovered from P(D) by inversion. Else if the syndrome is not zero then P(D) and erroneous message D stored in the buffer are together used for error correction based on the half rate code C_1_. If the pair (D,P(D)) form a correctable error pattern, they are corrected. The decoded message D is then accepted by the receiver and a positive acknowledgment (ACK) is sent to the transmitter. If the error in (D,P(D)) can be detected but not corrected, NAK is sent to the transmitter. Also the receiver replaces D with P(D) in its buffer. The transmitter on receipt of NAK transmits (D,Q). The receiver then computes the syndrome of the received packet (D, Q) as mentioned previously. If the syndrome of the received codeword is zero which is based on error-detecting code C_0_ the receiver combines the stored parity code P(D) with received erroneous message D. If the pair (D,P(D)) form a correctable error pattern, they are corrected. The decoded message D is then accepted by the receiver and a positive acknowledgment (ACK) is sent to the transmitter. If the error in (D,P(D)) can be detected but not corrected, NAK is sent to the transmitter. Also the receiver replaces P(D) with D in its buffer. On receiving this NAK, the transmitter transmits (P(D),Q_1_). The process is carried on until the message D is successfully decoded.
The key points in the above scheme is the range of coding mechanism with which the codeword can be transmitted making the scheme robust. Also the flexibility the invertible code gives enhances the throughput and robustness of the entire scheme. Due to the invertible property of code the message D can be reconstructed uniquely from the parity block P(D) by inversion. Hence, the parity block. P(D) contains the same amount of information as the message D. As a result, the overhead per transmission or retransmission is simply the number of parity-check bits n - k needed for error detection based on the (n, k) code C_1_, which is required by any ARQ scheme. Therefore, when the channel error rate is low, the type-II hybrid ARQ scheme maintains the same throughput as its corresponding ARQ scheme. When the channel error rate is high, the error-correct:ion capability provided by the half-rate code , and the parity retransmission reduces the retransmission frequency and maintains high throughput. The decoding complexity for the type-II hybrid ARQ scheme is only slightly greater than that of a corresponding type-I hybrid ARQ scheme with the same designed error-correcting capability. The extra circuits needed for the type-II hybrid ARQ scheme are an inversion circuit based on C_1_, which is simply a linear sequential circuit, and an error-detection circuit based on Co. The disadvantage of the type-I hybrid ARQ is that the overhead due to the extra parity-check bits for error correction must be included -in each transmission regardless of the error rate. When the channel is quiet, this represents a waste. However, the type-II hybrid ARQ removes this disadvantage.
This parity retransmission strategy can be incorporated with any of the three basic types of ARQ, namely, stop-and-wait, go-back-N, and selective-repeat ARQ schemes. It is particularly effective when it is used in conjunction with the selective-repeat ARQ.
Integration with wimax
The Wimax/Wifi protocol specification is still evolving. Hybrid ARQ is supported, but the support is limited.
As per the protocol specification, the convolutional turbo code is meant to be used in hybrid ARQ, since it admits incremental strengthening. The intent seems to be to support incremental redundancy by using a constant mother code and puncturing it at different rates. However, wimax does not really support very aggressive coding rates; even the R3/4 coding rate has quite significant error correcting capability.
Additionally, the way the base 802.16 spec is defined, it is very difficult to implement any form of Hybrid ARQ other than Stop-and-wait. If there are multiple packet losses in a given burst, there is no way to identify a retransmission as specifically pertaining to a given burst. The channel for negative retransmissions is ill-defined and there is no tie in with the burst scheduling algorithm.
However, there is some interest in the community for improving H-ARQ support in the Wimax specifications.
A change request submitted by Motorola and Intel in 2004 attempts to extend the 802.16e specification to support chase combining h-ARQ in all FEC types and also all multi-channel stop and wait ARQ. This will significantly improve h-ARQ performance. This change proposal2 calls for the following:
1.Modification of the HARQ MAP so as to integrate the negative acknowledgment of corrupted packets with the allocation of fresh slots for retransmission
2.Multi-channel support for the stop and wait protocol. This potentially allows the correction of several corrupted bursts simultaneously
3.The use of spid is optional, but can be used to identify a retransmission. In our mechanism, the retransmission is not a direct copy of the original data but the parity information; specifically, it is difficult to extract the packet identifier from this packet, unless it is received absolutely correctly; without identifying the packet identifier, the combining mechanism doesn't work. Potentially, however, the channel can identify the packet for retransmission and thus solve this problem.
Further work
We intend to extend our scheme by integrating it with the CTC coding rate currently preferred for H-ARQ in Wimax. The challenge is to design a complementary coding format for CTC which will generate an invertible parity check sequence. This is known as a 'complementary turbo code' or 'quasi-complementary turbo code'. One possibility is to use a very low-rate mother code and use complementary puncturing patterns to generate invertible outputs. An idea similar to this is suggested in 3.
Categories: Wimax
Comments
