譯碼方法

在編碼理論中，譯碼（英語：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.