UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the error analysis of correlation devices Chang, Ke-yen 1969

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

Item Metadata

Download

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

Full Text

ON THE ERROR ANALYSIS OP CORRELATION DEVICES •by KE - YEN CHANG-B.Sc. i n E.E., N a t i o n a l Taiwan U n i v e r s i t y , 1966 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n the Department of E l e c t r i c a l Engineering We accept t h i s t h e s i s as cenforr^ixig to the req u i r e d standard Research Supervisor Members of the Committee Head of the Department Members of the Department of E l e c t r i c a l Engineering THE UNIVERSITY OF BRITISH COLUMBIA August, 1969 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 o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e 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 a g r e e 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 o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e Head o f my D e p a r t m e n t o r by h i s 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 o f 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 n o t 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 . D e p a r t m e n t o f 0f/JAAja(l tCs^.,^,*,A V a The U n i v e r s i t y o f B r i t i s h C o l u m b i a V a n c o u v e r 8, Canada D a t e fikw^JT / f . ABSTRACT The use of uniformly d i s t r i b u t e d a u x i l i a r y random noise i n the p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r has been described i n the past. I t has the advantage of c o n s t r u c t i o n a l s i m p l i c i t y . I t a l s o gives an unbiased and co n s i s t e n t estimate of the c o r r e l a t i o n f u n c t i o n . In t h i s t h e s i s , the method of u s i n g a u x i l i a r y random noise i s extended to the m u l t i - l e v e l d i g i t a l c o r r e l a t o r . I t i s found t h a t any random noise of which the c h a r a c t e r i s t i c f u n c t i o n has p e r i o d i c zeros can be used as an a u x i l i a r y noise, that u n i -formly d i s t r i b u t e d noise i s a s p e c i a l case, and that q u a n t i z i n g the a u x i l i a r y random noise has the same e f f e c t as d i r e c t l y q u a n t i z i n g the input s i g n a l s . The mean-square e r r o r of t h i s modified d i g i t a l c o r r e l a t o r i s analyzed i n d e t a i l . I t d i f f e r s from, the mean—square e r r o r of the d i r e c t c o r r e l a t o r only by a term which i s i n v e r s e l y propor-t i o n a l to the t o t a l number of samples taken, provided that the power spectrum of the a u x i l i a r y noise i s wide enough. This a d d i -t i o n a l e r r o r i s the combined e f f e c t of sampling, q u a n t i z i n g and adding a u x i l i a r y noise. I t can be reduced to any des i r e d value by t a k i n g a l a r g e r number of samples, by u s i n g a higher sampling r a t e , or by q u a n t i z i n g more f i n e l y . For completeness, the mean-square e r r o r s of the d i g i t a l c o r r e l a t o r , the S t i e l t j e s c o r r e l a t o r and the modified S t i e l t j e s c o r r e l a t o r are a l s o d e r i v e d . The mean-square e r r o r of the modified p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r , which i s a s p e c i a l case of the modified d i g i t a l c o r r e l a t o r , is compared w i t h the e r r o r of the m u l t i - l e v e l modified d i g i t a l c o r r e l a t o r . Despite i t s c o n s t r u c t i o n a l s i m p l i c i t y , the modified p o l a r i t y - c o i n c i d e n c e has a much l a r g e r e r r o r than the m u l t i - l e v e l c o r r e l a t o r . A small increase i n the number of q u a n t i z a t i o n l e v e l s i i reduces the e r r o r considerably. The implementation of a modified d i g i t a l c o r r e l a t o r w i t h coarse q u a n t i z a t i o n i s a l s o considered. A f a s t d i r e c t m u l t i p l i e r i s designed to obtain high operation speed. F i n a l l y , the use of pseudo-random noise as an a u x i l i a r y noise i s discussed. i i i TABLE OF CONTENTS Page ABSTRACT ' i i TABLE OF CONTENTS i v LIST OF ILLUSTRATIONS v i ACKNOWLEDGEMENT v i i 1. INTRODUCTION 1 2 . ' CORRELATION DEVICES 5 2.1 The D i r e c t C o r r e l a t o r 5 2 . 2 The D i g i t a l C o r r e l a t o r 7 2 . 3 The Modified D i g i t a l C o r r e l a t o r 11 2 . 3.1 The Modified P o l a r i t y - C o i n c i d e n c e C o r r e l a t o r 17 2 . 3 - 2 D i s c r e t e A u x i l i a r y Random Noise 18 2 . 4 The S t i e l t j e s C o r r e l a t o r 22 2 . 5 The Modified S t i e l t j e s C o r r e l a t o r 23 3. ERROR ANALYSIS 25 3.1 C r i t e r i a f o r Judging the Performance of a C o r r e l a t o r 25 3 . 2 The Mean-Square E r r o r of the D i r e c t C o r r e l a t o r . . . 2 7 3«3 The Mean-Square E r r o r of the D i g i t a l C o r r e l a t o r . . 2 9 3 . 4 The Mean-Square E r r o r of the Modified D i g i t a l C o r r e l a t o r Using Continuous A u x i l i a r y Noise 33 3 - 4.1 White A u x i l i a r y Noise 3 3 3 . 4 . 2 Non-White A u x i l i a r y .Noise 4 3 3 . 5 The Mean-Square E r r o r of the Modified D i g i t a l C o r r e l a t o r Using D i s c r e t e A u x i l i a r y Noise 45 3 . 6 The Mean-Square E r r o r of the S t i e l t j e s C o r r e l a t o r 46 3 . 7 The Mean-Square E r r o r of the Modified S t i e l t j e s C o r r e l a t o r 47 4 . IMPLEMENTATION OF THE MODIFIED DIGITAL CORRELATOR 4 9 4.1 The Double-Shift-Register P o l a r i t y - C o i n c i d e n c e C o r r e l a t o r 49 i v Page 4.2 Implementation of the Modified D i g i t a l C o r r e l a t o r . . 53 4.2.1 A Past D i r e c t M u l t i p l i e r f o r the Modified D i g i t a l C o r r e l a t o r 54 4.3 The A p p l i c a t i o n of Pseudo-Random Noise to the Modified D i g i t a l C o r r e l a t o r . . . . 59 4.3-1 Pseudo-Random Binary Sequences 60 4.3-2 P r o p e r t i e s of Pseudo-Random Binary Sequences. 61 4.3.3 Pseudo-Random Noise 62 4.3.4 Pseudo-Random Noise as A u x i l i a r y Noise i n the Modified D i g i t a l C o r r e l a t o r 65 5. CONCLUSIONS 71 REFERENCES '. 73 v LIST OF ILLUSTRATIONS Figure Page 2.1 D i r e c t c o r r e l a t o r s ; a continuous d i r e c t c o r r e l a t o r (a) and a sampled-data d i r e c t c o r r e l a t o r (b) 6 2.2 A d i g i t a l c o r r e l a t o r 8 2.3 C h a r a c t e r i s t i c of the uniform quantizer 9 2.4 A modified d i g i t a l c o r r e l a t o r 11 2.5 Input/output c h a r a c t e r i s t i c of a quantizer f o r a u x i l i a r y noise 18 2.6 A S t i e l t j e s c o r r e l a t o r 22 2.7 A modified S t i e l t j e s c o r r e l a t o r 23 3.1 The d i f f e r e n c e of the mean-square e r r o r s of the modi-f i e d d i g i t a l and the d i r e c t c o r r e l a t o r s vs. the q u a n t i z a t i o n s t e p - s i z e f o r q u a n t i z a t i o n w i t h a n u l l zone 39 3-2 The d i f f e r e n c e of the mean-square e r r o r s of the modified d i g i t a l and the d i r e c t c o r r e l a t o r s vs. the q u a n t i z a t i o n s t e p - s i z e f o r q u a n t i z a t i o n without a n u l l zone " 40 4.1 . D o u b l e - s h i f t - r e g i s t e r p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r 50 4.2 D o u b l e - s h i f t - r e g i s t e r modified d i g i t a l c o r r e l a t o r 53 4«3 Representation of q u a n t i z a t i o n l e v e l s w i t h i n t e g r a l numbers 55 4.4 F i r s t scheme for. o b t a i n i n g two noise s i g n a l s from a s h i f t r e g i s t e r 64 4.5 Second scheme f o r o b t a i n i n g two noise s i g n a l s from a s h i f t r e g i s t e r 64 4.6 Auto- and c r o s s - c o r r e l a t i o n functions f o r (a) the f i r s t scheme, and (b) the second scheme, n=10, L=5 69 v i o ACKNOWLEDGEMENT I wish to express my sincere g r a t i t u d e to Dr. A.D. Moore, the supervisor of t h i s p r o j e c t , f o r h i s i n v a l u a b l e guidance and constant encouragement. I would l i k e to thank Mr. A.C. Davies f o r reading the manuscript and f o r h i s many h e l p f u l suggestions p e r t a i n i n g to the a p p l i c a t i o n of pseudo-random noise to the c o r r e l a t o r . -G r a t e f u l acknowledgement i s given to the Na t i o n a l Research Council and the Defence Research Board of Canada f o r f i n a n c i a l support received under NRC Grant A-3357 and DRB Grant 3801-36, r e s p e c t i v e l y , and to the U n i v e r s i t y of B r i t i s h Columbia f o r a U n i v e r s i t y of B r i t i s h Columbia Fellowship awarded i n 1968. I would a l s o l i k e to thank my parents f o r t h e i r encouragement, and Miss Beverly Harasymchuk f o r t y p i n g the manuscript. v i i 1 1. INTRODUCTION A l a r g e number of devices f o r measuring c o r r e l a t i o n functions have been described i n the past. Despite t h e i r d i f f e r e n c e s i n processing or computing techniques, they may be grouped i n t o f i v e b a s i c c a t e g o r i e s : the d i r e c t c o r r e l a t o r , the d i g i t a l c o r r e l a t o r , the modified d i g i t a l c o r r e l a t o r , the S t i e l t j e s c o r r e l a t o r and the modified S t i e l t j e s c o r r e l a t o r . I t i s the pur-pose of t h i s t h e s i s to analyze the e r r o r of these c o r r e l a t o r s . The d i r e c t c o r r e l a t o r performs the c o r r e l a t i o n computa-t i o n by . d i r e c t l y processing the input s i g n a l s of which the c o r r e -l a t i o n f u n c t i o n i s d e s i r e d . Without using q u a n t i z a t i o n or adding any e x t e r n a l n o i s e , the input s i g n a l or i t s samples are delayed, m u l t i p l i e d and i n t e g r a t e d w i t h analogue components. For example, magnetic tapes are commonly used to obtain delayed f u n c t i o n s ; and low-pass RC f i l t e r s or o p e r a t i o n a l a m p l i f i e r s are often employed as i n t e g r a t o r s . Most of the e a r l i e r c o r r e l a t o r s are of t h i s type. By sampling and q u a n t i z i n g the input s i g n a l s , d i g i t a l techniques can be used. W i d r o w ^ ^ ^ has i n v e s t i g a t e d the e f f e c t s of q u a n t i z a t i o n on the c o r r e l a t i o n f u n c t i o n . He has shown that i f the two-dimensional q u a n t i z i n g theorem i s . s a t i s f i e d , that i s , i f the c h a r a c t e r i s t i c f u n c t i o n of the quantizer input i s bounded i n two dimensions and the quantizer l e v e l s i z e i s f i n e enough, the c o r r e l a t i o n f u n c t i o n of the quantized s i g n a l s i s equal to the true c o r r e l a t i o n f u n c t i o n ; otherwise, i t w i l l deviate from the true c o r r e l a t i o n f u n c t i o n by a b i a s e r r o r term. Unfortunately, (3) no r e a l s i g n a l s can s a t i s f y the q u a n t i z i n g theorem. Watts has g e n e r a l i z e d Widrow's theory and proposed s e v e r a l q u a n t i z a t i o n c o r r e l a t o r s , i n c l u d i n g p o l a r i t y - c o i n c i d e n c e , r e l a y and S t i e l t j e s c o r r e l a t o r s . These are included here as the d i g i t a l and the S t i e l t j e s c o r r e l a t o r s . The former i s the one i n which "both of the input s i g n a l s are quantized; i n the l a t t e r only one of the input s i g n a l s i s quantized. The simplest d i g i t a l c o r r e l a t o r i s the p o l a r i t y - c o i n c i -dence c o r r e l a t o r , i n which the input s i g n a l s are quantized i n t o two l e v e l s ; thus only one b i t i s required f o r processing. However the c o r r e l a t o r i s ' a p p l i c a b l e only to Gaussian and c e r t a i n separabl random processes. Even f o r these random processes, the r e s u l t i n g c o r r e l a t i o n estimate has an inconvenient r e l a t i o n s h i p w i t h the true c o r r e l a t i o n f u n c t i o n . To overcome these disadvantages, Jespers, Chu and F e t t w e i s ^ ^ have improved the c o r r e l a t o r by adding uniformly d i s t r i b u t e d s t a t i s t i c a l l y independent noise to each of the input s i g n a l s before they are c l i p p e d . They have shown that t h i s modified p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r has an unbiased output and i s a p p l i c a b l e to any bounded random process. ( 5 ) Working independently, Ikebe and Sato , and a l s o Veltman and Kwakernaak^^ discovered the same method. For m u l t i - l e v e l (2) q u a n t i z a t i o n c o r r e l a t o r s , Widrow f i r s t suggested the method of using an e x t e r n a l s i g n a l or d i t h e r to a s s i s t the input s i g n a l i n s a t i s f y i n g the q u a n t i z i n g theorem. This r e q u i r e s the s t r i n g e n t assumption that the e x t e r n a l s i g n a l s a t i s f i e s the q u a n t i z i n g (7) theorem. Later i t was shown by Korn that uniformly d i s t r i b u t e d noise s i g n a l s can al s o be used i n m u l t i - l e v e l q u a n t i z a t i o n c o r r e -l a t o r s t o - y i e l d an unbiased output. This i s a g e n e r a l i z a t i o n of the modified p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r and w i l l be c a l l e d the modified d i g i t a l c o r r e l a t o r h e r e a f t e r . S i m i l a r l y , i t w i l l be 3 c a l l e d the m o dified S t i e l t j e s c o r r e l a t o r i f only one of the i n p u t s i g n a l s i s quantized and one e x t e r n a l n o i s e s i g n a l i s used. ( 8 ) R e c ently, Peek has employed d e t e r m i n i s t i c , s h i f t -i n v a r i a n t independent s i g n a l s as a u x i l i a r y f u n c t i o n s . Since h i s a n a l y s i s i s based completely on the time domain, the method a p p l i e s only to d e t e r m i n i s t i c time f u n c t i o n s and to e r g o d i c random processes. Although the mean-square e r r o r of the d i r e c t c o r r e l a t o r , u s i n g e i t h e r the continuous or the sampled-data scheme, has been s t u d i e d e x t e n s i v e l y i n the past, the e r r o r a n a l y s i s of the other c o r r e l a t o r s i s f a r from complete. For the d i g i t a l and the S t i e l t j e s c o r r e l a t o r s , a t t e n t i o n has been r e s t r i c t e d to the ana-l y s i s of the b i a s e r r o r . For the m o d i f i e d d i g i t a l and the m o d i f i e d S t i e l t j e s c o r r e l a t o r s , only the s i m p l e s t cases of the m o d i f i e d p o l a r i t y - c o i n c i d e n c e and the m o d i f i e d r e l a y c o r r e l a t o r s have been co n s i d e r e d . The mean-square e r r o r of the m o d i f i e d p o l a r i t y -(q) c o i n c i d e n c e c o r r e l a t o r was f i r s t g i v e n by T u r n e r v . I d e n t i c a l r e s u l t s a l s o appeared l a t e r i n papers by Knowles and T s u i ^ " ^ and by B e r n d t ^ 1 1 ) . In t h i s t h e s i s , the scheme of each of the f i v e c o r r e l a t o r s i s f i r s t d e s c r i b e d . S p e c i a l a t t e n t i o n i s p a i d to the m o d i f i e d d i g i t a l c o r r e l a t o r . By u s i n g the c h a r a c t e r i s t i c f u n c t i o n , i t i s shown that random nois e s a t i s f y i n g c e r t a i n c o n d i t i o n s can be used as an a u x i l i a r y f u n c t i o n to unbias the c o r r e l a t o r output, and t h a t u n i f o r m l y d i s t r i b u t e d random n o i s e as used i n the m o d i f i e d p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r i s a s p e c i a l case. The e f f e c t of u s i n g quantized a u x i l i a r y n o i s e i s a l s o c o nsidered. I t i s very i n t e r e s t i n g to f i n d t h at q u a n t i z i n g the a u x i l i a r y n o i s e i s e f f e c t i v e l y the same as d i r e c t l y q u a n t i z i n g the input s i g n a l . 4 Because we base a l l of the analyses on the ensemble average, the c o r r e l a t i o n methods and t h e i r e r r o r s apply to a l l s t a t i o n a r y random processes. This i s the basic d i f f e r e n c e from Peek's a n a l y s i s . In the t h i r d part of the t h e s i s , the mean-square e r r o r of each c o r r e l a t o r i s derived. I t i s found t h a t , f o r coarse q u a n t i -z a t i o n , the modified d i g i t a l c o r r e l a t o r i s superior to the d i g i t a l c o r r e l a t o r , f o r the l a t t e r has an appreciable constant bias e r r o r i n a d d i t i o n to the sampling e r r o r . The mean-square e r r o r of the modified d i g i t a l c o r r e l a t o r , on the other hand, d i f f e r s from that of the d i r e c t c o r r e l a t o r only by a term which i s i n v e r s e l y pro-p o r t i o n a l to the sample s i z e . By i n c r e a s i n g the sampling r a t e or sample s i z e , the a d d i t i o n a l e r r o r term can be reduced to a n e g l i g i b l e value. With f i x e d sampling r a t e and sample s i z e , the a d d i t i o n a l e r r o r can only be decreased by reducing the s t e p - s i z e of the quantizer. Por Gaussian processes, t h i s a d d i t i o n a l e r r o r has been evaluated f o r various s t e p - s i z e s . F i n a l l y , some aspects of the implementation of c o r r e l a t o r s w i t h coarse q u a n t i z a t i o n are considered. High-speed d i r e c t m u l t i p l i e r s using only l o g i c gates are designed. These make the m u l t i - l e v e l q u a n t i z a t i o n c o r r e l a t o r almost as e f f i c i e n t as the modified p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r , while having much smaller e r r o r . The a p p l i c a t i o n of pseudo-random, noise to the modified d i g i t a l c o r r e l a t o r i s a l s o discussed. 5 R 1 2 2. CORRELATION DEVICES The c o r r e l a t i o n f u n c t i o n of two random processes | x^(t)j- and j x 2 ( t ) j as an ensemble average i s d e f i n e d by , ( t ; t » ) = jj X l ( t ) x 2 ( t ' ) P ( x l 5 x 2 ) d x x d x 2 , where P(x-^;x 2) i s the j o i n t p r o b a b i l i t y - d e n s i t y f u n c t i o n of sample f u n c t i o n s x-^(t) and x 2 ( t ' ) . The c o r r e l a t i o n f u n c t i o n u s u a l l y depends on bo th of the sampl ing i n s t a n t s t and t ' . I f x^(t ) and x 2 ( t ) are sample f u n c t i o n s of s t a t i o n a r y random p r o c e s s e s , i t depends on l y on the i n t e r v a l ( t ' - t ) between the samp l ing i n s t a n t s . That i s , f o r s t a t i o n a r y random p r o c e s s e s , the c o r r e l a t i o n f u n c t i o n i s R 1 2 (T) = jj yL±(*) x 2 ( t+r ) P ( x 1 ; x 2 ) d x x d x 2 . (2 .1) Fo r n o t a t i o n a l s i m p l i c i t y , x-^(t) and x 2 ( t ) w i l l be used to denote random processes as w e l l as sample f u n c t i o n s . In t h i s t h e s i s we a l s o assume tha t x-^(t) and x 2 ( t ) are s t a t i o n a r y . 2.1 The D i r e c t C o r r e l a t o r The d i r e c t c o r r e l a t o r es t imates the c o r r e l a t i o n f u n c -t i o n by d i r e c t l y m u l t i p l y i n g the i npu t s i g n a l s x-^t) and x 2 ( t + T ) and then a ve r ag ing the product i n the t ime domain. A s i m p l i f i e d r e p r e s e n t a t i o n of the fundamenta l scheme of d i r e c t c o r r e l a t o r s i s shown i n F i g u r e 2 . 1 . In p r a c t i c e much more comp l i ca ted c i r c u i t s w i t h v a r i a b l e de l a y u n i t s and s to rage dev i c e s are u s u a l l y employed. The c o r r e l a t i o n f u n c t i o n es t imated by the cont inuous d i r e c t c o r r e l a t o r ( a ) , i n which analogue s i g n a l s x-^(t) and x-^t) x 2 ( t ) x-^t) x 2 ( t ) "DelayT -4 Delay k Sampler - 4 — M u l t i p l i e r [integrator (a) ft>) M u l t i p l i e r Averager ^ c 1 2 ( r ;T) •* C 1 2(k;N) F i g . 2.1 D i r e c t c o r r e l a t o r s ; a continuous d i r e c t c o r r e l a t o r (a) and a sampled-data d i r e c t c o r r e l a t o r (b) x 2 ( t ) are d i r e c t l y used f o r processing, i s C 1 2(T;T) = Jo x ^ t ) x2(t.+ r) at. (2.2) This c o r r e l a t o r output i s al s o a random v a r i a b l e . To see how t h i s time average can be used as an estimate of the true c o r r e l a -t i o n f u n c t i o n given by Eq. (2.1), we s h a l l f i n d the expected value of the output. By d e f i n i t i o n , we have E [ C 1 2 ( r ;T) = j rC 1 2(r;T) P ( x i ; x 2 ) ix±dx2 (2, where E denotes "the expected value of". S u b s t i t u t i n g Eq. (2.2) i n Eq. (2-3) and interchanging the order of i n t e g r a t i o n , we obtain 7 E c 1 2(T';T) T H 1 2(r) dt 0 ^ = R 1 2 ( T ) . (2.4) Therefore the expected value of the output of the continuous d i r e c t c o r r e l a t o r i s equal to the true c o r r e l a t i o n f u n c t i o n . In other words, the c o r r e l a t o r gives unbiased estimates of the true c o r r e l a t i o n f u n c t i o n . S i m i l a r l y , the c o r r e l a t i o n f u n c t i o n estimated by the sampled-data d i r e c t c o r r e l a t o r (b), i n which the sampled data of x-^(t) and x 2 ( t ) are used, i s N-l C 1 2(k;N) = ± X l ( n A t ) x 2(nAt+kAt) n=0 o r N - l C 1 2(k;N) = jjj <^ x l ( n ) x 2 ( n + k ) ' ( 2 ' 5 ) n=0 where, f o r s i m p l i c i t y , the sampling i n t e r v a l At i s neglected i n Eq. (2.5). Using the same method as above, i t can be shown that the expected value of the output of the sampled-data d i r e c t c o r r e l a t o r i s equal to the true c o r r e l a t i o n f u n c t i o n , i . e . , E |c i 2(k;N) = R 1 2 ( k A t ) . - (2.6) 2.2 The D i g i t a l C o r r e l a t o r Because i t i s qu i t e d i f f i c u l t to b u i l d accurate analogue delay u n i t s , m u l t i p l i e r s and i n t e g r a t o r s (or averagers), c o r r e l a -t i o n a n a l y s i s today i s u s u a l l y c a r r i e d out by d i g i t a l computation. A d i g i t a l c o r r e l a t o r has the general form shown i n Figure 2.2. The input s i g n a l s x ^ ( t ) and x 2 ( t ) are converted i n t o d i g i t a l form by the quantizers e i t h e r before or a f t e r sampling. The delay u n i t i s then r e a d i l y r e a l i z e d by s h i f t r e g i s t e r s . D i g i t a l 8 Quantizer Delay k Sampler x 2 ( t ) - 4 Quantizer M u l t i p l i e i Averager C 1 2 ( k ; N P i g . 2.2 A d i g i t a l c o r r e l a t o r m u l t i p l i e r s and averagers can a l s o be e a s i l y implemented. The c o r r e l a t o r c a l c u l a t e s the c o r r e l a t i o n f u n c t i o n of the quantized s i g n a l s x-^ q(t) x 2 q ^ ^ ' ^hus the output of the c o r r e l a t o r i s , N-l C 1 2(k;N) = i X ] x 1 n ( n ) x 9 n ( n + k ) . (2.7) n=0 1 (* 2 q Because q u a n t i z a t i o n i s a nonline a r operation, an e r r o r which d i s t o r t s the input s i g n a l i n h e r e n t l y occurs. The quantizer output can be regarded as the sum of the input s i g n a l and the qu a n t i z a t i o n n o i s e , i . e . , x i q ( t ) = x ± ( t ) + q ± ( t ) . (1=1,2) (2.8) I t i s the q u a n t i z a t i o n noise that a f f e c t s the expected value and increases the variance of the measurement. Using the above r e l a t i o n , , we have the expected value of the output of the d i g i t a l c o r r e l a t o r E [ G 1 2 ( k ; N ) J = E [ x l q x 2 q ] = E [ X 1 X 2 ] + E [ X 1 ^ 2 ] + B [ x 2 * l ] + B [ ^ 2 ] » ( 2 ' 9 ) 9 which d i f f e r s from the input c o r r e l a t i o n f u n c t i o n by jj xi cl2l + E J x g C i J + E ^ 2^2] • This b i a s e r r o r i s determined by the s t a t i s t i c s of the input s i g n a l s and the input/output c h a r a c t e r i s t i c s of the q u a n t i z e r s . Given the s t a t i s t i c s of the input s i g n a l s , one can des i g n an optimum q u a n t i z e r to y i e l d the l e a s t b i a s e r r o r . How-ever, i n the p r a c t i c a l a p p l i c a t i o n , a p r i o r i i n put s i g n a l d i s t r i -b u t i o n s are u s u a l l y unknown. E q u i - l n t e r v a l or uniform q u a n t i z e r s are thus e x t e n s i v e l y employed i n c o r r e l a t i o n a n a l y s i s . The uniform q u a n t i z e r has the input/output c h a r a c t e r i s t i c shown i n F i g u r e 2.3, where Ax^(i=l,2) i s the l e v e l increment or step s i z e . A^(i=l,2) i s a s h i f t f a c t o r . Two cases of l q 5 Ax. A, Ax. 1—? L A.Ax. r 1 1 F i g . 2.3 C h a r a c t e r i s t i c of the uniform q u a n t i z e r i n t e r e s t are when A^ = 0, where the in p u t s i g n a l i s quantized with a n u l l zone, and when A^ = 1/2, where the i n p u t s i g n a l i s quantized without a . n u l l zone. To f i n d the c o r r e l a t i o n f u n c t i o n of the quantized s i g n a l , we make use of the c h a r a c t e i s t i c f u n c t i o n which i s the F o u r i e r t r a n s f o r m a t i o n of the p r o b a b i l i t y - d e n s i t y f u n c t i o n . By d e f i n i t i o n , the c h a r a c t e r i s t i c f u n c t i o n of and i s M(a i ;a 2) = B I e 1 1 \ , (2.10) 10 and the c h a r a c t e r i s t i c f u n c t i o n of the quantized s i g n a l s x-^ and joe, x-, + j a 0 x 0 ( 2 . 1 1 ) I t i s obvious that the c o r r e l a t i o n f u n c t i o n i s equal to the negative of the d e r i v a t i v e of the c h a r a c t e r i s t i c f u n c t i o n w i t h respect to oc-^  and O w - , at the o r i g i n , i . e . , _ ^ 2 M ( a i ; a 2 ) E [ X l x 2 ] d a! d a2 and E [ X l d X 2 q ] 3 V*i;«2> a - j L=a 2 = 0 . ( 2 . 1 2 ) ( 2 . 1 3 ) I t can be shown^^-^ that the c h a r a c t e r i s t i c f u n c t i o n s of the quantized and unquantized s i g n a l s are r e l a t e d as f o l l o w s . C O oo M q ( a l ; a 2 ) = Y~". y"eJ2jc(kAl^A2 ) M ( a n - 2 * k 1 A x n ' ~2 A x 9 k=-eo jg=-co - 1 * 1 1 s i n 2 ( a - L A x 1 - 2 j t k ) s i n 2 ( a 2 A x 2 - 2 i t 9. ) | - ( a 2 A x 2 - 2 j t J c ) , ( 2 . 1 4 ) | ( a 1 A x 1 - 2 j t k ) where x ^ and x 2 are assumed to ha.ve zero mean value. S u b s t i t u t i n g Eq. ( 2 . 1 4 ) i n Eq. ( 2 . 1 3 ) , we have C O E [ X l q X 2 q ] = E [ X 1 X 2 ] - TZ * e J 2 i t k A 1 k=-oo A x 2 Jtk X ( - D k ^ ) M ( - 2 i t k / A x 1 ; a 2 ) a 2 = 0 - Y ^ e ^ k 2 • 4=-oo A x Q f 2> M ( a i ; - 2 ^ / A x 2 ) 1 a 1 = 0 co / « ' • ^  A-v ' A v ' k=-oo £ = - o o Q Ax-, ' A x 0 4* k j l 1 2 (2.15) where the prime on the summation s i g n means " s k i p the number 0 " . 1 1 Comparing E q . . ( 2 . 1 5 ) with E q . ( 2 . 9 ) , we can i d e n t i f y the 2 n d o term on the right-hand side as E ^ T ^ ] » "*:NE 3 r d term as E jx-^q^ and the 4 t h term as E Jq-^q^J • x^ and are said to s a t i s f y the two-dimensional quantizing theorem i f K(a^;a^) i s bounded i n two dimensions, and i f the step size i s so small that M(a 1;a 2) = 0 for a 1 > 2TC A x n and K>l> 2JC A x , (2.16) *1 1 ~~2 In t h i s case, the correlation function of the quantized signals i s equal to that of the unquantized signals, i . e . , E [ X l q X 2 q ] = E [ X 1 X 2 ] • ( 2 - 1 7 ) ( 2 ) Since no r e a l signals can s a t i s f y the quantizing theorem , the bias error given i n Eq. ( 2 . 1 5 ) inherently exists. This bias error has been studied extensively by Widrow^^ 2^ and other authors. 2 . 3 The Modified D i g i t a l Correlator One way to eliminate the bias error produced i n the d i g i t a l correlator i s to add independent a u x i l i a r y noise to each of the input signals before they are quantized, as shown i n Figure 2 . 4 . We s h a l l show i n this section that the expected value x±(t) a 1 ( t ) a 2 ( t ) x 2 ( t ) Idder Sampler Quantizer Delay Mu l t i p l i e r Adder - 4 Quantizer Averager C 1 2 ( k ; N ) F i g . 2 . 4 A modified d i g i t a l correlator 12 of the output of the modified d i g i t a l correlator can be equal to the c o r r e l a t i o n function of the input signals x^(t) and x 2 ( t ) , provided that the a u x i l i a r y noise inputs a-^(t) and a 2 ( t ) s a t i s f y c e r t a i n conditions. Let y 1 ( t ) = X l ( t ) + a i ( t ) and (2.18) y 2 ( t ) . = x 2 ( t ) + a 2 ( t ) , and l e t y ^ ( t ) and y 2 q ( t ) be the quantized versions of y-^(t) and y 2 ( t ) . Then the output of the correlator i s , N-l c 1 2(k;N) = | y y i q ^ n ) y 2 q ( n + k ) (2.19) n=0 and the expected value of the output of the correlator i s E [ 0 1 2 ( k ! N ) ] = B [ y l q y 2 q ] , (2.20) where y l q = y ^ d i ) and y 2 q = y 2 q(n+k). This expected value can be calculated from the joi n t c h a r a c t e r i s t i c function, M (<x-.;ap), of the quantized signals and Y2q> that i s a 1 = a 2=0. (2.21) As i n Eq. (2.14), M (a, ;a ? ) and the ch a r a c t e r i s t i c function, My(a^;a 2 ) , of the unquantized signals y-^(t) and y 2 ( t ) have the following r e l a t i o n : j2jt(kA +£A ) Q M (a :a ) - > > e 1 2 • M (a - — • a • yq v 1' 2 ; ~ / \/ , yK 1 Ax ' a2 Ax 0 J k=-oo 4=-co ± ^ 1 1 s i n 2(a. Ax, -2ick) s i n 2 (aoAxo-2:t0 ) T • T , (.2.22) 2(a 1Ax 1-2jtk) 2(a 2Ax 2-2it£ ) where y-^(t) and y 2 ( t ) , and hence a-^(t) and a 2 ( t ) , are assumed to have zero mean. By d e f i n i t i o n , we have 13 j a 1 ( x 1 + a 1 ) + j a 2 ( x 2 + a 2 ) P (X-J^  j x^ > 5 ) cl-Xj^dx^dEu^dsi^ • (2.23) Let us assume t h a t a-^(t) and a 2 ( t ) are independent of x-^(t) and x 2 ( t ) and of each other. Then the j o i n t p r o b a b i l i t y - d e n s i t y f u n c t i o n can be w r i t t e n as P ( x 1 ; x 2 ; a 1 ; a 2 ) = P U ^ x ^ P ( a i ) P ( a 2 ) . (2.24) S u b s t i t u t i n g Eq. (2.24) i n t o Eq. (2.23), we have M ( y ff j a 1 x 1 + j a „ x 9 f joe, a-. o c l ; a 2 ) = J J e ^ P ( x 1 ; x 2 ) d x 1 d x 2 - J e x - LP(a 1)da- L • e d ^ P ( a 2 ) d a 2 = M ( a 1 ; a 2 ) M a l ( a 1 ) M a 2 ( a 2 ) , (2.25) where M ( a 1 ; a 2 ) , M a 3 _ ( a i ) and M a 2 ^ a 2 ^ a r e t h e c n a r a c ' t e r i s ' t i c f u n c -t i o n s of x^ and x 2 , a-^, and a 2 r e s p e c t i v e l y . T h e r e f o r e , M ( yq oo co j23t(kA,+2A ) 0 , 0 Q k=-eo fi=-co 1 s i n 2(a-^Ax-^-2jtk) ^•(a 1Ax 1-2ick) M ( a _2sk) • a l v a l A X l ' 'sin 2(a 2Ax 2-2^j2.) ^ ( a 2 A x 2 - 2 K j i ) (2.26) D i f f e r e n t i a t i n g Eq. (2.26) w i t h r e s p e c t to and a 2 at the o r i g i n y i e l d s E [ y A ] = E[v 2] e j 2 j l k A l # 3 M( -2^k/Ax 1; a 2 ) ^ s i n 2 ( a 1 A x 1 - 2 t f k ) 2(a 1Ax - L -2 i tk ) 14 B u t 3 a-, a l V 1 A X l ; a,=«,=0 - ^ e J 2 , t e A 2 . $ M ( a i ; - 2 g t / A x 2 )  1 d j2 = -°= £ a. 1 2 1 s i n 2(OUAX„-2JCJI) M / _23tg. v —=—= — •• a2 v 2 Ax ; !(oc 2Ax 2-2:tl) a-^=a2=0 OO OO ^ ' e ^ ' i H A v . ' "AY_ J ->rt k=-cO £ = -oO Ax-^ ' x-^  ^a-^ 1 1 s i n 2 (a^Ax-L-2rck) |(a 1Ax 1-2^k) M (a - — ) a l v 1 Ax 1 1 s i n 2(a-^Ax-^-2itk) |'(a 1Ax 1-2ick) 1 9 a, "sin 2(a 9Ax Q-2:tjl) 0 0 -^— ^ • M 0 ( a 0 - f ^ J L - ) | ( a 2 A x 2 - 2 ^ ) a 2 2 A X 2 . M n ( a n - ^ ) a l 1 Ax-^  3 a 1 s i n 2(a^Ax^-2itk) i ( a 1 A x 1 - 2 J c k ) a 1 = 0 a 1 = 0 . M t 2rck>, s i n ( - J t k ) a l ^ A x ^ + (-jck) a-j =a2=0. (2.27) ^ M a l ^ a l " 2 j t k / / A x l ^ a 1 = 0 Ax 1 2atk . „ a i ( _ g k . ) , 1 k ^ 0, 0 » . S i m i l a r l y , 3 a. - • 1 s i n 2(a 2Ax 2-2jcJt) | ( a 2 A x 2 - 2 7 t ^ ) k = 0. a2 v 2 A x 2 ; a2=0 (2.28) A X 2 ( - 1 ) A • ¥ v ; a2 v Ax, ;' 2%l 0, X = o. (2.29) In order that the c o r r e l a t i o n f u n c t i o n of the quantized s i g n a l s be equal to that of the input s i g n a l s , we r e q u i r e that both terms of the l e f t - h a n d side of Eqs. (2.28) and (2.29) be equal to zero f o r a l l k and JL ; thus we r e q u i r e and M = 0, a l A x 1 ' a2^ A x 2 ; - u ' k / 0 , ^ 0. (2.30) In other words, the expected value of the output of the modified d i g i t a l c o r r e l a t o r can be equal to the desired c o r r e l a t i o n func-t i o n of the input s i g n a l s , provided that the added random noises ( l ) have zero mean values, (2) are independent of the input s i g n a l s and of each other, and (3) are so d i s t r i b u t e d that t h e i r character-i s t i c f u n c t i o n s have p e r i o d i c zeros w i t h periods 2ic/Ax^ and 2TC/L\X^. The c h a r a c t e r i s t i c f u n c t i o n which s a t i s f i e s the f i r s t and the t h i r d c o n d i t i o n s can be w r i t t e n i n the f o l l o w i n g general form: n i . F ( a ) , M f a ) = T T " i = l a i _ / 5 _ A x f (2.31) where n^ .'s are nonzero, p o s i t i v e numbers and F(oc) i s such that |F (ct)|<l, F(0) = 1 and F'(o) = 0. For the case that n-j_. = n, f o r a l l i , and F(oc) = 1, we have M ( a ) = I a i = l 1 - ( f ^ 2 n sin(aAx/2)" aAx/2 n (2.32) I t i s w e l l known t h a t , f o r n = 1, Eq. (2.32) represents the c h a r a c t e r i s t i c f u n c t i o n of a r e c t a n g u l a r d i s t r i b u t i o n with f o r |a|^Ax/2 -0, f o r |a|>Ax/2. (2.33) P(a) =fe- > Por a l l other i n t e g r a l n, the probability-density function represented by Eq. (2.32) i s just the n-fold convolution of the above rectangular d i s t r i b u t i o n . For example, for n = 2, we have M (a) = a sin(aAx/2. aAx/2 and the corresponding probability-density function i s (2.34) P(a) = 1 1 AX r Si]' f o r |£^Ax (,0, for |a|>Ax, (2.35) which i s a triangular d i s t r i b u t i o n and i s the two-fold convolution of the rectangular d i s t r i b u t i o n given by Eq. (2.33). F ( c t ) can be arbit r a r y as long as | P ( a ) | ^ l , F ( 0 ) = 1, and F ' ( o ) =0. An example i s the cosine d i s t r i b u t i o n with P(a) = 1 / T :ta\ I 2Ai ( l + C O S A i } ' 0, for |a|^Ax for |a|>Ax (2.36) Direct Fourier transformation of Eq. (2.36) gives M (a) = a aAx 2 A 2 -1 (1 - • , Thus we have F ( a ) cos aAx it 2 2 (1 - 5L|3L_) -1 (2.37) (2.38) Because P(a) can be the ch a r a c t e r i s t i c function of any di s t r i b u t i o n , Eq. ( 2.3l) implies that any random noise for which the probability-density function i s rectangular as given by Eq. (2.33) i t s n-fold convolution or i t s convolution with any other d i s t r i b u -t i o n function can be employed as an a u x i l i a r y noise i n the modified d i g i t a l correlator. This i n turn implies that, to unbias the output of the modified d i g i t a l correlator, the added auxiliary-random noise must have a rectangularly distributed noise component. 17 2 .3.1 The M o d i f i e d P o l a r i t y - C o i n c i d e n c e C o r r e l a t o r The q u a n t i z e r s considered so f a r have been assumed to quantize the in p u t s i g n a l to an i n f i n i t e number of l e v e l s . However, a l l the r e a l s i g n a l s are a m p l i t u d e - l i m i t e d f o r p r a c t i c a l reasons. In t h i s case only a f i n i t e number of q u a n t i z i n g l e v e l s are r e q u i r e d . The mo d i f i e d p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r i s the s i m p l e s t case, i n which only 2 - l e v e l q u a n t i z e r s are used. Le t B.^  and B^ be the bounds of the in p u t s i g n a l s x-^(t) and x 2 ( t ) , i . e . , Ix-^tJI^B.^ and | x 2 ( t)|^B 2. I f the q u a n t i z e r s are so s e l e c t e d t h a t = A 2 = l / 2 , i . e . , x^(t) and x 2 ( t ) are quantized without a n u l l zone, and At^ = 2B 1 and At^ = 2B 2, then we have |x 1+a 1|^Ax 1 and | x 2+a 2|^Ax 2, (2 .39) where the a u x i l i a r y n o i s e s are assumed to be r e c t a n g u l a r l y d i s t r i -buted. Therefore, only two l e v e l s are r e q u i r e d f o r the q u a n t i z e r s . Since Ax, y l q = — sgnUj+a-L) = B x sgn ( x 1+a 1) (2.40a) and y 2 q = B 2 sgn ( x 2+a 2), (2.40b) where sgn means "the s i g n o f ", we have £-,B_ N - l _ C 1 2 (k;N) = X sgn [x 1(n)+a 1(n)J • sgn [x2(n+k)+a2(n+k)J . (2.41) Thus the c o r r e l a t i o n f u n c t i o n can be r e a d i l y estimated from the si g n s of the samples of the combined s i g n a l and n o i s e . Using Eq. (2.41), a m o d i f i e d p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r can be e a s i l y r e a l i z e d by a comparator and a p o l a r i t y -c o i n c i d e n c e c i r c u i t . The theory and implementation of the modified p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r have been e x t e n s i v e l y s t u d i e d i n the past ^ ) (5) (6) (9), 18 2.3-2 D i s c r e t e A u x i l i a r y Random Noise We have shown that any random noise which s a t i s f i e s the c o n d i t i o n s given by Eq. (2.30) can be used as a u x i l i a r y random noise inputs to y i e l d an unbiased output i n the modified d i g i t a l c o r r e l a t o r . Obviously the d i s t r i b u t i o n f u n c t i o n of such noise i s continuous. However, i n the p r a c t i c a l a p p l i c a t i o n , i t . i s very hard, i f not impossible, to obtain such i d e a l i z e d random noise. For c o n s t r u c t i o n a l s i m p l i c i t y , a noise generator which produces d i s c r e t e - l e v e l outputs i s f r e q u e n t l y employed. This s e c t i o n i s concerned w i t h the e f f e c t of using d i s c r e t e l y d i s t r i b u t e d random noise i n the modified d i g i t a l c o r r e l a t o r . Por s i m p l i c i t y , only r e c t a n g u l a r l y d i s t r i b u t e d noise i s considered. the quantized v e r s i o n of a continuous d i s t r i b u t i o n f u n c t i o n as shown i n Figure 2.5, where b ( t ) i s the d i s c r e t e a u x i l i a r y n o i s e . A d i s c r e t e d i s t r i b u t i o n f u n c t i o n can be considered as b( t ) A a - A x / 2 •a A x / 2 a ( t ) * A a * F i g . 2.5 Input/output c h a r a c t e r i s t i c of a quantizer f o r a u x i l i a r y noise 19 Assume that b ( t ) has Q d i s c r e t e l e v e l s . Each of these Q l e v e l s • w i l l have equal p r o b a b i l i t y i f the s h i f t f a c t o r d i s equal to 0 or 1/2 and the step s i z e Aa i s Aa = |p . (2.42) Q i s odd i f d = 0 and even i f . d = 1/2. ' The " c h a r a c t e r i s t i c f u n c t i o n , M^(a), of b ( t ) i n terms of the c h a r a c t e r i s t i c - f u n c t i o n , M (a), of a ( t ) i s 1 HL (a) = y~^ei2%md • M ( a - 2 ^ ) • s i n ^ ( a A a ^ m n ) ( 2 > 4 3 )  b fe£ a A a |(aAa-2ran). Since a ( t ) i s uniformly d i s t r i b u t e d w i t h i n Ax, we have M ( a) = sin(aAx/2) (2.44) a cxAx/2 •' . S u b s t i t u t i n g Eq. (2.44) i n t o Eq. (2.43) y i e l d s NLpCoc) = > ° | e j 2 j c n i d s i n 2(aAx-2jrmQ) # s i n 2(aAa-2jrm) (2.45) m = - c 0 |(ocAx-2jtmQ) |(aAa-2rcm). Now l e t b-^(t) and b 2 ( t ) be the d i s c r e t e a u x i l i a r y noises which are added to the input s i g n a l s x-,(t) and x 2 ( t ) . D e f i n i n g QT_» Q2 > d-^j d2> and Aa-^, Aa 2 i n the same way as shown above, we may obtain s i m i l a r expressions f o r the c h a r a c t e r i s t i c f u n c t i o n s •Mbl(oc) and M^Coc) as given by Eq. (2.45). The expected value of the output of the c o r r e l a t o r i s i d e n t i c a l to that given by Eq. (2.27) except that M - ^ a ) and Ma2(oc) are replaced by M-j^a) and M^oc). To f i n d t h i s expected value, we must evaluate M ^ C a ) and M f e 2(a) at p e r i o d i c points as shown by Eqs. (2,28) and (2.29). From Eq. (2.45), we have. M / 2jcks s°° u^atmd-, sinittk+mQj) sinjt(k/Q1+m) 20 -j2ickd / Q e 0, a l l other k^O. (2.46) S u b s t i t u t i n g Eq. (2 .46) i n t o Eq. (2.28), w i t h M^ replaced by ^ " R • TT( aAx-, -2itk) 0 , 1 2=-( a-^Ax-^-2ick) Ax - j2 3tkd. 1/Q 1 • 2 ^ k ( - l ) ' e I 0, k=+Q1, +Q2,.. a l l other k^O Ax-. n -i2jrmd 1 2xky ± J e , kz=mQ-^  and m=+l, +2 , 0, I t i s noted that a l l other k^O (2.47) (-1) Q1 • e 1 (-Dm, (2.48) because i s odd i f d-^0 and even i f d - ^ l / 2 . Therefore we have "sin | ( V * i - ^ > „ _ | ( a i A X l - 2 , k ) ^ 1 A x l 1 (-Dm, S i m i l a r l y 1 2jck , 0 , s i n | ( « 2 A x 2 - 2 ^ } |(a 2Ax 2-2itC.) k=mQ-^  and m=+l, +2 , a l l other k^O. (2.49) 2%l (-1)n, I =nQ2 and n=+l, +2 0 , a l l other j? ^ 0 . (2.50) 2 1 S u b s t i t u t i n g Eqs. (2.49) and (2.50) i n t o Eq. ( 2 . 2 7 ) , w i t h M x and r e p l a c e d by and w e ^ a v e E [ y i q y 2 q ] - E [ x i x 2 ] co ^— 1 e m=-oo _ A x l 2:tmQ • ( - 1 ) m 00 T j2jcnQ 2A 2 n=_oo 1 A x n ~ 2 , ( - l ) n 3M(-2jtmQ1/Ax1;a2) a 2 =0 3M(a n ; - 2 j c n Q 2 / A x 2 ) 3 a 0^=0 0 0 ^ i ^ T - " j2it(mQ A +nQ 0A Q) Ax. Ax„ E 1 1 , 2 2- • 1 2 ^  _^ ^  m+n m=-«j n=-oo 2 4it mn 2rtmQ-, 2 j m Q 0 M(~ i - 2-) v A x 1 ' A x 2 ; (2.5D Comparing Eq. ( 2 . 5 1 ) w i t h Eq. ( 2 . 1 5 ) , we f i n d t h a t t h i s expected v a l u e i s the same as t h a t of the u n m o d i f i e d d i g i t a l c o r r e l a t o r of w h i c h the i n p u t s i g n a l s are q u a n t i z e d d i r e c t l y w i t h o u t a d d i n g a u x i l i a r y n o i s e . However, the s t e p s i z e s of the q u a n t i z e r s are now i n e f f e c t reduced t o Ax-^/Q^ and L\x^/Q^. T h e r e f o r e , as f a r as the c o r r e l a t i o n f u n c t i o n i s concerned, the d i s c r e t e a u x i l i a r y n o i s e , b e i n g added t o the i n p u t s i g n a l s b e f o r e they a re q u a n t i z e d , has the e f f e c t of q u a n t i z i n g more f i n e l y the i n p u t s i g n a l s . The l a r g e r the number of d i s c r e t e l e v e l s of the a u x i l i a r y n o i s e , the f i n e r the q u a n t i z a t i o n . I n the extreme case t h a t and Q 2 approach i n f i n i t y , the i n p u t s i g n a l s are e f f e c t i v e l y u n q u a n t i z e d and the expected v a l u e of the output of the c o r r e l a t o r i s e q u a l t o the t r u e c o r r e l a t i o n f u n c t i o n . T h i s i s t h e case of a d d i n g c o n t i n u o u s n o i s e as c o n s i d e r e d b e f o r e . The advantage of u s i n g d i s c r e t e a u x i l i a r y n o i s e can be seen i n the f o l l o w i n g . Consider,, f o r example, the case of the 22 modified polarity-coincidence correlator i n which uniformly distributed a u x i l i a r y noises of and discrete l e v e l s are used. The correlator i s i n effect the same as an unmodified d i g i t a l correlator i n which the input signals are quantized -into 2Q^ and 2Q^ l e v e l s . Although i t i s possible to build such a d i g i t a l correlator using 2Q-^ - and 2Q2~ l e v e l quantizers, implementation of the quantizers, the m u l t i p l i e r and the related processing units w i l l be intolerably complicated. On the other-hand, a modified polarity-coincidence correlator with a random noise generator which generates a large number of discrete output l e v e l s can be ea s i l y constructed. 2.4 The S t i e l t j e s Correlator In the S t i e l t j e s correlator, only one of the input signals i s quantized and no auxilary noise i s used, as shown i n Figure 2.6. This i s a kind of hybrid analogue-digital correlator. 4 X l ( t ) ^ Quantizer * Delay k M u l t i p l i e r Averager x 2 ( C 1 2(k;N) Fi g . 2.6 A S t i e l t j e s correlator It has some advantages of both the dire c t and the d i g i t a l correlators-The output of the S t i e l t j e s correlator, using the sampled-data scheme, i s • N-l C 12 (k;N) = | 21] „(n) x 0(n+k) n=0 (2.52) 23 I t can r e a d i l y be shown that the expected value of the out-put of the c o r r e l a t o r i s E [ci2(k;N)J = E [\x2J + E [ x^ J , ( 2 . 5 3 ) where E ^ x 2 q j i s equal to the second term on the right-hand side of Eq. ( 2 . 1 5 ) . Comparing t h i s w i t h the expected value of the output of the d i g i t a l c o r r e l a t o r given by Eq. ( 2 . 1 5 ) , we f i n d that the b i a s e r r o r of the S t i e l t j e s c o r r e l a t o r i s much smaller than that of the d i g i t a l c o r r e l a t o r . 2 . 5 The Modified S t i e l t j e s C o r r e l a t o r I f an a u x i l i a r y noise s a t i s f y i n g the c o n d i t i o n given by Eq. ( 2 . 3 0 ) i s added to the input s i g n a l , x-^(t), before i t i s quantized i n the S t i e l t j e s c o r r e l a t o r , the bias e r r o r E ^ x 2 q J can be e l i m i n a t e d . As shown i n Figure 2 . 7 , the output : 2 ( t ) a]Tt> x 2 ( t ) ' Adder "5 . A . > Quantize Delay k M u l t i p l i e r -4 Averager C 1 2(k;N) F i g . 2 . 7 A modified S t i e l t j e s c o r r e l a t o r of the modified S t i e l t j e s c o r r e l a t o r i s N - l C 1 2 (k ;N) 12 n=0 y l q ( n ) x 2(n+k), ( 2 . 5 4 ) where y^ q i s the quantized v e r s i o n of the combined s i g n a l x^ and a u x i l i a r y noise a-^ . The expected value of t h i s output, f o r the same reason as i n the case of the modified d i g i t a l c o r r e l a t o r , i s The simplest case of the modified S t i e l t j e s c o r r e l a t o r i s the modified r e l a y c o r r e l a t o r . I f the input s i g n a l x-^(t) i s a m p l i t u d e - l i m i t e d , a t w o - l e v e l or one-bit quantizer can be used. In t h i s case, the m u l t i p l i e r can be replaced by a simple r e l a y c i r c u i t . 25 3 . ERROR ANALYSIS 3 • 1 C r i t e r i a f o r Judging the Performance of a C o r r e l a t o r There are three c r i t e r i a commonly used f o r judging the performance of a c o r r e l a t o r . They are the mean-square e r r o r (tf or MSE), the s i g n a l - t o - n o i s e r a t i o (SNR), and the e r r o r index. The Mean-Square E r r o r The mean-square e r r o r of a c o r r e l a t o r i s defined as the expected value of the square of the d e v i a t i o n of the c o r r e l a -t o r output from the true value of the c o r r e l a t i o n f u n c t i o n . Let C denote the c o r r e l a t o r • output C^^^" '"^  o r ^ 1 2 ^ ' ^ ' a n < ^ ^ denote the true c o r r e l a t i o n f u n c t i o n R^i?) or R^{k) . Then, by d e f i n i t i o n , the mean-square e r r o r i s Let EC be the expected value of the output of the c o r r e l a t o r . The mean-square e r r o r can a l s o be expressed i n the f o l l o w i n g form: The f i r s t term on the right-hand side of Eq. ( 3 . 2 ) i s the mean-square e r r o r of the c o r r e l a t o r output about i t s expected value and i s c a l l e d "the variance of the estimate, i . e . , The second term i s the square of the d e v i a t i o n of the expected value from the true c o r r e l a t i o n f u n c t i o n . This, can be defined as the bias e r r o r , B, of the c o r r e l a t o r . That i s ( 3 . D ( 3 - 2 ) Var [ c ] = E [ ( C - E C ) 2 ] = E [ C 2 ] - [ E C ] 2 . ( 3 . 3 ) B = (EC - R ) 2 . ( 3 . 4 ) Therefore,the mean-square e r r o r of a c o r r e l a t o r about the true c o r r e l a t i o n f u n c t i o n i s composed of the variance and the bias e r r o r . The variance e x i s t s i n h e r e n t l y w i t h f i n i t e measuring-time, T, or f i n i t e number of samples, N. The bias e r r o r i s zero i f the output of the c o r r e l a t o r i s unbiased. I t i s u s u a l l y d e s i r a b l e f o r the mean-square e r r o r to decrease w i t h i n c r e a s i n g sampling time T or NAt. The c o r r e l a t o r i s s a i d to be con s i s t e n t i f the mean-square e r r o r approaches zero when T or N approaches i n f i n i t y , i . e . , i f l i m 2 ~ r - ^ e =0. (3-5J T or N-^°° For a c o r r e l a t o r to be con s i s t e n t i t i s required that the output of the c o r r e l a t o r be unbiased and that the variance approach zero w i t h i n c r e a s i n g T or N. In. some cases, the normalized mean-square e r r o r i s al s o used. I t i s defined as the r a t i o of the mean-square e r r o r to the square of the true c o r r e l a t i o n f u n c t i o n , i . e . , Normalized c 2 = E [(C-R) 2j/P. 2. (3-6) The Signal-to-Noise Ratio When a c o r r e l a t o r i s used f o r d e t e c t i n g a s i g n a l imbedded i n background noise, the primary i n t e r e s t i s not i n the true c o r r e l a t i o n f u n c t i o n , but ra t h e r i n the existence of the s i g n a l . The expected value of the output of the c o r r e l a t o r i s then not n e c e s s a r i l y equal to the true c o r r e l a t i o n f u n c t i o n . I t can be biased or d i s t o r t e d to a c e r t a i n extent without a f f e c t i n the d e t e c t a b i l i t y of the s i g n a l . In t h i s case the q u a l i t y of the c o r r e l a t o r i s determined by i t s output s i g n a l - t o - n o i s e r a t i o , which i s defined by SNR = [Ec] 2/Var [c ] , (3.7a) or, i n d e c i b e l s , SNR = 2 0 l o g 1 0 | ' [ E c ] 2 / V a r [c]} dB. ( 3 - 7 b ) For a c o r r e l a t o r which y i e l d s an unbiased estimate of the c o r r e l a t i o n f u n c t i o n , such as a d i r e c t or a modified d i g i t a l c o r r e l a t o r using continuously d i s t r i b u t e d a u x i l i a r y n o i se, the output SNR i s the same as the inverse of the normalized mean-square e r r o r . The E r r o r Index The e r r o r index i s defined as the square root of the normalized mean-square e r r o r , i . e . , 7 =J e2/R2 . ( 3 - 8 ) Because the s i g n a l - t o - n o i s e r a t i o and the e r r o r index are c l o s e l y r e l a t e d to the mean-square e r r o r , only the mean-square e r r o r w i l l be considered i n the f o l l o w i n g analyses. 3 . 2 The Mean-Square E r r o r of the D i r e c t C o r r e l a t o r . Since the expected value of the output of the d i r e c t c o r r e l a t o r i s unbiased, the mean-square e r r o r i s equal to the varian c e . Thus we have, f o r sampled-data measurement, N-l N - l N m=0 n=0 -5 1 N - l N - l - , 0 e^(k;N) = 2~] ^ 2 E| xi (m)x 9(m+k)x. (n)x 9(n+k)| -Rf„(k), ( 3 . 9 a ) and, f o r continuous measurement, - o -1 rT /-T E [ x 1 ( t ) x 2 ( t + r ) x 1 ( f ) x 2 ( t ' + r)] d t d t ' - R 2 2 ( r ) ° y o ( 3 . 9 b ) The 4th-order moment can be found only when the j o i n t 4th-order p r o b a b i l i t y - d e n s i t y f u n c t i o n of x ^ ( t ) and x 2 ( t ) i s known. I f x-^(t) and x 2 ( t ) are sample functions of Gaussian processes, the 28 4-th-order moment has the f o l l o w i n g simple form: E [x^^x^t+r)!^' ) x 2 ( t ' + 7-)] = R 1 1 ( ^ ) R 2 2 ^ ) + Ri 2 (r) + R 1 2(r+\)R 1 2(r~^), ( 3 . 1 0 ) where \ = t - t * . S u b s t i t u t i n g Eq. ( 3 . 1 0 ) i n t o Eqs. ( 3 - 9 a ) and 3 - 9 b ) y i e l d s £^(k;N) R u ( 0 ) R 2 2 ( 0 ) + R 2 2 ( 0 ) _ R 1 2 ( k - r ) ] N-l + ^ 2 ^ ] (N-r) [ R 1 3 ' ( r ) R 2 2 ( r ) + R 1 2 (k+r) ( 3 . 1 1 a ) r = l and •T e 2 ( r ; T ) = ^ 2 I ( T - \ ) [ R 1 1 ( \ ) R 1 2 ( \ ) + R 1 2 ( r + \ ) R 1 2 ( r - \ ) ] d \ . ( 3 . 1 1 b ) T J 0 I t i s noted that the mean-square e r r o r f o r Gaussian processes depends s o l e l y on the auto- and c r o s s - c o r r e l a t i o n f u n c t i o n s . By assuming commonly encountered c o r r e l a t i o n f u n c t i o n s , some u s e f u l knowledge of the e r r o r may be gained. Consider, f o r example, white Gaussian noise passed through a low-pass RC f i l t e r w i t h -3dB bandwidth b/2ic Hz. The a u t o c o r r e l a t i o n f u n c t i o n of the noise at the f i l t e r output i s . R(r) = cr2e~h]rl , b > o . ( 3 . 1 2 ) S u b s t i t u t i n g Eq. ( 3 . 1 2 ) i n t o Eqs. ( 3 . 1 1 a ) and ( 3 . 1 1 b ) w i t h x-^=x2, we obtain 4r e£(k;N) = N(l+e -2bkAt } + 4 N e "2 b A t _ 4 e - 2 b A t ( l - e - 2 b N A t ) ' 1-e -2bAt ( l _ e - 2 b A t ) 2 , k= 0 , l 29 4 r2 N' ~ ( 1 -2bkAt^ 2 N e " 2 b A t + 2 ( N - k ) e " 2 b k A t i n ± e ; + . -2bAt 1-e 0 -2bAt/, 0 -2bNAt -2bkAtx , 0, , A, - £e U-2e +e ± ( N _ k } ( } -2bkAt / ~2bAt^2 + U 2 M K ; e • (1-e ; , 2 < k ^ N - l , ( 3 . 1 3 a ) and cr 4 2irT^ i n 2bT-l+2e 2 b T + ( 2 b T + l ) ( 2 b T - l ) e 2 b 7 " - 2 b 2 r 2 e 2 b r 0 < r < T . ( 3 . 1 3 b ) I f the sampling time i n t e r v a l At i s much smaller than the r e c i p r o c a l bandwidth, 2ic/b, and i f the t o t a l number of samples taken i s so l a r g e that F b A t » l , then we have C T 4/NbAt < £2(k;N) < 2 C T 4/NbAt. S i m i l a r l y , i f bT^>l, we have <T 4/bT <£^(r ;T) < 2 C T 4 / b T , ( 3 . 1 4 a ) ( 3 . 1 4 b ) Eqs. ( 3 . 1 3 a ) and ( 3 . 1 3 b ) a l s o show that the mean-square e r r o r approaches zero when the observation time NAt or T i s •very l a r g e . Therefore,the output of the c o r r e l a t o r i s a c o n s i s t e n t estimate. The f l u c t u a t i o n e r r o r can be reduced t c any d e s i r e d value by t a k i n g a l a r g e r number of samples or measuring f o r a longer time. I f , f o r example, bAt = l/lOO ( i . e . , 1 0 0 samples are taken i n O ^ T ^ l / b ) , N^ > 2 x l 0 ^ w i l l make the d e v i a t i o n l e s s than one percent of 0" • 3 • 3 The Mean-Square E r r o r of the D i g i t a l C o r r e l a t o r The mean-square e r r o r of the d i g i t a l c o r r e l a t o r c o n s i s t s of both the variance and the bias e r r o r . That i s !(k;N) = V a r C^12(k;N)J + B q, (3.15) where B i s the "bias error of the d i g i t a l correlator, q to It follows d i r e c t l y from Eqs. (2.7) and ( 3 - 3 ) that the variance i s N-l N-l Var[C 1 2 (k;N)] = 3 ^ ] T ^ K U ) x 2 q ( m + k ) x l q ( n ) x 2 q ( n + k ) ] - J E [ c 1 2 ( k ; N ) ] j 2 , (3.16) where the expected value, EJC^ 2(k;N)J , of the output of the correlator has been given i n Eqs.(2.9) and(2.15). The 4th-order moment i n Eq. (3 .16) i s usually unknown. However, i n the special case that x-^(t) and x 2 ( t ) are sample functions of G-aussian processes, i t can be expressed e x p l i c i t l y i n terms of the i r auto- and cross-correlation functions. To f i n d the 4th-order moments, the method of ch a r a c t e r i s t i c functions i s again employed. Let the correlation functions of x-^(t) and x 2 ( t ) be E ^ - j X ^ ] = R i : L(r) , E[x 2x 2'] = R 2 2 ( r ) , E [ x - ^ ] = R 1 2 ( k ) , E [ X l x 2 ' ] = R 1 2(k+r), E j x ^ * ] =:.-.R12(k-r) , E f x - ^ x ^ ] = R 1 2 ( k ) , where x^=x-^(m), x - ^ ' = X j L(n), x2=x2(m+k), x2'=x2(m+k) and r = m-n. Then the ch a r a c t e r i s t i c function of x-^ , x 2, x-^ ' and x 2 ,(12) i s M ( a 1 ; a 2 ; a-^ ' ; a 9 ' ) = exp(-^aRa'), (3-17) where R i : L(0) R 1 2(k) R l x ( r ) R 1 2(k+r) R = R 1 2(k) R 2 2(0) R 1 2 ( k - r ) R 2 2 ( r ) (3.18) R i : L(r) R 1 2 ( k - r ) R 1 1(0) R 1 2(k) R 1 2(k+r) R 2 2 ( r ) R 1 2(k) R 2 2(0) 31 and a = ' ' J , a ' i s the transpose of a . (3-19) The c h a r a c t e r i s t i c f u n c t i o n of the quantized s i g n a l s x j _ q ' x 2 q ' x-. ' and x~ 1 i s l q 2q M fa - a - a ' - a 1 ) -<LLLLe 1 2 1 2 • M ( a -— • a -2j^-q 1' 2' 1 '2 J - s t u v U al Ax ' ° ^ A - ' 1 2 Ax 2 a l Ax 1' "2 "Ax 2 i 2TTV \ s i n | ( a 1 A x 1 - 2 i t s ) s i n | ( a 2 A x 2 - 2 ^ t ) ^ ( a^Ax-^-2rts) — 2 ( a 2 A x 2 - 2 ^ t ) s i n ICax'Ax^acu) g i n |(« • A x ^ c v ) | ( a 1 ' A x 1 - 2 i t u ) ^ ( a 2 ' Ax 2 - 2 J t v ) (3-20) S u b s t i t u t i n g Eq. (3-17) i n t o Eq. (3.20) and d i f f e r e n t i a t i n g Eq. . (3.20) w i t h respect to a ^ , a 2 , ' and a 2 ' at the o r i g i n , we obtain the 4th-order moment of the quantized Gaussian s i g n a l s as f o l l o w s . E Jx., _.x^ ,..x., 'x. L l q A 2 q ^ l q * 2 q F(k;r) = F Q + F-, + F Q + F^ + F^ , 1 3 (3.21) where F Q = R i : L ( r ) R 2 2 ( r ) + R 1 2(k) + R 1 2(k+r)R 1 2(k-r) , e i ^ h ^ ^ M R ^ M R ^ r ) ^ ) 2 ] exp - \ ^ Y s 1 1 + 3 s i m i l a r terms, s * 4 , 2 s t 1 2 < ' ,M(- 2jts. Ax x' girt "Ax^ ; 0; 0) + 5 s i m i l a r terms, p = ^ ' ^ ' ^ , e u 2 K ( s A 1 + t A 2 + u A 1 ) s+t+u. Ax 2Ax 2 s t u •5 8it s t u 32 1 1 M( 2JTS 2:tt 2jtu Ax-^' A x 2 ' Ax, ; 0) + 3 s i m i l a r terms, p _ ^ , ^ ' ^ ' ^ , e 3 2 j t ( s A 1 + t A 2 + u A 1 + v A 2 ' ) ^ ^  s, s+t+u+v _ A x 2 A x 2 s t u v I63t^stuv M(- 2 l£S. _ 2 j t t . _ 2 j t u . _2jtv Ax-^ ~ A x 2 ' _ A X l ' A x 2 ) S u b s t i t u t i n g Eq. (3.21) i n t o Eq. ( 3 .16) y i e l d s N-l Var[ci2(k;N)J= + ^ ^ ( N - r ) F ( k ; r ) - |E [ C i 2 (k;N)]J This variance can al s o be w r i t t e n i n the f o l l o w i n g form: ( 3 . 2 2 ) Var[ci2(k;N)J = e 2(k;N) + E (k;N), ( 3 - 2 3 ) where e (k;N) i s the mean-square e r r o r of the sampled-data d i r e c t c c o r r e l a t o r given by Eq. ( 3 . 1 1 a ) and E (k;N) i s ' N ^ E q(k;N). = ^ ' ^ O ^ X] ( N - r ) E ' ( k ; r ) + R 2 2 ( k ) - | E [ c i 2 ( k ; N ) ] | 2 , ( 3 . 2 4 ) where F'(k;r). = P 1 + F 2 + F^ + F 4. E^(k;N) may be considered as an increase i n sampling e r r o r due to q u a n t i z a t i o n . Prom Eqs. ( 2 . 9 ) and ( 3 - 4 ) we f i n d that the bias e r r o r of the d i g i t a l c o r r e l a t o r i s c Bq = { E [ X 1 * 2 ] + E [ X 2 ^ l ] + E [ ^ 2 ] } 2 ' The dependence of t h i s b i a s e r r o r on the input s t a t i s t i c s and the quantizer c h a r a c t e r i s t i c s i s given i n Eq. ( 2 . 1 5 ) . For Gaussian processes w i t h standard d e v i a t i o n s (T ^  and or we have ( 3 - 2 5 ) (CO CO B = 4 f 2 r 2 r 2 E e J 2 r t m A l e x P ( - 2 ^ 2 m 2 / A 2 ) + £ ] e ^ m A 2 e x P ( - 2 t t 2 n 2 / A 2 ) ^ lm=l n=l 3 3 C O o o + 2 l E e ^ 2 ! t ( m A l + n A 2 ) e x p ^ U ^ A ^ / A 2 ) ] s i n h ( 4 ^ m n / A ^ )  m = 1 n = 1 4 T t 2 p m n / A 1 A 2 ( 3 - 2 6 ) where A-^  = Ax^/cr ^ and A^ = Ax^/(T 2 and p = R 1 2(k)/CT 1 (T 2. In the case that A-^  and A 2 are s m a l l , the bias e r r o r B q i s a l s o small and can be neglected. However, when A^ and A 2 increase, B q increases r a p i d l y . Although the variance given by Eq. ( 3 . 2 2 ) may decrease when the t o t a l number of samples N i s increased, the bias e r r o r i s a constant value which i s independent of the number of samples taken. The mean-square e r r o r cannot be reduced to zero even when the number of samples taken approaches i n f i n i t y . Therefore the d i g i t a l c o r r e l a t o r i s not a c o n s i s t e n t estimator. 3 . 4 The Mean-Square E r r o r of the Modified D i g i t a l C o r r e l a t o r  Using Continuous A u x i l i a r y Noise 3 . 4 . I White A u x i l i a r y Noise Since the output of the modified d i g i t a l c o r r e l a t o r u s i n g continuous a u x i l i a r y noise i s unbiased, the bias e r r o r term i s zero and the mean-square e r r o r i s equal to the variance. From Eqs. ( 2 . 1 9 ) and ( 3 - 3 ) , we have N-l N-l <(k;N) = g Ig E [ y i q ( - ) y 2 q ( ^ ) y l q ( n ) y 2 q ( n + k ) ] - R 2 2 ( k ) . ( 3 . 2 7 ) The 4 t h-order moment can be found from the d e r i v a t i v e of the j o i n t c h a r a c t e r i s t i c f u n c t i o n , M y q ( a ^ ; ; a ^ ; a^) , of y ^ W > y 2 q ( m + k ) > y^ q(n) and y 2 q(n+k) wi t h rexpect to ct^, a^, and at the o r i g i n . However, M (cc, ; cx0; a'; a') and M (cc, ; cc;a'; cx') , the j o i n t yq x d. x d y J . <L x d c h a r a c t e r i s t i c f u n c t i o n of the unquantized s i g n a l s y^(m), y 2(m+k), y-^(n) and y (n+k), have the f o l l o w i n g r e l a t i o n : y q v 1 ' 2 ' 1 ' 2J l^^L^L-^ y . •r i ^ 2*t , 25U 2JTV) s i n f ^ A x ^ s ) s i n §( c t g A x ^ t ) a2~Ax.' a l A X - L ' a 2 Ax 2 | ( a 1 A x 1-2 1 c s ) . § ( a 2 A x 2 - 2 * t ) s i n | K A x l - 2 * u ) s i n | ( « 2 A X 2 - 2 J T V ) |(a-[Ax 1 -2iru) |(a 2Ax^ - 2 J t v ) . ( 3 - 2 8 ) I f the added a u x i l i a r y noises a-^(t) and a 2 ( t ) s a t i s f y i n g the con d i t i o n s given by Eqs. ( 2 . 3 0 ) are such that a-^m) i s independent of a-^(n) and a 2(m) of a 2(n) f o r a l l m^n, then we have M y ( a i ; a 2 ; a i ; a 2 ) = M( a±; ^ ; oc| ; a ' ) M ^ ) M ^ o c J M ^ o * ) M ^ a ' ) , ( 3 . 2 9 ) where M(a^; a 2 ; cc£; ccp i s the j o i n t c h a r a c t e r i s t i c f u n c t i o n of x-^(rn), x 2(m+k), x^(n) and x 2(n+k). S u b s t i t u t i n g Eq. ( 3 - 2 9 ) i n t o Eq. ( 3 . 2 8 ) and then d i f f e r e n t i a t i n g w i t h respect to cc^, cc,, cc| and at the o r i g i n , we have, using Eqs. ( 2 . 3 0 ) , E [ y l q ^ m ^ y 2 q ^ m + k ^ y l q ^ n ^ y 2 q ^ n + k ^ ] = E [ XT_ ( m ) x 2 ^ m + k ^ x i ( n ^ x 2 ^ n + k ^ ] ' f o r m^n. ( 3 . 3 0 ) Therefore the mean-square e r r o r of the modified d i g i t a l c o r r e l a t o r i s r 9 o - i r o 9 1 N-l N-l e 2(k;N) , E [ Y L ( Q ) y 2 a ( k j - E [ x l ( ° ) x ^ k ) ] + hTY N m=0 n=0 E i^x1(m)x2(m+k)x1(n)x2(n+k)J- R 2 2 ( k ) . ( 3 - 3 D 35 The l a s t two terms are i d e n t i f i e d as the mean-square e r r o r of the conventional sampled-d'ata d i r e c t c o r r e l a t o r , i n which no a u x i l i a r y noise or q u a n t i z a t i o n i s employed. Denoting t h i s by e^(k;N) as i n Eq. ( 3 - 9 a ) , we have H^) = E [ y i a ( Q ) 4 ( k ) ] - s [ * i ( 0 ) * 2 ( k ) ] 7(^0 ( 3 - 3 2 ) c £ m - + c Eq. ( 3 . 3 2 ) shows that the mean-square e r r o r of the modified d i g i t a l c o r r e l a t o r d i f f e r s from that of the conventional d i r e c t c o r r e l a t o r only by a term which i s i n v e r s e l y p r o p o r t i o n a l to the number of samples taken. This increase i n e r r o r may be explained as the combined r e s u l t s of q u a n t i z i n g , sampling and adding a u x i l i a r y n o i s e . Because the d i r e c t c o r r e l a t o r i s a c o n s i s t e n t estimator as has been shown i n Section 2 . 1 , and the increa.sed e r r o r term i s i n v e r s e l y p r o p o r t i o n a l to N, we have N i £ e 2(k;tf) = 0 . ( 3 - 3 3 ) Therefore, the modified d i g i t a l c o r r e l a t o r i s a c o n s i s t e n t estimator too. I t should be noted that the increase i n e r r o r does not have to be appreciable. By i n c r e a s i n g the sampling r a t e , w i t h -out i n c r e a s i n g the t o t a l observation time, the mean-square e r r o r of the d i r e c t c o r r e l a t o r w i l l approach a constant value, while the e x t r a term w i l l become so small that i t may be neglected. The continuous measurement may be considered as a l i m i t i n g case, i n which the sampling rate approaches i n f i n i t y . This w i l l be seen i n the f o l l o w i n g . Assume that the t o t a l observation time T-NAt i s f i x e d . By i n c r e a s i n g the t o t a l number of samples N, the time i n t e r v a l between consecutive samples, At, decreases r e l a t i v e l y . Expressing Eq. ( 3 . 3 1 ) i n terms of T and At and then l e t t i n g At approach zero, we obtain the mean-square error for continuous measurement A t ^ ° 1 A t 0 1 mAt=0 nAt E [xn (mAt)x„(mAt+kAt)x1 (nAt)x„(nAt+kAt)1AtAt - lim R^L (kAt) L 1 ^ -1 ^ -1 At-*0 = 2 I E j x ^ t ^ t t + T O x - ^ t O x ^ t ' + TOjdtdt' _ R^ 2 (r ) = e 2(T;T), ( 3 - 3 4 ) where f - kAt. Therefore, i n the l i m i t i n g case of continuous measurement, the mean-square error of the modified d i g i t a l correlator i s equal to that of the di r e c t analogue correlator. In other words, the errors r e s u l t i n g from quantization and a u x i l i a r y noise w i l l com-plet e l y vanish i f continuous measurement i s used. However, this i s true only under the assumption that a-^(t) and a 2 ( t ) are white noise; that i s , a-^(t) i s independent of a-^(t') and a 2 ( t ) of a 0 ( V for a l l t / t ' ; otherwise, the corr e l a t i o n among noise samples w i l l contribute additional errors. This w i l l be considered l a t e r . Nevertheless, Eq. ( 3 - 3 4 ) does suggest that, by increasing the sampling rate, the errors caused by quantizing, sampling and adding a u x i l i a r y noise can be reduced to a negli g i b l e value, provided that the spectrum of the a u x i l i a r y noise i s wide enough. The sampling rate of a d i g i t a l device i s usually constrained by the dynamics of the components and cannot be increased without l i m i t . With fixed sampling rate, the error of the modified d i g i t a l correlator can be further decreased by 37 f i n e r q u a n t i z a t i o n . This decrease i n e r r o r i s due to two e f f e c t s ; f i r s t , the f i n e r the q u a n t i z a t i o n , the smaller the q u a n t i z a t i o n noise, second, the variance of the a u x i l i a r y noise i s smaller f o r smaller q u a n t i z a t i o n step s i z e . In the extreme case that the q u a n t i z a t i o n step s i z e s Ax.^  and Ax^ approach zero, no a u x i l i a r y noise i s necessary and the input s i g n a l s are prac-t i c a l l y unquantized and uncontaminated. Thus we have (3-35) E [ y l q ( 0 ) y 2 q ( k ) ] = E [ * i ( 0 ) x 2 ( k ) " and e m 2(k;N) = £ c 2(k;N) ( 3 .36 ) To see i n more d e t a i l how the q u a n t i z a t i o n step s i z e a f f e c t s the mean-square e r r o r , l e t us define the d i f f e r e n c e i n e r r o r s of the modified d i g i t a l and the d i r e c t c o r r e l a t o r s "by D e 2(k;N) - e 2(k;N). (3-37) I t f o l l o w s d i r e c t l y from Eq. (3-32) that D = E [ria ( o>rio<*>1 - B [ * f o ) x j ( k ) ] (3-38) N 2 2 D i f f e r e n t i a t i n g Eq. ( 2 .26 ) w i t h respect to and at the o r i g i n and using Eqs. ( 2 . 3 0 ) , we f i n d t h a t , f o r r e c t a n g u l a r l y d i s t r i b u t e d n o i s e , the d i f f e r e n c e i n e r r o r s i s , f Ax 2 IT 2 Ax 2 ( r ; 2 Ax 2 x 2 V - 1' -o n A Ax 2 D = U 1 2 +-V1-+ 1 2 -+ L e^kAl 6 • 3 6 k 2 * 2 k 2 B2M(-2ark/Ax:i ;c<2) Ax, M(-23tk/A X l;0) a 2 =0 X E 1 j2itJlA 2 Ax 2 e 2, 2JL 2 3^M( a i;-27cJl/Ax 2) 2 a. 1 Ax ~ - M (0;-2jre/Ax 2) i U A x ^ -^q) •}. e^ k A l + *V oti = 0 ( 3 . 39 ) 38 In terms of the input probability-density functions, this leads, for A 1 = :A 2=l/2 or quantization without a n u l l zone, to 2 2 A x 2 A x 2 ^ f ( m + l / 2 ) A X l 1" "2 n 16 4 p(n+l/2)Ax 2 (n-l/2)Ax m (m-l/2)Ax 1 2 2 Ax,Ax„ P(x 1) (m -2mx 1/Ax 1)dx 1 - — P ( x 2 ) (n 2-2nx 2/Ax 2)dx 2 + Ax 2Ax 2^^ : 2 m n./ •(m+l/2) Ax x (m-l/2)Ax1, /.(n+l/2) Ax, (n-l/2)Ax, p 6 r 2 P(x 1;x 2) (m -2mx 1/Ax- L) (n - 2 n x 2 / A x 2 ) d x 1 d x 2 - E ^ .zation • Km+l) Ax (3.40a) and, for A-^=A2=0 or quantizati with a n u l l zone, to D Ax 1Ax R 2 ( k ) - A x 2 A x 2 1 mAx " A x l A x 2 Z K n+l) Ax, nAx, 1 (m -2mx-L/Ax-L+m; r x 2P(x- L ;x 2)dx 2dx 1 (n -2nx2/Ax +n) 2 2 x^P(x-L ; x 2) dx-Ldx2+Ax-LAx2 • K m+1) Ax-j^  r (n+l) Ax 2 I (m2-2mx1/Ax1+m) (n^-2nx 2/Ax 2+n)dx 1dx 2 -m n«/mAx- ~ A" E .2 2 R 1 X 2 '1 nAx, (3.40b) where x^=x^(0) and x 2=x 2(k) .This difference i n errors has been calculated for Gaussian processes and sketched i n Figures 3.1 and 3-2. Por simp l i c i t y , i t has been assumed that the quantizer i n both channels has. the same normalized step sizes; that i s , A, A, 1 ~ 2 where A-^ and A 2 are normalized step sizes defined by and A 2 = Ax 2/ ( T 2 . A-L = A x 1 / CT ± It i s noted that the difference i n error due to quantizing, (3.41) (3-42) sampling and adding a u x i l i a r y noise r i s e s rapidly with increasing quantization step'size. The value of correlation c o e f f i c i e n t , ^ , F i g . 3.1 The d i f f e r e n c e of the mean-square e r r o r s of the modified d i g i t a l and the d i r e c t c o r r e l a t o r vs. the q u a n t i z a t i o n s t e p - s i z e f o r q u a n t i z a t i o n w i t h a n u l l - z o n e . 4 0 c o = 0 . 6 \ = A 2 = 1/2 0 1 2 3 4 5 A F i g . 3.2 The d i f f e r e n c e of the mean-square e r r o r s of the modified d i g i t a l and the d i r e c t c o r r e l a t o r vs. the q u a n t i z a t i o n s t e p - s i z e f o r q u a n t i z a t i o n without a n u l l - z o n e . has l i t t l e e f f e c t on the e r r o r . I t i s i n t e r e s t i n g to note t h a t , f o r q u a n t i z a t i o n without a n u l l zone, the e r r o r f o r l a r g e r cor-r e l a t i o n i s always l e s s than that f o r smaller c o r r e l a t i o n , w h i l e , f o r q u a n t i z a t i o n w i t h a n u l l zone, the reverse i s t r u e . Since the Gaussian process i s unbounded, i t i s r e q u i r e d , t h e o r e t i c a l l y , that the quantizer have an i n f i n i t e number of q u a n t i z a t i o n l e v e l s f o r the output of the c o r r e l a t o r to be unbiased. A l l the above analyses have been based on t h i s assump-t i o n . In p r a c t i c e , however, the processing equipment a u t o m a t i c a l l y l i m i t s the amplitude of an unbounded process. A bias e r r o r thus occurs because of t h i s amplitude l i m i t a t i o n . I f , however, the l i m i t i n g range i s l a r g e enough, the bias e r r o r may be neglected. For Gaussian processes, i t has been found that the e r r o r due to amplitude l i m i t a t i o n i s n e g l i g i b l e i f the l i m i t i n g range i s not l e s s than three standard d e v i a t i o n s . By l i m i t i n g the amplitude of an unbounded process, we may use a f i n i t e number of q u a n t i z a t i o n l e v e l s . Assume that the amplitude i s bounded w i t h i n [-C,C], where C = = i s normalized by C and 0 ^ • Then the smallest number of l e v e l s r e q u i r e d i s L = [2C/A] + 1, (3-43) where [2C/A "j denotes the smallest i n t e g e r of those l a r g e r than or equal to..2C/A. On the other hand, i f L l e v e l s are to be used to process the combined input s i g n a l and n o i s e , the step s i z e i s A = 20/(1-1 ) . (3.44) For example, a two - l e v e l or p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r has A = 20 and a t h r e e - l e v e l c o r r e l a t o r has A = C. Therefore, i f C i s known, the step s i z e can be determined by Eq. (3.44) f o r 42 various L. In order to compare the mean-square e r r o r s of c o r r e l a t o r s u s i n g various numbers of l e v e l s , we consider a s p e c i a l case i n which e (k;N) can be found e a s i l y . We assume that x-, (t) and C -L x ^ ( t ) are s t a t i s t i c a l l y independent and that they are sampled i n such a way that a l l samples are unc o r r e l a t e d , i . e . , E [ x 1 ( m ) x 1 ( n ) ] = E p2 (m)x 2 (n) J = 0, f o r a l l m^n. Then we have — 5 N-l N-l C(k;N) = ^ 21! 2Z E [x (m)x (n)l • E fx(m+k)x (n+k)] N m=0 n=0 L J L J = c r i .^ 2/N. (3-45) Adding t h i s to the e r r o r d i f f e r e n c e s shown i n Figures 3.1 and 3.2 f o r p =0 gives the mean-square e r r o r f o r various A's, and hence L's, i f C i s known. .For C-3, the r e l a t i v e mean-square e r r o r , z m/ z c> ^ 0 T coarse q u a n t i z a t i o n i s tabulated i n the f o l l o w i n g . I 2 3 4 - 5 6 7 8 . < . 16 . . . . co 2/ 2 £ /£ m' c 72.23 5.75 2.75 1.89 1.53 1-36 1.23 ... 1.054 ••• 1 I t i s noted that a small increase i n the number of q u a n t i z a t i o n l e v e l s reduces the e r r o r sharply. The mean-square e r r o r f o r L=2, f o r example, i s 26 times that f o r L=4 and 53 times that f o r L=7. In other words, i f the p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r i s to have the same mean-square e r r o r , i t must take at l e a s t 26 times as many samples as the 4 - l e v e l c o r r e l a t o r and 53 times as many as the 7 - l e v e l c o r r e l a t o r . 4 3 3 . 4.2 Non-White A u x i l i a r y Noise The samples of the a u x i l i a r y noise have been assumed to be independent of each other i n the above a n a l y s i s . Thus the r e s u l t given by Eq. (3-32) a p p l i e s only to the case that the a u x i l i a r y noise i s white or that i t has a very wide fl a t -power spectrum. Since not a l l a u x i l i a r y noise s a t i s f i e s t h i s c o n d i t i o n , we consider now the e f f e c t of c o r r e l a t e d samples on the mean-square e r r o r of the c o r r e l a t o r . To f i n d the mean-square e r r o r , the same method as i n the d e r i v a t i o n of Eq. ( 3 . 3 1 ) can be followed. Eqs. (3.27) and (3.28) are s t i l l v a l i d i n t h i s case. However, because the noise samples are not independent of each other, the j o i n t c h a r a c t e r i s t i c f u n c t i o n of the unquantized s i g n a l s i s M y ( a 1 ; a 2 ; a : | _ ; a 2 ) = M( ; a 2 ; aj_; a p M ^ C a ^ M ^ C « 2 ; , ( 3 - 4 6 ) where M a^(a^;cc|) a n c^ ^ a 2 ^ a 2 ' a ; P 3 X 6 J°^ n^ c h a r a c t e r i s t i c f u n c t i o n s of a-^ (m) and a-^(n), and a2(m+k) and a 2(n+k), r e s p e c t i v e l y . S u b s t i t u t i n g Eq. ( 3 . 4 6 ) i n t o Eq. (3.28) and then d i f f e r e n t i a t i n g w i t h respect to ct^, cc,-,, cc| and at the o r i g i n , we obtain E [ y l q W l q y 2 q ] = E [ x l x 2 X i X 2 ] + F l l + P 2 2 + P12> " ^ - 4 7 ) where y l q = y l q ( m ) , y 2 q = y 2 q ( m + k ) , y l q = y l q ( n ) , y 2 q = y 2 q ( n + k ) , and x^=x^(m), x 2=x 2(m+k), x-^=x^(n), x 2=x 2(n+k), and F u =EEe s u j2rt(s+u)A 1 c > M / 2JCS 2:tu , \ •^(a. Ax,-2TCS) 1 (a' Ax, - 2 i t u ) M ( _2jts , 2jtus s i n 2 1 1 '-'"'KJ/ si n 2^"1"^1 1 a l V a l Ax n ' al~Ax-! ; 1 1 ^( <X-^L\X-^-2KS) 2 i(a^Ax^ - 2 i c u ^ a ^ a ^ O •P y ny i_j2 I t(t+v)A 2 _j) : M(a n ; a' • '.TtV 1' ^Ax 2' " l , _ A x ° 2 a2 V 2 Ax 2 0 . ^(a,-,Ax_- 2Jtt) . ^-(a'AX 0-2 J I V ) , 2jtV\ s i n 2 2 2 s m 2 2 2 aA—A i '" '" " 2 Ax, (a 0Ax 0-2jct) i k a ' Ax 0-2atv) 1 2 V"2" A2 2 X 2 2 a^=a 2=a^=0^ =0 P = ^ y ^ ^ e j 2 3 t ( s A l + t A 2 + u A l + v A 2 ) M(-1 2 s U V a 2 2jts . _2_ji't t _ 2itu. _2JTV A x 1 ; Ax 2' A x 1 ; Ax 2 1 1 M ( a 2jrs. 2J£U\ s i n 2 ( a l A x l ~ 2 j T S } s i n 2 ( 4 A x I ~ 2 j t u ) a l a l A x 1 » a l Axj_ I(a nAx,-2^s) |( ajAx-^ttu) ~b a 2 ^ a 2 2 ' " a 1 1 M („ 2att. , 2JTVN s i n 2 V 2 2 a 2 V a 2 Ax ' a2 Ax J (a 2Ax 2-2xi;t) 2 ( a 2 A x 2 -. ^(a'Ax-2^v)' s m 2 2 2 2 ^(a 0Ax 0 2rct) ^ ( a ^ A x ^ j e v ) a 1=a 2=a^ Note that F - Q ' B22 a n d "^ 12 ^ e P e n ( ^ i m p l i c i t l y on k, m and n. S u b s t i t u t i n g Eq. (3-47) i n t o Eq. (3-27), we have N-l N - l lirm=0 n=0 m/n (3-48) or e m(k;N) = " L y l q y 2 q N-l N - l + 1 N ( - F l l + F 2 2 + P 1 2 ) + e c ( k ; N ) * N m=0 n=0 m/n (3.49) Comparing Eq. (3-49) w i t h Eq. (3-32), we f i n d t h a t , i f the a u x i l i a r y noise samples taken are not independent of each other, an a d d i t i o n a l e r r o r w i l l r e s u l t . This e r r o r does not j u s t depend on the c o r r e l a t i o n among noise samples, but ra t h e r on the c h a r a c t e r i s t i c f u n c t i o n s of the added a u x i l i a r y noises and the input s i g n a l s . 45 3 . 5 The Mean-Square E r r o r of the Modified D i g i t a l C o r r e l a t o r  Using D i s c r e t e A u x i l i a r y Noise The mean-square e r r o r of the modified d i g i t a l c o r r e l a t o r using d i s c r e t e a u x i l i a r y noise i s e 2(k;N) = Var [c i 2(k;N)] + B m > ! N - l N - l where Var [ci2(k;N>] = ^ g g E [ y l q y 2 q y i q y 2 q m=0 n=0 - E y l q y 2 q (3.50) ' 2 and B m j E[ ylq y 2 q ] - V k > } 2 ' (3-51) (3.52) (3.53) I t has been shown i n Section 2 . 3 * 2 that M = E [ X l < J X 2 q ] ' where x^ q and x 2 q are quantized versions of x^ and x 2 w i t h new q u a n t i z a t i o n step s i z e s Ax^/Q^ and Ax 2/Q 2 r e s p e c t i v e l y . Using the same method as i n the d e r i v a t i o n of Eq. ( 2 . 5 1 ) , i t can be shown that the 4 t h-order moment of y- q^ and y 2 q i s E [ y l q y 2 q y i q y 2 q ] = E [ X l q X 2 q X i q X 2 q ] ' . ^  ' ( 5 ' 5 4 ) provided that the a u x i l i a r y noise b-^ (m) i s independent of b-^(n) and b 2(m) of bg(n) f o r a l l m/n. S u b s t i t u t i n g Eqs. ( 3 . 5 3 ) and ( 3 . 5 4 ) i n Eqs. ( 3 - 5 2 ) and ( 3 . 5 1 ) , we have [ 2 2 1 f 2 2 1 N-l N-l L ± z . -j y l q y 2 q J - E L x l a X 2 q J + l j>~" V " " E N m=0 n=0 X l q X 2 q X l q X 2 q and B = m  {EKX2qJ " R 1 2 ( k ) j : - H 1 2(k) Therefore the mean-square e r r o r i s = E [ y l q ^ o ] - E [ X l q 2 x 2 q ] ( 3 - 5 5 ) ( 3 . 5 6 ) e (k;N) N s 2 ( k ; N ) , ( 3 - 5 7 ) where (k;N) i s the mean-square e r r o r of the d i g i t a l c o r r e l a t o r w i t h q u a n t i z a t i o n step s i z e s Ax-^ /Q-^  and Ax^/Q^. I t i s noted that t h i s e r r o r i s very s i m i l a r to that of the modified d i g i t a l c o r r e l a t o r using continuous noise.given by Eq. (3-32). However, i n the extreme case that an i n f i n i t e number of samples are taken or that continuous measurement i s employed, the mean-square e r r o r approaches that of the d i g i t a l c o r r e l a t o r with, q u a n t i z a t i o n step s i z e s Ax-^ /Q-^  and Ax^/Q^ instead of that of the d i r e c t c o r r e l a t o r . I f the power spectrum of the a u x i l i a r y noise i s not wide enough that noise samples are unc o r r e l a t e d , an a d d i t i o n a l e r r o r w i l l be induced. In t h i s case, an expression s i m i l a r to Eq. (3'49) can be deri v e d . 3.6 The Mean-Square E r r o r of the S t i e l t j e s C o r r e l a t o r From Eqs. (2.52) and (3-2) we have the mean-square e r r o r of the S t i e l t j e s c o r r e l a t o r as (3-58) (3.59) (3.60) As i n Section 3«3> i t can be shown that the 4th-order moment f o r j o i n t Gaussian processes i s E [ X l q X 2 X l q X 2 J = P ( k ' r ) = F 0 ( k ; r ) + V k ; r ) + F 2 ( k ; r ) ' (3-61) 47 where P 0 ( k ; r ) = R 1 1 ( r ) R 2 2 ( r ) + R i 2 ( k ) + R 1 2 ( K + R ) R 1 2 ( K _ R } ' F1(k;r) =5Zej27tsAl R ^ r ^ C k ) ^ 2(k+r) ( | ~ ) 2 ( - l ) exp exp 1 - § < f ? ) 2 R l l ( 0 ) l H ^ 2 " 4 ! H l l ( r ) E l 2 ( k ) R 1 2 ( k - r ) ( 2 f f i ) 2 ( - l ) -¥1?/ E u ( 0 ) P 2 ( k ; r ) ^ ^ ^ e J Z t t s + u j A i ( _ l ) S + u ^ ( r i + u B ^ k - r ) ] . s u . ( S R 1 2 ( k + r ) + u R 1 2 ( k ) ] M(-ga ; 0; 0) . Therefore, Var [C 1 2(k;N)J = £ f e O J + | y ^ ( N - r )E(k;r) - E [ x i q X 2 ] ^ (3.62) S u b s t i t u t i n g Eqs. (3-62) and (3.60) i n t o Eq. ( 3 . 5 8 ) , we obtain £2(k;N) = F 1 ( k ; 0 ) + E 2 ( k ; 0 ) y ^ ( N _ r ) r F ( k ; r ) + F ( k ; r ) ] r = l - 2 R 1 2 ( k ) E [ q 1 x ' 2 J + e 2(k;W). The f i r s t three terms on the right-hand side of Eq. ( 3 - 6 3 ) denote the increase i n e r r o r due to q u a n t i z a t i o n of x-^(t). I t i s obvious that t h i s " e r r o r , as compared w i t h Eq. ( 3 . 2 3 ) > i s much l e s s than the e r r o r of the d i g i t a l c o r r e l a t o r . 3 • 7 The Mean-Square E r r o r of the Modified S t i e t l . j e s C o r r e l a t o r Because the output of the modified S t i e l t j e s c o r r e l a t o r i s unbiased, the mean-square e r r o r i s 4 8 _ -, N - l N ^ l n o 4 ( k j N ) = h Y. X. E [ y l q ( m ) x 2 ( m - , - k ) y l q ( n ) x 2 ( n + k J ] " R 1 2 ( k ) ' ( 5 ' 6 4 ) m=0 n=0 I f the a u x i l i a r y noise a-^(t) i s such that a-^ (m) i s independent of a-^(n) f o r a l l m/n, then i t can "be shown, as i n Section 3 . 4 , that E |ylq(m)x2(m+k)y-Lq(n)x2(n+k)J = E ^ ( m ) x 2 (m+k)x 1 (n)x^ (n+k)J , f o r m / n. ( 3 - 6 5 ) S u b s t i t u t i n g Eq. ( 3 . 6 5 ) i n t o Eq. ( 3 . 6 4 ) y i e l d s ^ " ^ ) = E [ y 2 a ( 0 ) x 2 ( k ) ] - E[x 2 ( 0)x 2 ( k ) ] ^ . M S N + N 2 Z _ , m=0 n=0 E[x 1(m)x 2(m+k)x 2(n)x 2(n+k)] - R 2 2 (k) , ( 3 - 6 6 ) ~2 /, ATN E [ y 2 ( 0 ) v 2 ( k ) l - E fx 2 ( o)x 2 ( k ) l ~x or 49 4 . IMPLEMENTATION OF THE MODIFIED DIGITAL CORRELATOR I t has been shown that the mean-square e r r o r of the modified d i g i t a l c o r r e l a t o r can be decreased by i n c r e a s i n g the sampling r a t e , by t a k i n g a l a r g e r number of samples, or by using a quantizer w i t h more q u a n t i z a t i o n l e v e l s . Sampling ra t e i s l i m i t e d by the dynamics of the components, and a higher sampling r a t e increases the e r r o r due to c o r r e l a t e d a u x i l i a r y noise samples. Taking a l a r g e r number of samples needs long computation time, which may a f f e c t the v a l i d i t y of the assump-t i o n of s t a t i o n a r i t y of the input random process. Moreover, a r e a l - t i m e d i s p l a y r e q u i r e s that the computation time be as short as p o s s i b l e . Therefore, i f high accuracy i s d e s i r e d , the best way i s to Increase the number of q u a n t i z a t i o n l e v e l s of the quantizer i n each channel. In f a c t , we have seen i n the l a s t chapter that a small increase i n the number of quantiza-t i o n l e v e l s decreases the mean-square e r r o r g r e a t l y . A d o u b l e - s h i f t - r e g i s t e r p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r i s designed and being b u i l t at U.B.C. I t i s a very simple and e f f i c i e n t device capable of computing c o r r e l a t i o n and some other s t a t i s t i c a l f u n c t i o n s . I t w i l l be shown i n t h i s part of the t h e s i s that a m u l t i - l e v e l m o d i f i e d - d i g i t a l c o r r e l a t o r can a l s o be b u i l t i n -a s i m i l a r way without a f f e c t i n g the e f f i c i e n c y very much. The use of pseudo-random noise as a u x i l i a r y noise i s a l s o considered. 4•1 The Double-Shift-Register P o l a r i t y - C o i n c i d e n c e C o r r e l a t o r The d o u b l e - s h i f t - r e g i s t e r p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r being b u i l t at U.B.C. i s shown i n Figure 4.1. This i s b a s i c a l l y 50 SRI x 1 ( t ) Jomparator — ^ A 128 B 128 SR2 x 2 ( t ) C ompar a t o: -— h*" i D 1 P . C . C E 128 *" Coin. Counter T 18-bit 128-word Memory E i g . 4.1 D o u b l e - s h i f t - r e g i s t e r p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r ( 9 ) an improved v e r s i o n of Turner's c o r r e l a t o r . By using s h i f t r e g i s t e r s i n both channels, the c o r r e l a t o r can operate -equally w e l l f o r both high and low sampling frequencies, because the samples are f i r s t stored before they are manipulated. The c o r r e l a t o r a l s o has many other advantages; f o r example, i t can operate i n the b i p o l a r mode, i n which the c o r r e l a t i o n i s d i s p l a y e d on both sides of the T =0 a x i s , as i s u s u a l l y required f o r c r o s s c o r r e l a t i o n . The theory of the modified p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r has been described i n Section 2.3.1. In Figure 4.1, each of the input s i g n a l s x-^(t) and x 2 ( t ) i s compared w i t h the corresponding a u x i l i a r y noise a-^(t) or a 2 ( t ) i n a comparator. Each comparator output has two p o s s i b l e s t a t e s corresponding to the signs of (x^-a-j ) or ( x 2 ~ a 2 ) . Each output i s then sampled p e r i o d i c a l l y , the period being determined e x t e r n a l l y on the basis of the c h a r a c t e r i s t i c s of the input s i g n a l s , and the results are stored i n s h i f t registers SRI and SR2 for com-puting. Each of these s h i f t registers has 256 stages; SRI consists of two 128-bit s h i f t registers A and B, and SR2 consists of two 64-bit registers C and B and another 128-bit re g i s t e r E. When the correlator i s i n the normal operating mode, the samples are fed to the s h i f t registers at the l e f t ends of A and C. At the beginning 256 samples have to be taken to f i l l up SRI and SR2. As soon as SRI and SR2 are f i l l e d up, the computing cycle i s i n i t i a t e d . The•computing cycle i s composed of two basic opera-tions, that i s , , a ring-and-compare operation and a s h i f t operation. By trig g e r i n g B and E with a r i n g toggle simul-taneously, B and E being closed on themselves as r i n g s h i f t -r e g i s t e r s , and then comparing the f i r s t (or l a s t ) f l i p -f l o p i n the polarity-coincidence c i r c u i t (P.C.C,) after the ri n g toggle, an output i s obtained from the P.C.C. Repeating the ring-and-compare operation 128 times and accumulating the outputs of the P.C.C. i n the coincidence counter, we obtain a word increment which corresponds to a correlation estimate from 128 samples for T =0. At the end of the 128th r i n g -and-compare operation, a l l contents of B and E are restored to t h e i r o r i g i n a l positions. The contents i n SRI ( i . e . A and B) are then shifted one place to the right , the l a s t d i g i t i n A being moved to the f i r s t f l i p - f l o p of B while the l a s t d i g i t i n B i s discarded. The time displacement between the contents of SRI and SR2 i s now L\T instead of 0, where A T i s the period between samples. In the meantime a l l contents of the coi n c i d e n c e counter and of the memory are/ v e r t i c a l l y s h i f t e d down one p l a c e , while the l a s t word i s brought i n t o the c o i n c i d e n c e counter. This f i n i s h e s a s h i f t o p e r a t i o n . As soon as the s h i f t o p e r a t i o n has been completed, B and E are r i n g e d and compared 128 times again to update the word which has j u s t been brought i n t o the coi n c i d e n c e counter. Another s h i f t o p e r a t i o n i s then c a r r i e d out. These r i n g -and-compare and s h i f t operations s e q u e n t i a l l y repeat u n t i l the e n t i r e contents of A have been s h i f t e d i n t o B, which com-p l e t e s a computing c y c l e . Thus, at the end of the computing c y c l e , each of the 128 words i n memory has been updated on the b a s i s of 128 new samples and r e s t o r e d to i t s o r i g i n a l p o s i t i o n . A one-megahertz c l o c k - p u l s e t r a i n i s used to toggle the f l i p - f l o p f o r the r i n g o p e r a t i o n . Therefore, the time r e -q u i r e d f o r a computing c y c l e i s approximately 16.4 m s e c , and i f the sample frequency i s l e s s than 60 Hz., the computing c y c l e w i l l be f i n i s h e d before the next sampling pulse occurs and sampling w i l l be u n i n t e r r u p t e d . In t h i s case only 128 new samples are r e q u i r e d to f i l l up the s h i f t r e g i s t e r s f o r the next computing c y c l e . On the other hand, i f the sample frequency i s h i g h e r than 60 Hz., some samples are d e l e t e d d u r i n g computing, so that 256 new samples are r e q u i r e d i f each sample sequence i s to be u n i n t e r r u p t e d . The choice between 128 and 256 samples i s a u t o m a t i c a l l y made by the c o r r e l a t o r . T h i s g i v e s great f l e x i b i l i t y i n o p e r a t i n g at e i t h e r h i g h or low f r e q u e n c i e s . 53 I f the c o r r e l a t o r i s to be operated i n the b i p o l a r mode, the samples i n channel two are fed i n at the l e f t end of D instead of C. The r e s t of the operation i s e x a c t l y the same as i n the normal, operation. 4.2 Implementation of the Modified D i g i t a l C o r r e l a t o r SRI Accumulator Memory F i g . 4.2 Double-shift r e g i s t e r modified d i g i t a l c o r r e l a t o r The implementation and operation of a m u l t i - l e v e l modified, d i g i t a l c o r r e l a t o r i s b a s i c a l l y the same as that of the modified p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r except that more than one b i t i s required to represent a sample. This i s shown i n Figure 4.2. The combined input s i g n a l s , (x-^ +a-^ ) or (x^+ag), are quantized and represented i n the form of coded s i g n a l s at the outputs of the quantizers and coders, which replace the comparators of the p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r . The combination of quantizer and coder can r e a d i l y be r e a l i z e d by an a n a l o g u e - t o - d i g i t a l converter. A l l b i t s of the converter output are then sampled simultaneously and the sampled data stored i n a s h i f t r e g i s t e r , which has the same number of b i t s i n each stage. The scheme of computing by r i n g i n g and s h i f t i n g the contents of the s h i f t r e g i s t e r and memory u n i t as described i n the previous s e c t i o n a l s o a p p l i e s to t h i s c o r r e l a t o r . However, a m u l t i p l i e r and an accumulator are now required i n order to perform m u l t i - b i t data m u l t i p l i c a t i o n and summation. Although a conventional m u l t i p l i e r may be employed f o r t h i s purpose, i t has the disadvantage of reducing g r e a t l y the e f f i c i e n c y of the c o r r e l a t o r . A high-speed d i r e c t m u l t i p l i e r f o r m u l t i p l y i n g the coded quantizer outputs when the number of q u a n t i z a t i o n l e v e l s i s small has been devised. Since only l o g i c gates are used, the m u l t i p l i e r i s almost as e f f i c i e n t as the p o l a r i t y - c o i n c i d e n c e c i r c u i t of the modified p o l a r i t y -coincidence c o r r e l a t o r . The design of the m u l t i p l i e r w i l l be described i n the next s e c t i o n . A f t e r each r i n g i n g operation, the contents of the accumulator are updated by the m u l t i p l i e r output. Of course a p a r a l l e l binary accumulator i s p r e f e r a b l e as f a r as the speed i s concerned. 4.2.1 A Fast D i r e c t M u l t i p l i e r f o r the Modified D i g i t a l  C o r r e l a t o r The c o n s t r u c t i o n of a m u l t i p l i e r by using d i r e c t g a t i n g i s based on the f a c t that t h e product of any two numbers, each being from a finite-member s e t , can only be one of c e r t a i n numbers. For example, the product of any two numbers from the set (-2,-1,0,1,2) can only be one of the numbers i n the set (-4,-2,-1,0,1,2,4). The p o s s i b i l i t y of being -3,3 or any other i n t e g e r may be excluded. Therefore the m u l t i p l i e r can be b u i l t i n such a way that the product i s d i r e c t l y s e l e c t e d from the p o s s i b l e numbers a f t e r d e t e c t i n g the input numbers. Thus 4 w i l l be s e l e c t e d as the product when the inputs are -2 and -2 or 2 and 2. This d e t e c t i o n method can be e a s i l y r e a l i z e d by l o g i c gates when the numbers are coded i n t o binary d i g i t s and the set s i z e i s not too l a r g e . For convenience i n the f i n a l c a l i b r a t i o n and. d i s p l a y , the number assigned to each q u a n t i z a t i o n l e v e l i s shown i n Figure 4.3> i n which both negative and p o s i t i v e numbers are used and, f o r the case of q u a n t i z a t i o n without a n u l l zone, only odd numbers are used.. These numbers are coded i n t o binary 0 , q 3 2 1 -1 X -2 -3 (a) (b) F i g . 4«3 Representation of q u a n t i z a t i o n l e v e l s w i t h i n t e g r a l numbers d i g i t s i n 2' s--complement form. The number of d i g i t s required depends on whether we are using q u a n t i z a t i o n w i t h or without a n u l l zone and on the t o t a l number of l e v e l s . I t i s obvious t h a t , because of the way of a s s i g n i n g numbers, the numbers f o r q u a n t i z a t i o n without a n u l l zone are l a r g e r and need more d i g i t s . Let cc=a a 0 a n a n and 8=b b0b-,b„ be the s 2 1 0 s 2 1 0 numbers to be m u l t i p l i e d and r=c g C2°1 C0 b e ^ e P r o^ u c^' a l l i n 2's complement binary form. a s » h s s.nd c g are used to denote the s i g n b i t . Given the number of q u a n t i z a t i o n l e v e l s i n each channel, the p o s s i b l e values of a and (3 can be deter-mined. Prom these p o s s i b l e values and t h e i r p o s s i b l e product values, r e l a t i o n s between the c^'s and a^'s, b^'s can be derived and the m u l t i p l i e r may be implemented based on these r e l a t i o n s . The l o g i c equations r e l a t i n g the c^'s and a^'s, b^'s f o r implementing the m u l t i p l i e r f o r coarse q u a n t i z a t i o n have been found and are l i s t e d below. For s i m p l i c i t y , the quantizers i n both channels are assumed to have an equal number cf l e v e l s . A 3-Level M u l t i p l i e r This i s the case of null-zone q u a n t i z a t i o n i n which only three l e v e l s are used.. Two d i g i t s are enough to represent each of the m u l t i p l i e r , the m u l t i p l i c a n d and the product. Therefore, we have o - a s a 0 , N b s b Q , r = c s c 0 , and t h e i r r e l a t i o n s are c 0 = a 0 b 0 c s = ( a s ® b s ) a 0 b 0 ' where © denotes " e x c l u s i v e OR" . 51-7 A 4-Le v e l M u l t i p l i e r c T h i s i s the case of q u a n t i z a t i o n w i t h o u t a n u l l zone i n w h i c h f o u r l e v e l s are used. Three d i g i t s are r e q u i r e d to r e p r e s e n t each of a and |3, w h i l e f i v e d i g i t s are r e q u i r e d t o r e p r e s e n t the p r o d u c t , r , i . e . , <x~a.sa.-^&Q, 3=bgt-^hQ and r ^ c ^ ^ ^ c - ^ C Q . The r e l a t i o n s are c Q = 1 c± = a ± $ b x c 2 = a s © b s c^ = a ( a g & b-j^ ) + ^ ( b g Q a 1) + a g a 1 b s + b g b - ^ A 5 - l e v e l M u l t i p l i e r Three d i g i t s are r e q u i r e d f o r a and f o r 8 and f o u r d i g i t s are r e q u i r e d f o r r . Thus, a = a s a 1 a 0 > B = b g b - ^ and r = ^s c2 c± co> and c = a b~ o o 0 c 1 = a 1b 0(b- L+a 0) + b- La 0(a 1+b 0) c 2 = a ^ ^ b Q + a s b s ( b 0 + b i a o ) + % ^ s U Q + a i h Q ) C s = a s b s ( b l + b O ) + V B ^ I ^ O 5 ' A 6 - L e v e l M u l t i p l i e r Four d i g i t s a r e r e q u i r e d f o r a and f o r B and s i x d i g i t s are r e q u i r e d f o r r . Thus, a=a oa 0aT a n , B-b b 0b-,b n and r=c c , c 7 c 0 c , c n . S Z 1 U S d 1 U S 4 J) 2 1 0 The r e l a t i o n s are c 0 = 1 c l = a l * b l c 3 = ( a s b s + a s h s ) ( a 2 + a 1 ) ( b 2 + b l ) + a ^ ^ + + b s a 2 a l + b s a 2 a l °A = a s b 2 a 2 b s + a 2 b s b 2 + b 2 a s a 2 + b s a 2 b 2 a s c = a © b . s s s A 7-Level M u l t i p l i e r Three d i g i t s are r e q u i r e d f o r a and f o r (3 and f i v e d i g i t s are r e q u i r e d f o r r . Thus, a = a s a l a O ' P = b s b l b O ' r = c s c 3 c 2 c l c 0 ' The r e l a t i o n s are c0 = a 0 b 0 c l = a- Lb 0(b 1-fa 0) + b 1 a Q ( a 1 + b 0 ) c2 = a l a 0 ^ b l a s b O + b l a s b O ^ + b l b 0 ^ a l b s a O + a l b s a O ' ) + ( a s Q> b s ) a Q b 0 c 3 = a s b s ( a l ® a 0 } + a s b s ( b l ® V + a l b l ( a s Q b s } + a s b s a l b l + a s b s a l b l a O b O c s = V s ( V V + ^ s V v V ' R e a l i z a t i o n of these l o g i c equations by l o g i c gates ( I n v e r t e r , AND, OR, NAND and/or NOR) i s s t r a i g h t f o r w a r d and thus omitted here. Many high speed p a r a l l e l m u l t i p l i e r s have been described r e c e n t l y ( 1 8 ) ( ! 9 ) ^ G u i l d ^ 1 ^ , f o r example, has proposed a f u l l y i t e r a t i v e p a r a l l e l m u l t i p l i e r by using c e l l l o g i c and c e l l -i n t e r c o n n e c t i o n p a t t e r n . The operating speed of t h i s m u l t i p l i e r i s ( 2 n - l ) T , where n i s the word len g t h of each of the two binary numbers which are m u l t i p l i e d and T i s the propagation delay f o r a s i n g l e c e l l . The l a t t e r i s equal to the propagation delay f o r f i v e l o g i c gates. Thus the speed f o r the m u l t i p l i c a -t i o n of two 3-bit binary numbers i s , f o r example, equal to the propagation delay f o r 25 l o g i c gates. As a -comparison, the speed of the 7 - l e v e l m u l t i p l i e r , which m u l t i p l i e s two 3-bit b i n a r y numbers, i s equal to the propagation delay f o r 5 l o g i c gates only. Therefore, the operating speed of the d i r e c t m u l t i p l i e r i s g r e a t l y improved. I t should be noted that the d i r e c t m u l t i p l i e r described above i s e s p e c i a l l y designed f o r the c o r r e l a t o r a p p l i c a t i o n . The numbers to be m u l t i p l i e d are r e s t r i c t e d to those appearing at the output of the quantizer. For example, the p o s s i b i l i t y that <x=100 or (3=100 i s excluded i n the 7 - l e v e l m u l t i p l i e r . Thus, i t i s not s u i t e d to general 3-bit m u l t i p l i c a t i o n . For general a p p l i c a t i o n , some m o d i f i c a t i o n s are necessary. The d i r e c t m u l t i p l i e r a l s o has the disadvantage t h a t , when the word leng t h i s increased, the l o g i c r e l a t i o n s between c's and a's, b's become very complicated. 4.3 The A p p l i c a t i o n of Pseudo-Random Noise to the Modified  D i g i t a l C o r r e l a t o r The modified d i g i t a l c o r r e l a t o r r e q u i r e s two s t a t i s t i c a l l y independent random noises, each of which i s uniformly d i s t r i b u t e d between two predetermined, l e v e l s . Some devices which generate random noise s a t i s f y i n g t h i s r e q u i r e -ment have been designed and used i n the modified p o l a r i t y -coincidence c o r r e l a t o r i n the past. For example, samples of a sawtooth waveform bounded by two predetermined l e v e l s but wi t h randomly changing slope was used by Jaspers et a l ^ 4 ^ . In the design of the o r i g i n a l U.B.C. c o r r e l a t o r , T u r n e r u s e d the random s i g n a l s from Zener-diodes to t r i g g e r f l i p - f l o p s con-nected to the inputs of a D/A converter. Sato and Kawarada suggested the method of t r i g g e r i n g a feedback s h i f t - r e g i s t e r w i t h random pulses. A l l of these methods i n v o l v e one or more e x t e r n a l random-noise sources. Although the random-noise so generated has very good random nature, e x t e r n a l random-noise sources, because of t h e i r dependence on various environmental c o n d i t i o n s , are u s u a l l y very d i f f i c u l t to c o n t r o l . Psuedo-random noise, on the other hand, i s very easy to generate and c o n t r o l . The c i r c u i t r y i n v o l v e d i s a l s o very simple. In t h i s s e c t i o n , we s h a l l discuss the a p p l i c a b i l i t y of pseudo-random noise to the modified d i g i t a l c o r r e l a t o r . 4-3.1 Pseudo-Random Binary Sequences^ ^ The a u x i l i a r y noise required i n the modified d i g i t a l c o r r e l a t o r can be generated from a pseudo-random binary sequence which i s i n tu r n generated by an n-stage feedback s h i f t - r e g i s t e r . Let d = j d ^ j be the sequence of O's and l ' s generated by the feedback s h i f t - r e g i s t e r . Let c ^ ( i = l , 2 , ,n) denote the feedback connection of the s h i f t - r e g i s t e r ; then the sequence s a t i s f i e s the l i n e a r r e c u r s i o n r e l a t i o n d k = C l d k - 1 C2 dk-2 ® ® W n ' ( 4 - l } where each of the c V s has the value 0 or 1. The sequence repeats i t s e l f p e r i o d i c a l l y . The period i s determined by the feedback c o e f f i c i e n t s c^'s. I t i s obvious that the period can never be greater than ( 2 n - l ) clock periods, as the a l l - z e r o s t a t e must be excluded. A sequence w i t h t h i s maximum period i s u s u a l l y c a l l e d a maximum-length sequence or simply m-sequence. The necessary and s u f f i c i e n t c o n d i t i o n f o r the sequence period to be maximum i s that the polynomial f ( x ) = 1 + c-j^ x + c 2 x 2 + + c n x n (4.2) i s i r r e d u c i b l e and p r i m i t i v e over G F ( 2 ) ^ ^ . A t a b l e of these polynomials can be found i n Reference (15). (17) 4.3.2 P r o p e r t i e s of Pseudo-Random Binary Sequences An m-sequence has the f o l l o w i n g randomness p r o p e r t i e s : 1. In each period of the sequence the number of 1's exceeds the number of O's by one; that i s , there are 2n~^~ l ' s and 2 n _ ^ - l O's w i t h i n the period. 2. In each period there are 2 -1 ways to choose n consecutive d i g i t s ; that i s , every p o s s i b l e set of n consecutive d i g i t s , except a l l O's, occurs e x a c t l y once. 3- There e x i s t s one and only one i n t e g e r v ( O ^ v ^ p - l ) , where P = 2 n - l , such t h a t , f o r every k and j , d, © d, . = d, (4.3) k k-j k+v v^ This i s known as the "cycle-and-add" or "shift-and-add" property. The above "0 and 1" sequence can be transformed, to a "-1 and +1" sequence a = ja^ j according to the f o l l o w i n g r e l a t i o n 62 a k = 1 - 2 d k > (4-4) Because modulo - 2 a d d i t i o n w i t h 0 and 1 i s equivalent to a r i t h m e t i c m u l t i p l i c a t i o n w i t h -1 and +1, the above randomness p r o p e r t i e s f o r "-1 and +1" sequence read as f o l l o w s : 1. In each period the number of -1's exceeds the number of 1 1s by P one. Thus \ a, = - 1 . k=l 2. In each period every p o s s i b l e set of n consecutive d i g i t s , except a l l l ' s , occurs e x a c t l y once. 3. There e x i s t s one and only one i n t e g e r v ( O ^ v ^ p - l ) such t h a t , f o r every k and j , = a k + v - (4.6) I t f o l l o w s d i r e c t l y from p r o p e r t i e s ( l ) and (3) that the autocor-r e l a t i o n of the sequence a i s T3( \ I P R(m) = p ^ a k ak+m k=l '1, I f m=0 (4.7) pS i f m^ O or any m u l t i p l e of P. 4 . 3 - 3 Pseudo-Random Noise The pseudo-random binary sequence described above can be converted to a m u l t i - l e v e l pseudo-random noise by forming a weighted summation of, say, L d i s t i n c t binary d i g i t s . In order to obtain equal l i k e l i h o o d f o r each equally spaced l e v e l , the weighting c o e f f i c i e n t s have to be any permutation of (2 -" 1", 2 ~ \ , 2""^), where the noise bound i s normalized to w i t h i n -1 and +1. D i f f e r e n t arrangements of the weighting c o e f f i c i e n t s and/or d i f f e r e n t choices of the d i s t i n c t binary d i g i t s do not a f f e c t the p r o b a b i l i t y - d e n s i t y 63 f u n c t i o n , but the c o r r e l a t i o n f u n c t i o n and power spectrum are-a f f e c t e d considerably. This w i l l be shown i n more d e t a i l l a t e r . As shown p r e v i o u s l y , two s t a t i s t i c a l l y independent s i g n a l s are required f o r the modified d i g i t a l c o r r e l a t o r . The use of two separate pseudo-random noises derived from separate feedback s h i f t - r e g i s t e r s w i t h d i f f e r e n t and r e l a t i v e l y prime numbers of stages and/or w i t h d i f f e r e n t and r e l a t i v e l y prime t r i g g e r i n g c l ock r a t e s seems a p p l i c a b l e f o r t h i s purpose. However, the c i r c u i t r y i nvolved appears to be very complicated. In f a c t , two independent noises can be obtained from a s i n g l e feedback s h i f t -r e g i s t e r . E s s e n t i a l l y there are two methods to obtain two independent noises from a s i n g l e s h i f t - r e g i s t e r . They d i f f e r i n the way of choosing and sampling the binary d i g i t s , as shown i n Figures 4.4 and 4.5- In the f i r s t scheme, Figure 4.4, 1 odd-number d i g i t s are fed to a D/A converter and the output i s sampled at h a l f of the clock r a t e , which generates a noise a-^(k). In the meantime, another noise a^(k) i s generated by t a k i n g L adjacent even-number d i g i t s . I f the weighting c o e f f i c i e n t s In the D/A converter are i n monotonically decreasing order, the r e s u l t i n g noises a-^(k) and a 2 ( k ) can be w r i t t e n as f o l l o w s . L a l ( k ) = § 2 ~ t a 2 k + r - 2 t , (4.8a) . a 2 ( k ) =X]2 a 2 k + l + r - 2 t , (4.8b) 2- t t = l where O ^ r ^ p - 1 and 2L<n. r i s included to show the randomness of the i n i t i a l value at k=0. I t i s obvious that the two noises are delayed versions of one another. Thus we have 6 4 a 2 ( k ) = / , P+l N a1(k-t-2-) f o r a l l k, ( 4 . 8 c ) P i g . 4 . 4 F i r s t scheme f o r o b t a i n i n g two noise s i g n a l s from a s h i f t r e g i s t e r 3/AConverter D/AConvertei S~ " 2L a x ( k ) a 2 ( k ) P i g . 4 . 5 Second scheme f o r o b t a i n i n g two noise s i g n a l s from a s h i f t r e g i s t e r In the second scheme, Figure 4 - 5 , two adjacent L - d i g i t s e c tions of the s h i f t r e g i s t e r are used to form a-^(k) and a 2 ( k ) . The output of each of the D/A converters i s sampled at frequency f /2L, where f i s the cl o c k frequency. The r e s u l t i n g adjacent numbers are the c 65 spaced 2L clock-periods apart. In t h i s case a. 1 (k) and a 0 ( k ) are w r i t t e n as L a-, (k) a 2Lk+r-t, (4.9a) 1 t = l '2Lk+L+r-t ( 4 . 9 b ) or a-L(k+-2—) . ( 4 . 9 c ) In order to have the longest period and uniform p r o b a b i l i t y - d e n s i t y f u n c t i o n , i t i s necessary that (2L,P) be r e l a t i v e l y prime. on the property t h a t , i f every qth d i g i t of an m-sequence i s r e t a i n e d and the remainder discarded, then the new sequence i s an m-sequence of the same per i o d , provided that (q,P) are r e l a t i v e l y prime. 4 . 3 . 4 Pseudo-Random Noise as A u x i l i a r y Noise i n the  Modified D i g i t a l C o r r e l a t o r We have seen i n Section 2 . 3 that two random noises which ( l ) have zero mean values, ( 2 ) are independent of the input s i g n a l s and of each other, and ( 3 ) are r e c t a n g u l a r l y d i s t r i b u t e d may be used as a u x i l i a r y noises i n the modified d i g i t a l c o r r e l a t o r . We have a l s o seen i n Section 3 - 4 that the mean-square e r r o r of the modified d i g i t a l c o r r e l a t o r d i f f e r s from that of the d i r e c t c o r r e l a t o r only by a term which i s i n v e r s e l y p r o p o r t i o n a l to N i f the noise samples taken are independent of each other. I t w i l l be shown i n t h i s Section that pseudo-random noises from a s i n g l e s h i f t - r e g i s t e r can almost s a t i s f y a l l of these c o n d i t i o n s . These two schemes of sampling an m-sequence are based Consider f i r s t the f i r s t scheme f o r o b t a i n i n g two noises 66 from a s i n g l e s h i f t - r e g i s t e r . Because of the randomness of r , o a 1 ( k ) and a 2 ( k ) may be regarded as random processes with Prob (r) = ~. (4.10) Based on t h i s we have the mean value of a-^(k) L t i = H ^ • ¥-v t = l = -(1-2~ L)/P. (4.11) I f the number of stages of the s h i f t r e g i s t e r i s very l a r g e , t h i s mean value i s almost equal to zero. D a v i e s ^ ^ has shown that a-^(k) has the d i s t r i b u t i o n 9-(n-L) P , ( x . ) = f i f 2 i = 0 ,1 1/-. „-nx l < i < 2 -1 (4.12) where x±•= 1 - (l + 2 i ) 2 2 " ( l - 2 - n ) , -L This d i s t r i b u t i o n i s approximately rectangular i f n i s l a r g e enough. S i m i l a r l y , we can derive the same r e s u l t s f o r a 2 ( k ) . To see the independence of a-^(k) and a 2 ( k ) , we s h a l l f i n d t h e i r c r o s s - c o r r e l a t i o n f u n c t i o n . By d e f i n i t i o n , we have R 1 2(m) = E [a1(k)a2(k+m)J lu L 9-(t+u) 1 P S 2k+r-2t 2k+2m+r+l-2u. 1 u=l r = l (4.13) I f m = ~^ - |m'| , jm'I^L and i i s a nonzero i n t e g e r , 67 P ( \ 1 ' s " - 1 0-(t+U.) 1 ^ s ^ - 1 K {m) •= ^ p a2k+r-2t" a2k+r-2 |m'| +ip-2u t=l u=l r=l 1 = ^V^-^' 1 + u ). i • p + X! S 2 _ ( t + u ) ' " u=l P t = l u=l g 1 ' 1 2-(u+|m'|+u)-. u=l = (1 + JL) 2-lmM [ ^ - 2 ( 1 - | m 1 ) ] _ . I i = | ^ L f ( 4 . 1 4 a ) and, i f m / ^ ~ ~ lm ' l » lm ' l< L> R 1 2(m) - ^ " p " )— = 0, f o r l a r g e n. (4.14b) Therefore, w i t h i n the reg i o n -2 n~ 1+L <m < 2 n _ 1 - l - L , the noises a 1 ( k ) and a 2 ( k ) are almost uncorrelated and may be considered as indepen-dent. As i n the d e r i v a t i o n of the c r o s s c o r r e l a t i o n , the auto-c o r r e l a t i o n of e i t h e r a-^(k) or a 2 ( k ) can a l s o be found as f o l l o w s . R l x(m)=f ( 1 + ^ ) 2 " I-'1 [l-2-^~ I"'" ]- % ^ , m = ip+m', m' ^  L, ( l - 2 " ~ L ) 2 , a l l other m's. " P (4.15) This i s a delayed v e r s i o n of R^ 2(m). For the second scheme, the noises a-^(k) and a 2 ( k ) have the same mean value and d i s t r i b u t i o n f u n c t i o n as f o r the f i r s t scheme. However, the auto- and c r o s s - c o r r e l a t i o n f u n c t i o n s are 11 '3 3? i P - V i m= 2 ^ — and V i L, <j(i + i p)2-< 2 I- V i» [ 1 _ 2 - 2 ( V i - D j _ X l = | : -L x2 m=r r 2 L +1 and V i > L, ( 1 - 2 " L ) 2 a l l other m's, (4.16) and R 1 2(m) -Lx2 m=-i R r l i 2L and V i ' = |L-Vi| ( 1 - 2 ~ L ) 2 a l l other m's, (4-17) where V i i s the residue of iP/2L and i i s 0 or any integer-I t i s noted that the number of words that are c o r r e l a t e d —L 2 (with c o r r e l a t i o n f u n c t i o n l a r g e r than -(1-2 ) /P) i s equal f o r both schemes. However, instead of accumulating together, the cor-r e l a t e d words f o r the second scheme spread out i n the form of spikes. This can be seen i n Pigure 4.6, i n which n=10 and L-5• E i t h e r using the f i r s t or the second shceme, the two noises generated from the s i n g l e feedback s h i f t r e g i s t e r can be used i n the modified d i g i t a l c o r r e l a t o r . However, i n order that the two noises are independent of each other and that t h e i r samples taken by the c o r r e l a t o r are uncorrelated w i t h each other, the t r i g g e r i n g c l o c k . r a t e of the feedback s h i f t - r e g i s t e r and the sampling frequency of the c o r r e l a t o r must s a t i s f y a c e r t a i n c o n d i t i o n . This w i l l be shown below. In order to prevent the same word being sampled twice, i t • i s r e q u i r e d , f o r the f i r s t scheme, that 2Atc<At (4.18) and, f o r the second scheme, that 2LAtc<At, (4.19) F i g . 4.6 Auto- and cross-correlation functions for (a) the 1st scheme, and (b) the 2nd scheme, n = 10, L = 5. 70 where Ate i s the t r i g g e r i n g clock period of the feedback s h i f t r e g i s t e r , and At i s the sampling period of the cor r e l a t o r . ' I f the noise samples are to be independent of each ether, so that no addi-t i o n a l e r r o r due to c o r r e l a t e d noise samples w i l l be introduced, i t i s f u r t h e r r e q u i r e d , f o r both schemes, that I n e q u a l i t y (4-19) be s a t i s f i e d . In order to ensure that the two noises a-^(t) and a^(±) are independent of each other during the computation i n t e r v a l , the maximum computing time, (N-t-km)At, where kmAt i s the maximum time delay, must be l e s s than the i n t e r v a l of time i n which a-^  and a^ are uncorrelated; that i s , f o r the f i r s t scheme, (N+km)At<2(2 n 1 - l - L ) A t c , o r (N+km)At<(P-l-2L)Atc, and, f o r the second scheme, (4.20) P-V (N+km)At <(~2jT + 1) 2LAtc, (4.21) or (N+km)At <(P-V 1 +2L)At c, where i s the residue of P/2L. Therefore, f o r app l y i n g the noises a-^  and a^ "to the modified d i g i t a l c o r r e l a t o r , i t i s necessary, f o r the f i r s t scheme, that fe^M < A t e < f i , (4.22) or, f o r the second scheme, that (N+km)At S.\+rS A t P _ V _ 4 . P T , \ A t c \ ? r ; -V1+2L \  2L. (4.23) 5. CONCLUSIONS The d i r e c t c o r r e l a t o r , the d i g i t a l c o r r e l a t o r , the modified d i g i t a l c o r r e l a t o r , the S t i e l t j e s c o r r e l a t o r and the modified S t i e l t j e s c o r r e l a t o r have been described. The scheme of u s i n g a u x i l i a r y noise to unbias the outputs of the modified d i g i t a l and the modified S t i e l t j e s c o r r e l a t o r s has been analyzed i n d e t a i l . I t has been found that any random noise of which the c h a r a c t e r i s t i c f u n c t i o n has p e r i o d i c zeros can be used as an a u x i l i a r y noise i n the modified d i g i t a l and the modified S t i e l t j e s c o r r e l a t o r s , that uniformly d i s t r i b u t e d noise i s a s p e c i a l case, and that q u a n t i z i n g the a u x i l i a r y noise has the same e f f e c t as d i r e c t l y q u a n t i z i n g the input s i g n a l s . The mean-square e r r o r of each of these c o r r e l a t o r s has been derived. The d i r e c t c o r r e l a t o r has the l e a s t e r r o r , because the input s i g n a l s are not d i s t o r t e d or contaminated. Quantization introduces a bias e r r o r and increases the sampling e r r o r i n the d i g i t a l c o r r e l a t o r and the S t i e l t j e s c o r r e l a t o r . This b i a s e r r o r i s eliminated i n the modified d i g i t a l c o r r e -l a t o r and the modified S t i e l t j e s c o r r e l a t o r . Their sampling e r r o r d i f f e r s from that of the d i r e c t c o r r e l a t o r only by a term which i s i n v e r s e l y p r o p o r t i o n a l to the number of samples taken, provided that the power spectrum of the a u x i l i a r y noise i s wide enough. This a d d i t i o n a l e r r o r i s the combined e f f e c t of q u a n t i z a t i o n and a u x i l i a r y noise. I t can be reduced to any desi r e d value by t a k i n g a l a r g e r number of samples, by usi n g a higher sampling r a t e , or by q u a n t i z i n g more f i n e l y . Although the modified polarity-coinciden.ce c o r r e l a t o r , which i s a s p e c i a l case of the modified d i g i t a l c o r r e l a t o r f o r bounded input s i g n a l s , has the advantage of c o n s t r u c t i o n a l s i m p l i c i t y , i t s e r r o r i s very large compared w i t h the other m u l t i - l e v e l modified d i g i t a l c o r r e l a t o r s . A small increase i n the number of q u a n t i z a t i o n l e v e l s decreases the e r r o r g r e a t l y . A modified d i g i t a l c o r r e l a t o r with coarse quantiza-t i o n can a l s o be implemented p a r a l l e l to a modified p o l a r i t y -coincidence c o r r e l a t o r . A d o u b l e - s h i f t - r e g i s t e r modified d i g i t a l c o r r e l a t o r has been considered. By u s i n g a f a s t d i r e c t m u l t i p l i e r as has been designed, i t i s as e f f i c i e n t as the modified p o l a r i t y - c o i n c i d e n c e c o r r e l a t o r . The use of pseudo-random noise as an a u x i l i a r y noise has a l s o been considered. I t has been found t h a t , i f the period of the t r i g g e r i n g c lock pulses of the noise generator and the sampling period s a t i s f y c e r t a i n c o n d i t i o n s , the two noises from the s i n g l e noise generator are independent of each other and the noise samples are p r a c t i c a l l y u n c o r r e l a t e d . 73 REFERENCES 1. Widrow, B., "A Study of Rough Amplitude Quantization by Means of Nyquist Sampling Theory", IRE Trans. or, C i r c u i t Theory, pp. 206-276, December 1956 2. Widrow, B., " S t a t i s t i c a l A n a l y s i s of Amplitude Quantized Sampled-Data Systems", AIEE Trans. on A p p l i c a t i o n s and Industry. V o l . 79, No. 52, pp. 555-558, January 1961 3. Watts, D.G., "A General Theory of Amplitude Quantization with A p p l i c a t i o n s to C o r r e l a t i o n Determination", IEE • Monograph No. 481M, •November 1961 4. Jespers, P., P.T. Chu and A. F e t t w e i s , "A New Method f o r Computing C o r r e l a t i o n Functions", I n t . Symposium on In-formation Theory, B r u s s e l s , September 1962 5. Ikebe, J . and T. Sato, "A New In t e g r a t o r Using Random-Voltage", E l e c t r i c a l T echnical J o u r n a l of Japan, V o l . 7, No. 12, pp. 43-47, 1962 6. Veltman, B.P.Th., and H. Kwakernaak, "Theorie und Technik der P o l a r i t a t s k o r e l a t i o n f u r die dynamische Analyse niederfrequenter Signale und Systeme", Regelungstechnik, September 1961 7. Korn, G.A., Random Process Simulation and Measurement, McGraw-Hill, 1966 8. Peek, J.B.H., "The Measurement of C o r r e l a t i o n Functions i n C o r r e l a t o r s Using S h i f t - I n v a r i a n t Independent Functions", P h i l i p s Research Reports (Supplements), 9 . Turner, R.M., "A D i g i t a l C o r r e l a t o r f o r Low Frequency S i g n a l s " , M.A.Sc. Thesis, Department of E l e c t r i c a l Engineering, F a c u l t y of Applied Science, U n i v e r s i t y of B r i t i s h Columbia, December 1 9 6 4 1 0 . Knowles, J.B. and H.T. T s u i , " C o r r e l a t i o n Devices and Their E s t i m a t i o n E r r o r s " , J . of Applied Physics, V o l . 38, No. 2, pp. .607-612, February 1967 11. Berndt, H., " C o r r e l a t i o n Function E s t i m a t i o n by a P o l a r i t y Method Using S t o c h a s t i c Reference S i g n a l s " , IEEE Trans. on Information Theory, V o l . 14 , No. 6, pp. 796-801, November 1966 74 1 2 . Wozencraft, J.M. and I.M. Jacobs, P r i n c i p l e s of Com-munication Engineering, John Wiley and Sons, p. 164, 1967 1 3 . Sato, T. and H. Kawarada, "Some Notes on the C o r r e l a t o r Using the Random-Voltage Method", B u l l e t i n of the Tokyo I n s t i t u t e of Technology. No. 60, pp. 25-32, 1964 1 4 . Golomb, S.W., S h i f t R e g i s t e r Sequences,Holden-Day, Inc. , 1967 1 5 . Peterson, W.W., E r r o r - C o r r e c t i n g Codes, M.I.T. Press and Wiley, pp. 251-270, 1961 16. Davies, A.C., " P r o b a b i l i t y D i s t r i b u t i o n of Noise-Like Waveforms Generated by a D i g i t a l Technique", E l e c t r o n i c s L e t t e r s , V o l . 4 , No. 1 9 , pp. 421-423, 1968 17. Tausworthe, R.C, "Random Numbers Generated by Linear Recurrence Modulo Two, Mathematics of Computation, V o l . 19, pp. 201-209, 1965 18. De Mori, R., "Suggestion f o r an I.C. Fast P a r a l l e l M u l t i -p l i e r " , E l e c t r o n i c s L e t t e r s . V o l . 5, No. 3, pp. 5 0 - 5 1 , 1969 1 9 . G u i l d , H.H., " F u l l y I t e r a t i v e Fast Array f o r Binary M u l i t p l i c a t i o n and A d d i t i o n " , E l e c t r o n i c s L e t t e r s , V o l . 5, No. 12, p. 263, 1969 

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-0102309/manifest

Comment

Related Items