信息论与编码理论基础(第六章)

1、2021-8-11 第六章：第六章：线性分组码 6.1 分组码的概念分组码的概念(与主教材标题不同与主教材标题不同) 6.2 线性分组码线性分组码 6.3 线性分组码的校验矩阵线性分组码的校验矩阵(与主教材标与主教材标 题不同题不同) 6.5 译码方法和纠错能力译码方法和纠错能力(与主教材标题与主教材标题 不同不同) 6.4 、6.6、6.7、6.8 一些特殊一些特殊 的线性分组码的线性分组码 2021-8-12 6.1 分组码的概念分组码的概念 设信道是一个D元字母输入/ D元字母输出的DMC信道，字母 表为0, 1, , D-1。其信道转移概率矩阵为DD矩阵 传输错误的概率为 p。信道容量

2、为 C=logD-H(p)-plog(D-1)。 p D p D p D p p D p D p D p p 1 11 1 1 1 11 1 2021-8-13 6.1 分组码的概念分组码的概念 对随机变量序列X1X2进行的信道编码为(N, L)码： (X1X2XL)(U1U2UN)=C(X1X2XL)。 这个(N, L)码又称为(N, L)分组码。 已经有结论：当设备所确定的编码速率RC/H(X)时， 存在 (N, L)分组码，使得 l实际编码速率 (信息率L/N)任意接近R， l译码错误的概率任意接近0。 问题是：怎样构造这样的分组码？这样的分组码的编码、译 码计算量会不会太大？（这才是研

3、究分组码的含义） 2021-8-14 6.1 分组码的概念分组码的概念 预备知识预备知识1：有限域：有限域 设D是一个素数。于是字母表0, 1, , D-1中的所有字母关 于(modD)加法、(modD)乘法构成了一个封闭的代数结构， 称作有限域有限域，又称作Galois域域，记作GF(D)： GF(D)=(0, 1, , D-1, (modD)加法, (modD)乘法)。 即 （1）(0, 1, , D-1, (modD)加法) 构成交换群（Abel群）。 （2）(1, , D-1, (modD)乘法) 构成交换群（Abel群）。 （3）分配律成立：a(b+c) (modD) =ab+ac(

4、modD)。 2021-8-15 6.1 分组码的概念分组码的概念 注1：如果D不是素数， (0, 1, , D-1, (modD)加法, (modD)乘 法)不是有限域，只是有限环。 注2：有限域GF(D)上的线性代数完全类似于实数域上的线性代 数，线性代数的所有内容都在“加法”和“乘法”基础上得 到。 元素的元素的“加法加法”负元；非负元；非0元的元的“乘法乘法”逆元；逆元； 一组向量是否一组向量是否“线性无关线性无关”的概念以及所有等价的判别方法；的概念以及所有等价的判别方法； 矩阵的矩阵的“秩秩”的概念以及所有计算方法；的概念以及所有计算方法； 方阵是否方阵是否“可逆可逆”的所有判别方

5、法；的所有判别方法； 求方阵的求方阵的“逆阵逆阵”的所有算法；的所有算法； 关于对称矩阵的所有结论；等等。关于对称矩阵的所有结论；等等。 注3：有限域GF(D)与实数域的区别是：传统的“逼近逼近”、“极极 限限”的概念消失了消失了。 2021-8-16 例例：取D=2，则GF(2)=(0, 1, (mod2)加法, (mod2)乘法)。 运算规则为： 0+0=1+1=0，0+1=1， 00=01=0，11=1。 方阵 是否可逆？回答是肯定的。两种不同的判 别方法都能够证明它是可逆的 ： （1）它经过可逆行变换能够变成单位阵； （2）它的行列式不等于0。（等于1！） 010 011 101 01

6、000010 010 011 101 2021-8-17 6.1 分组码的概念分组码的概念 该方阵的逆矩阵是什么？ 怎样计算？做联合可逆行变换： 111100 011110 001101 100010 011110 001101 100010 010011 001101 111100 100010 110001 111100 100010 001101 111 100 110 010 011 101 1 2021-8-18 6.1 分组码的概念分组码的概念 例例：取D=3，则GF(3)=(0, 1, 2, (mod3)加法, (mod3)乘法)。 运算规则为：0+0=1+2=0，0+1=2+2

7、=1，0+2=1+1=2， 00=01=02=0，11=22=1，12=2。 矩阵 是不是满行秩的？ 换句话说，此矩阵的三个行向量是不是在域GF(3)上线性无关 的？再换句话说，能否保证此矩阵的各行的任何非0线性组 合都不是全0的4维向量？再换句话说，此矩阵能否通过一 些可逆行变换变成一个“阶梯阵”？ 0110 0112 1011 2021-8-19 6.1 分组码的概念分组码的概念 可逆行变换 1200 1120 1011 0110 1120 1011 0110 0112 1011 是满行秩的。 0110 0112 1011 2021-8-110 6.1 分组码的概念分组码的概念 例：例：域

8、GF(D)上的一个L行N列的矩阵（LN阶的矩阵）G， 设它是满行秩的（当然此时有LN）。则变换 (u1, u2, , uN)=(x1, x2, , xL)G 一定是单射(即(x1, x2, , xL)的不同值一定变换为(u1, u2, , uN) 的不同值)。 证明 设u(1)=x(1)G， u(2)=x(2)G ，且x(1)x(2)。要证明u(1)u(2)。根 据线性性质， u(1)-u(2)=(x(1)-x(2)G， 因为(x(1)-x(2)全0的L维向量，所以(x(1)-x(2)G是G的各行的非0 线性组合。G满行秩，所以(x(1)-x(2)G全0的N维向量。所 以u(1)u(2)。 2

9、021-8-111 6.1 分组码的概念分组码的概念 预备知识预备知识2：有限域上的分组码：有限域上的分组码 当D是素数时，分组码可以充分利用有限域GF(D)的 代数运算，使得编码和译码更加简便。 2021-8-112 6.2 线性分组码线性分组码 定义定义 取GF(D)上的一个L行N列的矩阵G，它是满行秩的。 (N, L)分组码定义为 (u1, u2, , uN)=(x1, x2, , xL)G 其中(x1, x2, , xL)是信息向量信息向量，(u1, u2, , uN)是对应的码字码字。 （1）称此码为D元(N, L)线性分组码线性分组码。 （2）称矩阵G为此码的生成矩阵生成矩阵。 2

10、021-8-113 6.2 线性分组码线性分组码 线性分组码的代数结构线性分组码的代数结构 命题命题1 不同的信息向量对应不同的码字。 （因为矩阵G是满行秩的，所以变换u=xG是单射） 命题命题2 生成矩阵G的第1行是信息向量(1, 0, 0, , 0)的码字； 生成矩阵G的第2行是信息向量(0, 1, 0, , 0)的码字； 生成矩阵G的第L行是信息向量(0, , 0, 0, 1)的码字。 2021-8-114 6.2 线性分组码线性分组码 命题命题3 信息向量(x1, x2, , xL)的码字是： x1数乘G的第1行，加x2数乘G的第2行，加，加xL数乘G的第L 行。 换句话说， 任何一个

11、码字都是生成矩阵G的线性组合。 命题命题4 当u(1)和u(2)都是码字， u(1)+u(2)也是码字。（线性分组码 的码字关于线性运算封闭） 证明 设 u(1)是信息向量x(1)的码字：u(1)=x(1)G； u(2)是信息向量x(2)的码字：u(2)=x(2)G。 则u(1)+u(2)=x(1)G+x(2)G=(x(1)+x(2)G，即u(1)+u(2)是信息向量(x(1)+x(2) 的码字。 证完。 2021-8-115 6.2 线性分组码线性分组码 （命题（命题3和命题和命题4告诉我们，一个告诉我们，一个N维向量是一个码字，当且仅当它是生成维向量是一个码字，当且仅当它是生成 矩阵矩阵G

12、的第的第1行行第第L行的线性组合。还告诉我们，线性分组码的码字集行的线性组合。还告诉我们，线性分组码的码字集 合构成一个线性空间。这个线性空间是几维的？合构成一个线性空间。这个线性空间是几维的？L维的，因为生成矩阵维的，因为生成矩阵 G的第的第1行行第第L行恰好是该线性空间的一组基）行恰好是该线性空间的一组基） 命题命题5 设一个D元(N, L)线性分组码的生成矩阵为G。设另一 个D元(N, L)线性分组码的生成矩阵为G=MG，其中M是L阶 可逆方阵。则两个码的码字集合完全重合，只是信息向量 与码字的对应关系不同。 换句话说，如果把线性分组码的生成矩阵G做可逆行变换变成 另一个生成矩阵，则不改

13、变码字集合，只改变信息向量与 码字的对应关系。 2021-8-116 6.2 线性分组码线性分组码 证明 （要证明，第一个码中任一个码字也是第二个码中的码 字；第二个码中任一个码字也是第一个码中的码字） 设在第一个码中，u是信息向量x的码字： u=xG； 则在第二个码中，u是信息向量xM -1的码字： u=xM -1MG= xM -1G。 设在第二个码中，u是信息向量x的码字： u=xG； 则在第一个码中，u是信息向量xM的码字： u=xMM -1G= xM G。 证完。 2021-8-117 6.2 线性分组码线性分组码 线性分组码的特例：系统码线性分组码的特例：系统码 定义定义(p178)

14、 D元(N, L)线性分组码的生成矩阵为 G=PL(N-L), IL， 其中IL是是L阶单位阵阶单位阵， PL(N-L)是L(N-L)阶矩阵。 则称此码为系统码系统码。此时信息向量(x1, x2, , xL)的码字是 (u1, u2, , uN)=(x1, x2, , xL)G =(x1, x2, , xL) PL(N-L), x1, x2, , xL)。 码字的后L位恰好是信息向量(x1, x2, , xL)，称为码字的信码字的信 息位息位。称码字的前N-L位为码字的一致校验位一致校验位。 2021-8-118 6.2 线性分组码线性分组码 例例 此二元(7, 4)码是线性分组码，生成矩阵G

15、是由信息向量 (1000)、(0100)、(0010)、(0001)的码字组成的4行 1000101 0100111 0010110 0001011 G 该码是系统码。 2021-8-119 6.2 线性分组码线性分组码 例例 此二元(5, 3)线性分组码的生成矩阵是 11111 01100 00111 G 的生成矩阵。 码变换后，变成一个系统将生成矩阵经过可逆行该码不是系统码。但是 10011 01011 00111 10011 01100 00111 11111 01100 00111 合相同。与一个系统码的码字集因此，该码的码字集合 2021-8-120 6.3 线性分组码的校验矩阵线性

16、分组码的校验矩阵 线性分组码的校验矩阵线性分组码的校验矩阵 定理定理(p179) 对于D元(N, L)线性分组码的生成矩阵G（ G 是LN 阶矩阵），必存在一个(N-L)N阶矩阵H， （1）H是满行秩的； （2）GHT= OL(N-L)。 （HT是H的转置矩阵， OL(N-L)是全0的L(N-L) 阶矩阵。不证 明。这方面的知识属于有限域上的线性代数） 定义定义(p179) 由上述定理所描述的矩阵矩阵H称为D元(N, L)线性分组 码的校验矩阵校验矩阵。 2021-8-121 6.3 线性分组码的校验矩阵线性分组码的校验矩阵 有以下的结论。 （1）一个线性分组码有很多校验矩阵很多校验矩阵。一个

17、校验矩阵H经过 可逆行变换变为H ， H 是同一个线性分组码的另一个校验矩阵。 （2）固定一个校验矩阵H。则一个N维向量u是一个码字，当且仅当： uHT=全0的N-L维行向量。 （3）设一个D元(N, L)线性分组码的生成矩阵G，校验矩阵H。则H 是一个D元(N, N-L)线性分组码的生成矩阵，G是此码的一个校验 矩阵。称这两个码互为对偶码对偶码。 D元元(N, L)线性分组码线性分组码D元元(N, N-L)线性分组码线性分组码 生成矩阵生成矩阵G校验矩阵校验矩阵H生成矩阵生成矩阵H校验矩阵校验矩阵G 2021-8-122 6.3 线性分组码的校验矩阵线性分组码的校验矩阵 （怎样由生成矩阵G计

18、算出校验矩阵H？） （4）设D元(N, L)线性分组码是系统码，生成矩阵为G=P, IL， 其中IL是L阶单位阵，P是L(N-L)阶矩阵。则校验矩阵校验矩阵可以 取为H=IN-L, -PT，其中IN-L是N-L阶单位阵，PT是P 的转置矩 阵。 证明 GHT=P, IL IN-L, -PTT=P-P=OL(N-L)。证完。 （5）设D元(N, L)线性分组码的生成矩阵经过可逆行变换后变 为P, IL，则校验矩阵也可以取为H=IN-L, -PT。 2021-8-123 6.3 线性分组码的校验矩阵线性分组码的校验矩阵 。则可取 ，元编码， 。，则可取元编码， 。，则可取元编码， 01010 10

19、101 10001 01010 00101 10001 01111 00101 11110 01111 00101 2 22010 02201 10010 01011 00101 3 11010 01101 10010 01011 00101 2 H G HG HG 2021-8-124 6.5 译码方法和纠错能力译码方法和纠错能力 线性分组码的纠错译码准则线性分组码的纠错译码准则 定义定义 (已知) 一个N维向量u的Hamming重量重量定义为它的对应位置值不等于0 的位数。记为w(u)。 两个N维向量u(1)和u(2)的Hamming距离距离定义为它们的对应位置值 不相同的位数。记为d(u

20、(1), u(2)。 显然有以下的结论 d(u(1), u(2)=w(u(1)-u(2)。 三角不等式： d(u(1), u(3)d(u(1), u(2)+ d(u(2), u(3)。 或 w(u(1)-u(3) w(u(1)-u(2)+ w(u(2)-u(3)。 2021-8-125 6.5 译码方法和纠错能力译码方法和纠错能力 设GF(D)上的D元(N, L)线性分组码，生成矩阵为G。 将信息向量将信息向量x编码，得到码字编码，得到码字u=xG。将码字。将码字u输入信道。信道输入信道。信道 的输出值为的输出值为y。 使用最小距离准则：使用最小距离准则：给定输出值y，寻找码字c使d(y, c

21、)最小。 将输出值y译为码字c。当c=u时，就实现了正确译码。 直接使用最小距离准则的困难：直接使用最小距离准则的困难：需要将DL个码字与输出值y的 Hamming距离进行对比，才能找到码字c使d(y, c)最小。计 算量大。 (穷举搜索穷举搜索) 2021-8-126 编码编码- 译码过程图示。其中译码过程图示。其中 x(1)、x(2)、x(3)、x(4)是各个信息向量；是各个信息向量； c(1)、c(2)、c(3)、c(4)是各个对应码字。是各个对应码字。 2021-8-127 6.5 译码方法和纠错能力译码方法和纠错能力 实用纠错译码算法的预备知识：差错向量和伴随式实用纠错译码算法的预备

22、知识：差错向量和伴随式 定义定义6.1.8 设信道的输入为码字u；信道的输出值为向量y。称向 量 e=y- u 为差错向量差错向量，或差错图样差错图样。 （请注意：此时y=u+e；u=y-e；向量的加减法是对应分量的 (modD) 加减法。在信道的输出端，只能得到输出向量y，并 不能得到差错向量e，因此不能得到输入码字u。） 定义定义6.1.9(p195) 设H是校验矩阵。对于N维行向量t，记 s=tHT 并称N-L维行向量s为N维行向量t的伴随式伴随式。 2021-8-128 6.5 译码方法和纠错能力译码方法和纠错能力 有以下的结论。 （1）N维行向量t是一个码字，当且仅当t的伴随式是一个

23、全0的 N-L维行向量。（这是已知的结论） （2）设信道的输入码字u，输出向量y，差错向量e=y- u，则e的 伴随式等于y的伴随式。 证明 eHT=(y-u)HT=yHT-uHT=yHT。证完。 结论（结论（2）的注解：）的注解：在信道的输出端，虽然不能得到差错向量， 却能计算出差错向量的伴随式：它恰好等于输出向量的伴随式。 换句话说，设输出向量为y，并计算出y的伴随式s=yHT。则此 时虽然不能确切地得到差错向量，但任何一个“可能的差错向可能的差错向 量量”e都满足方程 eHT=s 2021-8-129 6.5 译码方法和纠错能力译码方法和纠错能力 （3）设 n输出向量为y，并计算出了y的

24、伴随式s=yHT。 nt是任意一个满足方程s=tHT的N维行向量。 则： y- t是一个码字 。 证明 (y-t)HT=yHT-tHT=s-s=全0的N-L维行向量， 因此y- t是一个码字。证完。 结论（结论（3）的注解：）的注解：当输入码字为该y- t，差错向量为该t时，输出 向量必然为该y。换句话说，此时的t就是一个“可能的差错向可能的差错向 量量”。 结论（结论（2）和结论（）和结论（3）的综合结论：）的综合结论：设输出向量y，并计算出了y 的伴随式s=yHT。则此时所有“可能的差错向量可能的差错向量” ， 恰好就是 方程s=tHT的所有解t。 2021-8-130 6.5 译码方法和

25、纠错能力译码方法和纠错能力 （4）设输出向量为y，并计算出了y的伴随式s=yHT。则此时所有 “可能的差错向量可能的差错向量” ，恰好就是任何一个“可能的差错向量可能的差错向量” 加上全体码字。 换句话说，此时所有“可能的差错向量可能的差错向量”， 恰好就是方程s=tHT的任何一个固定解t加上全体码字。 （证明思想：非齐次通解=非齐次特解+齐次通解） （5）每个伴随式所对应的“可能的差错向量可能的差错向量”共有DL个。伴随 式是N-L维行向量，因此有DN-L个不同的伴随式。不同的伴随 式所对应的“可能的差错向量可能的差错向量”不会重合。DLDN-L=DN。 定义定义 在以s为伴随式的全体“可能

26、的差错向量可能的差错向量”中，取一个 Hamming重量最小的向量称为s的陪集首的陪集首，记为e(s)。 （在以s为伴随式的全体“可能的差错向量可能的差错向量”中，Hamming重量 最小的向量或许有不止一个。任意选择一个作为陪集首e(s)即 可） 2021-8-131 6.5 译码方法和纠错能力译码方法和纠错能力 （6）对信道的输出向量y，计算伴随式计算伴随式s=yHT，以，以s为地址查找为地址查找 陪集首陪集首e(s)，计算，计算u=y- e(s)。则u就是在所有码字中与y的 Hamming距离最小的码字。 证明 首先，注意到e(s)是一个“可能的差错向量可能的差错向量”。 因此 uHT=

27、yHT- e(s)HT=s-s=全0的N-L维行向量， 说明 u=y- e(s)是一个码字。 其次，对任意另一个码字c， (y- c)HT=yHT- cHT=yHT=s。 这就是说，(y- c)是另外一个“可能的差错向量可能的差错向量”。 另一方面，(y- u)=e(s)是以s为伴随式的所有“可能的差错向量可能的差错向量” 中Hamming重量最小的。 所以w(y- u)w(y- c)，即d(y, u)w(y, c)。证完。 2021-8-132 6.5 译码方法和纠错能力译码方法和纠错能力 实用纠错译码算法实用纠错译码算法 预计算预计算 对每个伴随式（即N-L维行向量）s，寻找s的陪集首e(

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

29、离准则的计算 量DL。 2021-8-134 6.5 译码方法和纠错能力译码方法和纠错能力 线性分组码的检错能力和纠错能力线性分组码的检错能力和纠错能力 首先我们发现，能否正确译码并不依赖于输入的是什么码字， 仅仅依赖于真正的差错向量是什么。显然 P(正确译码)= P(真正的差错向量是某个陪集首)。 其次我们可以定义更加简单的检错能力和纠错能力。 定义定义6.1.3 线性分组码的最小最小Hamming距离距离定义为两个不同码 字的Hamming距离的最小值，记为dmin。 线性分组码的最小最小Hamming重量重量定义为非全0码字的Hamming 重量的最小值，记为wmin。 2021-8-1

30、35 6.5 译码方法和纠错能力译码方法和纠错能力 引理引理1 dmin=wmin。 证明 设两个不同的码字u(1)和u(2)，使得 dmin=d(u(1) , u(2)=w(u(1)-u(2)。 注意到(u(1)-u(2)是一个非全0码字，所以dminwmin。 设一个非全0码字u，使得 wmin=w(u)=w(u-全0码字)=d(u, 全0码字)。 所以dminwmin。 证完。 2021-8-136 6.5 译码方法和纠错能力译码方法和纠错能力 引理引理2 设信道的输入为码字u，信道的输出为向量y，差错 向量（注：真正的差错向量）为e=y-u。则 （1）当w(e)dmin，yHT肯定不是

31、全0的N-L维向量，因而发 现信道传输错误。 （2）当w(e)(dmin-1)/2（下方取整），由上述实用纠错译 码算法肯定将y译为真正的输入码字u，而不会将y译为其 它码字。 2021-8-137 6.5 译码方法和纠错能力译码方法和纠错能力 证明 （1）当w(e)(dmin-1)/2 w(e)=d(y,u) 因此，所有码字中，u与y的Hamming距离最小。证完。 2021-8-138 6.5 译码方法和纠错能力译码方法和纠错能力 引理引理3 设差错向量（注：真正的差错向量）为e。当w(e)(dmin- 1)/2（下方取整），由上述实用纠错译码算法未必将输出向 量译为真正的输入码字。 举例

32、 取两个码字u，c，恰好满足d(c, u)= dmin。 （请注意，这样的两个码字u，c存在！） 取向量y满足： d(y,u)=(dmin-1)/2+1(dmin-1)/2； d(c, u)= d(c, y)+d(y,u)。（三角不等式变为等式） （请注意，这样的向量y存在！） 此时 d(c, y)= d(c, u)-d(y,u)=dmin-(dmin-1)/2+1=dmin-1-(dmin-1)/2。 2021-8-139 d(y,u)=(dmin-1)/2+1； d(c, y)=dmin-1-(dmin-1)/2。 当dmin是奇数时， d(y,u)=(dmin-1)/2+1， d(c,

33、y)= (dmin-1)/2， 故d(c, y)(dmin-1)/2 ，则未必e(s)=e，因而未 必c=u。 换句话说，如果w(e)(dmin-1)/2 ，则e一定是s=eHT的陪集首； 如果w(e)(dmin-1)/2 ，则e未必是s=eHT的陪集首。 2021-8-141 6.5 译码方法和纠错能力译码方法和纠错能力 定理定理6.5.4 记真正的差错向量为e。记t是一个非负整数。如果 （1）当w(e)t时总是能够正确译码， （2）当w(e)t时并不总是能够正确译码， 则t =(dmin-1)/2 。 推论推论 记真正的差错向量为e。事件“总是能够正确译码”定 义为“w(e)(dmin-1

34、)/2 ”。则“总是能够正确译码总是能够正确译码”的概 率为 2/ ) 1( 0 min min )1 ()2/ ) 1()( d t tNtt N ppCdewP 2021-8-142 6.5 译码方法和纠错能力译码方法和纠错能力 定理6.5.4说明，dmin是线性分组码纠错能力的一个指标。dmin越 大，(dmin-1)/2就越大，“总是能够正确译码”的概率也越 大。 当N比L大得越多，码字在所有N维向量中占的比例越小，越容 易使得dmin大。问题是，当N和L都确定时，如何设计码使得 dmin大。 纠正一种误解：dmin越大， “总是能够正确译码”的概率越大。 决不能说：dmin越大，正确

35、译码的概率越大。 （? P185, 式子6.5.8） 2021-8-143 6.5 译码方法和纠错能力译码方法和纠错能力 例例 二元（6，3）线性分组码，生成矩阵G已经给出。求一致校 验矩阵H；码字集合；译码预计算（简化计算量）。 显然是系统码。 100011 010101 001110 G 011100 101010 110001 H 2021-8-144 6.5 译码方法和纠错能力译码方法和纠错能力 信息向量码字 000 000000 100 011100 010 101010 001 110001 110 110110 101 101101 011 011011 111 000111 2

36、021-8-145 6.5 译码方法和纠错能力译码方法和纠错能力 伴随式s对应的所有“可能的差错向量”e 000 000000，011100，101010，110001，110110，101101，011011，000111 100 100000，111100，001010，010001，010110，001101，111011，100111 010 010000，001100，111010，100001，100110，111101，001011，010111 001 001000，010100，100010，111001，111110，100101，010011，001111 110 000

37、100，011000，101110，110101，110010，101001，011111，000011 101 000010，011110，101000，110011，110100，101111，011001，000101 011 000001，011101，101011，110000，110111，101100，011010，000110 111 100100，111000，001110，010101，010010，001001，111111，100011 伴随式s陪集首e(s) 000 000000 100 100000 010 010000 001 001000 110 000100

38、101 000010 011 000001 111 100100 2021-8-146 6.5 译码方法和纠错能力译码方法和纠错能力 dmin=3；(dmin-1)/2=1。 当真正的差错向量的Hamming重量不超过1时，总是能够正确译 码； 当真正的差错向量的Hamming重量超过1时，未必总是能够正确 译码。 总是能够正确译码的概率为 (1-p)6+6(1-p)5p。 正确译码的概率为 (1-p)6+6(1-p)5p+(1-p)4p2。（p185, 式6.5.8） 若p=10-2，则(1-p)6=0.9415； (1-p)6+6(1-p)5p=0.9986； (1-p)6+6(1-p)5

39、p+(1-p)4p2=0.9987。 2021-8-147 6.5 译码方法和纠错能力译码方法和纠错能力 设信道的输出向量为y=(111111)。 计算伴随式s=yHT=(111)。 以s为地址查找e(s)=(100100)。 计算c=y- e(s)=(111111)-(100100)=(011011)。 信息向量为(011)。 2021-8-148 6.4 、6.6、6.7、 6.8 一些特殊的一些特殊的线性分组码线性分组码 二元二元Hamming码码 N=2m-1，L=2m-1-m，即二元(2m-1，2m-1-m)线性分组码。 n其校验矩阵是如下的m(2m-1)阶矩阵H： H的的(2m-1

40、)列恰好是列恰好是(2m-1)个非全个非全0的的m维向量维向量。 n因此：校验矩阵H的任意一列不是全0的m维向量；校验矩 阵H的任意两列互不相同；校验矩阵H的某三列的和为全0 的m维向量。换句话说，重量为1、重量为2的2m-1维向量 都不是码字，而某些重量为3的2m-1维向量是码字。再换 句话说， Hamming码的dmin=3。再换句话说， 当差错向量 的重量不超过1时，肯定能够正确译码。 n编码效率为R=(2m-1-m)/(2m-1) 。（编码效率大） 2021-8-149 6.4 、6.6、6.7、 6.8 一些特殊的一些特殊的线性分组码线性分组码 定义定义 如果存在一个t，使得任一个接

41、收向量y，都有唯一的码 字u满足d(y, u)t，则称该码为t阶完备码。 命题命题 当一个(N，L)线性分组码是t阶完备码时，所有不同伴随 式所对应的陪集首恰好是所有重量不超过t的N维向量。 注意：不同伴随式的个数为2N-L，重量不超过t的N维向量的个 数为 定理定理 二元Hamming码（它是二元(2m-1，2m-1-m)线性分组码） 是1阶完备码。（2m=1+2m-1 ） t k k N C 0 t k k N LN C 0 2此时应该 2021-8-150 6.4 、6.6、6.7、 6.8 一些特殊的一些特殊的线性分组码线性分组码 Hadamard码码 从Hadmard矩阵的行中选择码

42、字可以构造出Hadamad码。 Hadmard矩阵Mn是一个nn阶矩阵，其中n=2m。该矩阵满足 n有一行为全0行，其余的行有2m-1个0，2m-1个1。 n任意两行有2m-1个位置不同， 2m-1个位置相同。 n如何构造Hadmard矩阵？看如下的递归方法。 10 00 2 M 0110 1100 1010 0000 4 M nn nn n MM MM M 2 2021-8-151 6.4 、6.6、6.7、 6.8 一些特殊的一些特殊的线性分组码线性分组码 以Hadmard矩阵Mn的所有行作为所有的码字，得到的码就是 Hadamad码。 Hadamad码的参数如下： 共有n个码字，因此共有

43、n个信息，因此信息长为logn=m。 码长为n。 编码效率为R=m/n=m/2m。（编码效率小） 任何两个码字的Hamming距离都等于2m-1=n/2。因此 dmin=2m-1=n/2。 Mn的任意m个非全0行都是线性无关的，因此生成矩阵可能是Mn 的任意m个非全0行构成的mn阶矩阵。（？） 2021-8-152 6.4 、6.6、6.7、 6.8 一些特殊的一些特殊的线性分组码线性分组码 Golay码码 Golay码是线性(23, 12)码，最小距离为7。将其增加一个全校 验位扩展为二元线性（24,12）码，最小距离为8，称为扩 展Golay码。表6.4.1给出了Golay码和扩展Gola

44、y码的重量分 布。 循环码循环码 定义定义6.6.1(p188) 一个二元(N, L)线性分组码C，若对任意c=(c0, c1, c2, , cN-1)C，恒有c =(cN-1, c0, c1, , cN-2)C，则称 C为二元循环码。 2021-8-153 6.4 、6.6、6.7、 6.8 一些特殊的一些特殊的线性分组码线性分组码 二元循环码的产生过程二元循环码的产生过程 取二元域GF(2)=(0, 1, (mod2)加法, (mod2)乘法)。 取GF(2)上的N次多项式1+xN。取多项式1+xN的（在GF(2)上的） 一个N-L次因式g(x)：g(x)=g0+g1 x1+g2 x2+g

45、N-L xN-L。 取以下的LN矩阵G作为二元(N, L)线性分组码C的生成矩阵， 则该码一定就是一个二元循环码。（主教材中有证明） LN LNLN LN gg gggg gggg G 0 110 210 00 00 00 2021-8-154 6.4 、6.6、6.7、 6.8 一些特殊的一些特殊的线性分组码线性分组码 例例6.6.1(p190)例例6.6.2(p192) 取N=7。则（在GF(2)上）： 1+x7=(1+x)(1+x+x3)(1+x2+x3)。 若取g(x)=1+x+x3 ，则产生的二元(7, 4)线性分组码C一定就是一 个二元循环码，生成矩阵为 1011 1011 101

46、1 1011 G 2021-8-155 6.4 、6.6、6.7、 6.8 一些特殊的一些特殊的线性分组码线性分组码 如此产生的二元循环码的译码如此产生的二元循环码的译码 设接收向量为y=(y0, y1 , y2, , yN-1)。记 y(x)=y0+y1 x1+y2 x2+yN-1xN-1 。 用g(x)除y(x)，得余式s(x)=s0+s1 x1+s2 x2+sN-L-1xN-L-1 。 则此时： 除式y(x)=q(x)g(x)+s(x)也可以表示成y(x)s(x)(modg(x)。 余式s(x)的次数一定不超过N-L-1。 N-L维向量s=(s0, s1, s2, , sN-L-1)就是

47、接收向量y的伴随式。（因而 不需要校验矩阵） 2021-8-156 习题课习题课 6.1 设有4个消息al，a2，a3 和a4被编成为长为5的二元码的 00000，01101，10111， l1010。 (a)试给出码的一致校验关系。 (b)若通过转移概率为p1/2的BSC传送，试给出最佳译码表及 相应的译码错误概率表示式。 (c)若码通过BEC信道传送，试问可恢复几个删除?其最佳译码 表应如何配置？ (d)一般，最小距离为dmin的线性码，可恢复几个删除? 2021-8-157 习题课习题课 (a)首先需要验证该码是线性码：01101+10111=l1010。 其次需要给出该码的生成矩阵和校

48、验矩阵： 最后该码的一致校验关系为：对任意码字(x0 x1 x2 x3 x4)，恒有 x0+x1+x2=0，x0+x3=0，x0+x1+x4=0。 (?) 10110 11101 G 10011 01001 00111 H 2021-8-158 习题课习题课 (b) 通过转移概率为p1/2的BSC传送。如果直接按照“最小距离 准则”来求最佳译码表，则最佳译码表为 接收向量译为 00000，00001，00010，00100，01000，10000，10100，10001。00000 01101，01100，01111，01001，00101，11101，11001，11100。01101 10

49、111，10110，10101，10011，11111，00111，00011，00110。10111 11010，11011，11000，11110，10010，01010，01110，01011。 l1010 2021-8-159 习题课习题课 求“译码错误概率表示式”，可以有多种含义。本题应该理解 为以下的含义，而不应该理解为别的含义： 5 2 5 5 min )1 ( ) 1( ) 2 ( k kkk ppC P d P 错误向量的重量 错误向量的重量大于 2021-8-160 求最佳译码表，当然也可以采用标准方法，先求可能的 差错向量、伴随式、陪集首的关系： 可能的差错向量伴随式陪集

50、首 00000，01101，10111， 11010。00000000 00001，01100，10110， 11011。00100001 00010，01111，10101， 11000。01000010 00100，01001，10011， 11110。10000100 01000，00101，11111， 10010。10101000 10000，11101，00111， 01010。11110000 10100，11001，00011， 01110。01110100 10001，11100，00110， 01011。11010001 2021-8-161 习题课习题课 根据公式：“接收

51、向量”-“陪集首”=“所要译为的码字”，得到 的最佳译码表仍然是 接收向量译为 00000，00001，00010，00100，01000，10000，10100，10001。00000 01101，01100，01111，01001，00101，11101，11001，11100。01101 10111，10110，10101，10011，11111，00111，00011，00110。10111 11010，11011，11000，11110，10010，01010，01110，01011。 l1010 2021-8-162 习题课习题课 求“译码错误概率表示式”，第一种的理解是： )1

52、(5)1(1 ) 1(1 ) 2 (1 )(1 45 min ppp P d P P 差错向量的重量 差错向量的重量 肯定正确译码 2021-8-163 习题课习题课 求“译码错误概率表示式”，第二种的理解是： )1 (2)1 (5)1(1 )(1 )(1 )(1 4245 ppppp tP P P t 跑遍所有的陪集首 差错向量 之一差错向量是各个陪集首 正确译码 2021-8-164 (c)若码通过BEC信道传送，则至少可恢复dmin-1=2个删除。 因此，当接收向量中有不超过2个删除时，对应译码值是显然的。 当接收向量中有大于2个删除时，对应译码值比较复杂。 (d)一般，最小距离为一般，

53、最小距离为dmin的线性码，可恢复的线性码，可恢复dmin-1个删除。个删除。理由很 简单：一个码字，它的dmin-1个分量“模糊不清”，根据该码 字的其它N-(dmin-1)个分量来唯一确定码字。如果竟然确定了两 个码字满足条件，则这两个码字的距离 dmin-1。矛盾。 pp pp e 10 01 1 0 10 2021-8-165 习题课习题课 6.2 设证件号码由7位10进制数x7x6x1构成。今附加一位校验位x0， 其中 若(x7x6x1)(8245123)，试求x0。若其中数字x6模糊不清时，能 否恢复出原来的数字？ 6.2的解答 x0=33+29+127+581+4243+2729+82187(mod10) =