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

信息论与编码理论基础第六章第一页，共六十九页，2022年，8月28日2023/1/181§6.1分组码的概念设信道是一个D元字母输入/D元字母输出的DMC信道，字母表为{0,1,…,D-1}。其信道转移概率矩阵为D×D矩阵传输错误的概率为

p。信道容量为C=logD-H(p)-plog(D-1)。第二页，共六十九页，2022年，8月28日2023/1/182§6.1分组码的概念对随机变量序列X1X2…进行的信道编码为(N,L)码：(X1X2…XL)→(U1U2…UN)=C(X1X2…XL)。这个(N,L)码又称为(N,L)分组码。已经有结论：当设备所确定的编码速率R<C/H(X)时，存在(N,L)分组码，使得实际编码速率(信息率L/N)任意接近R，译码错误的概率任意接近0。问题是：怎样构造这样的分组码？这样的分组码的编码、译码计算量会不会太大？（这才是研究分组码的含义）

第三页，共六十九页，2022年，8月28日2023/1/183§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(modD)。第四页，共六十九页，2022年，8月28日2023/1/184§6.1分组码的概念注1：如果D不是素数，({0,1,…,D-1},(modD)加法,(modD)乘法)不是有限域，只是有限环。注2：有限域GF(D)上的线性代数完全类似于实数域上的线性代数，线性代数的所有内容都在“加法”和“乘法”基础上得到。元素的“加法”负元；非0元的“乘法”逆元；一组向量是否“线性无关”的概念以及所有等价的判别方法；矩阵的“秩”的概念以及所有计算方法；方阵是否“可逆”的所有判别方法；求方阵的“逆阵”的所有算法；关于对称矩阵的所有结论；等等。注3：有限域GF(D)与实数域的区别是：传统的“逼近”、“极限”的概念消失了。第五页，共六十九页，2022年，8月28日2023/1/185例：取D=2，则GF(2)=({0,1},(mod2)加法,(mod2)乘法)。运算规则为：

0+0=1+1=0，0+1=1，0×0=0×1=0，1×1=1。方阵是否可逆？回答是肯定的。两种不同的判别方法都能够证明它是可逆的：（1）它经过可逆行变换能够变成单位阵；（2）它的行列式不等于0。（等于1！）第六页，共六十九页，2022年，8月28日2023/1/186§6.1分组码的概念该方阵的逆矩阵是什么？怎样计算？做联合可逆行变换：第七页，共六十九页，2022年，8月28日2023/1/187§6.1分组码的概念例：取D=3，则GF(3)=({0,1,2},(mod3)加法,(mod3)乘法))。运算规则为：0+0=1+2=0，0+1=2+2=1，0+2=1+1=2，0×0=0×1==0×2=0，1×1=2×2=1，1×2=2。矩阵是不是满行秩的？换句话说，此矩阵的三个行向量是不是在域GF(3)上线性无关的？再换句话说，能否保证此矩阵的各行的任何非0线性组合都不是全0的4维向量？再换句话说，此矩阵能否通过一些可逆行变换变成一个“阶梯阵”？第八页，共六十九页，2022年，8月28日2023/1/188§6.1分组码的概念可逆行变换第九页，共六十九页，2022年，8月28日2023/1/189§6.1分组码的概念例：域GF(D)上的一个L行N列的矩阵（L×N阶的矩阵）G，设它是满行秩的（当然此时有L≤N）。则变换(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)。第十页，共六十九页，2022年，8月28日2023/1/1810§6.1分组码的概念预备知识2：有限域上的分组码当D是素数时，分组码可以充分利用有限域GF(D)的代数运算，使得编码和译码更加简便。第十一页，共六十九页，2022年，8月28日2023/1/1811§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为此码的生成矩阵。第十二页，共六十九页，2022年，8月28日2023/1/1812§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)的码字。第十三页，共六十九页，2022年，8月28日2023/1/1813§6.2线性分组码命题3信息向量(x1,x2,…,xL)的码字是：x1数乘G的第1行，加x2数乘G的第2行，加…，加xL数乘G的第L行。换句话说，任何一个码字都是生成矩阵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))的码字。证完。第十四页，共六十九页，2022年，8月28日2023/1/1814§6.2线性分组码（命题3和命题4告诉我们，一个N维向量是一个码字，当且仅当它是生成矩阵G的第1行~第L行的线性组合。还告诉我们，线性分组码的码字集合构成一个线性空间。这个线性空间是几维的？L维的，因为生成矩阵G的第1行~第L行恰好是该线性空间的一组基）命题5设一个D元(N,L)线性分组码的生成矩阵为G。设另一个D元(N,L)线性分组码的生成矩阵为G'=MG，其中M是L阶可逆方阵。则两个码的码字集合完全重合，只是信息向量与码字的对应关系不同。换句话说，如果把线性分组码的生成矩阵G做可逆行变换变成另一个生成矩阵，则不改变码字集合，只改变信息向量与码字的对应关系。第十五页，共六十九页，2022年，8月28日2023/1/1815§6.2线性分组码证明（要证明，第一个码中任一个码字也是第二个码中的码字；第二个码中任一个码字也是第一个码中的码字）设在第一个码中，u是信息向量x的码字：u=xG；则在第二个码中，u是信息向量xM-1的码字：u=xM-1MG=xM-1G'。设在第二个码中，u是信息向量x的码字：u=xG'；则在第一个码中，u是信息向量xM的码字：u=xMM-1G'=xMG。证完。

第十六页，共六十九页，2022年，8月28日2023/1/1816§6.2线性分组码线性分组码的特例：系统码定义(p178)

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位为码字的一致校验位。第十七页，共六十九页，2022年，8月28日2023/1/1817§6.2线性分组码例

此二元(7,4)码是线性分组码，生成矩阵G是由信息向量(1000)、(0100)、(0010)、(0001)的码字组成的4行第十八页，共六十九页，2022年，8月28日2023/1/1818§6.2线性分组码例此二元(5,3)线性分组码的生成矩阵是第十九页，共六十九页，2022年，8月28日2023/1/1819§6.3线性分组码的校验矩阵线性分组码的校验矩阵定理(p179)

对于D元(N,L)线性分组码的生成矩阵G（G是L×N阶矩阵），必存在一个(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)线性分组码的校验矩阵。第二十页，共六十九页，2022年，8月28日2023/1/1820§6.3线性分组码的校验矩阵有以下的结论。（1）一个线性分组码有很多校验矩阵。一个校验矩阵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第二十一页，共六十九页，2022年，8月28日2023/1/1821§6.3线性分组码的校验矩阵（怎样由生成矩阵G计算出校验矩阵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,-PT]T=P-P=OL×(N-L)。证完。（5）设D元(N,L)线性分组码的生成矩阵经过可逆行变换后变为[P,IL]，则校验矩阵也可以取为H=[IN-L,-PT]。第二十二页，共六十九页，2022年，8月28日2023/1/1822§6.3线性分组码的校验矩阵第二十三页，共六十九页，2022年，8月28日2023/1/1823§6.5译码方法和纠错能力线性分组码的纠错译码准则定义

(已知)一个N维向量u的Hamming重量定义为它的对应位置值不等于0的位数。记为w(u)。两个N维向量u(1)和u(2)的Hamming距离定义为它们的对应位置值不相同的位数。记为d(u(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))。第二十四页，共六十九页，2022年，8月28日2023/1/1824§6.5译码方法和纠错能力设GF(D)上的D元(N,L)线性分组码，生成矩阵为G。将信息向量x编码，得到码字u=xG。将码字u输入信道。信道的输出值为y。使用最小距离准则：给定输出值y，寻找码字c使d(y,c)最小。将输出值y译为码字c。当c=u时，就实现了正确译码。直接使用最小距离准则的困难：需要将DL个码字与输出值y的Hamming距离进行对比，才能找到码字c使d(y,c)最小。计算量大。(穷举搜索)第二十五页，共六十九页，2022年，8月28日2023/1/1825编码-译码过程图示。其中

x(1)、x(2)、x(3)、x(4)是各个信息向量；

c(1)、c(2)、c(3)、c(4)是各个对应码字。第二十六页，共六十九页，2022年，8月28日2023/1/1826§6.5译码方法和纠错能力实用纠错译码算法的预备知识：差错向量和伴随式定义

设信道的输入为码字u；信道的输出值为向量y。称向量e=y-u为差错向量，或差错图样。（请注意：①此时y=u+e；u=y-e；向量的加减法是对应分量的(modD)加减法。②在信道的输出端，只能得到输出向量y，并不能得到差错向量e，因此不能得到输入码字u。）定义(p195)设H是校验矩阵。对于N维行向量t，记s=tHT并称N-L维行向量s为N维行向量t的伴随式。第二十七页，共六十九页，2022年，8月28日2023/1/1827§6.5译码方法和纠错能力有以下的结论。（1）N维行向量t是一个码字，当且仅当t的伴随式是一个全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第二十八页，共六十九页，2022年，8月28日2023/1/1828§6.5译码方法和纠错能力（3）设输出向量为y，并计算出了y的伴随式s=yHT。t是任意一个满足方程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。第二十九页，共六十九页，2022年，8月28日2023/1/1829§6.5译码方法和纠错能力（4）设输出向量为y，并计算出了y的伴随式s=yHT。则此时所有“可能的差错向量”，恰好就是任何一个“可能的差错向量”加上全体码字。换句话说，此时所有“可能的差错向量”，恰好就是方程s=tHT的任何一个固定解t加上全体码字。（证明思想：非齐次通解=非齐次特解+齐次通解）（5）每个伴随式所对应的“可能的差错向量”共有DL个。伴随式是N-L维行向量，因此有DN-L个不同的伴随式。不同的伴随式所对应的“可能的差错向量”不会重合。DLDN-L=DN。定义在以s为伴随式的全体“可能的差错向量”中，取一个Hamming重量最小的向量称为s的陪集首，记为e(s)。（在以s为伴随式的全体“可能的差错向量”中，Hamming重量最小的向量或许有不止一个。任意选择一个作为陪集首e(s)即可）第三十页，共六十九页，2022年，8月28日2023/1/1830§6.5译码方法和纠错能力（6）对信道的输出向量y，计算伴随式s=yHT，以s为地址查找陪集首e(s)，计算u=y-e(s)。则u就是在所有码字中与y的Hamming距离最小的码字。证明首先，注意到e(s)是一个“可能的差错向量”。因此uHT=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)。证完。第三十一页，共六十九页，2022年，8月28日2023/1/1831§6.5译码方法和纠错能力实用纠错译码算法预计算对每个伴随式（即N-L维行向量）s，寻找s的陪集首e(s)，并以s为地址存储e(s)。（预计算的总体计算量很大，但有许多技巧可以大幅度地减少计算量）现场纠错译码

（1）对信道的输出向量y，计算伴随式s=yHT。（2）以s为地址查找陪集首e(s)。（3）将输出向量y译为码字u=y-e(s)。结束。u就是在所有码字中与y的Hamming距离最小的码字。第三十二页，共六十九页，2022年，8月28日2023/1/1832§6.5译码方法和纠错能力现场纠错译码的计算量计算量最大的是第（2）步。因为s是N-L维行向量，所以查找s的计算量是logDN-L=(N-L)logD

（而不是DN-L）。总之，计算量远远小于直接使用最小距离准则的计算量DL。第三十三页，共六十九页，2022年，8月28日2023/1/1833§6.5译码方法和纠错能力线性分组码的检错能力和纠错能力首先我们发现，能否正确译码并不依赖于输入的是什么码字，仅仅依赖于真正的差错向量是什么。显然P(正确译码)=P(真正的差错向量是某个陪集首)。其次我们可以定义更加简单的检错能力和纠错能力。定义

线性分组码的最小Hamming距离定义为两个不同码字的Hamming距离的最小值，记为dmin。线性分组码的最小Hamming重量定义为非全0码字的Hamming重量的最小值，记为wmin。第三十四页，共六十九页，2022年，8月28日2023/1/1834§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码字，所以dmin≥wmin。设一个非全0码字u，使得wmin=w(u)=w(u-全0码字)=d(u,全0码字)。所以dmin≤wmin。证完。第三十五页，共六十九页，2022年，8月28日2023/1/1835§6.5译码方法和纠错能力引理2

设信道的输入为码字u，信道的输出为向量y，差错向量（注：真正的差错向量）为e=y-u。则（1）当w(e)<dmin，yHT肯定不是全0的N-L维向量，因而发现信道传输错误。（2）当w(e)≤[(dmin-1)/2]（下方取整），由上述实用纠错译码算法肯定将y译为真正的输入码字u，而不会将y译为其它码字。第三十六页，共六十九页，2022年，8月28日2023/1/1836§6.5译码方法和纠错能力证明（1）当w(e)<dmin，e肯定不是码字。因此yHT=eHT≠全0的N-L维向量。（2）当w(e)≤[(dmin-1)/2]（下方取整），则y与任意另一个码字c的Hamming距离d(c,y)≥d(c,u)-d(y,u)（三角不等式）≥dmin-d(y,u)=dmin-w(e)≥dmin-[(dmin-1)/2]>[(dmin-1)/2]

≥w(e)=d(y,u)因此，所有码字中，u与y的Hamming距离最小。证完。第三十七页，共六十九页，2022年，8月28日2023/1/1837§6.5译码方法和纠错能力引理3

设差错向量（注：真正的差错向量）为e。当w(e)>[(dmin-1)/2]（下方取整），由上述实用纠错译码算法未必将输出向量译为真正的输入码字。举例取两个码字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]。第三十八页，共六十九页，2022年，8月28日2023/1/1838d(y,u)=[(dmin-1)/2]+1；

d(c,y)=dmin-1-[(dmin-1)/2]。当dmin是奇数时，d(y,u)=(dmin-1)/2+1，d(c,y)=(dmin-1)/2，故d(c,y)<d(y,u)。当dmin是偶数时，d(y,u)=dmin/2，d(c,y)=dmin/2，故d(c,y)=d(y,u)。这就是说，如果输入码字u，输出向量y，则当dmin是奇数时，将y译为c而不是u；当dmin是偶数时，将y译为c或u都符合最小距离准则。第三十九页，共六十九页，2022年，8月28日2023/1/1839§6.5译码方法和纠错能力对引理2和引理3的解释设信道真正的输入码字为u，信道的输出向量为y，真正的差错向量为e=y-u。采用实用纠错译码算法：接收y→计算伴随式s=yHT→以s为地址查找e(s)→计算c=y-e(s)→认为陪集首e(s)就是差错向量；认为c就是输入码字。引理2告诉我们，如果w(e)≤[(dmin-1)/2]

，则e(s)=e，因而c=u。引理3告诉我们，如果w(e)>[(dmin-1)/2]

，则未必e(s)=e，因而未必c=u。换句话说，如果w(e)≤[(dmin-1)/2]

，则e一定是s=eHT的陪集首；如果w(e)>[(dmin-1)/2]

，则e未必是s=eHT的陪集首。第四十页，共六十九页，2022年，8月28日2023/1/1840§6.5译码方法和纠错能力定理

记真正的差错向量为e。记t是一个非负整数。如果（1）当w(e)≤t时总是能够正确译码，（2）当w(e)>t时并不总是能够正确译码，则t

=[(dmin-1)/2]。推论记真正的差错向量为e。事件“总是能够正确译码”定义为“w(e)≤[(dmin-1)/2]”。则“总是能够正确译码”的概率为第四十一页，共六十九页，2022年，8月28日2023/1/1841§6.5译码方法和纠错能力定理说明，dmin是线性分组码纠错能力的一个指标。dmin越大，[(dmin-1)/2]就越大，“总是能够正确译码”的概率也越大。当N比L大得越多，码字在所有N维向量中占的比例越小，越容易使得dmin大。问题是，当N和L都确定时，如何设计码使得dmin大。纠正一种误解：dmin越大，“总是能够正确译码”的概率越大。决不能说：dmin越大，正确译码的概率越大。

（??P185,式子）第四十二页，共六十九页，2022年，8月28日2023/1/1842§6.5译码方法和纠错能力例

二元（6，3）线性分组码，生成矩阵G已经给出。求一致校验矩阵H；码字集合；译码预计算（简化计算量）。

显然是系统码。第四十三页，共六十九页，2022年，8月28日2023/1/1843§6.5译码方法和纠错能力信息向量→码字000→000000100→011100010→101010001→110001110→110110101→101101011→011011111→000111第四十四页，共六十九页，2022年，8月28日2023/1/1844§6.5译码方法和纠错能力伴随式s→对应的所有“可能的差错向量”e000→000000，011100，101010，110001，110110，101101，011011，000111100→100000，111100，001010，010001，010110，001101，111011，100111010→010000，001100，111010，100001，100110，111101，001011，010111001→001000，010100，100010，111001，111110，100101，010011，001111110→000100，011000，101110，110101，110010，101001，011111，000011101→000010，011110，101000，110011，110100，101111，011001，000101011→000001，011101，101011，110000，110111，101100，011010，000110111→100100，111000，001110，010101，010010，001001，111111，100011伴随式s→陪集首e(s)000→000000100→100000010→010000001→001000110→000100101→000010011→000001111→100100第四十五页，共六十九页，2022年，8月28日2023/1/1845§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,式）若p=10-2，则(1-p)6=0.9415；

(1-p)6+6(1-p)5p=0.9986；

(1-p)6+6(1-p)5p+(1-p)4p2=0.9987。第四十六页，共六十九页，2022年，8月28日2023/1/1846§6.5译码方法和纠错能力设信道的输出向量为y=(111111)。计算伴随式s=yHT=(111)。以s为地址查找e(s)=(100100)。计算c=y-e(s)=(111111)-(100100)=(011011)。信息向量为(011)。第四十七页，共六十九页，2022年，8月28日2023/1/1847§6.4、§6.6、§6.7、§6.8一些特殊的线性分组码二元Hamming码N=2m-1，L=2m-1-m，即二元(2m-1，2m-1-m)线性分组码。其校验矩阵是如下的m×(2m-1)阶矩阵H：H的(2m-1)列恰好是(2m-1)个非全0的m维向量。因此：校验矩阵H的任意一列不是全0的m维向量；校验矩阵H的任意两列互不相同；校验矩阵H的某三列的和为全0的m维向量。换句话说，重量为1、重量为2的2m-1维向量都不是码字，而某些重量为3的2m-1维向量是码字。再换句话说，Hamming码的dmin=3。再换句话说，当差错向量的重量不超过1时，肯定能够正确译码。编码效率为R=(2m-1-m)/(2m-1)

。（编码效率大）第四十八页，共六十九页，2022年，8月28日2023/1/1848§6.4、§6.6、§6.7、§6.8一些特殊的线性分组码定义

如果存在一个t，使得任一个接收向量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）第四十九页，共六十九页，2022年，8月28日2023/1/1849§6.4、§6.6、§6.7、§6.8一些特殊的线性分组码Hadamard码从Hadmard矩阵的行中选择码字可以构造出Hadamad码。Hadmard矩阵Mn是一个n×n阶矩阵，其中n=2m。该矩阵满足有一行为全0行，其余的行有2m-1个0，2m-1个1。任意两行有2m-1个位置不同，2m-1个位置相同。如何构造Hadmard矩阵？看如下的递归方法。第五十页，共六十九页，2022年，8月28日2023/1/1850§6.4、§6.6、§6.7、§6.8一些特殊的线性分组码以Hadmard矩阵Mn的所有行作为所有的码字，得到的码就是Hadamad码。Hadamad码的参数如下：共有n个码字，因此共有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行构成的m×n阶矩阵。（？）第五十一页，共六十九页，2022年，8月28日2023/1/1851§6.4、§6.6、§6.7、§6.8一些特殊的线性分组码Golay码Golay码是线性(23,12)码，最小距离为7。将其增加一个全校验位扩展为二元线性（24,12）码，最小距离为8，称为扩展Golay码。表给出了Golay码和扩展Golay码的重量分布。循环码定义(p188)一个二元(N,L)线性分组码C，若对任意c=(c0,c1,c2,…,cN-1)∈C，恒有c'=(cN-1,c0,c1,…,cN-2)∈C，则称C为二元循环码。第五十二页，共六十九页，2022年，8月28日2023/1/1852§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+g1x1+g2x2+…+gN-L

xN-L。取以下的L×N矩阵G作为二元(N,L)线性分组码C的生成矩阵，则该码一定就是一个二元循环码。（主教材中有证明）第五十三页，共六十九页，2022年，8月28日2023/1/1853§6.4、§6.6、§6.7、§6.8一些特殊的线性分组码例(p190)~例(p192)取N=7。则（在GF(2)上）：

1+x7=(1+x)(1+x+x3)(1+x2+x3)。若取g(x)=1+x+x3

，则产生的二元(7,4)线性分组码C一定就是一个二元循环码，生成矩阵为第五十四页，共六十九页，2022年，8月28日2023/1/1854§6.4、§6.6、§6.7、§6.8一些特殊的线性分组码如此产生的二元循环码的译码设接收向量为y=(y0,y1,y2,…,yN-1)。记y(x)=y0+y1x1+y2x2+…+yN-1xN-1

。用g(x)除y(x)，得余式s(x)=s0+s1x1+s2x2+…+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)就是接收向量y的伴随式。（因而不需要校验矩阵）第五十五页，共六十九页，2022年，8月28日2023/1/1855习题课6.1设有4个消息al，a2，a3

和a4被编成为长为5的二元码的00000，01101，10111，l1010。(a)试给出码的一致校验关系。(b)若通过转移概率为p<1/2的BSC传送，试给出最佳译码表及相应的译码错误概率表示式。(c)若码通过BEC信道传送，试问可恢复几个删除?其最佳译码表应如何配置？(d)一般，最小距离为dmin的线性码，可恢复几个删除?第五十六页，共六十九页，2022年，8月28日2023/1/1856习题课(a)首先需要验证该码是线性码：01101‘+’10111=l1010。其次需要给出该码的生成矩阵和校验矩阵：最后该码的一致校验关系为：对任意码字(x0x1x2x3x4)，恒有x0+x1+x2=0，x0+x3=0，x0+x1+x4=0。第五十七页，共六十九页，2022年，8月28日2023/1/1857习题课(b)通过转移概率为p<1/2的BSC传送。如果直接按照“最小距离准则”来求最佳译码表，则最佳译码表为接收向量译为00000，00001，00010，00100，01000，10000，10100，10001。0000001101，01100，01111，01001，00101，11101，11001，11100。0110110111，10110，10101，10011，11111，00111，00011，00110。1011111010，11011，11000，11110，10010，01010，01110，01011。

l1010第五十八页，共六十九页，2022年，8月28日2023/1/1858习题课求“译码错误概率表示式”，可以有多种含义。本题应该理解为以下的含义，而不应该理解为别的含义：第五十九页，共六十九页，2022年，8月28日2023/1/1859求最佳译码表，当然也可以采用标准方法，先求可能的差错向量、伴随式、陪集首的关系：可能的差错向量伴随式陪集首00000，01101，10111，11010。0000000000001，01100，10110，11011。0010000100010，01111，10101，11000。0100001000100，01001，10011，11110。1000010001000，00101，11111，10010。1010100010000，11101，00111，01010。1111000010100，11001，00011，01110。0111010010001，11100，00110，01011。11010001第六十页，共六十九页，2022年，8月28日2023/1/1860习题课根据公式：“接收向量”-“陪集首”=“所要译为的码字”