[信息與通信]6 無失真信源編碼ppt課件

1、6 無失真信源編碼無失真信源編碼單義可譯碼n平均碼長n無失真信源編碼定理nHuffman編碼單義可譯碼單義可譯碼編碼器相關(guān)概念n非延長碼及其構(gòu)成n單義可譯定理編碼器相關(guān)概念編碼器相關(guān)概念:S編碼器qissss,2112, ,iq :C(),)iijjila aXs是由 個(gè)組成的序列并與 一一對應(yīng):X12, ,ra aa編碼器相關(guān)概念編碼器相關(guān)概念編碼器將信源符號集中的符號si（或者長為N的信源符號序列）變換成由aj（j=1,2,r）組成的長度為li的一一對應(yīng)的序列。即：12(1,)()liiiiiisiqWaaa1212()()(1,2,)(1,2, )NlikkiiiiiiiiiiiSs s

2、sWa aasS kNaX kl或者編碼器相關(guān)概念編碼器相關(guān)概念幾個(gè)定義幾個(gè)定義：n二元碼二元碼 ：若碼符號集為0，1，所有碼字都是一些二元序列，則稱為二元碼.二元碼是數(shù)字通信和計(jì)算機(jī)系統(tǒng)中最常用的一種碼. n等長碼（定長碼）等長碼（定長碼）：碼中所有碼字的碼長都相同n變長碼變長碼：碼中所有碼字的碼長各不相同n奇異碼與非奇異碼奇異碼與非奇異碼：若一組碼中所有碼字都不相同，則為非奇異碼，反之，若一組碼中有相同的碼字則為奇異碼n唯一可譯碼唯一可譯碼：任意有限長的碼元序列，只能被唯一地分割成一個(gè)個(gè)的碼字 n即時(shí)碼和非即時(shí)碼即時(shí)碼和非即時(shí)碼：如果收到一個(gè)完整的碼字以后，就可以立即譯碼，則叫做即時(shí)碼;反

3、之為非即時(shí)碼.即時(shí)碼要求任何一個(gè)碼字都不是其他碼字的前綴部分，也叫做異前綴碼.編碼器相關(guān)概念編碼器相關(guān)概念信源符號xi碼碼碼碼x10011x211101001x30000100001x4110110000001奇異碼非奇異碼唯一可譯碼即時(shí)碼單義可譯碼單義可譯碼編碼器相關(guān)概念非延長碼及其構(gòu)成n單義可譯定理非延長碼及其構(gòu)成非延長碼及其構(gòu)成非延長碼的樹圖表示非延長碼的樹圖表示樹圖：根、枝、點(diǎn)樹圖與碼字：樹圖與碼字：r進(jìn)制樹圖：每個(gè)節(jié)點(diǎn)可以有r個(gè)分枝 節(jié)點(diǎn)：分枝的端點(diǎn)節(jié)點(diǎn)的階數(shù)：節(jié)點(diǎn)通過樹枝的數(shù)目終點(diǎn)：不再有分枝的節(jié)點(diǎn)碼字：每個(gè)終點(diǎn)代表一個(gè)碼字非滿樹碼：變長碼滿樹碼：等長碼00001111W1：0W1

4、W2W3W4W5W2：10W3：110W4：1110W5：1111單義可譯碼單義可譯碼編碼器相關(guān)概念非延長碼及其構(gòu)成單義可譯定理單義可譯定理單義可譯定理單義可譯碼存在定理：若碼元個(gè)數(shù)為r，碼字個(gè)數(shù)為q，碼長分別為ni(i=1,2,q)，則存在單義可譯碼的充要條件是： 注意：注意：克拉夫特不等式只是說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)（可以排除，不能肯定）.11()iqnirKraft克拉夫特不等式必要性證明:單義可譯必滿足Kraft不等式1,LLZ1112()1111iiiiLLLqqqqnnnniiiirr 12LiiiiKnnn1,2,Liq1/maxlim1LLLn11iq

5、nir111LiiLqqnKiirrmax1innmaxiLKLnmaxLnlll LBrlBl表示長度為 的碼符號序列數(shù)maxLnlll Lr rmaxLn1iLqnir必要性證畢充分性證明:滿足Kraft不等式必存在單義可譯碼思路：滿足Kraft不等式一定能構(gòu)成至少一種具有這種碼長的即時(shí)碼，而即時(shí)碼唯一可譯11iqnir證明:maxmax1nniqnirrr1nqiqqnnirr三階節(jié)點(diǎn)二元整樹6 無失真信源編碼無失真信源編碼單義可譯碼平均碼長n無失真信源編碼定理nHuffman編碼平均碼長平均碼長平均碼長與有效性n平均碼長的界限定理平均碼長與有效性平均碼長與有效性1212:( ):( )

6、()()qqSsssS PP Sp sp sp s1( )1qiip sisiw()in長度為平均碼長1( )qiiinp s n碼符號/信源符號21( )( )log( )qiiiH Sp sp s 比特/信源符號信息傳輸率( )H SRn比特/碼符號R 每個(gè)碼符號攜帶的平均信息量效率n平均碼長平均碼長平均碼長與有效性平均碼長的界限定理平均碼長的界限定理平均碼長的界限定理1212: ,( ): , ,qriSs ssH SXa aaq rnKraftn定理：離散無記憶信源的信息熵為， 碼符號集若碼長 滿足不等式，總可找到一種單義可譯碼，其平均碼長 滿足( )( )1loglogH SH Sn

7、rr下界證明( )logH Snr證明:( )logH Snr11( )log( )( )logqqiiiiiip sp sp s nr 11( )log( )( )logiqqniiiiip sp sp sr 1( )log( )inqiiirp sp s1log( )( )inqiiirp sp s1logiqnirlog10( )=inip sr時(shí)取“ ”平均碼長的界限定理平均碼長的界限定理下界說明( )logH Snr1( )log( )logqiiip sp sr1( )log( )qiriip sp s ( )rHS/碼符號 信源符號上界證明( )1logH Snr證明:log(

8、)log( ) 1riirip snp s 111( )( )iqqqniiiiip sp srr11loglog1( )( )ririinp sp slog( )rirp s1( )( )iniirrp sp s( )( )iniip sp srr1r1111( )( )log( )( )qqqiiiriiiiip s np sp sp s ( ) 1rHS( ) 1rnHS即6 無失真信源編碼無失真信源編碼單義可譯碼平均碼長無失真信源編碼定理nHuffman編碼無失真信源編碼定理無失真信源編碼定理信源擴(kuò)展與數(shù)據(jù)壓縮n無失真信源編碼定理信源擴(kuò)展與數(shù)據(jù)壓縮信源擴(kuò)展與數(shù)據(jù)壓縮1212:( ):(

9、 )()()qqSsssS PP Sp sp sp s1( )1qiip s1212:():()()()NNNqNNqSSPP Sppp1()1Nqiipiiw(/)NinN長度為碼符號信源符號()()1loglogNNNH SH Snrr()()1loglogNNNnH SH SNrNNrN( )( )1loglogNnH SH SnrNrN( )( )1limlimlimlimloglogNNNNH SH SnrrNlim( )rNnHS()( )NH SNH S對于無記憶信源( )( )1loglogNHHnrrSS( )( )1loglogNnHHNrNNrNSS( )( )1logl

10、ogNnHHnNrNNrNSS( )( )1limlimlimlimloglogNNNNHHnNrNrNSSlim/logrNnHrH12112-1( )()(/)(/)NNHH SH SSH SS SSS對于有記憶信源limloglogNHHnrr( )rHS無失真信源編碼定理無失真信源編碼定理信源擴(kuò)展與數(shù)據(jù)壓縮無失真信源編碼定理無失真信源編碼定理無失真信源編碼定理( )(- )( )- )( )tttSH SCSCH SCH S定理：離散無記憶信源 的熵為，離散無噪信道的信道容量為 ，則信源 的無失真信源編碼在無噪信道上的碼速度的限度為每秒個(gè)信源符號( 是任意小的正數(shù))。要使碼速度大于(是

11、不可能的。:n平均碼長證明：無失真信源編碼每信源符號所需要的平均碼符號數(shù)/碼符號 信源符號( ):H S信源熵/信息單位 信源符號每信源符號所攜帶的平均信息量:R信道的信息傳輸率信息單位/碼符號無噪信道每碼符號傳輸?shù)钠骄畔⒘縃 SRn（ ）limlogNH Snr（ ）limlimNNH SRn（ ）logH SH Sr（ ）（ ）logrC無噪信道容量limNRC即：limttNRC信息單位/秒:碼速度信源符號/秒( )tRH Slimlim( )( )ttNNRCH SH S:即對于任意小的正數(shù)( )tCH S證畢:平穩(wěn)遍歷有記憶信源的情況(- )- )tttHCSCHCH離散平穩(wěn)遍歷有

12、記憶信源S的極限熵為，離散無噪信道的信道容量為 ，則信源 的無失真信源編碼在無噪信道上的碼速度的限度為每秒個(gè)信源符號( 是任意小的正數(shù))。要使碼速度大于(是不可能的。6 無失真信源編碼無失真信源編碼單義可譯碼平均碼長無失真信源編碼定理Huffman編碼Huffman編碼編碼最佳編碼nHuffman編碼方法最佳編碼最佳編碼n最佳編碼：對于S，將其編碼為二進(jìn)制的單義碼，若此代碼的平均長度不大于其他任何方法的平均長度，則稱此代碼為最佳代碼，與之對應(yīng)的編碼方法稱為最佳編碼方法。n香農(nóng)第一定理給出了信源熵與編碼后的平均碼長之間的關(guān)系，同時(shí)也指出可以通過編碼使平均碼長達(dá)到極限值，因此，香農(nóng)第一定理是一個(gè)極

13、限定理。但定理中并沒有告訴我們?nèi)绾蝸順?gòu)造這種碼。Huffman編碼編碼最佳編碼Huffman編碼Huffman編碼編碼Huffman編碼的步驟1.將q個(gè)信源符號按概率分布p(si)的大小,以遞減次序由大到小,自上而下排成一列;2.對處于最下面的概率最小的r個(gè)信源符號,各分配一個(gè)碼元a1,a2,ar.將處于最下面的概率最小的r個(gè)信源符號合并成一個(gè)新符號，并用這r個(gè)最小概率之和作為新符號的概率。結(jié)果得到一個(gè)只包含(q-r+1)個(gè)信源符號的新信源。稱為信源的第一次縮減信源，用S1表示;3.將縮減信源S1的符號仍按概率從大到小的順序排列，重復(fù)上面的步驟，得到只含(q-r+1)-r+1)個(gè)符號的縮減信源

14、S2;4.重復(fù)上面的步驟,直至縮減信源的符號數(shù)小于或等于r為止，此時(shí)所剩符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號對應(yīng)的碼字。例例 設(shè)信源共有7個(gè)符號組成，其概率如表所示，求其 Huffman碼。信源符號xi符號概率p(xi)x10.20 x20.19x30.18x40.17x50.15x60.10 x70.01 信源符號符號概率編碼過程碼字 碼長x10.20102x20.19112x30.180003x40.170013x50.150103x60.1001104x70.0101114010.200.190.180.170.150.110.260.200.190.180.1701010.260.350.200.19010.350.260.39010.390.6101Huffman編碼編碼n特點(diǎn)：n編碼不是唯一的n保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，而且短碼得到充分利用n每次縮減信源的最后二個(gè)碼字總是最后一位碼元不同，前面各位碼元相同（二元碼情況）n每次縮減信源的最長兩個(gè)碼字具有相同碼長n后三個(gè)特點(diǎn)保證了所得到后三個(gè)特點(diǎn)保證了所得到HuffmanHuffman碼一定是最佳碼碼一定是最佳碼Huffma