A hybrid ARQ system with erasures correction and parity retransmission.

1. Introduction

Automatic Repeat Re-Quest (ARQ) systems with error control are widely used for data transmission over noisy channels. Their performance is usually characterized by two parameters: Throughput Efficiency (TE) and Bit Error Rate (BER). So-called hybrid ARQ (HARQ) systems use two codes (inner and outer) [1-8]. In a HARQ-1 system Forward Error Correction (FEC) is performed prior to error detection [2]. In more effective HARQ-II [3-5] system, parity-check digits for error correction are sent to the receiver only when they are needed. For example [3], at the initial step data blocks D with parity-check bits of the outer error detection code are transmitted. If errors in D are detected, the system begins not simple repetitions of D, but repetitions of a parity block P(D) of the inner code. P(D) as well as D itself are alternately stored in the receiver buffer for error correction until D will be recovered. As shown in [4], application of HARQ schemes can significantly improve TE in comparison with a pure ARQ scheme.

It is well known [1] that error correcting capability of block codes may be enhanced when soft decision approach is realized, for example, in the form of Soft Decision Erasures Correcting (SDEC) decoding [7-9]. In this case the number of erroneous bits that may be corrected is not less than [d.sub.H]-1. It is assumed also that all error symbols are erased, while for FEC decoding the number of erroneous corrected bits is not less than 0.5([d.sub.H]-1), where [d.sub.H] is the minimum Hamming distance of the block code.

In this paper, a modified type of HARQ-II is considered. Two linear block codes are used in the system: an outer systematic (n,k) block code CZ and an inner half-rate invertible (2k,k) code C,. At the receiver FEC and SDEC decoding are used alternately, according to the procedure described below. The system is named HARQ with Erasures Correction (HARQ-EC). Theoretical analysis and computer simulation of the proposed system are performed for the case of noiseless feedback, Nakagami common fading and Additive White Gaussian Noise (AWGN) in the forward channel (1). Moreover, we consider the forward channel as memoryless, i.e. interleaving/de-interleaving assumed to be ideal. The obtained results show that HARQ-EC provides gain in BER, or gain in TE in comparison with parameters of HARQ-II for the same outer and inner codes [2,4-5].

The paper is organized as follows. In Section 2, we describe the HARQ-EC algorithm. In Section 3 the relevant BER and TE are analyzed. The comparison of HARQ-EC and HARQ-II characteristics is given in Section 4. Section 5 presents discussion of results and some conclusions.

2. Description of the HARQ-EC System

HARQ-EC scheme uses the outer (n,k) code [C.sub.2] with minimal Hamming distance [d.sup.(2).sub.H] and the inner (2k,k) half-rate invertible code [2] [C.sub.1] with minimal Hamming distance [d.sup.(1).sub.H]. It is called invertible since with the help of inversion of k parity-check bits k information bits can be uniquely determined. We assume that each transmitted message D consists of k information bits and that each encoded message, called a code word CW, consists of n bits. When D is ready for transmission, it is encoded by the outer encoder into the transmitted n-length code word [CW.sub.2](D,Q), where Q denotes the vector of n-k parity-check bits. In parallel the transmitter computes k bits of the parity-check block P(D) of the half rate invertible (2k,k) code [C.sub.1]. The block P(D) is not transmitted and is stored in the buffer for later use.

Let [CW.sub.2](Dr Qr) denotes the received vector if [CW.sub.2](Dr, Qr) was transmitted. The received data block Dr is passed to the forward channel receiver of the HARQ-EC. Its key elements are Soft Decision Maximum Likelihood Demodulator (SDMLD), FEC and Errors Erasure Correction (EEC) decoders for the outer and inner codes respectively. In SDMLD the decision [A.sup.(r).sub.i] about symbol Al is obtained according to the following rule [7]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where Ai is the log-likelihood ratio calculated for the i-th symbol, His the dimension of the used constellation, and thr is the threshold level determining the width of the erasure zone in the decision space of the SDMLD. If the number of the erased bits [t.sup.(2).sub.er] in the code word is zero, the received vector feeds the outer code of the FEC decoder and after error correction the restored message Dr is sent to the user. If [t.sup.(2).sub.er] > 0, the received vector is passed to the outer code of the EEC decoder. If this combination is identified by the EECD with only one of the codebook [C.sub.2], it is considered as the transmitted codeword and the message Dr is sent to the user. Otherwise, the ReQuest signal (RQ) is sent to the transmitter via the feedback channel. Simultaneously, the message Dr (with erased elements) is saved in the buffer of the receiver. Upon receiving this request, the transmitter encodes the k-th parity bits block P(D) of the inner code [C.sub.1] into the n-length codeword [CW.sub.2](P(D),[Q.sup.(P)]) of the code [C.sub.2] where [Q.sup.(P)])denotes the n-k parity-check digits for P(D).

Let [CW.sub.2](Pr(D), [Q.sub.r.sup.(P)]) denotes the received vector corresponding to [CW.sub.2](P(D), [Q.sup.(P)])). The SDMLD, according to (1), erases its unreliable symbols. If the number of the erasures [t.sup.(2).sub.er] in [CW.sub.2]([P.sub.r](D), [Q.sub.r.sup.(P)]) is equal to zero, the received vector is passed to the FEC decoder of the outer code. After error correction procedure, the message D is recovered from [P.sub.r](D). by inversion and is sent to the user. Otherwise, the received vector is passed to the EECD of the outer code. If vector [CW.sub.2]([P.sub.r](D), [Q.sub.r.sup.(P)])is identified by the EECD, the message D is recovered with the help of inversion of [P.sub.r](D). The message Dr that is stored in the receiver memory (after recovery of D from [P.sub.r](D)) is then discarded. If the combination [CW.sub.2]([P.sub.r](D), [Q.sub.r.sup.(P)]) is not identified by the EECD of the outer code, the received parity block [P.sub.r](D) is integrated with Dr kept in the buffer. The code word [CW.sub.1]([D.sub.r], [P.sub.r](D)) of the code [C.sub.1] with [t.sup.(1).sub.er] erased symbols is formed and passed to EECD of the inner code. If this combination is identified by EECD with certain vector of the code book [C.sub.1] then it is considered to be correct and the recovered message D is passed to the user. Otherwise, the request signal is generated and transmitted via the backward channel. Simultaneously, the message D is discarded from the receiver buffer, and the parity block [P.sub.r](D) (with erased symbols) is saved in the receiver buffer. Upon receiving the second request for the message D, the transmitter resends the code word [CW.sub.2](D,Q) and the procedure described above is repeated. The block diagram in Figure 1 illustrates transmission and retransmission procedures in the proposed HARQ-EC.

3. Analysis of the HARQ-EC Performance in Fading Channel

The main characteristics of any ARQ systems are BER and TE, defined as

TE = E[N]/E[V] * k/n, (2)

BER = 1- [(1 - [P.sub.NC]).sup.k]

where V is the total number of transmitted code words and N is the number of information messages sent during the transmission interval, E[V], E[N] denote the expectations of V and N respectively, and [P.sub.NC] is the probability of an undetected word error. As follows from [2], for selective-repeat ARQ scheme with noiseless feedback channel, unlimited receiver buffer and maximal number of retransmissions the values of TE and [P.sub.NC] may be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

where [P.sup.(l).sub.crd] and [P.sup.(l).sub.erd] are probabilities of correct and erroneous reception of the data block, respectively, at the l-th (2) start of the procedure described above (see Figure 1).

[FIGURE 1 OMITTED]

We analyze performance of HARQ-EC for the case of a binary modulation. The transmitted signal within one symbol time duration T is represented by

[s.sub.m](t) = Re {[A.sub.m]g(t - mT)exp(j[[omega].sub.c],t)} (4)

where [A.sub.m] is the information symbol, g(t) is the impulse response of the transmitter filter and [w.sub.c] is the carrier frequency (3). As was mentioned earlier, we consider the case of the forward channel with additive white Gaussian noise and flat fading with Nakagami distribution [8]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

where [Gamma](m) is the gamma function, [[mu].sup.2.sub.0] = E{[[mu].sup.2]}, and m [greater than or equal to]0.5 is the fading depth parameter (4). Moreover, it is assumed that fading is slow, which means that [[mu].sub.ch] may be considered constant, at least for one symbol interval T.

The signal [x.sub.m](t) is demodulated by SDMLD which includes a Log-Likelihood Ratio (LLR) estimator followed by a Decision Device with Eraser (DDE) [1]. The output of LLR is

[[Lambda].sub.12] = [q.sub.1] - [q.sub.2],

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for coherent SDMLD and

[q.sub.1] = [square root of [X.sup.2.sub.1] + [Y.sup.2.sub.1], i =1,2]

for noncoherent SDMLD.

Here

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the Hilbert transform of [s.sub.i](t), and T is the symbol duration. The vector [[Lambda].sub.cw] = [[[Lambda].sub.1], [[Lambda].sub.2], ... [[Lambda].sub.l] ..., [[Lambda].sub.n]] is passed to DDE which produces a version of the outer code word. The elements of the received vector [C.sup.(r).sub.2]) are obtained according decision rule (1), which in our case can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Using (6) and results of BER analysis for binary orthogonal set of signals [1] probabilities of symbol error [P.sub.e] and symbol erasure [P.sub.ers] are written as (see Appendix A)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

where [[gamma].sub.0] = E{[[mu].sup.2] [E.sub.s]/[[mu].sup.2.sub.0] [N.sub.0]} and [E.sub.S] is the energy of the transmitted signal element. With the help of (7) and (8) we estimate performance of the considered system.

Taking into account transmission and retransmission procedures in HARQ-EC, probabilities of correct and erroneous decoding of the code word can be evaluated with the help of the following expressions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

are probabilities of correct decoding, erroneous decoding and request of the code word [CW.sub.2]([D.sub.r],[Q.sub.r]) respectively, at the first stage of transmission,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

are probabilities of correct decoding and erroneous decoding of the codeword [CW.sub.2]([D.sub.r],[Q.sub.r]) respectively, at the second stage of transmission,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

are probabilities of correct and erroneous decoding, respectively, of the code word [CW.sub.1]([D.sub.r],[P.sub.r](D)), which is created from the block of data Dr extracted from the receiver memory and the parity block [P.sub.r](D) of the inner code received at the second stage of transmission. Here [P.sup.([FEC.sub.j]).sub.cr], [P.sup.([FEC.sub.j]).sub.er] are probabilities of correct and erroneous reception of code words at the output of the FEC decoders, and [P.sup.([RC.sub.j]).sub.cr], [P.sup.([RC.sub.j]).sub.er]) are probabilities of correct and erroneous reception of code words at the output of the errors erasure correction decoders, for the inner (j=1) and outer (j=2) codes respectively.

Bearing in mind the assumptions made above on the statistical properties of the channel, we consider that errors, as well as erasures in the received stream of code symbols, are independent. In this case probabilities [P.sup.([FEC.sub.j]).sub.cr], [P.sup.([FEC.sub.j]).sub.er], [P.sup.([RC.sub.j]).sub.cr], [P.sup.([RC.sub.j]).sub.er] and [P.sup.(j).sub.rq] for the outer and inner codes can be determined (Appendix B) with the help of the following expressions:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

[n.sub.j] is the length of code word, [d.sub.[H.sub.j]] is the minimum Hamming distance of the used code, [t.sub.[er.sub.j] is a number of codeword symbols erased in the SDMLD, and [t.sub.[erd.sub.j] is the number of the erased symbols taken from those that determine the Hamming distance of the original code (o [less than or equal to] [t.sub.[erd.sub.j] [less than or equal to] [t.sub.[er.sub.j]. Substituting (7), (8) into (13), (14), and the results into (9-12) and afterward into (2) and (3), we obtain values of TE and BER. For the given inner and outer codes they depend on the average SNR [[gamma].sub.0] and on the threshold thr.

4. Comparison of HARQ-EC and HARQ-11 Performance

In this Section, we compare the theoretical results obtained above for HARQ-EC with those obtained by computer simulation. Then we will compare the performance of HARQ-EC to that of HARQ-11 schemes [2, 4,5] for the same inner and outer codes (5). The systematic linear block code with parameters [n.sub.2]=15, k=11 and [d.sub.[H.sub.2]] = 3 is used as the outer code [C.sub.2], and the half invertible code with [n.sub.1] =22, k=11 and [d.sub.[H.sub.1]] = 7 is used as the inner code [C.sub.1].

Figures 2, 3 show for HARQ-EC dependence of BER and TE (for the threshold values thr=1.5, thr=2, and thr=3), obtained as a result of analytical calculation and computer simulation respectively. Inspection of Figures 2 and 3 demonstrates good agreement between theory and simulation results. It follows that increase of the threshold level thr in HARQ-EC leads to decrease of both BER and TE.

Figure 4 shows BER for HARQ-EC (for the threshold values thr=1.5, thr=2, and thr=3), HARQ-I1 and FEC systems with the same code redundancy as a function of the average SNR while at Figure 5 dependence of TE of the compared systems from average SNR is presented. Examination of these figures demonstrates the fact that by choice of thr value in SDMLD of HARQ-EC, gain in BER or TE can be achieved. For example, TE of HARQ-EC with thr=2 exceeds TE of HARQ-II for a roughly equal value of BER in a quite wide range of average SNR.

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

5. Conclusions

We propose the Hybrid ARQ system with erasure of unreliable symbols and retransmission of the code words (HARQ-EC). Its performance is considered for the case of flat Nakagami fading and AWGN in the forward channel. The obtained theoretical results are valid for any memoryless channel with common slow Nakagami fading, while the calculations and simulation were performed for Rayleigh fading. Good agreement between theoretical and simulation results is obtained. It has been shown that performance of HARQ-EC may be better than HARQ-11 over a wide range of average SNR when the same codes are used.

Appendix A

Let us assume that symbol "1" was transmitted. The probability of correct reception [P.sub.cr] in SDMLD can be found as the probability that A,>thr, and the probability of symbol erasure [P.sub.ers] in SDMLD, in turn, can be obtained as the probability that 1/thr [less than or equal to] [[Lambda].sub.i] [less than or equal to] thr. From (6) we obtain.

[P.sub.cr] ([mu]) = p([[Lambda].sub.i] > thr), [P.sub.ers] ([mu]) = P (1/thr [less than or equal to] [[Lambda].sub.i] [less than or equal to] thr) (A1)

where (see [1])

[[Lambda].sub.i] = [U.sub.1]/[U.sub.2] >

[U.sub.1] = |[2E.sub.S][[mu]e.sup.-j[phi]] + [N.sub.1]|

[U.sub.2] = |[N.sub.2]| (A2)

[N.sub.1] and [N.sub.2] are complex-valued Gaussian random variables with zero mean and variance ([[sigma].sup.2] = 2[mu]Es, [U.sub.1] and [U.sub.2] are mutually independent variables with distributions [1]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A3)

Taking into account (A1), (A2) we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A4)

With the help of elementary algebra and tabulated integrals

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A6)

where

[gamma]([mu]) = [[mu].sup.2][E.sub.s]/[N.sub.0] (A7)

Taking into account that

[P.sub.e] = 1 - [p.sub.cr] - [P.sub.ers]

we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A8)

Probabilities (A6) and (A8) are conditional probabilities of erasure and error reception in SDMLD respectively, given u and therefore Pe and Per are

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A9)

where f([mu]) is defined by (5).

Appendix B

Let us determine probability of request [P.sub.rq], probabilities of correct and erroneous reception of a code word at the output of the ECE decoder ([P.sup.(RC).sub.cr] and [P.sup.(RC).sub.er]), and also at the output of the FEC decoder ([P.sup.(FEC).sub.cr] and [P.sup.(FEC).sub.er]) under the following conditions:

1) The code used is a linear block code (n,k) with the minimal Hamming distance [d.sub.H];

2) The encoded bit stream is represented by a codeword CW with length n, supplied from the SDMLD output to the FEC decoder, if CW does not contain the erased symbols. Otherwise, a codeword CW feeds the ECE decoder.

3) Errors and erasers in a sequence of code symbols CW are independent (the channel is memoryless). For Nakagami frequency -nonselective fading in the forward channel, the probabilities of symbol error Pe and symbol erasure Pers are defined by (7), (8).

First, we find probabilities [P.sup.(FEC).sub.cr] and [P.sup.(FEC).sub.er]. Since symbol errors are independent events, the binomial law determines probabilities of correct and erroneous reception of a code word at the output of the FEC decoder. Keeping in mind that FEC decoding is used when the number of erased symbols in the received codeword [t.sub.er]=0, we thus obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (B1)

where [t.sub.er] is the number of correct errors per codeword.

Probabilities [P.sub.rq], [P.sup.(RC).sub.cr] and [P.sup.(RC).sub.er] may be obtained as follows. The ECE decoding is used when [t.sub.er]> 0, where [t.sub.er] is a number of the erased symbols in the received code word. The erasure of [t.sub.er] symbols from n creates a new shorter code with code word length [n.sup.(sh)]=n-[t.sub.er] and the Hamming distance [d.sup.(sh).sub.H] = [d.sub.H] -[t.sub.erd], where [t.sub.erd] is the number of erased symbols taken from those ones that determine [d.sub.H] of the original code (0[less than or equal to][t.sub.erd][less than or equal to][t.sub.er]). Since symbol erasures are independent, the probability of the erasure of [t.sub.er] symbols from n as well as probability of the erasure of [t.sub.erd] symbols from [d.sub.H] are determined by the binomial law. Taking this into account, we obtain [P.sub.rq] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (B2)

Probabilities of correct and erroneous reception of a code word at the output of ECE decoder depend on the random variables [t.sub.er] and [t.sub.erd], i.e. they have to be considered as conditional probabilities P(cr/[t.sub.er],[t.sub.erd]) and P(er/[t.sub.er],[t.sub.erd]) written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (B3)

Twice averaging (B3) by the binomially distributed [t.sub.er] and [t.sub.erd], we obtain the unconditional probabilities [P.sup.(RC).sub.cr] and [P.sup.(RC).sub.er] (see 13).

10.4236/ijcns.2009.27069

Received June 30, 2009; revised August 4, 2009; accepted September 8, 2009

Published Online October 2009 (http://www.SciRP.org/journal/ijcns/).

6. References

[1] J. C. Proakis, "Digital communications," McGraw-Hill, New York, 1995.

[2] S. Lin and P. S. Yu, "A hybrid ARQ scheme with parity retransmission for error-control in satellite channels," IEEE Trans. Commun., Vol. COM-30, No. 7, pp. 1701-1719,1982.

[3] Y. Wang and S. Lin, "A modified Selective-Repeat Type-11 Hybrid ARQ system and its performance analysis," IEEE Trans. Commun., Vol. COM-31, No. 5, pp. 593-607,1983.

[4] K. Q. Archer and J. A. Edwards, "Effect of channel fade rate on throughput of three GHARQ-11 schemes over Rayleigh fading channel," Electronic Letters, Vol. 31, No. 16, pp. 1320-1322, 1995.

[5] C. Sunkyun and K. Shin, "A class of adaptive hybrid ARQ for wireless links," IEEE Trans. Veh. Tech., Vol. 50, No. 3, pp. 777-790, 2001.

[6] S. Kallel, R. Link, and S. Bakhtiyari, "Throughput performance of memory ARQ schemes," IEEE Trans. Veh. Tech., Vol. 48, No. 3, pp. 891-899, 1999.

[7] S. B. Wicker, "Reed-Solomon error coding for Rayleigh fading channels with feedback," IEEE Trans. Veh. Tech., Vol. 41, No. 2, pp. 124-133, 1992.

[8] L. Goldfeld, V. Lyandres, and D. Wulich, "ARQ with erasures correction in the frequency-nonselective fading channel," IEICE Trans. Commun., Vol. E80-B, No. 7, pp. 1101-1103,1997.

[9] T. Hashimoto, "Comparison of erasure-and error threshold decoding schemes," IEICE Trans. Fundamentals, Vol. E76-A, pp. 820-827, 1993.

L. GOLDFELD, A. HOFMAN, V. LYANDRES

Department of Electrical and Computer Engineering, Communications Laboratory, Ben-Gurion University of the Negev, Beer-Sheva, Israel

Email: [e-mail]

(1) The assumption of noiseless feedback does not reduce the generality of the analysis, as we are interested in the performance comparison of HARQ-EC and HARQ-11 system in the same conditions.

(2) The index l will be omitted as the statistics of errors and erases in the received codeword do not depend on l.

(3) The kind of modulation and alphabet dimension M does not reduce the generality of the analysis, as we are interested in a comparison of the HARQ-EC performance to HARQ-11 systems in the same conditions.

(4) The Nakagami pdf includes, as a special case, the Rayleigh pdf for m = 1, and can approximate both the Rice and log-normal pdf's [8].

(5) The kind of modulation and type of codes do not reduce the generality of the analysis, as we are interested in comparison of the HARQ-EC performance to HARQ-II systems in the same conditions.