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

1、 第三章讨论无失真信源编码，给出无失真编码所需最小速率R H(U)/logD. 信道给定，以任意小的错误概率实现可靠通信的最大传输速率为多少？ Shannon于1948年提出并证明了信道编码定理，揭示了在什么条件下可以实现可靠通信，在什么情况下不能实现。 后来很多研究者给出了更严格、更一般化的证明，指出了各种信道和编码条件下所能达到的编码定理的上、下限。 这些理论的进展为合理设计实际通信系统提供了理论依据。什么条件？RC信道信道信源信源信源编码信源编码信道编码信道编码调 制 器调 制 器干 扰 源干 扰 源信宿信宿信源译码信源译码信道译码信道译码解 调 器解 调 器数字通信系统模型数字通信系统

2、模型信道编码信道编码信道编码（纠错编码）的任务是将输入的信息数字序列信道编码（纠错编码）的任务是将输入的信息数字序列变换成另一个数字序列送入有扰离散信道。人为的按一变换成另一个数字序列送入有扰离散信道。人为的按一定规则增加多余度，以便纠正传送过程中可能出现的错定规则增加多余度，以便纠正传送过程中可能出现的错误，以尽可能小的错误概率恢复原来的信源序列。误，以尽可能小的错误概率恢复原来的信源序列。0001101100000101011101001111r = 1111011010 (10)011-p101-ppp 假设假设p0.5不编码，误码率不编码，误码率pb=p编码，编码，pe=3p2+p3-

3、6p4+3p5信道编码器模型信道编码器模型c0000=,cscsnknk每个信息数字持续时间为每个信息数字持续时间为 秒秒ssR/1编码器通常对信息数字进行分段，称为信息段，信息段，设其长度为 . 0ksk00n在 时间段内，编码器计算出 个编码数字送入信道，称为码段码段。 编码数字持续时间为编码数字持续时间为 秒秒,信道编码分类信道编码分类通常纠错码被分为两类，分组码和格状码。通常纠错码被分为两类，分组码和格状码。（N,K)分组码：每分组码：每 K个信息数字为一组，计算出个信息数字为一组，计算出 N 个编个编码数字构成一个分组，一个分组又称为一个码字。码数字构成一个分组，一个分组又称为一个码

4、字。码字之间是不相关的。码字之间是不相关的。格状码：输出的码段不仅依赖于当前的格状码：输出的码段不仅依赖于当前的K0位信息数字，位信息数字，还依赖于前还依赖于前m个信息段的信息数字，即总共与（个信息段的信息数字，即总共与（m+1)K0个信息数字有关。个信息数字有关。 称（称（m+1)K0为编码约束长度。为编码约束长度。称称 或或 为纠错码的编码速率或简称码率为纠错码的编码速率或简称码率 00/nkR NKR/要求纠错能力越强，所需多余度越大，码率就越低。0001101110101100100111011111编码编码jm1jm11 0111111 100101 1 0 1jm1jm2jm1jX

5、2jX11 01 01 00实实 例例分组码分组码(5,2)卷积码卷积码(2,1,3)分组码的译码准则分组码的译码准则以分组码为例讨论信道编码的译码问题。),(21Nyyyy长为K的二元信息序列总数为 个 ，而长为N的二元数字序列总数为 个。KM2N2分组编码就是从 个N长数字序列中选出 个码字，分别用于代表M个不同的信息序列。任何一种指定方案就给定了一种编码方案。 N2KM2令令 是是 信道输入相应的信道输出。信道输入相应的信道输出。),(21Nmxxxx分组码的译码准则分组码的译码准则纠错译码器的作用就是根据接收到的纠错译码器的作用就是根据接收到的y和编码规则，对发和编码规则，对发送的是送

6、的是M个可能序列中的哪一个做出判决。个可能序列中的哪一个做出判决。设译码器在收到设译码器在收到y后将它译为后将它译为 。若。若 ，就出现，就出现了错误。这种事件出现的概率是了错误。这种事件出现的概率是误组率误组率 。mxmm epekp其中其中 是第是第 k 位出现错误的概率位出现错误的概率一个码字发生错误意味着一个码字发生错误意味着N长二元数字序列中至少有一长二元数字序列中至少有一位错。位错。K11Kbekkpp误比特率误比特率是译码后错误比特数与总比特数之比是译码后错误比特数与总比特数之比)|(max)| (yupympNuN跑遍所有码字分组码的译码准则分组码的译码准则译码准则就是猜测规则

7、，即当信道的输出值为译码准则就是猜测规则，即当信道的输出值为y时，时，将其译为哪个码字将其译为哪个码字m最合理？最合理？最大后验概率准则最大后验概率准则对特定接收序列对特定接收序列y，)(1)()(yyymmpmmppNNe译码时要求译码时要求 最小最小)(yep若有一个以上的若有一个以上的m，使，使 取同样的最大值时，取同样的最大值时，我们可从其中任选一个，而不会影响平均错误概率我们可从其中任选一个，而不会影响平均错误概率)(ympN最小错误概率译码准则最小错误概率译码准则)|(max) |(uypmypNuN跑遍所有码字分组码的译码准则分组码的译码准则最大似然译码准则最大似然译码准则)()

8、()()(yxyywpmQmpmNN最大后验概率最大后验概率若所有可能消息序列的先验概率相等若所有可能消息序列的先验概率相等，则最大后验概率准则，则最大后验概率准则可进一步简化为可进一步简化为)|(max) |(uypmypNuN跑遍所有码字最大后验概率译码最大后验概率译码)(ln)(ln)(ln) (lnmNmNpmQpmQxyxy mm 最大似然译码（当消息先验概率相等时）最大似然译码（当消息先验概率相等时）)(ln)(lnmNmNppxyxy mm 译码准则的对数形式译码准则的对数形式)()()()(yxyywpmQmpmNN后验概率后验概率【注注2】在消息先验等概条件下，它等价于最大后

9、验概率在消息先验等概条件下，它等价于最大后验概率 译码，因而也是最佳的。但若消息先验概率不确译码，因而也是最佳的。但若消息先验概率不确 知时，采用最大似然译码就不一定保证译码错误知时，采用最大似然译码就不一定保证译码错误 概率最小。概率最小。【注注1】它并不要求消息的先验概率。它并不要求消息的先验概率。【注注3】实际系统中，信源发出的序列传送到信道之前都实际系统中，信源发出的序列传送到信道之前都 已进行信源编码，经过有效的信源编码，输出码已进行信源编码，经过有效的信源编码，输出码 元的概率分布会均匀化，所以信道的输入近似为元的概率分布会均匀化，所以信道的输入近似为 等概，因此在工程应用中采用最

10、大似然译码尽管等概，因此在工程应用中采用最大似然译码尽管 不会使错误概率达到最小，但也接近最小。不会使错误概率达到最小，但也接近最小。最大似然译码准则最大似然译码准则例例 题题设有一个离散信道，其转移概率矩阵为设有一个离散信道，其转移概率矩阵为 4 . 03 . 03 . 05 . 03 . 02 . 02 . 03 . 05 . 0/xyP并设并设 ， ， ，试分别按最小错，试分别按最小错误概率准则与最大似然译码准则确定译码规则，并计误概率准则与最大似然译码准则确定译码规则，并计算相应的译码错误概率？算相应的译码错误概率？41)(1xp41)(2xp21)(3xp根据根据最大似然译码准则最大

11、似然译码准则，译码函数为，译码函数为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

12、根据根据最小错误概率最小错误概率译码准则译码准则，译码函数为，译码函数为2 . 015. 015. 0125. 0075. 005. 005. 0075. 0125. 0 xyP333231)()()(:abDabDabDC在输入分布为在输入分布为（0.25,0.25,0.5）时的采用时的采用最大似然译最大似然译码准则码准则的平均错误概率：的平均错误概率：5 . 0)5 . 02 . 0 (21) 3 . 03 . 0 (41) 2 . 05 . 0 (41)/()(*),(xypxpPaXxye可见，在输入不等概分布时的采用可见，在输入不等概分布时的采用最大似然译码准则最大似然译码准则的平的

13、平均错误概率不是最小。均错误概率不是最小。平均错误概率平均错误概率Pe与译码规则有关，而译码规则又由信道特与译码规则有关，而译码规则又由信道特性来决定。性来决定。由于信道存在噪声和干扰，使得接收到输出符号后，对发由于信道存在噪声和干扰，使得接收到输出符号后，对发送的是什么符号还存在不确定性。送的是什么符号还存在不确定性。可见，可见，Pe与信道怀疑义度与信道怀疑义度H(X/Y)是有一定关系，也即满是有一定关系，也即满足足Fano不等式。不等式。) 1(log)()/(MPPHYXHeeFano不等式不等式证明：证明： 定义随机变量定义随机变量 ererpzppzpxyxyZ) 1(,1)0(10

14、)()()(XYZHYXHYXZH0)(XYZH)(YXH)()()(ZYXHYZHYXZH)()(ZYXHZH)()(ZYXHpHe), 1(), 0()1 ()(YZXHpYZXHpZYXHee) 1log() 1log(0MpMpee) 1log()()(MppHYXZHee)()() 1log(YXHpHMpee) 1log()()(MppHYXHeeFano不等式不等式)(1)() 1log(LLbbVUHLpHMp证明：证明： )()()(112UVUHVUHVUHLLLLLllLVUHUUVUHlLL11)()(1由由Fano不等式，可得不等式，可得LlelelLllLLpHMp

15、VUHVUHl11)() 1log()()(LlelepHMLp1)() 1log(LlelepLp11由引理由引理2两边对两边对l求和，得求和，得LleeleelLlelpppppH1111log)1 (1log)(eeeeppLpLp11log)1 (1log综上综上)() 1log()(eeLLpLHMLpVUH即即)(1)() 1log(LLeeVUHLpHMpLlelepLp11)(epLHLleleLLpHMLpVUH1)() 1log()(eeleelelelelell epppppppppHlog)1 (loglog)1 (log)(Fano不等式不等式对于给定的信源、信道及编

16、译码规则，即给定了联合对于给定的信源、信道及编译码规则，即给定了联合空间空间 ，则信道的含糊度，则信道的含糊度 就可被确定，这个值就给定了译码错误概率的下限。就可被确定，这个值就给定了译码错误概率的下限。 ),(,vupUV);()()(VUIUHVUH)()() 1log(VUHpHMpee分组码的译码分组码的译码 分组码编码：消息空间分组码编码：消息空间UL到输出空间到输出空间YN的一种映射的一种映射译码规则可以看成是译码规则可以看成是YN到到UL的一种映射，即将空间的一种映射，即将空间YN按译码准则划分成不相交的判决空间按译码准则划分成不相交的判决空间 。11,MMYYY 最大后验概率译

17、码最大后验概率译码 最大似然译码最大似然译码 )(ln)(ln)(ln) (ln:mNmNmpmQpmQYYxyxy mm )(ln)(ln:mNmNmppYYxyxy mm 其中其中 ,kiYY , ik 11MiNiYY若接收矢量若接收矢量 ，就将，就将y判为消息判为消息m。若若 ，就将，就将y作为删除或检错处理。作为删除或检错处理。mYy1MYy令令cmY表示表示mY的补集，当发送消息为的补集，当发送消息为m，而接收，而接收y落入落入中就会产生译码错误。中就会产生译码错误。1)(McmYYmNemppyxy若消息若消息m的先验概率为的先验概率为Q(m)，则平均译码错误概率为，则平均译码错

18、误概率为MmemepmQp1)(1McmYY分组码的译码分组码的译码若消息若消息m的先验概率为的先验概率为Q(m)，则，则可检测可检测译码错误概率为译码错误概率为 给定给定m时的时的不可检测不可检测译码错误概率为译码错误概率为MmmMNuYpmQp11)()(xy定义： 和 的汉明距离 为),(21Nyyyy),(21Nxxxx( ,)Hdx yNmmmHyxd1),(),(yx其中mmmmmmyxyxyx10),(当所有码字为等概时，信道为BSC，最大似然译码为( ,)(1)( ,)( ,)(1)( ,)HHHHNdppdNdppdmmmmy xy xy xy x),(),(mmxyxyHH

19、dd对所有的 在对称信道条件下，离散输入序列的最大似然译码等价于在对称信道条件下，离散输入序列的最大似然译码等价于最小汉明距离译码。最小汉明距离译码。二元对称信道（BSC）的译码011-p101-ppp 假设假设p0.5 假设p0.5，可化简为mm 例例 题题设设M=2且两个消息等概，令且两个消息等概，令 ， 。通过转移概率为通过转移概率为p1/2的的BSC信道传送。信道传送。(1)若采用完备译码，试根据最大后验概率准则划分译若采用完备译码，试根据最大后验概率准则划分译码区间并给出相应的译码错误概率。码区间并给出相应的译码错误概率。(2)若可以划分三个区间，试确定译码规则并给出译码若可以划分三

20、个区间，试确定译码规则并给出译码错误概率和有错不能判决的概率？错误概率和有错不能判决的概率？)0000(1x)1111(2x解：消息等概，最大后验概率准则最大后验概率准则等效等效最大似然译码准则最大似然译码准则。223421)1 (3)1 (4ppppppppeee1.若采用完备译码，即对任何情况都必须做出判决。判决空间判决空间划分划分Y1=0000，0001，0010，0100，1000，0011，1100，1001Y2=1111，1110，1101，1011，0111，1010，0101，0110这时不难算出错误概率为：2.若可以划分三个区间，若可以划分三个区间，可将可将Y划分成：划分成：

21、0000，0001，0010，0100，10001111，1110，1101，1011，01110011，1100，0110，1001，1010，0101这时不难算出错误概率为：)1 (43421ppppppeee发现有错而不能判决的概率为：22)1 (6pppd连续序列的译码此时以转移概率密度 描述信道的转移特性。最大后验概率准则为找寻m，使),|()|(mmPP对所有的yxyxmm由贝叶斯公式，等价于),|()()|() (mmpmQpmQ对所有的mmxyxy若各信号为等概的，则最大后验概率准则就转化为最大似然准则，即),|()|(mmpp对所有的mmxyxy高斯白噪声信道的译码准则高斯白噪声信道的译码准则若加性信道噪声是均值为0，双边功率谱密度为 的高斯白噪声，则信号转移概率密度可以表示为)(exp)1()|(022/110NxyNpkmkNkmxy)(