第1頁2024/4/14第六章信源編碼6.1信源編碼概論6.2變長編碼方法6.3實用的無失真信源編碼方法6.4信源編碼總結(jié)ElectronicsEngineeringDepartment,XXXXXxxXxxx第2頁2024/4/146.1信源編碼概論6.1.1概述6.1.2信源編碼及分類第3頁2024/4/146.1.1概述香農(nóng)編碼定理雖然指出了理想編碼器的存在性，但是并沒有給出實用碼的結(jié)構(gòu)及構(gòu)造方法；編碼理論正是為了解決這一問題而發(fā)展起來的科學(xué)理論；編碼的目的是為了優(yōu)化通信系統(tǒng)，使這些指標(biāo)達(dá)到最佳；通信系統(tǒng)的性能指標(biāo)主要是有效性、可靠性、安全性和經(jīng)濟性，除了經(jīng)濟性外，這些指標(biāo)正是信息論研究的對象。按不同的編碼目的，編碼分為三類：信源編碼、信道編碼和保密編碼（密碼）。6.1引言第4頁2024/4/146.1.1概述信源編碼：提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實現(xiàn)。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。信道編碼：提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通常通過增加

信源的冗余度來實現(xiàn)。采用的一般方法是增大碼率（帶寬）。與信源編碼正好相反。保密編碼：提高通信系統(tǒng)的安全性為目的的編碼。通常通過加密和解密來實現(xiàn)。從信息論的觀點出發(fā)，“加密”可視為增熵的過程，“解密”可視為減熵的過程。6.1引言第5頁2024/4/146.1.2信源編碼及分類(1)信源編碼的理論基礎(chǔ)信源編碼理論是信息論的一個重要分支，其理論基礎(chǔ)是信源編碼的兩個定理。無失真信源編碼定理：是離散信源／數(shù)字信號編碼的基礎(chǔ)；限失真信源編碼定理：是連續(xù)信源／模擬信號編碼的基礎(chǔ)。6.1引言第6頁2024/4/146.1.2信源編碼及分類(2)信源編碼的分類

根據(jù)信源特性離散信源編碼：獨立信源編碼，可做到無失真編碼；連續(xù)信源編碼：獨立信源編碼，只能做到限失真信源編碼；相關(guān)信源編碼：非獨立信源編碼。根據(jù)壓縮的特性冗余度壓縮編碼：可逆壓縮，經(jīng)編譯碼后可以無失真地恢復(fù)。熵壓縮編碼：不可逆壓縮。6.1引言第7頁2024/4/146.1.2信源編碼及分類(3)數(shù)據(jù)壓縮概貌KLT：Karhunen-LoeveTransformDCT：DiscreteCosineTransformDST：DiscreteSinusoidTransformDFT：DiscreteFourierTransformWHT：Walsh-HadamardTransformSLT：SlantTransformHAAR：HaarTransformLPC-10：GovernmentStandardLinearPredictiveCodingAlgorithm:LPC-10MELP：MixedExcitedLinearPredictiveCodingCELP：CodebookExcitedLinearPredictiveCodingACELP：AlgebraicCocebookExcitationLPCQCELP：QualcomCocebookExcitationLPCEVRC：EnhancedVariableRateCodecLD-CELP：LowDelay-CELP28種6.1引言第8頁2024/4/146.1.2信源編碼及分類(3)數(shù)據(jù)壓縮概貌CS-ACELP：Conjugate-StructureAlgebraicCELPVSELP：VectorSumExcitationLPCRPE-LT：LongTimePredictiveRegular-PulseExcitationLPCMPLPC：Multi-PulseExcitationLPCMP-MLQ：MultipulseMaximumLikelihoodQuantizationMBE：Multi-BandExcitationSpeechCoderSTC：SinusoidTransformCocingCVSD：ContinuouslyVariableSlopeDeltaModulatorSB-ADPCM：Sub-BandAdaptiveDifferentialPulseCodeModulationPTC：PictureTelTransformCoderAC-2；AC-3：DigitalAudioCompressionStandard，美國Dolby公司AAC：AdvancedAudioCoding,日本13818－7,MPEG-2MUSICAM：MaskingPatternAdaptedUniversalSubbandIntegratedCodingandMultiplexingATRAC：AdaptiveTransformAcousticCoder6.1引言第9頁2024/4/146.1.2信源編碼概述(3)數(shù)據(jù)壓縮概貌6.1引言第10頁2024/4/146.1.2信源編碼及分類

有些編碼原理和技術(shù)在通信原理和信號處理等相關(guān)課程中已經(jīng)介紹過。例如：連續(xù)信源編碼：脈沖編碼調(diào)制（PCM）、矢量量化技術(shù)相關(guān)信源編碼：預(yù)測編碼：增量編碼、差分脈沖調(diào)制（DPCM）、自適應(yīng)差分脈沖調(diào)制（ADPCM）、線性預(yù)測聲碼器；變換編碼：K-L變換、離散變換、子帶編碼、小波變換。6.1引言第11頁2024/4/146.2變長編碼方法6.2.1香農(nóng)編碼6.2.2費諾編碼6.2.3霍夫曼編碼第12頁2024/4/146.2.1香農(nóng)編碼

設(shè)離散無記憶信源：二進(jìn)制香農(nóng)碼的編碼步驟如下：

將信源符號按概率從大到小的順序排列，為方便起見，令：p(x1)≥

p(x2)≥…≥

p(xn)

令p(x0)=0，用pa(xj)，j=i+1表示第i個碼字的累加概率，則：6.2變長編碼方法第13頁2024/4/146.2.1香農(nóng)編碼

設(shè)離散無記憶信源：二進(jìn)制香農(nóng)碼的編碼步驟如下：確定滿足下列不等式的整數(shù)li，并令li為第i個碼字的長度－log2

p(xi)≤

li<1－log2

p(xi)

將pa(xj)

用二進(jìn)制表示，并取小數(shù)點后li

位作為符號xi的編碼。6.2變長編碼方法第14頁2024/4/146.2.1香農(nóng)編碼[例6-1]：有一單符號離散無記憶信源：對該信源編二進(jìn)制香農(nóng)碼。其編碼過程如表6-2所示。6.2變長編碼方法第15頁2024/4/146.2.1香農(nóng)編碼[例6-1]：計算出給定信源香農(nóng)碼的平均碼長：若對上述信源采用等長編碼，要做到無失真譯碼，每個符號至少要用3個比特表示。相比較，香農(nóng)編碼對信源進(jìn)行了壓縮。6.2變長編碼方法第16頁2024/4/146.2.1香農(nóng)編碼[例6-1]：由離散無記憶信源熵定義，可計算出信源熵為：對上述信源采用香農(nóng)編碼的信息率為：編碼效率為信源熵和信息率之比。則：可以看出，編碼效率并不是很高。6.2變長編碼方法第17頁2024/4/146.2.2費諾編碼將概率按從大到小的順序排列，令：p(x1)≥

p(x2)≥…≥

p(xn)按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組，編r進(jìn)制碼就分成r組。給每一組分配一位碼元。將每一分組再按同樣原則劃分，重復(fù)步驟2和3，直至概率不再可分為止。6.2變長編碼方法第18頁2024/4/146.2.2費諾編碼[例6-2]：設(shè)有一單符號離散信源對該信源編二進(jìn)制費諾碼。編碼過程如表6-3。6.2變長編碼方法第19頁2024/4/146.2.2費諾編碼[例6-2]該信源的熵為：平均碼長為：對上述信源采用費諾編碼的信息率為：編碼效率為：本例中費諾編碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。特別是對每次分組概率都相等的信源進(jìn)行編碼時，可達(dá)到理想的編碼效率。6.2變長編碼方法第20頁2024/4/146.2.2費諾編碼[例6-3]：有一單符號離散無記憶信源對該信源編二進(jìn)制費諾碼，編碼過程如表6-4。6.2變長編碼方法第21頁2024/4/146.2.2費諾編碼[例6-3]信源熵為：H(X)=2.75(比特/符號)平均碼長為：編碼效率為η=1。之所以如此，因為每次所分兩組的概率恰好相等。6.2變長編碼方法第22頁2024/4/146.2.3霍夫曼編碼

霍夫曼（Huffman）編碼是一種效率比較高的變長無失真信源編碼方法。(1)編碼步驟(2)二進(jìn)制霍夫曼編碼(3)D進(jìn)制霍夫曼編碼6.2變長編碼方法第23頁2024/4/14(1)編碼步驟①將信源符號按概率從大到小的順序排列，令：p(x1)≥

p(x2)≥…≥p(xn)②

信源的第一次縮減信源：給兩個概率最小的信源符號p(xn－1)和p(xn)各分配一個碼位“0”和“1”，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含(n－1)個信源符號的新信源，用S1表示。③將縮減信源S1的符號仍按概率從大到小順序排列，重復(fù)步驟②，得到只含(n－2)個符號的縮減信源S2。④重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。6.2變長編碼方法第24頁2024/4/14(2)二進(jìn)制霍夫曼編碼[例6-4]：設(shè)單符號離散無記憶信源如下，要求對信源編二進(jìn)制霍夫曼碼。編碼過程如圖6-2。6.2變長編碼方法第25頁2024/4/14(2)二進(jìn)制霍夫曼編碼[例6-4]6.2變長編碼方法第26頁2024/4/14(2)二進(jìn)制霍夫曼編碼[例6-4]：設(shè)單符號離散無記憶信源如下，要求對信源編二進(jìn)制霍夫曼碼。編碼過程如圖6-2。在圖中讀取碼字的時候，一定要從后向前讀，此時編出來的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。6.2變長編碼方法第27頁2024/4/14(2)二進(jìn)制霍夫曼編碼[例6-4]信源熵為：平均碼長為：編碼效率為：若采用等長編碼，碼長L=3，則編碼效率：霍夫曼的編碼效率提高了12.7%。6.2變長編碼方法第28頁2024/4/14(2)二進(jìn)制霍夫曼編碼

注意：霍夫曼的編法并不唯一

每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長li不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別；縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長度li也不盡相同。6.2變長編碼方法第29頁2024/4/14(2)二進(jìn)制霍夫曼編碼[例6-5]：單符號離散無記憶信源用兩種不同的方法對其編二進(jìn)制霍夫曼碼。方法一：合并后的新符號排在其它相同概率符號的后面。6.2變長編碼方法R第30頁2024/4/14(2)二進(jìn)制霍夫曼編碼[例6-5]：單符號離散無記憶信源用兩種不同的方法對其編二進(jìn)制霍夫曼碼。方法二：合并后的新符號排在其它相同概率符號的前面。6.2變長編碼方法R第31頁2024/4/14(2)二進(jìn)制霍夫曼編碼[例6-5]：單符號信源編二進(jìn)制霍夫曼碼，編碼效率主要決定于信源熵和平均碼長之比。對相同的信源編碼，其熵是一樣的，采用不同的編法，得到的平均碼長可能不同。平均碼長越短，編碼效率就越高。編法一的平均碼長為：編法二的平均碼長為：可見，本例兩種編法的平均碼長相同，所以編碼效率相同。6.2變長編碼方法第32頁2024/4/14(2)二進(jìn)制霍夫曼編碼

討論：

碼字長度的方差σ2：長度li與平均碼長之差的平方的數(shù)學(xué)期望，即：編法一碼字長度方差：編法二碼字長度方差：哪種方法更好？6.2變長編碼方法第33頁2024/4/14(2)二進(jìn)制霍夫曼編碼

比較：第二種編碼方法的碼長方差要小許多。第二種編碼方法的碼長變化較小，比較接近于平均碼長。第一種方法編出的5個碼字有4種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長；第二種編碼方法更簡單、更容易實現(xiàn)，所以更好。結(jié)論：在霍夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng)使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。6.2變長編碼方法ii第34頁2024/4/14(3)D進(jìn)制霍夫曼編碼①“全樹”概念②舉例③結(jié)論6.2變長編碼方法第35頁2024/4/14(3)D進(jìn)制霍夫曼編碼①“全樹”概念定義：碼樹圖中每個中間節(jié)點后續(xù)的枝數(shù)為D時稱為全樹；若有些節(jié)點的后續(xù)枝數(shù)不足D，就稱為非全樹。二進(jìn)制碼不存在非全樹的情況，因為后續(xù)枝數(shù)是1時，這個枝就可以去掉使碼字長度縮短。D進(jìn)制編碼：若所有碼字構(gòu)成全樹，可分離的碼字?jǐn)?shù)（信源個數(shù)）必為D+i(D－1)。i為信源縮減次數(shù)。若信源所含的符號數(shù)K不能構(gòu)成D進(jìn)制全樹，必須增加M個不用的碼字形成全樹。顯然M<D－1，若M=D－1，意味著某個中間節(jié)點之后只有一個分枝，為了節(jié)約碼長，這一分枝可以省略。6.2變長編碼方法第36頁2024/4/14(3)D進(jìn)制霍夫曼編碼①“全樹”概念

在編D進(jìn)制霍夫曼碼時為了使平均碼長最短，必須使最后一步縮減信源有D個信源符號。非全樹時，有M個碼字不用：第一次對最小概率符號分配碼元時就只取(D－M)個，分別配以0,1,…,D－M－1，把這些符號的概率相加作為一個新符號的概率，與其它符號一起重新排列。以后每次就可以取D個符號，分別配以0,1,…,D－1；…；如此下去，直至所有概率相加得1為止，即得到各符號的D進(jìn)制碼字。6.2變長編碼方法第37頁2024/4/14(3)D進(jìn)制霍夫曼編碼②舉例對如下單符號離散無記憶信源（例6-4）編三進(jìn)制霍夫曼碼。

這里：D=3，K=8令i=3，D+i(D－1)=9，則M=9－K=9－8=1所以第一次取D－M=2個符號進(jìn)行編碼。6.2變長編碼方法第38頁2024/4/14(3)D進(jìn)制霍夫曼編碼②舉例6.2變長編碼方法第39頁2024/4/14(3)D進(jìn)制霍夫曼編碼②舉例平均碼長為：信息率為：編碼效率為：可見：霍夫曼的編碼效率相當(dāng)高，對編碼器的要求也簡單得多。6.2變長編碼方法第40頁2024/4/14(3)D進(jìn)制霍夫曼編碼③結(jié)論香農(nóng)碼、費諾碼、霍夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮；香農(nóng)碼有系統(tǒng)的、唯一的編碼方法，但在很多情況下編碼效率不是很高;費諾碼和霍夫曼碼的編碼方法都不唯一；費諾碼比較適合于對分組概率相等或接近的信源編碼，費諾碼也可以編D進(jìn)制碼，但D越大，信源的符號數(shù)越多，可能的編碼方案就越多，編碼過程就越復(fù)雜，有時短碼未必能得到充分利用；6.2變長編碼方法第41頁2024/4/14(3)D進(jìn)制霍夫曼編碼③結(jié)論霍夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼。6.2變長編碼方法第42頁2024/4/146.3實用的無失真信源編碼方法6.3.1游程編碼6.3.2算術(shù)編碼6.3.3通用信源編碼第43頁2024/4/146.3.1游程編碼(1)游程編碼對象和性質(zhì)(2)游程編碼的定義(3)二元獨立序列(4)游程編碼的效率(5)長碼的截斷處理方法6.3實用的無失真信源編碼方法第44頁2024/4/14(1)游程編碼對象和性質(zhì)香農(nóng)編碼、費諾編碼、霍夫曼編碼主要是針對無記憶信源。當(dāng)信源有記憶時上述編碼效率不高；游程編碼對相關(guān)信源編碼更有效；游程編碼是熵編碼。黑白游程分別最佳編碼后的碼長仍以信源熵為極限。6.3實用的無失真信源編碼方法第45頁2024/4/14(2)游程編碼的定義

游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。二元序列的游程：只有“0”和“1”兩種符號。連“0”這一段稱為“0”游程，它的長度稱為游程長度l0；連“1”這一段稱為“1”游程，它的游程長度用l1表示。6.3實用的無失真信源編碼方法第46頁2024/4/14(3)二元獨立序列①基本概念②二元獨立序列游程長度的概率和熵③二元獨立序列的平均游程長度④二元獨立序列的熵6.3實用的無失真信源編碼方法第47頁2024/4/14(3)二元獨立序列①基本概念若規(guī)定二元序列總是從“0”開始，第一個游程是“0”游程，則第二個游程必為“1”游程，第三個又是“0”游程……。對于隨機序列，游程長度是隨機的，其取值可為1,2,3,…，直至無窮。游程長度序列

（游程序列）：用交替出現(xiàn)的“0”游程和“1”游程長度表示任意二元序列。游程變換：是一種一一對應(yīng)的變換，也是可逆變換。例如：二元序列：000101110010001…

可變換成如下游程序列：311321316.3實用的無失真信源編碼方法第48頁2024/4/14(3)二元獨立序列①基本概念游程變換減弱了原序列符號間的相關(guān)性。游程變換將二元序列變換成了多元序列；這樣就適合于用其它方法，如霍夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。編碼方法首先測定“0”游程長度和“1”游程長度的概率分布，即以游程長度為元素，構(gòu)造一個新的信源；對新的信源（游程序列）進(jìn)行霍夫曼編碼。6.3實用的無失真信源編碼方法第49頁2024/4/14(3)二元獨立序列①基本概念多元序列也可以變換成游程序列，如r元序列可有r種游程。但是變換成游程序列時，需要增加標(biāo)志位才能區(qū)分游程序列中的“長度”是r種游程中的哪一個的長度，否則，變換就不可逆。這樣，增加的標(biāo)志位可能會抵消壓縮編碼得到的好處。所以，對多元序列進(jìn)行游程變換的意義不大。6.3實用的無失真信源編碼方法第50頁2024/4/14(3)二元獨立序列②二元獨立序列游程長度的概率和熵若二元序列的概率特性已知，由于二元序列與游程變換序列的一一對應(yīng)性，可計算出游程序列的概率特性。令“0”和“1”的概率分別為p0和p1，則“0”游程長度l0的概率為：式中l(wèi)0=1,2,…

在計算p(l0)時必然已有“0”出現(xiàn)，否則就不是“0”游程，若下一個符號是“1”，則游程長度為1，其概率是p1=1－p0；若下一個符號為“0”、再下一個符號為“1”，則游程長度為2，其概率將為p0p1

；依此類推。6.3實用的無失真信源編碼方法第51頁2024/4/14(3)二元獨立序列②二元獨立序列游程長度的概率和熵游程長度至少是1，理論上，游程長度可以是無窮，但很長的游程實際出現(xiàn)的概率非常小。同理可得“1”游程長度l1

的概率為：6.3實用的無失真信源編碼方法第52頁2024/4/14(3)二元獨立序列②二元獨立序列游程長