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

信息通過信道傳輸到信宿的過程。要做到既不失真又快速地通信，需要解決兩個問題：信源編碼:

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

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

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

對信源的符號按一定的數學規則進行的變換。它可以看作這樣一個系統，它的輸入端為原始信源S，其符號集為而信道所能傳輸的符號集為

2021/6/273

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

(碼或碼書)

稱為碼字，li

為碼字的碼元個數（碼字長度，碼長）。碼字集合C稱為碼或碼書。2021/6/274

若要實現無失真編碼，這種映射應是一一對應的可逆映射。編碼的形式化描述：

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

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

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

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

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

碼符號集中每個碼符號所占的傳輸時間都相同(大多數情況)。變長碼中每個碼字的傳輸時間就不一定相同。（摩爾斯電報碼，點-劃所占傳輸時間不同）5、碼的N次擴展

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

設信源S的概率空間為：

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

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

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

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

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

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

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

1）碼字與信源符號之間一一對應（非奇異碼）；

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

若等長碼是非奇異碼，則它的任意有限長N次擴展碼一定也是非奇異碼。因此，等長非奇異碼字一定是唯一可譯碼,因為采用固定長度劃分碼字序列.5.2等長碼2021/6/27141）若對每個信源符號進行等長編碼，則必須滿足:

其中:l是碼長，r是碼符號集的碼元數，q信源符號數。2）若對信源的N次擴展信源進行編碼，必須滿足:表示平均每個信源符號所需的碼符號個數。即

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

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

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

左邊:長為l

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

右邊:長為N的信源符號序列平均攜帶的信息量。因此，定理說明了：只要碼字傳輸的最大信息量大于信源序列攜帶的信息量，則可以實現無失真編碼。編碼后信源的信息傳輸率

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

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

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

一般情況下，在已知信源熵的情況下，信源序列長度N的選擇，與最佳編碼效率和允許錯誤概率有關。可以證明：2021/6/2720若采用等長二元編碼，要求編碼效率，允許錯誤率則：例：設離散無記憶信源：2021/6/27211、唯一可譯變長碼5.5變長碼優勢：容易實現效率很高的編碼。變長碼也必須是唯一可譯碼，才能實現無失真編碼。碼1是一個奇異碼，故不是唯一可譯碼；碼2也不是唯一可譯碼，因為收到一串序列，無法唯一譯出對應的原符號序列，如01000，即可譯作s4s3s1,也可譯作s4s1s3,s1s2s3或s1s2s1s1；2021/6/2722碼2本身不是奇異碼，但從有限長的碼符號序列是奇異碼。如果把碼2的2次擴展碼寫出，則會發現：

S1S3的擴展碼字為：000；

S3S1的擴展碼字也為：000

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

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

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

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

在每個節點上都有r個分枝的樹稱為整樹（滿樹），否則稱為非整（滿）樹。

01

01

01

01010101

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

因為每一碼元對應于一個的樹圖分枝路徑，則即時碼的樹圖可以用來譯碼。譯碼器系統對一串符號序列譯碼過程：1）首先從樹根出發，根據接收的第一個碼元符號來選擇應走的第一條路徑；2）若沿著所選路徑走到某中間節點，再根據接收的第二個碼元符號來選擇第二條路經；3）若又走到中間節點，再依次繼續選擇路徑，直到終端節點為止。這時，可根據所經歷的枝路，判斷出所接收的碼字。4）重新返回樹根，再作下一個接收碼字的判斷。

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

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

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

若信道傳輸一個碼符號平均需要t秒鐘，則編碼后信道的每秒傳輸的信息量為：（比特/秒）由此可見：

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

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

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

由于li

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

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

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

同時，通過對擴展信源進行變長編碼，當擴展長度N足夠大時，平均碼長可達到此極限值。

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

2021/6/2748定理推廣：

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

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

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

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

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

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