1、中南大学通信原理 Principles of Digital CommunicationF中南大学信息科学与工程学院中南大学信息科学与工程学院School of Information Science and EngineeringCentral South University主讲：李敏主讲：李敏联系方式：联系方式： 课件邮箱：课件邮箱：txyl_中南大学通信原理 中南大学通信原理 差错控制的目的和基本原理；差错控制的目的和基本原理；差错控制方式及其特点；差错控制方式及其特点；码重、汉明距离、最小距离的概念和确定；码重、汉明距离、最小距离的概念和确定；纠错和检错能力分析纠错和检错能力分析 编
2、码效率编码效率 汉明码和汉明码和CRCCRC码码中南大学通信原理7.1 7.1 基本概念基本概念系统特性的不理想：系统特性的不理想：乘性噪声乘性噪声数字信号波形失真数字信号波形失真接收端误判接收端误判形成误码形成误码信道噪声干扰：信道噪声干扰：加性噪声加性噪声数字信号变形数字信号变形误码误码按加性噪声引起的错码分布规律按加性噪声引起的错码分布规律随机信道随机信道：白色高斯噪声，误码相互独立；白色高斯噪声，误码相互独立；突发信道：突发信道：存在突发脉冲干扰，误码在短时间内成串存在突发脉冲干扰，误码在短时间内成串出现，并前后有关；出现，并前后有关；混合信道：混合信道：随机信道突发信道随机信道突发信
3、道中南大学通信原理7.1 7.1 基本概念基本概念：差错的出现随机，且差错之间是统计独立的差错的出现随机，且差错之间是统计独立的由随机噪声引起由随机噪声引起：差错在短时间成串出现，而在其间又存在较长的无差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关差错区间，且差错之间相关因脉冲噪声，也可能是由存储系统中磁带的缺陷或因脉冲噪声，也可能是由存储系统中磁带的缺陷或读写头接触不良引起读写头接触不良引起中南大学通信原理7.1 7.1 基本概念基本概念即提高信噪比，虽简单有效，但功率即提高信噪比，虽简单有效，但功率不可无限增加，实际受到一定的限制；不可无限增加，实际受到一定的限制；：
4、可抑制白色噪声，使误码率下降；：可抑制白色噪声，使误码率下降；PePePSKPSKPePeDPSKDPSKPePeFSKFSK相干、相干、ASKASKPet)中南大学通信原理7.7.2 2 纠错编码原理纠错编码原理v假设随机信道中发送假设随机信道中发送“0”码与发送码与发送“1”码码传错概率相等为传错概率相等为Pe,且且Pe1,则在码长为则在码长为n的码的码组中发生组中发生r个错误的概率为：个错误的概率为：vPn(r)=Cnr Per(1-Pe)n-rn!/r!(n-r)!Perv当码长当码长n=7,Pe=10-3时，则有时，则有P7(1)7 Pe=7 10-3P7(2)21 Pe2=2.1
5、10-5P7(3)35 Pe3=3.5 10-8中南大学通信原理7.7.2 2 纠错编码原理纠错编码原理指一个码组中指一个码组中信息位所占比重信息位所占比重，用，用表示表示=k/n，其中，其中k为信息码元的数目，为信息码元的数目，n为码长为码长nrnrnnk1v可见：若加入的监督位越多，纠错能力越强，编码效可见：若加入的监督位越多，纠错能力越强，编码效率越低；率越低；v纠错编码的纠错编码的是，根据不同干扰特性设计出纠检错是，根据不同干扰特性设计出纠检错能力最强，效率高的纠错码，且译码设备不太复杂；能力最强，效率高的纠错码，且译码设备不太复杂；中南大学通信原理7.7.3 3常用的简单编码常用的简
6、单编码：使码字加上：使码字加上1 1位监督位位监督位C C0 0后，码字中后，码字中“1 1”的个数为奇数个；的个数为奇数个；：使码字加上：使码字加上1 1为监督位为监督位C C0 0后，码字中后，码字中“1 1”的个数为偶数个；的个数为偶数个；只能检测出奇数个错误，不能纠错只能检测出奇数个错误，不能纠错应用：以随机错误为主的计算机通信系统，难于对付应用：以随机错误为主的计算机通信系统，难于对付突发错误突发错误最小码距最小码距d dminmin=2=2中南大学通信原理7.7.3 3常用的简单编码常用的简单编码【编码规则编码规则】（1 1）对需要传输的数据，进行奇偶校验编码；）对需要传输的数据，
7、进行奇偶校验编码；（2 2）将经过奇偶监督编码的码元序列按行排成方阵，每）将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶校验编码；行为一组奇偶校验编码；（3 3）发送时按照列的顺序传输；）发送时按照列的顺序传输；（4 4）接收端仍将码元排成发送时的方阵形式，然后按行）接收端仍将码元排成发送时的方阵形式，然后按行进行奇偶校验。进行奇偶校验。【例例】偶校验：偶校验：0100 1 1000 1 传输时为传输时为:01 10 00 00 11中南大学通信原理7.7.3 3常用的简单编码常用的简单编码将奇偶校验码的若干码组排列成矩阵将奇偶校验码的若干码组排列成矩阵每一码组写成一行每一码组写成一
8、行m个码组个码组m行行m个监督位构成了一监督位列个监督位构成了一监督位列按列的方向增加第二维校验位按列的方向增加第二维校验位n个监督位构成了一监督位行个监督位构成了一监督位行maaa02010 021cccnn012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn检错能力检错能力:检出所有行和列中的检出所有行和列中的奇数个差错奇数个差错 能检出大多数能检出大多数偶数个差错偶数个差错能检出突发长度不大于方阵行数能检出突发长度不大于方阵行数或列数的或列数的突发错误突发错误 适用于检测突发适用于检测突发错误，将使误码减少到原来的错误，将使误码减少到原
9、来的1 11 1 中南大学通信原理7.7.3 3常用的简单编码常用的简单编码中南大学通信原理7.7.3 3常用的简单编码常用的简单编码每个码组中含每个码组中含“1”和和“0”的个数的比例恒定，又称的个数的比例恒定，又称、；能检测出所有能检测出所有1位错和奇数个错误，并能部分检测出位错和奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出）偶数个错误（成对交换错则检测不出）简单，适应于对字母或符号进行编码，常用于电传机简单，适应于对字母或符号进行编码，常用于电传机传输汉字，以及其他产生固定字符的键盘设备中；传输汉字，以及其他产生固定字符的键盘设备中；【例】电传机传输数字时广泛采用的【例】电
10、传机传输数字时广泛采用的五单位数字保护五单位数字保护电码电码，是一种五中取三的恒比码，共有，是一种五中取三的恒比码，共有355!C103!2!种组合，代表种组合，代表10个阿拉伯数字。个阿拉伯数字。中南大学通信原理7.7.3 3常用的简单编码常用的简单编码监督位数与信息位数目相同，且两者相同或相反，取决监督位数与信息位数目相同，且两者相同或相反，取决于信息序列中于信息序列中“1”的个数；的个数；当信息位中有奇数个当信息位中有奇数个“1”时，监督位是信息位的简单重复；时，监督位是信息位的简单重复；当信息位中有偶数个当信息位中有偶数个“1”时，监督位是信息位的反码；时，监督位是信息位的反码；先将码
11、组中信息位与监督位按位模先将码组中信息位与监督位按位模2加，得到加，得到合成码组合成码组;产生校验码组：码组中信息码元有奇数个产生校验码组：码组中信息码元有奇数个“1”，则校验码组，则校验码组=合成码组，否则校验码组合成码组，否则校验码组=合成码组的反码合成码组的反码按照校验码组中按照校验码组中“1”的个数进行检错及纠错的个数进行检错及纠错中南大学通信原理7.7.3 3常用的简单编码常用的简单编码校验码组的组成校验码组的组成错码情况错码情况1 1全为全为“0 0”无错码无错码2 2有有4 4个个“1 1”，1 1个个“0 0”信息码中有一位错码，位置为信息码中有一位错码，位置为校验码中对应的校
12、验码中对应的“0 0”的位置的位置3 3有有4 4个个“0 0”，1 1个个“1 1”监督码中有一位错码，位置为监督码中有一位错码，位置为校验码中对应的校验码中对应的“1 1”的位置的位置4 4其他组成其他组成错码多于错码多于1 1个个中南大学通信原理7.7.3 3常用的简单编码常用的简单编码 举例：电报通信中常用举例：电报通信中常用5单位电码来构造正反码单位电码来构造正反码编码编码若为若为11001，则码字为，则码字为1100111001若为若为10001，则码字为，则码字为1000101110假设发送码组为假设发送码组为1100111001若接收码组为若接收码组为1100111001，判决
13、为无错传输，判决为无错传输若接收码组为若接收码组为1000111001：合成码组：合成码组01000（先将码组中信息位与（先将码组中信息位与监督位按位模监督位按位模2加，得到合成码组）；因码组中信息码元有加，得到合成码组）；因码组中信息码元有偶数个偶数个“1”，则校验码组为，则校验码组为10111；说明信息码元中第二位错码，给以纠；说明信息码元中第二位错码，给以纠正正若接收码组为若接收码组为1100101001：合成码组：合成码组10000；因码组中信息码元有；因码组中信息码元有奇数个奇数个“1”，则校验码组为，则校验码组为10000，说明监督码元中第一位错码，说明监督码元中第一位错码若接收码
14、组为若接收码组为1001111001：合成码组：合成码组01010；因码组中信息码元有；因码组中信息码元有奇数个奇数个“1”，则校验码组为，则校验码组为01010，说明错码多于，说明错码多于1个个码长为码长为10的正反码能够纠正的正反码能够纠正1位差错，并能检测所有位差错，并能检测所有2位及以下的位及以下的错码。错码。中南大学通信原理7.7.4 4 线性分组码线性分组码：信息码元编码后，信息码元本身不变，而只在信息码元：信息码元编码后，信息码元本身不变，而只在信息码元后加入监督码元，即前半部分为不变的信息码元，后半部分为监后加入监督码元，即前半部分为不变的信息码元，后半部分为监督码元的码型；督
15、码元的码型；：监督码元和信息码元成线性关系的码型；：监督码元和信息码元成线性关系的码型；：监督码元只和本身信息码元有关的码型；：监督码元只和本身信息码元有关的码型；：利用代数关系，将信息序列划分为等长的：利用代数关系，将信息序列划分为等长的k k位序列位序列段，在每一信息段后附加段，在每一信息段后附加r r个监督码元，并使监督码元和信息码个监督码元，并使监督码元和信息码元成线性关系，这样构成的码型就叫；元成线性关系，这样构成的码型就叫；：纠单个错的线性分组码；：纠单个错的线性分组码；：在严谨的代数基础上构造的、纠错能力强的解编码设备：在严谨的代数基础上构造的、纠错能力强的解编码设备并不复杂的线
16、性分组码；并不复杂的线性分组码；：监督码元不仅与本身信息码元有关，且跟其它码元有关：监督码元不仅与本身信息码元有关，且跟其它码元有关的一种码型；的一种码型；中南大学通信原理7.7.4 4 线性分组码线性分组码具有具有，即任意两许用码组之和仍为一许用码组；，即任意两许用码组之和仍为一许用码组；（除全（除全“0 0”码组以外）；码组以外）；线性分组码的表示（线性分组码的表示（n n，k k），码长为），码长为n n，信息码长为，信息码长为k k，监督码长监督码长r rn nk k；一致校验矩阵一致校验矩阵HH(Paritycheck Matrix)(Paritycheck Matrix):用于说明
17、监督码元与信息码元监督关系的矩阵用于说明监督码元与信息码元监督关系的矩阵设码元表示为：设码元表示为：C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0；由（由（7 7，4 4）码可知：）码可知：n=7n=7，k=4k=4，r=3r=3；假设：假设：346035614562CCCCCCCCCCCC000034613562456CCCCCCCCCCCC中南大学通信原理7.7.4 4 线性分组码线性分组码写成矩写成矩阵形式阵形式：0001001101010101100101110123456CCCCCCC一致校验矩阵一致校验矩阵HH中南大学通信原理7.7.4
18、4 线性分组码线性分组码000034613562456CCCCCCCCCCCC 00TTTHCCH或(n n,k k)码的所有码字均按码的所有码字均按H H所确定的规则求出所确定的规则求出H H矩阵的每一行代表一个线性方程的系数，矩阵的每一行代表一个线性方程的系数，它表示求一个校验元的线性方程。它表示求一个校验元的线性方程。H H矩阵每一列代表此码元与哪几个校验方程矩阵每一列代表此码元与哪几个校验方程 有关。有关。k+r=n列列 HH是是r rn n阶矩阵，阶矩阵，r r为监督码元个数，为监督码元个数，n n为码长；为码长；H=P|IH=P|Ir r，P P是是r rk k阶阵，阶阵，I Ir
19、 r为为r r个监督码系数构个监督码系数构成的成的r rr r阶单位矩阵，此时称阶单位矩阵，此时称HH为典型形式监督矩为典型形式监督矩阵，各行线性无关；阵，各行线性无关；若接收到码字若接收到码字R R与与HH的转置乘积为的转置乘积为00，则说明接收，则说明接收到的码字到的码字R R是正确的，即是正确的，即 R RHHT T=0=0，则，则R R正确；正确；最小码距最小码距d d0 0=n-k+1=r+1RRCC，说明正确接收；，说明正确接收；若传输过程发生误码，设收发码组之差为若传输过程发生误码，设收发码组之差为E,E,则则 E=E E=En-1n-1E En-2n-2E E0 0=R-C=R
20、-C E Ei i1 1 第第i i位有错，即位有错，即R Ri i不等于不等于C Ci i 0 0 第第i i位没有错，即位没有错，即R Ri iC Ci i EE为错误图样为错误图样，即发送数据序列与接收序列对应码位，即发送数据序列与接收序列对应码位的的模和模和；R=C+E(R=C+E(模模2)2)，S=RHS=RHT T=EH=EHT T，称，称SS为校为校正子正子或伴随式或校验子，为或伴随式或校验子，为1 1r r阶行矩阵，它最多能指阶行矩阵，它最多能指出出2r-1种错误。种错误。中南大学通信原理7.7.4 4 线性分组码线性分组码设设发送的码字为发送的码字为C=CC=Cn-1n-1C
21、 Cn-2n-2C C0 0 接收的码字为接收的码字为R=RR=Rn-1n-1R Rn-2n-2R R0 0，则，则例题例题(6,3)(6,3)码码能纠正能纠正单个错误单个错误的高效率线性分组码的高效率线性分组码特点：特点：（n,k）汉明码，）汉明码，K位信息，监督位有位信息，监督位有r位，为能指位，为能指出所有出所有单错位置和无错情况，单错位置和无错情况，n、k和和r间应满足下间应满足下述关系：述关系：取等号：码长取等号：码长n=2r-1，k=2r-1-r 最小码距为最小码距为3，纠错能力为，纠错能力为1；编码效率较高，编码效率较高，=k/n=(2r-1-r)/(2r-1)=1-r/(2r-
22、1)当当n增大，增大，r增大，但增大，但也增加；也增加；汉明码是一种完备码，能纠正一个错码，能检测两汉明码是一种完备码，能纠正一个错码，能检测两个错码；个错码；中南大学通信原理7.7.4 4 线性分组码线性分组码nr12中南大学通信原理7.7.4 4 线性分组码线性分组码346035614562CCCCCCCCCCCC000034613562456CCCCCCCCCCCC中南大学通信原理7.7.4 4 线性分组码线性分组码码长为码长为n的码组中的各码元当作的码组中的各码元当作n-1次多项式的系数次多项式的系数若码组若码组A=（an-1，an-2，a1，a0)，则其相应的码多，则其相应的码多项式
23、为：项式为：A(x)=an-1xn-1+an-1xn-1+a1x+a0 如码组（如码组（1100101）对应的码多项式可表示为）对应的码多项式可表示为 A7(x)=1x6+1x5+0 x4+0 x3+1x2+0 x+1=x6+x5+x2+1 码多项式与码组的关系：本质上是一回事，仅是表示方法的码多项式与码组的关系：本质上是一回事，仅是表示方法的不同而已不同而已中南大学通信原理7.7.5 5 循环码循环码循环码是一种循环码是一种系统分组码系统分组码，前，前k k位是信息码，后位是信息码，后r r位是监位是监督码。不仅具有督码。不仅具有封闭性封闭性，还具有，还具有循环性循环性，即一许用码组，即一许
24、用码组经循环移位后得到另一个许用码组。经循环移位后得到另一个许用码组。中南大学通信原理7.7.5 5 循环码循环码中南大学通信原理7.7.5 5 循环码循环码多项式的模运算示例多项式的模运算示例若若c c(x)(x)是是n n长循环码中的一个码多项式，则长循环码中的一个码多项式，则xic c(x)(x)按模按模xn1 1运算的运算的余式余式必为循环码中的另一个码多项式；必为循环码中的另一个码多项式；即即若若xi c(x)ci(x)（模（模xn+1）,则则 c i(x)也是一许用码组，且也是一许用码组，且为为c(x)码组向左循环移位码组向左循环移位i次的结果。次的结果。中南大学通信原理7.7.5
25、 5 循环码循环码02211 )(cxcxcxcnnnn102312)1()(nnnnncxcxcxcxc)()1()()1(10121xcxcxcxcxcxcxnnnnnnci(x)xi c(x)ci(x)中南大学通信原理7.7.5 5 循环码循环码g(x)g(x)是循环码中前是循环码中前k-1k-1位为位为0 0码字的码多项式，即为码字的码多项式，即为(n-k)(n-k)阶码多项式阶码多项式中南大学通信原理7.7.5 5 循环码循环码中南大学通信原理7.7.5 5 循环码循环码在循环码中，在循环码中，(n-k)阶码多项式有且仅有一个；阶码多项式有且仅有一个；循环码中，所有码多项式都能被循环
26、码中，所有码多项式都能被g(x)整除；整除；：次数不大于：次数不大于k-1次的任何多项式与次的任何多项式与g(x)的乘积都是的乘积都是码多项式；码多项式；循环码的生成多项式循环码的生成多项式g(x)是是xn+1的一个因式；的一个因式；中南大学通信原理7.7.5 5 循环码循环码 根据循环性，根据循环性，xg(x)，x2 g(x)，xk-1g(x)都是许用码组，都是许用码组，连同连同g(x)共共k个许用码组，构成码的个许用码组，构成码的生成矩阵生成矩阵G(x)：)()()()()(21xgxxgxgxxgxXGkkxi g(x)（i k-1）相当于对）相当于对g(x)向左循环移位向左循环移位i次
27、次中南大学通信原理7.7.5 5 循环码循环码(设信息码多项式为设信息码多项式为m(x)m(x)1）确定循环码的）确定循环码的生成多项式生成多项式g(x);2）信息码元左移信息码元左移r位位，得，得M(x)=xn-km(x)；3）M(x)除以除以g(x)，求余数求余数R(x)；4）T(x)=xn-km(x)+R(x)中南大学通信原理7.7.5 5 循环码循环码中南大学通信原理7.7.5 5 循环码循环码中南大学通信原理7.7.5 5 循环码循环码中南大学通信原理7.7.5 5 循环码循环码中南大学通信原理7.7.5 5 循环码循环码中南大学通信原理7.7.5 5 循环码循环码对于系统循环码而言
28、，其监督矩阵必然是典型形式。即对于系统循环码而言，其监督矩阵必然是典型形式。即若已知典型生成矩阵若已知典型生成矩阵则典型监督矩阵则典型监督矩阵【注】【注】可以通过矩阵的初等变换，把非典型形式的生可以通过矩阵的初等变换，把非典型形式的生成矩阵和监督矩阵，变换成典型形式。变换时注意是成矩阵和监督矩阵，变换成典型形式。变换时注意是模模2运算运算。中南大学通信原理7.7.5 5 循环码循环码 能检出全部的单个错误：能检出全部的单个错误：对应一位错码的错码多项式对应一位错码的错码多项式E(x)=xi，而多于一项的生成多项式，而多于一项的生成多项式g(x)=+1，显然，显然xi除以除以g(x)的余数不会等
29、于的余数不会等于0，也即能检测出全，也即能检测出全部单个错码。部单个错码。能检出全部离散的二位错：能检出全部离散的二位错：对应的错码多项式对应的错码多项式E(x)=xi+xj=xi(1+xj-i)，只要选取的，只要选取的g(x)不能除尽不能除尽(xj-i+1)，且，且(n-k)(j-i)能检出全部的奇数个错码：能检出全部的奇数个错码：含有奇数项错码的多项式必不含含有奇数项错码的多项式必不含(x+1)因子，只要选取的因子，只要选取的g(x)含有含有(x+1)因子因子 能检测所有长度不超过能检测所有长度不超过(n-k)的突发错误：的突发错误：突发长度不大于突发长度不大于b的突发错误对应的错码多项式
30、的突发错误对应的错码多项式 为为E(x)=xi(eb-1xb-1+eb-2xb-2+e1x+1)=xi E1(x)由于由于g(x)除不尽除不尽xi；g(x)为为n-k次多项式，只要次多项式，只要E1(x)的次数的次数b-1不超不超过过(n-k-1)次，次，g(x)便除不尽便除不尽E1(x)。也就是说，能检测长度不超过。也就是说，能检测长度不超过(n-k)的突发错误。的突发错误。中南大学通信原理7.7.5 5 循环码循环码 在在(n，k)循环码的循环码的2k个码组集合中，选择前个码组集合中，选择前i个信息个信息位为位为0的所有码组（共的所有码组（共2k-i个），组成一个新的码组个），组成一个新的
31、码组集合，这一新的码组集合就构成了集合，这一新的码组集合就构成了(n-i，k-i)码，称码，称它为它为(n，k)的的缩短循环码缩短循环码。例如要构造一个能够纠正一位错误的例如要构造一个能够纠正一位错误的(12，8）码，）码，我们可以从（我们可以从（15，11）汉明码中挑出前三位均为）汉明码中挑出前三位均为0的码组来构成。的码组来构成。中南大学通信原理7.7.5 5 循环码循环码 在在(n，k)的缩短循环码中，每一个码组的缩短循环码中，每一个码组必定能被必定能被g(x)除尽除尽（注注：g(x)是原循环码的生成多项式是原循环码的生成多项式）每一个码组是原来循环码的码组，只是这码组的前每一个码组是原
32、来循环码的码组，只是这码组的前i个信息个信息码元为码元为0，所以它必定能被，所以它必定能被g(x)除尽。除尽。换言之，所有次数小于换言之，所有次数小于n-i次，且能被次，且能被g(x)除尽的多项式都是除尽的多项式都是(n-i，k-i)缩短循环码的码多项式。缩短循环码的码多项式。在在(n，k)的缩短循环码中，所有码组的前的缩短循环码中，所有码组的前i位为位为0，故，故发送时可不发送这发送时可不发送这i个个0，仅传输后面的，仅传输后面的n-i位码元。位码元。(n-i，k-i)码的纠检错能力不低于原来的码的纠检错能力不低于原来的(n，k)循环码循环码的纠检错能力。的纠检错能力。缩短循环码的所有码组是原来循环码组集合中的一部分，且缩短循环码的所有码组是原来循环码组集合中的一部分，且监督码元位数没变。监督码元位数没变。中南大学通信原理7.7.5 5 循环码循环码
