最大似然译码详解（最大似然解码，Maximum Likelihood Decoding）
【例子】假设编码函数 $e:B^3\to B^6$ 定义为：
$$ \begin{array}{l} e(000)=000000 \\ e(001)=001100 \\ e(010)=010011 \\ e(011)=011111 \\ e(100)=100101 \\ e(101)=101001 \\ e(110)=110110 \\ e(111)=111010 \end{array} $$求最大似然译码表，并对 100000 和 101010 进行译码。
【分析与解答】
写译码表
我们直接把代码字抄到第一行：
| $000000$ | $001100$ | $010011$ | $011111$ | $100101$ | $101001$ | $110110$ | $111010$ |
|---|---|---|---|---|---|---|---|
其中的单位元是 $000000$，课本上会记作 $\bar{0}$。把 第一行未列出的任意一个码字（这里我选择 000001），放到第二行开头，这叫做 陪集头（陪集首部，Coset Leader）：
| $000000$ | $001100$ | $010011$ | $011111$ | $100101$ | $101001$ | $110110$ | $111010$ |
|---|---|---|---|---|---|---|---|
| $000001$ | |||||||
拿它和上面的个码字进行异或，异或的结果写在交叉处：
| $000000$ | $\color{red}001100$ | $010011$ | $011111$ | $100101$ | $101001$ | $110110$ | $111010$ |
|---|---|---|---|---|---|---|---|
| $\color{red}000001$ | $\color{blue}001101$ | ||||||
如此完成此行。
| $000000$ | $001100$ | $010011$ | $011111$ | $100101$ | $101001$ | $110110$ | $111010$ |
|---|---|---|---|---|---|---|---|
| $000001$ | $001101$ | $010010$ | $011110$ | $100100$ | $101000$ | $101111$ | $111011$ |
把前两行未列出的任意一个码字（这里我选择 000010），放到第三行开头，同样的操作进行异或：
| $000000$ | $\color{red}001100$ | $010011$ | $011111$ | $100101$ | $101001$ | $110110$ | $111010$ |
|---|---|---|---|---|---|---|---|
| $000001$ | $001101$ | $010010$ | $011110$ | $100100$ | $101000$ | $101111$ | $111011$ |
| $\color{red}000010$ | $\color{blue}001110$ | ||||||
各行均如此操作，直到行数等于 $|N| = 2^n = 8$。
得到译码表：
$$ \begin{array}{llllllll}000000 & 001100 & 010011 & 011111 & 100101 & 101001 & 110110 & 111010 \\ 000001 & 001101 & 010010 & 011110 & 100100 & 101000 & 110111 & 111011 \\ 000010 & 001110 & 010001 & 011101 & 100111 & 101011 & 110100 & 111000 \\ 000100 & 001000 & 010111 & 011011 & 100001 & 101101 & 110010 & 111110 \\ 010000 & 011100 & 000011 & 001111 & 110101 & 111001 & 100110 & 101010 \\ 100000 & 101100 & 110011 & 111111 & {000101} & 001001 & 010110 & 011010 \\ 000110 & 001010 & {010101} & 011001 & 100011 & 101111 & 110000 & 111100 \\ 010100 & 011000 & 000111 & 001011 & 110001 & 111101 & 100010 & 101110\end{array} $$译码示范
对“100000”译码：定位它的位置：
$$ \begin{array}{llllllll}\color{blue}000000 & 001100 & 010011 & 011111 & 100101 & 101001 & 110110 & 111010 \\ 000001 & 001101 & 010010 & 011110 & 100100 & 101000 & 110111 & 111011 \\ 000010 & 001110 & 010001 & 011101 & 100111 & 101011 & 110100 & 111000 \\ 000100 & 001000 & 010111 & 011011 & 100001 & 101101 & 110010 & 111110 \\ 010000 & 011100 & 000011 & 001111 & 110101 & 111001 & 100110 & 101010 \\ \color{red}{100000} & 101100 & 110011 & 111111 & {000101} & 001001 & 010110 & 011010 \\ 000110 & 001010 & {010101} & 011001 & 100011 & 101111 & 110000 & 111100 \\ 010100 & 011000 & 000111 & 001011 & 110001 & 111101 & 100010 & 101110\end{array} $$其顶端的数字是 $000000$，$d(000000) = 000$，译码结果是 $000$。
对“101010”译码：
$$ \begin{array}{llllllll}000000 & 001100 & 010011 & 011111 & 100101 & 101001 & 110110 & \color{blue}111010 \\ 000001 & 001101 & 010010 & 011110 & 100100 & 101000 & 110111 & 111011 \\ 000010 & 001110 & 010001 & 011101 & 100111 & 101011 & 110100 & 111000 \\ 000100 & 001000 & 010111 & 011011 & 100001 & 101101 & 110010 & 111110 \\ 010000 & 011100 & 000011 & 001111 & 110101 & 111001 & 100110 & \color{red}101010 \\ 100000 & 101100 & 110011 & 111111 & {000101} & 001001 & 010110 & 011010 \\ 000110 & 001010 & {010101} & 011001 & 100011 & 101111 & 110000 & 111100 \\ 010100 & 011000 & 000111 & 001011 & 110001 & 111101 & 100010 & 101110\end{array} $$顶端的码字是 $110010$，$d(111010) = 111$，译码结果是 $111$。