信息论中的有噪信道编码

信息论中的有噪信道编码2023/6/27信息论中的有噪信道编码25.1错误概率和译码规则编码信道2023/6/27信息论中的有噪信道编码3正确概率通信过程不是在信道输出端结束，要经过译码到达收信者，所以译码过程和译码规则对错误概率有影响2023/6/27信息论中的有噪信道编码4图5.1二元对称信道设输入等概，收到0，译为0，译对概率为，译错概率为收到0，译为1，收到1，译为0，译对概率为，译错概率为结论错误概率与信道统计特性有关，与译码规则有关2023/6/27信息论中的有噪信道编码5XYa1a2arb1b2bsp(bj/ai)译码函数定义译码规则2023/6/27信息论中的有噪信道编码6rs种译码规则2023/6/27信息论中的有噪信道编码7两种典型的译码规则

译码规则选择的一个很自然的规则就是错误概率最小若定义收到bj后就一定译为ai

，若发送的是ai

，就认为正确2023/6/27信息论中的有噪信道编码8平均错误概率如何使平均错误概率最小？最大后验概率准则最小错误概率准则2023/6/27信息论中的有噪信道编码9一般是已知：根据贝叶斯公式：一般：选择2023/6/27信息论中的有噪信道编码10如果都相等上式：这样定义的译码规则称为最大似然译码规则最大似然译码规则不依赖于先验概率，但当先验概率为等概时，它使平均错误概率最小2023/6/27信息论中的有噪信道编码11上式中求和号表示对输入符号集X中除以外的所有元素求和

2023/6/27信息论中的有噪信道编码12正确概率上式在联合矩阵先求每列除去所对应的以外所有元素之和，然后再对各列求和。也可在联合矩阵中先对行i求和，除去译码规则中所对应的然后再对行求和2023/6/27信息论中的有噪信道编码13输入ai引起的错误概率如果先验概率是等概2023/6/27信息论中的有噪信道编码14例题已知信道则设计的最大似然译码规则：设输入等概，则错误概率：信道矩阵中每列取大值2023/6/27信息论中的有噪信道编码15设输入不等概，p(a1)=1/4,p(a2)=1/4,p(a3)=1/2

则设计的最小错误概率译码规则为：联合矩阵中每列取大值2023/6/27信息论中的有噪信道编码16=(1/8+1/24)+(1/12+1/12)+(1/12+1/24)=11/24

输入不等概时，最大似然译码规则的平均错误概率不是最小2023/6/27信息论中的有噪信道编码175.2错误概率与编码方法

图二元对称信道

（输入等概）2023/6/27信息论中的有噪信道编码182023/6/27信息论中的有噪信道编码19则最大似然译码规则：择多译码2023/6/27信息论中的有噪信道编码20显然，重复更多次，错误概率会更小消息传输率（码率）：比特/码符号

比特/秒

M是输入消息符号的个数

2023/6/27信息论中的有噪信道编码21（重复三次），M=2比特/码符号

（重复五次），M=2比特/码符号

如何使得错误概率相当低，而R却保持在一定水平？从理论上讲，这时可能的，即香农第二定理，有噪信道编码定理2023/6/27信息论中的有噪信道编码22N＝3，输入端有8个消息，选择2个消息，即M=2，这样每个消息携带平均信息量仍为1比特，而传送一个消息需要付出三个二元符号，所以R下降到1/3而输入端8个消息都作为消息发送，R＝1，错误概率却又降低了输入端有2n符号序列可作为消息，如果选择其中的M个作为消息，则M大些，PE也跟着大，R也大，则M小些，PE也跟着小，R也小，2023/6/27信息论中的有噪信道编码23图N次扩展信道的消息符号2023/6/27信息论中的有噪信道编码24在三次扩展信道中，取M=4作为消息符号第I种选法第II种选法000000011001101010110100按照最大似然译码规则第I种选法PE=2×10－2

第II种选法PE×10－2

2023/6/27信息论中的有噪信道编码25选择M=4，n＝5，2023/6/27信息论中的有噪信道编码262023/6/27信息论中的有噪信道编码27这与M=4，n=3两中编码方法比较，R略为下降一些，错误概率却小得多汉明距离码的最小距离：2023/6/27信息论中的有噪信道编码28

码A码B码C码D码E码

字00011100001110111000000110001000000011011011111010000001010011100101110111消息数M24448码的最小距离32131信息传输率R(比特/码符号)1/32/32/32/51错误概率(最大似然译码规则)310-4210-22.2810-27.810-4310-22023/6/27信息论中的有噪信道编码29最大似然译码规则：满足越大，越小越小，越大2023/6/27信息论中的有噪信道编码30最大似然译码规则用汉明距离表示为：最小距离译码准则在二元对称信道中，最小距离译码准则等于最大似然译码规则2023/6/27信息论中的有噪信道编码31在有噪信道中，错误概率与编码、译码规则有关，编码可采用选择M个消息，使之对应的码字最小距离尽可能最大的编码方法；译码采用将接受符号序列译为距离最近的码字，则码长足够长时，合适的选择M，可使错误概率很小，而信息传输率保持不变2023/6/27信息论中的有噪信道编码325.3有噪信道编码定理

香农第二定理证明方法包含的思路：允许平均错误概率任意小；连续使用信道许多次；在n次无记忆扩展信道中讨论，使大数定律有效；随机选取码书，证明有一种好码存在2023/6/27信息论中的有噪信道编码33有噪信道编码定理：设离散无记忆信道[X,p(y|x),Y],p(y|x)为信道传递概率，其信道容量为C，当信息传输率R<C时，只要码长足够长，总可以在输入Xn符号中找到M＝2nR个码字，构成一组码（2nR

，n）和相应的译码规则，使译码的错误概率任意小（PE

－>0）2023/6/27信息论中的有噪信道编码34有噪信道编码逆定理：设离散无记忆信道[X,p(y|x),Y],p(y|x)为信道传递概率，其信道容量为C，当信息传输率R>C时，无论码长多长，总也找不到一组码（2nR

，n）和相应的译码规则，使译码的错误概率任意小（PE

－>0）2023/6/27信息论中的有噪信道编码355.4纠错码基本思想和汉明码处理差错的两种基本策略：纠错码和检错码纠错码：在每一个要发送的数据块上附加足够的冗余信息，使接受方能够推导出已发出的字符应该是什么。检错码：只加入足够的冗余位，使接受方知道有差错发生，但不知错误所在，然后，要求发送方重传。码字：通常一帧包括m个数据位和r个校验位或冗余位，整个长度为n位,(n=m+r)则此长度为n的单元被称为n位码字。2023/6/27信息论中的有噪信道编码36汉明距离：两个码字中不同的位的个数该概念的重要性：两个码字具有汉明距离d，则需要d个位差错才能将其中一个码字转换成另一个。一种编码的校验和纠错能力取决于它的汉明距离。2023/6/27信息论中的有噪信道编码37从功能角度：检错码、纠错码对信息序列的处理方法：分组码、卷积码码元与原始信息位的关系：线性码、非线性码差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码、几何码、算术码、组合码等纠错码分类2023/6/27信息论中的有噪信道编码38码字的汉明重量非零码元个数，二元码中指含“1”的个数汉明距离满足：对称性；非负性；距离三角不等式2023/6/27信息论中的有噪信道编码39定义E＝(en－1,…,e1,e0)＝R－C

＝(rn-1－cn-1,…,r1－c1,r0－c0)二进制码中模2加与模2减是等同的，因此有E=R＋C及R=C＋E 错误图样E（差错图案E）ei取0，表示该码元无错C=RE

，差错图样中的“１”既是符号差错也是比特差错。2023/6/27信息论中的有噪信道编码40若BSC信道的差错概率是p，则长度n的码中错误概率：

0个错1个错2个错…n个错

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

由于p<<1,>>>>>>…>>

出错越少的情况，发生概率越大，E的重量越轻，2023/6/27信息论中的有噪信道编码41分组码纠正随机错误能力与码书中最小距离关系码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmindmin=3，纠错能力是1，检错能力是22023/6/27信息论中的有噪信道编码422023/6/27信息论中的有噪信道编码43要发现（检测）e个随机错误，要求：2023/6/27信息论中的有噪信道编码44要纠正e个随机错误，要求：2023/6/27信息论中的有噪信道编码45要纠正e个错误，同时检测到f个随机错误，要求：2023/6/27信息论中的有噪信道编码46常用的检、纠错码奇偶检验码行列奇偶检验码1101001010110001011011000010011110011001

10110001

行监督元列监督元发送顺序1101001010110001…2023/6/27信息论中的有噪信道编码47等比码检验码字中含“1”和“0”个数之比如：3：2等比码，“1”－>3个，

“0”

－>2个，5中取3码2023/6/27信息论中的有噪信道编码48在（n,k）线性分组码中，n－码长，k－信息位，也就是自空间的维数。设M=(m1,m2,…mk)是输入纠错码编码器的信息组，输出码字cc＝mG1×n1×k

k×n

码字消息生成矩阵G建立了消息与码字矢量间的一一对应关系，C的每一位都是消息数字的线性组合2023/6/27信息论中的有噪信道编码492023/6/27信息论中的有噪信道编码50G1=

101011110101111000G2=

100110010011001100消息用G1得到的码字用G2得到的码字0000000000000000011110000011010101101010100110110011010111101001010111001101010100111010111100111101101011111001101110002023/6/27信息论中的有噪信道编码51上表所示码字，虽然用不同的生成矩阵得到，但属于同一个（n,k）码的码字空间，检、纠错能力一样。G2生成是码字，其前k位与消息位完全相同，这种码称为系统码，否则称为非系统码2023/6/27信息论中的有噪信道编码52想要保证(n,k)线性分组码能够构成k维n重子空间，G的k个行矢量gk,…,g2,g1必须是线性无关的，只有这样才符合作为基底的条件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。2023/6/27信息论中的有噪信道编码53若通过行运算和列置换能将两个生成矩阵G互等，则称这两个G等效。非系统码的G可通过运算转变为系统码的G。等效的两个G生成的两个(n,k)线性码也是等效的。因此，每个(n,k)线性码都可以和一个系统的(n,k)线性码等效。2023/6/27信息论中的有噪信道编码54系统形式的生成矩阵(n,k)码的任何生成矩阵都可以通过行运算（以及列置换）简化成“系统形式”。G=[Ik

P]Ik是k×k单位矩阵，P是k×(n-k)矩阵。2023/6/27信息论中的有噪信道编码55在线性分组码（n,k）中因为监督元和信息位之间是线性关系，所以每个码字中r(=n-k)和信息位之间关系为：

HCT=0T

或CHT=0H称为（n,k）线性码的一致监督矩阵2023/6/27信息论中的有噪信道编码56把H实行初等行变换和列置换，将H的后r列化为单位子矩阵，则H实行初等行变换和列置换，后r列为单位子矩阵的H称为监督矩阵的标准形式H=[QIr]2023/6/27信息论中的有噪信道编码57G和H之间关系：由于G中的每一行都是一个码字，所以G每行满足监督关系式HCT=0T

，则有

HGT=0T

或GHT=0将H=[QIr]和G=[Ik

P]代入上式，得到

P=QT或PT=QG和H行矢量彼此正交得到G=[Ik

P]=[Ik

QT]2023/6/27信息论中的有噪信道编码58汉明码汉明码不是指一个码，而是代表一类码。汉明码的纠错能力t=1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律：(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整数,n－码长，k－信息位，r－监督位，d－最小距离。当m＝3、4、5、6、7、8…时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。2023/6/27信息论中的有噪信道编码59

汉明码的校验矩阵H具有特殊的性质，能使构造方法简化。一个(n,k)码的校验矩阵有n－k行和n列，二进制时n-k个码元所能组成的列矢量总数是2n-k-1,恰好和校验矩阵的列数n=2m-1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。汉明码H中任意两列线性无关，且没有全零列2023/6/27信息论中的有噪信道编码60例6.4构造一个m=3的二元(7，4)汉明码。解：先利用汉明码的特性构造一个(7，4)汉明码的校验矩阵H，再通过列置换将它变为系统形式：

0001111列置换0111100 H= 0110011 1011010=[PT

I3] 1010101 1101001再得生成矩阵G为

1000011 G=[I4

P]=0100101 0010110 0001111 2023/6/27信息论中的有噪信道编码61H矩阵各列位置调动后，相当于码字各个分量次序作了相应的变动，不过只是形式不同，码字重量分布不同，检纠错能力一样H矩阵各列位置调动，不改变各列之间的相关性H各列排列原则上是任意的，应用上常两种：标准形式，得到系统码，＝>GR重二进制按所代表的十进数次序排列2023/6/27信息论中的有噪信道编码62