查看“︁译码方法”︁的源代码

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

==记号==
<math>C \subset \mathbb{F}_2^n</math> 是指长度为 <math>n</math> 的{{le|二元码|binary code}}；<math>x,y</math> 为 <math>\mathbb{F}_2^n</math> 的元素；而 <math>d(x,y)</math> 为它们之间的距离。

==理想观察者译码==

给定信号 <math>x \in \mathbb{F}_2^n</math>，则'''理想观察者译码'''会生成码字 <math>y \in C</math>。该过程得到这个解：

:<math>\mathbb{P}</math>({{mvar|y}}发送 | {{mvar|x}}接收)

例如，在传输后可以选择最接近消息 <math>x</math> 的码字 <math>y</math>。

=== 译码约定 ===

所有码字都不满足期望概率：可能会有多于一个码字其转变为接收到的消息的似然性相等。在此情况下，发送方和接收方必须提前对译码约定达成一致。广泛使用的约定有：
:# 请求重发码字 -- [[ARQ|自动重传请求]]
:# 从最接近码字的集合中随机选取码字

==最大似然译码==
{{Further|最大似然估计}}

给定一个接收到的码字 <math>x \in \mathbb{F}_2^n</math>，'''[[最大似然估计|最大似然]]译码'''选取可以[[最优化|最大化]]

:<math>\mathbb{P}</math>({{mvar|x}}接收 | {{mvar|y}}发送)

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

:<math>
\begin{align}
\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{align}
</math>

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

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

最大似然译码问题可以建模为[[整数规划]]问题。<ref name = feldman>{{cite news | title=Using Linear Programming to Decode Binary Linear Codes | first1=Jon | last1=Feldman |first2=Martin J. | last2=Wainwright | first3=David R. | last3=Karger | journal=IEEE Transactions on Information Theory | volume=51 | issue=3 | pages=954–972 |date=March 2005 | doi=10.1109/TIT.2004.842696}}</ref>

最大似然译码问题是“乘积函数边缘化"问题（已通过运用{{le|广义分配律|generalized distributive law}}解决）的一个实例。<ref name=GenDistLaw>{{cite journal | last1=Aji | first1=Srinivas M. | last2=McEliece | first2=Robert J. | title=The Generalized Distributive Law | journal=IEEE Transactions on Information Theory |date=March 2000 | volume=46 | issue=2 | pages=325–343 | doi=10.1109/18.825794}}</ref>

==最小距离译码==

给定一个接收到的码字 <math>x \in \mathbb{F}_2^n</math>，'''最小距离译码'''会选出使[[汉明距离]]最小化的码字 <math>y \in C</math>：

:<math>d(x,y) = \# \{i : x_i \not = y_i \}</math>

即选取尽可能接近 <math>x</math> 的码字 <math>y</math>。

注意到如果一个{{le|离散无记忆信道|discrete memoryless channel}}误差概率 <math>p</math> 小于二分之一，则''最小距离译码''等价于''最大似然译码''，因为若

:<math>d(x,y) = d,\,</math>

则：

:<math>
\begin{align}
\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{align}
</math>

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

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

:#出现差错的概率 <math>p</math> 与符号的位置无关
:#差错是独立事件 - 消息中某一位置出现差错不会影响其他位置

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

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

==校正子译码==
<!-- [[伴随式译码]]重定向到这里 -->
'''伴随式译码'''（{{lang-en|'''syndrome decoding'''}}）是在''有噪信道''（即会有产生差错的信道）译码{{le|线性码|linear code}}的一种高效的方法。本质上，伴随式译码是''最小距离译码''使用一个简化的查找表。线性码允许这种译码。

假设 <math>C\subset \mathbb{F}_2^n</math> 是[[奇偶檢驗矩陣]]为 <math>H</math>的，长为 <math>n</math>、最小距离为 <math>d</math> 的线性码。则显然 <math>C</math> 有纠正信道产生的

:<math>t = \left\lfloor\frac{d-1}{2}\right\rfloor</math>

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

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

:<math>d(c,z) \leq d(y,z)</math>.

伴随式译码利用了奇偶校验矩阵的性质：对于所有 <math>x \in C</math>

:<math>Hx = 0</math>.

接收到的 <math>z=x+e</math> 的''伴随式''定义为：

:<math>Hz = H(x+e) =Hx + He = 0 + He = He</math>

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

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

:<math>
\begin{matrix}
\sum_{i=0}^t \binom{n}{i} < |C| \\
\end{matrix}
</math>.

该表是针对所有可能的错误图样 <math>e \in \mathbb{F}_2^n</math> 下，<math>He</math> 的预计算值的。

已知 <math>e</math>，译码 <math>x</math> 就不是难事了：

:<math>x = z - e </math>

== 部分响应最大似然法 ==

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

== 维特比译码器 ==

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

== 参见 ==
* [[差错检测与校正]]

==来源==
* {{cite book | last=Hill | first=Raymond | title=A first course in coding theory | url=https://archive.org/details/firstcourseincod0000hill | publisher=[[牛津大學出版社|Oxford University Press]] | series=Oxford Applied Mathematics and Computing Science Series | year=1986 | isbn=0-19-853803-0 }}
* {{cite book | last = Pless | first = Vera | authorlink=Vera Pless | title = Introduction to the theory of error-correcting codes | url = https://archive.org/details/introductiontoth0000ples_o1b9 | publisher = [[約翰威立|John Wiley & Sons]]|series = Wiley-Interscience Series in Discrete Mathematics | year = 1982| isbn = 0-471-08684-3 }}
* {{cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd | publisher=Springer-Verlag | series=[[數學研究生教材|GTM]] | volume=86 | year=1992 | isbn=3-540-54894-7 }}

== 参考文献 ==
{{reflist}}

[[Category:编码理论]]