Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Analysis and optimization of differential PCM systems operating on noisy communication channels Chang, Ke-yen 1972

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

Item Metadata

Download

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

Full Text

ANALYSIS AND OPTIMIZATION OF DIFFERENTIAL PCM SYSTEMS OPERATING ON NOISY COMMUNICATION CHANNELS  BY  KE-YEN CHANG B . S c , National Taiwan U n i v e r s i t y , 1966 M . A . S c , University of B r i t i s h Columbia, 1969  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENT FOR THE DEGREE OF DOCTOR OF PHILOSOPHY i n the Department of E l e c t r i c a l Engineering  We accept this thesis as conforming to required standard  THE UNIVERSITY OF BRITISH COLUMBIA SEPTEMBER  1972  the  In p r e s e n t i n g  this  thesis  an advanced degree at the L i b r a r y I  further  of  this  fulfilment  the U n i v e r s i t y of  s h a l l make i t  freely  British  available  for  agree t h a t p e r m i s s i o n f o r e x t e n s i v e  for scholarly by h i s  in p a r t i a l  of  the  requirements  Columbia,  I agree  r e f e r e n c e and copying o f  this  for  that  study. thesis  purposes may be granted by the Head of my Department or  representatives. thesis for  It  financial  i s understood that gain s h a l l  written permission.  Department The U n i v e r s i t y o f B r i t i s h Vancouver 8, Canada  Columbia  not  copying o r  publication  be allowed without my  ABSTRACT A closed-form a n a l y t i c a l expression for the output noise r a t i o  (SNR^) of d i f f e r e n t i a l PCM systems operating on noisy communi-  cation channels i s obtained. SNR  q  A procedure i s then proposed for maximizing  by j o i n t optimization of the quantizer, p r e d i c t o r ,  bandwidth.  signal-to-  sampling rate, and  Several examples are considered, including one- and two-sample  feedback systems excited by speech and video s i g n a l s . for reducing channel errors are then discussed.  Various techniques  The predictor used i n the  DPCM system i s l i n e a r and time i n v a r i a n t , but otherwise  arbitrary.  As with PCM, contributions to output signal d i s t o r t i o n can be expressed as a sum of three d i s t i n c t terms r e s u l t i n g , respectively, quantization errors,  channel transmission e r r o r s ,  and mutual errors a r i s i n g  from interaction between quantization and channel e r r o r s . the predictor c o e f f i c i e n t s are presented.  from  Constraints on  for channel errors not to b u i l d up unlimitedly  When a conventional optimum l i n e a r predictor i s used,  transmission errors are shown to be no more serious for DPCM than for PCM. The values of  SNR  q  obtainable from DPCM are also compared with the  t i c a l bound obtained from the r a t e - d i s t o r t i o n  theore-  function.  For a well-designed DPCM system, the value of SNR^ i s shown to be considerably higher than that for a well-designed PCM system operating on the same d i g i t a l channel, even i f the channel i s noisy. examples, for  SNR  q  In considering  p a r t i c u l a r attention i s devoted to determining maximum values and to examining the dependence of  SNR  q  on predictor  coefficient  values, number of quantization l e v e l s , message s t a t i s t i c s , and channel error p r o b a b i l i t y .  Implications of this dependence on system design are  noted. Among the various techniques investigated for combating channel  noise are channel encoding, periodic r e s e t t i n g , and pseudo-random r e s e t ting.  These techniques are further evaluated subjectively with two video  images. DPCM systems with coarse quantization are studied. quantization noise i s considered i n optimizing the p r e d i c t o r .  The fedback Simple  equations for the optimum predictor c o e f f i c i e n t s and the r e s u l t i n g are derived.  \  iii  SNR  Q  TABLE OF CONTENTS PAGE ABSTRACT  ii  TABLE OF CONTENTS  iv  LIST OF ILLUSTRATIONS  vii  LIST OF TABLES  xi  ACKNOWLEDGEMENT I.  II.  x  INTRODUCTION  i  1  1.1  Motivation of this Study  1  1.2  Review of Previous Research •  2  1.3  Scope of the Thesis  4  ANALYSIS OF DPCM SYSTEM WITH NOISY CHANNEL  6  2.1  Mean-Square Error of Sampled Signal  6  2.2  Overall Mean-Square-Error and Output Signal-to-Noise Ratio  2.3  •  11  2 2 Calculation of e , e , e , Q and a / a ' q' m n e x 2.3.1  Expressions  for e , e q  III.  l  and  13  e  m  13 n  2.3.2  Evaluation of Q  15  2.3.3  2 2 Calculation of a /a e x  16  2.4  S t a b i l i t y of the Decoder  17  2.5  Channel noise for Conventional Optimum Linear P r e d i c t i o n '  22  2.6  Comparison of DPCM Error Bound with Rate-Distortion Bound  23  2.6.1  One-Dimensional Random Signals  24  2.6.2  Two-Dimensional Random Signals  28  SYSTEM OPTIMIZATION 3.1  General Optimization Procedure  3.2  Optimization of the Quantizer  3.3  Optimization of the Linear iPredictor v  35 •  35 •  36 37  3.4  3.5  IV.  38  3.4.1  Noiseless D i g i t a l Channels  38  3.4.2  Noisy D i g i t a l Channels  40  Optimization of the Bandwidth  43  3.5.1  Noiseless D i g i t a l Channels  46  3.5.2  Noisy D i g i t a l Channels  47  ONE- AND TWO-SAMPLE FEEDBACK SYSTEMS ••••  51  4.1  Restrictions on System Parameters  51  4.2  Speech and Video Samples  52  4.3  Simulation of Channel Errors  4.4  One-Previous-Sample Feedback  4.5  4.6  V.  Optimization of the Sampling Rate  •  53 58  4.4.1  Effect of a and <>}  4.4.2  S e n s i t i v i t y to Variations i n Signal S t a t i s t i c s  4.4.3  -SNR  58  v s . Number of Quantizer -Output Bits  Two-Previous-Sample Feedback  •••  • • •  •••• -64  •  66  4.5.1  Effect of a^, a^, and $  4.5.2  S e n s i t i v i t y to Variations i n Signal S t a t i s t i c s  69 ...  Previous-Line-and-Sample Feedback S t a b i l i t y Constraints on ct, and a„  4.6.2  Evaluation of Q  4.6.3  Effect of a  4.6.4  S e n s i t i v i t y to Variations i n Signal S t a t i s t i c s  80  T  I  N 84  a„ and <> j I N  86  1 (  SCHEMES FOR COMBATING CHANNEL NOISE Introduction  5.2  Channel Encoding  79 80  4.6.1  5.1  63  •••  91 95 95  •  5.2.1  Uniform P r o b a b i l i t y Density Function  5.2.2  Non-Uniform P r o b a b i l i t y Density Function v  96 97 100  VI.  VII.  5.3  Periodic Resetting  106  5.4  Pseudo-Random Resetting  112  5.5  Other Techniques for Combating Channel Noise  114  5 .6  Subjective Evaluation  -  116  5.6.1  Preparation of Video Samples  116  5.6.2  E f f e c t of Feedback C o e f f i c i e n t s  117  5.6.3  Periodic and Pseudo-Random Relettings  119  DPCM SYSTEMS WITH COARSE QUANTIZATION  130  6.1  Introduction  130  6.2  Optimum Quantizer  131  6.3  Optimum Predictor  6.4  Optimum Quantizer and Predictor  133  6.5  Illustrative  136  •  Examples  132  6.5.1  One-Previous-Sample Feedback  137  6.5.2  Two-Previous-Sample Feedback  138  CONCLUSIONS  141  7.1  Summary of the Present Research  7.2  Suggestions  APPENDIX I. APPENDIX I I .  for Further Research  Calculation of R (k) and R  141 •  144  (k)  147  n qn Derivation of the Overall Mean-Square Error  REFERENCES  149 152  vi  LIST OF ILLUSTRATIONS FIGURE  PAGE  1.  DPCM system  7  2.  Quantizer c h a r a c t e r i s t i c  14  3.  Power spectrum of x(t)  24  4.  Comparison of DPCM performance with the bound; a |  with the minimum cb^ rate-distortion  / =-14.35dB ••••  2  27  2  5.  Samples shown i n black dot are used for p r e d i c t i o n  •••  29  6.  SNR as obtained from (3.14) v s . the normalized sampling rate £ = f /2W for noiseless channel. Fixed at the values shown are the number of quantization b i t s K ( s o l i d l i n e s ) and b i t rate R=fgK (dotted l i n e s ) ; (a) speech, (b) video •••  42  7.  SNR for speech as obtained from (3.14) v s . £ ; a-^ot i s optimized. Values of K are shown next to s o l i d l i n e s . Dotted l i n e s correspond to the constant R values of F i g . 6(a). (a) c}> =P/7f N =10dB, (b) cb =8dB 44 s so ' s SNR for video as obtained from (3.14) with a optimized. Values of K are shown next to s o l i d l i n e s . Dotted l i n e s correspond to the constant R values of F i g . 6(b). (a) <> j = lOdB, (b) cb =8dB 45 Q  T  8.  s  9.  10.  SNR for Gaussian Markov process as obtained from (3,18) for N=l and N-*-"> and from (3.22) for r a t e - d i s t o r t i o n bound v s . 2W/R. The channel i s noiseless  48  SNR as obtained from (3.23) v s . 2W/R with the r e l a t i v e transmitter power <j>w=P/1000f N fixed at lOdB (a) and 8dB (b) •  50  Pictures o r i g i n a l s ; per picture element  54  o  11. 12.  13. 14.  o  512x512 picture elements with 8 b i t s  Correlations of the pictures shown i n F i g . 11; (a) crowd scene, (b) cameraman scene. The distance of the h o r i z o n t a l scale i s r e l a t i v e to the distance between 2 adjacent horizontal elements * •  55  Amplitude p r o b a b i l i t y density of the pictures shown i n F i g . 11; (a) crowd scene, (b) cameraman scene  56  Amplitude p r o b a b i l i t y density of ^=x_-P2X^_^; (a) crowd scene, (b) cameraman scene. Laplacian d i s t r i b u t i o n i s shown for comparison ••  57  e  vii  15.  SNR for speech v s . a =a and <(>=P/RN; N=l, f =2W=8KHz, P=p(l) =0.89, K=4. Quantizer overload l e v e l V/o =20dB. Experimentally measured values are indicated i n symbols 60  16.  SNR v s . a and <> ) for video s i g n a l s ; N=l, K=4 V/a =20dB. crowd scene, p =0.9569, (b) cameraman scene, p^=0.9809  Q  o  g  (a)  e  61  1  17.  Optimum value of a v s . <> j  18.  a v s . cb; when 0<a<a of PCM.  19. 20.  21.  22.  max  •  63  , SNR of DPCM i s higher than SNR  Q  63  % change i n SNR v s . % v a r i a t i o n of p for ct=0.5, 0.75, 0.89; p=0.89 • Q  and 65  S N R for speech vs. K and <b =P/7f N for previous-sample s s o § back systems when a i s optimum, a i s optimum assuming no channel e r r o r s , and when a=0 (PCM)  67  SNR for the crowd scene v s . K and d> =P/f N for previouso, , ,, , , . s. s o . . sample feedDack systems when a i s optimum, a i s optimum assuming no channel e r r o r s , and when a=0 (PCM)  68  SNR for speech vs.a-, and a \ K=4, f =2W=8KHz, V/a =20dB. Experimentally measured values of SNR are shown by the "x" symbols, (a) <j>=10dB, (b) <)>=6dB  70  s  2  e  Q  23A. SNR 10d8, 23B. 24.  25.  for crowd scene v s . a, (b)  and ex.; K=4,  <f>=6dB  V/a =20dB.  •  SNR for cameraman scene v s . a ^ ando^; K=4, l O d S , (b) <f.=6dB  (a)  cb= 71  ?  V/a =20dB. ?  (a) <j>=  Locus of SNR which i s equal to that of PCM for speech. The "x" symbols denote the values of a-^ and that maximize S N R for various values of <> j  72  Q  74  Locus of SNRQ which i s equal to that of PCM for the crowd (a) and cameraman (b) scenes. The symbol "x" denotes the values of a, and a that maximize SNR for the value of cb shown 75 1 2 o Locus of SNR which i s equal to that obtainable from previoussample feedback system for the speech sample ••»••• • 77 0  26. 27.  Locus of SNR which i s equal to that obtainable from previoussample feedback system for the crowd (a) and cameraman (a) scenes *' ** * 7 8  28.  S t a b i l i t y boundary for previous line-and-sample systems. (a) even N, (b) odd N *  29,  The factor Q for previous line-and-sample feedback DPCM as obtained from (4.29) vs. N for various values of a-^ and ••• 87  Q  viii  feedback  83  30.  SNR O  v s a_ and a__ for line-and-sample feedback DPCM f o r the 4  1  N  crowd scene. 31. 32.  (a) cp=10dB, (b) <j>=6dB  SNR vs. and cameraman scene.  89  f o r line-and-sample feedback DPCM f o r the (a) <j)=10dB, (b) cf)=6dB  90  Locus of SNR which i s equal to that of PCM. The values of and that maximize SNR^ are denoted by "x". (a) the crowd scene, (b) the cameraman scene ••••  92  q  33.  Locus of SNR which i s equal to that obtainable from previoussample feedback DPCM. (a) the crowd scene, (b) the cameraman scene . 93  34.  SNR for previous-sample feedback DPCM using Hamming code and non-redundant natural binary code. The channel i s white Gaussian; p (a) i s uniform; a^=p^=0.9569; K=4. (a) transmitter power fixed, (b) b i t - e r r o r p r o b a b i l i t y fixed 101  35.  SNR for previous-sample feedback DPCM using Hamming code and non-redundant natural-binary code.. The channel i s white Gaussian; P (a) i s Laplacian; a^=p =0.89; K=4. (a) transmitter power fixed, (b) b i t - e r r o r p r o b a b i l i t y fixed • 103 e  36.  SNR f o r previous-sample feedback DPCM using Hamming code and non-redundant natural binary code. The channel i s white Gaussian; p (a) i s Gaussian; cx^=p^=0.9569; K=4. (a) transmitter power fixed, (b) b i t - e r r o r p r o b a b i l i t y fixed 104  37.  Encoder for the Hamming code used i n p l o t t i n g Figs. 35 and 36  38.  The factor Q given i n (5.29) vs. the block s i z e M for DPCM with periodic resetting •  105 I l l  39.  SNR for previous-sample feedback DPCM with periodic resetting vs. the block size M; K=4, N=l. (a) the crowd scene, (b) the cameraman scene. Symbols (A,x) denote the experimentally measured values 113  40.  Pictures obtained from a 4-bit previous-sample feedback DPCM with cb=10dB or p=3.9xl0"  120  Pictures obtained from a 4-bit previous-sample feedback DPCM with <f>=8dB or p=l.9*10-4  121  Pictures obtained from a 4-bit previous-sample feedback DPCM with c6=6dB or p=2.4xl0  122  Pictures obtained from a 4-bit line-and-sample feedback DPCM with <j>=10dB or p=3.9xl0  123  Pictures obtained from a 4-bit line-and-sample feedback DPCM with <j>=8dB or p=1.9xi0"  124  6  41. 42.  -3  43.  -6  44.  4  ix  45.  Pictures obtained from a 4 - b i t line-and-sample feedback DPCM with cb=6dB or p=2.4xl0"  125  Pictures obtained from a 4 - b i t previous-sample feedback DPCM with periodic r e s e t t i n g ; -j P^> <f>8dB  126  3  46.  a  47.  =  Pictures obtained from a 4 - b i t previous-sample feedback DPCM with p e r i o d i c r e s e t t i n g ; ^ P^> <j>=6dB 127 a  48.  = L  =  Pictures obtained from a 4 - b i t previous-sample feedback DPCM with pseudo-random r e s e t t i n g ; i P]_> cb=8dB 128 a  49.  =  Pictures obtained from a 4 - b i t previous-sample feedback DPCM with pseudo-random r e s e t t i n g ; i i > ^^dB a  9  = P  129  i  50.  Optimum values of n = c T g / a and as obtained from (6.25) and (6.26) v s . e f o r previous-sample feedback DPCM with n o i s e less channel; p =0.89 139  51.  Optimum values of r)=o"g/a£, and a . for two previous-sample feedback DPCM as obtained from (6.2/) and (6.15) v s . e ; p = 0.89, p =0.65 140  x  o  9  2  1.1.  D i g i t a l communication system  149  x  LIST OF TABLES TABLE I.  II. III. IV.  PAGE 2 2-1 Comparison o f the v a l u e s o f (o /a ) i n dB w i t h p(m,n) o b t a i n e d from (2.59) and those w i t h p(m,n) o b t a i n e d from measurement •  33  Quantizer overload l e v e l r e l a t i v e  51  e  to a  e  i n dB  Improvement i n SNR^ when N=2 over N=l Improvement o f SNR f o r line-and-sample previous-sample feedback  xi  76 feedback  over 91  ACKNOWLEDGEMENT I would l i k e to express my sincere  gratitude  to my research  supervisor, Dr. R.W. Donaldson, for h i s valuable suggestions encouragement throughout the course of this work.  and constant  I am also greatly i n -  debted to Dr. A . D . Moore for his understanding and moral support. I wish to thank Dr. G.B. Anderson for making available d i g i t i z e d picture data produced i n the Research Laboratory of of the Massachusetts  I n s t i t u t e of Technology.  the  Electronics  I would also l i k e to  thank Messrs. J . Yan and A. Soubigou for many h e l p f u l discussions, Mr. M. Koombes for assistance with the picture d i s p l a y , and Miss N. Duggan for typing the  thesis.  I g r a t e f u l l y acknowledge the f i n a n c i a l assistance received from the University of B r i t i s h Columbia in the form of a Graduate Fellowship, from the National Research Council of Canada through Grant NRC A-3308, and from the Defence Research Board of Canada through Grant DRB 2801-26. Finally,  I would l i k e to thank my wife Shirley for her contin-  uous encouragement and support.  xii  I. INTRODUCTION  1.1  Motivation of This Study It i s w e l l known that d i g i t a l communication systems have many  advantages over analog communication systems. attractive,  for instance,  D i g i t a l systems  are  i n situations where there i s h i g h - l e v e l noise  or interference i n the transmission medium.- A l s o , they are p a r t i c u l a r l y useful when t i m e - d i v i s i o n multiplexing of several signals into a common channel i s desired.  However, they also have some shortcomings,  the most  serious of which i s that broader bandwidth i s required for transmission. Much e f f o r t has therefore been devoted to the reduction of bandwidth requirement i n d i g i t a l systems, dundancy reduction or source encoding. proposed i n the past,  a technique also known as re-  Among the many source encoders  d i f f e r e n t i a l pulse-code modulation (DPCM) i s one  of the simplest and most e f f i c i e n t .  Taking advantage of the large amount  of redundancy, or c o r r e l a t i o n , inherent i n most signals by using p r e d i c t i o n , i t offers s i g n i f i c a n t improvement i n system performance r e l a t i v e to PCM without great increase i n system complexity or cost. Although a great number of studies on DPCM has been reported i n the past,  an important aspect that has l a r g e l y been overlooked i s the  effects of channel noise and the many associated problems.  It has been  suggested i n some studies that, due to i t s feedback network i n the decoder, DPCM i s more susceptible to channel noise than PCM.  Without a rigorous  proof, however, the correctness of this i n t u i t i v e suggestion appears be doubtful.  to  Furthermore, even i f i t i s true, questions arise as to how  much more serious the effect of channel noise i s on DPCM than on PCM, and how variations i n system parameters,  channel parameters,  and message-  2  source s t a t i s t i c s affect system performance.  These questions motivated  the present research.  1.2  Review of Previous Work In order to transmit an analog waveform d i g i t a l l y , i t i s .  necessary to convert i t into a waveform which i s discrete i n both time and amplitude. This can be accomplished by f i r s t sampling the analog waveform at a constant rate and then representing the r e s u l t i n g samples, which are continuous i n amplitude, with a f i n i t e number of discrete levels.  The f i r s t system that performed  1938[1] and was  these operations appeared i n  l a t e r known as the pulse-code modulation  Much work on the design, analysis and development of PCM  (PCM)  system.  then followed  [2]. Due to i t s inconvenience i n .requiring a broader bandwidth than an analog system, however, some researchers also started exploring new techniques for bandwidth reduction. i.e.,  delta modulation  (AM), was  In 1945,  a simple encoding  discovered!3].  technique,  Instead of quantizing  analog samples d i r e c t l y and independently as i n PCM,  i t transmits  only  the sign of the difference between the input sample and the output of a l o c a l decoder, which i s simply an integrator.  Because only one binary  d i g i t i s used f o r each sample, the bandwidth required i s greatly  reduced.  However, this bandwidth reduction i s achieved at the expense of system performance.  The system was  l a t e r improved and generalized with the sign  detector replaced by a m u l t i l e v e l quantizer[4,5], and the integrator replaced by a l i n e a r predictor[6].  The new  d i f f e r e n t i a l pulse-code modulation system.  system became what i s c a l l e d a It was not only e f f i c i e n t i n  redundancy reduction, but also simple i n structure  and high i n p e r f o r -  3  formance.  It has therefore received very much attention. Much work on DPCM was l a t e r done by 0'Neal[7,8],  He i n v e s -  tigated the usefulness of DPCM for the transmission of t e l e v i s i o n signals . and presented a procedure for the design of near-optimum systems.  He  also derived bounds for s i g n a l - t o - q u a n t i z i n g noise ratios of DPCM and AM, and compared them with Shannon's t h e o r e t i c a l bound. Nitadori[10],  McDonald[9] and  on the other hand, analyzed the performance of DPCM for  speech s i g n a l s .  Further study of DPCM for the transmission of speech  signals was done by Donaldson and C h a n [ l l ] , who analyzed and, i n p a r t i cular, subjectively evaluated the performance of the system.  Also,  Donaldson and Douville[12] subjectively compared DPCM with other  source  encoders. Although so much work on DPCM has been done i n the past,  its  performance i n ,a .noisy environment, despite i t s importance, has received r e l a t i v e l y l i t t l e attention.  It has only been suggested i n some e a r l i e r  studies that transmission errors i n DPCM are more serious than those i n PCM.  Recently, Arguello et a l [13]  studied the effects of channel e r r o r s .  However, their results apply only to a 4 - b i t DPCM system with PCM updating for video s i g n a l s .  For speech s i g n a l s , Yan and Donaldson[14]  subjectively compared the effects of transmission errors on DPCM and PCM systems. As for the effects of the variations i n system parameters, channel parameters and signal s t a t i s t i c s on the performance of a system operating on a noisy d i g i t a l channel, no studies have, to the  author's  best knowledge,ever been reported, other than the work described i n this thesis,  some of which has recently been published[15].  k  1.3  Scope of tha Thesis The purpose of the present study i s to calculate  signal-to-noise ratio  ( S N R ) of DPCM systems when channel errors q  be ignored, to maximize s e n s i t i v i t y of  SNR  the output  SNR  q  cannot  by system optimization, to determine  the  to variations i n system parameters, channel parame-  q  ters, and message-source s t a t i s t i c s , and to evaluate the  effectiveness  of various techniques for combating channel noise. The predictor used i n this study i s l i n e a r and time-invariant, or non-adaptive, but otherwise a r b i t r a r y . expressions  In Chapter I I ,  analytical  for SNR are derived and the s t a b i l i t y of the decoder i s o  discussed.  As with PCM[16], contributions to output s i g n a l d i s t o r t i o n  can be expressed as a sum of three d i s t i n c t terms r e s u l t i n g from quantization errors,  channel transmission e r r o r s ,  between quantization and channel e r r o r s . ssion errors on  SNR  q  and mutual errors  The effect of channel transmi-  when the conventional optimum predictor i s used i s  determined i n Section 2.5.  Contrary to e a r l i e r suggestions,  transmis^-  sion errors are shown to be no more serious for DPCM than for PCM.  In  Section 2.6, the d i s t o r t i o n bound of DPCM i s compared with the r a t e d i s t o r t i o n bound for both one- and two-dimensional s i g n a l s . In Chapter I I I ,  a procedure for optimizing  mization of the quantizer, p r e d i c t o r , proposed.  SNR  q  by j o i n t o p t i -  sampling r a t e , and bandwidth i s  The optimization of each of the above items i s also studied i n  detail. In Chapter IV, several p r a c t i c a l examples are considered, including one- and two-previous-sample feedback and p r e v i o u s - l i n e - a n d sample feedback systems.  Both speech and video signals are used to eva-  luate the performance of these systems.  The results show that SNR of o  a  well-designed DPCM system i s considerably higher than that of a w e l l designed PCM system operating on the same d i g i t a l channel, even i f t h i s channel i s noisy. maximizing  SNR^  In studying these systems,  attention i s devoted to  and to examining the dependence of  SNR  q  on the values of  predictor c o e f f i c i e n t s , number of quantization l e v e l s , message-source statistics  and channel error p r o b a b i l i t y .  Implications of this  dependence on system design are noted. Various techniques for combating channel noise are ted i n Chapter V.  Among these are channel encoding, periodic  and pseudo-random r e s e t t i n g .  These techniques are further  investigaresetting  subjectively  evaluated with two video images. F i n a l l y , i n Chapter V I , DPCM systems with coarse quantization are studied*. the p r e d i c t o r .  The fedback quantization noise i s considered i n optimizing Simple equations for the optimum predictor  and the r e s u l t i n g SNR are derived.  This work has recently been presented i n ICC-72I17].  coefficients  6  II.  ANALYSIS OF DPCM SYSTEM WITH NOISY CHANNEL  Shown i n F i g . 1 i s a DPCM system block diagram. p o s t f i l t e r s G^(f) and G ^ i f )  The pre- and  are assumed to s a t i s f y the following equation,  where the set J " contains a l l frequencies i n the f i l t e r s ' passband, and the set  contains a l l frequencies not included i n j r • G ( f ) = G-(f) = 1  1  In a d d i t i o n , x(t) G.. (f)  \  1  2  fs  & _ f s ^  (2.1)  i s assumed to be free of a l i a s i n g e r r o r s * ;  therefore  and G_(f) are non-zero for at most one frequency i n the set f + kf  X.  s  c,  where k i s any integer, including zero, and f i s the sampling frequency. Normally, the input samples would result from low-pass f i l t e r i n g the input s i g n a l m(t)  and sampling the r e s u l t i n g signal x(t)  every  1/f  s  second. Instead of being quantized and coded d i r e c t l y ' a s i n PCM, the sampled s i g n a l  i s f i r s t compared with i t s predicted value z^ and the  difference e^ i s then quantized, coded and transmitted over the d i g i t a l channel.  In the receiver,  another version of the predicted value z^ i s  added back to the received signal to form the output sequence x^. i s noted that when the feedback parameters  =  = a^...=  It  = 0, a  PCM system r e s u l t s . 2.1  Mean-Square Error of Sampled Signal Let q. = s.  - e.  denote the quantization error and n . = r.  denote the d i g i t a l channel noise (see F i g . 1).  s.  The difference x^ - x^  i s obtained as follows, where 6^ i s the unit impulse, I K i s the *  -  (digital)  A l i a s i n g errors result when sampling rate f i s too low. A careful discussing of how frequency set ^ s h o u l d be selected to eliminate aliasing appears elsewhere [18],  DIGITAL  ENCODER  I PRE mft)  FILTER  Gj(f)  \  x(t)  I  X- _  1  QUANTIZER e-  CHANNEL  s-  i  +  +  LINEAR PREDICTOR 7  -<=|  «J>H  POST FILTER —^-s  A  G (f) 2  +  LINEAR PREDICTOR  A  z. z  i=j^j H x  DIGITAL  DECODER  F i g . 1 DPCM system  DIGITAL ri  i m p u l s e response o f t h e l i n e a r p r e d i c t o r , and f ^ i s t h e ( d i g i t a l ) response o f the decoder.  impulse  Thus, i n F i g . 1,  h. = I ^  i = 1, 2,  N  ( 2 > 2 )  otherwise y ^ x . + q .  (2.3)  s , = y. - z. ( x . + q.) ( 6 .  I  . - h. .)  (2.4)  x. = E (s, + n. ) f. , l , k k l-k k=-°° oo  oo  Z  (x + qj) io  11  When t h e q u a n t i z a t i o n  A  I  L  \  +  ]  i-k  f  < ' 2  5)  noise i n F i g . 1 i s neglected, the d i g i t a l  encoder and d i g i t a l decoder a r e i n v e r s e  k  ~ V j >  systems.  Therefore,  E (6, . - h. .) f . , = <5. . __«_ k-3 k-j i-k i - j  (2.6)  CO  D  X  i "  X  i  =  q  i  +  \  Z v  f  i-kA =  +  E  n  i-k k f  Assume now t h a t x. and n. a r e samples from s t a t i o n a r y i l *  sequences, i n w h i c h case x. - x., q. and X  random sequences.  L e t E[  1  1  oo  E , k=-  n. f. , a r e a l s o co  iC  1 K.  < ' 2  7)  random stationary  ] denote " t h e e x p e c t e d v a l u e o f " . Then t h e  discrete c o r r e l a t i o n functions  R ( k ) and R ( k ) can be d e f i n e d qn n  as f o l l o w s ,  R ( k ) = E [ q . n. . ] qn l i-k  (2.8)  R ( k ) = E[n. n._ ]  (2.9)  n  k  From (2.7),  (2.8) and (2.9), one obtains the mean-square 2  tween x^ and x^, normalized with respect  2  to  difference be?  = E[x^] = E [ x ~ ( t ) ]  5  as  follows. e  = E [(x. - x . ) ] / a 2  = (e + e q m  2  + e ) a / a c e x 2  (2.10a)  2  where a  2 2 = E[e/] e l  e = E[q ]/a q i e 2  n  = R (0)/o q e  2  (2.10b)  2  J  CO  e  = [2  Z  m k  =  R  _ c o  (k) f, ]/ a  qn  k  (2.10c)  2  e  and co  e  c  As i n PCM  f ]/ a /  (2.10d)  •*  quantization  error e can be separated into  error e , mutual error e and channel q m  These errors can also be expressed i n terms of the power spec-  t r a l densities S ( f ) , S q  '  (f) and S ( f ) , which are the Fourier qn  respectively, of R^(k), R  *  (k-j) f  n  [16 ], the mean-square  three d i s t i n c t terms: error e .  9  oo  = [ Z E R k=—°° j = — o o  '  n  (k) and  transforms,  '  R n  ( k ) , as follows*.  The Fourier transform T(f) f o r a sequence (t^} of numbers i s related to the sequence as follows m/rN T(f) =  ? E k=-»  _ -j2irfk/f t.e s J  k  k  1 t, = — s f  . f 12 j2Trfk./f / s T(f)e s J  - f 12 s  V2  1 \  T  ' - f 12 s f 12  s  n  2 S  q( > f  d f  /°  (  -  2  e  U  a  )  n  g  e = T~ m f s  / - / -i s12  1  e  c  f  =j s  c  /  2  9  2  /  (2.11b) '  S (f) F*(f) df/o qn ' e ^  9  S (f) |F(f)j  2  n  Z  9  (2.11c)  df/o^  s  where the d i g i t a l decoder's transfer function F ( f ) i s  Expressions for R  -1 exp (~j2irfk/f )]  N  F(f) = [1 -  I k=l  ^ k  (k) and  (2.lid)  S  R- 0O are derived i n Appendix I. n  These correlation functions depend on the second-order amplitude prob a b i l i t y density of e^. In fact, even when these second-order are  available, calculation of R  (k) and  statistics  R 00 i s tedious. When the d i g i t a l n  channel i n F i g . 1 i s memoryless, however, and when the samples  are  s t a t i s t i c a l l y independent, then (see Appendix I) R^^(k) = E[q^] E[n^_^] 2 and R 00  =  (E[n^]}  for k^O.  I f , i n addition, we assume with no loss  i n generality that E[q_^] = E [ T K ] = 0 , then, since .f  = 1,  ( 2 . 1 0 a ) can be  rewritten as follows. e  where  = <q e  +  e  m  ^n> e x  +  a  /a  ( 2  1 2 a )  e = 2 R (0)/o m qn e  (2.12b)  e = R (0)/a n n e  (2.12c)  2  2  v  and  '  1f s  Q = T~  V2  - f 12 s /\Hf)\  9  / 9  When the samples x^ are from an  «  (2.12d) order Gaussian Markov source,  when the number of quantization l e v e l s L 5 8, and when the feedback  parameters ples  ( i = 1,  . . . , N) are chosen, to minimize  are uncorrelated and, therefore,  2  , then the sam-  s t a t i s t i c a l l y independent [19].  Because a w e l l designed l i n e a r predictor causes the samples e^ to be weakly correlated, i t i s not unreasonable to assume that R (k) = R (k) = qn n J  for a l l kf"0.  The examples i n Chapter IV w i l l show that this assumption  leads to a very close agreement between measured and calculated p e r f o r mance curves when m(t) i s a speech or a video waveform. 2.2  Overall Mean-Square Error and Output Signal-to-Noise Ratio When the sampling rate f  = 2W, where W i s the t o t a l width i n  Hertz of the p o s i t i v e frequency spectrum over which G^(f) 4- 0, and when G^(f) and ^ ( f ) are given by (2.1), i n reference  then an argument s i m i l a r to the one  [18] y i e l d s the mean-square difference between analog wave-  forms x(t) and x(t) i n F i g . 1 as follows. E{[x(t) - x ( t ) ] } / a 2  2  = e  (2.13a)  In certain cases, the s i g n a l to be transmitted i s bandlimited.  Then  G^(f) i s not required and x(t) may be considered as the input of the system.  The output s i g n a l - t o - n o i s e ratio SNR , defined as the r a t i o of o  the input s i g n a l power to the mean-square error between the input and output of the system"'", i s then simply the r e c i p r o c a l of (2.13a); i . e . , SNR When f  s  = 1/e  (2.13b)  >, 2W, i t can be shown that the mean-square difference  between x(t) and x(t) i s  n  2  (see Appendix II)  In some cases, the output s i g n a l - t o - n o i s e r a t i o i s defined as the r a t i o of the inband s i g n a l power to the inband mean square d i s t o r t i o n [11,12]. Our d e f i n i t i o n here i s more general. 2  For s i m p l i c i t y , G^(f) and ^ ( f ) are assumed to be low-pass f i l t e r s here.  2 E{[x(t) - x ( t ) ] } =  1  W  j- f s -W  Z  [S ( f ) + S q  (f)F*(f) + S  q  S (f)  |F(f)|  n  When f  i s not v e r y l a r g e compared w i t h 2W,  s  2  ] df  +  (2.14a)  S ( f ) , the spectrum of q  q u a n t i z a t i o n n o i s e samples q^, i s r e l a t i v e l y and  *(f) F(f)  q  flat  [20],  If S  the  ( f ) , S^(f)  F ( f ) are a l s o r e l a t i v e l y f l a t - i n f a c t , S  ( f ) and S ( f ) are c o n s t a n t qn n then the i n t e g r a l i n (2.14a) can be c l o s e l y  J  i f R^ (k) = R (k) n  v  = 0 f o r k^O,  n  2 a p p r o x i m a t e d as 2Wea  and  x  the o u t p u t s i g n a l - t o - n o i s e r a t i o i s  SNR  = f o  where e i s o b t a i n e d  / 2We  (2.14b)  s  from (2.10) o r  (2.12).  F i n a l l y , the o v e r a l l mean-square d i f f e r e n c e between m(t)  and  x ( t ) can be w r i t t e n as f o l l o w s (see A p p e n d i x I I )  E{[x(t) - m ( t ) ]  2  W = i - / s -W  [SCf)  f  q  + S  ( f ) F * ( f ) + S*  q n  (f) F(f)  +  q n  OO  S (f) n  where S ( f ) r e p r e s e n t s m  random p r o c e s s m ( t ) .  | F ( f ) | ] df + 2/ 2  S„(f)  The  a l l frequencies  in-band d i s t o r t i o n .  CO  o  = o/  -  o  S ( f ) df / x  m  /  (2.15a)  stationary  second i n t e g r a l i n (2,15a) i n v o l v e s  If f  approximate the o u t p u t s i g n a l - t o - n o i s e r a t i o as  SNR  df  the power s p e c t r a l d e n s i t y of t h e  caused by p r e f i l t e r i n g from m(t) i n t e g r a l represents  w  f  f s  W -Wm  greater i s not  the  than W.  error The  t o o l a r g e , we  first can  follows. 00  S ( f ) df + 2 A_ S W m ( f ) df}  (2.15b)  T h i s r e l a t i o n w i l l be used t o s t u d y the e f f e c t of b a n d w i d t h i n C h a p t e r I I I .  2 2 C a l c u l a t i o n o f e , e , E , Q and a /a q m n e x  2.3  %  We have seen i n S e c t i o n  2.1 t h a t the mean-square  be e x p r e s s e d i n terms o f e , e , e , Q and a q m' n' •e 1  and e  n  a r e dependent on the q u a n t i z e r  2  /a x  2  .  The e r r o r s  e , e q m  c h a r a c t e r i s t i c and the c h a n n e l  n  error probability.  Q and  2  M  e r r o r e can  The l i n e a r p r e d i c t o r  a f f e c t s e t h r o u g h the f a c t o r s  2 /a_ .  I n the f o l l o w i n g , we s h a l l e x p r e s s each o f the above  f a c t o r s e x p l i c i t l y i n terms o f t h e s i g n a l s t a t i s t i c s and system parameters 2.3.1 E x p r e s s i o n s f o r e , e and e . q m n F i g . 2 shows the t r a n s f e r c h a r a c t e r i s t i c o f t h e q u a n t i z e r i n r  Fig.  1.  Assume t h a t  that  the q u a n t i z e r  the d i g i t a l c h a n n e l i n F i g . 1 i s memoryless  i n p u t samples e^ are s t a t i s t i c a l l y i n d e p e n d e n t .  P (°0 denote the a m p l i t u d e p r o b a b i l i t y d e n s i t y denote the p r o b a b i l i t y t h a t the q u a n t i z e r  m i t t e d and V j r e c e i v e d .  Let  o f t h e samples e^, and l e t  e  P  and  output l e v e l v^ i s trans-  Then use o f (2.12) and an approach s i m i l a r t o  t h a t i n Appendix I y i e l d s i+1 / u.  L  e  q  =  2 ( v . - a) i  U  E . ,  1=1  I  2 P (a) da / a e e  A  i+1 f" i  L  =  e  = 2  ~ 2 ( v . - a r P (a) da  U  E 1-1  A  U  L E  1  L E P.. j=l  1=1  (2.16)  6  J  J  „ u ( v . - v.) /„ u.  (a - v.) p (a) da  J  l (2.17)  and L  e  =  L  E Z P., i=l j=l J  where u. = u./a l l  (v  " 2 - v )  U Z  i+1  p (a)  da  (2.18)  u. l  , v. = v./a and p (a) - a p (a a ) . e i i e e e *e e r  *  Thus, p (a) has ' e r  the same f u n c t i o n a l form as p ( a ) , b u t i s n o r m a l i z e d to have u n i t v a r i a n c e g  Uj=-ao  U  U  2  3  U  4  -7<-  L-1  U  L  U  3  v  2  v  Fig.  2  Quantizer  Assume that e_^ and density.  Then, from (2.12),  Characteristic  have the same amplitude p r o b a b i l i t y (2.17) and (2.18), we can see that the  quantization error and mutual error of DPCM are reduced from their c o r responding values by the factor  2 2 '/o .  The DPCM channel error equals 2 2 that f o r PCM m u l t i p l i e d by the factor Qa^ /a . I f the quantizer output CT  e  l e v e l s are arranged i n accordance with the following equation, then e  m  [21]. U  /  u. l  i+1  (v  ±  - a) P (a) da = 0,  i = 1, 2,  L  (2.19)  If the d i g i t a l channel has memory, and/or i f the samples e_. are s t a t i s t i c a l l y  dependent, then  (2.10c),  (1.1) and (1.3)'  (2.10d),  and  can be obtained by using  2.3.2  The (2.12d)  in  of Q  Evaluation  z plane.  s u b s t i t u t i o n z = exp ( j 2 ? r f  t o be e x p r e s s e d as a c l o s e d  / f ) can be used t o e n a b l e Q  c o n t o u r i n t e g r a l i n t h e complex  A Thus,  Q = ~  j ^  | | z  =  !  {  1  t  /  z H  < ) z  H  (  )]>  z _ 1  d  (2.20a)  z  where N H(z)  1  =  -  Z  a.  i=l In o r d e r and  sufficient  the  z-plane.  that  that This  z  (2.20b)  1  1  the decoder i n F i g . 1 be s t a b l e , i t i s n e c e s s a r y  a l l the zeros  o f H(z) l i e i n s i d e t h e u n i t  assumption w i l l be made i n d e t e r m i n i n g Q.  L e t a = - 1 and d e f i n e o  <Kk)  = ~ - r  iKk) as f o l l o w s ,  (j>, | ,  Jl l=l  2  N E  K0).  From ( 2 . 2 1 )  HCz" ) 1  H  (  z  )  i t follows  r ^(k-i) = —  a  i=0  i <j>, 2TTJ  1  (2.21)  dz  1 n  z  Note t h a t Q =  circle of  that  k-1  ,  (2.22)  dz  J | z | - 1  H  (  z  - 1  }  -1 Since the i n t e g r a n d  the roots o f H(z  of ( 2 . 2 2 )  ) a r e the r e c i p r o c a l s o f those o f H(z) ,  has no s i n g u l a r i t i e s  c i r c l e when i n t e g e r k >, 1 , and f i r s t o f Cauchy's r e s i d u e  The  l  at z = 0 f o r k = 0 .  Use  k= 0  C-l Q  pole  i n s i d e the u n i t  theorem y i e l d s  N ±  order  (poles)  °i « W > = {  o  substitution w = z ^ i n (2.21)  k  = l , 2,  ...,N  (  2  -  3  y i e l d s the following expression f o r  -2  iK-k) (note t h a t  2  dw = -z d z ) .  Note t h a t H(z) i s n o t t h e t r a n s f e r f u n c t i o n c o r r e s p o n d i n g t o h^.  )  16  K"k)  w  2rrj  r l  k+l  (-w  dw)  (2.24)  H(w -) K(w) 1  It follows from (2.21) and (2.24) that Kk). = K~k).  Equation (2.23)  can now be rewritten as follows.  a ip (0) + a.^  + a^_  (1) + a ^(2) +  Q  (0)+ ( a + a ) <KJ) + « 2  Q  a )^(l)  a _*(0)+ ( a + 2  <K2) +  3  + a  ^(H-l) = 0  N  + (a +a )i|»(2) + . .  1  3  *(N-1) + cyKN) = -1  ±  2  t|>(N-21 = 0  Q  (2.25)  V l *  (  0  )  +  (  V2  +  V  +  a N  -3^  ( 2 )  +  a 'K0)+ a ^ - i K D + _ " J ( ) + • • . . + a  N  ,  N  2  2  ' •  V  +  (  N  _  1  )  =  0  a^CN-l) + a f(N) = 0 Q  The set of equations i n (2.25) can now be solved to obtain ~4>(Q) = Q, as follows. a  + a  Q  a  2  a., + a„ 1  a  3  a"+a. . . 0 4  3  0  0  a  a  Q  l  a  a  ±  0  + a  . .  2  2  a  N-l  ' * "  a  N  ®  a„ a..+a„ a„+a, . . 0 2 1 3 0 4  0  V l V2 N V3-' 0  °  Q=-  a  N-2 N +a  *N-1  a  v.  N-3  0  •i o a  N-2  a  +a  "N N - l N-2 a  a  a  *'  l  a  a  0 (2.26)  2.3.3  Calculation of a The r a t i o a  e  2 2 /a x  2 2 /a can be calculated as follows. e x  In F i g . 1,  e. = x. -  N Z a.  (x.  . + q. .)  (2.27)  2 ? o = E[e/] e I L  N = R (fl) - 2 Z a  +2  J  [R (j)+R  N-1 N-j Z. Z a j = l k=l  a  J  K  (j)] +  N Z a /  [R (0)+2R  (0)+R (0)] fl  [R (k) + 2R (k) + R ( k ) ] x xq q  2  (2.28)  2 Since R (k) and R (k) are again dependent on a , i t i s extremely d i f xq q • e 2 f i c u l t to solve for a i n terms of the .signal s t a t i s t i c s and a. i n e l &  (2.28). I f , however, the number of quantization levels L i s not too small ( t y p i c a l l y L 5 8), then the quantization noise q^ i s small, on the average,  with respect to x . .  In this case,  | R ^ ( j ) | << |R ( j ) | and  i xq |R (j)|> and (2.28) s i m p l i f i e s as follows, x N N N-j 0^/0 = Z a + 2 Z Z a. OL p(j) e j=0 j=l k=0 *  |R (3)I « q  (2.29a)  2  2  X  where  x  3  K  2  p(j) = R ( j ) / R ( 0 ) x  (2.29b)  x  Much of the analysis to follow i s based on the assumptions |R (i)\ n  «  |R (j)I and |R ( j ) | << |R ( j ) | .  When L $ 8, these assumptions  are of doubtful v a l i d i t y , with the result that the values of SNR c a l o culated for L $ 8 w i l l be i n e r r o r .  The discrepancy between the c a l -  culated value of SNR and the actual value increases  as L decreases, and  o is largest 2.4  for L = 2 (A-modulation).  S t a b i l i t y of the Decoder An important factor which has to be considered i n designing  a DPCM  system i s the s t a b i l i t y of the decoder.  Because of the feedback  network i n the receiver,  errors  caused by channel noise may accumulate  or even magnify unlimitedly i f the feedback c o e f f i c i e n t s a ^ , . . . , c t ^ are not c a r e f u l l y chosen. A network i s said to be stable i f every bounded input to the network gives a bounded output. for  The necessary and s u f f i c i e n t condition  a ( d i g i t a l ) network to be stable i s that a l l the poles of i t s trans-  f e r function l i e inside the unit c i r c l e of the z-plane [22]. for  Therefore,  the decoder i n F i g . 1 to be s t a b l e , i t i s required that a l l the roots  of the polynomial H(z) l i e inside the unit c i r c l e .  For convenience i n  p r a c t i c a l a p p l i c a t i o n s , we s h a l l express this condition e x p l i c i t l y i n terms of the feedback c o e f f i c e i n t s . Define  the matrices X. and Y. as follows. x  x  0  0  0  0  1 $ i s; N-KL  X. a. x-2 0  a  i-l  a  a  i-3  i-2  "N-i+l  a  N-i+2  a  a  Vi+3  (2.30a)  -a. . i-4 a  i-3  N-i+2  °N-i+3 '.. ' ' '.  N-i+3  V-i+4  Vi+4  a  N-i+5 * * '  N  a  N °  ° 1 $ i $ N+1  Y. =  x  V l L N  °N  0  0  0  0  (2.30b)  Then i t can be shown that the necessary and s u f f i c i e n t conditions for a l l the zeros of H(z) to l i e inside 1)  H(l) > 0  2)  H(-l) > 0  3)  a. f o r even N  (2.31a) and  < 0 or  the unit c i r c l e are [23]  (2.31b)  k = 1, 3, 5, 7 , . . . ,  N-l  (2.31c)  alternatively, > 0  k = 2, 4, 6,..., N-2,  and D " ^  < 0  (2.31d)  b . f o r odd N D £ >:0 or  k = 2, 4, 6 , . . . , N - l  (2.31e)  alternatively,  Br < 0  k = 1, 3, 5 , . . . , N - 2 ,  and D ~  k  N-l  where the determinants  and  DJ-I^ D  +  k  > 0 (2.31f)  =  are defined as follows.  + YJ  K  (2.32a)  ~ k'  (2.32b)  Y  -  +  -  In f a c t , D , and D. for k < N - l can be obtained from D and D „ , . , r e s k k N-l N-l XT  pectively,  as shown i n (2.33a) for odd k and (2.33b) for even k. We note In passing that the factor Q i n (2.26) can be expressed  i n terms of l\, , and , as follows. N-l N+1  2/D  2  Examples  N+l D  N  N-1 I °N+1  1  ( 2 > 3 4 )  N  >  1  L i s t e d i n the following are the constraints on the feedback  parameters obtained from (2.31) for certain low-order l i n e a r  predictors.  cd ro co  >  53  8  +1 I  25  O  8  +1  8  +1  O 8  o  8  53 OJ  CN  8  8  cs  ro 53  I  8*  co  +1 " ©  4?  8  I 53  +1  I  CM  8  I  8 +1  S  8 +1  s  8 8  CO  CO  I + 1 + L53  8* +1  +1 O 8  8* I  CO  53 8 +1  8 CM  CO  +1  I  53 8  8  II H  8* +1 CN I  8*  a  0  ± a  ±a  2  ±a  3  N-1  4  N  D:  N-3  a  l  ±  a  3  ±OL.  V4 a  D ± 3  a  0 N-3  *V2  a±  ±a N-1  D ± 2  a  l ±  N-2?C±Vl  a  l±  a  N odd  N  a,  a  N-3 N-l ± a  V2 N ±a  0L  T  a.  + 0L-  N-4  V3  N  a  i  a  o  (2.33b)  22  a)  N = 1 -1  b)  < a  N = 2 1 - a  - a  1  1 + a  - a  > 0 > 0  2  (2.36)  1 + a  > 0  1 -  -  -  > 0  1 +  -  +  > 0  2  c)  (2.35)  < 1  ±  N = 3  -1 < a  < 1  3  2 1 + a d)  + a a  2  x  3  -a  > 0  (2.37)  ,N = 4 1 - a , - a„ - a_ - a.. > 0 1 2 3 4 1 + a, - a„ + a„ - a, > 0 1 2 3 4 2 1 - a - a a - a^ > 0 2 1 + a_ + a., a. - a. > 0 3 14 4 2 2 2 2 3 l+a„+a.+2a_a.+a a„+ a. a.+a.a. -a a„a.-a_ -a. -a. > 0 2 4 2 4 1 3 1 4 2 4 1 3 4 3 4 4 3  ][  4  1  2.5  (2.38)  n  Cliannel Noise f o r Conventional Optimum Linear  Prediction  The l i n e a r predictor i n F i g . 1 i s often designed to minimize the r a t i o  2 2 /a  as given by (2.29) [7-12 ]> i n which case the DPCM 2 2 quantization error q ° / ° i s minimized with respect to {a^}, i f 2 2 L £ 8. To minimize a /a , {a^} must s a t i s f y the following set of N E  e  x  g  l i n e a r equations [24]. N p(k) «= E a . i=l 1  (k-i)  k = 1, 2,...,N  (2.39)  For t h i s c h o i c e o f {a.}, x  2 2 a */a = 1 - E a. p ( i ) e x . . l i=l N  (2.40)  S i n c e p ( k ) i s an even f u n c t i o n o f k, (2.39) and (2.40) can be combined and w r i t t e n as f o l l o w s . N Z a i=0  p(k-i) = i  -a 2la 2 e x  k = 0  0  From the s i m i l a r i t y between  Qo /o 2  e  2 x  k = 1, 2,...,N  (2.41)  (2.23) and ( 2 . 4 1 ) , one o b t a i n s  = p(0) = 1  Therefore,  (2.42)  f o r t h i s c h o i c e o f {a^} , (2.12) and (2.42) y i e l d e = (e + e ) a /a + e q m e x n 2  (2.43)  2  T h i s e q u a t i o n shows t h a t t h e e f f e c t o f c h a n n e l t r a n s m i s s i o n e r r o r s on e i s no more s e v e r e f o r DPCM than f o r PCM.  I t w i l l be seen i n Chapter I V  t h a t f o r many o t h e r c h o i c e s o f { c O , t h e mean-square DPCM can even be l e s s than t h a t f o r PCM.  channel e r r o r f o r  Thus, e a r l i e r s u g g e s t i o n s  that  t r a n s m i s s i o n e r r o r s i n DPCM a r e n e c e s s a r i l y more s e r i o u s t h a n t h o s e i n PCM a r e i n c o r r e c t . 2.6  Comparison o f DPCM E r r o r Bound w i t h R a t e - D i s t o r t i o n Bound The r a t e - d i s t o r t i o n f u n c t i o n i n t r o d u c e d by Shannon [25] d e t e r -  mines t h e minimum e r r o r a c h i e v a b l e by any communication system. F o r 2 DPCM, t h e minimum v a l u e o f t h e r a t i o a  2 la  , as g i v e n b y (2.39) and  ( 2 . 4 0 ) , i n c o n j u n c t i o n w i t h t h e minimum v a l u e o f e^, g i v e s t h e minimum mean-square  e r r o r o f the system.  I t i s t h e r e f o r e o f i n t e r e s t t o compare  this lower bound with the t h e o r e t i c a l l i m i t obtained from theory.  rate-distortion  Both one- and two-dimensional random signals w i l l be considered  i n the following. 2.6.1  One-Dimensional Random Signal The r a t e - d i s t o r t i o n  function of a Gaussian random signal x(t)  with power spectrum S(f) can be expressed parametrically  where A = {f:  R(*> - \  /  d(<j)) = / A  cbdf + / A  S(f) £ cb},  log  df  2  S(f)  A- = {f: c  as follows  bits/sec  [26].  (2.44a)  (2.44b)  df  S(f) < co} and d i s mean-square e r r o r .  At a given rate, the mean-square error obtained from (2.44) i s also a lower bound for non-Gaussian random  signals.  Assume that x(t) i s bandlimited within -W £ f £ W, deterministic  For a non-  random s i g n a l , S(f) > 0 for a l l |f| £ W. Let < | > be the  minimum of S ( f ) , as shown i n F i g . 3.  Then, from (2.44), i t can be  S(f)  0  0  Fig. 3  W  Power spectrum of x(t) with the minimum <f> m  readily shown that f o r cb < i> , the normalized mean-square error m J  e=d/a x  z  IS  -R/W e = 2  , 2W { —— x  e x  l W L-^y ^ -W  r  P  r  l n  s  ^) f  . d  f  , J '  (2.45a)  S i n c e d = 2Wcb when <p $ cb^, (2.45) i s t r u e f o r  e $ 2Wcb h m x or R  >  1 ' f  (2.45b)  = e o  W -W  J  l o  S  S 2  ( > f  d f  Note t h a t i f S ( f ) i s a m o n o t o n i c a l l y  - °Z K m  2  decreasing  (2.45c)  = o R  f u n c t i o n o f f , t h e n cb^ =  S(W) . C o n s i d e r now the mean-square e r r o r o f DPCM s y s t e m . 1  that f  = 2W.  Then  Assume  i n (2.29) can be w r i t t e n i n T o e p l i t z form;  2 a  N N I Z a. a. R ( i - i ) i=0 j=0  =  J  (2.46)  The minumum o f t h i s T o e p l i t z form i s [27]  a  2 e  ' N+1' i i V.N V  =  a  2 x  (2.47a)  1  where  i s the covariance matrix;  p  0  p  p  l  p  l 2  'N-l  l  N-2  P  0  i . e . , with  p  = p(i),  (2.47b)  N p  2  P  N-1  l  p  P  P  0  N-2 N-3 P  N-3  Equation (2.47a) can also be obtained from (2.41) by solving f o r and then substituting a  with - 1 .  This minimum value i s a non-increasim  function of N . When N i s large, we have [27] cr  2 e  = 2W exp [ ^ / J J l n S(f) df]  (2.48)  If e i s also minimized, then the minimum error achievable by DPCM i s q £  = e  q  v-^f exp [|y /_JJ l n S(f) df]}  (2.49)  °x Comparing (2.45) and (2.49), we can see that for e £ £  q  or R £ R , the q  r a t e - d i s t o r t i o n bound and the minimum mean-square error achievable by -R/W  DPCM d i f f e r only i n a factor which i s due to quantization. is  Since 2  the error bound for transmitting independently d i s t r i b u t e d random  samples at rate R , and since no p r a c t i c a l quantizers can achieve this bound, the difference between (2.45) and (2.49) may be regarded as inherent i n the quantizing process. Shown i n F i g . 4 are the s i g n a l - t o - n o i s e r a t i o v s . the rate R as obtained from the reciprocals of (2.45) f o r the r a t e - d i s t o r t i o n bound and  (2.49) for DPCM using Max's optimum and optimum uniform quantizers,  both with and without entropy coding.  The minimum p r e d i c t i o n error i s  2 assumed to be 14.35 dB below the  SNR  q  *.  It i s noted that with entropy coding,  achievable by DPCM i s approximately 2 dB below the bound.  When  fixed-length coding i s used, a degradation of 1 to 1.5 dB i s noticed f o r optimum quantizer. Optimum uniform quantizer with fixed-length coding This value i s obtained from the power spectrum of the f i r s t - o r d e r Markov process bandlimited within W = 40irf , where f i s the corner f r e o o quency.  27  R/2W, F i g . 4.  BITS PER SAMPLE  Comparison of DPCM performance with the r a t e - d i s t o r t i o n bound; a !  / a = -l4.35dB  2  2  e u-*1  00  x  has the lowest SNR .  AT R/2W = 5, f o r example, the SNR  o  f o r this case  o  i s almost 5 dB below the bound. 2 2 Although F i g . 4 i s plotted with (a /a ) „ = -14.35 dB, i t 2 2 applies also to any other value of (a / a _ ) ^ ' only necessary change 2 2 i s to add [the new value of (a / a ) „ i n dB - 14.35 dB] to the v e r t i c a l e x N-*» N  T  co  h  e  scale. 2.6.2 Two-Dimensional Random Signal For a two-dimensional random s i g n a l , such as a video- image, the rate-distortion  function with mean-square error f i d e l i t y c r i t e r i o n can  also be expressed parametrically as follows* [28].  1  R<*> = \ ff d((j>) = a where A = {f , f : x y  A  2  log  S(f 2  x'V  —f-Z-  df d f x  (2.50a)  y  - SS. [S(f , f ) -cb] df df A x y x y  S(f , f ) > d>}, a x y  2  (2.50b)  i s the s i g n a l power, S(f , f ) i s x y  the two-dimensional power spectral density, and f_ and f frequencies i n the h o r i z o n t a l and v e r t i c a l d i r e c t i o n s ,  are the s p a t i a l  respectively.  For discrete video s i g n a l s , such as those r e s u l t i n g from r a s t e r scanning and sampling, the power spectrum S(£^,£y) If  I £ W and I f I £ W , where 1/2W  i s defined within  i s the distance between two adjacent  x x y y x samples and 1/2W^ the distance between two adjacent A denote the minimum value of S(f , f ). m x' y v  lines.  Again, l e t  Then, f o r <J> $ c|> , i t can be m  e a s i l y shown from (2.50) that the normalized mean-square error i s e = 2"  R/2W  4W W x y {-^f W  a  W e x p t ^ - Z ^ x / ^ l x y x y  n S  (f ,f x  ) d f _ d f ]}  (2.51a)  S t r i c t l y speaking, (2.50) i s the r a t e - d i s t o r t i o n function of Gaussian random s i g n a l s . However, i t i s also a bound f o r non-Gaussian random signals [ 24] •  Since d = 4W W cb when cb $ cb , (2.51a) holds for x y m T  e j? 4W W x y  or  cb m  la  (2.51b)  W W R >, =r f * / . l o g . S(f , f ) df df 2 -W -W °2 x y x y x y  - 2W W l o g . cb (2.51c) x y °2 m  y T  The values of R and e i n most p r a c t i c a l  T  communication systems are such  that (2.51b) and (2.51c) are true. As i n the one-dimensional case, the error bound i n (2.51a) i s -R/2W W composed of two f a c t o r s ; the f i r s t factor, 2  x y , represents the  error bound for quantizing independently d i s t r i b u t e d random samples, and the second, which i s enclosed within  the braces,  represents the l i m i t  of redundancy reduction. Consider now the DPCM system with feedback of previous samples on the present and previous l i n e s .  Although for a l i n e - b y - l i n e scanned  image, any past sample may be used to predict the present sample, the analysis to be followed shows that only the previous samples indicated with black dot i n F i g . 5 are required to obtain the best l i n e a r prediction  U  fS  \  0 3  S s  r \  5  i-l  J-1  r  i-2'j  U  f3  r  Vj-2  ei  u  i+rj-2  C>  Fl fr e  1 u  Fig.  i-2'j-2 V l ' J - 2  Vj-1  "i+i'j-i  < •>  r  u. .  i-l'j Vr \  1J  '  Samples shown i n black dot are used for prediction  of the present sample ^y u  Assume that the number of quantization levels  L £ 8.  Then the p r e d i c t e d v a l u e , u.., o f u . . can be w r i t t e n i n terms o f  the feedback c o e f f i c i e n t s  u. . = a .  0,1  IJ  1  {a } as f o l l o w s . m,n  u. . , + a_ „ u. . +  . .. + a  1,3-2  0,2  0  „ u. . vr 0,N i,3-N  rt  + a u. , . + OL - u. .. . , + ...+ a, „ u. .„ 1,0 1-1,3 1,1 i-l,3-l 1,N i-i,j-N A  +  n  OL. _ u. ,, . + CL, - u.  M,0  i-M,j  L e t R(m,n) denote  w  . , + • • • +a  i-M,j-l  M,N  the two-dimensional  2 E { f u . . u. ] }. ij i-m,j-n J  M  Z  2  i-M,j-N  c o r r e l a t i o n , i , e . ', R(m,n) =  e  2 = E [ ( u . . - u. Y] 13 13  M N E E , „  E  u  Then t h e mean-square p r e d i c t i o n e r r o r i s  a  =  M,l  N E ,  n  . R(m-m',n-n'), m+n^O, m ' + n V O  a a . m,nm,n  m=-0 m = 0 n = 0 n = 0 n  (2.53) 2 i t can be shown t h a t 0 ' i s m i n i m i z e d i f {a } e m,n  By d i f f e r e n t i a t i o n , satisfy  the f o l l o w i n g s e t o f e q u a t i o n s  M  N  E  E  m  «  m'=0 n ' = 0  t „i m  '  R(m-m',n-n') = 0  = 0,1,..,M , n  m  n  +  n  *  0  n = 0 , 1 , . . . ,N (2.54a)  2 and  the r e s u l t i n g minimum v a l u e o f  a  2 e  M  =  is  N  E E a _ m,n m=0 n = 0  R(m,n)  (2.54b)  n  D e f i n e the o n e - d i m e n s i o n a l c o v a r i a n c e m a t r i x V^(k)  as f o l l o w s , where  2 p(m,n) = R(m,n)/o . p(k,0)  p(k,l)  p(k,l) p ( k , 0 )  p(k,N) p(k,N-l)  v (k) =  (2.55)  1  p(k,N) p ( k , N - l )  P(k,0)  31  Then, from  i n a form s i m i l a r t o  (2.54), we can express the minimum  (2.47) as f o l l o w s .  Iv]  2  2  (2.56a)  | -1| V  where  v (0)  v (i)  v (i)  •v (p)  1  V (M)  1  1  1  V (M-1)  1  1  (2.56b)  V (M)  v (0)  V (M-1)  1  1  1  and V_^ i s a m a t r i x o b t a i n e d from V by d e l e t i n g i t s f i r s t It i s noted that  row and column.  (2.53) i s a T o e p l i t z form i n two dimensions 2  and t h a t the minimum o f of M and N.  g i v e n i n (2.56) i s a n o n - i n c r e a s i n g f u n c t i o n  F o l l o w i n g a procedure s i m i l a r  3.1 o f r e f e r e n c e  t o the one used i n S e c t i o n  [27], i t can be shown t h a t when M and N approach  the minimum v a l u e o f a  2  is  e W W = 4W W e x p h — - — f * f J l n S ( f , f ) df df ] •w « x y 4W W -W -W x y x y M,N-x» x y x y  (2.57)  r  Comparing  (2.51) and (2.57), we see t h a t DPCM can a l s o remove a l l the  redundancy samples  infinity  i n two-dimensional s i g n a l s , p r o v i d e d t h a t a l l the p r e v i o u s  shown w i t h b l a c k dot are used f o r p r e d i c t i o n . I f S ( f , f ) i s s e p a r a b l e , t h a t i s , i f i t can be w r i t t e n as x y  S(f  x  , f ) = S , ( f ) S . ( f ) . then (2.57) can be s i m p l i f i e d as f o l l o w s , y 1 x 2 y ' W • M,N-+<»  { 2 W  x  e x  P 2 W - -W [  J  x  X  x  l n S  W l( x> f  d  f  ] x  H  2  W  y  e  ^2W-'^ y  l n S  2  ( f  y  ) d f  y > ]  y  (2.58)  Furthermore, i f S (f ) and S_(f ) are the power spectra of M ' - and N ^ x x /. y t  order Markov sequences,  1  r e s p e c t i v e l y , where M and N are f i n i t e integers,  then only (M+l) x (N-1) -1 previous samples are required to achieve the p r e d i c t i o n error bound given i n (2.58).  For example, i f both S , ( f ) X  and ^ ( f y )  a  r  P  e  o w e r  spectra of f i r s t - o r d e r Markov sequence,  X  then  the correlation c o e f f i c i e n t p(m,n) can be written as follows: p(m,n) = exp (-a|m| - 8|n|)  (2.59)  which has been widely used as a model for the correlation function of random video images.  In this case, only the three nearest previous  samples, i . e . , u . _ . , u. , and u . , . _ , , are required for the best i l>3 --> 3 1 l>3 l 1  1  l i n e a r p r e d i c t i o n , and the r e s u l t i n g minimum p r e d i c t i o n error i s a  2 e  = (1 - e~ ) 2a  (1 - e " ) a 2B  2  (2.60)  2 2 The values of a /a f o r certain simple p r e d i c t i o n schemes e were calculated from (2.56) by using the s t a t i s t i c s of two video images shown i n F i g . 11 and the results are l i s t e d i n Table I .  Two d i f f e r e n t  correlation c o e f f i c i e n t s were used i n c a l c u l a t i o n for each image, one obtained d i r e c t l y from measurement,  the other calculated from.(2.59). The  values of a and 3 for the l a t t e r case were obtained by f i t t i n g an expon e n t i a l curve to the 30 measured values of the correlation function as shown i n F i g . 12.  Table I shows that with the c o r r e l a t i o n function of  (2.59), the prediction using 3 nearest previous samples y i e l d s a very 2 high value of (a  2-1 /a )  i n dB, which i n fact i s the summation of the  values for prediction using only the previous sample and that using only the sample above on the previous l i n e .  This fact i s also implied i n (2.60)  When the measured values of p(m,n) are used, however, the results are not  as encouraging; an improvement of only 3 dB or so over the previous sample feedback i s seen for both images.  This shows that the assumption  of the two-dimensional correlation function given i n (2.59) f o r video images may not be a good one.  In f a c t , the correlation i n diagonal  d i r e c t i o n obtained from this equation i s much smaller than the actual value i n most cases.  Also shown i n Table I are. the values of (a  2 2-1 /a ) e  TABLE I 2 Comparison of the values of (a  2-1 /a )  i n dB with p(m,n) obtained from  (2.59) and those with p(m,n) obtained from measurement Samples Fedback Scene N. \ ^  , p(m,n)^\^^ From (2.59)  Crowd  from measurement  Cameraman  from (2.59) from measurement  Previous  Above  Previous and Above  Nearest Three  9.78  10.56  12.98  20.34  10.74  11.62  13.28  13.60  16.74  17.53  20.13  34.27  14.24  16.40  16.89  17.46  For crowd scene, a = 0.0556, $ = 0.00460, p ( l , 0 ) = 0.9569, p ( 0 , l ) = 0.9650 and p ( l , l ) = 0.9391. For cameraman scene, a = 0.0107, 3 = 0.0089, p ( l , 0 ) = 0.9809, p ( 0 , l ) = 0.9885 and p ( l , l ) = 0.9833. for prediction based on the previous sample . and the one on top, which i s also called line-and-sample feedback.  For measured values of p(m,n),  the results i n this case are seen to be almost as good as those using the nearest 3 previous samples. To obtain the minimum mean-square error achievable by DPCM f o r two-dimensional s i g n a l s , we can simply multiply (2.57) or (2.58) with the  minimum quantization error e . q  The argument i n Section 2.6.1  regarding  the minimum DPCM error and the r a t e - d i s t o r t i o n bound also applies here. In p a r t i c u l a r , with a proper correction i n the v e r t i c a l s c a l e , F i g . 4 remains v a l i d .  III. 3.1  SYSTEM OPTIMIZATION  General Optimization ProcedureWe consider now the problem of designing the system i n F i g . 1  to maximize SNR i n (2.15b). o and L ^ 8,  i n which case  Assume that R (k) = R (k) = 0 for k ^ 0, n qn i s given by (2.16),  (2.18) and (2.26), and a /a 2  by (2.29).  2  by (2.17) and  by  The following facts are of  importance: a)  depends on L , {u^},  and p ( i ) ;  p(i)  depends on f  depends only on {u^}  {v^},  and W.  g  and {v^}.  and P ( a ) ; Pg( ) For L , { c O ,  g  £  e  b)  e  I  a  s  f  g  When x(t)  changes  in Fig. 1 is  also Gaussian, independent of {cu},  depends on a l l of those factors which a f f e c t £ .  f  r  f  s  c)  and W f i x e d , £ e  m  depends only on {u.} l  and  g  and W.  In addition,  1 e depends on P . . , which depends on the b i t rate R = f log„ L. m xj s °2 m  {a.}, x  {a^}  and=W f i x e d ,  In many p r a c t i c a l s i t u a t i o n s ,  in f , W and (a^}have l i t t l e e f f e c t on p ( a ) . Gaussain and L v 8, P ( )  depends on  a  g  For L ,  {v.}. x  = E Q, where Q depends only on {a.} as shown i n (2.26) and n x e depends on the same factors which a f f e c t e . n m 2 2 d) a /o depends on {a.}, and on p(i) which depends on f and W. £ X 1 S c  The above facts motivate the following optimization procedure. 1)  F i x L , f , W, and s  2)  Determine p (a)  3)  Choose {u.} x Using p (a) e  4) 2, 2 a /a e x 5)  e  o r  {a.}. x A,  (or P ( a ) ) . e  and {v.} to minimize e + e + Qe . x q m n from step 2, choose {a.} to minimize ( E + E + QE ) r > q m n . x  Repeat steps 3 and 4 u n t i l the values of SNR which result Q  fol-  lowing repeated application of steps 3 and 4 are v i r t u a l l y i d e n t i c a l .  36  6)  Repeat steps 2-5 u n t i l further r e p e t i t i o n y i e l d s v i r t u a l l y  i d e n t i c a l values of S N R .  I f x(t) i s Gaussian, proceed d i r e c t l y to step  q  7 from step 5. 7)  Repeat the above procedure beginning at step 1 f o r new values of  L , f and W. ' s In many a p p l i c a t i o n s , some system parameters  are constrained.  Any such constraints must be maintained i n system optimization. For example, i n voice systems the quantizer i s usually constrained to be logarithmic, with the result that the only independent quantizer variables are the overload l e v e l and the companding parameter  [29]•  When the system i n F i g . 1 i s optimized, both e^ and  - Qe » n  and possibly z w i l l contribute s i g n i f i c a n t l y to e i n (2.12), unless m i s given by (3.3).  P  If this statement were not true, then £ could be  decreased, -either by -increasing -L u n t i l -e  becomes s i g n i f i c a n t , or by de-  creasing L u n t i l £q becomes s i g n i f i c a n t . 3.2  Optimization of the Quantizer The s e l e c t i o n of {u^}  and W^} i n step 3 involves the optimi-  zation of the quantizer for a fixed number of output l e v e l s L . and W f i x e d , minimization of e i n (2.12) maximizes S N R optimum {u^} • i u  =  q  in  With f  (2.15b).  The  and W^} must s a t i s f y the following equations, assuming  "L+l 3E  3E  ^  du.  I  3E  + - ~ 3u.  + Q ~ 9u.  X  3E  9v.  I  +  (3.1a)  3E  -r8v.  51  X  i = 2,..., L  1  9E  £  = 0  + Q T- - =0 ^ 8v 2  i = l,2,...,L  .  X  Substituting (2.16) - (2.18) into (3.1) y i e l d s , a f t e r some  (3.1b)  manipulation,  the following equations.  (1-Q)[v. „  2  - v  1  i - i  =  + 2.E. v . ( v . P . . - v .  2  x  j  3=1  i  j-1  3 I J  L 2 E • ~  = 1  . P. .  1.-1,3  v . ( P . . - P . . .) J i J 1-1,3  J  L u (1-Q) E ( v . - v . ) P . . / . , 3 i 13 u. 3=1 1 1  L =  1  .)]+0.S. v 3=1  2  3  (P..-P. iJ  1=2,...,L  .  .)  i-l,.1  (3.2a)  L u . p (a)da+ E [(1-Q)v.+Qv.] P . . / p (a)da e •. , 3 i 31 u . e 3=1 3 J  v  u  E  f  P  3=1  3  P (a)d  ±  ,  e  j=l,2,...,L  (3.2b)  j  For PCM, Q=l and (3.2) reduces to equations obtained by Kurtenbach and Wintz [16].  Furthermore, when the d i g i t a l channel i n F i g . 1  is noiseless, P. . 13  7^  = \ l  I0  (3.3)  x^3  i n which case (3.2) reduces tothose obtained by Max [30]. s o l u t i o n of (3.3) requires an i t e r a t i v e earlier 3.3  In general,  approach s i m i l a r to that used  [16] f o r PCM.  Optimization of the Linear Predictor The normalized mean-square error e can be minimized with r e s -  pect to the feedback parameters  by d i f f e r e n t i a t i n g e with respect to a_^  1 £ i S N i e q u a t i n g the r e s u l t i n g N equations to zero, and then solving fo {a.}.. x  Since e , e and. e are independent of {a.}, we have q m n , 1 2 2 8 e 30 e (e + e + Qe ) (-^) + ^ - . e = 0 i=l,...,N q m n da. 2 da. n 2 x a x a x x r  a  0  n  3 where  i  O  2  (—) = a a x  2p(i) +  N E a p(i-j) i=l 2  (3.4a)  (3.4b)  J  and the d i f f e r e n t i a t i o n 3Q/8a  can be obtained from (2.26). i  Because of  the complexity of Q, an e x p l i c i t s o l u t i o n f o r a^ from (3.4) i s very d i f ficult. Consider, for example, the case N=l.  From (2.12),  (2.2b) and  (2.29), we have e e = [e  +  E  q  where a=  m  and p = p^. (1 - a ) 2  +  9  y] (1+a - 2ap) 1-a  (3.5)  2  The optimum a must s a t i s f y the following equation,  (a-p) (e +e ) - (pa - 2a+p) e  2  q  2  m  n  = 0  (3.6)  I t can be seen that even for this simple case, a f i f t h order equation results. Numerical solution of {a^}  from (3.4) i s straightforward,  however, as i s demonstrated i n Chapter IV. 3.4  Optimization of the Sampling Rate In studying the effect of sampling rate, i t i s assumed that the  out-of-band d i s t o r t i o n i s n e g l i g i b l e and, hence, as i n (2.14b).  SNR  q  can be approximated  In addition, P ( ° 0 i s assumed to be independent of e  {a^}  and f . 3.4.1  s  Noiseless D i g i t a l Channels  In some p r a c t i c a l s i t u a t i o n s , the channel noise l e v e l i s s u f f i c i e n t l y low that £ I << e and E << e , i n which case one can assume ' m q c q J  1  that (3.3) i s true. For optimum or near optimum quantizers and for logarithmic —  K  quantizers, e = C 4 [29.31], where constant q q p (a). If p (a) i s Gaussian, for example, C = e e q 2 2 Laplacian, C = 4.5. When N=l and when a /a q e x r  (2.12),  (2.14) and (2.40)  yield  C depends only on q /3TT/2 and i f p (a) i s e i n (2.29) i s minimized,  o = l t  S N R  [Cqd-P )]" 2  1  In considering the dependence of  SNR  4 R / f s  (3.7)  where p = p^.  bered that p varies with f .  Let T = 1/f .  s In most cases of i n t e r e s t ,  q  on f , i t must be rememg  Then p i s a function of x.  s p(x) can be c l o s e l y approximated by the f i r s t  two non-zero terms i n the Taylor s e r i e s .  I f p i s d i f f e r e n t i a b l e at T = 0  then p(x) i s even i n x and p(x) where  a  = 1 + a  = (1/2)  2  x  2  (3.8a)  2  [d p/dx ] 2  2  0  T = 0  (3.8b)  The inequality i n (3.8b) i s true because p(x) i s maximum at x = 0. We s h a l l assume that  ^.  If a  using the f i r s t non-zero series  2  = 0, the following analysis a p p l i e s , coefficent.  The substitution of (3.8a) into (3.7) y i e l d s  SNR  =  q  f  where C-, = (-4 C a„ W ) 1 q z 3SNR ... or s  _ 1  g  3  > 0.  =  exp  (2R  ln 2/f )  (3.9)  g  Since  C. f (3f - 2R ln2) exp(2Rln2/f ) x s s s  3 SNR  (3.10)  2  and  SNR  3f  s  3f =2Rln2 s  i s minimized at f  o  either f at f  o 2  s  s  = 2W or f  s  s  1  (3.11)  s  Since 2W $ f £ R, i t follows that s  = R maximizes SNR . o  - SNR o f =2W  3C exp (2Rln2/f ) > 0  = (2Rln2)/3.  = 2W and SNR at f o s SNR  =  The difference between SNR o  = R yields = C (2W) 4 f =R s 3  R / 2 W  [1-(R/2W)  3  2W 4 R ( _  _  1  )  ]  (3.12)  From (3.12), i t follows that i f otherwise f  s  R  * 4(2W), f  = 2W maximizes  SNR ; Q  = R maximizes SNR . o  If p(x) i s not d i f f e r e n t i a b l e at T = 0, then series  expansion  about x = 0 can be replaced by expansion about a point near x = 0.  In  this case, .  where  p(x) s i +  a  ±  a  | |  (3.13a)  T  = dp/dx\^+  (3.13b)  In (3.13) we assume that a^. ^ 0, and x ->• 0 p o s i t i v e values".  +  means "as x approaches 0 from  The negative exponential correlation p(x) = e k | l T  }  b > 0, i s an example of p(x) being not d i f f e r e n t i a b l e at x = 0. An approach s i m i l a r to the one above shows that SNR i s minimized at f  s  o = R ln2 since a.. < 0, and that f - 2W, which i s also c a l l e d the 1 s  Nyquist rate, maximizes f  s  SNR  for a l l values of R >, 2 (2W).  q  If R < 2(2W),  = R maximizes SNR . o It should be noted that the conclusions made above are true  only i f the power spectrum S^(f) of quantization noise i s r e l a t i v e l y f l a t over a l l |f| $ f / 2 .  In p r a c t i c e ,  s maximum at f = 0 [32].  S (f) i s bell-shaped with a q  In p a r t i c u l a r , when K = R / f i s small, the specg  trum has a very high and narrow peak within the s i g n a l band, i n which case sampling at a rate higher than f than predicted above.  = 2W w i l l be f a r less  advantageous  Therefore, i t may be concluded that for noiseless  channel the Nyquist rate f  = 2W always maximizes SNR^, even i f the b i t rate  R i s low. 3.4.2  Noisy D i g i t a l Channels When the transmission channels i s n o i s y , SNR f o r N = 1 i s J  o  f S N R  o  =  2W  e  [ ( G  q  +  £  m  +  """"V  ( I +  a  2 a p )]  ( 3  1-a  '  1 4 )  Unless p (a) i s uniformly d i s t r i b u t e d , closed-form expression f o r E e m and  are l a c k i n g .  e ,  and  To study the dependence of  SNR  q  on f , the errors  were f i r s t calculated from (2.16)-(2.18), a was then  to minimize the term i n the brackets  selected  i n (3.14), and SNR was then obtained o  for various values of K and R.  In c a l c u l a t i n g E , e and e , the quantizer x^as assumed to be ° q m n n  logarithmic with u = 100 and overload l e v e l s chosen such that e^ i s close to i t s minimum.  The quantizer output l e v e l s were natural-binary coded  and the r e s u l t i n g binary d i g i t s were transmitted over an additive white Gaussian channel using antipodal s i g n a l s .  A more detailed description  of the quantizer and d i g i t a l channel used i n simulation i s given i n Section 4.1. Both speech and video signals were considered.  The amplitude  p r o b a b i l i t y density P ( ° 0 was assumed to be Laplacian f o r speech and e  Gaussian for video (see Section 4.2).  The c o r r e l a t i o n function P ( T )  was assumed to be exponential for both speech and video; thus p = e~ ^ s h  f  with b = 2irf  and p = 0.9753 at f = 20 x (2irf ) for video, and  o b chosen such that p = 0.89 at f Fie.  s = 8 kHz.  SNR  q  o  s 6 shows SNR v s . the normalized sampling rate £ = f /2W o s  when the d i g i t a l channel i s noiseless nals.  =  When K i s held constant,  SNR  q  for speech (a) and video (b) s i g increases l i n e a r l y with l o g £ , with  increasing by approximately 3dB whenever £ i s doubled.  held constant, 5 = 1  maximizes SNR  When  R  f o r the values of R considered.  o r e s u l t agrees with the analysis i n the previous  is This  section.  When the channel becomes noisy, and when K i s held constant,  43  SNR  q  no l o n g e r i n c r e a s e s l i n e a r l y w i t h l o g E, as shown by the s o l i d  curves i n F i g s .  E = 4 f o r K = 3,  at  I n F i g . 7 ( a ) , f o r example, S N R  7 and 8.  and the r e s u l t i n g v a l u e o f S N R  h i g h e r than the v a l u e o b t a i n e d f o r £ = 1.  K considered i n Figs.  (= 20dB) i s 5 dB  However, when K and E, are  both a l l o w e d to vary,E, = 1 i s seen to maximize S N R of  q  i s optimized  q  q  f o r a l l the v a l u e s  7 and 8.  The d o t t e d curves show the maximum S N R when R = f K i s c o n s t r a i n e d o s have the v a l u e s shoxra. When R i s c o n s t r a i n e d , E, = 1 maximizes S N R , o  to  except  f o r l a r g e v a l u e o f R and low channel e n e r g y - t o - n o i s e The envelope  tangent  t o the top p o r t i o n s o f the s o l i d  in  F i g . 2 and 8 y i e l d s the maximum v a l u e of S N R  of  E.  3.5  The optimum  q  f o r any f i x e d  curves value  v a l u e f o r K when E, i s f i x e d depends on £.  O p t i m i z a t i o n of the Bandwidth To o p t i m i z e the bandwidth W,  t i o n must be taken i n t o account.  tion.  Then, from  q  = / -  00  i n most  (2.12) and (2.15), we  CO  o  the e f f e c t o f out-of-band  Assume t h a t the sampling  which has been shown to o p t i m i z e S N R  SNR  r a t i o cb^.  rate f  =  cases i n the p r e v i o u s  have 2 £1  distor-  O O  Ul  S ( f ) d f / { ( e + e + Qe ) ( ~ ^ r ) A. S ( f ) d f + 21 m q m n 2 -W m W x q  S  m  2W, sec-  (f)df}  (3.15) Equation  (3.15) i s a v e r y c o m p l i c a t e d  f u n c t i o n o f W, because a t a c o n s t a n t  bit  r a t e R, a l l the e r r o r s e , e and e are dependent on W. In a d d i t i o n , q m n 2 2 2 2 the r a t i o a /a depends on W t o o , s i n c e , from (2.29), a /a is a 6 x e x f u n c t i o n of p ( i ) , which depends on W as f o l l o w s . p(i)  In  =/J 0  S ( f ) cos (7rif/W)df/ m  view o f the d i f f i c u l t y  U  S ( f ) df m  (3.16)  i n a n a l y t i c a l l y s o l v i n g f o r the optimum  8 NORMALIZED SAMPLING RATE g (a)  2  Fig. 7.  S  N  R  4  f ° speech as obtained from (3.14) vs. £ ; ct r  0  solid lines.  ~T  i—!—i—r  2  r  -  4  NORMALIZED SAMPLING RATE 5  fb)  = a i s optimized.  Values of K are shown next to  Dotted l i n e s correspond to the constant R values of F i g . 6(a).  lOdB, (b) <j> = 8dB. s  (a) cb = P/7f N = s so  2 4 8 NORMALIZED SAMPLING RATE £ fa) F i g . 8.  SNR  q  f o r video as obtained from (3.14), with a optimized.  lines. 8dB.  2 4 8 NORMALIZED SAMPLING RATE § fb) Values of K are shown next to s o l i d  Dotted lines correspond to the constant R\ values of F i g . 6(b).  (a) cb  = lOdB, (b) cb =  W, n u m e r i c a l approach  i s employed.  The i n p u t s i g n a l m(t) i s assumed  to be a Gaussian Markov p r o c e s s w i t h power s p e c t r a l  density  i  S (f) =  (3.17)  i + (f/f r 0  3.5.1  Noiseless D i g i t a l  Channels  When the t r a n s m i s s t i o n  channel i s n o i s e l e s s , e  = e  m  = 0 , and  n  (3.15) becomes „„ SNR  • — .-R/2W = [/3 4  n  -1 . W. tan (—) I o  r  O  2 .e v , . (—r-) + 1 a  a  Z  2  -1 ,W , - 1 ,„ ., „ tan (—) ] (3.18) s  IT  N  I  o  X  where we have assumed the q u a n t i z e r i s optimum o r n e a r optimum so t h a t C = /3IT/2. q  When the p r e d i c t o r i s o p t i m i z e d , a  N, S^Cf) and W. is,  2 2 /a depends o n l y on e x  I n c h o o s i n g N, two cases a r e o f p a r t i c u l a r i n t e r e s t ;  N = l , which has been used e x t e n s i v e l y i n p r a c t i c a l  which g i v e s an upper bound f o r S N R  a p p l i c a t i o n s , and  o f DPCM i n t h i s p a r t i c u l a r  q  that  case.  N--*»,  When  N-l, we have 2 W  a  h  X  ~ - r p = /  c o s ( f/W) . -1 ,W . T: d f / f t a n (-=—) l+(f/f ) ° o  w  n  U  . . (3.20)  Z  o  When N-*°°, we have,  a  W/f  2  e  from (2.48),  =  o  ^  1 + (W/f )  z  Q  SNTA  O  e x p  [2  _  2  f  _  ta  tan" (W/f ) X  ( 3 > 2 1 )  o  W  o  v s . 2W/R f o r N = 1 and N-*» as o b t a i n e d from  (3.18) -  (3.21)  are p l o t t e d i n F i g . 9 f o r R = 1000 f , 2000 f , 4000 f and 8000 f . ° o o o o r  Note that 2W/R = 1/K, s i n c e f  = 2W.  Three curves a r e p l o t t e d  f o r each  R; the lower one a p p l i e s when N = 1, t h e m i d d l e one when N-*», and the upper one i s t h e r a t e - d i s t o r t i o n bound.  It i s interesting  to n o t e t h a t i n each  47  case the curves have an i d e n t i c a l shape f o r a l l R . N = 1 and N 0.33.  °°, a maximum occurs at the same value of 2W/R; i . e . , 2W/R=  Thus, the optimum bandwidth W = 0.66R, which i s equaivalent to  K = 3. bit  In p a r t i c u l a r , when  It i s also noted that, the curves f o r N = 1 and N •> °° at the same  rate almost coincide, which means that the prediction based on the  previous sample i s almost as good as that based on a l l the previous  samples,  although i n this case P(T) i s no longer exponential due to bandwidth l i m i t a t i o n , SNR  o  for the r a t e - d i s t o r t i o n  bound i n F i g . 9 were calculated 0  from the following equations, which were derived from ( 2 . 4 4 ) and (3.17) with the out-of-band d i s t o r t i o n added to (2.44b). ™ ™  ,s-R/W  SNR = {2 ° r  W  ^o  1  l+(W/f r o  i  with  SNR  q  2f R = -ln2 ~  (W/f )  ~  T A N  +  f  ,W . ,  (—) ] o  +  ±  for R ^ R  1  (3.22a)  O O  — ^ — (l+/)tan (W/f )  W)  F O R  (3.22b)  R <Ro  (3.22c)  function of W, as shown i n F i g . 9.  When  bound and SNR of DPCM coincide, because o  i n this region the out-of-band d i s t o r t i o n 3.5.2  -1  tan  X  i n (3.22) i s anon-decreasing  W i s small, the r a t e - d i s t o r t i o n  N  W  (I-)}"  1  IT  o  „-^o  exp [2-2 (—)  o  1 - - tan"  SNR = 1- *s£* tan  ,„  — tan ( W / f )  dominates.  Noisy D i g i t a l Channels When the channel i s noisy,  SNRo = q{(e m+ e^ + i 1-a  SNR  q  i s given as follows.  (1+a - 2ap) -TTtan (l-) + 1 -TTr o _1  2  tan"  1  (j-)}" o  1  (3.23)  Rote-Distortion  i .2  SNR  i .3  2W/R  DPCM;  N + co  DPCM;  N =1  i .4  i .5  Bound  i—n 1—i—i .6 .7 .8 .9 1  for Gaussian Markov process as obtained from (3,18) for N = 1 o and N -> °° and from (3.22) f o r r a t e - d i s t o r t i o n bound v s . 2W/R; The channel i s n o i s e l e s s .  where p i s given i n (3.20) and e , £ and e i n (2.16), q m n respectively.  (2.17) and (2.18),  In numerical c a l c u l a t i o n , i t i s assumed that the quantizer  i s logarithmic and the channel i s additive white Gaussian as i n Section 3.4.2. Shown i n F i g . 10 i s S N R the r e l a t i v e  transmitter  power  cb  r 7  v s . 2W/R as obtained from (3.23) with = P/1000 f  W 8dB (b).  N  fixed at lOdB (a) and  oo  The cross symbols denote the values of  SNR , q  which were actually  claculated from (3.23) with integer values of K = R/2W, and the s o l i d l i n e s were f i t t e d from these symbols.  F i g . (10) suggests that when the  channel i s noisy, larger bandwidth and smaller K can give better performance at a constant b i t rate. and the b i t rate R i s increased.  This i s also true when <f> i s fixed w  IV.  ONE- AND TWO-SAMPLE FEEDBACK SYSTEMS  Because of their s i m p l i c i t y i n structure, feedback systems are used widely i n p r a c t i c a l  one- and two-sample  applications.  In this  chapter, we s h a l l study i n d e t a i l the performance of these systems,  in-  cluding one- and two-previous-sample feedback systems for speech and video signals and previous-line-and-sample feedback systems for video s i g n a l s . 4'. 1  Restrictions  on System Parameters  Some system parameters are constrained i n conducting this study. 1)  The constraints  are as follows.  The sampling rate f  n e g l i g i b l e , i n which case 2)  = 2W and the out-of-band d i s t o r t i o n i s  SNR  = 1/e  q  as given i n (2.13b).  The quantizer i s logarithmic [29,31] with u = 100 and overload  l e v e l for various values of K chosen according to Table II unless wise stated.  other-  When the overload l e v e l i s so chosen, the quantization error TABLE II  Probability Density Laplacian Gaussian  e  K  -  1  2  3  4  5  6  7  10  12  18  20  21  22  23  7  8  9  10  11  12  13  i s close to i t s minimum.  Logarithmic quantizers are f a i r l y easy to  r e a l i z e and have the advantage that the d i s t o r t i o n i s r e l a t i v e l y i n dependent of the signal s t a t i s t i c s for large values of u [29,31].  They  are p a r t i c u l a r l y a t t r a c t i v e i n voice systems, where large variations i n talker volume occur. 3)  The quantizer output levels are natural-binary coded.  That i s ,  the binary code assigned to the quantizer output l e v e l V ^ , 1 $k ?2  , is  the binary representation of the decimal integer 4)  (k-1).  The coded binary d i g i t s are transmitted over an additive white  Gaussian channel using antipodal s i g n a l s .  P  = P iJ d  ± j  d-p)  K _ d  Thus,  iJ  (4.1)  where d^j i s the Hamming distance between the codes of the quantizer output  levels v^ and v^, and p i s the p e r - b i t error p r o b a b i l i t y .  In our  case [33],  p = —  r  exp (-y /2)dy  (4.2a)  2  where <J> i s the channel s i g n a l energy to noise r a t i o . of the transmitted signal and N white Gaussian noise.  q  Let P be the power  / 2 be the power s p e c t r a l density of the  Then, <> j =  P/RN  (4.2b)  q  where the b i t rate R = f K = f log_L. s s 2 4.2  Speech and Video Samples The input to the system i s assumed to be either a speech or video  signal.  In each case,  SNR  q  calculated from (2.13) and the related equa-  tions are compared with the measured values of  SNR  q  obtained from simu-  l a t i o n using a 2.5 sec. speech sample and two video images.  The speech  sample was produced by a 29 year-old male speaker reading the sentences "Joe took f a t h e r ' s shoa bench out; she was waiting at my lawn".  These  sentences contain most of the phonemes found i n the English language and have a power spectral density t y p i c a l of conversational speech [34,35]. The two video images used i n simulation are shown i n F i g . 11. Each of these images was reconstructed from an array of 512 x 512 p i c t u r e  g elements, each picture element being represented by 2  = 256 gray l e v e l s  Shown i n F i g . 12 are the measured correlation functions, along with the least-mean-square-fitted negative-exponential v e r t i c a l and diagonal d i r e c t i o n s .  curves, i n the h o r i z o n t a l ,  These correlation functions  the fact that crowd and cameraman scenes, respectively,  reflect  contain large an  small amounts of d e t a i l s . The measurement of N SNR  =  Q  (  E  i=l  SNR  q  i s based on the following equation.  N xp  /  „  [ E  (x.  i=l  -  x  ) ]  (4.3)  Z  where N i s the t o t a l number of samples.  In the c a l c u l a t i o n of S N R , the o measured values of the correlation c o e f f i c i e n t s are d i r e c t l y used and  /v -  the amplitude p r o b a b i l i t y density, P ( c t ) , of e^ i s assumed to be either e  Gaussian or Laplacian. For speech s i g n a l s , we assume that the amplitude p r o b a b i l i t y density of of  i s Laplacian, i . e . , P ( ° 0 e  exp (-/2~  =  la])/^,  independent  This function has been shown to be a reasonable approximation  to P (°<) f ° e  r  r e a l speech samples [9,11,29,35 ].  For video s i g n a l s , P (a) i s assumed to be Gaussian, also e  dependent of {ou}.  F i g s . 13 and 14 show the amplitude p r o b a b i l i t y den-  s i t i e s of x. (p (a)) and e . , where e. = x. - p, x. 1  x t  x  in-  i '  for the two images shown i n F i g . 11.  i  i  K  l  i - l '  respectively, r  /  '  A Gaussian approximation for P ( ° 0 e  i s not unreasonable, although, as shown i n F i g s . 13 and 14, a Laplacian approximation may be more accurate for DPCM (see also  [ 7,36]), and a  uniform approximation for p (a), which i s equivalent to p (a) when = ... = 4.3  = 0, seems more appropriate for PCM (see also  [7,36,38 ])•  Simulation of Channel Errors In the simulation of the DPCM system shown i n F i g . 1, an IBM  F i g . 11.  P i c t u r e o r i g i n a l s ; 512x512 p i c t u r e elements with 8 b i t s per p i c t u r e element.  55 A : Horizontal +:  Vertical  X:  Diagonal  15  DISTANCE (a)  A • Horizontal +  ^ .6-3  O C:  .' Vertical  X : Diagonal  3.5* UJ  ct Q:  o .4-3  o  •3"!  .i-i -T  1  1  r-  -T  1  JO  [  r-  r—i  1  i  1  15  r-  20  — i — — -  25  I  30  DISTANCE (b) F i g . 12. Correlations of the pictures shown i n F i g . 11; (a) crowd scene, (b) cameraman scene. The distance of the h o r i z o n t a l scale i s r e l a t i v e to the distance between 2 adjacent h o r i z o n t a l elements,  F i g . 13.  Amplitude p r o b a b i l i t y density scene.  of the pictures shown i n F i g . 11; (a) crowd scene, (b) cameraman  58  360/67 d i g i t a l computer i s used.  In p a r t i c u l a r ,  a pseudo-random number  generator implemented by using Lehmer's m u l t i p l i c a t i v e congruence method [39] i s used to simulate the noisy d i g i t a l channel.  The pseudo-random  numbers generated are uniformly d i s t r i b u t e d within 0 and 1 and have a 30 period of 2  .  For a d i g i t a l channel with b i t - e r r o r p r o b a b i l i t y p , the  natural-binary coded quantizer output i s transmitted  (by simulation) i n  the following manner. Every time a binary d i g i t i s emitted from the natural-binary  coder,  a pseudo-random number i s also generated and compared with the value of p.  I f the random number i s less than p , then the binary d i g i t i s changed  to 0 i f i t was a 1 or vice versa; unchanged.  i f not, then the binary d i g i t remains  Since the random number i s uniformly d i s t r i b u t e d within 0  and 1, i t i s not d i f f i c u l t to see that the error p r o b a b i l i t y of the r e ceived d i g i t i s p. 4.4  One-Previous-Sample Feedback For one-previous-sample  by (3.5).  feedback system, N = 1 and e i s given  To ensure system s t a b i l i t y ,  |a| < 1.  A l s o , e i s minimized  by choosing the sign of a to be the same as the sign of p. practical situations,  In most  p £ 0, i n which case the allowable range for a  i s 0 S a < 1. 4.4.1  E f f e c t of a and cb  From (3.6), i t can be e a s i l y seen that f o r noiseless d i g i t a l channels, e = e = 0 and a = p, where a _ denotes the value of a m n opt opt which naximizes S N R . q  On the other hand, i f the channel i s very noisy,  e >> e and, since e i s usually much smaller than either or both e n q m n 2 and e [l6]> a _ = (1 - A - p ) / p , which i s less than p. q op t J  The  effect  F i g s . 15 and 16.  of a and cb on S N R  q  The g e n e r a l b e h a v i o u r  f o r other values of K .  when K = log2L = 4 i s shown i n o f the curves  remains unchanged  The curves bunch t o g e t h e r i n the r e g i o n cb  £  because i n t h i s r e g i o n S N R  lOdB,  i s l i m i t e d by q u a n t i z a t i o n n o i s e , which i s  q  independent o f cb. . The bunching t o g e t h e r o f the curves i n the r e g i o n <b = -8dB, where S N R  q  i s l i m i t e d by channel n o i s e , o c c u r s because p = 1/2  i n t h i s r e g i o n , which i s independent of cb t o o . F i g s . 15 and 16 show t h a t a decreases m o n o t o n i c a l l y from opt a = p when cb i s h i g h to a = ( 1 - , / l - p ) / p when cb i s low. T h i s b e opt opt V 2  h a v i o u r can be seen more c l e a r l y i n F i g . 17, where ct 16 i s p l o t t e d as a f u n c t i o n o f r  its  lower  asymptotic  r  cb.  I t i s noted  -yi^-  (1 -J  value,  For speech s i g n a l ,  i n F i g s . 15 and  Q  that a i s very opt A  c l o s e to  -  -  3  1-p ) / p , when cb $ 5dB, o r p ^ 6 x 10  the c h o i c e a = 0.75 appears to be a good one.  F i g . 15 shows t h a t f o r K = 4 such  a c h o i c e keeps S N R  q  w i t h i n 1/2 dB o f  i t s maximum v a l u e as cb v a r i e s from 10 to 4 dB, which i m p l i e s a v a r i a t i o n 6 i n p from 3.9 x 10 convenient digitally. reasonably  ~2 to 1.3 x 10  .  The c h o i c e 0.75 i s p a r t i c u l a r l y  when the. encoder and decoder i n F i g . 1 a r e to be For video s i g n a l ,  realized  the c h o i c e a = 0.9 i n F i g . 16 seems to y i e l d  optimum performance when <j> and p v a r y over  the range c o n s i d e r e d  above f o r speech. For s i m p l i c i t y  and convenience  c h o i c e a = 1/2 i s p a r t i c u l a r l y  desirable.  F i g s . 15 and 16 l i e s a p p r o x i m a t e l y the v a l u e o b t a i n a b l e when a  in digital  r e a l i z a t i o n , the  For this value of a , S N R i n q  midway between the maximum v a l u e and  a = 0.  When a - 0, a PCM system r e s u l t s . F i g s . 15 and 16 show t h a t when i s g r e a t e r than zero and l e s s than a c e r t a i n ' v a l u e , S N R f o r DPCM i s ° o  always g r e a t e r than t h a t f o r PCM, even when the d i g i t a l  channel  i s very  60  r r 1111111111 M 11 * 1111 > 11111111 [ i r 1111111 [ 11 MT r 11 r [ 1111 err r q i n i r i i i 11 I i i n 111111 u 11111111) 111111 .'£p  0  .2  .4 FEEDBACK  F i e . 15. °  .6  f o r speech vs. a, = a and cb = P/RN  SNR O  o(  ; N = 1, f  -L  p = p ( i ) = 0.89, K = 4.  .8  COEFFICIENT  O  = 2W = 8KHz, b  Quantizer overload l e v e l V / a  Experimentally measured values are indicated  g  = 20dB.  i n symbols.  7  o  = 0 . 9 d 0 9  P  03 o  0.9569  Speech O  Crowd  J  Cameraman 0 . 8 9 1 0  -}  r~i—i—i—i—|—i—i—i—i—i—i—i—i—i—|  , -T—i—i—i—i—i—i—i—i—I—i—i—i—i—i—i—i—i—i—I—i—i—i—i  °-5  0  10  5 0,  15  dB  F i g . 17. Optimum value of a v s . cb.  P =  0 . 9 8 0 9  0 . 9 5 6 9  o  Speech  —I  Crowd  0 . 8 9  Cameraman  CO T  1  1  -5  1  1  !  1  1  1  I  0  1  !  1  1  1  1  1  1  1  11  T—i—i—i—i—I—r 1  5 J0O dB  1  1  1  1  1  1  1  p  10  F i g . 18. a v s . c b ; When 0<a< a , SNR of DPCM i s higher than SNR of & ™ » max o max n  m  1 15  noisy.  Let a denote the maximum value of ex for which SNR of DPCM i s max o  greater than that of PCM. Then, a can be obtained by equating e i n max (3.5) to (e + E + e ), the normalized mean-square error of PCM. Thus, q m n ^ °max  m u s t  s a t i s r  (e  q  y  +  the following equation:  E  )(a - 2p)(l - a ) + 2(u - p)e =0 m max max max n  (4.4)  2  '  It i s noted that when the d i g i t a l channel i s very noisy, e >> ( E + e ) ' n q m and a = p. On the other hand, when channel noise l e v e l i s very low, max 6  e  q  J  J  + e >> e and a = 1, -1 or 2p. Obviously, i f p < 0.5, m n max  = 2p.  If p :> 0.5,  of our i n t e r e s t .  then a  max  then a = 1 , since a = -1 i s outside the range max max " ( S t r i c t l y speaking, a i s not allowed to take the value  1 for s t a b i l i t y reasons. Fig.  18 shows a  max  However, a = 1 can be interpreted as a ->• ] max max as a function of d> for the speech and video signals  considered i n F i g s . 15 .and 16. gives higher  SNR  q  In any case, DPCM with 0 < a < p always  than PCM, regardless  the noisiness of the channel.  This range of a increases when <> j >. 5dB and reaches the f u l l  range,  i.e.,  0 $ a < 1, when <> j ^ lOdB. The symbols i n F i g s . 15 and 16 indicate the experimentally measured values of  SNR  q  obtained by using (4.3).  These results  agree  almost p e r f e c t l y with those calculated. 4.4.2  S e n s i t i v i t y to Variations i n Signal  Statistics  Variations i n signal s t a t i s t i c s must be considered i n system design.  Deviations i n P ( o t ) of the sort encountered i n practice w i l l £  normally have a r e l a t i v e l y small effect on S N R , p a r t i c u l a r l y i f the q  quantizer i s logarithmic. 2  through changes i n follows.  CT e  Variations i n p ( k ) , however, w i l l affect  2  /°  x  • Define the s e n s i t i v i t y c o e f f i c i e n t  as  SNR  Q  64  .3 A. =  1  From (2.12) and  SNR  -  o  2  which i s independent  2  i  =  I  | 3 (a /a )/3p. |  1  2  VW  (4.5)  o f cb.  Substituting  (2.29a) i n t o N  j  '/  +  a  *  2  j-U In the case N = 1, we A^ = 2 a / ( l + a  1 $ .1- $ N  2  N  k^o  2  1 $ i sS N  have  N-j A  o  3P.  (2.12), we  A. = (o /o )  SNR  1  (4.6)  (4.6) y i e l d s  N-j  * V W J V  1  $ 1  j-1 K-0  *  N  ( 4  - 2ap)  2  (4.8a) (4.8b)  2  The bound i n (4.8b) decreases r a p i d l y as a decreases from u n i t y ,  if  F o r example, i f a = p = 0.89,  and p = 0.89,  a = 0.75  then A^ = 2.78. if  then &  1  = 6.09,  then A^ = 8.56,  = 20.5,  and i f a = 0.75  decrease SNR  o  .  p o s i t i v e d i r e c t i o n always a = 0.5  4.4.3  SNR  q  necessarily  F i g . 19 shows the change i n S N R as a f u n c t i o n ° o b  v a r i a t i o n of p when p = 0.89.  that  the s e n -  r e l a t i v e to changes i n p, as w e l l as to changes i n <j>.  s h o u l d be noted that v a r i a t i o n s i n p do not  It  whereas  Therefore,  choosing a to be l e s s than i t s optimum v a l u e f o r p = 0 reduces s i t i v i t y o f SNR^  0.89,  and p = 0.9569,  S i m i l a r r e s u l t s a l s o o c c u r when p = 0.9809.  A^ = 11.8.  whereas  and p =  and i f a= 0.5  as does  On the o t h e r hand, i f a = p = 0.9569, A.^ = 22.7,  and p = 0.9569, ^  a = 0.90  7 )  have  £ 2a/(1-a )  A^ i n (4.8a).  '  I t i s seen that  increases  SNR . q  deviation  This  of the  o f p i n the  f i g u r e a l s o shows  i s l e a s t s e n s i t i v e to changes i n p . v e r s u s Number o f Q u a n t i z e r Output  F i g s . 20 and 21 show S N R  q  Bits  as a f u n c t i o n  of the number o f  quantizer  65  F i g . 19.  % change i n SNR p= 0.89.  v s . % v a r i a t i o n o f p f o r a =0.5, 0.75 and 0.89;  output b i t s K when a = a , when a i s otpimized assuming p = 0, and opt . when a = O(PCM).  The upper curves i n each set of three applies when  a  i s optimum, the middle curves when a i s optimized assuming no channel e r r o r s , and the lowest  curves f o r a = 0.  sample feedback DPCM r e l a t i v e  The maximum improvement of previous-  to PCM i s approximately  7dB f o r speech  and 13dB f o r video. An optimum value f o r K when channel i s noisy i s seen to e x i s t in  Figs.  20 and 21, as explained i n the l a s t paragraph of Section 3.1.  Even i f the r e l a t i v e  transmitter power  cb = P/7f N increases l i n e a r l y s s o with K, i n which case p i s constant, SNR i s maximized at some f i n i t e ' o value of K because, the quantizer overload l e v e l , being near the value r  r  for which e i s minimized, increases with K and causes e to increase q n with K.  In f a c t , i f the overload l e v e l i s chosen to minimize e instead  of e .for a given 6, SNR w i l l increase monotonically with K when p q o i s held constant. In F i g s . 20 and 21, when K and a are optimized, SNR may be s i g n i f i c a n t l y higher than when ot i s optimized assuming p = 0. imum obtainable  SNR  q  The max-  for a DPCM system i s seen to be considerably  larger  than that f o r a PCM system operating over the same d i g i t a l channel, even if  the channel i s noisy. It i s also seen from F i g s . 20 and 21 that unit v a r i a t i o n of  K from i t s optimum value can cause considerable 4.5  change i n SNR .  Two-Previous-Sample Feedback When N = 2, (2.12), (2.26) and (2.29) y i e l d 1 £=[£+£  q m  +  '2  (ct +l) (c^+CLj-l) ( a - a - l ) 2  2  1  +  2 ( ^ 0 1 ^ )  (4.9)  67  NO. OF QUANTIZER F i e . 20. °  SNR  o  OUTPUT  f o r speech vs. K and < j > =P/7f N s s o  BITS,  K  f o r previous-sample  feedback  systems when a i s optimum, a i s optimum assuming no channel e r r o r s , and when a - 0 (PCM).  NO. OF SNR  QUANTIZER  OUTPUT  f o r crowd scene v s . K and A =P/7f N s s o  o  Y  BITS,  K  f o r previous-sample feedback r  systems when a i s optimum, a i s optimum assuming no c h a n n e l e r r o r s , and when  u  = 0  (PCM).  In order for the. decoder i n F i g . 1 to be stable, must be constrained by the i n e q u a l i t i e s given i n (2.36).  and These inequal-  i t i e s define the region of s t a b i l i t y to l i e inside the triangle shown i n F i g s . 22 and 23, which clearly show the dependence of when K = 4.  SNR  q  on  Curves s i m i l a r to those i n F i g s . 22 and 23 r e s u l t  other values of K.  and for  We note i n passing that the curves i n F i g s . 15 and  16 can be obtained d i r e c t l y from those i n F i g s . 22 and 23 by setting  a  2  = 0.  4.5.1  Effect of a^,  and < > j  Consider f i r s t the case when error p r o b a b i l i t y p = 0, i n which case e = E = 0 m n E = E  q  and  ( 1 + a, 1  2  2 + a „ - 2a,p 2 11  - 2a_p„ + 2 a , a „ p , ) 2 2 1 2 l  n  (4.10)  Thus, i t can be readily shown that the locus of constant centered about the point a^ = a^ and a lc  =  P  °2c  =  (p  a  2  SNR  q  i s an e l l i p s  = <*2> here C  w  l ( -P ) ( -Pi ) 1  and 2  2  /  1  (4.11a)  2  „ „ " P )/(l-P! )  (4.11b)  x  The semimajor axis of the e l l i p s e has length /c/(1-p^) and l i e s along the l i n e a, + a. = a.. + a„ : the semiminor axis has length /C/(1+p,) 1 2 Ic 2c l and l i e s along the l i n e a^ - a^ = a^^ - c^^,  C = (e/e  Note that a  lc  and a  ) -  2c  [1 - (  Pl  2  + p  2  2  - 2  where  P ; L  2  p )/(l 2  equal the optimum values of a  1  P l  2  )]  (4.12)  and a when p = 0, 2  and that the second term in the square brackets i n (4.12) equals  the  f°, -0.89 P, =0.65  F i e . 22. &  SNR  f o r speech vs. a and a • K=4, f =2W=8KHz, V / =20dB. o 1 2 s e Experimentally measured values of SNR are shown by the " x " symbols.  A  (a) cb = 10dB, (b) cb = 6dB.  7.1 =0.9569 fi =0.9009  - i — i — i — i — i  1—i  1—r—i  -1  T  i  T  I  I  l  T""^  I  I  l  1  I'  I  1^'  0 FEEDBACK COEFFICIENT ol, (a)  P, =0.9569 P = 0.9009 2  FEEDBACK COEFFICIENT ol  F i g . 23A.  SNR  (b)  for crowd scene vs. a. and a„; K=4, V/a =20dB. o 1 2 e lOdB, (b) cb=6dB.  (a) <f>=  72  P, - 0.9809 p = 0.9635 2  28.75 28.5  FEEDBACK COEFFICIENT oi) (a)  ft = 0.9809 f> =0.9635 2  FEEDBACK COEFFICIENT d (b)  F i g . 23B.  SNR  f o r cameraman scene vs. a., and a • K=4, V/a =20dB. o 1 2 e lOdB, (b) <j>=6dB.  (a) < * > =  2  r e s u l t i n g minimum v a l u e o f  /a  b > 0, t h e optimum c h o i c e f o r  2  . When p = 0 and p (k) = exp (-b|k|),  and  —b = e and  is  = 0, as n o t e d  elsewhere.[24,40]• When t h e d i g i t a l c h a n n e l i s n o i s y , t h e optimum v a l u e s o f and cx„ no l o n g e r e q u a l a, and a , and t h e l o c i o f c o n s t a n t SNR , as I l c Ic o n  shown i n F i g s . 22 and 23, a r e no l o n g e r e l l i p t i c a l .  I t i s n o t e d t h a t when  <j> d e c r e a s e s , t h e optimum p o i n t (OL , a„ )• a t w h i c h SNR l o p t 2opt o Y  s h i f t s away from the s t a b i l i t y boundary toward  i s maximized  the center o f the t r i a n g l e .  T h i s b e h a v i o u r i s more c l e a r l y seen i n F i g s . 24 and 25, where t h e optimum p o i n t s f o r v a r i o u s v a l u e s o f co a r e denoted b y " x " . A l t h o u g h t h e decoder i n F i g . 1 i s s t a b l e as l o n g as ct^ and l i e i n s i d e t h e t r i a n g l e , t h e r e i s no p o i n t u s i n g t h e l i n e a r p r e d i c t o r if  the v a l u e s o f a, and a_ chosen y i e l d an SNR s m a l l e r than t h a t f o r 1 2 o FCM. Figs. 24 and 25 show t h e a r e a w i t h i n w h i c h SNR o f DPCM i s g r e a t e r o  than SNR o f PCM. o  I t i s n o t e d t h a t t h e a r e a i n c r e a s e s when <J> i s i n c r e a s e d ,  and when <j> $ 10 dB, the boundary o f t h e a r e a a l m o s t c o i n c i d e s w i t h t h e s t r a i g h t l i n e cx^ + of t h i s l i n e .  = 0 and t h e p a r t o f t h e t r i a n g l e t o t h e r i g h t  T h i s i s p a r t i c u l a r l y t r u e f o r v i d e o s i g n a l s as shown i n  F i g . 25. When <j> i s l a r g e , e » e and e >> |e I . Then E can be apq n q m p r o x i m a t e d by (4.10). L e t t i n g E i n (4.10) e q u a l E ^ , we have 1  2 a  Normally,  l  and p  proximated  2  ~  a  a  i  p  l  ~  2 a  p 2  2  +  2  a  l 2 l a  p  =  ^  .(^«13) (4.13) can be ap-  as f o l l o w s .  1  +  2  a r e c l o s e t o u n i t y , i n which case  (a  Since  r  2 +  2  1  -  + a ) (a + c* - 2) = 0 2  1  2  2 = 0 i s outside the s t a b l e r e g i o n , i t f o l l o w s that  (4.14)  FEEDBACK PARAMETER oC Fig. 24.  Locus of S N R  q  }  w h i c h i s e q u a l t o t h a t o f P C M f o r speech.  denote the v a l u e s  of cx^ and  w h i c h maximize  SNR  q  The  symbols  f o r v a r i o u s v a l u e s o f cb.  75  FEED8RCK PARAMETER c<. (a)  F i g . 25. .  Locus o f SNR  w h i c h i s e q u a l t o t h a t o f PCM f o r t h e o  crowd scene (a) and cameraman scene ( b ) . The " x " symbol denotes t h e v a l u e s . o f SNR  f o r t h e v a l u e o f cb shown.  and  that  maximize  CLj + a  ?  = 0 i n c o n j u n c t i o n w i t h the r i g h t - h a n d s i d e o f the t r i a n g l e d e f i n e s  the a r e a w i t h i n w h i c h DPCM y i e l d s h i g h e r S N R t h a n • o  PCM.  J  F i g s . 26 and 27 g i v e the curves on w h i c h and one-previous-sample  feedback  q  f o r both  two-  systems are e q u a l f o r a g i v e n <b.  each curve S N R ^ would be h i g h e r f o r the former. performance i s concerned,  SNR  the use o f  As f a r as the  Within  system  can be j u s t i f i e d o n l y i f  and  chosen w i t h i n the a r e a bounded by t h e s e c u r v e s , a l t h o u g h o t h e r  a r e  choices of  and  may  be d e s i r a b l e f o r s e n s i t i v i t y  reasons.  It is  i n t e r e s t i n g to n o t e t h a t f o r speech the e n c l o s e d a r e a w i t h i n a s i n g l e curve i s l a r g e s t when <>j i s l a r g e , whereas f o r v i d e o the o p p o s i t e i s t r u e . I n p a r t i c u l a r , when <f)=8dB f o r the crowd scene and <{>=10dB f o r the cameraman s c e n e , the a r e a i s almost z e r o , w h i c h i n d i c a t e s t h a t i n t h e s e cases i s almost no v a l u e s f o r  w h i c h we  can use to improve  T a b l e I I I shows improvement i n N = 2 i s used, r a t h e r than N = 1. 2.73 The  SNR  q  SNR  Q  there  .  f o r speech and v i d e o when  F o r speech the maximum improvement o f  dB o c c u r s when p = 0 and the improvement decreases as p i n c r e a s e s . c o r r e s p o n d i n g maximum improvement f o r v i d e o i s 0.68  when p = 1/2  f o r the cameraman scene.  dB and  occurs  There seems to be l i t t l e  i n u s i n g more t h a n one sample o f feedback  advantage  f o r v i d e o samples on the same  l i n e , even when the c h a n n e l i s n o i s y . TABLE I I I Improvement i n SNR^ when N=2 o v e r N = l --  *  00  0  p  Speech Crowd Scene  dB  3.9xl0~  8 dB 6  1.9xl0~  6 4  4 dB  dB  2.4xl0"  3  2  1. 3 x l 0 ~  2  0  dB  3.8xl0~  2  dB  7.9xl0  2.73  2.66  1.53  0.47  0. 29  0.26  0.23  0.14  0.13  0.02  0.12  Q. 20  0.20  0.20  0.05  0.20  0.50  0. 67  0.67  0.68  Cameraman 0.006 Scene The  10  \J-  feedback  c o e f f i c i e n t a, f o r N=l i s o p t i m i z e d ;  K=4.  - 2  L  0.5  F i g . 26.  0  Locus o f  SNR  0.5 1.0 FEEDBACK PARAMETER ctj  q  1.5  2.0  w h i c h i s e q u a l t o t h a t o b t a i n a b l e from p r e v i o u s - s a m p l e  feedback system f o r t h e speech  sample.  For speech, s i g n a l ,  SNR  sample d e s c r i b e d i n S e c t i o n 4.2  q  was a l s o measured u s i n g the speech  f o r various values of  the r e s u l t s a r e shown i n F i g . 22.  and a^,  I t i s n o t e d t h a t the measured  and values  agree v e r y w e l l w i t h those o b t a i n e d from c a l c u l a t i o n s . 4.5.2  S e n s i t i v i t y to V a r i a t i o n s i n S i g n a l S t a t i s t i c s Changes i n SNR caused by v a r i a t i o n s i n p. can be o b t a i n e d ° o x  (4.7) as f o l l o w s , where  A  x  = 2 ^  from  i s d e f i n e d as i n ( 4 . 5 ) .  ( a - 1)|/A  (4.13a)  2  * 8/A m  (4.13b)  = 2|a |/A  (4.14a)  $ 2/A  (4.14b)  and A  2  2  m where  2 A = 1 + a  2 + a  1  9  and A  m  = 1 -  Z P ] L  2  - 2a P 1  9 -p  z 2  1  - 2a p 2  2  +  2 0 ^ ( 4 . 1 5 a )  9 + 2  Z P ; L  p /(p 2  - 1)  2  (4.15b)  I f a, and a„ are so chosen t h a t S N R i s maximized when p = 0, 1 2 o t h e n A becomes v e r y s m a l l , w i t h the r e s u l t t h a t s m a l l v a r i a t i o n s i n p^ and/or P P  2  2  = 0.65  can cause l a r g e d e v i a t i o n s i n  SNR .  and p = 0, a  = -0.6835 maximize  w h i c h case A^ = 45 and A then A^ = 30 and A  2  = 8.  = 1.4983 and a 2  = 12.  Q  F °  R  speech w i t h p^ =  I f we choose ot^ = 1.25  Therefore,  cx^ and  SNR , q  0.89,  in  and c* = -0.5, 2  can be chosen t o y i e l d  n e a r optimum performance w h i l e r e d u c i n g c o n s i d e r a b l y the s e n s i t i v i t y o f SNR  o  t o v a r i a t i o n s i n p . , as w e l l as cb. x  80  4.6  P r e v i o u s Line-and~Sample-Feedback When x ( t ) i n F i g . 1 r e s u l t s from r a s t e r - s c a n n i n g a t w o - d i m e n s i o n a l  v i d e o image, then the sample r i g h t above may be used, a l o n g w i t h the p r e v i o u s sample, t o improve S N R , w h i c h i s u s u a l l y r e f e r r e d t o as a p r e q  v i o u s l i n e - a n d - s a m p l e - f e e d b a c k system [ 7 ].  I n t h i s c a s e , cx^ and cx^ a r e  the o n l y non-zero v a l u e s o f {cx^}, where N i s the number o f samples p e r l i n e , w h i c h i s n o r m a l l y much g r e a t e r t h a n 1.  a  2.2 a e  . , 2 . 2 = l + a.. + ex I N  2  From ( 2 . 2 9 ) , we have  Vi,o ~ Vo,i 2  +  2  W i , i  (  4  -  1  6  )  where a  i s the s i g n a l power and, f o r s i m p l i c i t y , p. . i s used to denote i >3 P(i,j) = R ( i , j ) / . From ( 2 . 2 6 ) , where cx = 1 a 2  Q  -1  0  cx^  -1  .  0  °N  % °  -1  a  0  a  -1  0  1  • '  ° K  N  "N °  0 (4.17)  Q = . -1 a  N  0 0  °  a  N  ^  »  •  •  °  -1  0  a,  -1  Note t h a t the numerator i s an ( N - l ) x ( N - l ) d e t e r m i n a n t w i t h 3 non-zero elements i n each row e x c e p t the f i r s t one, and the denominator i s an (N+1) x (N+1) d e t e r m i n a n t w i t h 3 non-zero elements i n each row o r column. 4.6.1  S t a b i l i t y C o n s t r a i n t s on cx^ and cx^ From (2.20b) the p r e d i c t o r t r a n s f e r f u n c t i o n H(z) i s  H(z) = 1 - cx^z I t f o l l o w s from (2.31a) and (2.31b)  - cx^z that  (4.18)  81  1 - ct^ - ct^ > 0 and 1  - CL I  - a N  > 0  and  1 +  and  1  -  + CL I+  The t h i r d c o n s t r a i n t i n (2.31) r e q u i r e s (2.33). a  S e t t i n g a„  a  3  =  -  > 0  f o r even N  a > 0 N  (4.19)  f o r odd N  T  (4.20)  the c a l c u l a t i o n of  ^~from  = 0 i n (2.33) and e l i m i n a t i n g cx^  i n the l e f t - h a n d h a l f o f t h e ( N - l ) x ( N - l ) d e t e r m i n a n t , we can reduce  i t t o an M x M d e t e r m i n a n t as f o l l o w s , where M = N/2 i f N i s even and ( N - l ) / 2 i f N i s odd.  i e± ±  a  3 ±  !  3  "  1  +  a  0  N  A  !  a  l  A  1 • •  V N  N  l  a  0  -l+a j  i  | ' •  a N 2  a  a  2 2  2  i  0  4-i  i  a  M-l„+  a 3 ± j a 3— 1 . . 2  i  l  . .  a  a  a  M--3 2 l °»  a  M-4 2 l N M-5 2 l N A  a  a  A  e-  1  M-2 2 l N 2 M-3 l "N M-4 2 l N A  A  M (-1)  (4.21) t  0  0  0  0  . .  0  0  0  0  . .  2 "  1  +  N  A  a  l  "  1  +  A  N  The s u b d e t e r m i n a n t s shown by dashed l i n e s i n (4.21) denote e i t h e r -I-  -f*  -H  4-  4-  T  c  + w h i c h case 3  4-  i n w h i c h case 3— = 4- ct_ , o r -D„—, D.—, -D,—, — N 2 4 6 2  -D_—, D —, 3 5  D^—,  ., i n  + j_°<N + °JJ • To c a l c u l a t e t h e s e d e t e r m i n a n t s , we can  — =  a  further eliminate  the s u b d i a g o n a l formed by a^, and t h e n m u l t i p l y t h e  d i a g o n a l elements o f the r e s u l t i n g t r i a n g u l a r d e t e r m i n a n t . L e t u , 1 £ m S M, denote the p r i n c i p a l d i a g o n a l elements o f mm the r e s u l t i n g M x M t r i a n g u l a r d e t e r m i n a n t . Then i t can be shown +  u  u  = -1 +3-  -1 + cc^  that  f o r even N (4.22a)  -1 +  K l  a  N  + a  N  f o r odd N  U  22  =  _ 1  U  33  =  _  u  1  " \  %  +  " l a  +  a  N  ~  "  2  l  a  a  i  2  /  2 / u  u  l l  22  2 2 2 = -1 - a. + OL - a, /u .. , 1 N 1 m-l,m-l  mm  (4.22b)  t  Note t h a t (4.22) i s an i t e r a t i v e e q u a t i o n .  The d e t e r m i n a n t  can t h e n  be c a l c u l a t e d from u ^ as f o l l o w s .  rt-iw?  ' (-1)^  < +i)/2 k  n  ; /  T  4  m  k/2 (-1)  k  /  =  u  k = 1,3,5,...,N-1,N even  mm  (4.23a)  1  2  n m=l  u mm  k = 2,4,6  N-1, N odd (4.23b)  I t f o l l o w s from (4.23) t h a t Item (3) i n (2.31) i s e q u i v a l e n t t o u  < 0  for  m = 1, 2, 3., ..., M  mm  (4.24)  .  The c o n s t r a i n t i n (4.24) i s based on (2.31c) and ( 2 . 3 1 e ) .  S i m i l a r con-  d i t i o n s can a l s o be o b t a i n e d f o r the a l t e r n a t i v e form i n (2.31d) and (2.31f). T h e r e f o r e , i n o r d e r f o r the decoder t o be s t a b l e , must s a t i s f y  and  (4.24) and (4.19) o r ( 4 . 2 0 ) , depending on N even o r odd.  F i g . 28 shows t h e a r e a f o r w h i c h these c o n d i t i o n s  are s a t i s f i e d .  It is  i n t e r e s t i n g to n o t e t h a t the c o n d i t i o n u < 0 reduces t h e a r e a o f t h e s t a b l e mm r e g i o n whenever m i s i n c r e a s e d ,  and i f m i s s u f f i c i e n t l y l a r g e , t h e s t a b l e  a r e a converges t o a square bounded by t h e f o l l o w i n g s t r a i g h t l i n e s f o r b o t h even and odd N. 1 + ^ - ^ = 0 1 - a - c* = 0 1  N  (4.25)  F i g . 28.  S t a b i l i t y boundary  f o r p r e v i o u s l i n e - a n d - s a m p l e feedback systems,  (a) even N, (b) odd N.  1 + a. + 1  0  =  OL  N  1 '- a- + a„ = 0 1 N 4.6.2  E v a l u a t i o n of Q S i n c e the numerator i n (4.17) i s e q u a l t o +  > w h i c h has been  e v a l u a t e d i n t h e p r e v i o u s s e c t i o n ( s e e ( 4 . 2 3 ) ) , t h e f a c t o r Q can be e a s i l y e v a l u a t e d i f we can a l s o e x p r e s s t h e denominator i n ( 4 . 1 7 ) , w h i c h i s + + e q u a l t o D^_^/2, i n a form s i m i l a r t o D _ i n (4.23). N-1 M  1  By e l i m i n a t i n g a , and a„ i n t h e l e f t - h a n d h a l f and below the 1 N J  b  +  p r i n c i p a l d i a g o n a l o f the (N+1) x (N+1) d e t e r m i n a n t -1+3  a  +  0l  e  14-  l  +  a  2  a  0  D  N+1  (-D / 2  1 -  -1+a  'N  a  l  a  M + x  3  M-l 2 l N a  M-2 2 °1 N  M-3 2 l %  a  M+l  (4.26a)  a!  o  0  where a = -1 + a.  1  and  M-2 2  2  we o b t a i n  2  0  0  0  0  0  0  a (l  2  + CL , N  1  T  l  V N  "  1 + a  2  i  2 2  V N i N a  A  l o - a  2 1  + a  N  2 ),  N even  "N  -  ,, 2  0  (4.26b)  N odd  + CL.  ' "N  E l i m i n a t i n g a g a i n t h e s u b d i a g o n a l e l e m e n t s , we o b t a i n  2  D  N+1  / 2  2 i V l  M+l M-l =- ( n u ) ( u . + a ) ( 1 - a ) [ - l - a + a / 2 , mm MM 1 1 I N 1 - a, m=l 2  a  2  +  o  t  "MM  +  a  2 2 l V  f M  « (-1)  M + 1  M-l (H u  m=l  m m  )  [(-iV+a/)  u  M  M  -2a ] 1  2  l  (4.27)  85  where u i s d e f i n e d i n (4.22), b u t i n t h i s case u „ mm ' 11 s i g n i n (4.22a).  M  M =  N-L  n  (-1)  „ m=l  (4.28) mm  D,  'N-I  Q =  1 + a 1  N+1  2  -  OL,  (4.29)  2  2a.. /u.„, 1 MM  +  N  can be c a l c u l a t e d by i t e r a t i o n s as shown i n ( 4 . 2 2 ) . The term  as  u  +  2  Therefore  where  J  From ( 4 . 2 3 ) , we. have  + D  takes o n l y the "+"  can a l s o be e x p r e s s e d by a c o n t i n u e d  fraction  follows. 2 "l "MM  2  C  c c (M-l) y fractions (4.30) c -  c -  where c = ~1 - a, I the e x p a n s i o n  2  + ct N  2  .  -1 +  This continued f r a c t i o n i s very s i m i l a r to J  2 2 1/2 o f [c - ( c - 4a^ ) ]/2 as shown i n t h e f o l l o w i n g .  Since [c - ( c - 4 a 2  )  2 1  1 / 2  ]  [c + ( c - 4 a 2  2 1  )  1 / 2  ]  = Aa  (4.31)  2 ±  we have [c - ( c - 4 c t 2  2 1  )  1 / 2  ] / 2 = c - [c + ( c 2  4a  2 1  )  1 / 2  ]/2  2 _l  a  = c 2 ^1  (4.32) 2 • l a  c T h e r e f o r e , by comparing (4.30) and ( 4 . 3 2 ) , we can e x p e c t  that i f N i s  increased, ^  ]/2 (4.33) 2 2 1/2 The s u b s t i t u t i o n o f u ^ i n (4.29) by [c - ( c - 4cx^ ) ]/2 y i e l d s n - z - i j . Q = (1 + a  ^ ±  = [(1 - a  ±  +  + a ,  ^ N  [c - ( c - 4 a 2  T - 2 a  o - 2 a  2  x  - c^) (1 - a  ±  2  N  2  1  )  1 / 2  - o2 ^ a 2.-1/2 ) 2  N  + ojj) (1 + a  ±  - o^) (1 + ^  +  « )  ]  _  1  /  2  N  (4.34) The f a c t o r Q g i v e n i n (4.29) has been p l o t t e d i n F i g . 29 as a f u n c t i o n of N f o r t h r e e s e t s o f a, and OL.. I N  I t i s seen t h a t f o r each s e t o f a, 1  and a^, the v a l u e o f Q decreases when N i n c r e a s e s , and reaches  a constant  when N i s g r e a t e r than 40 f o r t h e upper two c u r v e s and 10 f o r t h e l o w e r two c u r v e s . (4.34).  The c o n s t a n t , i n f a c t , i s the same as t h a t o b t a i n e d from  Curves f o r o t h e r v a l u e s o f  s i m i l a r behaviour.  In general, i f  and cx^ a r e found t o have v e r y and  a r e n o t too c l o s e t o t h e  s t a b i l i t y boundary d e r i v e d i n S e c t i o n 4.6.1, t h e a s y m p t o t i c v a l u e s w i l l be approached r a p i d l y as N i n c r e a s e s . For most r a s t e r - s c a n n e d v i d e o images, t h e number o f samples  taken  i n one l i n e i s i n t h e o r d e r o f h u n d r e d s , i n w h i c h case the e x p r e s s i o n o f Q g i v e n i n (4.34) i s v a l i d , even i f bility  boundary.  4.6.3  E f f e c t o f cx^, cx^ and cb  and ct^ a r e v e r y c l o s e t o t h e s t a -  The s u b s t i t u t i o n o f (4.16) and (4.34) i n t o (4.12) y i e l d s  87  73  oo-g CO-3 in-a  lod, - 0.2690 [oL = 0.7240  cn  N  'c&,  =  .d =  0.4291 0.5621  N  o CO  CD  Mi =0.45 cn-4  \<*>\ =0.3725 [cC . = 0.5 N  j i  1  i i IMM  ip  2  i inmt}niiiiiii|iriin!npvitB|'iivi|iiii]i(ii|mi| • r f r !  3  4  5  6  8  N  i i i 111)  10  Hiiim[ii»iiiii|iwiiw|ni&.. ... .... ... r  2  3  4  5  6  |  |  8 1 0  Q  F i g . 29. The f a c t o r ^ f o r p r e v i o u s l i n e - a n d - s a m p l e  feedback DPCM as o b t a i n e d  from (4.29) v s . N f o r v a r i o u s v a l u e s o f a, and a.,. I  N  88  = [e + e  ] ra + /(1-cy-c^) ( l - a + a ) (1+c^-o^) (1+a^c^)  q  1  +  2  a  iVi,i  (4  1  1  V  < P  N  0,1 " l , 0 l , l  = ( i p  p  )  - o,i i,i p  > 0  i i,o p  -  35)  ( o r c o n s t a n t e) i s an e l l i p s e  q  Ic  p  2 a  and CL, = CL, , where  c e n t e r e d about t h e p o i n t a, = a.,  =  +  ^Vo.P  "  When p = 0, t h e l o c u s o f c o n s t a n t S N R  °lc  d+4 V  N  p  /  (  HSIc'  " l , l  1  p  -  ) / ( 1  p  2  )  i , i  2  ( A  -  )  3 6 a )  ( 4  The semimajor a x i s o f t h e e l l i p s e has l e n g t h / c / ( l - p ^ ^) and l i e s the l i n e a,+a =a, +a„ : t h e semiminor a x i s h a s l e n g t h /c/(1+p, TT 1 N l c Nc 1,1  *  3 6 b )  along and,lies  a l o n g t h e l i n e a -ex =oi -«._ , where N 1 Nc l c to  c  = ( / e ) - [1 - ( P j e  q  + >  0  p  0,r  2  p  l,0 0,l l,l p  p  )  /  (  1  - l,l p  )  ]  ( 4  -  3 7 >  I t i s n o t e d t h a t a, and a a r e t h e optimum v a l u e s o f a, and ct_ when lc Nc 1 2 2 2 p = 0, and t h e r e s u l t i n g  minimum v a l u e o f  /a  i s g i v e n i n t h e square  b r a c k e t s i n (4.37) When p ^ 0, t h e a l l o w a b l e v a l u e s f o r cx^ and cx^ a r e r e s t r i c t e d w i t h i n t h e square shown i n S e c t i o n 4.5.1.  I n t h i s case t h e optimum v a l u e s  o f ex^ and cx^ a r e no l o n g e r e l l i p t i c a l , as shown i n F i g s . 30 and 31. F o r cb= 10 dB, t h e optimum v a l u e s , - j _ p a  0  on t h e s t a b i l i t y  boundary.  t  and cijj p » °f 0  t  When <j> i s reduced  and cx^ l i e almost  from 10 t o 6 dB, ( j _ p > a  0  t  Nopt^ ^ away from the boundary, as shown more c l e a r l y i n F i g . 32, where (ex, , a „ .) i s l a b e l l e d by " x " f o r v a r i o u s v a l u e s o f <j>. An asyml o p t Nopt p t o t i c v a l u e i s approached f o r b o t h a, ^ and OL, . when cf> i s f u r t h e r r e * lopt Nopt a  s n i  t s  t  J  v  duced.  v  Choosing  &  ex.. and ex,, n e a r t h e s e asymptotes i n s t e a d o f OL_ and CL, 1 N l c Nc J  -1  0  I  FEEDBACK C0EFFJCJEN7 oi; (a)  F i e . 30. SNR v s . a and a f o r l i n e - a n d - s a m p l e feedback DPCM f o r t h e o 1 N the crowd s c e n e . (a) cb=10dB, (b) cp=6dB. &  -1  0  1  FEEDBACK COEFFICIENT Uj  (a)  F i g . 31.  SNR  q  vs. a  and o.^ f o r l i n e - a n d - s a m p l e feedback DPCM f o r t h e  cameraman scene.  (a) <J>=10dB, (b) <j)=6dB.  can g r e a t l y reduce the s e n s i t i v i t y o f s i g n i f i c a n t l y d e g r a d i n g the system  SNR  q  t o v a r i a t i o n s i n cb w i t h o u t  performance.  A l s o shown i n F i g . 32 a r e t h e l o c i f o r w h i c h  of  SNR  with  DPCM  o l i n e - a n d - s a m p l e feedback i s g r e a t e r than t h a t o f PCM.  The v a l u e s o f  and OL^ must always l i e w i t h i n the r e g i o n bounded by these c u r v e s .  When  <j> i s l a r g e , t h e l o w e r l e f t - h a n d p a r t o f t h e curve c o i n c i d e s w i t h  +  The r e a s o n f o r t h i s i s the same as t h a t e x p l a i n e d i n S e c t i o n 4.4.1.  = 0 The  a r e a bounded by these c u r v e s d e c r e a s e s when cb i s d e c r e a s e d . The c u r v e s i n F i g . 33 show t h e v a l u e s o f and that give the same SNR as t h a t o b t a i n a b l e when N = 1. The a r e a bounded by t h e s e o J  c u r v e s i s s i g n i f i c a n t l y l a r g e r than t h e e q u i v a l e n t a r e a f o r t w o - p r e v i o u s sample-feedback system shown i n F i g . 27. maximum v a l u e o f SNR  I n f a c t , t h e improvement i n t h e  o v e r t h a t o b t a i n a b l e when N = 1 i s a l s o much o TABLE IV  Improvement of  SNR  f o r l i n e - a n d - s a m p l e feedback o v e r p r e v i o u s -  q  sample *  CO  10 dB  p  0  3.9xl0~  Crowd 2.54 scene Cameraman scene 2.67  8 dB 6  feedback 6 dB  1.9xl0~  4  2.4xl0~  3  1.3xl0~  0 dB  2 dB  4 dB 2  3.8xl0~  2  7.9xl0~  2.57  3.19  3.58  3.64  3.65  3.67  2.70  3.76  4.40  4.51  4.51  4.51  The feedback c o e f f i c i e n t a  2  f o r N=l i s o p t i m i z e d ; K=4.  l a r g e r , as i s shown i n T a b l e IV.  T h i s improvement i n c r e a s e s as p i n c r e a s e s ,  which s u g g e s t s t h a t l i n e - a n d - s a m p l e - f e e d b a c k system i s e s p e c i a l l y  desirable  when the c h a n n e l i s n o i s y . 4.6.4  S e n s i t i v i t y of V a r i a t i o n s i n S i g n a l S t a t i s t i c s L e t A'  pect to p  7  n  , p  n  n  , A  and A  , and p..  1  be t h e s e n s i t i v i t y c o e f f i c i e n t s w i t h r e s -  r e s p e c t i v e l y , as d e f i n e d i n ( 4 . 5 ) .  Then,  92  l.O-i  0=1OdB  0.5-  a <_> CJ or 03  a £  0  -0.5  0.5  0  -0.5  (b) Fig.  32.  Locus o f  1.0  FFEOBRCK COEFFICIENT oC  SNR  q  which i s equal t o that of  1  PCM.  S N R are denoted by "x' o s c e n e , (b) the cameraman scene. and a  N  t h a t maximize  The v a l u e s o f ^ a  (a) the crowd  93  F i g . 33.  Locus of  SNR  q  w h i c h i s e q u a l t o t h a t o b t a i n a b l e from p r e v i o u s -  sample feedback DPCM.  (a) the crowd s c e n e , (b) the cameraman scene.  A  x  = 2 | ct 1 /A  0  (4.38a)  1  $ 2/A m A =2|a |/A  (4.38b) (4.39a)  N  Q j l  (4.39b)  £ 2/A m l , l  A  =  2  l  a  i  N '  A  /  (4.40a)  A  (4.40b)  * 2/A m 2 2 where A = O /a , w h i c h i s g i v e n i n ( 4 . 1 6 ) , and g  A  m  =  "  1  l,0  ( p  2  +  p  0,l  2  "  2  p  l,0 0,l l,l p  p  )  /  (  1  - l,l p  2 )  ( 4  '  4 1 )  I t can be seen from (4.38) - (4.40) t h a t i n o r d e r t o reduce A  l 0' 0 1 A  ^  a n  A  l 1'  A  m  u  s  t  D  e  a  l a r g e as p o s s i b l e w h i l e |a^| and  s  On t h e o t h e r hand, ct^ and ot^ s h o u l d  |a^| must be as s m a l l as p o s s i b l e .  be so chosen as n o t t o degrade the system p e r f o r m a n c e . example, t h e crowd s c e n e , i n w h i c h case Pj_ Q  0.9569, P Q ^  =  ±  Q  0.9650  =  I f we choose a, = a, = 0.4291 and a„ = O L 1 lc N  and p.. .. = 0.9391. 1,1 then A  Consider, f o r  = 18.24, A  Q1  = 23.90 and A  = 10.25; whereas i f a  x ±  ±  and a„ = 0 . 5 , then A . = 12.27, A . = 1648 and A. . = 6 . 1 4 . N 1,0 0,1 1,1 when  = 0.3725 and ct^ = 0.5,  SNR  q  t  = 0.5621,  = 0.3725 Note t h a t  i s c l o s e t o i t s optimum v a l u e when  p -> 1/2 and i s o n l y s l i g h t l y l e s s t h a n i t s optimum v a l u e when p = 0. For  t h e cameraman s c e n e , P-,  = 0.9809, p  n  The c h o i c e  = a  l  c  = 0.2690 and ct^ = «  26.28, A~ = 70.74 and A , , = 19.02. 0,1 1,1 n  0.5, then A  XjU  = 20.83, A  = 0.3725 and  = 0.7240 g i v e s &  Q  =  T  . =10.41.  Thus, t h e c h o i c e  X$ X  = 0.5 appears t o be a good one f o r b o t h images.  choice i s also s u i t a b l e f o r d i g i t a l  1  However, i f a, = 0.3725 and C L = 1 N  = 26.96, and A  U)X  N c  , = 1 jX  0,-L  X,U  0.9833.  =0.9885 and p  realization.  This  V. SCHEMES FOR COMBATING CHANNEL NOISE  5.1  Introduction We have seen i n t h e p r e v i o u s  analysis that transmission  errors  i n DPCM system can be more s e r i o u s than i n PCM system i f t h e DPCM f e e d back c o e f f i c i e n t s {a } a r e n o t c a r e f u l l y chosen. t r u e i f {OL} l i e n e a r t h e s t a b i l i t y boundary. DPCM system i s u s u a l l y d e s i g n e d such t h a t transmission  SNR  This i s p a r t i c u l a r l y  In practical applications, q  i s maximized when t h e  c h a n n e l i s n o i s e l e s s , i n w h i c h case t h e feedback  coeffici-  e n t s a r e , u n f o r t u n a t e l y , v e r y c l o s e t o t h e s t a b i l i t y b o u n d a r y , as has been shown i n Chapter I V . A l t h o u g h t h e mean-square c h a n n e l e r r o r f o r DPCM c a n be l e s s than t h a t f o r PCM i n a b s o l u t e v a l u e nel  n o i s e i n DPCM i n e f f e c t s t i l l  i f { O L } a r e c a r e f u l l y s e l e c t e d , chan-  c o n t r i b u t e s more t o t h e o v e r a l l mean-  square e r r o r than c h a n n e l n o i s e i n PCM.  From ( 2 , 1 2 ) , i t can be seen t h a t  the mean-square q u a n t i z a t i o n e r r o r o f DPCM i s reduced from i t s e q u i v a 2 2 l e n t PCM v a l u e by the f a c t o r a la , whereas f o r t h e mean-square c h a n n e l e x 2 2 e r r o r , t h e f a c t o r i s Q° /° > where Q i s n o r m a l l y e  much g r e a t e r  than 1.  S u b j e c t i v e l y , c h a n n e l n o i s e i n DPCM a l s o appears t o be l e s s d e s i r a b l e , even i f i t g i v e s t h e same mean-square c h a n n e l e r r o r as t h a t o f PCM.  One o f t h e reasons f o r t h i s i s t h a t any t r a n s m i s s i o n  DPCM w i l l a f f e c t many samples.  error i n  F o r example, i n t h e t r a n s m i s s i o n  of video  s i g n a l s w i t h p r e v i o u s - s a m p l e feedback DPCM, an e r r o r i n t r a n s m i s s i o n  will  produce a l o n g h o r i z o n t a l s t r e a k s t a r t i n g a t t h e p o i n t where t h e e r r o r occurs.  This kind of disturbance  i s found t o be more o b j e c t i o n a b l e to  the human eyes than random e r r o r s i n PCM. I n v i e w o f these f a c t s , i t i s p a r t i c u l a r l y d e s i r a b l e t o  i n c o r p o r a t e an e f f e c t i v e scheme t o cope w i t h c h a n n e l chapter, v a r i o u s techniques are  noise.  In this  w h i c h can be used f o r combating c h a n n e l  noise  discussed. S i n c e t h e mean-square channel  e r r o r o f a DPCM system i s con-  t r i b u t e d by two major f a c t o r s , namely, Q and e , t h e e f f e c t o f c h a n n e l e r r o r s can be a l l e v i a t e d by r e d u c i n g e i t h e r o r b o t h o f these two f a c t o r s . Channel e n c o d i n g , w h i c h i s a t e c h n i q u e i n S e c t i o n 5.2. Q.  used f o r r e d u c i n g e , i s s t u d i e d  S e c t i o n s 5.3-5.5 d i s c u s s v a r i o u s t e c h n i q u e s  f o r reducing  Some s i m p l e and e f f e c t i v e schemes a r e s u b j e c t i v e l y e v a l u a t e d i n  S e c t i o n 5.6.  5.2  Channel E n c o d i n g For a g i v e n q u a n t i z e r c o n f i g u r a t i o n , t h e mean-square e r r o r e^  can be reduced by channel  encoding.  Instead o f u s i n g the n a t u r a l - b i n a r y  code as d e s c r i b e d i n S e c t i o n 4.1, f o r example, we can use e i t h e r o t h e r non-redundant coding schemes, such as Gray code and f o l d e d b i n a r y code, o r e r r o r - c o r r e c t i n g codes, i n w h i c h case an e x t r a number o f b i n a r y  digits  i s added t o t h e n a t u r a l - b i n a r y coded q u a n t i z e r o u t p u t t o check and correct transmission errors. F o r non-redundant b i n a r y codes, Yan and Donaldson have subj e c t i v e l y compared t h e e f f e c t s o f u s i n g n a t u r a l - b i n a r y code and f o l d e d b i n a r y code i n PCM and DPCM systems f o r speech s i g n a l s [ 1 4 ] .  Arguello et  a l . , on t h e o t h e r hand, have proposed a c o d i n g scheme w h i c h i s p a r t i c u l a r l y s u i t a b l e f o r the transmission of t e l e v i s i o n s i g n a l s [ 1 3 ] . Assuming t h a t t h e i n p u t t o t h e q u a n t i z e r i s u n i f o r m l y  distributed,  Huang [41] has compared t h e mean-square e r r o r o f t h e r e f l e c t e d - b i n a r y Gray code w i t h t h a t o f t h e n a t u r a l - b i n a r y code.  He a l s o shows t h a t f o r  a t h r e e - b i t word, t h e n a t u r a l - b i n a r y  code i s optimum i n t h e sense  i t y i e l d s t h e minimum mean-square e r r o r .  A l t h o u g h non-redundant  that codes  a r e s i m p l e and easy t o implement, i t has no e r r o r - c o r r e c t i n g c a p a b i l i t i e s , w i t h t h e r e s u l t t h a t t h e improvement,  i f any, i n performance o f one scheme  over t h e other i s r a t h e r l i m i t e d . For e r r o r - c o r r e c t i n g c o d e s , numerous schemes have been p r o p o s e d i n the past.  However, t h e i r e f f e c t on t h e performance o f communication  systems, p a r t i c u l a r l y DPCM, had r e c e i v e d ing, the e f f e c t of using  l i t t l e attention.  c e r t a i n s i m p l e e r r o r - c o r r e c t i n g c o d e s , such as  Hamming code, i n DPCM i s s t u d i e d .  In Section  s i t y function of the input t o the quantizer  5.2.1, t h e p r o b a b i l i t y den-^  i s assumed t o be u n i f o r m , i n  w h i c h case an a n a l y t i c a l s o l u t i o n i s p o s s i b l e . to non-uniform d i s t r i b u t i o n s i n Section  5.2.1  In the follow-  The a n a l y s i s i s extended  5.2.2.  Uniform P r o b a b i l i t y Density Function When t h e p r o b a b i l i t y d e n s i t y  quantizer  function P ( a ) of the input t o the e  i s u n i f o r m , t h e optimum q u a n t i z e r  t h i s c a s e , i t can be shown [21,30] E  =  4~  =  0  i s also uniform [30]. In  that (5.1)  K  q and  E  M  (5.2)  where K i s t h e number o f q u a n t i z a t i o n e n c o d i n g scheme.  bits.  The e r r o r E ^ depends on t h e  F o r group codes, i t has t h e f o l l o w i n g s i m p l e form  e  n  K = 12 Z 4" i=l  1  p(i)  (5.3)  where p ( i ) i s t h e p r o b a b i l i t y t h a t i t h b i t i s i n e r r o r a f t e r d e c o d i n g . F u r t h e r m o r e , i f a code i s c y c l i c , p ( i ) i s independent o f i and (5.3) c a n be f u r t h e r s i m p l i f i e d as f o l l o w s .  e = 4(1-4 ) p n c  (5.4)  K  r  where p^ r e p r e s e n t s t h e b i t - e r r o r p r o b a b i l i t y w i t h c h a n n e l e n c o d i n g . L e t N be t h e codeword and q=l-p.  Then p  l e n g t h , p be t h e c h a n n e l b i t - e r r o r  can be c a l c u l a t e d from W.,  w i t h Hamming w e i g h t j ,  probability,  t h e number o f codewords  and Q ( j | 0 ) , the p r o b a b i l i t y t h a t 0 i s t r a n s m i t t e d  and a K - t u p l e word c o r r e s p o n d i n g t o an N - t u p l e codeword w i t h w e i g h t j i s decoded, from t h e f o l l o w i n g e q u a t i o n [ 4 2 ] . N P  =  c  . JtfW Q(j|0)' + V p q ' ]  E  j  j=0  J  N  (5.5)  j  J-  where V_. i s t h e c o e f f i c i e n t o f 7? i n t h e p o l y n o m i a l V ( z ) , where V(.)  - (l  ) - N  +  Z  Ij  N  q  0  V  ( j | 0 )  W «  C 5  - ' 6  F o r an m - e r r o r - c o r r e c t i n g code, t h e decoder i s c a p a b l e o f d e c o d i n g t h e r e c e i v e d N - t u p l e i f i t i s w i t h i n a Hamming d i s t a n c e m o f some  codeword,  i n w h i c h case t h e p r o b a b i l i t y Q ( j | 0 ) i s  Q(j|0) - q  N  I  ? i =  o k=o  Crhd) 1 _ f c  ( /q) P  J + 1  -  (5.7)  2 k  k  I f any o t h e r N - t u p l e i s r e c e i v e d , a d e c o d i n g f a i l u r e o c c u r s , i n w h i c h case t h e K i n f o r m a t i o n d i g i t s a r e d i r e c t l y used.  The second term i n t h e  square b r a c k e t s i n (5.5) r e p r e s e n t s t h e e r r o r due t o t h i s d e c o d i n g failure. C o n s i d e r now t h e s i n g l e - e r r o r c o r r e c t i n g Hamming code.  Since  t h e r e i s no d e c o d i n g f a i l u r e i n t h i s c a s e , and s i n c e m=l, we have P  r  =  N I j=0  Q(j|0) N  J  (5.8a)  where Q(j|0) = q  (p/q)  N  j  [l+Np/q+j(l-2p)/pq]  (5.8b)  To f u r t h e r s i m p l i f y ( 5 . 8 ) , we d e f i n e N E  W(z) =  W.z  (5.9)  J  j=0  3  W(z) i s a l s o c a l l e d t h e w e i g h t enumerator o f t h e codeword.  By d i f f e r e n -  t i a t i o n , i t can be shown t h a t 1  N  E jW.z j=0  = zW (z)  J  (5.10a)  3  N . E j W.z = z W " ( z ) - zW'(z) j=0  (5.10b)  J  3  S u b s t i t u t i n g (5.8b) i n t o  p = ^ *c N  N  (5.8a) and making use o f ( 5 . 1 0 ) , we have  { [ 1 + z + ( N - l ) z ] W'(z) + z ( l - ' z ) W " ( z ) } , z=p/q  (5.11)  L  The w e i g h t enumerator f o r t h e Hamming code i s [43] N-1 W(z) = — ^ -  [(l+z)  N  + N(l+z)  2  (1-z)  N+1 ]  2  (5.12)  The s u b s t i t u t i o n o f (5.12) i n t o (5.11) y i e l d s N c  —— N-3  N+1 Lfd+N^d+^N"  1  _ (l+2Nz+z ) (1+z) 2  2  (1-z)  N-1 2  ]  z  =  p  /  q  (5.13)  Thus, ( 5 . 1 ) , ( 5 . 2 ) , (5.4) and (5.13) i n c o n j u n c t i o n w i t h (2.12) g i v e s the mean-square e r r o r o f DPCM systems w i t h s i n g l e - e r r o r c o r r e c t i n g Hamming code. C o n s i d e r , f o r example, t h e case N=7, i n w h i c h case t h e r e a r e t h r e e check d i g i t s and K=4.  L e t t i n g N=7 i n (5.13) and r e a r r a n g i n g , we  obtain p = q p [z +7z +12z +16z +19z+9] , • c z=p/q 5  2  5  4  3  2  (5.14)  100  Fig.  34 shows t h e e f f e c t o f t h i s s i n g l e - e r r o r - c o r r e c t i n g code as compared  to the non-redundant n a t u r a l b i n a r y code when t h e t r a n s m i t t e r power i s c o n s t a n t (a) and when the channel b i t - e r r o r - p r o b a b i l i t y i s c o n s t a n t ( b ) . The DPCM system i s assumed t o have one-previous-sample  feedback w i t h cx^=  p^=0.9569 and the t r a n s m i s s i o n c h a n n e l i s assumed t o be w h i t e as d e s c r i b e d i n S e c t i o n 4.1.  Curves f o r o t h e r v a l u e s of  v e r y s i m i l a r and t h e r e f o r e n o t p r e s e n t e d .  Gaussian  and  are  I n F i g . 3 4 ( a ) , where t h e t r a n s -  m i t t e r power i s h e l d c o n s t a n t i n b o t h c a s e s , Hamming code i s seen t o p e r f o r m b e t t e r o n l y when P/4f N > 6dB, w i t h a maximum inprovement i n s o - ' SNR o f a p p r o x i m a t e l y 1.5dB a t P/4f N = 8dB. There i s no improvement o s o when P/4f N > lOdB, because i n t h i s r e g i o n SNR i s l i m i t e d by t h e quans o o tization error.  A t l o w t r a n s m i t t e r power, Hamming code g i v e s l o w e r  SNR , Q  because i n t h i s r e g i o n t h e r e a r e many words w h i c h have m u l t i p l e e r r o r s and cannot be c o r r e c t l y decoded and, f u r t h e r m o r e , these e r r o r s a r e more l i k e l y t o o c c u r due t o i t s h i g h e r c h a n n e l b i t - e r r o r p r o b a b i l i t y . I f Hamming code and non-redundant n a t u r a l code have t h e same channel b i t - e r r o r p r o b a b i l i t y , then t h e former performs much b e t t e r than the l a t t e r ,  as shown i n F i g . 3 4 ( b ) .  The maximum improvement i n  SNR  q  for  Hamming code exceeds 12dB a t <t=6dB.  5.2.2  Non-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 When t h e 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 P (oO and t h e q u a n t i z e r e  are n o t u n i f o r m , c l o s e d - f o r m e x p r e s s i o n s f o r e , e and e as those i n q m n the p r e v i o u s s e c t i o n a r e v e r y d i f f i c u l t t o d e r i v e . However, i f we can c a l c u l a t e P.., t h e p r o b a b i l i t y t h a t v. i s t r a n s m i t t e d and v. i s r e c e i v e d , then e , e and e c n be computed f q m n a  any  difficulty.  r  o  m  (2.16) - (2.18) n u m e r i c a l l y w i t h o u t  tn co"  HAMMING —if CODE "  in rvj'  tn  (7,4) HAMMING 1 CODE '  /  /  1  o rvj  1  CQ  '  I 1 1  1  1  A NON-REDUNDANT NATURAL-BINARY CODE  to  NON-REDUNDANT / NATURAL-BINARY / CODE in-  in-  ->—I—'—1—'—1— —r 1  -10  -8  -6  -4  -  1 4  -2  ' r  -1—'—l—'—I  10  8  6  RELATIVE TRANSMITTER POWER P/4f N , dB s  12  ir>.  -10  1  -8  1  1  -6  — ,  -4  , — ,  -2  Q  (a)  F i g . 34.  SNR  o  r  0  n —r 1  4  "6  -1—'—1—•—1  8  10  12  0, dB  (b)  f o r p r e v i o u s - s a m p l e feedback DPCM u s i n g Hamming code and non-redundant n a t u r a l b i n a r y code.  The c h a n n e l i s w h i t e G a u s s i a n ; P ( a ) i s u n i f o r m ; a^=p^=o.9569; K=4. e  (b) f i x e d b i t - e r r o r  (a) f i x e d t r a n s m i t t e r power,  probability. o  Assume again that the quantizer output l e v e l s are natural-binary coded, i . e . , i f v.,  first  1 < i < 2 , i s the quantizer out-  put l e v e l , then i t i s denoted by the binary representation of ( i - 1 ) , then further encoded with a group code of length N. binary representation of ( i - 1 ) .  and  Let b_^ be the K-bit  From the properties of group codes, i t  K can be shown that for any values of the integers i and j , 1 < i < 2 and K K i 1 < j < 2 , there'exists an integer p , 1 < ^ < 2 , such that ^0^1]^) = 1  P ( b j 0 ) , where b =b. © b /  and 0 denotes the a l l 0 K-tuple.  Since P..  =  P(bj|b__^), i t i s only necessary to calculate P(b^|0_), which i s a function of the Hamming weight of the codeword corresponding to b,.  Let k denote  the weight of this codeword. Then we have  -H  P  =  P(  >  JO)  where 0(k|0) i s given i n (5.7)  = Q(k|0)  (5.15)  and, i n the case of Hamming code, i n (5.8b)  The weight k can be obtained by d i r e c t l y coding the K-tuple b_^ i f  the  coding scheme i s known. In Figs. 35 and 36, S N R  q  r e l a t i v e transmitter power, P / 4 f N , G  O  i s plotted as a function of the and <j> for previous-sample feedback  DPCM with Laplacian and Gaussian d i s t r i b u t i o n s , respectively.  The quan-  t i z e r i s assumed to be logarithmic with u=100 and overload l e v e l V=10a i n both cases and the feedback c o e f f i c i e n t ct^=p^=0.89 for Laplacian 0.9569 for Gaussian.  e  and  The performance of a (7,4) Hamming code i s compared  with that of the non-redundant natural binary code i n each case. encoder for Hamming code i s a three-stage  The  feedback s h i f t r e g i s t e r  © denotes the component-by-component exclusive or of the two sequences.  binary  CM  - 1  Q.  CM  (7,4) HAMMING CODE •  (7,4) HAMMING , CODE -j  03  CO  7  'r  NON-REDUNDANT NATURAL-BINARY CODE  NON-REDUNDANT NATURAL-BINARY CODE  IO.  I  i  T  T  1  1 ' 1—'  1  '  1  ~r  ' 1 ' !  8  -10 -8 -6 -4 -2 0 2 4 6 RELATIVE TRANSMITTER POWER P/4f.N , dB  (a)  F i g . 35.  SNR  10  -1  12  -10  i  -4  I  -2  0  2  0,dB  ~T~  8  I— —I 1  10  12  (b)  f o r p r e v i o u s - s a m p l e feedback DPCM u s i n g Hamming code and non-redundant n a t u r a l - b i n a r y code.  The c h a n n e l i s w h i t e G a u s s i a n ; P (a) i s L a p l a c i a n ; a ^ p =0.89; K=4. (b) b i t - e r r o r p r o b a b i l i t y  fixed.  (a) t r a n s m i t t e r power f i x e d ,  7~ -10  1  i i i i i i i i i i i -8 --S -4 -2 0 2 4 6 8 10 12 RELATIVE TRANSMITTER POWER P/U N , dB 1  1  1  1  1  1  1  1  1  5  1  Q  T '  ' -10  1  1  -8  '  1  1  -6  1  i '—i— —i—'—i— —i—'—i— —i— —i -4 -2 0 2 A 6 8 30 0 dB  fa) F i g . 36.  S  N  R  1  1  1  1  12  /  fb)  f ° p r e v i o u s - s a m p l e feedback DPCM u s i n g Hamming code and non-redundant n a t u r a l b i n a r y code. r  Q  The  c h a n n e l i s w h i t e G a u s s i a n ; P ( a ) i s G a u s s i a n ; a^=p^=0.9569; K=4.  (b) b i t - e r r o r p r o b a b i l i t y  e  fixed.  (a) t r a n s m i t t e r power f i x e d ,  M I  plemented  from t h e p r i m i t i v e b i n a r y p o l y n o m i a l g(x) = x  shown i n F i g . 37.  4  3  To encode, t h e f l i p - f l o p s f , f ^ , and f ^ a r e s e t t o  -0  c c c c, 2  + x + 1, as  '3  +x~  +x F i g . 37  Encoder f o r t h e Hamming code used i n p l o t t i n g F i g s . 35 and 36.  zero i n i t i a l l y .  The f o u r i n f o r m a t i o n d i g i t s c^., c^, c^, and c^, each o f  w h i c h b e i n g e i t h e r 0 o r 1, a r e t h e n s e q u e n t i a l l y f e d i n t o the encoder. A f t e r t h i s i s completed, the t h r e e f l i p - f l o p s c o n t a i n t h e t h r e e d e s i r e d check  digits. The g e n e r a l b e h a v i o u r o f the c u r v e s i n F i g s . 35 and 36 i s v e r y  s i m i l a r t o t h a t o f t h e c u r v e s i n F i g . 34.  When the t r a n s m i t t e r power i s  h e l d c o n s t a n t ( F i g s . 35(a) and 3 6 ( a ) ) , t h e Hamming code i s seen t o y i e l d h i g h e r SNR  o  t h a n t h e non-redundant  n a t u r a l code i f P/4f N > 5dB f o r b o t h s o -  L a p l a c i a n and G a u s s i a n d i s t r i b u t i o n s . that f o r uniform d i s t r i b u t i o n . the same f o r b o t h codes  T h i s range i s s l i g h t l y w i d e r t h a n  I f the c h a n n e l b i t - e r r o r p r o b a b i l i t y i s  ( F i g s . 35(b) and 3 6 ( b ) ) , then t h e Hamming code  almost always p e r f o r m s b e t t e r . To c o n s t r u c t t h e encoder f o r (7,4) Hamming code, we can a l s o 3 use another p r i m i t i v e b i n a r y p o l y n o m i a l , i . e . , g ( x ) = x  2 + x  +1.  It is  found t h a t t h i s encoder g i v e s a l m o s t i d e n t i c a l r e s u l t as t h e one shown  The p r i n c i p l e o f t h i s encoder can be found i n Chapter IV o f R e f e r e n c e [44],  i n F i g . 37.  5.3  Periodic Resetting To reduce the f a c t o r Q, we can e i t h e r r e d e s i g n the feedback  parameters {OL}  i n such a way  t h a t Q i s reduced s i g n i f i c a n t l y w h i l e the 2  2  n o r m a l i z e d p r e d i c t i o n e r r o r ° /° . does n o t d e v i a t e too f a r away from i t s e  y  minimum v a l u e , o r p e r i o d i c a l l y r e s e t the p r e d i c t o r o u t p u t  t o zero so  t h a t any c h a n n e l e r r o r does n o t p r o p a g a t e l o n g e r than the l e n g t h o f a period.  The d e s i g n o f feedback parameters has been d i s c u s s e d i n d e t a i l  i n Chapter IV.  I n t h i s s e c t i o n , the t e c h n i q u e o f u s i n g p e r i o d i c r e s e t -  t i n g t o reduce Q w i l l be i n v e s t i g a t e d . For convenience i n a n a l y s i s , the i n p u t sequence {x_^} i s d i v i d e d i n t o b l o c k s w i t h M samples i n each b l o c k , where M i s the number o f samples i n each p e r i o d o f r e s e t t i n g . v i d e o , each s c a n n i n g  I n the case of r a s t e r scanned  l i n e can be c o n s i d e r e d as a b l o c k i f r e s e t t i n g  o c c u r s a t the b e g i n n i n g o f each l i n e .  L e t x^, 0 < i < M - l , denote the  i k sample i n each b l o c k and x^ denote the o u t p u t o f the system c o r r e s fc  ponding t o t h i s sample.  Then the n o r m a l i z e d mean-square e r r o r e can be  d e f i n e d as the s t a t i s t i c a l e x p e c t a t i o n o f the average o f the squared d i f f e r e n c e i n each b l o c k , n o r m a l i z e d w i t h r e s p e c t t o the s i g n a l power 2 . a ,i.e., x  E = E{ i  M-l E (x. - x . ) } / a i=0 2  2  (5.16)  U s i n g the n o t a t i o n s shown i n F i g . 1, we can w r i t e the d i f f e r e n ce between x.and x. as f o l l o w s , l  l  x. - x. = r . + z. - e. - z. 1 1 1 x x 1  = q. + n. + ( z . - z . ) X  X  (5,17)  X I  where q.=s.-e. denotes the q u a n t i z a t i o n e r r o r and n.=r.-s. denotes t h e ^x x l x x x 1  e r r o r due t o channel n o i s e .  The d i f f e r e n c e ( z . - z . ) i s a r e s u l t of the i x c h a n n e l e r r o r s , as w i l l be shown i n the f o l l o w i n g . S i n c e  previous  N E  z. =  a.y.  .  and  N E  z. =  ct.x. .  we have . z.-z.= i i  N E j  =  a . (x. .-y. .) 3 i-J i-J  N E  =  1  N E a.n. • T J 1~J J=l  =  „ .+z.  o.[(r.  .) - ( s . .+z.  N + E ( z , . - z , .) . 1 1-J 1-1 j - l A  Note t h a t (5.18) i s a r e c u r s i v e e q u a t i o n . (5.18) w i t h i - j , we  (5.18)  R e p l a c i n g the s u b s c r i p t i i n  obtain  N z. . - z. . = E a. n. . . i-J ^ j l J ^-32 2  .)]  =  N E a. ( z . . . - z . . . ) j -l 2  +  (5.19)  3  2  2  The s u b s t i t u t i o n o f (5.19) i n t o (5.18) y i e l d s N E a..n.  z. - z. = 1  1  j ^ i  +  h  N E 1=1 l  J  N E  +  ^ i  j ^ i  N E a. a j =1 1 2 2 3  J  Where, f o r c o n s i s t e n c y ,  N E a. a. n. .  3  j -i 2  J  i  J 2  ( z . _ . . - z . . _. ) 1~ 2 ~1 2 1  2  3  X  3  (5.20)  J  i s used t o denote j i n (5.18) and  (5.19).  R e p e a t i n g the above p r o c e d u r e f o r i t i m e s , we o b t a i n the f o l l o w i n g  equation. N z.-z. 1  -  1  E a. n. . + j  ]  - i H  L  Since i n i t i a l l y  z  N  E  E a. a, n. .  j ^ u y i  ~h  x  N + E j =1  N  N h  h  N E a. . . . a . ( z . . j =1 l i 1 J  J  1  _  .+  E ...  ~h~h  x  J  j  J  ±  E a, . . . a , n. . - ih  _. - z . . .) i ~1 "' ± X  2  h  ^  r  -  (5.21)  3  the p r e d i c t o r o u t p u t s z^ and z^ a r e s e t t o z e r o , i . e . ,  = z  k  = 0  k  and s i n c e  for k < 0  (5.22)  < 0, the l a s t term i n (5.21) v a n i s h e s .  A f t e r ex-  p a n d i n g t h e summation and r e g r o u p i n g t h e l i k e t e r m s , we can e x p r e s s t h e difference ^ z  - z  ^  i  (5.21) as a w e i g h t e d sum o f t h e i p r e v i o u s c h a n n e l  n  e r r o r s as f o l l o w s . z.-z. = i l  E f n. i m l-m m=l  (5.23)  where f  l  =  f  2  =  f  3  K  a  l  2  +  = a  a  3  l  + 2a a 2  1  + a  3  2 2 2 f. = a. + 2a„a. + a + 3a„a + a. 4 4 31 2 2 1 1 0  1  (k +. . . 4 - k ^ ) ! N  and  f  =  E  A  m  •  k !...k,'k,' 2*1'  k  ^ ^ k  O L . ...a„ a. N  2  (5.24a)  1  N  where k^, k , ..., k^ a r e 0 o r p o s i t i v e i n t e g e r s and t h e summation i s o v e r 2  a l l t h e v a l u e s o f k^, k ^ j ..., k^ w h i c h a r e i n t h e s e t A = {k  1 5  k , . . . , k : N ^ . . .+2k +k =m} 2  N  2  1  (5.24b)  Define ^=1.  Then t h e s u b s t i t u t i o n o f (5.23) i n t o (5.17) y i e l d s  x.-x. = q. + i l l  i E f n. ~ m l-m m=0  (5.25)  I t i s n o t e d t h a t (5.25) and (2.7) a r e v e r y s i m i l a r .  The w e i g h t i n g c o e f -  f i c i e n t f , i n f a c t , i s t h e d i g i t a l i m p u l s e response o f t h e decoder. m t i t u t i n g (5.25) i n t o ( 5 . 2 3 ) , we have M-l i i e = - j E ( E [ q ] + 2 E f E[q.n. ] + E [ ( E f n. ) ] } / a M. ^ i « m x l-m „ m l-m x x=0 m=0 m=0 2  2  Subs-  (5.26)  2  n  The f i r s t term i n t h e b r a c e s i n (5.26) r e p r e s e n t s t h e e r r o r due t o quant i z a t i o n , t h e l a s t term i s t h e errory'resulting from c h a n n e l n o i s e , and t h e second term i s t h e e r r o r due t o i n t e r a c t i o n between t h e q u a n t i z a t i o n and channel n o i s e . memoryless  Assume, as i n S e c t i o n 2.-1, t h a t t h e d i g i t a l c h a n n e l i s  and t h e d i f f e r e n c e samples e^ a r e s t a t i s t i c a l l y i n d e p e n d e n t .  Then E f q . n . ] = 0 f o r m + 0 and E [ n . .n. , ] =0 f o r j ^ k. ^ i x-m 1-3 i - k 2 2 L  J  J  J  Furthermore, 2  assume t h a t t h e e x p e c t e d v a l u e s E [ e ^ ] , E [ q ] , Efq^n^] and E[n^] a r e i n d e pendent o f i .  T h i s l a t t e r assumption i s n o t u n r e a s o n a b l e when i i s n o t  2 2 2 2 too s m a l l ( t y p i c a l l y i > N ) . L e t a = E [ e . ] , e = E [ q . ] / a , £ = E [ q . n . ] / a • e l q l e m l l 2 2 and e^ = E[n^]/a^. Then, under t h e above assumptions (5,26) can be x  /r  J  e x p r e s s e d i n t h e same form as ( 2 . 1 2 a ) , namely, e = (e + e + Qe ) o /a q m n e x  (5.27a)  M-l i Q = ^ E ( E f M . _ m 1=0 m=0  (5.27b)  2  2  where n  )  n  T h e r e f o r e , u s i n g (5.27) i n c o n j u n c t i o n w i t h t h e e x p r e s s i o n s f o r e^, e^, £ , n  2 2 and a lo d e r i v e d i n S e c t i o n 2.3, we can c a l c u l a t e SNR o f DPCM system e x o with periodic resetting. C o n s i d e r now t h e p r e v i o u s - s a m p l e - f e e d b a c k DPCM.  Setting N i n  (5.24) t o 1, we have f m  = a™ 1  (5.28)  I t f o l l o w s from (5.27b) and (5.28) t h a t  i M-l Q - £  1  * < = 1=0 m=0 ..  .  1  ) 2  2  M  a (1-a )  l-a^  1-a^ 2  When t h e r e i s no p e r i o d i c r e s e t t i n g , M ->•  00  and Q = 1/ (1-cx^) , w h i c h i s t h e  same as t h a t o b t a i n e d from ( 2 . 2 6 ) , as would be e x p e c t e d . Fig,  38 shows Q as a f u n c t i o n o f t h e b l o c k s i z e M f o r  0.9569 and 0.9809.  The f a c t t h a t Q can be reduced by p e r i o d i c  i s c l e a r l y seen i n t h i s f i g u r e . most when  - 0.89,  resetting  F o r a g i v e n b l o c k s i z e M, Q i s reduced  i s l a r g e , as compared t o t h e v a l u e o f Q when no p e r i o d i c  r e s e t t i n g i s used.  F o r example, i f  = 0.89, Q i s reduced from i t s m a x i -  mum v a l u e o f 4.81 f o r no p e r i o d i c r e s e t t i n g t o 4.52 a t M=64, w h i c h means a r e d u c t i o n o f o n l y 5.95%. 11.86 Qis  However, i f  = 0.9569, Q i s reduced from  f o r M + » t o 9.85 a t M=64, a r e d u c t i o n o f 16.9%, and i f a  reduced from 26.43 f o r M For  00  by 36.4% t o 16.82 a t M=64.  video s i g n a l s , the p r e d i c t o r outputs  r e s e t t o z e r o a t t h e b e g i n n i n g o f each l i n e . per  = 0.9809,  l i n e , t h i s means a b l o c k s i z e o f 512.  and z^ a r e n o r m a l l y  F o r an image w i t h 512 samples  The v a l u e o f Q i n t h i s case i s  almost t h e same as t h a t f o r M-*-. , as i s shown i n F i g . 38. T h e r e f o r e i n 00  o r d e r t o have a s m a l l e r v a l u e o f Q, t h e p r e d i c t o r o u t p u t must be r e s e t more o f t e n than once p e r l i n e . A l t h o u g h F i g . 3 8 s u g g e s t s t h a t a s h o r t e r b l o c k l e n g t h always y i e l d s a s m a l l e r v a l u e o f Q, i t s h o u l d a l s o be remembered t h a t when r e s e t t i n g i s t o o o f t e n , t h e system w i l l be c o m p l i c a t e d . F u r t h e r m o r e , i f M i s  F i g . 38.  The  f a c t o r g i v e n i n (5.29) v s . the b l o c k s i z e M f o r DPCM w i t h p e r i o d i c  resetting.  too s m a l l , (5.27) w i l l be i n v a l i d , because i n t h i s case the assumptions used i n i t s d e r i v a t i o n become v e r y i n a c c u r a t e .  I n f a c t , t h e v e r y advan-  tage o f u s i n g p r e d i c t i o n i n DPCM may c o m p l e t e l y d i s a p p e a r i f the p r e d i c t o r i s r e s e t too f r e q u e n t l y . Fig. &  39 shows t h e c a l c u l a t e d and measured v a l u e s o f S N R as a o  f u n c t i o n o f the b l o c k s i z e M f o r t h e crowd (a) and t h e cameraman (b) scenes.  2 2 I n c a l c u l a t i o n , t h e n o r m a l i z e d p r e d i c t i o n e r r o r a /a i s assumed e x  to be c o n s t a n t , independent o f M. the c a l c u l a t e d v a l u e s o f S N R  q  Thus, when the b l o c k s i z e M  always i n s c r e a s e due t o t h e m o n o t o n i c a l l y -  d e c r e a s i n g n a t u r e o f Q shown above. i n c r e a s e and thus SNR  decreases,  2 2 I n f a c t , when M d e c r e a s e s , a /a will  w i l l descrease.  T h i s f a c t can be seen from t h e  o e x p e r i m e n t a l l y measured v a l u e s o f S N R , as shown i n symbols i n F i g . 39. q  A maximum i s seen t o e x i s t between M = 16 and 64 i n each case.  The m a x i -  mum v a l u e s a r e a p p r o x i m a t e l y 1.5dB h i g h e r than those f o r M = 512 f o r t h e cameraman scene and l d B h i g h e r f o r t h e crowd scene.  A l s o , the improve-  ment due t o f a s t e r r e s e t t i n g i s more e v i d e n t when p i s l a r g e .  5.4  Pseudo-Random R e s e t t i n g A l t h o u g h p e r i o d i c r e s e t t i n g i s s i m p l e and easy t o implement, i t  a l s o has a u n d e s i r a b l e e f f e c t .  S i n c e t h e i n i t i a l samples o f each b l o c k  are n o t p r e d i c t e d o r i n c o m p l e t e l y p r e d i c t e d , and s i n c e t h e q u a n t i z e r i s u s u a l l y designed  f o r t h e p r e d i c t i o n e r r o r samples e_^, t h e q u a n t i z a t i o n  e r r o r f o r t h e i n i t i a l samples o f each b l o c k i s v e r y l a r g e . a r e s u l t of amplitude overload. the  This e r r o r i s  Since r e s e t t i n g i s performed p e r i o d i c a l l y ,  h i g h - o v e r l o a d - e r r o r samples w i l l l i e on the same v e r t i c a l l i n e f o r  v i d e o s i g n a l s and t h e e r r o r s can be e a s i l y  detected.  In o r d e r t o p r e v e n t t h e i n i t i a l samples w i t h l a r g e o v e r l o a d  0=  8dB  0 = 8dB CQ ~C3  o  in.  0 = 6dB 0=6dB  —i 16  32  1  1  64  128  BLOCK  SIZE  256  512  M  (a) F i g . 39,  SNR  o  16  32  64  £LOC/<  128  SIZE  256  512  M  (b)  o f p r e v i o u s - s a m p l e feedback DPCM w i t h p e r i o d i c r e s e t t i n g v s . t h e b l o c k s i z e M; K=4, N = l .  (a) t h e crowd s c e n e , (b) t h e cameraman scene.  Symbols (A,x) denote t h e e x p e r i m e n t a l l y measured v a l u e s .  e r r o r from a p p e a r i n g  on the same v e r t i c a l l i n e , the p r e d i c t o r can be  pseudo-randomly i n s t e a d o f p e r i o d i c a l l y . to  r e s e t the p r e d i c t o r a p p r o x i m a t e l y  pseudo-random number g e n e r a t o r  reset  For i n s t a n c e , i f i t i s d e s i r e d  once every M samples, we  to accomplish  can use  a  t h i s i n the f o l l o w i n g manner.  When a sample i s t r a n s m i t t e d , a pseudo-random number, w h i c h i s u n i f o r m l y d i s t r i b u t e d between 0 and 1, i s g e n e r a t e d and number i s l e s s than 1/M, p r e d i c t i o n continues.  compared w i t h 1/M.  t h e n the p r e d i c t o r i s r e s e t ; o t h e r w i s e , This technique w i l l  I f the the  o b v i o u s l y e l i m i n a t e the unde-  s i r a b l e v e r t i c a l l i n e s r e s u l t i n g from p e r i o d i c r e s e t t i n g ,  -Subjective  e f f e c t o f pseudo-random r e s e t t i n g i s e v a l u a t e d  5.6.  5.5  i n Section  Other Techniques f o r Combating Channel N o i s e S i n c e the l a r g e e r r o r o f i n i t i a l samples i n p e r i o d i c r e s e t t i n g  i s a r e s u l t of amplitude out i n S e c t i o n 5.4  overloads  a d i r e c t s o l u t i o n f o r the problem p o i n t e d  i s to use a more p r e c i s e q u a n t i z e r w i t h l a r g e r o v e r l o a d  l e v e l f o r the i n i t i a l samples o f each b l o c k . sample feedback systems, we may o f each b l o c k .  This technique  F o r example, f o r  one-previous-  use a 7 - b i t q u a n t i z e r f o r the f i r s t i s a l s o known as PCM  updating  sample  and has  been  i n v e s t i g a t e d by A r g u e l l o e_t al_. [ 1 3 ] . The ting.  a n a l y s i s i n S e c t i o n 5.4  can be e a s i l y extended to PCM  Assume t h a t the i n i t i a l k samples o f each b l o c k , where k < M,  t r a n s m i t t e d w i t h a PCM  system.  Then the n o r m a l i z e d  updaare  mean-square e r r o r  d e f i n e d i n (5.16) can be w r i t t e n as f o l l o w s .  i=0 The  first  i=k  summation i n (5.30) denotes the e r r o r due  t o PCM  transmission  and the second summation i s a r e s u l t of DPCM t r a n s m i s s i o n . and e  np  , e qp mp q u a n t i z a t i o n , m u t u a l and c h a n n e l e r r o r s ,  denote the n o r m a l i z e d  r e s p e c t i v e l y , o f the PCM p a r t o f the system.  Let e  Then, f o l l o w i n g a p r o c e d u r e  s i m i l a r t o t h a t i n S e c t i o n 5.4, i t can be shown t h a t e = (e + e +s ) + (e + e + Qe ) t ? / a qp mp cp q m n e x 2  (5.31a)  2  2 2 where e , £ , e and a /cr a r e g i v e n i n S e c t i o n 2.3 q m n e x 6  1  2  1  . \  >  (  i=k  and  (  5  "  3  1  b  )  m=0  As compared t o p e r i o d i c r e s e t t i n g o r pseudo-random r e s e t t i n g , PCM u p d a t i n g w i l l no doubt p e r f o r m b e t t e r . more c o m p l i c a t e d ,  However, the l a t t e r i s much  s i n c e two d i f f e r e n t q u a n t i z e r s are r e q u i r e d .  Moreover,  the average number o f b i t s p e r sample i s a l s o l a r g e r due t o the use o f a more p r e c i s e  quantizer.  Limb and Mounts [45] a l s o proposed a method f o r combating channel  e r r o r s i n DPCM systems.  They suggested the use o f a  pre-assigned  number a t the end o f a b l o c k o f samples a t the t r a n s m i t t e r . m i s s i o n , the decoder a t t h e r e c e i v e r s h o u l d r e c o v e r  t o the same number.  I f i t does n o t , t h e n t r a n s m i s s i o n e r r o r s must have o c c u r r e d , the b l o c k of samples i s r e p l a c e d by an m a t i o n can be based on the p r e v i o u s previous  lines.  not too n o i s y complexity  This technique  estimate  After trans-  i n w h i c h case  o f the b l o c k .  The  esti-  l i n e o r the average of the n e x t and  w i l l be s a t i s f a c t o r y when the c h a n n e l i s  and t h e b l o c k s i z e M i s n o t too l a r g e .  Of c o u r s e ,  the  o f the system w i l l be g r e a t l y i n c r e a s e d i n o r d e r t o i n c o r p o r a t e  an e s t i m a t i o n scheme f o r erroneous b l o c k s . Connor e t a l . [46] have s t u d i e d a DPCM system w h i c h uses the  average o f t h e p r e v i o u s sample and the sample above and t o t h e r i g h t o f the sample b e i n g encoded as a p r e d i c t i o n and found t h a t c h a n n e l e r r o r s i n t h i s system a r e much l e s s v i s i b l e than those i n p r e v i o u s - s a m p l e system.  feedback  T h i s system i n f a c t i s v e r y s i m i l a r t o t h e l i n e - a n d - s a m p l e  feed-  back system d i s c u s s e d i n S e c t i o n 4.6.  5.6  Subjective Evaluation The  output s i g n a l - t o - n o i s e r a t i o o f mean-square e r r o r i s a  c o n v e n i e n t and good measure o f t h e performance o f a communication  system.  I t i s m a t h e m a t i c a l l y t r a c t a b l e and thus can s e r v e as a f i r s t s t e p i n system a n a l y s i s o r d e s i g n .  The d i s a d v a n t a g e o f t h i s measure i s t h a t i t  may n o t i n d i c a t e e x a c t l y t h e s u b j e c t i v e q u a l i t y o f t h e system. In  t h i s s e c t i o n , we s h a l l s u b j e c t i v e l y e v a l u a t e t h e e f f e c t i v e -  ness o f c e r t a i n s i m p l e e r r o r - c o m b a t i n g schemes by u s i n g t h e v i d e o images shown i n F i g . 11 as i n p u t s i g n a l s .  5.6.1  P r e p a r a t i o n o f Video In  Samples  o r d e r t o p r o c e s s s i g n a l s o f z e r o mean v a l u e , t h e average o f  a l l t h e 512x512 p i c t u r e e l e m e n t s , w h i c h a r e p o s i t i v e i n t e g e r s ranging- from 0 t o 257, o f each p i c t u r e was f i r s t each o f t h e s e p i c t u r e elements.  c a l c u l a t e d and t h e n s u b t r a c t e d from  A f t e r p r o c e s s i n g by s i m u l a t i o n , t h e  r e c e i v e d p i c t u r e elements were r e p r e s e n t e d by 3 2 - b i t r e a l numbers. (The word l e n g t h o f s i n g l e - p r e c i s i o n r e a l numbers o f t h e IBM 360/67 computer i s 32 b i t s . )  F o r d i s p l a y , t h e mean v a l u e o f t h e p i c t u r e p r o c e s s e d was added  back t o each o f these r e a l numbers and t h e r e s u l t was t h e n l i m i t e d w i t h i n 0 and 257.  F i n a l l y , t h e r e s u l t i n g r e a l number was rounded i n t o t h e n e a r e s t  i n t e g e r and then r e p r e s e n t e d a g a i n as an 8 - d i g i t b i n a r y number.  The p i c t u r e elements o b t a i n e d  from t h i s p r o c e d u r e were d i s p l a y e d  on a L i t t o n I n d u s t r i e s ' LP203 phosphor s c r e e n by u s i n g a P r e c i s i o n D i s p l a y System, Model Ds0502-B1520-100-l, made by C e l c o . c o n t r o l l e d w i t h a Supernova computer.  display unit  To make sure t h a t each f i l m was  P/N.  p r o p e r l y exposed, a 1 5 - l i n e  appended t o the bottom o f each p i c t u r e .  ness i n t e n s i t y o f the d i s p l a y u n i t was  was  P i c t u r e s were then t a k e n from the  s c r e e n w i t h P o l a r o i d 4x5 Land f i l m s , Type 55  l e v e l gray s c a l e was  The  8-  The b r i g h t -  so a d j u s t e d t h a t i n each p i c t u r e  the gray l e v e l s r a n u n i f o r m l y from the d a r k e s t at the l e f t - m o s t l e v e l t o the b r i g h t e s t at the r i g h t - m o s t  level.  F o r convenience i n c o m p a r i s o n , the e r r o r p a t t e r n s were the same f o r p i c t u r e s h a v i n g i d e n t i c a l channel b i t - e r r o r p r o b a b i l i t y p. These e r r o r p a t t e r n s were g e n e r a t e d from a pseudo-random number g e r e r a t o r d e s c r i b e d i n S e c t i o n 4.3. 100  and the n o r m a l i z e d  The  q u a n t i z e r was  o v e r l o a d l e v e l V/a  as  l o g a r i t h m i c w i t h K = 4, u =  = 20dB. e  5.6.2  E f f e c t o f Feedback C o e f f i c i e n t s F i g s . 40, 41 and 42 show the p i c t u r e s o b t a i n e d  from the  sample feedback DPCM system w i t h cb= 10, 8 and 6 dB, r e s p e c t i v e l y . v a l u e s f o r the feedback c o e f f i c i e n t ct^ were c o n s i d e r e d i s , ct^ = p^, 0.9  and  i n each c a s e ,  that  Although  the p i c t u r e s are almost as good  t h e r e are f i v e e r r o n e o u s b i t s i n each p i c t u r e ,  they are h a r d l y d e t e c t a b l e e x c e p t some i n (a) and degradation  Three  0.8.  I n F i g . 40, where cb = 10 dB, as the o r i g i n a l s .  previous-  i n p i c t u r e q u a l i t y when cx^ = 0.9  (d) , where ct^ = p^.  and 0.8  The  as compared to ct^ =  i s almost i n v i s i b l e . When the channel becomes n o i s i e r , however, the advantage of  p^  using smaller value of  i s a p p a r e n t , as shown i n F i g s . 41 and 42.  When  ct^ = p , t h e h o r i z o n t a l s t r e a k s , w h i c h s t a r t a t t h e p o i n t s where c h a n n e l e r r o r s o c c u r , a r e l o n g and c l e a r ; whereas when  = 0.9, t h e l e n g t h o f  t h e s e s t r e a k s i s g r e a t l y r e d u c e d , and i n t h e case p f  = 0.8, t h e s t r e a k s  appear o n l y as s h o r t and s m a l l dashes. These f i g u r e s c o n f i r m t h e c o n c l u s i o n made i n t h e e a r l i e r l y s i s that a desirable choice f o r  ana-  i s near i t s optimum v a l u e f o r n o i s y  c h a n n e l when t h e system i s t o o p e r a t e i n b o t h n o i s e l e s s and n o i s y e n v i r o n ment.  The v a l u e o f S N R f o r each p i c t u r e i s a l s o shown i n t h e s e f i g u r e s . o  By c o m p a r i s o n , i t appears t h a t S N R ^ i s a good measure o f t h e s u b j e c t i v e quality too. P i c t u r e s o b t a i n e d from t h e l i n e - a n d - s a m p l e feedback DPCM system are shown i n F i g s . 43, 44 and 45 f o r <J) = 10, 8 and 6 dB, r e s p e c t i v e l y . A g a i n , t h r e e s e t s o f feedback c o e f f i c i e n t s and were compared, namely, a, = cc, , ct„, =a„ ; a, = 0.5, a„ = 0.5; and a, = 0.3725, a„ = 0.5. The 1 lc N Nc 1 N 1 N T  set  =  T  = 0.5 was s e l e c t e d because i t i s v e r y c o n v e n i e n t i n d i g i t a l  r e a l i z a t i o n and has been used i n p r a c t i c a l d e s i g n . made  and  Although t h i s choice  l i e on t h e s t a b i l i t y boundary, t h e system s t a b i l i t y was  not a s e r i o u s problem because t h e p r e d i c t o r was r e s e t a t t h e b e g i n n i n g o f each l i n e and t h e number o f l i n e s was f i n i t e .  The s e t ct^ = 0.3725 and  ct^ - 0.5 was chosen b e c a u s e , as shown i n S e c t i o n 4.6.4, i t i s easy t o implement d i g i t a l l y and t h e r e s u l t i n g  SNR  q  i s h i g h and a l s o f a i r l y  insen-  s i t i v e t o v a r i a t i o n s i n cb and p . .. 1,3  U n l i k e t h o s e i n t h e p r e v i o u s - s a m p l e feedback system, c h a n n e l e r r o r s i n t h e l i n e - a n d - s a m p l e feedback system show up as s t r e a k s w i t h w i d e r and l i g h t e r t a i l i n t h e d i a g o n a l d i r e c t i o n . three sets of  and  F o r a good c h a n n e l , t h e  y i e l d almost i d e n t i c a l p i c t u r e q u a l i t y , as shown  i n F i g . 43. When t h e c h a n n e l i s n o i s y , however, t h e c h o i c e and  = 0.3725  = 0.5 i s most d e s i r a b l e , i n w h i c h case t h e e f f e c t o f a c h a n n e l  e r r o r i s v i s i b l e o n l y a t t h e spot where t h e e r r o r o c c u r s , as shown i n F i g s . 44 and 45. F o r a g i v e n v a l u e o f <b, t h e l i n e - a n d - s a m p l e  = 0.3725 and ct^ = 0.5 a l s o appears t o y i e l d b e t t e r p i c t u r e  system w i t h  q u a l i t y than t h e p r e v i o u s - s a m p l e  5.6.3  feedback  P e r i o d i c and Pseudo-Random  feedback system.  Resettings  F i g s . 46 and 47 show t h e p i c t u r e s o b t a i n e d from t h e p r e v i o u s sample feedback system w i t h p e r i o d i c r e s e t t i n g f o r <k = 8 and 6 dB, r e s pectively.  Three d i f f e r e n t b l o c k s i z e s a r e compared i n each c a s e ; i . e . ,  M = 512, 128 and 32.  when M =512, t h e p r e d i c t o r was r e s e t o n l y a t t h e  b e g i n n i n g o f each l i n e .  The s t r e a k s t h e r e f o r e a r e v e r y l o n g .  reduced, t h e l e n g t h of t h e s t r e a k s i s a l s o reduced.  When M i s  However, s e v e r a l  v e r t i c a l l i n e s do show up as p r e d i c t e d i n S e c t i o n 5.3. These v e r t i c a l l i n e s a r e p a r t i c u l a r l y v i s i b l e i n b l a c k a r e a s , where a m p l i t u d e i s most  overload  severe. F i g s . 48 and 49 show t h e p i c t u r e s o b t a i n e d from pseudo-random  resetting.  The p r e d i c t o r was r e s e t t o z e r o a p p r o x i m a t e l y  once e v e r y M  samples, where M = 512, 128 o r 32. No v e r t i c a l l i n e s as t h o s e i n F i g s . 46 and 47 can be seen i n t h e s e p i c t u r e s .  The improvement i n q u a l i t y when  M = 32 over M = 512 i n t h i s case i s a l s o g r e a t e r than t h e s i m i l a r i m p r o v e ment f o r p e r i o d i c r e s e t t i n g .  Some s t r e a k s , however, a r e s t i l l v e r y  long  even when M = 32. These l o n g s t r e a k s c a n be s h o r t e n e d by l i m i t i n g t h e b l o c k s i z e generated  by t h e pseudo-random number g e n e r a t o r  w h i c h i s s l i g h t l y h i g h e r t h a n M.  to a value  (a)  a - p =0.9569 1 1  (a) a =0.9 1  SNR =25.98dB o  (d) a =p =o.9809 1 1  SNR =29.52dB o  SNR =25.84dB o  (e) a =0.9 1  SNR =28.79dB o  SNR =24.74dB o  (f) a =0.8 1  SNR =26.81dB o  m (c) 3 =0.8 1 F i g . 40.  P i c t u r e s obtained from a 4-bit previous-sample feedback DPCM with <j=10dB or p=3.9*10 .  (a) a - o =0.9569  SNR =20.71dB  (e) a =0.9 1  SNR =26.00dB o  ( f ) a =0.8 1  SNR =24.75dB o  P  (c) a =0.8 1 F i g . 41.  SJTR =22.79dB o  P i c t u r e s obtained from a 4 - b i t previous-sample feedback DPCM with cb=8dB o r p=1.9*10 .  (c) a =0.8 1 F i g . 42.  SNR =15.76dB o  ( f ) a =0.8 1  SNR =17.46dB o  P i c t u r e s obtained from a 4 - b i t previous-sample feedback DPCM with cb=6dB or p=2.4*10 .  123  F i g . 43.  P i c t u r e s obtained from a,4-bit line-and-sample feedback DPCM with <{.=10dB o r p=3.9*10 .  124  (c) cij-0.3725 0^=0.5 F i g 44.  ( f ) 0^=0.3725 <*=0.5 N  P i c t u r e s obtained from a 4 - b i t line-and-sample feedback DPCM with <j>=8dB or p-l.9x10"*.  125  (a) a - a . =0.4291 a =a =0.5621 1 l c N Nc  (d) a -a, =0.2690 a - a =0.7240 "1 ~ l c N Nc  XT  A (b) a - 0 . 5  a =0.5  pq  —  iiJL " i\  (e) a - 0 . 5  N  a  N  = 0  -  Pi  5  PQ  co  Pi  r W  ( f ) c^-0.3725 c ^ - 0 . 5  ( c ) 0^=0.3725 0^=0.5 F i g . 45.  Li  P i c t u r e s o b t a i n e d from a 4 - b i t l i n e - a n d - s a m p l e w i t h 4=6dB o r p = 2 . 4 x l 0 . -3  feedback  DPCM  . 46.  P i c t u r e s o b t a i n e d f r o m a 4 - b i t p r e v i o u s - s a m p l e f e e d b a c k DPCM w i t h p e r i o d i c r e s e t t i n g ; a =o , £=8dB.  (b) M=128  SNR =11.36dB  (e) M=128  SNR =11.93dB  F i g . 47. P i c t u r e s obtained from a 4-bit previous-sample feedback DPCM with p e r i o d i c r e s e t t i n g ; a =p , cb=6dB.  128  r  (d) M=512 SNR =22.02dB o  F i g . 48.  P i c t u r e s o b t a i n e d from a 4 - b i t p r e v i o u s - s a m p l e f e e d b a c k DPCM w i t h pseudo-random r e s e t t i n g ; a =p , cb=8dB.  129  (a\  M=S1?  CJMP  o  =11  CtOAU  (d) M=512 SNR =11.18dB o  _  - 1 (b) M=128 SNR =11.22dB o  (e) M=128 SNR =11.59dB o  ( f ) M=32dB SNR =12.93dB (c) M=32 SNR =11.78dB o o F i g . 4 9 . P i c t u r e s o b t a i n e d from a 4 - b i t p r e v i o u s - s a m p l e f e e d b a c k DPCM w i t h pseudo-random r e s e t t i n g ; a^=o^, c£=6dB.  VI.  6.1  DPCM SYSTEMS  WITH COARSE  QUANTIZATION  Introduction I n most o f t h e p r e v i o u s  quantization noise q  a n a l y s i s , we have assumed t h a t t h e  f e e d i n g i n t o t h e p r e d i c t o r i s n e g l i g i b l e and,  2 2 t h e r e f o r e , t h e r a t i o a /a can be s i m p l i f i e d as i n (2.29). e x obtained  by u s i n g t h i s e q u a t i o n  Results  can thus be used w i t h c o n f i d e n c e  t h e number o f q u a n t i z a t i o n l e v e l s L i s n o t t o o s m a l l  only i f  ( t y p i c a l l y L z 8) .  Because o f t h e i r s i m p l i c i t y and low b i t r a t e , D P C M systems w i t h coarse q u a n t i z a t i o n are very a t t r a c t i v e .  Recently,  S t r o h and  B o o r s t y n [47] have s t u d i e d t h e e f f e c t o f q u a n t i z a t i o n n o i s e through the p r e d i c t o r .  However, t h e i r method o f c a l c u l a t i n g t h e optimum  p r e d i c t o r c o e f f i c i e n t s and t h e r e s u l t i n g S N R apply  i n practice.  fedback  q  i s t e d i o u s and d i f f i c u l t t o  A l s o , t h e y have assumed t h a t t h e p r e d i c t o r o p e r a t e s  on an i n f i n i t e number o f p r e v i o u s  samples; whereas i n p r a c t i c a l s i t u a t i o n s ,  o n l y a few ( u s u a l l y one o r a t most two) p r e v i o u s  samples a r e used.  O'Neal  [48] has a l s o s t u d i e d t h e e f f e c t o f f e d b a c k q u a n t i z a t i o n n o i s e on t h e performance o f D P C M systems e x c i t e d by f i r s t - o r d e r Markov  processes.  I n t h i s c h a p t e r , we s h a l l d e r i v e s i m p l e e q u a t i o n s f o r t h e c o e f f i c i e n t s o f t h e optimum l i n e a r p r e d i c t o r and f o r t h e r e s u l t i n g SNR^, assuming t h a t t h e q u a n t i z e r i s chosen t o m i n i m i z e t h e q u a n t i z a t i o n I t i s shown t h a t when t h e q u a n t i z a t i o n n o i s e i s c o n s i d e r e d  noise.  i n optimizing  the p r e d i c t o r , improved p r e d i c t i o n o c c u r s , w i t h t h e r e s u l t t h a t f o r n o i s e l e s s communication c h a n n e l s , SNR^ i s l a r g e r when t h e q u a n t i z a t i o n i s used t o o p t i m i z e previous  chapters,  t h e p r e d i c t o r t h a n when i t i s n e g l e c t e d .  noise  As i n t h e  t h e 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 P ( ° 0 i s assumed t o e  be independent o f { a . } , and x. and e. a r e assumed t o have i d e n t i c a l  distribution function.  I n p a r t i c u l a r , i t w i l l be assumed t h a t x.  and  thus e. are G a u s s i a n . 1  The  system w i l l be o p t i m i z e d  channel i s n o i s e l e s s . t i z e r and  the l i n e a r p r e d i c t o r .  The  e f f e c t of c h a n n e l e r r o r s on  Examples f o r one-  sample feedback systems are f i n a l l y  Optimum  transmission  T h i s i n v o l v e s the j o i n t o p t i m i z a t i o n of the quan-  optimum system i s then d i s c u s s e d .  6.2  by assuming t h a t the  and  studied i n Section  the  two-previous6.5.  Quantizer  L e t u^, i = 1,**',L+1, and v.., j = l ' t  , m  ,L,  be the  transition  and o u t p u t l e v e l s , r e s p e c t i v e l y , of the q u a n t i z e r , as shown i n F i g . 2. Then, i t can be shown t h a t the v a l u e s square q u a n t i z a t i o n e r r o r  of u. and  between the i n p u t and  must s a t i s f y t h e . f o l l o w i n g system o f e q u a t i o n s ~ 1 U  =  "L+l  v. t h a t m i n i m i z e the meanoutput of the  quantizer  [28].  "  =  u. = (v.+v. ,)/2 l l i - i  i = 2,  •••  ,L  (6.1a)  u. ,, /  (v.-a) p (a) da = 0 l e  u. l  i = 1,  •••  , L  (6.1b) 2  The  r e s u l t i n g minimum mean-square e r r o r , n o r m a l i z e d  1 e  q ^  = 1 -  ± r  a  i+1 E f . .. u. i=l l L  2 e  with respect  to cr , i s  U  v.ap I  *e  (a) da  (6.2)  S i n c e e^ i s e s s e n t i a l l y G a u s s i a n and s i n c e the q u a n t i z e r i s a memoryless n o n l i n e a r element, i t can be r e a d i l y shown t h a t the c o r r e l a t i o n between the q u a n t i z e r o u t p u t s_^ and  any  Gaussian s i g n a l w  t o the c o r r e l a t i o n between the q u a n t i z e r i n p u t e. and w.  i s related  as f o l l o w s  [49].  1 k+1 E f s . w . l = E[e.w.l —x- E / 1 i l i 2 , , u, a k=l k e L  J  U  J  = E[e.w.] I t follows from (6.3)  (6.3)  (1-E ) q  J  1  av, p (a) da k e  that  E[q.w.l =E[s.w.] - E[e.w.] = -e E[e.w.] i 3 13 q i 3  (6.4)  T h i s r e l a t i o n w i l l be u s e f u l i n the s e q u e l .  6.3  Optimum Predictor 2 Since y\ = x^ + q^, the mean-square p r e d i c t i o n error  given  i n (2.28) can be rewritten as follows. N N N a = a - 2 E a.R ( i ) + E E a.a.R ( i - k ) j - i^ j = i k=i J y e  x  x  (6.5)  y  where R and  x y  ( j ) = Etx.y.^]  R (j) y  = E[y.y.  (6.6a)  .]  (6.6b)  11-3  By d i r e c t d i f f e r e n t i a t i o n , i t can be shown that the values of a^, •••  ,a^  2 that minimize a  must s a t i s f y the following system of equations.  &  N E a.R (j-n) 3 y  (n) =  R xy  j  =  n - 1 , ••• ,N  (6.7)  1  2 The r e s u l t i n g minimum value of 2 a  e  2 =  It i s noted that (6.7)  a  is  N  -  x  .  E  = 1  a.R (j) j xy  (6.8)  also implies the orthogonality between e  i  and y ,  i.e., R  (n) = E [ e . y . ] = 0 ey i i-n J  n = 1,  ••• ,N  (6.9)  t h e d i f f i c u l t y i n the c a l c u l a t i o n o f a^, ••• , a^ d i r e c t l y  from  (6.7) i s t h a t R (k) and R (k) , b e i n g dependent on R (k) and R (k) , a r e xy y o r xq q n o t known.  I t w i l l be shown below t h a t i f b o t h t h e q u a n t i z e r and t h e 2  2  p r e d i c t o r a r e optimum, a,, ••• ,ot and a /a can be c a l c u l a t e d I N e x  easily.  We n o t e h e r e t h a t R (n) = R (n) + R (n) and R (n) = R (n) + xy x xq y x R (n) + R (-n) + R ( n ) . T h e r e f o r e , i f IR ( n ) I « I R (n)I and IR ( n ) I « xq xq q ' q x xq 1  1  1  1  1  1  | R ( n ) | , t h e n (6.7) and (6.8) reduce t o e q u a t i o n s o b t a i n e d when fedback x  q u a n t i z a t i o n n o i s e i s n e g l e c t e d , as shown i n S e c t i o n 2 . 5 .  6.4  Optimum Q u a n t i z e r and P r e d i c t o r Assume now t h a t b o t h t h e q u a n t i z e r and t h e p r e d i c t o r a r e  optimum i n t h e sense t h a t b o t h e L>4 and  2  q  2  and a /a a r e m i n i m i z e d . e x  Since f o r  y. = x. + q. i s a l s o e s s e n t i a l l y G a u s s i a n [ 4 7 ] , we h a v e , from (6.4) ^i x x n  (6,9), R qy  (n) = E[q.y. ] = -e E [ e . y . ] = 0 'l^i-n q x-'x-n  or  R q  x  ^  " q  =  R  n = 1,  ( n )  n = 1, ••• ,N  ,N  (6.10a)  (6.10b)  S i n c e R (n) i s r e a l and even, R (n) = R (-n) f o r n = 1, ••• ,N and thus q ' qx qx R  (-n) = 0  n = 1, ••• ,N  (6.10c)  qy I n f a c t , (6.10a) and (6.10c) a r e a l s o t r u e f o r n = 0, because R  qx  (0) = E [ q . x . ] = -e E [ e . x . ] ii q i i n  = -e E [ ( x . q i  N Z j  =  1  a.y. . ) x . ] J i-3 i  = -e a = - R (0) q e q  (6.10d)  2  I t f o l l o w s from (6.7) and (6.10)  that  134  N R (n) = R (-n) = E xy xy' .  = 1  a.R ( j - n ) J xy  n = 1, ••• ,N  (6.11)  From (6.5) and ( 6 . 1 1 ) , we have R(n)  (n)  = -R  XQ  |n| = 1 ,  ••• ,N  (6.12)  X^i  However, f o r optimum q u a n t i z e r , we have, from (6.4)  R (n) = -e R (n) xq q xe Since  fora l l n  (6.13)  i s always l e s s than 1 when t h e q u a n t i z e r i s optimum [ 3 0 ] , (6.12)  and (6.13) can be s a t i s f i e d i f and o n l y i f  R  (n) = R  xq  In  (n) = 0  xe  1  The s u b s t i t u t i o n o f (6.14) i n t o  = 1, ••• ,N  (6.14)  1  (6.11) and (6.8) y i e l d s  N cb(n) =  E a.<Kj-n) 3=1 N n= 1 - 3=1 E a.p(n)  n = 1, * * * ,N  (6.15)  3  (6.16)  3  2 2 where n = a la and e x ' p(n) = R ( n ) / a x x 2  + (n)  1-  2 2 a q/ a x =* 1 • - neq  n - 1 , ••• ,N (6.17) n = 0  I t i s n o t e d t h a t t h e above r e s u l t s a r e v e r y s i m i l a r t o those o b t a i n e d w i t h fedback q u a n t i z a t i o n n o i s e n e g l e c t e d  as g i v e n i n S e c t i o n 2.5;  the o n l y d i f f e r e n c e i s t h a t p(0) = 1 i n (2.41) i s now r e p l a c e d by co(0) = 1 - ne . q  S o l u t i o n s f o r a., ••• ,a„ and n i n t h e p r e s e n t I N  case,  however,  a r e more c o m p l i c a t e d , because a^ and n a r e i n t e r r e l a t e d i n (6.15) and (6.16)  To s o l v e these e q u a t i o n s , we may  s u b s t i t u t e (6.16) i n t o  (6.15) and  s o l v e the r e s u l t i n g N n o n l i n e a r e q u a t i o n s , b u t the p r o c e d u r e t e d i o u s and cumbersome.  I n s t e a d , we  i s very  c o n s i d e r the f o l l o w i n g method.  D e n o t i n g CXQ = -1 as b e f o r e , we as  then  can combine (6.15) and  (6.16)  follows, N S j=0  -(l-e )n  n = 0  q  a.cf>(j-n) 3  (6.18) n = 1,  .N  C o n s i d e r (6.18) as a s e t o f s i m u l t a n e o u s l i n e a r e q u a t i o n s w i t h unknowns a^, a ^  and a^.  s  S o l v i n g f o r a^, s e t t i n g a  n  (N+1)  = -1 and  rear-  ranging y i e l d s  l-n P  H(n)  N l  ^ q  = p(i).  N-1  Note t h a t H(ri)  c o e f f i c i e n t s are independent reduces  l  1-ne  =  P  where  M  P  J  N-1  J  N-2  i s a p o l y n o m i a l o f degree N+1  of a , l'  to a f i r s t order equation.  i s decreased.  (6.19)  1-ne  N-2  ,a . N 1T  If e  =0,  and i t s  then  (6.19)  q  A l t h o u g h i n g e n e r a l (6.19) has  r o o t s , t h e r e i s o n l y one r o o t w h i c h w i l l approach e  = 0  the r o o t f o r  N+1 = 0 when  T h i s w i l l become e v i d e n t i n the f o l l o w i n g examples.  q Once n i s c a l c u l a t e d , the optimum p r e d i c t o r c o e f f i c i e n t s a^, be found from (6.18) w i t h o u t The a n o t h e r form.  •••  can  difficulty.  n o r m a l i z e d p r e d i c t i o n e r r o r n can a l s o be e x p r e s s e d i n C o n s i d e r t h a t tj>(i) i n (6.18) are unknown v a r i a b l e s .  s o l v i n g f o r <i(0) from  ( 6 . 1 8 ) , we have  Then,  cb(0) = Q ( l - e ) where Q i s g i v e n i n ( 2 . 2 6 ) .  (6.20)  S u b s t i t u t i n g (6.17) i n t o (6.20) and s o l v i n g  for n yields 1  (6.21)  Q-(Q-l)e  I t i s i n t e r e s t i n g t o n o t e t h a t i f Q > 1, w h i c h i s u s u a l l y the c a s e , n as g i v e n by (6.21) i s s m a l l e r than t h e v a l u e o f n when e = 0 . q  then  In other  words, t h e fedback q u a n t i z a t i o n n o i s e has t h e e f f e c t o f r e d u c i n g t h e p r e d i c t i o n e r r o r n.  T h i s improvement i n p r e d i c t i o n i s due t o t h e f a c t  t h a t t h e q u a n t i z a t i o n n o i s e q. a l s o c o n t a i n s some i n f o r m a t i o n about x.. l  I  I t f o l l o w s t h a t t h e a c t u a l v a l u e o f SNR  as o b t a i n e d from (2.12) and o  (6.21) i s l a r g e r than when t h e fedback n o i s e i s n e g l e c t e d when t h e t r a n s m i s s i o n channel i s n o t t o o n o i s y . U s i n g (6.21) we can a l s o w r i t e t h e f a c t o r m u l t i p l y i n g t h e PCM channel e r r o r e  as f o l l o w s .  n  i  Q°e x /g  =  1-(1-1/Q)  £q  "  1  ( 6  -  2 2 )  T h e r e f o r e , a l t h o u g h t h e e f f e c t o f channel n o i s e on DPCM w i t h c o n v e n t i o n a l optimum l i n e a r p r e d i c t o r i s t h e same as t h a t on PCM when t h e fedback q u a n t i z a t i o n n o i s e i s n e g l e c t e d (see S e c t i o n 2 . 5 ) , t h i s i s no l o n g e r t r u e when t h e fedback q u a n t i z a t i o n n o i s e i s taken i n t o account.  Despite i t s  advantage i n i m p r o v i n g t h e p r e d i c t i o n , i t makes t h e system more s u s c e p t i b l e to channel n o i s e .  6.5  I l l u s t r a t i v e Examples C o n s i d e r e d i n t h e f o l l o w i n g a r e t h e one- and t w o - p r e v i o u s -  sample feedback systems.  6.5.1  One-Previous-Sample Feedback When N = 1, we have, from ( 6 . 1 9 ) ,  H(n)  = e n  2  -  )n  (1+e  q  +  (1-P?) = 0  q  (6.23)  1 .  The two r o o t s o f t h i s e q u a t i o n are  n = {1 + e  ± [(1-e ) q q  2  2 ' /2 + 4p^e ] }/2e i q q 1  (6.24)  To d e t e r m i n e w h i c h of t h e s e two r o o t s s h o u l d be chosen, we make e  approach q  0;  f o r "+" lim n = • 2 e -+0 1 - p. V . 1 q  S i n c e n = 1-P^ when  sign  f o r "-"  sign  = 0, we c o n c l u d e t h a t "-" s i g n i n (6.24) s h o u l d be  s e l e c t e d ; thus  n = {1 + e  - [(1-e ) q q  2  + 4p e ] i q 2  1 / 2  }/2e  (6.25) q  The s u b s t i t u t i o n o f (6.25) i n t o (6.17) and (6.15) g i v e s the optimum v a l u e of  as f o l l o w s .  a  1  = -{1 - e  q  - [(1-e ) q  2  + 4p e ] 1 q 2  1 / 2  }/2  e 1 q  P l  n  (6.26)  The optimum v a l u e s o f ri and a, a r e p l o t t e d as a f u n c t i o n o f e 1 q i n F i g . 50, assuming t h a t p^ = 0.89. the number o f q u a n t i z e r o u t p u t b i t s K.  improvement i n o u t p u t S N R  less.  When  i n c r e a s e s , n d e c r e a s e s and  The a b s o l u t e v a l u e o f ri i n dB a l s o denotes  i n c r e a s e s as shown above. the  A l s o shown I n the h o r i z o n t a l s c a l e i s  q  f o r D P C M when t h e d i g i t a l c h a n n e l i s n o i s e -  When K = 2, t h i s improvement i s 7.2dB as compared t o 6.8dB when t h e  fedback q u a n t i z a t i o n n o i s e i s n e g l e c t e d .  When K = 1, t h e improvement i s  even g r e a t e r , b u t t h e e x a c t v a l u e i s somewhat s o u b t f u l , because t h e assumption made i n t h e a n a l y s i s may n o t a p p l y i n t h i s  6.5.2  Two-Previous-Sample Feedback L e t N = 2 i n (6.19).  H(n)  case.  = A q  - (2 + e )e n  3  2  Then, we have  + [ ( 2 - p - p ) e + 1 - p ]n 1 2 q 1 2  2  2  - p ] = 0  2  (6.27)  2  It i s d i f f i c u l t  - [1 + 2p (p„-l) 1 /  to express the roots o f t h i s equation  i n c l o s e d form.  However, t h e r o o t t h a t converges t o n = [1 + 2 p ( p - l ) - p ] / ( l - p ) 2  2  (6.28)  2  2  when  0 can be e a s i l y f o u n d n u m e r i c a l l y .  Shown i n F i g . 51 a r e t h e  optimum v a l u e s o f n, a, and a„ v s . E when p. = 0.89 and p_ = 0.65. I t 1 2 q 1 I i s n o t e d t h a t t h e fedback q u a n t i z a t i o n n o i s e c o n t r i b u t e s more s i g n i f i c a n t l y t o t h e improvement i n p r e d i c t i o n .  F o r example, when K = 2, t h e  r e d u c t i o n i n n i s more than IdB as compared t o 0.4dB f o r N = 1 i n S e c t i o n 6.5.1.  Both  and  a l s o change c o n s i d e r a b l y when t h e fedback q u a n t i -  z a t i o n noise i s considered.  139  F i g . 50.  Optimum v a l u e s o f ^ (6.26) v s . e  = a &  /  a  a n d x  a  ^  a s  f o r previous-sample  l e s s c h a n n e l ; p =0.89.  o b t a i n e d from  (6.25) and  feedback DPCM w i t h n o i s e -  51.  Optimum v a l u e s o f =o" /a , ] _ n  a  a  n  d  a  2  f  o  r  t w o  previous-sample  feedback DPCM as o b t a i n e d from (6.27) and (6.15) v s . e^; 0.89,  p =0.65. 2  P= 1  VII.  7.1  CONCLUSIONS  Summary o f the P r e s e n t Research V a r i o u s a s p e c t s o f DPCM systems o p e r a t i n g  channels have been i n v e s t i g a t e d i n t h i s s t u d y . are t h e r e s u l t s t h a t have been 1)  on n o i s y  communication  Summarized i n the f o l l o w i n g  obtained.  A n a l y t i c a l e x p r e s s i o n s f o r t h e mean-square d i s t o r t i o n and  of DPCM systems when c h a n n e l t r a n s m i s s i o n been d e r i v e d .  e r r o r s cannot be i g n o r e d  SNR  Q  have  As w i t h PCM, c o n t r i b u t i o n s t o o u t p u t s i g n a l d i s t o r t i o n can  be e x p r e s s e d as a sum o f t h r e e s e p a r a t e terms; namely, q u a n t i z a t i o n c h a n n e l e r r o r , and m u t u a l e r r o r .  error,  Each o f t h e s e e r r o r s i s f u r t h e r e x p r e s s e d  e x p l i c i t l y i n terms o f the c o r r e l a t i o n c o e f f i c i e n t s , q u a n t i z e r  and p r e d i c -  t o r p a r a m e t e r s , and c h a n n e l e r r o r p r o b a b i l i t y . 2)  The s t a b i l i t y o f t h e decoder has been i n v e s t i g a t e d .  The c o n s -  t r a i n t s on t h e p r e d i c t o r c o e f f i c i e n t s i n o r d e r f o r c h a n n e l e r r o r s n o t t o b u i l d up u n l i m i t e d l y have been p r e s e n t e d . 3)  The e f f e c t o f c h a n n e l e r r o r s on SNR  when t h e c o n v e n t i o n a l  opti-  o mum l i n e a r p r e d i c t o r i s used has been examined.  Transmission errors i n  t h i s case a r e found t o be no more s e r i o u s than f o r PCM, as has been s u g g e s t e d i n some e a r l i e r s t u d i e s .  In f a c t , i f the p r e d i c t o r c o e f f i c i e n t s  are chosen c a r e f u l l y , as demonstrated i n Chapter I V , t h e mean-square e r r o r r e s u l t i n g from c h a n n e l n o i s e 4)  can even be l e s s than t h a t f o r PCM.  The maximum v a l u e o f SNR  o b t a i n a b l e by DPCM has been d e r i v e d o and compared w i t h t h e t h e o r e t i c a l bound o b t a i n e d from t h e r a t e - d i s t o r t i o n f r n c t i o n . I t i s shown t h a t , f o r b o t h one- and t w o - d i m e n s i o n a l s i g n a l s , J  the SNR  o  o f DPCM can a c h i e v e a v a l u e t h a t i s o n l y two o r t h r e e  below t h e bound.  In f a c t , i f the transmission  decibels  r a t e i s not too s m a l l ,  142  DPCM can remove almost a l l t h e redundancy i n h e r e n t i n most s i g n a l s ; t h e d i f f e r e n c e between SNR o f DPCM and t h e t h e o r e t i c a l bound i s thus o  simply J  a result of quantization. 5)  A procedure f o r m a x i m i z i n g  SNR  Q  by t h e j o i n t o p t i m i z a t i o n o f  the q u a n t i z e r , p r e d i c t o r , s a m p l i n g r a t e , and bandwidth has been p r o p o s e d . In p a r t i c u l a r , equations  f o r t h e i n p u t t h r e s h o l d s and o u t p u t l e v e l s o f  the optimum q u a n t i z e r a r e d e r i v e d .  The o p t i m i z a t i o n o f t h e p r e d i c t o r ,  s a m p l i n g r a t e and bandwidth i s a l s o c o n s i d e r e d  separately.  t r a n s m i s s i o n r a t e , i t i s shown t h a t s a m p l i n g a t t h e N y q u i s t always y i e l d s t h e h i g h e s t S N R . q  For a fixed r a t e almost  When t h e s a m p l i n g r a t e i s N y q u i s t , t h e  t r a n s m i s s i o n r a t e R i s f i x e d , t h e i n p u t s i g n a l i s G a u s s i a n Markov, and the t r a n s m i s s i o n c h a n n e l i s n o i s e l e s s , t h e bandwidth W •= 0.66R i s found to o p t i m i z e SNR . The optimum v a l u e o f bandwidth i n c r e a s e s when t h e o c h a n n e l becomes n o i s y . 6)  Both one- and two-sample feedback systems, i n c l u d i n g p r e v i o u s -  l i n e - a n d - s a m p l e feedback DPCM f o r v i d e o s i g n a l s , have been a n a l y z e d i n detail.  These systems have a l s o been s i m u l a t e d w i t h a d i g i t a l computer  by u s i n g a r e a l speech sample and two v i d e o images as i n p u t s i g n a l s . The e x p e r i m e n t a l l y measured v a l u e s o f those c a l c u l a t e d i n each case.  SNR  q  a r e found t o agree v e r y w e l l w i t h  For a well-designed  DPCM system, the v a l u e  o f SNR^ i s shown t o be c o n s i d e r a b l y h i g h e r t h a n t h a t f o r a w e l l - d e s i g n e d PCM  o p e r a t i n g on t h e same t r a n s m i s s i o n c h a n n e l .  T h i s i s t r u e even when  the channel i s v e r y n o i s y . 7)  F o r o n e - p r e v i o u s - s a m p l e feedback system, c h o o s i n g  coefficient  7  t h e feedback  n e a r i t s optimum v a l u e f o r v e r y n o i s y c h a n n e l ,  i.e.,  =  2  (l-vl-pp/p^, desirable.  r a t h e r t h a n i t s c o n v e n t i o n a l v a l u e o f <x^=p^ i s found t o be most  When t h e c h a n n e l i s n o i s e l e s s , t h e d e g r a d a t i o n  i n performance  r e s u l t i n g from t h i s c h o i c e o f  i s very small.  When t h e c h a n n e l becomes  n o i s y , however, t h e e f f e c t o f c h a n n e l e r r o r s i s much l e s s s e v e r e than when  = p . The p i c t u r e s shown i n F i g s . 40 - 42 s t r o n g l y s u p p o r t  analytical 8)  this  result. The improvement i n S N R  q  when two p r e v i o u s samples a r e used f o r  p r e d i c t i o n i s f a i r l y s m a l l as compared t o t h e o n e - p r e v i o u s - s a m p l e system, even i f t h e t r a n s m i s s i o n c h a n n e l i s n o i s y .  feedback  This i s e s p e c i a l l y  true f o r video s i g n a l s . 9)  When t h e c h a n n e l i s n o i s e l e s s , a p p r o x i m a t e l y 2.6dB can be g a i n e d  by u s i n g t h e sample on t o p i n t h e p r e v i o u s l i n e , i n a d d i t i o n t o t h e p r e v i o u s sample, f o r t h e p r e d i c t i o n f o r t h e two v i d e o images shown i n F i g . 11.  The g a i n i n c r e a s e s when t h e c h a n n e l e r r o r p r o b a b i l i t y i n c r e a s e s .  At  _2 p = 7.9x10  , o r <j> = OdB, f o r example, an improvement o f 3.67dB f o r t h e  crowd scene and 4.51dB f o r t h e cameraman scene c a n be o b t a i n e d by f e e d i n g back t h e sample on t o p . 10)  The s e n s i t i v i t y o f SNR^ t o v a r i a t i o n s i n s i g n a l  statistics,  p a r t i c u l a r l y c o r r e l a t i o n c o e f f i c i e n t s , and c h a n n e l e r r o r p r o b a b i l i t y has been a n a l y z e d and i t s i m p l i c a t i o n s on t h e d e s i g n o f feedback noted.  coefficients  S p e c i a l a t t e n t i o n i s p a i d t o t h e s e l e c t i o n o f these c o e f f i c i e n t s  f o r t h e purpose o f d i g i t a l r e a l i z a t i o n . sample f e e d b a c k , f o r example,  F o r speech s i g n a l s w i t h p r e v i o u s -  = 0.75 i s found t o be a v e r y good c h o i c e .  F o r l i n e - a n d - s a m p l e feedback, on t h e o t h e r hand, i t i s most d e s i r a b l e t o use  = 0.3725 and cx^ = 0.5. 11)  V a r i o u s t e c h n i q u e s f o r combating  c h a n n e l n o i s e have been examined,  i n c l u d i n g c h a n n e l e n c o d i n g , p e r i o d i c r e s e t t i n g , pseudo-random r e s e t t i n g , and PCM u p d a t i n g .  F o r c h a n n e l e n c o d i n g , a t t e n t i o n i s devoted t o t h e use  of s i n g l e - e r r o r c o r r e c t i n g Hamming code, w h i c h i s f a i r l y s i m p l e i n s t r u c t u r e .  When the t r a n s m i t t e r i s h e l d c o n s t a n t , Hamming code i s found to p e r f o r m b e t t e r i f the t r a n s m i s s i o n c h a n n e l i s not too n o i s y , w i t h a maximum improvement i n SNR  o f a p p r o x i m a t e l y 1.5dB.  and easy to implement. 1.5dB  I t can a l s o a c h i e v e an improvement i n  f o r the two images shown i n F i g . 11.  from a m p l i t u d e o v e r l o a d appear e a s i l y detected.  However, e r r o r s  SNR  resulting  on the same v e r t i c a l l i n e and can be  errors.  The s u b j e c t i v e e f f e c t s o f c h a n n e l e r r o r s on v i d e o s i g n a l s  t r a n s m i t t e d w i t h v a r i o u s DPCM systems have a l s o been e v a l u a t e d . systems  of  q  The use o f a pseudo-random number g e n e r a t o r can e l i m i -  n a t e these annoying 12)  P e r i o d i c r e s e t t i n g i s simple  c o n s i d e r e d i n c l u d e p r e v i o u s - s a m p l e feedback f o r  The  = p^, 0.9  and  0.8, l i n e - a n d - s a m p l e feedback f o r a, = a., : CL, =CL, , a, = OL, = 0.5, and ' 1 lc' N Nc' 1 N ' OL^ = 0.3725; CL^ = 0.5, p r e v i o u s sample feedback w i t h p e r i o d i c and pseudo-random r e s e t t i n g . system w i t h and a  N  = 0.5  13)  = 0.8  I t i s found t h a t p r e v i o u s - s a m p l e  and l i n e - a n d - s a m p l e feedback system w i t h  feedback = 0.3725  are most f a v o r a b l e .  DPCM systems w i t h c o a r s e q u a n t i z a t i o n have been a n a l y z e d .  E q u a t i o n s f o r the optimum l i n e a r p r e d i c t i o n and the r e s u l t i n g assuming  resetting  t h a t Max  SNR , Q  q u a n t i z e r i s used and t h a t the t r a n s m i s s i o n c h a n n e l i s  n o i s e l e s s , are d e r i v e d .  I t i s shown t h a t the v a l u e o f  SNR  q  i s larger  when the fedback q u a n t i z a t i o n n o i s e i s used t o o p t i m i z e the p r e d i c t o r t h a n when i t I s n e g l e c t e d .  SNR  q  i n t h i s c a s e , however, i s more s e n s i t i v e  to c h a n n e l n o i s e .  7.2  S u g g e s t i o n s f o r F u r t h e r Research As a n a t u r a l e x t e n s i o n of the p r e s e n t s t u d y , work on the  lowing t o p i c s i s suggested.  fol-  1)  Formal s u b j e c t i v e e v a l u a t i o n o f t h e e f f e c t o f c h a n n e l n o i s e on  s t r a i g h t DPCM systems and those w i t h n o i s e - c o m b a t i n g this thesis,  SNR  q  schemes.  has been used as a c r i t e r i o n o f . s y s t e m  Throughout  performance.  A l t h o u g h i t i s one o f t h e b e s t o b j e c t i v e measures and i s a l s o a c o n v e n i e n t b a s i s f o r system a n a l y s i s and d e s i g n , i t may n o t t r u l y i n d i c a t e t h e subjective quality.  A f o r m a l s u b j e c t i v e e v a l u a t i o n , such as t h a t based on  isopreference testing or multi-scale rating, i s therefore 2)  suggested.  E f f e c t o f channel n o i s e on t h e performance o f a d a p t i v e d i f f e r e n -  t i a l systems.  Some a d a p t i v e d i f f e r e n t i a l systems, such as t h e , a d a p t i v e  AM proposed by J a y a n t  [ 5 0 ] , a r e v e r y a t t r a c t i v e because o f t h e i r  simplicity  and e f f i c i e n c y i n a c h i e v i n g a h i g h q u a l i t y a t a r e l a t i v e l y low b i t r a t e . U n f o r t u n a t e l y , most a d a p t i v e systems a r e v e r y s e n s i t i v e t o c h a n n e l n o i s e . To make these systems p r a c t i c a l and u s e f u l , an i n t e n s i v e , s t u d y o f t h e e f f e c t o f channel n o i s e s h o u l d be performed and, more i m p o r t a n t l y , s i m p l e and e f f e c t i v e schemes f o r combating c h a n n e l n o i s e s h o u l d be e x p l o r e d . 3)  Complete d i g i t a l r e a l i z a t i o n o f DPCM systems.  Advancement i n  modern t e c h n o l o g y has made d i g i t a l e l e c t r o n i c components more and more economical  and r e l i a b l e .  The f e a s i b i l i t y o f t h e complete d i g i t a l  reali-  z a t i o n o f DPCM systems and i t s e f f e c t on system performance s h o u l d t h e r e f o r e be f u r t h e r i n v e s t i g a t e d . 4)  Performance o f DPCM systems o p e r a t i n g on o t h e r t y p e s o f t r a n s -  m i s s i o n channel.  A l t h o u g h e x p r e s s i o n s f o r t h e mean-square e r r o r g i v e n i n  (2.10) and (2.11) o f t h i s t h e s i s a r e v e r y g e n e r a l , a l l o f t h e a n a l y s i s f o l l o w e d a r e based on t h e assumption t h a t c h a n n e l n o i s e samples a r e s t a t i s t i c a l l y independent.  I t i s o f i n t e r e s t t o l o o k i n t o how t h e system  performance i s a f f e c t e d by o t h e r types o f t r a n s m i s s i o n c h a n n e l , such as those w i t h i n t e r s y m b o l i n t e r f e r e n c e .  5)  DPCM systems w i t h t h r e e - d i m e n s i o n a l c o d i n g f o r v i d e o  signals.  In p a r t i c u l a r , i t i s o f i n t e r e s t t o i n v e s t i g a t e t h e e f f e c t o f p r e d i c t i n g a sample by u s i n g i t s s p a t i a l c o u n t e r p a r t on t h e i m m e d i a t e l y  previous  frame, a l o n g w i t h the p r e v i o u s sample and the sample on t o p , and compare the r e s u l t i n g  SNR  q  o r s u b j e c t i v e q u a l i t y w i t h t h a t o f one- and two-sample  feedback systems when they a r e o p e r a t i n g on t h e same d i g i t a l The e x p r e s s i o n s f o r S N R  q  derived i n this thesis s t i l l  channel.  apply i n t h i s  case.  The major d i f f i c u l t i e s i n t h i s s t u d y w i l l be t h e e v a l u a t i o n o f t h e f a c t o r Q and t h e d e r i v a t i o n o f s t a b i l i t y 6)  E f f e c t s o f more e l a b o r a t e c o d i n g schemes on t h e r e d u c t i o n o f  mean-square ing  constraints.  c h a n n e l e r r o r , p a r t i c u l a r l y those w i t h m u l t i p l e - e r r o r - c o r r e c t -  capability.  APPENDIX I Calculation  o f R (k) and R (k) n ^ qn^—'  Let P(A,B) and P(A/B) denote, r e s p e c t i v e l y ,  the j o i n t  o f e v e n t s A and B and the p r o b a b i l i t y o f the e v e n t A g i v e n B. denote t h e j o i n t a m p l i t u d e p r o b a b i l i t y d e n s i t y  o f e. and e. , . X  probability Let P (a,3) e  Quantities  X K.  r . , s., e., v. and u. are d e f i n e d i n F i g s . 1 and 2, w h i l e P.. and p (a) 1' 1 1 1 1 ' i j e 6  are  d e f i n e d i n S e c t i o n 2.3.1.  r  Then,  R (k) = E[n.n. . ] n i i-k L L L L E E E E ( v , - v ) ( v , - v ) P(r.=v, ls.=v , r . =v,,s. , ,,, ...... b a d c l b ' i a' i - k d i - k a=l b = l c = l d=l  v ) P ( r . , = v , , s . = v , s . , =v ) P(s.=v , s . =v ) c i-k d l a i-k c l a i-k c I f the d i g i t a l  c h a n n e l i s memoryless,  and i f P ( s . = v , s. . = v ) i s X  e x p r e s s e d i n terms o f p ( a , 3 ) ,  X K.  SL  L  L  c  then f o r k ^ 0,  a + l c+1 E E E E (v,-v )(v,-v ) P , P , / / n , , -, , -. b a d c ab cd u u a=l b = l c = l d=l a c L  R (k) = n  (1.1)  L  u  U  C  P (a,3)dctd3 e (1.2)  I f e. and e. , a r e s t a t i s t i c a l l y i n d e p e n d e n t , t h e n p (a,3) = P (ct)p (3) X X™K. G 6 6 and R (k) = [ E ( n . ) ] . n I 2  =  L L L u E E E jf ""-(v ~cO(v,-v ) P ( r . = v, | s. = v , r . , , b d c I b ' i a i-k b = l c = l d=l u a  v  N  = (1.3)  3  , c+1 v , , s . . = v ) P ( r . . = v , s. = v , s . . =v ) / P (a,3)dad3 d i-k c i-k d l a i-k c u &• c U  1  I f the d i g i t a l c h a n n e l i s memoryless, a+1 E E E / , . , ,, u b = l c = l d=l a L  R  qn 1  (k) =  L  L  U  then f o r k ^ 0  c+3 (v, - a ) ( v , - v )P , P , / b d c ab cd u c U  P (a,3)dad3 e  (1.4)  148  If e  1  and e  , are s t a t i s t i c a l l y i-k  i n d e p e n d e n t , t h e n (1.3) reduces t o  R ( k ) = E[q.] E [ n . . _ ] . q n  k  F u n c t i o n s R (0) and R (0) are g i v e n by ( 2 . 1 2 ) , (2.17) and n qn  (2.18)  APPENDIX I I Derivation  o f t h e O v e r a l l Mean-Square E r r o r  The b l o c k diagram o f F i g . 1 can be s i m p l i f i e d as shown i n F i g . 1.1, where G ^ ( f ) and ^ ( f ) a r e r e p l a c e d  by low-pass f i l t e r s  convenience i n the a n a l y s i s t o be f o l l o w e d , by  and, f o r  the p o s t - f i l t e r i s r e p r e s e n t e d  two l o w - p a s s - f i l t e r s ; one f o r r e p r o d u c i n g the a n a l o g s i g n a l and t h e  o t h e r f o r e l i m i n a t i n g the o u t - o f - b a n d e r r o r .  1  m(t) >-  -w  DIGITAL CODER DECODER AND CHANNEL  <(t) w  f >2w s  Fig.  1.1  l/f *»  s  I fs  I  1  x(t) >•  -w  x(t) w  D i g i t a l Communication System  The mean-square e r r o r between t h e i n p u t and o u t p u t o f t h e s y s tem i n F i g . I . 1 i s E{[x(t) - m(t)] } = E{[x(t) 2  = E{[x(t)  - x(t) + x(t) - m(t)] } 2  - x(t)]"> + 2 / S (f)df w m  (II.1)  The l a s t e q u a l i t y i n ( I I . 1 ) i s t r u e because x ( t ) - x ( t ) and x ( t ) - m ( t ) have no common f r e q u e n c y . as  The f i r s t term o f ( I I . 1 ) can a g a i n be w r i t t e n  follows. E{[x(t) - x ( t ) ] } = E{[x(t) - x(t) + x(t) - x ( t ) ] } 2  2  = E { [ x ( t ) - x ( t ) ] } + 2E{[x(t) - x ( t ) ] [ x ( t ) - x ( t ) ] } + E { [ x ( t ) - x ( t ) ] } 2  2  (II.2)  E{[x(t) - x ( t ) ] } = E[(x. - x . ) ] = 2  2  f 12 - f 12 s s f  S  d  ( f ) d f  ( I I > 3 )  150  where S ^ ( f ) i s t h e power s p e c t r a l d e n s i t y o f d^ = x^ - x^.  Since x ( t )  and x ( t ) - x ( t ) have no common f r e q u e n c y , the second term o f ( I I . 2 ) becomes 2 E { [ x ( t ) - x ( t ) ] [ x ( t ) - x ( t ) ] } = 2E{[x<t)-x(t)]  s  - f 12 s  x(t) }  s  f 12 f* ls;(f) + s;(-f)]df W x x  9  = - T~ r s  (ii.4)  where S ^ ( f ) i s the power s p e c t r a l d e n s i t y o f x^.  S i m i l a r l y , the f i r s t  term o f ( I I . 2) can be w r i t t e n i n terms o f S ~ ( f ) as f o l l o w s . f /2 E{[x(t) - x ( t ) ] } = j - / s  tS^(f) + S^(-f)]df  S W  (II.5)  S u b s t i t u t i n g (II.3) - (II.5) i n t o (II.2) y i e l d s E { [ x ( t ) - x ( t ) ] ) = fZ  f /2 f 12 f_\ S ( f ) d f - f- / [S^(f)+S-(-f)]df s s s  (II.6)  S  / 2  d  W  D e n o t i n g S ~ ( f ) i n terms o f S ( f ) , t h e power s p e c t r u m o f x., and S ( f ) , X  X  X  X Q  the cross-power s p e c t r u m o f x^ and d^, we have S^(f) = S ( f ) + S ( f ) + S * ( f ) + S ( f ) x  x d  x  (II.7)  d  S i n c e x. has no energy f o r W £ | f | £ f /2, X s f 12 f 12 f 12 S* s ; ( f ) d f = /• s (-f)df = / s (f)df s  W  x  W  x  W  A l s o , from ( 2 . 7 ) , i t can be shown t h a t S (f) - S ( f ) + S (f) F*(f) + S *(f) d  q  q n  (ii.8)  s  q  d  F(f)+ S (f) |F(f)| n  2  (II.9)  151  The  s u b s t i t u t i o n of  E{[x(t)-x(t)] } 2  ( I I . 8 ) and  = is  (II.9) into (II.6)  [S (f)+S  (f)F*(f)+S  yields  *(f)F(f)+S (f)|F(f)| ]df 2  n  (11.10) Substituting  (11.10) i n t o  (II.1) again gives  (2.15a).  152  REFERENCES  1.  A.H.  Reeves, F r e n c h P a t e n t No. 852,183, O c t o b e r 3, 1938.  2.  E.M. D e l o r a i n e and A.H. Reeves, "The 2 5 t h a n n i v e r s a r y o f p u l s e code m o d u l a t i o n " , IEEE Spectrum, v o l . 2, pp. 56-63, May 1965.  3.  B. D e r j a v i t c h , E.M. D e l o r a i n e , and S. van M i e r l o , F r e n c h P a t e n t No. 932,140, August 1946.  4.  C C . C u t l e r , " D i f f e r e n t i a l q u a n t i z a t i o n o f communication s i g n a l s " , P a t e n t No. 2,605,361, J u l y 29, 1952.  5.  H. van de Weg, " Q u a n t i z i n g n o i s e o f a s i n g l e i n t e g r a t i o n d e l t a modul a t i o n system w i t h an N - d i g i t code", P h i l i p s R e s e a r c h R e p o r t s , v o l . 8, pp. 367-385, October 1953.  6.  R.E. Graham, " P r e d i c t i v e q u a n t i z a t i o n o f t e l e v i s i o n s i g n a l s " , IRE Wescon Conv. Reed., P t . 4, pp. 147-157, August 1958.  7.  J.B. O'Neal, J r . , " P r e d i c t i v e q u a n t i z i n g systems ( d i f f e r e n t i a l p u l s e code m o d u l a t i o n ) f o r the t r a n s m i s s i o n of t e l e v i s i o n s i g n a l s " , B e l l S y s t . Tech. J . , v o l . 45, pp. 689-721, May/June 1966.  8.  "A bound on s i g n a l - t o - q u a n t i z i n g n o i s e r a t i o s f o r d i g i t a l e n c o d i n g systems", P r o c . IEEE, v o l . 55, pp. 287-292, March 1967.  9.  R.A. McDonald, " S i g n a l - t o - n o i s e and i d l e c h a n n e l performance o f d i f f e r e n t i a l p u l s e code m o d u l a t i o n systems - p a r t i c u l a r a p p l i c a t i o n s to v o i c e s i g n a l s " , B e l l S y s t . Tech. J . , v o l . 45, pp. 1123- 1151, S e p t ember 1966.  10.  K. N i t a d o r i , " S t a t i s t i c a l a n a l y s i s o f APCM", E l e c t r o n . Commun. J a p a n , v o l . 48, pp. 17-26, F e b r u a r y 1965.  11.  R.W. Donaldson and D. Chan, " A n a l y s i s and s u b j e c t i v e e v a l u a t i o n o f d i f f e r e n t i a l p u l s e - c o d e m o d u l a t i o n v o i c e communication s y s t e m s " , IEEE T r a n s . Commun. T e c h n o l . , v o l . C0M-17, pp. 10-19, F e b r u a r y 1969.  12.  R.W. Donaldson and R.J. D o u v i l l e , " A n a l y s i s , s u b j e c t i v e e v a l u a t i o n , o p t i m i z a t i o n , and comparison of the performance c a p a b i l i t i e s o f PCM, DPCM, AM, AM, and PM v o i c e communication s y s t e m s " , IEEE T r a n s . Commun. T e c h n o l . , v o l . COM-17, pp. 421-431, August 1969.  13.  R.J. A r g u e l l o , H.R. S e l l n e r , and J.A. S t u l l e r , "The e f f e c t of c h a n n e l e r r o r s i n the d i f f e r e n t i a l - p u l s e - c o d e - m o d u l a t i o n t r a n s m i s s i o n o f samp l e d imagery", IEEE T r a n s . Commun. T e c h n o l . , v o l . COM-19, pp. 926-933.  14.  J . Yan and R.W. Donaldson, " S u b j e c t i v e e f f e c t s o f c h a n n e l t r a n s m i s s i o n e r r o r s on PCM and DPCM v o i c e communication s y s t e m s " , IEEE T r a n s . Commun. T e c h n o l . , v o l . C0M-20, pp. 281-290, June 1972.  U.S.  153  15.  K.Y. Chang and R.W. Donaldson, " A n a l y s i s , o p t i m i z a t i o n , and s e n s i t i v i t y study o f d i f f e r e n t i a l PCM systems o p e r a t i n g on n o i s y communic a t i o n c h a n n e l s " , IEEE Trans. Commun., v o l . COM-20, pp 338-350, June 1972.  16.  A . J . Kurtenback and P.A. W i n t z , " Q u a n t i z i n g f o r n o i s y c h a n n e l s " , IEEE Trans. Commun. T e c h n o l . , p t . I , v o l . COM-19, pp. 601-612, October 1971.  17.  K.Y. Chang and R.W. Donaldson, " A n a l y s i s and o p t i m i z a t i o n o f DPCM system w i t h c o a r s e q u a n t i z a t i o n " , I n t . Conf. Commun., Conv. Reed., pp. 6.7-6.11, June 1972.  18.  D. Chan and R.W. Donaldson, "Optimum p r e - and p o s t - f i l t e r i n g o f sampled s i g n a l s , w i t h a p p l i c a t i o n t o p u l s e m o d u l a t i o n and d a t a compression systems", IEEE Trans. Commun. T e c h n o l . , v o l . COM-19, pp. 141-157, A p r i l 1971.  19.  A.M. Yaglom, An I n t r o d u c t i o n t o t h e Theory o f S t a t i o n a r y Random F u n c t i o n s , New J e r s e y : P r e n t i c e H a l l , pp. 110-121, 1962.  20.  G.H. R o b e r t s o n , "Computer s t u d y o f q u a n t i z e d o u t p u t s p e c t r a " , B e l l S y s t . Tech. J . , v o l . 48, pp. 2391-2403, September 1969.  21.  R.E. T o t t y and G.C. C l a r k , " R e c o n s t r u c t i o n e r r o r i n waveform t r a n s m i s s i o n " , IEEE Trans. I n f o r m . Theory ( C o r r e s p . ) , v o l . I T - 1 3 , pp. 336338, A p r i l 1967.  22.  H.M. James, N.B. N i c h o l s , and R.S. P h i l l i p s , Theory o f Servomechanisms, New Y o r k : M c G r a w - H i l l , Chapter 5, pp. 231-261, 1947.  23.  E . I . J u r y , Theory and A p p l i c a t i o n o f t h e z-Transform Method, New Y o r k : W i l e y , Chapter 3, pp. 79-141, 1964.  24.  A. P a p o u l i s , P r o b a b i l i t y , Random V a r i a b l e s and S t o c h a s t i c P r o c e s s e s , New Y o r k : McGraw H i l l , pp. 39 7-403, 1965.  25.  C.E. Shannon and W. Weaver, The M a t h e m a t i c a l Theory o f Communication, Urbana, 111,: U n i v . o f 111. P r e s s , Chapter 5, pp. 108-125, 1949.  26.  A.N. Kolmogorov, "On t h e Shannon Theory o f i n f o r m a t i o n t r a n s m i s s i o n i n t h e case o f c o n t i n u o u s s i g n a l s " , IRE T r a n s . I n f o r m . Theory, v o l . I T - 2 , pp. 102-108, December 1956.  27.  U. Grenander and G. Szegb, T o e p l i t z Forms and T h e i r A p p l i c a t i o n s , B e r k e l e y , C a l i f . : U n i v . o f C a l i f . P r e s s , Chapter 3, pp. 44-55, 1958.  28.  D.J. S a k r i s o n and V.R. A l g a z i , "Compression o f l i n e - b y - l i n e and twod i m e n s i o n a l e n c o d i n g o f random s i g n a l s " , IEEE T r a n s . I n f o r m . Theory, v o l . IT-17, pp. 386-398, J u l y 1971.  29.  B. S m i t h , " I n s t a n t a n e o u s companding o f q u a n t i z e d s i g n a l s " , B e l l S y s t . Tech. J . , v o l . 36, pp. 653-709, May 1957.  154  30.  J . Max, " Q u a n t i z i n g f o r minimum d i s t o r t i o n " , IRE T r a n s . I n f o r m . Theory, ' v o l . I T - 6 , pp. 7-12, March 1960.  31.  P.F. P a n t e r and W. D i t e , " Q u a n t i z a t i o n d i s t o r t i o n i n p u l s e - c o u n t m o d u l a t i o n w i t h nonuniform s p a c i n g o f l e v e l s " , P r o c . IRE, v o l . 39, pp. 44-48, January 1951.  32.  W.R, B e n n e t t , " S p e c t r a o f q u a n t i z e d s i g n a l s " , B e l l S y s t . Tech. J . , v o l . 27, pp. 446-472, J u l y 1948.  33.  J.M. W o z e n c r a f t and I.M. J a c o b s , P r i n c i p l e s o f Communication E n g i n e e r i n g , New Y o r k : W i l e y , pp. 248-250, 1965.  34.  R.W. Benson and I . J . H i r s h , "Some v a r i a b l e s i n a u d i o s p e c t r o m e t r y " , J . A c o u s t . Soc. Amer., v o l . 25, pp. 499-505, May 1953.  35.  W.B. Davenport, J r . , "An e x p e r i m e n t a l s t u d y o f speech-wave p r o b a b i l i t y d i s t r i b u t i o n s " , J . A c o u s t . Soc. Amer., v o l . 24, pp.'390-399, J u l y 1952.  36.  E.R. K r e t z m e r , " S t a t i s t i c s o f t e l e v i s i o n s i g n a l s " , B e l l S y s t . Tech. J . , v o l . 31, pp. 751-763, J u l y 1952.  37.  A. N i s h i k a w a , R.J. Massa, and J.C. M o t t - S m i t h , "Area p r o p e r t i e s o f t e l e v i s i o n s i g n a l s " , IEEE Trans. Inform. Theory, v o l . I T - 1 1 , pp. 348352, J u l y 1965.  38.  W.F. S c h r e i b e r , "The measurement o f 3 r d o r d e r p r o b a b i l i t y d i s t r i b u t i o n s o f t e l e v i s i o n s i g n a l s " , IRE Trans. I n f o r m . Theory, v o l . I T - 2 , pp. 94105, September 1956.  39.  D.S. S e r a p h i n , "A f a s t random number g e n e r a t o r f o r IBM 360", Comm u n i c a t i o n s o f t h e ACM, v o l . 1 2 , p. 695, December 1969.  40.  B.M. O l i v e r , " E f f i c i e n t C o d i n g " , B e l l S y s t . Tech. J . , v o l . 31, pp. 724-750, J u l y 1952.  41.  T.S. Huang, "Optimum b i n a r y code", MIT Q u a r t e r l y P r o g r e s s Rept., No. 82, pp. 223-227, J u l y 1966.  42.  G.G. A p p l e and P.A. W i n t z , "BCH code performance f o r sampled d a t a " , IEEE I n t . Conf. Commun., Conv. Reed., v o l . 2, pp. 28.1-28.8, June 1970.  43.  W.W. P e t e r s o n , E r r o r C o r r e c t i n g Codes, Cambridge, Mass.: pp. 67-70, 1961.  44.  E.R. Berlekamp, A l g e b r a i c Coding Theory, New Y o r k : pp. 119-125, 1968.  45.  J.O. Limb and F.W. Mounts, " D i g i t a l d i f f e r e n t i a l q u a n t i z e r f o r t e l e v i s i o n " , B e l l S y s t . Tech. J . , v o l . 48, pp. 2583-2599, September 1969.  MIT P r e s s ,  McGraw-Hill,  155  46.  D.J. Connor, R.F.W. Pease and W.G. S c h o l e s , " T e l e v i s i o n c o d i n g u s i n g t w o - d i m e n s i o n a l s p a t i a l p r e d i c t i o n , " B e l l S y s t . Tech. J . , v o l . 50, pp. 1049-1061, March 1971.  47.  R.W. S t r o h and R.R. B o o r s t y n , "Optimum and a d a p t i v e d i f f e r e n t i a l p u l s e code m o d u l a t i o n , " Tech. Rept., Dept. o f E l e c . Eng., P o l y t e c h n i c I n s t , of B r o o k l y n , 1970.  48.  J.B. O'Neal, J r . , " S i g n a l - t o - q u a n t i z i n g n o i s e r a t i o s f o r d i f f e r e n t i a l PCM," IEEE T r a n s . Commun. T e c h n o l . , v o l . COM-19, pp. 568-569, August 1970.  49.  J . J . Bussang, " 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 o f a m p l i t u d e d i s t o r t e d G a u s s i a n S i g n a l s , " MIT Res. L a b . E l e c t r o n i c s , Tech. Rept. no. 216, March 1952.  50.  N.S. J a y a n t , " A d a p t i v e d e l t a m o d u l a t i o n w i t h a o n e - b i t memory," B e l l S y s t . Tech. J . , v o l . 49, pp. 321-342, March 1970.  

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

Comment

Related Items