### Paper Menu >>

### Journal Menu >>

Int. J. Communications, Network and System Sciences, 2009, 7, 619-626 doi:10.4236/ijcns.2009.27069 Published Online October 2009 (http://www.SciRP.org/journal/ijcns/). Copyright © 2009 SciRes. IJCNS A Hybrid ARQ System with Erasures Correction and Parity Retransmission L. GOLDFELD, A. HOFMAN, V. LYANDRES Department of Electrical and Computer Engineering, Communications Laboratory, Ben-Gurion University of the Negev, Beer-Sheva, Israel Email: lyandres@ee.bgu.ac.il Received June 30, 2009; revised August 4, 2009; accepted September 8, 2009 ABSTRACT A modified type of Hybrid ARQ system with erasures correction and parity bits retransmission is considered. Performance of the system is analyzed under assumption that the forward channel suffers from Nakagami common fading and additive white Gaussian noise. A good agreement between theoretical results and simu- lation is achieved. The proposed ARQ protocol is compared with other known Hybrid ARQ algorithms. It demonstrates significantly higher throughput efficiency in a range of SNR. Keywords: Hybrid ARQ Scheme, Erasures Correction Decoding, Fading Channel 1. Introduction Automatic Repeat ReQuest (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) sys- tems use two codes (inner and outer) [1–8]. In a HARQ-I 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 ex- ample [3], at the initial step data blocks D with par- ity-check bits of the outer error detection code are trans- mitted. 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 al- ternately 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 com- parison with a pure ARQ scheme. It is well known [1] that error correcting capability of block codes may be enhanced when soft decision ap- proach is realized, for example, in the form of Soft Deci- sion Erasures Correcting (SDEC) decoding [7–9]. In this case the number of erroneous bits that may be corrected is not less than dH –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(dH –1), where dH is the minimum Hamming distance of the block code. In this paper, a modified type of HARQ-II is consid- ered. Two linear block codes are used in the system: an outer systematic (n,k) block code C2 and an inner half- rate invertible (2k,k) code C1. 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 ana- lysis 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 channel1. Moreover, we con- sider the forward channel as memoryless, i.e. interleav- ing/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 rele- vant BER and TE are analyzed. The comparison of HARQ-EC and HARQ-II characteristics is given in Sec- tion 4. Section 5 presents discussion of results and some conclusions. 2. Description of the HARQ-EC System 1The assumption of noiseless feedback does not reduce the generality o f the analysis, as we are interested in the performance comparison o f HARQ-EC and HARQ-II system in the same conditions. HARQ-EC scheme uses the outer (n,k) code C2 with L. GOLDFELD ET AL. 620 minimal Hamming distance and the inner (2k,k) half-rate invertible code [2] C1 with minimal Hamming distance . 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 transmit- ted 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 CW2(D,Q), where Q denotes the vector of n–k par- ity-check bits. In parallel the transmitter computes k bits of the parity-check block P(D) of the half rate invertible (2k,k) code C1. The block P(D) is not transmitted and is stored in the buffer for later use. 2 H d 1 H d Let CW2(Dr ,Qr) denotes the received vector if CW2(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 Maxi- mum Likelihood Demodulator (SDMLD), FEC and Er- rors Erasure Correction (EEC) decoders for the outer and inner codes respectively. In SDMLD the decision r l A about symbol Al is obtained according to the following rule [7]: if max where,1, 2,.., Erasureif max ik k ii r l k k ii A andthri kM A and thr (1) where Λi is the log-likelihood ratio calculated for the i-th symbol, M is 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 in the code word is zero, the received vector feeds the outer code of the FEC de- coder and after error correction the restored message Dr is sent to the user. If t, 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 C2, it is considered as the transmitted codeword and the message Dr is sent to the user. Other- wise, 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 C1 into the n-length codeword CW2(P(D),Q(p)) of the code C2 where Q(p)denotes the n–k parity-check digits for P(D). 2 er t 0 2 er Let CW2(Pr(D),Qr (p)) denotes the received vector cor- responding to CW2(P(D),Q(p)). The SDMLD, according to (1), erases its unreliable symbols. If the number of the erasures in CW2(Pr(D),Qr (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 Pr(D). by inversion and is sent to the user. Otherwise, the received vector is passed to the EECD of the outer code. If vector CW2(Pr(D),Qr (p))is identified by the EECD, the message D is recovered with the help of inversion of Pr(D). The message Dr that is stored in the receiver memory (after recovery of D from Pr(D)) is then discarded. If the combination CW2(Pr(D),Qr (p)) is not identified by the EECD of the outer code, the received parity block Pr(D) is integrated with Dr kept in the buffer. The code word CW1(Dr,Pr(D)) of the code C1 with 2 er t 1 er t 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 C1 then it is consid- ered 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 Pr(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 CW2(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 , 11 k NC EN k TE EV n BER P (2) 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 expecta- tions of V and N respectively, and PNC 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 PNC may be written as ll crd erd l erd NC ll erd crd k TEP P n P P PP (3) where l crd P and l erd P are probabilities of correct and rroneous reception of the data block, respectively, at the e Copyright © 2009 SciRes. IJCNS L. GOLDFELD ET AL. Copyright © 2009 SciRes. IJCNS 621 Data Source Inner Encoding Control Symbol Memorize Outer Encoding Erasure of "unreliable" symbols Ner>0 FEC of CW2 Recovery of CW2 Information Symbols Memorize Control Symbol Memorize Outer Encoding Erasure of "unreliable" symbols Ner>0 FEC of CW2 Recovery of CW2 Creating of CW1 Ner>0 FEC of CW1 Recovery of CW1 Output Retransmission of Data Block Transmission of following Data Block Step I of Transmission Step I of Reception No CW2 (D, Q) D P(D) Dr Successful Recovery Yes Yes No NAK 1 Step II of Transmission P(D) CW2 (P(D), Q)No Yes Successful Recovery Yes No P(D) b CW1 (D, P(D))No Successful Recovery Yes No NAK2 Step II of Reception Step III of Reception Figure 1. Transmission and retransmission procedures in HARQ-EC. l-th2 start of the procedure described above (see Figure 1). symbol time duration T is represented by Re exp mm c s tAgtmTj t (4) We analyze performance of HARQ-EC for the case of a binary modulation. The transmitted signal within one where Am is the information symbol, g(t) is the impulse response of the transmitter filter and wc is the carrier frequency3. As was mentioned earlier, we consider the case of the forward channel with additive white Gaussian noise and flat fading with Nakagami distribution [8] 2The index l will be omitted as the statistics of errors and erases in the received codeword do not depend on l. 3The 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-II systems in the same conditions. L. GOLDFELD ET AL. 622 2 21 2 00 2exp m m ch mm fm2 (5) where is the gamma function, m 22 0 E, and m ≥0.5 is the fading depth parameter4. Moreover, it is as- sumed that fading is slow, which means that μch may be considered constant, at least for one symbol interval T. The signal xm(t) is demodulated by SDMLD which in- cludes a Log-Likelihood Ratio (LLR) estimator followed by a Decision Device with Eraser (DDE) [1]. The output of LLR is 2112 qq , where T imi idttstxq 0 2,1, for coherent SDMLD and 2,1, 22 iYXq iii for noncoherent SDMLD. Here dttstxX T imi 0 , , ˆ 0 T imidttstxY ts ˆi is the Hilbert transform of si(t), and T is the symbol duration. The vector Λcw=[Λ1, Λ2,…Λl…, Λn] is passed to DDE which produces a version of the outer code word. The elements of the received vector are obtained ac- cording decision rule (1), which in our case can be writ- ten as r C2 1if 0if erase if 1 l r l l l thr Athr thr thr (6 ) Using (6) and results of BER analysis for binary or- thogonal set of signals [1] probabilities of symbol error Pe and symbol erasure Pers are written as (see Appendix A) 0 11 exp1 111 m em mthr thr p thr mthr m (7) 0 0 1 11 11 11 exp1 111 m m ers m m m mthr p thr mthr mthrthr m thr mthr (8) where 0 2 0 2 0NEE s and Es 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 123 11 12 11 crdrq rq crd crdcrd erdrq rq erd erderd PPPPPP PPPPPP 3 (9) where 22 22 1 22 1 22 2 12 ,, ,, FEC RC crr rcrr r crd FEC RC err rerr r erd rqer H PPCWDQ PCWDQ PPCWDQ PCWDQ PPt d , , (10) are probabilities of correct decoding, erroneous decoding and request of the code word CW2(Dr,Qr) respectively, at the first stage of transmission, 2 2 2 2 2 2 2 2 2 2 , , , , FEC p crr r crd RC p crr r FEC p err r erd RC p err r PP CWPDQ PCWPDQ PP CWPDQ PCWPDQ (11) are probabilities of correct decoding and erroneous de- coding of the codeword CW2(Dr,Qr) respectively, at the second stage of transmission, 1 1 1 1 3 1 1 3 1 1 , , , , FEC crr r crd RC crr r FEC err r erd RC err r PP CWDPD PCWDPD PP CWDPD PCWDPD (12) are probabilities of correct and erroneous decoding, re- spectively, of the code word CW1(Dr,Pr(D)), which is created from the block of data Dr extracted from the re- ceiver memory and the parity block Pr(D) of the inner code received at the second stage of transmission. Here j FEC cr P, j FEC er P are probabilities of correct and errone- ous reception of code words at the output of the FEC decoders, and j RC cr P, j are probabilities of cor- rect 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 respective RC er P ly. Bearing in mind the assumptions made above on the statistical properties of the channel, we consider that er- rors, as well as erasures in the received stream of code 4The Nakagami pdf includes, as a special case, the Rayleigh pdf fo r 1m, and can approximate both the Rice and log-normal pdf’s [8]. Copyright © 2009 SciRes. IJCNS L. GOLDFELD ET AL. 623 symbols, are independent. In this case probabilities j FEC cr P, j FEC er P, j RC cr P, j RC er P and for the outer and inner codes can be determined (Appendix B) with the help of the following expressions: j rq P 0 1 1 11, 11, 1, 1 crjj jjj jj jjj crj jj j Hj Hjjer jjer jj erj erj erj erd j tn FEC nni i crerse e i i nn FEC nni i ererse e i it nnni ji rqers ers i id dnt RC nt crers ers t t t t ppp Pp pp Ppp Ppp 0 0 1 1 1 1 1, erj erd er erd jjj jj erd j Hjjer jjer jj erj erj er er jjerd ererd jjj jj erd j erd j t ttt erserser erd t dnt RC nt erers ers t t ttttt erserser erd t t pp Pcrtt Ppp pp Pertt , (13) where 0.5 1 0 0.5 1 ,1 ,1 Herd jj jer j jer j jj jer jjerj jer j jj Herd jj dt nt nt i i er erdee i i nt nt nt i i er erdee i idt Pcrttpp Perttpp (14) nj is the length of code word, is the minimum Hamming distance of the used code, j H d erj t is a number of codeword symbols erased in the SDMLD, and j erd t is the number of the erased symbols taken from those that determine the Hamming distance of the original code jjererd tt0. 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 γ0 and on the threshold thr. 4. Comparison of HARQ-EC and HARQ-II Performance In this Section, we compare the theoretical results ob- tained above for HARQ-EC with those obtained by computer simulation. Then we will compare the per- formance of HARQ-EC to that of HARQ-II schemes [2, 4,5] for the same inner and outer codes5. The systematic linear block code with parameters n2=15, k=11 and is used as the outer code C2, and the half in- vertible code with n1=22, k=11 and is used as the inner code C1. 3 2 H d 7 1 H d 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-II 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. Figure 2. Average BER of HARQ-EC2 as a function of the average SNR (for the threshold values thr=1.5, thr=2, and thr=3); analytical calculation and computer simulation. Figure 3. Throughput efficiency of HARQ-EC2 as a func- tion of average SNR (for the threshold values thr=1.5, thr=2, and thr=3); analytical calculation and computer simulation. 5The 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 p erformance to HAR Q -II s y stems in the same conditions. Copyright © 2009 SciRes. IJCNS L. GOLDFELD ET AL. Copyright © 2009 SciRes. IJCNS 624 Figure 4. Average BER of HARQ-EC and HARQ-II sys- tems as functions of average SNR. Figure 5. Throughput efficiency of HARQ-EC and HARQ– II systems as functions of average SNR. 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 av- erage SNR. 5. Conclusions We propose the Hybrid ARQ system with erasure of un- reliable 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 fad- ing, while the calculations and simulation were per- formed 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-II over a wide range of average SNR when the same codes are used. 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-II Hybrid ARQ system and its performance analy- sis,” 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-II 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 per- formance 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 thresh- old decoding schemes,” IEICE Trans. Fundamentals, Vol. E76-A, pp. 820–827, 1993. L. GOLDFELD ET AL. 625 Appendix A Let us assume that symbol “1” was transmitted. The probability of correct reception Pcr in SDMLD can be found as the probability that Λi>thr, and the probability of symbol erasure Pers in SDMLD, in turn, can be ob- tained as the probability that thr th r i 1. From (6) we obtain. , 1 cr i ers i ppthr p pt thr hr (A1) where (see [1]) 1 2 1 22 ; 2 i j S U U UEeN UN 1 (A2 ) N1 and N2 are complex-valued Gaussian random vari- ables with zero mean and variance σ2=2μEs, U1 and U2 are mutually independent variables with distributions [1] 222 11 1 00 2 22 2 00 4 exp , 24 pUexp. 24 S SS SS UUEU pU I ENEN N UU EN EN 1 0 0 (A3) Taking into account (A1), (A2) we obtain 1 1 1 12 122 00 2 12 122 0 ; cr Uthr ers Uthr Uthr ppUthrU 1 1 p UpUdUd U ppUthrU thr pUpUdU dU U (A4) With the help of elementary algebra and tabulated in- tegrals 1 1exp exp 1 cr thr thr pthrthr thr 1 (A5) 1 exp exp 11 11 expexp 11 ers thr thr pthr thr thr thr thr thr thr ( A6) where 2 0 S E N (A7) Taking into account that erscre ppp 1 we have 11 exp exp 11 e thr thr pthr thr (A8) Probabilities (A6) and (A8) are conditional probabilities of erasure and error reception in SDMLD respectively, given μ and therefore Pe and Per are 0 0 , , er ers ee Pp fd Pp fd (A9 ) where f(μ) is defined by (5). Appendix B Let us determine probability of request Prq, probabilities of correct and erroneous reception of a code word at the output of the ECE decoder ( and ), and also at the output of the FEC decoder ( and RC cr P RC er P FEC cr P FEC er P) under the following conditions: 1) The code used is a linear block code (n,k) with the minimal Hamming distance dH; 2) The encoded bit stream is represented by a code- word CW with length n, supplied from the SDMLD out- put 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 and FEC cr P FEC er P. Since symbol errors are independent events, the binomial law determines probabilities of correct and erroneous recep- tion 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 ter=0, we thus obtain 0 1 11 11 cr cr tn nn FEC i crerse e i i nn nn FEC i erersee i it Pppp Pp pp i i (B1) Copyright © 2009 SciRes. IJCNS L. GOLDFELD ET AL. Copyright © 2009 SciRes. IJCNS 626 where tcr is the number of correct errors per codeword. Probabilities of correct and erroneous reception of a code word at the output of ECE decoder depend on the random variables ter and terd, i.e. they have to be consid- ered as conditional probabilities P(cr/ter,terd) and P(er/ter ,terd) written as Probabilities rq P , RC cr P and RC er P may be ob- tained as follows. The ECE decoding is used when ter>0, where ter is a number of the erased symbols in the re- ceived code word. The erasure of ter symbols from n cre- ates a new shorter code with code word length n(sh)=n–ter and the Hamming distance erdH sh Htdd , where terd is the number of erased symbols taken from those ones that determine dH of the original code (0≤terd≤ter). Since symbol erasures are independent, the probability of the erasure of ter symbols from n as well as probability of the erasure of terd symbols from dH are determined by the binomial law. Taking this into account, we obtain Prq as 0.5 1 0 0.51 ,1 ,1 erd er er er erer erd dt nt nt i i er erdee i i nt nt nt i i er erdee i idt Pcrt tpp Pert tpp (B3) Twice averaging (B3) by the binomially distributed ter and terd, we obtain the unconditional probabilities RC cr P and RC er P (see 13). 1 er er er er H nnnt t rqer Hersers t td PPtdpp (B2) |