Lloyd-MAX算法的研究報(bào)告

1、 LloydMax 算法的總結(jié)摘 要：本文分析模擬數(shù)字信號(hào)轉(zhuǎn)變過程中抽象信號(hào)為離散時(shí)間，幅度連續(xù)，無記憶的 隨機(jī)信號(hào)的最佳量化問題。并對(duì)算法做了總結(jié)，應(yīng)用MATLAB編寫程序?qū)崿F(xiàn)該算 法，最后給出了運(yùn)用該程序進(jìn)行計(jì)算的幾個(gè)例子。關(guān)鍵詞：非均勻量化，失真度，LloydMax算法一引言 模數(shù)轉(zhuǎn)換要經(jīng)過抽樣，量化和編碼三個(gè)步驟。如下圖所示： SCH 編碼量化抽樣 為帶限的平穩(wěn)隨機(jī)過程，根據(jù)抽樣理論，我們可以對(duì)此隨機(jī)信號(hào)進(jìn)行奈圭斯特抽樣抽樣的輸出為 。它是與 等效的離散抽樣序列。經(jīng)過量化器以后，用L個(gè)電平值來表示次 序列，然后對(duì)此L個(gè)電平進(jìn)行編碼（假設(shè)為2進(jìn)制碼）。如果L為2的整數(shù)冪。則每個(gè)量化電平需

2、要的碼長(zhǎng)為： , 如果L不是2的整數(shù)冪。則上式為 。如果L個(gè)電平值不等概的情況下，我們可以用哈夫蔓編碼（又叫熵編碼）增加編碼效率。 然而，量化過程用到數(shù)據(jù)的壓縮，從而引進(jìn)了信號(hào)的失真。這種失真即為量化失真。我們用量化誤差來表示。本文的重點(diǎn)就是討論如何最大限度的減小量化誤差。二信息論的解釋 21失真度D 假定抽樣器的輸出序列為 ，量化器的輸出序列為 。 為不同的量化值。則兩個(gè)量化值的失真為：如果p=2 ；則此失真稱為均方失真。平均失真量為：如果x（t）是服從概率密度函數(shù)為p（x）的隨機(jī)信號(hào)，則：失真度D：如果用： 來表示。量化噪聲MSE：量化信噪比SNR：22率失真函數(shù)R（D）： 我們假定信源為

3、無記憶，連續(xù)幅度，它的幅度概率密度函數(shù)為p（x），則率失真函數(shù)R（D）的表示式為： 現(xiàn)在分析一下失真函數(shù)R（D）的意義。給定允許的失真度D 的情況下，尋求平均互信息量的最小值。在信源編碼過程中，該最小值的意義即為：給定一定的失真度D，存在最小的編碼碼長(zhǎng)R。即可尋求最小的量化電平數(shù)L。因此，進(jìn)行最佳量化設(shè)計(jì)的目標(biāo)可以看成以下問題： A：給定量化電平數(shù)L，尋求一種方法使得失真度D最小。 B：對(duì)于允許的失真度D，怎樣減少量化電平數(shù)L。本文章將討論問題A，即怎樣尋擇量化方法使D最小。量化的方法有很多，如權(quán)量化，自適應(yīng)量化，矢量量化和標(biāo)量量化。下面將對(duì)標(biāo)量量化進(jìn)行討論。三標(biāo)量量化的最佳量化問題在信源量化

4、中，如果我們知道量化器的輸入信號(hào)為概率密度函數(shù)為p（x），則量化器可以進(jìn)行優(yōu)化。同樣的，設(shè)輸入的信號(hào)概率密度函數(shù)為p（x），量化電平數(shù)設(shè)為L(zhǎng)。誤差函數(shù)設(shè)為 量化失真度為D。最佳量化器的目的即為減小D，為此，必須正確選取最佳量化電平值和量化區(qū)間 。Lloyd-Max算法就是最佳量化的好的實(shí)現(xiàn)方法。我們稱用Lloyd-Max算法的量化器為L(zhǎng)loyd-Max最佳量化器。為討論該算法，我們先介紹均勻量化 對(duì)于均勻量化，設(shè)量化電平為： ，其中，為量化臺(tái)階當(dāng)(k-1)x<k時(shí)，量化為假設(shè)均勻量化器的輸出為對(duì)稱的偶數(shù)個(gè)電平，則平均失真為：對(duì)求導(dǎo)，即可得到最小的量化失真。對(duì)上式求導(dǎo)為：給定一個(gè)p（x），

5、可以通過計(jì)算機(jī)編程設(shè)計(jì)得到最佳量化的矢量步長(zhǎng) 。Max首先對(duì)輸入信號(hào)為均值為0，單位方差的高斯信號(hào)進(jìn)行了計(jì)算。四LloydMax算法對(duì)于輸入信號(hào)分布函數(shù)p（x），量化輸出電平，量化電平數(shù)為，量化區(qū)間端點(diǎn)值為 當(dāng) 時(shí) 則量化為，.則失真度為： 對(duì) 和 進(jìn)行優(yōu)化以減小D，同時(shí)對(duì) 和 分別求導(dǎo)，得到下面兩個(gè)等式： 采用均方誤差則 ，所以可以得出： 這兩個(gè)式子可以通過計(jì)算機(jī)編程進(jìn)行連續(xù)的迭代計(jì)算，求出最佳的 和 ，以盡可能達(dá)到最小的D。五MATALB的編程實(shí)現(xiàn) 給定量化電平L和輸入信號(hào)概率密度函數(shù)p（x）和信號(hào)可能的最大值，最小值進(jìn)行迭代，求出最佳量化電平 和量化范圍 。并給出了一個(gè)結(jié)果。其中的失真度

6、D的絕對(duì)值過大，僅僅是為了說明情況，具體的計(jì)算可以根據(jù)需要的值進(jìn)行設(shè)置兩次迭帶中的D值之差，進(jìn)而計(jì)算出比較精確的結(jié)果。（程序清單和計(jì)算結(jié)果見附錄）六結(jié)束語(yǔ) LloydMax算法的特點(diǎn)是：量化電平集中在信號(hào)概率大的區(qū)域。在量化電平極小的情況下，均勻量化和非均勻量化的性能差不多。但是隨著量化電平數(shù)的增加，非均勻量化產(chǎn)生的失真度明顯比均勻量化小。根據(jù)信號(hào)的概率密度函數(shù)進(jìn)行量化，將時(shí)間離散，幅度連續(xù)的信號(hào)量化到各個(gè)離散的電平 上，它們對(duì)應(yīng)了相應(yīng)的概率 ?？梢該?jù)此進(jìn)行熵編碼，以期在相同的失真度條件下得到最小的碼長(zhǎng)R。 非均勻量化簡(jiǎn)單有效的實(shí)現(xiàn)且應(yīng)用在商業(yè)電話的對(duì)數(shù)量化器，根據(jù)人的語(yǔ)音特點(diǎn)，在低幅度時(shí)用比

7、較多的量化電平（量化臺(tái)階?。?，而在信號(hào)不常發(fā)生的大幅度電平值時(shí)，量化電平就大，常用的技術(shù)有美國(guó)的 律壓縮和歐洲的A-律壓縮。參考文獻(xiàn)：1：John.G.Proakis Digital Communication， 電子工業(yè)出版社影印版2：Theodore.S.Rappaport Wireless communication , 電子工業(yè)出版社影印版3：傅祖蕓 信息論基礎(chǔ) ，電子工業(yè)出版社4：沈振元，聶志泉，區(qū)雪荷 通信系統(tǒng)原理 西安電子科技大學(xué)出版社附錄：源程序清單：1：MAINfunction mainclear all;string1=input('Please input the

8、 pdf of the signal: ');string2=string1;disp('Please input the max amplitude of the signal:');xmax=input(' ');disp('Please input the min amplitude of the signal:');xmin=input(' ');disp('Please input the number of the quantization levels:');qsteps=input('

9、; ');lloyedmax(string2,xmax,xmin,qsteps)2：LloydMaxfunction d=lloyedmax(pdf,xmax,xmin,qsteps)g=inline(pdf);step=abs(xmax-xmin)/qsteps;for i=1:qsteps xvalue(i)=xmin+(i-0.5)*step;end;dold=1;dsum=0;j=0;while abs(dold-dsum)>0.01 j=j+1; x(j)=dsum; dold=dsum; xdomin(1)=xmin;xdomin(qsteps+1)=xmax; fo

10、r i=2:qsteps xdomin(i)=(xvalue(i-1)+xvalue(i)./2; end dsum=0; for i=2:qsteps+1 xstemp=xdomin(i-1):abs(xdomin(i)-xdomin(i-1)/100:xdomin(i); y=(xvalue(i-1)-xstemp).2).*g(xstemp); d=trapz(xstemp,y); dsum=dsum+d; end for i=2:qsteps+1 xstemp=xdomin(i-1):abs(xdomin(i)-xdomin(i-1)/100:xdomin(i); y1=xstemp.

11、*g(xstemp); y2=g(xstemp); d1=trapz(xstemp,y1); d2=trapz(xstemp,y2); xvalue(i-1)=d1/d2; figure(j); plot(xvalue,1:1:qsteps,'*',xdomin,1:1:qsteps+1,'x') ylabel('the compute numbers') xlabel('regions (x) and outputlevels (*)') end outputlevel=xvalue regions=xdomin distort

12、ion=dsumendj=j+1;x(j)=dsumoutputlevel=xvalueregions=xdominfigure(j);ylabel('the compute numbers')xlabel('regions (x) and outputlevels (*)')plot(xvalue,1:1:qsteps,'*',xdomin,1:1:qsteps+1,'x')figure(j+1)clear c;for i=2:j c(i-1)=x(i);endplot(1:1:j-1,c,'*')xlabel(

13、'the compute numbers')ylabel('everyone distortion')附錄：計(jì)算舉例：例子：1當(dāng) 時(shí)，量化電平數(shù)L=16； =2。輸入-20，+20 過程參數(shù)與圖示：說明：main為主函數(shù)，outputlevel為量化輸出電平值，regions為量化區(qū)域，distortion為量化失真度,x為每次迭代得出的量化失真度mainPlease input the pdf of the signal: 'exp(-x.2)/(2*4)/sqrt(2*pi*4)'Please input the max amplitude

14、of the signal: 20Please input the min amplitude of the signal: -20Please input the number of the quantization levels: 16outputlevel = -17.7225 -15.2575 -12.8047 -10.3710 -7.9677 -5.6117 -3.3209 -1.0969 1.0969 3.3209 5.6117 7.9677 10.3710 12.8047 15.2575 17.7225regions = -20.0000 -17.5000 -15.0000 -1

15、2.5000 -10.0000 -7.5000 -5.0000 -2.5000 0 2.5000 5.0000 7.5000 10.0000 12.5000 15.0000 17.5000 20.0000distortion =0.5209outputlevel = -16.7250 -14.3051 -11.9139 -9.5678 -7.2895 -5.1032 -3.0152 -0.9973 0.9973 3.0152 5.1032 7.2895 9.5678 11.9139 14.3051 16.7250regions = -20.0000 -16.4900 -14.0311 -11.

16、5878 -9.1694 -6.7897 -4.4663 -2.2089 0 2.2089 4.4663 6.7897 9.1694 11.5878 14.0311 16.4900 20.0000distortion =0.4092outputlevel = -15.7636 -13.4011 -11.0891 -8.8534 -6.7213 -4.7050 -2.7849 -0.9221 0.9221 2.7849 4.7050 6.7213 8.8534 11.0891 13.4011 15.7636regions = -20.0000 -15.5151 -13.1095 -10.7408

17、 -8.4286 -6.1963 -4.0592 -2.0063 0.0000 2.0063 4.0592 6.1963 8.4286 10.7408 13.1095 15.5151 20.0000distortion =0.3390F4 F6F8F10F12outputlevel = -9.8274 -8.3387 -6.9523 -5.6241 -4.3372 -3.0791 -1.8402 -0.6122 0.6122 1.8402 3.0791 4.3372 5.6241 6.9523 8.3387 9.8274regions =-20.0000 -9.4395 -7.9327 -6.

18、5133 -5.1524 -3.8325 -2.5406 -1.2661 0.0000 1.2661 2.5406 3.8325 5.1524 6.5133 7.9327 9.4395 20.0000distortion =0.1354x = 0.5209 0.4092 0.3390 0.2900 0.2536 0.2254 0.2029 0.1845 0.1692 0.1562 0.1451 0.1354 2 同樣條件，輸入為-60，60時(shí)的情況。 outputlevel = -10.1614 -8.5297 -7.0115 -5.6234 -4.3137 -3.0524 -1.8207 -

19、0.6052 0.6052 1.8207 3.0524 4.3137 5.6234 7.0115 8.5297 10.1614 regions = -60.0000 -9.8716 -8.1112 -6.5563 -5.1407 -3.8037 -2.5136 -1.2506 0.0000 1.2506 2.5136 3.8037 5.1407 6.5563 8.1112 9.8716 60.0000 distortion = 0.1332 3同樣函數(shù)，輸入為-20，20，L=8時(shí) outputlevel = -4.9505 -3.3100 -1.9443 -0.6436 0.6436 1.9

20、443 3.3100 4.9505 regions = -20.0000 -4.2345 -2.7073 -1.3360 0.0000 1.3360 2.7073 4.2345 20.0000 distortion =0.16514同樣函數(shù)，輸入為-60，60，L=32時(shí)outputlevel = -31.8333 -28.4797 -25.0944 -21.8405 -18.7849 -16.0125 -13.5971 -11.5539 -9.8169 -8.2835 -6.8751 -5.5461 -4.2694 -3.0277 -1.8083 -0.6014 0.6014 1.8083

21、3.0277 4.2694 5.5461 6.8751 8.2835 9.8169 11.5539 13.5971 16.0125 18.7849 21.8405 25.0944 28.4797 31.8333regions = -60.0000 -31.7736 -28.3413 -24.9372 -21.6598 -18.5750 -15.7669 -13.3094 -11.2202 -9.4397 -7.8702 -6.4306 -5.0723 -3.7663 -2.4941 -1.2422 0.0000 1.2422 2.4941 3.7663 5.0723 6.4306 7.8702

22、 9.4397 11.2202 13.3094 15.7669 18.5750 21.6598 24.9372 28.3413 31.7736 60.0000distortion =0.13085 輸入為-20，20，L=16時(shí)outputlevel = -18.7500 -16.2500 -13.7500 -11.2500 -8.7500 -6.2500 -3.7500 -1.2500 1.2500 3.7500 6.2500 8.7500 11.2500 13.7500 16.2500 18.7500regions = -20.0000 -17.5000 -15.0000 -12.5000 -10.0000 -7.5000 -5.0000 -2.5000 0.0000 2.5000 5.0000 7.5000 10.0