译码方法

在编码理论中，译码（英語：decoding）是将接收到的消息译成给定码元的码字（英语：codewords）的过程。有许多常用的将消息映射到码字的方法。这些方法通常用于在有噪信道（如二元对称信道（英语：binary symmetric channel））传输后恢复消息。

记号

${\displaystyle C\subset \mathbb {F} _{2}^{n}}$ 是指长度为 ${\displaystyle n}$ 的二元码（英语：binary code）；${\displaystyle x,y}$ 为 ${\displaystyle \mathbb {F} _{2}^{n}}$ 的元素；而 ${\displaystyle d(x,y)}$ 为它们之间的距离。

理想观察者译码

给定信号 ${\displaystyle x\in \mathbb {F} _{2}^{n}}$，则理想观察者译码会生成码字 ${\displaystyle y\in C}$。该过程得到这个解：

${\displaystyle \mathbb {P} }$(y发送 | x接收)

例如，在传输后可以选择最接近消息 ${\displaystyle x}$ 的码字 ${\displaystyle y}$。

译码约定

所有码字都不满足期望概率：可能会有多于一个码字其转变为接收到的消息的似然性相等。在此情况下，发送方和接收方必须提前对译码约定达成一致。广泛使用的约定有：

1. 请求重发码字 -- 自动重传请求
2. 从最接近码字的集合中随机选取码字

最大似然译码

更多信息：最大似然估计

给定一个接收到的码字 ${\displaystyle x\in \mathbb {F} _{2}^{n}}$，最大似然译码选取可以最大化

${\displaystyle \mathbb {P} }$(x接收 | y发送)

的码字 ${\displaystyle y\in C}$，即会最大化发送 ${\displaystyle y}$ 条件下，接收到 ${\displaystyle x}$ 的概率。如果所有码字的发送概率都相等的话，则此方法与理想观察者译码等价。 事实上，根据贝叶斯定理，

${\displaystyle {\begin{aligned}\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac {\mathbb {P} (x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb {P} (y{\mbox{ sent}})}}\\&{}=\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot {\frac {\mathbb {P} (x{\mbox{ received}})}{\mathbb {P} (y{\mbox{ sent}})}}.\end{aligned}}}$

在固定 ${\displaystyle \mathbb {P} (x{\mbox{ received}})}$ 下，可以重建 ${\displaystyle x}$，而由于所有符号等可能地发送， ${\displaystyle \mathbb {P} (y{\mbox{ sent}})}$ 为常数。 于是 ${\displaystyle y}$ 的函数 ${\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}$ 在最大化的同时， ${\displaystyle \mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})}$ 也会最大化，因而遵循该断言。

与理想观察者译码一样，对于非唯一译码，也需要事先达成译码约定。

最大似然译码问题可以建模为整数规划问题。^[1]

最大似然译码问题是“乘积函数边缘化"问题（已通过运用广义分配律（英语：generalized distributive law）解决）的一个实例。^[2]

最小距离译码

给定一个接收到的码字 ${\displaystyle x\in \mathbb {F} _{2}^{n}}$，最小距离译码会选出使汉明距离最小化的码字 ${\displaystyle y\in C}$：

${\displaystyle d(x,y)=\#\{i:x_{i}\not =y_{i}\}}$

即选取尽可能接近 ${\displaystyle x}$ 的码字 ${\displaystyle y}$。

注意到如果一个离散无记忆信道（英语：discrete memoryless channel）误差概率 ${\displaystyle p}$ 小于二分之一，则最小距离译码等价于最大似然译码，因为若

${\displaystyle d(x,y)=d,\,}$

则：

${\displaystyle {\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}}$

该式（由于 p 小于二分之一）是通过最小化 d 来最大化的。

最小距离译码也叫最近邻居译码。可以用标准阵列（英语：standard array）来辅助或自动译码。在满足下列条件的情况下，最小距离译码是一种合理的译码方法：

1. 出现差错的概率 ${\displaystyle p}$ 与符号的位置无关
2. 差错是独立事件 - 消息中某一位置出现差错不会影响其他位置

这些假设对于在二元对称信道（英语：binary symmetric channel）中传输时合理的。对于其他介质可能不适用，比如在DVD中，光盘上的一个划痕就可以引起很多相邻的符号或码字产生错误。

与其他译码方法一样，对于非唯一译码，需要事先达成译码约定。

校正子译码

伴随式译码（英語：syndrome decoding）是在有噪信道（即会有产生差错的信道）译码线性码（英语：linear code）的一种高效的方法。本质上，伴随式译码是最小距离译码使用一个简化的查找表。线性码允许这种译码。

假设 ${\displaystyle C\subset \mathbb {F} _{2}^{n}}$ 是奇偶檢驗矩陣为 ${\displaystyle H}$的，长为 ${\displaystyle n}$、最小距离为 ${\displaystyle d}$ 的线性码。则显然 ${\displaystyle C}$ 有纠正信道产生的

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }$

个错的能力（因为如果产生了不到 ${\displaystyle t}$ 个差错，则最小距离译码仍可以正确译出传输错误的码字）。

现在假设码字 ${\displaystyle x\in \mathbb {F} _{2}^{n}}$ 在该信道中发送，发生错误图样 ${\displaystyle e\in \mathbb {F} _{2}^{n}}$。则收到 ${\displaystyle z=x+e}$ 。普通的最小距离译码会在大小为 ${\displaystyle |C|}$ 的表中找向量 ${\displaystyle z}$ 最接近的匹配 - 即对于所有 ${\displaystyle y\in C}$，元素（不一定唯一）${\displaystyle c\in C}$ 都满足

${\displaystyle d(c,z)\leq d(y,z)}$.

伴随式译码利用了奇偶校验矩阵的性质：对于所有 ${\displaystyle x\in C}$

${\displaystyle Hx=0}$.

接收到的 ${\displaystyle z=x+e}$ 的伴随式定义为：

${\displaystyle Hz=H(x+e)=Hx+He=0+He=He}$

在二元对称信道（英语：Binary symmetric channel）中进行最大似然译码，要从大小为 ${\displaystyle 2^{n-k}}$ 的预计算表格中查询，将 ${\displaystyle He}$ 映射到 ${\displaystyle e}$。
注意到这比起标准阵列译码（英语：standard array）的复杂度已经明显减小了。

不过，在假设传输中不会超过 ${\displaystyle t}$ 个差错的前提下，接收方仅仅需要在更小的表格（对于二元码来说）中查找 ${\displaystyle He}$ 这个值

${\displaystyle {\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}<|C|\\\end{matrix}}}$.

该表是针对所有可能的错误图样 ${\displaystyle e\in \mathbb {F} _{2}^{n}}$ 下，${\displaystyle He}$ 的预计算值的。

已知 ${\displaystyle e}$，译码 ${\displaystyle x}$ 就不是难事了：

${\displaystyle x=z-e}$

部分响应最大似然法

部分响应最大似然法（PRML）是一种将弱模拟信号从磁盘或磁带驱动器的的磁头转换成数字信号的方法。

维特比译码器

维特比译码器使用维特比算法译码已经用基于卷积码的前向錯誤更正编码的比特流。 汉明距离用来作为硬判决维特比译码器的度量。 欧氏距离的平方用作软判决译码器的度量。

参见

• 差错检测与校正

来源

• Hill, Raymond. A first course in coding theory. Oxford Applied Mathematics and Computing Science Series. Oxford University Press. 1986. ISBN 0-19-853803-0.
• Pless, Vera. Introduction to the theory of error-correcting codes. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons. 1982. ISBN 0-471-08684-3.
• J.H. van Lint. Introduction to Coding Theory. GTM 86 2nd. Springer-Verlag. 1992. ISBN 3-540-54894-7.

参考文献

1. Feldman, Jon; Wainwright, Martin J.; Karger, David R. Using Linear Programming to Decode Binary Linear Codes 51 (3). March 2005: 954–972. doi:10.1109/TIT.2004.842696. |journal=被忽略 (帮助)
2. Aji, Srinivas M.; McEliece, Robert J. The Generalized Distributive Law. IEEE Transactions on Information Theory. March 2000, 46 (2): 325–343. doi:10.1109/18.825794.