Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Performance analysis of a memory ARQ scheme with soft decision detectors Lau, Chiew Tong 1985

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1985_A7 L39.pdf [ 3.37MB ]
Metadata
JSON: 831-1.0096298.json
JSON-LD: 831-1.0096298-ld.json
RDF/XML (Pretty): 831-1.0096298-rdf.xml
RDF/JSON: 831-1.0096298-rdf.json
Turtle: 831-1.0096298-turtle.txt
N-Triples: 831-1.0096298-rdf-ntriples.txt
Original Record: 831-1.0096298-source.json
Full Text
831-1.0096298-fulltext.txt
Citation
831-1.0096298.ris

Full Text

PERFORMANCE ANALYSIS OF A MEMORY ARQ SCHEME WITH SOFT DECISION DETECTORS by CHIEW TONG LAU A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We a c c e p t t h i s t h e s i s as co n f o r m i n g t o the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA • August 1985 © Chiew Tong L a u , 1985 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the r e q u i r e m e n t s f o r an advanced degree a t the THE UNIVERSITY OF BRITISH COLUMBIA, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g of t h i s t h e s i s f o r s c h o l a r l y purposes may be g r a n t e d by the Head of my Department or by h i s or her r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . DEPARTMENT OF ELECTRICAL ENGINEERING THE UNIVERSITY OF BRITISH COLUMBIA 2075 Wesbrook P l a c e V ancouver, Canada V6T 1W5 Date: August 1985 ABSTRACT An a u t o m a t i c r e p e a t r e q u e s t (ARQ) scheme w i t h memory and s o f t e r r o r d e t e c t o r s has been r e c e n t l y proposed by B e n e l l i . I t s p erformance was s t u d i e d m a i n l y t h r o u g h computer s i m u l a t i o n . In t h i s t h e s i s , a g e n e r a l i z e d v e r s i o n of t h i s ARQ scheme i s examined. The s e l e c t i o n of c e r t a i n t h r e s h o l d s and w e i g h t s t o m i n i m i z e the b i t e r r o r r a t e i n systems u s i n g a f i x e d number of p a c k e t r e p e a t s i s c o n s i d e r e d . The e v a l u a t i o n of the average number of t r a n s m i s s i o n s p e r packet i n systems i n which n e g a t i v e l y acknowledged p a c k e t s are r e t r a n s m i t t e d u n t i l s u c c e s s f u l l y r e c e i v e d i s d e s c r i b e d . F i n a l l y , t h e performance of the memory ARQ scheme w i t h f o r w a r d e r r o r c o r r e c t i o n i s a n a l y z e d . T a b l e of C o n t e n t s Chapter Page 1. INTRODUCTION 1 2. MEMORY ARQ WITHOUT FEC 7 2 . 1 D e s c r i p t i o n of the ARQ scheme 7 2.2 B i t E r r o r Rate A n a l y s i s 1 2 2.3 A n a l y s i s of Average Number of T r a n s m i s s i o n s 1 9 3. THRESHOLDS DETERMINATION 32 3 . 1 ' Minimum B i t E r r o r Rate Approach 33 3.2 Minimum Average Number of T r a n s m i s s i o n s Approach 38 3.3 Maximum Channel C a p a c i t y Approach 41 3.4 Optimum (minimum BER) weight d e t e r m i n a t i o n 47 4. MEMORY ARQ WITH FEC 52 4 . 1 System Throughput 59 5. CONCLUSION 66 REFERENCES 68 APPENDIX A 70 APPENDIX B 73 APPENDIX C 75 APPENDIX D 82 i i i L i s t of F i g u r e s F i g u r e Page 1.1. Stop and Wait ARQ 1 1.2. Go-Back-N ARQ 2 1.3. S e l e c t i v e Repeat ARQ 3 1.4. B e n e l l i ' s memory ARQ scheme 5 2.1. B l o c k diagram of the memory ARQ system 8 2.2. F l o w c h a r t of the d e c o r d e r 11 2.3. P r o b a b i l i t y d i s t r i b u t i o n f u n c t i o n of y 12 2.4. P, (/) vs number of t h r e s h o l d s (2m-1) f o r b SNR=8dB and /=1 t o 4 15 2.5. P. (/) vs SNR f o r m=2 and J=\ t o 5 17 o 2.6. P. (5) vs SNR f o r m=1 , 2 and 3 18 b 2.7. Tree diagram f o r h a r d d e c i s i o n d e t e c t o r 22 2.8. Tree diagram f o r m=2 s o f t d e c i s i o n d e t e c t o r 23 2.9. Tree diagram f o r com p l e t e s o f t d e c i s i o n d e t e c t o r 24 2.10. E ( / ) vs w e i g h t s (±1, ±m) f o r SNR=7, 8, 9 and lOdB 26 2.11. E ( / ) vs SNR f o r BKER=0.5, 0.7 and 0.9 27 2.12. D i s t r i b u t i o n of / f o r t h e c o n v e n t i o n a l and the memory (m=1 and 2) ARQ systems w i t h SNR=9dB and n=511 28 2.13. E ( / ) v s BKER f o r t h e c o n v e n t i o n a l and t h e memory (m=1 and 2 and complete s o f t d e c i s i o n d e t e c t o r ) ARQ systems (n=511) 29 3.1. P, (/) v s t h r e s h o l d f o r m=2 and SNR=6dB 34 D 3.2. P. (/) vs t h r e s h o l d f o r m=2 and SNR=8dB 35 o i v L i s t of F i g u r e s F i g u r e Page 3.3. P. (/) vs t h r e s h o l d f o r m=2 and SNR=lOdB 36 b 3.4. Optimum t h r e s h o l d (minimum BER) vs SNR f o r J=2 t o 5 37 3.5. Pb (3) vs ,V ; and V 2 f o r SNR=8dB 39 3.6. E ( y ) vs t h r e s h o l d f o r n=511 and SNR=5, 6, 7, 8 and 9dB 40 3.7. D i s c r e t e memoryless c h a n n e l r e s u l t i n g from q u a n t i z i n g the r e c e i v e r matched f i l t e r o u t p ut 42 3.8. Q u a n t i z a t i o n r e g i o n s of the r e c e i v e r matched f i l t e r o u t p u t 42 3.9. P^ (5) which o b t a i n e d from u s i n g t h e maximum c a p a c i t y and the minimum BER t h r e s h o l d s vs SNR f o r m=2 and 3 48 4.1. P y (5) vs SNR f o r t=5 and n=5H 53 4.2. E(W) vs t f o r n=5H and SNR=5, 6, 7 and 8dB 57 4.3. E(W) vs f f o r SNR=7dB and n=63, 127, 255, 51 1 and 1 023 58 4.4. SR-ARQ scheme 61 4.5. S t a t e diagram of the c o n v e n t i o n a l ARQ scheme 62 4.6. TJ vs P ^ f o r t h e c o n v e n t i o n a l h y b r i d and the memory (m=1 and 2) SR-ARQ w i t h SNR=8dB, n=!023, M=10 and b=30 65 v L i s t of T a b l e s T a b l e Page 3.1. The maximum c a p a c i t y and the minimum BER U=5) t h r e s h o l d s f o r SNR=8dB and m=2 t o 5 49 4.1. S i m u l a t i o n r e s u l t s f o r memory (m=2) ARQ w i t h SNR=8dB and n=511 55 4.2. Some t . f o r d i f f e r e n t SNR and n 60 opt 4.3. Some s i m u l a t i o n r e s u l t s of E(H) and E ( / ) f o r m=1, 2 and 3, SNR=8dB, M= 10 and n=l 023 64 v i ACKNOWLEDGEMENT I would l i k e t o thank Dr. C y r i l Leung f o r h i s s u p e r v i s i o n on t h i s t h e s i s . v i i 1. INTRODUCTION One commonly used method f o r t r a n s m i t t i n g messages r e l i a b l y i n a da t a communication system i s the Automatic Repeat Request (ARQ) scheme. In an ARQ system, the r e c e i v e r checks each d a t a b l o c k f o r p o s s i b l e e r r o r s . I f an e r r o r i s d e t e c t e d , a r e q u e s t f o r r e t r a n s m i s s i o n of the err o n e o u s b l o c k i s made. Many ARQ t r a n s m i s s i o n s t r a t e g i e s [1-16] have been proposed; commonly s t u d i e d schemes i n c l u d e Stop and Wait system, Go-Back-N system and S e l e c t i v e Repeat system. The Stop and Wait ARQ system [2] i s i l l u s t r a t e d i n f i g u r e 1.1. Here the t r a n s m i t t e r sends each d a t a b l o c k and w a i t s f o r an acknowledgement from the r e c e i v e r . A p o s i t i v e acknowledgement (ACK) i n d i c a t e s t h a t the b l o c k has been r e c e i v e d w i t h no e r r o r d e t e c t e d and the t r a n s m i t t e r w i l l send the next d a t a b l o c k . A n e g a t i v e acknowledgement (NACK) 'rsnsmitter R e c e i v e r e r r o r F i g u r e 1.1. Stop and Wait ARQ. 1 2 on the o t h e r hand i n d i c a t e s t h a t e i t h e r an e r r o r has been d e t e c t e d or no acknowledgement i s r e c e i v e d a f t e r some ti m e - o u t and the t r a n s m i t t e r w i l l r e s e nd the b l o c k . The t r a n s m i t t e r and the r e c e i v e r a r e i n an i d l e s t a t e w h i l e w a i t i n g f o r an acknowledgement and a d a t a b l o c k r e s p e c t i v e l y . T h i s reduces th e throughput of the system which i s d e f i n e d as the r e c i p r o c a l of the number of b i t s w hich c o u l d have been t r a n s m i t t e d c o n t i n u o u s l y i n the time t a k e n t o s u c c e s s f u l l y send one b i t of i n f o r m a t i o n . I n s t e a d of g o i n g i n t o the i d l e s t a t e , the t r a n s m i t t e r c o u l d send the d a t a b l o c k c o n t i n u o u s l y . Two commonly used continuous-mode systems a r e Go-Back-N and S e l e c t i v e Repeat ARQ. In a Go-Back-N ARQ system [ 2 ] , i l l u s t r a t e d i n f i g u r e 1.2, when a r e q u e s t f o r r e t r a n s m i s s i o n of a p a r t i c u l a r b l o c k i s r e c e i v e d , the r e q u i r e d b l o c k and a l l the p r e v i o u s l y F i g u r e 1.2. Go-Back-N ARQ. 3 t r a n s m i t t e d b l o c k s subsequent t o i t a r e r e t r a n s m i t t e d . T h i s p r o c e s s c o n t i n u e s u n t i l the r e q u i r e d b l o c k i s c o r r e c t l y r e c e i v e d and d u r i n g t h i s time the d a t a b l o c k s subsequent t o each r e t r a n s m i s s i o n of the r e q u i r e d b l o c k a r e i g n o r e d by the r e c e i v e r . T h i s system p r o v i d e s a h i g h e r t h r o u g h p u t than the S t o p and Wait system. A number of v a r i a t i o n s of the Go-Back-N system have been proposed [ 4 - 7 ] . However the r e t r a n s m i s s i o n of many p r e v i o u s l y r e c e i v e d e r r o r - f r e e b l o c k s f o l l o w i n g a r e t r a n s m i t t e d b l o c k l e a d s t o i n e f f i c i e n c y i n the Go-Back-N system. T h i s i n e f f i c i e n c y i s overcome i n the S e l e c t i v e Repeat ARQ system. In an i d e a l S e l e c t i v e Repeat ARQ system, the t r a n s m i t t e r resends the r e q u i r e d b l o c k once on e v e r y r e q u e s t f o r r e t r a n s m i s s i o n and c o n t i n u e s s e n d i n g o t h e r b l o c k s i n sequence as i l l u s t r a t e d i n f i g u r e 1.3. At the r e c e i v e r , o n l y Transmitter 1 Receiver 1 2* 3 4 5* 2 6 7* 5* 8 9 error F i g u r e 1.3. S e l e c t i v e Repeat ARQ. 4 those b l o c k s t h a t a r e d e t e c t e d i n e r r o r s a r e i g n o r e d . T h i s system p r o v i d e s v e r y h i g h t h roughput e f f i c i e n c y , but i n f i n i t e b u f f e r i s r e q u i r e d at the r e c e i v e r i n or d e r t o d e l i v e r d a t a b l o c k s t o the user i n c o r r e c t o r d e r . I f a f i n i t e b u f f e r i s used, b u f f e r o v e r f l o w may o c c u r which would reduce the throughput e f f i c i e n c y . Some v a r i a t i o n s on the S e l e c t i v e Repeat ARQ system [8-10] have been proposed t o overcome t h i s problem. For a c h a n n e l w i t h a h i g h b i t e r r o r r a t e (BER), e r r o r d e t e c t i o n and r e t r a n s m i s s i o n of da t a b l o c k s i s i n s u f f i c i e n t f o r a c h i e v i n g an a c c e p t a b l e t h r o u g h p u t . In t h i s c a s e , f o r w a r d e r r o r c o r r e c t i o n (FEC) [11-13] i s u s u a l l y i n c l u d e d i n the ARQ system. T h i s i s known as a h y b r i d ARQ system. In the above mentioned ARQ systems, t h e r e c e i v e r d i s c a r d s the i n f o r m a t i o n i n tho s e b l o c k s t h a t a r e d e t e c t e d i n e r r o r . In a memory ARQ system [ 1 4 - 1 6 ] , t h e r e c e i v e r s t o r e d e r r o n e o u s b l o c k s a l s o . T h i s may then be combined w i t h subsequent r e t r a n s m i s s i o n s i n o r d e r t o i n c r e a s e the t h r o u g h p u t . R e c e n t l y , B e n e l l i s u g g e s t e d a memory ARQ scheme w i t h s o f t e r r o r d e t e c t o r s [16] as shown i n f i g u r e 1.4. The o p e r a t i o n of the t r a n s m i t t e r i s i d e n t i c a l t o t h a t i n a c o n v e n t i o n a l ARQ system. At the r e c e i v e r , the r e c e i v e d s i g n a l i s i n p u t t o a h a r d and a s o f t demodulator. As i n the c o n v e n t i o n a l ARQ system, the h a r d demodulator c a r r i e s out a ha r d e s t i m a t e on the r e c e i v e d s i g n a l . A '+1* i s a s s i g n e d i f 5 Source B u f f e r Encoder Modulator ^ Feedback Channel * Forward Channel Sink Decoder t Hard Demodulator c R e l i a b i l i t y Updating S o f t Demodulator F i g u r e 1.4. B e n e l l i ' s memory ARQ scheme. the a m p l i t u d e of the r e c e i v e d s i g n a l y . i s p o s i t i v e ; o t h e r w i s e , a '-1' i s a s s i g n e d . The s u b s c r i p t s r e p r e s e n t the y'th t r a n s m i s s i o n of the /'th symbol i n a b l o c k . In the s o f t d e m o d u l a t o r , a r e l i a b i l i t y w eight w. . i s a s s i g n e d t o each J * ' r e c e i v e d symbol a c c o r d i n g t o the f o l l o w i n g r u l e : + 2 i f V < + 1 i f 0 < YJ , i < V -1 i f -V < YJ , i < 0 -2 i f yJ.i < -V where V i s a p r e d e t e r m i n e d t h r e s h o l d . The o u t p u t i s then used i n a r e l i a b i l i t y u p d a t i n g p r o c e s s t o be d e s c r i b e d i n the next c h a p t e r . The decoder f i r s t c hecks the b l o c k output by the s o f t demodulator f o r p o s s i b l e e r r o r s . I f an e r r o r i s 6 d e t e c t e d , i t t h e n c h e c k s t h e b l o c k o u t p u t by t h e h a r d d e m o d u l a t o r . I f an e r r o r i s a g a i n d e t e c t e d , a r e q u e s t f o r r e t r a n s m i s s i o n i s made . T h e r e s u l t s o f B e n e l l i ' s w o r k , o b t a i n e d by c o m p u t e r s i m u l a t i o n , i n d i c a t e t h a t t h e r e i s a s i g n i f i c a n t i m p r o v e m e n t i n t h e a v e r a g e number o f t r a n s m i s s i o n s o v e r t h e c o n v e n t i o n a l ARQ s y s t e m . B e c a u s e o f c o m p u t e r t i m e l i m i t a t i o n s , t h e b l o c k l e n g t h s w h i c h B e n e l l i u s e d i n t h e s i m u l a t i o n were r a t h e r s h o r t . I n t h i s t h e s i s , a memory ARQ s y s t e m i n w h i c h t h e number o f q u a n t i z a t i o n r e g i o n s i n t h e s o f t d e m o d u l a t o r i s a r b i t r a r y , i s s t u d i e d . The scheme i s d e s c r i b e d . i n s e c t i o n 2 . 1 . T h e r e s u l t i n g i m p r o v e m e n t s i n t h e BER a n d t h e a v e r a g e number o f t r a n s m i s s i o n s a r e a n a l y z e d i n s e c t i o n s 2 . 2 a n d 2 . 3 . T h e p e r f o r m a n c e o f t h e scheme d e p e n d s n o t o n l y on t h e number o f q u a n t i z a t i o n r e g i o n s b u t a l s o on t h e v a l u e s o f t h e t h r e s h o l d s a n d t h e w e i g h t s u s e d . C h a p t e r 3 d e s c r i b e s t h r e e a p p r o a c h e s t o d e t e r m i n e t h e t h r e s h o l d s v a l u e s . Once t h e t h r e s h o l d v a l u e s a r e d e t e r m i n e d , t h e op t imum (minimum BER) v a l u e s o f t h e w e i g h t s c a n be c a l c u l a t e d . I n c h a p t e r 4 , F E C i s i n c l u d e d i n t h e memory ARQ s y s t e m . T h e i m p r o v e m e n t s i n t h e b l o c k e r r o r r a t e (BKER) and t h e a v e r a g e number o f t r a n s m i s s i o n s o v e r c o n v e n t i o n a l h y b r i d ARQ s y s t e m s a r e d i s c u s s e d . The t h r o u g h p u t e f f i c i e n c y o f t h e s y s t e m i s a n a l y s e d i n s e c t i o n 4 . 1 . 2. MEMORY ARQ WITHOUT FEC In t h i s c h a p t e r , the memory ARQ w i t h no FEC i s c o n s i d e r e d . As f o r the e r r o r d e t e c t i o n scheme, the type of code used i s not of p a r t i c u l a r i n t e r e s t h e r e . The code can be chosen such t h a t the 2 ^ n ^ upper bound on the p r o b a b i l i t y of u n d e t e c t e d e r r o r [20] f o r an (n,k) b l o c k code i s s a t i s f i e d . The p r o b a b i l i t y of u n d e t e c t e d e r r o r can t h e r e f o r e be made a r b i t r a r i l y s m a l l . In t h i s t h e s i s , i t i s assumed t o be n e g l i g i b l e . 2.1 D e s c r i p t i o n of the ARQ scheme C o n s i d e r the b i n a r y s i g n a l i n g t r a n s m i s s i o n of an n - b i t d a t a b l o c k over an a d d i t i v e w h i t e g a u s s i a n n o i s e (AWGN) c h a n n e l . B i n a r y phase s h i f t k e y i n g (PSK) or f r e q u e n c y s h i f t k e y i n g (FSK) m o d u l a t i o n i s commonly used f o r t r a n s m i t t i n g the d a t a . In t h i s t h e s i s , b i n a r y PSK m o d u l a t i o n i s assumed. The a n a l y s i s t o be d e s c r i b e d can a l s o be a p p l i e d t o o t h e r b i n a r y m o d u l a t i o n schemes s i n c e any s e t of two s i g n a l v e c t o r s i n a t w o - d i m e n s i o n a l v e c t o r communication system can be r e d u c e d t o a s e t of two s i g n a l v e c t o r s i n a o n e - d i m e n s i o n a l v e c t o r communication system [ 2 4 ] . The o p e r a t i o n of the t r a n s m i t t e r i s s i m i l a r t o t h a t i n a c o n v e n t i o n a l ARQ system. Data b l o c k s a re t r a n s m i t t e d e i t h e r i n t h e Stop and Wait or the c o n t i n u o u s mode depending on the t y p e of ARQ system used. Every t r a n s m i t t e d b l o c k i s s t o r e d u n t i l the ACK s i g n a l i s r e c e i v e d . Suppose t h a t the 7 Message Source Packetizer Message Assembler Message Sink Packet Retransmission Controller Feedback Channel Decoder v . - J Modulator Gaussian Noise Additive Channel Matched F i l t e r Hard Detector Decision Accumulator Updating 2m-region Quantizer F i g u r e 2.1. B l o c k diagram of the memory ARQ system. 9 d a t a b l o c k t o be t r a n s m i t t e d i s d e n o t e d by ( b ^ , b ^ , . . . , where b ;. e { 0 , l } , /'= 1 , 2 , . . . , n . T h e n t h e i n p u t t o t h e v e c t o r c h a n n e l i s x = ( x ^ , x ^ , . . . , w h e r e : A i f b . =1 i - A i f b . =0 (2.1 ) A t t h e r e c e i v e r , t h e o u t p u t o f t h e m a t c h e d f i l t e r c o r r e s p o n d i n g t o t h e y ' th t r a n s m i s s i o n o f i s (y Yj 2""' Y j , n ) w h e r e Yjj = x/ + nj!i a n d * i ) , 1 ^ / ^ n , j = 1 , 2 , . . . , r e p r e s e n t o u t c o m e s o f i n d e p e n d e n t G a u s s i a n random v a r i a b l e s , e a c h w i t h v a r i a n c e a 2 . E a c h y . i s t h e n a s s i g n e d a r e l i a b i l i t y w e i g h t a c c o r d i n g t o e q u a t i o n ( 2 . 2 ) , w j >  1 +W m +W. +W -W -W. -W m V2 * V - V m-j , ' * y • • 0 . > y . . - V , > y . . i > h,i m- 1 > V > 0 > -v > -v. ( 2 . 2 ) w h e r e ' s a r e t h e w e i g h t s a n d V , ' s a r e p r e d e t e r m i n e d t h r e s h o l d s . F o r m=1, t h e o u t p u t o f t h e m a t c h e d f i l t e r i s 1 0 q u a n t i z e d i n t o two r e g i o n s , r e s u l t i n g i n a h a r d d e c i s i o n demodulator. I f the number of q u a n t i z a t i o n r e g i o n s exceeds two, t h a t i s m>1, the demodulator i s a s o f t d e c i s i o n demodulator. A complete s o f t d e c i s i o n demodulator i s one which the matched f i l t e r o u t p u t i s not q u a n t i z e d . • W i t h w e i g h t s a s s i g n e d t o each r e c e i v e d sample y . , the n - b i t b l o c k can be r e p r e s e n t e d by the v e c t o r w^. = (w^ . } , ) . w. i s used i n the r e l i a b i l i t y u p d a t i n g p r o c e s s . Here a d e c i s i o n a c c u m u l a t o r z. , l</<n, i s m a i n t a i n e d f o r each b i t i n the d a t a b l o c k . P r i o r t o the r e c e p t i o n of a b l o c k , a l l z. 's a r e r e s e t t o z e r o . A f t e r the y t h r e c e p t i o n of the da t a b l o c k , the a c c u m u l a t o r s a r e updated a c c o r d i n g t o : z . . = z . , . + w . . . ( 2 . 3 ) J J-1,i J , i The i n p u t s t o the decoder r. and v. a r e d e t e r m i n e d from: ^ -J -J r . . = J > 1 v . J , * 1 i f y. . > 0 0 i f y. . < 0 (2.4) J , 1 1 i f z. . > 0 J , i 0 i f z. . < 0 ( 2 . 5 ) J > i In the event t h a t z. . =0, v. . i s s e t t o e i t h e r ' 1 ' or '0' J , * J , 1 w i t h e q u a l p r o b a b i l i t y . At the de c o d e r , v i s f i r s t p r o c e s s e d t o de t e r m i n e i f i t i s a v a l i d codeword. I f i t i s , v i s a c c e p t e d ; o t h e r w i s e 11 r . i s decoded. I f r . i s a codeword, i t i s then a c c e p t e d ; - J ~ J o t h e r w i s e , a r e q u e s t f o r r e t r a n s m i s s i o n i s made.' The o p e r a t i o n of the decoder i s i l l u s t r a t e d i n t h e f l o w c h a r t of f i g u r e 2.2. Transmission Complete Transmission Complete No Request Packet Retransmission F i g u r e 2.2. F l o w c h a r t of the decod e r . 1 2 2.2 B i t E r r o r Rate A n a l y s i s U n l i k e c o n v e n t i o n a l ARQ s y s t e m s i n w h i c h t h e b i t e r r o r r a t e (BER) i s c o n s t a n t f o r a l l j's, t h e memory ARQ h a s a BER w h i c h d e c r e a s e s a s j i n c r e a s e s . F o r a g i v e n number / o f t r a n s m i s s i o n s t h e BER o f t h e memory ARQ i s a n a l y s e d . B a s e d on t h e a s s u m p t i o n s t h a t PSK m o d u l a t i o n i s u s e d a n d t h a t t h e c h a n n e l n o i s e i s AWGN, t h e p r o b a b i l i t y d i s t r i b u t i o n f u n c t i o n ( p d f ) o f y . . when a ' 1 ' ha s b e e n s e n t a n d t h e p d f o f y . . J ,  1 J >  1 when a ' 0 ' h a s b e e n s e n t a r e shown i n f i g u r e 2 . 3 . I f a ' 1 ' i s s e n t , t h e p r o b a b i l i t y t h a t y i f a l l s i n t h e r a n g e where a n e g a t i v e w e i g h t i s a s s i g n e d i s g i v e n b y : *m-l,e = Q [ ( k+Vm-2 ^ w. . = -W J , i rn w. . = -W m, e p ( y l i ) w . . = - W , J •  1 2 F i g u r e 2 . 3 . P r o b a b i l i t y d i s t r i b u t i o n f u n c t i o n o f y . 1 3 p , = Q [ ( A ) / a ] - p - - p , - . . . - p w. . = - W , * l , e 2,e 3,e * m , e j , i J ( 2 . 6 ) a n d t h e p r o b a b i l i t y t h a t y i f a l l s i n t h e r a n g e where a p o s i t i v e w e i g h t i s a s s i g n e d i s g i v e n b y : p = Q[ ( V . -k)/a] w. . = + W *m, c m-1 j ,i m P „ _ , , = Qt( V , - A ) / o ] - p m r w = + W m~ 1 s c m~ 2 m, c j , i tn J P , = Q[ ( V , - A ) / o ] - p , p w. . = + W . ^2, c 1 3, c cm, c j , i 2 p , = Q[ ( - A ) / a ] ~ p , - p , p w. . = + W . l,c 2,c 3,c * m , c j , i 1 ( 2 . 7 ) where Q [ a ] = f™ e x p ( - ^ - ) d x . I f y . . f a l l s i n t h e r a n g e where w . . = - W . i s a s s i g n e d , t h e n t h e p r o b a b i l i t y t h a t Zj . = S i s g i v e n b y : P y ( Zj t « S > - ( Z j _ I i t =S + W ; ) • P / > M o r e g e n e r a l l y , we h a v e t h e f o l l o w i n g : ( 2 . 8 ) PJ ( ZJ.i = S ) = ( ( Z / - 7 , / = S + W * > P * , e + m k=1 P / - 7 ( * J - l . t =S~ W * } P * , c } ( 2 ' 9 ) f o r - / W <S<y W , w h e r e 1 4 P ( z . ) = 0 0,1 1 i f z . = 0 o, i 0 o t h e r w i s e . When z . . =0, a *1' or a '0' i s chosen at random, each w i t h p r o b a b i l i t y 0.5. Hence, assuming a '1' was s e n t , the BER a f t e r J t r a n s m i s s i o n s i s : P, (J) = ^ P r ( z T . =0) + Z P, ( z , . = S ) . (2.10) b 2 J J, i a n s < 0 J J, i The BER P^ (/) f o r a g i v e n s i g n a l t o n o i s e r a t i o (SNR=201og!o{A/a}) i s dependent on the number of t h r e s h o l d s , the v a l u e s of the t h r e s h o l d s and the w e i g h t s used. For a complete s o f t d e c i s i o n d e t e c t o r , the f a c t t h a t each b i t i s t r a n s m i t t e d J t i m e s i s e q u i v a l e n t t o t r a n s m i t t i n g each b i t once w i t h the energy i n c r e a s e d by J t i m e s . T h e r e f o r e a lower bound f o r P^ (J) i s g i v e n by: P f c U) > Q(/7A/a). (2.11) F i g u r e 2.4 shows t h a t P^ {J) d e c r e a s e s as the number of t h r e s h o l d s (2m-l) i n c r e a s e s . In t h i s f i g u r e , SNR=8dB, the v a l u e s of t h e t h r e s h o l d s a r e o b t a i n e d by t h e minimum BER approach t o be d e s c r i b e d i n s e c t i o n 3.1. and w e i g h t s a r e o b t a i n e d by t h e method d e s c r i b e d i n s e c t i o n 3.4. P^ (/) i n d i c a t e d by "+" i s c a l c u l a t e d w i t h the v a l u e s of the t h r e s h o l d s o b t a i n e d by t h e maximum c a p a c i t y approach d i s c u s s e d i n s e c t i o n 3.3. Note t h a t t h e r e i s a g r e a t r e d u c t i o n i n BER when s o f t d e c i s i o n i s used i n s t e a d of h a r d d e c i s i o n , t h a t i s , the o u t p u t of the matched f i l t e r i s q u a n t i z e d i n t o more than two r e g i o n s . As the number of F i g u r e 2.4. P f c (/) vs number of t h r e s h o l d s (2m-l) f o r SNR=8dB and 7=1 t o 4. 16 t h r e s h o l d s i n c r e a s e s , t h e BER a p p r o a c h e s • t h e l o w e r b o u n d ( 2 . 1 1 ) w h i c h i s i n d i c a t e d by d a s h e d l i n e i n f i g u r e 2 . 4 . In t h e c a s e where t h e number o f q u a n t i z a t i o n r e g i o n s i s two ( m = l ) , t h i s h a r d d e c i s i o n ARQ w i t h memory i s e q u i v a l e n t t o t h e m a j o r i t y v o t e d e c i s i o n i n [ 1 7 ] . N o t e t h a t (y'=2/ + l ) = P^ (y=2/+2) f o r t h e h a r d d e c i s i o n ARQ w i t h memory where / i s a n o n - n e g a t i v e i n t e g e r ( s ee A p p e n d i x A f o r p r o o f ) . F i g u r e 2 . 5 shows how P^ ( / ) c h a n g e s w i t h SNR f o r d i f f e r e n t v a l u e s o f / . The number o f q u a n t i z a t i o n r e g i o n s i s e q u a l t o f o u r (m=2) and t h e w e i g h t s u s e d a r e o p t i m u m (minimum B E R ) . P^ (/=1) i s t h e p r o b a b i l i t y t h a t v^ . i s i n e r r o r w h i c h i s a l s o e q u a l t o t h e BER o f t h e h a r d d e c i s i o n ARQ w i t h o u t memory . P^ (/) i s t h e p r o b a b i l i t y t h a t v ^ . i s i n e r r o r a f t e r t h e / t h t r a n s m i s s i o n . A s / i n c r e a s e s , P^ ( / ) d e c r e a s e s r a p i d l y . T h i s i n c r e a s e s t h e p r o b a b i l i t y t h a t t h e b l o c k v ^ i s a v a l i d c o d e w o r d a f t e r / t r a n s m i s s i o n s . On t h e o t h e r h a n d , i n c o n v e n t i o n a l ARQ s y s t e m s w i t h no memory, P^ (j) i s c o n s t a n t f o r a l l j ' s a n d h e n c e t h e b l o c k e r r o r r a t e (BKER) i s a l s o c o n s t a n t f o r a l l y ' s . F i g u r e 2 . 6 i s a p l o t o f P f c (5) a g a i n s t SNR f o r m=1, 2 a n d 3 . A l s o shown i s t h e l o w e r b o u n d , Q ( / 5 A / a ) . F o r a t a r g e t BER o f 1 0 " 5 , t h e u se o f m=2 i n s t e a d o f m=1 r e s u l t s i n a s a v i n g s o f a b o u t 1.2 d B . I n c r e a s i n g t o m=3 s a v e s o n l y an e x t r a 0 . 2 d B . 1 7 F i g u r e 2.5. P, (/) vs SNR f o r m=2 and 7=1 t o 5. 18 F i g u r e 2.6. P. (5) vs SNR f o r m=1, 2 and 3. i 9 2.3 A n a l y s i s of Average Number of T r a n s m i s s i o n s So f a r the number of t r a n s m i s s i o n s J has been assumed f i x e d . As an example, i n the Advanced M o b i l e Phone S e r v i c e (AMPS) [ 1 7 ] , the messages a r e r e p e a t e d f i v e t i m e s . The d e c i s i o n on each b i t i s based on a m a j o r i t y v o t e when a l l f i v e r e p e a t s have been r e c e i v e d . However, i n o t h e r systems, / may not be f i x e d . I n s t e a d each b l o c k may be r e t r a n s m i t t e d u n t i l i t i s s u c c e s s f u l l y r e c e i v e d . In t h i s s e c t i o n we d e t e r m i n e the d i s t r i b u t i o n of the number of t r a n s m i s s i o n s / f o r a b l o c k of d a t a t o be s u c c e s s f u l l y t r a n s m i t t e d . In s e c t i o n 2.1, i t was s t a t e d t h a t the decoder f i r s t c hecks v. -J ; i f Y . i s not a codeword, i t then checks r . and i f r . i s J ~J 'J a l s o not a codeword, a r e t r a n s m i s s i o n i s r e q u e s t e d . When v i s i n e r r o r , t h e r e i s a h i g h p r o b a b i l i t y t h a t r . w i l l a l s o be e r r o n e o u s . T h i s w i l l be j u s t i f i e d by s i m u l a t i o n i n c h a p t e r 4. T h e r e f o r e i n a n a l y z i n g t h e a v e r a g e number of t r a n s m i s s i o n s E ( / ) , we assume t h a t the decoder examines o n l y v , and i g n o r e s r . L e t P be the p r o b a b i l i t y t h a t e x a c t l y j t r a n s m i s s i o n s are r e q u i r e d f o r a b l o c k t o be s u c c e s s f u l l y t r a n s m i t t e d , E be the e vent t h a t the b l o c k i s i n v a l i d a f t e r the y t h t r a n s m i s s i o n and E. be the event t h a t the b l o c k i s v a l i d J a f t e r t h e y t h t r a n s m i s s i o n . Then P , the p r o b a b i l i t y t h a t a l l t r a n s m i s s i o n s p r i o r t o y t h t r a n s m i s s i o n a r e u n s u c c e s s f u l and the y t h t r a n s m i s s i o n i s s u c c e s s f u l , i s g i v e n by: 20 P = Pr [ E 1 , E 2 , . . . , E ., ,E ] = P r [ E r E 2,... r E ]-Pr[ E 2,..., E _ 1 ,E ]. (2.12) The e x p e c t e d number of t r a n s m i s s i o n s f o r a b l o c k t o be s u c c e s s f u l l y t r a n s m i t t e d i s : E(/)= I / P. j = o y J = (1 - P r [ E , ] ) + 2( P r t E j ] - P r f E ^ E ^ ) + 3( P r [ E i r E 2 ] - P r [ E r E 2 , E 3 ] ) +... = 1 + P r [ E j + P r [ E 1 f E 2 ] + P r t E ^ E ^ E g ] +... (2.13) I f the p r o b a b i l i t y of u n d e t e c t e d e r r o r i s s m a l l enough t o be n e g l e c t e d , a b l o c k can be c o n s i d e r e d v a l i d i f and o n l y i f a l l b i t s i n the b l o c k are e r r o r f r e e . S i n c e t h i s i s the o n l y c o n d i t i o n f o r a b l o c k t o be s u c c e s s f u l l y r e c e i v e d , i t i s e a s i e r t o a n a l y z e E ( / ) i n term of E*. as f o l l o w s : J P r [ E 1 ] =1- P r [ E 1 ] P r [ E r E 2 ] = 1 - P r f E ^ - P r [ E 2 ] + P r f E ^ E ^ P r [ E 1 , E 2 , E 3 ] = 1 - P r t E ^ j - P r [ E 2 ] - P r [ E 3 ] + P r t E ^ E ^ ] + P r [ E 2 , E 3 ] + P r [ E r E 3 ] - P r [ E 1 f E 2 , E 3 ] P r [ E 1 , E 2 , E 3 , E 4 ] = 1 - Pr[Et] - P r [ E 2 ] - P r [ E 3 ] - P r [ E 4 ] + P r [ E 1 f E 2 ] + P r [ E 1 f E 3 ] + P r [ E l f E 4 ] + P r [ E 2 , E 3 ] + P r [ E 2 , E 4 ] + P r [ E 3 , E 4 ] -2 1 P r [ E 1 f E 2 , E 3 ] - P r [ E 1 , E 2 , E 4 ] - P r l E ^ E g , ^ ] -P r [ E 2 , E 3 , E 4 ] + P r [ E 1 , E 2 , E 3 , E 4 ] (2.14) and so on. Now, l e t n be the b l o c k l e n g t h . The p r o b a b i l i t y of E^ . can be e x p r e s s e d i n terms of the p r o b a b i l i t y t h a t a b i t i s v a l i d at the y t h t r a n s m i s s i o n a s : P r f E ^ = ( P r [ b i t v a l i d a t y = 1 ] ) n P r [ E 2 ] = ( P r [ b i t v a l i d a t y = 2 ] ) n P r [ E 1 , E 2 ] = ( P r [ b i t v a l i d a t y=1 , b i t v a l i d a t y = 2 ] ) n (2.15) and so on. From e q u a t i o n s (2.12-2.15), the d i s t r i b u t i o n of J and the average number of t r a n s m i s s i o n s can be d e t e r m i n e d . S i n c e t h e number of t h r e s h o l d s i s a r b i t r a r y i n the d e r i v a t i o n of the above e q u a t i o n s ,these a p p l y t o any memory ARQ scheme d e t e c t o r s i n c l u d i n g t h e hard d e c i s i o n and the complete s o f t d e c i s i o n . F i g u r e s 2.7, 2.8 and 2.9 a r e the t r e e diagrams d e m o n s t r a t i n g how the p r o b a b i l i t i e s P r [ b i t v a l i d a t y=1] , P r [ b i t v a l i d a t y'=2j, P r f b i t v a l i d a t j = 1 , b i t v a l i d a t y'=2], and so on, a r e d e t e r m i n e d f o r the h a r d d e c i s i o n , the t h r e e - t h r e s h o l d s o f t d e c i s i o n and the complete s o f t d e c i s i o n d e t e c t o r s r e s p e c t i v e l y . In t h e s e d i a g r a m s , an upward p o i n t i n g branch r e p r e s e n t s a v a l i d b i t whereas a downward p o i n t i n g branch r e p r e s e n t s an i n v a l i d b i t . The v a l u e i n F i g u r e 2.7. Tree diagram f o r h a r d d e c i s i o n d e t e c t o r . 23 <+2) P2,c ( + 1 ) P P2.cP2.c P2.cPl,c P2.cPJ,e P2,cP2.e P2,cP2.< P,.cP2,c P l , c P l , c PJ,cPJ,e PJ.cPJ,e Pl.cP2,e ( - 1 ) P l.e <'2> P2.c F i g u r e 2.8. Tree diagram f o r m=2 s o f t d e c i s i o n d e t e c t o r 24 / f d ) / f ( y ) d y d i x-0 y»-x / f d ) / f ( y > d y d x »-0 ym-m I f i x ) J f ( y ) d y d x x--» y - - x 0 -* / f i x ) / f ( y > d y d x s x-0 x-0 x-0 x-0 0 ; x--» 0 / » » - • 0 / »•-» x) / f ( y ) / f(z) dzdydx y - - x »»-x - y - x - y x ) / f ( y ) / f i x ) d z d y d x y--x «•-• -x » x) / f ( y ) / tit) d z d y d x T — x - - x - y -x - x - y x ) / f ( y ) } lit) d z d y d x ym-m X--» x) / f l y ) / f ( z ) d z d y d x y--x x - - x - y - - x - y x ) / f ( y ) / f i x ) d z d y d x y»-x »•-• -x *• x ) / f ( y ) / f l z ) d z d y d x j.-m z — x - y -x - x - y x> / f < y > / f l z ) d z d y d x y--» «•-» 1(a) = ^  exp(-(-*=^ } T r e e diagram f o r complete s o f t d e c i s i o n d e t e c t o r . 25 p a r e n t h e s i s i s the r e s u l t a n t weight a f t e r j t r a n s m i s s i o n s and b e s i d e i t i s t h e p r o b a b i l i t y . P r [ b i t v a l i d a t ;'=/] i s eq u a l t o t h e sum of t h e p r o b a b i l i t i e s of a l l the upward branches a t j=i and P r [ b i t v a l i d a t j=i , b i t v a l i d a t j=l ] i s e q u a l t o the sum of the p r o b a b i l i t i e s of a l l the upward branches a t j=l which j o i n t o any upward branches a t j=i where />/. Other c o m b i n a t i o n s can be det e r m i n e d i n the s i m i l a r way. The weight d i s t r i b u t i o n used i n t h i s s e c t i o n i s (-2,-1,1,2) i n s t e a d of the optimum (minimum BER) w e i g h t s . As shown i n f i g u r e 2.10, t h e r e i s no s i g n i f i c a n t improvement i n the average number of t r a n s m i s s i o n s i f the optimum weight d i s t r i b u t i o n i s used. F o r s i m p l i c i t y , i n t e g e r w e i g h t s a re used. The t h r e s h o l d v a l u e used here i s 0.4A. F i g u r e 2.11 shows t h a t f o r a g i v e n BKER (^  1 - ( 1 - Q [ A / a ] ) n ) , d i f f e r e n t c o m b i n a t i o n s of SNR's and b l o c k l e n g t h s w i t h i n the range of i n t e r e s t do not make a s i g n i f i c a n t d i f f e r e n c e i n the average number of t r a n s m i s s i o n s . In the c o m p u t a t i o n of the average number of t r a n s m i s s i o n s , t h e b l o c k l e n g t h i s f i x e d a t 511 b i t s . D i f f e r e n t v a l u e s of the BKER a r e o b t a i n e d by changing the SNR. F i g u r e 2.12 shows t h e d i s t r i b u t i o n of J f o r the c o n v e n t i o n a l ARQ, the h a r d d e c i s i o n memory ARQ and the t h r e e - t h r e s h o l d s o f t d e c i s i o n memory ARQ systems. The average number of t r a n s m i s s i o n s f o r the c o n v e n t i o n a l ARQ (c u r v e a ) , the ha r d d e c i s i o n ARQ w i t h memory (curve b ) , the 26 F i g u r e 2.10. E(/) vs w e i g h t s (-W, - 1 , +1, +W) f o r SNR=7, 8, 9 and 10 dB. 27 o m i n Blocklength n oo BKER=0.9 3 °. BKER=0.7 00 CM CM CM CM H OO C -+ + 5> + tO H + 2? ^ •7* CM + + Lf\ CM H x * -m BKER=0.5 00 + "3" • 00 CTi o 00 tO • + c— E— - 3 -CM CM + CM i n + 00 00 CM + i n CM H + H • cn oo • to H + CM Lf\ m CO 00 + + o CM CM " l r— 8.0 9.0 SNR (dB) 6.0 7.0 10.0 11.0 F i g u r e 2.11. E(J) vs SNR f o r BKER=0.5, 0.7 and 0.9. 28 C O o CD o o C\J o o 0 «>•¥ 1 D c o n v e n t i o n a l A one-threshold x t h r e e - t h r e s h o l d r — T 4 1 F i g u r e 2.12. D i s t r i b u t i o n of J f o r the con v e n t i o n a l ARQ and the memory (m=l and 2) ARQ systems with 3NR=9dB and n=511. 29 BKER F i g u r e 2.13. E(7) vs BKER f o r t h e c o n v e n t i o n a l ARQ and the m=1, 2 and co m p l e t e s o f t d e c i s i o n d e t e c t o r memory ARQ systems (n=511). 30 t h r e e - t h r e s h o l d s o f t d e c i s i o n ARQ w i t h memory (cu r v e c) and the complete s o f t d e c i s i o n ' ARQ w i t h memory ( c u r v e d) schemes ar e d e p i c t e d i n f i g u r e 2.13. Except f o r the hard d e c i s i o n ARQ w i t h memory a t BKER < 0.4, a l l the ARQ schemes w i t h memory a r e s u p e r i o r t o the c o n v e n t i o n a l ARQ scheme i n terms of the average number of t r a n s m i s s i o n s . The reason i s as f o l l o w s : In the event i n which a b l o c k i s t r a n s m i t t e d and the f i r s t and second t r a n s m i s s i o n s c o n t a i n £ and 0 e r r o r s r e s p e c t i v e l y , the c o n v e n t i o n a l ARQ system w i l l r e q u i r e 2 t r a n s m i s s i o n s . I f the h a r d d e c i s i o n memory ARQ system i s used, more than 2 t r a n s m i s s i o n s w i l l be r e q u i r e d w i t h p r o b a b i l i t y 1-(0.5) . However, i n an a c t u a l i m p l e m e n t a t i o n where the decoder checks b o t h v. and r . , the h a r d d e c i s i o n -J 'J memory ARQ scheme w i l l y i e l d a lower average number of t r a n s m i s s i o n s . A s i m p l e l ower bound f o r the average number of t r a n s m i s s i o n s can be o b t a i n e d by c o n s i d e r i n g the f i r s t two terms on the R.H.S. of e q u a t i o n ( 2 . 1 3 ) . E ( / ) > 1+BKER (2.16) T h i s lower bound i s shown as c u r v e e i n f i g u r e 2.13. Even though c u r v e d i s a t i g h t e r lower bound, i t can be seen t h a t the lower bound g i v e n by (2.16) i s v e r y good f o r low BKER v a l u e s . Comparing c u r v e c and c u r v e d, we see t h a t the average number of t r a n s m i s s i o n s f o r t h e t h r e e - t h r e s h o l d scheme i s 31 o n l y s l i g h t l y h i g h e r . For any number of t h r e s h o l d s g r e a t e r than t h r e e , the average number of t r a n s m i s s i o n s w i l l l i e between cu r v e c and c u r v e d. S i n c e t h e average number of t r a n s m i s s i o n s does not d e c r e a s e much as we i n c r e a s e the number of t h r e s h o l d s , we s h a l l o n l y c o n c e n t r a t e on the t h r e e - t h r e s h o l d s o f t d e c i s i o n ARQ w i t h memory. I n c r e a s i n g the number of t h r e s h o l d s w i l l i n c r e a s e t h e i m p l e m e n t a t i o n c o m p l e x i t y . 3. THRESHOLDS DETERMINATION In t h i s c h a p t e r the problem of c h o o s i n g the t h r e s h o l d s i n t h e memory ARQ scheme w i t h s o f t d e c i s i o n d e t e c t o r s i s a d d r e s s e d . Three d i f f e r e n t approaches a r e c o n s i d e r e d : 1. Choose the t h r e s h o l d s so as t o m i n i m i z e the BER. 2. Choose the t h r e s h o l d s so as t o m i n i m i z e the average number of t r a n s m i s s i o n s . 3. Choose the t h r e s h o l d s so as t o maximize the c h a n n e l capac i t y . In t h e f i r s t a pproach, a f i x e d number of t r a n s m i s s i o n s i s assumed. As an example, i n the AMPS [17] system, a b l o c k i s t r a n s m i t t e d s u c c e s s i v e l y f i v e t i m e s i n o r d e r t o ensure t h a t the p r o b a b i l i t y of a r e p e a t r e q u e s t i s below some s p e c i f i e d v a l u e . Here i t i s a p p r o p r i a t e t o use the f i r s t approach t o d e t e r m i n e the minimum P, (/=5) t h r e s h o l d v a l u e s . In o t h e r b c a s e s where the minimum average number of t r a n s m i s s i o n s i s r e q u i r e d , d e t e r m i n a t i o n of the t h r e s h o l d s based on minimum E(/) i s more s u i t a b l e . These two approaches f o r d e t e r m i n i n g the optimum t h r e s h o l d s use a n u m e r i c a l s e a r c h t e c h n i q u e . As the number of t h r e s h o l d s i n c r e a s e s , the computer time i n v o l v e d can become v e r y l o n g . An a l t e r n a t i v e i s the t h i r d a p p r o a c h w h i c h i s a f a s t method f o r d e t e r m i n i n g the t h r e s h o l d s f o r an a r b i t r a r y number of q u a n t i z a t i o n r e g i o n s . T h i s a p p r o a c h i s based on m a x i m i z i n g the c h a n n e l c a p a c i t y or m i n i m i z i n g the e q u i v o c a t i o n as i n [18] where up t o f o u r q u a n t i z a t i o n r e g i o n s a r e d i s c u s s e d . D e t a i l s of each approach a r e g i v e n i n the f o l l o w i n g s e c t i o n s . 32 33 3.1 Minimum B i t E r r o r Rate Approach C o n s i d e r the memory ARQ w i t h m=2. F i g u r e s 3.1, 3.2 and 3.3 show how (/) v a r i e s w i t h the t h r e s h o l d f o r SNR=6dB, 8dB and 1fJdB r e s p e c t i v e l y . The optimum weight d i s t r i b u t i o n has been used f o r c a l c u l a t i n g P^ (J) f o r each g i v e n t h r e s h o l d . The d e t e r m i n a t i o n of the optimum weight based on minimum BER i s d i s c u s s e d i n s e c t i o n 3.4. At a f i x e d SNR, the optimum t h r e s h o l d (minimum BER) i s q u i t e i n s e n s i t i v e t o J. The c u r v e s a l s o i n d i c a t e t h a t P^ (/) become more s e n s i t i v e t o t h e t h r e s h o l d as the SNR i n c r e a s e s . For a v e r y h i g h t h r e s h o l d v a l u e , the p r o b a b i l i t y t h a t the r e c e i v e d s i g n a l f a l l s above the t h r e s h o l d i s a l m o s t z e r o . T h i s i s e q u i v a l e n t t o the case where the t h r e s h o l d v a l u e i s z e r o as can be n o t e d i n f i g u r e s 3.1, 3.2 and 3.3. For SNR v a r i a t i o n between OdB t o 12dB, the v a r i o u s optimum t h r e s h o l d v a l u e s (minimum BER) w i t h J=2, 3, 4 and 5 a r e shown i n f i g u r e 3.4. An e m p i r i c a l f o r m u l a (/=2) can be o b t a i n e d f o r t h e optimum t h r e s h o l d ( n o r m a l i z e d t o A) as a f u n c t i o n of SNR i n dB by a p p r o x i m a t i n g the c u r v e (7=2) w i t h an e x p o n e n t i a l f u n c t i o n . The f u n c t i o n (dashed l i n e i n f i g u r e 3.4) which g i v e s minimum l e a s t square e r r o r i s found t o be: V = a 0 + a, e x p ( a 2 SNR) (3.1) opt where a 0 = 0.22452728, a, = 0.61318152 and a 2 = -0.15031385, w i t h a l e a s t square e r r o r of 5 . 5 x l 0 " 5 . I t was n o t e d e a r l i e r t h a t the optimum t h r e s h o l d i s i n s e n s i t i v e t o / and P^ (/) e x h i b i t s broad minimum a t low SNR, i t i s t h e r e f o r e not 34 F i g u r e 3.1. P, (/) vs t h r e s h o l d f o r m=2 and SNR=6dB. 35 36 F i g u r e 3.3. P.(^) v s t h r e s h o l d f o r m=2 and SNR=lOdB. 37 F i g u r e 3 . 4 . Opt imum t h r e s h o l d (min imum BER) v s SNR f o r J=2 t o 5 . 38 n e c e s s a r y t o determine the e m p i r i c a l formulae f o r J>2. The method f o r d e t e r m i n i n g the t h r e s h o l d v a l u e s f o r an a r b i t r a r y number of t h r e s h o l d s which m i n i m i z e (/) f o r a g i v e n / and SNR i s now d i s c u s s e d . F i r s t c o n s i d e r a scheme which has s i x q u a n t i z a t i o n r e g i o n s and f o r which two t h r e s h o l d v a l u e s ( and ) a r e r e q u i r e d . F i g u r e 3.5 shows how P, (J=3) v a r i e s w i t h V. and V. where V_ > V. . An 0 1 2 2 1 ad-hoc a l g o r i t h m f o r d e t e r m i n i n g the v a l u e s of and which m i n i m i z e P. (J) i s as f o l l o w s : b S t e p 1. L e t Pb] = 1 . S t e p 2. F i x where > 0, s e a r c h f o r where > such t h a t P, (J) i s minimum. b S t e p 3. U s i n g the v a l u e o b t a i n e d i n s t e p 2, s e a r c h f o r where V. > V. > 0 such t h a t P. (/) i s minimum. 2 1 b Denote t h i s minimum v a l u e by P ^ . S t e p 4. I f | P^2 - P^j | i s g r e a t e r than some t o l e r a n c e , then l e t P ^ = Pb2 and r e p e a t s t e p 2 t h r o u g h s t e p 4. O t h e r w i s e t a k e and as the optimum t h r e s h o l d s . T h i s method can be extended t o a l a r g e r number of t h r e s h o l d s . At each s t e p , a l l but one t h r e s h o l d a re kept f i x e d . P, (/) i s then m i n i m i z e d over .that t h r e s h o l d b v a r i a b l e . 3.2 Minimum Average Number of T r a n s m i s s i o n s Approach One o b j e c t i v e i n the d e s i g n of an ARQ scheme i s t o m i n i m i z e the average number of t r a n s m i s s i o n s r e q u i r e d per 39 F i g u r e 3 . 5 . P f c ( 3 ) v s V ; a n d V 2 f o r SNR=8dB. 40 F i g u r e 3.6. E ( / ) vs t h r e s h o l d f o r n=511 and SNR=5, 6, 7, 8 and 9 dB. 4 1 d a t a b l o c k . The optimum t h r e s h o l d s can be o b t a i n e d by a n u m e r i c a l s e a r c h t e c h n i q u e . The a l g o r i t h m f o r d e t e r m i n i n g the minimum BER t h r e s h o l d s d e s c r i b e d i n s e c t i o n 3.1 can be used h e r e . F i g u r e 3.6 shows how the v a l u e of the t h r e s h o l d a f f e c t s the average number of t r a n s m i s s i o n s f o r v a r i o u s SNR i n the t h r e e - t h r e s h o l d memory ARQ system w i t h n=5l1. The c u r v e s i n d i c a t e t h a t the optimum t h r e s h o l d based on the minimum average number of t r a n s m i s s i o n s i s f a i r l y c o n s t a n t f o r SNR>7dB. Each cu r v e a l s o e x h i b i t s a broad minimum. A good compromise v a l u e f o r the optimum t h r e s h o l d i s 0.4A which i s the v a l u e used i n the a n a l y s i s of the average number of t r a n s m i s s i o n s i n s e c t i o n 2.3. i 3 . 3 Maximum Channel C a p a c i t y Approach A method f o r d e t e r m i n i n g a s e t of t h r e s h o l d s based on ma x i m i z i n g the c a p a c i t y of the d i s c r e t e memoryless c h a n n e l (DMC) which r e s u l t s from q u a n t i z i n g the r e c e i v e r matched f i l t e r o u t p u t i s d i s c u s s e d i n t h i s s e c t i o n . The DMC shown i n f i g u r e 3.7 can be d e s c r i b e d by the f o l l o w i n g t r a n s i t i o n p r o b a b i l i t i e s : P( Y=+W m 1 ( P +P ) 2 cm em P( Y=+W P( Y=+W P( Y=-W 2 v cl el ' - ( P +P ) 2 V c/ e/ ' 42 F i g u r e 3.7. D i s c r e t e memoryless c h a n n e l r e s u l t i n g from q u a n t i z i n g the r e c e i v e r matched f i l t e r o u t p u t . P( y=-w 2 ) = 1 ( p c 2 + p e 2 ) (3.2) where P . and P . , /=1,2,...,m a r e g i v e n by the f o l l o w i n g : F i g u r e 3 . 8 . Q u a n t i z a t i o n r e g i o n s of t h e r e c e i v e r matched f i l t e r o u t p u t . 43 P c m . j - Q K V m . 2 . - A ) / a ] - Q[( Vm_1 -K)/o] Pc2 = Q [ ( v ; " A ) / a ] ' °- [ ( V 2 _ A ) / ° ] P c ; = Q [ - A / o ] - Q[( V ; - A ) / a ] em m~ J P*m-i = Q [ ( V ™ - ? + A ) / ° ^ ~ Q K V m . + A ) / a ] e / w - y w 2 m J Pe2 = Q [ ( V 7 + A ) / a ] ~ Q [ ( V 2 + A ) / ° ] Pel = Q [ A / f f ] ~ Q t ( V 7 + A ) / ° ] ( 3 - 3 ) T h e c a p a c i t y o f t h e a b o v e c h a n n e l i s t h e m u t u a l i n f o r m a t i o n l ( X ; Y ) m a x i m i z e d o v e r P ( x ) . T h i s o c c u r s when t h e i n p u t s a r e e q u a l l y l i k e l y a n d t h e r e f o r e t h e c h a n n e l c a p a c i t y c a n be w r i t t e n a s : C = max [ I ( X ; Y ) ] p ( x ) = max [ H ( X ) - H ( X | Y ) ] p ( x ) = 1 + Z p ( x , y ) l o g { p ( x | y ) } = 1 + Z p ( y ) p ( x | y ) l o g { p ( x | y ) } x , y = 1 + 1 p ( y ) Z p ( x | y ) l o g { p ( x | y ) } y * 44 = 1 - 2 p ( y ) Z ( p ( y | x ) p ( x ) / p ( y ) } l o g { p ( y ) / p ( y | x ) p ( x ) } y x m = 1 - Z ( P . + P . ) h [ P . / ( P . +.P . ) ] (3.4) ^_ 1 c i e i ci e i a where h [ e ] = e l o g {1 / e } + (1 - e ) l o g {1/(1 -e) } i s t h e b i n a r y e n t r o p y f u n c t i o n ( l o g d e n o t e s l o g a r i t h m t o t h e b a s e 2 ) . N o t e t h a t t h e w e i g h t s { } a s s o c i a t e d w i t h t h e q u a n t i z a t i o n r e g i o n s do n o t a f f e c t t h e c a p a c i t y . In o r d e r t o o b t a i n t h e t h r e s h o l d v a l u e s w h i c h m a x i m i z e t h e c h a n n e l c a p a c i t y , t h e p a r t i a l d e r i v a t i v e e q u a t i o n (3.4) w i t h r e s p e c t t o e a c h t h r e s h o l d i s e q u a t e d t o z e r o . T h e t h r e s h o l d v a l u e s c a n t h e n be o b t a i n e d by s o l v i n g t h e r e s u l t i n g s e t o f m-1 n o n - l i n e a r s i m u l t a n e o u s e q u a t i o n s . T a k i n g t h e p a r t i a l d e r i v a t i v e s o f e q u a t i o n (3.4) w i t h r e s p e c t t o where / = 1 , 2 , . . . , m - 1 we g e t t h e f o l l o w i n g : -.r, .> m P . + P . Fv, - -hr; < . V p«' 1 o 9 ( - ^ — - » + / / i= 1 ci . P . + P . e i m 3 P . P . + P . - - . V r v f iog(-^—" » + 1=1 / a , a p . 9 p . l o g e , p e_t _ ci ) P . + P . ci 9 V . ei 9 V . ' c i e i I i 9 P . P . + P . ei i„„t_ci e± s / ei , 9 P . 9 P . l o 9 e ( p £1 - p ti )] P . + P . v ei 9 V . c i 9 V , ' J ci ei I I 45 m 9 P . P . + P . 3 P . P . + P . - " - V ^ T 1 o 9 ( - T - — ) +crvr l o g ( — p - — • ) ] 1 = 1 / ci I ei ( 3 . 5 ) 9 P . 9 P . d v a n d Q ^- c a n be o b t a i n e d by p a r t i a l l y d i f f e r e n t i a t i n g e q u a t i o n ( 3 . 3 ) w i t h r e s p e c t t o e a c h t h r e s h o l d a s f o l l o w s : 9 P cm - ~ m e x p [ " ( V ; -A>V2C»] 7^ e x p [ - ( Vm_2 - A ) 2 / 2 a 2 ] m- I 9 V m- 7 9 P cm- 1 9 V m-2 9 P cm- 1 5 P c 2 9 V , 9 P , c 2 9 p c ; 9 v ; - ^ e x p [ - ( v y - A ) 2 / 2 a 2 ] + T== e x p [ - ( V , - A ) 2 / 2 a 2 ] 9 V 2 / 2 T T ^ L V 2 + 7= e x p [ - ( V y - A ) 2 / 2 a 2 ] 9 P , em 1 n T " - - m E X P [ - ( V ; + A ) » / 2 . ' l 1 46 9 P . 2 3 V , 9 Pe2 b V , 9 Pel b V , = " / I i e x P [ _ ( V ; + A ) 2 / 2 a 2 ] = + e x p [ - ( V 2 + A ) 2 / 2 a 2 ] = + ^ e x p [ - ( V ; + A ) 2 / 2 a 2 ] ( 3 . 6 ) F r o m e q u a t i o n ( 3 . 3 ) a n d ( 3 . 6 ) , we n o t e t h a t P . a n d P . a r e ^ ci e i d e p e n d e n t on V^. a n d V\ _j e x c e p t f o r Pc] a n d Pg] w h i c h d e p e n d o n l y on V , a n d f o r P a n d P w h i c h d e p e n d o n l y on V , . J cm em r J m- J A l s o n o t e t h a t : cj_ cl * 1 , el el * 1 b V z = 3 V / a n 0 3 V / = 3 Vt ( 3 . 7 ) T h e r e f o r e e q u a t i o n ( 3 . 5 ) c a n be s i m p l i f i e d t o : 3C _ r c j cl el v , — - - [ g — l o g ( p— ) + / / cl bP P + P 0 c l * l . , lcl±J__J_el+J.\ + L 0 9 < > « M ; 1 3 P , P , + P , e/_ cl ej_ ^ g - ^ r - l o g ( p— ) + / el el* 1 , / c / + 7 e/ + 7 N i 1 0 9 < —^77, - - i r v r l 0 ^ p c i < p • p ) ) 47 e_L •> n „ r cl el el + 1 •> •, c T v T 1 o 9 { P . ( P / + . + P L ¥ . ) } ] / el c/ + 7 el *• 1 ( P , + P . ) P , . . cl el cl +7 - - m [ « P ! - < V , - A ) V 2 » ' } l - o 9 t p - p „ p - , ) • cl cl + 7 e/ + 7 «p{-( V, ^ A ) V 2 . ' } l o 9 { p I ! p e ' ^ , } ] , el cl + 7 e/ + 7 / = 1 , 2 , . . . , m - 1 ( 3 . 8 ) S e t t i n g e q u a t i o n ( 3 . 8 ) t o z e r o , a s e t o f n o n - l i n e a r e q u a t i o n s i s o b t a i n e d w h i c h c a n be s o l v e d n u m e r i c a l l y f o r t h e t h r e s h o l d v a l u e s w h i c h m a x i m i z e t h e c h a n n e l c a p a c i t y . F o r a g i v e n SNR v a l u e , t h e r e s u l t i n g s e t o f e q u a t i o n s c a n be s o l v e d f o r n u m e r i c a l l y , e x a m p l e u s i n g N e w t o n ' s m e t h o d [ 2 3 ] , To i l l u s t r a t e t h e u s e f u l n e s s o f t h i s a p p r o a c h , P^ (5) w h i c h o b t a i n e d f r o m u s i n g t h e maximum c a p a c i t y a n d t h e minimum BER t h r e s h o l d s a r e p l o t t e d a s a f u n c t i o n o f SNR i n f i g u r e 3 . 9 . F o r a BER o f 1 0 ~ 5 , u s i n g t h e maximum c a p a c i t y t h r e s h o l d s f o r m=2 a n d 3 r e s u l t i n a l o s s o f a b o u t 0 . 2 a n d 0.1 dB r e s p e c t i v e l y . T a b l e 3.1 p r e s e n t s t h e maximum c a p a c i t y a n d t h e minimum BER (7=5) t h r e s h o l d s f o r SNR=8dB a n d m=2, 3 , 4 a n d 5 . N o t e t h a t t h i s a p p r o a c h i s c o m p u t a t i o n a l l y a t t r a c t i v e when t h e number o f t h r e s h o l d s i s l a r g e . 3 . 4 Opt imum (minimum BER) w e i g h t d e t e r m i n a t i o n F o r t h e p u r p o s e o f d e t e r m i n i n g t h e o p t i m u m w e i g h t s , t h e J r e p e a t s o f a b i t i n t h e memory ARQ s y s t e m c a n be v i e w e d a s t h e N^ (=/) s a m p l e s o f a r e c t a n g u l a r p u l s e t o be p r o c e s s e d by t h e o p t i m u m W e i g h t e d P a r t i a l D e c i s i o n (WPD) [ 1 9 ] . T h e 48 F i g u r e 3 . 9 . (5) which o b t a i n e d from u s i n g the maximum c a p a c i t y and the minimum BER t h r e s h o l d s vs SNR f o r m=2 and 3 . 49 m Minimum P^(5) Thresholds Maximum Capacity Thresholds CPU Time P b(5) 2 0.4635 0.2722 lOsec 3sec 0.530l5846xl0" 7 0.13040362xl0' 6 3 0.2984 0.6350 0.1622 0.4012 2min 4sec 0.22741592xl0" 7 0.40453194xlO" 7 4 0.2082 0.4288 0.7197 0.1168 0.2598 0.4839 7min 5sec 0.15679730xl0" 7 0.25115463xlO" 7 5 0.1706 0.3337 0.5178 0.7666 0.0916 0.1954 0.3299 0.5444 30min 6sec 0.13214319xl0' 7 0.18418953xl0"" 7 T a b l e 3.1. The maximum c a p a c i t y and the minimum BER (/=5) t h r e s h o l d s f o r SNR=8dB and m=2 t o 5. 50 op t imum d e c i s i o n r u l e i n t h e c a s e o f b i n a r y s i g n a l i n g and 2m q u a n t i z a t i o n r e g i o n s i s a s f o l l o w s ( s ee e q u a t i o n (20) i n [ 1 9 ] ) . D e c l a r e a '1' was s e n t i f : P P Z I n p + . . . + Z In ^ + x . . e R em x . . e R - , e 2 j ,i cm j,i c 2 P P Z I n ^ + Z I n . . . + x . . e R , el x . e R cm j,i cl j , i em P . P Z I n + Z I n p > 0 (3.9) x . . e R _ c 2 x . . e R , c1 j , i e 2 j , i el o t h e r w i s e d e c i d e '0' was s e n t . F r o m t h e d e c i s i o n r u l e (3.9), i t c a n be s e e n t h a t t h e o p t i m u m w e i g h t s a s s o c i a t e d w i t h t h e r e g i o n s R , a n d R , , / = 1 , 2 , . . . , m i s l n ( P . / P . ) a n d l n ( P e l ^ P c / ^ r e s p e c t i v e l y . In t h e c a s e o f f o u r q u a n t i z a t i o n r e g i o n s , i n e q u a l i t y (3.9) b e c o m e s : P , P Z I n ^ + Z I n ^ -x . . e R - . e 2 x . . e R , e l j , i c2 j , i cl P P . Z I n p - Z, I n > 0 ( 3 . 1 0 ) x . e R , e l x . . e R - e 2 j , i el j , i e 2 D i v i d i n g ( 3 . 1 0 ) by l n ( P c I / P ^ ) we g e t : l n ( Pc2 * Pe2 » x. . , R , LN< P d ' Pel j , i c2 Z 1 - Z n c * , n t z , > 0 ( 3 . 1 1 ) j , i el j ,i e2 J, I z 1 -' Rcl l n { Pc2 ' Pe2 ) > l n ( P c 7 ' P e l ) 51 The optimum weight a s s o c i a t e d w i t h each r e g i o n i s thus g i v e n by: Region Optimum Weight R , - l n ( P , / P . ) / l n ( P , / P . ) e 2 c 2 e 2 d e l R . -1 e 1 R , +1 c 1 R , +ln( P , / P , ) / l n ( P , / P , ) c2 c 2 e 2 cl el As an example, f o r SNR=8dB, 7=5 and threshold=0.4635A ( t a b l e 3.1), the minimum BER w e i g h t s are -3.38, - 1 , +1 and +3.38. 4 . MEMORY ARQ WITH F E C I n t h i s c h a p t e r , t h e u s e o f f o r w a r d e r r o r c o r r e c t i o n ( F E C ) i n c o n j u n c t i o n w i t h t h e memory ARQ i s e x a m i n e d . W i t h F E C , a d a t a b l o c k w i l l be c o r r e c t l y d e c o d e d a s l o n g a s t h e number o f e r r o n e o u s b i t s d o e s n o t e x c e e d t h e n u m b e r , t, o f c o r r e c t a b l e e r r o r s o f t h e c o d e u s e d . C o n s i d e r t h e scheme i n w h i c h t h e number / o f r e p e a t s i s g i v e n . S i n c e b i t e r r o r s a r e i n d e p e n d e n t , t h e r e p e a t r e q u e s t p r o b a b i l i t y a f t e r J s u c c e s s i v e t r a n s m i s s i o n s c a n be w r i t t e n a s : t n P , (/) = 1 - Z ( ) P . ( J ) 1 ( 1 - P . ( / ) ) n 1 ( 4 . 1 ) i=0 i b b I n t h e c o n v e n t i o n a l ARQ s y s t e m , t h e r e p e a t r e q u e s t p r o b a b i l i t y a f t e r / s u c c e s s i v e t r a n s m i s s i o n s i s e q u a l t o t h e p r o b a b i l i t y t h a t a l l t h e J b l o c k s f a i l a n d i s g i v e n b y : P v (J) = [1 - I ( D ) p M l - p ) 1 1 " 1 ] J ( 4 . 2 ) i = 0 i w h e r e p = Q[— ] . F i g u r e 4.1 c o m p a r e s t h e P y ( / ) o f some memory ARQ s y s t e m s w i t h F E C t o t h a t o f a c o n v e n t i o n a l h y b r i d ARQ s y s t e m f o r t= 5 , n=511 a n d 7=5. A t a P y (/) o f 0 . 1 , s a y , t h e t h r e e - t h r e s h o l d memory ARQ s y s t e m i s 5 . 5 d B b e t t e r t h a n t h e c o n v e n t i o n a l ARQ s y s t e m . T h e c o r r e s p o n d i n g g a i n o v e r t h e h a r d d e c i s i o n memory ARQ s y s t e m i s a b o u t 1 . 2 d B . A l s o p l o t t e d i n f i g u r e 4 .1 i s a l o w e r b o u n d f o r P y (/). I t m i g h t be n o t e d t h a t t h e r e i s l i t t l e t o be g a i n e d i n i n c r e a s i n g t h e number o f t h r e s h o l d s b e y o n d t h r e e . 52 54 The a n a l y s i s of the average number of t r a n s m i s s i o n s E ( / ) i n the system i n which each b l o c k i s sent u n t i l i t i s s u c c e s s f u l l y r e c e i v e d , i s now c o n s i d e r e d . For d e t e r m i n i n g E(J) of t h i s system, e q u a t i o n (2.13) i s a l s o a p p l i c a b l e here but e q u a t i o n (2.15) i s no l o n g e r v a l i d . The e x p r e s s i o n s f o r P r [ E \ ] and PrfE^. ] a r e d e r i v e d i n appendix B. I t might be noted t h a t the e x p r e s s i o n f o r Pr[E.,E^ ,. . . ] would i n v o l v e more terms and the d e t e r m i n a t i o n of E(J) by e q u a t i o n (2.13) becomes d i f f i c u l t . An a l t e r n a t i v e method i s t o e s t i m a t e E(J) by u s i n g Monte C a r l o s i m u l a t i o n s . The s i m u l a t i o n program f o r e s t i m a t i n g E(/) f o r t h e t h r e e - t h r e s h o l d memory ARQ w i t h FEC i s l i s t e d i n Appendix D. The average number of t r a n s m i s s i o n s f o r d i f f e r e n t v a l u e s of t , u s i n g SNR=8dB and BCH codes w i t h n=511 a r e shown i n t a b l e 4.1. The parameters (n,k,«) of the BCH codes are t a b u l a t e d i n [ 2 2 ] . Column 3 and 4 a r e f o r the c a s e s which the decoder checks o n l y v and both Y and n. r e s p e c t i v e l y . The r e s u l t s i n d i c a t e t h a t t h e r e i s l i t t l e r e d u c t i o n i n E ( / ) s u g g e s t i n g t h a t o n l y v need be p r o c e s s e d . There i s a t r a d e - o f f i n t h e c h o i c e of t : As t i n c r e a s e s , E(/) d e c r e a s e s towards one; however, a l a r g e t r e s u l t s i n i n c r e a s e d overhead i n the d a t a b l o c k . One model which can be used t o d e t e r m i n e the optimum v a l u e of t i s t o m i n i m i z e the e x p e c t e d wasted time per message as i n [ 2 0 ] . I t i s assumed i n [20] t h a t the messages have random l e n g t h s / which a r e g e o m e t r i c a l l y ' d i s t r i b u t e d k t E ( J ) * E ( J ) 511 0 2.22433 2.21433 502 1 1.84267 1.83900 493 2 1.58667 1.58600 484 3 1.37033 1.37033 475 4 1.19367 1.19367 466 5 1.09067 1.09067 457 6 1.03667 1.03667 448 7 1.00800 1.00800 439 8 1.00300 1.00300 430 9 1.00133 1.00133 421 10 1.00000 1.00000 r . ignored. T a b l e 4.1. S i m u l a t i o n r e s u l t s f o r memory (m=2) ARQ w i t h SNR=8dB and n=5l1. 56 w i t h a v e r a g e l e n g t h E ( L ) = 1 / ( 1 - p ) , where p i s t h e p r o b a b i l i t y t h a t t h e m e s s a g e i s one b i t l o n g . E a c h message i s s p l i t i n t o p a c k e t o f s i z e k b i t s . T h e l a s t p a c k e t i s f i l l e d w i t h dummy b i t s ( i f n e c e s s a r y ) . F E C p a r i t y b i t s a r e a d d e d t o e a c h p a c k e t t o f o r m an n - b i t b l o c k . The a v e r a g e number o f p a c k e t s p e r mes sage i s t h e n g i v e n b y : 00 E(M) = L i P r [ ( i - 1 ) k < / < i k ] i=1 0 0 i K •_ 1 = E i L ( 1 - p ) p D i=1 j = ( i - i ) k + 1 ( 4 . 3 ) 1 - p The e x p e c t e d w a s t e d t i m e p e r mes sage E(W) i s d e f i n e d a s t h e d i f f e r e n c e b e t w e e n t h e t i m e i t t a k e s t o s e n d t h e mes sage u s i n g t h e t h r e e - t h r e s h o l d memory ARQ s y s t e m a n d t h e t i m e i t w o u l d t a k e t o d i r e c t l y t r a n s m i t t h e message o v e r an e r r o r - f r e e c h a n n e l w i t h t h e same b i t r a t e . I t c a n be e x p r e s s e d a s f o l l o w s : E(W) = E(M) E U ) (A+T) - E ( L ^ + b ( 4 . 4 ) where A i s t h e a c k n o w l e d g e m e n t d e l a y , T i s t h e b l o c k t r a n s m i s s i o n t i m e , R i s t h e c h a n n e l r a t e and b i s t h e o v e r h e a d . F o r a g i v e n SNR a n d n a n d d i f f e r e n t v a l u e s o f t , E ( 7 ) was o b t a i n e d by s i m u l a t i o n . E(W) c a n t h e n be c a l c u l a t e d f r o m e q u a t i o n ( 4 . 4 ) . F o r n u m e r i c a l e x a m p l e s , i t was a s s u m e d t h a t R=4000 b i t s / s e c , E ( L ) = 1 0 0 0 b i t s , A = 0 . 2 s ec a n d b=30 b i t s . F i g u r e 4 . 2 a n d 4 . 3 show t h e p l o t s o f E(W) a g a i n s t t 57 F i g u r e 4.2. E(W) vs t f o r n=511 and SNR=5, 6, 7 and 8 dB. 58 e 4.3. E(W) vs t f o r SNR=7dB and n=63, 127, 255, 511 and 1023. 59 f o r v a r i o u s SNR's and b l o c k l e n g t h s r e s p e c t i v e l y . From the f i g u r e s , t can be chosen so as t o m i n i m i z e E(W) f o r a g i v e n SNR and n. Some sample optimum v a l u e s tQ a r e g i v e n i n t a b l e 4.2. As e x p e c t e d , tQ i n c r e a s e s w i t h n and d e c r e a s e s w i t h i n c r e a s i n g SNR. 4.1 System Throughput A s e l e c t i v e r e p e a t (SR) ARQ scheme i n which o n l y e r r o n e o u s b l o c k s a r e r e t r a n s m i t t e d p r o v i d e s the h i g h e s t throughput of an . ARQ scheme. In t h i s c a s e , the system throughput T? i s g i v e n by the r a t i o of the number of i n f o r m a t i o n b i t s t o the t o t a l number of t r a n s m i t t e d b i t s . The improvement over a c o n v e n t i o n a l (no memory) SR-ARQ scheme o b t a i n e d by u s i n g an memory SR-ARQ scheme w i t h one and t h r e e t h r e s h o l d s i s now examined. As i n [ 1 5 ] , we w i l l assume a message c o n s i s t s of M b l o c k s . E v e r y message or group of r e t r a n s m i t t e d b l o c k s i s preceded by a header of s i z e b b i t s . F i r s t t h e M-block message p r e c e d e d by an b - b i t header i s t r a n s m i t t e d . Should one or more r e c e i v e d b l o c k s be d e t e c t e d i n e r r o r , a r e q u e s t f o r r e t r a n s m i s s i o n of the e r r o n e o u s b l o c k s i s made. These b l o c k s a r e then r e t r a n s m i t t e d w i t h the b - b i t header. T h i s i s i l l u s t r a t e d i n f i g u r e 4.4. T r a n s m i s s i o n i s c o mpleted when a p o s i t i v e acknowledgement (ACK) i s r e c e i v e d by the t r a n s m i t t e r . SNR (dB) n c 6 7 8 9 10 63 1 1 1 1 0 0 127 5 4 3 2 1 1 255 12 9 6 4 2 1 511 25 18 11 7 4 2 1023 50 34 .20 12 7 4 T a b l e 4.2. Some f . f o r d i f f e r e n t SNR and n. 61 For an M-block message" t o be s u c c e s s f u l l y t r a n s m i t t e d , on t h e average each b l o c k i s t r a n s m i t t e d E(7) t i m e s and each header i s t r a n s m i t t e d E(H) t i m e s . The system throughput i s then g i v e n by: M_k (A E \ 71 ~ b E(H) + n E(7) where k i s the number of i n f o r m a t i o n b i t s per b l o c k . I f a header i s mi s s e d ( w i t h a p r o b a b i l i t y = ), the t r a n s m i s s i o n of the messa'ge or group of r e t r a n s m i t t e d b l o c k s i s wasted. T h i s r e s u l t s i n r e d u c i n g 7? by a f a c t o r of ( 1 -). I n the f o l l o w i n g n u m e r i c a l example, P^ i s assumed n e g l i g i b l e . E(H) and E(/) f o r the memory (m=1 and 2) SR-ARQ schemes a r e o b t a i n e d by s i m u l a t i o n . T a b l e 4.3 shows some r e s u l t s f o r SNR=8dB, M=10 and n=l023. As f o r the c o n v e n t i o n a l h y b r i d SR-ARQ system, E(H) and E(/) can be F i g u r e 4.4. The SR-ARQ scheme. 62 d e t e r m i n e d a s f o l l o w s . C O E ( H ) = Z j P r [ h e a d e r t r a n s m i t t e d j t i m e s ] 3 = 1 00 = Z {1 - P r [ h e a d e r t r a n s m i t t e d < j t i m e s ] } j=1 The p r o b a b i l i t y o f t r a n s m i t t i n g t h e h e a d e r f e w e r t h a n . j t i m e s i s e q u a l t o t h e p r o b a b i l i t y t h a t a l l t h e b l o c k s i n t h e M - b l o c k mes sage a r e t r a n s m i t t e d l e s s t h a n j t i m e s . S i n c e a l l b l o c k t r a n s m i s s i o n s a r e i n d e p e n d e n t , E ( H ) c a n be w r i t t e n a s : 00 E ( H ) = Z {1 - ( P r [ e a c h b l o c k t r a n s m i t t e d < j t i m e s ] ) } j=1 = 1 + P M ) M } + { 1 - ( 1 - P ^ 2 ) M + . . . = 1 + Z {1 - (1 - P B „ 1 )M} i=1 M ( 4 . 6 ) t n _ . a where P „ , = 1 - Z ( ) p ' d - p ) \ p = Q [ ^ ] E(J) Z j P r f e a c h b l o c k t r a n s m i t t e d j t i m e s ] j=1 1 - P, 1- P F i g u r e 4 . 5 . S t a t e d i a g r a m o f t h e c o n v e n t i o n a l ARQ s c h e m e . 63 = Hr-P— ( 4 . 7 ) F i g u r e 4 . 6 i s a p l o t o f 17 a s a f u n c t i o n o f f o r t h e c o n v e n t i o n a l h y b r i d a n d t h e memory (m=1 a n d 2) S R - A R Q schemes w i t h SNR=8dB, n=1023 , M=10 a n d b=30. N o t e t h a t t h e r e i s a t h r o u g h p u t i m p r o v e m e n t o v e r t h e c o n v e n t i o n a l scheme i n u s i n g memory ARQ s c h e m e s . I m p r o v e m e n t i s more s i g n i f i c a n t a t h i g h PR„ . 64 k t m= 2 m= 1 E ( J ) E ( H ) E ( J ) E ( H ) 1023 0 2 . 4 7 3 9 3 . 1 2 4 0 3 . 1474 4 . 1 1 1 0 1013 1 2. 1135 2 . 7 5 2 0 2 .9461 3 . 0 5 6 0 1003 2 1 .9693 2 . 2 5 1 0 2 . 7964 3 . 0 0 2 0 0993 3 1.8661 2 . 0 3 9 0 2 . 5 3 5 3 3 . 0 0 0 0 0983 4 1 . 7 3 2 0 2 . 0 0 4 0 2 . 1 9 8 3 2 . 9 9 9 0 0973 5 1 .5707 2 . 0 0 1 0 1 . 8 5 3 7 2 . 9 6 3 0 0963 6 1 . 4 1 2 4 1 .9980 1 .5531 2 . 7 8 9 0 0953 7 1 .2762 1 .9600 1 . 3 2 4 2 2 . 4 0 5 0 0943 8 1 .1673 1 .8410 1 . 1 8 3 9 2 . 0 1 9 0 0933 9 1 .0939 1 .6370 1 . 0 9 6 6 1 .6810 0923 10 1 .0482 1 .4020 1 . 0 4 8 4 1 .4010 0913 1 1 1.0241 1 .2190 1 . 0 2 2 9 1 .2070 0903 1 2 1 .0117 1 .1120 1 . 0 1 0 0 1 .0940 0893 13 1 .0043 1 .0420 1 . 0 0 2 7 1 .0270 T a b l e 4 . 3 . Some s i m u l a t i o n r e s u l t s o f E ( H ) a n d E ( J ) f o r m=1 a n d 2, SNR=8dB, M=10 a n d n = l 0 2 3 65 F i g u r e 4.6. T? V S f o r the c o n v e n t i o n a l h y b r i d and the memory (m=1 and 2) SR-ARQ w i t h SNR=8dB, n=1fJ23, M=10 and b=30. 5 . CONCLUSION A g e n e r a l i z e d v e r s i o n o f t h e ARQ scheme w i t h memory a n d s o f t e r r o r d e t e c t o r s p r o p o s e d by B e n e l l i was s t u d i e d . T h e number o f q u a n t i z a t i o n r e g i o n s (2m) i s a r b i t r a r y a n d t h e w e i g h t s a r e no t r e s t r i c t e d t o ± 1 , ± 2 , ± m . The f o l l o w i n g a s p e c t s o f t h e memory ARQ scheme were a n a l y z e d : 1. t h e b i t e r r o r r a t e i n s y s t e m s w h i c h t r a n s m i t e a c h d a t a b l o c k a f i x e d n u m b e r , / , o f t i m e s , 2 . t h e a v e r a g e number o f t r a n s m i s s i o n s i n s y s t e m s w h i c h r e s e n d n e g a t i v e l y a c k n o w l e d g e d p a c k e t s u n t i l t h e y a r e s u c c e s s f u l l y r e c e i v e d a n d 3 . t h e i m p r o v e m e n t i n s y s t e m t h r o u g h p u t w h i c h c a n be o b t a i n e d u s i n g f o r w a r d e r r o r c o r r e c t i o n . I n t h e a n a l y s i s , i t was f o u n d t h a t t h e r e i s a s u b s t a n t i a l p e r f o r m a n c e i m p r o v e m e n t i n q u a n t i z i n g t h e r e c e i v e d s a m p l e s t o f o u r r e g i o n s i n s t e a d o f two r e g i o n s a s i n t h e h a r d d e c i s i o n d e t e c t o r . H o w e v e r , i n c r e a s i n g t h e number o f q u a n t i z a t i o n r e g i o n s b e y o n d f o u r r e s u l t s i n l i t t l e a d d i t i o n a l i m p r o v e m e n t . By p r o p e r l y s e l e c t i n g t h e t h r e s h o l d s a n d w e i g h t s , t h e s y s t e m p e r f o r m a n c e c a n be o p t i m i z e d . M e t h o d s f o r c h o o s i n g t h e t h r e s h o l d s a n d t h e w e i g h t s w h i c h m i n i m i z e t h e b i t e r r o r r a t e i n s y s t e m s u s i n g a f i x e d number o f t r a n s m i s s i o n s " were g i v e n . A c o m p u t a t i o n a l l y e f f i c i e n t m e t h o d f o r d e t e r m i n i n g t h e t h r e s h o l d s w h i c h m a x i m i z e t h e c h a n n e l c a p a c i t y was a l s o 66 67 d i s c u s s e d . In t h i s t h e s i s , the c h a n n e l model used was t h a t of an a d d i t i v e w h i t e g a u s s i a n n o i s e c h a n n e l . F u r t h e r work i s r e q u i r e d t o a c c e s s the performances of the memory ARQ scheme when used on o t h e r c h a n n e l s , such as a f a d i n g m o b i l e r a d i o c h a n n e l . R E F E R E N C E S [ I ] J . B. Moore, " C o n s t a n t - R a d i o Code and Automatic-RQ on T r a n s o c e a n i c HF Radio S e r v i c e s , " IRE Tr a n s . Commun., v o l . CS-8, pp72-75, Mar. 1960. [2] R. J . B e n i c e and A. H. F r e y , J r . , "Comparisons of E r r o r C o n t r o l T e c h n i q u e s , " IEEE T r a n s . Commun. Tech., v o l . COM-12, pp146-l54, Dec. 1964. [3] B. A r a z i , "Improving the Throughput of an ARQ Stop and Wait Scheme f o r B u r s t N o i s e C h a n n e l s , " IEEE T r a n s . Commun., v o l . COM-24 p p 6 6 l - 6 6 3 , J un. 1976. [4] A. S. K. S a s t r y , "Improving A u t o m a t i c Repeat-Request (ARQ) Performance on S a t e l l i t e Channels Under H i g h E r r o r Rate C o n d i t i o n s , " IEEE T r a n s . Commun., v o l . COM-23, pp436-439, Apr. 1975. [5] J . M. M o r r i s , "On Another Go-Back-N ARQ Technique f o r H i g h E r r o r Rate C o n d i t i o n s , " IEEE T r a n s . Commun., v o l . COM-26, p p l 8 7 - l 8 9 , J a n . 1978. [6] D. Towsley, "The S t u t t e r Go Back-N ARQ P r o t o c o l , " IEEE T r a n s . Commun., v o l . COM-27, pp869-875, J un. 1979. [7] S. L i n and P. Yu, "An E f f e c t i v e E r r o r C o n t r o l Scheme f o r S a t e l l i t e Communications," IEEE T r a n s . Commun., v o l . COM-28, pp 3 9 5 - 4 0 l , Mar. 1980. [8] P. Yu and S. L i n , "An E f f i c i e n t S e l e c t i v e - R e p e a t ARQ Scheme f o r S a t e l l i t e C hannels and I t s Throughput A n a l y s i s , " IEEE T r a n s . Commun., v o l . COM-29, pp353-363, Mar. 1 9 8 1 . [9] M. J . M i l l e r and S. L i n , "The A n a l y s i s of Some S e l e c t i v e - R e p e a t ARQ Schemes w i t h F i n i t e R e c e i v e r B u f f e r , " IEEE T r a n s . Commun., v o l . COM-29, pp1307-1315, Sep. 1981. [10] E. J . Weldon, J r . , "An Improved S e l e c t i v e - R e p e a t ARQ S t r a t e g y , " IEEE T r a n s . Commun., v o l . COM-30, pp480-486, Mar. 1982. [ I I ] A. S. K. S a s t r y , "Performance of H y b r i d E r r o r C o n t r o l Schemes on S a t e l l i t e C h a n n e l s , " IEEE T r a n s . Commun., v o l . COM-23, pp689-694, J u l . 1975. [12] C. S. K. Leung and A. Lam, "Forward E r r o r C o r r e c t i o n f o r an ARQ scheme," IEEE T r a n s . Commun., v o l . COM-29, pp1514-1519, O c t . 1981. 6 8 69 [13] C. F u j i w a r a , M. K a s a h a r a , K. Yamashita and T. Namekawa, " E v a l u a t i o n s of E r r o r C o n t r o l Techniques i n Both I n d e p e n d e n t - E r r o r and D e p e n d e n t - E r r o r C h a n n e l s , " IEEE T r a n s . Commun., v o l . COM-26, pp785-793, Jun. 1978. [14] P. S. Si n d h u , " R e t r a n s m i s s i o n E r r o r C o n t r o l w i t h Memory," IEEE T r a n s . Commun., v o l . COM-25, pp473-479, May 1977. [15] R. A. Comroe and D. J . C o s t e l l o , J r . , "ARQ schemes f o r Data T r a n s m i s s i o n i n M o b i l e R a d i o Systems," IEEE T r a n s . Veh. Tech., v o l . VT-33, pp88-97, Aug. 1984. [16] G. B e n e l l i , "An ARQ Scheme w i t h Memory and S o f t E r r o r D e t e c t o r s , " IEEE T r a n s . Commun., v o l . COM-33, pp285-288, Mar. 1985. [17] G. A. Arredondo, J . C. F e g g e l e r and J . I . Sm i t h , " V o i c e and Data T r a n s m i s s i o n , " B e l l S y s t . Tech. J . , v o l . 58, pp9 7 - l 2 2 , J a n . 1979. [18] F. J . Bloom, S. S. L. Chang, B H a r r i s , A. H a u p t s c h e i n and K. C. Morgan, "Improvement of B i n a r y T r a n s m i s s i o n by N u l l - Z o n e R e c e p t i o n , " P r o c . IRE, v o l . 45, pp963-975, J u l y 1957. [ 1 9 ] N. C. B e a u l i e u and C. -Leung, "Optimal D e t e c t i o n of H a r d - L i m i t e d Data S i g n a l s i n D i f f e r e n t N o i s e E n v i r o m e n t s , " S u b m i t t e d f o r p u b l i c a t i o n , IEEE T r a n s . Commun. [20] S. K. Leung and M. E. H e l l m a n , " C o n c e r n i n g a Bound on Un d e t e c t e d E r r o r P r o b a b i l i t y , " IEEE T r a n s , on I n f o . Theory, v o l . IT-22, pp235-237, Mar. 1976. [21] S. L i n and D. J . C o s t e l l o , J r . , " E r r o r C o n t r o l C o d i n g : Fundamentals and A p p l i c a t i o n s , " Englewood C l i f f s , NJ: P r e n t i c e - H a l l , 1983. [22] W. W. P e t e r s o n and E. J . Weldon, J r . , E r r o r C o r r e c t i n g Codes, 2nd E d i t i o n , t he MIT P r e s s , Cambridge, M a s s a c h u s e t t s , 1970. [23] C. F. G e r a l d , A p p l i e d N u m e r i c a l A n a l y s i s , 2nd E d i t i o n , Addison-Wesley P u b l i s h i n g Company, Read i n g , M a s s a c h u s e t t s , 1980. [24] J . M. Wozencra f t and I . M. J a c o b s , P r i n c i p l e s of Communication E n g i n e e r i n g , John W i l e y & Sons, I n c . , New y o r k , 1965. APPENDIX A T h i s a p p e n d i x shows t h a t : P . ( 2 / + 1 ) = P . {21+2) b b ,1=0,1,2,... (A.1 ) i n t h e h a r d d e c i s i o n memory ARQ s y s t e m . Assume t h a t a c e r t a i n b i t t o be t r a n s m i t t e d i s ' 1 ' . F o r e a c h j , t h e c o r r e s p o n d i n g m a t c h e d f i l t e r o u t p u t y i s A+N where N i s a z e r o - m e a n G a u s s i a n random v a r i a b l e w i t h v a r i a n c e a 2 . T h e p r o b a b i l i t y d i s t r i b u t i o n f u n c t i o n ( p d f ) o f y i s d e p i c t e d i n f i g u r e A . 1 pdf F i g u r e A . 1 w h e r e p = Q[—] i s t h e p r o b a b i l i t y t h a t t h e b i t • i s r e c e i v e d i n c o r r e c t l y . T h e L . H . S . o f ( A . 1 ) c a n be w r i t t e n a s : P , ( 2 / + 1 ) = P r [ a t l e a s t ( / + 1 ) o f t h e ( 2 / + 1 ) t r a n s m i s s i o n s o f b t h e b i t a r e i n c o r r e c t ] 2/ + 1 2 /+1 . = I ( ) p ' O - p ) 2 ' 1 ' = B ( A .2) 70 71 and the R.H.S. can be w r i t t e n a s : Pb (2/+2) = P r [ a t l e a s t (/+l)of the (2/+2) t r a n s m i s s i o n s of the b i t a r e i n c o r r e c t ] -^ P r [ e x a c t l y (/+1) of the t r a n s m i s s i o n s are i n c o r r e c t ] 2/+2 2/+2 I ( ) p 1 (1-p) /=/ + 1 21+2-i 1 , 2 l + 2 , /+1 + i -j ( ) p (1 - p ) ( A . 3) 2/+2 2/ + 1 2/+1 o/*-,--- L [ ( ) + ( ) ] p 1 ( 1 - p ) 2 / 2 1 / = / + 1 /' / - 1 2/ + 1 / ( ) [ p ( l ~ p ) ] / + 1 ( A . 4 ) 2/+1 2/ + 1 ... . ( 1 - P ) B + Z ( ) p ' + 1 ( 1 - p ) 2 7 - 1 " 1 -/ = / i 2 / + 1 Z+1 ( ) [ p O - p)r 1 ( A . 5 ) = ( l - p ) B + pB = B Q.E.D. From ( A . 3 ) t o ( A . 4 ) , we have used the f o l l o w i n g i d e n t i t i e s : r+1 r r r - r-1 ( ) = ( ) + ( ) and ( ) = I ( ). k k k-1 k K k-1 In ( A . 5 ) , the d e f i n i t i o n of B as i n ( A . 2 ) and a change i n t h e summation v a r i a b l e were used. A P P E N D I X B I n t h i s a p p e n d i x , t h e e x p r e s s i o n s f o r P r [ E ; . ] a n d P r [ E \ , E ^ ] a r e d e r i v e d . C o n s i d e r a d a t a b l o c k o f l e n g t h n w i t h F E C o f t e r r o r s . A s s u m i n g t h e ' a l l z e r o c o d e w o r d i s s e n t , t h e s e t o f v a l i d b l o c k s a t d i f f e r e n t j a r e shown i n f i g u r e B . 1 , 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 . . . 1 1 1 0 . . . 0 1 0 1 . . . 0 1 0 0 . . . 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 e r r o r 0 0 1 0 0 . . . 1 1 e r r o r • 2 e r r o r s 1 1 1 . . . 0 J =/ 1" 1 1 . . . 0 t e r r o r s F i g u r e B . 1 . A s e t o f v a l i d c o d e w o r d s . 73 74 where E^. ' s i s as d e f i n e d i n s e c t i o n 2.3. The p r o b a b i l i t y of Ej i s g i v e n by the f o l l o w i n g : P r [ E . ] =' Z P ( b . ) k P ( b . ) n _ k ' k=0 k ' ' P r [ E . , E , ] = (°) Z (") P ( B . , b , ) k P ( b . , b , ) n - k + 1 1 0 k = 0 k ' ' 1 1 n 1 1 . . ( ) I [ ( ) P ( b . , b , ) ] P(b.,b, 1 j-0 j 1 1 1 1 t _ j n _ 1 k - - n-k-1 Z ( ) p ( b . , b , ) k P ( b . , b . ) n k 1 ] + k=0 k 1 ' 1 1 n 2 2 . . ( ) Z [ ( ) P ( b . , b , ) 3 P(b. ,b, ) 3 2 j=0 j 1 1 1 1 t - j n-2 _ , _, Z ( ) P(b. ,b, ) K P(-b. ,b, ) n * z ] + .. .+ k=0 k 1 ' 1 1 n t t . . . ( ) Z [ ( ) P(b. ,b, ) 3 P(b. ,b, ) t _ : i t j=0 j 1 1 n _ t k - - n-k-t Z ( ) P(b.,b. )* P ( b . , b , ) n k fc ] k=0 k 1 1 1 1 t n m m = Z { ( ) Z [ ( ) P(b. ,b. ) D P(b. ,5, ) m _ : i m=0 m j=0 j 1 ' ' ' t - j n-m , , _ Z ( ) P(b. ,b, ) k P(b. ,b. ) n _ l c m ]} k=0 k 1 1 1 ' where P(b^.) and P(b^.) a r e the p r o b a b i l i t i e s t h a t a b i t i s i n v a l i d and v a l i d a t j r e s p e c t i v e l y . A P P E N D I X C T h i s appendix c o n t a i n s programs w r i t t e n i n FORTRAN f o r computing P f c (/) and E(/) f o r a g i v e n SNR. Program 1 computes P^ (/) a t optimum weight d i s t r i b u t i o n f o r /<8 and the number of r e g i o n s ^10. Program 2 computes E(J) g i v e n a f i x e d b l o c k l e n g t h and t h r e s h o l d . Program 3 i s a s u b r o u t i n e w h i c h r e t u r n s t h e p r o b a b i l i t i e s of the upward branches i n the t r e e diagrams as shown i n f i g u r e s 2.7 and 2.8 up t o 7=8. Program 4 g e n e r a t e s a l i s t of i n d i c e s f o r the complement e v e n t s of e q u a t i o n (2.14) t o be used by program 2 f o r computing E ( J ) . 75 76 1 C P r o g r a m 1 2 C T h i s p r o g r a m c o m p u t e s P B ( J ) f o r J = 1 - 8 g i v e n a f i x e d n u m b e r 3 C o f t h r e s h o l d s ( 2 M - 1 ) , t h e S N R ( d B ) a n d t h e t h r e s h o l d 4 C v a l u e s V s . O p t i m u m w e i g h t s a r e u s e d . 5 6 7 C P ( I ) = p r o b a b i l i t y t h a t r e c e i v e d s i g n a l f a l l s i n r e g i o n I . 8 c P R O B ( I ) = p r o b a b i l i t y o f t h e I t h u p w a r d b r a n c h c a l c u l a t e d 9 c f r o m s u b r o u t i n e P R O B J . 1 0 1 1 1 2 c D Q F U N C = 0 f u n c t i o n . I M P L I C I T R E A L * 8 ( A - H . O - Z ) 1 3 D I M E N S I O N V ( 5 ) , W E I G H T ( 1 0 ) . P ( 1 0 ) , P B ( 1 0 ) . P R 0 B ( 2 5 5 ) 1 4 1 5 O P E N ( U N I T = 2 0 . F I L E = ' I N P U T . D A T ' , S T A T U S 1 ' O L D ' ) 1 6 O P E N ( U N I T = 2 1 , F I L E = ' O U T P U T . D A T ' . S T A T U S = ' N E W ' ) 1 7 R E A D ( 2 0 . * ) M . S N R , ( V ( I ) , I = 1 , M ) 1 8 C L O S E ( U N I T = 2 0 ) 1 9 2 0 A R = 1 0 . 0 D 0 * * ( S N R / 2 0 . 0 D 0 ) 2 1 N B I N = 2 * M 2 2 2 3 c C o m p u t e t h e r e g i o n a l p r o b a b i l i t i e s a n d t h e o p t i m u m w e i g h t s 2 4 2 5 P E T = O.ODO 2 6 P C T = O.ODO 2 7 D O I = 1 , M 2 8 I I = N B I N - I + 1 2 9 P ( I ) = D Q F U N C ( A R * ( V ( I ) - 1 . O D O ) ) - P C T 3 0 P ( I I ) = D Q F U N C ( A R * ( V ( I ) + 1 . O D O ) ) - P E T 3 1 P C T = P C T + P ( I ) 3 2 P E T = P E T + P ( I I ) 3 3 W E I G H T ( I ) = D L O G ( P ( I ) / P ( I I ) ) 3 4 W E I G H T ( I I ) = W E I G H T ( I ) 3 5 E N D D O 3 6 3 7 c C o m p u t e t h e B E R f o r J = 1 t o 8 . 3 8 3 9 D O I = 1 , 2 5 5 4 0 P R O B ( I ) = O.ODO 4 1 E N D D O 4 2 C A L L P R O B J ( P R O B , P , W E I G H T , N B I N ) 4 3 D O J = 1 , 8 4 4 K = 2 * * ( J - 1 ) 4 5 K K = K - 1 4 6 P B ( J ) = 1 . 0 D 0 4 7 D O I = 1 . K 4 8 P B ( J ) = P B ( J ) - P R O B ( I + K K ) 4 9 E N D D O 5 0 W R I T E ( 2 1 , 1 0 ) J . P B ( J ) 5 1 E N D D O 5 2 1 0 F O R M A T ( ' P B C . I 1 , ' ) = ' . E 1 4 . 8 ) 5 3 C L O S E ( U N I T = 2 1 ) 5 4 S T O P 5 5 E N D Program 1 77 1 C P r o g r a m 2 2 C T h i s p r o g r a m c o m p u t e s E ( d ) f o r a g i v e n S N R a n d t h e t h r e s h o l d 3 C v a l u e s V s . 4 £ * * * * * * * * * * * * * * * * * * * * * * * * * * * » * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 5 6 C P d = d i s t r i b u t i o n o f d . 7 C A V E = a v e r a g e n u m b e r o f t r a n s m i s s i o n s E ( n ) . 8 9 I M P L I C I T R E A L * 8 ( A - H . O - Z ) 1 0 D I M E N S I O N V ( 5 ) , W E I G H T ( I O ) . P ( 1 0 ) , P d ( B ) , P R 0 B ( 2 5 5 ) 11 D I M E N S I O N W ( 8 ) , I B ( 2 4 4 4 ) , I P B K ( 3 . 2 5 6 ) 1 2 1 3 O P E N ( U N I T = 2 0 , F I L E = ' I N P U T . D A T ' . S T A T U S = ' O L D ' ) 1 4 O P E N ( U N I T = 2 1 . F I L E = ' O U T P U T . D A T ' , S T A T U S * ' N E W ' ) 1 5 R E A D ( 2 0 , * ) M , S N R , ( V ( I ) , I = 1 , M ) , N B L K 1 6 C L O S E ( U N I T = 2 0 ) 1 7 1 8 C R e a d t h e l i s t o f i n d i c e s g e n e r a t e d b y p r o g r a m 4 . 1 9 2 0 K = 1 2 1 L = 1 2 2 O P E N ( U N I T = 2 0 , F I L E = ' I N D E X . D A T ' . S T A T U S 1 ' O L D ' ) 2 3 1 0 C O N T I N U E 2 4 R E A D ( 2 0 , * ) I P B K ( 1 , K ) 2 5 I F ( I P B K ( 1 , K ) . E O . 0 ) G O T O 2 0 2 6 R E A D ( 2 0 . * ) I P B K ( 2 , K ) 2 7 I P B K ( 3 , K ) = L 2 8 K 1 = I P B K ( 1 , K ) 2 9 D O I = 1 , K 1 3 0 R E A D ( 2 0 . * ) I B ( L ) 3 1 L = L + 1 3 2 E N D D O 3 3 K = K + 1 3 4 G O T O 1 0 3 5 2 0 C L O S E ( U N I T = 2 0 ) 3 6 3 7 C C o m p u t e t h e r e g i o n a l p r o b a b i l i t i e s a n d t h e o p t i m u m w e i g h t s . 3 8 3 9 A R = 1 0 . 0 D 0 * * ( S N R / 2 0 . 0 D 0 ) 4 0 P E T = O . O D O 4 1 P C T = O . O D O 4 2 N B I N = 2 * M 4 3 D O I = 1 . M 4 4 I I = N B I N - I + 1 4 5 P ( I ) = D 0 F U N C ( A R * ( V ( I ) - 1 . O D O ) ) - P C T 4 6 P ( I I ) = D Q F U N C ( A R * ( V ( I ) + 1 . O D O ) ) - P E T 4 7 P C T = P C T + P ( I ) 4 8 P E T - P E T + P ( I I ) 4 9 W E I G H T ( I ) = D L O G ( P ( I ) / P ( I I ) ) 5 0 W E I G H T ( I I ) = W E I G H T ( I ) 5 1 E N D D O 5 2 - 5 3 C C o m p u t e t h e d i s t r i b u t i o n o f d a n d t h e a v e r a g e n u m b e r o f 5 4 C t r a n s m i s s i o n s . 5 5 5 6 D O I = 1 , 2 5 5 5 7 P R O B ( I ) = O . O D O 5 8 E N D D O Program 2 78 59 CALL PROBd (PROB. P, WEIGHT, NBIN) 60 AVE = O.ODO 61 DO d = 1,8 62 P J ( J ) = O.ODO 63 02 = 2 * * ( U - D 64 J3 = J 2 - 1 65 1 1 = 0 66 1 = 0 67 30 I = 1+1 68 IF (11 .EO. J 2 ) GOTO 40 69 IF ( I P B K ( 2 . I ) .GT. J2) GOTO 30 70 11 = 11+1 71 K2 = IPBK(1,1) 72 PBK = O.ODO 73 DO K = 1,K2 74 J4 = I B ( I P B K ( 3 , I )+K-1) 75 PBK = PBK+PR0B(d3+J4) 76 END DO 77 d5 = INT(ALOG(FL0AT(K2))/AL0G(2 .O)+O.5)+1 78 d6 = ( ( - 1 ) * * d ) * ( ( - 1 ) * * J 5 ) 79 P d ( d ) = PU(J)+J6*(PBK**NBLK) 80 GOTO 30 81 40 AVE = AVE+d*Pd(d) 82 END DO 83 WRITE ( 2 1 , 5 0 ) AVE 84 50 FORMAT ( ' THE AVERAGE NUMBER OF TRANSMISSIONS = ' , F 6 . 2 ) 85 CLOSE (UNIT=21) 86 STOP 87 END P r o g r a m 2 79 1 C P r o g r a m 3 2 C T h i s s u b - p r o g r a m c o m p u t e s P R O B , t h e p r o b a b i l i t y o f e v e r y 3 C u p w a r d p o i n t i n g b r a n c h w h i c h c o r r e s p o n d s t o a c o r r e c t 4 C d e c i s i o n , f o r <J=8 . 5 6 7 c P ( I ) = t h e p r o b a b i l i t y a s s o c i a t e d w i t h r e g i o n I . 8 c W T ( I ) = t h e w e i g h t a s s o c i a t e d w i t h r e g i o n I . 9 c N B I N = t h e n u m b e r o f r e g i o n s . 1 0 1 1 S U B R O U T I N E P R O B J ( P R O B , P . W T , N B I N ) 1 2 I M P L I C I T R E A L * 8 ( A - H . O - Z ) 1 3 D I M E N S I O N P ( 1 ) , P R 0 B ( 1 ) , W T ( 1 ) 1 4 I N T E G E R W ( 8 ) 1 5 C O M M O N W 1 6 1 7 O H = O . O D O 1 8 D O 4 0 I 1 = 1 . N B I N 1 9 C A L L T 1 ( 1 , 1 1 . O H . W 1 , 1 . 0 , P 1 , L 1 , P , W T ) 2 0 I F ( W 1 . G E . O . O D O ) P R 0 B ( 1 ) = P R 0 B ( 1 ) + P 1 2 1 D O 4 0 1 2 = 1 , N B I N 2 2 C A L L T 1 ( 2 , 1 2 , W 1 , W 2 . P 1 , P 2 . L 2 . P , W T ) 2 3 I F ( W 2 . L T . O H ) G O T O 11 2 4 1 0 L 2 = L 2 + 1 2 5 C A L L T 2 ( 2 , W 2 , P 2 , L 2 , W, K ) 2 6 I F ( L 2 . E O . 1 ) P R O B ( K ) = P R 0 B ( K ) + P 2 2 7 1 1 D O 3 9 1 3 = 1 . N B I N 2 8 C A L L T 1 ( 3 , 1 3 , W 2 , W 3 , P 2 , P 3 , L 3 . P , W T ) 2 9 I F ( W 3 . L T . O H ) G O T O 1 3 3 0 1 2 L 3 = L 3 - M 3 1 C A L L T 2 ( 3 , W 3 , P 3 , L 3 , W , K ) 3 2 I F ( L 3 . E O . 1 ) P R O B ( K ) * P R 0 B ( K ) + P 3 3 3 1 3 D O 3 8 1 4 = 1 . N B I N 3 4 C A L L T 1 ( 4 . 1 4 , W 3 , W 4 , P 3 , P 4 . L 4 , P , W T ) 3 5 I F ( W 4 . L T . O H ) G O T O 1 5 3 6 1 4 L 4 = L 4 + 1 3 7 C A L L T 2 ( 4 , W 4 , P 4 , L 4 , W , K ) 3 8 I F ( L 4 . E O . 1 ) P R O B ( K ) = P R 0 B ( K ) + P 4 3 9 1 5 D O 3 7 1 5 = 1 . N B I N 4 0 C A L L T 1 ( 5 . 1 5 , W 4 , W 5 , P 4 , P 5 . L 5 , P , W T ) 4 1 I F ( W 5 . L T . O H ) G O T O 1 7 4 2 1 6 L 5 = L 5 + 1 4 3 C A L L T 2 ( 5 , W 5 , P 5 . L 5 , W, K ) 4 4 I F ( L 5 . E O . 1 ) P R O B ( K ) = P R 0 B ( K ) + P 5 4 5 1 7 D O 3 6 1 6 = 1 . N B I N 4 6 C A L L T 1 ( 6 , 1 6 , W 5 . W 6 . P 5 , P 6 , L 6 , P , W T ) 4 7 I F ( W 6 . L T . O H ) G O T O 1 9 4 8 1 8 L 6 = L 6 + 1 4 9 C A L L T 2 ( 6 . W 6 , P 6 . L 6 . W, K ) 5 0 I F ( L 6 . E O . 1 ) P R O B ( K ) = P R 0 B ( K ) + P 6 5 1 1 9 D O 3 5 1 7 = 1 . N B I N 5 2 C A L L T 1 ( 7 , 1 7 , W 6 , W 7 , P 6 . P 7 . L 7 , P . W T ) 5 3 I F ( W 7 . L T . O H ) G O T O 2 1 5 4 2 0 L 7 « L 7 + 1 5 5 C A L L T 2 ( 7 , W 7 , P 7 , L 7 , W, K ) 5 6 I F ( L 7 ' . E O . 1 ) P R O B ( K ) = P R 0 B ( K ) + P 7 5 7 2 1 D O 3 4 I B = 1 , N B I N 5 8 C A L L T 1 ( 8 , 1 8 , W 7 , W 8 . P 7 , P 8 . L 8 , P . W T ) P r o g r a m 3 80 59 IF (W8 . LT . OH) GOTO 34 60 22 18 = L8+1 61 CALL T2 (8, W8. P8. L8, w, K) 62 IF (L8 .EO. 1) PROB(K) = PR0B(K)+P8 63 .34 CONTINUE 64 IF (L7 .EO. 1 .AND. W7 .EO OH) GOTO 20 65 35 CONTINUE 66 IF (L6 • EO. 1 .AND. W6 .EO OH) GOTO 18 67 36 CONTINUE 68 IF (L5 • EO. 1 .AND. W5 .EO OH) GOTO 16 69 . 37 CONTINUE 70 IF (L4 .EO. 1 .AND. W4 .EO OH) GOTO 14 71 38 CONTINUE 72 IF (L3 .EO. 1 .AND. W3 .EO OH) GOTO 12 73 39 CONTINUE 74 IF (L2 • EQ. 1 .AND. W2 .EO OH) GOTO 10 75 40 CONTINUE 76 77 RETURN 78 END 79 80 SUBROUTINE T1 (d. I, WO, WI . PO, PI, LI 81 REAL*8 P( 1 ) , WT(1 ) PO, PI , WO, WI 82 INTEGER W(8) 83 COMMON W 84 WI = WO+WT(I) 85 PI = PO*P(I ) 86 LI = 0 87 IF (WI .LT. 0. ODO) THEN 88 W(J) = 1 89 ELSE 90 W(d) = 0 91 END IF 92 RETURN 93 END 94 95 SUBROUTINE T2 (d. WI, PI , LI W, I ) 96 REAL*8 PI . WI 97 INTEGER W(8) 98 IF ( L I .EO. 1) THEN 99 N = d-1 100 I = 2** N 101 DO K = 1 .N 102 I = I+W(K) *2**(N- K) 103 END DO 104 IF (WI .EO. O.ODO) PI = 0.5D0*PI 105 ELSE 106 . W(d) = 1 107 END IF 108 RETURN 109 END P r o g r a m 3 8 1 1 C P r o g r a m 4 2 C T h i s p r o g r a m g e n e r a t e s a l i s t o f i n d i c e s f o r t h e e v e n t s E ' s 3 C i n e q u a t i o n ( 2 . 1 4 ) . T h e l i s t o f i n d i c e s i s s t o r e d i n t h e 4 C f i l e I N D E X . D A T . 5 ^ * * * * * * * * * * * * * * * * * * * * * * * » * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 6 7 C d = n u m b e r o f t r a n s m i s s i o n s > 1 a 9 I N T E G E R B ( 5 1 2 , 9 ) , I B ( 2 5 0 0 0 ) 1 0 O P E N ( U N I T = 2 1 , F I L E = ' I N D E X . D A T ' , S T A T U S = ' N E W ' ) 11 W R I T E ( 6 , * ) ' E N T E R N O . O F T R A N S M I S S I O N S ' 1 2 R E A D ( 5 , * ) d 1 3 1 4 N = d - 1 1 5 N N = 2 * * N 1 G D O L = 1 , N 1 7 K K = 2 * * ( L - 1 ) 1 8 D O I = 1 , N N 1 9 K « ( I + K K - O / K K 2 0 B ( I , L ) = 1 2 1 I F ( ( ( K - 1 ) / 2 ) * 2 . E O . K - 1 ) B ( I , L ) = 0 2 2 E N D D O 2 3 E N D D O 2 4 2 5 K = 1 2 6 I B ( K ) = O 2 7 D O 1 1 = 1 . N N 2 8 1 = 0 2 9 D O 2 0 1 2 = 1 , N N 3 0 D O L = 1 , N 3 1 I F ( B ( I 1 , L ) * B ( I 2 , L ) . N E . 0 ) G O T O 2 0 3 2 E N D D O 3 3 K = K + 1 3 4 I = 1 + 1 3 5 M = 1 2 3 6 I B ( K ) = 1 2 3 7 2 0 C O N T I N U E 3 8 K = K + 1 3 9 I B ( K ) = M 4 0 K = K + 1 4 1 I B ( K ) = I 4 2 E N D D O 4 3 4 4 D O L = 1 , K 4 5 I = K - L + 1 4 6 W R I T E ( 2 1 . * ) I B ( I ) 4 7 E N D D O 4 8 S T O P 4 9 E N D P r o g r a m 4 A P P E N D I X D 1 C S imulat ion 2 C This program estimates the average number of transmissions 3 C for the three-threshold memory ARQ scheme with 99 percents 4 C confidence. Number of correctable errors T varies from 0 5 C to NERROR. 6 C The average number of transmissions for both cases ( with 7 C and without r j ignored ) are estimated. 8 9 10 DIMENSION Z(511). NT(31), NSUM(31). NSUM2(31) 1 1 DIMENSION ZN(511), NNT(31), NNSUM(31), NNSUM2(31) 12 INTEGER*2 11, 12, DONE, T 13 COMMON /SEEDS/ 11, 12 14 15 OPEN (UNIT=20, FILE='INPUT.DAT', STATUS='OLD') 16 OPEN (UNIT = 21, FILE='OUTPUT.DAT'. STATUS='NEW' ) 17 READ (20,*) NBLOCK, NERROR, SNR. NTRIAL. 11. 12 18 CLOSE (UNIT=20) 19 20 A = 10.0**(SNR/20.0) 21 V = 0.4*A 22 M = NERROR+1 23 24 DO I = 1,M 25 NSUM(I ) = 0 26 NSUM2(I ) = 0 27 NNSUMlI) = 0 28 NNSUM2(I) = 0 29 END DO 30 31 DO KOUNT = 1.NTRIAL 32 DO K = 1,NBLOCK 33 Z(K) = O.O 34 END DO 35 N = 1 36 NN = 1 37 NEO = M 38 NNEO = M 39 DONE = 0 40 1 CONTINUE 41 42 C Add Gaussian noise to each transmitted bit and assign 43 C weight to every received signal. 44 45 DO I = 1,NBLOCK 46 Y = A+RANDN(0) 47 IF ( Y ) 10, 10. 20 48 10 IF ( Y + V ) 30. 40, 40 49 20 IF ( Y - V ) 50, 50, 60 50 30 W = -2.0 51 GO TO 70 52 40 W = -1.0 53 GO TO 70 54 50 W = 1.0 55 GO TO 70 56 60 W = 2.0 57 70 Z(I) = Z(I)+W 58 ZN(I) = W 82 83 5 9 E N D D D 6 0 6 1 C C h e c k n u m b e r o f e r r o r s N E 1 ( I . e . n e g a t i v e w e i g h t ) i n t h e 6 2 C d a t a b l o c k . 6 3 6 4 N E 1 = 0 6 5 N N E 1 = 0 6 6 D O I = 1 , N B L D C K 6 7 I F ( Z ( I ) . L E . 0 . 0 ) T H E N 6 8 I F ( Z ( I ) E O . 0 . 0 ) T H E N 6 9 X X = R A N D N ( O ) 7 0 I F ( X X . G T . O ) N E 1 = N E 1 + 1 7 1 E L S E 7 2 N E 1 = N E 1 + 1 7 3 E N D I F 7 4 E N D I F 7 5 I F ( Z N ( I ) . L E . O . O ) N N E 1 = N N E 1 - M 7 6 E N D D O 7 7 7 8 C R e q u e s t f o r r e t r a n s m i s s i o n i f t h e n u m b e r o f e r r o r s i s 7 9 C g r e a t e r t h a n 0 . 8 0 8 1 I F ( N E 1 . L T . N N E 1 ) N N E 1 = N E 1 8 2 I F ( D O N E . L T . 1 ) T H E N 8 3 I F ( N N E 1 . E O . 0 ) T H E N 8 4 D O I = 1 . N N E 0 8 5 N N T ( I ) = N N 8 6 E N D D O 8 7 D O N E = 1 8 8 E L S E 8 9 I F ( N N E 1 . G E . N N E O ) G O T O 8 0 9 0 I I = N N E 1 + 1 9 1 D O I = 1 1 ,N N E O 9 2 N N T ( I ) = N N 9 3 E N D D O 9 4 N N E O = N N E 1 9 5 8 0 N N = N N + 1 9 6 E N D I F 9 7 E N D I F 9 8 9 9 I F ( N E 1 . E O . 0 ) T H E N 1 0 0 D O I = 1 . N E 0 1 0 1 N T ( I ) = N 1 0 2 E N D D O 1 0 3 E L S E 1 0 4 I F ( N E 1 . G E . N E O ) G O T O 9 0 1 0 5 I I = N E 1 + 1 1 0 6 D O I = 1 1 ,N E O 1 0 7 N T ( I ) = N 1 0 8 E N D D O 1 0 9 N E O = N E 1 1 1 0 9 0 N • N + 1 1 1 1 G O T O 1 1 1 2 E N D I F 1 1 3 1 1 4 C S u m t h e n u m b e r o f t r a n s m i s s i o n s . 1 1 5 1 1 6 D O I = 1.M 84 1 1 7 N S U M ( I ) = N 5 U M ( I ) + N T ( I ) 1 1 8 N N S U M ( I ) = N N S U M ( I ) + N N T ( I ) 1 1 9 N S U M 2 ( I ) = N S U M 2 ( I ) + N T ( I ) * * 2 1 2 0 N N S U M 2 ( I ) = N N S U M 2 ( I ) + N N T ( I ) * * 2 1 2 1 E N D D O 1 2 2 E N D D O 1 2 3 1 2 4 C C o m p u t e t h e a v e r a g e n u m b e r o f t r a n s m i s s i o n s a n d t h e 1 2 5 C 9 9 p e r c e n t c o n f i d e n t i n t e r v a l s . 1 2 G c E N = a v e r a g e n u m b e r o f t r a n s m i s s i o n s ( r j i g n o r e d ) . 1 2 7 c E N N = a v e r a g e n u m b e r o f t r a n s m i s s i o n s ( r j n o t i g n o r e d ) . 1 2 8 c C I N T a n d C I N T N = c o n f i d e n t i n t e r v a l s f o r E N a n d E N N r e s p 1 2 9 1 3 0 T R I A L = F L O A T ( N T R I A L ) 1 3 1 K T A N T = F L 0 A T ( N T R I A L * ( N T R I A L - 1 ) ) 1 3 2 D O I = 1 , M 1 3 3 E N = F L O A T ( N S U M ( I ) ) / T R I A L 1 3 4 V A R = ( F L O A T ( N S U M 2 ( I ) * N T R I A L - N S U M ( I ) * * 2 ) ) / K T A N T 1 3 5 C I N T = 2 . 5 8 * S Q R T ( V A R / T R I A L ) 1 3 6 E N N = F L O A T ( N N S U M ( I ) ) / T R I A L 1 3 7 V A R N = ( F L O A T ( N N S U M 2 ( I ) * N T R I A L - N N S U M ( I ) * * 2 ) ) / K T A N T 1 3 8 C I N T N = 2 . 5 8 * S Q R T ( V A R N / T R I A L ) 1 3 9 T = 1 - 1 1 4 0 E N D D O 1 4 1 W R I T E ( 2 1 , * ) T , E N , C I N T , E N N , C I N T N 1 4 2 C L O S E ( U N I T = 2 1 ) 1 4 3 S T O P 1 4 4 E N D 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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-0096298/manifest

Comment

Related Items