信息论及编码第二十讲

《信息论及编码第二十讲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章：线性分组码§7.1分组码的概念§7.2线性分组码§7.4循环码§7.5卷积码2021/8/131§7.2线性分组码实用纠错译码算法的预备知识：差错向量和伴随式定义6.1.8设：信道的输入为码字u；信道的输出为向量y。称向量e=y-u为差错向量，或差错图样。（请注意，此时y=u+e；向量的加减法是对应分量的(modD)加减法）定义6.1.9(p195)设信道的输出为y。记s=yHT其中H是一致校验矩阵。称N-L维行向量s为y的伴随式。有以下的结论。2021/8/132§7.2线性分组码（1）当两个差错向量相同时，它们的伴随式相同。这

2、就是说，伴随式s的值仅仅与信道传输错误有关，与输入信道的码字无关。证明s=yHT=(u+e)HT=uHT+eHT=eHT。证完。（2）两个差错向量的伴随式相同，当且仅当它们的差向量是码字。证明设有两个差错向量e(1)和e(2)。e(1)HT=e(2)HT，当且仅当(e(1)-e(2))HT=全0的N-L维行向量，当且仅当(e(1)-e(2))是码字。证完。2021/8/133§7.2线性分组码（3）给定一个差错向量e。则与e具有相同伴随式的所有差错向量恰好是e加上所有码字。换句话说。设s是一个伴随式。以s为伴随式的全体差错向量，就是以s为

3、伴随式的一个差错向量加上全体码字。（4）伴随式s是N-L维行向量，因此有DN-L个不同的伴随式。差错向量e是N维行向量，因此有DN个不同的差错向量。具有相同伴随式的差错向量的个数为DL。DLDN-L=DN。定义在以s为伴随式的全体差错向量中，Hamming重量最小的差错向量称为s的陪集首，记为e(s)。（s可能有不止一个Hamming重量最小的差错向量，任意选择一个作为陪集首e(s)即可）2021/8/134§7.2线性分组码（5）对信道的输出向量y，计算伴随式s=yHT，以s为地址查找陪集首e(s)，计算u=y-e(s)。则u就是在所有

4、码字中与y的Hamming距离最小的码字。证明首先，u=y-e(s)是码字。这是因为uHT=yHT-e(s)HT=s-s=全0的N-L维行向量。其次，对任意另一个码字c，(y-c)HT=yHT-cHT=yHT=s。这就是说，(y-c)是以s为伴随式的一个差错向量。另一方面，(y-u)=e(s)是以s为伴随式的Hamming重量最小的差错向量。所以w(y-u)≤w(y-c)，即d(y,u)≤w(y,c)。证完。2021/8/135§7.2线性分组码实用纠错译码算法预计算对每个伴随式（即N-L维行向量）s，寻找s的陪集首e(s)，并以s为地址

5、存储e(s)。（预计算的总体计算量很大，但有许多技巧可以大幅度地减少计算量）现场纠错译码（1）对信道的输出向量y，计算伴随式s=yHT。（2）以s为地址查找陪集首e(s)。（3）将输出向量y译为码字u=y-e(s)。结束。u就是在所有码字中与y的Hamming距离最小的码字。2021/8/136§7.2线性分组码现场纠错译码的计算量计算量最大的是第（2）步。因为s是N-L维行向量，所以查找s的计算量是logDN-L=(N-L)logD（而不是DN-L）。总之，计算量远远小于直接使用最小距离准则的计算量DL。2021/8/137§7.2线性

6、分组码线性分组码的检错能力和纠错能力定义6.1.3线性分组码的最小Hamming距离定义为两个不同码字的Hamming距离的最小值，记为dmin。线性分组码的最小Hamming重量定义为非全0码字的Hamming重量的最小值，记为wmin。2021/8/138§7.2线性分组码引理1dmin=wmin。证明设两个不同的码字u(1)和u(2)，使得dmin=d(u(1),u(2))=w(u(1)-u(2))。注意到(u(1)-u(2))是一个非全0码字，所以dmin≥wmin。设一个非全0码字u，使得wmin=w(u)=w(u-全0码字)=

7、d(u,全0码字)。所以dmin≤wmin。证完。2021/8/139§7.2线性分组码引理2设信道的输入为码字u，信道的输出为向量y，差错向量为e=y-u。则（1）当w(e)

8、]（下方取整），则y与任意另一个码字c的Hamming距离d(c,y)≥d(c,u)-d(y,u)（三角不等式）≥dmin-d(y,u)=dmin-w(e)≥dmin-[(dmin-1)/2]