信道编码1015上课

1、信道编码2021-9-182第第6章章 信道编码信道编码p目的目的：n了解信道编码的了解信道编码的作用与意义n掌握掌握几种典型的信道编码、译码方法n对信道编码的对信道编码的研究方法和成果有基本认识，为有基本认识，为进一步研究打下基础进一步研究打下基础p特点：基本概念、物理意义、基本方法为特点：基本概念、物理意义、基本方法为主主2021-9-183主要内容p基本概念和方法基本概念和方法p线性分组码线性分组码p循环码（实验）循环码（实验）pBCHBCHp卷积码卷积码2021-9-1846.1 用于可靠传输和存储数据的编码p信道编码的引入信道编码的引入p信道编码的基本思想信道编码的基本思想p编码系统

2、模型编码系统模型2021-9-1856.1 用于可靠传输和存储数据的编码 信道编码的引入移动通信移动通信通信网小张小李2021-9-1866.1 用于可靠传输和存储数据的编码 信道编码的引入p通信的目的在于通信的目的在于传输信息传输信息p通信系统主要质量指标是通信的通信系统主要质量指标是通信的有效性和可靠性有效性和可靠性p在实际信道上传输信号时，由于信道传输特性不在实际信道上传输信号时，由于信道传输特性不理想及噪声的影响，接收端收到的信号不可避免理想及噪声的影响，接收端收到的信号不可避免地会发生错误地会发生错误发送端发送端接收端接收端干扰干扰2021-9-1876.1 用于可靠传输和存储数据的

3、编码 信道编码的引入p随着差错控制编码理论的完善和数字电路技术的随着差错控制编码理论的完善和数字电路技术的发展，信道编码不仅应用于各种通信系统中，在发展，信道编码不仅应用于各种通信系统中，在计算机存储、运算系统以及超大规模集成电路的计算机存储、运算系统以及超大规模集成电路的设计中也得到日益广泛的应用。设计中也得到日益广泛的应用。2021-9-1886.1 用于可靠传输和存储数据的编码 信道编码的作用 信道编码是在数据传输信道编码是在数据传输/ /存储中所采用存储中所采用的的降低系统差错率，提高系统可靠性降低系统差错率，提高系统可靠性的一种数字处理技术。的一种数字处理技术。2021-9-1896

4、.1 用于可靠传输和存储数据的编码 信道编码的基本思想p通过对信息码元序列作某种变换通过对信息码元序列作某种变换, ,即即增加增加一一定数量的多余码元，使原来彼此相互独立、定数量的多余码元，使原来彼此相互独立、没有关联的信息码元没有关联的信息码元, ,经过变换后经过变换后, ,产生某产生某种规律性或相关性种规律性或相关性, ,从而在接收端可根据这从而在接收端可根据这种规律性来检查、纠正传输序列中的差错。种规律性来检查、纠正传输序列中的差错。p编码的实质编码的实质利用冗余降低差错概率。利用冗余降低差错概率。2021-9-18106.1 用于可靠传输和存储数据的编码 信道编码的基本思想p举例：举例

5、：ASCII码的偶校验码的偶校验n过程过程ASCII码：码：7bit表示符号，例如表示符号，例如“L”的的ASCII是是 0011001偶校验：使得编码后输出的码字中偶校验：使得编码后输出的码字中“1”的的个数为偶数个数为偶数 0011001-00110011接收端验证接收端验证“1”的个数是否为偶数这一的个数是否为偶数这一“规律规律”（关系）是否成立来检验错误是（关系）是否成立来检验错误是否发生否发生启示启示l需要增加冗余码元（需要增加冗余码元（8，7） l监督码元与信息码元建立了一组关系监督码元与信息码元建立了一组关系 l接收端利用这组关系检查和纠正错误接收端利用这组关系检查和纠正错误 2

6、021-9-18116.1 用于可靠传输和存储数据的编码 编码系统模型信源：输出的是信息序列（信息码元）信源：输出的是信息序列（信息码元）信道：广义信道，也称编码信道信道：广义信道，也称编码信道2021-9-1812信息序列：信息序列：mi=mi1 , mi2 , mik编码后的发送序列：编码后的发送序列：Ci=Ci1 , Ci2 , , Cin受到干扰后的接收序列：受到干扰后的接收序列：ri=ri1 , ri2 , rin信息序列：信息序列：mi=mi1 , mi2 , , mik编码编码译码译码发发送送端端接接收收端端信道（干扰）信道（干扰）编码系统模型下的数字序列变换2021-9-181

7、36.1 用于可靠传输和存储数据的编码 编码系统模型三点说明：三点说明：1.1.不可无限的增加冗余码不可无限的增加冗余码2.2.尽可能的重现尽可能的重现m m，即，即 使使m m尽量接近尽量接近m m3.3.编译码算法易实现，设备费用尽量低编译码算法易实现，设备费用尽量低研究各种编码和译码方法是信道编码所要解决的问题。研究各种编码和译码方法是信道编码所要解决的问题。噪声干扰噪声干扰2021-9-18146.2 错误类型与信道模型噪声干扰噪声干扰输入输入输出输出转移概率转移概率2021-9-18156.2 错误类型与信道模型p随机错误和随机信道随机错误和随机信道p突发错误和突发信道突发错误和突发

8、信道p混合错误和混合信道混合错误和混合信道2021-9-18166.2 错误类型与信道模型p随机错误和随机信道随机错误和随机信道n随机错误：各码元是否出现错误，与前、后码随机错误：各码元是否出现错误，与前、后码元是否差错没有关系，每个码元独立的按一定元是否差错没有关系，每个码元独立的按一定的概率发生差错。的概率发生差错。一般是由一般是由加性加性高斯白噪声高斯白噪声引起的。引起的。n只存在随机错误的信道称为无记忆信道只存在随机错误的信道称为无记忆信道/随机信随机信道，用信道转移概率来描述。比如，二进制对道，用信道转移概率来描述。比如，二进制对称信道称信道BSC。2021-9-1817二进制对称信

9、道（二进制对称信道（Binary Symmetric Channel, BSCBinary Symmetric Channel, BSC）P(1/0)=pP(0/1)=pP(1/1)=1-pP(0/0)=1-p输入符号取值集合输入符号取值集合 X=0，1输出符号取值集合输出符号取值集合 Y=0，10101XYpp1-p1-p6.2 错误类型与信道模型2021-9-18186.2 错误类型与信道模型p突发错误和突发信道突发错误和突发信道n突发错误：噪声对各传输码元的影响不是独立突发错误：噪声对各传输码元的影响不是独立的，从而导致差错是一连串出现的。的，从而导致差错是一连串出现的。例如移动通信中信

10、号在某一段时间内发生衰例如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等。落，造成一串差错；光盘上的一条划痕等。n存在突发错误的信道，称之为有记忆信道存在突发错误的信道，称之为有记忆信道/ /突突发信道。发信道。2021-9-18196.2 错误类型与信道模型p混合错误和混合信道混合错误和混合信道n混合错误：混合错误：既有突发错误又有随机错误。既有突发错误又有随机错误。n突发错误和随机错误并存的信道称之为突发错误和随机错误并存的信道称之为混合信混合信道道。2021-9-1820错误图样：错误图样： 设发送的是序列设发送的是序列C C（码元长度为（码元长度为n n），通过

11、），通过信道传输后，接收端的序列为信道传输后，接收端的序列为R R。由于在传。由于在传输过程中受到信道噪声干扰，输过程中受到信道噪声干扰，R R序列中的某序列中的某些元素和些元素和C C序列中的对应码元的值可能不同，序列中的对应码元的值可能不同，如果信道中的噪声干扰采用二进制序列如果信道中的噪声干扰采用二进制序列e e表表示，相应有错误的位取值为示，相应有错误的位取值为1 1，无错的位取，无错的位取值为值为0 0，可得，可得 e=C Re=C R6.2 错误类型与信道模型2021-9-1821p例：发送序列例：发送序列C C：（：（11111000001111100000），收到的），收到的序

12、列序列R R：（：（10010100001001010000），第二、三、五、），第二、三、五、六位产生了错误，因此错误图样六位产生了错误，因此错误图样e e的二、三、的二、三、五、六位取值为五、六位取值为1 1，即，即e e：(0(011011110110000)0000)p对于突发信道，错误图样中，第一个对于突发信道，错误图样中，第一个“1 1”和最后一个和最后一个“1 1”之间的码元总个数称为之间的码元总个数称为突突发长度发长度，其图样称为突发图样。该例中，其图样称为突发图样。该例中，突发图样是（突发图样是（1101111011），突发长度为），突发长度为5 5。6.2 错误类型与信道模

13、型2021-9-18226.3 差错控制的基本方式p反馈重传方式反馈重传方式 p前向纠错方式前向纠错方式 p混合方式混合方式2021-9-18236.3 差错控制的基本方式p反馈重传方式反馈重传方式(Automatic Repeat reQuest, (Automatic Repeat reQuest, ARQ)ARQ)n工作原理：发送端发送的是检错码，通过信道工作原理：发送端发送的是检错码，通过信道传输到接收端，接收端译码器只需根据编码规传输到接收端，接收端译码器只需根据编码规则判断是否有错误，并把判决信号通过反馈信则判断是否有错误，并把判决信号通过反馈信道送回发送端。发送端根据判决信号将收

14、端认道送回发送端。发送端根据判决信号将收端认为有错误的重新发送，直到接收端检查无误为为有错误的重新发送，直到接收端检查无误为止。止。2021-9-18246.3 差错控制的基本方式发端发端收端收端检错码检错码判决信号判决信号p反馈重传方式反馈重传方式(Automatic Repeat reQuest, (Automatic Repeat reQuest, ARQ)ARQ)n分为两类：等待式和连续式分为两类：等待式和连续式2021-9-18256.3 差错控制的基本方式p前向纠错方式前向纠错方式 (Forward Error Correction, FEC)n工作原理：发送端发送能纠正错误的码字

15、，在工作原理：发送端发送能纠正错误的码字，在接收端根据接收到的码字和编码规则，能自动接收端根据接收到的码字和编码规则，能自动纠正传输中的错误纠正传输中的错误。n不需要反馈信道，实时性好。不需要反馈信道，实时性好。n随着纠错能力的提高，编译码设备复杂。随着纠错能力的提高，编译码设备复杂。2021-9-18266.3 差错控制的基本方式p混合方式混合方式 (Hybrid Error Correction, HEC)n工作原理：结合前向纠错和工作原理：结合前向纠错和ARQ的系统，在纠的系统，在纠错能力范围内，自动纠正错误，超出纠错范围错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。则要

16、求发送端重新发送。n折衷方案。折衷方案。2021-9-18276.4 信道编码的分类p按差错控制编码的不同功能：按差错控制编码的不同功能：n检错码：发现错误的码检错码：发现错误的码n纠错码：自动纠正错误的码纠错码：自动纠正错误的码p按信息码元与附加监督码元间检验关系：按信息码元与附加监督码元间检验关系：n线性码线性码(Linear Code)：监督码元与信息码元满：监督码元与信息码元满足线性关系足线性关系n非线性码非线性码(Nonlinear Code)：监督码元与信息：监督码元与信息码元不满足线性关系码元不满足线性关系2021-9-18286.4 信道编码的分类p按信息码元与监督码元间约束方

17、式：按信息码元与监督码元间约束方式：n分组码分组码(Block Code)：信息序列每：信息序列每k位分成一位分成一组，产生组，产生r位监督元，输出长度为位监督元，输出长度为n=r+k的码字。的码字。r位监督元只与本分组的位监督元只与本分组的k位信息元有关，记为位信息元有关，记为（n, k）。）。n卷积码卷积码(Convolutional Code)：编码器给每：编码器给每k0位信息加上位信息加上r0位监督元得到长度为位监督元得到长度为n0的码字。的码字。该码字的运算，不仅与本组该码字的运算，不仅与本组k0位信息有关，还位信息有关，还与其前面与其前面m组组k0位信息有关。称这种码为（位信息有关

18、。称这种码为（n0，k0，m）卷积码。）卷积码。2021-9-18296.4 信道编码的分类p按信息码元在编码后是否保持原来的形式：按信息码元在编码后是否保持原来的形式：n系统码、非系统码系统码、非系统码p按纠正错误的类型：按纠正错误的类型：n纠正随机错误的码、纠正突发错误的码纠正随机错误的码、纠正突发错误的码p按每个码元取值：按每个码元取值：n二进制码、多进制码二进制码、多进制码2021-9-18306.4 信道编码的分类2021-9-18316.5 信道编码定理p香农信道编码定理香农信道编码定理p性能指标性能指标2021-9-18326.5 信道编码定理p香农信道编码定理香农信道编码定理

19、对于一个给定的有扰信道，若信道的容量为C，只要发送端以低于C的速率发送信息，则一定存在一种编码方法，使译码错误概率P随着码长n的增加，按指数下降到任意小的值，表示为 这里E(R)称为可靠性函数。()nE RPe2021-9-18336.5 信道编码定理定理告诉我们：定理告诉我们：p当信息速率小于信道容量时，总存在一种当信息速率小于信道容量时，总存在一种编码方式使差错率低于任一给定值编码方式使差错率低于任一给定值；p为减小差错概率，可增大码长为减小差错概率，可增大码长n或增大或增大E(R) 增大增大E(R)可：可：n可以增大信道容量；（增大带宽、增大功率、可以增大信道容量；（增大带宽、增大功率、

20、降低噪声）降低噪声）n减小码率；减小码率；2021-9-18346.6线性分组码p分组码及参数分组码及参数n分组码：将信息序列分成分组码：将信息序列分成k k位一组，按照一定位一组，按照一定的校验关系增加的校验关系增加r r位校验位，构成位校验位，构成n(n=k+r)n(n=k+r)位位码分组，称为码字码分组，称为码字（Code wordsCode words ) )，所有可能码，所有可能码字构成的集合称为一个分组码，记为字构成的集合称为一个分组码，记为(n,k)(n,k)分分组码组码n分组码的校验关系仅限于一个码分组之内分组码的校验关系仅限于一个码分组之内2021-9-18356.6线性分组

21、码p分组码及参数分组码及参数n主要参数：主要参数：信息分组：信息分组：m=(mm=(mk-1k-1 m mk-2k-2 m m1 1 m m0 0) )码字：码字：C=(cC=(cn-1n-1 c cn-2n-2 c c1 1 c c0 0) )码长码长n n，信息位个数，信息位个数k k，校验位个数，校验位个数r=n-kr=n-k码字个数码字个数( (二进制二进制) )：2 2k k编码效率：编码效率：R=k/nR=k/n2021-9-18366.6 线性分组码p许用码组、禁用码组许用码组、禁用码组n（n，k）码中有）码中有2k个个n重码字。但是重码字。但是n bit的二的二进制序列具有进制

22、序列具有2n种不同的组合序列；种不同的组合序列；n分组码的编码规则就是从分组码的编码规则就是从2n种不同序列中选择种不同序列中选择2k个码字，建立信息序列与码字的对应关系；个码字，建立信息序列与码字的对应关系；这2k个码字组成的集合称为许用码组，剩余的2n-2k个n重向量组成的集合称为禁用码组。2021-9-18376.6 分组码基本概念p码重、码距码重、码距n 码重：码字中非码重：码字中非0码元的个数，又称汉明码元的个数，又称汉明重量。重量。 例如码字例如码字 x=(11000)，则码重，则码重w(x)=2n 码距：码字码距：码字x与码字与码字y对应位取值不同的对应位取值不同的个数，又称为汉

23、明距离。个数，又称为汉明距离。 例如：例如：x=(10111101)，y=(01110101) 2021-9-18386.6 分组码的基本概念p最小码距（最小汉明距离）最小码距（最小汉明距离）n最小码距：（最小码距：（n，k）分组码中，任何两个码字）分组码中，任何两个码字之间距离的最小值，称为该分组码的最小汉明之间距离的最小值，称为该分组码的最小汉明距离，简称最小距离，用距离，简称最小距离，用d表示。表示。n最小码距描述分组码特性的重要参量，决定了最小码距描述分组码特性的重要参量，决定了码的纠错、检错性能码的纠错、检错性能。n(n,k)分组码通常也记为分组码通常也记为(n,k,d)分组码。分组

24、码。2021-9-18396.6 分组码的基本概念p最小码距（最小汉明距离）最小码距（最小汉明距离）例例： (2,1)重复码，重复码，00,11 d=？ (3,1)重复码，重复码，000,111d=？(4,1)重复码，重复码，0000, 1111 d=？2021-9-18406.6 分组码的基本概念p最小汉明距离译码最小汉明距离译码n准则：在许用码组中，判断与接收序列准则：在许用码组中，判断与接收序列r “最近最近”的码字为发送码字的码字为发送码字2021-9-1841分组码的检纠错能力p分组码的检纠错能力分组码的检纠错能力n码的最小距离为码的最小距离为d0 = e+1，其检错能力为，其检错能

25、力为e。2021-9-1842分组码的检纠错能力p分组码的检纠错能力分组码的检纠错能力n纠错能力：一个纠错能力：一个(n,k)分组码，如果能纠正码字分组码，如果能纠正码字内的所有小于或等于内的所有小于或等于t个个(位位)错误，则称该码的错误，则称该码的纠错能力为纠错能力为t2021-9-1843p分组码的检纠错能力分组码的检纠错能力n码的最小距离为码的最小距离为d0 = 2t+1，其纠错能力为，其纠错能力为t。且。且当当d*=2t+1或或d*=2t+2时，都不能纠正时，都不能纠正t+1个错个错误。误。2021-9-1844分组码的检纠错能力p分组码的检纠错能力分组码的检纠错能力n同时纠检错能力

26、：一同时纠检错能力：一 (n,k)分组码，如果能纠正分组码，如果能纠正码字内的所有小于或等于码字内的所有小于或等于t个个(位位)错误，同时又错误，同时又能检出所有小于或等于能检出所有小于或等于e(e t)个个(位位)错误，则错误，则称该码的同时纠检错能力为纠称该码的同时纠检错能力为纠t个错同时检个错同时检e个个错。错。2021-9-1845p分组码的检纠错能力分组码的检纠错能力n码最小码距码最小码距 d0=e+t+1， 其中其中et，该码能够，该码能够纠纠正正t个错误，同时检测个错误，同时检测e个错误。个错误。2021-9-18466.7 几种常用的编码方式p奇偶校验奇偶校验(监督监督)码码p

27、水平一致监督码水平一致监督码p水平垂直一致监督码水平垂直一致监督码p群计数码群计数码p恒比码（等重码）恒比码（等重码）2021-9-18476.7 几种常用的编码方式p奇偶校验码奇偶校验码n是是(n,n-1)码。假设奇偶校验码的码字表示为码。假设奇偶校验码的码字表示为n偶校验码：加入监督位后，码字中偶校验码：加入监督位后，码字中“1”的个数的个数为偶数个，即所有位的模二和为为偶数个，即所有位的模二和为0。 （即偶数个（即偶数个1）120.0nnccc120(,.,)nnccc2021-9-18486.7 几种常用的编码方式p奇偶监督（校验）码奇偶监督（校验）码n奇校验码：加入监督位后码字中奇校

28、验码：加入监督位后码字中“1”的个数为的个数为奇数个，即所有位的模二和为奇数个，即所有位的模二和为1。 （即奇数个（即奇数个1）n可以检测任意奇数个错误；可以检测任意奇数个错误；n构造简单，易于实现，在计算机内部数据传送构造简单，易于实现，在计算机内部数据传送和输入输出设备中经常使用。和输入输出设备中经常使用。120.1nnccc2021-9-18496.7 几种常用的编码方式p水平一致监督码水平一致监督码n将原信息序列以适当长度排成一行，如每将原信息序列以适当长度排成一行，如每k位位信息为一行，设共有信息为一行，设共有m行。行。n对每行进行偶（奇）校验经，构成对每行进行偶（奇）校验经，构成(

29、m(k+1),mk)分组码分组码n传输时按列传输；传输时按列传输；n译码时排成表，检验每行的校验关系译码时排成表，检验每行的校验关系2021-9-18506.7 几种常用的编码方式p水平一致监督码水平一致监督码n可以发现所有长度可以发现所有长度bm的单个突发错误的单个突发错误2021-9-18516.7 几种常用的编码方式p水平垂直一致监督码水平垂直一致监督码n经奇偶校验后的若干码字排列成矩阵，每个码经奇偶校验后的若干码字排列成矩阵，每个码字排成一行，然后再按列的方向增加垂直校验字排成一行，然后再按列的方向增加垂直校验位，就构成了二维奇偶校验码位，就构成了二维奇偶校验码(m(k+1)+k,mk

30、)n传输时可以按行传输，也可以按列传输。传输时可以按行传输，也可以按列传输。2021-9-18526.7 几种常用的编码方式p水平垂直一致监督码水平垂直一致监督码2021-9-18536.7 几种常用的编码方式p水平垂直一致监督码水平垂直一致监督码n纠检错能力强：纠检错能力强：可检测每一行中奇数个错和每一列中奇数个可检测每一行中奇数个错和每一列中奇数个错；错；二维奇偶码适用于检测突发错误。如果采用二维奇偶码适用于检测突发错误。如果采用按照列的顺序传输，可以发现长度按照列的顺序传输，可以发现长度tm+2的的突发错；如果按照行的顺序传输，可以发现突发错；如果按照行的顺序传输，可以发现t k+2。n

31、应用于穿孔纸带、磁带记录系统中。应用于穿孔纸带、磁带记录系统中。2021-9-18546.7 几种常用的编码方式p群计数码群计数码n将码字中将码字中“1”的计数值作为监督码元的计数值作为监督码元例如，信息组为例如，信息组为01011，共，共3个个1，用，用011表示，表示，得到得到(8,5)码。群计数码的码字为码。群计数码的码字为01011011n检错能力很强，除了检错能力很强，除了0错成错成1和和1错成错成0成对发生成对发生的情况外，其它形式的错误都能发现。的情况外，其它形式的错误都能发现。n为了降低发送码元中的冗余度，有时只传送计为了降低发送码元中的冗余度，有时只传送计数码元中最后几位。特

32、别的只传输最后数码元中最后几位。特别的只传输最后1位监位监督元，则群计数码变成奇偶校验码督元，则群计数码变成奇偶校验码2021-9-18556.7 几种常用的编码方式p恒比码恒比码n码字中码字中“1”和和“0”的个数保持相同的比例，即的个数保持相同的比例，即每个码字中每个码字中1的个数相同。的个数相同。n恒比码的译码可以采用查表方法，检错时查恒比码的译码可以采用查表方法，检错时查1或或0的个数。的个数。n恒比码是一种检错码。恒比码是一种检错码。n恒比码一般用在电报。恒比码一般用在电报。2021-9-18566.7 几种常用的编码方式p恒比码恒比码n例：发汉字电报时，每个汉字用例：发汉字电报时，

33、每个汉字用4位阿拉伯数位阿拉伯数字表示，每个阿拉伯数字用字表示，每个阿拉伯数字用5个比特的码字表个比特的码字表示。由于阿拉伯数字只有示。由于阿拉伯数字只有10个，因此从个，因此从32中可中可能的码字中挑出能的码字中挑出 =10个个1的个数为的个数为3的码字作的码字作为阿拉伯数字的编码方式。为阿拉伯数字的编码方式。阿拉伯数字阿拉伯数字编码编码阿拉伯数字阿拉伯数字编码编码10101161010121100171110031011080111041101091001150011100110135C2021-9-18576.8 信道编码理论的发展历史p1948年香农（年香农（Shannon）在其论文）

34、在其论文通信通信中的数学理论中的数学理论中提出有扰信道编码定中提出有扰信道编码定理理奠定了信道编码的基石。奠定了信道编码的基石。p50年代至年代至60年代初，信道编码从无到有得年代初，信道编码从无到有得到了迅速的发展：奠定了线性分组码的理到了迅速的发展：奠定了线性分组码的理论基础；提出了著名的论基础；提出了著名的BCH码编译码方法码编译码方法以及卷积码的序列译码。以及卷积码的序列译码。2021-9-18586.8信道编码理论的发展历史p60年代至年代至70年代初，信道编码发展最为活年代初，信道编码发展最为活跃的时期：提出了门限译码、迭代译码、跃的时期：提出了门限译码、迭代译码、软判决译码和维特比译码等有效的译码方软判决译码和维特比译码等有效的译码方法，并注重纠错码的实用化；在此期间以法，并注重纠错码的实用化；在此期间以代数方法特别以有限域理论为基础的线性代数方法特别以有限域理论为基础的线性分组码理论趋于成熟。分组码理论趋于成熟。2021-9-1859p70年代至年代至80年代，理论上，戈帕（年代，理论上，戈帕（Goppa）为首的一批学者构造了一类为首的一批学者构造了一类G