MULTIPLE COPY COMBINING SCHEMES FOR THEADDITIVE WHITE GAUSSIAN NOISE CHANNELbyCARSON Y. H. LAMB.Eng. (Electronic and Communication Engineering),University of Bath, U.K., 1990A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF ELECTRICAL ENGINEERINGWe accept this thesis as conformingto the required standard...... ...................... .THE UNIVERSITY OF BRITISH COLUMBIAJuly 1992© Carson Y. H. Lam, 1992In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.Department of Z&CtA 6ILç /LiThe University of British ColumbiaVancouver, CanadaDate________________DE-6 (2/88)AbstractA generalized version of a memory automatic repeat request (ARQ) scheme[15-221 using hard, soft, and completely soft detection is examined. The communicationchannel is modeled as an additive white Gaussian noise (AWGN) channel. The followingsix combining schemes are considered. In Scheme 1, error detection is performed on eachof the n received copies. In Scheme 2, all n copies are combined and error detection isperformed on the resulting packet. Scheme 3 uses Scheme 1 followed by Scheme 2 (ifdecoding using Scheme 1 is not successful). In Scheme 4, each incoming packet iscombined with the copies received so far, and the resulting combined packet is checkedfor errors. Scheme 5 uses Schemes 1 followed by Scheme 4. The last scheme, Scheme6, attempts decoding on up to all 2’- I possible combinations of the received copies.For an arbitrary detector quantization, analytic expressions for the retransmissionprobability, F’ of Scheme 3 are derived, and numerical procedures for evaluating the Fof Schemes 4, 5 and 6 are described. Numerical examples showing the dependence of Fon various parameters, such as the signal to noise ratio (SNR), number of transmissions n,number of quantization levels M and packet length L are given. Although Scheme 6 hasthe lowest F’ its decoding complexity increases exponentially with n.The six combining schemes are applied to the Weldon ARQ scheme [13,14,221. Itis found that the throughput T is generally improved using multiple copy combiningschemes. The throughput can be further increased by using a soft detector. For blockerror rates BKER > 0.5 and soft detectors, the throughputs of Schemes 2 to 6 aretypically higher than that of an ideal selective repeat ARQ system with no packetcombining. In general, Scheme 3 appears to be a good choice among all the six schemeswith a good performance and a simple decoder structure.IITable of ContentsAbstract.iiList of Figures vList of Tables viiiAcknowledgment ixChapter 1 Introduction 11.1 Conventional ARQ Schemes 11.1.1 Stop-and-Wait ARQ 11.1.2 Go-back-NARQ 21.1.3 Selective Repeat ARQ 41.2 An Improved Selective Repeat ARQ Strategy 51.3 Memory ARQ 61.3.1 Combining Schemes 71.3.2 Detection Methods 81.4 Organization of thesis 9Chapter 2 Analysis of Retransmission Probabilities 102.1 Hard Decision Schemes 132.1.1 Scheme 1H 142.1.2 Scheme2H 152.1.3 Scheme3H 162.1.4 Scheme4Hand5H 182.1.5 Scheme6H 222.1.6 Comparison of hard detection schemes 242.2 Completely Soft Decision Schemes 262.1.1 SchemeiP 262.2.2 Scheme2P 27ifi2.2.3 Scheme3P .272.2.4 Schemes 4P, 5P and 6P 302.2.5 Comparison of completely soft detection schemes 332.3 Soft Decision Schemes 342.3.1 Scheme iS 372.3.2 Scheme 2S 372.3.3 Scheme3S 382.3.4 Schenes 4S and 55 442.3.5 Scheme 65 482.3.6 Comparison of soft detection schemes 502.4 Effect of packet length L 52Chapter 3 Throughput Analysis and Simulations 55Chapter 4 Conclusions 63References 65Appendix A Determination of Optimum Values of {n1 } 68Appendix B Numerical Procedures for evaluating Pc(n,m) 69Appendix C Optimum Thresholds for Soft Decoders 71Appendix D Asymptotic Behaviour of Retransmission Probabilityfor Schemes 1H, 2H and 3H 72D.i SchemelH 72D.2 Scheme2H 72D.3 Scheme3H 74ivList of FiguresFigure 1.1 Stop-and-wait ARQ 2Figure 1.2 Go-back-N ARQ 3Figure 1.3 Selective Repeat ARQ 4Figure 2.1 Block diagram of the memory ARQ system (adapted from [18]) 10Figure 2.2 Weights and Thresholds distribution 11Figure 2.3 Probability Distribution function of Y3, 13Figure 2.4 Retransmission probability for Scheme 1H (n = l,2,...,7, L = 500) 14Figure 2.5 Retransmission probability for Scheme 2H (n = 1,3,5,7, L = 500) 16Figure 2.6 Retransmission probability for Scheme 3H (n = l,2,...,6, L = 500) 18Figure 2.7 Retransmission probability for Scheme 4H (n = 1,2,...,6, L = 500) 21Figure 2.8 Retransmission probability for Scheme 5H (n = l,2,...,6, L = 500) 21Figure 2.9 Retransmission probability for Scheme 6H (n = 1,2,3,4, L = 500) 23Figure 2.10 Retransmission probabilities for Schemes 1H to 6H (n = 2, L = 500) 25Figure 2.11 Retransmission probabilities for Schemes 1H to 6H (n = 3, L = 500) 25Figure 2.12 Retransmission probabilities for Schemes 1H to 6H (n = 4, L = 500) 26Figure 2.13 Retransmission probabilities for Schemes 2H to 6H and 2P to 6P(n=3,L=500) 33Figure 2.14 The weights and thresholds associated with the 2M regions 34Figure 2.15 DMC resulting from quantizing the receiver matched filteroutput into 2M regions (adapted from [18]) 35Figure 2.16 Retransmission probability for Scheme 3S with varying threshold value(M=2,n=3,4,L=500) 37Figure 2.17 Retransmission probability for Scheme 2S(M= l,..,5,n=4,L= 500) 39VFigure 2.18 Retransmission probability for Scheme 2S(M=3,n= 1,...,6,L= 500) 39Figure 2.19 Tree diagram form = 2 andM = 3 42Figure 2.20 Retransmission probability for Scheme 3S(M=1,..,5,n=4,L=500) 43Figure 2.21 Retransmission probability for Scheme 3S(M=3,n= 1,...,5,L=500) 43Figure 2.22 Retransmission probability for Scheme 4S(M= l,..,5,n=4,L=500) 46Figure 2.23 Retransmission probability for Scheme 4S(M=3,n= 1,...,5,Lz-_500) 46Figure 2.24 Retransmission probability for Scheme 5S(M= 1,..,5,n=4,L=500) 47Figure 2.25 Retransmission probability for Scheme 5S(M=3,n= 1,...,4,L=500) 47Figure 2.26 Retransmission probability for Scheme 6S(M= 1,..,5,n=3,L=500) 49Figure 2.27 Retransmission probability for Scheme 6S(M=3,n= 1,...,4,L=500) 50Figure 2.28 Retransmission probabilities for Schemes iS to 6S(M=2,n=3,L500) 51Figure 2.29 Retransmission probabilities for Schemes 15 to 6S(M=3,n=3,L=500) 51Figure 2.30 Retransmission probabilities for Schemes 2H to 6H and 2S to 6S (M = 3)with n = 4, L = 500 52Figure 2.31 Retransmission probabilities for Schemes 1H to 6H against L(n=3,M=1,SNR=8dB) 53Figure 2.32 Retransmission probabilities for Schemes iS to 6S against L(n=3,M=3,SNR=8dB) 53Figure 2.33 Retransmission probabilities for Schemes 15 to 6S againstL(n=4,M=3,SNR=8dB) 54Figure 3.1 Throughput for Scheme 2S(M= i,2,3,4,L=500,q=1,S = 1000) 59Figure 3.2 Throughput for Scheme 3S(M= 1,2,3,4,L=500,q=1,S = 1000) 59Figure 3.3 Throughput for Scheme 4S(M= i,2,3,L=500,q=1,S = 1000) 60Figure 3.4 Throughput for Scheme 5S(M= 1,2,3,L=500,q=1,S =1000) 60Figure 3.5 Throughputs for Schemes 1H to 5H(M= 1,L=500,q=1,S = 1000) 61Figure 3.6 Throughputs for Schemes 15 to 5S(M=2,L=500,q=1,S=1000) 61Figure 3.7 Throughputs for Schemes iS to 5S(M=3,L=500,q=1,S=1000) 62Figure 3.8 Simulated Throughputs for Schemes 3H and 6H(L = 500, q = 1, S = 1000) 62viiList of TablesTable 1.1 Summary of the six combining schemes 8Table 2.1 Optimum Thresholds (Normalized to A) and weightsforM = 2,...,5 , SNR = 8 dB, and n = 5 (adapted from [181) 36Table 3.1 Optimum number of copies for Schemes 1H to 6H withq=1,S —l000,L=500 57Table 3.2 Optimum number of copies for Schemes 2S to 5S withM=2,q=l,S=1000,L=500 57Table 3.3 Optimum number of copies for Schemes 2S to 5S withM—_3,q=1,S =1000,L=500 58Table 3.4 Optimum number of copies (simulated) for Scheme 6H withq=1,S =1000,L=500 58wilAcknowledgmentI would like to thank Dr. Cyril Leung for his supervision and enlightening teachingand advice. I also thank my colleagues Richard Cam, S.W. To, Kenneth Wong andVictor Wong for their helpful support during the year. This work was partially supportedby NSERC Grant 0GP0001731.xChapter 1 Introduction1.1 Conventional ARQ SchemesIn order to transmit messages reliably in a data communication system, errorcontrol strategies have to be used [1-22]. In many systems, data are sent as a sequence ofpackets of fixed size. The packets are to be delivered to the destination in the same orderin which they were sent. During transmission over the channel, noise is introduced; thisresults in bits of the received packets being possibly altered. To achieve transmissionintegrity, the receiver should be able to detect these bit errors. Typically, a cyclicredundancy check (CRC) code is used [23,24].If no error is detected in a data packet, the receiver sends back a positiveacknowledgment (ACK). Conversely if errors are detected, a negative acknowledgment(NACK) is returned to the transmitter. The transmitter wifi retransmit the packets thatwere negatively acknowledged or have not been acknowledged after a predetermined timeinterval. Such error control schemes are referred to as automatic repeat request (ARQ).Many ARQ transmission strategies have been proposed [1-22]; they can be classified as:(1) Stop-and-wait(2) Go-back-N(3) Selective repeat1.1.1 Stop-and-Wait ARQIn Stop-and-Wait ARQ [4,5] (Figure 1.1), the transmitter sends a single packetand then waits for an acknowledgment (ACK). It does not send any other packet until itreceives an ACK or NACK from the receiver or a time-out period expires. If a packeterror is detected by the receiver, it discards the packet and asks for a retransmission bysending a NACK. Upon receiving the NACK, the transmitter re-sends this packet. To1Chapter 1. Introduction 2cope with lost packets, the source is usually equipped with a timer. If there is no response(ACK or NACK) after a certain predetermined period of time, the source will retransmitthe unacknowledged packet again. Hence this system requires the source to store a singlecopy of the transmitted packet.Stop-and-wait ARQ is simple to use, but is often inefficient due to the waiting(idle) times. Instead of waiting for an ACK or NACK, the transmitter could send datapackets continuously; such a scheme is referred to as continuous ARQ.idle time * error N - NACK A - ACKTransmitterReceiverFigure 1.1 Stop-and-wait ARQ1.1.2 Go-back-N ARQOne continuous ARQ scheme is go-back-N (GBN) ARQ [4,7-10). With GBNARQ, it is not required that each individual packet be acknowledged. As shown inFigure 1.2, the transmitted packets from source to sink are numbered sequentially, and thissequence number SN is sent together with the packet. In contrast to stop-and-wait ARQ,successive packets are sent without waiting for the previous packet to be ACK/NACKed.idle timeChapter 1. Introduction 3The destination sends request numbers RN back to the source requesting packet RN andacknowledging all packets prior to RN. The number N in a go-back-N protocol is aparameter that determines how many packets can be outstanding (i.e. sent without beingacknowledged). The performance of GBN ARQ is better than that of stop-and-waitARQ. If an error occurs in packet X, the receiver will send back the sequence number ofX as RN and ignore all incoming packets until a correct copy of X is obtained. Onreceiving RN, the transmitter goes back to the packet numbered RN and re-sends it as wellas all ensuing packets. Hence many error-free packets may have to be retransmitted,leading to inefficiency, especially for long delay channels such as satellite Links. However,there is no buffer requirements at the receiver; at the transmitter a buffer of size N packetsis needed. If buffer space is available at the receiver, the efficiency can be improved byusing a selective-repeat (SR) ARQ scheme.* error N - NACK A - ACKTransmitterReceiverignoredFigure 1.2 Go-back-N ARQ.Chapter 1. Introduction 4TransmitterReceiverFigure 1.3 Selective Repeat ARQ1.1.3 Selective Repeat ARQIn selective repeat (SR) ARQ [1 1,12j as shown in Figure 1.3, the receiver willaccept out-of-order packets and request retransmissions from the source only for thosepackets that contain errors. However, the receiver theoretically requires an infinite bufferin order to rearrange the received packets in correct order before delivery to the user. Thethroughput of the ideal (infmite re-ordering buffer) SR ARQ scheme, T, defmed as theaverage number of packets received correctly per transmitted packet, is given byT = 1— F’ where F is the retransmission probability for a single packet. In practicalsystems, there is a window size which specifies how many outstanding packets areallowed. When this limit is reached, the source can wait for some time out or immediatelystart retransmission of unacknowledged packets. The actual throughput is hence smallerthan 1- F• Although by making the window size large enough, the probability that the* error N- NACK A-ACKChapter]. Introduction 5number of outstanding packets exceeding the window size can be made very small, thereare two difficulties with very large window sizes. The first is that storage must beprovided at the receiver for all of the accepted packets. The second is that a large numberof stored packets may all be delayed waiting for a single incorrect packet.One way to reduce the number of outstanding packets (i.e. the window size) is toretransmit the same packet several times in succession if the previous transmissioncontained errors. A multiple copy retransmission scheme reduces the retransmissionprobability and the delay variations, but is not as efficient. However, the number ofretransmitted copies can be chosen in such a way as to optimize the throughput of thesystem.1.2 An Improved Selective Repeat ARQ StrategyIn 1982, Weldon [13} described an ARQ scheme for which the throughputcompares very favorably with those of previously described schemes. Basically, it is amultiple copy retransmission scheme in which the number of repeats is optimized. In1984, a modification to the Weldon ARQ scheme was proposed in [14j; this allows formultiple copies to be transmitted at the beginning and can improve the throughput Tsignificantly.Let S be the number of data packets which can be sent by continuous transmissionduring the time between the start of the transmission of a packet and the receipt of a ACKor NACK for that packet. In the Weldon ARQ scheme, the receiver buffer size is qS,where q is a positive integer. When q = 0, it becomes a GBN ARQ scheme. Each datapacket F is transmitted as follows:Initially, F is at level 0 and is transmitted for the first time. If an ACK is received (Spacket times later), the transmission of F is complete. If a NACK is received, F moves tolevel].Chapter 1. Introduction 6Level]: F is repeated n1 times. If any of these n1 copies is ACKed, the transmissionof F is complete. If all n1 copies are NACKecI, F moves to level 2.Level 2: F is repeated n2 times. If any of these n2 copies is ACKed, the transmissionofF is complete. If alln2copies are NACKed, F moves to level 3.This procedure is continued until level q is reached.Level q: - At this point the receiver buffer is considered full even though it may notactually be full because of repeats of other erroneous packets. Thisassumption leads to a simple analysis. Here F is repeated flq times. If all flqcopies are NACKed, F moves to level q + 1.Level q+]: Buffer overflow occurs, leading to the loss of (S - 1) packets. F is repeatednq times and stays at this level until it is successfully received.Let [3 = lIT be the average number of transmissions required to send one packetsuccessfully. From [14] we haveqi—iq k=Ok (nq+S_i)Pj.°+i=0 lPf (1.1)For given values of q, S and F’ the number of copies to be sent {n1} can bechosen so as to minimize [3or equivalently maximize T. In [14], a detailed analysis for theoptimum values of } is given and is reproduced in Appendix A for reference.1.3 Memory ARQIn the above mentioned ARQ schemes, a data packet is discarded if it is found tocontain errors. This is so even if only a few bits in the data packet are corrupted.In memory ARQ systems [15-22], the receiver does not discard erroneous packets.A weight is associated with each demodulated bit in each packet received. By combiningcopies of received packets bit by bit, the retransmission probability F can be reduced.Chapter 1. Introduction 7These combining schemes would typically be used in an ARQ scheme in which a number,n, of copies are sent either initially or in response to a repeat-request, such as the WeldonARQ scheme [13,14,22].1.3.1 Combining SchemesIn this thesis, we consider the following six combining schemes. In Scheme 1,error detection is performed on each of the n individual received copies. if one or morecopy is correct, transmission of the packet is successful. In the event that all n copies areerroneous, we have a decoding failure and retransmission is required. In Scheme 2, all ncopies are combined to a single one by using hard or soft detection and error detection isthen performed on the combined packet. Decoding failure results if this combined packetis found to be erroneous.By implementing both Scheme 1 and Scheme 2, we obtain Scheme 3. In Scheme3, error detection is performed on the n individual copies first. If all copies contains errorsthe n packets are combined into one and error detection is performed on it. Decodingfailure results if all the n packets and the combined packet are erroneous.In Scheme 4, each newly arrived packet is combined with all the previouslyreceived packets. The first received and the following (n - 1) combined packets arechecked in turn for errors. Decoding failure results if the first packet and all the combinedpackets are erroneous. Scheme 5 uses both Scheme 1 and 4. When a new copy arrivesand is found to be erroneous, it is combined with the copies received so far and errordetection is performed on the new combined packet. Decoding failure results if all the npackets and the (n - 1) combined packets are erroneous.Finally in Scheme 6, error detection is performed on all 2” —1 possiblecombinations of the received packets. Therefore, it has the lowest retransmissionprobability among all the schemes described so far. The six schemes are summarized inTable 1.1.Chapter 1. Introduction 8Schemes Perform Decoding on1 n Individual copies2 Single sum of n copies3 Scheme 1 + Scheme 24 Sumsofl&2,1&2&3,andsoon5 Scheme 1 + Scheme 46 All the 21z +1 combinations of the packetsTable 1.1 Sununary of the six combining schemesIt is assumed in this thesis that no packets are lost during transmission so thatcombining of all copies is possible.1.3.2 Detection MethodsThe receiver can use either a hard-decision or soft-decision demodulator. Thehard-decision demodulator makes a hard estimate on the received signal. A 1+1? isassigned if the amplitude of the received signal is positive; otherwise, a ‘-1’ is assigned.The subscripts represent the jth transmission of the ith bit in a packet. In the soft-decisiondemodulator, a reliability weight is assigned to each received bit depending on thequantization region the received signal amplitude falls into. Theoretically, the finer thequantization regions of the system, the better the performance will be, albeit at the cost ofincreased decoder complexity. A system with infinitely fine quantization levels is referredto as completely soft or perfectly quantized. In this case, the decoder can use the exactvalue of the received signal amplitude for combining purposes.The six combining schemes have been previously considered by a number ofauthors. Scheme 2 is used with n = 5 and single error correction for data transmission inChapter]. Introduction 9the AMPS system [15]. Scheme 5 has been suggested by Sindhu in [16], and later on,with soft-decision decoding by Beneffi [17]. Soft-decision decoding is generalized andoptimized in [18], which in particular, showed a numerical procedure for evaluating F ofScheme 4. The retransmission probability of Scheme 5 was analyzed to a limited extent in[20], which gives an expression for n = 2 only. A lower bound on the F of Scheme 6was given in [21].1.4 Organization of thesisIn this thesis, we will consider the application of all six combining schemes in anARQ system. The Weldon ARQ scheme is of special interest since it uses a multiple copytransmission strategy. In chapter 2, we consider the retransmission probability F of thecombining schemes using hard, soft and perfectly quantized detection methods. Analyticexpressions for the F of Schemes 1 and 2 for hard detection can be easily obtained, whilethe F for soft detection of Scheme 2 was derived in [18]. Here, new expressions for Fof Scheme 3 for hard, soft and perfectly quantized detectors are derived. Analyticexpressions for the F of Schemes 4 to 6 appear to be difficult to obtain. Instead,numerical procedures for evaluating them are described. We then compare the resultingthroughputs after applying the six combining schemes to the Weldon ARQ scheme inchapter 3 with the throughput of Scheme 6 found by simulation. Finally, the main resultsof the thesis and some suggestions for future development are included in chapter 4.Chapter 2 Analysis of RetransmissionProbabilitiesIn this chapter, the retransmission probabilities F for a number of differentcombining and detection methods are analyzed.Consider an L-bit data packet transmitted over an additive white Gaussian noise(AWGN) channel using binary PSK modulation with the system model used in [18] asshown in Figure 2.1. It is assumed that no errors occur in the feedback channel. Forsimplicity, it is also assumed that the error detecting code used is able to detect all channelerror patterns; this is not an unreasonable assumption in practice [26]. The transmitteroperates as in a conventional ARQ system. Every transmitted data packet is stored untilan ACK signal is received. Suppose that the data packet to be transmitted is denoted by(SI,S2,...,SL) where Si e{O,i}, i=l,2,...,L. Then the input to the vector channel isX=(Xl,X,..., L) where:Figure 2.1 Block diagram of the memory ARQ system (adapted from [18])10Chapter 2. Analysis ofReransmission Probabilities 11-TM1 -T2 -7 0 7j T TM1—RM —R2 R1 R2 RWM W2 —WI W1 W2 WMFigure 2.2 Weights and Thresholds distribution.(A ifs1=1= —A S =0 (2.1)At the receiver, the output of the matched filter y corresponding to the jthtransmission of x is (Yj,i Yj,2 i... Yj,L) where = x1 + d1, and fd1 }, I i L,j = 1,2,... represent independent Gaussian noise samples with variance a2 Each y11 isthen assigned a reliability weight according to equation (2.2) and is also shown inFigure 2.2.+WM y1, > TM_IT2y,1>T—y,>Owi,1——w1—T1 > —T2WM —TM_I > ‘i,1 (2.2)where there are 2M weights f—wp..j ,WM_1 ,WM } and 2M -1 thresholdsf—TM_i ,—TM_2 ,... ,0,T1 ,. ..,TM_i}. For M = 1, the output of the matched filter isquantized into two regions only, resulting in a hard decision demodulator. If the numberChapter 2. Analysis ofRetransmission Probabilities 12of quantization regions exceeds two, that is M > 1, the demodulator is a soft decisiondemodulator. A completely soft decision demodulator is one in which the matched filteroutput is perfectly quantized (infinite number of quantization regions).With weights assigned to each received sample YJA’ the L-bit packet can berepresented by the vector w = ,w,... ,wJL) which is used in the reliabilityupdating process. Here a decision accumulator z1, I I L, is maintained for each bit inthe data packet. Prior to the reception of a packet, we set = 0, 1 I L. After thejthreception of the data packet, the accumulators are updated according to= Zj_1,j + (2.3)The inputs to the decoder u and v are determined from11 ify1Ouj,i— 0 if <0 (2.4)and_11 ifz,O— 0 if z1, <0 (2.5)In the case that zj1 = 0, is set to either ?1? or ‘0’ completely at random. Theabove configuration is applicable for Scheme 1 to 5. For Scheme 6, the modification is asfollows: the decision accumulator updating block in Figure 2.1 is not required; instead,storage is required to store all the received copies at any stage. Packet combining (allpossible combinations) and decoding for the combined packets are performed whenever anew copy of the packet arrives. Hence it has to perform 2 — 1 packet combining anddecoding when I copies of the packet are received, while Scheme 5 has to perform a singlecombining and 2 decoding processes only for each newly received copy. Henceimplementing Scheme 6 requires a much larger computational effort than all the otherschemes, especially when j becomes large.Chapter 2. Analysis ofRetransmission Probabilities 132.1 Hard Decision SchemesLet P11 denote the retransmission probability for Scheme iH, I = 1,.. .6, where Hindicates the use of hard detection with PSK modulation and an AWGN channel. Theprobability distribution function (pdf) of Y when a ‘1’ has been sent and the pdf of Y11when a ‘0 has been sent are shown in Figure 2.3. If a 1? was sent, the probability thatY,1 <0 is given byPrfr1 <01 t , was sent} Q(J (2.6)which is equal to Pr{Yj1 o’ c’ was sent} = p’ the bit error rate (BER) of the channel.The function, Q(a) [25] is defined asIe2dxa•(2.7)pdfPIIO (y,) p11,i(y)-A 0 A yFigure 2.3 Probability Distribution function of Yjj.Chapter 2. Analysis ofRetransmission Probabilities 142.1.1 Scheme 1HThe retransmission probability for Scheme 1H is given byP111 = Pr fall n packets are hard detected incorrectly}= [Prfa packet is hard detected incorrectly}]?Z= [i — Pr{a packet is hard detected correctly}j’1= [i — Pr fall L bits of a packet are correct}]’7=[i_(i_p)UJZ(2.8)A plot of 1H against the signal to noise ratio (SNR) in dB defined as201og10(A/) for n = l,2,...,7 and L = 500 is given in Figure 2.4. For a given SNR, 1Hdecreases with the number of copies as to be expected and it is shown in Appendix D thatP111 decreases as p’2 for p << 1. To achieve a retransmission probability of forn = 4, Scheme IH requires an SNR of approximately 10.6 dB.n=7 — - — -n=6 — — —n=5-ii=4n=3n=2-n=1010ic-210I ‘N’S”\\ N•7 S 9SNR (dB)10 11Figure 2.4 Retransmission probability for Scheme 1H (n = 1,2 7, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 152.1.2 Scheme 2HThe retransmission probability for Scheme 2H is given by‘211 = Pr{the combined packet is hard detected incorrectly }= 1 — Pr{the combined packet is hard detected correctly}= 1 —[Pr{a bit of the combined packet is hard detected correctly}}’= 1 — [i— Prfa bit of the combined packet is hard detected incorrectly }]L(2.9)where Pj(n,p,m) is the probability of incorrect majority-vote decoding on n bits withbit error rate p, given that rn of the n bits are known to be correct and the remaining(n — rn) bits may or may not be correct. For Scheme 2H, since none of the n bits is knownto be correct, the value of rn is 0. For n odd, P,1(n,p,rn) is given byfn+1(n, p,rn) = Pr12or more errors in n — m unknown bits=n+1(2.lOa)Similarly for n even, we haven-rn n—rn ..n—rn .P,(n,p,m)= [ J(1_)n_m_i n/2 ]P21 —p)m(2.lOb)where the last term on the R.H.S. of (2.lOb) accounts for the event of an equal number ofcorrect and incorrect bits. In such a case, the decoder breaks the tie based on the outcomeof a fair coin toss. Also note that (n, p,rn) = 0 when rn > - for even n or rn> 1for odd n.Chapter 2. Analysis ofRetransmission Probabilities 16010 — --.. ———-1 —.-.- .-....-.-10..10 ‘ ...•....-310o.410 N,o..1 \-7 n=7 — - — - \10-4 n=3 \10 - n=1I I I I I I I I0 1 2 3 4 5 6 7 8 9 10SNR (dB)Figure 2.5 Retransmission probability for Scheme 2H (n = 1,3,5,7, L = 500)A plot of 2H against SNR for n = 1,3,5,7 is given in Figure 2.5. In Appendix D,In+1Iit is shown for r’ << l “211 decreases as L 2 In fact, as shown in Figure 2.5, p211the same for n = 21 - 1 and 21 where / = 1,2,3,... [19]. As n increases, 2H decreases asexpected. To achieve a retransmission probability of i0 for n = 4, Scheme 2H requiresan SNR of approximately 10 dB.2.1.3 Scheme 3HFor Scheme 3H, let j 1, 2, ..., n denote the event that the jth copy of thepacket is correct and BH denotes the event that majority voting on the n copies results incorrect packet decoding. ThenP311=1—PrfAA2u...uAuB} (2.11)Chapter 2. Analysis ofRetransmission Probabilities 17By expanding the union of events [25j, we get“3H =1_Pr{A}+ Pr{AA}— Pr{AJAkAl}+...+(—1)’Pr{Al...Afl1j=1 1j<kn 1j<k<ln—Pr{BH } + PrAB } — Pr{AJAkBH }+. Pr{A1A2 A,Bq }j=1 1j<kn(2.12)Since the events {A1}, j = 1,2,. . ., n are independent,Pr{A...}=P {Ai}Pr{A”Prf j}= {PrfAi }]‘—(l—p) (2.13)andPr{AIAZ...AmBH}= Pr{Al}Pr{A2}...Pr{ m}Pr{BHIAIA” m}=[Pr{Ai}]mPr{BHIAIA2...Am}= (1 _p)”[1 — P,j(n,p,m)]’ (2.14)Using (2.13) and (2.14) in (2.12) yields3H= ()L +[)(l_p)2L [J)3L(1)flflJ(1)nL_[i _p(o)]L +n[(1 _p)L[i_.(1)]L]_[;)[(1--P (n,p,2)]L ]+.. - )flL [i - p.()jL]= [i_(1)L]’ +(_1)k+1 j[(i _p)k{i —P, (n,p,k)]]L.(2.15)Chapter 2. Analysis ofRetransmission Probabilities 18010>..-210-3Figure 2.6 Retransmission probability for Scheme 3H (n = 1,2,...,6, L = 500)A plot of 3H against SNR for n = l,2,...,6 is given in Figure 2.6. We observe thatfor values of SNR below 8 dB, 3H are very close for values of n = 21 - 1 and 2/,1 = 1,2,..., and it is shown in Appendix D that for p << has the same behaviour asthat of Scheme 1H and decreases as p’. To achieve a retransmission probability of iOfor n = 4, Scheme 3H requires an SNR of approximately 9.4 dB.2.1.4 Scheme 4H and 5HFor Schemes 4H and 5H, let B’H , j = 1,2,.. .,n denote the event of successfulpacket decoding after majority voting on the first i copies. Then= l-pr{A1UB2HU-..UB,H} (2.16)andSNR(dB)PSH=1—PrfAIUA2U...AflUBHU...UB,7} (2.17)Chapter 2. Analysis ofRetransmission Probabilities 19These expressions can be evaluated by expanding the union of events, as done inthe case of Scheme 3H. The probability of each joint event in the union expansion can beevaluated numerically as follows. Let E12 - Em denote such a joint occurrence(of m events), where E E { A1 , A2 ,. . . , A, , B2H , B311 ,. . . , B, } and denotes the eventthat majority voting on the copies involved in E yields a correct decision at bit position i.Since each E corresponds to the joint occurrence of the independent and equiprobableevents fe1, ,. ..,eJ }, we have Pr{E } = [r{ej }]L, where Pr{ej } = Pr{ej,j } fori = l,2,...,L. Similarly, the joint occurrence of a set of E31scan be written asPr{E1E2...Em}=[Pr{ele.em}]L (2.18)The probability, Pr{e1e2•- em }, can be evaluated by exhaustively enumerating allthe error events in the bits that are relevant to that event and summing the correspondingprobabilities. As an example, consider the eventE1234=A1B3HB4A5for the caseof n = 8 copies. Let and b3H denote respectively the event of A and BJH at aparticular bit position. Define the bit error indicator ij as= f1 if there is no error at a given bit position in packet jO, otherwise. (2.19)Then,Pr{A1B3HB45} = [Pr{a1b3114a5}1L (2.20)wherePr{a1b3114a5}= ± ±±Pr{aib311b4n5ii2} rfi ii1=0i2345O5 51 1 1 1 1 5—si,= p i’=0i2345O (2.21)Chapter 2. Analysis ofRetransmission Probabilities 20The conditional probabilities are given byPr{alb3Hb45Ii ...i5}= Pr{a1Ii...i5}Pr{b3nIii...i5Pr{b4HIil...i5}Pr{a fri(2.22)wherePr{ajlii...i5}= j (2.23)andPr{bJHfrl...i5}= - if0 , otherwise.(2.24)Thus, if the bit error indicators take values i12345= 10101,Pr{alb3Hb45Iili2= ioioi} = lxi x!xi = IPlots of 4H and 5H against SNR for n = l,2,...,6 are given in Figures 2.7 and 2.8respectively. It can be seen that for Schemes 4H and 5H, the relative percentagedifference in retransmission probability for values of n = 21 - i and 21, 1 = 1,2,..., is largerthan that of Scheme 3H. This percentage difference is noticeable even at low values ofSNR. To achieve a retransmission probability of for n = 4, Scheme 4H and 5Hrequire SNR’s of approximately 9.5 dB and 9.1 dB respectively.Chapter 2. Analysis ofRetransmission Probabilities 210105___• - - _ - ._ _- —‘-.5--.-----15-.----- ---5-in ‘--S.--.-- -.5.5-—-- 5s‘-S..-S.. 5.--5- -S.‘---S..-. .55-S-S-2 ‘____5. —-S-10 ‘--.5. ‘555-3 ‘%_._._•..•%.-‘5.,.10 .5%..--I - n=6 — — — \‘\-5 n=5 N10- n4—-—-—-—\•*..0=3n=210 - n=11—j I I I I I I I2 3 4 5 6 7 8 9 10SNR (dB)Figure 2.7 Retransmission probability for Scheme 4H (n = 1,2 6, L = 500)10 —---.—.5----2 _-S%.5_.•.. 555510 .5-.. •‘p -5 S.. ‘.5--3 -S-S. So 10 -S-..4-10-510 _“5f) n=6 — — — s\“•10 -\-.I— n=210 - n=1410 I I I I2 3 4 5 ,6 7 8 9 10SNR(dB)Figure 2.8 Retransmission probability for Scheme 5H (n = 1,2 6, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 222.1.5 Scheme 6HScheme 6H attempts majority-vote decoding on all 2’ —1 possible combinations ofthe n received copies. Let D , k = 1,.. —1, denote the event of successful majority-vote decoding using the copies ‘selectedtby the binary expansion of k as follows. Let thebinary expansion of k be expressed ask = c1 (2.25)where cj E {O,l} , j =Then the jth copy is used in D if and only if c = 1. The retransmissionprobability is given by(2—1 1P6H=l—Pr’ UDWE4,kt4 J (2.26)where the union of events can be expanded, as done in cases of Schemes 3H to 5H. Eachterm in the corresponding union expansion can then be evaluated in a manner similar tothe procedure described for Schemes 4H and 5H. Let d denote the event of D at aparticular bit position and consider the eventD1HD3HD17HD22H for the case of n = 8copies.Pr{D1H37HD22H } = [Pr{dlHd3H l7jj221]’ (2.27)Since the highest value of the subscript in { D } is 22, the number of bit error indicatorsrequired is5 since 2 22<z2.Pr{dlHd3H l7d22J = ±... ± Pr{dlHd3Hdl7Hd22H 1u112131415 pr{ii23i1=O i5=O5 51 1 ij 5—i= 2 pi1=O 15=0(2.28)Chapter 2. Analysis ofRetransmission Probabilities 23The conditional probabilities are given byPrfdlHd3H l7d22‘i-. i5 }= pr{dlH 1• .15 } Pr{d3Hil. . .15 } Pr{dl7HIil. . .15 }Prd22Hjil. . .15 }, (2.29)where5Cj1 if2j=155 cjif c3ij =‘0 , otherwise.(2.30)SNR (dB)Figure 2.9 Retransmission probability for Scheme 6H (n = 1,2,3,4, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 24The computational complexity of the numerical procedure described above growsrapidly with the number of copies (in the order of 22_1). However, as a practical matter,the values of n of most interest are typically small since otherwise the throughput wouldbe unacceptably low.A plot of 6H against SNR for n = 1,2,3 and 4 is given in Figure 2.9. The relativepercentage difference in retransmission probabilities for values of n = 21 - 1 and 21 where1 = 1,2,..., is even larger than that of Scheme 5H. To achieve a retransmissionprobability of i0 for n = 4, Scheme 6H requires an SNR of approximately 8 dB.2.1.6 Comparison of hard detection schemesThe retransmission probabilities of Schemes 1H to 6H are plotted in Figures 2.10,2.11 and 2.12 for n = 2,3 and 4 respectively. From Figure 2.10, it can be seen that forn = 2, 2H is the highest among all the schemes. This is because 2H is the same forn = 1 and n = 2. Besides, PIH, 3H’ 5H and 6H are nearly the same and all of them aresignificantly lower than P4Jf which is slightly lower than 2H itself.From Figure 2.11, the following observations can be made: For n = 3,Schemes 2H to 6H have nearly the same retransmission probability for SNR valuesbelow 8 dB. It was found that P311 is lower than lH 2H and while P611 is thelowest as to be expected. Finally, P511 lies between 3H and 6H•From Figure 2.12, for n = 4, we observe that the relative percentage difference inretransmission probabilities among the schemes is much larger than that for n = 3,especially between Scheme 6H and the others. Besides, P is lower than P311 for SNRabove 9 dB.Although Scheme 6H always has the lowest retransmission probability, thecomputational effort required to implement Scheme 6H is much larger compared withthose for the other schemes as n increases. Hence Scheme 6H is suitable for systems withsmall values of n only.25I6 7 8 9 10 11 12 13 14Chapter 2. Analysis ofRetransmission Probabilities-o10•110-210- 10-410.10-610. .710-8106)10• -1010—11105SNR (dB)Figure 2.10 Retransmission probabilities for Schemes iN to 6H (n = 2, L = 500)010—110-210-310-41015SNR(dB)Figure 2.11 Retransmission probabilities for Schemes 111 to 6H (n = 3, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 26010...a .2-101—’ -3100410I10SNR(dB)Figure 2.12 Retransmission probabilities for Schemes 1H to 6H (n = 4, L = 500)2.2 Completely Soft Decision SchemesLet P1p denote the retransmission probabiitiy for Scheme iP using perfectquantization with i = 1,. ..6, where P indicates the use of perfectly quantized detectors. Inthis case, (2.3) can be written as= z_ + Yp f 1,2,... ,nI = 1,2,... ,L. (2.31)2.1.1 Scheme 1PSince packet combining is not performed in Scheme 1P, the retransmissionprobability for this scheme using perfect quantization will be the same as that using harddetection and is given byiP“IH5 6 7 8 9(2.32)Chapter 2. Analysis ofRetransmission Probabilities 272.2.2 Scheme 2PThe retransmission probability for Scheme 2P is given by= Pr { the combined packet is detected incorrectly }1 — Pr{ the combined packet is detected correctly}= 1 — [Pr{a bit of the combined packet is detected correctly}]Lr 1L=1[P2pJ (2.33)where P2P is the effective bit error probability of the combined packet using perfectquantization. Since Y are Gaussian random variables, Zn_rn,j is also Gaussian. Thevariance of i = 1,2,...,L, is the sum of variances of Y, j = 1,2,...,n, i.e. na2. Themean of Z,,1 is given by nA. Therefore the effective bit error probability is given by(%ThAP2PQIa (2.34)Thus the net effect on the bit error rate of combining the n copies is equivalent tothat of using a signal whose power is n times that of a single copy.2.2.3 Scheme 3PLet B denote the event that completely soft detection on the combined n copiesresults in successful packet decoding. ThenP3p = 1— Pr{A1 U A2 u uA u B } (2.35)By expanding the union of events, we getP3p1_Pr{A}+ Pr{AJAk}— PrfAJAkAI}+...÷(—l)’Pr{Al...Afl}j=1 1j<kn 1j<k<ln— Pr{Bp}+ PrfAB } — Pr{Aj AkBP .+(—iY’ PrfA1A2• . AB}j=1 1j<kn(2.36)Chapter 2. Analysis ofRetransmission Probabilities 28Since each event A1 is independent, Pr{A1A2 • A) is still (1 — . Letting bbe the event of B at a particular bit position, we havePr{A1A2 ABp } = {Pr{aia2 abp}] = [P(nm)]Lwhere P. (n, m) is the probability of successful decoding using a given set of m copies andthe combination of all n packets at a particular bit position. Assuming a packet of all tithas been transmitted, this corresponds to Z,,1 = Y11 + Y2 +• +Y, > 0 for a givenI e [l,2,...,L} and Y1,L > 0,Y2, > 0,..., and ‘mi > 0. Therefore,Pc(n,m)=Pr{Yi,1,Y2,i,...,Ym,i >0 andZn,j >o}Pr { Y1 , Y21 ,. . , m,i > 0 and ‘k,i > }ii m= PrYij,Y2j,...,Ymj >0 and >I. k=m+1 k=1= Pr{YiiY2,i... m,i >0 and Gn_m,i > _Yk1}k=1 (2.38)where Gn_m,i = k,i’ is the sum of (n - m) Gaussian random terms Yj. The variancek=m+1of Gn_m,i is the sum of the variances of Y, namely (n — m)a2. The mean of Gn_m,i(n — m)A. The pdf of Gn_m,i is thus given byj g_,,—(n—m)Af 1 2 ,J(n_m)G2PGn_mi n_n,1) = 2(2.39)Hence, the joint pdf of Y1, , Y21 , . .,Ym,j and Gn_m,j SChapter 2 Analysis ofRetransmission Probabilities 29Ym,i,Gn_m,i (yi,i,...,ym,i,gn_m,i)i(yj—A2 gn_m,i(u1m)A2—1 1 Ue J 1 2 Jm)a2J k1 42(n_m)o2 e (2.40)From (2.38) and (2.40) we can writeP (n, m)=$ }‘m,j,Gn_m,j1,j.)’m,j,nm,j) dg,j dym,i”dYi,iYi,r Ym,i — Yk,Lk=1m 1 Yk —A 2 1g,_,,i—(n—m)A 2( 1 ‘ 14e2( 1 e 2Ld27ta2) 421t(n_m)a2Yi,° Ym,i0 —8n-m,iLYk,i do . dv . dk=1 on-m,j Jm,j .1,j(2.41)YkiA g_ •—(n—m)ALetting Ytkj = ‘ , k = 1,...,m and= ii m,i,we havea .J(n_m)a2P(n,m)mm 1,2 1, 2=,‘A, A m(IL) fleYm,z flmi=Yki+__]g n-m,i y m” y i,imm 2 1= $ ... $ Lk) fle2” $ Iii y’mi—1 (, , dg n-m,i1Y m,i”1Y 1,ia ‘ ag n—m—.—;\Ly k,i )= $AY’k,i +)) dY’m,i •-dy’1Yjj Y’m,ia a(2.42)Chapter 2. Analysis ofRetransmission Probabilities 30The numerical procedures for evaluating F (n, m) are given in Appendix B. WithF(n,m) defined, P3p can be expressed asP3p =1 -n(i - )L + ;)(l - )2L (](l - )3L.+:)1-_[(,o)]L+ n[(n, i)JL - 2)]L+.. +(_l)n+1= [i_ (1- )L] + ( 1)k+1 (n, k)JL.k=O (2.43)Note that for Scheme 2P in (2.33), P2p = 1— P(n,O) and P2p = 1 —[P(n,O)]’.2.2.4 Schemes 4P, 5P and 6PLet B1, j = 1,2,.. .,n, denote the event of successful packet decoding on thecombined packet using the first j copies and DkP, k = l,...,2’ —1, denote the event ofsuccessful decoding using the copies selected’ by the binary expansion of k as described insection 2.1.5. For Schemes 4P, 5P and 6P, the corresponding retransmission probabilitiesare given byp_1_Pr{AuB2u.”uB,p} (2.44)F5p lPi{A uA2”•uAuB2pu...uB,p} (2.45)127z_1‘6P =l—Pr UDk=1 (2.46)and can be evaluated by expanding the union of events, as done in the case of harddetection, with the exception that each joint event in the union expansion is an integralsimilar to (2.42). Using the same example as in section 2.1.4, consider the eventA1B345for the case of n = 8 copies. Let denote the event of B3 at a particularbit position, we havePr{A1B3pB4A5} = [Pr{a1b3pb4a5}]L (2.47)Chapter 2. Analysis ofRetransmission Probabilities 31Similar to the derivation of P (n,m) in (2.38-2.42) above,andPr{a1b3pb4a5} Pr{a5}Pr{a1b3pb4}(1— p)Pr{a1b3pb4}Pr{a1b3pb4}= PrfY1,>0 and Y1, + Y2,1 + Y31 >0 and Y1 + + Y3,1 + Y4, > o}Prfr1 >0 and Y1 + G21 >0 and Y1, + G2,1 + >0)= pr{yi,i > 0 and G2,1 > —Yi, and Y4, >—(1,+ G2,)Jwhere G21 = Y2, + (2.49) can be written asPr{a1b3pb4}=y,=O g21=—y44,=—(y1+g2)1 e03 1dy4dg21y1(2.50)Yk -ALet Y’k,= ,1, k = 1 and 4, and g2,Pr{a1b3pb4}1’ 3As4AYi1=—g2,j=—y’i,i) Y’4,I=—(Y 1J+’2+—)g •-2A= 2,i, we have1,2 1,2 1,21 —jY li 1 —g 2,i 1 Y 4,ie e edyt dg’ 2,i dy’100= $ f 1 1 ——g2 2Y’i,1(3A)2‘ Q(_[Y’i, +g’2+])dgt2,jdy’111,1 +g’ 2,i +]g’ 2,i dy’ 1j(2.48)(2.49)(2.51)Chapter 2. Analysis ofRetransmission Probabilities 32HencePr{a1b34a5} = (1 —p)Pr{ab34}e 2 Q(_[Y’ ij +gt21 + Jfi2 !(yj2+gj2)A i(, 3A’Yi,i—-g2,=—y +— I dg’ 2,1 dy’a)(2.52)For Scheme 6P, the lower limit of the integrals may happen to be -oo. Forexample, consider the event ofD35 for the case of n = 3 copies. Letting d be theevent of DkP at a particular position, we havePr{D3pD5} = [ Pr{dpd5p}]L (2.53)Pr{d3pd5} = Pr{Y11 + Y21 >0 and Y + Y31 > o}= Pr{ > —Y1, and Y3,1 > —Y1, } (2.54)Using a similar approach to (2.51), we have1 1( 2APr{d3d5}= QI —y’1_) dy’a01________= j___$e+112Q(_yt. 2A’ 1 (2A)e2 Q dy’1a) ‘ a (2.55)Put y’ = —y’ lj in the first integral on the R.H.S., (2.55) becomesPr{d3pd5}_ _1 2 2A’1 2 2A 11 ——Y’i.i= fe 2 ——I dy’11 + Se 2 Q(_Y’i,i——J dy’a)1 21 Yi, [ , 2AN 1’ 2A”= fe 2— 1,i —— I +QI y’i, —— I ]dY’i,i(2.56)a) a)Chapter 2. Analysis ofRetransmission Probabilities 332.2.5 Comparison of completely soft detection schemesA plot of the retransmission probability using perfect quantization for Schemes 2Pto 6P with n = 3* and L = 500 is given in Figure 2.13. The curves for the hard detectioncase are also shown. It can be seen that the retransmission probabilities using perfectquantization are significantly lower than those using hard detection and the relativepercentage differences in retransmission probabilities among the schemes are higher in thecase of perfect quantization.1 —-2- 10-C-310C-410E-510-ii)-610 -.710 I3 4 5 6 7 8 9 10SNR(dB)Figure 2.13 Retransmission probabilities for Schemes 2H to 6H and 2P to 6P (n 3, L = 500)HardDetectionPerfect..•—c.—. %_Quantization N - . -%.- s..N N’kNN “Scheme6 — —Scheme5Scheme 4 — - — - — - —Scheme3Scheme2I I* Numerical results for Schemes 3P, 4P, 5P and 6P for n> 3 are very time-consuming to obtain.Chapter 2. Analysis ofRetransmission Probabilities 342.3 Soft Decision SchemesWe now consider a decision scheme with an arbitrary number, 2M - 1, ofthresholds {O,±7,±7,...,±TM_l}, which defines 2M regions fRM} as shown inFigure 2.14. The weights associated with each region is ±Wm m = l,2,...,M. Assumea packet of all ‘1’ is transmitted. The probability p(m) that the matched filter outputj = 1,...,n and i = l,...,L, falls into region Rm is given byp(M)= Q(TM_i_A)p(m) = Q(TmA_Q(TmA) ,m=1,2,...,(M—l) (2.57a)Similarly, the probability p(—m) that falls into region R_m is given byp(—M) = Q(TM1 +,m = 1,2,...,(iJ —1)(2.57b)-R2-R1 R1 R2I I—w2—W1 W1-RMWM0 T1 A7 TM1RMWMFigure 2.14 The weights and thresholds associated with the 2M regionsChapter 2. Analysis ofRetransmission Probabilities 35WMA w2Wix Yw-l-A w2WMFigure 2.15 DMC resulting from quantizing the receiver matched filteroutput into 2M regions (adapted from [18])To obtain the set of thresholds which optimize the performance of the system, twotechniques have been proposed in [18]. The first uses a numerical search technique, whichcontinuously varies the threshold values until it gives the minimum effective BER for thesystem. The other approach is to find a set of thresholds that maximizes the capacity ofthe discrete memoryless channel (DMC) [27] which results from quantizing the receivermatched filter output and is shown in Figure 2.15. This approach requires solving a set ofM - 1 non-linear equations, which are reproduced in Appendix C for reference.With a given set of threshold, it is then required to select the optimum weights tobe used. From [17,18], these optimum weights are given by* P(RmIl)w=Inm P(RmIO) (2.58)Chapter 2. Analysis ofRetransmission Probabilities 36where m = 1,..., M, P(RmIO) and P(Rm 1) are the probabilities that the matched filteroutput falls in region Rm given tt(’ and “1” were sent respectively. Since the result willnot be affected by a scaling of weights, w is chosen as 1 for simplicity.From [18], a set of optimum thresholds (which are normalized to A and minimizethe effective BER) and weights are given and shown in Table 2.1 with M = 2 to 5, n = 5,and SNR = 8 dB.M Optimal thresholds f7 Optimal weights M2 0.46 1.00 3.383 0.30 0.63 1.00 3.09 5.904 0.21 0.43 0.72 1.00 3.05 5.41 8.945 0.17 0.33 0.52 0.77 1.00 2.96 4.98 7.41 11.30Table 2.1 Optimum Thresholds (Normalized to A) and weightsforM = 2,...,5 , SNR = 8 dB, and n = 5 (adapted from [18])In Figure 2.16, the retransmission probability of Scheme 3S is plotted against thethreshold value for M = 2, n = 3 and 4, L = 500 with SNR = 6, 8 and 10 dB respectively.We observe that the minimum retransmission probability occurs at around T1 = 0.4 forSNR = 10 dB and the minimum becomes broader as SNR decreases. Although theminimum point varies somewhat with n, the value of n in practice is typically small sinceotherwise the throughput would be very low. In the following analysis, we will thus usethe optimum threshold values in Table 2.1 (SNR = 8 dB, n = 5) for all values of n andSNR.In the following derivations, let 1’ denote the retransmission probability forScheme iS, i = 1,... 6, where S indicates the use of soft detection.Chapter 2. Analysis ofRetransmission Probabilities 37R6dBSNR=8dB--3—-.n=410-4o io — --—5------—-—--n=3E 10 - SNR=l0dB-6 - — -10 -—n=4-710ic I I I0.2 0.3 0.4 0.5 0.6 0.7 0.8ThresholdFigure 2.16 Retransmission probability for Scheme 3S with varying threshold value(M 2,,i = 3,4,L= 500)2.3.1 Scheme iSThe decoding failure probability for this scheme is the same as that of Scheme 1Hand is given by1S =1H=[i_(i_p)L]ll(2.59)2.3.2 Scheme 2SThe decoding failure probability for Scheme 2S is given by2s = Pr { the combined packet is soft detected incorrectly }= 1 — Pr { the combined packet is soft detected correctly }= 1 — [Pr{a bit of the combined packet is soft detected correct1y}]’= I — [i — Pr{a bit of the combined packet is soft detected incorrectly}]’=1—[l—p2s] (2.60)Chapter 2. Analysis ofRetransmission Probabilities 38where P2s denotes the effective bit error rate (BER) of a combined packet using softdecision decoding. From [18], the probability that the decision accumulatorj= 1,...,n and i = l,...,L, has value sis given byMPrfZ1 = sJ PrfZ_1, s — w,jp(m)+ Pr{Z_1,j = s + w,’,jp(—m)‘m=1 (2.61)where Pr{Z0,j = o} = 1. The effective BER P2s is given byP2s Pr{ZM. =sI+Pr{ZMI o}. (2.62)all s<OFigure 2.17 shows P2. with n 4 for M = 1,...,5. The improvement in 2S is thegreatest when M is changed form 1 to 2 and the incremental improvement drops forfurther increasing values of M. Figure 2.18 shows 2S with M = 3 for n = 1 to 6.Comparing with 2H in Figure 2.5, 2s for n 21 and 2/ - 1, l = 1,2,..., are no longerthe same; there is a steady improvement in 2S as n increases. To achieve aretransmission probability of iO with M = 3 and n = 4, an SNR of approximately 7.5 dBis required.2.3.3 Scheme 3SLet Bs denote the event that the combined packet (of n received copies using softdetection) is successfully decoded and bs the event of Bs at a particular bit position.Similar to the derivations for Scheme 3H, we haveP3s =l_Pr{Aj}+ Pr{AJAk}— Pr{AjAkAj}+...+(_1Y1Pr{AI...Afl}j=1 1j<kn 1j<k<1n—Pr{Bs}+PrABs}— PrAJAkBs}+...+(—1)’’ PrfAiA2...AB}jz1 1j<kn(2.63)Pr{A1A2. AmBy} = [ Pr{bsaia2 .am}IL = [P(nm)]L (2.64)4-I-o10‘a-2• 10-310o 10-5. 1• 1-10410.910-1010-1110- 1 2 3 4 5 6 7 8 9 10SNR (dB)Chapter 2. Analysis ofRetransmission Probabilities 39010-210-310-410--510-610.710Figure 2.17 Retransmission probability for Scheme 2S (M = 1,..,5, n = 4, L = 500)SNR(dB)-- — -.- — . .••___•% .--.% —‘-S5.,. ‘-..5%---S 5s 5.’N‘\ “S5.•4-S‘5— ——S_S.‘Sn=3n=2 \n=1I I I I I IFigure 2.18 Retransmission probability for Scheme 2S (M = 3, n = 1,.,6, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 40=Pr{bs,Y11 >0,Y2 >O,...,Ypjj >O}=Pr{bs,Y1E{Rl,R...,RM},...,Ymi E{Rl,R2..., M}== W ,...,Wmi = wr}r1=1 ,1=r{sw1j W ,...,Wmi = w }Pr{W11 = W ,...,Wmi Wr }r1 rm=1= W ,...,Wmi = w }Pr{Wi,j = w }...pr{Wm,i = Wr Ir1=1 rm=1= = w,. ..,Wmi = Wr }flPr{Wk = w }r1=1 rm=1 k=1= = W ,...,Wmi =w)flp(rk)r1=1 rm=1 k=1M M=•••r1 rm=1Pr{Wk,i > OWii = = }m In>-w+Prk=1 J k=m+1Pr{H,_,, = S+Pr{Hnmim=—w !.Hp(rk)k=1 J k11jwherePg(n,m) = Pr{bsaia2.am}M=11=1M=••r1 =1M,;, =1Mm1 * *+Pr{Wki OW1, Wr1,...,Wmi WrmPr {}Wk,jk=m+1k=1m m=-w Iflp(rk)k=1 JIk=1(2.65)Chapter 2 Analysis ofRetransmission Probabilities 41where Hn_m,i = and Wk,1 is the quantized value of the matched filter output k,i•k=m+1The parameter rk, k = 1,2,. . . , m, indicates the region number that k,i falls into, and€ {—M,. . .,—1,1,,. ..,M}. The term Pr{Hn_mj = s) can be written asPr{Hnm,j = s} = Pr{Hn_m_i,i = s — w}p(k) + Prf Hn_m_i,i = S + w}p(_k)k=1 (2.66)where Pr{H0, = o} = 1.Actually, (2.65) implies a tree search technique as shown in Figure 2.19 for thecase of m = 2, M = 3. A branch corresponds to a decision (quantization of k,I) and theweights and probabilities for the different paths are also shown. Each node at the mth level(terminal node) corresponds to a possible combination of {w1,,w21 ,...,Wmi } withprobability fl p(r). This probability is multiplied by the probabifity of successfuldecoding of the combined packet {z }, i = 1,2,..., L, and it gives Pr {b5a1a2 am forthis terminal node. By summing up all the probabilities of the terminal nodes, we getPg(n,m).With P9(n,m) defined as in (2.65), 3s becomesP3 =1— n(l — )L + (j(i — )2L (;(l — )3L +. .+(—1) ‘(1 —_{Pg (n,O)] + n[Pg (n, l)]L - ()[Pg (n, 2)]L . . .+(_l)n+1(flJ[P ()jL=[1 -(1 _p)Ljfl+k=O (2.67)Note also that P2s •= 1 — Pg (n,O) in (2.62). Hence (2.60) for Scheme 2S can berewritten asChapter 2. Analysis ofRetransmission Probabilities 42“2S _[1’g(t,0)} (2.68)Figure 2.20 shows 3S with n = 4 for M = 1,.. . , 5. The retransmisson probabilitydrops as M increases and the incremental improvement decreases for further increasingvalues of M. Figure 2.21 gives P1ç with M = 3 for n = 1 to 5. It shows a steadyimprovement in retransmission probability as n increases. To achieve a retransmissionprobability of i0 with M = 3 and n = 4, an SNR of approximately 7.5 dB is required.(2w), p(1)p(l)( + w), p(1)p(2)(w +), p(1)p(3)(w +w), p(2)p(l)(2w), p(2)p(2)(w p(2)p(3)(w ÷wjj, p(3)p(l)( +w),p(3)p(2)(2w), p(3)p(3)Figure2.19 Treediagramform=2andM=3(p(k)and w,k=1,...,3are defined in (2.57) and (2.58) respectively)1(), p(1)(w),p(2)p(3)-o10-210-4o 10-s100ib6-710-8106.)là-1010-11100 1 2 3 4 5 6 7 8 9 10SNR (dB)Chapter 2. Analysis ofRetransmission Probabilities 43010id-210id-4101t-610-710-810SNR (dB)Figure 2.20 Retransmission probability for Scheme 3S (M 1,..,5, n = 4, L = 500)2 3 4 5 6 7 8 9 10----:-;------. —--- . S..5.-5-S -5-S.S.\. \,n=5n—_4 —. - — - — - —n=3n=2n=1I I I I I IFigure 2.21 Retransmission probability for Scheme 3S (M = 3, n = 1,...,5, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 442.3.4 Schemes 4S and 5SLet Bs, j 1,2,..., n, denote the event of successful packet decoding of thecombined packet of the first] copies using soft detection. The retransmission probabilitiesfor Schemes 4S and 5S are given by(2.69)and(2.70)Again, these expressions can be evaluated by expanding the union of events, asdone in the case for hard detection. The probability of each joint event in the unionexpansion can be evaluated numerically as follows. Using the same example in section2.1.4 and 2.2.4, consider the eventA1B3sB4A5for the case of n = 8 copies. Letting bsdenote the event of Bs at a particular bit position, we havePr{A1B3SB4A5} = {Pr{aib3sb45}]L (2.71)wherePr{aib3sb45}= Pr[aib3sb45I ir2}Pr{riri=-Mr2=-Mr3=-Mr4=-Mr5=-Mr1O r2O r3O r4O r5OM M M M M 5= Pr{albsbasr r}flp(rk)i=—Mr2=—Mr3=—Mr4=-Mr5=—M k=1tjO r2O r3O r4O r5O(2.72)The conditional probabilities are given byChapter 2. Analysis ofRetransmission Probabilities 45Praib3sb45I •••r5 } = Prfa1 ri ••r5 }Pr{b3sjr1 ••-r5 }Pr{b4sr1 -••r5 }Pr{a5I i•-r5(2.73)where11 if rk>O,k=1,...,5PrfakIrl...rS}=otherwise (2.74)and1 ifPr{bjslri...r5]’= ! j0 , otherwise.(2.75)Figures 2.22 and 2.24 give the retransmission probabilities of Schemes 4S and 5Srespectively with n = 4 for M = 1,.. .,5. In both Figures 2.22 and 2.24, the retransmissonprobabilities drop as M increases and the incremental improvement decreases for furtherincreasing values of M. Figure 2.23 gives the retransmission probability of Scheme 4S withM 3 for n = 1 to 5 and Figure 2.25 gives the retransmission probability of Scheme 5Swith M = 3 for n = 1 to 4. The figures show steady improvement in retransmissionprobabilities as n increases. It can be seen from the figures that to achieve aretransmission probability of with M = 3 and n = 4, Schemes 4S and 5S both requirean SNR of approximately 7.3 dB.46—IChapter 2. Analysis ofRetransmission Probabilities010‘a-210-310-410-510-610-710-810Figure 2.22 Retransmission probability for Scheme 4S (M = 1,..,5, n = 4, L = 500)010i-a-21010o -10-5• 10410-710410-910-1010SNR (dB)SNR (dB)Figure 2.23 Retransmission probability for Scheme 4S (M = 3, n = 1 5, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 47010>-.-2•-. 10310C-410Cic-610-7.910SNR (dB)2 3 4 5 6 7 8 9 10SNR (dB)2 3 4 5 6 7 8 9 10Figure 2.24 Retransmission probability for Scheme 5S (M = 1,..,5, n = 4, L = 500)I010-110-210-310.410-510-610.710410.—- —•-.n=4ri=3n=2n=1Figure 2.25 Retransmission probability for Scheme 5S (M = 3, ,z = 1,...,4, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 482.3.5 Scheme 6SLet D, k = 1,..., 2’ — 1, denote the event of successful decoding on thecombined packet using the copies ‘selected’ by the binary expansion of k as described insection 2.1.5. For Scheme 6S, the retransmission probability is given by12 —1P6slPrUDk=1 (2.76)Equation (2.76) can be evaluated by expanding the union of events with the probability ofeach joint event in the union expansion evaluated as follows. To illustrate the calculation,we consider the same example as in section 2.1.5, i.e. DisD3sDi722for the case ofn = 8 copies. Letting d denotes the event of D at a particular bit position, we havePr{D15D3sD722} =[Pr{d1sd3722}]L (2.77)Pr{disd3s i722} = ... Prfdisd3sdi722grir45}pr{r1rr3},—M r5=—Mr1O r5O= ... Pr{disds i22rir}p(rj)zj=—M r5=—M j=1rO r5O (2.78)The conditional probabilities are given byPr{disd3s i722r . . . r5 }=Pr{disri...r}Pr{ds i...rr{di2, (2.79)whereChapter 2. Analysis ofRetransmission Probabilities 4951 if cw>0j=1I if0 , otherwise. (2.80)The above numerical method for Scheme 6S can be applied to evaluate theretransmission probabilities of all other kinds of combination schemes using hard (M = 1)or soft detection.Figure 2.26 shows 6S with n = 3 for M = 1,... ,5 and Figure 2.27 gives 6S withM = 3 for n = 1 to 4. It can be seen that as M or n is increased, P6ç decreases asexpected. The improvement in P obtained from increasing n is the greatest among allthe schemes. To achieve a retransmission probability of l0 with M = 3 and n = 4,Schemes 6S requires an SNR of approximately 6.4 dB.010-2- 10-3P. 10C-410.610.710SNR(dB)Figure 2.26 Retransmission probability for Scheme 6S (M = 1,..,5, n = 3, L = 500)Chapter 2. Analysis ofRetransmission Probabilities 50irnSNR (dB)Figure 2.27 Retransmission probability for Scheme 6S (M = 3, n = 1,...,4, L = 500)2.3.6 Comparison of soft detection schemesFigures 2.28 and 2.29 show the retransmission probabilities of Schemes iS to 6Swith n = 3 and M = 2 and 3 respectively. From these figures, we observe that theincremental improvement from increasing M from 2 to 3 is quite small. From Figures 2.29and 2.13, it can be seen that the result forM = 3 is very close to that for soft detection.To compare the detection schemes at a different n value, Figure 2.30 gives theretransmission probabilities of Schemes 2S to 6S with M = 3 and n = 4. The results forhard detection with the same n are also shown. It can be seen that for a higher value of n,the relative percentage difference in the retransmission probabilities among the schemesincreases.010I410ii-610IChapter 2. Analysis ofRetransmission Probabilities 51-210-310SNR(dB)Figure 2.28 Retransmission probabilities for Schemes iS to 6S (M = 2, n = 3, L 500)010ic-210-310410-s104103 4 5 6 7 8 9SNR (dB)10Figure 2.29 Retransmission probabilities for Schemes 15 to 6S (M = 3, n = 3, L = 500)10là3O -41 10-5o io1010ià810-10102.4 Effect of packet length LTo observe the effect of the packet length L on the error performance,retransmission probabilities of Schemes iS to 6S are plotted against the packet length Lwith a constant SNR value of 8 dB and n = 3 in Figures 2.31, 2.32 with M = 1 and 3respectively. From Figure 2.31, we can see that as L increases, the retransmissionprobability increases as expected and for L greater than 500, all the schemes exceptScheme 1H have similar retransmission probabilities. Note that from observingFigure 2.31, Scheme 3H is better than Scheme 4H generally. In Figure 2.32 for M = 3,the relative percentage differences in retransmission probability among the schemesincrease for L > 100 and the difference is even greater when n is increased to 4 inFigure 2.33.Chapter 2. Analysis ofRetransmission Probabilities 52Hard—-----.--.- —----.-- ---.-..-.- —..-—. -4-t--- SoftDetection- (M=3)DetectionScheme6 — —Scheme5Scheme 4Scheme3Scheme 27 8 95 6 10SNR (dB)Figure 2.30 Retransmission probabilities for Schemes 2H to 6H and 2S to 6S (M = 3) with n = 4, L = 500Chapter 2. Analysis ofRetransmission ProbabilitiesI53lot 102Bits per packet010o -z100.510Figure 2.31 Retransmission probabilities for Schemes IH to 6H against L (n = 3, M = 1, SNR = 8 dB)010-210410-510.610102Bits per packetFigure 2.32 Retransmission probabilities for Schemes IS to 6S against L (n = 3, M 3, SNR = 8 dB)Chapter 2. Analysis ofRetransmission Probabilities 54010-110-410-5to-610-710410làII101 102Bits per packetFigure 2.33 Retransmission probabilities for Schemes iS to 6S against L (n = 4, M 3, SNR = 8 dB)Chapter 3 Throughput Analysis and SimulationsIn this section, we compare the performance of the six schemes by examining thethroughput T for the Weldon ARQ scheme [13,14,22] with q = 1, S = 1000 and L = 500.The receiver buffer size is qS and the throughput is given byT=1(3.1)where [3 is the average number of transmissions required to send one block successfully.For all six combining schemes, f3 can be expressed as [22]3= fl0 +fl1PF(flO)+fl2PF(flO)PF(fll)+.”q-1 ( +s—i)+flqflPF(ni)+q HPF(n)i0 “FVq) 1=0 (3.2)where P (ne) is the retransmission probability for the detection and combining schemesused with n1 copies. F (n1) can be calculated as discussed in chapter 2. The optimalnumber of copies, n (found using procedures described in [14], which are alsoreproduced in Appendix A for reference), of Schemes 1H to 5H are given in Table 3.1while those for Schemes 2S to 5S for M = 2 and 3 are given in Tables 3.2 and 3.3respectively. These optimal values were used in (3.1) and (3.2) to calculate thecorresponding throughputs. Because of the large amount of computational effortrequired, the throughput of Scheme 6 is considered only for the hard detection case usingsimulation. The optimal number of copies used (Table 3.4) is found by simulation search,i.e. we vary n until the simulated throughput is maximized.In our analysis, we consider only the case in which the n1 packets received at theith level are combined and the packets at preceeding levels are discarded; otherwise thethroughput analysis will be complicated by dependencies among error events from55Chapter 3. Throughput Analysis and Simulations 56decoding failures in different levels. Tn [22], this variation was considered and applied toSchemes 1H to 6H.The throughputs of Schemes 2S to 5S are shown in Figures 3.1 to 3.4 withM = 1,2 and 3. Also shown are the throughputs of the Weldon ARQ scheme with variablen0 and ideal selective repeat scheme with no combining. It can be seen that combining canresult in a significantly higher throughput for the Weldon ARQ scheme. There is also alarge improvement when M is increased from 1 to 2; however the incrementalimprovement drops when M is increased further. A reasonable value of M to choose interms of performance and decoding complexity is 2 or 3. When M is above or equal to 2,Schemes 2S to 6S have better performance than the ideal selective repeat scheme with nocombining for block error rates (BKER) greater than 0.5. Note also from Table 3.1 thatthe optimal number of copies for Scheme 2H (M = 1) are all odd numbers. This is becausethe retransmission probability of Scheme 2H remains unchanged if n is increased by onefrom an odd value [19]. In general, Schemes 2S to 5S have a lower optimum number ofcopies than Scheme iS. This optimum value decreases when M increases.Figures 3.5 to 3.7 show the throughputs of Schemes lS to 5S with M 1, 2 and 3respectively. It can be seen that except for Scheme 1, the difference in throughput amongthe schemes is small. In general, Schemes 3S and 5S have similar throughputs andoptimum number of copies and perform better than Schemes iS, 2S and 4S. HenceScheme 3S with M = 2 or 3 will give good performance with reasonable systemcomplexity.The simulated throughput of Scheme 6H is shown in Figure 3.8 along with the99% confidence limits. The throughput of Scheme 3H is also shown for comparison. Itcan be seen that the difference in throughputs between Schemes 3H and 6H is quite small.0C IPPP229999DOL4t’J-t00C_1.1:.Li)kk—••*-—L)*::::::::::!t’*-——LuUiLuLiiL)t)L)L)Lj)(.)Lij)—.*——————wLiiL(.ui—‘c-”L)-*L)*:::::::::1CD 0 CD -t C C-) C CD I999929299\D00LI’-)-i-‘t’-)t’—)IN-)IN-)t’‘‘(JiLI’44.4-L)tj.)-*r) ICD 0 I I I.999999999D00—QLI,.IN)L’JIN)I’)IN)‘JIN)0 -————————a DLt)J-*IN-)‘—IN-)IN--)IN-•—*::::::::::!IN.)IN)IN)IN)IN)IN)——Cl) 0——————————FL)L)L,)Li-)Li-)Li-)Li-)IN)*IN.)IN-.)IN.)IN.)IN)IN)—-————————cT.f..ci-)Li-)Li-)Li-)Li-)Li-.)IN.)IN.)-*LitC C pUI00Chapter 3. Throughput Analysis and SimulationsI0100.1Figure 3.1 Throughput for Scheme 2S (M = 1,2,3,4, L = 500, q = 1, S = 1000)Block Error Probability59Block Error Probability0100.1Fiure 3.2 Throughput for Scheme 3S (M = 1,2,3,4, L = 500, q = 1, S = 1000)Chapter 3. Throughput Analysis and Simulations 60II010100.1Block Error ProbabilityFigure 3.3 Throughput for Scheme 4S (M 1,2,3, L 500, q = 1, S = 1000)010—1100.1Block Error Probability1Figure 3.4 Throughput for Scheme 5S (M = 1,2,3, L = 500, q = 1, S = 1000)Chapter 3. Throughput Analysis and Simulations 61I0.80.70.60.50.40.30.20.10Block Error ProbabilityFigure 3.5 Throughputs for Schemes 1H to 5H (M = 1, L = 500, q = 1, S = 1000)0.90.80.70.60.50.40.30.1Block Error ProbabilityFigure 3.6 Throughputs for Schemes IS to 5S (M = 2, L = 500, q = 1, S = 1000)Chapter 3. Throughput Analysis and Simulations 62z-C0.90.80.70.60.50.40.30.1Block Error ProbabilityFigure 3.7 Throughputs for Schemes iS to 5S (M 3, L = 500, q = 1, S = 1000)0.80.70.60.50.40.30.20.1Block Error Probability1Figure.3.8 Simulated Throughputs for Schemes 3H and 6H (L = 500, q = 1, S = 1000)Chapter 4 ConclusionsA general multiple copy combining ARQ scheme was investigated using hard, soft,and perfectly quantized detectors. Six different combining schemes have been consideredIn each case the dependence of the retransmission probability, F’ on the signal to noiseratio (SNR), the number of copies transmitted (n), the number of quantization levels of thedetector (M), and the packet length (L) are studied.For an arbitrary degree of detector quantization, analytic expressions for F ofScheme 3 have been derived, and numerical procedures for evaluating the F of Schemes4, 5 and 6 have been described. It has been shown that Scheme 3 can have a significantlysmaller F than Scheme 1 or Scheme 2. Scheme 4 has a higher “F than Scheme 5 and therelative percentage difference between them increases as SNR increases. It was found thatScheme 3 has a F close to that of Scheme 5, especially for small values of n. Scheme 6has the lowest F of all the schemes, but requires higher decoding complexity. Generally,when n is increased, the relative percentage difference of F between the schemesincreases as well.When M is increased from 1 to 2, F of Schemes 2 to 6 drops significantlyespecially for Schemes 2 and 4 with even n. When M is increased further, “F ofSchemes 2 to 6 continue to decrease but the incremental improvement is smaller. Theadditional improvement obtained from increasing M from 4 to 5 is already very small.When M is increased, the relative percentage differences in F among the schemesincrease as well. The“F of Scheme I is the same for any value of M since it does notperform combinations.As the packet length L increases, the“F for the six schemes increase as expected,but the difference between them drops.The six schemes were then applied to the Weldon ARQ scheme [13,14,221 and theresultant throughputs for different values of M were analyzed. The throughput of the63Chapter 4. Conclusions 64Weldon ARQ scheme can be greatly improved using multiple copy combining. It can befurther increased by using soft decision detection. Using about 8 quantization levels isadequate to give a throughput which is close to that obtainable from using perfectquantization. For block error rate BKER > 0.5 and M 2, the performance of Schemes2S to 6S are better than that of an ideal selective repeat ARQ system with no packetcombining. It can be seen that except for Scheme 1, the difference in throughputbetween the schemes is small and generally, Schemes 3 and 5 have throughputs, whichare higher than those of Schemes 2 and 4. Simulation results indicate that the throughputsof Schemes 6H and 3H for q = 1 and S 1000 are not very different. Hence in general,Scheme 3 is a good choice among all the six schemes with a good performance and simpledecoder structure.Among the topics which could be further studied are the following:1. The computational effort required for calculating the retransmission probability ofScheme 6 using the numerical procedures described in section 2.1.5, 2.2.4 and 2.3.5grows rapidly as n > 4 (order of 22_1). Procedures to reduce the computationaltime for Schemes 4 to 6 perhaps by finding analytical expressions should beinvestigated.2. The memory ARQ schemes can be applied to other types of ARQ strategies wheremultiple copy transmission is used.3. Apart from the additive white Gaussian channel model, other types of channelmodels, e.g. fading or impulsive noise, can be considered when the combiningschemes are applied.References[1] J. B. Moore, “Constant-radio code and Automatic-RQ on transoceanic HF radioservices,” IRE Trans. Commun., vol. CS-8, pp. 72-75, Mar. 1960.[2] R.D. Stuart, “An insert system for use with feedback communication links,”IEEE Trans. Commun. Syst., vol. CS-il, pp. 142-143, Mar. 1963.[3] R. J. Benice and A. H. Frey, Jr., “An analysis of retransmission systems,”IEEE Trans. Commun. and Components, vol. COM-12, pp. 135-145, Dec. 1964.[4] R. J. Benice and A. H. Frey, Jr. “Comparisons of error control techniques,”IEEE Trans. Commun. and Components, vol. COM-12, pp. 146-154, Dec. 1964.[5] B. Arazi, “Improving the throughput of an ARQ stop and wait scheme for burstnoise channels,” IEEE Trans. Commun., vol. COM-24, pp. 66 1-663, Jun. 1976.[6] H. 0. Burton and D. D. Sullivan, “Errors and error control,” Proc. IEEE, vol. 60,pp. 1293-1301, Nov. 1972.[7] A. R. K. Sastry, “Improving automatic repeat-request (ARQ) performance onsatellite channels under high error rate conditions,” IEEE Trans. Commun.,vol. COM-23, pp. 436-439, Apr. 1975.[8] J. M. Morris, “On another go-back-N ARQ technique for high error rate conditions,”iEEE Trans. Commun., vol. COM-26, pp. 187-189, Jan. 1978.[9] D. Towsley, “The Stutter go-back-N ARQ protocol,” IEEE Trans. Commun.,vol. COM-27, pp. 869-875, Jun. 1979.[10] S. Lin and P. Yu, “An effective error control scheme for satellite communications,”IEEE Trans. Commun., vol. COM-28, pp. 395-40 1, Mar. 1980.[11] P. S. Yu and S. Lin, “An efficient selective-repeat ARQ scheme for satellite channelsand its throughput analysis,” IEEE Trans. Commun., vol. COM-29, pp. 353-363,Mar. 1981.65References 66[121 M. J. Miller and S. Lin, “The analysis of some selective-repeat ARQ schemes withfmite receiver buffer,” IEEE Trans. Commun., vol. COM-29, pp. 1307-13 15,Sept. 1981.[13] E. J. Weldon, Jr., “An improved selective-repeat ARQ strategy,”IEEE Trans. Commun., vol. COM-30, pp. 480-486, Mar. 1982.[14] Y. Chang and C. Leung, “On Weldon’s ARQ Strategy,” IEEE Trans. Commun.,vol. COM-32, pp. 297-300, Mar. 1984.[15] G. Arredondo, et al, “Voice and data transmission,”The Bell System Technical Journal, vol. 58, pp. 97-122, Jan. 1979.[16] P. S. Sindhu, “Retransmission error control with memory,” IEEE Trans. Commun.,vol. COM-25, pp. 473-479, May 1977.[17] G. Benelli, “An ARQ scheme with memory and soft error detectors,”IEEE Trans. Commun., vol. COM-33, pp. 285-288, Mar. 1985.[18] C. Lau and C. Leung, “Performance analysis of a memory ARQ scheme with softdecision detectors,” IEEE Trans. Commun., vol. COM-34, pp. 827-832,Aug. 1986.[19] C. Leung and C. Lau, “On a memory ARQ scheme with soft decision detectors,”IEEE Montech’ 86, Conference on Antennas and Communications, pp. 263-266,Sep. - Oct., 1986.[20] R. Fantacci, “Performance evaluation of efficient continuous ARQ protocols,”IEEE Trans. Commun., vol. COM-38, pp. 773-78 1, June 1990.[21] S. Kallel and C. Leung, “Efficient ARQ schemes with multiple copy decoding,”IEEE Trans. Commun., vol. COM-40, pp. 642-650, Mar. 1992.[22] R. Cam, C. Leung and C. Lam, “A performance comparison of some combiningschemes for fmite-buffer ARQ systems in a Rayleigh-fading channel,”1992 IEEE International Conference on Selected Topics in WirelessCommunications, pp. 88-92, Jun. 1992, Vancouver, B.C., Canada.References 67[231 D. Bertsekas and R. Gallager, Data Networks. Prentice-Hall, Inc., 1987.[24] W. Stallings, Data and Computer Communications. Macmillan Publishing Company,1991.[25] J. M. Wozencraft and I. M. Jacobs, Principles of Communication Engineering.Waveland Press, Inc., 1990.[26] S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals andApplications. Prentice Hall, Ijic., 1983.[27] R. G. Gallager, Information Theory and Reliable Communication. New York:Wiley, 1968.[28] S. D. Conte and Carl de Boor, Elementary numerical analysis, an algorithmicapproach. McGraw-Hill, 1986.[29] E. Kreyszig, Advanced engineering mathematics, John Wiley & sons, Inc., 1983.Appendix ADetermination of Optimum Values of {n1 }In this appendix, the method to find the optimum values of {n1 is given [14].From (1.1), we haveqi—IIn, / \ k=O, k=O’ iflq+Sl)PFLi13F +i=O+flq_1nO+. +nq_i (nq +5— 1)PFfO+lPF +fl2PF +“+flIPF +flqPF + 1_P=no p° [1 +;‘ [...[ni+;i [...[n_i p;’ [n +P(A.1)From (A. 1), to minimize f3, we perform the following stepsStep 1: Find the value of flq (say n) that minimizes(n +S—1fq(flq)flq±pn qflq\ 1P (A.2)Step2: Seti=q.Step 3: Decrement i by 1.Step 4: Determine the value of n1 (say n,) that minimizesf(n) = n+Pf(n,n+2...,n) (A.3)StepS: Ifi>O,gotoStep3.Step 6: Irint out { } and stop.68Appendix BNumerical Procedures for evaluating Pc(n,m)We describe the numerical evaluation of the integrals such as (2.42) defined insection 2.3. The method chosen is based on Simpson’s rule [28,29]. The estimation of1(f)= J f(x) dxa (B.l)is given by( N N-I1(f) ! 0 +4f2_1+2f + f2Ni=1 1=1 (B.2)where h = b—a and f = f(a + jh), j = O,...,N . Bounds for the error are given byCMesCM4 (B.3)lbwhere C =“ a,and M and M4 are the smallest and the largest value of the fourth180(2N)4derivative of f(x) in the interval of integration. Hence we can control the accuracy byadjusting the value of 2N, the number of subdivisions between a and b.Another point to be considered is the upper limit of the integrals. Since they areinfinite, we have to use an approximation here. The error introduced can be estimated asfollows. Take P(n,m) in (2.42) as an example,69Appendix B. Numerical Proceduresfor finding P(n,m) 701 2 (___—1 (m nAP(n,m)= f ••• f fle Q1 I Y’k I IdY’m”Y’i) k=1 Jfl — m \k=1 GA AYi= Y’ma a= J j ( 1 fle2YkQb b mm 1 2 ( m flA))dY?m•..dYIl +ETA A) k=1-nm)4 aYi Yma a(B.4)Hence the integral can be approximated using an upper limit of b with an error Eintroduced. Since 0 < Q(k) <1, ET is bounded bymm 2 1 (m nA”ET = •.. fle_ 1—1 1 Y’k dY’m”dY’ik=1 -.Jn—m k=1 ay1=b Ymthmm 2< S ••• 5 fle dY’m”dY’iy=b y’=b= [Q(b)JmE1 b7____2(B.5)In our calculations, the value of b used is 10. The error introduced in using an upper limit10 instead of infmity is bounded by ET <[1.33 x lO_16]m.Appendix COptimum Thresholds for Soft DecodersIn [181, a set of M - 1 nonlinear equations whose solution gives the set ofthresholds which maximizes the capacity of a discrete memoryless channel (DMC) shownin Figure 2.15 was given. We haveCH(X)—H(XIY)=1-[p(i)+p(-i)]h p)p(i) + p(—z) (C. 1)where h(e)=elog2{1/e}+(1—e)log/(1 )} is the binary entropy function.Substituting (2.57) into (C. 1) and setting the partial derivatives C / )Tm = 0, we have aset of M - 1 equations:(Tm -A)2 {p(m)+p(-m)}p(m+1)exp •1og22 [p(m)fp(m+1)+p(—m—1)}______{p(m)+p(-m)}p(-m-1) 1+exp log =02a p(—m){p(m+1)+ p(—m —i)}j (C.2)where m=1,2,...,M—1.71Appendix UAsymptotic Behaviour of Retransmission Probabilityfor Schemes 1H, P211 and 3HWe consider in this appendix the behaviour of 1H’ 2H and 3H for p << 1.D.1 Scheme 1HFrom (2.8), we haver L1’“IH [1_(l_P) I (D.1)Applying the binomial series [29] to (i—p)’, and neglecting higher order termsin p (since p <<1), we obtain“1H [1_(l_Lp)](D.2)D.2 Scheme2HFrom (2.9),‘2H _{1_1’rnaj(12,P,0)j (D.3)Consider first the case for n odd. From (2.lOa), p,, (n,p,k) is given byn—k (n—k”P,(n,p,k)=j )2 (D.4)72AppendixD. Asymptotic Behaviour ofRetransmission Probability for Schemes 1H, 2H and 3H 73For p << 1, we can neglect higher order terms in p so thatn—k !P,,(n,p,k) [(n+1X]2if=0 ,otherwise (D.5)For odd n, (D.3) then becomes‘2H=l_[l_p,j(n,p,O)]Ln1[1[(n±iy]P 21L (n+l)/ 2/2) (D.6)From (2.lOb), P,j (n,p,k) for even n is given byP(n,p,k) = (n_k)i(l _)nki(D.7)For p <<1, we can neglect higher order terms in p so thatif kP,(n,p,k) 2otherwise (D.8)n=0For even n, (D.3) then becomesAppendixD. Asymptotic Behaviour ofRetransmission Probability for Schemes 1H, 2H and 3H 74‘2H=l_[l_P,,j(n,p,O)]LL1— 1—— p22Ln/2Jf_ ‘ nLI I —p22n/2) (D.9)n+1Hence for both odd and even values of n, 2H decreases as [ 2 J when p << 1.D.3 Scheme 3HFrom (2.15) we have“3H [i_(i_ )Ljfl +(_l)k÷1J[(l — )k[i_ P,,j (n,p,k)]]L.k-O (D.1O)Let the second term on the R.H.S. be ST. Since Pj (n,p,k) << 1 for both evenand odd n when p << 1 (D.5,D.8), ST becomesST=- )k [1- Pj(n,p,k)]j(‘) [k1-P_nPk11)k+1—.(n,p,k)]= (-i)’ [:] 1)k+1 [n][LP. (n,p,k)]=k=O (D.11)because (_l)1[’] = 0. With (D.5) and (D.11) and for odd n ST becomesAppendixD. Asymptotic Behaviour ofRetransmission Probability for Schemes 1H, 2H and 3H 75(n9/ ( n—k n+1(1)k+1InEL(fl+lyJP]k=O kJ[n n—k=-Lp 2 (1)k+1[)[(n+ly]k=On+1k+1 n! (n—k)!=-Lp2__________________k!(n —k)! (n+ 1,(n—1_k)!2 2n+1(n—/ 1n—1n! ()k+1 2)!=—Lp 2___________(n — 1,(n +__2 ) 2 )! k=O 2 (D.12)The summation term in (D.12) is zero and hence ST isO for odd n with n > 1. Forn = 1, this summation term reduces to -1 and ST = Lp. Hence we have, for odd n withn> 1,(D.13)and P3H —2Lpforn——1.For the case of n even, with (D.8) and (D.1 1), ST can be written asAppendixD. Asymptotic Behaviour ofRetransmission Probability for Schemes 1H, 2Ff and 3H 76ST_(_l)1r(fl—kk=O [k][fl/2J](nNn—kL()k+1 (k=Ok+1 n! (n—k)!= -p(-l)k!(n-k)! (n/2)! -k=O Lj )L n! A= 2 (nI2)!(1)k+1__2k=O k!(’—knxOL____(n12)!2(D.14)and hence P3 = [Lp]’ for even n. In conclusion, P311 decreases as p’ for p << 1 forn = 1,2,3
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Multiple copy combining schemes for the additive white...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Multiple copy combining schemes for the additive white Gaussian noise channel Lam, Carson Y.H. 1992
pdf
Page Metadata
Item Metadata
Title | Multiple copy combining schemes for the additive white Gaussian noise channel |
Creator |
Lam, Carson Y.H. |
Date Issued | 1992 |
Description | A generalized version of a memory automatic repeat request (ARQ) scheme [15-221 using hard, soft, and completely soft detection is examined. The communication channel is modeled as an additive white Gaussian noise (AWGN) channel. The following six combining schemes are considered. In Scheme 1, error detection is performed on each of the n received copies. In Scheme 2, all n copies are combined and error detection is performed on the resulting packet. Scheme 3 uses Scheme 1 followed by Scheme 2 (if decoding using Scheme 1 is not successful). In Scheme 4, each incoming packet is combined with the copies received so far, and the resulting combined packet is checked for errors. Scheme 5 uses Schemes 1 followed by Scheme 4. The last scheme, Scheme 6, attempts decoding on up to all 2n- I possible combinations of the received copies. For an arbitrary detector quantization, analytic expressions for the retransmission probability, PϜ of Scheme 3 are derived, and numerical procedures for evaluating the PϜ of Schemes 4, 5 and 6 are described. Numerical examples showing the dependence of PϜ on various parameters, such as the signal to noise ratio (SNR), number of transmissions n, number of quantization levels M and packet length L are given. Although Scheme 6 has the lowest PϜ its decoding complexity increases exponentially with n. The six combining schemes are applied to the Weldon ARQ scheme [13,14,22] It is found that the throughput T is generally improved using multiple copy combining schemes. The throughput can be further increased by using a soft detector. For block error rates BKER > 0.5 and soft detectors, the throughputs of Schemes 2 to 6 are typically higher than that of an ideal selective repeat ARQ system with no packet combining. In general, Scheme 3 appears to be a good choice among all the six schemes with a good performance and a simple decoder structure. |
Extent | 1257397 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-01-05 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0064795 |
URI | http://hdl.handle.net/2429/3366 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1992-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1992_spring_lam_carson_y_h.pdf [ 1.2MB ]
- Metadata
- JSON: 831-1.0064795.json
- JSON-LD: 831-1.0064795-ld.json
- RDF/XML (Pretty): 831-1.0064795-rdf.xml
- RDF/JSON: 831-1.0064795-rdf.json
- Turtle: 831-1.0064795-turtle.txt
- N-Triples: 831-1.0064795-rdf-ntriples.txt
- Original Record: 831-1.0064795-source.json
- Full Text
- 831-1.0064795-fulltext.txt
- Citation
- 831-1.0064795.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0064795/manifest