最大似然译码详解(最大似然解码,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$。