【正文】 )()1( DR k ?的差別小于預先給定的值時，取)()( DR k或)()1( DR k ?作為 )( 1SR 的近似值； ( 6 ) 選稍大一些的負數(shù)2S，重復上述的迭代過程，得到對應(yīng)的2S的)( 2SR； ( 7 ) 重復上述過程，直到)( m a xSR趨近于 0 ； ( 8 ) 根據(jù)m ax21 , SSS ?以及與之相對應(yīng)的)(,),(),( m a x21 SRSRSR ?，可以做出)( SR曲線， 根據(jù))( DR函數(shù)的S參量表述理論，進而得到)( DR曲線，由此完成整個迭代過程。 限失真信源編碼定理 第 5章 限失真信源編碼 對于無失真信源編碼來說，每一個信源符號（或符號序列）必須對應(yīng)一個碼字（或碼字 序列），信源輸出信息率不能減少，而在允許一定失真的情況下，信源輸出信息率最少可減少 到信息率失真函數(shù))( DR，有可能是多個信源符號（符號序列）對應(yīng)一個碼字（碼字序列）。限 失真信源編碼定理就是關(guān)于信息率和失真關(guān)系的一個極限定理，保真度準則下的離散信源編 碼定理?，F(xiàn)在我們主要看一下，在保真度準則下的信源編碼定理和逆定理。 1. 信源編碼定理 在保真度準則下的信源編碼定理為： 設(shè))( DR為一離散信源的信源率失真函數(shù)，并且具有有限的失真測度，對于任意的 00 ≥ εD ，以及任意足夠長的碼長l，則一定存在一種信源編碼C。其碼字個數(shù)為： { }]+)([ ≤ εDRleM 而編碼后碼的平均失真度為： εDCd + )( ≤ 這個定理又稱為香農(nóng)第三定理。由定理可知：對于任何失真度0 ≥D，只要碼長l足夠長， 總可以找到一種編碼C，使編碼后每個信源符號的信息傳輸率為： εDRlMR39。 +)( l o g= ≤ 而碼的平均失真度DCd )( ≤ 。 第 5章 限失真信源編碼 2. 信源編碼逆定理 不存在平均失真度為D，而平均信息傳輸率)(39。 DRR ?的任何信源碼，即對任意碼 長為l的信源碼C，若碼字個數(shù) )]([ DRleM ?，一定有DCd ?)(。 從逆定理可知：如果編碼后平均每個信源符號的信息傳輸率R39。小于信息率失真函數(shù) )( DR，就不能在保真度準則下再現(xiàn)信源的信息。 保真度準則下的信源編碼定理和逆定理在實際通信理論中有著重要的意義。這兩個 定理證實了在允許失真度 D 確定后，總存在一種編碼方法，使編碼后的信息傳輸率 R39。 大 于)( DR，且可任意接近于)( DR，而平均失真度小于允許失真度 D 。反之，若)(39。 DRR ?， 那么編碼后的平均失真度將大于 D 。如果用二進制符號來進行編碼，在允許一定失真的 情況下，平均每個信源符號所需二進制碼符號的下限就是)( DR。 由此可以看出，從香農(nóng)第三定理可知：)( DR確實是允許失真度為 D 的情況下信源信息 壓縮的下限值。比較香農(nóng)第一定理和第三定理可知：當信源給定后，無失真信 源壓縮的極 限值是信源熵H ( X )，而有失真信源壓縮的極限值是信息率失真函數(shù))( DR。在給定 D 后，一 般H ( X )DR ?)(，因此香農(nóng)第三定理是有失真信源壓縮的理論基礎(chǔ)。 第 5章 限失真信源編碼 另外，把香農(nóng)第二定理和香農(nóng)第三定理結(jié)合起來，可得信息傳輸?shù)牧硪恢饕Y(jié)論：若 通過某信道來傳送信源輸出的信息，如果信道的信道容量)( DRC ?，則對信源和信道處理 后，總能以保真度εD ?再現(xiàn)信源的信息；如果)( DRC ?，則不管如何處理，在信道的接收 端總有不能以保真度D的要求再現(xiàn)信源的信息。 在給定信源X和允許失真度D后，可以求得信源的信息率失真函數(shù))( DR，若設(shè)信源 通過某信道傳輸，而信道的信道容量滿足)( DRC ?，那么，根據(jù)香農(nóng)第三定理，可以對給定 的信源X先進行信源壓縮編碼，使編碼后的信息傳輸率為： )(39。 ≥ DRR 并且編碼的平均失真度DCd ?)(，這時39。R必滿足 )( 39。 ≥ DRRC ( 5 3 6 ) 然后，把壓縮后的信源通過信道傳輸，由于上式（ 5 36 ）左半邊不等式存在，根據(jù)香農(nóng)第 二定理，則存在一種信道編碼，使壓縮后的信源通過信道傳輸后，錯誤概率趨于 0 ，因此，在 接收再現(xiàn)信源的信息時，總的失真或錯誤不會超過允許失真度D。這意味著引起的失真是由 信源壓縮造成的，而信道傳輸不會造成新的失真或錯誤。反之，若)( DRC ?，即不能保證信 源壓縮后的信息率CR ?39。，所以香農(nóng)第二定理不能成立，這樣信道中引起的失真或錯誤不可避 免，必然會在接收端再現(xiàn)信源信息時，總的失真或錯誤大于D。 第 5章 限失真信源編碼 最佳標量量化 設(shè)信源符號的取值區(qū)間為),( 0 naa，即： naxa ??0 0a可為負無限值，na可為正無限值。令x的概率密度函數(shù)為)( xp，當量化級數(shù)為 n時，量化就把上面區(qū)間分成n個小區(qū)間，每個區(qū)間內(nèi)定一個量化值iy，若各區(qū)間端點為 1?ia和ia，必有： nnn ayayaya ≤ ≤ ≤ ≤ ≤ 12110 ? 當失真函數(shù)為),( yxd時，平均失真度 D 為： ? ????niaajiiidxxpyxdnD11)(),()( ( 5 37) 在上述量化中，由于x是一個標量，所以稱為標量量化，而最佳標量量化就是在一定的n 值時，選則ia和iy使)( nD最小，此時的信息率為： nR l o g? 限失真信源編碼的具體方法 第 5章 限失真信源編碼 最佳標量量化在一般情況下是比較難理解的，對于絕對值|| yx ?型的失真函數(shù)，即 失真只與x和y的差的絕對值有關(guān)，它可以用遞推算法獲得近似解。 下面依據(jù)公式（ 5 37 ）尋找最佳量化的必要條件，它有兩個必要條件，下面分別討論。 首先固定iy求式（ 5 38 ）對ia的偏導數(shù)，并使之為 0 ，得： 0)(),()(),( 1 ?????? iiiiiiiapyadapyadaD 即： ),(),( 1?? iiii yadyad 由此式可見， D 的極值出現(xiàn)在區(qū)間的分界點對iy和1?iy有同樣的失真，由絕對值|| yx ? 型的失真函數(shù)，可求得一維標量量化的第一個必要條件為： iiii ayya ??? ? 1 即： 21???iiiyya ( 5 38) 第 5章 限失真信源編碼 此式表明：當各量化值已選定后，區(qū)間的的分界必在兩個量化值的中點。 其次，固定ia，求式（ 5 37 ）對iy的偏導數(shù)，并使之為 0 ，此時將與具體的失真函數(shù)有 關(guān)，由平方失真函數(shù)2)(),( yxyxd ??可得： ? ?? ??????????? iiiiaaaaiiiidxxpyxdxxpyxyy 1 10)()(2)()(D 2 則可解出一維標量量化的第二個必要條件為： ?????iiiiaaaaidxxpdxxxpy11)()( 此式表明：在這個條件下，D也是取極小值，且iy應(yīng)為),1 ii aa ?（區(qū)間內(nèi)對)( xp的重心， 由絕對值失真可得： ?? ? ??????????????? ?iiiiiiayiiaayaiiiiidxxpyxydxxpxyydxxpyxyy)()()()()(||D1 1 ?????iiiiayyadxxpdxxp )()(1 即：????iiiiayyadxxpdxxp )()(1 ( 5 3 9 ) 第 5章 限失真信源編碼 矢量量化 矢量量化編碼是上述一維標量量化編碼的自然發(fā)展，它是 20 世紀 70 年代末以來 隨著數(shù)字技術(shù)和語音低速率編碼的需求而迅速發(fā)展起來的，并在量化領(lǐng)域取得突破性 進展的一項新技術(shù)。其中最有實際價值的是類似于標量量化，用實驗方法基本解決多 維矢量量化的設(shè)計問題，同時還不斷提出很多快速搜索實現(xiàn)算法。 標量量化是逐個樣點量化，而矢量量化是將K個信號樣點分為一組的多維量化，即 將K維空間中的一個信號矢量進行多維量化。若 用kQ表示K維矢量量化編碼，則有： ? ?ikk yRQ ?：，其中：Miy 2 , 2 , 1 , 0 ???? ? 也就是說，矢量量化編碼是將一個K維的空間的模擬連續(xù)量 kRx ?變化為另一個K 維空間的一個有限子空間的整數(shù)集合為： ? ? ki RCy ?? 這里有限大小的碼本 MC 2?即為 2 的方冪，而碼字iy又稱為恢復矢量，M等于K 維X矢量編碼的碼位數(shù)，相應(yīng)KM /等于平均每個取樣值所含的碼數(shù)。與標量量化不同， 矢量量化很容易做到每個取樣值所含的碼數(shù)小于 1 。 第 5章 限失真信源編碼 由以上分析可知，矢量量化的過程可以分解為編碼與譯碼兩個過程，如圖 5 . 3 所示： u)( ua理 想 信 道)( jiβ編 碼 器 譯 碼 器ii ji v 圖 矢量量化編譯碼過程 矢量量化的編碼可以分解為兩個變換（編碼、譯碼）的乘積，用數(shù)學知識表示為： ????kQ ? ?jNkk yIRQ ? ??? ?? ??： 其中：? ?NN iiiI , 21 ?? ( 5 40) 式（ 5 40 ）表示：對于屬于 K 維 樣值空間的某個連續(xù)矢量X，可以通過矢量編碼器將其 變成某個信道符號標記) , 2 , 1( Nji j ??，即共有N個信道符號標記，經(jīng)過理想信道傳輸?shù)? 接收端，再通過譯碼器將其變換成相應(yīng)碼本C中的基本碼字iy，并用它來代表改善端輸入的 K維樣值矢量X。因此，總的矢量量化編碼過程可以寫以表示為： ? ?)()( xaβxQy ki ?? 顯然，一維標量量化僅是上述K維矢量量化1?K的一個特例。 矢量量化可以由矢量量化器來完成，一是最佳的矢量量化器包括兩大部分，一個 是通過試驗迭代的群聚法形成的碼本，二是在碼本作用下的矢量量化器的量化過程。 矢量量化器的框圖如圖 5 . 4 所示。 矢 量 量 化（ 最 近 相 鄰 準 則 ）群 聚 法 設(shè) 計（ 最 近 相 鄰 準 則 ）訓 練 數(shù) 據(jù)碼 本最 后 碼 字信 道 符 號輸 入 矢 量ivu 圖 矢量量化器的設(shè)計框圖 矢量量化能否實際應(yīng)用，關(guān)鍵在于算法，目前的算法有：基于全搜索的快速算法和 準最佳碼本結(jié)構(gòu)的快速算法。隨著算法研究的進展以及超大規(guī)模集成電路技術(shù)的飛速發(fā) 展，矢量量化特別是語音參量的矢量量化編碼器已走向?qū)嵱没? 第 5章 限失真信源編碼 第 5章 限失真信源編碼 預測編碼 目前，解除信源相關(guān)性的方式主要包含兩類：一類是從時域 ( 空域 ) —— 預測編碼， 一類是從廣義頻域 —— 變換編碼。預測編碼是專門用于壓縮相關(guān)信源的，它也是一種 變化編碼，主要是在時域?qū)崿F(xiàn)。 ⒈預測編碼的基本原理 預測編碼不是直接對信源輸出的信號進行編碼，而是將信源輸出的信號通過預測 編碼后，再對信源輸出與被預測的差值進行編碼，其原理如圖 5 . 5 所示： iu編 碼 器iii uue ???iu?預 測 變 換 器?信 源 輸 出 編 碼 輸 出 圖 預測編碼原理圖 第 5章 限失真信源編碼 若變換是線