MULTIPLE COPY COMBINING SCHEMES FOR THE ADDITIVE WHITE GAUSSIAN NOISE CHANNEL by CARSON Y. H. LAM B.Eng. (Electronic and Communication Engineering), University of Bath, U.K., 1990 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard ...... ...................... . THE UNIVERSITY OF BRITISH COLUMBIA July 1992 © Carson Y. H. Lam, 1992 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Z&CtA ILç /Li 6 The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Abstract 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 2’- I possible combinations of the received copies. For an arbitrary detector quantization, analytic expressions for the retransmission of Scheme 3 are derived, and numerical procedures for evaluating the F of Schemes 4, 5 and 6 are described. Numerical examples showing the dependence of F probability, F’ 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 F’ its decoding complexity increases exponentially with n. The six combining schemes are applied to the Weldon ARQ scheme [13,14,221. 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. II Table of Contents Abstract . ii List of Figures v List of Tables viii Acknowledgment ix Chapter 1 1 Introduction 1 1.1 Conventional ARQ Schemes 1.1.1 Stop-and-Wait ARQ 1 1.1.2 Go-back-NARQ 2 1.1.3 Selective Repeat ARQ 4 1.2 An Improved Selective Repeat ARQ Strategy 5 1.3 Memory ARQ 6 1.3.1 Combining Schemes 7 1.3.2 Detection Methods 8 9 1.4 Organization of thesis Chapter 2 Analysis of Retransmission Probabilities 10 13 2.1 Hard Decision Schemes 2.1.1 Scheme 1H 14 2.1.2 Scheme2H 15 2.1.3 Scheme3H 16 2.1.4 Scheme4Hand5H 18 2.1.5 Scheme6H 22 2.1.6 Comparison of hard detection schemes 24 2.2 Completely Soft Decision Schemes 26 2.1.1 SchemeiP 26 2.2.2 Scheme2P 27 ifi 2.2.3 Scheme3P .27 2.2.4 Schemes 4P, 5P and 6P 30 2.2.5 Comparison of completely soft detection schemes 33 34 2.3 Soft Decision Schemes 2.3.1 Scheme iS 37 2.3.2 Scheme 2S 37 2.3.3 Scheme3S 38 2.3.4 Schenes 4S and 55 44 2.3.5 Scheme 65 48 2.3.6 Comparison of soft detection schemes 50 52 2.4 Effect of packet length L Chapter 3 Throughput Analysis and Simulations 55 Chapter 4 Conclusions 63 65 References 1 Appendix A Determination of Optimum Values of {n } 68 Appendix B Numerical Procedures for evaluating Pc(n,m) 69 Appendix C Optimum Thresholds for Soft Decoders 71 Appendix D Asymptotic Behaviour of Retransmission Probability for Schemes 1H, 2H and 3H 72 D.i SchemelH 72 D.2 Scheme2H 72 D.3 Scheme3H 74 iv List of Figures Figure 1.1 Stop-and-wait ARQ 2 Figure 1.2 Go-back-N ARQ 3 Figure 1.3 Selective Repeat ARQ 4 Figure 2.1 Block diagram of the memory ARQ system (adapted from [18]) 10 Figure 2.2 Weights and Thresholds distribution 11 Figure 2.3 , 3 Probability Distribution function of Y 13 Figure 2.4 Retransmission probability for Scheme 1H (n = l,2,...,7, L = 500) 14 Figure 2.5 Retransmission probability for Scheme 2H (n = 1,3,5,7, L = 500) 16 Figure 2.6 Retransmission probability for Scheme 3H (n = l,2,...,6, L = 500) 18 Figure 2.7 Retransmission probability for Scheme 4H (n = 1,2,...,6, L = 500) 21 Figure 2.8 Retransmission probability for Scheme 5H (n = l,2,...,6, L = 500) 21 Figure 2.9 Retransmission probability for Scheme 6H (n = 1,2,3,4, L 500) 23 = Figure 2.10 Retransmission probabilities for Schemes 1H to 6H (n = 2, L = 500) 25 Figure 2.11 Retransmission probabilities for Schemes 1H to 6H (n = 3, L = 500) 25 Figure 2.12 Retransmission probabilities for Schemes 1H to 6H (n = 4, L = 500) 26 Figure 2.13 Retransmission probabilities for Schemes 2H to 6H and 2P to 6P 33 (n=3,L=500) Figure 2.14 The weights and thresholds associated with the 2M regions 34 Figure 2.15 DMC resulting from quantizing the receiver matched filter output into 2M regions (adapted from [18]) 35 Figure 2.16 Retransmission probability for Scheme 3S with varying threshold value 37 (M=2,n=3,4,L=500) Figure 2.17 Retransmission probability for Scheme 2S 39 (M= l,..,5,n=4,L= 500) V Figure 2.18 Retransmission probability for Scheme 2S 39 (M=3,n= 1,...,6,L= 500) Figure 2.19 Tree diagram form = 2 andM = 42 3 Figure 2.20 Retransmission probability for Scheme 3S 43 (M=1,..,5,n=4,L=500) Figure 2.21 Retransmission probability for Scheme 3S 43 (M=3,n= 1,...,5,L=500) Figure 2.22 Retransmission probability for Scheme 4S 46 (M= l,..,5,n=4,L=500) Figure 2.23 Retransmission probability for Scheme 4S 46 (M=3,n= 1,...,5,Lz-_500) Figure 2.24 Retransmission probability for Scheme 5S 47 (M= 1,..,5,n=4,L=500) Figure 2.25 Retransmission probability for Scheme 5S 47 (M=3,n= 1,...,4,L=500) Figure 2.26 Retransmission probability for Scheme 6S 49 (M= 1,..,5,n=3,L=500) Figure 2.27 Retransmission probability for Scheme 6S 50 (M=3,n= 1,...,4,L=500) Figure 2.28 Retransmission probabilities for Schemes iS to 6S 51 (M=2,n=3,L500) Figure 2.29 Retransmission probabilities for Schemes 15 to 6S 51 (M=3,n=3,L=500) Figure 2.30 Retransmission probabilities for Schemes 2H to 6H and 2S to 6S (M with n = 4, L = 500 = 3) 52 Figure 2.31 Retransmission probabilities for Schemes 1H to 6H against L (n=3,M=1,SNR=8dB) 53 Figure 2.32 Retransmission probabilities for Schemes iS to 6S against L 53 (n=3,M=3,SNR=8dB) Figure 2.33 Retransmission probabilities for Schemes 15 to 6S againstL 54 (n=4,M=3,SNR=8dB) Figure 3.1 Throughput for Scheme 2S (M= i,2,3,4,L=500,q=1,S Figure 3.2 Figure 3.5 = 1000) 59 1000) 60 (M= 1,2,3,L=500,q=1,S =1000) 60 = Throughput for Scheme 5S Throughputs for Schemes 1H to 5H (M= 1,L=500,q=1,S Figure 3.6 59 Throughput for Scheme 4S (M= i,2,3,L=500,q=1,S Figure 3.4 1000) Throughput for Scheme 3S (M= 1,2,3,4,L=500,q=1,S Figure 3.3 = = 1000) Throughputs for Schemes 15 to 5S (M=2,L=500,q=1,S=1000) Figure 3.7 61 Throughputs for Schemes iS to 5S (M=3,L=500,q=1,S=1000) Figure 3.8 61 62 Simulated Throughputs for Schemes 3H and 6H (L = 500, q = 1, S = 62 1000) vii List of Tables Table 1.1 Summary of the six combining schemes Table 2.1 Optimum Thresholds (Normalized to A) and weights forM Table 3.1 = 2,...,5 SNR , = 8 dB, and n = 5 (adapted from [181) 57 Optimum number of copies for Schemes 2S to 5S with M=2,q=l,S=1000,L=500 Table 3.3 57 Optimum number of copies for Schemes 2S to 5S with M—_3,q=1,S =1000,L=500 Table 3.4 36 Optimum number of copies for Schemes 1H to 6H with q=1,S —l000,L=500 Table 3.2 8 58 Optimum number of copies (simulated) for Scheme 6H with 58 q=1,S =1000,L=500 wil Acknowledgment I would like to thank Dr. Cyril Leung for his supervision and enlightening teaching and advice. I also thank my colleagues Richard Cam, S.W. To, Kenneth Wong and Victor Wong for their helpful support during the year. This work was partially supported by NSERC Grant 0GP0001731. x Chapter 1 Introduction 1.1 Conventional ARQ Schemes In order to transmit messages reliably in a data communication system, error control strategies have to be used [1-22]. In many systems, data are sent as a sequence of packets of fixed size. The packets are to be delivered to the destination in the same order in which they were sent. During transmission over the channel, noise is introduced; this results in bits of the received packets being possibly altered. To achieve transmission integrity, the receiver should be able to detect these bit errors. Typically, a cyclic redundancy check (CRC) code is used [23,24]. If no error is detected in a data packet, the receiver sends back a positive acknowledgment (ACK). Conversely if errors are detected, a negative acknowledgment (NACK) is returned to the transmitter. The transmitter wifi retransmit the packets that were negatively acknowledged or have not been acknowledged after a predetermined time interval. 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 repeat 1.1.1 Stop-and-Wait ARQ In Stop-and-Wait ARQ [4,5] (Figure 1.1), the transmitter sends a single packet and then waits for an acknowledgment (ACK). It does not send any other packet until it receives an ACK or NACK from the receiver or a time-out period expires. If a packet error is detected by the receiver, it discards the packet and asks for a retransmission by sending a NACK. Upon receiving the NACK, the transmitter re-sends this packet. To 1 2 Chapter 1. Introduction cope 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 retransmit the unacknowledged packet again. Hence this system requires the source to store a single copy 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 data packets continuously; such a scheme is referred to as continuous ARQ. * idle time error N - NACK A ACK - Transmitter Receiver idle time Figure 1.1 Stop-and-wait ARQ 1.1.2 Go-back-N ARQ One continuous ARQ scheme is go-back-N (GBN) ARQ [4,7-10). With GBN ARQ, it is not required that each individual packet be acknowledged. As shown in Figure 1.2, the transmitted packets from source to sink are numbered sequentially, and this sequence 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. 3 Chapter 1. Introduction The destination sends request numbers RN back to the source requesting packet RN and The number N in a go-back-N protocol is a acknowledging all packets prior to RN. parameter that determines how many packets can be outstanding (i.e. sent without being acknowledged). The performance of GBN ARQ is better than that of stop-and-wait ARQ. If an error occurs in packet X, the receiver will send back the sequence number of X as RN and ignore all incoming packets until a correct copy of X is obtained. On receiving RN, the transmitter goes back to the packet numbered RN and re-sends it as well as 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 packets is needed. If buffer space is available at the receiver, the efficiency can be improved by using a selective-repeat (SR) ARQ scheme. * error N - NACK A ACK - Transmitter Receiver ignored Figure 1.2 Go-back-N ARQ. 4 Chapter 1. Introduction Transmitter Receiver * error N- NACK A-ACK Figure 1.3 Selective Repeat ARQ 1.1.3 Selective Repeat ARQ In selective repeat (SR) ARQ [1 1,12j as shown in Figure 1.3, the receiver will accept out-of-order packets and request retransmissions from the source only for those packets that contain errors. However, the receiver theoretically requires an infinite buffer in order to rearrange the received packets in correct order before delivery to the user. The throughput of the ideal (infmite re-ordering buffer) SR ARQ scheme, T, defmed as the average number of packets received correctly per transmitted packet, is given by T = 1 — F’ where F is the retransmission probability for a single packet. In practical systems, there is a window size which specifies how many outstanding packets are allowed. When this limit is reached, the source can wait for some time out or immediately start retransmission than 1 - F• of unacknowledged packets. The actual throughput is hence smaller Although by making the window size large enough, the probability that the 5 Chapter]. Introduction number of outstanding packets exceeding the window size can be made very small, there are two difficulties with very large window sizes. The first is that storage must be provided at the receiver for all of the accepted packets. The second is that a large number of 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 to retransmit the same packet several times in succession if the previous transmission contained errors. A multiple copy retransmission scheme reduces the retransmission probability and the delay variations, but is not as efficient. However, the number of retransmitted copies can be chosen in such a way as to optimize the throughput of the system. 1.2 An Improved Selective Repeat ARQ Strategy In 1982, Weldon [13} described an ARQ scheme for which the throughput compares very favorably with those of previously described schemes. Basically, it is a multiple copy retransmission scheme in which the number of repeats is optimized. In 1984, a modification to the Weldon ARQ scheme was proposed in [14j; this allows for multiple copies to be transmitted at the beginning and can improve the throughput T significantly. Let S be the number of data packets which can be sent by continuous transmission during the time between the start of the transmission of a packet and the receipt of a ACK or 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 data packet F is transmitted as follows: Initially, F is at level 0 and is transmitted for the first time. If an ACK is received (S packet times later), the transmission of F is complete. If a NACK is received, F moves to level]. 6 Chapter 1. Introduction F is repeated n 1 copies is ACKed, the transmission 1 times. If any of these n Level]: 1 copies are NACKecI, F moves to level 2. of F is complete. If all n F is repeated n 2 copies is ACKed, the transmission 2 times. If any of these n Level 2: opies are NACKed, F moves to level 3. n c ofF is complete. If all 2 This procedure is continued until level q is reached. Level q: - At this point the receiver buffer is considered full even though it may not actually be full because of repeats of other erroneous packets. assumption leads to a simple analysis. Here F is repeated copies are NACKed, F moves to level q + Let [3 = times. If all flq flq 1. Level q+]: Buffer overflow occurs, leading to the loss of (S nq This - 1) packets. F is repeated times and stays at this level until it is successfully received. lIT be the average number of transmissions required to send one packet successfully. From [14] we have q i—i q (nq+S_i)Pj.° k=Ok + i=0 For given values of q, S and F’ lPf (1.1) 1 the number of copies to be sent {n } can be chosen so as to minimize [3or equivalently maximize T. In [14], a detailed analysis for the optimum values of } is given and is reproduced in Appendix A for reference. 1.3 Memory ARQ In the above mentioned ARQ schemes, a data packet is discarded if it is found to contain 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 combining copies of received packets bit by bit, the retransmission probability F can be reduced. Chapter 1. Introduction 7 These 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 Weldon ARQ scheme [13,14,22]. 1.3.1 Combining Schemes In 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 more copy is correct, transmission of the packet is successful. In the event that all n copies are erroneous, we have a decoding failure and retransmission is required. In Scheme 2, all n copies are combined to a single one by using hard or soft detection and error detection is then performed on the combined packet. Decoding failure results if this combined packet is found to be erroneous. By implementing both Scheme 1 and Scheme 2, we obtain Scheme 3. In Scheme 3, error detection is performed on the n individual copies first. If all copies contains errors the n packets are combined into one and error detection is performed on it. Decoding failure results if all the n packets and the combined packet are erroneous. In Scheme 4, each newly arrived packet is combined with all the previously The first received and the following (n received packets. - 1) combined packets are checked in turn for errors. Decoding failure results if the first packet and all the combined packets are erroneous. Scheme 5 uses both Scheme 1 and 4. When a new copy arrives and is found to be erroneous, it is combined with the copies received so far and error detection is performed on the new combined packet. Decoding failure results if all the n packets and the (n - 1) combined packets are erroneous. Finally in Scheme 6, error detection is performed on all 2” —1 possible combinations of the received packets. Therefore, it has the lowest retransmission probability among all the schemes described so far. The six schemes are summarized in Table 1.1. 8 Chapter 1. Introduction Schemes Perform Decoding on 1 n Individual copies 2 Single sum of n copies 3 Scheme 1 + Scheme 2 4 Sumsofl&2,1&2&3,andsoon 5 Scheme 1 + Scheme 4 6 All the 21z +1 combinations of the packets Table 1.1 Sununary of the six combining schemes It is assumed in this thesis that no packets are lost during transmission so that combining of all copies is possible. 1.3.2 Detection Methods The receiver can use either a hard-decision or soft-decision demodulator. The hard-decision demodulator makes a hard estimate on the received signal. A 1+1? is assigned 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-decision demodulator, a reliability weight is assigned to each received bit depending on the quantization region the received signal amplitude falls into. Theoretically, the finer the quantization regions of the system, the better the performance will be, albeit at the cost of increased decoder complexity. A system with infinitely fine quantization levels is referred to as completely soft or perfectly quantized. In this case, the decoder can use the exact value of the received signal amplitude for combining purposes. The six combining schemes have been previously considered by a number of authors. Scheme 2 is used with n = 5 and single error correction for data transmission in Chapter]. Introduction 9 the 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 and optimized in [18], which in particular, showed a numerical procedure for evaluating F of Scheme 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 6 was given in [21]. 1.4 Organization of thesis In this thesis, we will consider the application of all six combining schemes in an ARQ system. The Weldon ARQ scheme is of special interest since it uses a multiple copy transmission strategy. In chapter 2, we consider the retransmission probability of the F combining schemes using hard, soft and perfectly quantized detection methods. Analytic expressions for the F of Schemes 1 and 2 for hard detection can be easily obtained, while the F for soft detection of Scheme 2 was derived in [18]. Here, new expressions for F of Scheme 3 for hard, soft and perfectly quantized detectors are derived. Analytic of Schemes 4 to 6 appear to be difficult to obtain. Instead, expressions for the F numerical procedures for evaluating them are described. We then compare the resulting throughputs after applying the six combining schemes to the Weldon ARQ scheme in chapter 3 with the throughput of Scheme 6 found by simulation. Finally, the main results of the thesis and some suggestions for future development are included in chapter 4. Chapter 2 Analysis of Retransmission Probabilities In this chapter, the retransmission probabilities F for a number of different combining 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] as shown in Figure 2.1. It is assumed that no errors occur in the feedback channel. For simplicity, it is also assumed that the error detecting code used is able to detect all channel error patterns; this is not an unreasonable assumption in practice [26]. The transmitter operates as in a conventional ARQ system. Every transmitted data packet is stored until an ACK signal is received. Suppose that the data packet to be transmitted is denoted by ...,SL) where Si (SI,S , 2 e{O,i}, i=l,2,...,L. Then the input to the vector channel is ...,XL) where: X=(Xl,X , 2 Figure 2.1 Block diagram of the memory ARQ system (adapted from [18]) 10 11 Chapter 2. Analysis ofReransmission Probabilities 1 -TM -7 2 -T 2 —R —RM 2 W WM —WI T 7j 0 TM1 1 R 2 R R 1 W 2 W WM Figure 2.2 Weights and Thresholds distribution. (A = 1 ifs = 1 —A S =0 (2.1) At the receiver, the output of the matched filter y transmission of x is (Yj,i Yj,2 i... Yj,L) where = corresponding to the jth 1 , and fd 1 1 +d x }, I i L, 11 is 2 Each y j = 1,2,... represent independent Gaussian noise samples with variance a then assigned a reliability weight according to equation (2.2) and is also shown in Figure 2.2. , > TM_I 1 y +WM , T y 2 T > 1 ,>O T y 1 — — 1 wi, 1 —w 1 > —T —TM_I > WM where there are 2M weights f—wp..j f—TM_i ,—TM_2 ,... 1 ..,TM_i}. ,0,T ,. ,WM_1 For M = 2 —T (2.2) ‘i,1 ,WM } and 2M -1 thresholds 1, the output of the matched filter is quantized into two regions only, resulting in a hard decision demodulator. If the number 12 Chapter 2. Analysis ofRetransmission Probabilities of quantization regions exceeds two, that is M > 1, the demodulator is a soft decision demodulator. A completely soft decision demodulator is one in which the matched filter output is perfectly quantized (infinite number of quantization regions). With weights assigned to each received sample YJA’ the L-bit packet can be represented by the vector w ,w = ,... which is used in the reliability ,wJL) , I 1 updating process. Here a decision accumulator z I the data packet. Prior to the reception of a packet, we set L, is maintained for each bit in = 0, 1 I L. After thejth reception 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 from uj,i — 11 O 1 ify 0 if <0 (2.4) and _11 ifz,O 0 , <0 1 if z — 1 In the case that zj = 0, (2.5) is set to either ?1? or ‘0’ completely at random. The above configuration is applicable for Scheme 1 to 5. For Scheme 6, the modification is as follows: 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 (all possible combinations) and decoding for the combined packets are performed whenever a new copy of the packet arrives. Hence it has to perform 2 — 1 packet combining and decoding when I copies of the packet are received, while Scheme 5 has to perform a single combining and 2 decoding processes only for each newly received copy. Hence implementing Scheme 6 requires a much larger computational effort than all the other schemes, especially when j becomes large. 13 Chapter 2. Analysis ofRetransmission Probabilities 2.1 Hard Decision Schemes 1 denote the retransmission probability for Scheme iH, I P Let 1 = 1,.. .6, where H indicates the use of hard detection with PSK modulation and an AWGN channel. The 1 Y probability distribution function (pdf) of Y when a ‘1’ has been sent and the pdf of 1 when a ‘0 has been sent are shown in Figure 2.3. If a 1? was sent, the probability that 1 <0 is given by Y, 1 which is equal to Pr{Yj The function, Q(a) 1 Prfr <01 o’ c’ was sent} t , Q(J was sent} = (2.6) p’ the bit error rate (BER) of the channel. [25] is defined as Ie2dx a (2.7) • pdf 1 (y) ,i 1 p PIIO (y,) -A 0 Figure 2.3 Probability Distribution function A of Yjj. y 14 Chapter 2. Analysis ofRetransmission Probabilities 2.1.1 Scheme 1H The retransmission probability for Scheme 1H is given by 11 1P = Pr fall n packets are hard detected incorrectly} = [Prfa packet is hard detected incorrectly}]?Z = [i = [i — — 1 Pr{a packet is hard detected correctly}j’ 7 Pr fall L bits of a packet are correct}]’ =[i_(i_p)UJZ (2.8) A plot of 1H (A/) for n 10 201og = against the signal to noise ratio (SNR) in dB defined as l,2,...,7 and L = 500 is given in Figure 2.4. For a given SNR, 1H decreases with the number of copies as to be expected and it is shown in Appendix D that 2 for p 11 decreases as p’ 1P n = << for To achieve a retransmission probability of 1. 4, Scheme IH requires an SNR of approximately 10.6 dB. 0 10 ic -2 10 I ‘N’S” \\ n=7 n=6 n=5 - - 7 — — - — — N• - — ii=4 n=3 n=2 n=1 S 11 10 9 SNR (dB) Figure 2.4 Retransmission probability for Scheme 1H (n = 1,2 7, L = 500) Chapter 2. Analysis ofRetransmission Probabilities 15 2.1.2 Scheme 2H The retransmission probability for Scheme 2H is given by ‘211 = Pr{the combined packet is hard detected incorrectly } = 1 = 1 —[Pr{a bit of the combined packet is hard detected correctly}}’ = 1 — — Pr{the combined packet is hard detected correctly} [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 with bit 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 known (n,p,rn) is given by 1 to be correct, the value of rn is 0. For n odd, P, (n, p,rn) = fn+1 or more errors in n Pr 1 2 — m unknown bits = n+1 (2.lOa) Similarly for n even, we have n-rn P,(n,p,m)= [ n—rn . _)n_m_i 1 J( n—rn . . ]P21 —p) m n/2 (2.lOb) where the last term on the R.H.S. of (2.lOb) accounts for the event of an equal number of correct and incorrect bits. In such a case, the decoder breaks the tie based on the outcome of a fair coin toss. Also note that for odd n. (n, p,rn) = 0 when rn > - for even n or rn> 1 16 Chapter 2. Analysis ofRetransmission Probabilities 0 10 —— --.. — -1 .-....-.- —.-.- .. 10 10 ...•.... ‘ -3 o 10 .4 N, 10 o . . \ 1 -7 n=7 10 - — — \ - \ - n=3 n=1 4 10 - 0 I I I I I 1 2 3 4 5 I 6 7 I 8 I 9 10 SNR (dB) Figure 2.5 Retransmission probability for Scheme 2H (n A plot of 2H against SNR for n = = 1,3,5,7, L = 500) 1,3,5,7 is given in Figure 2.5. In Appendix D, In+1I it is shown for the same for n r’ << l = 21 - “211 decreases as L 1 and 21 where / = 2 211 In fact, as shown in Figure 2.5, p 1,2,3,... [19]. As n increases, 2H decreases as expected. To achieve a retransmission probability of i0 for n = 4, Scheme 2H requires an SNR of approximately 10 dB. 2.1.3 Scheme 3H For Scheme 3H, let j 1, 2, ..., n denote the event that the jth copy of the packet is correct and BH denotes the event that majority voting on the n copies results in correct packet decoding. Then uB 1 PrfA 11 ...uA } 3 P =1— u 2 A 1 1 (2.11) 17 Chapter 2. Analysis ofRetransmission Probabilities By expanding the union of events [25j, we get “3H Pr{AA}— =1_Pr{A}+ 1j<kn j=1 } PrAB —Pr{BH + j=1 Pr{AJAkAl}+...+(—1)’Pr{Al...Afl1 1j<k<ln } 2 A 1 Pr{A Pr{AJAkBH }+. — A,Bq } 1j<kn (2.12) }, 1 Since the events {A j = 1,2,. . ., n are independent, ”PrfAj} ..A . 2 A Pr{A } 1 } =Pr{Ai}Pr{A = {PrfAi }]‘ —(l—p) (2.13) and Am} }...Pr{Am}Pr{BHIAIA 2 Pr{Al}Pr{A Pr{AIAZ...AmBH}= ” m Pr{BHIAIA =[Pr{Ai}] ...Am} 2 = (1 _p)”[1 — P,j(n,p,m)]’ (2.14) Using (2.13) and (2.14) in (2.12) yields = ()L +[)(l_p)2L [J)3L(1)flflJ(1)nL H 3 _[i _p(o)]L _[;)[(1 - = [i +n[(1 -P ]L] _.( ) _p)L[i 1 (n,p,2)]L )k+1 1 _)L]’ + (_ 1 _( - ]+.. j[(i _p)k{i )flL [i - p. ()jL] —P, (n,p,k)]]L. (2.15) 18 Chapter 2. Analysis ofRetransmission Probabilities 0 10 >.. -2 10 -3 SNR(dB) Figure 2.6 Retransmission probability for Scheme 3H (n A plot of 3H against SNR for n for values of SNR below 8 dB, 1 = 3H = = 1,2,...,6, L = 500) l,2,...,6 is given in Figure 2.6. We observe that are very close for values of n 1,2,..., and it is shown in Appendix D that for p = 21 - 1 and 2/, has the same behaviour as << that of Scheme 1H and decreases as p’. To achieve a retransmission probability of iO for n = 4, Scheme 3H requires an SNR of approximately 9.4 dB. 2.1.4 Scheme 4H and 5H For Schemes 4H and 5H, let B’H , j = 1,2,.. .,n denote the event of successful packet decoding after majority voting on the first i copies. Then = 1 UB l-pr{A HU-..UB,H} 2 (2.16) and , B IUA PrfA } flU =1—.UB ...A U.. 7 PSH U H 2 H (2.17) Chapter 2. Analysis ofRetransmission Probabilities 19 These expressions can be evaluated by expanding the union of events, as done in the case of Scheme 3H. The probability of each joint event in the union expansion can be 2 1 Let E evaluated numerically as follows. (of m events), where E E 1 {A , 2 A ,. . . , - Em 311 A, B H B 2 , , denote such a joint occurrence ,. . . , B, } and denotes the event that 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 equiprobable , 1 events fe i = ,. . ,eJ }, we have Pr{E } . }]L, = [r{ej where Pr{ej } Pr{ej,j = } for s can be written as 1 3 l,2,...,L. Similarly, the joint occurrence of a set of E le ..em}]L ...Em}=[Pr{e 2 E 1 Pr{E . 2 em e 1 The probability, Pr{e •- (2.18) }, can be evaluated by exhaustively enumerating all the error events in the bits that are relevant to that event and summing the corresponding 4 3 2 1 probabilities. As an example, consider the event E of n = A B for the case 5 H 3 B 1 A H 4 and b H denote respectively the event of A and BJH at a 3 Let 8 copies. = particular bit position. Define the bit error indicator ij as = f1 if there is no error at a given bit position in packet j O, otherwise. (2.19) Then, A B 5 H 3 B 1 Pr{A H 4 } = 11 a 3 1 [Pr{a 4 b 5 L 1 } (2.20) where 11 a 3 1 Pr{a 4 b } 5 ±± = i aib a ii Prfii ±Pr{ n b 311 i } 2 } 5 4 3 i 0i O 2 =0i 3 = 4 = i1 5 5 5 1 1 1 1 5—si, 1 p = 0i O 5 1 2 3 = 4 = i’ (2.21) 20 Chapter 2. Analysis ofRetransmission Probabilities The conditional probabilities are given by } 5 b a ...i il 5 H 3 Pr{alb H 4 I = 1 Pr{a }Pr{a fri ...i Iil 5 Iii 4 }Pr{b 5 ...i n Pr{b 5 ...i H Ii 3 (2.22) where =ij Pr{ajlii...i } 5 (2.23) and = Pr{bJHfrl...i } 5 if - 0 , otherwise. (2.24) if Thus, bit the b a ili 2 H Pr{alb H I 5 4 3 i Plots of respectively. 4H and = error ioioi} 5H = lxi x!xi = values take indicators 5 4 3 2 1 i = 10101, I against SNR for n = l,2,...,6 are given in Figures 2.7 and 2.8 It can be seen that for Schemes 4H and 5H, the relative percentage difference in retransmission probability for values of n = 21 - i and 21, 1 = 1,2,..., is larger than that of Scheme 3H. This percentage difference is noticeable even at low values of SNR. To achieve a retransmission probability of for n = require SNR’s of approximately 9.5 dB and 9.1 dB respectively. 4, Scheme 4H and 5H 21 Chapter 2. Analysis ofRetransmission Probabilities 0 10 - ._ 5___• - - _ _- — ‘-.5--.---5-.----- ---5- -1 in -.5.5-—- ‘--S.--.-- - -S.. ‘-S.. -2 -S. .55-S-S —-S ‘555 ‘--.5. •%.-‘5.,. ‘%_._._•.. -3 10 I 5.- ‘____5. 10 - 5s -5- ‘---S..-. .5%..-- n=6 n=5 n4 0=3 n=2 n=1 - -5 10 - 10 - —j 1 2 \‘\ — — — N \•*.. —-—-—-— I I I I I I I 3 4 5 6 7 8 9 10 SNR (dB) Figure 2.7 Retransmission probability for Scheme 4H (n 10 - 5555 .5-.. -5 • S.. -3 10 - 10 6, L = 500) _-S%.5_.•.. 10 o 1,2 —.5--- —---. -2 ‘p = ‘.5 S -S-S. -S-.. 4 -5 f) 10 n=6 _“5 — — — s \“• 10 - -. I— 10 - n=2 n=1 4 10 2 3 I 4 I I I 5 ,6 7 8 9 SNR(dB) Figure 2.8 Retransmission probability for Scheme 5H (n = 1,2 6, L = 500) 10 Chapter 2. Analysis ofRetransmission Probabilities 22 2.1.5 Scheme 6H Scheme 6H attempts majority-vote decoding on all 2’ —1 possible combinations of the n received copies. Let D k , = —1, denote the event of successful majority- 1,.. t by the binary expansion of k as follows. Let the vote decoding using the copies ‘selected binary expansion of k be expressed as k where cj E {O,l} , = 1 c (2.25) j= Then the jth copy is used in D if and only if c = 1. The retransmission probability is given by 1 UDWE4, kt4 J (2—1 H=l—Pr’ 6 P (2.26) where the union of events can be expanded, as done in cases of Schemes 3H to 5H. Each term in the corresponding union expansion can then be evaluated in a manner similar to the procedure described for Schemes 4H and 5H. Let d denote the event of D at a particular bit position and consider the event D HD3HD17HD22H for the case of n 1 = 8 copies. D HD22H 1 Pr{D H 3 7 } = dl jd 22 H 3 [Pr{dlHd j 7 H 1]’ (2.27) Since the highest value of the subscript in { D } is 22, the number of bit error indicators required is5 since 2 22<z2. d dl 22 H 3 Pr{dlHd H 7 H J = ±... ± =O 1 i Pr{dlHd3Hdl7Hd22H 5 4 3 2 i 1 1u112131415 pr{i =O 5 i 5 5 1 = 1 2 15=0 5—i ij p =O 1 i (2.28) 23 Chapter 2. Analysis ofRetransmission Probabilities The conditional probabilities are given by 5 dl d ‘i-. i 22 H 3 PrfdlHd H 7 H = pr{dlH 1• } } .15 Pr{d Hil. 3 . .15 Hjil. .15 }, 22 HIil. 7 } Prd } Pr{dl . .15 . (2.29) where 5 Cj 1 if 2 j=1 5 cj 5 if c ij 3 0 =‘ , otherwise. (2.30) SNR (dB) Figure 2.9 Retransmission probability for Scheme 6H (n = 1,2,3,4, L = 500) 24 Chapter 2. Analysis ofRetransmission Probabilities The computational complexity of the numerical procedure described above grows rapidly 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 would be unacceptably low. A plot of 6H against SNR for n = 1,2,3 and 4 is given in Figure 2.9. The relative percentage difference in retransmission probabilities for values of 1 = 1,2,..., is even larger than that of probability of i0 for n = Scheme 5H. n = 21 - 1 and 21 where To achieve a retransmission 4, Scheme 6H requires an SNR of approximately 8 dB. 2.1.6 Comparison of hard detection schemes The retransmission probabilities of Schemes 1H to 6H are plotted in Figures 2.10, 2.11 and 2.12 for n = n = 2, 2H 1 and n n = 2,3 and 4 respectively. From Figure 2.10, it can be seen that for is the highest among all the schemes. This is because = 2. Besides, significantly lower than PIH, 3H’ 5H P4Jf and 6H 2H is the same for are nearly the same and all of them are which is slightly lower than itself. 2H 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 values 311 is lower than below 8 dB. It was found that P lH 2H 511 lies between lowest as to be expected. Finally, P 3H From Figure 2.12, for n = and and while P 611 is the 6H• 4, we observe that the relative percentage difference in retransmission probabilities among the schemes is much larger than that for n = 3, 311 for SNR especially between Scheme 6H and the others. Besides, P is lower than P above 9 dB. Although Scheme 6H always has the lowest retransmission probability, the computational effort required to implement Scheme 6H is much larger compared with those for the other schemes as small values of n only. n increases. Hence Scheme 6H is suitable for systems with 25 Chapter 2. Analysis ofRetransmission Probabilities -o 10 •1 10 -2 10 - 10 -4 10 . 10 -6 10 . .7 10 -8 10 6) 10 • -10 10 —11 10 5 6 7 8 9 10 11 13 12 14 SNR (dB) Figure 2.10 Retransmission probabilities for Schemes iN to 6H (n = 2, L = 500) 0 10 —1 10 I -2 10 -3 10 -4 10 SNR(dB) Figure 2.11 Retransmission probabilities for Schemes 111 to 6H (n = 3, L = 500) 15 26 Chapter 2. Analysis ofRetransmission Probabilities 0 10 .. .a - 1—’ .2 10 -3 10 0 4 10 I 10 9 8 7 6 5 SNR(dB) Figure 2.12 Retransmission probabilities for Schemes 1H to 6H (n = 4, L = 500) 2.2 Completely Soft Decision Schemes p denote the retransmission probabiitiy for Scheme iP using perfect 1 Let P quantization with i = 1,. ..6, where P indicates the use of perfectly quantized detectors. In this case, (2.3) can be written as = z_ + Yp f 1,2,... ,n I = 1,2,... ,L. (2.31) 2.1.1 Scheme 1P Since packet combining is not performed in Scheme 1P, the retransmission probability for this scheme using perfect quantization will be the same as that using hard detection and is given by iP “IH (2.32) 27 Chapter 2. Analysis ofRetransmission Probabilities 2.2.2 Scheme 2P The retransmission probability for Scheme 2P is given by = Pr { the combined packet is detected incorrectly } 1 = 1 — — Pr{ the combined packet is detected correctly} [Pr{a bit of the combined packet is detected correctly}]L r L 1 2pJ = P [ 1 (2.33) where P2P is the effective bit error probability of the combined packet using perfect quantization. Since Y are Gaussian random variables, Zn_rn,j is also Gaussian. The variance of i = 1,2,...,L, is the sum of variances of Y, j = 1,2,...,n, i.e. . 2 na The 1 is given by nA. Therefore the effective bit error probability is given by mean of Z,, (%ThA P2PQI a (2.34) Thus the net effect on the bit error rate of combining the n copies is equivalent to that of using a signal whose power is n times that of a single copy. 2.2.3 Scheme 3P Let B denote the event that completely soft detection on the combined n copies results in successful packet decoding. Then P3p = 2 u uA u B 1 UA 1— Pr{A } (2.35) By expanding the union of events, we get + 1_Pr{A 1 p 3 P } Prf AB Pr{Bp}+ j=1 PrfAJAkAI}+...÷(—l)’Pr{Al...Afl} 1j<k<ln 1j<kn j=1 — Pr{AJAk}— } — Pr{Aj AkBP • 2 1A .+(—iY’ Prf A . AB} 1j<kn (2.36) 28 Chapter 2. Analysis ofRetransmission Probabilities 2 A 1 Since each event A 1 is independent, Pr{A • A) is still (1 . — Letting b be the event of B at a particular bit position, we have } 2 ABp = {Pr{aia 2 A 1 Pr{A abp}] = [P(nm)]L where P. (n, m) is the probability of successful decoding using a given set of m copies and the combination of all n packets at a particular bit position. Assuming a packet of all has been transmitted, 2 1 =Y 11 + Y this corresponds to Z,, +• +Y, > 0 tit for a given , > 0,..., and ‘mi > 0. Therefore, 2 I e [l,2,...,L} and Y1,L > 0,Y Pc(n,m)=Pr{Yi,1,Y2,i,...,Ym,i >0 andZn,j >o} { 1 Y Pr Y 1 2 , ,. . , m,i > 0 and ‘k,i > } ii ,...,Ymj >0 and PrYij,Y j =2 k=m+1 I. m > k=1 = Pr{YiiY ,i...Ym,i >0 and Gn_m,i > _Yk1} 2 k=1 where Gn_m,i = k,i’ k=m+1 is the sum of (n m) Gaussian random terms Yj. The variance - of Gn_m,i is the sum of the variances of Y, namely (n (n — (2.38) — . The mean of Gn_m,i 2 m)a m)A. The pdf of Gn_m,i is thus given by j g_,,—(n—m)A f PGn_mi n_n,1) 2 1 = ,J(n_m)G2 2 (2.39) 1 , 2 , Y 1 Hence, the joint pdf of Y , , . . , Ym,j and Gn_m,j S 29 Chapter 2 Analysis ofRetransmission Probabilities Ym,i,Gn_m,i (yi,i,...,ym,i,gn_m,i) 2 2 i(yj—A —1 J 1 Ue J gn_m,i(u1m)A 1 2 2 Jm)a e 42(n_m)o2 k1 (2.40) From (2.38) and (2.40) we can write P (n, m) = Yi,r $ Ym,i }‘m,j,Gn_m,j1,j.)’m,j,nm,j) — dg,j dym,i”dYi,i Yk,L k=1 ( 1 1 Yk —A m 14e2( ‘ 1 g,_,,i—(n—m)A 2 e doon-m,j. dvJm,j. — 8n-m,iLYk,i k=1 d.1,j (2.41) YkiA Letting Y kj = t ‘ , ii m,i•—(n—m)A = g_ k = 1,...,m and ,we have .J(n_m)a2 a P(n,m) (IL) = , = $ ii a $ = Yjj $ Lk) ... y’mi ‘ a g n-m,i y m” y 2 fle2” —1 $(, , g n—m—.—;\Ly k,i Y’k,i A a Y’m,i 1, 1,2 mm fle m A ‘A, Ym,z flmi=Yki+__] mm 2 421t(n_m)a2 Ld27ta2) 0 Ym,i Yi,° 1 2 2 i,i 1 I ) dg n-m,i Y 1 Y m,i” 1 +)) 1,i 1 dY’m,i •-dy’ a (2.42) 30 Chapter 2. Analysis ofRetransmission Probabilities The numerical procedures for evaluating F (n, m) are given in Appendix B. With p can be expressed as 3 F(n,m) defined, P p =1 -n(i 3 P - )L _[(,o)]L = + ;)(l + n[(n, [i_ (1- )L ] + ( )2L - (](l i)JL - 1)k+1 )3L - .+:)1 - 2)]L+.. +(_l)n+1 (n, k)JL. (2.43) k=O p = 1 —[P(n,O)]’. 2 Note that for Scheme 2P in (2.33), P2p = 1— P(n,O) and P 2.2.4 Schemes 4P, 5P and 6P B j = 1,2,.. .,n, denote the event of successful packet decoding on the , Let 1 = combined packet using the first j copies and DkP, k l,...,2’ —1, denote the event of successful decoding using the copies selected’ by the binary expansion of k as described in section 2.1.5. For Schemes 4P, 5P and 6P, the corresponding retransmission probabilities are given by B _1_Pr{A u.”uB,p} 2 4 P u 1 p p 5 F pu...uB,p} 2 ”•uA uB uA u lPi{A 2 ‘6P (2.44) (2.45) 127z_1 =l—Pr UD k=1 (2.46) and can be evaluated by expanding the union of events, as done in the case of hard detection, with the exception that each joint event in the union expansion is an integral similar to (2.42). Using the same example as in section 2.1.4, consider the event 5 for the case of n = 8 copies. Let 4 3 B 1 A 3 at a particular denote the event of B bit position, we have a b 5 p 3 b 1 [Pr{a p A}=4 B 5 p 3 B 1 Pr{A P 4 }]L (2.47) Chapter 2. Analysis ofRetransmission Probabilities 31 Similar to the derivation of P (n,m) in (2.38-2.42) above, b a 5 p 3 b 1 Pr{a p 4 } 54 Pr{a b } 3 b 1 }Pr{a p pb 3 b 1 Pr{a p (1— p) 4 } (2.48) and >0) , +G 1 21 >0 and Y 1+ , 2 1 >0 and Y Prfr 1+G = where G 21 = pr{yi,i > , )J 2 —( + G , 1 ,> 4 —Yi, and Y (2.49) (2.49) can be written as ,+ 2 Y b } 4 3 b 1 Pr{a p 1 , 2 0 and G > o} 1 +Y , 3 , > 4 +Y 1 +Y , 2 , +Y 1 31 >0 and Y , >0 and Y 1 b } = PrfY 4 3 b 1 Pr{a p 1+ = 1 1 e03 g =—(y 2 , 4 y + ) 1 1 , =—y 2 g y,=O 4 dg 4 1 dy dy 21 (2.50) Let Y’k, = Yk ,1 -A , b 4 p 3 b 1 Pr{a p — Yi = 1 k = 1 and 4, and 3A s = $ Y’i, , we have } 1’ j=—y’i,i) ,g’ 2 f 1,2 1 e —jY li 1 1,2 e —g 2,i 4A t dy Y’4,I=—(Y 1J+’2+—) 00 = g 2,i•-2A g2, 1 1 2 2 ——g 2 ‘ 2 Q(_[Y’i, +g’ 1 e 1,2 Y 4,i 1 dg’ 2,i dy’ j dy’ +])dgt , 2 11 1(3A) 1,1 +g’ 2,i +]g’ 2,i dy’ 1j (2.51) 32 Chapter 2. Analysis ofRetransmission Probabilities Hence 5 a 4 3 b 1 Pr{a } = (1 —p)Pr{a } 4 3 b 1 !(yj2+gj2) i2 2 e f A i(, Q(_[Y’ ij 21 + +gt 3A’ J dg’ 2,1 dy’ a)I ,=—y +— 2 Yi,i—- g (2.52) For Scheme 6P, the lower limit of the integrals may happen to be 5 for the case of n 3 example, consider the event of D = -oo. For 3 copies. Letting d be the event of DkP at a particular position, we have pD 3 Pr{D p 5 } pd 3 Pr{d p 5 } [ = p 5 Pr{dpd }]L (2.53) = 31 11 + Y Pr{Y 21 >0 and Y + Y = Pr{ > 1 , 3 , and Y 1 —Y > , 1 —Y > o} } (2.54) Using a similar approach to (2.51), we have } 5 d 3 Pr{d = j___ = _) 1 2 e Q ( ‘ 2A) 1 dy’ a (2.55) —y’ lj in the first integral on the R.H.S., (2.55) becomes } 1 ——Y’i.i 1 fe 2 1 2A 2 dy’ a 2A’ 2 a) $e+112Q(_yt. pd 3 Pr{d p 5 = QI —y’ 1 0 1 Put y’ = 1( 1 = fe 2 1 2 Yi, 2 2 2A ——I [ a) 11 + dy’ 2 2AN — , 1,i 1 1’ I +QI a) —— Se 1 2 2 2A” y’i, a)I —— 2 Q(_Y’i,i 2 2A’ ——J dy’ ]dY’i,i (2.56) 33 Chapter 2. Analysis ofRetransmission Probabilities 2.2.5 Comparison of completely soft detection schemes A plot of the retransmission probability using perfect quantization for Schemes 2P to 6P with n = 3* and L = 500 is given in Figure 2.13. The curves for the hard detection case are also shown. It can be seen that the retransmission probabilities using perfect quantization are significantly lower than those using hard detection and the relative percentage differences in retransmission probabilities among the schemes are higher in the case of perfect quantization. 1 — Hard Detection -2 - Perfect Quantization 10 .. —. - C •—c. N %_ - . - %.- s.. -3 10 N’k N N C -4 N 10 “ E -5 10ii) -6 10 - .7 10 3 Scheme6 Scheme5 Scheme 4 Scheme3 Scheme2 I 4 — — - — — - — - — 5 I 6 I 7 8 10 9 SNR(dB) Figure 2.13 Retransmission probabilities for Schemes 2H to 6H and 2P to 6P (n * Numerical results for Schemes 3P, 4P, 5P and 6P 3, L = 500) for n> 3 are very time-consuming to obtain. 34 Chapter 2. Analysis ofRetransmission Probabilities 2.3 Soft Decision Schemes We now consider a decision scheme with an arbitrary number, 2M - 1, of 2M regions fRM} as shown in thresholds {O,±7,±7,...,±TM_l}, which defines Figure 2.14. The weights associated with each region is ±Wm m = l,2,...,M. Assume a packet of all ‘1’ is transmitted. The probability p(m) that the matched filter output j = 1,...,n and i = l,...,L, falls into region Rm is given by Q(TM_i_A) p(M)= p(m) = Q(TmA_Q(TmA) (2.57a) falls into region R_m is given by Similarly, the probability p(—m) that p(—M) ,m=1,2,...,(M—l) = Q(TM1 + ,m = 1,2,...,(iJ —1) (2.57b) 1 T 0 2 -R -RM I WM 2 —w 1 -R 1 —W Figure 2.14 The weights and 1 R A7 2 R 1 TM RM I 1 W WM thresholds associated with the 2M regions 35 Chapter 2. Analysis ofRetransmission Probabilities WM A 2 w Wi x w-l Y 2 w -A WM Figure 2.15 DMC resulting from quantizing the receiver matched filter output into 2M regions (adapted from [18]) To obtain the set of thresholds which optimize the performance of the system, two techniques have been proposed in [18]. The first uses a numerical search technique, which continuously varies the threshold values until it gives the minimum effective BER for the system. The other approach is to find a set of thresholds that maximizes the capacity of the discrete memoryless channel (DMC) [27] which results from quantizing the receiver matched filter output and is shown in Figure 2.15. This approach requires solving a set of M 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 to be used. From [17,18], these optimum weights are given by * w=In m P(RmIl) P(RmIO) (2.58) 36 Chapter 2. Analysis ofRetransmission Probabilities where m = 1,..., M, P(RmIO) and P(Rm 1) are the probabilities that the matched filter output falls in region Rm given (’ tt and “1” were sent respectively. Since the result will not 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 minimize the effective BER) and weights are given and shown in Table 2.1 with M and SNR = = 2 to 5, n = 5, 8 dB. M Optimal thresholds 2 0.46 3 0.30 0.63 4 0.21 0.43 0.72 5 0.17 0.33 0.52 f7 M Optimal weights 0.77 1.00 3.38 1.00 3.09 5.90 1.00 3.05 5.41 8.94 1.00 2.96 4.98 7.41 11.30 Table 2.1 Optimum Thresholds (Normalized to A) and weights forM = 2,...,5 SNR = 8 dB, and n = 5 (adapted from [18]) , In Figure 2.16, the retransmission probability of Scheme 3S is plotted against the threshold value for M = 2, n = 3 and 4, L = 500 with SNR = 6, 8 and 10 dB respectively. 1 We observe that the minimum retransmission probability occurs at around T SNR = 10 dB and the minimum becomes broader as SNR decreases. = 0.4 for Although the minimum point varies somewhat with n, the value of n in practice is typically small since otherwise the throughput would be very low. In the following analysis, we will thus use the optimum threshold values in Table 2.1 (SNR = 8 dB, n = 5) for all values of n and SNR. In the following derivations, let 1 ’ denote the retransmission probability for Scheme iS, i = 1,... 6, where S indicates the use of soft detection. 37 Chapter 2. Analysis ofRetransmission Probabilities R6dB SNR=8dB -3 - n=4 —-. 10 -4 io o — - -— ------—-—-- 5 E 10 n=3 SNR=l0dB - -6 - 10 — - -— n=4 -7 10 ic 0.2 I I I 0.3 0.4 0.5 0.6 0.7 0.8 Threshold Figure 2.16 Retransmission probability for Scheme 3S with varying threshold value (M 2,,i = 3,4,L= 500) 2.3.1 Scheme iS The decoding failure probability for this scheme is the same as that of Scheme 1H and is given by =[i_(i_p)L]ll 1S =1H (2.59) 2.3.2 Scheme 2S The decoding failure probability for Scheme 2S is given by 2s = Pr { the combined packet is soft detected incorrectly } = 1 = 1 = I — — — Pr { the combined packet is soft detected correctly } [Pr{a bit of the combined packet is soft detected correct1y}]’ [i — Pr{a bit of the combined packet is soft detected incorrectly}]’ =1—[l—p2s] (2.60) 38 Chapter 2. Analysis ofRetransmission Probabilities where P2s denotes the effective bit error rate (BER) of a combined packet using soft decision decoding. j= 1,...,n From [18], the probability that the decision accumulator and i = l,...,L, has value sis given by M 1 = PrfZ sJ , 1 PrfZ_ s — ,j = 1 w,j p(m)+ Pr{Z_ s + w,’,jp(—m) (2.61) ‘m=1 j = o} = 1. The effective BER P2s is given by Pr{Z , where 0 o}. Pr{ZM. =sI+Pr{ZMI P2s (2.62) all s<O 4 for M = 1,...,5. The improvement in 2S is the . with n 2 Figure 2.17 shows P greatest when M is changed form 1 to 2 and the incremental improvement drops for further increasing values of M. Comparing with 2H Figure 2.18 shows in Figure 2.5, 2s for n the same; there is a steady improvement in 2S with M = 3 for 21 and 2/ 2S - n = 1 to 6. 1, l = 1,2,..., are no longer as n increases. To achieve a retransmission probability of iO with M = 3 and n = 4, an SNR of approximately 7.5 dB is required. 2.3.3 Scheme 3S Let Bs denote the event that the combined packet (of n received copies using soft detection) is successfully decoded and bs the event of Bs at a particular bit position. Similar to the derivations for Scheme 3H, we have s =l_Pr{Aj}+ 3 P Pr{AJAk}— 1j<k<1n 1j<kn j=1 Pr{AjAkAj}+...+(_1Y1Pr{AI...Afl} ..AB} PrfAiA . —Pr{Bs}+PrABs}— PrAJAkBs}+...+(—1)’’ 2 jz1 1j<kn (2.63) 2 A 1 Pr{A . [ AmBy} = Pr{bsaia 2 .am}IL = [P(nm)]L (2.64) 39 Chapter 2. Analysis ofRetransmission Probabilities 0 10 4- -2 10 -3 10 -4 10 --5 I 10 -6 10 .7 10 SNR(dB) Figure 2.17 Retransmission probability for Scheme 2S (M 1,..,5, n = 4, L = 500) = -o 10 ‘a • - — -.- — ••___•% . . .--. -2 10 % — -3 10 o 10 . 1 --S 5s N -5 ‘-S 5%- ‘-.. 5.,. 5.’ ‘ \ “S 5.•4-S • 110 ‘5 — — 4 — 10 ‘S .9 10 n=3 n=2 n=1 -10 10 -11 \ I 10 - 1 2 3 I I I I I 4 5 6 7 8 9 SNR (dB) Figure 2.18 Retransmission probability for Scheme 2S (M = 3, n = 1,.,6, L = 500) 10 40 Chapter 2. Analysis ofRetransmission Probabilities where Pg(n,m) = am} Pr{bsaia . 2 2 >O,...,Ypjj >O} 11 >0,Y =Pr{bs,Y 1 E{Rl,R =Pr{bs,Y ...,RM} 2 ...,RM},...,Ymi E{Rl,R 2 = W ,...,Wmi = wr} W ,...,Wmi = w = W ,...,Wmi = w }Pr{Wi,j = w ..,Wmi = Wr = =1 1 r ,1 j 1 r{sw = 1 r =1 1 r rm=1 M M }...pr{Wm,i = Wr I Pr{Wk,i > OWii Pr { , 1 OW w } } m * * ...,Wmi ,Wr 1 In m Wk,j >-w+Pr k=m+1 k=1 k=m+1 J Pr{H,_,, = m k=1 k=1 1 } !.Hp(rk) J k1 m S+Pr{Hnmi =-w Iflp(rk) k=1 rm=1 Wrm =—w m M =••• = = +Pr{Wki M r1 =1 = W ,...,Wmi =w)flp(rk) 1 ,;, =1 =•• }flPr{Wk k=1 = 1 r ,. rm=1 =1 1 r M w = k=1 = M } Wr ,...,Wmi rm=1 = 11=1 = W rm=1 = =1 1 r 11 }Pr{W JIk=1 j (2.65) 41 Chapter 2 Analysis ofRetransmission Probabilities where Hn_m,i and Wk,1 is the quantized value of the matched filter output k,i• = k=m+1 The parameter rk, k € = 1,2,. . . , m, indicates the region number that {—M,. .,—1,1,,. ..,M}. The term Pr{Hn_mj . Pr{Hnm,j s} = = Pr{Hn_m_i,i = s — = s) k,i falls into, and can be written as w}p(k) + Prf Hn_m_i,i =S+ w}p(_k) (2.66) k=1 , 0 where Pr{H o} = 1. = Actually, (2.65) implies a tree search technique as shown in Figure 2.19 for the case of m = 2, M = 3. A branch corresponds to a decision (quantization of k,I) and the weights and probabilities for the different paths are also shown. Each node at the mth level (terminal node) corresponds to a possible combination of probability fl , ,w 1 {w 21 ,...,Wmi } with This probability is multiplied by the probabifity of successful p(r). decoding of the combined packet {z }, i = 5a 1a 2 1,2,..., L, and it gives Pr {b am for this terminal node. By summing up all the probabilities of the terminal nodes, we get Pg(n,m). n,m) defined as in (2.65), 3s becomes P ( With 9 3 =1— n(l P — )L _{Pg (n,O)] = [1 -(1 _p)L + (j(i — )2L + n[Pg (n, l)]L — )3L +. ()[Pg (n, 2)]L . .+(—1) ‘(1 . .+(_l)n+1 — (flJ[P ()jL jfl + (2.67) k=O Note also that P2s rewritten as - (;(l •= 1 — Pg (n,O) in (2.62). Hence (2.60) for Scheme 2S can be 42 Chapter 2. Analysis ofRetransmission Probabilities “2S _[1’g(t,0)} Figure 2.20 shows 3S with n = 4 for M = (2.68) 1,.. 5. The retransmisson probability . , drops as M increases and the incremental improvement decreases for further increasing ç with M 1 values of M. Figure 2.21 gives P = 3 for n = 1 to 5. It shows a steady improvement in retransmission probability as n increases. To achieve a retransmission probability of i0 with M = 3 and n = 4, an SNR of approximately 7.5 dB is required. (2w), p(1)p(l) (), ) 1 p( ( + w), p(1)p(2) +), p(1)p(3) (w (w +w), p(2)p(l) 1 (w),p(2) (2w), p(2)p(2) (w p(2)p(3) (w ÷wjj, p(3)p(l) p(3) ( +w),p(3)p(2) (2w), p(3)p(3) Figure2.19 Treediagramform=2andM=3(p(k)and w,k=1,...,3 are defined in (2.57) and (2.58) respectively) 43 Chapter 2. Analysis of Retransmission Probabilities 0 10 id -2 10 id -4 10 1t -6 10 -7 10 -8 10 2 3 4 7 8 Figure 2.20 Retransmission probability for Scheme 3S (M 1,..,5, n 5 6 10 9 SNR (dB) -o 10 = 4, L = 500) ----:-;-----. —-- . S. .5. -2 -5 -S -5 -S. S. 10 -4 o 10 -s \. 10 \, 0 6 ib -7 10 -8 10 n=5 6.) n—_4 -10 10 -11 10 —. - — - — - — n=3 n=2 n=1 là 0 1 I I I I I I 2 3 4 5 6 7 8 9 SNR (dB) Figure 2.21 Retransmission probability for Scheme 3S (M = 3, n = 1,...,5, L = 500) 10 44 Chapter 2. Analysis ofRetransmission Probabilities 2.3.4 Schemes 4S and 5S Let Bs, j 1,2,..., n, denote the event of successful packet decoding of the combined packet of the first] copies using soft detection. The retransmission probabilities for Schemes 4S and 5S are given by (2.69) and (2.70) Again, these expressions can be evaluated by expanding the union of events, as done in the case for hard detection. The probability of each joint event in the union expansion can be evaluated numerically as follows. Using the same example in section 2.1.4 and 2.2.4, consider the event 5 B for the case of n sA 3 B 1 A s 4 = 8 copies. Letting bs denote the event of Bs at a particular bit position, we have A B 5 S 3 B 1 Pr{A S 4 } = b a 5 s 3 {Pr{aib s 4 }]L (2.71) where b a rir Pr{rir s Pr[aib s I } 2 } 5 4 3 r = b a 5 s 3 Pr{aib s 4 } =-M 5 =-M r 3 =-M r 4 =-M r 2 i=-M r O 1 r O 2 r O 3 r O 4 r O 5 r M M M M M 5 b asrlr flp(rk) s Pr{alb s } 5 4 3 r 2 = =—M 5 r = -M r =—M 4 3 =—M r 2 i=—M r O 5 4 r O tjO r O r 3 O r 2 k=1 (2.72) The conditional probabilities are given by 45 Chapter 2. Analysis ofRetransmission Probabilities 5 a •••r b ri 5 s 3 Praib s 4 I } = 1 -••r 5 5 }Pr{b 1 ••-r 5 }Pr{b 1 ri ••r Prfa s r 4 s jr 3 5 ri •-r }Pr{a I 5 (2.73) where if rk>O,k=1,...,5 11 PrfakIrl...rS}= otherwise (2.74) and ’= Pr{bjslri...r ] 5 1 if ! j 0 , otherwise. (2.75) Figures 2.22 and 2.24 give the retransmission probabilities of Schemes 4S and 5S respectively with n = 4 for M = 1,.. .,5. In both Figures 2.22 and 2.24, the retransmisson probabilities drop as M increases and the incremental improvement decreases for further increasing values of M. Figure 2.23 gives the retransmission probability of Scheme 4S with M 3 for n with M = = 1 to 5 and Figure 2.25 gives the retransmission probability of Scheme 5S 3 for n = 1 to 4. The figures show steady improvement in retransmission probabilities as n increases. It can be seen from the figures that to achieve a retransmission probability of an SNR of approximately 7.3 dB. with M = 3 and n = 4, Schemes 4S and 5S both require 46 Chapter 2. Analysis ofRetransmission Probabilities 0 10 ‘a -2 — 10 I 10 -3 -4 10 -5 10 -6 10 -7 10 -8 10 SNR (dB) Figure 2.22 Retransmission probability for Scheme 4S (M = 1,..,5, n = 4, L = 500) 0 10 i-a -2 10 10 o • - 10 -5 10 4 10 -7 10 4 10 -9 10 -10 10 SNR (dB) Figure 2.23 Retransmission probability for Scheme 4S (M = 3, n = 1 5, L = 500) 47 Chapter 2. Analysis ofRetransmission Probabilities 0 10 >-. •-. -2 10 3 10 C -4 10 C ic -6 10 -7 .9 10 2 3 4 5 6 7 8 9 10 SNR (dB) Figure 2.24 Retransmission probability for Scheme 5S (M = 1,..,5, n = 4, L = 500) 0 10 .—- -1 —•-. 10 -2 10 I -3 10 .4 10 -5 10 -6 n=4 ri=3 n=2 n=1 10 .7 10 4 10 2 3 4 5 6 7 8 9 SNR (dB) Figure 2.25 Retransmission probability for Scheme 5S (M = 3, ,z = 1,...,4, L = 500) 10 48 Chapter 2. Analysis ofRetransmission Probabilities 2.3.5 Scheme 6S Let D, k = 1,..., 2’ 1, denote the event of successful decoding on the — combined packet using the copies ‘selected’ by the binary expansion of k as described in section 2.1.5. For Scheme 6S, the retransmission probability is given by 12 —1 lPrUD P s 6 k=1 (2.76) Equation (2.76) can be evaluated by expanding the union of events with the probability of each 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. s Di D for the case of 22 s 3 DisD s 7 n = 8 copies. Letting d denotes the event of D at a particular bit position, we have D 17 s 3 D 15 Pr{D s 22 sD d di 22 s 3 Pr{disd s 7 s } = ,—M =—M 5 r O 1 r O 5 r rO d 17 1 [Pr{d s 3 s 22 sd }]L (2.77) } } d d di p(rj) 22 Pr{dis s s 7 } 5 4 3 r 2 srir ... zj=—M = r 3 1 pr{r d r Prf 22 sdi disd s 7 5 4 3 r 2 grir ... = } r = 5 —M r5O j=1 (2.78) The conditional probabilities are given by di d 22 s 3 Pr{disd s 7 sri . . . 5 r } .r di d , sri...r ...r ri.. Pr{ Pr{ =Pr{di 3 } s 7 } 5 sri 22 } where (2.79) 49 Chapter 2. Analysis ofRetransmission Probabilities 5 if cw>0 1 j=1 I if 0 , otherwise. (2.80) The above numerical method for Scheme 6S can be applied to evaluate the retransmission probabilities of all other kinds of combination schemes using hard (M = 1) or soft detection. Figure 2.26 shows 6S with n M = 3 for n = = 3 for M = 1,... ,5 and Figure 2.27 gives 6S with 1 to 4. It can be seen that as M or n ç decreases as 6 is increased, P expected. The improvement in P obtained from increasing n is the greatest among all the schemes. To achieve a retransmission probability of l0 with M = 3 and n Schemes 6S requires an SNR of approximately 6.4 dB. 0 10 -2 - 10 P. 10 -3 C -4 10 .6 10 .7 10 SNR(dB) Figure 2.26 Retransmission probability for Scheme 6S (M = 1,..,5, n = 3, L = 500) = 4, 50 Chapter 2. Analysis ofRetransmission Probabilities irn SNR (dB) Figure 2.27 Retransmission probability for Scheme 6S (M = 3, n = 1,...,4, L = 500) 2.3.6 Comparison of soft detection schemes Figures 2.28 and 2.29 show the retransmission probabilities of Schemes iS to 6S with n = 3 and M = 2 and 3 respectively. From these figures, we observe that the incremental improvement from increasing M from 2 to 3 is quite small. From Figures 2.29 and 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 the retransmission probabilities of Schemes 2S to 6S with M hard detection with the same n = 3 and n = 4. The results for are also shown. It can be seen that for a higher value of n, the relative percentage difference in the retransmission probabilities among the schemes increases. 51 Chapter 2. Analysis ofRetransmission Probabilities 0 10 I -2 10 -3 10 4 10 ii -6 10 SNR(dB) Figure 2.28 Retransmission probabilities for Schemes iS to 6S (M = 2, n = 3, L 500) 0 10 ic -2 I 10 -3 10 4 10 -s 10 4 10 3 4 5 6 7 9 8 SNR (dB) Figure 2.29 Retransmission probabilities for Schemes 15 to 6S (M = 3, n = 3, L = 500) 10 52 Chapter 2. Analysis ofRetransmission Probabilities 10 Hard Detection — ----.--.- —.. -.- 3 là - -4 O 1 10 - ---.-.. -.-- - —-- -4-t-- —. Soft Detection (M=3) -5 o io 10 10 Scheme6 Scheme5 Scheme 4 Scheme3 Scheme 2 8 ià 10 — — -10 10 5 7 6 8 9 10 SNR (dB) Figure 2.30 Retransmission probabilities for Schemes 2H to 6H and 2S to 6S (M = 3) with n = 4, L = 500 2.4 Effect of packet length L To 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 L with a constant SNR value of 8 dB and n respectively. = 3 in Figures 2.31, 2.32 with M = 1 and 3 From Figure 2.31, we can see that as L increases, the retransmission probability increases as expected and for L greater than 500, all the schemes except Scheme 1H have similar retransmission probabilities. Note that from observing Figure 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 schemes increase for L > 100 and the difference is even greater when n is increased to 4 in Figure 2.33. 53 Chapter 2. Analysis ofRetransmission Probabilities 0 10 o -z 10 0 .5 10 lot 102 Bits per packet Figure 2.31 Retransmission probabilities for Schemes IH to 6H against L (n = 3, M = 1, SNR = 8 dB) = 3, M 3, SNR = 8 dB) 0 10 -2 10 I 4 10 -5 10 .6 10 102 Bits per packet Figure 2.32 Retransmission probabilities for Schemes IS to 6S against L (n 54 Chapter 2. Analysis ofRetransmission Probabilities 0 10 -1 10 II là -4 10 -5 to -6 10 -7 10 4 10 101 102 Bits per packet Figure 2.33 Retransmission probabilities for Schemes iS to 6S against L (n = 4, M 3, SNR = 8 dB) Chapter 3 Throughput Analysis and Simulations In this section, we compare the performance of the six schemes by examining the throughput 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 by 1 T= (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] fl +fl1PF(flO)+fl2PF(flO)PF(fll)+.” 3= 0 q-1 +flqflPF(ni)+ i0 (q +s—i) HPF(n) “FVq) 1=0 (3.2) where P (ne) is the retransmission probability for the detection and combining schemes ) can be calculated as discussed in chapter 2. The optimal 1 1 copies. F (n used with n number of copies, n (found using procedures described in [14], which are also reproduced in Appendix A for reference), of Schemes 1H to 5H are given in Table 3.1 while those for Schemes 2S to 5S for M respectively. = 2 and 3 are given in Tables 3.2 and 3.3 These optimal values were used in (3.1) and (3.2) to calculate the corresponding throughputs. Because of the large amount of computational effort required, the throughput of Scheme 6 is considered only for the hard detection case using simulation. 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. 1 packets received at the In our analysis, we consider only the case in which the n ith level are combined and the packets at preceeding levels are discarded; otherwise the throughput analysis will be complicated by dependencies among error events from 55 56 Chapter 3. Throughput Analysis and Simulations decoding failures in different levels. Tn [22], this variation was considered and applied to Schemes 1H to 6H. The throughputs of Schemes 2S to 5S are shown in Figures 3.1 to 3.4 with M = 1,2 and 3. Also shown are the throughputs of the Weldon ARQ scheme with variable 0 and ideal selective repeat scheme with no combining. It can be seen that combining can n result in a significantly higher throughput for the Weldon ARQ scheme. There is also a large improvement when M is increased from 1 to 2; however the incremental improvement drops when M is increased further. A reasonable value of M to choose in terms 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 no combining for block error rates (BKER) greater than 0.5. Note also from Table 3.1 that the optimal number of copies for Scheme 2H (M = 1) are all odd numbers. This is because the retransmission probability of Scheme 2H remains unchanged if n is increased by one from an odd value [19]. In general, Schemes 2S to 5S have a lower optimum number of copies 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 3 respectively. It can be seen that except for Scheme 1, the difference in throughput among In general, Schemes 3S and 5S have similar throughputs and the schemes is small. optimum number of copies and perform better than Schemes iS, 2S and 4S. Scheme 3S with M = Hence 2 or 3 will give good performance with reasonable system complexity. The simulated throughput of Scheme 6H is shown in Figure 3.8 along with the 99% confidence limits. The throughput of Scheme 3H is also shown for comparison. It can be seen that the difference in throughputs between Schemes 3H and 6H is quite small. 0 I C 00 t C_1 .1:. Li) L — k 4 k — t’J •• - P229999 * * - L Ui (.ui Lu —‘ Lii c-” — Lij) L) L) —. L) L) Lj) - * - * * —————w t) — * :::::::::1 L) Lii (.) Lu — t’ ::::::::::! L) O D PP p C C I CD C C-) C -t CD 0 CD IN-) 4 00 t’—) LI’ \D t’-) (Ji 4. IN-) 4- t’ LI’ L) tj.) ) -i -‘ -‘ ‘ 999929299 * I. I I 0 CD IN-) Lt) IN) I’) IN- IN) Q -) ‘J LI, IN- IN) . IN) • — - 0 — J * * D IN-) ———a IN) IN) IN) IN) IN) .f.. — IN.) ci-) — IN-.) IN.) Li-) Li-) —— IN.) Li-) IN) — Li-) Li-.) —— IN) — IN) * 0 Cl) IN.) Li-) IN.) — - * cT Lit — - ————F — —————— Li-) Li-) Li-) L) L) L,) IN.) 00 UI I ::::::::::! ‘— L’J 00 — ———— D 999999999 r) 59 Chapter 3. Throughput Analysis and Simulations 0 10 I 0.1 Block Error Probability Figure 3.1 Throughput for Scheme 2S (M = 1,2,3,4, L = 500, q = 1, S = 1000) = 1, S = 1000) 0 10 0.1 Block Error Probability Fiure 3.2 Throughput for Scheme 3S (M = 1,2,3,4, L = 500, q 60 Chapter 3. Throughput Analysis and Simulations 0 10 I 10 1 0.1 Block Error Probability Figure 3.3 Throughput for Scheme 4S (M 1,2,3, L 500, q = 1, S = 1000) 0 10 I —1 10 0.1 Block Error Probability Figure 3.4 Throughput for Scheme 5S (M = 1,2,3, L = 500, q = 1, S = 1000) 61 Chapter 3. Throughput Analysis and Simulations 0.8 0.7 0.6 0.5 I 0.4 0.3 0.2 0.1 0 Block Error Probability Figure 3.5 Throughputs for Schemes 1H to 5H (M = 1, L = 500, q = 1, S = 1000) = 1, S = 1000) 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.1 Block Error Probability Figure 3.6 Throughputs for Schemes IS to 5S (M = 2, L = 500, q 62 Chapter 3. Throughput Analysis and Simulations 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.1 Block Error Probability Figure 3.7 Throughputs for Schemes iS to 5S (M 3, L = 500, q = 1, S = 1000) 0.8 0.7 0.6 z -C 0.5 0.4 0.3 0.2 1 0.1 Block Error Probability Figure.3.8 Simulated Throughputs for Schemes 3H and 6H (L = 500, q = 1, S = 1000) Chapter 4 Conclusions A general multiple copy combining ARQ scheme was investigated using hard, soft, and perfectly quantized detectors. Six different combining schemes have been considered In each case the dependence of the retransmission probability, on the signal to noise F’ ratio (SNR), the number of copies transmitted (n), the number of quantization levels of the detector (M), and the packet length (L) are studied. For an arbitrary degree of detector quantization, analytic expressions for Scheme 3 have been derived, and numerical procedures for evaluating the F F of of Schemes 4, 5 and 6 have been described. It has been shown that Scheme 3 can have a significantly smaller F than Scheme 1 or Scheme 2. Scheme 4 has a higher “F than Scheme 5 and the relative percentage difference between them increases as SNR increases. It was found that Scheme 3 has a has the lowest F F close to that of Scheme 5, especially for small values of n. Scheme 6 of all the schemes, but requires higher decoding complexity. Generally, when n is increased, the relative percentage difference of F between the schemes increases as well. When M is increased from 1 to 2, F especially for Schemes 2 and 4 with even n. of Schemes 2 to 6 drops significantly When M is increased further, “F of Schemes 2 to 6 continue to decrease but the incremental improvement is smaller. The additional improvement obtained from increasing M from 4 to 5 is already very small. When M is increased, the relative percentage differences in increase as well. The “F F among the schemes of Scheme I is the same for any value of M since it does not perform 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 the resultant throughputs for different values of M were analyzed. The throughput of the 63 Chapter 4. Conclusions 64 Weldon ARQ scheme can be greatly improved using multiple copy combining. It can be further increased by using soft decision detection. Using about 8 quantization levels is adequate to give a throughput which is close to that obtainable from using perfect quantization. For block error rate BKER > 0.5 and M 2, the performance of Schemes 2S to 6S are better than that of an ideal selective repeat ARQ system with no packet combining. It can be seen that except for Scheme 1, the difference in throughput between the schemes is small and generally, Schemes 3 and 5 have throughputs, which are higher than those of Schemes 2 and 4. Simulation results indicate that the throughputs of 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 simple decoder structure. Among the topics which could be further studied are the following: 1. The computational effort required for calculating the retransmission probability of Scheme 6 using the numerical procedures described in section 2.1.5, 2.2.4 and 2.3.5 grows rapidly as n > 4 (order of 22_1). Procedures to reduce the computational time for Schemes 4 to 6 perhaps by finding analytical expressions should be investigated. 2. The memory ARQ schemes can be applied to other types of ARQ strategies where multiple copy transmission is used. 3. Apart from the additive white Gaussian channel model, other types of channel models, e.g. fading or impulsive noise, can be considered when the combining schemes are applied. References [1] J. B. Moore, “Constant-radio code and Automatic-RQ on transoceanic HF radio services,” 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 burst noise 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 on satellite 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 channels and its throughput analysis,” IEEE Trans. Commun., vol. COM-29, pp. 353-363, Mar. 1981. 65 66 References [121 M. J. Miller and S. Lin, “The analysis of some selective-repeat ARQ schemes with fmite 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 soft decision 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 combining schemes for fmite-buffer ARQ systems in a Rayleigh-fading channel,” 1992 IEEE International Conference on Selected Topics in Wireless Communications, 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 and Applications. 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 algorithmic approach. McGraw-Hill, 1986. [29] E. Kreyszig, Advanced engineering mathematics, John Wiley & sons, Inc., 1983. Appendix A 1 Determination of Optimum Values of {n 1 In this appendix, the method to find the optimum values of {n } is given [14]. From (1.1), we have q i—I \ k=O / In, iflq+Sl)PF k=O’ , + F 13 Li i=O +flq_1 fO+lPF =no p° +fl2PF [1 (nq +nq_i nO+. +“+flIPF + +flqPF +;‘ [...[ni+;i [...[n_i +5— 1)PF 1_P p;’ [n +P (A.1) From (A. 1), to minimize Step 1: f3, we perform the following steps Find the value of flq (say n) that minimizes fq(flq)flq±pn(n q \ +S—1 1P flq Step2: Seti=q. Step 3: Decrement i by 1. Step 4: 1 (say n,) that minimizes Determine the value of n f(n) StepS: Ifi>O,gotoStep3. Step 6: Irint out = n n+ ...,n) 2 ( +Pf , 1 n, { } and stop. 68 (A.2) (A.3) Appendix B Numerical Procedures for evaluating Pc(n,m) We describe the numerical evaluation of the integrals such as (2.42) defined in section 2.3. The method chosen is based on Simpson’s rule [28,29]. The estimation of 1(f) = J f(x) dx (B.l) a is given by 1(f) where h = b—a and f = N N-I i=1 1=1 !( 0 + 4f 2 + f2N 1 + 2f _ 2 f(a + jh), j = O,...,N . Bounds for the error 4 CMesCM where C “ lb a, = (B.2) are given by (B.3) 4 are the smallest and the largest value of the fourth and M and M 4 180(2N) derivative of f(x) in the interval of integration. Hence we can control the accuracy by adjusting 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 are infinite, we have to use an approximation here. The error introduced can be estimated as follows. Take P(n,m) in (2.42) as an example, 69 70 Appendix B. Numerical Procedures for finding P(n,m) 1 P(n,m)= f A J Yi a k=1 nA —1 (m I IdY’m”Y’i Y’k G Jfl m \k=1 I — a b A ) A Y’m a = f ••• Yi= b 2 ( fle 1 Q j ( 1 2 mm ( fle2YkQ 1 m flA))dY?m•..dYIl +ET a - A) Ym nm)4 k=1 a (B.4) Hence the integral can be approximated using an upper limit of b with an error E introduced. Since 0 < Q(k) <1, ET is bounded by mm ET = < mm S 5 fle —1 (m 1 Y’k -.Jn—m k=1 k=1 Ymth 1 1 fle_ •.. b y = 1 2 nA” dY’m”dY’i a 2 dY’m”dY’i ••• y=b y’=b = [Q(b)J m 1 E b7 2 (B.5) In our calculations, the value of b used is 10. The error introduced in using an upper limit 10 instead of infmity is bounded by ET <[1.33 x lO_16]m. Appendix C Optimum Thresholds for Soft Decoders In [181, a set of M - 1 nonlinear equations whose solution gives the set of thresholds which maximizes the capacity of a discrete memoryless channel (DMC) shown in Figure 2.15 was given. We have CH(X)—H(XIY) =1-[p(i)+p(-i)]h p) p(i) + p(—z) (C. 1) og is the binary entropy function. log 1/e}+(1—e)l 1/(1—e)} h(e)=e { 2 where { Substituting (2.57) into (C. 1) and setting the partial derivatives C / )Tm set of M - = 0, we have a 1 equations: exp {p(m)+p(-m)}p(m+1) 2 (Tm -A) •1og 22 [p(m)fp(m+1)+p(—m—1)} +exp log 2 2a {p(m)+p(-m)}p(-m-1) 1 =0 p(—m){p(m+1)+ p(—m —i)}j where m=1,2,...,M—1. 71 (C.2) Appendix U Asymptotic Behaviour of Retransmission Probability 211 and 3H for Schemes 1H, P We consider in this appendix the behaviour of 1H’ 2H and 3H for p << 1. D.1 Scheme 1H From (2.8), we have “IH r [1_(l_P) Applying the binomial series [29] to (i — L1’ I (D.1) p)’, and neglecting higher order terms in p (since p <<1), we obtain “1H [1_(l_Lp)] (D.2) D.2 Scheme2H From (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 by n—k (n—k” P,(n,p,k)= j 2 72 ) (D.4) AppendixD. Asymptotic Behaviour ofRetransmission Probability for Schemes 1H, 2H and 3H For p << 73 1, we can neglect higher order terms in p so that n—k ! 2 if [(n+1X] P,,(n,p,k) ,otherwise =0 (D.5) For odd n, (D.3) then becomes ‘2H =l_[l_p,j(n,p,O)]L n 1[1[(n±iy]P 21 2 L (n+l)/ /2) (D.6) From (2.lOb), P,j (n,p,k) for even n is given by P(n,p,k) = (n _k)i(l _)nki (D.7) For p <<1, we can neglect higher order terms in p so that n if k 2 P,(n,p,k) =0 For even n, (D.3) then becomes otherwise (D.8) AppendixD. Asymptotic Behaviour ofRetransmission Probability for Schemes 1H, 2H and 3H ‘2H 74 =l_[l_P,,j(n,p,O)]L L p2 1— 1—— Ln/2J 2 f_ I n/2) 2 Hence for both odd and even values of n, n ‘ LI 2H — 2 p (D.9) decreases as [ n+1 2 J when p << 1. D.3 Scheme 3H From (2.15) we have “3H )L [i_(i_ jfl +(_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) and odd n when << 1 for both even p << 1 (D.5,D.8), ST becomes - ST )k [1- Pj(n,p,k)]j = (‘) [k1-P_nPk1 )k+1 1 = (-i)’ — [:] (n,p,k)] . 1)k+1 [n][LP. (n,p,k)] = (D.11) k=O because (_l)1[’] = 0. With (D.5) and (D.11) and for odd n ST becomes AppendixD. Asymptotic Behaviour ofRetransmission Probability for Schemes 1H, 2H and 3H (n9/ k=O ( n—k 75 n+1 (1)k+1InEL(fl+lyJP] kJ[ n n—k (1)k+1[)[(n+ly] =-Lp 2 k=O n+1 2 k+1 =-Lp n+1 =—Lp 2 (n—k)! n! k!(n —k)! (n+ 1,(n —1_k)! 2 2 (n—/ n! (n 1,(n + 2 2 — ) ()k+1 )! k=O 1 n —1 2 2 )! (D.12) The summation term in (D.12) is zero and hence ST isO for odd n with n > 1. For n = 1, this summation term reduces to -1 and ST = Lp. Hence we have, for odd n with n> 1, (D.13) and P3H —2Lpforn——1. For the case of n even, with (D.8) and (D.1 1), ST can be written as AppendixD. Asymptotic Behaviour of Retransmission Probability for Schemes 1H, 2Ff and 3H 76 r(fl—k 1 ST_(_l) [k][fl/2J] k=O ( (nNn—k L()k+1 k=O = -p(-l) k+1 k=O L = 2 n! (nI2)! n! k!(n-k)! A )k+1 1 ( k=O (n—k)! (n/2)! Lj - ) 2 k!(’—k n L (n12)!2 xO (D.14) 3 and hence P n = 1,2,3 = 311 decreases as p’ for p [Lp]’ for even n. In conclusion, P << 1 for
- 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 |
File Format | 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. |
DOI | 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 |
Graduation Date | 1992-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | 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