【計算機科學與技術】資訊論筆記（10）：通用信源編碼

200804

本篇是學習資訊論的入門筆記，希望能與各位分享進步！這是第十章也是最後一章：通用信源編碼~

文章目錄

• • 10. 通用信源編碼
  • • 10.1 通用碼與信道容量
    • 10.2 二進制序列的通用編碼
    • 10.3 算術編碼
    • 10.4 Lempel-Ziv編碼

10. 通用信源編碼

10.1 通用碼與信道容量

• 備援度：如果使用的碼的碼長為 l ( x ) l(x) l(x)，并假設該碼通過Huffman編碼所得，相應的機率為 q ( x ) = 2 − l ( x ) q(x)=2-l(x) q(x)=2−l(x)， 定義碼的備援度為編碼的期望長度與期望長度的下界之差：

R ( p θ , q ) = E p θ [ l ( X ) ] − ( − E p θ [ log ⁡ p θ ( X ) ] ) = D ( p θ ∣ ∣ q ) R(p_\theta,q) = E_{p_\theta}[l(X)] - (-E_{p_\theta}[\log p_\theta(X)]) = D(p_\theta || q) R(pθ​,q)=Epθ​​[l(X)]−(−Epθ​​[logpθ​(X)])=D(pθ​∣∣q)

其中 q ( x ) = 2 − l ( x ) q(x) = 2^{-l(x)} q(x)=2−l(x)為對應碼字長度 l ( x ) l(x) l(x)的分布。

• 編碼目标：無論真實分布 p θ p_θ pθ​如何，總希望找到一個編碼，能始終表現得很好。
• 最小最大備援度：定義為

R ∗ = min ⁡ q max ⁡ p θ R ( p θ , q ) = min ⁡ q max ⁡ p θ D ( p θ ∣ ∣ q ) R^\ast = \min_q \max_{p_\theta}R(p_\theta,q) = \min_q\max_{p_\theta}D(p_\theta ||q) R∗=qmin​pθ​max​R(pθ​,q)=qmin​pθ​max​D(pθ​∣∣q)

• 編碼器：為求得分布 q q q，使它在相時熵意義下盡可能與所有可能的 p θ p_θ pθ​ 接近，對于信道 { θ , p θ ( x ) , X } \{θ, p_θ(x), X\} {θ,pθ​(x),X}的轉移矩陣，它的行等于信源的可能分布 p θ p_θ pθ​ 。
• 結論：最小最大備援度 R ∗ R^\ast R∗等于該信道的容量，且達到信道容量時的輸入分布導出該信道的輸出分布，即是此時的最優碼分布。信道容量為

C = max ⁡ π ( θ ) ∑ θ π ( θ ) p θ ( x ) log ⁡ p θ ( x ) q π ( x ) C = \max_{\pi(\theta)}\sum_\theta \pi(\theta)p_\theta(x)\log\frac{p_\theta(x)}{q_\pi(x)} C=π(θ)max​θ∑​π(θ)pθ​(x)logqπ​(x)pθ​(x)​

其中

q π ( x ) = ∑ θ π ( θ ) p θ ( x ) q_\pi(x) = \sum_\theta\pi(\theta)p_\theta(x) qπ​(x)=θ∑​π(θ)pθ​(x)

• 定理10.1.1：設信道 p ( x ∣ θ ) p(x|θ) p(x∣θ)的各行分别為 p 1 , p 2 , … , p m p_1, p_2,…, p_m p1​,p2​,…,pm​，則它的容量為

C = R ∗ = min ⁡ q max ⁡ p θ D ( p θ ∣ ∣ q ) C = R^\ast =\min_q\max_{p_\theta}D(p_\theta ||q) C=R∗=qmin​pθ​max​D(pθ​∣∣q)

其中，最小值時的分布 q q q為達到信道容量時的輸入分布 π ( θ ) π(θ) π(θ)的所導出的輸出分布

q ∗ ( x ) = q π ∗ ( x ) = ∑ θ π ∗ ( θ ) p θ ( x ) q^\ast(x) = q_{\pi^\ast}(x) =\sum_\theta\pi^\ast(\theta)p_\theta(x) q∗(x)=qπ∗​(x)=θ∑​π∗(θ)pθ​(x)

10.2 二進制序列的通用編碼

• 脫機算法描述：計算0、1比例，算法為兩階段描述：
  • 獲得1的數目 k k k；（編碼比特數： ⌈ log ⁡ ( n + 1 ) ⌉ \lceil \log(n+1) \rceil ⌈log(n+1)⌉）
  • 給所有 k k k個1的上面序列一個确定的下标 ⌈ log ⁡ C n k ⌉ \lceil \log C_n^k \rceil ⌈logCnk​⌉。
• 兩階段編碼長度估計：總長度為

l ( x n ) ⩽ log ⁡ ( n + 1 ) + log ⁡ C n k + 2 ⩽ n H ( k n ) + 1 2 log ⁡ n − 1 2 log ⁡ ( π k ( n − k ) n 2 ) + 3 l(x^n)\leqslant \log(n+1) + \log C_n^k +2 \leqslant nH(\frac{k}{n})+\frac{1}{2}\log n - \frac{1}{2}\log(\pi\frac{k(n-k)}{n^2})+3 l(xn)⩽log(n+1)+logCnk​+2⩽nH(nk​)+21​logn−21​log(πn2k(n−k)​)+3

• 結論：編碼序列的代價大約等于 ( log ⁡ n ) / 2 (\log n)/2 (logn)/2比特，與對應于 ( k / n ) (k/n) (k/n)的伯努利分布的香農碼的最優代價相比，上述描述的代價更大。
• 兩階段編碼缺陷：壓縮器需要耐心等待到看完整個序列。
• 另一種編碼方法：編碼時使用總體上達到上述相同結果的混合分布。
  • 編碼分布： q ( x 1 , x 2 , . . . , x n ) = 2 − l ( x 1 , x 2 , . . . , x n ) q(x_1,x_2,...,x_n) = 2^{-l(x_1,x_2,...,x_n)} q(x1​,x2​,...,xn​)=2−l(x1​,x2​,...,xn​)。為 x 1 , x 2 , … , x n x_1, x_2,…,x_n x1​,x2​,…,xn​上所有Bernoulli(θ)分布的混合分布。

  • 性質：

    a.序列混合機率 p ( x 1 , x 2 , . . . , x n ) = ∫ 0 1 θ k ( 1 − θ ) n − k d θ = A ( n , k ) p(x_1,x_2,...,x_n) = \int_0^1 \theta^k(1-\theta)^{n-k}d\theta = A(n,k) p(x1​,x2​,...,xn​)=∫01​θk(1−θ)n−kdθ=A(n,k)

    b.機率遞歸公式： A ( n , k ) = n − k k + 1 A ( n , k + 1 ) A(n,k) = \frac{n-k}{k+1}A(n,k+1) A(n,k)=k+1n−k​A(n,k+1)

    c.初值 A ( n , n ) = 1 n + 1 A(n,n) = \frac{1}{n+1} A(n,n)=n+11​

    d.編碼碼字長度估計： log ⁡ 1 q ( x n ) ⩽ log ⁡ ( n + 1 ) + log ⁡ C n k + 1 \log\frac{1}{q(x^n)} \leqslant \log(n+1) + \log C_n^k +1 logq(xn)1​⩽log(n+1)+logCnk​+1。

    結論：與上述的兩階段錨述相比，長度相差在1 比待之内。

  • 與最優編碼器的差距：若實際信源服從Bernoulli(θ)，則最優碼的碼長需要 n H ( k / n ) nH(k/n) nH(k/n)，但對于沒有任何假設的信源分布而言，上述混合分布達到的碼字長度與之相比超出的代價在 ( log ⁡ n ) / 2 (\log n)/2 (logn)/2比特之間。

10.3 算術編碼

• 字元序列的編碼是一個區間，它的長度随着增加更多的字元到序列中而減少。
• 給定任意長度 n n n和機率密度函數 q ( x 1 , x 2 , … , x n ) q(x_1, x_2,…, x_n) q(x1​,x2​,…,xn​)，算術編碼程式能夠以長度 − log ⁡ ( q ( x 1 , x 2 , … , x n ) ) + 2 -\log(q(x_1, x_2,…, x_n))+2 −log(q(x1​,x2​,…,xn​))+2比特編碼序列 x 1 , x 2 , … , x n x_1, x_2,…, x_n x1​,x2​,…,xn​。
• 如果信源為i.i.d.，并假定分布 q q q等于資料的真實分布 p p p，這個程式能達到的平均分組長度與熵相比超出的部分在2比持之内。
• 盡管對固定的分組長度，此程式不一定是最優的，但這個程式是增量式的，而且對任意分組長度都适用。

10.4 Lempel-Ziv編碼

• 自适應字典式壓縮算法。LZ77或滑動窗Lempel-Ziv算法與LZ78或樹結構Lempel-Ziv算法。
• Lempel-Ziv編碼：設 R n ( X n ) R_n(X^n) Rn​(Xn)表示我們在過去觀察到 n n n長字元組 X n X^n Xn的最近時刻，則 ( log ⁡ R n ) / n → H ( X ) (\log R_n)/n\to H(X) (logRn​)/n→H(X)，且描述再現時間的編碼是漸進最優的。如果序列可以解析為此前未出現過的最短詞組， l ( x n ) l(x^n) l(xn)為解析序列的描述長度，則對任意平穩周遊過程 { X i } \{X_i\} {Xi​}，均有

lim ⁡ sup ⁡ 1 n l ( X n ) ⩽ H ( X ) a . s . \lim \sup \frac{1}{n} l(X^n) \leqslant H(X)\quad a.s. limsupn1​l(Xn)⩽H(X)a.s.