编码理论

编码理论（英語：Coding theory）是研究编码的性质以及它们在具体应用中的性能的理论。编码用于数据压缩、加密、纠错（英语：error-correction），最近也用于网络编码中。不同学科（如信息论、電機工程學、数学、语言学以及计算机科学）都研究编码是为了设计出高效、可靠的数据传输方法。这通常需要去除冗余并校正（或检测）数据传输中的错误。

盲文是一种广泛使用数据压缩以补偿阅读速度缓慢的编码。

编码共分四类：^[1]

1. 数据压缩（或信源编码）
2. 前向錯誤更正（或信道编码）
3. 加密编码
4. 线路码

数据压缩和前向錯誤更正可以一起考虑（英语：Joint source and channel coding）。

信源编码试图压缩来自信源的数据以使传输更高效。这种做法每天都能在互联网上见到，因为在互联网上使用常见的ZIP格式来降低网络负载，使文件更小。

第二种，信道编码，加入额外的数据位以使在传输信道有干扰存在的时候数据传输的強健性更强。普通用户可能不知道许多应用中都使用了信道编码。平常的音乐CD使用里德-所罗门码来纠正划痕和灰尘。在此应用中传输信道就是光盘本身。手机也使用编码技术纠正高频无线电传输的衰落和噪声。数据调制解调器、电话传输、NASA都采用信道编码技术来传输信息，例如涡輪码（英语：turbo code）和低密度码。

编码理论的历史

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

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

 

汉明距离的二维可视化

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

信源编码

主条目：数据压缩

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

定义

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

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

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

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

• 码长的期望值为 ${\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]}$ 

• 码字拼接 ${\displaystyle C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})}$ .

• 空字符串的码字为空字符串本身：${\displaystyle C(\epsilon )=\epsilon }$ 

性质

1. 当 ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$  为单射时，是非奇异码。
2. 当 ${\displaystyle C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}}$  为单射时，是唯一可解码（英语：Uniquely decodable code）。
3. 如果 ${\displaystyle C(x_{1})}$  和 ${\displaystyle C(x_{2})}$  相互不是另一个的前缀，则 ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$  是即时码。

原理

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

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

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

例子

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

参见

• 编码增益（英语：Coding gain）
• 覆盖码（英语：Covering code）
• 前向錯誤更正
• 群试（英语：Group testing）
• 汉明距离、汉明重量
• 信息论
• 李距离
• 多天线研究中的空间编码和MIMO

注释

1. James Irvine, David Harle. "Data Communications and Networks". 2002. p. 18. section "2.4.4 Types of Coding". quote: "There are four types of coding"

参考文献

• 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, .