第六章有噪信道编码定理

2020/1/211/17理信学院孙桂萍有噪信道编码定理2020/1/212/17理信学院孙桂萍主要内容错误概率和译码规则最大后验概率准则最大似然译码准则错误概率与编码方法最小距离译码准则2020/1/213/17理信学院孙桂萍信道编码的目的o从信道编码的构造方法看，信道编码的基本思路是根据一定的规律在待发送的信息码中加入一些人为多余的码元，以保证传输过程可靠性。信道编码的任务就是构造出以最小的冗余度代价换取最大抗干扰性能的“好码”。2020/1/214/17理信学院孙桂萍信道的统计特性错误概率与信道的统计特性有关，而信道的统计特性可由信道的传递矩阵描述。二元对称信道，错误的传递概率为p，正确的为1-p：pppp110101信道矩阵2020/1/215/17理信学院孙桂萍错误概率不仅与信道的统计特性有关，还与接收端的译码规则有关。0输入10输出11/32/3二元对称信道2/31/3译码规则a：收到“0”译成“0”；收到“1”译成“1”在规则a确定的情况下，错误概率为：发送“0”，收到“0”，译成“0”——正确的译码，译码正确的概率为1/3；发送“0”，收到“1”，译成“1”——错误的译码，译码错误的概率为2/3错误概率与译码规则的关系2020/1/216/17理信学院孙桂萍因为是对称信道，那么发送“1”，错译成“0”的概率也为2/3。在此译码规则下，平均错误概率——PE这里，假设输入端等概率分布。3232213221)1()0()1()0(eeEPPPPP2020/1/217/17理信学院孙桂萍译码规则b：收到“0”译成“1”；收到“1”译成“0”在规则b确定的情况下，错误概率为：发送“0”，收到“1”，译成“0”——正确的译码，译码正确的概率为2/3；发送“0”，收到“0”，译成“1”——错误的译码，译码错误的概率为1/30输入10输出11/32/3二元对称信道2/31/3在此译码规则下，平均错误概率——PE3131213121)1()0()1()0(eeEPPPPP可见，译错的可能性减少，译对的可能性增加了。2020/1/218/17理信学院孙桂萍译码规则数学定义：设离散单符号信道的输入符号集为A={ai}，i=1,2,…,r；输出符号集为B={bj}，j=1,2,…,s。制定译码规则就是设计一个函数F(bj)，它对于每一个输出符号bj确定一个唯一的输入符号ai与其对应。每一个输入符号可以对应于多个输出符号，也就是s个输出符号中的每一个都可以译成r个输入符号中的任何一个，所以共有rs种译码规则。2020/1/219/17理信学院孙桂萍译码规则举例例6.1：有一离散单符号信道，信道矩阵为：4.03.03.05.03.02.02.03.05.0321321aaabbbP针对于这种信道，设计两种译码规则：332211)()()(:abFabFabFA233211)()()(:abFabFabFB2020/1/2110/17理信学院孙桂萍平均错误概率译码规则的选取原则是使得平均错误概率尽可能小。在确定了译码规则F(bj)后，若收到的为bj，译成ai，发送的是ai——正确收到的为bj，译成ai，发送的不是ai—错误条件正确概率为：条件错误概率为：)())((jijjbaPbbFP合以外的所有输入符号集代表除了ijaebeP)()(1))((1)(jijjjbaPbbFPbeP2020/1/2111/17理信学院孙桂萍平均错误概率平均错误概率PE应是条件错误概率对所有的Y求统计平均。sjjjEbePbPP1)()(为了是PE尽可能的小，对于“=”右侧的每个求和项都是非负的，所以应使得每个项尽量的小，而且译码规则只影响条件错误概率，对P(bj)没有影响，所以应选取译码规则使得条件错误概率尽量的小，那么也就是寻找条件正确概率尽量的大。2020/1/2112/17理信学院孙桂萍最大后验概率准则BbAaabFjj,,)(**数学描述选择译码函数：并使之满足条件**),()(aaAabaPbaPiijij文字描述采用一个译码函数，它对于每一个输出符号均译成具有最大后验概率的那个输入符号，则信道错误概率能达到最小，这种译码规则称为最大后验概率准则或最小错误概率准则。2020/1/2113/17理信学院孙桂萍最大后验概率准则另一种描述因为一般已知传递概率和输入符号的先验概率，所以将根据贝叶斯定律改写为：)(ijabP)(iaP**),()(aaAabaPbaPiijijBbaaAabPaPabPbPaPabPjiijiijjj,,)()()()()()(***一般P(bj)不等于0，最大后验概率可表示为：选择译码函数：使满足BbAaabFjj,,)(*****),()()()(aaAaaPabPaPabPiiiijj1式2020/1/2114/17理信学院孙桂萍最大似然译码准则若输入符号的先验概率均相等，则1式可写为：数学描述：选择译码函数：)(iaPBbAaabFjj,,)(**并满足：**),()(aaAaabPabPiiijj文字描述选择译码函数，收到bj后，译成信道矩阵P的第j列中最大那个元素所对应的信源符号。注意：最大似然译码准则对于先验概率等概率分布时才可使得错误概率PE最小。2020/1/2115/17理信学院孙桂萍平均错误概率的计算YaXYjijYXjiYjjYXjijYjjjYjjYjjEbaPbaPbaPbbFPbaPbPbbFPbPbbFPbePbPP*,*,,)()()(])([)()(])([1)(])([1)()(*)(abFj*)(abFj求和：可先列后行或先行后列，也就是说对于联合概率矩阵中可先求每列中除去所对应的以外所有元素，再对各列求和；也可以先对行i求和，除去译码规则中所对应的，然后再对各行求和。)(jibaP2020/1/2116/17理信学院孙桂萍平均错误概率的计算XieaXYijEPrabPrP)(,1)(1*)(iaP如果先验概率是等概率的，则PE为：raPi/1)(2020/1/2117/17理信学院孙桂萍例题6.2已知信道矩阵如下，根据最大似然译码选取译码规则，并计算平均错误概率。若输入不等概，概率分别为1/4，1/4，1/2，比较按照最大似然译码准则和最大后验概率准则选取的译码规则的PE4.03.03.05.03.02.02.03.05.0321321aaabbbP2020/1/2118/17理信学院孙桂萍费诺不等式平均错误概率与译码规则有关，而译码规则又由信道特性决定，由于错误的存在，所以当收到某符号后对发送端仍存在不确定性。可见，PE与信道疑义度有关：)1log()()/(rPPHYXHEE费诺不等式2020/1/2119/17理信学院孙桂萍对于此二元对称信道（假设等概）可以利用最大似然译码准则选取译码规则，使得PE尽量的小。F(b1)=a1F(b2)=a2注：b1=a1=0，b2=a2=1PE=0.5*0.01+0.5*0.01=0.01一般要求在-6到-9数量级上。错误概率与编码方法的关系0输入10输出1/p=0.99p=0.01二元对称信道0.010.99例12020/1/2120/17理信学院孙桂萍码一：重复编码将待发送的消息码重复发送几遍，可以减小错误的发生，提高可靠性。例如，重发三次，n=3输入序列（αi）输出序列（βj）000（许用码字）000001001010010011011100100101101110110111（许用码字）111输出序列8种可能，每一位都可能出错2020/1/2121/17理信学院孙桂萍码一：重复编码（n=3）的PE利用最大似然译码准则选取译码规则时需要知道信道矩阵，可计算得3222222332222223ppppppppppppppppppppppppppppP依据最大似然译码准则，应选取信道矩阵的每列中最大的那个传递概率对应的输入符号即为该列对应的输出要译成的输入符号。在此规则下求出PE：与发送单个符号相比，平均错误概率减小了两个数量级423103]6*2[21)(1*3pppPMPCYijE2020/1/2122/17理信学院孙桂萍重复编码可以使平均错误概率减小的原因重复编码三次时，α1(000)对应的输出序列为β1(000)，β2(001)，β3(010)，β5(100)，与α1比较之后可发现，或是相同，或是发生了一位错误，但是译码的结果都是正确的，降低了译错的可能性，平均错误概率减小了。若继续增大n，PE可逐渐减小，n可以无限增大吗？2020/1/2123/17理信学院孙桂萍答案是否定的，n不可以无限量增大因为n增大的同时，会降低信息传输率编码后的信道的信息传输率R=logM/n（比特/码符号）M不变的情况下，n增大，R变小所以不能为了使平均错误概率降低而一味的增大n。寻找好的编码方法的思路：找到一种编码方法，使PE相当低，但R能保持在一定水平。2020/1/2124/17理信学院孙桂萍码二：将8个符号均作为许用码字传送M=8，logM=3，R=logM/n=3/3=1同样利用最大似然译码准则选取译码规则，并可求得PE=3*10-2，比10-2还大。可发现，在二元信道的n次扩展信道中有2n个输入，从中取出M个做许用码字，M大，PE大，R大；M小，PE小，R小。2020/1/2125/17理信学院孙桂萍码三：在这个二元三次扩展信道中，取M=4再比较一下PE和R取{000，011，101，110}PE=2*10-2，R=2/3,与M=8比较都变小了。从8个中取4个有70种方法，选两组比较一下Ⅰ{000，011，101，110}Ⅱ{000，001，010，100}PE=2*10-2PE=2.28*10-2比较一下两组码的特点，分析为什么第Ⅱ组的平均错误概率大2020/1/2126/17理信学院孙桂萍码四：M=4，n=5，从二元五次扩展信道中32个输入符号中取4个，再比较一下PE和RR=log4/5=2/52151421354321)(iiiiiiiiiiiiiiaaaaaaaaaaaaaPE=7.8*10-4结论：增大了n，并适当的增大M及合适的编码方法，即可达到希望的结果重点比较一下M=4，n=3的情况，R略降，但PE却减少很多2020/1/2127/17理信学院孙桂萍汉明距离：码字对应位置上不同码元的个数D（αi，βj）两个二元码字Ci和Cj的距离等于对应位置上码元的模二和。码C的最小距离：这个码C中，任意两个码字的汉明距离的最小值dmin。码字距离2020/1/2128/17理信学院孙桂萍码A码B码C码D码E码字00011100001110111000000110001000000011011011111010000001010011100101110111消息数M24448码的最小距离dmin32131信息传输率R1/32/32/32/51错误概率PE3*10-42*10-22.28*10-27.8*10-43*10-22020/1/2129/17理信学院孙桂萍最小距离译码准则选择译码函数njjYCF,)(**使满足**,),(),(iijijCDD即满足*min*,),(),(iijijCDD注意：二元对称信道中最小距离译码准则等于最大似然译码准则。文字描述：二元信道中最大似然译码准则可表述为：当收到βj后，译成与之距离最近的输入码字α*。2020/1/2130/17理信学院孙桂萍总结编码，应采用选择M个消息所对应的码字之间最小距离dmin尽可能的大。译码，将接收的序列βj译成与之距离最近的那个码字α*。