数据编码理论/信息

编码器/解码器

接收输入数据序列并输出传输码的设备称为编码器。接收编码传输并输出原始数据的设备称为解码器。编码器和解码器可以根据其设计满足的特定规范而有很大差异。

代码的设计原因多种多样。使用代码的一些原因是

• 错误检测和纠正。发现和纠正噪声通信介质引入的错误的能力。
• 数据压缩。某些编码技术允许将大型数据缩小尺寸，以便更快地进行通信。
• 频谱扩展。某些代码允许将信号跨越多个频率进行扩展，以获得许多益处，包括抗干扰和抗阻塞，以及允许多个用户在同一频率范围内同时发送数据。
• 加密。某些代码可用于隐藏信息，使其仅供预期接收者访问。

本书不可能涵盖与数据压缩、加密或长距离通信相关的所有主题。对于这些主题，读者应参阅其他维基教科书和其他资源。本书将讨论数据编码，但不一定能讨论所有代码的用途或实现。

熵

假设我们有一个特定的代码，它包含实际上不携带任何信息的位，而是仅用于帮助传输。例如，这些可以是用于表示异步传输开始和结束的起始位和停止位、用于提供错误检查的CRC位，或任何数量的不同位。然后，这些额外的位与数据位组合在一起形成一个数据包或一个符号。了解传输系统中每个符号的平均信息量很重要。我们将此参数称为熵，并以“每符号位”为单位进行衡量。请注意，这不是物理学中用于描述能量耗散的熵。我们将用变量 H(S) 来标记熵。

假设我们的传输字母表包含集合 S 中的 K 个不同符号

$S=(S_{0},S_{1},S_{2}...,S_{K-1})$

这些不同的符号可以代表任何东西：位、双位、长序列等。在给定的传输方案中，这些不同的符号将具有不同的概率 Pk，具体取决于每个符号的传输可能性。我们可以用以下等式定义通信系统的熵

$H(S)=\sum _{k=0}^{K-1}P_{k}\log _{2}\left({\frac {1}{Pk}}\right)$

从这个等式中，我们可以为 H(S) 设置一些一般的界限

$0<H(S)<\log _{2}(K)$

我们可以看到，在完全确定性的系统中，H(S) 接近下限，即在该系统中，特定传输的概率为 Pk = 1。我们还可以看到，在所有不同符号等概率的情况下，H(S) 接近上限。

码长

我们有一个编码器接收数据输入，并输出一个特定的代码。此输出代码由于包含额外的非数据位，因此比输入数据序列更长。我们可以使用以下等式定义平均输出码长

${\bar {L}}=\sum _{k=0}^{K-1}P_{k}L_{k}$

其中 Pk 是输出每个不同传输代码的概率，Lk 是每个代码的长度。例如，假设我们有一个包含 2 个符号的字母表

S = {S0, S1}
S0 = 101010, P0 = .5, L0 = 6
S1 = 1100,   P1 = .5, L1 = 4

我们可以使用上述等式找到平均码长：5。

效率

编码系统的效率是每个符号的平均信息量与平均码长的比率。可能的最大效率为 1，理论上可以通过使用前缀码（将在下面讨论）获得。