ANALYSIS AND OPTIMIZATION OF DIFFERENTIAL PCM SYSTEMS OPERATING ON NOISY COMMUNICATION CHANNELS BY KE-YEN CHANG B . S c , National Taiwan University, 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 in the Department of E l e c t r i c a l Engineering We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA SEPTEMBER 1972 In present ing t h i s thes is in p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the Un ive rs i t y of B r i t i s h Columbia, I agree that the L ib ra ry sha l l make i t f r e e l y a v a i l a b l e for reference and study. I fu r ther agree that permission for extensive copying of th i s thes i s for s c h o l a r l y purposes may be granted by the Head of my Department or by h i s representat i ves . It is understood that copying or p u b l i c a t i o n of th i s thes is f o r f i n a n c i a l gain sha l l not be allowed without my wr i t ten permiss ion . Department The Un ivers i t y of B r i t i s h Columbia Vancouver 8, Canada ABSTRACT A closed-form analytical expression for the output s ignal - to -noise ratio (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. A procedure i s then proposed for maximizing S N R q by joint optimization of the quantizer, predictor, sampling rate, and bandwidth. Several examples are considered, including one- and two-sample feedback systems excited by speech and video signals. Various techniques for reducing channel errors are then discussed. The predictor used i n the DPCM system is l inear and time invariant, but otherwise arbitrary. As with PCM, contributions to output signal distortion can be expressed as a sum of three dist inct terms result ing, respectively, from quantization errors, channel transmission errors, and mutual errors arising from interaction between quantization and channel errors. Constraints on the predictor coefficients for channel errors not to bui ld up unlimitedly are presented. When a conventional optimum linear predictor i s used, transmission errors are shown to be no more serious for DPCM than for PCM. The values of S N R q obtainable from DPCM are also compared with the theore-t i c a l bound obtained from the rate-distortion function. For a well-designed DPCM system, the value of SNR^ is 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. In considering examples, particular attention i s devoted to determining maximum values for S N R q and to examining the dependence of S N R q on predictor coefficient values, number of quantization levels , message s t a t i s t i c s , and channel error probabil i ty . Implications of this dependence on system design are noted. Among the various techniques investigated for combating channel noise are channel encoding, periodic resetting, and pseudo-random reset-t ing. These techniques are further evaluated subjectively with two video images. DPCM systems with coarse quantization are studied. The fedback quantization noise is considered i n optimizing the predictor. Simple equations for the optimum predictor coefficients and the resulting S N R Q are derived. \ i i i TABLE OF CONTENTS PAGE ABSTRACT i i TABLE OF CONTENTS iv LIST OF ILLUSTRATIONS v i i LIST OF TABLES x i ACKNOWLEDGEMENT x l i I. INTRODUCTION 1 1.1 Motivation of this Study 1 1.2 Review of Previous Research • 2 1.3 Scope of the Thesis 4 II . 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 • 11 2 2 2.3 Calculation of e , e , e , Q and a / a ' 13 q' m n e x 2.3.1 Expressions for e , e and e 13 q m n 2.3.2 Evaluation of Q 15 2 2 2.3.3 Calculation of a /a 16 e x 2.4 S tabi l i ty of the Decoder 17 2.5 Channel noise for Conventional Optimum Linear Prediction' 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 III. SYSTEM OPTIMIZATION 35 3.1 General Optimization Procedure • 35 3.2 Optimization of the Quantizer • 36 3.3 Optimization of the Linear Predictor 37 iv 3.4 Optimization of the Sampling Rate 38 3.4.1 Noiseless D i g i t a l Channels 38 3.4.2 Noisy Digi ta l Channels 40 3.5 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 IV. 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 • 53 4.4 One-Previous-Sample Feedback 58 4.4.1 Effect of a and <}> 58 4.4.2 Sensitivity to Variations in Signal Stat is t ics ••• 63 4.4.3 -SNR vs. Number of Quantizer -Output Bits • • • •••• -64 4.5 Two-Previous-Sample Feedback • 66 4.5.1 Effect of a^, a^, and $ 69 4.5.2 Sensit ivity to Variations i n Signal Stat is t ics . . . 79 4.6 Previous-Line-and-Sample Feedback 80 4.6.1 S tabi l i ty Constraints on ct, and a„T 80 I N 4.6.2 Evaluation of Q 84 4.6.3 Effect of a 1 ( a„ and <j> 86 I N 4.6.4 Sensit ivity to Variations in Signal Stat is t ics ••• 91 V. SCHEMES FOR COMBATING CHANNEL NOISE 95 5.1 Introduction 95 5.2 Channel Encoding • 96 5.2.1 Uniform Probability Density Function 97 5.2.2 Non-Uniform Probability Density Function 100 v 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 Effect of Feedback Coefficients 117 5.6.3 Periodic and Pseudo-Random Relettings 119 VI. DPCM SYSTEMS WITH COARSE QUANTIZATION 130 6.1 Introduction 130 6.2 Optimum Quantizer 131 6.3 Optimum Predictor • 132 6.4 Optimum Quantizer and Predictor 133 6.5 I l lustrat ive Examples 136 6.5.1 One-Previous-Sample Feedback 137 6.5.2 Two-Previous-Sample Feedback 138 VII . CONCLUSIONS 141 7.1 Summary of the Present Research 141 7.2 Suggestions for Further Research • 144 APPENDIX I. Calculation of R (k) and R (k) 147 n qn APPENDIX II . Derivation of the Overall Mean-Square Error 149 REFERENCES 152 v i LIST OF ILLUSTRATIONS FIGURE PAGE 1. DPCM system 7 2. Quantizer characteristic 14 3. Power spectrum of x(t) with the minimum cb^ 24 4. Comparison of DPCM performance with the rate-distort ion bound; a 2 | / 2=-14.35dB •••• 27 5. Samples shown i n black dot are used for prediction ••• 29 6. SNR as obtained from (3.14) vs. the normalized sampling rate £=f /2W for noiseless channel. Fixed at the values shown are the number of quantization bi ts K (solid lines) and b i t rate R=fgK (dotted l i n e s ) ; (a) speech, (b) video ••• 42 7. SNRQ for speech as obtained from (3.14) v s . £ ; a-^ot i s optimized. Values of K are shown next to so l id l i n e s . Dotted lines correspond to the constant R values of F i g . 6(a). (a) c}> =P/7f N =10dB, (b) cb =8dB 44 Ts s o ' s 8. SNR for video as obtained from (3.14) with a optimized. Values of K are shown next to sol id l i n e s . Dotted lines correspond to the constant R values of F i g . 6(b). (a) <j> = lOdB, (b) cbs=8dB 45 9. SNR for Gaussian Markov process as obtained from (3,18) for N=l and N-*-"> and from (3.22) for rate-distortion bound vs. 2W/R. The channel i s noiseless 48 10. SNR as obtained from (3.23) vs . 2W/R with the relative transmitter power <j>w=P/1000foNo fixed at lOdB (a) and 8dB (b) • 50 11. Pictures or iginals ; 512x512 picture elements with 8 bi ts per picture element 54 12. Correlations of the pictures shown i n F i g . 11; (a) crowd scene, (b) cameraman scene. The distance of the horizontal scale i s relative to the distance between 2 adjacent horizontal elements * • 55 13. Amplitude probability density of the pictures shown i n F i g . 11; (a) crowd scene, (b) cameraman scene 56 14. Amplitude probability density of e^=x_-P2X^_^; (a) crowd scene, (b) cameraman scene. Laplacian distr ibution is shown for comparison •• 57 v i i 15. SNRQ for speech vs. a =a and <(>=P/RNo; N=l, fg=2W=8KHz, P=p(l) =0.89, K=4. Quantizer overload level V/o =20dB. Experimentally measured values are indicated i n symbols 60 16. SNR vs. a and <)> for video signals ; N=l, K=4 V/ae=20dB. (a) crowd scene, p1=0.9569, (b) cameraman scene, p^=0.9809 61 17. Optimum value of a vs . <j> • 63 18. a vs. cb; when 0<a<amax, SNR of DPCM i s higher than SNRQ of PCM. 63 19. % change in SNRQ vs. % variation of p for ct=0.5, 0.75, and 0.89; p=0.89 • 65 20. SNR 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 errors, and when a=0 (PCM) 67 21. SNR for the crowd scene vs . K and d> =P/f N for previous-o, , ,, , , . s. s o . . sample feedDack systems when a i s optimum, a is optimum assuming no channel errors, and when a=0 (PCM) 68 22. SNR for speech vs.a-, and a2\ K=4, fs=2W=8KHz, V/ae=20dB. Experimentally measured values of SNRQ are shown by the "x" symbols, (a) <j>=10dB, (b) <)>=6dB 70 23A. SNR for crowd scene vs . a, and ex.; K=4, V/a =20dB. (a) cb= 10d8, (b) <f>=6dB • ? 71 23B. SNR for cameraman scene vs.a^ ando^; K=4, V/a =20dB. (a) <j>= l O d S , (b) <f.=6dB ? 72 24. Locus of SNR which is equal to that of PCM for speech. The "x" symbols denote the values of a-^ and that maximize S N R Q for various values of <j> 74 25. Locus of SNRQ which is equal to that of PCM for the crowd (a) and cameraman (b) scenes. The symbol "x" denotes the values of a, and a 0 that maximize SNR for the value of cb shown 75 1 2 o 26. Locus of SNR which i s equal to that obtainable from previous-sample feedback system for the speech sample ••»••• • 77 27. Locus of SNRQ which is equal to that obtainable from previous-sample feedback system for the crowd (a) and cameraman (a) scenes * ' * * * 7 8 28. Stabi l i ty boundary for previous line-and-sample feedback systems. (a) even N, (b) odd N * 83 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 v i i i 30. SNR vs 4 a_ and a__ for line-and-sample feedback DPCM for the O 1 N crowd scene. (a) cp=10dB, (b) <j>=6dB 89 31. S N R q vs. and for line-and-sample feedback DPCM for the cameraman scene. (a) <j)=10dB, (b) cf)=6dB 90 32. Locus of SNR which is 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 33. Locus of SNR which is equal to that obtainable from previous-sample 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 is white Gaussian; p (a) is uniform; a^=p^=0.9569; K=4. (a) transmitter power fixed, (b) bit-error probability fixed 101 35. SNR for previous-sample feedback DPCM using Hamming code and non-redundant natural-binary code.. The channel is white Gaussian; P e(a) is Laplacian; a^ =p =0.89; K=4. (a) transmitter power fixed, (b) bit-error probability fixed • 103 36. SNR for previous-sample feedback DPCM using Hamming code and non-redundant natural binary code. The channel is white Gaussian; p (a) is Gaussian; cx^ =p^ =0.9569; K=4. (a) transmitter power fixed, (b) bit-error probability fixed 104 37. Encoder for the Hamming code used in plotting Figs. 35 and 36 105 38. The factor Q given in (5.29) vs. the block size M for DPCM with periodic resetting • 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"6 120 41. Pictures obtained from a 4-bit previous-sample feedback DPCM with <f>=8dB or p=l.9*10-4 121 42. Pictures obtained from a 4-bit previous-sample feedback DPCM with c6=6dB or p=2.4xl0 - 3 122 43. Pictures obtained from a 4-bit line-and-sample feedback DPCM with <j>=10dB or p=3.9xl0 - 6 123 44. Pictures obtained from a 4-bit line-and-sample feedback DPCM with <j>=8dB or p=1.9xi0"4 124 i x 45. Pictures obtained from a 4-bit line-and-sample feedback DPCM with cb=6dB or p=2.4xl0"3 125 46. Pictures obtained from a 4-bit previous-sample feedback DPCM with periodic resetting; a-jL=P^> <f>=8dB 126 47. Pictures obtained from a 4-bit previous-sample feedback DPCM with periodic resetting; a^=P^> <j>=6dB 127 48. Pictures obtained from a 4-bit previous-sample feedback DPCM with pseudo-random resetting; ai=P]_> cb=8dB 128 49. Pictures obtained from a 4-bit previous-sample feedback DPCM with pseudo-random resetting; a i = P i > ^ ^ d B 129 9 i 50. Optimum values of n=cTg / a x and as obtained from (6.25) and (6.26) vs. e for previous-sample feedback DPCM with noise-less channel; p =0.89 139 o 9 51. Optimum values of r)=o"g/a£, and a. for two previous-sample feedback DPCM as obtained from (6.2/) and (6.15) vs . e ; p = 0.89, p2=0.65 1 4 0 1.1. D i g i t a l communication system 149 x LIST OF TABLES TABLE PAGE 2 2-1 I. Comparison of the values of (oe/a ) i n dB with p(m,n) obtained from (2.59) and those with p(m,n) obtained from measurement • 33 I I . Quantizer overload l e v e l r e l a t i v e to a i n dB 51 e I I I . Improvement i n SNR^ when N=2 over N=l 76 IV. Improvement of SNR for line-and-sample feedback over previous-sample feedback 91 x i ACKNOWLEDGEMENT I would l ike to express my sincere gratitude to my research supervisor, Dr. R.W. Donaldson, for his valuable suggestions and constant encouragement throughout the course of this work. 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 the digi t ized picture data produced in the Research Laboratory of Electronics of the Massachusetts Institute of Technology. I would also l i k e to thank Messrs. J . Yan and A. Soubigou for many helpful discussions, Mr. M. Koombes for assistance with the picture display, and Miss N. Duggan for typing the thesis. I gratefully acknowledge the f inancial 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. F i n a l l y , I would l i k e to thank my wife Shirley for her contin-uous encouragement and support. x i i I. INTRODUCTION 1.1 Motivation of This Study It i s well known that d i g i t a l communication systems have many advantages over analog communication systems. D i g i t a l systems are attractive, for instance, in situations where there is high-level noise or interference in the transmission medium.- Also, they are part icularly useful when time-division multiplexing of several signals into a common channel is desired. However, they also have some shortcomings, the most serious of which is that broader bandwidth is required for transmission. Much effort has therefore been devoted to the reduction of bandwidth requirement in d i g i t a l systems, a technique also known as re-dundancy reduction or source encoding. Among the many source encoders proposed in the past, d i f f e r e n t i a l pulse-code modulation (DPCM) is one of the simplest and most e f f i c i e n t . Taking advantage of the large amount of redundancy, or correlation, inherent i n most signals by using predi -ction, i t offers significant improvement in system performance relative to PCM without great increase in system complexity or cost. Although a great number of studies on DPCM has been reported in the past, an important aspect that has largely been overlooked is the effects of channel noise and the many associated problems. It has been suggested in some studies that, due to i t s feedback network in the decoder, DPCM is 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 to be doubtful. Furthermore, even i f i t i s true, questions arise as to how much more serious the effect of channel noise is on DPCM than on PCM, and how variations in system parameters, channel parameters, and message-2 source st 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 is discrete in 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 resulting samples, which are continuous in amplitude, with a f i n i t e number of discrete levels. The f i r s t system that performed these operations appeared in 1938[1] and was later known as the pulse-code modulation (PCM) system. Much work on the design, analysis and development of PCM then followed [2]. Due to i t s inconvenience in .requiring a broader bandwidth than an analog system, however, some researchers also started exploring new techniques for bandwidth reduction. In 1945, a simple encoding technique, i.e., delta modulation (AM), was discovered!3]. Instead of quantizing analog samples directly and independently as in PCM, i t transmits only the sign of the difference between the input sample and the output of a local decoder, which is simply an integrator. Because only one binary digit i s used for each sample, the bandwidth required is greatly reduced. However, this bandwidth reduction is achieved at the expense of system performance. The system was later improved and generalized with the sign detector replaced by a multilevel quantizer[4,5], and the integrator replaced by a linear predictor[6]. The new system became what i s called a differential pulse-code modulation system. It was not only efficient in redundancy reduction, but also simple in structure and high in perfor-3 formance. It has therefore received very much attention. Much work on DPCM was later done by 0'Neal[7,8], He inves-tigated the usefulness of DPCM for the transmission of television signals . and presented a procedure for the design of near-optimum systems. He also derived bounds for signal-to-quantizing noise ratios of DPCM and AM, and compared them with Shannon's theoretical bound. McDonald[9] and Nitadori[10], on the other hand, analyzed the performance of DPCM for speech signals. Further study of DPCM for the transmission of speech signals was done by Donaldson and Chan[ll] , who analyzed and, in 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, i t s performance i n ,a .noisy environment, despite i t s importance, has received relat ively l i t t l e attention. It has only been suggested in some ear l ier studies that transmission errors in DPCM are more serious than those in PCM. Recently, Arguello et a l [13] studied the effects of channel errors. However, their results apply only to a 4-bit DPCM system with PCM upda-ting for video signals. For speech signals , 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 ta t i s t i cs 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 in this thesis, some of which has recently been published[15]. k 1.3 Scope of tha Thesis The purpose of the present study is to calculate the output signal-to-noise ratio ( S N R q ) of DPCM systems when channel errors cannot be ignored, to maximize S N R q by system optimization, to determine the sensi t ivi ty of S N R q to variations i n system parameters, channel parame-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 in this study is l inear and time-invariant, or non-adaptive, but otherwise arbitrary. In Chapter II , analytical expressions 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 signal distort ion can be expressed as a sum of three dist inct terms resulting from quantization errors, channel transmission errors, and mutual errors between quantization and channel errors. The effect of channel transmi-ssion errors on S N R q when the conventional optimum predictor i s used is determined in Section 2.5. Contrary to ear l ier suggestions, transmis^-sion errors are shown to be no more serious for DPCM than for PCM. In Section 2.6, the distortion bound of DPCM is compared with the rate-distortion bound for both one- and two-dimensional signals. In Chapter III , a procedure for optimizing S N R q by joint o p t i -mization of the quantizer, predictor, sampling rate, and bandwidth is proposed. The optimization of each of the above items i s also studied i n d e t a i l . In Chapter IV, several pract ical examples are considered, including one- and two-previous-sample feedback and previous-line-and-sample feedback systems. Both speech and video signals are used to eva-luate the performance of these systems. The results show that SNR of a o well-designed DPCM system is 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 this channel is noisy. In studying these systems, attention i s devoted to maximizing S N R ^ and to examining the dependence of S N R q on the values of predictor coeff ic ients , number of quantization levels , message-source s ta t i s t i cs and channel error probabil i ty . Implications of this dependence on system design are noted. Various techniques for combating channel noise are investiga-ted in Chapter V. Among these are channel encoding, periodic resetting and pseudo-random resetting. These techniques are further subjectively evaluated with two video images. F i n a l l y , in Chapter VI , DPCM systems with coarse quantization are studied*. The fedback quantization noise is considered in optimizing the predictor. Simple equations for the optimum predictor coefficients and the resulting SNR are derived. This work has recently been presented in ICC-72I17]. 6 II . ANALYSIS OF DPCM SYSTEM WITH NOISY CHANNEL Shown in F ig . 1 is a DPCM system block diagram. The pre- and postf i l ters G^(f) and G ^ i f ) are assumed to sat isfy the following equation, where the set J " contains a l l frequencies in the f i l t e r s ' passband, and the set contains a l l frequencies not included in j r • 1 fs & G 1 (f) = G-(f) = \ _ (2.1) 1 2 f s ^ In addition, x(t) is assumed to be free of al iasing errors*; therefore G.. (f) and G_(f) are non-zero for at most one frequency in the set f + kf X. c, s where k is any integer, including zero, and f is the sampling frequency. Normally, the input samples would result from low-pass f i l t e r i n g the input signal m(t) and sampling the resulting signal x(t) every 1/f s second. Instead of being quantized and coded direct ly 'as in PCM, the sampled signal i s f i r s t compared with i t s predicted value z^ and the difference e^ is 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^. It i s noted that when the feedback parameters = = a^...= = 0, a PCM system results . 2.1 Mean-Square Error of Sampled Signal Let q. = s. - e. denote the quantization error and n. = r. - s. denote the d i g i t a l channel noise (see F ig . 1). The difference x^ - x^ is obtained as follows, where 6^ i s the unit impulse, I K i s the (digital) * Aliasing 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], PRE FILTER mft) Gj(f) x(t) X- _ DIGITAL ENCODER I \ QUANTIZER 1 DIGITAL I e-i s- CHANNEL LINEAR PREDICTOR 7-<=| «J>H + + r-i + A z. A LINEAR PREDICTOR zi=j^jxH — ^ - s POST FILTER G2(f) DIGITAL DECODER Fig. 1 DPCM system impulse response of the l i n e a r p r e d i c t o r , and f ^ i s the ( d i g i t a l ) impulse response of the decoder. Thus, i n F i g . 1, h. = I ^ i = 1, 2, N ( 2 > 2 ) otherwise y ^ x . + q . (2.3) s , = y. - z. I (x. + q.) ( 6 . . - h. .) (2.4) x. = E (s, + n. ) f. , l , k k l - k k=-°° oo oo Z 11 (x + qj) io ~ V j > + \ ] f i - k < 2' 5 ) When the q u a n t i z a t i o n n o i s e i n F i g . 1 i s ne g l e c t e d , the d i g i t a l encoder and d i g i t a l decoder are in v e r s e systems. Therefore, E (6, . - h. .) f. , = <5. . (2.6) k__«_ k-3 k-j i - k i - j A I L D CO X i " X i = q i + v Z \ f i - k = A + E n i - k f k < 2' 7 ) Assume now th a t x. and n. are samples from s t a t i o n a r y random i l * oo sequences, i n which case x. - x., q. and E n. f. , are a l s o s t a t i o n a r y X 1 1 , iC 1 K. k=- c o random sequences. Let E[ ] denote "the expected value o f " . Then the d i s c r e t e c o r r e l a t i o n f u n c t i o n s R (k) and R (k) can be def i n e d as f o l l o w s , qn n R (k) = E[q. n. . ] (2.8) qn l i - k R n(k) = E[n. n._ k] (2.9) From (2.7), (2.8) and (2.9), one obtains the mean-square difference be-2 2 ? tween x^ and x^, normalized with respect to = E[x^] = E[x~(t)] 5 as follows. e = E [(x. - x . ) 2 ] / a 2 = (e + e + e ) a 2 / a 2 (2.10a) q m c e x where and 2 2 a = E[e/] e l e = E[q 2]/a 2 = R (0)/o 2 (2.10b) q n i J e q e CO e = [2 Z R (k) f, ]/ a 2 (2.10c) m k = _ c o qn k e co oo 9 e c = [ Z E Rn (k-j) f f ]/ a / (2.10d) k=—°° j =—oo •* As in PCM [16 ], the mean-square error e can be separated into three distinct terms: quantization error e , mutual error e and channel q m error e . These errors can also be expressed in terms of the power spec-t r a l densities S ( f ) , S (f) and S ( f ) , which are the Fourier transforms, q ' qn ' n ' respectively, of R^(k), R (k) and R n ( k ) , as follows*. * The Fourier transform T(f) for a sequence (t^} of numbers is related to the sequence as follows m/rN ? _ -j2 i r f k / f 1 . f 12 j2Trfk./f T(f) = E t . e J s t, = —- / s T(f)e J s k=-» k k fs - f 12 s 1 V2 2 \ T ' - f 12 Sq( f> d f / ° e ( 2 - U a ) n s s n f 12 g e = T~ / - / 9 S (f) F*(f) df/o 2 (2.11b) m f -i 12 qn ' e ' s s ^ 1 f c / 2 9 9 e c = j - / 2 S n(f) | F ( f ) j Z d f / o ^ (2.11c) s s where the digital decoder's transfer function F(f) i s N -1 F(f) = [1 - I ^ exp (~j2irfk/f )] ( 2 . l i d ) k=l k S Expressions for R (k) and R-n0O are derived in Appendix I. These correlation functions depend on the second-order amplitude pro-bability density of e^. In fact, even when these second-order st a t i s t i c s are available, calculation of R (k) and R n 00 is tedious. When the di g i t a l channel in Fig. 1 i s memoryless, however, and when the samples are st 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. If, in addition, we assume with no loss in generality that E[q_^] = E [ T K ] = 0 , then, since .f = 1, (2.10a) can be rewritten as follows. e = <eq + e m + ^n> ae/ax ( 2 ' 1 2 a ) where e = 2 R (0)/o 2 (2.12b) m qn e e = R (0)/a 2 (2 .12c) n n v e and 1 V2 9 Q = T~ /- / 9 \Hf)\ « (2.12d) f - f 12 s s When the samples x^ are from an order Gaussian Markov source, when the number of quantization levels L 5 8, and when the feedback 2 parameters ( i = 1, . . . , N) are chosen, to minimize , then the sam-ples are uncorrelated and, therefore, s t a t i s t i c a l l y independent [19]. Because a well designed linear predictor causes the samples e^ to be weakly correlated, i t is not unreasonable to assume that R (k) = R (k) = J qn n for a l l kf"0. The examples in Chapter IV w i l l show that this assumption leads to a very close agreement between measured and calculated perfor-mance curves when m(t) is 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 is the total width in Hertz of the positive frequency spectrum over which G^(f) 4- 0, and when G^(f) and ^ ( f ) are given by (2.1), then an argument similar to the one in reference [18] yields the mean-square difference between analog wave-forms x(t) and x(t) in Fig . 1 as follows. E{[x(t) - x(t)] 2 } / a 2 = e (2.13a) In certain cases, the signal to be transmitted is bandlimited. Then G^(f) is not required and x(t) may be considered as the input of the system. The output signal-to-noise ratio SNRo, defined as the ratio of the input signal power to the mean-square error between the input and output of the system"'", is then simply the reciprocal of (2.13a); i . e . , SNR = 1/e (2.13b) When f >, 2W, i t can be shown that the mean-square difference s n 2 between x(t) and x(t) is (see Appendix II) In some cases, the output signal-to-noise ratio i s defined as the ratio of the inband signal power to the inband mean square distortion [11,12]. Our definit ion here i s more general. 2 For s implic i ty , G^(f) and ^ ( f ) are assumed to be low-pass f i l t e r s here. 2 1 W E { [ x ( t ) - x ( t ) ] Z } = j- f [S ( f ) + S ( f ) F * ( f ) + S * ( f ) F ( f ) + s -W q q q S n ( f ) | F ( f ) | 2 ] df (2.14a) When f i s not very l a r g e compared w i t h 2W, S ( f ) , the spectrum of the s q q u a n t i z a t i o n noise samples q^, i s r e l a t i v e l y f l a t [20], I f S ( f ) , S^(f) and 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 constant J qn n v i f R^ n(k) = R n(k) = 0 f o r k^O, then the i n t e g r a l i n (2.14a) can be c l o s e l y 2 approximated as 2Wea x and the output s i g n a l - t o - n o i s e r a t i o i s SNR = f / 2We (2.14b) o s where e i s obtained from (2.10) or (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 Appendix I I ) W E { [ x ( t ) - m ( t ) ] 2 = i - / [ S C f ) + S ( f ) F * ( f ) + S* ( f ) F ( f ) + f s -W q q n q n OO S n ( f ) | F ( f ) | 2 ] df + 2/ w S„(f) df (2.15a) where S m ( f ) represents the power s p e c t r a l d e n s i t y of the s t a t i o n a r y random process m(t). The second i n t e g r a l i n (2,15a) i n v o l v e s the e r r o r caused by p r e f i l t e r i n g from m(t) a l l frequencies g r e a t e r than W. The f i r s t i n t e g r a l represents in-band d i s t o r t i o n . I f f i s not too l a r g e , we can approximate the output s i g n a l - t o - n o i s e r a t i o as f o l l o w s . CO W 0 0 SNR = / S ( f ) df / f S ( f ) df + 2 A_ S ( f ) df} (2.15b) o - o o m x / f -Wm W m s This r e l a t i o n w i l l be used to study the e f f e c t of bandwidth i n Chapter I I I . 2 2 2.3 C a l c u l a t i o n of e , e , E , Q and a /a q m n % e x We have seen i n S e c t i o n 2.1 that the mean-square e r r o r e can 2 2 be expressed i n terms of e , e , e , Q and a /a . The e r r o r s e , e 1 q m' n' M • e x q m and e are dependent on the qu a n t i z e r c h a r a c t e r i s t i c and the channel n n e r r o r p r o b a b i l i t y . The l i n e a r p r e d i c t o r a f f e c t s e through the f a c t o r s 2 2 Q and /a_ . In the f o l l o w i n g , we s h a l l express each of the above f a c t o r s e x p l i c i t l y i n terms of the s i g n a l s t a t i s t i c s and system parameters 2.3.1 Expressions f o r e , e and e . r 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 of the q u a n t i z e r i n F i g . 1. Assume that the d i g i t a l channel i n F i g . 1 i s memoryless and that the q u a n t i z e r input samples e^ are s t a t i s t i c a l l y independent. Let Pe(°0 denote the amplitude p r o b a b i l i t y d e n s i t y of the samples e^, and l e t P 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 output l e v e l v^ i s t r a n s -m i t t e d and V j received. Then use of (2.12) and an approach s i m i l a r to that i n Appendix I y i e l d s L U i + 1 2 2 e = E / (v. - a) P (a) da / a q . , u. i e e 1=1 I A L U i + 1 ~ 2 A = E f" (v. - a r P (a) da (2.16) 1-1 U i 1 6 L L „ u e = 2 E E P.. (v. - v.) /„ (a - v.) p (a) da 1=1 j = l J J u. J l (2.17) and L L " 2 U i + 1 * e = E Z P., (v - v ) Z p (a) da (2.18) i = l j = l u. J l where u. = u./a , v. = v./a and p (a) - a p (a a ) . Thus, p (a) has l l e i i e r e e *e e ' r e the same f u n c t i o n a l form as p g ( a ) , but i s normalized to have u n i t v a r i a n c e Uj=-ao U2 U3 U4 -7<-UL-1 UL v3 v2 Fig . 2 Quantizer Characteristic Assume that e_^ and have the same amplitude probability density. Then, from (2.12), (2.17) and (2.18), we can see that the quantization error and mutual error of DPCM are reduced from their cor-2 2 responding values by the factor CTe '/o . The DPCM channel error equals 2 2 that for PCM multiplied by the factor Qa^ /a . If the quantizer output levels are arranged in accordance with the following equation, then e [21]. m Ui+1 / (v ± - a) P (a) da = 0, i = 1, 2, L u. 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 and can be obtained by using (2.10c), (2.10d), (1.1) and (1.3)' 2 . 3 . 2 Evaluation of Q The s u b s t i t u t i o n z = exp ( j2?rf / f ) can be used to enable Q i n ( 2 . 1 2 d ) to be expressed as a closed contour i n t e g r a l i n the complex A z plane. Thus, Q = ~ j ^ | z | = ! { 1 / t z H< z) H ( z _ 1 ) ] > d z ( 2 . 2 0 a ) where N H(z) = 1 - Z a. z 1 ( 2 . 2 0 b ) i = l 1 In order that the decoder i n F i g . 1 be s t a b l e , i t i s necessary and s u f f i c i e n t that a l l the zeros of H(z) l i e i n s i d e the unit c i r c l e of the z-plane. This assumption w i l l be made i n determining Q. Let a = - 1 and define iKk) as follows, o <Kk) = ~ - r (j>, | , 2 1 n dz ( 2 . 2 1 ) J l z l = l H ( z ) HCz" 1) Note that Q = K 0 ) . From ( 2 . 2 1 ) i t follows that N r k -1 E a ^ ( k - i ) = — i <j>, , dz ( 2 . 2 2 ) i = 0 1 2TTJ J | z | - 1 H ( z - 1 } -1 Since the roots of H(z ) are the r e c i p r o c a l s of those of H(z) , the integrand of ( 2 . 2 2 ) has no s i n g u l a r i t i e s (poles) i n s i d e the un i t c i r c l e when integer k >, 1 , and f i r s t order pole at z = 0 f o r k = 0 . Use of Cauchy's residue theorem y i e l d s N C-l k = 0 ± l Q °i « W > = { o k = l , 2 , ...,N ( 2 - 2 3 ) The s u b s t i t u t i o n w = z ^ i n ( 2 . 2 1 ) y i e l d s the following expression f o r - 2 iK-k) (note that dw = -z dz). Note that H(z) i s not the transfer function corresponding to h^. 16 k+l K"k) w 2rrj r l H(w -1) K(w) (-w dw) (2.24) It follows from (2.21) and (2.24) that Kk). = K~k). Equation (2.23) can now be rewritten as follows. aQip (0) + (1) + a 2^(2) + + a^_± *(N-1) + cyKN) = -1 a.^ (0)+ (a 2 + a Q) <KJ) + « 3 <K2) + + a N ^(H-l) = 0 a 2_*(0)+ ( a 3 + a 1)^(l) + (a +aQ)i|»(2) + . . t|>(N-21 = 0 V l * ( 0 ) + (V2 + V + a N - 3 ^ ( 2 ) + ' • + V ( N _ 1 ) = 0 aN'K0)+ a^-iKD + a N_ 2"J ,( 2) + • • . . + a^CN-l) + a Qf(N) = 0 (2.25) The set of equations in (2.25) can now be solved to obtain ~4>(Q) = Q, as follows. Q=-a Q + a 2 a 3 aN-2 + aN aN-3 *N-1 N-2 a., + a„ a"+a. . . 0 0 1 3 0 4 v. 0 • ai ao a Q a± a 2 . . aN-l aN a l a0 + a2 ' * " ® a„ a..+a„ a„+a, . . 0 0 2 1 3 0 4 V l V2 + aN V3-' a0 ° "N aN-l aN-2 * ' al a0 (2.26) 2 2 2.3.3 Calculation of a /a e x 2 2 The ratio a /a can be calculated as follows. In Fig. 1, e x N e. = x. - Z a. (x. . + q. .) (2.27) 2 ? o = E [ e / ] e L I J N N = R (fl) - 2 Z a [R (j)+R (j)] + Z a / [R (0)+2R (0)+Rfl(0)] N-1 N-j +2 Z. Z a a [R (k) + 2R (k) + R ( k ) ] (2.28) j=l k=l J K 2 x xq q 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 in terms of the .signal s t a t i s t i c s and a. i n e & l (2.28). If , however, the number of quantization levels L is not too small ( typically L 5 8), then the quantization noise q^ is small, on the average, with respect to x. . In this case, |R^ (j)| << |R (j)| and i xq x |R (3)I « |R (j)|> and (2.28) simplif ies as follows, q x N N N-j 0^/0 2 = Z a 2 + 2 Z Z a. OL p(j) (2.29a) X j=0 3 j=l k=0 * K 2 e where p(j) = R x ( j ) /R x (0) (2.29b) Much of the analysis to follow is based on the assumptions |R n(i)\ « |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 error. The discrepancy between the c a l -culated value of SNR and the actual value increases as L decreases, and o is largest for L = 2 (A-modulation). 2.4 Stabi l i ty of the Decoder An important factor which has to be considered i n designing a DPCM system is the s t a b i l i t y of the decoder. Because of the feedback network in the receiver, errors caused by channel noise may accumulate or even magnify unlimitedly i f the feedback coefficients a ^ , . . . , c t ^ are not carefully chosen. A network is said to be stable i f every bounded input to the net-work gives a bounded output. The necessary and suff ic ient condition for a (digital) network to be stable i s that a l l the poles of i t s trans-fer function l i e inside the unit c i r c le of the z-plane [22]. Therefore, for the decoder in F ig . 1 to be stable, 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 in pract ical applications, we shal l express this condition e x p l i c i t l y i n terms of the feedback coefficeints . Define the matrices X. and Y. as follows. x x X. 0 0 a. 0 a - a . . x-2 i -3 i-4 a i - l a i - 2 a i - 3 0 0 1 $ i s; N-KL (2.30a) Y. = x "N-i+l aN-i+2 °N-i+3 '.. ' ' '. aN-i+2 aN-i+3 V-i+4 V i + 3 V i + 4 aN-i+5 * * ' a N ° ° V l °N L N N 0 0 0 0 1 $ i $ N+1 (2.30b) Then i t can be shown that the necessary and suff ic ient conditions for a l l the zeros of H(z) to l i e inside the unit c i rc le are [23] 1) H(l) > 0 (2.31a) 2) H(-l) > 0 and (2.31b) 3) a. for even N < 0 k = 1, 3, 5, 7 , . . . , N - l (2.31c) or al ternatively, > 0 k = 2, 4, 6,..., N-2, and D " ^ < 0 (2.31d) b. for odd N D £ >:0 k = 2, 4, 6 , . . . , N - l (2.31e) or alternatively, B r < 0 k = 1, 3, 5, . . . , N - 2 , and D ~ > 0 (2.31f) k N - l where the determinants and are defined as follows. D J - I ^ + YJ (2.32a) D k = K ~ Y k' (2.32b) + - + -In fact, D, and D. for k < N - l can be obtained from D X T and D „ , . , res-k k N - l N - l 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 N + l N 1 ( 2 > 3 4 ) 2 DN-1 I °N+1 N > 1 Examples Listed i n the following are the constraints on the feedback parameters obtained from (2.31) for certain low-order l inear predictors. cd ro co > 53 8 + 1 I 25 8 + 1 + 1 O 8 O 8 CN ro 53 co cs I 8* +1 " © 8 53 8 4 ? o 8 +1 O J 8 I 53 8 I CM 8 I 8 S +1 8 +1 s CO + 1 + L53 CO I 8 + 1 O 8 8* +1 8* CM 8 CO 8 + 1 I 53 8 +1 CO I 53 8 8* +1 CN I 8* II H a 0 ± a 2 ± a 3 ± a 4 D: N-3 a l ± a 3 Va4 0LT + 0L-N-4 N aN-3 ± aN-l V2 ± aN V 3 D 3 ± a0 a ±N-3 *V2 D 2 ± a l ± N - 2 ? C ± V l a l ± a N ±a N-1 a, a. N-1 N ±OL. a i a o N odd (2.33b) 22 a) N = 1 -1 < a± < 1 ( 2 . 3 5 ) b) N = 2 1 - a 1 - a > 0 1 + a - a 2 > 0 ( 2 . 3 6 ) 1 + a2 > 0 c) N = 3 1 - - - > 0 1 + - + > 0 -1 < a 3 < 1 2 1 + a 2 + a x a 3 - a > 0 (2.37) d) ,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 3 - a ] [a 4 - a^ > 0 (2.38) 2 1 + a_ + a., a. - a. > 0 3 1 4 4 2 2 2 2 3 l+a„+a.+2a_a.+a1 a„+ a. a.+a.a. -ana„a.-a_ -a. -a. > 0 2 4 2 4 1 3 1 4 2 4 1 3 4 3 4 4 2.5 Cliannel Noise for Conventional Optimum Linear Prediction The linear predictor in Fig. 1 i s often designed to minimize 2 2 the ratio /a as given by (2.29) [7-12 ]> in which case the DPCM 2 2 quantization error E q ° e / ° x is minimized with respect to {a^}, i f 2 2 L £ 8. To minimize a g /a , {a^} must satisfy the following set of N linear equations [24]. N p(k) «= E a . (k-i) k = 1, 2,...,N ( 2 . 3 9 ) i=l 1 For t h i s choice of {a.}, x 2 2 N a */a = 1 - E a. p ( i ) (2.40) e x . . l i = l Since p(k) i s an even f u n c t i o n of 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 p ( k - i ) = i i=0 -a 2la 2 k = 0 e x (2.41) 0 k = 1, 2,...,N From the s i m i l a r i t y between (2.23) and (2.41), one obtains Qo e 2/o x 2 = p(0) = 1 (2.42) Therefore, f o r t h i s choice of {a^} , (2.12) and (2.42) y i e l d e = (e + e ) a 2/a 2 + e (2.43) q m e x n This equation shows that the e f f e c t of channel t r a n s m i s s i o n e r r o r s on e i s no more severe f o r DPCM than f o r PCM. I t w i l l be seen i n Chapter IV th a t f o r many other choices of { c O , the mean-square channel e r r o r f o r DPCM can even be l e s s than that f o r PCM. Thus, e a r l i e r suggestions that t r a n s m i s s i o n e r r o r s i n DPCM are n e c e s s a r i l y more s e r i o u s than those i n PCM are i n c o r r e c t . 2.6 Comparison of 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 the minimum e r r o r achievable by any communication system. For 2 2 DPCM, the minimum value of the r a t i o a la , as given by (2.39) and (2.40), i n conjunction w i t h the minimum value of e^, gives the minimum mean-square e r r o r of the system. I t i s t h e r e f o r e of i n t e r e s t to compare this lower bound with the theoretical l imi t obtained from rate-distort ion theory. Both one- and two-dimensional random signals w i l l be considered in the following. 2.6.1 One-Dimensional Random Signal The rate-distortion function of a Gaussian random signal x(t) with power spectrum S(f) can be expressed parametrically as follows [26]. R(*> - \ / l o g 2 df bi ts /sec (2.44a) d(<j)) = / cbdf + / S(f) df A A (2.44b) where A = {f: S(f) £ cb}, A- = {f: S(f) < co} and d is mean-square error. c 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) is bandlimited within -W £ f £ W, For a non-deterministic random signal , S(f) > 0 for a l l |f| £ W. Let <|> be the minimum of S(f ) , as shown i n Fig . 3. Then, from (2.44), i t can be S(f) 0 0 W Fig . 3 Power spectrum of x(t) with the minimum <f> m readily shown that for cb < i> , the normalized mean-square error e=d/a z J m x I S -R/W , 2W r l r W . , e = 2 { —— e x P L-^ y ^ l n s ^ f ) d f J ' x -W (2.45a) Since d = 2Wcb when <p $ cb^, (2.45) i s true f o r e $ 2Wcb h = e m x o (2.45b) or 1 W R > ' f J-W l o S 2 S ( f > d f - m°Z2K = R o (2.45c) Note that i f S ( f ) i s a monotonically decreasing f u n c t i o n of f , then cb^ = S(W) . Consider now the mean-square 1 e r r o r of DPCM system. Assume that f = 2W. Then 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 N N a = I Z a. a. R ( i - i ) i=0 j=0 J (2.46) The minumum of t h i s T o e p l i t z form i s [27] 2 'VN+1' 2 a = a e i i x V. N 1 (2.47a) where i s the covariance matrix; i . e . , w i t h = p ( i ) , N p 0 p l P2 p l p0 p l p2 p l P 0 PN-1 PN-2 PN-3 'N-l N-2 N-3 (2.47b) Equation (2.47a) can also be obtained from (2.41) by solving for and then substituting a with -1 . This minimum value is a non-increasim function of N . When N is large, we have [27] 2 cr e = 2W exp [ ^ / JJ ln S(f) df] (2.48) If e is also minimized, then the minimum error achievable by DPCM is q £ = e q v-^f exp [|y /_JJ ln S(f) df]} (2.49) ° x Comparing (2.45) and (2.49), we can see that for e £ £ q or R £ R q , the rate-distortion bound and the minimum mean-square error achievable by -R/W DPCM dif fer only in a factor which i s due to quantization. Since 2 is the error bound for transmitting independently distributed random samples at rate R , and since no pract ical 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 ig . 4 are the signal-to-noise ratio vs. the rate R as obtained from the reciprocals of (2.45) for the rate-distortion bound and (2.49) for DPCM using Max's optimum and optimum uniform quantizers, both with and without entropy coding. The minimum prediction error i s 2 assumed to be 14.35 dB below * . It i s noted that with entropy coding, the S N R q achievable by DPCM is approximately 2 dB below the bound. When fixed-length coding is used, a degradation of 1 to 1.5 dB i s noticed for optimum quantizer. Optimum uniform quantizer with fixed-length coding This value is obtained from the power spectrum of the f i rs t -order Mar-kov process bandlimited within W = 40irf , where f is the corner f re -o o quency. 2 7 R/2W, BITS PER SAMPLE Fig. 4. Comparison of DPCM performance with the rate-distortion bound; a 2! /a 2 = -l4.35dB e 1 u-*-00 x has the lowest SNR . AT R/2W = 5, for example, the SNR for this case o o is almost 5 dB below the bound. 2 2 Although Fig . 4 is plotted with (a /a ) „ = -14.35 dB, i t 2 2 applies also to any other value of (a /a_ )N^ c o' T h e only necessary change 2 2 i s to add [the new value of (a /a ) „ in dB - 14.35 dB] to the v e r t i c a l e x N-*» scale. 2.6.2 Two-Dimensional Random Signal For a two-dimensional random signal , such as a video- image, the rate-distortion function with mean-square error f i d e l i t y cr i ter ion can also be expressed parametrically as follows* [28]. 1 S(fx'V R<*> = \ ffA l o g 2 — f - Z - d f x d f y (2.50a) d((j>) = a 2 - SS. [S(f , f ) -cb] df df (2.50b) A x y x y 2 where A = {f , f : S(f , f ) > d>}, a i s the signal power, S(f , f ) i s x y x y x y the two-dimensional power spectral density, and f_ and f are the spatial frequencies in the horizontal and ver t i ca l directions, respectively. For discrete video signals , such as those resulting from raster-scanning and sampling, the power spectrum S(£^,£y) i s defined within I f I £ W and If I £ W , where 1/2W is the distance between two adjacent x x y y x samples and 1/2W^ the distance between two adjacent l i n e s . Again, le t A denote the minimum value of S(f , f ). Then, for <J> $ c|> , i t can be vm x' y m easily shown from (2.50) that the normalized mean-square error is 4W W W e = 2 " R / 2 W x W y {-^f e x p t ^ - Z ^ x / ^ l n S ( f x , f )df_df ]} (2.51a) a x y x y S t r i c t l y speaking, (2.50) i s the rate-distortion function of Gaussian random signals. However, i t i s also a bound for non-Gaussian random signals [ 24] • Since d = 4W W cb when cb $ cb , (2.51a) holds for x y T m e j? 4W W cb la x y m (2.51b) or W W R >, =r f * / Ty. l o g . S(f , f ) df df - 2W W l o g . cb 2 -W -W °2 x y x y x y °2 Tm x y (2.51c) The values of R and e in most pract ical communication systems are such that (2.51b) and (2.51c) are true. As in the one-dimensional case, the error bound in (2.51a) is -R/2W W composed of two factors; the f i r s t factor, 2 x y , represents the error bound for quantizing independently distributed random samples, and the second, which is enclosed within the braces, represents the l imit 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 in F i g . 5 are required to obtain the best l inear prediction f U i - 2 ' j - 2 S 0 V l ' J - 2 S f V j - 2 Fl C u i + r j - 2 3 e i - l J - 1 s e r V j - 1 i < > "i+i'j-i •> \ r 1 u i - 2 ' j \ f r U i - l ' j 3 V r u. . 1J r r ' \ Fig . 5 Samples shown i n black dot are used for prediction of the present sample u^y Assume that the number of quantization levels L £ 8. Then the predicted value, u.., of u.. can be wri t t e n i n terms of the feedback c o e f f i c i e n t s {a } as follows. m,n u. . = a. 1 u. . , + a_ „ u. . 0 + . .. + a r t „ u. . vr I J 0 , 1 0 , 2 1 , 3 - 2 0,N i , 3-N + a A u. , . + OL - u. .. . , + ...+ a, „ u. n . „ 1 , 0 1 - 1 , 3 1 , 1 i - l , 3 - l 1,N i - i , j - N + OL. _ u. ,, . + CL, - u. w . , + • • • +a u M ,0 i-M,j M,l i - M , j - l M,N i-M,j-N Let R(m,n) denote the two-dimensional c o r r e l a t i o n , i , e . ', R(m,n) = 2 E{fu.. u. ] }. Then the mean-square p r e d i c t i o n e r r o r i s i j i-m,j-n J 2 2 a Z = E[(u. . - u. Y] e 13 13 M M N N = E E E E a a . . R(m-m',n-n'), m+n^O, m ' + n V O , „ n , n m,nm,n m=-0 m =0n=0 n =0 (2.53) 2 By d i f f e r e n t i a t i o n , i t can be shown that 0 ' i s minimized i f {a } e m,n s a t i s f y the following set of equations M N m = 0,1,..,M n = 0 , 1 , . . . ,N E E « t „ i R(m-m',n-n') = 0 , n m '=0 n ' = 0 m ' n m + n * 0 (2.54a) 2 and the r e s u l t i n g minimum value of i s 2 M N a = E E a R(m,n) e _ n m,n m=0 n=0 (2.54b) Define the one-dimensional covariance matrix V^(k) as follows, where 2 p(m,n) = R(m,n)/o . v 1 ( k ) = p ( k , 0 ) p(k,l) p(k,l) p ( k , 0 ) p(k,N) p(k,N-l) p(k,N) p(k,N-l) P ( k , 0 ) (2.55) 31 Then, from (2.54), we can express the minimum i n a form s i m i l a r to (2.47) as follows. 2 Iv] 2 | V-1| (2.56a) where v 1 (0) v 1 ( i ) v 1 ( i ) • v 1 ( p ) V 1(M) V1(M-1) V 1(M) V 1(M-1) v 1(0) (2.56b) and V_^ i s a matrix obtained from V by de l e t i n g i t s f i r s t row and column. It i s noted that (2.53) i s a T o e p l i t z form i n two dimensions 2 and that the minimum of given i n (2.56) i s a non-increasing function of M and N. Following a procedure s i m i l a r to the one used i n Section 3.1 of reference [27], i t can be shown that when M and N approach i n f i n i t y the minimum value of a 2 i s e W W = 4W W e x p h — - — f * f J l n S ( f ,f ) df df ] (2.57) •w « x y r 4W W -W -W x y x y M,N-x» x y x y Comparing (2.51) and (2.57), we see that DPCM can also remove a l l the redundancy i n two-dimensional s i g n a l s , provided that a l l the previous samples shown with black dot are used f o r p r e d i c t i o n . I f S(f ,f ) i s separable, that i s , i f i t can be w r i t t e n as x y S(f ,f ) = S,(f ) S.(f ). then (2.57) can be s i m p l i f i e d as follows, x y 1 x 2 y ' W W • { 2 W x e xP [2W- J-WX l n S l ( f x > d f x ] H 2 W y e^2W-'^ l n S 2 ( f y ) d f y ] > M,N-+<» x x y y (2.58) Furthermore, i f S (f ) and S_(f ) are the power spectra of M t ' 1 - and N ^ -x x /. y order Markov sequences, respectively, 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 prediction error bound given in (2.58). For example, i f both S,(f ) X X and ^ ( f y ) a r e P o w e r spectra of f i rs t -order Markov sequence, then the correlation coefficient 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 . _ 1 . , u. , and u . , . _ , , are required for the best i l>3 -1-> 3 1 l>3 l l inear prediction, and the resulting minimum prediction error i s ae2 = (1 - e~ 2 a) (1 - e" 2 B) a 2 (2.60) 2 2 The values of a /a for certain simple prediction schemes e were calculated from (2.56) by using the s ta t i s t i cs of two video images shown i n Fig . 11 and the results are l i s t e d in Table I . Two different correlation coefficients were used i n calculation for each image, one ob-tained direct ly from measurement, the other calculated from.(2.59). The values of a and 3 for the lat ter case were obtained by f i t t i n g an expo-nential curve to the 30 measured values of the correlation function as shown i n Fig . 12. Table I shows that with the correlation function of (2.59), the prediction using 3 nearest previous samples yields a very 2 2 - 1 high value of (a /a ) in dB, which in 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 in (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 is seen for both images. This shows that the assumption of the two-dimensional correlation function given in (2.59) for video images may not be a good one. In fact , the correlation i n diagonal direction obtained from this equation i s much smaller than the actual 2 2 - 1 value i n most cases. Also shown in Table I are. the values of (a /a ) e TABLE I 2 2 - 1 Comparison of the values of (a /a ) in 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 ) ^ \ ^ ^ Previous Above Previous and Above Nearest Three Crowd From (2.59) 9.78 10.56 12.98 20.34 from measurement 10.74 11.62 13.28 13.60 Cameraman from (2.59) 16.74 17.53 20.13 34.27 from measurement 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 is 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 for two-dimensional signals, we can simply multiply (2.57) or (2.58) with the minimum quantization error e . The argument i n Section 2.6.1 regarding q the minimum DPCM error and the rate-distortion bound also applies here. In part icular , with a proper correction i n the ver t i ca l scale, F i g . 4 remains v a l i d . III . SYSTEM OPTIMIZATION 3.1 General Optimization Procedure-We consider now the problem of designing the system in F i g . 1 to maximize SNR in (2.15b). Assume that R (k) = R (k) = 0 for k ^ 0, o n qn and L ^ 8, in which case is given by (2.16), by (2.17) and by (2.18) and (2.26), and a 2/a 2 by (2.29). The following facts are of importance: a) depends on L, {u^}, {v^}, and P g (a ) ; Pg( a) depends on {a }^ and p ( i ) ; p(i) depends on f g and W. For L , {cO, f g and=W fixed, depends only on {u }^ and {v^}. In many pract ical si tuations, changes in f g , W and (a^}have l i t t l e effect on p £ (a ) . When x(t) i n F i g . 1 is Gaussain and Lv 8, P e ( a ) I s also Gaussian, independent of {cu}, f g and W. b) e depends on a l l of those factors which affect £ . In addition, m 1 e depends on P . . , which depends on the b i t rate R = f log„ L. For L , m r xj s °2 {a.}, f and W fixed, £ depends only on {u.} and {v.}. x s m l x c) e = E Q, where Q depends only on {a.} as shown in (2.26) and c n x e depends on the same factors which affect e . n m 2 2 d) a /o depends on {a.}, and on p(i) which depends on f and W. £ X 1 S The above facts motivate the following optimization procedure. 1) Fix L , f , W, and {a.}. s x A, 2) Determine p e (a) (or P e (a ) ) . 3) Choose {u.} and {v.} to minimize e + e + Qe . x x q m n 4) Using p (a) from step 2, choose {a.} to minimize ( E + E + Q E ) o r e r > x q m n . 2, 2 a /a e x 5) Repeat steps 3 and 4 u n t i l the values of SNRQ which result f o l -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 unt i l further repetition yields v i r t u a l l y ident ical values of S N R q . If x(t) is Gaussian, proceed direct ly to step 7 from step 5. 7) Repeat the above procedure beginning at step 1 for new values of L , f and W. ' s In many applications, some system parameters are constrained. Any such constraints must be maintained i n system optimization. For example, in voice systems the quantizer is usually constrained to be logarithmic, with the result that the only independent quantizer variables are the overload level and the companding parameter [29]• When the system in F i g . 1 i s optimized, both e^ and - Qen» and possibly z w i l l contribute s ignif icant ly to e in (2.12), unless m P i s given by (3.3). If this statement were not true, then £ could be decreased, -either by -increasing -L u n t i l -e becomes s ignif icant , or by de-creasing L u n t i l £q becomes s ignif icant . 3.2 Optimization of the Quantizer The selection of {u }^ and W^} i n step 3 involves the optimi-zation of the quantizer for a fixed number of output levels L . With f and W fixed, minimization of e in (2.12) maximizes S N R q in (2.15b). The optimum {u }^ and W^} must satisfy the following equations, assuming • u i = "L+l 3E 3E 3E ^ + - ~ + Q ~ = 0 i = 2 , . . . , L (3.1a) du. 3u. 9u. I X 1 3E 9E 3E £ + -r- 5 1 + Q T - 2 - =0 i = l , 2 , . . . , L . (3.1b) 9v. 8v. ^ 8v I X X Substituting (2.16) - (2.18) into (3.1) y ie lds , after some manipulation, the following equations. ( 1 - Q ) [ v . 2 1 - v 2 + 2.E. v . ( v . P . . - v . . P. . .)]+0.S. v 2 (P . . -P . . .) „ = i - i x 3 = 1 j 3 I J j-1 1.-1,3 3=1 3 iJ i - l ,.1 i L 2 E v . (P . . -P . . .) • = 1 J i J 1-1,3 J ~ 1=2, . . . ,L (3.2a) L u L u . (1 -Q) E ( v . - v . ) P . . / 1 1 p (a)da+ E [(1-Q)v.+Qv.] P . . / J p (a)da . , 3 i 13 u. e v •. , 3 i 31 u. e 3=1 1 3=1 3 L u = E P f 3 ± P e (a)d , j = l , 2 , . . . , L (3.2b) 3=1 j For PCM, Q=l and (3.2) reduces to equations obtained by Kurten-bach and Wintz [16]. Furthermore, when the d i g i t a l channel in F i g . 1 is noiseless, P. . = \ l 7^ (3.3) 13 I 0 x^3 i n which case (3.2) reduces tothose obtained by Max [30]. In general, solution of (3.3) requires an i terative approach similar to that used ear l ier [16] for PCM. 3.3 Optimization of the Linear Predictor The normalized mean-square error e can be minimized with res-pect to the feedback parameters by differentiat ing e with respect to a_^ 1 £ i S Niequating the resulting N equations to zero, and then solving fo {a.}.. Since e , e and. e are independent of {a.}, we have x - q m n , r 1 2 2 8 a e 30 0 e (e + e + Qe ) (-^) + ^ - . e n = 0 i = l , . . . , N (3.4a) q m n da. 2 da. n 2 x a x a x x 3 O 2 N where ( — ) = a 2p(i) + E a p ( i - j ) (3.4b) i a i=l 2 x J and the differentiat ion 3Q/8a can be obtained from (2.26). Because of i the complexity of Q, an expl ic i t solution for a^ from (3.4) i s very d i f -f i c u l t . Consider, for example, the case N=l. From (2.12), (2.2b) and (2.29), we have e 9 e = [e + E + y] (1+a - 2ap) (3.5) q m 1-a 2 where a= and p = p^. The optimum a must sat isfy the following equation, (1 - a 2 ) 2 (a-p) (eq+em) - (pa 2 - 2a+p) e n = 0 (3.6) It 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 is demonstrated in 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 distortion is negligible and, hence, S N R q can be approximated as i n (2.14b). In addition, P e ( ° 0 i s assumed to be independent of {a }^ and f . s 3.4.1 Noiseless Digi ta l Channels In some practical situations, the channel noise level i s s u f f i -ciently low that £ I << e and E << e , i n which case one can assume J ' m1 q c q that (3.3) is true. For optimum or near optimum quantizers and for logarithmic — K quantizers, e = C 4 [29.31], where constant C depends only on q q q p (a). If p (a) is Gaussian, for example, C = /3TT/2 and i f p (a) is re e q e 2 2 Laplacian, C = 4.5. When N=l and when a /a i n (2.29) i s minimized, q e x (2.12), (2.14) and (2.40) y i e l d S N R o = l t 4 R / f s [ C q d-P 2)]" 1 (3.7) where p = p^. In considering the dependence of S N R q on f g , i t must be remem-bered that p varies with f . Let T = 1/f . Then p i s a function of x. s s In most cases of interest , p(x) can be closely approximated by the f i r s t two non-zero terms in the Taylor series. If p i s differentiable at T = 0 then p(x) is even in x and p(x) = 1 + a 2 x 2 (3.8a) where a 2 = (1/2) [ d 2 p / d x 2 ] T = 0 0 (3.8b) The inequality in (3.8b) i s true because p(x) i s maximum at x = 0. We shal l assume that ^ . If a 2 = 0, the following analysis applies, using the f i r s t non-zero series coefficent. The substitution of (3.8a) into (3.7) yields S N R q = f g 3 exp (2R l n 2/f g ) (3.9) where C-, = (-4 C a„ W ) _ 1 > 0. Since 1 q z 3SNR . . . - = C. f (3f - 2R ln2) exp(2Rln2/f ) (3.10) o r x s s s s and 3 2 S N R o 3f 2 s = 3C exp (2Rln2/f ) > 0 (3.11) 3f =2Rln2 1 s s SNR is minimized at f = (2Rln2)/3. Since 2W $ f £ R, i t follows that o s s either f = 2W or f = R maximizes SNR . The difference between SNR s s o o at f = 2W and SNR at f = R yields s o s SNR o - SNR f =2W 2W = C (2W)3 4 R / 2 W [1-(R/2W)3 4 ( _ R _ 1 ) ] (3.12) f =R s From (3.12), i t follows that i f R * 4(2W), f = 2W maximizes S N R Q ; otherwise f = R maximizes S N R . s o If p(x) is not differentiable at T = 0, then series expansion about x = 0 can be replaced by expansion about a point near x = 0. In this case, . p(x) s i + a | T | (3.13a) where a± = dp/dx\^+ (3.13b) In (3.13) we assume that a^ . ^ 0, and x ->• 0 + means "as x approaches 0 from positive values". The negative exponential correlation p(x) = e k| T l } b > 0, is an example of p(x) being not differentiable at x = 0. An approach similar to the one above shows that SNR is minimized o at f = R ln2 since a.. < 0, and that f - 2W, which i s also called the s 1 s Nyquist rate, maximizes S N R q for a l l values of R >, 2 (2W). If R < 2(2W), f = R maximizes SNR . s o It should be noted that the conclusions made above are true only i f the power spectrum S^(f) of quantization noise is relat ively f l a t over a l l |f| $ f /2. In practice, S (f) is bell-shaped with a s q maximum at f = 0 [32]. In part icular , when K = R / f g i s small, the spec-trum has a very high and narrow peak within the signal band, i n which case sampling at a rate higher than f = 2W w i l l be far less advantageous than predicted above. 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 Digi ta l Channels When the transmission channels is noisy, SNR for N = 1 i s J o f e S N R o = 2W [ ( G q + £m + " " " " V ( I + a 2 a p ) ] ( 3 ' 1 4 ) 1-a Unless p (a) is uniformly distributed, closed-form expression for E e m and are lacking. To study the dependence of S N R q on f , the errors e , and were f i r s t calculated from (2.16)-(2.18), a was then selected to minimize the term i n the brackets in (3.14), and SNR was then obtained o for various values of K and R. In calculating E , e and e , the quantizer x^ as assumed to be ° q m n n logarithmic with u = 100 and overload levels chosen such that e^ i s close to i t s minimum. The quantizer output levels were natural-binary coded and the resulting binary digits were transmitted over an additive white Gaussian channel using antipodal signals. 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 probability density P e ( ° 0 was assumed to be Laplacian for speech and Gaussian for video (see Section 4.2). The correlation function P ( T ) was assumed to be exponential for both speech and video; thus p = = e~h^fs with b = 2irf and p = 0.9753 at f = 20 x (2irf ) for video, and o s o b chosen such that p = 0.89 at f = 8 kHz. s Fie . 6 shows SNR vs. the normalized sampling rate £ = f /2W o s when the d i g i t a l channel i s noiseless for speech (a) and video (b) s i g -nals . When K is held constant, S N R q increases l inear ly with log £ , with S N R q increasing by approximately 3dB whenever £ i s doubled. When R is held constant, 5 = 1 maximizes SNR for the values of R considered. This o result agrees with the analysis in the previous section. When the channel becomes noisy, and when K is held constant, 43 S N R q no longer increases l i n e a r l y with l o g E, as shown by the s o l i d curves i n Figs. 7 and 8. In F i g . 7(a), for example, S N R q i s optimized at E = 4 for K = 3 , and the r e s u l t i n g value of S N R q (= 20dB) i s 5 dB higher than the value obtained f or £ = 1. However, when K and E, are both allowed to vary,E, = 1 i s seen to maximize S N R q f o r a l l the values of K considered i n Figs. 7 and 8. The dotted curves show the maximum S N R when R = f K i s constrained o s to have the values shoxra. When R i s constrained, E, = 1 maximizes S N R , o except f or large value of R and low channel energy-to-noise r a t i o cb^. The envelope tangent to the top portions of the s o l i d curves i n F i g . 2 and 8 y i e l d s the maximum value of S N R q for any f i x e d value of E. The optimum value f or K when E, i s f i x e d depends on £. 3.5 Optimization of the Bandwidth To optimize the bandwidth W, the e f f e c t of out-of-band d i s t o r -t i o n must be taken i n t o account. Assume that the sampling rate f = 2W, which has been shown to optimize S N R q i n most cases i n the previous sec-t i o n . Then, from (2.12) and (2.15), we have 2 CO £1 Ul O S N R = / S (f) df/{(e + e + Qe ) ( ~ ^ r ) A. S ( f ) d f + 21 S (f)df} o - 0 0 m q m n 2 -W m W m q x (3.15) Equation (3.15) i s a very complicated function of W, because at a constant b i t rate R, a l l the errors e , e and e are dependent on W. In addition, q m n 2 2 2 2 the r a t i o a /a depends on W too, since, from (2.29), a /a i s a 6 x e x function of p ( i ) , which depends on W as follows. p(i ) = / J S (f) cos (7rif/W)df/ S (f) df (3.16) 0 m U m In view of the d i f f i c u l t y 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 2 4 8 NORMALIZED SAMPLING RATE g (a) ~T i — ! — i— r r -2 4 NORMALIZED SAMPLING RATE 5 fb) Fig. 7. S N R 0 f° r speech as obtained from (3.14) vs. £ ; ct = a is optimized. Values of K are shown next to solid lines. Dotted lines correspond to the constant R values of Fig. 6(a). (a) cb = P/7f N = s s o lOdB, (b) <j>s = 8dB. 2 4 8 NORMALIZED SAMPLING RATE £ fa) 2 4 8 NORMALIZED SAMPLING RATE § fb) Fig. 8. S N R q for video as obtained from (3.14), with a optimized. Values of K are shown next to solid lines. Dotted lines correspond to the constant R\ values of Fig. 6(b). (a) cb = lOdB, (b) cb = 8dB. W, numerical approach i s employed. The input s i g n a l m(t) i s assumed to be a Gaussian Markov process with power s p e c t r a l density S (f) = i (3.17) i + ( f / f 0 r 3.5.1 Noiseless D i g i t a l Channels When the transmisstion channel i s n o i s e l e s s , e = e =0, and m n (3.15) becomes a 2 n „ „ r•— .-R/2W -1 . W. . e v , . 2 -1 ,W s,-1 ,„ ., „ N SNR = [/3 4 tan (—) (—r-) + 1 tan (—) ] (3.18) O I Z IT I o a o X where we have assumed the quantizer i s optimum or near optimum so that 2 2 C = /3IT/2. When the pr e d i c t o r i s optimized, a /a depends only on q e x N, S^Cf) and W. In choosing N, two cases are of p a r t i c u l a r i n t e r e s t ; that i s , N = l , which has been used extensively i n p r a c t i c a l a p p l i c a t i o n s , and N - - * » , which gives an upper bound f or S N R q of DPCM i n t h i s p a r t i c u l a r case. When N-l, we have 2 a h X W ~ - r w cos( f/W) . -1 ,W . . . p = / n T: d f / f tan (-=—) (3.20) U l + ( f / f o ) Z ° o When N-*°°, we have, from (2.48), a 2 W/f f e = o ^ e x p [2 _ 2 ta_ ( 3 > 2 1 ) 1 + (W/ f Q ) z tan" X(W/f o) W o S N T A O vs. 2W/R for N = 1 and N-*» as obtained 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 . r ° o o o o Note that 2W/R = 1/K, since f = 2W. Three curves are p l o t t e d f o r each R; the lower one applies when N = 1, the middle one when N-*», and the upper one i s the r a t e - d i s t o r t i o n bound. I t i s i n t e r e s t i n g to note that i n each 47 case the curves have an identical shape for a l l R . In part icular , when N = 1 and N °°, a maximum occurs at the same value of 2W/R; i . e . , 2W/R= 0.33. Thus, the optimum bandwidth W = 0.66R, which i s equaivalent to K = 3. It is also noted that, the curves for N = 1 and N •> °° at the same b i t 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 in this case P(T) is no longer exponential due to bandwidth l imitat ion, S N R for the rate-distortion bound i n F i g . 9 were calculated o 0 from the following equations, which were derived from (2 .44) and (3.17) with the out-of-band distortion added to (2.44b). ™ ™ r,s-R/W W ^ o 1 ,„ „-^o N -1 ,W . , SNR = {2 — exp [2-2 (—) tan (—) ] + ° l + ( W / f or tan i (W/f o ) W ±o 1 - - tan" 1 (I-)}"1 for R ^ R (3.22a) IT f O O SNRo = 1- *s£* + — ^ — (3.22b) tan (W/f ) ( l + / ) t a n X (W/f ) with 2f R = - ~ ~ T A N W) F O R R <R (3.22c) ln2 o S N R q i n (3.22) i s anon-decreasing function of W, as shown i n F i g . 9. When W is small, the rate-distortion bound and SNR of DPCM coincide, because o i n this region the out-of-band distortion dominates. 3.5.2 Noisy Digi ta l Channels When the channel is noisy, S N R q i s given as follows. SNR = {(e + e + (1+a2 - 2ap) - tan _ 1(l-) + 1 - -o q m ^ i TT r TT 1-a o tan" 1 (j-)}" 1 (3.23) o Rote-Distortion Bound DPCM; N + co DPCM; N = 1 i i i i i — n 1 — i — i .2 .3 .4 .5 .6 .7 .8 .9 1 2W/R SNR o for Gaussian Markov process as obtained from (3,18) for N = 1 and N -> °° and from (3.22) for rate-distortion bound vs. 2W/R; The channel i s noiseless. where p is given in (3.20) and e , £ and e in (2.16), (2.17) and (2.18), q m n respectively. In numerical calculation, i t i s assumed that the quantizer is logarithmic and the channel is additive white Gaussian as i n Section 3.4.2. Shown in F ig . 10 i s S N R vs. 2W/R as obtained from (3.23) with the relative transmitter power c b r 7 = P/1000 f N fixed at lOdB (a) and W o o 8dB (b). The cross symbols denote the values of S N R q , which were actually claculated from (3.23) with integer values of K = R/2W, and the s o l i d l ines were f i t t e d from these symbols. F ig . (10) suggests that when the channel is noisy, larger bandwidth and smaller K can give better per-formance at a constant b i t rate. This is also true when <f> i s fixed w and the b i t rate R is increased. IV. ONE- AND TWO-SAMPLE FEEDBACK SYSTEMS Because of their simplici ty i n structure, one- and two-sample feedback systems are used widely in pract ical applications. In this chapter, we shal l study i n detail the performance of these systems, i n -cluding one- and two-previous-sample feedback systems for speech and video signals and previous-line-and-sample feedback systems for video signals . 4'. 1 Restrictions on System Parameters Some system parameters are constrained in conducting this study. The constraints are as follows. 1) The sampling rate f = 2W and the out-of-band distortion is negl igible , i n which case S N R q = 1/e as given in (2.13b). 2) The quantizer is logarithmic [29,31] with u = 100 and overload level for various values of K chosen according to Table II unless other-wise stated. When the overload l e v e l i s so chosen, the quantization error TABLE II e -Probability K Density 1 2 3 4 5 6 7 Laplacian 10 12 18 20 21 22 23 Gaussian 7 8 9 10 11 12 13 is close to i t s minimum. Logarithmic quantizers are f a i r l y easy to realize and have the advantage that the distortion is re lat ively i n -dependent of the signal s ta t is t ics for large values of u [29,31]. They are part icularly attractive in 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 level V^, 1 $k ?2 , i s the binary representation of the decimal integer (k-1). 4) The coded binary digits are transmitted over an additive white Gaussian channel using antipodal signals. Thus, P ± j = P d i J d - p ) K _ d i J (4.1) where d^j i s the Hamming distance between the codes of the quantizer out-put levels v^ and v^, and p is the per-bit error probabil i ty . In our case [33], p = — r exp (-y 2/2)dy (4.2a) where <J> is the channel signal energy to noise ra t io . Let P be the power of the transmitted signal and N q / 2 be the power spectral density of the white Gaussian noise. Then, <j> = P / R N q (4.2b) 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 is assumed to be either a speech or video s ignal . In each case, S N R q calculated from (2.13) and the related equa-tions are compared with the measured values of S N R q obtained from simu-lation 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 father'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 typical of conversational speech [34,35]. The two video images used i n simulation are shown in F i g . 11. Each of these images was reconstructed from an array of 512 x 512 picture g elements, each picture element being represented by 2 = 256 gray levels Shown in Fig . 12 are the measured correlation functions, along with the least-mean-square-fitted negative-exponential curves, i n the horizontal , v e r t i c a l and diagonal directions. These correlation functions reflect the fact that crowd and cameraman scenes, respectively, contain large an small amounts of detai ls . The measurement of S N R q is based on the following equation. N N „ S N R Q = ( E x p / [ E (x. - x ) Z ] (4.3) i=l i=l where N is the total number of samples. In the calculation of S N R , the o measured values of the correlation coefficients are direct ly used and /-v the amplitude probability density, P e ( c t ) , of e^ is assumed to be either Gaussian or Laplacian. For speech signals, we assume that the amplitude probability density of is Laplacian, i . e . , P e (°0 = exp (-/2~ la])/^, independent of This function has been shown to be a reasonable approximation to P e(°<) f ° r real speech samples [9,11,29,35 ]. For video signals, P e(a) is assumed to be Gaussian, also i n -dependent of {ou}. Figs. 13 and 14 show the amplitude probability den-s i t i e s of x. (p (a)) and e. , where e. = x. - p, x. respectively, 1 x t x i ' i i K l i - l ' r / ' for the two images shown in Fig . 11. A Gaussian approximation for P e (°0 is not unreasonable, although, as shown i n Figs. 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 = . . . = = 0, seems more appropriate for PCM (see also [7,36,38 ])• 4.3 Simulation of Channel Errors In the simulation of the DPCM system shown i n F i g . 1, an IBM Fig. 11. Picture originals; 512x512 picture elements with 8 b i t s per picture element. 55 A : Horizontal +: Vertical X: Diagonal 15 DISTANCE (a) ^ .6-3 O C: 3.5* UJ ct Q: o .4-3 o A • Horizontal + .' Vertical X : Diagonal •3"! . i - i 20 — i — — -25 I 30 r—i 1 i 1 r-15 DISTANCE (b) Fig. 12. Correlations of the pictures shown in Fig. 11; (a) crowd scene, (b) cameraman scene. The distance of the horizontal scale i s relative to the distance between 2 adjacent horizontal elements, -T 1 1 r- - T 1 [ r-JO Fig. 13. Amplitude probability density of the pictures shown in Fig. 11; (a) crowd scene, (b) cameraman scene. 58 360/67 d i g i t a l computer is used. In part icular , a pseudo-random number generator implemented by using Lehmer's multiplicative congruence method [39] is used to simulate the noisy d i g i t a l channel. The pseudo-random numbers generated are uniformly distributed 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 ror probability p, the natural-binary coded quantizer output i s transmitted (by simulation) in the following manner. Every time a binary d i g i t is emitted from the natural-binary coder, a pseudo-random number is also generated and compared with the value of p. If the random number i s less than p, then the binary digi t i s changed to 0 i f i t was a 1 or vice versa; i f not, then the binary digi t remains unchanged. Since the random number is uniformly distributed within 0 and 1, i t is not d i f f i c u l t to see that the error probability of the re-ceived digit is p. 4.4 One-Previous-Sample Feedback For one-previous-sample feedback system, N = 1 and e i s given by (3.5). To ensure system s t a b i l i t y , |a| < 1. Also, e i s minimized by choosing the sign of a to be the same as the sign of p. In most practical si tuations, p £ 0, i n which case the allowable range for a is 0 S a < 1. 4.4.1 Effect of a and cb From (3.6), i t can be easily seen that for 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 is usually much smaller than either or both e n q m J n 2 and e [l6]> a _ = (1 - A - p )/p, which i s less than p. q op t The e f f e c t of a and cb on S N R q when K = log2L = 4 i s shown i n Figs. 15 and 16. The general behaviour of the curves remains unchanged f o r other values of K . The curves bunch together i n the region cb £ lOdB, because i n t h i s region S N R q i s l i m i t e d by quantization noise, which i s independent of cb. . The bunching together of the curves i n the region <b = -8dB, where S N R q i s l i m i t e d by channel noise, occurs because p = 1/2 i n t h i s region, which i s independent of cb too. Figs. 15 and 16 show that a decreases monotonically from opt a = p when cb i s high to a = ( 1 - , / l - p 2 ) / p when cb i s low. This be-opt opt V haviour can be seen more c l e a r l y i n F i g . 17, where ctQ i n Fig s . 15 and 16 i s p l o t t e d as a function of cb. I t i s noted that a A i s very close to r r opt - y i ^ - - -3 i t s lower asymptotic value, (1 J 1-p ) / p , when cb $ 5dB, or p ^ 6 x 10 For speech s i g n a l , the choice a = 0.75 appears to be a good one. F i g . 15 shows that for K = 4 such a choice keeps S N R q w i t h i n 1/2 dB of i t s maximum value as cb varies from 10 to 4 dB, which implies a v a r i a t i o n 6 ~ 2 i n p from 3.9 x 10 to 1.3 x 10 . The choice 0.75 i s p a r t i c u l a r l y convenient when the. encoder and decoder i n F i g . 1 are to be r e a l i z e d d i g i t a l l y . For video s i g n a l , the choice a = 0.9 i n F i g . 16 seems to y i e l d reasonably optimum performance when <j> and p vary over the range considered above for speech. For s i m p l i c i t y and convenience i n d i g i t a l r e a l i z a t i o n , the choice a = 1/2 i s p a r t i c u l a r l y d e s i r a b l e . For th i s value of a , S N R q i n Figs. 15 and 16 l i e s approximately midway between the maximum value and the value obtainable when a = 0. When a - 0, a PCM system r e s u l t s . F i g s . 15 and 16 show that when a i s greater than zero and less than a certain'value, S N R f o r DPCM i s ° o always greater than that for 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 .6 .8 7 FEEDBACK COEFFICIENT o( Fie. 15. SNR for speech vs. a, = a and cb = P/RN ; N = 1, f = 2W = 8KHz, ° O -L O b p = p(i) = 0.89, K = 4. Quantizer overload level V/a g = 20dB. Experimentally measured values are indicated in symbols. o o 03 O J 1 0 -} P = 0 . 9 d 0 9 0.9569 0 . 8 9 Speech Crowd Cameraman , - T — i — i — i — i — i — i — i — i — I — i — i — i — i — i — i — i — i — i — I — i — i — i — i r °-5 0 5 0, dB Fig. 17. Optimum value of a vs. cb. ~ i — i — i — i — | — i — i — i — i — i — i — i — i — i — | 10 15 o —I P = 0 . 9 8 0 9 0 . 9 5 6 9 0 . 8 9 Speech Crowd Cameraman CO T 1 1 1 1 ! 1 1 1 I 1 ! 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 p -5 0 5 10 T — i — i — i — i — I — r 1 15 J0O dB Fig. 18. a vs. cb ; When 0<a< a , SNR of DPCM i s higher than SNR of & m ™ » max o n max noisy. Let a denote the maximum value of ex for which SNR of DPCM is max o greater than that of PCM. Then, a can be obtained by equating e in 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 y the following equation: (e + E )(a - 2p)(l - a 2 ) + 2(u - p)e =0 (4.4) q m max max max n ' It is noted that when the d i g i t a l channel is very noisy, e >> ( E + e ) 6 J J ' n q m and a = p. On the other hand, when channel noise level is very low, max e + e >> e and a = 1, -1 or 2p. Obviously, i f p < 0.5, then a q m n max max = 2p. If p :> 0.5, then a =1 , since a = -1 i s outside the range max max " of our interest . (Strict ly speaking, a i s not allowed to take the value 1 for s t a b i l i t y reasons. However, a =1 can be interpreted as a ->• ] max max Fig . 18 shows a as a function of d> for the speech and video signals max considered i n Figs. 15 .and 16. In any case, DPCM with 0 < a < p always gives higher S N R q 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 Figs. 15 and 16 indicate the experimentally measured values of S N R q obtained by using (4.3). These results agree almost perfectly with those calculated. 4.4.2 Sensit ivi ty to Variations in Signal Stat is t ics Variations i n signal s ta t i s t i cs must be considered in system design. Deviations i n P £ ( o t ) of the sort encountered i n practice w i l l normally have a relat ively small effect on S N R q , par t icular ly i f the quantizer is logarithmic. Variations in p (k) , however, w i l l affect S N R Q 2 2 through changes i n CTe/°x • Define the sensi t iv i ty coefficient as follows. 64 A. = S N R - 1 1 o . 3 S N R o 3P. 1 $ i sS N (4.5) From (2.12) and (2.12), we have A. = (o2/o2) 1 | 3 (a2/a2 )/3p. | 1 $ .1- $ N (4.6) which i s independent of cb. S u b s t i t u t i n g (2.29a) i n t o (4.6) y i e l d s N-j N N N-j A i = I 2 k^o V W '/ aj + 2 * * V W J V 1 $ 1 * N ( 4 ' 7 ) j-U j-1 K-0 In the case N = 1, we have A^ = 2a/(l + a 2 - 2ap) (4.8a) £ 2a/(1-a 2) (4.8b) The bound i n (4.8b) decreases r a p i d l y as a decreases from unity, as does A^ i n (4.8a). For example, i f a = p = 0.89, then A^ = 8.56, whereas i f a = 0.75 and p = 0.89, then &1 = 6.09, and i f a= 0.5 and p = 0.89, then A^ = 2.78. On the other hand, i f a = p = 0.9569, A.^ = 22.7, whereas i f a = 0.90 and p = 0.9569, ^ = 20.5, and i f a = 0.75 and p = 0.9569, A^ = 11.8. S i m i l a r r e s u l t s also occur when p = 0.9809. Therefore, choosing a to be less than i t s optimum value for p = 0 reduces the sen-s i t i v i t y of SNR^ r e l a t i v e to changes i n p, as w e l l as to changes i n <j>. I t should be noted that v a r i a t i o n s i n p do not n e c e s s a r i l y decrease SNR . F i g . 19 shows the change i n S N R as a function of the o ° b o v a r i a t i o n of p when p = 0.89. It i s seen that deviation of p i n the p o s i t i v e d i r e c t i o n always increases S N R q . This f i g u r e also shows that a = 0.5 i s l e a s t s e n s i t i v e to changes i n p . 4.4.3 S N R q versus Number of Quantizer Output B i t s Figs. 20 and 21 show S N R q as a function of the number of quantizer 65 F i g . 19. % change i n SNR vs. % v a r i a t i o n of p f o r a =0.5, 0.75 and 0.89; p= 0.89. output bi ts 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 is optimum, the middle curves when a is optimized assuming no channel errors, and the lowest curves for a = 0. The maximum improvement of previous-sample feedback DPCM relative to PCM is approximately 7dB for speech and 13dB for video. in Figs. 20 and 21, as explained in the last paragraph of Section 3.1. Even i f the relative transmitter power cb = P/7f N increases l i n e a r l y r s s o with K, in which case p is constant, SNR is maximized at some f i n i t e r ' o value of K because, the quantizer overload l e v e l , being near the value for which e i s minimized, increases with K and causes e to increase q n with K. In fact , i f the overload level 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 is held constant. s ignif icant ly higher than when ot is optimized assuming p = 0. The max-imum obtainable S N R q for a DPCM system i s seen to be considerably larger than that for a PCM system operating over the same d i g i t a l channel, even i f the channel is noisy. An optimum value for K when channel i s noisy i s seen to exist In Figs. 20 and 21, when K and a are optimized, SNR may be It i s also seen from Figs. 20 and 21 that unit variation of K from i t s optimum value can cause considerable change in SNR . 4.5 Two-Previous-Sample Feedback When N = 2, (2.12), (2.26) and (2.29) y i e l d 1 -'2 £ = [ £ + £ + q m (ct 2+l) (c^+CLj-l) ( a 2 - a 1-l) + 2 ( ^ 0 1 ^ ) (4.9) 67 NO. OF QUANTIZER OUTPUT BITS, K Fie. 20. SNR for speech vs. K and <j> =P/7f N for previous-sample feedback ° o s s o systems when a i s optimum, a i s optimum assuming no channel errors, and when a - 0 (PCM). NO. OF QUANTIZER OUTPUT BITS, K SNR f o r crowd scene vs. K and A =P/7f N f o r previous-sample feedback o Y s s o r systems when a i s optimum, a i s optimum assuming no channel e r r o r s , and when u = 0 (PCM). In order for the. decoder in F i g . 1 to be stable, and must be constrained by the inequalities given in (2.36). 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 Figs. 22 and 23, which clearly show the dependence of S N R q on and when K = 4. Curves similar to those in Figs. 22 and 23 result for other values of K. We note in passing that the curves i n Figs. 15 and 16 can be obtained directly from those in Figs . 22 and 23 by setting a2 = 0. 4.5.1 Effect of a^ , and <j> Consider f i r s t the case when error probability p = 0, in which case e = E =0 and m n 2 2 E = E ( 1 + a, + a „ - 2a,p n - 2a_p„ + 2a,a„p,) (4.10) q 1 2 1 1 2 2 1 2 l Thus, i t can be readily shown that the locus of constant S N R q i s an e l l i p s centered about the point a^ = a^ and a 2 = <*2C> where a l c = P l ( 1 - P 2 ) / ( 1 - P i 2 ) (4.11a) and „ „ ° 2 c = ( p 2 " P x ) / ( l - P ! ) (4.11b) The semimajor axis of the e l l ipse has length /c/(1 -p^) and l i e s along the l ine a, + a. = a.. + a„ : the semiminor axis has length /C/(1+p,) 1 2 Ic 2c l and l ies along the l ine a^ - a^ = a^^ - c^^, where C = (e/e ) - [1 - ( P l 2 + p 2 2 - 2 P ; L 2 p 2 ) / ( l - P l 2 ) ] (4.12) Note that a and a equal the optimum values of a and a when p = 0, l c 2c 1 2 and that the second term in the square brackets i n (4.12) equals the f°, -0.89 P, =0.65 Fie. 22. SNR for speech vs. a and a • K=4, f =2W=8KHz, V/ A =20dB. & o 1 2 s e Experimentally measured values of SNR are shown by the " x " symbols. (a) cb = 10dB, (b) cb = 6dB. =0.9569 fi =0.9009 7.1 - i — i — i — i — i 1—i 1—r—i T i T I I l T""^ I I l 1 I' I 1 ^ ' -1 0 FEEDBACK COEFFICIENT ol, (a) P, =0.9569 P2 = 0.9009 FEEDBACK COEFFICIENT ol (b) Fig. 23A. SNR for crowd scene vs. a. and a„; K=4, V/a =20dB. o 1 2 e (a) <f>= lOdB, (b) cb=6dB. P, - 0.9809 p2= 0.9635 72 28.75 28.5 FEEDBACK COEFFICIENT oi) (a) ft = 0.9809 f>2 =0.9635 F i g . 23B. FEEDBACK COEFFICIENT d (b) SNR for cameraman scene vs. a., and a • K=4, V/a =20dB. o 1 2 e lOdB, (b) <j>=6dB. (a) <*>= 2 2 r e s u l t i n g minimum value of /a . When p = 0 and p (k) = exp (-b|k|), —b b > 0, the optimum choice f o r and i s = e and = 0, as noted elsewhere.[24,40]• When the d i g i t a l channel i s n o i s y , the optimum values of and cx„ no longer equal a, and an , and the l o c i of constant SNR , as I l c Ic o shown i n F i g s . 22 and 23, are no longer e l l i p t i c a l . I t i s noted that when <j> decreases, the optimum p o i n t (OL , a„ )• at which SNR i s maximized Y l o p t 2opt o s h i f t s away from the s t a b i l i t y boundary toward the center of the t r i a n g l e . This behaviour i s more c l e a r l y seen i n F i g s . 24 and 25, where the optimum p o i n t s f o r v a r i o u s values of co are denoted by "x". Although the decoder i n F i g . 1 i s s t a b l e as long as ct^ and l i e i n s i d e the t r i a n g l e , there i s no poin t using the l i n e a r p r e d i c t o r i f the values of a, and a_ chosen y i e l d an SNR s m a l l e r than that f o r 1 2 o FCM. F i g s . 24 and 25 show the area w i t h i n which SNRo of DPCM i s g r e a t e r than SNR of PCM. I t i s noted that the area i n c r e a s e s when <J> i s i n c r e a s e d , o and when <j> $ 10 dB, the boundary of the area almost c o i n c i d e s w i t h the s t r a i g h t l i n e cx^ + = 0 and the p a r t of the t r i a n g l e to the r i g h t of t h i s l i n e . This i s p a r t i c u l a r l y true f o r video 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 ap-q n q 1 m1 r proximated by (4.10). L e t t i n g E i n (4.10) equal E ^ , we have 2 2 a l + a2 ~ 2 a i p l ~ 2 a 2 p 2 + 2 a l a 2 p l = ^ .(^«13) Normally, and p 2 are clos e to u n i t y , i n which case (4.13) can be ap-proximated as f o l l o w s . (a1 + a 2) (a1 + c*2 - 2) = 0 (4.14) Since + - 2 = 0 i s ou t s i d e the s t a b l e r e g i o n , i t f o l l o w s that FEEDBACK PARAMETER oC} F i g . 2 4 . Locus of S N R q which i s equal to that of PCM f o r speech. The symbols denote the values of cx^ and which maximize S N R q f o r v a r i o u s values of cb. 75 FEED8RCK PARAMETER c<. (a) F i g . 25. Locus of SNR which i s equal to that of PCM f o r the . o crowd scene (a) and cameraman scene ( b ) . The " x " symbol denotes the values.of and that maximize SNR f o r the value of cb shown. CLj + a ? = 0 i n conjunction w i t h the right-hand s i d e of the t r i a n g l e defines the area w i t h i n which DPCM y i e l d s h i g her S N R than PCM. J • o F i g s . 26 and 27 give the curves on which S N R q f o r both two-and one-previous-sample feedback systems are equal f o r a given <b. W i t h i n each curve S N R ^ would be higher f o r the former. As f a r as the system performance i s concerned, the use of can be j u s t i f i e d only i f and a r e chosen w i t h i n the area bounded by these curves, although other 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. I t i s i n t e r e s t i n g to note that f o r speech the enclosed area 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 video the opposite i s t r u e . In 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 scene, the area i s almost zero, which i n d i c a t e s that i n these cases there i s almost no values f o r which we can use to improve S N R Q . Table I I I shows improvement i n S N R q f o r speech and video when N = 2 i s used, r a t h e r than N = 1. For speech the maximum improvement of 2.73 dB occurs when p = 0 and the improvement decreases as p i n c r e a s e s . The corresponding maximum improvement f o r video i s 0.68 dB and occurs when p = 1/2 f o r the cameraman scene. There seems to be l i t t l e advantage i n using more than one sample of feedback f o r video samples on the same l i n e , even when the channel i s n o i s y . TABLE I I I Improvement i n S N R ^ when N=2 over N=l -- \J-* 00 10 dB 8 dB 6 dB 4 dB 2 dB 0 dB p 0 3.9xl0~ 6 1 . 9 x l 0 ~ 4 2 . 4 x l 0 " 3 1. 3 x l 0 ~ 2 3 . 8 x l 0 ~ 2 7 . 9 x l 0 - 2 Speech 2.73 2.66 1.53 0.47 0. 29 0.26 0.23 Crowd Scene 0.14 0.13 0.02 0.12 Q. 20 0.20 0.20 Cameraman Scene 0.006 0.05 0.20 0.50 0. 67 0.67 0.68 The feedback c o e f f i c i e n t a, f o r N=l i s optimized; K=4. L0.5 0 0.5 1.0 1.5 2.0 FEEDBACK PARAMETER ctj F i g . 26. Locus of S N R q which i s equal to that o b t a i n a b l e from previous-sample feedback system f o r the speech sample. For speech, s i g n a l , S N R q was a l s o measured us i n g the speech sample described i n S e c t i o n 4.2 f o r v a r i o u s values of and a^, and the r e s u l t s are shown i n F i g . 22. I t i s noted that the measured values agree very w e l l w i t h those obtained 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 obtained from ° o x (4.7) as f o l l o w s , where i s defined as i n (4.5). A x = 2 ^ ( a 2 - 1)|/A (4.13a) * 8/A (4.13b) m and where A 2 = 2|a2|/A (4.14a) $ 2/A (4.14b) m 2 2 A = 1 + a 1 + a 2 - 2 a 1 P 1 - 2 a 2 p 2 + 2 0 ^ ( 4 . 1 5 a ) and 9 9 9 A m = 1 - P ] L Z - p 2 z + 2 P ; L Z p 2 / ( p 2 - 1) (4.15b) I f a, and a„ are so chosen that S N R i s maximized when p = 0, 1 2 o then A becomes very s m a l l , w i t h the r e s u l t that s m a l l v a r i a t i o n s i n p^ and/or P 2 can cause l a r g e d e v i a t i o n s i n S N R Q . F ° R speech w i t h p^ = 0.89, P 2 = 0.65 and p = 0, a = 1.4983 and a = -0.6835 maximize S N R q , i n which case A^ = 45 and A 2 = 12. I f we choose ot^ = 1.25 and c*2 = -0.5, then A^ = 30 and A 2 = 8. Therefore, cx^ and can be chosen to y i e l d near optimum performance w h i l e reducing c o n s i d e r a b l y the s e n s i t i v i t y of S N R to v a r i a t i o n s i n p . , as w e l l as cb. o x 80 4.6 Previous 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 two-dimensional video image, then the sample r i g h t above may be used, along w i t h the previous sample, to improve S N R q , which i s u s u a l l y r e f e r r e d to as a p r e -vious line-and-sample-feedback system [7 ]. In t h i s case, cx^ and cx^ are the only non-zero values of {cx^}, where N i s the number of samples per l i n e , which i s normally much greater than 1. From (2.29), we have 2.2 . , 2 . 2 a a = l + a.. + ex e I N 2Vi,o ~ 2Vo,i + 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 ) / a 2 . From (2.26), where cxQ = 1 Q = -1 0 . cx^ -1 0 aN ° 0 % °N ° . -1 0 -1 a 0 a1 -1 0 0 ^ aN ° • ° "N ' KN ° » • • -1 0 a, -1 (4.17) Note that the numerator i s an (N-l) x (N-l) determinant w i t h 3 non-zero elements i n each row except the f i r s t one, and the denominator i s an (N+1) x (N+1) determinant w i t h 3 non-zero elements i n each row or 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 - cx^z (4.18) I t f o l l o w s from (2.31a) and (2.31b) that 81 1 - ct^ - ct^ > 0 and 1 + - > 0 f o r even N (4.19) and 1 - CL - a > 0 and 1 + CL + a T > 0 f o r odd N I N I N (4.20) 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 the c a l c u l a t i o n of ^~from (2.33). S e t t i n g a„ a 3 - = = 0 i n (2.33) and e l i m i n a t i n g cx^ a i n the l e f t - h a n d h a l f o f the (N-l) x (N-l) determinant, we can reduce i t to an M x M determinant 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. 4 - i (-1) M i ± e ± i a i 3 ± ! a 2 3± j a 3 3— 1 . . M-l„+ a 1 e -a i " 1 + A N ! 2 a l A N 2 2 V N 1 • • M--3 2 a l °» M-2 2 a l A N 0 a l a i a N | ' • M-4 2 a l A N 2 M-3 a l " N 0 0 a l - l + a2 j . . M-5 2 a l A N M-4 2 a l A N t 0 0 0 0 . . " 1 + A N 2 0 0 0 0 . . a l " 1 + A N (4.21) The subdeterminants shown by dashed l i n e s i n (4.21) denote e i t h e r D^—, ., i n -I- -f* -H 4- 4- 4--D_—, Dc—, i n which case 3— = 4- ct_T, or -D„—, D.—, -D,—, 3 5 — N 2 4 6 + 2 which case 3 — = + aj_°<N + °JJ • To c a l c u l a t e these determinants, we can f u r t h e r e l i m i n a t e the subdiagonal formed by a^, and then m u l t i p l y the diagonal elements of the r e s u l t i n g t r i a n g u l a r determinant. Let u , 1 £ m S M, denote the p r i n c i p a l diagonal elements of mm the r e s u l t i n g M x M t r i a n g u l a r determinant. Then i t can be shown t h a t + -1 + cc^ f o r even N u u = -1 +3- (4.22a) -1 + K l a N + a N f o r odd N U22 = _ 1 " \ + % ~ a l 2 / u l l U33 = _ 1 " a l + a N 2 " a i 2 / u 2 2 2 2 2 u = -1 - a. + OLt - a, /u .. , (4.22b) mm 1 N 1 m-l,m-l Note that (4.22) i s an i t e r a t i v e equation. The determinant can then be c a l c u l a t e d from u ^ as f o l l o w s . r t - iw ? < k+i)/2 ' (-1)^ ; / n u k = 1,3,5,...,N-1,N even T mm m = 1 (4.23a) 4 k/2 k / 2 (-1) n u k = 2,4,6 N-1, N odd (4.23b) mm m=l I t f o l l o w s from (4.23) that Item (3) i n (2.31) i s e q u i v a l e n t to u < 0 f o r m = 1, 2, 3., ..., M (4.24) mm . The c o n s t r a i n t i n (4.24) i s based on (2.31c) and (2.31e). S i m i l a r con-d i t i o n s can also be obtained f o r the a l t e r n a t i v e form i n (2.31d) and (2. 3 1 f ) . Therefore, i n order f o r the decoder to be s t a b l e , and must s a t i s f y (4.24) and (4.19) or (4.20), depending on N even or odd. F i g . 28 shows the area f o r which these c o n d i t i o n s are s a t i s f i e d . I t i s i n t e r e s t i n g to note that the c o n d i t i o n u < 0 reduces the area of the s t a b l e mm region whenever m i s in 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 , the s t a b l e area converges to a square bounded by the 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 both even and odd N. 1 + ^ - ^ = 0 1 - a1 - c*N = 0 (4.25) F i g . 28. S t a b i l i t y boundary f o r previous line-and-sample feedback systems, (a) even N, (b) odd N. 1 + a. + OL = 0 1 N 1 '- a- + a„ = 0 1 N 4.6.2 E v a l u a t i o n of Q + Since the numerator i n (4.17) i s equal to > which has been evaluated i n the previous s e c t i o n (see (4.23)), the f a c t o r Q can be e a s i l y evaluated i f we can a l s o express the denominator i n (4.17), which i s + + equal to D^_^/2, i n a form s i m i l a r to DM_1 i n (4.23). N-1 By e l i m i n a t i n g a, and a„ i n the l e f t - h a n d h a l f and below the J b 1 N + p r i n c i p a l diagonal of the (N+1) x (N+1) determinant we o b t a i n DN+1 / 2 (-D M+l 1 - a ! -1+3 a l 0 + 0 0 0 + 0 l e o 0 0 1 4 - 2 2 -1+a 'N 0 0 0 M-2 2 a l M-3 2 a l % M + a x 3 M-l 2 a l aN M-2 2 °1 aN , , 2 2 2 2 " 1 + a i V N a i A N l o (4.26a) 2 2 where a = -1 + a. + CL T , 1 N and - " N + CL. 2 2 a 1(l - a 1 + a N ), N even N odd l V N ' "N E l i m i n a t i n g again the subdiagonal elements, we o b t a i n M+l M-l DN+1 / 2 (4.26b) =- ( n u ) ( u . f M + a 2 ) ( 1 - a 2 ) [ - l - a 2 + a / 2 , mm MM 1 1 I N 1 - a, m=l M-l « ( - 1 ) M + 1 ( H u m m ) [ ( - iV+a/) u M M - 2 a 1 ] 2 m=l 2 i 2 2 V a l + o t l V "MM + a l (4.27) 85 where u i s defined i n (4.22), but i n t h i s case u „ takes only the "+" mm ' 1 1 J s i g n i n (4.22a). From (4.23), we. have M + M D = ( - 1 ) n u N-L „ mm m=l (4.28) Therefore 2 D, Q = + 'N-I N+1 2 2 1 + a - OL, + 2a.. /u.„, 1 N 1 MM (4.29) where 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.22). The term can also be expressed by a continued f r a c t i o n as f o l l o w s . 2 " l "MM C 2 c -c -c -c --1 + (M-l) y f r a c t i o n s (4.30) 2 2 where c = ~1 - a, + ct . This continued f r a c t i o n i s very s i m i l a r to I N J 2 2 1/2 the expansion of [c - (c - 4a^ ) ]/2 as shown i n the f o l l o w i n g . Since [c - ( c 2 - 4 a 1 2 ) 1 / 2 ] [c + ( c 2 - 4 a 1 2 ) 1 / 2 ] = Aa±2 (4.31) we have [c - ( c 2 - 4 c t 1 2 ) 1 / 2 ] / 2 = c - [c + ( c 2 - 4 a 1 2 ) 1 / 2 ] / 2 2 a_l = c 2 ^1 (4.32) 2 • a l c Therefore, by comparing (4.30) and (4.32), we can expect that i f N i s in c r e a s e d , ^ + [c - ( c 2 - 4 a 1 2 ) 1 / 2 ] / 2 (4.33) 2 2 1/2 The s u b s t i t u t i o n of u ^ i n (4.29) by [c - (c - 4cx^ ) ]/2 y i e l d s n - z - i j . ^ , ^ T 2 o 2 o 2 2.-1/2 Q = (1 + a± + a N - 2 a x - 2 a N - 2 ^ a N ) = [ ( 1 - a± - c^) (1 - a± + ojj) (1 + a± - o^) (1 + ^ + « N ) ] _ 1 / 2 (4.34) The f a c t o r Q given 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 three sets of a, and OL.. I t i s seen that f o r each s e t of a, I N 1 and a^, the value of Q decreases when N i n c r e a s e s , and reaches a constant when N i s gr e a t e r than 40 f o r the upper two curves and 10 f o r the lower two curves. The constant, i n f a c t , i s the same as th a t obtained from (4.34). Curves f o r other values of and cx^ are found to have very s i m i l a r behaviour. In gene r a l , i f and are not too c l o s e to the s t a b i l i t y boundary derived i n S e c t i o n 4.6.1, the asymptotic values 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 raster-scanned video images, the number of samples taken i n one l i n e i s i n the order of hundreds, i n which case the expr e s s i o n o f Q given i n (4.34) i s v a l i d , even i f and ct^ are very c l o s e to the s t a -b i l i t y boundary. 4.6.3 E f f e c t of cx^, cx^ and cb The s u b s t i t u t i o n of (4.16) and (4.34) i n t o (4.12) y i e l d s 87 7 3 oo-g CO-3 in -a cn o CO CD cn-4 lod, - 0.2690 [oLN = 0.7240 'c&, = 0.4291 .dN= 0.5621 Mi =0.45 \<*>\ =0.3725 [cCN. = 0.5 j i i i I M M i p i inmt}niiiiiii|iriin!npvitB|'iivi|iiii]i(ii|mi| • r f r ! i i i 111) H i i i m [ i i » i i i i i | i w i i w | n i & . . r . . . | . . . . | . . . 1 2 3 4 5 6 8 10 2 3 4 5 6 8 1 0 N Q F i g . 29. The f a c t o r ^ f o r previous line-and-sample feedback DPCM as obtained from (4.29) vs. N f o r va r i o u s values of a, and a.,. I N 88 = [e + e q ra + /(1-cy-c^) (l-a 1+a N) (1+c^-o^) (1+a^c^) ] d + 4 + V 2 a i p i , o + 2 a i V i , i " ^Vo.P ( 4 - 3 5 ) When p = 0, the locus of constant SNR q (or constant e) i s an e l l i p s e centered about the p o i n t a, = a., and CL, = CL, , where 1 1 I c N HSIc' °lc = < P0,1 " p l , 0 p l , l ) / ( 1 " p l , l 2 ) ( A - 3 6 a ) V = ( p i > 0 - p o , i p i , i ) / ( 1 - p i , i 2 ) ( 4 * 3 6 b ) The semimajor a x i s of the e l l i p s e has l e n g t h / c / ( l - p ^ ^) and l i e s along the l i n e a,+a =a, +a„ : the semiminor a x i s has length /c/(1+p, TT a n d , l i e s 1 N l c Nc 1,1 along the l i n e a -ex =oi -«._ , where to N 1 Nc l c c = ( e/e q) - [1 - ( P j > 0 + p 0 , r 2 p l , 0 p 0 , l p l , l ) / ( 1 - p l , l ) ] ( 4 - 3 7 > I t i s noted that a, and a are the optimum values of a, and ct_ when l c Nc 1 2 2 2 p = 0, and the r e s u l t i n g minimum value of /a i s given i n the square brackets i n (4.37) When p ^ 0, the allo w a b l e values f o r cx^ and cx^ are r e s t r i c t e d w i t h i n the square shown i n S e c t i o n 4.5.1. In t h i s case the optimum values of ex^ and cx^ are no longer e l l i p t i c a l , as shown i n F i g s . 30 and 31. For cb= 10 dB, the optimum v a l u e s , a-j_ 0p t and cijj0pt» °f and cx^ l i e almost on the s t a b i l i t y boundary. When <j> i s reduced from 10 to 6 dB, ( aj_ 0p t> aNopt^ s n i ^ t s away from the boundary, as shown more c l e a r l y i n F i g . 32, where (ex, t,a„ .) i s l a b e l l e d by "x" f o r various values of <j>. An asym-l o p t Nopt J p t o t i c value i s approached f o r both a, ^ and OL, . when cf> i s f u r t h e r r e -v * v l o p t Nopt duced. Choosing ex.. and ex,, near these asymptotes i n s t e a d of OL_ and CL, & 1 N J l c Nc - 1 0 I FEEDBACK C0EFFJCJEN7 oi; (a) F i e . 30. SNR vs. a and a f o r line-and-sample feedback DPCM f o r the & o 1 N the crowd scene. (a) cb=10dB, (b) cp=6dB. -1 0 1 FEEDBACK COEFFICIENT Uj (a) F i g . 31. S N R q vs. a and o.^ f o r line-and-sample feedback DPCM f o r the 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 of S N R q to v a r i a t i o n s i n cb without s i g n i f i c a n t l y degrading the system performance. Also shown i n F i g . 32 are the l o c i f o r which S N R of D P C M w i t h o line-and-sample feedback i s greater than that of PCM. The values of and O L ^ must always l i e w i t h i n the region bounded by these curves. When <j> i s l a r g e , the lower l e f t - h a n d p a r t of the curve c o i n c i d e s w i t h + = 0 The reason f o r t h i s i s the same as that e x p l a i n e d i n S e c t i o n 4.4.1. The area bounded by these curves decreases when cb i s decreased. The curves i n F i g . 33 show the values of and that give the same SNR as that o b t a i n a b l e when N = 1. The area bounded by these o J curves i s s i g n i f i c a n t l y l a r g e r than the e q u i v a l e n t area f o r two-previous-sample-feedback system shown i n F i g . 27. In f a c t , the improvement i n the maximum value of SNR over that o b tainable when N = 1 i s al s o much o TABLE IV Improvement of S N R q f o r line-and-sample feedback over p r e v i o u s - sample feedback * CO 10 dB 8 dB 6 dB 4 dB 2 dB 0 dB p 0 3.9xl0~ 6 1 . 9 x l 0 ~ 4 2 . 4 x l 0 ~ 3 1 . 3 x l 0 ~ 2 3 . 8 x l 0 ~ 2 7 . 9 x l 0 ~ 2 Crowd scene 2.54 2.57 3.19 3.58 3.64 3.65 3.67 Cameraman scene 2.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 f o r N=l i s optimized; K=4. l a r g e r , as i s shown i n Table IV. This improvement i n c r e a s e s as p i n c r e a s e s , which suggests that line-and-sample-feedback system i s e s p e c i a l l y d e s i r a b l e when the channel 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 Let A' n , A and A 1 be the 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 -pect to p 7 n , p n , and p.. r e s p e c t i v e l y , as defined i n (4.5). Then, 9 2 l .O-i 0.5-a <_> CJ or 03 a £ 0 -0.5 -0.5 0=1OdB 0 0.5 FFEOBRCK COEFFICIENT oC (b) 1 1.0 F i g . 3 2 . Locus of S N R q which i s equal to that of P C M . and a that maximize S N R are denoted by "x' N o scene, (b) the cameraman scene. The values of a^ (a) the crowd 9 3 F i g . 33. Locus of S N R q which i s equal to that obtainable from p r e v i o u s -sample feedback DPCM. (a) the crowd scene, (b) the cameraman scene. A x 0 = 2 | ct11 /A (4.38a) $ 2/A (4.38b) m A Q j l = 2 | a N | / A (4.39a) £ 2/A (4.39b) m A l , l = 2 l a i A N ' / A (4.40a) * 2/A (4.40b) m 2 2 where A = O g /a , which i s given i n (4.16), and Am = 1 " ( p l , 0 2 + p 0 , l 2 " 2 p l , 0 p 0 , l p l , l ) / ( 1 - p l , l 2 ) ( 4 ' 4 1 ) I t can be seen from (4.38) - (4.40) that i n order to reduce A l 0' A 0 1 a n ^ A l 1' A m u s t D e a s l a r g e as p o s s i b l e w h i l e |a^| and |a^| must be as sm a l l as p o s s i b l e . On the other hand, ct^ and ot^ should be so chosen as not to degrade the system performance. Consider, f o r example, the crowd scene, i n which case Pj_ Q = 0.9569, P Q ^ = 0.9650 and p.. .. = 0.9391. I f we choose a, = a, = 0.4291 and a„ = O L t = 0.5621, 1,1 1 l c N then A± Q = 18.24, A Q 1 = 23.90 and A x ± = 10.25; whereas i f a± = 0.3725 and a„ =0.5, then A . = 12.27, A . = 1648 and A. . =6.14. Note that N 1,0 0,1 1,1 when = 0.3725 and ct^ = 0.5, S N R q i s c l o s e to i t s optimum value when p -> 1/2 and i s only s l i g h t l y l e s s than i t s optimum value when p = 0. For the cameraman scene, P-, n = 0.9809, p =0.9885 and p , = X , U 0,-L 1 j X 0.9833. The choice = a l c = 0.2690 and ct^ = « N c = 0.7240 gives &1 Q = 26.28, A~ n = 70.74 and A , , = 19.02. However, i f a, = 0.3725 and CL T = 0,1 1,1 1 N 0.5, then A = 20.83, A = 26.96, and A . =10.41. Thus, the choice X j U U ) X X $ X = 0.3725 and = 0.5 appears to be a good one f o r both images. This choice i s a l s o s u i t a b l e f o r d i g i t a l r e a l i z a t i o n . V. SCHEMES FOR COMBATING CHANNEL NOISE 5.1 I n t r o d u c t i o n We have seen i n the previous a n a l y s i s t h a t t r a n s m i s s i o n e r r o r s i n DPCM system can be more ser i o u s than i n PCM system i f the DPCM feed-back c o e f f i c i e n t s {a } are not c a r e f u l l y chosen. This i s p a r t i c u l a r l y true i f {OL} l i e near the s t a b i l i t y boundary. In p r a c t i c a l a p p l i c a t i o n s , DPCM system i s u s u a l l y designed such that S N R q i s maximized when the tra n s m i s s i o n channel i s n o i s e l e s s , i n which case the feedback c o e f f i c i -ents are, u n f o r t u n a t e l y , very close to the s t a b i l i t y boundary, as has been shown i n Chapter IV. Although the mean-square channel e r r o r f o r DPCM can be l e s s than that f o r PCM i n absolute value i f {OL} are c a r e f u l l y s e l e c t e d , chan-n e l noise i n DPCM i n e f f e c t s t i l l c o n t r i b u t e s more to the o v e r a l l mean-square e r r o r than channel noise i n PCM. From (2,12), i t can be seen that the mean-square q u a n t i z a t i o n e r r o r of DPCM i s reduced from i t s equiva-2 2 l e n t PCM value by the f a c t o r a la , whereas f o r the mean-square channel e x 2 2 e r r o r , the f a c t o r i s Q° e/° > where Q i s normally much grea t e r than 1. S u b j e c t i v e l y , channel n o i s e i n DPCM als o appears to be l e s s d e s i r a b l e , even i f i t gives the same mean-square channel e r r o r as that of PCM. One of the reasons f o r t h i s i s that any tra n s m i s s i o n e r r o r i n DPCM w i l l a f f e c t many samples. For example, i n the tr a n s m i s s i o n of video s i g n a l s w i t h previous-sample feedback DPCM, an e r r o r i n t r a n s m i s s i o n w i l l produce a long h o r i z o n t a l streak s t a r t i n g at the po i n t where the e r r o r occurs. This k i n d of disturbance i s found to 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. In view of 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 to i n c o r p o r a t e an e f f e c t i v e scheme to cope w i t h channel n o i s e . In t h i s chapter, v a r i o u s techniques which can be used f o r combating channel n o i s e are discussed. Since the mean-square channel e r r o r of 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 , the e f f e c t of channel e r r o r s can be a l l e v i a t e d by reducing e i t h e r or both of these two f a c t o r s . Channel encoding, which i s a technique used f o r reducing e , i s s t u d i e d i n S e c t i o n 5.2. Sections 5.3-5.5 discus s v a r i o u s techniques f o r reducing Q. Some simple and e f f e c t i v e schemes are s u b j e c t i v e l y evaluated i n Se c t i o n 5.6. 5.2 Channel Encoding For a given q u a n t i z e r c o n f i g u r a t i o n , the mean-square e r r o r e^ can be reduced by channel encoding. Instead of usin g the n a t u r a l - b i n a r y code as described i n Se c t i o n 4.1, f o r example, we can use e i t h e r other non-redundant coding schemes, such as Gray code and fo l d e d b i n a r y code, or e r r o r - c o r r e c t i n g codes, i n which case an e x t r a number o f b i n a r y d i g i t s i s added to the n a t u r a l - b i n a r y coded q u a n t i z e r output to check and co r r e c t t r a n s m i s s i o n e r r o r s . For non-redundant b i n a r y codes, Yan and Donaldson have sub-j e c t i v e l y compared the e f f e c t s of usin 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 ] . A r g u e l l o et a l . , on the other hand, have proposed a coding scheme which 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 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 [ 1 3 ] . Assuming that the input to the qu a n t i z e r i s uniforml y d i s t r i b u t e d , Huang [41] has compared the mean-square e r r o r of the r e f l e c t e d - b i n a r y Gray code w i t h that of the n a t u r a l - b i n a r y code. He a l s o shows that f o r a t h r e e - b i t word, the n a t u r a l - b i n a r y code i s optimum i n the sense that i t y i e l d s the minimum mean-square e r r o r . Although non-redundant codes are simple and easy to 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 the r e s u l t that the improvement, i f any, i n performance of one scheme over the 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 codes, numerous schemes have been proposed i n the past. However, t h e i r e f f e c t on the performance of communication systems, p a r t i c u l a r l y DPCM, had r e c e i v e d l i t t l e a t t e n t i o n . In the f o l l o w -i n g , the e f f e c t of using c e r t a i n simple e r r o r - c o r r e c t i n g codes, such as Hamming code, i n DPCM i s s t u d i e d . In Se c t i o n 5.2.1, the p r o b a b i l i t y den-^ s i t y f u n c t i o n of the input to the qu a n t i z e r i s assumed to be uniform, i n which 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 . The a n a l y s i s i s extended to non-uniform d i s t r i b u t i o n s i n Se c t i o n 5.2.2. 5.2.1 Uniform P r o b a b i l i t y Density Function When the p r o b a b i l i t y d e n s i t y f u n c t i o n P e ( a ) of the input to the quan t i z e r i s uniform, the optimum q u a n t i z e r i s a l s o uniform [30]. In t h i s case, i t can be shown [21,30] that E = 4~ K (5.1) q and E M = 0 (5.2) where K i s the number of q u a n t i z a t i o n b i t s . The e r r o r E ^ depends on the encoding scheme. For group codes, i t has the f o l l o w i n g simple form K e n = 12 Z 4" 1 p ( i ) (5.3) i = l where p ( i ) i s the p r o b a b i l i t y that i t h b i t i s i n e r r o r a f t e r decoding. Furthermore, i f a code i s c y c l i c , p ( i ) i s independent of i and (5.3) can 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 K ) p (5.4) n r c where p^ represents the b i t - e r r o r p r o b a b i l i t y w i t h channel encoding. Let N be the codeword l e n g t h , p be the channel b i t - e r r o r p r o b a b i l i t y , and q=l-p. Then p can be c a l c u l a t e d from W., the number of codewords w i t h Hamming weight j , and Q ( j | 0 ) , the p r o b a b i l i t y that 0 i s tr a n s m i t t e d and a K-tuple word corresponding to an N-tuple codeword w i t h weight j i s decoded, from the f o l l o w i n g equation [42]. N . P c = E JtfW Q(j|0)' + V p j q N ' j ] (5.5) j=0 J J -where V_. i s the c o e f f i c i e n t of 7? i n the polynomial V(z) , where V(. ) - ( l + Z ) N - q - N I j 0 V ( j | 0 ) W « C 5 - 6 ' For an m - e r r o r - c o r r e c t i n g code, the decoder i s capable of decoding the rec e i v e d N-tuple i f i t i s w i t h i n a Hamming distance m of some codeword, i n which case the p r o b a b i l i t y Q(j|0) i s Q(j|0) - q N ? I Crhd) ( P / q ) J + 1 - 2 k (5.7) i = o k=o 1 _ f c k I f any other N-tuple i s r e c e i v e d , a decoding f a i l u r e occurs, i n which case the K in f o r m a t i o n d i g i t s are d i r e c t l y used. The second term i n the square brackets i n (5.5) represents the e r r o r due to t h i s decoding f a i l u r e . Consider now the s i n g l e - e r r o r c o r r e c t i n g Hamming code. Since there i s no decoding f a i l u r e i n t h i s case, and s i n c e m=l, we have N P r = I Q(j|0) (5.8a) j=0 N J where Q(j|0) = q N ( p / q ) 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 define N W(z) = E W.zJ (5.9) j=0 3 W(z) i s a l s o c a l l e d the weight enumerator of the codeword. By d i f f e r e n -t i a t i o n , i t can be shown that N 1 E jW.z J = zW (z) (5.10a) j=0 3 N . E j W.zJ = z W"(z) - zW'(z) (5.10b) j=0 3 S u b s t i t u t i n g (5.8b) i n t o (5.8a) and making use of (5.10), we have N p = ^ {[1 + z + ( N - l ) z ] W'(z) + z(l-'z ) W " ( z ) } , (5.11) *c N L z=p/q The weight enumerator f o r the Hamming code i s [43] N-1 N+1 W(z) = — ^ - [ ( l + z ) N + N(l+z) 2 (1-z) 2 ] (5.12) The s u b s t i t u t i o n of (5.12) i n t o (5.11) y i e l d s N-3 N-1 N — —L f d + N ^ d + ^ N " 1 _ (l+2Nz+z 2) (1+z) 2 (1-z) 2 ] z = p / q (5.13) c N+1 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) gives the mean-square e r r o r of 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. Consider, f o r example, the case N=7, i n which case there are three 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 o b t a i n p = q 5p 2[z 5+7z 4+12z 3+16z 2+19z+9] , (5.14) • c z=p/q 100 F i g . 34 shows the e f f e c t of 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 the t r a n s m i t t e r power i s constant (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 constant ( b ) . The DPCM system i s assumed to have one-previous-sample feedback w i t h cx^ = p^=0.9569 and the tr a n s m i s s i o n channel i s assumed to be white Gaussian as described i n Secti o n 4.1. Curves f o r other values of and are very s i m i l a r and th e r e f o r e not presented. In F i g . 34(a), where the t r a n s -m i t t e r power i s hel d constant i n both cases, Hamming code i s seen to perform b e t t e r only when P/4f N > 6dB, w i t h a maximum inprovement i n s o - ' S N R of approximately 1.5dB at 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 ion SNR i s l i m i t e d by the quan-s o - o t i z a t i o n e r r o r . At low t r a n s m i t t e r power, Hamming code gives lower S N R Q , because i n t h i s r e g ion there are many words which 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, furthermore, these e r r o r s are more l i k e l y to occur due to i t s higher channel 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 the same channel b i t - e r r o r p r o b a b i l i t y , then the former performs much b e t t e r than the l a t t e r , as shown i n F i g . 34(b). The maximum improvement i n S N R q f o r Hamming code exceeds 12dB at <t=6dB. 5.2.2 Non-Uniform P r o b a b i l i t y Density Function When the p r o b a b i l i t y d e n s i t y f u n c t i o n P e(oO and the q u a n t i z e r are not uniform, closed-form expressions f o r e , e and e as those i n q m n the previous s e c t i o n are very d i f f i c u l t to d e r i v e . However, i f we can c a l c u l a t e P.., the p r o b a b i l i t y that 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 a n be computed f r o m (2.16) - (2.18) n u m e r i c a l l y without q m n any d i f f i c u l t y . in rvj' o rvj in-HAMMING —if CODE " tn co" NON-REDUNDANT / NATURAL-BINARY / CODE ->—I—'—1—'—1—1—r --10 -8 -6 -4 -2 1 ' r 4 6 - 1 — ' — l — ' — I 8 10 12 RELATIVE TRANSMITTER POWER P/4fsNQ, dB (a) tn CQ to i n -ir>. (7,4) HAMMING 1 CODE ' / / 1 1 1 I 1 1 A NON-REDUNDANT ' 1 NATURAL-BINARY CODE 1 1 1 -10 -8 -6 — , , — , r -4 -2 0 n 1 — r 4 "6 - 1 — ' — 1 — • — 1 8 10 12 0, dB (b) F i g . 34. SNRo f o r previous-sample feedback DPCM using Hamming code and non-redundant n a t u r a l b i n a r y code. The channel i s white Gaussian; P e ( a ) i s uniform; a^=p^=o.9569; K=4. (a) f i x e d t r a n s m i t t e r power, (b) f i x e d b i t - e r r o r p r o b a b i l i t y . o Assume again that the quantizer output levels are f i r s t natural-binary coded, i.e., i f v., 1 < i < 2 , is the quantizer out-put level, then i t is denoted by the binary representation of (i-1), and then further encoded with a group code of length N. Let b_^ be the K-bit binary representation of (i-1). 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 1 K i 1 < j < 2 , there'exists an integer p , 1 < ^ < 2 , such that ^ 0 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 is only necessary to calculate P(b^|0_), which is a function of the Hamming weight of the codeword corresponding to b,. Let k denote the weight of this codeword. Then we have P-H = P (> JO) = Q(k|0) (5.15) where 0(k|0) is given in (5.7) and, in the case of Hamming code, in (5.8b) The weight k can be obtained by directly coding the K-tuple b_^ i f the coding scheme i s known. In Figs. 35 and 36, S N R q is plotted as a function of the relative transmitter power, P/4f G N O , and <j> for previous-sample feedback DPCM with Laplacian and Gaussian distributions, respectively. The quan-tizer is assumed to be logarithmic with u=100 and overload level V=10ae in both cases and the feedback coefficient ct^=p^=0.89 for Laplacian and 0.9569 for Gaussian. The performance of a (7,4) Hamming code is compared with that of the non-redundant natural binary code in each case. The encoder for Hamming code is a three-stage feedback shift register © denotes the component-by-component exclusive or of the two binary sequences. C O IO. i (7,4) HAMMING CODE • NON-REDUNDANT 'r NATURAL-BINARY 7 CODE T T 1 1 ' 1—' 1 ' 1 ' 1 ' ! -10 -8 -6 -4 -2 0 2 4 6 RELATIVE TRANSMITTER POWER P/4f.N0, dB ~r 8 10 - 1 12 (a) C M - 1 Q . CM 03 I -10 (7,4) HAMMING , CODE -j NON-REDUNDANT NATURAL-BINARY CODE i -4 I -2 2 ~T~ 8 I—1—I 10 12 0,dB (b) F i g . 35. SNR f o r previous-sample feedback DPCM using Hamming code and non-redundant n a t u r a l - b i n a r y code. The channel i s white Gaussian; P (a) i s L a p l a c i a n ; a ^ p =0.89; K=4. (a) t r a n s m i t t e r power f i x e d , (b) b i t - e r r o r p r o b a b i l i t y f i x e d . 7~ 1 i 1 i 1 i 1 i 1 i 1 i 1 i 1 i 1 i 1 i 1 i T ' ' 1 1 ' 1 1 1 i ' — i — 1 — i — ' — i — 1 — i — ' — i — 1 — i — 1 — i -10 -8 --S -4 -2 0 2 4 6 8 10 12 -10 -8 -6 -4 -2 0 2 A 6 8 30 12 RELATIVE TRANSMITTER POWER P/U5NQ, dB 0/ dB fa) fb) F i g . 36. S N R Q f ° r previous-sample feedback DPCM using Hamming code and non-redundant n a t u r a l b i n a r y code. The channel i s white Gaussian; P e ( a ) i s Gaussian; a^=p^=0.9569; K=4. (a) t r a n s m i t t e r power f i x e d , (b) b i t - e r r o r p r o b a b i l i t y f i x e d . M I plemented from the p r i m i t i v e b i n a r y polynomial g(x) = x + x + 1, as shown i n F i g . 37. To encode, the f l i p - f l o p s f , f ^ , and f^ are set to c4c3c2c, -0 '3 +x +x~ F i g . 37 Encoder f o r the 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 four i n f o r m a t i o n d i g i t s c^ ., c^, c^, and c^, each of which being e i t h e r 0 or 1, are then s e q u e n t i a l l y fed i n t o the encoder. A f t e r t h i s i s completed, the three f l i p - f l o p s c o n t a i n the three d e s i r e d check d i g i t s . The general behaviour of the curves i n F i g s . 35 and 36 i s very s i m i l a r to that of the curves 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 constant ( F i g s . 35(a) and 3 6 ( a ) ) , the Hamming code i s seen to y i e l d h igher SNR than the non-redundant n a t u r a l code i f P/4f N > 5dB f o r both o s o -L a p l a c i a n and Gaussian d i s t r i b u t i o n s . This range i s s l i g h t l y wider than that f o r uniform d i s t r i b u t i o n . I f the channel b i t - e r r o r p r o b a b i l i t y i s the same f o r both codes ( F i g s . 35(b) and 3 6 ( b ) ) , then the Hamming code almost always performs b e t t e r . To construct the encoder f o r (7,4) Hamming code, we can a l s o 3 2 use another p r i m i t i v e b i n a r y polynomial, i . e . , g(x) = x + x + 1 . I t i s found that t h i s encoder gives almost i d e n t i c a l r e s u l t as the one shown The p r i n c i p l e of t h i s encoder can be found i n Chapter IV of Reference [44], i n F i g . 37. 5.3 P e r i o d i c R e s e t t i n g To reduce the f a c t o r Q, we can e i t h e r redesign the feedback parameters {OL} i n such a way that 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 normalized p r e d i c t i o n e r r o r ° e/° y. does not deviate too f a r away from i t s minimum va l u e , or 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 output to zero so that any channel e r r o r does not propagate longer than the length of a p e r i o d . The design of feedback parameters has been discussed i n d e t a i l i n Chapter IV. In t h i s s e c t i o n , the technique of using p e r i o d i c r e s e t -t i n g to 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 input sequence {x_^} i s d i v i d e d i n t o blocks w i t h M samples i n each b l o c k , where M i s the number of samples i n each p e r i o d of r e s e t t i n g . In the case of r a s t e r scanned vide o , each scanning l i n e can be considered as a block i f r e s e t t i n g occurs at the beginning of each l i n e . Let x^, 0 < i < M - l , denote the i f ck sample i n each b l o c k and x^ denote the output of the system c o r r e s -ponding to t h i s sample. Then the normalized mean-square e r r o r e can be defined as the s t a t i s t i c a l e x p e c t a t i o n of the average of the squared d i f f e r e n c e i n each b l o c k , normalized w i t h respect to the s i g n a l power 2 . a , i . e . , x M-l E = E{ i E (x. - x . ) 2 } / a 2 (5.16) i=0 Using 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.) (5,17) X X 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 the ^x x l 1 x x x e r r o r due to 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 previous channel 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 . Since N N z. = E a.y. . and z. = E ct.x. . we have . N z . - z . = E a . (x. .-y. .) i i j = 1 3 i - J i - J N „ = E o . [ ( r . .+z. .) - (s. .+z. . ) ] N N A = E a.n. + E ( z , .-z, .) (5.18) • T J 1 ~ J . 1 1-J 1-1 J = l j - l Note that (5.18) i s a r e c u r s i v e equation. Replacing the s u b s c r i p t i i n (5.18) w i t h i - j , we o b t a i n N N z. . - z. . = E a. n. . . + E a. ( z . . . - z . . . ) (5.19) i - J ^ j 2 = l J 2 ^ - 3 2 j 2 - l 3 2 The s u b s t i t u t i o n of (5.19) i n t o (5.18) y i e l d s N N N z. - z. = E a..n. + E E a. a. n. . 1 1 j ^ i h ^ i j ^ i j 2 - i J i J 2 N N + E E a. a ( z . _ . . - z . . _. ) (5.20) 1=1 j =1 3 1 3 2 1 21~32 X~31 J2 J l J 2 Where, f o r co n s i s t e n c y , i s used to denote j i n (5.18) and (5.19). Repeating the above procedure f o r i times, we o b t a i n the f o l l o w i n g equation. N N N N z.-z. - E a. n. . + E E a. a, n. . . + E ... E a, ...a, n. . 1 1 j ] L - i H x~h j ^ u y i h h x~h~h j ± - i h h ^ r -N N + E E a. ...a. (z. . _. - z . . . ) (5.21) j =1 j =1 J l J i 1 _ J 1 J i X~21 "'3± Since i n i t i a l l y the p r e d i c t o r outputs z^ and z^ are set to zero, i . e . , z k = z k = 0 f o r k < 0 (5.22) and si n c e < 0, the l a s t term i n (5.21) vanishes. A f t e r ex-panding the summation and regrouping the l i k e terms, we can express the d i f f e r e n c e z ^ - z ^ i n (5.21) as a weighted sum of the i previous channel e r r o r s as f o l l o w s . z.-z. = E f n. (5.23) i l i m l-m m=l where f l = K l f2 = a 2 + a l f 3 = a 3 + 2 a 2 a 1 + a 3 2 2 2 f. = a. + 2a„a. + a 0 + 3a„a1 + a. 4 4 3 1 2 2 1 1 (k N+. . . 4 - k ^ ) ! k ^ k ^ and f = E • O L . ...a„ a. (5.24a) m A k N!...k,'k,' N 2 1 2 * 1 ' where k^, k 2 , ..., k^ are 0 or p o s i t i v e i n t e g e r s and the summation i s over a l l the values of k^, k ^ j ..., k^ which are i n the set A = { k 1 5 k 2 , . . . ,k N: N ^ . . .+2k2+k1=m} (5.24b) Define ^=1. Then the s u b s t i t u t i o n of (5.23) i n t o (5.17) y i e l d s i x.-x. = q. + E f n. (5.25) i l l ~ m l-m m=0 I t i s noted that (5.25) and (2.7) are very s i m i l a r . The weighting coef-f i c i e n t f , i n f a c t , i s the d i g i t a l impulse response of the decoder. Subs-m t i t u t i n g (5.25) i n t o (5.23), we have M-l i i e = - j E ( E [ q 2 ] + 2 E f E[q.n. ] + E[( E f n. ) 2 ] } / a 2 (5.26) M. n ^ i « m x l-m „ m l-m x x=0 m=0 m=0 The f i r s t term i n the braces i n (5.26) represents the e r r o r due to quan-t i z a t i o n , the l a s t term i s the errory'resulting from channel n o i s e , and the second term i s the e r r o r due to i n t e r a c t i o n between the q u a n t i z a t i o n and channel n o i s e . Assume, as i n Sectio n 2.-1, that the d i g i t a l channel i s memoryless and the d i f f e r e n c e samples e^ are s t a t i s t i c a l l y independent. Then Efq.n. ] = 0 f o r m + 0 and E[n. .n. , ] =0 f o r j ^ k. Furthermore, L ^ i x-mJ 1-3 i - k J J 2 2 2 assume that the expected values E [ e ^ ] , E[q ], Efq^n^] and E[n^] are inde -pendent of i . This l a t t e r assumption i s not unreasonable when i i s not 2 2 2 2 too s m a l l ( t y p i c a l l y i > N). Let a = E [ e . ] , e = E[q.]/a , £ = E[q.n.]/a x • / r J e l q l e m l l 2 2 and e^ = E[n^]/a^. Then, under the above assumptions (5,26) can be expressed i n the same form as (2.12a), namely, e = (e + e + Qe ) o2/a2 (5.27a) q m n e x where M-l i Q = ^ E ( E f ) (5.27b) M . n _ n m 1=0 m=0 Therefore, using (5.27) i n conjunction w i t h the expressions f o r e^, e^, £ n, 2 2 and a lo d e r i v e d i n Se c t i o n 2.3, we can c a l c u l a t e SNR of DPCM system e x o w i t h p e r i o d i c r e s e t t i n g . Consider now the previous-sample-feedback DPCM. S e t t i n g N i n (5.24) to 1, we have f = a™ (5.28) m 1 I t f o l l o w s from (5.27b) and (5.28) that i M-l 1 Q - £ * < = ) 1=0 m=0 2 2 M .. . 1 a (1-a ) l - a ^ 1-a^ 2 When there i s no p e r i o d i c r e s e t t i n g , M ->• 0 0 and Q = 1/ (1-cx^) , which i s the same as that obtained from (2.26), as would be expected. F i g , 38 shows Q as a f u n c t i o n of the block s i z e M f o r - 0.89, 0.9569 and 0.9809. The f a c t that Q can be reduced by p e r i o d i c r e s e t t i n g i s c l e a r l y seen i n t h i s f i g u r e . For a given b l o c k s i z e M, Q i s reduced most when i s l a r g e , as compared to the value of Q when no p e r i o d i c r e s e t t i n g i s used. For example, i f = 0.89, Q i s reduced from i t s maxi-mum value of 4.81 f o r no p e r i o d i c r e s e t t i n g to 4.52 at M=64, which means a r e d u c t i o n of only 5.95%. However, i f = 0.9569, Q i s reduced from 11.86 f o r M + » to 9.85 at M=64, a r e d u c t i o n of 16.9%, and i f a = 0.9809, Q i s reduced from 26.43 f o r M 0 0 by 36.4% to 16.82 at M=64. For video s i g n a l s , the p r e d i c t o r outputs and z^ are normally r e s e t to zero at the beginning of each l i n e . For an image w i t h 512 samples per l i n e , t h i s means a bl o c k s i z e of 512. The value of Q i n t h i s case i s almost the same as that f o r M-*-.00, as i s shown i n F i g . 38. Therefore i n order to have a sma l l e r value of Q, the p r e d i c t o r output must be r e s e t more o f t e n than once per l i n e . Although Fig.38 suggests that 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 value of Q, i t should a l s o be remembered that when r e s e t -t i n g i s too o f t e n , the system w i l l be complicated. Furthermore, i f M i s F i g . 38. The f a c t o r given i n (5.29) vs. the block s i z e M f o r DPCM w i t h p e r i o d i c r e s e t t i n g . 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 very i n a c c u r a t e . In f a c t , the very advan-tage of using p r e d i c t i o n i n DPCM may completely disappear 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 . F i g . 39 shows the c a l c u l a t e d and measured values of S N R as a & o f u n c t i o n of the block s i z e M f o r the crowd (a) and the cameraman (b) 2 2 scenes. In c a l c u l a t i o n , the normalized p r e d i c t i o n e r r o r a /a i s assumed e x to be constant, independent of M. Thus, when the block s i z e M decreases, the c a l c u l a t e d values of S N R q always i n s c r e a s e due to the m o n o t o n i c a l l y -2 2 decreasing nature of Q shown above. In f a c t , when M decreases, a /a w i l l i n crease and thus SNR w i l l descrease. This f a c t can be seen from the o experimentally measured values of S N R q , as shown i n symbols i n F i g . 39. A maximum i s seen to e x i s t between M = 16 and 64 i n each case. The maxi-mum values are approximately 1.5dB higher than those f o r M = 512 f o r the cameraman scene and ldB higher f o r the crowd scene. A l s o , the improve-ment due to f a s t e r r e s e t t i n g i s more evident when p i s l a r g e . 5.4 Pseudo-Random R e s e t t i n g Although p e r i o d i c r e s e t t i n g i s simple and easy to implement, i t al s o has a undesirable e f f e c t . Since the i n i t i a l samples of each block are not p r e d i c t e d or incompletely p r e d i c t e d , and s i n c e the q u a n t i z e r i s u s u a l l y designed f o r the p r e d i c t i o n e r r o r samples e_^ , the q u a n t i z a t i o n e r r o r f o r the i n i t i a l samples of each block i s very l a r g e . This e r r o r i s a r e s u l t of amplitude overload. 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 , the 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 video s i g n a l s and the e r r o r s can be e a s i l y detected. In order to prevent the i n i t i a l samples w i t h l a r g e overload 0 = 8dB 0=6dB 16 — i 1 1 32 6 4 128 BLOCK SIZE M (a) 256 512 CQ ~C3 o in. 0= 8dB 0 = 6dB 16 32 6 4 128 £ L O C / < SIZE M (b) 256 512 F i g . 39, SNRo of previous-sample feedback DPCM wi t h p e r i o d i c r e s e t t i n g v s . the bl o c k s i z e M; K=4, N=l. (a) the crowd scene, (b) the cameraman scene. Symbols (A,x) denote the 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 appearing 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 r e s e t pseudo-randomly i n s t e a d of p e r i o d i c a l l y . For i n s t a n c e , i f i t i s d e s i r e d to r e s e t the p r e d i c t o r approximately once every M samples, we can use a pseudo-random number generator to accomplish 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, which i s uni f o r m l y d i s t r i b u t e d between 0 and 1, i s generated and compared w i t h 1/M. I f the number i s l e s s than 1/M, then the p r e d i c t o r i s r e s e t ; otherwise, the p r e d i c t i o n continues. This technique w i l l 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 , - S u b j e c t i v e e f f e c t of pseudo-random r e s e t t i n g i s evaluated i n S e c t i o n 5.6. 5.5 Other Techniques f o r Combating Channel Noise Since the l a r g e e r r o r of 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 overloads a d i r e c t s o l u t i o n f o r the problem pointed out i n S e c t i o n 5.4 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 overload l e v e l f o r the i n i t i a l samples of each b l o c k . For example, f o r one-previous-sample feedback systems, we may use a 7-bit q u a n t i z e r f o r the f i r s t sample of each b l o c k . This technique i s a l s o known as PCM updating 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_. [13]. The 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 upda-t i n g . Assume that the i n i t i a l k samples of each b l o c k , where k < M, are t r a n s m i t t e d w i t h a PCM system. Then the normalized 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 i=k The f i r s t summation i n (5.30) denotes the e r r o r due to PCM t r a n s m i s s i o n 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 . Let e , e qp mp and e denote the normalized q u a n t i z a t i o n , mutual and channel e r r o r s , np r e s p e c t i v e l y , of the PCM p a r t of the system. Then, f o l l o w i n g a procedure s i m i l a r to that i n S e c t i o n 5.4, i t can be shown that e = (e + e +s ) + (e + e + Qe ) t ? 2 / a 2 (5.31a) qp mp cp q m n e x 2 2 where e , £ , e and a /cr are given i n S e c t i o n 2.3 and q m n e x 6 1 1 2 . \ ( > ( 5 " 3 1 b ) i=k m=0 As compared to p e r i o d i c r e s e t t i n g or pseudo-random r e s e t t i n g , PCM updating w i l l no doubt perform b e t t e r . However, the l a t t e r i s much more complicated, 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 of b i t s per sample i s a l s o l a r g e r due to the use of a more p r e c i s e q u a n t i z e r . Limb and Mounts [45] a l s o proposed a method f o r combating chan-n e l e r r o r s i n DPCM systems. They suggested the use of a pre-assigned number at the end of a block of samples at the t r a n s m i t t e r . A f t e r t r a n s -m i s s i o n , the decoder at the r e c e i v e r should recover to the same number. I f i t does not, then t r a n s m i s s i o n e r r o r s must have occurred, i n which case the block of samples i s replaced by an estimate of the b l o c k . The e s t i -mation can be based on the previous l i n e or the average of the next and previous l i n e s . This technique w i l l be s a t i s f a c t o r y when the channel i s not too n o i s y and the block s i z e M i s not too l a r g e . Of course, the complexity of the system w i l l be g r e a t l y increased i n order to 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 et a l . [46] have s t u d i e d a DPCM system which uses the average of the previous sample and the sample above and to the r i g h t of the sample being encoded as a p r e d i c t i o n and found that channel e r r o r s i n t h i s system are much l e s s v i s i b l e than those i n previous-sample feedback system. This system i n f a c t i s very s i m i l a r to the line-and-sample feed-back system discussed i n Secti o n 4.6. 5.6 Sub j e c t i v e E v a l u a t i o n The output s i g n a l - t o - n o i s e r a t i o of mean-square e r r o r i s a convenient and good measure of the performance of a communication system. I t i s mathematically t r a c t a b l e and thus can serve as a f i r s t step i n system a n a l y s i s or design. The disadvantage of t h i s measure i s that i t may not i n d i c a t e e x a c t l y the s u b j e c t i v e q u a l i t y of the 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 evaluate the e f f e c t i v e -ness of c e r t a i n simple error-combating schemes by using the video images shown i n F i g . 11 as input s i g n a l s . 5.6.1 P r e p a r a t i o n of Video Samples In order to process s i g n a l s of zero mean v a l u e , the average of a l l the 512x512 p i c t u r e elements, which are p o s i t i v e i n t e g e r s ranging- from 0 to 257, of each p i c t u r e was f i r s t c a l c u l a t e d and then subtracted from each of these p i c t u r e elements. A f t e r p r o c e ssing by s i m u l a t i o n , the re c e i v e d p i c t u r e elements were represented by 32- b i t r e a l numbers. (The word le n g t h of s i n g l e - p r e c i s i o n r e a l numbers of the IBM 360/67 computer i s 32 b i t s . ) For d i s p l a y , the mean value of the p i c t u r e processed was added back to each of these r e a l numbers and the r e s u l t was then l i m i t e d w i t h i n 0 and 257. F i n a l l y , the r e s u l t i n g r e a l number was rounded i n t o the nearest i n t e g e r and then represented again as an 8 - d i g i t b i n a r y number. The p i c t u r e elements obtained from t h i s procedure 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 screen by using 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 Celco. The d i s p l a y u n i t was c o n t r o l l e d w i t h a Supernova computer. P i c t u r e s were then taken from the screen w i t h P o l a r o i d 4x5 Land f i l m s , Type 55 P/N. To make sure that each f i l m was p r o p e r l y exposed, a 1 5 - l i n e 8-l e v e l gray s c a l e was appended to the bottom of each p i c t u r e . The b r i g h t -ness i n t e n s i t y of the d i s p l a y u n i t was so adjusted that i n each p i c t u r e the gray l e v e l s ran uniformly from the darkest at the l e f t - m o s t l e v e l to the b r i g h t e s t at the right-most l e v e l . For convenience i n comparison, 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 having 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 patterns were generated from a pseudo-random number g e r e r a t o r as described i n Section 4.3. The q u a n t i z e r was l o g a r i t h m i c w i t h K = 4, u = 100 and the normalized overload l e v e l V/a = 20dB. e 5.6.2 E f f e c t of 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 obtained from the p r e v i o u s -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 . Three values f o r the feedback c o e f f i c i e n t ct^ were considered i n each case, that i s , ct^ = p^, 0.9 and 0.8. In F i g . 40, where cb = 10 dB, the p i c t u r e s are almost as good as the o r i g i n a l s . Although there are f i v e erroneous b i t s i n each p i c t u r e , they are h a r d l y detectable except some i n (a) and (d) , where ct^ = p^. The degradation i n p i c t u r e q u a l i t y when cx^ = 0.9 and 0.8 as compared to ct^ = p^ 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 using smaller v a l u e of i s apparent, as shown i n F i g s . 41 and 42. When ct^ = p , the h o r i z o n t a l s t r e a k s , which s t a r t at the p o i n t s where channel e r r o r s occur, are long and c l e a r ; whereas when = 0.9, the l e n g t h of these st r e a k s i s g r e a t l y reduced, and i n the case pf = 0.8, the st r e a k s appear only as short and small dashes. These f i g u r e s confirm the co n c l u s i o n made i n the e a r l i e r ana-l y s i s that a d e s i r a b l e choice f o r i s near i t s optimum value f o r n o i s y channel when the system i s to operate i n both n o i s e l e s s and n o i s y e n v i r o n -ment. The value of SNR f o r each p i c t u r e i s a l s o shown i n these f i g u r e s . o By comparison, i t appears that S N R ^ i s a good measure of the s u b j e c t i v e q u a l i t y too. P i c t u r e s obtained from the line-and-sample 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 . Again, three sets of 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„T = 0.5; and a, = 0.3725, a„T = 0.5. The 1 l c N Nc 1 N 1 N set = = 0.5 was s e l e c t e d because i t i s very convenient 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 design. Although t h i s choice made and l i e on the s t a b i l i t y boundary, the system s t a b i l i t y was not a ser i o u s problem because the p r e d i c t o r was r e s e t at the beginning of each l i n e and the number of l i n e s was f i n i t e . The set ct^ = 0.3725 and ct^ - 0.5 was chosen because, as shown i n Se c t i o n 4.6.4, i t i s easy to implement d i g i t a l l y and the r e s u l t i n g S N R q i s high and a l s o f a i r l y i n s e n -s i t i v e to v a r i a t i o n s i n cb and p . .. 1,3 U n l i k e those i n the previous-sample feedback system, channel e r r o r s i n the line-and-sample feedback system show up as s t r e a k s w i t h wider and l i g h t e r t a i l i n the diagonal d i r e c t i o n . For a good channel, the three sets of and 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 the channel i s n o i s y , however, the choice = 0.3725 and = 0.5 i s most d e s i r a b l e , i n which case the e f f e c t of a channel e r r o r i s v i s i b l e only at the spot where the e r r o r occurs, as shown i n F i g s . 44 and 45. For a given value of <b, the line-and-sample feedback system w i t h = 0.3725 and ct^ = 0.5 a l s o appears to y i e l d b e t t e r p i c t u r e q u a l i t y than the previous-sample feedback system. 5.6.3 P e r i o d i c and Pseudo-Random R e s e t t i n g s F i g s . 46 and 47 show the p i c t u r e s obtained from the 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 -p e c t i v e l y . Three d i f f e r e n t b l o c k s i z e s are compared i n each case; i . e . , M = 512, 128 and 32. when M =512, the p r e d i c t o r was r e s e t only at the beginning of each l i n e . The stre a k s t h e r e f o r e are very long. When M i s reduced, the len g t h of the stre a k s i s a l s o reduced. 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 Se c t i o n 5.3. These v e r t i c a l l i n e s are 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 areas, where amplitude overload i s most severe. F i g s . 48 and 49 show the p i c t u r e s obtained from pseudo-random r e s e t t i n g . The p r e d i c t o r was r e s e t to zero approximately once every M samples, where M = 512, 128 or 32. No v e r t i c a l l i n e s as those i n F i g s . 46 and 47 can be seen i n these 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 the s i m i l a r improve-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, are s t i l l very long even when M = 32. These long s t r e a k s can be shortened by l i m i t i n g the bl o c k s i z e generated by the pseudo-random number generator to a value which i s s l i g h t l y higher than M. (a) a -p =0.9569 SNR =25.98dB 1 1 o (a) a =0.9 SNR =25.84dB 1 o m (c) 3 =0.8 SNR =24.74dB 1 o (d) a =p =o.9809 SNR =29.52dB 1 1 o (e) a =0.9 SNR =28.79dB 1 o (f) a =0.8 SNR =26.81dB 1 o Fig. 40. Pictures 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 SNR =26.00dB 1 o P (c) a =0.8 SJTR =22.79dB (f) a =0.8 SNR =24.75dB 1 o 1 o Fig. 41. Pictures obtained from a 4-bit previous-sample feedback DPCM with cb=8dB or p=1.9*10 . (c) a =0.8 SNR =15.76dB (f) a =0.8 SNR =17.46dB 1 o 1 o Fig. 42. Pictures obtained from a 4-bit previous-sample feedback DPCM with cb=6dB or p=2.4*10 . 123 F i g . 43. Pictures obtained from a,4-bit line-and-sample feedback DPCM with <{.=10dB or p=3.9*10 . 124 (c) cij-0.3725 0^=0.5 (f) 0^=0.3725 <*N=0.5 Fig 44. Pictures obtained from a 4-bit line-and-sample feedback DPCM with <j>=8dB or p-l.9x10"*. 125 (a) a -a. =0.4291 a =a X T =0.5621 1 l c N Nc (b) a -0.5 aN=0.5 r W PQ co Pi (c) 0^=0.3725 0^=0.5 (d) a -a, =0.2690 a -a =0.7240 "1 ~ l c N Nc A iiJL " i \ pq — Pi (e) a -0.5 a N = 0 - 5 L i ( f ) c^-0.3725 c^-0.5 F i g . 45. P i c t u r e s obtained from a 4-bit line-and-sample feedback DPCM with 4=6dB or p=2 .4x l0 - 3 . . 46. P i c t u r e s o b t a i n e d from a 4 - b i t previous-sample feedback 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 Fig. 47. Pictures obtained from a 4-bit previous-sample feedback DPCM with periodic resetting; 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 previous-sample feedback DPCM w i t h pseudo-random r e s e t t i n g ; a =p , cb=8dB. (a\ M=S1? CJMP =11 CtOAU 129 o (b) M=128 SNR =11.22dB o (d) M=512 SNR =11.18dB o _ - 1 (e) M=128 SNR =11.59dB o ( f ) M=32dB SNR =12.93dB o (c) M=32 SNR =11.78dB o F i g . 49. P i c t u r e s o b t a i n e d from a 4 - b i t previous-sample feedback DPCM w i t h pseudo-random r e s e t t i n g ; a^=o^, c£=6dB. V I . DPCM SYSTEMS WITH COARSE QUANTIZATION 6.1 I n t r o d u c t i o n In most of the previous a n a l y s i s , we have assumed that the q u a n t i z a t i o n noise q feeding i n t o the 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 , the r a t i o a /a can be s i m p l i f i e d as i n (2.29). R e s u l t s e x obtained by using t h i s equation can thus be used w i t h confidence only i f the number of q u a n t i z a t i o n l e v e l s L i s not too small ( t y p i c a l l y L z 8) . Because of t h e i r s i m p l i c i t y and low b i t r a t e , DPCM 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 . R e c e n t l y , Stroh and Boorstyn [47] have s t u d i e d the e f f e c t of q u a n t i z a t i o n n o i s e fedback through the p r e d i c t o r . However, t h e i r method of c a l c u l a t i n g the optimum p r e d i c t o r c o e f f i c i e n t s and the r e s u l t i n g S N R q i s tedious and d i f f i c u l t to apply i n p r a c t i c e . A l s o , they have assumed that the p r e d i c t o r operates on an i n f i n i t e number of previous samples; whereas i n p r a c t i c a l s i t u a t i o n s , only a few ( u s u a l l y one or at most two) previous samples are used. O'Neal [48] has a l s o s t u d i e d the e f f e c t of fedback q u a n t i z a t i o n n o i s e on the performance of DPCM systems e x c i t e d by f i r s t - o r d e r Markov processes. In t h i s chapter, we s h a l l d e r i v e simple equations f o r the c o e f f i c i e n t s of the optimum l i n e a r p r e d i c t o r and f o r the r e s u l t i n g SNR^, assuming that the q u a n t i z e r i s chosen to minimize the q u a n t i z a t i o n n o i s e . I t i s shown that when the q u a n t i z a t i o n n o i s e i s considered i n o p t i m i z i n g the p r e d i c t o r , improved p r e d i c t i o n occurs, w i t h the r e s u l t that f o r n o i s e -l e s s communication channels, SNR^ i s l a r g e r when the q u a n t i z a t i o n n o i s e i s used to optimize the p r e d i c t o r than when i t i s neglected. As i n the previous chapters, the p r o b a b i l i t y d e n s i t y f u n c t i o n P e(°0 i s assumed to be independent of {a.}, and x. and e. are assumed to have i d e n t i c a l d i s t r i b u t i o n f u n c t i o n . In p a r t i c u l a r , i t w i l l be assumed that x. and thus e. are Gaussian. 1 The system w i l l be optimized by assuming that the t r a n s m i s s i o n channel i s n o i s e l e s s . This 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-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 channel e r r o r s on the optimum system i s then discussed. Examples f o r one- and two-previous-sample feedback systems are f i n a l l y s t u d i e d i n S e c t i o n 6.5. 6.2 Optimum Quantizer Let u^, i = 1,**',L+1, and v.., j = l t ' , m , L , be the t r a n s i t i o n and output 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 that the values of u. and v. that minimize the mean-square q u a n t i z a t i o n e r r o r between the input and output of the q u a n t i z e r must s a t i s f y t h e . f o l l o w i n g system of equations [28]. ~ U 1 = "L+l = " u. = (v.+v. ,)/2 i = 2, ••• ,L (6.1a) l l i - i u. ,, / (v.-a) p (a) da = 0 i = 1, ••• , L (6.1b) u. l e l 2 The r e s u l t i n g minimum mean-square e r r o r , normalized w i t h respect to cr , i s 1 L U i + 1 e = 1 - ± r E f v.ap (a) da (6.2) q 2 . .. u. I *e ^ a i = l l e Since e^ i s e s s e n t i a l l y Gaussian 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 that the c o r r e l a -t i o n between the q u a n t i z e r output s_^ and any Gaussian s i g n a l w i s r e l a t e d to the c o r r e l a t i o n between the q u a n t i z e r input e. and w. as f o l l o w s [49]. 1 L Uk+1 Efs.w.l = E[e.w.l —x- E / av, p (a) da 1 i l i 2 , , u, k e J J a k=l k e = E[e.w.] ( 1 - E ) (6.3) 1 J q I t follows from (6.3) that E[q.w.l =E[s.w.] - E[e.w.] = -e E[e.w.] (6.4) i 3 1 3 q i 3 This r e l a t i o n w i l l be u s e f u l i n the sequel. 6.3 Optimum Predictor 2 Since y\ = x^ + q^, the mean-square prediction 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 ) (6.5) e x j - i ^ x y j = i k=i J y where R x y ( j ) = E t x . y . ^ ] (6.6a) and R (j) = E[y.y. .] (6.6b) y 1 1 - 3 By direct d i f ferent ia t ion , i t can be shown that the values of a^, ••• ,a^ 2 that minimize a& must satisfy the following system of equations. N R (n) = E a.R (j-n) n - 1 , ••• ,N (6.7) xy j = 1 3 y 2 The resulting minimum value of i s 2 2 N a = a - E a.R (j) (6.8) e x . = 1 j xy It i s noted that (6.7) also implies the orthogonality between e i and y , i . e . , R (n) = E[e.y. ] = 0 n = 1, ••• ,N (6.9) ey i J i - n the d i f f i c u l t y i n the c a l c u l a t i o n of a^, ••• , a^ d i r e c t l y from (6.7) i s that R (k) and R (k) , being dependent on R (k) and R (k) , are xy y o r xq q not known. I t w i l l be shown below that i f both the q u a n t i z e r and the 2 2 p r e d i c t o r are optimum, a,, ••• ,ot and a /a can be c a l c u l a t e d e a s i l y . I N e x We note here that R (n) = R (n) + R (n) and R (n) = R (n) + xy x xq y x R (n) + R (-n) + R (n). Therefore, i f IR ( n ) I « I R (n)I and IR ( n ) I « xq xq q ' 1 q 1 1 x 1 1 xq 1 | R x ( n ) | , then (6.7) and (6.8) reduce to equations obtained when fedback q u a n t i z a t i o n noise i s neg l e c t e d , as shown i n Section 2 . 5 . 6.4 Optimum Quantizer and P r e d i c t o r Assume now that both the qu a n t i z e r and the p r e d i c t o r are 2 2 optimum i n the sense that both e and a /a are minimized. Since f o r q e x L > 4 y. = x. + q. i s a l s o e s s e n t i a l l y Gaussian [47], we have, from (6.4) ^ i x n x and (6,9), R (n) = E[q.y. ] = -e E[e.y. ] = 0 n = 1, ••• ,N (6.10a) qy ' l ^ i - n q x-'x-n or R q x ^ = " R q ( n ) n = 1, ,N (6.10b) Since 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 In f a c t , (6.10a) and (6.10c) are a l s o true f o r n = 0, because R (0) = E[q.x.] = -e E[e.x.] qx n i i q i i N = -e E [ ( x . - Z a.y. .)x.] q i j = 1 J i-3 i = -e a 2 = - R (0) (6.10d) q e q I t f o l l o w s from (6.7) and (6.10) that 134 N R (n) = R (-n) = E a.R ( j - n ) n = 1, ••• ,N (6.11) xy xy' . = 1 J xy From (6.5) and (6.11), we have R ( n ) = -R (n) | n | = 1 , ••• ,N (6.12) X Q 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) f o r a l l n (6.13) xq q xe Since i s always l e s s than 1 when the q u a n t i z e r i s optimum [30], (6.12) and (6.13) can be s a t i s f i e d i f and only i f R (n) = R (n) = 0 In = 1, ••• ,N (6.14) xq xe 1 1 The s u b s t i t u t i o n of (6.14) i n t o (6.11) and (6.8) y i e l d s N cb(n) = E a.<Kj-n) n = 1, * * * ,N (6.15) 3=1 3 N n= 1 - E a.p(n) (6.16) 3=1 3 2 2 where n = a la and e x ' p(n) = R ( n ) / a 2 n - 1 , ••• ,N + (n) x x (6.17) 2 2 1 - a / a =* 1 • - ne n = 0 q x q I t i s noted that the above r e s u l t s are very s i m i l a r to those obtained w i t h fedback q u a n t i z a t i o n noise neglected as given i n Se c t i o n 2.5; the only d i f f e r e n c e i s th a t p(0) = 1 i n (2.41) i s now repl a c e d by co(0) = 1 - ne . S o l u t i o n s f o r a., ••• ,a„ and n i n the present case, however, q I N are more complicated, because a^ and n are 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 equations, we may s u b s t i t u t e (6.16) i n t o (6.15) and then solve the r e s u l t i n g N n o n l i n e a r equations, but the procedure i s very tedious and cumbersome. Instead, we consider the f o l l o w i n g method. Denoting CXQ = -1 as b e f o r e , we can combine (6.15) and (6.16) as f o l l o w s , N S a.cf>(j-n) j=0 3 - ( l - e q ) n n = 0 n = 1, (6.18) .N Consider (6.18) as a set of simultaneous l i n e a r equations w i t h (N+1) unknowns a^, a^ s and a^. S o l v i n g f o r a^, s e t t i n g an = -1 and rear-ranging y i e l d s H(n) = l - n P l ^ q M l 1-ne PN-1 PN-2 N JN-1 JN-2 1-ne = 0 (6.19) where = p ( i ) . Note that H(ri) i s a polynomial of degree N+1 and i t s c o e f f i c i e n t s are independent of a , ,a 1 T. I f e = 0 , then (6.19) l ' N q reduces to a f i r s t order equation. Although i n general (6.19) has N+1 r o o t s , there i s only one root which w i l l approach the root f o r = 0 when e i s decreased. This w i l l become evident 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^, ••• can be found from (6.18) without d i f f i c u l t y . The normalized p r e d i c t i o n e r r o r n can a l s o be expressed i n another form. Consider that tj>(i) i n (6.18) are unknown v a r i a b l e s . Then, s o l v i n g f o r <i(0) from (6.18), we have cb(0) = Q(l-e ) (6.20) where Q i s given i n (2.26). 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 f o r n y i e l d s 1 Q-(Q-l)e (6.21) I t i s i n t e r e s t i n g to note that i f Q > 1, which i s u s u a l l y the case, then n as given by (6.21) i s sm a l l e r than the value of n when e = 0 . In other q words, the fedback q u a n t i z a t i o n noise has the e f f e c t of reducing the p r e d i c t i o n e r r o r n. This improvement i n p r e d i c t i o n i s due to the f a c t that the q u a n t i z a t i o n noise q. a l s o contains some i n f o r m a t i o n about x.. I l I t f o l l o w s that the a c t u a l value of SNR as obtained from (2.12) and o (6.21) i s l a r g e r than when the fedback noise i s neglected when the t r a n s -mission channel i s not too n o i s y . Using (6.21) we can a l s o w r i t e the f a c t o r m u l t i p l y i n g the PCM channel e r r o r e as f o l l o w s . n i Q°e / gx = 1-(1-1/Q) £ q " 1 ( 6 - 2 2 ) Therefore, although the e f f e c t of channel noise on DPCM w i t h conventional optimum l i n e a r p r e d i c t o r i s the same as that on PCM when the fedback q u a n t i z a t i o n noise i s neglected (see Secti o n 2.5), t h i s i s no longer t r u e when the fedback q u a n t i z a t i o n noise i s taken i n t o account. Despite i t s advantage i n improving the p r e d i c t i o n , i t makes the 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 Considered i n the f o l l o w i n g are the one- and two-previous-sample feedback systems. 6.5.1 One-Previous-Sample Feedback When N = 1, we have, from (6.19), H ( n ) = e n 2 - (1+e ) n + ( 1 - P ? ) = 0 (6.23) q q 1 . The two roots of t h i s equation are 2 2 ' 1/2 n = {1 + e ± [(1-e ) + 4p^e ] }/2e (6.24) q q i q q To determine which of these two roots should be chosen, we make e approach q 0; l i m n = • e -+0 q f o r "+" s i g n 2 1 - p. f o r "-" s i g n V. 1 Since n = 1-P^ when = 0, we conclude that "-" s i g n i n (6.24) should be s e l e c t e d ; thus n = {1 + e - [(1-e ) 2 + 4p 2e ] 1 / 2 } / 2 e (6.25) q q i q q The s u b s t i t u t i o n of (6.25) i n t o (6.17) and (6.15) gives the optimum value of as f o l l o w s . a = -{1 - e - [(1-e ) 2 + 4p 2e ] 1 / 2 } / 2 P l e n (6.26) 1 q q 1 q 1 q The optimum values of ri and a, are p l o t t e d as a f u n c t i o n of e 1 q i n F i g . 50, assuming that p^ = 0.89. A l s o shown In the h o r i z o n t a l s c a l e i s the number of q u a n t i z e r output b i t s K. When i n c r e a s e s , n decreases and increases as shown above. The absolute value of ri i n dB a l s o denotes the improvement i n output S N R q f o r D P C M when the d i g i t a l channel i s n o i s e -l e s s . When K = 2, t h i s improvement i s 7.2dB as compared to 6.8dB when the fedback q u a n t i z a t i o n noise i s neglected. When K = 1, the improvement i s even g r e a t e r , but the exact value i s somewhat s o u b t f u l , because the assumption made i n the a n a l y s i s may not apply i n t h i s case. 6.5.2 Two-Previous-Sample Feedback Let N = 2 i n (6.19). Then, we have H(n) = A 3 - (2 + e )e n 2 + [ (2 - p 2 - p 2 )e + 1 - p2]n - [1 + 2p2(p„-l) q 1 2 q 1 1 / - p 2 ] = 0 (6.27) I t i s d i f f i c u l t to express the roots of t h i s equation i n closed form. However, the root that converges to n = [1 + 2p 2 ( p 2-l) - p 2 ] / ( l - p 2 ) (6.28) when 0 can be e a s i l y found n u m e r i c a l l y . Shown i n F i g . 51 are the optimum values of n, a, and a„ vs. E when p. = 0.89 and p_ = 0.65. I t 1 2 q 1 I i s noted that the fedback q u a n t i z a t i o n noise 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 to the improvement i n p r e d i c t i o n . For example, when K = 2, the re d u c t i o n i n n i s more than IdB as compared to 0.4dB f o r N = 1 i n Se c t i o n 6.5.1. Both and als o change co n s i d e r a b l y when the fedback q u a n t i -z a t i o n noise i s considered. 139 F i g . 50. Optimum values of ^ = a & / a x a n d a ^ a s obtained from (6.25) and (6.26) v s . e f o r previous-sample feedback DPCM w i t h n o i s e -l e s s channel; p =0.89. 51. Optimum values of n=o" /a , a ] _ a n d a 2 f o r t w o previous-sample feedback DPCM as obtained from (6.27) and (6.15) v s . e^; P1= 0.89, p2=0.65. V I I . CONCLUSIONS 7.1 Summary of the Present Research Various aspects of DPCM systems operating on n o i s y communication channels have been i n v e s t i g a t e d i n t h i s study. Summarized i n the f o l l o w i n g are the r e s u l t s that have been obtained. 1) A n a l y t i c a l expressions f o r the mean-square d i s t o r t i o n and S N R Q of DPCM systems when channel t r a n s m i s s i o n e r r o r s cannot be ignored have been deri v e d . As w i t h PCM, c o n t r i b u t i o n s 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 separate terms; namely, q u a n t i z a t i o n e r r o r , channel e r r o r , and mutual e r r o r . Each of these e r r o r s i s f u r t h e r expressed e x p l i c i t l y i n terms of 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 parameters, and channel 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 of the decoder has been i n v e s t i g a t e d . The cons-t r a i n t s on the p r e d i c t o r c o e f f i c i e n t s i n order f o r channel e r r o r s not to b u i l d up u n l i m i t e d l y have been presented. 3) The e f f e c t of channel e r r o r s on SNR when the conv e n t i o n a l o p t i -o mum l i n e a r p r e d i c t o r i s used has been examined. Transmission e r r o r s i n t h i s case are found to be no more s e r i o u s than f o r PCM, as has been sug-gested 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 IV, the mean-square e r r o r r e s u l t i n g from channel noise can even be l e s s than that f o r PCM. 4) The maximum value of SNR obtainable by DPCM has been derived o J and compared w i t h the t h e o r e t i c a l bound obtained from the 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 both one- and two-dimensional s i g n a l s , the SNR of DPCM can achieve a value that i s only two or three d e c i b e l s o below the bound. In f a c t , i f the tr a n s m i s s i o n r a t e i s not too s m a l l , 142 DPCM can remove almost a l l the redundancy inherent i n most s i g n a l s ; the d i f f e r e n c e between SNR of DPCM and the t h e o r e t i c a l bound i s thus simply o J a r e s u l t of q u a n t i z a t i o n . 5) A procedure f o r maximizing S N R Q by the j o i n t o p t i m i z a t i o n of the q u a n t i z e r , p r e d i c t o r , sampling r a t e , and bandwidth has been proposed. In p a r t i c u l a r , equations f o r the input thresholds and output l e v e l s of the optimum qu a n t i z e r are deri v e d . The o p t i m i z a t i o n of the p r e d i c t o r , sampling r a t e and bandwidth i s a l s o considered s e p a r a t e l y . For a f i x e d t r a n s m i s s i o n r a t e , i t i s shown that sampling at the Nyquist r a t e almost always y i e l d s the highest S N R q . When the sampling r a t e i s Nyquist, the tran s m i s s i o n r a t e R i s f i x e d , the inp u t s i g n a l i s Gaussian Markov, and the t r a n s m i s s i o n channel i s n o i s e l e s s , the bandwidth W •= 0.66R i s found to optimize SNR . The optimum value of bandwidth increases when the o channel 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 -line-and-sample feedback DPCM f o r video s i g n a l s , have been analyzed i n d e t a i l . These systems have al s o been simulated w i t h a d i g i t a l computer by using a r e a l speech sample and two video images as input s i g n a l s . The experimentally measured values of S N R q are found to agree very w e l l w i t h those c a l c u l a t e d i n each case. For a well-designed DPCM system, the value of SNR^ i s shown to be con s i d e r a b l y higher than that f o r a well-designed PCM o p e r a t i n g on the same tr a n s m i s s i o n channel. This i s true even when the channel i s very n o i s y . 7) For one-previous-sample feedback system, choosing the feedback c o e f f i c i e n t near i t s optimum value f o r very n o i s y channel, i . e . , = 7 2 ( l - v l - p p / p ^ , r a t h e r than i t s conventional value of <x^ =p^ i s found to be most d e s i r a b l e . When the channel i s n o i s e l e s s , the degradation i n performance r e s u l t i n g from t h i s choice of i s very s m a l l . When the channel becomes n o i s y , however, the e f f e c t of channel e r r o r s i s much l e s s severe 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 support t h i s a n a l y t i c a l r e s u l t . 8) The improvement i n S N R q when two previous samples are 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 to the one-previous-sample feedback system, even i f the tr a n s m i s s i o n channel i s n o i s y . 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 the channel i s n o i s e l e s s , approximately 2.6dB can be gained by using the sample on top i n the previous l i n e , i n a d d i t i o n to the previous sample, f o r the p r e d i c t i o n f o r the two video images shown i n F i g . 11. The gain i n c r e a s e s when the channel 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 , or <j> = OdB, f o r example, an improvement of 3.67dB f o r the crowd scene and 4.51dB f o r the cameraman scene can be obtained by feeding back the sample on top. 10) The s e n s i t i v i t y of SNR^ 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 , 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 channel e r r o r p r o b a b i l i t y has been analyzed and i t s i m p l i c a t i o n s on the design of feedback c o e f f i c i e n t s noted. S p e c i a l a t t e n t i o n i s p a i d to the s e l e c t i o n of these c o e f f i c i e n t s f o r the purpose of d i g i t a l r e a l i z a t i o n . For speech s i g n a l s w i t h p r e v i o u s -sample feedback, f o r example, = 0.75 i s found to be a very good choice. For line-and-sample feedback, on the other hand, i t i s most d e s i r a b l e to use = 0.3725 and cx^ = 0.5. 11) Various techniques f o r combating channel noise have been examined, i n c l u d i n g channel encoding, 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 updating. For channel encoding, a t t e n t i o n i s devoted to the 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, which i s f a i r l y simple 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 constant, Hamming code i s found to perform b e t t e r i f the t r a n s m i s s i o n channel i s not too n o i s y , w i t h a maximum im-provement i n SNR of approximately 1.5dB. P e r i o d i c r e s e t t i n g i s simple and easy to implement. I t can a l s o achieve an improvement i n S N R q of 1.5dB f o r the two images shown i n F i g . 11. However, e r r o r s r e s u l t i n g from amplitude overload appear on the same v e r t i c a l l i n e and can be e a s i l y detected. The use of a pseudo-random number generator can e l i m i -nate these annoying e r r o r s . 12) The s u b j e c t i v e e f f e c t s of channel e r r o r s on video 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 evaluated. The systems considered i n c l u d e previous-sample feedback f o r = p^, 0.9 and 0.8, line-and-sample feedback f o r a, = a., : CL, =CL, , a, = OL, = 0.5, and ' 1 l c ' N Nc' 1 N ' OL^ = 0.3725; CL^ = 0.5, previous sample feedback w i t h p e r i o d i c r e s e t t i n g and pseudo-random r e s e t t i n g . I t i s found that previous-sample feedback system w i t h = 0.8 and line-and-sample feedback system w i t h = 0.3725 and a N = 0.5 are most f a v o r a b l e . 13) DPCM systems w i t h coarse q u a n t i z a t i o n have been analyzed. Equations 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 S N R Q , assuming that Max q u a n t i z e r i s used and that the t r a n s m i s s i o n channel i s n o i s e l e s s , are d e r i v e d . I t i s shown that the value of S N R q i s l a r g e r when the fedback q u a n t i z a t i o n noise i s used to optimize the p r e d i c t o r than when i t Is neglected. S N R q i n t h i s case, however, i s more s e n s i t i v e to channel n o i s e . 7.2 Suggestions f o r Further Research As a n a t u r a l extension of the present study, work on the f o l -lowing t o p i c s i s suggested. 1) Formal s u b j e c t i v e e v a l u a t i o n of the e f f e c t of channel noise on s t r a i g h t DPCM systems and those w i t h noise-combating schemes. Throughout t h i s t h e s i s , S N R q has been used as a c r i t e r i o n of.system performance. Although i t i s one of the best o b j e c t i v e measures and i s a l s o a convenient b a s i s f o r system a n a l y s i s and design, i t may not t r u l y i n d i c a t e the sub-j e c t i v e q u a l i t y . A formal s u b j e c t i v e e v a l u a t i o n , such as that based on iso p r e f e r e n c e t e s t i n g or m u l t i - s c a l e r a t i n g , i s t h e r e f o r e suggested. 2) E f f e c t of channel noise on the performance of adaptive d i f f e r e n -t i a l systems. Some adaptive d i f f e r e n t i a l systems, such as the, adaptive AM proposed by Jayant [50], are very a t t r a c t i v e because of t h e i r s i m p l i c i t y and e f f i c i e n c y i n ac h i e v i n g a high q u a l i t y at 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 adaptive systems are very s e n s i t i v e to channel 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 intensive, study of the e f f e c t of channel noise should be performed and, more i m p o r t a n t l y , simple and e f f e c t i v e schemes f o r combating channel noise should be explored. 3) Complete d i g i t a l r e a l i z a t i o n of DPCM systems. Advancement i n modern technology 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 of the complete d i g i t a l r e a l i -z a t i o n of DPCM systems and i t s e f f e c t on system performance should t h e r e -fore be f u r t h e r i n v e s t i g a t e d . 4) Performance of DPCM systems o p e r a t i n g on other types of t r a n s -m i s s i o n channel. Although expressions f o r the mean-square e r r o r given i n (2.10) and (2.11) of t h i s t h e s i s are very g e n e r a l , a l l of the a n a l y s i s followed are based on the assumption that channel noise samples are s t a -t i s t i c a l l y independent. I t i s of i n t e r e s t to look i n t o how the system performance i s a f f e c t e d by other types of tr a n s m i s s i o n channel, such as those w i t h intersymbol i n t e r f e r e n c e . 5) DPCM systems w i t h three-dimensional coding f o r video s i g n a l s . In p a r t i c u l a r , i t i s of i n t e r e s t to i n v e s t i g a t e the e f f e c t of p r e d i c t i n g a sample by using i t s s p a t i a l counterpart on the immediately previous frame, along w i t h the previous sample and the sample on top, and compare the r e s u l t i n g S N R q or s u b j e c t i v e q u a l i t y w i t h that of one- and two-sample feedback systems when they are ope r a t i n g on the same d i g i t a l channel. The expressions f o r S N R q derived i n t h i s t h e s i s s t i l l 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 study w i l l be the e v a l u a t i o n of the f a c t o r Q and the d e r i v a t i o n of s t a b i l i t y c o n s t r a i n t s . 6) E f f e c t s of more elaborate coding schemes on the r e d u c t i o n of mean-square channel 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 -i n g c a p a b i l i t y . APPENDIX I C a l c u l a t i o n of 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 p r o b a b i l i t y of events A and B and the p r o b a b i l i t y of the event A given B. Let P e ( a , 3 ) denote the j o i n t amplitude p r o b a b i l i t y d e n s i t y of e. and e. , . Q u a n t i t i e s X X K. r . , s., e., v. and u. are defined i n F i g s . 1 and 2, wh i l e P.. and p (a) 1' 1 1 1 1 6 ' i j r e are defined i n Se c t i o n 2.3.1. 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 ) (1.1) c i - k d l a i - k c l a i - k c I f the d i g i t a l channel i s memoryless, and i f P ( s . = v , s. . = v ) i s X SL X K. c expressed i n terms of p (a,3), then f o r k ^ 0, L L L L u a + l Uc+1 R (k) = E E E E (v,-v ) ( v , - v ) P , P , / / C P (a,3)dctd3 n n , -, -, , -. b a d c ab cd u u e a=l b=l c=l d=l a c (1.2) I f e. and e. , are s t a t i s t i c a l l y independent, then p (a,3) = P (ct)p (3) X X™K. G 6 6 and R (k) = [ E ( n . ) ] 2 . n I L L L u = E E E jf a ""-(v ~cO(v,-v ) P ( r . = v, | s. = v , r. = , , v b d c N I b ' i a i - k b=l c=l d=l u 3 (1.3) , Uc+1 v,,s. . = v ) P ( r . . = v, s. = v ,s. . =v ) / P (a ,3)dad3 d i - k c i - k d 1 l a i - k c u & • c I f the d i g i t a l channel i s memoryless, then f o r k ^ 0 L L L Ua+1 Uc+3 R (k) = E E E / (v, - a ) ( v , - v )P , P , / P (a ,3)dad3 (1.4) qn , . , , , u b d c ab cd u e 1 b=l c=l d=l a c 148 I f e and e , are s t a t i s t i c a l l y independent, then (1.3) reduces to 1 i - k R q n ( k ) = E[q.] E[n.._ k]. Functions R (0) and R (0) are given by (2.12), (2.17) and (2.18) n qn APPENDIX I I D e r i v a t i o n of the O v e r a l l Mean-Square E r r o r The block diagram of 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 ) are replaced by low-pass f i l t e r s and, f o r convenience i n the a n a l y s i s to be fo l l o w e d , the p o s t - f i l t e r i s represented by two l o w - p a s s - f i l t e r s ; one f o r reproducing the analog s i g n a l and the other f o r e l i m i n a t i n g the out-of-band e r r o r . m(t) 1 >--w w <(t) fs>2w DIGITAL CODER DECODER AND CHANNEL l/fs x(t) 1 *» I I >• fs -w w x(t) F i g . 1.1 D i g i t a l Communication System The mean-square e r r o r between the in p u t and output of the s y s -tem i n F i g . I.1 i s E { [ x ( t ) - m ( t ) ] 2 } = E { [ x ( t ) - x ( t ) + x ( t ) - m ( t ) ] 2 } = E { [ x ( t ) - x ( t ) ] " > + 2 / S ( f ) d f w m (I I . 1 ) The l a s t e q u a l i t y i n (II.1) i s true because x ( t ) - x ( t ) and x ( t ) - m(t) have no common frequency. The f i r s t term of (II.1) can again be w r i t t e n as f o l l o w s . E { [ x ( t ) - x ( t ) ] 2 } = E { [ x ( t ) - x ( t ) + x ( t ) - x ( t ) ] 2 } = E { [ x ( t ) - x ( t ) ] 2 } + 2E{[x(t) - x ( t ) ] [ x ( t ) - x ( t ) ] } + E { [ x ( t ) - x ( t ) ] 2 } ( I I . 2 ) f 12 E { [ x ( t ) - x ( t ) ] 2 } = E [ ( x . - x . ) 2 ] = f - f 12 S d ( f ) d f ( I I > 3 ) s s 150 where S^(f) i s the power s p e c t r a l d e n s i t y of d^ = x^ - x^. Since x ( t ) and x ( t ) - x ( t ) have no common frequency, the second term of (II.2) becomes 2 E { [ x ( t ) - x ( t ) ] [ x ( t ) - x ( t ) ] } = 2E{ [ x < t ) - x ( t ) ] x ( t ) } s - f 12 s s 9 f 12 = - T~ f * l s ; ( f ) + s ; ( - f ) ] d f ( i i . 4 ) r W x x s where S^(f) i s the power s p e c t r a l d e n s i t y of x^. S i m i l a r l y , the f i r s t term of ( I I . 2) can be w r i t t e n i n terms of S~(f) as f o l l o w s . f /2 E { [ x ( t ) - x ( t ) ] } = j - / W S t S ^ ( f ) + S ^ ( - f ) ] d f ( I I . 5 ) s S u b s t i t u t i n g (II.3) - (I I . 5 ) i n t o ( I I . 2 ) y i e l d s f /2 f 12 E { [ x ( t ) - x ( t ) ] Z ) = f- f_\ / 2 S d ( f ) d f - f- / W S [ S ^ ( f ) + S - ( - f ) ] d f ( I I . 6 ) s s s Denoting S~(f) i n terms of S ( f ) , the power spectrum of x., and S ( f ) , X X X X Q the cross-power spectrum of x^ and d^, we have S^(f) = S x ( f ) + S x d ( f ) + S x * ( f ) + S d ( f ) ( I I . 7 ) Since 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 s (-f)df = / s s ( f ) d f ( i i . 8 ) W x W x W d A l s o , from (2.7), i t can be shown th a t S d ( f ) - S q ( f ) + S q n ( f ) F * ( f ) + S q * ( f ) F ( f ) + S n ( f ) | F ( f ) | 2 ( I I . 9 ) 151 The s u b s t i t u t i o n of (II.8) and ( I I . 9 ) i n t o ( I I . 6 ) y i e l d s E { [ x ( t ) - x ( t ) ] 2 } = i - [S (f)+S ( f ) F * ( f ) + S * ( f ) F ( f ) + S n ( f ) | F ( f ) | 2 ] d f s (11.10) S u b s t i t u t i n g (11.10) i n t o (II.1) again gives (2.15a). 152 REFERENCES 1. A.H. Reeves, French Patent No. 852,183, October 3, 1938. 2. E.M. Deloraine and A.H. Reeves, "The 25th anniversary of pulse code modulation", 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 , French Patent 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 of communication s i g n a l s " , U.S. Patent No. 2,605,361, J u l y 29, 1952. 5. H. van de Weg, "Quantizing noise of a s i n g l e i n t e g r a t i o n d e l t a modu-l 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 Research Reports, 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 of 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 ulse code modulation) f o r the transmission of t e l e v i s i o n s i g n a l s " , B e l l Syst. 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 noise r a t i o s f o r d i g i t a l encoding systems", Proc. 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 channel performance of d i f -f e r e n t i a l pulse code modulation 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 Syst. Tech. J . , v o l . 45, pp. 1123- 1151, Sept-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 of APCM", E l e c t r o n . Commun. Japan, v o l . 48, pp. 17-26, February 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 of d i f f e r e n t i a l pulse-code modulation v o i c e communication systems", IEEE Trans. Commun. Technol., v o l . C0M-17, pp. 10-19, February 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 of PCM, DPCM, AM, AM, and PM v o i c e communication systems", IEEE Trans. Commun. Technol., 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 channel 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 of sam-p l e d imagery", IEEE Trans. Commun. Technol., 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 of channel 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 systems", IEEE Trans. Commun. Technol., v o l . C0M-20, pp. 281-290, June 1972. 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 of 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 communi-c a t i o n channels", IEEE Trans. Commun., v o l . COM-20, pp 338-350, June 1972. 16. A.J. Kurtenback and P.A. Wintz, "Quantizing f o r n o i s y channels", IEEE Trans. Commun. Technol., 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 of DPCM system w i t h coarse 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 pre- and p o s t - f i l t e r i n g of sampled s i g n a l s , w i t h a p p l i c a t i o n to pulse modulation and data compression systems", IEEE Trans. Commun. Technol., 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 to the Theory of S t a t i o n a r y Random Functions, New Jersey: P r e n t i c e H a l l , pp. 110-121, 1962. 20. G.H. Robertson, "Computer study of quantized output s p e c t r a " , B e l l Syst. Tech. J . , v o l . 48, pp. 2391-2403, September 1969. 21. R.E. Totty and G.C. C l a r k , "Reconstruction e r r o r i n waveform t r a n s -m i s s i o n " , IEEE Trans. Inform. Theory (Corresp.), v o l . IT-13, pp. 336-338, 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 of Servomechanisms, New York: McGraw-Hill, 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 of the z-Transform Method, New York: Wiley, 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 Processes, New York: McGraw H i l l , pp. 39 7-403, 1965. 25. C.E. Shannon and W. Weaver, The Mathematical Theory of Communication, Urbana, 111,: Univ. of 111. P r e s s , Chapter 5, pp. 108-125, 1949. 26. A.N. Kolmogorov, "On the Shannon Theory of 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 the case of continuous s i g n a l s " , IRE Trans. Inform. Theory, v o l . IT-2, pp. 102-108, December 1956. 27. U. Grenander and G. Szegb, T o e p l i t z Forms and Their A p p l i c a t i o n s , B e rkeley, C a l i f . : Univ. of C a l i f . P r e s s , Chapter 3, pp. 44-55, 1958. 28. D.J. Sakrison and V.R. A l g a z i , "Compression of l i n e - b y - l i n e and two-dimensional encoding of random s i g n a l s " , IEEE Trans. Inform. Theory, v o l . IT-17, pp. 386-398, J u l y 1971. 29. B. Smith, "Instantaneous companding of quantized s i g n a l s " , B e l l Syst. Tech. J . , v o l . 36, pp. 653-709, May 1957. 154 30. J . Max, "Quantizing f o r minimum d i s t o r t i o n " , IRE Trans. Inform. Theory, ' v o l . IT-6, pp. 7-12, March 1960. 31. P.F. Panter 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 pulse-count modulation w i t h nonuniform spacing of l e v e l s " , Proc. IRE, v o l . 39, pp. 44-48, January 1951. 32. W.R, Bennett, "Spectra of quantized s i g n a l s " , B e l l Syst. Tech. J . , v o l . 27, pp. 446-472, J u l y 1948. 33. J.M. Wozencraft and I.M. Jacobs, P r i n c i p l e s of Communication E n g i n e e r i n g , New York: Wiley, 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 audio spectrometry", J . Acoust. Soc. Amer., v o l . 25, pp. 499-505, May 1953. 35. W.B. Davenport, J r . , "An experimental study of 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 . Acoust. Soc. Amer., v o l . 24, pp.'390-399, J u l y 1952. 36. E.R. Kretzmer, " S t a t i s t i c s of t e l e v i s i o n s i g n a l s " , B e l l Syst. Tech. J . , v o l . 31, pp. 751-763, J u l y 1952. 37. A. Nishikawa, R.J. Massa, and J.C. Mott-Smith, "Area p r o p e r t i e s of t e l e v i s i o n s i g n a l s " , IEEE Trans. Inform. Theory, v o l . IT-11, pp. 348-352, J u l y 1965. 38. W.F. Sc h r e i b e r , "The measurement of 3rd order p r o b a b i l i t y d i s t r i b u t i o n s of t e l e v i s i o n s i g n a l s " , IRE Trans. Inform. Theory, v o l . IT-2, pp. 94-105, September 1956. 39. D.S. Seraphin, "A f a s t random number generator f o r IBM 360", Com-munications of the ACM, v o l . 12, p. 695, December 1969. 40. B.M. O l i v e r , " E f f i c i e n t Coding", B e l l Syst. 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 Progress Rept., No. 82, pp. 223-227, J u l y 1966. 42. G.G. Apple and P.A. Wintz, "BCH code performance f o r sampled data", IEEE I n t . Conf. Commun., Conv. Reed., v o l . 2, pp. 28.1-28.8, June 1970. 43. W.W. Peterson, E r r o r C o r r e c t i n g Codes, Cambridge, Mass.: MIT P r e s s , pp. 67-70, 1961. 44. E.R. Berlekamp, A l g e b r a i c Coding Theory, New York: McGraw-Hill, 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 Syst. Tech. J . , v o l . 48, pp. 2583-2599, September 1969. 155 46. D.J. Connor, R.F.W. Pease and W.G. Scholes, " T e l e v i s i o n coding using two-dimensional s p a t i a l p r e d i c t i o n , " B e l l Syst. Tech. J . , v o l . 50, pp. 1049-1061, March 1971. 47. R.W. Stroh and R.R. Boorstyn, "Optimum and adaptive d i f f e r e n t i a l pulse code modulation," Tech. Rept., Dept. of E l e c . Eng., P o l y t e c h n i c I n s t , of Brooklyn, 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 Trans. Commun. Technol., 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 of amplitude d i s t o r t e d Gaussian S i g n a l s , " MIT Res. Lab. E l e c t r o n i c s , Tech. Rept. no. 216, March 1952. 50. N.S. Jayant, "Adaptive d e l t a modulation w i t h a one-bit memory," B e l l Syst. Tech. J . , v o l . 49, pp. 321-342, March 1970.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Analysis and optimization of differential PCM systems...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Analysis and optimization of differential PCM systems operating on noisy communication channels Chang, Ke-yen 1972
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Analysis and optimization of differential PCM systems operating on noisy communication channels |
Creator |
Chang, Ke-yen |
Publisher | University of British Columbia |
Date Issued | 1972 |
Description | A closed-form analytical expression for the output signal-to-noise ratio (SNR₀) of differential PCM systems operating on noisy communication channels is obtained. A procedure is then proposed for maximizing SNR₀ by joint optimization of the quantizer, predictor, sampling rate, and bandwidth. Several examples are considered, including one- and two-sample feedback systems excited by speech and video signals. Various techniques for reducing channel errors are then discussed. The predictor used in the DPCM system is linear and time invariant, but otherwise arbitrary. As with PCM, contributions to output signal distortion can be expressed as a sum of three distinct terms resulting, respectively, from quantization errors, channel transmission errors, and mutual errors arising from interaction between quantization and channel errors. Constraints on the predictor coefficients for channel errors not to build up unlimitedly are presented. When a conventional optimum linear predictor is used, transmission errors are shown to be no more serious for DPCM than for PCM. The values of SNR₀ obtainable from DPCM are also compared with the theoretical bound obtained from the rate-distortion function. For a well-designed DPCM system, the value of SNR₀ is shown to be considerably higher than that for a well-designed PCM system operating on the same digital channel, even if the channel is noisy. In considering examples, particular attention is devoted to determining maximum values for SNR₀ and to examining the dependence of SNR₀ on predictor coefficient values, number of quantization levels, message statistics, and channel error probability. Implications of this dependence on system design are noted. Among the various techniques investigated for combating channel noise are channel encoding, periodic resetting, and pseudo-random resetting. These techniques are further evaluated subjectively with two video images. DPCM systems with coarse quantization are studied. The fedback quantization noise is considered in optimizing the predictor. Simple equations for the optimum predictor coefficients and the resulting SNR₀ are derived. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0101223 |
URI | http://hdl.handle.net/2429/32506 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
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
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0101223/manifest