Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. VII (2012), No. 1 (March), pp. 115-122 Switched Nonuniform and Piecewise Uniform Scalar Quantization of Laplacian Source A.V. Mosic, Z.H. Peric, S.R. Panic Aleksandar V. Mosić Faculty of Electronic Engineering, University of Niš Aleksandra Medvedeva 14, 18000 Niš, Serbia E-mail: mosicaca@yahoo.com Zoran H. Perić Faculty of Electronic Engineering, University of Niš Aleksandra Medvedeva 14, 18000 Niš, Serbia E-mail: zoran.peric@elfak.ni.ac.rs Stefan R. Panić Faculty of Natural Science and Mathematics, University of Priština Lole Ribara 29, 38200 Kosovska Mitrovica, Serbia E-mail: stefanpnc@yahoo.com Abstract: In this paper switched nonuniform and piecewise uniform scalar quantization of Laplacian source are analyzed. This scalar quantization techniques are used in order to obtain higher signal quality by increasing signal-to-quantization noise ratio (SNRQ) with respect to it’s necessary robustness over a broad range of input variances in a wide range of signal volumes. We observe µ-law compandor implementation to achieve compromise between high-rate digitalization and variance adaptation. The main contribution of this model is kipping almost the same quality as the nonuniform compandor model, with simpler realization structure and the possibility of it’s applying for digitalization of wide range continuous signals. Keywords: switching quantization, µ-law companding, variance adaptation, Laplacian source. 1 Introduction Quantization denotes the heart of analog to digital (A/D) conversion and efficient technique of data compression. Quantizers play an important role in the theory and practice of modern day signal processing. They are applied for the purpose of storage and transmission of continual signals. In a number of papers like this one the quantization of Laplacian source was analyzed since the probability density function (PDF) of the instantaneous speech signal values for higher number of digitalization samples is better represented by Laplacian then the Gaussian function [1], [2], [4], [7], [10]. Analysis of nonlinear quantization optimization in wide volume range [5], [6], for Gaussian source is given in [8], [9]. In this paper we analyze robust and switched nonuniform and piecewise uniform scalar quantization of Laplacian source to achieve compromise between high-rate digitalization and variance adaptation. The aim of our research is to find a simple way to realize a quantizer system having high quality performance but maintaining robustness in wide range of input signal. The goal of the paper is designing piecewise uniform scalar quantizer based on the µ-law compandor which satisfy G.712 standard. In this purpose, we must to find optimal values for parameter µ and number of quantizers. Proposed solution Copyright c⃝ 2006-2012 by CCC Publications 116 A.V. Mosic, Z.H. Peric, S.R. Panic has the same complexity as the G.711 standard, because we use 8 bits, but it satisfy G.712 standard with 7 bits/sample. Important issues from the engineer’s point of view are the design and implementation of quantizers to meet performance objectives. When the required hardware solution it is better to use piecewise uniform scalar quantizers, because they can be realized using linear electronic circuits. But if the required software solution it is better to use nonuniform scalar quantizers. This paper is organized as follows. In chapter 2. we have developed expressions for granular and overload distortion of nonuniform scalar quantization, using Bennett’s integral on Laplacian distribution. Then in chapter 3. a switching nonuniform model and numerical results for µ- logarithmic compandor are presented. In chapter 4. our switching piecewise uniform model and numerical results for µ-logarithmic compandor are presented. Last two chapters show how the increase of number of quantizers, in switching scheme, affects the SQNR dependence of input power. Also we have discussed how constant µ should be chosen in order for total distortion to be as minimum as possible in the wide volume range of input signal. Finally, in conclusion we have discussed obtained results, and on these bases, we derived conclusions about the possibilities of this switched quantization application in speech processing. 2 Distortion for nonuniform µ-logarithmic compandor Scalar quantizers are the only types of quantizers considered in this paper, so we just briefly recall their properties. An N-point fixed rate scalar quantizer is characterized by the set of real numbers t1, t2, . . . , tN , called decision thresholds, which satisfy −∞ = t0 < t1 < · · · < tN−1 < tN = +∞, and set y1,y2, . . . ,yN , called representation levels, which satisfy yj ∈ αj = (tj−1, tj], for j = 1, . . . ,N. Sets α1,α2, . . . ,αN form the partition of the set of real numbers R and are called quantization cells. The quantizer is defined as many-to-one mapping Q : R → R, Q(x) = yj where x ∈ αj. In practice, input signal value x is quantized to the value yj. Cells α2,α3, . . . ,αN−1 are inner cells (or granular cells) while α1 and αN are outer cells (or overload cells). In such way, cells α2,α3, . . . ,αN−1 form granular while cells α1 and αN form an overload region. Let input signal is characterized by continuous random variable X with PDF p(x). The first approximation to the long-time-averaged PDF of amplitudes is provided by a two-sided exponential or Laplacian model. Waveforms are sometimes represented in terms of adjacent- sample differences. The PDF of the difference signal for an image waveform follows the Laplacian function [4]. Laplacian source can be also used for modelling of the speech signal. In the rest of the paper we assume that information source is Laplacian source with memoryless property and zero mean value. The PDF of that source is given by: p(x) = 1 √ 2σ2 e− |x| √ 2 σ , (1) where x is zero-mean statistically independent Laplacian random variable of variance σ2. The quality of the quantizer is measured by distortion of resulting reproduction in comparison to the original one. Mostly used measure of distortion is mean-squared error. It is defined by: D(Q) = E(X − Q(X))2 = N∑ i=1 ∫ ti ti−1 (x − yi)2p(x)dx. (2) The N-point quantizer Q is optimal for the source X if there is no other N-point quantizer Q1 such that D(Q1) < D(Q). We also define granular distortion Dg(Q) and overload Dol(Q) Switched Nonuniform and Piecewise Uniform Scalar Quantization of Laplacian Source 117 distortion by: Dg(Q) = N−1∑ j=2 ∫ tj tj−1 (x − yj)2p(x)dx, (3) Dol(Q) = ∫ t1 −∞ (x − y1)2p(x)dx + ∫ +∞ tN−1 (x − yN)2p(x)dx. (4) Obviously follows that D(Q) = Dg(Q) + Dol(Q). The companding technique is one of the commonly used techniques for the construction of nearly optimal quantizers for large number of quantization levels. It forms the core of the ITU- T G.711 standard [3]. It is a nonuniform PCM standard recommended for encoding speech signals. The recommendation is based on digitally linearizable companding, which permits a precise control of quantization characteristics. The compression and expansion characteristics are piecewise linear approximations to µ-law , where µ = 255, with 8 bits/sample are adopted, leading to a bit-rate of 64 kbps at 8 kHz of sampling frequency. Companding procedure consists of following steps: i) compressing the input signal x by applying the compressor function c(x). ii) applying the uniform quantizer Qu on the compressed signal. iii) expanding the quantized version of the compressed signal using an inverse compressor function c−1(x). As explained the corresponding non-uniform quantizer consisting of a compressor, a uniform quantizer, and an expander in cascade is called companding quantizer (compandor). Hence, the companding quantizer can be represented as Q(x) = c−1(Qu(c(x))), where Qu(x) is uniform quantizer in the interval [−1,1]. Let us denote by tu,i and yu,i decision thresholds and representation levels of the uniform quantizer Qu(x). Corresponding values ti and yi of the companding quantizer Q(x) could be determined as the solutions of the following equations: c(ti) = tu,i = −1 + 2i N , c(yi) = yu,i = −1 + 2i − 1 N . (5) There are several ways how to choose the compressor function c(x) for compression law. In practice, a piecewise linear approximation of the logarithmic compression characteristic is used. There are two different ways. In North America, a µ-law compression characteristic is used, which is defined as follows: c(x) =   xmax ln(1+µ) ln ( 1 + µ x xmax ) , 0 ≤ x ≤ xmax − xmax ln(1+µ) ln ( 1 − µ x xmax ) , −xmax ≤ x ≤ 0 . (6) Substituting (1), (5) and (6) in (3) and (4), and considering that yN can be approximated with xmax, granular and overload distortions are defined as: Dg(Q) = σ2 ln2(1 + µ) 3N2 [ 1 µ2 x2max σ2 + xmax σ √ 2 µ + 1 ] , (7) Dol(Q) = σ 2e− √ 2xmax σ . (8) Since we now know how to calculate total distortion for quantization of a Laplacian source that has variable average power in a wide range: D(Q) = σ2 ln2(1 + µ) 3N2 [ 1 µ2 x2max σ2 + xmax σ √ 2 µ + 1 ] + σ2e− √ 2xmax σ , (9) 118 A.V. Mosic, Z.H. Peric, S.R. Panic we can find the signal power-to-total-distortion ratio (dB), which is denoted as SQNR: SQNR = 10 lg σ2 D(Q) = 10 lg 1 ln2(1+µ) 3N2 [ 1 µ2 x2max σ2 + xmax σ √ 2 µ + 1 ] + e− √ 2xmax σ . (10) On the basis of this expression we will design the desired model below. 3 Switching nonuniform scalar quantization and numerical re- sults for µ-logarithmic compandor Classical quantizer with µ-law compression characteristic (see Fig. 1, µ = 255) has limited range of input variances. We will solve that problem with switching quantization application. One simple technique is switched codebook adaptive scalar quantization. The basic scheme of robust and switched codebook adaptation is shown in [8]. This technique uses a classifier that looks at the contents of the input frame buffer and decides that the next block of samples belongs to a particular statistical class of samples from a finite set of K possible classes. Namely, the index specifying the class is used to select a particular codebook from a redesigned set of K codebooks. In addition, this index is transmitted as side information to the receiver. Then, each sample in the block is encoded by the scalar quantizer, which performs a search through the selected codebook. One frame has length of M. The index to identify the class is sent on the end of block. If each of the K codebooks has size N, the bit rate per sample is: R = log2 N + log2 K M . (11) Codebook size N depends on number of bits that are used for the encoding n. The relation between N and n is N = 2n, where n is the number of bits per sample. We will use this switching technique for our problem solving. We have K codebooks, i.e., K nonuniform scalar quantizers designed for particular values σ0j to cover input power range σ20j/σ 2 0 ∈ [σ 2 1j/σ 2 0,σ 2 2j/σ 2 0),where σ0 denotes referent value of input power and ∪ K j=1[σ 2 1j/σ 2 0[dB], σ22j/σ 2 0j[dB]) = [−20,20). Maximal amplitude for each quantizer xmaxj (each codebook j) is chosen in a way, that for each input power range σ20j/σ 2 0 ∈ [σ 2 1j/σ 2 0,σ 2 2j/σ 2 0) the total distortion has a minimum. The procedure is as follows: We optimize total distortion (9) to have a minimum. The optimization is going over parameter c, witch denotes ratio xmax/σ. After finding copt, for corresponding µ, which satisfies the following term: ∂D(Q) ∂c = 0 ⇒ c = copt. (12) We can easily evaluate xmaxj for each input power range σ20j/σ 2 0 ∈ [σ 2 1j/σ 2 0σ 2 2j/σ 2 0), from the expression xmaxj = coptσ0j. Each particular value σ0j can be represented as σ0j = kjσ0, where kj is called adaptation factor. During the switched quantizer design, a particular type of memory is needed. Each input class j = 1,2, . . . ,K requires one quantizer, for which we know adaptation factor kj and input power range [σ21j/σ 2 0,σ 2 2j/σ 2 0) for which the quantizer is designed. Also we have to store in memory the corresponding µ and copt. First, let us examine switched codebook adaptive scalar quantization model with only one quantizer present. Here, only parameter that can be optimized, for achieving high quality of transmission by increasing SNRQ, in a wide range of signal volumes (variances) with respect to Switched Nonuniform and Piecewise Uniform Scalar Quantization of Laplacian Source 119 it’s necessary robustness over a broad range of input variances is the ľ parameter in expression for SNRQ. Parameter µ can be optimized, for the case when expression for SNRQ has his maximum, which means that expression (9) for total distortion should have his minimum. Opti- mization of total distortion is derived in two steps. First, we accomplish adaptation on maximal amplitude of input signal, or the optimization for parameter c in corespondents to µ, which is described as: ∂D(Q) ∂c = 0 ⇒ c = copt(µ). (13) Then in the second step, we find required µopt, for witch total distortion should have his minimum, which is described as ∂D(Q) ∂µ ∣∣∣∣ c=copt(µ) = 0 ⇒ µ = µopt, D(Q)(µopt) = Dmin(Q). (14) These two steps can be represented as the following equation system: ∂D(Q) ∂c = σ2  −√2e−√2c + ( 2c µ2 + √ 2 µ ) ln2(1 + µ) 3N2   = 0 (15) ∂D(Q) ∂µ ∣∣∣∣ c=copt(µ) = σ2  2 ( 1 + c2opt(µ) µ2 + √ 2copt(µ) µ ) ln(1 + µ) 3N2(1 + µ) − ( 2c2opt(µ) µ3 + √ 2copt(µ) µ2 ) ln2(1 + µ) 3N2   = 0. (16) For N1 = 128 and N2 = 256, numerical solutions for presented systems are copt1 = 8.8, µopt1 = 15 and copt2 = 9.9 and µopt2 = 17, respectively. If there are not restrictive limitations about memory size and sample bit rate for the transmission system, then there is a possibility to choose optimal number of quantizers in our model, for which we can achieve high quality measured by SQNR, in a wide range of signal volumes (variances) with respect to it’s necessary robustness over a broad range of input. If we increase number of quantizers K, there is a way to flatten the SQNR dependence of input power in such a way that, if the memory size isn’t the limiting factor, with data compression being disregarded, we will achieve a signal-to-noise ratio that does not have a large variation during input power changes which is shown in Figs 1 and 2. In Fig 2, we can see that SQNR varies from it’s peak value, for maximum 0.282 dB and 0.313 dB for each input power range [σ21j/σ 2 0,σ 2 2j/σ 2 0), ∪ K j=1[σ 2 1j/σ 2 0[dB],σ 2 2j/σ 2 0j[dB]) = [−20,20), for which the quantizer is designed, in case of codebook size of 128 and 256, with 16 codebooks. There is a conclusion, that if we want to satisfy the same standard for varying of SQNR in twice larger input power range of [-40dB,40dB], we will have to use same codebook size for 32 codebooks. If we want to satisfy less restrictive standards of SQNR variance for each input power range [σ21j/σ 2 0,σ 2 2j/σ 2 0), we can use smaller number of codebooks, and if we want to achieve smaller peak value of SQNR, we can use smaller size of each codebook, for each input power range. If we analyze bit sample rate in function of frame length with respect to number of quantizers K, we can se that for relatively small frame length of 80 samples, bit sample rate rapidly convergates to the value of bit sample rate of transmission without side information. So we can derive conclusion that memory size is much more restrictive limitation for multi-quantizer implementation, than sample rate is. 120 A.V. Mosic, Z.H. Peric, S.R. Panic From Fig. 2, we can see that presented nonuniform switched quantizer with optimized µ outperform classical µ = 255 switched quantizer characteristic for 3 dB and 2.7 dB in the cases of N = 128 and N = 256, respectively. 4 Switched piecewise uniform scalar quantization and numerical results for µ-logarithmic compandor This paper utilizes the basic concept of the Jayant quantizer model in order to provide the development of the adaptive piecewise uniform scalar quantizer [4]. Particularly, the model avails the Jayant manner of maximum amplitude adaptation, which means according to the one word memory. Finally, since one of the main goals when designing quantizers is to provide as high as possible quality, i.e. as low as possible distortion, an analysis will be conducted in order to provide optimal values of µ. In this section, it is showed that segmental µ-law better than method presented in Section 3, when the required hardware solution because they can be realized using linear electronic circuits, and provide almost the same results for quality. Switched piecewise uniform scalar quantization of memoryless Laplacian source is asymptotically analyzed for the case where the power of input signal varies in a wide range. One possible solution for encoder design is given for the same quantizer. Switched quantization is used in order to give a higher quality in a wide range of signal volumes (variances). These systems, although not optimal, may have asymptotic performance arbitrarily close to the optimum. Furthermore, their analysis and implementation can be simpler than those of optimal systems. We also define granular distortion Dg(Q) and overload Dol(Q) distortion by: Dg(Q) = 2 L∑ i=1 ∆2i 12 Pi(σ) (17) Dol(Q) = 2 ∫ +∞ xmax (x − yL,nunif ) 2p(x)dx. (18) where are amplitudes quant in the i-th segment defines es: ∆i = xi − xi−1 N 2L (19) and yL,nunif is representation layer in the last cell of L-th segment: yL,nunif = xmax − ∆L 2 ≈ xmax (20) Finally p(x) is the PDF of inner signal on quantizer, which define probability Pi(σ) that quantum of signal belong the i-th segment: Pi(σ) = ∫ xi xi−1 p(x,σ)dx. (21) As we know D(Q) = Dg(Q) + Dol(Q). After sam basic mathematical operations we can get that: D(Q) = x2max 12(N/2L)2µ2 L∑ i=1 (1 + µ) 2(i−1) L ((1 + µ) 1 L − 1)2e− √ 2xmax µσ ((1+µ) i−1 L −1) × ( 1 − e− √ 2xmax µσ ((1+µ) i L −(1+µ) i−1 L ) ) + σ2e− √ 2xmax σ . (22) Switched Nonuniform and Piecewise Uniform Scalar Quantization of Laplacian Source 121 Optimizing the previous expression in the same manner as in Section 3, we get the results given in the Table 1 and Figure 2. In Figure 2 we can observe that our L = 4 switching piecewise uniform method with N1 = 128 and N2 = 256 outperforms the classical µ = 255 law method for 2.5 dB and 2.2dB, respectively. Comparatione is also made with G.711 standard, and it is also shown that our model satisfy the G.712 standard with 1 bit compression obtained. Our switching piecewise uniform model, with L = 8 segments and L = 16 segments (see table 1), gives almost same results as switching nonuniform method, with much more simpler realization structure of hardware. Figure 1: Improvement of quality of transmission (SNRQ), for model implementations with two quantizers over robust quantization. Figure 2: Comparatione of quality of transmission (SQNR), for model implementations with sixteen quantizers for standard and optimized value of parameter µ. 5 Conclusions and Future Works We have suggested switched nonuniform and piecewise uniform scalar quantzation of Lapla- cian source that solve the problem of variable input power in a wide range. We also have presented 122 A.V. Mosic, Z.H. Peric, S.R. Panic L SQNRN=128 SQNRN=256 2 32.76 38.21 4 34.35 39.96 8 34.73 40.37 16 34.82 40.48 64 34.85 40.51 128 34.85 40.52 Table 1: Comparison between values of SQNR of piecewise uniform scalar quantizers for different values of bitrate R, i.e. N1 = 128, µ1 = 15 and N2 = 256, µ2 = 17. how they can accomplish high quality of SNRQ by optimization on maximal amplitude of input signal, by optimization on parameter µ, and by adaptation on input variance range length. They can be applied for coding of speech signals and other continuous signals. The dependence of quality and robustness of quantized signals is analyzed over the broad range of input variances and corresponding number of codebooks with respect to system memory and sample bit rate. Presented switching piecewise uniform model gives almost same results as switching nonuniform method, with much more simpler realization structure of hardware. Bibliography [1] R. Gray, Quantization and Data Compression, Lecture Notes, Stanford University, 2004. [2] D. Hankerson, G. A. Harris, P. D. Jr. Johnson, Introduction information theory and data compression, 2nd Ed., CHAPMAN & HALL/CRC, 2004. [3] ITU-T, Recommendation G.711, Pulse Code Modulation (PCM) of Voice Frequencies, International Telecommunication Union, 1972. [4] N. S.Jayant, P. Noll, Digital Coding of Waveforms, Prentice-Hall, New Jersey, 1984. [5] Z. H. Perić, I. Djordjević , M. Stefanović, S. Bogosavljević, Combined Source and Channel Coding of Speech Signal in Wide Volume Range, Proceedings of the IASTED, Las Vegas, Nevada, USA, 1998. [6] Z. H. Perić, Quantization Optimizations of Speech Signal in Wide Volume Range, Elec- troniccs and Electrical Engineering, Vol.45, pp.41-48, 2003. [7] Z. H. Perić, J. Nikolić, An effective method for initialization of Lloyd-Max’s algorithm of optimal scalar quantization for Laplacian source, Informatica, Vol.18, pp.1-10, 2007. [8] Z. H. Perić, A. V. Mosić , S. R. Panić, Robust and switched nonuniform scalar quantiza- tion of Gaussian source in a wide dynamic range of power, Journal of Communications Technology and Electronics, AVT Journal, Vol.6, pp.74-84, 2008. [9] Z. H. Perić, A. V. Mosić , S. R. Panić, Coding Algorithm Based on Loss Compression using Scalar Quantization Switching Technique and Logarithmic Companding, Journal of Information Science and Engineering, Vol.26, pp.967-976, 2010. [10] K. Sayood, Introduction to data Compression, 3rd Ed., Elsevier Inc, 2006.