Shannon 編碼定理

2021-01-13 泡泡網
Shannon 編碼定理
2018年02月27日 09:01作者：科普中國網編輯：網絡

Shannon 編碼定理

在資訊理論中，香農的信源編碼定理（或無噪聲編碼定理）確立了數據壓縮的限度，以及香農熵的操作意義。

信源編碼定理表明（在極限情況下，隨著獨立同分布隨機變量數據流的長度趨於無窮）不可能把數據壓縮得碼率（每個符號的比特的平均數）比信源的香農熵還小，不滿足的幾乎可以肯定，信息將丟失。但是有可能使碼率任意接近香農熵，且損失的概率極小。

碼符號的信源編碼定理把碼字的最小可能期望長度看作輸入字（看作隨機變量）的熵和目標編碼表的大小的一個函數，給出了此函數的上界和下界。

陳述

信源編碼是從信息源的符號（序列）到碼符號集（通常是bit）的映射，使得信源符號可以從二進位位元（無損信源編碼）或有一些失真（有損信源編碼）中準確恢復。這是在數據壓縮的概念。

信源編碼定理

在資訊理論中，信源編碼定理非正式地陳述為：

N個熵均為H(X)的獨立同分布的隨機變量在N→∞時，可以很小的信息損失風險壓縮成多於N H(X)bit；但相反地，若壓縮到少於 bit，則信息幾乎一定會丟失。

碼符號的信源編碼定理

令Σ1,Σ2表示兩個有限編碼表，並令Σ1*和Σ2*（分別）表示來自那些編碼表的所有有限字的集合。

設X為從Σ1取值的隨機變量，令 f 為從Σ1*到Σ2*的唯一可解碼，其中|Σ2|=a。令S表示字長 f (X)給出的隨機變量。

如果 f 是對X擁有最小期望字長的最佳碼，那麼：

證明：碼符號的信源編碼定理

對於1≤i≤n令si表示每個可能的xi的字長。定義 ，其中C會使得q1+...+qn=1。於是

其中第二行由吉布斯不等式推出，而第五行由克拉夫特不等式推出：

因此logC≤0。

對第二個不等式我們可以令

於是

因此

並且

因此由克拉夫特不等式，存在一種有這些字長的無前綴編碼。因此最小的S滿足

本詞條內容貢獻者為:

陳紅 - 副教授 - 西南大學

相關焦點

  • 老司機這樣解讀編碼與調製
    由於這個定理只局限在無噪聲的環境下計算信道最大數據傳輸速率，而在有噪聲的環境下仍然不能有效計算出信道最大數據傳輸速率，因此在 1948年，香農(Claude Shannon)把奈奎斯特的工作進一步擴展到了信道受到隨機噪聲幹擾的情況，即在有隨機噪聲幹擾的情況計算信道最大數據傳輸速率，這就是今天的香農定理。下面分別介紹這兩個定理。
  • 5G信道編碼之爭
    又因為信道編碼裡頭還劃分了數據信道編碼以及控制信道編碼，由於數據通常碼長比較長，而控制碼長非常短，不明所以然的人就誤以為長碼就是數據信道編碼，而短碼是控制信道編碼，其實這是一種誤讀的，其實長短碼都是用於描述數據信道編碼。
  • 哥德爾定理是如何玩壞數學的!
    關注 哆嗒數學網 每天獲得更多數學趣文哥德爾的不完備定理是那種能把你腦漿敲出來的一個定理。在上一篇博客，我們討論了定理本身及其影響。簡單說來，它們顯示出了數學本身的內在局限性。哥德爾第一定理與一致性、可證明性這兩個概念有關。一個數學系統（由一些假設組成，這些假設被稱作是「公理」）稱為一致的，如果它們沒有矛盾存在。
  • 數據科學家必須了解的事:中心極限定理
    來源：Pexels數據科學家必須了解的事：中心極限定理。你了解嗎？編碼之前，快速回顧今天，我想重構中心極限定理（CentralLimit Theorem），以及該定理與數據科學家的大量工作之間的關係。回顧直方圖首先，對於任何數據科學家來說，核心工具都是直方圖——一種非常簡單的圖表。雖然我們肯定會看到許多直方圖，但經常會忽略它的重要性。直方圖的核心目的是了解給定數據集的分布。
  • 超能課堂(137):5G信道編碼之爭
    其中RAN1工作組負責無線接入網物理層設計，其中就包括信道編碼。信道編碼也叫差錯控制編碼，可以說是每一代移動通信技術中的核心要素，是所有現代通信系統的基石。它承擔起數據糾錯功能，防止你手機發送的是「不行」，而在電磁波傳輸過程由於各種幹擾導致數據出現丟失，到了別人手機就變成了「行」，這樣的誤會可就大了，因此移動通信系統普遍引入信道編碼技術。那麼長短碼又是什麼？
  • 5G信道編碼技術及其標準化
    香農定理指出，在有噪聲環境下，數據傳輸的最大速率，是通信理論基礎和科學依據，也是近代資訊理論的基礎。 3GPP（第三代合作夥伴計劃）是移動通信領域的國際標準化組織，其定義了5G三大應用場景：增強移動寬帶(eMBB)、大規模機器通信(mMTC)和低時延高可靠通信(URLLC)。
  • 編碼解碼是什麼意思?URL 如何編碼解碼?為什麼要編碼?
    編碼解碼是什麼?編碼是信息從一種形式或格式轉換為另一種形式的過程，也稱為計算機程式語言的代碼簡稱編碼。用預先規定的方法將文字、數字或其它對象編成數碼，或將信息、數據轉換成規定的電脈衝信號。編碼在電子計算機、電視、遙控和通訊等方面廣泛使用。編碼是信息從一種形式或格式轉換為另一種形式的過程。解碼，是編碼的逆過程。
  • 世界十大最美方程式排行榜,勾股定理上榜你能get到它們的美嗎?
    世界十大最美方程式1、廣義相對論方程式2、標準模型方程式3、微積分方程式4、勾股定理方程式5、歐拉方程式6、狹義相對論方程式7、1=0.9無限循環方程式8、歐拉拉格朗日方程和諾特定理9、Callan-Symanzik方程式10、極小曲面方程1、廣義相對論方程式1915年愛因斯坦提出的宏觀物體引力理論
  • 華為工程師純技術解讀5G編碼標準
    在通信系統架構中，信源編碼的功能是實現模擬信號的數位化傳輸，而信道編碼則主要解決數字通信的可靠性問題。提高正確識別信號的能力和通信的可靠性，是保證信息高效、可靠傳輸的關鍵步驟。5G信道編碼技術究竟是怎麼回事？本文告訴你。
  • 物理層的編碼分類,物理介質相關編碼
    ，在運輸過程中不受損，同樣，線路編碼的目的就是使編碼後的二進位數據更適合線路傳輸。 物理層的編碼分類： 一類是和物理介質相關，常用的光接口碼型有NRZ、NRZI；電接口碼型有HDB3、BnZS、CMI、Manchester、MLT-3。 另一類和物理介質無關，比如百兆乙太網用的4B/5B編碼，千兆乙太網用的8B/10B編碼，萬兆乙太網用的64B/66B編碼。本文不再描述。
  • 鄧白氏編碼
    因此，鄧氏編碼早已成為國內企業開啟海外貿易的敲門磚。2、全球大型企業的管理規範一些財富500強企業也都通過各種方式將鄧氏編碼嵌入其內部運作系統和流程，對其業務夥伴的信息進行管理。因此，擁有鄧氏編碼是企業符合跨國採購商要求的首要標準。3、識別家族關聯企業的關鍵鄧氏編碼是成功建立企業族系樹的關鍵。由於同一企業在各地的實體都有自己的鄧氏編碼，一個龐大企業的族系樹裡就有可能包含許多不同的鄧氏編碼所關聯的企業實體。鄧白氏正是通過鄧氏編碼將全球2.85億家企業的母公司和子公司、總部和分公司連結組成族系樹。
  • 編碼方式有哪些_簡述常用的編碼方式
    編碼方式有哪些_簡述常用的編碼方式 　　1、ASCII碼 　　學過計算機的人都知道ASCII碼，總共有128個，用一個字節的低7位表示，0~31是控制字符如換行回車刪除等；32~126是列印字符，可以通過鍵盤輸入並且能夠顯示出來。
  • 中考(必考)定理補充:射影定理與角平分線第二性質定理
    今天為大家帶來的是兩個數學定理，這兩個定理並不在我國現行數學教材中。一般來說，老師都會在相似三角形章節中補充，但若當時上課沒聽到，就很難再見到了。兩個定理就是直角三角形射影定理和角平分線的第二性質定理。一、三角形射影定理直角三角形中，斜邊上的高是兩條直角邊在斜邊上的射影的比例中項；每一條直角邊是這條直角邊在斜邊上的射影和斜邊的比例中項。
  • 費馬小定理與歐拉定理Ⅰ
    費小定理與歐拉定理Ⅰ費馬小定理我們對費馬小定理和歐拉定理應該非常熟悉。
  • 正弦定理、餘弦定理
    正弦定理（Law of Sines）在一個三角形中，各邊和它所對角的正弦的比值相等。餘弦定理（Law of Cosines）三角形中任何一邊的平方 = 其它兩邊的平方和減去這兩邊與它們的夾角的餘弦的積的兩倍。
  • 數學教育定理-切消定理
    切消定理是確立相繼式演算重要性的主要結果。
  • 香農定理 與 奈奎斯特定理 例題分析
    奈奎斯特定理與香農定理作為物理層為數不多、能出計算題的知識點，會時常被出題老師拿來小考一下。
  • 戴維寧定理和諾頓定理
    諾頓定理的工程場景電網絡本身較為複雜，但所要求解的只是其中一條支路上的電壓或電流響應，此時可以使用諾頓定理，將待求支路以外部分用一個電流源和電阻/阻抗的並聯形式加以替換，從而將待求支路看成是並在一個實際電流源上，進而可以是用簡單的一個電流源和兩個電阻並聯的模型，來實現整個待求響應的分析。
  • 弦切角定理及推論-相交弦定理、切割線定理
    ~~~~~~~分--隔--符~~~~~~~弦切角定理：弦切角的度數等於它所夾的弧所對的圓心角度數的一半，等於它所夾的弧所對的圓周角度數
  • 壞小孩定理與貝克爾定理
    壞小孩定理，也稱貝克爾定理，是經濟學家貝克爾在分析利己主義和利他主義的基礎上提出來的。所謂的「壞小孩定理」，意味為人父母者對於子女都具有「利他心」，都會為子女的利益和幸福著想，雖對不同的子女會有程度上的區別，但基本上都會為每個小孩的利益著想。不過，為人子女者卻往往有「自私自利」者，貝克爾就稱這些只具「利己心」卻沒有「利他心」的子女為「壞小孩」。