Speech Coding Algorithms: Foundation and Evolution of Standardized Coders

EXERCISES 181 than 4 bits, increasing the resolution by 1 bit roughly increases the SNR by 6 dB. Since the speech samples have a statistical distribution close to the Laplacian type, nonuniform quantization with more low-amplitude output levels is better suited for the quantization task. The m-law and A-law nonlinearities are introduced as com- monly accepted rules for the design of nonuniform quantizers. Unlike uniform quantizers, where good quality output is maintainable only for a relatively narrow range of input level, nonuniform quantizers can sustain high SNR for a wider range of input level. Therefore, it is more suitable for speech coding since the energy level of the signal varies drastically with speakers, environments, equipment, and so on. For nonstationary signals like speech, use of some kind of adaptation can achieve higher coding efficiency. Several schemes of APCM and ADPCM are pre- sented. Forward adaptation is less sensitive to transmission errors, with higher delay and lower coding efficiency when compared to backward schemes. In subsequent chapters, the principles of adaptive methods are applied to speech coding algorithm design. Discussion of APCM and ADPCM has been limited to high-level concepts and system structures, without entering into the details of implementation of any coding standard. For ADPCM a well-known standard exists and is due to ITU. This spe- cifies a 64-kbps nonuniform PCM (G.711) input, and four possible bit-rates are available: 40, 32, 24, and 16 kbps. It is known as recommendation G.726 and is based on backward adaptation. It utilizes a pole-zero or ARMA predictor with its parameters updated through a gradient-based adaptive algorithm. Readers are referred to ITU [1990] for details. Also, Jayant and Noll [1984] contains ample descriptions of many PCM-related schemes, as well as early developments in the field. EXERCISES 6.1 In uniform quantization, consider the case when the size is large (high resolution). (a) Given the input is in a particular cell, argue why the conditional PDF of the quantization error is uniform over the interval ðÀÁ=2; Á=2Þ. Show that the conditional variance of the quantization error is Á2/12, with Á the quantizer’s step size. (b) Argue why the unconditional average distortion is given approximately by D ¼ Á2=12: (c) Show that Á % 2A=N

182 PULSE CODE MODULATION AND ITS VARIANTS and D ¼ s2g22À2r=3 with N the quantizer’s size. (d) Show that  SNR ¼ 6:02r þ 10 log10 3 ; g2 that is, SNR increases approximately 6 dB for each additional bit used to quantize an input sample. 6.2 Using a large amount of speech samples, construct the histogram and verify the validity of the proposed Laplacian distribution. 6.3 Generate SNR curves (as a function of g) for nonuniform m-law quantization using uniformly distributed input. Compare with uniform quantization in terms of peak SNR. 6.4 Generate SNR curves (as a function of g) for A-law quantization. Compare with m-law results. 6.5 In DPCM, assuming stationary input, show that SNR ¼ sx2 ¼ PG Á QG Efe2½nŠg where s2 ¼ input variance; e½nŠ ¼ quantization error; PG ¼ prediction gain; QG ¼ quantizer gain; and PG ¼ sx2 ; s2e QG ¼ s2e ^e½nŠÞ2g : Efðe½nŠ À 6.6 Delta modulation is the 1-bit (or two-level) version of DPCM. In this scheme, the prediction is given by the past quantized sample xp½nŠ ¼ ^x½n À 1Š and the quantizer has only two levels ^e½nŠ ¼ Ásgnðe½nŠÞ;

EXERCISES 183 where sgn( Á) is the sign function, while Á is the quantizer’s step size. Show that Xn xp½nŠ ¼ Á sgnðe½iŠÞ; i¼1 assuming that the system is initialized at instant n ¼ 0 with xp[0] ¼ 0. 6.7 In Figure 6.5, the peaks of the SNR curves tend to shift toward higher values of g for increasing resolution. Explain this phenomenon. Why isn’t the situation occurring for uniformly distributed input (Figure 6.3)? 6.8 Draw the block diagrams of a DPCM system based on an ARMA predictor; that is, the predictor takes as inputs the samples of the quantized input signal and the quantized prediction-error signal. 6.9 Draw the block diagrams of the encoder and decoder for an ADPCM system with forward gain adaptation and backward predictor adaptation. Repeat for the case of backward gain adaptation and forward predictor adaptation. 6.10 Similar to Example 6.4, design a 2-bit DPCM-MA scheme using a first-order predictor and compare its performance to 3-bit PCM. The predictor coeffi- cient can be determined by trial-and-error. Develop a systematic way to find the optimal predictor coefficient, when the quantizer is fixed.

CHAPTER 7 VECTOR QUANTIZATION Vector quantization (VQ) concerns the mapping in multidimensional space from a (possibly continuous-amplitude) source ensemble to a discrete ensemble. The map- ping function proceeds according to some distortion criterion or metric employed to measure the performance of VQ. VQ offers several unique advantages over scalar quantization, including the ability to exploit the linear and nonlinear dependencies among the vector components, and is highly versatile in the selection of multidi- mensional quantizer cell shapes. Due to these reasons, for a given resolution (mea- sured in bits), use of VQ typically results in lower distortion than scalar quantization. In VQ, vectors of a certain dimension form the input to the vector quantizer. At both the encoder and decoder of the quantizer there is a set of vectors, having the same dimension as the input vector, called the codebook. The vectors in this code- book, known as codevectors, are selected to be representative of the population of input vectors. At the encoder, the input vector is compared to each codevector in order to find the closest match. The elements of this codevector represent the quan- tized vector. A binary index is transmitted to the decoder in order to inform about the selected codevector. Because the decoder has exactly the same codebook, it can retrieve the codevector given its binary index. Some materials in this chapter are natural generalizations of results in scalar quantization. After all, scalar quantization is VQ with unit dimension. VQ has become more and more significant for signal coding applications, mainly due to its high performance. In subsequent chapters we will see how the technique is applied to various speech coding standards; hence, it is imperative to acquire pro- ficiency in the subject. In this chapter, the basic definitions involved with vector quantization are given, followed by the conditions required for optimal quantiza- tion; algorithms for quantizer design are described in detail. It is shown that optimal 184 Speech Coding Algorithms: Foundation and Evolution of Standardized Coders. Wai C. Chu Copyright  2003 John Wiley & Sons, Inc. ISBN: 0-471-37312-5

INTRODUCTION 185 VQ is highly costly to implement in practice. Therefore, several suboptimal schemes with certain structure are explained in detail; these include multistage VQ (MSVQ), split VQ, and conjugate VQ. These suboptimal schemes provide good performance at a reasonable implementational cost, enabling the deployment of VQ to many speech coding applications. Similar to DPCM in scalar quantization, incorporation of prediction into the VQ framework leads to improved performance in most cases; these schemes are discussed in a separate section, where predictive VQ (PVQ) and PVQ-MA are introduced. 7.1 INTRODUCTION The basic issues of vector quantization are introduced in this section. Many topics are mere extensions of scalar quantization from one dimension to multiple dimen- sions. Definition 7.1: Vector Quantizer. A vector quantizer Q of dimension M and size N is a mapping from a vector x in M-dimensional Euclidean space RM into a finite set Y containing N M-dimensional outputs or reproduction points, called codevectors or codewords. Thus, Q: RM ! Y; where x ¼ ½x1; x2; . . . ; xMŠT ; ðy1; y2; . . . ; yNÞ 2 Y; yi ¼ ½yi1; yi2; . . . ; yiMŠT ; i ¼ 1; . . . ; N: Y is known as the codebook of the quantizer. The mapping action is written as QðxÞ ¼ yi; i ¼ 1; . . . ; N: ð7:1Þ Definition 7.2: Resolution. We define the resolution of a vector quantizer as r ¼ lg N; ð7:2Þ which measures the number of bits needed to uniquely address a specific codeword. Definition 7.3: Cell. Associated with every N-point M-dimensional vector quanti- zer is a partition of RM into N regions or cells, Ri; i ¼ 1; . . . ; N. The ith cell is defined by Ri ¼ fx 2 RM : QðxÞ ¼ yig ¼ QÀ1ðyiÞ: ð7:3Þ Definitions of granular cell and overload cell found in scalar quantization apply directly to VQ.