【計算機科學與技術】資訊論筆記（8）：率失真理論

200804

本篇是學習資訊論的入門筆記，希望能與各位分享進步！這是第八章：率失真理論~

文章目錄

• • 8. 率失真理論
  • • 8.1 量化
    • 8.2 定義
    • 8.3 率失真函數的計算

8. 率失真理論

• 離散信源的有損壓縮：信道描述 Q = ( q ( b j ∣ a K ) ) K × J Q=(q(b_j | a_K))_{K\times J} Q=(q(bj​∣aK​))K×J​。
• 連續信源：輸出消息在時間和取值上都連續的信源。

8.1 量化

• 量化分類：标量量化和矢量量化。
  • 标量量化：每個信源輸出分别量化。
  • 标量量化劃分：均勻量化（量化區域等長）和非均勻量化（量化區域可以不等長）。
  • 矢量量化：對信源輸出組合進行整體量化。
• 定義8.1.1（标量量化）：僅考慮一個采樣點的量化問題。将一個連續幅度值轉變成離散幅度值（有限個值） x ^ = Q ( x ) \hat{x}=Q(x) x^=Q(x)。 Δ i = d i − d i − 1 \Delta i = d_i - d_{i-1} Δi=di​−di−1​△i=di-di-1稱為量化步長。

• 最優（Max-Lloyd）量化器：信源 X X X的機率密度為 p ( x ) p(x) p(x)， x → x ^ x\to \hat{x} x→x^，量化均方誤差為

  D = E [ ( x − x ^ ) 2 ] = ∫ ( x − x ^ ) 2 p ( x ) d x = ∑ k = 1 K ∫ d k − 1 d k p ( x ) d x D = E[(x-\hat{x})^2] = \int (x-\hat{x})^2p(x)dx = \sum_{k=1}^K\int_{d_{k-1}}^{d_k}p(x)dx D=E[(x−x^)2]=∫(x−x^)2p(x)dx=k=1∑K​∫dk−1​dk​​p(x)dx

  為使 D D D最小，可得

  d k = 1 2 ( r k + r k + 1 ) , r k = ( ∫ d k − 1 d k x p ( x ) d x ) / ( ∫ d k − 1 d k p ( x ) d x ) d_k = \frac{1}{2}(r_k+r_{k+1}),r_k = (\int_{d_{k-1}}^{d_k}xp(x)dx)/(\int_{d_{k-1}}^{d_k}p(x)dx) dk​=21​(rk​+rk+1​),rk​=(∫dk−1​dk​​xp(x)dx)/(∫dk−1​dk​​p(x)dx)

  代表值 r k r_k rk​實際上是輸入的機率密度函數在區間 [ d k − 1 , d k ] [d_{k-1}, d_k] [dk−1​,dk​]上的中心矩；

• 均勻量化器：假設信源的機率密度函數關于Y軸對稱，僅考慮 x > 0 x>0 x>0的部分，量化間隔相等。量化值 r k = ( ( 2 k − 1 ) / 2 ) d r_k = ((2k-1)/2)d rk​=((2k−1)/2)d。目标：對給定機率密度函數 p ( x ) p(x) p(x)和量化分層數 K K K，可以确定 d d d，使失真最小。

  • 均勻量化失真：

    D = 2 ∑ k = 1 K / 2 − 1 ∫ ( k − 1 ) d k d ( 2 k − 1 2 d − x ) 2 p ( x ) d x + 2 ∫ ( K / 2 − 1 ) d ∞ ( K − 1 2 d − x ) 2 p ( x ) d x D=2 \sum_{k=1}^{K / 2-1} \int_{(k-1) d}^{k d}\left(\frac{2 k-1}{2} d-x\right)^{2} p(x) \mathrm{d} x+ 2 \int_{(K / 2-1) d}^{\infty}\left(\frac{K-1}{2} d-x\right)^{2} p(x) \mathrm{d} x D=2k=1∑K/2−1​∫(k−1)dkd​(22k−1​d−x)2p(x)dx+2∫(K/2−1)d∞​(2K−1​d−x)2p(x)dx

  • 性質：當信源在 [ ∗ d ∗ 0 , ∗ d ∗ K ] [*d*0,*d*K] [∗d∗0,∗d∗K]上均勻分布時，最優量化與均勻量化等價，且 Δ = ( d K − d 0 ) / K , D m i n = Δ 2 / 12 \Delta = (d_K-d_0)/K,D_{min} = \Delta^2/12 Δ=(dK​−d0​)/K,Dmin​=Δ2/12。

• 正态信源量化： x ∼ N ( 0 , σ 2 ) x\sim N(0,\sigma^2) x∼N(0,σ2)量化值計算：

  X ^ ( X ) = { 2 / π σ  當  x ≥ 0 − 2 / π σ  當  x < 0 \hat{X}(X)=\left\{\begin{array}{ll} \sqrt{2 / \pi} \sigma & \text { 當 } x \geq 0 \\ -\sqrt{2 / \pi} \sigma & \text { 當 } x<0 \end{array}\right. X^(X)={2/π

  ​σ−2/π

  ​σ​ 當 x≥0 當 x<0​

• 當代表點集合 { X ^ ( ω ) } \{\hat{X}(\omega)\} {X^(ω)} 給定時，可通過将信源随機變量 X X X映射為代表點中最接近于它的表示 X ^ ( ω ) \hat{X}(\omega) X^(ω)，使失真最小化。該映射定義一個X的區域構成的集合，稱為由代表點定義的Voronoi 劃分或狄利克雷劃分。代表點應該在各自劃分到的區域上使條件期望失真最小化。
• 滿足這兩個性質的量化就是Max-Lloyd量化器。
• 定義8.1.2（矢量量化）：将 n n n個連續的采樣值構成一個資料塊或矢量 x = [ x 1 , x 2 , … , x n ] T x=[x_1,x_2,…,x_n]^T x=[x1​,x2​,…,xn​]T，用有限個代表矢量 { X ^ 1 , X ^ 2 , . . . , X ^ K } \{\hat{X}_1,\hat{X}_2,...,\hat{X}_K\} {X^1​,X^2​,...,X^K​}中的一個來逼近連續矢量 x x x，代表矢量中的任一個矢量 X ^ k = { x ^ k 1 , x ^ k 2 , . . . , x ^ k n } \hat{X}_k=\{\hat{x}_{k1},\hat{x}_{k2},...,\hat{x}_{kn}\} X^k​={x^k1​,x^k2​,...,x^kn​}都是與 x x x相同維數的矢量。代表矢量的集合稱為碼本，碼本中的一個矢量稱為碼字。對一個給定的矢量 x x x，從碼本中找到一個碼字來盡可能逼近 x x x。

8.2 定義

• 失真度量：信源字母表與重建字母表的乘積空間到非負實數集上的映射。 失真矩陣

( d ( k , j ) ) K × J = [ d ( a 1 , b 1 ) d ( a 1 , b 2 ) ⋯ d ( a 1 , b J ) d ( a 2 , b 1 ) d ( a 2 , b 2 ) ⋯ d ( a 2 , b J ) ⋮ d ( a K , b 1 ) d ( a K , b 2 ) ⋯ d ( a K , b J ) ] (d(k, j))_{K \times J}=\left[\begin{array}{c} d\left(a_{1}, b_{1}\right) d\left(a_{1}, b_{2}\right) \cdots d\left(a_{1}, b_{J}\right) \\ d\left(a_{2}, b_{1}\right) d\left(a_{2}, b_{2}\right) \cdots d\left(a_{2}, b_{J}\right) \\ \vdots \\ d\left(a_{K}, b_{1}\right) d\left(a_{K}, b_{2}\right) \cdots d\left(a_{K}, b_{J}\right) \end{array}\right] (d(k,j))K×J​=⎣⎢⎢⎢⎡​d(a1​,b1​)d(a1​,b2​)⋯d(a1​,bJ​)d(a2​,b1​)d(a2​,b2​)⋯d(a2​,bJ​)⋮d(aK​,b1​)d(aK​,b2​)⋯d(aK​,bJ​)​⎦⎥⎥⎥⎤​

• 平均失真：

  D ˉ = ∑ k = 1 K ∑ j = 1 J p ( a k , b j ) d ( a k , b j ) = ∑ k = 1 K ∑ j = 1 J p ( a k ) p ( b j / a k ) d ( a k , b j ) \bar{D} = \sum_{k=1}^K\sum_{j=1}^Jp(a_k,b_j)d(a_k,b_j) = \sum_{k=1}^K\sum_{j=1}^Jp(a_k)p(b_j/a_k)d(a_k,b_j) Dˉ=k=1∑K​j=1∑J​p(ak​,bj​)d(ak​,bj​)=k=1∑K​j=1∑J​p(ak​)p(bj​/ak​)d(ak​,bj​)

• 平均失真度是信道傳輸品質的一種度量。在信源和編碼器給定的情況下，平均失真度是編碼器（信道機率矩陣）的函數。
• 定義8.2.1 一個 ( 2 n R , n ) (2^{nR},n) (2nR,n)率失真碼(rate distortion code)包括一個編碼函數 f n : X n → { 1 , 2 , . . . , 2 n R } f_n:X^n\to \{1,2,...,2^{nR}\} fn​:Xn→{1,2,...,2nR}和一個譯碼函數 g n : { 1 , 2 , . . . , 2 n R } → X ^ n g_n:\{1,2,...,2^{nR}\}\to\hat{\mathcal{X}}^n gn​:{1,2,...,2nR}→X^n，關于這個 ( 2 n R , n ) (2^{nR},n) (2nR,n)碼的失真定義為 D = E d ( X n , g n ( f n ( X n ) ) ) D=Ed(X^n,g_n(f_n(X^n))) D=Ed(Xn,gn​(fn​(Xn))).

• 定義8.2.2 稱率失真對 ( R , D ) (R,D) (R,D)是可達的，若存在一個 ( 2 n R , n ) (2^{nR},n) (2nR,n)率失真碼序列 ( f n , g n ) (f_n,g_n) (fn​,gn​) ， 滿足

  lim ⁡ n → ∞ E d ( X n , g n ( f n ( X n ) ) ) ⩽ D \lim_{n\to \infty}Ed(X^n,g_n(f_n(X^n)))\leqslant D n→∞lim​Ed(Xn,gn​(fn​(Xn)))⩽D

• 定義8.2.3 全體可達率失真對 ( R , D ) (R,D) (R,D)所成的集合閉包稱為信源的率失真區域。

• 信道傳輸的觀點：給定信源統計特性 p ( a k ) p(a_k) p(ak​)，允許的最大平均失真度 ∗ D ∗ *D* ∗D∗，信道傳輸率是前向轉移機率的下凸函數，信道傳輸的最低資訊量是 D D D的函數，即

  R ( D ) = min ⁡ Q { I ( X ; Y ) , E [ D ( X , Y ) ] ⩽ D } R(D) = \min_Q \{I(X;Y),E[D(X,Y)]\leqslant D\} R(D)=Qmin​{I(X;Y),E[D(X,Y)]⩽D}

• 率失真函數直覺意義：給定失真度，對固定信源，在滿足失真度要求 E { d ( X , Y ) } ⩽ D E\{d(X,Y)\}\leqslant D E{d(X,Y)}⩽D下，為重建信源所必須獲得的最小平均資訊量 I ( X , Y ) I(X,Y) I(X,Y)，也就是信源通過該信道必須傳輸給接收端的最小資訊率。

• 性質：

  a. R ( D ) R(D) R(D)的定義域為 ( D m i n , D m a x ) (D_{min},D_{max}) (Dmin​,Dmax​)，其中 D m i n = ∑ k = 1 K p ( a k ) [ min ⁡ j d ( a k , b j ) ] D_{min} = \sum_{k=1}^Kp(a_k)[\min_jd(a_k,b_j)] Dmin​=∑k=1K​p(ak​)[minj​d(ak​,bj​)]

  b. R ( D ) R(D) R(D)的定義域 D D D上的下凸函數。

  c. R ( D ) R(D) R(D)的定義域 D D D上的連續函數；

  d. R ( D ) R(D) R(D)的定義域 D D D上的單減函數。

• 定理8.2.1（率失真編碼定理，香農第三定理）：設 R ( D ) R(D) R(D)為某離散無記憶信源的率失真函數，對任意允許失真度 D ⩾ D m i n D\geqslant D_{min} D⩾Dmin​和任意小的正數 ε \varepsilon ε，以及足夠長的分組長度 n n n，則必存在一種信源編碼 W W W，其碼字個數 M ⩽ 2 n [ R ( D ) + ε ] M\leqslant 2^{n[R(D)+\varepsilon]} M⩽2n[R(D)+ε]，編碼後的平均失真度滿足 D ˉ ( W ) ⩽ D + ε \bar{D}(W) \leqslant D +\varepsilon Dˉ(W)⩽D+ε
• 綜上所述，如果不等式 C > R 1 ⩾ R ( D ) C>R_1\geqslant R(D) C>R1​⩾R(D)成立，通過定理3（率失真編碼）、定理1（備援編碼）和定理2（抗幹擾信道編碼），總能得到既有效、又可靠的通信系統；反之，不等式不成立，則在信宿端失真或錯誤不可避免。

8.3 率失真函數的計算

• **定理8.3.1 （二進制信道）**Bernoulli(p)信源在漢明失真度量下的率失真函數為

  R ( D ) = { H ( p ) − H ( D ) , 0 ≤ D ≤ min ⁡ { p , 1 − p } 0 , D > min ⁡ { p , 1 − p } R(D)=\left\{\begin{array}{ll} H(p)-H(D), & 0 \leq D \leq \min \{p, 1-p\} \\ 0, & D>\min \{p, 1-p\} \end{array}\right. R(D)={H(p)−H(D),0,​0≤D≤min{p,1−p}D>min{p,1−p}​

• **定理8.3.2 （高斯信道）**一個 N ∼ ( 0 , σ 2 ) N\sim(0,σ^2) N∼(0,σ2)信源在均方誤差失真度量下的率失真函數為

  R ( D ) = { 1 2 log ⁡ σ 2 D , 0 ≤ D ≤ σ 2 0 , D > σ 2 R(D)=\left\{\begin{array}{ll} \frac{1}{2} \log \frac{\sigma^{2}}{D}, & 0 \leq D \leq \sigma^{2} \\ 0, & D>\sigma^{2} \end{array}\right. R(D)={21​logDσ2​,0,​0≤D≤σ2D>σ2​

• 定理8.3.3 （并聯高斯信源的率失真） 設 X i ∼ N ( 0 , σ i 2 ) X_i\sim N(0,σ_i^2) Xi​∼N(0,σi2​) 為獨立的高斯随機變量，假定失真度量為 d ( x m , y m ) = ∑ i = 1 m ( x i − y i ) 2 d(x_m,y_m) = \sum_{i=1}^m(x_i-y_i)^2 d(xm​,ym​)=∑i=1m​(xi​−yi​)2。則率失真函數為

  R ( D ) = ∑ i = 1 m { 1 2 log ⁡ σ i 2 D i } R(D)=\sum_{i=1}^{m}\left\{\frac{1}{2} \log \frac{\sigma_{i}^{2}}{D_{i}}\right\} R(D)=i=1∑m​{21​logDi​σi2​​}

其中 D 1 = min ⁡ { λ , σ i 2 } D_1 = \min \{\lambda,\sigma_i^2\} D1​=min{λ,σi2​}，且 ∑ i = 1 m D i = D \sum_{i=1}^mD_i = D ∑i=1m​Di​=D。

• 率失真函數表達式：将最小化改寫為雙重最小化

R ( D ) = min ⁡ r ( x ^ ) min ⁡ q ( x ^ ∣ x ) : ∑ p ( x ) q ( x ^ ∣ x ) d ( x , x ^ ) ⩽ D ∑ x ∑ x ^ p ( x ) q ( x ^ ∣ x ) log ⁡ q ( x ^ ∣ x ) r ( x ^ ) R(D) = \min_{r(\hat{x})}\min_{q(\hat{x}|x):\sum p(x)q(\hat{x}|x)d(x,\hat{x})\leqslant D}\sum_x\sum_{\hat{x}}p(x)q(\hat{x}|x)\log \frac{q(\hat{x}|x)}{r(\hat{x})} R(D)=r(x^)min​q(x^∣x):∑p(x)q(x^∣x)d(x,x^)⩽Dmin​x∑​x^∑​p(x)q(x^∣x)logr(x^)q(x^∣x)​

若 A A A為其邊際分布 p ( x ) p(x) p(x)滿足失真限制的所有聯合分布構成的集合， B B B為乘積分布 P ( x ) r ( x ^ ) P(x)r(\hat{x}) P(x)r(x^)全體構成的集合，其中 r ( x ^ ) r(\hat{x}) r(x^)為任意， 則

R ( D ) = min ⁡ q ∈ B min ⁡ p ∈ A D ( p ∣ ∣ q ) R(D) = \min_{q\in B}\min_{p \in A}D(p||q) R(D)=q∈Bmin​p∈Amin​D(p∣∣q)

可應用交替最小化算法。