第14讲――信道编码与译码2014

信道编码与译码第十四讲•第三章讨论无失真信源编码，给出无失真编码所需最小速率R≥H(U)/logD.•信道给定，以任意小的错误概率实现可靠通信的最大传输速率为多少？•Shannon于1948年提出并证明了信道编码定理，揭示了在什么条件下可以实现可靠通信，在什么情况下不能实现。•后来很多研究者给出了更严格、更一般化的证明，指出了各种信道和编码条件下所能达到的编码定理的上、下限。•这些理论的进展为合理设计实际通信系统提供了理论依据。什么条件？RC信道信源信源编码信道编码调制器干扰源信宿信源译码信道译码解调器数字通信系统模型信道编码信道编码（纠错编码）的任务是将输入的信息数字序列变换成另一个数字序列送入有扰离散信道。人为的按一定规则增加多余度，以便纠正传送过程中可能出现的错误，以尽可能小的错误概率恢复原来的信源序列。0001101100000101011101001111r=1111011010(10)011-p101-ppp假设p0.5不编码，误码率pb=p编码，pe=3p2+p3-6p4+3p5输入L级移存器纠错编码器0KmUu0NmXx输出信道编码器模型c0000=,cscsnknk每个信息数字持续时间为秒ssR/1编码器通常对信息数字进行分段，称为信息段，设其长度为.0ksk00n在时间段内，编码器计算出个编码数字送入信道，称为码段。编码数字持续时间为秒,信道编码分类通常纠错码被分为两类，分组码和格状码。（N,K)分组码：每K个信息数字为一组，计算出N个编码数字构成一个分组，一个分组又称为一个码字。码字之间是不相关的。格状码：输出的码段不仅依赖于当前的K0位信息数字，还依赖于前m个信息段的信息数字，即总共与（m+1)K0个信息数字有关。称（m+1)K0为编码约束长度。称或为纠错码的编码速率或简称码率00/nkRNKR/要求纠错能力越强，所需多余度越大，码率就越低。0001101110101100100111011111编码jm1jm110111111100101101jm1jm2jm1jX2jX11010100实例分组码(5,2)卷积码(2,1,3)分组码的译码准则以分组码为例讨论信道编码的译码问题。),,,(21Nyyyy长为K的二元信息序列总数为个，而长为N的二元数字序列总数为个。KM2N2分组编码就是从个N长数字序列中选出个码字，分别用于代表M个不同的信息序列。任何一种指定方案就给定了一种编码方案。N2KM2令是信道输入相应的信道输出。),,,(21Nmxxxx分组码的译码准则纠错译码器的作用就是根据接收到的y和编码规则，对发送的是M个可能序列中的哪一个做出判决。设译码器在收到y后将它译为。若，就出现了错误。这种事件出现的概率是误组率。'mx'mmepekp其中是第k位出现错误的概率一个码字发生错误意味着N长二元数字序列中至少有一位错。K11Kbekkpp误比特率是译码后错误比特数与总比特数之比)|(max)|'(yupympNuN跑遍所有码字分组码的译码准则译码准则就是猜测规则，即当信道的输出值为y时，将其译为哪个码字m最合理？最大后验概率准则对特定接收序列y，)'(1)'()(yyymmpmmppNNe译码时要求最小)(yep若有一个以上的m，使取同样的最大值时，我们可从其中任选一个，而不会影响平均错误概率)'(ympN最小错误概率译码准则)|(max)'|(uypmypNuN跑遍所有码字分组码的译码准则最大似然译码准则)()()()(yxyywpmQmpmNN最大后验概率若所有可能消息序列的先验概率相等，则最大后验概率准则可进一步简化为)|(max)'|(uypmypNuN跑遍所有码字最大后验概率译码)(ln)(ln)(ln)'(ln'mNmNpmQpmQxyxy'mm最大似然译码（当消息先验概率相等时）)(ln)(ln'mNmNppxyxy'mm译码准则的对数形式)()()()(yxyywpmQmpmNN后验概率【注2】在消息先验等概条件下，它等价于最大后验概率译码，因而也是最佳的。但若消息先验概率不确知时，采用最大似然译码就不一定保证译码错误概率最小。【注1】它并不要求消息的先验概率。【注3】实际系统中，信源发出的序列传送到信道之前都已进行信源编码，经过有效的信源编码，输出码元的概率分布会均匀化，所以信道的输入近似为等概，因此在工程应用中采用最大似然译码尽管不会使错误概率达到最小，但也接近最小。最大似然译码准则例题设有一个离散信道，其转移概率矩阵为4.03.03.05.03.02.02.03.05.0/xyP并设，，，试分别按最小错误概率准则与最大似然译码准则确定译码规则，并计算相应的译码错误概率？41)(1xp41)(2xp21)(3xp根据最大似然译码准则，译码函数为233211)()()(:abDabDabDB在输入等概分布时的采用最大似然译码准则的平均错误概率：567.0)]4.02.0()3.03.0()3.02.0[(31)/(31*),(xypPaXxye在输入分布为（0.25,0.25,0.5）时的采用最大似然译码准则的平均错误概率：6.0)]4.02.0(21)3.03.0(41)3.02.0(41)/()(*),(xypxpPaXxye根据最小错误概率译码准则，译码函数为2.015.015.0125.0075.005.005.0075.0125.0xyP333231)()()(:abDabDabDC在输入分布为（0.25,0.25,0.5）时的采用最大似然译码准则的平均错误概率：5.0)]5.02.0(21)3.03.0(41)2.05.0(41)/()(*),(xypxpPaXxye可见，在输入不等概分布时的采用最大似然译码准则的平均错误概率不是最小。平均错误概率Pe与译码规则有关，而译码规则又由信道特性来决定。由于信道存在噪声和干扰，使得接收到输出符号后，对发送的是什么符号还存在不确定性。可见，Pe与信道怀疑义度H(X/Y)是有一定关系，也即满足Fano不等式。)1(log)()/(MPPHYXHeeFano不等式证明：定义随机变量ererpzppzpxyxyZ)1(,1)0(10)()()(XYZHYXHYXZH0)(XYZH)(YXH)()()(ZYXHYZHYXZH)()(ZYXHZH)()(ZYXHpHe),1(),0()1()(YZXHpYZXHpZYXHee)1log()1log(0MpMpee)1log()()(MppHYXZHee)()()1log(YXHpHMpee)1log()()(MppHYXHeeFano不等式信道编码信道信道译码),,,(21Luuu),,,(21Nxxx),,,(21Nyyy),,,(21LvvvLULVNXNY)(1)()1log(LLbbVUHLpHMp证明：)()()(112UVUHVUHVUHLLLLLllLVUHUUVUHlLL11)()(1由Fano不等式，可得LlelelLllLLpHMpVUHVUHl11)()1log()()(LlelepHMLp1)()1log(LlelepLp11由引理2两边对l求和，得LleeleelLlelpppppH1111log)1(1log)(eeeeppLpLp11log)1(1log综上)()1log()(eeLLpLHMLpVUH即)(1)()1log(LLeeVUHLpHMpLlelepLp11)(epLHLleleLLpHMLpVUH1)()1log()(eeleelelelelellepppppppppHlog)1(loglog)1(log)(Fano不等式对于给定的信源、信道及编译码规则，即给定了联合空间，则信道的含糊度就可被确定，这个值就给定了译码错误概率的下限。),(,vupUV);()()(VUIUHVUH)()()1log(VUHpHMpee分组码的译码分组码编码：消息空间UL到输出空间YN的一种映射译码规则可以看成是YN到UL的一种映射，即将空间YN按译码准则划分成不相交的判决空间。11,,,MMYYY最大后验概率译码最大似然译码)(ln)(ln)(ln)'(ln:''mNmNmpmQpmQYYxyxy'mm)(ln)(ln:''mNmNmppYYxyxy'mm其中,kiYY,ik11MiNiYY若接收矢量，就将y判为消息m。若，就将y作为删除或检错处理。mYy1MYy令cmY表示mY的补集，当发送消息为m，而接收y落入中就会产生译码错误。1)(McmYYmNemppyxy若消息m的先验概率为Q(m)，则平均译码错误概率为MmemepmQp1)(1McmYY分组码的译码若消息m的先验概率为Q(m)，则可检测译码错误概率为给定m时的不可检测译码错误概率为MmmMNuYpmQp11)()(xy定义：和的汉明距离为),,(21Nyyyy),,(21Nxxxx(,)HdxyNmmmHyxd1),(),(yx其中mmmmmmyxyxyx10),(当所有码字为等概时，信道为BSC，最大似然译码为''[(,)](1)(,)[(,)](1)(,)HHHHNdppdNdppdmmmmyxyxyxyx),(),('mmxyxyHHdd对所有的在对称信道条件下，离散输入序列的最大似然译码等价于最小汉明距离译码。二元对称信道（BSC）的译码011-p101-ppp假设p0.5假设p0.5，可化简为'mm例题设M=2且两个消息等概，令，。通过转移概率为p1/2的BSC信道传送。(1)若采用完备译码，试根据最大后验概率准则划分译码区间并给出相应的译码错误概率。(2)若可以划分三个区间，试确定译码规则并给出译码错误概率和有错不能判决的概率？)0000(1x)1111(2x解：消息等概，最大后验概率准则等效最大似然译码准则。223421)1(3)1(4ppppppppeee1.若采用完备译码，即对任何情况都必须做出判决。判决空间划分Y1={0000，0001，0010，0100，1000，0011，1100，1001}Y2={1111，1110，1101，1011，0111，1010，0101，0110}这时不难算出错误概率为：2.若可以划分三个区间，可将Y划分成：Ｙ１＝{0000，0001，0010，0100，1000}Ｙ２＝{1111，1110，1101，1011，0111｝Ｙ３＝{0011，1100，0110，1001，1010，0101}这时不难算出错误概率为：)1(43421ppppppeee发现有错而不能判决的概率为：22)1(6pppd连续序列的译码此时以转移概率密度描述信道的转移特性。最大后验概率准则为找寻m＇，使'),|()|('mmPP对所有的yxyxmm由贝叶斯公式，等价于'),|()()|()'('mmpmQpmQ对所有的mmxyxy若各信号为等概的，则最大后验概率准则就转化为最大似然准则，即'),|()|('mmpp对所有的mmxyxy高斯白噪声信道的译码准则若加性信道噪声是均值为0，双边功率谱密度为的高斯白噪声，则信号转移概率密度可以表示为})(exp{)1()|(02'2/110'NxyNpkmkNkmxy'})(1exp{})(1exp{12012'0mmxyNx