北京邮电大学通信原理第九章信道编码

1、第九章 信道编码彭涛P 2主要内容n信道编码的基本概念和分类n两种主要的信道编码n分组码n卷积码n其他类型编码和编码界限n（工程应用）P 3章节n信道编码的基本概念n线形分组码n循环码nBCH码n卷积码n其他编码类型n纠正突发错误码、交织码、级联码、Turbo码、高效率信道编码TCMP 49.1 信道编码的基本概念n为什么需要信道编码？n在数字信号的传输中，实际信道不是理想的，存在噪声和干扰，会导致接收端的误判，这样就产生了差错。n可采取的办法：n合理设计基带信号n选择调制、解调方式n采用均衡技术n增大发送功率n仍然达不到要求，就需要信道编码P 59.1 信道编码的基本概念n信道分类（按差错出

2、现类型）n独立随机差错信道n差错随机出现，且相互独立（无记忆性）n原因：由高斯白噪引起（信道本身的传输特性比较理想）n太空信道、卫星信道、同轴电缆、光缆信道、视距微波信道P 69.1 信道编码的基本概念n信道分类（按差错出现类型）n突发差错信道n差错成串出现（记忆性）n原因：信道传输特性不理想（衰落和码间干扰），有大的脉冲干扰n短波信道、移动通信信道、散射信道、明线和电缆信道n混合信道P 79.1 信道编码的基本概念n信道编码的构造n在发送端，在待发送的信息序列中加入一些多余的码元（监督码元），这些监督码元和信息码元之间以某种确定的规则相互关联，即满足一定的约束关系。n在接收端，按既定的规则检

3、验信息码元与监督码元之间的约束关系。约束关系被破坏就意味着传输中有差错（检错）；借助于约束关系甚至还可以纠正错误（纠错）。P 89.1 信道编码的基本概念n信道编码分类（按纠正错误类型分类）n纠独立随机差错码：分组码和卷积码中的大部分种类n纠突发差错码：分组码和卷积码中的几类、交织码n纠混合差错码：级联码P 99.1 信道编码的基本概念n信道编码分类（按约束关系分类）n线性码：信息码元与监督码元之间的约束关系是线性关系，即满足一组线性方程式n非线性码：约束关系不是线性关系。（缺少理论和应用上的研究）P 109.1 信道编码的基本概念n信道编码分类（按编码方式分类）n分组码：将信息序列分成独立的

4、若干组进行编码。编码后，一组中的码元只与本组的原始信息码元有关，而与其他组的信息码元无关。n分组码用符号（n，k）表示。k是一组中信息码元的数目，n是码元总数目，则监督码元有n-k位n编码效率k/n，编码冗余度1-k/nn非分组码：卷积码是其中最主要的一类。P 119.1 信道编码的基本概念n信道编码分类（按编码后是否包含原始信息码元分类）n系统码：编码后的信息序列中包含原始信息码元（位置可能变化）n非系统码：编码后的信息序列中不包含原始信息码元P 129.1 信道编码的基本概念n在数字通信系统中，利用信道编码可提高系统可靠性，控制差错。其控制差错的方式主要分为三种。n前向纠错（FEC）：发端

5、发送有一定纠错能力的码，若传输中产生的差错的数目在码的纠错能力内，收端可以纠正。n优点：单向通信（不需要反馈信道），实时性好。n缺点：码的构造复杂，译码电路复杂。P 139.1 信道编码的基本概念n反馈重传（ARQ）：发端发送有一定检错能力的码，收端译码时如发现有错，则通知发端重发，直到正确接收。也称为检错重传或自动请求重复。n优点：检错比较简单，码的效率和结构简单，译码电路简单。n缺点：需要反馈信道，不能单向通信；实时性差。n三种类型：等待式ARQ、退N步ARQ，选择重传ARQ。P 149.1 信道编码的基本概念n混合差错控制（HEC）：是FEC和ARQ的结合。n需要反馈信道。实时性和译码复

6、杂性是FEC和ARQ两种方式的折衷。P 159.1 信道编码的基本概念n检错和纠错的基本原理n例1：一个由3位二进制数字构成的码组，共有8种组合。若用其表示不同的天气，如：000（晴）、001（云）、010（阴）、011（雨）、100（雪）、101（霜）、110（雾）、111（雹）。n任一码组在传输中产生传输中产生一个或多个错误，都会变成另一个信息码组。无法检错和纠错。n原因：码组中只有信息码元，没有监督码元P 169.1 信道编码的基本概念n检错和纠错的基本原理n例2：利用2位二进制数字的4种组合表示4种天气，再加1位奇偶校验位。n可以检测出传输中的1个或3个错误（无法检测2个错误，无法纠错

7、）n原因：监督码元的引入使得8个组合中只有4个是许用组合，其余4个是禁用组合P 179.1 信道编码的基本概念n码重，码距，最小码距n码重：在分组码中，把一个码组/字（A）中所含1的数目定义为码组/字重量，简称码重，记为W(A)n码距：把两码组A、B中对应位置上码元不同的数目定义为两码组的距离，简称码距或汉明距，记为d(A,B)n最小码距：把某种编码中各个码组间距离的最小值定义为最小码距dminP 189.1 信道编码的基本概念n码重，码距，最小码距n码距的几何解释（图）P 199.1 信道编码的基本概念n一种编码的最小码距直接关系到这种编码的检错和纠错能力（图9.1.2）n为检测e个误码，要

8、求最小码距n为纠正t个误码，要求最小码距n为纠正t个误码，同时检测e（et），要求最小码距min1demin21dtmin1dte P 209.1 信道编码的基本概念n两种简单的信道编码n(n,1)重复码（以(3,1) 重复码为例）n许用码组(000),(111)ndmin=nn可纠1位错或检2位错n用来纠错时，出现错误的概率为2233233132ePC ppC pppP 219.1 信道编码的基本概念n两种简单的信道编码n(n,n-1)奇偶校验码（以(4,3)偶校验为例）n最后一位为校验位（例9.1.2）n偶校验：码字中1的个数为偶数；奇校验：码字中1的个数为奇数n最小码距为2n只能用于检错

9、：只能检奇数个错误，无法检偶数个错误22244441ePC ppC pP 229.1 信道编码的基本概念n两种简单的信道编码n(n,1)重复码n编码效率1/n，dmin=nn随着n的增大，检错、纠错能力越来越强，但编码效率越来越低n(n,n-1)奇偶校验码n编码效率1-1/n，dmin=2n随着n的增大，编码效率越来越高，但只能检奇数个错误P 239.1 信道编码的基本概念n有限域n定义：一个有限个元素的集合，进行规定的代数四则运算后，结果仍是属于该集合的元素（自封闭性）。nGF(2)：集合0,1对规定的模二和“”及点乘“”运算是自封闭的，所以是一个有限域，称之为二元域P 249.1 信道编码

10、的基本概念n有限域nGF(2k)：以0,1中的元素构成的所有长度为k的序列所组成的集合，对规定的模二和“”及点乘“”运算也是自封闭的。 011011001111011,., , ,., , ,.,.,20,1kkkkkXXx xxxxxxxxxxxXxxxGFP 259.2 线性分组码n定义n分组：将k个信息位作为一组进行编码，变换成长度为n（nk）的二进制码组n线性：信息码元与监督码元的约束关系是一组线性代数方程。n记为（n，k）码，编码效率=k/n，冗余度为1-=1-k/nP 269.2 线性分组码n数学定义n分组：n线性：n线性编码f就是从矢量空间GF(2k)到另一个矢量空间GF(2n)

11、的一组线性变换。它可以用线性代数中的有限维矩阵来表示。:knf UCnk ,20,1, kfuuf uf uGFu uU P 279.2 线性分组码n线性分组码的码距n两个码组的距离必等于另一个码组的码重n编码的最小码距等于非零码的最小重量（决定该编码的纠错能力）112212121212,Cf UCf Ud C CW CCWf Uf UWf UUP 289.2 线性分组码n例：(7,3)线性分组码320622210511214001064365426515409 1009200cuucucuuucucuucucuucccccccccccccP 299.2 线性分组码n例n将(9-1)表示成矩阵

12、形式210100111001001110011101Cu u uU GUI QP 309.2 线性分组码n(n,k)线性分组码可以由k个输入信息位通过一线性变换矩阵G（k行n列）产生，G称为该线性分组码的生成矩阵n若G能分解成两个子矩阵，其中I为k维单位方阵，则称该线性分组码c为系统码或组织码，G为该系统码的典型生成矩阵GI QP 319.2 线性分组码n例n将(9-2)表示成矩阵形式65010110000111010001100010001100010,TTTTcccH COP ICO P 329.2 线性分组码n(n,k)线性分组码的监督关系（n-k个线性监督方程）用H矩阵（n-k行n列）

13、表示，H称为该线性分组码的监督矩阵n若H可以分解成两个子矩阵，其中I是(n-k)维单位方阵，则称该线性分组码c为系统码或组织码，H为该线性分组码的典型监督矩阵HP IP 339.2 线性分组码n生成矩阵G与监督矩阵H之间的关系n生成矩阵G与监督矩阵H可以互相转换。知道了其中一个，另一个就容易求得TTTTTTTTH COC HOU G HOG HOCU GPI QPQOPQIP 349.2 线性分组码n对偶码n定义：若把(n,k)码的监督矩阵H作为(n,n-k)码的生成矩阵G，把(n,k)码的生成矩阵G作为(n,n-k)码的监督矩阵H，则这样的(n,k)码和(n,n-k)码互为对偶码P 359.

14、2 线性分组码n系统码与非系统码n系统码的广义定义：只要编码前的信息码元以不变的形式在码组中的k位出现，都可称为系统码。否则，就是非系统码n对线性分组码而言，在检纠错方面，系统码和非系统码是完全一样的。P 369.2 线性分组码n系统码与非系统码n任何一个线性分组(n,k)码都可等价于一个系统码n非系统码的生成矩阵可通过初等行变换和列交换得到等价的系统码的生成矩阵n初等行变换：矩阵的两行交换位置；将矩阵的一行加到另一行n列交换：矩阵的两列交换位置n思考：为什么？P 379.2 线性分组码n例14, 13334, 233, 244010101010101010111001011100111100

15、100100111101010101010101010101011100100100110011110lllllllllllll P 389.2 线性分组码n例344131, 234210101010111001001001100011011000110010011100100110001101llllll llll P 399.2 线性分组码n线性分组码的编码实现n由生成矩阵，非常容易得到线性分组码的电路实现方式P 409.2 线性分组码n伴随子（校正子）TTTTTTTYCESY HCEHC HE HC HOSY HE HP 419.2 线性分组码n伴随子（校正子）n校正子只与传输差错E有关

16、，可见错误图样和校正子之间有确定的关系n码组有n位，可产生2n个错误图样；而校正子S是(n-k)维矢量，只有2n-k种组合的校正式；这样对每一种校正式，都有2k个错误图样与之对应P 429.2 线性分组码n二进制对称信道（BSC）下的译码n在输入信息0、1等概的情况下，二进制对称信道下的最优译码准则等效为最小汉明距离准则n在译码时，得到伴随式S后，应该选择与S对应的2k个可能的错误图样中重量最小的进行译码n若收到的码字为Y，得到的伴随式为S，若S对应的码重最小的错误图样是E，那么译码输出就是C=YEP 439.2 线性分组码n利用监督矩阵进行译码n例9.2.5TTSH Y65241302101

17、10110011100100111001yysysysyyyP 449.2 线性分组码n利用监督矩阵进行译码n若接收码字中只有一个码元出现差错，比如yi出错，则校正子S等于监督矩阵第i列。n比较(7,4)码的监督矩阵和码重最小的E110110011100100111001P 459.2 线性分组码n汉明码n汉明码是一种能纠正一位错码的线性分组码n主要参数：n码长n=2m-1n信息位k=2m-1-mn监督位n-k=mn最小码距dmin=3，纠错能力t=1n码效率R=k/n=1-m/n=1-m/(2m-1)n当n很大时，R趋近于1，所以汉明码是一类高效率的纠错码。P 469.2 线性分组码n汉明码

18、n当m=3时，n=7，k=4。之前的(7,4)码就是汉明码。n特点：监督矩阵中的n=2m-1列正好是m位码元的2m种组合中除全0组合外的其它组合，且每种组合出现一次。每种组合对应该列对应的码元出现传输错误时的校正子。P 479.2 线性分组码n汉明码的译码电路n利用最小码重错误图样进行译码的电路实现（图9.2.4）n利用校正子与错码位置的对应关系，也可以使用地址译码器来帮助实现译码P 489.3 循环码n循环码n是线性分组码的一个重要子类nBCH码是其主要的一大类n汉明码、R-M码、Golay码、RS码等可变换或纳入循环码内，Goppa码的一个子类也属于循环码n用反馈线性移位寄存器可以容易的实

19、现其编码和得到伴随式n由于数学上的特性，译码方法简单P 499.3 循环码n循环码的循环移位特性n循环码具有线性分组码的一般特性n循环移位特性：任一许用码组经过任意位的循环移位后得到的码组仍是一个许用码组16101 100001 10001101 100001 10001LeftShiftRightShift P 509.3 循环码n定义：n循环移位推广： 12102301,(,),nnnnnn kcccccc cn kCcCcC设 是某线性分组码的码字集合，如果对任何，它的循环移位也属于 ，则称该码为循环码 12012,in in innn iiccc ccc cc的 次循环移位也是该循环码

20、的一个码字P 519.3 循环码n举例：（7,3）码101110001011100010111G00000000000010010111010010111010010111000110111001110111001011111001011011001011P 529.3 循环码n循环码的多项式描述n码字的多项式描述，一个n元码字可以用一次数不超过n-1的多项式唯一的表示n其中，我们不关心x的具体取值，其次数只表示相应码元的位置n称这样的c(x)为c的码字多项式 121 01211210nnnnnncccc cc xcxcxc xcP 539.3 循环码n多项式的加法n注意多项式加法与向量加法的

21、对应关系 210210221100222102102221100,uu u ugg g gugug ug ugu xu xu xug xg xg xgu xg xugxugxug，P 549.3 循环码n多项式的乘法n注意多项式乘法与矩阵乘法的对应关系 222102104322221122011021001002102102102102102102102102221122011020000,00,000000,u xu xu xug xg xg xgu x g xu g xu gu gxu gu gu gxu gu gxu gggguuuu u uggggg guuuggguuuu gu gu

22、 gu gu gu g，100100,u gu gu gP 559.3 循环码n模运算n整数的模运算n码字多项式的模运算（其中p(x)次数为n，r(x)次数小于n）,modmpQpnnnmpn ,modc xr xQ xp xp xc xr xp xP 569.3 循环码n模运算n码字多项式的模运算举例532233532311111,mod1xxxxxxxxxx P 579.3 循环码n循环移位特性的多项式描述n码字c及其码多项式c(x)n其左移i位后的码字ci和码多项式ci(x) 121 01211210nnnnnncccc cc xcxcxc xc 120112101201in in in

23、n iinniin in inn icccc cccxcxcxc xcxcx P 589.3 循环码n循环移位特性的多项式描述nc的码字多项式c(x)乘以xi 11211201012112010101110112112011in innninn in in ininninn in in iiinn inn ininn inniin in inx c xcxcxcxcxc xxcxcxcxcxc xcxcxcxcxxcxcxcxcxc xcx 01,mod1n iniiincxg xxcxx c xcxxP 599.3 循环码n循环移位特性的多项式描述n上面的表达式说明码字循环移位i位后的多项式

24、ci(x)在模xn+1的运算下与xic(x)是相同的n在循环码的研究中可以用xic(x)代替ci(x) ,mod1iinx c xcxxP 609.3 循环码n循环码的生成矩阵n循环码中除全0码组外必然有一个且仅有一个前k-1位均为0的码组，且其最后一位为1n存在性：循环码属于线性分组码，必可以变换为一个系统码；系统码的信息码元可以有k-1位0n不存在前k位均为0的非全0码组：k位输入信息码元为0则编码后必定是全0码组n唯一性：如果有两个码组满足此条件，由线性分组码对运算的封闭性，两个码组相加前k位为0n此码组最后一位为1：若为0则移位后会成为前k位为0的非全0码组P 619.3 循环码n循环

25、码的生成矩阵n(n,k)线性分组码的生成矩阵（k行n列）的每一行均为一个许用码组，且线性无关n利用循环码的唯一的前k-1位为0的非全0码组g(x)，容易得到生成多项式：将g(x)和其依次循环移位直到k-1次的各个码组g(1)(x)，g(2)(x)，g(k-1)(x)，分别作为生成矩阵的k行（容易知道它们互不相关），即得到生成矩阵ng(x)（次数为n-k）称为循环码的生成多项式P 629.3 循环码n循环码的生成矩阵n举例：若已知某(7,3)循环码的一个码字为(0111001)，则其循环移位4次后的码字(0010111)也是一许用码字，易得生成矩阵101110001011100010111GP

26、639.3 循环码n循环码的生成矩阵n(n,k)循环码的每个码字的码多项式都是g(x)的倍数n凡次数小于n的多项式，若能被g(x)除尽，则必是该循环码的码多项式 1212012120kkkkkkkkxg xxg xc xuuug xg xuxuxuP 649.3 循环码n循环码的生成矩阵n用上面的办法所产生的生成矩阵所表示的循环码不是系统循环码n系统循环码的生成矩阵的形式为n第i行也为一许用码字，多项式表示为kGIQ ,modn iiiin iiin iicxxr xg x axr xxg x axr xxg xP 659.3 循环码n循环码的生成矩阵n系统循环码的生成矩阵的多项式表示 112

27、2nnn kkxr xxrxG xxrxP 669.3 循环码n循环码的生成矩阵n系统循环码的生成矩阵举例：(7,3)循环码的生成多项式g(x)=x4+x2+x+1，g=(0010111) 64231542322442236353242mod11mod1mod1111001011,010111010010111r xxxxxxxrxxxxxxxxrxxxxxxxxxxG xxxxxGxxxP 679.3 循环码n循环码的生成矩阵n非系统循环码变换为系统循环码也可以用矩阵变换的办法，但只能用简单行变换，不能用列的交换3111011100100101101011100101110001011100

28、10111lll P 689.3 循环码n循环码的生成多项式ng(x)为n-k次多项式，则xkg(x)为n次多项式nc(x)为许用码组，所以必是g(x)的倍数n生成多项式g(x)必是xn+1的因式，为寻找生成多项式指出了方法 111knnx g xc xxx 111knnnkkx g xxc xxg x a xxx g xg x a xg xxa x P 699.3 循环码n循环码的生成多项式n举例：寻找(7,3)循环码的生成多项式g(x)，其次数为n-k=4 732332421343221111111111xxxxxxgxxxxxxxgxxxxxxx P 709.3 循环码n循环码的生成多项

29、式n对任意n，有：n若取x+1为生成多项式，构成的循环码是简单的偶监督码(n,n-1)。最小码距dmin=2n若用xn-1+ xn-2+x+1为生成多项式，构成的(n,1)循环码信息位个数为1，校验码个数为n-1。容易知道实际就是重复码。12111nnnxxxxx P 719.3 循环码n循环码的生成多项式n(7,k)循环码P 729.3 循环码n循环码的监督多项式n循环码的生成多项式g(x)是xn+1的因式nh(x)称为此循环码的监督多项式n举例，(7,3)循环码 1ng x h xx 3213132321111111gxxxxh xxxgxxxxh xxxP 739.3 循环码n循环码的监

30、督矩阵 1010000 11 0011011210110011000101,2,10n kn kkkniin kin knnn kkn kkiin kin kn kkg xgxg xgh xh xh xhg x h xxg hg hg hg hg hghg hg hghghg hg hghing hghP 749.3 循环码n循环码的监督矩阵n由上面的式子，可知循环码的监督矩阵可表示为n容易验证，由g(x)移位得到的生成矩阵与上面的监督矩阵相乘得到0阵010101000000kkkhhhhhhHhhh 0TGHP 759.3 循环码n循环码的监督矩阵n举例：(7,3)循环码，g(x)=x4+x

31、2+x+1，h(x)=x3+x+11011100010111000101111101000011010000110100001101GHP 769.3 循环码n循环码的监督矩阵n系统循环码的监督矩阵n例:(7,3)系统循环码kTn kGIQHQI1001011010111000101111101000011010011100101010001GHP 779.3 循环码n系统循环码的编码器n系统循环码的编码方式是将信息码多项式升n-k次幂后除以生成多项式，然后将所得余式置于升幂后的信息多项式之后 n kn kn ka x g xxu xa x g xr xxu xr xa xg xg xc xx

32、u xr xP 789.3 循环码n系统循环码的编码器n举例：(7,4)系统循环码的生成多项式为g(x)=x3+x+1，输入信息多项式为u(x)= x3+1 7 46363233363211n kn kn kxu xxu xxxxu xxxxxxxg xxxxxc xxu xr xxxxxP 799.3 循环码n系统循环码的编码器n多项式除法电路可以用带反馈的线性移位寄存器来实现（图9.3.2）n与采用手算进行多项式长除运算的过程类似n用除法电路进行系统码的编码的过程（表9.3.3）（板书）P 809.3 循环码n系统循环码的译码器n校正子 modmodmodmodn kTTn kn kr x

33、xu xg xcu ruGu I QruQsyHu rP Iu Qrs xxuxg xrxxuxrxg xs xy xg xP 819.3 循环码n系统循环码的译码器n校正子与错误图样的关系 modmodTTsyHeHs xy xg xe xg xP 829.3 循环码n系统循环码的译码器n校正子的一个重要性质：n一码组移位i次后的码组的校正子等于原码组的校正子在除法电路中移位i次的结果 ,mod,mod,mod0,mod,modiiiiiiiisxx y xg xs xy xg xx s xx y xg xx s xsxg xsxx s xg xP 839.3 循环码n系统循环码的译码器n举

34、例： (7,4)系统循环码的生成多项式为g(x)=x3+x+1 4262222432modmod1mod1y xxs xy xg xxxyxxsxyxg xxxxg xxP 849.3 循环码n系统循环码的译码器n上面的性质使得译码器需要识别的错误图样的数目大大减小（如果某(n,k)码可纠正m个错误，则识别错误图样数目由 减为 ）；(7,4)码的识别数由7减为1。mnC/mnCnP 859.3 循环码n系统循环码的译码器n译码器电路（图9.3.3）n译码过程（板书）n一次译码需要2n个节拍才能完成。所以真正的译码电路需要两个除法电路（图）P 869.3 循环码n码字的扩展与收缩：可增加信息位、

35、校验位来增加码字长度，减少信息位、校验位来减少码字长度（图9.3.4）P 879.3 循环码nCRC（Cyclic Redundancy Check）:循环冗余校验n检错能力很强n实现简单nCRC校验已成为国际标准，在数据通信和移动通信中广为使用P 889.3 循环码nCRC的检错原理nc(x)能被生成多项式g(x)整除，如接收到的y(x)不能被g(x)整除，意味着传输出错n编码电路与循环码一样(图9.3.5)n译码电路检查对g(x)的整除性(图9.3.6)P 899.3 循环码nCRC的检错原理P 909.3 循环码nCRC的检错原理P 919.3 循环码n注意：CRC并不一定是循环码n因为

36、g(x)可以对任意信息码长k的分组进行编码，作为生成多项式P 929.3 循环码nCRC的检错能力n错误图样总个数:2k+rn无法检出的错误图样个数:2k-1n无法检出的错误图样的比例:(2k-1)/ 2k+r =1/2rP 939.4 BCH码nBCH码n由Bose，Chaudhuri和Hocquenghem发现n属于循环码n纠错能力强，能纠正多个随机错误n构造方便n（我们不从理论上研究BCH码的性质，只学习如何使用BCH码）P 949.4 BCH码nBCH码的构造n其生成多项式为nt为纠错个数，mi(x)为最小多项式，LCM表示取最小公倍式n其能纠正t个随机差错，最小码距 1321,.,t

37、g xLCM mxmxmxmin21dtP 959.4 BCH码n本原BCH码n码长n非本原BCH码n码长n为2m-1的因子21mn P 969.4 BCH码n最小多项式表（表）n阶数m表示码长n=2m-1中的mn十进制数字表示mi(x)中的in最小多项式用8进制数表示，如n最小多项式后的字母意义：ABCD表示非本原多项式，EFGH表示本原多项式 8252451001011m xxxP 979.4 BCH码nBCH码构造举例n例9.4.1：码长15的BCH码，能纠正3个错误 41824323822582135443221085422115,4,3230100111370111111071111

38、,1111mnmtmxxxmxxxxxmxxxg xLCM mxmxmxxxxxxxxxxxxxxx P 989.4 BCH码n表9.4.1（本原BCH码）n表9.4.2（非本原BCH码）n（学会根据需要查找）P 999.4 BCH码nGolay码n(23,12)非本原BCH码，生成多项式为n码距为7，能纠正3个随机错误n是GF(2)上纠多个随机差错的唯一一个完备码，监督码元得到了最充分的利用 8211976553431010111000111g xxxxxxx012323 122323232320482CCCCP 1009.4 BCH码nRS（Reed-Solomon，里德-所罗门）码n一种

39、非二进制BCH码，编码的单位是符号；一个符号由m个二进制码元组成，即为2m进制n纠正t个符号错误的RS码的参数：n码长n=2m-1个符号（即m(2m-1)比特）n信息位数k=n-2t个符号（即m(n-2t)比特）n监督位数2t个符号（即2mt比特）n最小码距d=2t+1个符号（即m(2t+1)比特）n纠正突发错误的能力强P 1019.5 卷积码n简单介绍n不是分组码n1955年，由P. Elias提出n没有进行理论研究的好的数学工具n纠错性能和码字构成之间的直接关系没找到n性能好的码的构成不能从理论上推导得到，只能用计算机搜索P 1029.5 卷积码n编码器一般结构P 1039.5 卷积码n编

40、码器一般结构P 1049.5 卷积码n编码器一般结构n有k个输入信息端，n个输出端（kK-1后，树图中的2k(K-1)个状态开始重复出现n格图是从l=K开始，合并重复出现的状态n格图特点：保持了时序的清晰性，表达也比较简洁n格图是研究维特比译码算法的重要工具P 1149.5 卷积码n格图举例：(2,1,3)卷积码P 1159.5 卷积码n离散卷积法：以(2,1,4)卷积码为例说明n输出的各个分支所构成的系统都是线性时不变系统；而线性时不变系统可以用冲激相应来表示（长为K），且输出是输入与冲激相应的卷积01211112222011011112211 1 122220 120121212120 0

41、1 122,*,*,KKuu u ugg gggg ggcu g cu gcc c ccc c ccc c c c c cP 1169.5 卷积码n离散卷积法n举例： (2,1,4)卷积码P 1179.5 卷积码n离散卷积法n举例： (2,1,4)卷积码（图9.5.3）n相应的冲激相应也叫生成序列121122101111011 ,1111*10000001*110111011101000101010011uggcu gcu gcP 1189.5 卷积码n码多项式法n将输入序列、生成序列和输出序列分别用码多项式表示，容易验证，输出码多项式等于输入码多项式和生成序列码多项式的乘积 ,uu xgg

42、xcc xc xu x g xP 1199.5 卷积码n码多项式法n举例： (2,1,4)卷积码（图9.5.3） 23411232223117122345721011111011111111110000001111011101uu xxxxggxxxggxxxxcxu x gxxccxu x gxxxxxxc P 1209.5 卷积码n生成矩阵法：以(2,1,4)卷积码为例推导110111111101111111011111110111111101 11 111101000101010011Gcu GP 1219.5 卷积码n生成矩阵法：以(2,1,4)卷积码为例推导1212121200112

43、23312121212001122331212121200112233012301230123g gg gg gg gg gg gg gg gGg gg gg gg gGGGGGGGGGGGG P 1229.5 卷积码n生成矩阵法：推广到一般(n,k,K)卷积码n(n,k,K)卷积码的生成序列一般表示式为n其中gli,j表示每组k个输入比特中第i个比特经延迟l后的输出与每组n个输出比特中第j个比特的模2和器件的输入端的连接关系；为1表示有连接，为0表示没有连接,0111,2, ;1,2, ;0,1,1i ji ji ji ji jlKgggggik jn lKP 1239.5 卷积码n生成矩阵

44、法：推广到一般(n,k,K)卷积码n生成矩阵为0110110111,11,21,2,12,22,1,2,KKKnlllnllllkkk nlllGGGGGGGGGGggggggGgggP 1249.5 卷积码n生成矩阵法：推广到一般(n,k,K)卷积码n举例：(3,2,2)卷积码（图9.5.4）P 1259.5 卷积码n生成矩阵法：推广到一般(n,k,K)卷积码n举例：(3,2,2)卷积码（图9.5.4）1,11,21,32,12,22,30101010111 ,01 ,1101 ,10 ,10101111,011100110110110000001111ggggggGGuGGcu GuGGG

45、G P 1269.5 卷积码n卷积码的译码方法n代数译码：根据卷积码的本身编码结构进行译码，译码时不考虑信道的统计特性 n概率译码：这种译码在计算时要考虑信道的统计特性n门限译码n序贯译码n维特比译码（最佳译码，最大似然译码）P 1279.5 卷积码n最大后验概率（MAP）译码 minmin:min:min 1:max:maxeyyeyPp y P e yp y P cc yPp y P cc yccP cc ycP cc yccP cc ycP c yP 1289.5 卷积码n最大似然（ML）译码n若发送码字等概出现，MAP等价于ML P c P y cP c yP y:max:maxccP

46、 c ycP y cP 1299.5 卷积码n最大似然（ML）译码n对于无记忆信道n称上式中的取对数部分为对数似然函数，简称似然函数（或度量值） 0110110111011010110,:max,:max,:maxlognnnnnlllnnlllcc ccPyyyc ccc ccP y cc ccP y cP 1309.5 卷积码n编码信道n硬输出：解调器将信号硬判决为0或1n软输出：输出模拟量或经多电平量化的值P 1319.5 卷积码n举例（2PSK）nV1(t)=s(t)+n(t)是软输出，或对其进行Q=2m2的多电平量化也是软输出nV2(t) 是硬输出，对V1(t)进行了硬判决 V2(n

47、) BPF LPF 抽样 cosct V1(n) 判决 P 1329.5 卷积码n维特比译码n硬判决译码：对应于解调器的硬输出n软判决译码：对应于解调器的软输出P 1339.5 卷积码n维特比硬判决译码n对于二进制对称信道（BSC）P 1349.5 卷积码n维特比硬判决译码n似然函数n译码准则（因为P5m时，性能已经非常接近最大似然译码P 1489.5 卷积码n维特比截短译码（优点）n时延降低：由n降为Ln存储量减小：译码序列存储量由n2km减为L2kmP 1499.5 卷积码n维特比软判决译码（直接输出：2PSK）n直接以V1(l)作为软输出yln其中cl =0,1 V2(n) BPF LP

48、F 抽样 cosct V1(n) 判决 2002211()exp44lblllbbyEcf y cN EN EP 1509.5 卷积码n维特比软判决译码（直接输出：2PSK）n求最大似然函数等价于求最小欧氏距离n若去掉公有项，则10110120110:max,:maxlog,:min221nnlllnnlbllccP y cc ccP y cc ccyEc10110,:max21nnlllcc ccycP 1519.5 卷积码n维特比软判决译码（多电平量化）n以V1(l)经多电平量化后的值作为软输出yln2PSK：将 作为度量值，或将其加上一个常数使之恒为非负21llyc P 1529.5 卷

49、积码n维特比软判决译码（多电平量化举例）nc=(111,000,001,001,111,001,111,110)ny=(101,100,001,011,110,110,111,110)P 1539.5 卷积码n维特比软判决译码（总结）n解调直接输出可以看作是多电平量化的一种n译码过程与硬判决译码一样，唯一的区别是度量值不同n也具有汇聚特性，可以使用维特比截短译码n性能优于硬判决译码，增益有1.52.0dBn3比特量化即基本足够P 1549.5 卷积码n卷积码的距离特性n码的距离特性与纠错能力有密切关系n分组码：最小距离dminn卷积码n最小距离dmin ：长度为nK的编码后序列之间的最小汉明距离（用于门限译码，不讨论）n自由距离dfree：任意长度的编码后序列的最小汉明距离（用于维特比译码）n分组码与卷积码的区别：卷积码没有固定的长度的码字P 1559.5 卷积码n卷积码的距离特性n由卷积码的编码器结构，可知卷积码具有线性性质n这样，卷积码的码序列之间的自由距离就等于非全零码序列的最小码重112212121212,Cf UCf Ud C CW CCWf Uf UWf UUP 1569.5 卷积码n卷积码的距离特性（自由距离dfree）n求自由距离dfree可以转化为求任意长非全零码序列的最小码重