差错控制和信道编码课件

通信原理程琳兰州大学信息科学与技术学院电信系M.P:mail:chenglin@

or

chenglinwtt@Address：DepartmentofElectronics&InformationScience,SchoolofInformationScience&Engineering,LanzhouUniversity,TianshuiSouthernRoad222#，GansuProvince，P.R.ChinaPrinciplesofCommunications－兰州大学信息科学与工程学院电信、通信工程系－通信原理程琳兰州大学信息科学与技术学院电信系Pri第十三章差错控制和信道编码主要内容提要：

》差错控制方式及信道编码的基本概念》线性分组码

》循环码》卷积码》其它信道编码简介7/27/20232－兰州大学信息科学与工程学院电信、通信工程系－第十三章差错控制和信道编码主要内容提要：7/26/本章的教学基本要求本章要求掌握差错控制的基本方式、信道编码的一些基本概念、线性分组码特性及其设计、循环码特性及其设计、卷积码特性及其设计；其余的内容可根据学时情况酌情加以了解即可。7/27/20233－兰州大学信息科学与工程学院电信、通信工程系－本章的教学基本要求本章要求掌握差错控制的基在实际信道上传输数字信号时，由于信道传输特性不理想以及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误。产生差错的原因信道的电气特性引起信号幅度、频率、相位的畸变；信号反射；串扰；闪电、大功率电机的启停产生脉冲干扰等。一般说来，线路传输差错是不可避免的，但要尽量减小其影响。§1.引言7/27/20234－兰州大学信息科学与工程学院电信、通信工程系－在实际信道上传输数字信号时，由于信道传输特性不理想以及加性噪§1.引言信道差错的几种模式随机差错：差错的出现是随机的，一般而言差错出现的位置是随机分布的。这种情况一般是由信道的加性随机噪声引起的。一般将这种信道称为随机信道。突发差错：差错的出现是一连串出现的。这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等。这样的信道我们称之为突发信道。混合差错：既有突发错误又有随机差错的情况。这种信道称之为混合信道。7/27/20235－兰州大学信息科学与工程学院电信、通信工程系－§1.引言信道差错的几种模式7/26/20235－兰州大§1.引言降低误码的技术措施：》为了在已知信噪比情况下达到一定的误比特率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域/频域均衡，使误比特率尽可能降低。》但若误比特率仍不能满足要求，则必须采用信道编码（即差错控制编码），将误比特率进一步降低，以满足系统指标要求。随着差错控制编码理论的完善和数字电路技术的发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与存储中也得到日益广泛的应用。7/27/20236－兰州大学信息科学与工程学院电信、通信工程系－§1.引言降低误码的技术措施：7/26/20236－兰州大§1.引言我们研究的是编码和译码，所以完全可以将调制、解调与信道合起来等效成一个等效信道——编码信道。编码信道根据调制解调的不同输入和输出具有不同的类型离散无记忆对称二进制输入二进制输出信道（BSC）离散无记忆二进制输入多进制输出信道离散无记忆多进制输入多进制输出离散无记忆二进制输入连续输出离散有记忆信道编码信道信源编码调制信道解调译码信宿7/27/20237－兰州大学信息科学与工程学院电信、通信工程系－§1.引言我们研究的是编码和译码，所以完全可以将调制、§1.引言信道编码的目的：改善数字通信系统的传输质量信道编码(差错控制编码)的基本思路：在发送端将被传输的信息附上一些监督码元，这些冗余的码元与信息码元之间以某种确定的规则相互关联（约束）。接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。信道编码的任务：构造出以最小多余度（冗余度）代价换取最大抗干扰性能的“好码”。研究各种编码和译码方法是信道编码所要解决的主要问题。

7/27/20238－兰州大学信息科学与工程学院电信、通信工程系－§1.引言信道编码的目的：改善数字通信系统的传输质量7/信道编码与信源编码的区别信源编码尽量减少信源的冗余度。即尽可能用最少的信息比特来表示信源。如话音压缩编码、图象压缩编码。信道编码在待传输信息中加入冗余信息，以此达到差错控制的目的，从而提高通信系统的可靠性。如纠错编码、检错重发编码等7/27/20239－兰州大学信息科学与工程学院电信、通信工程系－信道编码与信源编码的区别信源编码信道编码7/26/20239§2.差错控制方式及信道编码的基本概念一、差错控制的三种方式：检错重发（ARQ：AutomaticRepeatRequest）在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道要求发送端重新发送，直到接收端检查无误为止。ARQ系统需要反馈信道，效率较低，但是能达到很好的性能。前向纠错（FEC：ForwardErrorCorrection）

发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动纠正传输中的错误。不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂。混合方式（HEC：HybridErrorCorrection）结合前向纠错FEC和ARQ的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。它是一种折中的方案。7/27/202310－兰州大学信息科学与工程学院电信、通信工程系－§2.差错控制方式及信道编码的基本概念一、差错控制的三种方差错控制的三种方式检错重发（ARQ：Automatic

RepeatRequest）前向纠错（FEC：ForwardErrorCorrection）混合方式（HEC：Hybrid

ErrorCorrection）发送接收可检错的码序列应答信号发送接收可检错和纠错的码序列发送接收可检错和纠错的码序列应答信号7/27/202311－兰州大学信息科学与工程学院电信、通信工程系－差错控制的三种方式检错重发（ARQ：AutomaticR差错控制的三种方式之ARQ检错重发ARQ系统具有各种不同的重发机制停等ARQ发送方每发完一帧必须等接收方确认后才能发下一帧。Go-back-NARQ(回退N)发送方可连续发送多帧。若前面某帧出错，从该帧以后的各帧都需重发。（一般与流控结合使用）选择性重传SARQ发送方可连续发送多帧。若前面某帧出错，只需重发该出错的帧。发送方需要缓存前面所有未被确认的帧。……其它不常用的差错控制方式：信息反馈方式（IRQ）7/27/202312－兰州大学信息科学与工程学院电信、通信工程系－差错控制的三种方式之ARQ检错重发ARQ系统差错控制的三种方式之ARQ停等ARQ回退N选择性重传码组1ACKNAK码组2ACK重发码组2码组3无错无错有错发送接收1234563456712345634567发现错误NAK重发12345637891234563789发现错误NAK重发7/27/202313－兰州大学信息科学与工程学院电信、通信工程系－差错控制的三种方式之ARQ停等ARQ回退N码组1二、信道编码的分类1、按功能划分为：检错码、纠错码、纠删码（兼检错、纠错）2、按信息位和校验位的约束关系分为：线性码、非线性码3、按信息码元和监督码元的约束关系分为：分组码：监督码仅与本码组信息码有关卷积码：监督码不仅与本码组信息码有关，而且与前面码组的信息码有关。4、按编码后信息码结构是否发生变化分为：系统码：编码前后信息码结构不变非系统码：编码前后信息码结构发生改变5、按码元的进制进行划分：二进制码、多进制码：7/27/202314－兰州大学信息科学与工程学院电信、通信工程系－二、信道编码的分类1、按功能划分为：7/26/20231三、信道编码的基本概念分组码：将k比特信息编成n比特一组的码字（码组），记为（n，k）分组码。K位码元，作为信息码元r=n-k位码元，称作冗余码、监督码许用码组：禁用码组：码重W：码字中1的个数。如W(11000)=2;W(010)=1

码距d（汉明距离Hamming）：两码组中对应位不同的比特（bit）数。如C1:11000，C2:11101,则d(C1，C2)=27/27/202315－兰州大学信息科学与工程学院电信、通信工程系－三、信道编码的基本概念分组码：将k比特信息编成n比特一组的码信道编码的基本概念最小码距：分组码(n,k)中任何两个码字Ci、Cj之间的码距的最小值，用dmin表示。最小码距是衡量码的一种内在属性最小码距决定了码的纠错、检错性能若要发现e个独立随机错误，要求dmin≥e+1若要纠正t个独立随机错误，要求dmin≥2t+1若要发现e个同时又纠正t(e>t)个独立随机错误，要求dmin≥e+t+1e+1ee2t+1tte+t+1et7/27/202316－兰州大学信息科学与工程学院电信、通信工程系－信道编码的基本概念最小码距：e+1ee2t+1tte+t+1四、常用简单检错码1.奇偶监督码（奇偶校验码）最简单的检错码(1bit校验)，在计算机数据传输中得到广泛应用传送信息分组(an-1,…,a1,)+监督位(a0)=一个传输码组(an-1,…,a1,a0)偶校验：an-1+an-2+

…+a1+a0=0(mod2)（即偶数个1）奇校验：an-1+an-2+

…+a1+a0=1(mod2)（即奇数个1）可见这种码的最小码距为2，只能检出1个独立随机差错。7/27/202317－兰州大学信息科学与工程学院电信、通信工程系－四、常用简单检错码1.奇偶监督码（奇偶校验码）7/26/20简单的检错码2.二维奇偶监督码（行列监督码）可检测出任一行或任一列上所有奇数个错码信息码元水平监督码010110110010101010010000110000110垂直监督码001111110117/27/202318－兰州大学信息科学与工程学院电信、通信工程系－简单的检错码2.二维奇偶监督码（行列监督码）信息码元水平监督简单的检错码3.恒比码

每个码组中的1的个数都是一样的。典型应用：一般用在电传、电报。例如，我国电传机传输汉字时每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示，即从32种组合选取10个为阿拉伯数字编码阿拉伯数字编码阿拉伯数字编码101011610101211001711100310110801110411010910011500111001101恒比码的编译码可以采用查表的方法，检错时检查1的个数是否为37/27/202319－兰州大学信息科学与工程学院电信、通信工程系－简单的检错码3.恒比码阿拉伯数字编码阿拉伯数字编码1010简单的检错码4.ISBN国际统一图书编号（例一）在国际图书的发行中，经常用编码的方式来防止书号在通信过程中发生错误，举例如下所述。如《通信原理》的书号是ISBN7-5635-0525-3其中第一位数字“7”表示“中国”，“5635”表示出版社，“0525”表示书名编号，最后一位“3”表示校验位。这里所采用的校验方式如下所示：75635052537121821262631333841719375884110141174212253(模11)≡0若通信过程中统一书号发生了错误，则上述累计和就不能被11整除，从而可以校验出来。7/27/202320－兰州大学信息科学与工程学院电信、通信工程系－简单的检错码4.ISBN国际统一图书编号（例一）若通信过程中简单的检错码4.ISBN国际统一图书编号（例二）如《通信原理》的书号是ISBN7-118-0429-X其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”表示书名编号，最后一位“X”表示校验位（它是罗马数字10的表示）。这里所采用的校验方式如下所示：71180429X=1078917172123324271524415879102134176176(模11)=0。又譬如：ISBN7－03－014456－2，大家可自行分析。7/27/202321－兰州大学信息科学与工程学院电信、通信工程系－简单的检错码4.ISBN国际统一图书编号（例二）7/26/2§3.线性分组码近世代数学有限域的概念：有限个元素的集合，按规定可以进行的代数四则运算，其运算结果仍属于该集合中有限的元素。最简单的有限域{0，1}——Galois域1+1=0、1+0=1、0+1=1、0+0=01x1=1、1x0=0、0x0=0、0x1=0定义线性分组码的加法为模2加，乘法为二进制乘法。且码字与码字的运算是各个相应比特位上的上述二进制运算规则。7/27/202322－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码近世代数学有限域的概念：7/26/202§3.线性分组码基本概念码组中监督码与信息码之间满足线性方程；任意两个可用码组之和(逐位模2加)仍为一个可用码组奇偶监督码——最简单的线性分组码偶校验时奇校验时不满足线性分组码的第二个性质。定义校正子（校验子伴随式）接收时进行校验计算：

S=0→无错；

S=1→有错（奇数个）7/27/202323－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码基本概念7/26/202323－兰州大学信§3.线性分组码一般情况下：如果码组中有2个监督码，校正子为S=[s1,s2]可以检测到三种误码状态7/27/202324－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码一般情况下：7/26/202324－兰州大§3.线性分组码如果码组中有r个监督码，假设码组中有K个信息码，则线性分组码的长度应该为n=K+r。码的结构线性分组码（n，k）的性质封闭性：任意两个码组的和还是许用的码组码的最小距离等于非零码的最小码重K位信息位r位监督位n位码组7/27/202325－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码如果码组中有r个监督码，假设码组中有K个信§3.线性分组码检错能力：有r个校正子方程→可以指示（2r-1）个错误纠错能力：对1位错码，可以指示（2r-1）个错误位置若2r-1≥n，可以纠正1bit或以上的错码，即2r-1≥r+k，2r-1-r≥k设k=4，能纠正1位误码的最小r=3，则n=7

（7，4）线性分组码，码组C=[c6c5c4c3c2c1c0]，其中c6c5c4c3为信息码，c2c1c0为监督码7/27/202326－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码检错能力：7/26/202326－兰州大学§3.线性分组码一般分析，对于线性分组码（n,k）,若可记为：（Cn-1Cn-2Cn-3……Cn-KCr-1Cr-2Cr-3……C1C0）

现令信息码元与监督码元的约束关系为：7/27/202327－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码一般分析，对于线性分组码（n,k）,若可记§3.线性分组码据此可得如下结果：由上式可得一致监督关系为：7/27/202328－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码据此可得如下结果：由上式可得一致监督关系为§3.线性分组码其中的H为：7/27/202329－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码其中的H为：7/26/202329－兰州大§3.线性分组码同样可知：7/27/202330－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码同样可知：7/26/202330－兰州大学§3.线性分组码若令下述关系成立：对比H和G，可见：7/27/202331－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码若令下述关系成立：对比H和G，可见：7/2§3.线性分组码所以可得如下结果：这里称H为一致监督矩阵；G则是生成矩阵。下面研究一个实际例子。7/27/202332－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码所以可得如下结果：这里称H为一致监督矩阵§3.线性分组码现以一个(7,3)线性分组码为例n=7,k=3,r=n-k=4编码效率为：R=k/n=3/7

c0=u0

c3=u0+

u2

信息位c1=u1

监督位c4=u0+

u1+

u2

c2=u2

c5=u0+

u1

c6=u1+

u2

则C=（c0c1c2c3c4c5c6）=（u0,u1,u2,u0+

u2,u0+

u1+

u2,

u0+

u1,u1+

u2）7/27/202333－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码现以一个(7,3)线性分组码为例7/26/§3.线性分组码n位的码组，由k个信息位的输入消息u通过一个线性变换矩阵k×n阶G来产生，称G——生成矩阵G=，I为k阶单位方阵——典型生成矩阵生成矩阵G7/27/202334－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码n位的码组，由k个信息位的输入消息u通过一§3.线性分组码将监督位线性方程组写为即可见上述监督关系的线性方程组完全由矩阵H所决定。故将此r×n的H矩阵称为监督矩阵H=,I为(n-k＝r)维（阶）单位方阵——典型监督矩阵7/27/202335－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码将监督位线性方程组写为7/26/20233§3.线性分组码根据前面所得可推导：∴G与H生成的空间互为零空间，且G与H可以互相转换。（即P、Q互为转置矩阵）7/27/202336－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码根据前面所得可推导：（即P、Q互为转置矩§3.线性分组码校正子（码组伴随式）发送码组C经过传输系统到达接收端时，假设收到的码组为B，B=[bn-1bn-2…b0]差错关系为B-C=E，B＋E=CE=[en-1en-2…e0]，E又称为错误图样。其中接收时计算校正子为

7/27/202337－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码校正子（码组伴随式）7/26/202337§3.线性分组码编码器若以{c0c1c2}为信息码,由监督码的生成关系可得c3=1·c0+

0·c1+

1·c2c4=1·c0+

1·c1+1·

c2c5=1·c0+

1·c1+0·c2c6=0·c0+

1·c1+

1·c2C0C1C2++++u0u1u2C4C5C6C37/27/202338－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码编码器C0C1C2++++u0u1u2C4§3.线性分组码译码器由校正子关系可得7/27/202339－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码译码器7/26/202339－兰州大学信息§3.线性分组码译码器b0b1b2b3b4b5b6++++b0s1s2s3s4s1s2s3s4与+r0c0b1与+r1c1b2与+r2c2b3与+r3c3b4与+r4c4b5与+r5c5b6与+r6c6伴随式计算电路错误图样检测电路7/27/202340－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码译码器b0b1b2b3b4b5b6++++§3.线性分组码汉明（海明）码（Hamming）能纠正单个随机错误的线性分组码码长n=2m-1信息位k=2m-1-m监督位n-k=m，且m≥3最小距离dmin=d0=3汉明码是一类高效率的纠错码编码效率R=k/n=(n-m)/n=1-m/nn很大时，R→17/27/202341－兰州大学信息科学与工程学院电信、通信工程系－§3.线性分组码汉明（海明）码（Hamming）7/26/§4.循环码基本概念线性分组码的一个子类，比较成熟任何一个可用码组经过循环移位后所得到的码组仍为一个可用码组原码组C=[cn-1cn-2…

c1c0]左移一位C1=[cn-2cn-3…c0cn-1]右移一位C2=[c1cn-1…c3c2]移i位Ci=[cn-i-1cn-i-2…

cn-i]循环码组C=[cn-1cn-2…

c1c0]可表示为多项式C(x)=cn-1xn-1

+

cn-2xn-2

+…+

c1x+

c0式中x的幂次表示：①码元的位置；②码的移位次数7/27/202342－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码基本概念7/26/202342－兰州大学信息科§4.循环码基本概念如多项式C(x)=

x6

+

x4

+x+1→C=[1010011]c6x6可以看作c6从最低位c0左移6次的结果C(x)左移一位记作C(1)(x)C(1)(x)=cn-2xn-1

+

cn-3xn-2

+…+

c0x+

cn-1C(x)左移i位后为C(i)(x)=cn-i-1xn-1

+

cn-i-2xn-2

+…+

cn-i+1x+

cn-i7/27/202343－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码基本概念7/26/202343－兰州大学信息科§4.循环码循环码多项式的运算特性码长为n的循环码，其码多项式C(x)，则xi·C(x)=Q(x)·(xn+1)+C(i)(x)即例如：某循环码组为C=(1100101)，码长n=7，对应的码多项式为C(x)=x6

+x5

+

x2+

1左移一位后x·C(x)=x7

+x6

+

x3+

x因为C(1)(x)≡x·C(x)(mod（x7+1）)=x6

+x3

+

x

+

1→（1001011）7/27/202344－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码循环码多项式的运算特性7/26/202344－§4.循环码左移2位时x2·C(x)=x8

+x7

+

x4+

x2x+1x7

+1)x8

+x7

+

x4+

x2x8+x

x7

+

x4+

x2+xx7+1x4+

x2+x+1∴C(2)(x)=x4+

x2+x+1→(0010111)7/27/202345－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码左移2位时7/26/202345－兰州大学信息§4.循环码生成多项式g(x)对于(n,k)循环码来说，生成多项式g(x)是一个能除尽xn+1的（n-k）阶多项式。阶数低于n并能被g(x)除尽的一组多项式就构成一个(n,k)循环码阶数小于等于(n-1)并能被g(x)除尽的每个多项式都是循环码的可用码组多项式。所以，循环码完全由其码组长度n和生成多项式g(x)所决定。7/27/202346－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码生成多项式g(x)7/26/202346－兰州§4.循环码生成多项式g(x)设构成循环码的信息码多项式为u(x)，其阶数不大于(k-1)，则有循环码组为C(x)=u(x)·g(x)例如，n=7，g(x)=x4+x3+x2+1是x7+1的一个因式；g(x)最高幂次为4=n-k；则k=3，r=4（即信息码3bit，监督码4bit）。可用码组如下：7/27/202347－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码生成多项式g(x)7/26/202347－兰州§4.循环码生成多项式g(x)以上是一个（7，3）循环码，最小码距dmin=4，其信息码多项式如下：7/27/202348－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码生成多项式g(x)7/26/202348－兰州§4.循环码生成多项式g(x)为了得到g(x)，需对xn+1进行因式分解对于大部分n值，xn+1仅有很少的几个因式；只有很少的几个n值，xn+1才有较多因式设g(x)·h(x)=xn+1或g(x)·h(x)≡0mod(xn+1)以（7，3）循环码为例，n=7x7+1=(x+1)(x3+x2+1)(x3+x+1)7/27/202349－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码生成多项式g(x)7/26/202349－兰州§4.循环码生成多项式g(x)n=7，x7+1=(x+1)(x3+x2+1)(x3+x+1)循环码dming(x)h(x)(7,6)2x+1(x3+x2+1)(x3+x+1)(7,4)3x3+x2+1(x+1)(x3+x+1)x3+x+1(x+1)(x3+x2+1)(7,3)4(x+1)(x3+x+1)x3+x2+1(x+1)(x3+x2+1)x3+x+1(7,1)7(x3+x2+1)(x3+x+1)x+1显然，(7，3)、(7，4)循环码互为对偶码.7/27/202350－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码生成多项式g(x)循环码dming(x)h(x§4.循环码生成矩阵GC(x)=u(x)·g(x)

=(uk-1xk-1+uk-2xk-1+…+u1x+u0)·g(x)=uk-1xk-1g(x)+uk-2xk-2g(x)+…+u0g(x)

=u·G根据u的不同取值可求得(n,k)循环码的所有2k个码字，但这样所得到的码并非系统码。7/27/202351－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码生成矩阵G7/26/202351－兰州大学信息§4.循环码生成矩阵G为了进一步得到系统码，可作如下运算：xn-ku(x)=Q(x)g(x)+r(x)C(x)=xn-ku(x)+r(x)=Q(x)g(x)+r(x)+r(x)=Q(x)g(x)构造系统循环码：只需将信息码多项式升(n-k)阶，然后以g(x)为模求余，所得余式即为监督码多项式——“除法求余”过程7/27/202352－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码生成矩阵G7/26/202352－兰州大学信息§4.循环码例如：已知(7,4)系统码的生成多项式为g(x)=x3+x2+1，求其生成矩阵。解：由先求出7/27/202353－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码例如：7/26/202353－兰州大学信息科学§4.循环码监督矩阵H由于xn+1=g(x)·h(x)生成多项式g(x)=gn-kxn-k+…+g1x+g0监督多项式h(x)=hkxk+…+h1x+h07/27/202354－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码监督矩阵H7/26/202354－兰州大学信息§4.循环码例如，已知(7,3)系统循环码的生成多项式g(x)=x4+x3+x2+1，求生成矩阵G及监督矩阵H。解：由g(x)·h(x)=x7+1的关系可得：h(x)=x3+x2+1=h3x3+h2x2+h1x+h0根据前例方法先计算rn-i(x)≡[xn-i]modg(x)可得7/27/202355－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码例如，已知(7,3)系统循环码的生成多项式g(§4.循环码编码器循环码的特点一：可以采用反馈线性移位寄存器实现编码和伴随式计算以g(x)=x3+x+1的（7，4）循环编码器为例D0D1D2++门输入u(x)·xn-k12码字输出7/27/202356－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码编码器D0D1D2++门输入u(x)·xn-§4.循环码编码器以g(x)=x3+x+1的（7，4）循环编码器为例节拍信息组输入依存状态输出码字D0(x0)D1(x1)D2(x2)0000111101200110301110410111500116000170000初态为000门开四次移位后信息1001全部输出，关门，输出开关倒向2又循环回到初始状态信息位监督位7/27/202357－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码编码器节拍信息组输入依存状态输出码字D0(x0§4.循环码译码器仍以g(x)=x3+x+1生成的（7，4）循环码译码为例复用器++门1门2+门2Y(x)s0s1s2错误图样检测电路只有1套，其译码电路比一般的(7,4)线性分组码大大简化7/27/202358－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码译码器复用器++门1门2+门2Y(x)s0s1§4.循环码(7，4)循环码d=3g(x)=(x3+x+1)(8,4)非循环码d=4(7，3)循环码d=4g(x)=(x3+x+1)(x+1)删减增扩收缩加长缩短扩展7/27/202359－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码(7，4)循环码d=3(8,4)非循环码d=4§4.循环码循环码检错——CRC(CyclicRedundancyCheck,循环冗余校验)一般能检测的错误：突发长度<n-k+1的突发错误大部分突发长度=n-k+1的错误，其中不可检出错误仅占2-(n-k-1)大部分突发长度>n-k+1的错误，其中不可检出错误仅占2-(n-k)所有与许用码组码距≤dmin-1的错误所有奇数个错误CRC码在数据通信及移动通信中得到广泛应用7/27/202360－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码循环码检错——CRC7/26/202360－§4.循环码循环码检错：——CRC(CyclicRedundancyCheck,循环冗余校验)常用的CRC码——国际标准CRC-12：g(x)=x12+x11+x3+x2+x+1CRC-16:g(x)=x16+x15+x2+1CRC-CCITT:g(x)=x16+x12+x5+1CRC-32:g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1CRC-12用于字符长度为6bit情况，后三种用于8bit字符。7/27/202361－兰州大学信息科学与工程学院电信、通信工程系－§4.循环码循环码检错：——CRC7/26/202361CRC校验示例待校验数据：1101,0110,11g(x)=x4+x+1,即10011

1101011011

00001001111000010101001110011100110000101101001110100100111110余数∴传送序列T(x)=1101,0110,11

11,10待发送的原数据校验码7/27/202362－兰州大学信息科学与工程学院电信、通信工程系－CRC校验示例待校验数据：1101,0110,11CRC接收端的处理过程假设收到序列R(X)=1101,1110,1111,10≠T(x)(出错)

仍然用g(x)=x4+x+1,即10011做除数110111101111101001111001011001001110001100111010110011110111001110001100111010非0余数表示有错7/27/202363－兰州大学信息科学与工程学院电信、通信工程系－CRC接收端的处理过程假设收到序列R(X)=1101,111接收端的处理过程（续）假设收到序列无误，则有R(X)=T(X)=1101,0110,1111,10仍然用g(x)=x4+x+1,即10011做除数110101101111101001111000010101001110011100110010111100111001110011

000000余数为0表示正确接收7/27/202364－兰州大学信息科学与工程学院电信、通信工程系－接收端的处理过程（续）假设收到序列无误，则有11§5.卷积码卷积码是非分组码的典型代表，亦称连环码。它是1955年由埃里亚斯（Elias）最早提出。与分组码的主要差异：卷积码编码器有记忆，在任意给定的时段，编码器的n个输出不仅与此时段的k个输入有关，而且与前m个输入有关卷积码记为（n，k，m）n为输出码元数k为输入码元数m为编码器的存储器数7/27/202365－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码卷积码是非分组码的典型代表，亦称连环码。7/2§5.卷积码卷积码编码串并转换….有限状态的有记忆系统（最大延迟为m）….并串转换输出码字序列C输入信息序列uu①c①u②c②描述时序网络的方法解析表示法离散卷积法、生成矩阵法、码多项式法图形表示法状态图法、树图法、格图法7/27/202366－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码卷积码编码串….有限状态的有记忆系统….并输出§5.卷积码卷积码编码现以一个二元（2，1，3）卷积码为例输入信息序列u=(u0u1u2…)++输出码字序列c=(c0①

c0②c1①

c1②

c2①

c2②

……)

g①有限状态的有记忆系统k=1，即一个输入位n=2，即两个输出位m=3，即三级移位寄存器输出c①=u*g①=(c0①c1①c2①…)输出c②=u*g②=(c0②

c1②

c2②…)g

②7/27/202367－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码卷积码编码输入信息序列u=(u0u1u2…)+§5.卷积码卷积码编码——离散卷积法以一个二元（2，1，3）卷积码为例由图可知g1(x)=1+x2+x3

→g①=(1011)

g2(x)=1+x+x2+x3

→g②=(1111)设u=(10111)，则有

c①=(10111)*(1011)=(10000001)

c②=(10111)*(1111)=(11011101)最后输出的码字为c=(1101000101010011)生成序列7/27/202368－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码卷积码编码——离散卷积法生成序列7/26/20§5.卷积码生成矩阵G——生成矩阵法理论分析g0①g0②g1①g1②g2①g2②g3①g3②0

00g0①g0②g1①g1②g2①g2②g3①g3②0G=00g0①g0②g1①g1②g2①g2②g3①g3②……………生成矩阵G是一个半无限的矩阵编码方程的矩阵形式：c=u·G7/27/202369－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码生成矩阵G——生成矩阵法理论分析g0§5.卷积码生成矩阵G已知u=(10111),求得g①=(1011),g②=(1111)

代入公式，可求得

11011111

0

000011011111000001101111100000110111110000011011111

C=u·G=(10111)=(1101000101010011)7/27/202370－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码生成矩阵G已知u=(10111),求得§5.卷积码码多项式表达式——工程应用u=(10111)=1+x2+x3+x4g①=(1011)=1+x2+x3g②=(1111)=1+x+x2+x3

则卷积码输出为：c①=(1+x2+x3+x4)(1+x2+x3)=1+x7=(10000001)c②=(1+x2+x3+x4)(1+x+x2+x3)=1+x+x3+x4+x5+x7=(11011101)输出序列为

C=(1101000101010011)7/27/202371－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码码多项式表达式——工程应用u=(10111)§5.卷积码状态图法描述现以（2，1，2）卷积码为例：k=1，n=2，m=2总的可能状态数为2km=22=4种，即00,10,01,11每次可能的输入有两个即2k=2每次可能的输出状态也只有两个状态图的画法圆圈中的数字——状态状态之间的连线和箭头——转移方向（分支）分支上的数字——转移时输出的码字括号中的数字——转移时输入的信息数字7/27/202372－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码状态图法描述7/26/202372－兰州大学信§5.卷积码状态图法（2，1，2）卷积码为例：（2，1，2）卷积码状态转移图0011100111(1)01(1)01(0)11(0)10(0)00(1)00(0)10(1)7/27/202373－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码状态图法（2，1，2）卷积码状态转移图0011§5.卷积码树图法按时间展开l=0l=1l=2l=3l=4l=5l=6l=7l节点级数树根0分支1分支a00110000001111100111100110010011011011000110001110010011011000110011优点：时序关系清晰对每一个信息输入序列有且仅有一个不重复的树枝结构相对应缺点：进行到一定时序后，状态重复且树图越来越复杂7/27/202374－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码树图法l=0l=1l=2l=3l=4l=5l=§5.卷积码树图法l=0l=1l=2l=3l=4l=5l=6l=7l节点级数树根0分支1分支a00110000001111100111100110010011011011000110001110010011011010011100C=(1110000110011100)输入序列为u=(10111000)7/27/202375－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码树图法l=0l=1l=2l=3l=4l=5l=§5.卷积码格图法（篱笆图）二维状态l=0l=1l=2l=3l=4l=5l=6l=7l节点级数a=00b=10c=01d=110000000000000011111111111110011001011010100111000110011011110110010000111100在l=3时状态abcd呈现重复图示说明：输入为0所走的分支输入为1所走的分支C=(11100001100111)所对应的路径7/27/202376－兰州大学信息科学与工程学院电信、通信工程系－§5.卷积码格图法（篱笆图）l=0l=1l=2l=3l=4§5.卷积码卷积码的译码代数译码（略）概率译码——最