編碼理論

編碼理論（英語：Coding theory）是研究編碼的性質以及它們在具體應用中的效能的理論。編碼用於數據壓縮、加密、糾錯，最近也用於網絡編碼中。不同學科（如資訊論、電機工程學、數學、語言學以及電腦科學）都研究編碼是為了設計出高效、可靠的數據傳輸方法。這通常需要去除冗餘並校正（或檢測）數據傳輸中的錯誤。

盲文是一種廣泛使用數據壓縮以補償閱讀速度緩慢的編碼。

編碼共分四類：

1. 數據壓縮（或信源編碼）
2. 前向錯誤更正（或信道編碼）
3. 加密編碼
4. 線路碼

數據壓縮和前向錯誤更正可以一起考慮。

信源編碼試圖壓縮來自信源的數據以使傳輸更高效。這種做法每天都能在互聯網上見到，因為在互聯網上使用常見的ZIP格式來降低網絡負載，使檔案更小。

第二種，信道編碼，加入額外的數據位以使在傳輸信道有干擾存在的時候數據傳輸的強健性更強。普通用戶可能不知道許多應用中都使用了信道編碼。平常的音樂CD使用里德-所羅門碼來糾正劃痕和灰塵。在此應用中傳輸信道就是光碟本身。手機也使用編碼技術糾正高頻無線電傳輸的衰落和噪聲。數據數據機、電話傳輸、NASA都採用信道編碼技術來傳輸資訊，例如渦輪碼和低密度碼。

編碼理論的歷史

1948年，克勞德·香農發表了《通訊的數學理論》，這篇文章由《貝爾系統技術雜誌》的七月和十月刊分兩部分發行。該文重點研究了如何最有效地對傳送者要傳送的資訊進行編碼的問題。在這篇基礎性的論文中，他使用了諾伯特·維納發展的概率論工具，而這些概率論工具用於通訊理論在當時還尚處萌芽階段。香農提出資訊熵作為訊息不確定性的量度，而實質上創造了資訊論這個領域。

二進制戈萊碼在1949年被提出。更具體地說，它是一種每個24位元字能夠糾正三個錯誤、檢測出第四個錯誤的糾錯碼。

漢明距離的二維視覺化

理查德·漢明因在貝爾實驗室在數值方法、自動編碼系統以及錯誤檢測和糾錯碼的成就於1968年獲得了圖靈獎。他發明了漢明碼、漢明窗、漢明數和漢明距離等概念。

信源編碼

主條目：數據壓縮

信源編碼的目的是讓源數據變小。

定義

• 數據可看作隨機變數 $X:\Omega \rightarrow {\mathcal {X}}$，其中$x\in {\mathcal {X}}$出現概率為 $\mathbb {P} [X=x]$。
• 數據用字母表 $\Sigma$ 中的字串（單詞）進行編碼的。
• 碼是一個函數 $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$（或當空字串不在字母表內時為 $\Sigma ^{+}$）。$C(x)$ 是與 $x$ 關聯的碼字。
• 碼長寫作 $l(C(x))$。
• 碼長的期望值為 $l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]$
• 碼字拼接 $C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})$.
• 空字串的碼字為空字串本身：$C(\epsilon )=\epsilon$

性質

1. 當 $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ 為單射時，是非奇異碼。
2. 當 $C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}$ 為單射時，是唯一可解碼代碼。
3. 如果 $C(x_{1})$ 和 $C(x_{2})$ 相互不是另一個的字首，則 $C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ 是字首碼。

原理

信源的熵是資訊的度量。基本上，信源編碼在儘量減少信源的冗餘，用攜帶更多資訊的更少的位元來表示信源。

明確試圖根據特定的假定概率模型來最小化訊息的平均長度被稱為熵編碼。

有各種採用信源編碼方案試圖達到信源熵的極限的技術。C(x) ≥ H(x)，其中 H(x) 為信源熵（位元速率），C(x) 為壓縮後的位元速率。特別指出，沒有源編碼方案可以比信源的熵更好。

例子

傳真傳輸使用簡單的遊程編碼。信源編碼去除所有發射機必要傳送以外所有多餘數據，降低了傳輸所需的頻寬。

參見

• 編碼增益
• 覆蓋碼
• 前向錯誤更正
• 群試
• 漢明距離、漢明重量
• 資訊論
• 李距離
• 多天線研究中的空間編碼和MIMO

參考文獻

• Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
• Elwyn R. Berlekamp (1984), Algebraic Coding Theory, Aegean Park Press (revised edition), ISBN 0-89412-063-8, ISBN 978-0-89412-063-3.
• Randy Yates, A Coding Theory Tutorial.