信息論 基礎(chǔ)理論與應(yīng)用第三版(傅祖蕓) 第5章 講義

第5章無失真信源編碼定理5.1編碼器5.2等長碼5.6變長信源編碼定理5.4等長信源編碼定理5.5變長碼2021/6/271

信息通過信道傳輸?shù)叫潘薜倪^程。要做到既不失真又快速地通信，需要解決兩個(gè)問題：信源編碼:

在不失真或允許一定失真條件下，提高信息傳輸率.信道編碼:

在信道受到干擾的情況下，增加信號的抗干擾能力，同時(shí)又使得信息傳輸率最大.最佳編碼：一般來說，抗干擾能與信息傳輸率二者相互矛盾。而編碼定理理論上證明，至少存在某種最佳的編碼能夠解決上述矛盾，做到既可靠又有效地傳輸信息。信源編碼：信源雖然多種多樣，但無論是哪種類型的信源，信源符號之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。信源編碼的目的就是要減少冗余，提高編碼效率。

引言2021/6/272研究方法研究信源編碼時(shí)，將信道編碼與譯碼看成是信道的一部分，從而突出信源編碼；研究信道編碼時(shí)，將信源編碼與譯碼看成是信源與信宿的一部分，從而突出信道編碼。5.1編碼器編碼器：

對信源的符號按一定的數(shù)學(xué)規(guī)則進(jìn)行的變換。它可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源S，其符號集為而信道所能傳輸?shù)姆柤癁?/p>

2021/6/273

編碼器功能：用符號集X中的元素，將原始信源的符號變換為相應(yīng)的碼字符號，編碼器輸出符號集為

(碼或碼書)

稱為碼字，li

為碼字的碼元個(gè)數(shù)（碼字長度，碼長）。碼字集合C稱為碼或碼書。2021/6/274

若要實(shí)現(xiàn)無失真編碼，這種映射應(yīng)是一一對應(yīng)的可逆映射。編碼的形式化描述：

從信源符號到碼符號的一種映射或：2021/6/2751、二元碼與r元碼

2元碼:碼符號集X={0,1}.如果將信源通過二元信道傳輸，必須將信源編成二元碼，這是最常用的一種碼。

r元碼:碼符號集有r個(gè)符號的編碼。2、等長碼與變長碼等長碼:一組碼中所有碼字的長度都相同。變長碼:一組碼中所有碼字的長度各不相同。

碼的分類及定義2021/6/2763、非奇異碼與奇異碼非奇異碼:一組碼中所有碼字都不相同。

奇異碼:一組碼中有相同的碼字。2021/6/2774、同價(jià)碼同價(jià)碼:

碼符號集中每個(gè)碼符號所占的傳輸時(shí)間都相同(大多數(shù)情況)。變長碼中每個(gè)碼字的傳輸時(shí)間就不一定相同。（摩爾斯電報(bào)碼，點(diǎn)-劃所占傳輸時(shí)間不同）5、碼的N次擴(kuò)展

若某碼C，它把信源S中的符號一一變換成碼C中的碼字，則碼C的N次擴(kuò)展碼是所有N個(gè)碼字組成的碼字序列的集合B:S擴(kuò)展2021/6/278碼C碼B擴(kuò)展信源擴(kuò)展碼N次擴(kuò)展N次擴(kuò)展2021/6/279[例]

設(shè)信源S的概率空間為：

若通過—個(gè)二元信道進(jìn)行傳輸，須把信源符號變換成0，1符號組成的碼符號序列(二元序列)。采用如下二元碼，如下表所示（q=4）：試求碼的二次擴(kuò)展碼。2021/6/2710信源S的二次擴(kuò)展信源：則碼的二次擴(kuò)展碼為：2021/6/27116、唯一可譯碼(單義可譯碼）由碼構(gòu)成的任意一串有限長的碼符號序列只能被唯一的譯成所對應(yīng)的信源符號序列。否則,就為非惟一可譯碼或非單義可譯碼。

例：對于二元碼，當(dāng)任意給定一串碼字序列，例如…10001101…只可唯一地劃分為1,00,01,1,01，因此是惟一可譯碼；而對另一個(gè)二元碼，當(dāng)碼字序列為…01001…可劃分為0,10,01或01,0,01，所以是非惟一可譯的。2021/6/2712唯一可譯碼的條件

1）不同的信源符號變換成不同的碼字(非奇異碼)；

2）任意有限長的信源序列所對應(yīng)的碼元序列各不相同.

即:碼的任意有限長N次擴(kuò)展碼都是非奇異碼。Or:

碼符號序列的反變換也唯一的（擴(kuò)展碼非奇異）

原因：若要使某一碼為惟一可譯碼，則對于任意有限長的碼符號序列，必須只能被惟一地分割成一個(gè)個(gè)的碼字，才能實(shí)現(xiàn)唯一的譯碼。2021/6/2713無失真的編碼的一般條件

1）碼字與信源符號之間一一對應(yīng)（非奇異碼）；

2）碼符號序列的反變換也唯一的（擴(kuò)展碼非奇異）。即：編碼必須是唯一可譯碼。否則，就會(huì)引起譯碼的錯(cuò)誤與失真。等長碼是唯一可譯碼的條件

若等長碼是非奇異碼，則它的任意有限長N次擴(kuò)展碼一定也是非奇異碼。因此，等長非奇異碼字一定是唯一可譯碼,因?yàn)椴捎霉潭ㄩL度劃分碼字序列.5.2等長碼2021/6/27141）若對每個(gè)信源符號進(jìn)行等長編碼，則必須滿足:

其中:l是碼長，r是碼符號集的碼元數(shù)，q信源符號數(shù)。2）若對信源的N次擴(kuò)展信源進(jìn)行編碼，必須滿足:表示平均每個(gè)信源符號所需的碼符號個(gè)數(shù)。即

為了使等長碼為非奇異碼（唯一可譯碼），那么:2021/6/2715例證：根據(jù)依賴關(guān)系，信源符號平均所需碼符號數(shù)可減少。例設(shè)信源而其依賴關(guān)系為：1）若不考慮符號間的依賴關(guān)系，可得每符號碼長l＝2；2）若考慮符號間的二元依賴關(guān)系，可作二次擴(kuò)展信源進(jìn)行分析。根據(jù)條件概率僅有4項(xiàng)的概率不為零，可得擴(kuò)展信源的碼長l’=2，而每個(gè)信源符號的平均碼長為l’/N=1

。2021/6/27165.4等長信源編碼定理給出了等長信源編碼所需碼長的極限值。定理等長信源編碼定理

一熵為H(S)的離散無記憶信源，若對其N次擴(kuò)展信源進(jìn)行等長r元編碼，碼長為l，對于任意大于0，只要滿足當(dāng)N足夠大時(shí)，則可以實(shí)現(xiàn)幾乎無失真編碼，反之，若：則不可能實(shí)現(xiàn)無失真編碼，當(dāng)N趨向于無窮大時(shí)，譯碼錯(cuò)誤率接近于1。2021/6/2717分析：定理中的條件式可寫成

左邊:長為l

的碼符號（碼字）所能載荷的最大信息量；

右邊:長為N的信源符號序列平均攜帶的信息量。因此，定理說明了：只要碼字傳輸?shù)淖畲笮畔⒘看笥谛旁葱蛄袛y帶的信息量，則可以實(shí)現(xiàn)無失真編碼。編碼后信源的信息傳輸率

令：可見，只有編碼后信息傳輸率

，才能實(shí)現(xiàn)無失真編碼。(編碼后，平均每個(gè)信源符號承載的信息量)2021/6/2718最佳編碼效率：

由定理知，編碼效率移項(xiàng)后，2021/6/2719當(dāng)信源符號自信息量的方差和確定時(shí)，只要N足夠大，就可以實(shí)現(xiàn)允許錯(cuò)誤概率：這時(shí)要求序列長度滿足：（任意一正數(shù)）信源序列長度N

一般情況下，在已知信源熵的情況下，信源序列長度N的選擇，與最佳編碼效率和允許錯(cuò)誤概率有關(guān)。可以證明：2021/6/2720若采用等長二元編碼，要求編碼效率，允許錯(cuò)誤率則：例：設(shè)離散無記憶信源：2021/6/27211、唯一可譯變長碼5.5變長碼優(yōu)勢：容易實(shí)現(xiàn)效率很高的編碼。變長碼也必須是唯一可譯碼，才能實(shí)現(xiàn)無失真編碼。碼1是一個(gè)奇異碼，故不是唯一可譯碼；碼2也不是唯一可譯碼，因?yàn)槭盏揭淮蛄校瑹o法唯一譯出對應(yīng)的原符號序列，如01000，即可譯作s4s3s1,也可譯作s4s1s3,s1s2s3或s1s2s1s1；2021/6/2722碼2本身不是奇異碼，但從有限長的碼符號序列是奇異碼。如果把碼2的2次擴(kuò)展碼寫出，則會(huì)發(fā)現(xiàn)：

S1S3的擴(kuò)展碼字為：000；

S3S1的擴(kuò)展碼字也為：000

所以，當(dāng)出現(xiàn)000序列時(shí)候，不能唯一地確定信源符號。碼3和碼4都是唯一可譯的，但碼3和碼4也不太一樣。碼4稱作逗點(diǎn)碼，只要收到1，就可以立即作出譯碼；而碼3不同，當(dāng)收到一個(gè)或幾個(gè)碼時(shí)，必須參考后面的碼才能作出判斷。

100010010…2021/6/2723即時(shí)碼接收端收到一個(gè)完整的碼字后，就能立即進(jìn)行譯碼，無須參考后面的碼字就可以作出唯一判斷（譯碼）。對于非即時(shí)碼，接收端收到一個(gè)完整的碼字后，還需等后續(xù)碼元接收后才能判斷是否可以唯一譯碼。非延長碼（前綴條件碼）

若碼C中，沒有任何完整的碼字是其他碼字的前綴，即設(shè)是碼C中的任意碼字，而它不是其他碼字（j>m）的前綴，則此碼為非延長碼（或前綴條件碼）。！！顯然：即時(shí)碼等價(jià)于前綴條件碼（非延長碼）。2021/6/2724碼3：s1的碼字是s2,s3,s4的碼字的前綴（詞頭）；s2的碼字是s3,s4的碼字的前綴；s3的碼字是s4的碼字的前綴；當(dāng)譯碼時(shí)，接受到一個(gè)完整碼字后，不能馬上譯碼，還需考察后續(xù)碼元的情況才能進(jìn)行正確譯碼；如：100010010…可譯碼為：s4s3？…因此，碼3不是即時(shí)碼；但確是唯一可譯碼。碼4：碼本中的任何一個(gè)碼字都不是其他碼字的前綴。當(dāng)譯碼時(shí)，接受到一個(gè)完整碼字后，不需要等待后續(xù)碼元的情況即可正確譯碼；如：100010010…可譯碼為：s1s4s3…因此，碼4是即時(shí)碼，也是唯一可譯碼。2021/6/2725因此，對于碼C：若其為唯一可譯碼，則必為非奇異碼；若其為即時(shí)碼，則必是唯一可譯碼；反之，作為唯一可譯碼，則不一定是即時(shí)碼。所有的碼非奇異碼唯一可譯碼即時(shí)碼（非延長碼）2021/6/27262、即時(shí)碼（非延時(shí)碼）的樹圖構(gòu)造法

對于給定碼字集合C，可用碼樹來描述。同時(shí)，樹圖法可構(gòu)造即時(shí)碼。01001111010010001碼4的樹圖描述2021/6/2727

在每個(gè)節(jié)點(diǎn)上都有r個(gè)分枝的樹稱為整樹（滿樹），否則稱為非整（滿）樹。

01

01

01

01010101

0101010101010101等長碼二元碼樹（整樹）樹根——碼字的起點(diǎn)樹枝數(shù)—碼符號數(shù)終端節(jié)點(diǎn)—碼字階數(shù)—碼長中間節(jié)點(diǎn)2021/6/2728012012012012012012三元碼樹（整樹）滿樹——變長碼01001111010010001非滿樹2021/6/2729非即時(shí)碼的樹圖中間節(jié)點(diǎn)安排為碼字1.樹圖中間節(jié)點(diǎn)不作為碼字；2.一旦某節(jié)點(diǎn)作為碼字，則不再繼續(xù)進(jìn)行分枝。這樣可保證每個(gè)碼字不同，且滿足前綴條件碼的條件。一般編碼方法選擇相應(yīng)節(jié)點(diǎn)作為碼字：不同的路徑上的分支，對應(yīng)了相應(yīng)的碼元符號，則可得到所編碼字。10001101001000構(gòu)造即時(shí)碼2021/6/2730編碼舉例（即時(shí)碼，編碼方式不同）都為即時(shí)碼，但編碼方式不唯一2021/6/2731編碼舉例（多元即時(shí)碼）2021/6/2732譯碼方法

因?yàn)槊恳淮a元對應(yīng)于一個(gè)的樹圖分枝路徑，則即時(shí)碼的樹圖可以用來譯碼。譯碼器系統(tǒng)對一串符號序列譯碼過程：1）首先從樹根出發(fā)，根據(jù)接收的第一個(gè)碼元符號來選擇應(yīng)走的第一條路徑；2）若沿著所選路徑走到某中間節(jié)點(diǎn)，再根據(jù)接收的第二個(gè)碼元符號來選擇第二條路經(jīng)；3）若又走到中間節(jié)點(diǎn)，再依次繼續(xù)選擇路徑，直到終端節(jié)點(diǎn)為止。這時(shí)，可根據(jù)所經(jīng)歷的枝路，判斷出所接收的碼字。4）重新返回樹根，再作下一個(gè)接收碼字的判斷。

這樣，便可將接收到的一串碼符號序列譯成信源符號序列。2021/6/27333、克拉夫特（Kraft）不等式定理對于碼符號為的任意r元即時(shí)碼

，若所對應(yīng)的碼長，則必定滿足：反之，若碼長滿足上式，則一定存在這樣的即時(shí)碼。*可以證明，對于唯一可譯碼也須滿足Kraft不等式。

這說明，其他唯一可譯碼并不比即時(shí)碼占優(yōu)。而即時(shí)碼很容易用樹圖法構(gòu)造，所以在討論唯一可譯碼時(shí)，只需要討論即時(shí)碼就可以了。定理若存在一個(gè)碼長為的唯一可譯碼，則一定存在一個(gè)同樣長度的即時(shí)碼。2021/6/2734例：設(shè)二進(jìn)制碼樹中S=(s1,s2,s3,s4),L1=1,L2=2,L3=2,L4=3,應(yīng)用Kraft不等式,得：不存在滿足這種Li的唯一可譯碼如果將各碼字長度改成L1=1,L2=2,L3=3,L4=3,則存在滿足這種Li唯一可譯碼0001101011011碼樹111000110101102021/6/2735設(shè)信源編碼后的碼字為：碼長為：碼的平均長度（平均碼長）為：5.6變長信源編碼定理（碼符號/信源符號）碼的平均長度信息傳輸率（碼率）：平均每個(gè)碼元攜帶的信息量，即編碼后信道的信息傳輸率：（比特/碼符號）2021/6/2736

若信道傳輸一個(gè)碼符號平均需要t秒鐘，則編碼后信道的每秒傳輸?shù)男畔⒘繛椋海ū忍?秒）由此可見：

平均碼長越短，信息傳輸效率越高。緊致碼（最佳碼）對于某一信源和某一個(gè)碼符號集合，若有一個(gè)唯一可譯碼，它的平均碼長小于其他唯一可譯碼的長度。無失真信源編碼的基本問題就是尋找緊致碼。2021/6/2737定理

若對一熵為H(S)的離散無記憶信源S進(jìn)行r元編碼，則總是可以找到一種無失真編碼方法構(gòu)成唯一可譯碼，使其平均碼長滿足：

說明：下界：平均碼長不能小于極限H(s)/logr,否則唯一可譯碼不存在。上界：給出了平均碼長的上界。但并不是說大于這個(gè)上界就不能構(gòu)成唯一可譯碼。而是說在上界范圍內(nèi)，可找到唯一可譯碼。2021/6/2738證明：1.下界證明：詹森不等式2021/6/2739因總可找到一種唯一可譯碼，其碼長滿足Craft不等式，所以則證得：由Craft不等式，此等式成立的充要條件：即：可見，只有當(dāng)能夠選擇每個(gè)碼長滿足上述等式時(shí)候，平均碼長才能夠達(dá)到這個(gè)下界值。2021/6/2740

由于li

必須為正整數(shù)，所以也必須為正整數(shù)。那么，當(dāng)該等式成立時(shí)，每個(gè)信源符號的概率分布必須呈現(xiàn)如下形式：如果這個(gè)條件滿足，則只要選擇：根據(jù)這些碼長，按照樹圖法構(gòu)造出一種唯一可譯碼，所得的碼一定是緊致碼。2021/6/27412.上界證明：只需證明存在一種唯一可譯碼滿足即可。令則，選取每個(gè)碼字的長度的原則是：顯然知2021/6/2742即為Craft不等式；因此，用這樣選擇的碼長滿足Craft不等式，故可構(gòu)造唯一可譯碼。但不一定是緊致碼。兩邊對i求和，則有：由于2021/6/2743右邊的不等式兩邊進(jìn)行如下處理：平均碼長因此，平均碼長小于上界的唯一可譯碼存在。兩邊乘以P(si)后，求和。另外由于2021/6/2744無失真變長信源編碼定理（香農(nóng)第一定理）離散無記憶信源S的N次擴(kuò)展信源，其熵為，且編碼器碼元符號集為.對信源進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源S中每個(gè)信源符號si所需要的平均碼長滿足當(dāng)則得：2021/6/2745證明：設(shè)離散無記憶信源X的數(shù)學(xué)模型N次擴(kuò)展由于無記憶性，有：2021/6/2746由前述定理，有：2021/6/2747定理含義：

要做到無失真信源編碼，變換每個(gè)信源符號平均所需最少的r元碼元數(shù)是信源的熵值。

若編碼的平均碼長小于信源的熵，則唯一可譯碼不存在，在譯碼時(shí)必然帶來失真或差錯(cuò)。

同時(shí)，通過對擴(kuò)展信源進(jìn)行變長編碼，當(dāng)擴(kuò)展長度N足夠大時(shí)，平均碼長可達(dá)到此極限值。

信源的熵是無失真信源壓縮的極限值。

2021/6/2748定理推廣：

可以推廣到平穩(wěn)有記憶信源和馬爾科夫信源：2021/6/2749

如果將定理中的下式改寫：為編碼后平均每個(gè)信源符號所能承載的最大信息量，即變長編碼后信源的信息傳輸率（編碼信息率）。這樣，香農(nóng)第一定理也可表述為：

若R’>=H(S),就存在唯一可譯變長編碼；若R’<H(S),唯一可譯邊長碼不存在，不能實(shí)現(xiàn)無失真德信源編碼。則定義：等長編碼2021/6/2750

從信道角度看，編碼后信道的信息傳輸率：

由此可見，此時(shí)信道的信息傳輸率等于無噪無損信道的信道容量C，信息傳輸率最高。

因此，無失真信源編碼的實(shí)質(zhì)是：對離散信源進(jìn)行適當(dāng)編碼，使變換后新的碼符號信源（信道的輸入信源）盡可能等概率分布，以使新信源的每個(gè)碼符號平均所含的信息量達(dá)到最大，從而使信道的信息傳輸率R達(dá)到信道容量C，實(shí)