基本信息論常用信源編碼

基本信息論常用信源編碼第一頁，共二十一頁，編輯于2023年，星期五通信系統(tǒng)的兩個(gè)重要技術(shù)指標(biāo)：有效性：信源編碼（有效性編碼）可靠性：信道編碼（抗干擾編碼）通過壓縮信源冗余，以提高信源熵，則可用較少的碼來傳送同樣多的信息量，也即增大單位時(shí)間內(nèi)傳送的平均信息量，從而提高通信的有效性通過增加信源冗余，以發(fā)現(xiàn)甚至糾正傳送錯(cuò)誤，從而提高通信的可靠性。代價(jià)：增大碼率或帶寬第二頁，共二十一頁，編輯于2023年，星期五一、山農(nóng)-費(fèi)諾編碼1、編碼步驟1）將信源符號(hào)按其概率從大到小排列；2）將這一列符號(hào)分成概率和盡可能接近或相同的兩組；3）上面一組符號(hào)編為0，下面一組符號(hào)編為1，或反之；4）將已分的組重復(fù)步驟2)，3)，直至不能再分組；5）自左至右寫出各碼字。第三頁，共二十一頁，編輯于2023年，星期五2、例題與分析第四頁，共二十一頁，編輯于2023年，星期五信源符號(hào)X概率p(X)編碼碼字碼長x10.400002x20.181012x30.11001003x40.111013x50.0710011004x60.06111014x70.051011104x80.041111143）編碼過程：第五頁，共二十一頁，編輯于2023年，星期五4）平均碼長：5）編碼后的平均碼元熵：6）編碼效率：第六頁，共二十一頁，編輯于2023年，星期五7）碼冗余度：第七頁，共二十一頁，編輯于2023年，星期五8）碼樹圖：00011110x1x2x3x401010011x5x6x8x7第八頁，共二十一頁，編輯于2023年，星期五二、哈夫曼編碼1、編碼步驟1）將信源符號(hào)按其概率從大到小排列；2）把概率最小的兩個(gè)分成一組，上面一個(gè)編為0，下面一個(gè)編為1，并將這兩個(gè)符號(hào)的概率加起來，其結(jié)果再與尚未處理過的符號(hào)重新按大小排序；3）重復(fù)步驟2)，直到所有信源符號(hào)都處理完；4）自右至左依據(jù)編碼路徑返回，即得到各碼字。第九頁，共二十一頁，編輯于2023年，星期五2、例題與分析第十頁，共二十一頁，編輯于2023年，星期五2）編碼過程：11x10.43001x20.183011x30.140000x40.140100x50.0740101x60.06500010x70.05500011x80.040110.090110.13000.1910010.60.370.23101.0碼長碼字第十一頁，共二十一頁，編輯于2023年，星期五3）平均碼長：4）編碼后的平均碼元熵：5）編碼效率：6）碼冗余度：第十二頁，共二十一頁，編輯于2023年，星期五7）碼樹圖：x1x2x3x4x5x6x8x70001111001101010第十三頁，共二十一頁，編輯于2023年，星期五三、冗余位編碼1、L-D編碼Lynch/Davission例：有一二元序列，其中一串000100000000100共15位二進(jìn)制，其余的也可分割成15位一串，稱為一幀，用L-D編碼壓縮冗余。對(duì)該幀的描述：1）幀長為152）共有兩個(gè)13）第一個(gè)1在第4位4）第二個(gè)1在第13位第十四頁，共二十一頁，編輯于2023年，星期五分析：需要多少位二進(jìn)制數(shù)來表示該幀信息？1）對(duì)于幀長N=15，Q的取值為0~15共16種情況，2）1的位置的可能性應(yīng)為N中取Q的組合數(shù)：取最小整數(shù)為7，即需要7位二進(jìn)制數(shù)來描述每個(gè)1的位置。所以，共需要4+7=11位二進(jìn)制數(shù)15-11=4位冗余第十五頁，共二十一頁，編輯于2023年，星期五如何求這11位二進(jìn)制數(shù)？1）將Q=2直接轉(zhuǎn)換成4位二進(jìn)制數(shù)，得00102）由1的位置得到T值，將T轉(zhuǎn)換成7位二進(jìn)制數(shù)。010001017位合并Q和T，得到消息序列000100000000100的L-D編碼：001001000101000000000000011第十六頁，共二十一頁，編輯于2023年，星期五如何由有11位L-D碼譯碼為原序列？1）根據(jù)N=15，將11位碼字的前4位0010二進(jìn)制數(shù)轉(zhuǎn)換為Q值：Q=22）將11位碼字的后7位01000101二進(jìn)制數(shù)轉(zhuǎn)換為T值：T=69第十七頁，共二十一頁，編輯于2023年，星期五……第十八頁，共二十一頁，編輯于2023年，星期五L-D編碼方法：1）將冗余序列截成N位二進(jìn)制一幀2）根據(jù)1的數(shù)目寫出Q，根據(jù)1的位置寫出ni第十九頁，共二十一頁，編輯于2023年，星期五L-D譯碼方法：第二十頁，共二十一頁，編輯于2023年，星期五2、游程編碼例：01000111101100000連在一起的0段稱為0游程連在一起的1段稱為1游程規(guī)定：以0游程開始，并且0，1游程交替則對(duì)上序列游程編碼：1134125變長編碼的優(yōu)點(diǎn)：編碼效率較高