编码理论的历史

1948年，克劳德·香农发表了《通信的数学理论》，这篇文章由《贝尔系统技术杂志》的七月和十月刊分两部分发行。该文重点研究了如何最有效地对发送者要发送的信息进行编码的问题。在这篇基础性的论文中，他使用了诺伯特·维纳发展的概率论工具，而这些概率论工具用于通信理论在当时还尚处萌芽阶段。香农提出信息熵作为消息不确定性的量度，而实质上创造了信息论这个领域。

二进制戈莱码（英语：binary Golay code）在1949年被提出。更具体地说，它是一种每个24位字能够纠正三个错误、检测出第四个错误的纠错码。

汉明距离的二维可视化

理查德·汉明因在贝尔实验室在数值方法、自动编码系统以及错误检测和纠错码的成就于1968年获得了图灵奖。他发明了汉明码、汉明窗、汉明数和汉明距离等概念。

信源编码

信源编码的目的是让源数据变小。

定义

数据可以看作是随机变量X:Ω Ω -->→ → -->X{\displaystyle X:\Omega \rightarrow {\mathcal {X}}}，其中 x∈ ∈ -->X{\displaystyle x\in {\mathcal {X}}} 出现概率为 P[X=x]{\displaystyle \mathbb {P} [X=x]}。

数据用字母表Σ Σ -->{\displaystyle \Sigma } 中的字符串（单词）进行编码的。

码是一个函数 C:X→ → -->Σ Σ -->∗ ∗ -->{\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}（或当空字符串不在字母表内时为 Σ Σ -->+{\displaystyle \Sigma ^{+}}）。C(x){\displaystyle C(x)} 是与 x{\displaystyle x} 关联的码字。

码长写作 l(C(x)){\displaystyle l(C(x))}。

码长的期望值为 l(C)=∑ ∑ -->x∈ ∈ -->Xl(C(x))P[X=x]{\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]}

码字拼接C(x1,...,xk)=C(x1)C(x2)...C(xk){\displaystyle C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})}.

空字符串的码字为空字符串本身：C(ϵ ϵ -->)=ϵ ϵ -->{\displaystyle C(\epsilon )=\epsilon }

性质

当 C:X→ → -->Σ Σ -->∗ ∗ -->{\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}} 为单射时，是非奇异码。

当 C:X∗ ∗ -->→ → -->Σ Σ -->∗ ∗ -->{\displaystyle C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}} 为单射时，是唯一可解码（英语：Uniquely decodable code）。

如果 C(x1){\displaystyle C(x_{1})} 和 C(x2){\displaystyle C(x_{2})} 相互不是另一个的前缀，则 C:X→ → -->Σ Σ -->∗ ∗ -->{\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}} 是即时码。

原理

信源的熵是信息的度量。基本上，信源编码在尽量减少信源的冗余，用携带更多信息的更少的比特来表示信源。

明确试图根据特定的假定概率模型来最小化消息的平均长度被称为熵编码。

有各种采用信源编码方案试图达到信源熵的极限的技术。C(x) ≥ H(x)，其中 H(x) 为信源熵（比特率），C(x) 为压缩后的比特率。特别指出，没有源编码方案可以比信源的熵更好。

例子

传真传输使用简单的游程编码。信源编码去除所有发射机必要发送以外所有多余数据，降低了传输所需的带宽。

参见

编码增益（英语：Coding gain）

覆盖码（英语：Covering code）

前向错误更正

群试（英语：Group testing）

汉明距离、汉明重量

信息论

李距离

多天线研究中的空间编码和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.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。