Re: [機統] 資訊理論熵編碼證明

[arrenwu (最是清楚哇她咩)]

※ 引述《chun10396974 (娜嗲希摳老公)》之銘言：
: 手機發文排版請見諒
: 假設現有n個符號，且n為2的正整數次方，其機率由1至n遞減排列為p1, p2, ..., pm, ..., pn
: 其中自第m個開始其編碼後長度大於log2(n)，亦即log2(1/pm)>log2(n)
: 以下是我的猜測，但證明到一半卡住：
: 現在針對每個輸入額外多1bit作為檢查bit，若其編碼後長度>log2(n)，則不編碼，以log2(n)傳送；反之若編碼後長度<log2(n)則以原本熵編碼的log(1/pi)進行傳送，試證此方法的平均碼長較其entropy還高
: 我的做法是原本entropy為
: p1log2(1/p1) + p2log2(1/p2) + ... + pnlog2(1/pn) < log2(n)
: =p1log2(n) + ... pnlog2(n)        (1)
: 加上檢查bit後的平均碼長為
: p1log2(1/p1) + ... + p(m-1)log2(1/p(m-1)) + pmlog2(n) + pnlog2(n) + 1
:      (2)
: 原本是拿(2)去扣(1)的上界
: http://i.imgur.com/dnQmMxy.jpg
: 結果發現這樣證不出來，所以改成用檢查bit的碼長減entropy永遠大於0，即

: 1 + pm[log2(n)+log2(pm)] + p(m+1)[log2(n)+log2(p(m+1))] + ... +
: pn[log2(n)+log2(pn)] > 0?
: 到這邊卡住了，看起來也沒辦法用對數求和不等式？麻煩各位解惑，謝謝。
這部分可以用 log-sum inequlity 得出

下面所使用的log全部都是 log2，
同時，令 k = log(n)

https://i.imgur.com/suKH9Yi.jpg

其中 -Plog(P) <= 1 的證明來自
-Plog(P) <= -Plog(P) - (1-P)log(1-P) <= 1


--
角卷綿芽給予炭治郎的建議
https://i.imgur.com/0mPdESk.jpg
https://i.imgur.com/Ts4dBjy.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.195.96 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1735026803.A.528.html
※ 編輯: arrenwu (98.45.195.96 美國), 12/24/2024 16:18:44
推 chun10396974: 感謝