通信原理第7章

《通信原理》

第7章

楊鴻文

yanghong@1信源編碼/譯碼通信系統(tǒng)的目標(biāo)：在信宿端再現(xiàn)信源的輸出（V=U）本章研究信源編碼及譯碼假設(shè)信道理想：Y=X本章目標(biāo)：如何將信源輸出轉(zhuǎn)換為二進(jìn)制比特序列X如何以盡量少的比特?cái)?shù)做到這一點(diǎn)2本章內(nèi)容信源的分類離散信源、波形信源信息的度量熵、聯(lián)合熵、條件熵、互信息信源編碼定理信源編碼能做到多好？離散信源的編碼哈夫曼編碼波形信源的編碼抽樣、量化、編碼3信源的分類離散信源信源輸出是一個(gè)序列{Xl}，其中的Xl是離散隨機(jī)符號(hào)，一般進(jìn)制數(shù)為有限值M經(jīng)壓縮編碼后成為二進(jìn)制比特序列連續(xù)信源（波形信源）信源輸出是一個(gè)隨機(jī)過(guò)程X(t)經(jīng)采樣后成為時(shí)間離散取值連續(xù)的信源經(jīng)量化后成為M進(jìn)制離散信源經(jīng)編碼后成為二進(jìn)制比特序列4信源的數(shù)學(xué)表述離散無(wú)記憶信源所有Xl獨(dú)立同分布，其統(tǒng)計(jì)特性由概率分布P(X=xi)表述。{x1…xM}是X（任意一個(gè)Xl）的樣本空間相關(guān)序列信源序列{X1…XL}的統(tǒng)計(jì)特性由聯(lián)合概率分布P(X=xi)表述。X、xi是向量。X的樣本空間有ML個(gè)元素?？蓪視同一個(gè)樣本空間很大的大符號(hào)連續(xù)信源按隨機(jī)過(guò)程的方式來(lái)表述5什么是信息？信息就是信宿對(duì)于信源的輸出所不能確定的那部分內(nèi)容因?yàn)橥ㄐ畔到y(tǒng)使信源得到了信息，所以信宿才能確定出信源的輸出是什么信息量的多少就是不確定的程度，其數(shù)值就是熵6熵是對(duì)數(shù)概率的數(shù)學(xué)期望若隨機(jī)符號(hào)X的取值空間是{x1,x2,…,xM}，出現(xiàn)概率是{p1,p2,…,pM}。則熵定義為對(duì)數(shù)概率的數(shù)學(xué)期望7單位是bit為什么是熵是信息的度量？如果信源X只有兩種可能性，那么你顯然需要發(fā)送1bit來(lái)使信宿確定地知道X具體是哪個(gè)依次來(lái)看，如果信源X有M種可能性，其信息量應(yīng)該是log2Mbit例如考慮X=(X1,X2,…,XL)是一個(gè)長(zhǎng)為L(zhǎng)的二進(jìn)制序列，其元素獨(dú)立同分布，“0”出現(xiàn)的概率是p則X是M=2L進(jìn)制，貌似需要L比特來(lái)指示信源的輸出具體是哪一個(gè)序列但是，且慢下結(jié)論。貌似的事實(shí)未必是事實(shí)。8根據(jù)大數(shù)定理，如果L足夠大，那么我們基本上可以相信：信源輸出應(yīng)該只有pL個(gè)0數(shù)出L中出現(xiàn)pL個(gè)0的組合數(shù)，將發(fā)現(xiàn)總個(gè)數(shù)幾乎就是2LH[X]—就是說(shuō)，只需LH[X]bit就可以基本上保證能讓信宿知道：信源輸出的序列具體是哪個(gè)。如果你對(duì)以上論證中出現(xiàn)的基本上、應(yīng)該、幾乎這樣的表述不很放心，請(qǐng)參閱信息論教材，那里將通過(guò)嚴(yán)格的數(shù)學(xué)語(yǔ)言徹底打消你的顧慮。9等概符號(hào)熵最大離散隨機(jī)符號(hào)在等概時(shí)熵最大其中等式僅在所有pi=1/M時(shí)成立對(duì)于等概符號(hào)，M越大，熵越大10二元熵函數(shù)11聯(lián)合熵對(duì)于兩個(gè)隨機(jī)符號(hào)X、Y，將(X,Y)整體看成一個(gè)大符號(hào)，可得這個(gè)大符號(hào)的熵為12關(guān)于記號(hào)“概率”的規(guī)范寫法是P(X=x)。在不產(chǎn)生歧義的情況下，我們也經(jīng)常簡(jiǎn)寫為P(X)或P(x)的情況下。其中的小差別是：P(X)表示“X的出現(xiàn)概率”，數(shù)值未必確定（要看X具體等于什么）P(x)表示“X出現(xiàn)x的概率”（X已經(jīng)明確為x）13條件熵H[X|Y=y]對(duì)于兩個(gè)隨機(jī)符號(hào)X、Y，在已知Y=y的條件下，X仍然可能是隨機(jī)的。此條件下X的分布是條件分布P(X|Y=y)，由此可得X在條件Y=y下的熵為注意是對(duì)X求數(shù)學(xué)期望，Y已經(jīng)固定為y，不再是隨機(jī)的。14條件熵H[X|Y]對(duì)于兩個(gè)隨機(jī)符號(hào)X、Y，給定Y=y，可以得到H[X|Y=y]（一個(gè)確定的數(shù)，是y的函數(shù)）。對(duì)于不同的y，可能有不同的H[X|Y=y]值。對(duì)Y取平均的結(jié)果是：X相對(duì)于各種Y取值的條件熵15注意不是條件概率條件熵的含義H[X]是你對(duì)X的不確定程度H[X|Y=y]是知道Y是y之后，還剩下的對(duì)X的不確定程度有可能變大。完全有可能：得到一個(gè)與X有關(guān)系的Y的具體情報(bào)Y=y后，你發(fā)現(xiàn)原本所關(guān)注的問(wèn)題X變得更為撲朔迷離16條件熵的含義H[X|Y]是：如果你知道Y（先不論知道具體是哪個(gè)y），平均而言，你對(duì)X的判斷所剩余的不確定程度可以證明：H[X|Y]≤H[X]，等號(hào)在獨(dú)立時(shí)成立總的來(lái)說(shuō)，得到一個(gè)有關(guān)X的情報(bào)Y，總體上有助于你對(duì)X的判斷如果Y和X毫無(wú)關(guān)系，那么得知Y無(wú)助于改善你對(duì)X的判斷。此時(shí)H[X|Y]=H[X]17與聯(lián)合熵的關(guān)系你對(duì)XY整體的不確定程度=你對(duì)X的不確定程度+如果你完全知道X的話，Y額外存在的不確定程度你對(duì)XY整體的不確定程度可能小于各自不確定程度之和：因?yàn)閮烧哂嘘P(guān)系，知道其中一個(gè)能使你對(duì)另一個(gè)多少有所判斷。除非兩者沒(méi)有關(guān)系推論：隨機(jī)序列獨(dú)立時(shí)的熵最大18互信息你對(duì)X的不確定程度是H[X]，觀察到Y(jié)后使你對(duì)X的不確定程度減少了I[X;Y]，即：I[X;Y]是你觀察到Y(jié)后，所獲得的關(guān)于X的信息量19互信息非負(fù)對(duì)于你所關(guān)注的X，平均而言，得知情報(bào)Y最多幫不上忙（若它們獨(dú)立），但不可能幫倒忙20互信息的對(duì)稱性根據(jù)Y能獲得的關(guān)于X的信息量=根據(jù)X能獲得的關(guān)于Y的信息量21互信息小于熵根據(jù)Y的所獲得的關(guān)于X的信息量不可能超過(guò)Y自身的信息量，也不可能超過(guò)X自身的信息量。等號(hào)發(fā)生在H[X|Y]=0或H[Y|X]=0時(shí)。即觀察到Y(jié)后可以完全已知X，或者觀察到X可以完全已知Y22互信息與聯(lián)合熵如果XY各自的不確定度之和超過(guò)他們聯(lián)合的不確定度，說(shuō)明二者是有聯(lián)系的。這部分差額是同時(shí)存在于X和Y中的共同信息。此時(shí)，觀察到XY其中的一個(gè)，對(duì)另一個(gè)所能判斷出的信息量就是這個(gè)差額（共有信息）23信源編碼定理通信系統(tǒng)的目的是讓信宿重現(xiàn)信源。凡是信宿能自己確定的東西，都不需要傳輸只需要傳輸信宿自己不能確定的部分。信宿所不能確定的那部分到底有多少？答案就是信源的熵香農(nóng)已經(jīng)嚴(yán)格證明：只要傳輸?shù)目偙忍乜倲?shù)大于等于信源總的熵（單位也是比特），就一定有辦法讓信宿再現(xiàn)信源的輸出24無(wú)失真信源編碼定理等長(zhǎng)編碼定理及變長(zhǎng)編碼定理所陳述的事實(shí)是：用等長(zhǎng)編碼的方法，或者用變長(zhǎng)編碼的方法，都可以使平均每信源符號(hào)的編碼輸出比特?cái)?shù)逼近每符號(hào)的信源熵H[X]，使得信宿幾乎可以100%復(fù)原出原始信源不可能存在任何一種壓縮算法，其輸出速率比H[X]更低，居然還能使信宿幾乎100%復(fù)原出原始信源。25限失真信源編碼定理如果我們可以接受：信宿的復(fù)原結(jié)果和信源原始輸出之間有不超過(guò)D的失真度，那么：最低速率可以壓縮到某個(gè)信息論可以算出的數(shù)值R，其值是D的函數(shù)：R(D)函數(shù)不可能存在任何一種壓縮算法，其輸出速率比這個(gè)R更低，居然還能使失真不超過(guò)D。26無(wú)失真編碼的一個(gè)經(jīng)典例子：

哈夫曼編碼哈夫曼編碼是變長(zhǎng)編碼的一種變長(zhǎng)編碼的基本思路根據(jù)信源輸出信號(hào)出現(xiàn)概率的不同來(lái)選擇碼字，出現(xiàn)概率大的用短碼，出現(xiàn)概率小的用長(zhǎng)碼，以使平均編碼長(zhǎng)度最短，從而提高編碼效率需解決讓信宿正確斷句的問(wèn)題：每個(gè)碼字長(zhǎng)度不同，信宿不能預(yù)先知道來(lái)的是哪個(gè)碼字27哈夫曼編碼的思路—斷句問(wèn)題

無(wú)前綴編碼：任何碼字都不是其他碼字的前綴例如：網(wǎng)友的ID是變長(zhǎng)的（有長(zhǎng)有短）。不使用標(biāo)點(diǎn)符號(hào)，將N個(gè)ID串起來(lái)，無(wú)法保證唯一正確地辨識(shí)。但如果規(guī)定：任何一個(gè)ID不得成為其他ID的前綴，就不會(huì)有問(wèn)題28哈夫曼編碼—字長(zhǎng)與概率匹配按小概率合并字符集M-1進(jìn)制符號(hào)的編碼中，若將某個(gè)符號(hào)分裂為兩個(gè)，新編碼應(yīng)該是原編碼后續(xù)1個(gè)比特來(lái)識(shí)別這兩個(gè)新的符號(hào)將M進(jìn)制符號(hào)中出現(xiàn)概率最小的兩個(gè)看成是一個(gè)符號(hào)進(jìn)一步細(xì)分的結(jié)果。于是M進(jìn)制變成M-1進(jìn)制。如此不斷進(jìn)行，直至成為二進(jìn)制，編碼為0、1。然后按合并路線陸續(xù)添續(xù)上1、029哈夫曼編碼舉例30略去重復(fù)的節(jié)點(diǎn)：31限失真編碼：抽樣、量化、編碼抽樣：把時(shí)間連續(xù)波形變成時(shí)間離散序列這是一種典型方法，但不是唯一方法量化：把連續(xù)隨機(jī)變量變成M進(jìn)制的離散隨機(jī)變量編碼：把M進(jìn)制符號(hào)序列映射為比特序列可以采用某種壓縮編碼，此處我們不考慮這個(gè)問(wèn)題32抽樣定理設(shè)x(t)限帶于fH，設(shè){xk}是對(duì)x(t)的等間隔抽樣：xk=x(kTs)，則當(dāng)Ts≤1/(2fH)時(shí)，可以用序列{xk}完全算出函數(shù)x(t)在任意t處的值。計(jì)算公式為上述計(jì)算的實(shí)際實(shí)現(xiàn)方法是：讓理想抽樣的信號(hào)經(jīng)過(guò)LPF33原理理想抽樣的信號(hào)是LPF（高度為Ts）的沖激響應(yīng)是因此LPF輸出是34另一方面，理想抽樣的信號(hào)是其頻譜為經(jīng)過(guò)LPF（高度為Ts）后的輸出是X(f)35帶通抽樣帶通信號(hào)的頻譜36帶通抽樣抽樣后的頻譜是局部圖形37帶通抽樣抽樣率fs最小的情形結(jié)論：若最高頻率是帶寬的整倍數(shù)，則最小采樣率是帶寬的2倍38帶通抽樣若最高頻率不是帶寬的整倍數(shù)將S(f)的頻帶當(dāng)作是[fL-D,fH]，則帶寬B’=B+D滿足最高頻率是帶寬整倍數(shù)的關(guān)系。39帶通抽樣定理帶通信號(hào)的最小抽樣率是2(B+D)，其中D是能讓fH被(B+D)整除的最小非負(fù)實(shí)數(shù)。40量化量化器Q是一個(gè)階梯函數(shù)，它將連續(xù)取值的自變量x映射為離散取值的函數(shù)值y具體規(guī)則是稱：(xk-1,xk)為量化區(qū)間，{yk}為量化區(qū)間的量化電平或代表點(diǎn)，{xk}為分層電平或量化邊界41注意：此Q(x)不是高斯概率密度積分的那個(gè)Q函數(shù)量化函數(shù)示例量化函數(shù)也可圖示為量化器將區(qū)間(xk-1,xk)內(nèi)的x值一律不加區(qū)分地替換為一個(gè)數(shù)值yk量化是不可逆的過(guò)程這個(gè)不可逆的信號(hào)失真稱為量化誤差，定義為

可將量化器的輸出看成是：原始信號(hào)x疊加了一個(gè)量化噪聲eq量化誤差44雖然Q是確定函數(shù)，但因?yàn)檩斎離是隨機(jī)變量，所以量化誤差eq也是隨機(jī)變量，其功率稱為均方誤差，或量化噪聲功率量化誤差45均勻量化指：所有量化間隔都是等長(zhǎng)區(qū)間(D)。即：量化邊界均勻安排量化電平處于每個(gè)量化區(qū)間的中點(diǎn)均勻量化46均勻量化若輸入x是均勻分布的隨機(jī)變量，則量化噪聲功率為信號(hào)功率是量化信噪比是47最優(yōu)量化器就一般情形而言，均勻量化未必是最佳的：Nq是量化邊界和代表點(diǎn)的函數(shù)，該函數(shù)的極小點(diǎn)未必就是均勻量化所規(guī)定的邊界和代表點(diǎn)。最優(yōu)量化器的解與輸入x的概率分布有關(guān)?？梢宰C明：若x是均勻分布，則均勻量化是最佳量化48對(duì)數(shù)壓擴(kuò)目的：改善語(yǔ)音信號(hào)動(dòng)態(tài)范圍過(guò)大的問(wèn)題量化器如果按小信號(hào)設(shè)計(jì)量化間隔，按大信號(hào)設(shè)計(jì)幅度范圍，則量化比特?cái)?shù)過(guò)大可改善的原因?qū)π⌒盘?hào)來(lái)說(shuō)，量化器的幅度過(guò)于浪費(fèi)；對(duì)大信號(hào)來(lái)說(shuō)，量化間隔過(guò)于浪費(fèi)有浪費(fèi)，就應(yīng)該有節(jié)約的辦法49對(duì)數(shù)壓擴(kuò)方法：將輸入信號(hào)通過(guò)一個(gè)稱為“壓縮器”的部件，進(jìn)行類似于ln(1+Ax)的非線性放大大信號(hào)放大倍數(shù)小小信號(hào)放大倍數(shù)大效果是最大幅度和平均幅度(有效值)的比值（稱為峰均比）被壓縮然后做均勻量化收端對(duì)重建的量化值解壓縮（擴(kuò)張）50對(duì)數(shù)量化這一點(diǎn)也等價(jià)于：不做壓擴(kuò)，直接對(duì)輸入信號(hào)進(jìn)行非均勻量化小信號(hào)量化的細(xì)一些，以保證量化信噪比大信號(hào)量化的粗一些，以縮減比特?cái)?shù)51標(biāo)準(zhǔn)PCM采用A律十三折線來(lái)近似實(shí)現(xiàn)對(duì)數(shù)壓擴(kuò)等價(jià)的非線性量化器為：1比特分出正負(fù)兩個(gè)區(qū)間3個(gè)比特分出8個(gè)非均勻段落4個(gè)比特在段落內(nèi)均勻量化最終速率：64kbps52對(duì)數(shù)量化體現(xiàn)在8個(gè)段落的劃分上53時(shí)分復(fù)用多個(gè)數(shù)據(jù)源經(jīng)過(guò)TDM后的總速率是各個(gè)數(shù)據(jù)源的速率之和標(biāo)準(zhǔn)范例：E1載波每路電話按8k取樣，取樣間隔是125ms，每個(gè)樣值用8比特表示將125ms分割成32個(gè)時(shí)隙，只用其中一個(gè)時(shí)隙來(lái)傳輸一路電話的8個(gè)比特共有32個(gè)時(shí)隙，用來(lái)傳30路標(biāo)準(zhǔn)PCM話音，其余兩個(gè)時(shí)隙用于隨路信令和同步32×64kbps構(gòu)成2.048Mbps54矢量量化