信息论-基础理论与应用第三版(傅祖芸)-第9章-讲义.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第9章 信道的纠错编码,差错控制的基本形式,纠错码分类及其基本概念,线性分组码,*循环码,*卷积码,香农第二定理指出，只要信息传输率小于信道容量，通过适当的编译码方法，就能以任意小的错误概率传输信息。但从实际工程看，并没有指出具体的编译码方法。,这正是,信道纠错编码,要解决的问题。,1,香农第二定理指出，在信道中以信息传输率R小于信道容量条件下，使差错概率尽可能小的,信道编译码原则,是：,编码原则,：,在n次扩展信道输入符号序列中选取M个作为码字构成一组码C，并尽量使选取的M个码字中两两不相同码字的汉明距离尽可能地大；,译码原则,：,当收到符号序列后，翻译成与之汉明距离最近的码字（最大似然准则）。,几十年来，基于香农编码定理和以上编译码原则，科技工作者们开发了很多具有,纠错能力的信道编码,，如线性分组码、循环码、BCH码、卷积码、TCM码、Tuobo码等，在通信系统中得到了广泛应用。,2,9.1 差错控制的基本形式,现代数字通信系统中，利用检错和纠错的编码技术，使得信道编译码具备一定的差错控制能力。主要方式有：,1、前向纠错(FEC)方式,：,发送端信道编码器将信息码组编成具有一定,纠错能力,的码。,接收端信道译码器对接收码字译码，若传输中产生的差错数目在码的纠错能力之内，译码器对差错进行,定位,并加以,纠正,。,发送端,接收,端,可检错纠错的码,FEC,检错、纠错,3,FEC 特点,单向控制，不需要反馈信道；时延小，实时性好。,为适应较差信道，冗余码元多，编码效率低，译码设备复杂。,有一定的纠错范围限制。,适用于容错能力强的语音、图像传输；不适合容错能力弱的数据通信网。,2、反馈重发(ARQ)方式（检错重发方式）：,发送端,发送的是能够,发现（检测）,错误的码；,接收端,收到信道传输来的码后，译码器依据该码编码规则，判决出当前码字传输是否出错，并把,判决结果,（应答信号）反馈至发送端。发送端把接收端认为有错的信息,重新发出,，直到接收端认为正确为止。,4,发送端,接收端,可检错的码,ARQ,应答信号,检错、不纠错,ARQ特点,需要双向控制和反馈信道。,系统的控制设备和存储设备复杂，但编译码设备较简单。,接收端检错能力、系统纠错能力强，可大大降低系统误码率。,具有自适应性。但若重发频繁，将使效率降低，甚至系统阻塞，使得连续性和实时性变差。,在短波、有线干扰情况复杂的信道，在计算机网络、分组交换网、卫星通信、移动通信中广泛应用。,5,3、混合纠错(HEC)方式：,前向纠错FEC+反馈重发ARQ,发送端发送的是兼有,检错和纠错能力,的码；接收端收到码字后，首先检测错误情况。当差错在码的纠错能力范围内，就自动纠错；当差错很多已经超出了纠错能力，但能够检测到错误，接收端就通过反馈信道，请求重发。,发送端,接收端,可检错和纠错的码,HEC,应答信号,检错、纠错,HEC的特点,总体性能介于FEC和ARQ之间，误码率低，但需要反馈信道。,实时性和连续性好。,设备不太复杂，应用广泛。,6,4、信息反馈(IRQ)方式(回程校验方式),:,接收端,收到信道传输来的码后，全部由反馈信道发回发送端；,发送端,将发送的码与反馈回的码进行比较，发现错误后，把出错的码再次重发，直到接收端认为正确为止。,发送端,接收端,消息（不编码）,IRQ,消息,不检错、纠错,IRQ特点：,需要双向控制，需要反馈信道。,系统的控制设备和存储设备相对复杂。,无需编译码设备，接收端不具备检、纠错能力强，整体系统纠错能力强，可大大降低整个系统误码率。,具有自适应性，但若重发频繁，将使传输效率降低，甚至系统阻塞，使得连续性和实时性变差。,7,5、检错删除：,接收端,发现错码后，立即将其删除。,适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。,6、差错隐藏：,在某些应用领域，如音乐、语音、图像、视频等领域，有差错或损失的部分数据对人的主观感受影响不大，此时，可根据已接收的数据采用内插或外推的技术，得到满足应用的输出数据。,8,9.2 纠错码分类,1、纠错码的分类：,按纠正错误的类型分类：,纠随机差错码：,无记忆信道中，噪声随机独立地影响每个码元，造成了随机差错；,纠突发差错码：,有记忆信道中，突发噪声可造成突发性的成群差错（如太阳黑子、雷电等引起）,。,纠混合差错码,按应用目的分类：,检错码,只能检测错误是否存在。,纠错码,能够检测错误，并能够自动纠正错误。,纠删码,能够纠正删除（丢失）了的信息。,9,按码元取值分类：,二元纠错码,目前最常用模式,多元纠错码,按码的结构中对信息序列的处理方式分类：,分组码（n,k）,将信息序列每k位分组，再增加入r=n-k 个冗余码元（校验元），校验元只由本组k个信息元按照一定规律产生，与其他信息组无关。,卷积码（n,k,0,L）,将信息序列每 k,0,位分组，编码器输出该段的r=n-k,0,个与本组和前L组信息元相关的校验元，得到n长的码字。,10,按码的数学结构中校验元与信息元关系分类：,线性码,线性关系，如线性方程组,非线性码,非线性关系,按码的是否具有循环性分类：,循环码,分组码中任一码字的码元经过循环移位后，仍是本码中的码字。,非循环码,至少有一个码字经循环移位后，不再是本码中的码字。,按构造码的数学理论分类：,代数码,近世代数，比较完善，如线性分组码。,几何码,投影几何学,算术码,数论，高等算术,组合码,排列组合，数论,11,实际的码可能同时分别具备以上某些特征，比如：某一纠错码可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代数码等。,12,9.3 纠错码的概念及其纠错能力,信息序列,码字序列,接收序列,译码后信息序列,噪声源,E 错误图样,13,对编码器的输入信息序列，每k个信息符号分成,信息组,：,m,=（,m,k-1,m,k-2,m,0,），,m,i,为,信息元,（i=0,1,k-1）。,（在q元数字通信系统中，共有 种信息组。）,码字,：,为了纠错，编码器按一定规则增加产生r个多余符,号，形成长度为 n=k+r 的序列,：,C=(c,n-1,c,n-2,c,0,),c,i,为,码元,（i=0,1,n-1）,校验元,：,增加的,r=n-k,位码元,。,n：码长；k：信息组长度；r：校验元的位长。,1、信息元、校验元、码字：,14,码C中的码字个数（k为信息位数）：,（n,k）分组码：,编码器输出为 个码字组成的序列；,许用码字,：种码符号序列中，取出 个作为分组码的码字。,禁用码字,：其余 种码符号序列。,卷积码（n,k,0,L）:,编码器输出的校验元不仅由本组信息元有关，也与其前面若干段的信息组所确定。,k,个信息位,r,个监督位,a,n,-1,a,n,-2,.,a,r,a,r,-1,a,n,-2,.,a,0,t,码长,n,=,k,+,r,分组码的结构,15,2、码字的汉明重量：,汉明距离,D(C,1,C,2,)：对应位置上不同码元的个数。,码的最小距离,：d,min,d(C),汉明重量（汉明势）,：码字中非零码元的个数 W(C)。,对2元码，汉明重量为码字中的,“,1,”,的个数。因此，二,元码字的汉明重量和汉明距离为：,模2加，若对应位不同则为1；相同则为0。,其重量即为不相同的总位数，也就是两个码字的汉明距离。,16,3、错误图样：,码字序列通过信道传输送入译码器之前，由于信道的,噪声干扰，使得接收序列中某些码元发生差错，可用,错误,图样,（,差错图样,）定量描述：,E=(e,n-1,e,n-2,e,1,e,0,)=CR,二元数字通信系统中，码元传输错误图样：,E=(e,n-1,e,n-2,e,1,e,0,),e,i,=0,1,i=0,1,n-1,若,e,i,=0 ，第i位码元无差错；,若,e,i,=1，第i位码元发生差错；,17,差错关系,：,接收序列=许用码字+错误图样,R=(r,n-1,r,n-2,r,1,r,0,),r,i,=0,1,i=0,1,n-1,接收序列长度=码字长度=错误图样长度=n,差错类型：,随机差错,是相互独立的、不相关，存在这种差错的信道是无记忆信道或随机信道；,突发差错,指成串出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串码元。,18,例,发送码字 C=010110111,接收序列 R=001110011,错误图样 E=C+R=011000100,若为,随机差错,，错误码元为：2，3，7，错误数量=W(E)=3；,若为,突发差错,，错误码元串长度为：6；,出错范围：从错误图样E中的第一个1到最后一个1，其错误串中的0表示该位码元未发生错误。,19,BSC（二元无记忆对称信道）的错误图样的出现概率,设p为错误概率(1),则n次无记忆扩展信道中，,随机差错,的某错误图样E的出现概率为：,0位差错（全对）：W(E,0,)=0，,1位随机差错：W(E,1,)=1,2位随机差错：W(E,2,)=2,e位随机差错：W(E,e,)=e,n位差错（全错）W(E,n,)=n,差错图样数,概率,20,错误图样的,总数,：,发生,多位错误的概率,小于,较少位数,随机错误的概率。,因此，,无记忆信道,中，一般优先纠正较少位数的随机错,误，如1-2位，此时的误码率就可下降几个数量级。,错误图样出现的,概率关系,（p1）：,21,4、分组码的纠错能力与码最小距离的关系,一般地，分组码的码间最小距离 dmin 越大，意味着任,意码字间的差别越大，则码的检、纠错能力越强。,检错能力,：,如果一个分组码能检出,总位数,e,个码元,的任何错误图样，称码的,检错能力为,e。,纠错能力,：,如果分组码能纠正,总位数,t,个码元,的任意错误图样，称码的,纠错能力为,t,。,22,例,重复码（3，1）为：（000，111），最小码间距为3。,两个码字在传输后发生1位错误的接收序列形成两个互不相交的子集，按照,最小距离译码准则,，就能纠正1位随机错误。若发生2-3位错误，则接收序列进入另一个子集内，无法纠正。,(0,0,0),(0,0,1),(1,0,1),(1,0,0),(1,1,0),(0,1,0),(0,1,1),(1,1,1),a,2,a,0,a,1,23,定理,：对于一个（n,k）分组码,C,，最小距离为,d,min,，则：,若能检测（发现）e个随机错误，则要求,d,min,e+1,;,或：可检测出任意小于等于 e=d,min,1个随机差错；,若能纠正 t 个随机错误，则要求,d,min,2t+1,;,或：可纠正任意小于等于 t=INT(d,min,-1)/2个随机差错；,若能纠正 t 个随机错误，同时能检测e t 个随机错误，则要求：,d,min,t+e+1,。,24,设V,U为距离最小的两个许用码字。若某码字传输发生错误，按最小距离准则译码，为了检测 R=U+E：,须d,min,e+1，否则，会发生码字译码混淆，如 R+E=V。,e,V,U,d,min,d,min,=4,码距和检错能力关系示意图,25,t,V,U,d,min,图,d,min,=5,码距和纠错能力关系示意图,设V,U为距离最小的两个许用码字。若某码字传输发生错误，按最小距离准则译码.,若 R=V+E，W（E）=t，则若 dmin 2t+1,则可能译码为 U。错误！,当 dmin 2t+1，D（R，V）,k,)码字，其中(,n,k,)个附加码元是由信息码元的,线性运算,产生的。,对于二元码，信息码组长,k,位，有 2,k,个不同的信息码组，则有 2,k,个码字与它们一一对应。,29,2、一致监督（校验）方程,编码方法：已知信息码组k位信息位，按预定规则生成 r 个监督（校验）码元，与信息位一起构成码字。,要求：每个监督元是其中某些信息元的运算结果。,（以下仅讨论二元码）,例,：,k,=3,r,=4，构成,(7,3)线性分组码,。设码字为,(,C,6,C,5,C,4,C,3,C,2,C,1,C,0,),其中，,C,6,C,5,C,4,为信息元，,C,3,C,2,C,1,C,0,为监督元，码元取0或1。,监督元可按下面方程组计算,30,一致监督（校验）方程,由确定信息元得到监督元规则的一组方程。由于所有码字都按,同一规则,确定，又称为一致监督（校验）方程。,线性分组码,若一致监督方程是,线性,的，监督元和信息元之间是线性运算关系，所以由监督方程所确定的分组码是,线性分组码,。,信息组,对应码字,0 0 0,0 0 0 0 0 0 0,0 0 1,0 0 1 1 1 0 1,0 1 0,0 1 0 0 1 1 1,0 1 1,0 1 1 1 0 1 0,1 0 0,1 0 0 1 1 1 0,1 0 1,1 0 1 0 0 1 1,1 1 0,1 1 0 1 0 0 1,1 1 1,1 1 1 0 1 0 0,前例,31,3,、一致监督（校验）矩阵,为了运算方便，,可,将监督方程写成矩阵形式。,前例,：,32,推广：,一般情况，对,(,n,k,),线性分组码，每个码字中的,r,(,r,=,n,k,),个监督元与信息元之间的关系可由如下,r*n,阶,线性方程组确定：,则：,令：,33,若用h,i,(i=n-1,n-2,1,0)表示H矩阵中的,列矢量,，则H可写为：,H矩阵的,每一行元素,是线性方程组中一个方程的系数，由它来唯一确定每一个校验元。因此，H中,每一行必须是线性无关,的，且必定有：,r=nk,行。,34,4、生成矩阵,根据（n,k）线性分组码的一致监督方程出发，将,信息组信息位,与,生成的码字,之间的生成关系用矩阵来表示，就可得到,生成矩阵。,例,前例中，,35,生成矩阵G,1,其各行为码字，互不相关。,其他码字为此三个码字的线性组合方式生成。,信息组,对应码字,0 0 0,0 0 0 0 0 0 0,0 0 1,0 0 1 1 1 0 1,0 1 0,0 1 0 0 1 1 1,0 1 1,0 1 1 1 0 1 0,1 0 0,1 0 0 1 1 1 0,1 0 1,1 0 1 0 0 1 1,1 1 0,1 1 0 1 0 0 1,1 1 1,1 1 1 0 1 0 0,36,推广,：对一般(,n,k,)线性分组码，设有一组k个,线性独立的码字，,由此一组线性独立的码字以行向量构成的矩阵，称为线性分组码的,生成矩阵G,（k*n阶）：,满足：,37,G中每一行及其线性组合都是,许用码字,，故有：,线性分组码的所有码字都可由其生成矩阵或一致校验矩阵求得。当已知G、H中的一个，就可求另一个。,系统码：,信息元以不变形式出现在码字的任意k位上。,标准生成矩阵：,生成矩阵能把信息元保留在各码字的,最左边k位,上。,38,因此，,标准系统生成矩阵,G应满足如下形式：,其与H矩阵之间的转换关系：,若非标准系统码，则G与H之间元素需要由方程组确定。,39,(略)生成矩阵之间的关系,对于二元（n,k）分组码，在2,k,个码字中，k个,独立码字组,不止一个。对于同一码，选择不同的独立码字组构成生成矩阵G也不相同。但经过若干次,初等变换,，可变成等价的,标准生成矩阵,。,例,一个二元（7，3）码,生成矩阵为：,信息组,000,001,010,011,100,101,110,111,码字,000,0000,111,0100,101,0011,010,0111,100,1110,011,1010,001,1101,110,1001,生成的码字为：,40,信息组,000,001,010,011,100,101,110,111,码字,000,0000,111,0100,101,0011,010,0111,100,1110,011,1010,001,1101,110,1001,码字集合完全相同。,但生成矩阵G1、G2选取了不同的独立码字构成。,生成矩阵,可以经过初等行变换,得到其,标准生成矩阵,。,比较：生成矩阵G,2,产生的码（非系统码）,比较：生成矩阵G,1,产生的码（系统码）,41,2行+3行=2行,1行+2行=3行,标准生成矩阵,42,5、线性分组码性质与纠错能力,1）（n,k）线性分组码由生成矩阵G或校验矩阵H确定。,它们满足：,2）封闭性。（n,k）码中任意两个码字之和仍为许用码字，即：,43,3）含有零码字。,n位长的零矢量为（n,k）线性分组码的许用码字。,（因为满足 ）,4）所有许用码字可由其中k个独立码字（基底）线性组合而成。,在 个许用码字中，k个独立许用码字不止一组。它们可构成生成矩阵G。,5）码的最小距离等于非零码字的最小重量。即：,因为：,44,定理,设（n,k）线性分组码C的校验矩阵为,H,，则码的最小距离为,d,的,充要条件,为：,H,中任意,d-1,个列向量线性无关，且有,d,个列向量线性相关。,（提供了构造最小距离为d的线性分组码的思路。）,任何3列相加均非0，,而最少的相关列数为4：,如：从右向左第0，1，2，5之和为0，相关。,故，码最小距离为：4,由此可知：,当所有,列向量相同,，而排列位置不同的,H,矩阵所对应的分组码，具有相同的,最小距离,，则它们在纠错能力和码率上等价。,对于分组码来说，由于可以进行,初等变换,进行等价变换，,系统码,和,非系统码,的纠错能力是相同的，而系统码的编译码比非系统码简单，且,G、H,矩阵可方便互求，因此，一般只需讨论系统码。,例,45,6,、线性分组码的纠错与伴随式,：,接收到一个序列,R,后，校验,H,R,T,=0,T,是否成立：,若关系成立，则认为,R,是一个码字；,否则判为码字在传输中发生了错误；,伴随式（,/,监督子,/,校验子）,：,S=R,H,T,或,S,T,=H,R,T,如何纠错？,设发送码矢,C=(c,n,1,c,n,2,c,0,),信道错误图样为,E=(e,n,1,e,n,2,e,0,),，,其中,e,i,=0,，表示第,i,位无错；,e,i,=1,，表示第,i,位有错。,i=n,1,n,2,0,。,46,接收序列,R,：,R,=(,r,n,1,r,n,2,r,0,)=,C,+,E,=(,c,n,1,+e,n,1,c,n,2,+,e,n,2,c,0,+,e,0,),接收序列的伴随式（接收字用监督矩阵进行检验）,S,T,=H,R,T,=H,(C+E),T,=H,C,T,+H,E,T,由于,H,C,T,=0,T,，所以,S,T,=H,E,T,或,S=E,H,T,即：,分析,：,47,对于2元码，,e,i,=0，1，伴随式是,H,矩阵中对应,若干列向量之和,。（1位错，多位错）,例,：已知(7,3)码的一致校验矩阵。,设发送码矢,C,=1010011。,若传输时没有差错，,E,0,=（0000000），,则接收码字,R,1010011=C，,R,与,C,相同：,S,0,=,E,0,H,T,=,（0000）没有错误；,若传输时差错图样为 E,00,=C=1010011，,则,R,0000000，,S,00,=,E,00,H,T,=,（0000），无法发现此错误；,48,若,发送码矢C,1,=0100111,，,C,2,=1101001，,错误图样 E,1,=（1000000），,接收码字 R,1,1100111，R,2,0101001；,伴随式,S,1,=R,1,H,T,=E,1,H,T,=,（1110），,S,2,=R,2,H,T,=E,2,H,T,=,（1110），,可见：,S,1,=S,2,0,；不为0，译码器判断有错误；,第1位错误，刚好对应于H矩阵的第1列向量；,伴随式与发送码字无关，只与错误图样有关。,49,当,错误图样,E,3,=（0010000），,可得：,S,3,=E,3,H,T,=（1101），,刚好为H矩阵的第3列向量。,依此类推：,当发生1位错误时，当i位错误发生在第i位，其伴随式,正好是H矩阵中的第i列向量。,若传送时发送2位码元错误，设 E,=（1010000）=,E,1,+,E,3,，,伴随式 S,=E,H,T,=（E,1+,E,3,）,H,T,=,E,1,H,T,+E,3,H,T,=,（0011），,可见：,S,不同于H中的任何一列，说明发生了不止一位错误；,可能是第1、第3位错误；,但若错误图样,E,=（0100100）或（0000011），,其伴随式仍为（0011），译码器无法判断错误的位置，故无法纠正2位的随机差错。,50,若,错误图样 E,=（0110100），可得：S=E,H,T,=（1110）=S,1,，刚好为H矩阵的第1列向量。,由此：,此（7，3）码可发现3位随机错误，但当发生1位错误时，无法纠正；或者相反。,H矩阵：任意小于等于3列线性无关，而最少4列就线性相关，故其,最小,码距,d,min,=4,故可纠正1位错误的同时检测出2位错误，或检测3位错误。,51,本章习题,9-1 9-3 9-4,52,7、标准阵列译码,传输中错误图样,E,不同时，有可能对应相同的伴随式。,当信道译码器接收到接收序列R后，由下式求解E：,S,=R,H,T,=,E,H,T,但是，此式中对应的错误图样可以有,2,k,个解。,一般采用,最大似然准则译码,（输入码元等概分布），其译码错误概率最小，正确译码概率最大。,在,BSC,信道中，重量最小的E,*,，其发生的概率最大，则：,P(C+E,*,|C)=P(E,*,)P(C+E|C),EE,*,因此，用伴随式译码时就采用最大似然准则（最小距离译码准则），选取重量最轻的E作为译码的错误图样。,53,实际译码中，根据,R,H,T,=,S,=E,H,T,找出重量最轻的E的译码,方法及其繁琐。一般采用标准阵列译码方法。,标准阵列译码方法：,发送码字：取自由 2,k,个码字构成的集合,C,；,接收序列：可以是 2,n,个,n,长序列中任一个矢量；,把 2,n,个,n,长序列划分为 2,k,个互不相交的子集 ，并按照最大似然译码准则，使得在每个子集对应一个许用码字；,根据码字和子集间一一对应关系，若接收矢量,R,落在子集,D,l,中，就把,R,l,译为子集,D,l,对应的码字,C,l,。,因此 当接收序列,R,与实际发送码字在同一子集中时，译码就是正确的。,54,标准阵列表的构造：,先将,2,k,个许用码字排成一行，作为,标准阵列,的第一行，并将全,0,码矢,C,0,=(000),放在最左面的位置上；,然后在剩下的,(2,n,2,k,),个,n,长序列中选取一个重量最轻的重,E,1,放在全,0,码矢,C,0,下面，即第,2,行首位；再将,E,1,分别和所有许用码字相加：,C,i,+,E,1,，放在对应码字下构成阵列第二行；,在第二次剩下的,n,长序列中，选取重量最轻的,n,重,E,2,，放在,E,1,下面，并将,E,2,分别加到第一行各许用码字上,C,i,+,E,2,，得到第三行；,，继续这样做下去，直到全部,n,重用完为止。得到,(,n,k,),线性码的标准阵列。,55,E,0,=S,0,E,0,+C,0,=0,E,0,+C,1,=C,1,E,0,+C,j,=C,j,E,0,+C,2,k,-1,=C,2,k,-1,E,1,=S,1,E,1,+C,0,=E,1,E,1,+C,1,E,1,+C,j,E,1,+C,2,k,-1,E,2,=S,2,E,2,+C,0,=E,2,E,2,+C,1,E,2,+C,j,E,2,+C,2,k,-1,.,.,.,.,E,2,n-k,-1,=S,2,n-k,-1,E,2,n-k,-1,+C,0,=E,2,n-k,-1,E,2,n-k,-1,+C,1,E,2,n-k,-1,+C,j,E,2,n-k,-1,+C,2,k,-1,标准阵列表结构,伴随式,陪集首（表中每一行称为陪集）,56,标准阵列表的特点：,表中每一行称为,陪集,，该行的首位元素,E,i,在为,陪集首,，各行元素都不同；,如果把,错误图样,作为陪集首，则同一个陪集中所有的元素都队应相同的伴随式；,表中,各列,以同一组许用码字为基础，将2,n,个接收序列划分成不相交的子集合D,0,D,1,D,2,D,2,k,-1,.每个子集合D,j,对应同一个许用码字C,j,，它是每列子集的,子集首,。,57,标准阵列的译码：,列子集D,j,各元素是同一许用码字C,j,在信道中发生若干错误得到。同列中各元素对应的是不同的错误图样。,而列子集D,j,各元素是与许用码字C,j,距离最近的，与许用码字的,距离,等于错误图样E,j,在的重量W(E,j,).,由建表过程中，选取的,陪集首,都是重量为最轻的错误图样，所以，这样的列子集D,j,的划分是满足,最大似然准则的,（最小距离准则）.,58,标准阵列的译码方式：,方式1：在表中查询接收序列R，并把R所在列的子集首C,j,作为R的译码。,方式2：先求出伴随式S,找出S所在的行中的R，以R所在列的子集首C,j,作为R的译码。,表较大时，两种方式的搜索时间差别也较大。,59,例,设（5，2）系统线性码的生成矩阵为,构造该码的标准阵列译码表。,信息组为（00）（01）（10）（11），由,C=m G,可求出相应码字。,同时，可得到校验矩阵（用于计算伴随式）：,伴随式个数：(2,n,2,k,)=8，标准阵列表应有8行。,按照重量选择错误图样，并计算其对应伴随式，填入表中。,60,S,0,=000,伴随式,E,0,+C,0,=00000,陪集首,C,1,=10111,C,2,=01101,C,3,=11010,S,1,=111,S,2,=101,S,3,=100,S,4,=010,S,5,=001,E,1,=10000,E,2,=01000,E,3,=00100,E,4,=00010,E,5,=00001,00111,11111,10011,10101,10110,11101,00101,01001,01111,01100,01010,10010,11110,11000,11011,S,6,=011,S,7,=110,E,6,=10100,E,7,=10001,00011,00110,11001,11100,01110,01011,重量为2的错误图样的选择,：,1、根据前面6行填满后，选择未出现的重量为2的二元序列；,2、根据尚未出现的伴随式，计算出对应的错误图样，并选用之。,61,若接收序列R=（10101）,可采用两种译码方式：,1、搜索全部码表，在（5，2）位置，查询到R，则其所在列子集首为码字C,1,则将此R译码为C,1,=10111；,2、根据尚未出现的伴随式，计算出对应的错误图样。,RH,T,=S=010=S,4,在S,4,所在行查找R，则其所在列子集首为码字C,1,则将此R译码为C,1,=10111。,由阵列译码表知，此（5，2）码能够纠正所有的1位错误，以及两个2位发生图样。,62,简化译码表：,问题：,利用标准阵列译码，需要将标准阵列的2,n,个接收序列R存入存储器，译码器复杂度随着n增大而成指数增大，限制了其适用性。,简化译码表：,只构造表的第0、第1列：即S,i,与E,i,对照表，译码器只需要存储2,n-k,个长度为（n-k）的向量S,i,与2,n-k,个长度为n的错误图样E,i。,大大减少了存储量，简化了译码器。,译码方式：,先由R计算伴随式S=RH,T,然后在简化表中查找出S对应的错误,图样E，最后计算：C=R+E，C作为译码输出。,63,建立译码表的注意点：,在构造译码表时，当不等式（r 为错误图样重量）,成立时，在第1列中顺序存入重量为0，1，2，r的错误图样,E,i,由EH,T,=S求出S，放入表的第0列。,当第1列剩余位置少于 个时，才需要由S解方程EH,T,=S,求出,E，从中挑选重量为（r+1）的错误图样填入第一列剩余位置。,64,线性码可纠正的错误图样,若发送码矢为,C,j,，信道干扰的错误图样是陪集首，则接收矢量,R,必在,D,j,中；,若错误图样不是陪集首，则接收矢量,R,不在,D,j,中，则译成其它码字，造成错误译码；,当且仅当错误图样为陪集首时，译码才是正确的。,可纠正的错误图样,：,这,2,n,k,个陪集首称为,可纠正,的错误图样。,65,线性码纠错能力与监督元数目（,r=n-k,）的关系,：,一般地，任意二元,(,n,k,d,),线性码，有,2,n,k,个伴随式，能纠正小于等于,t=(d-1)/2,个随机错误。,故凡是重量不大于,t,的错误图样，都对应有,唯一确定,的,伴随式，,则伴随式的数目需满足条件：,此条件式称为,汉明限,，任何能纠正小于等于t个错误的码，都必须满足此条件。,66,上式中等式成立时的线性码称为,完备码,。即,若上式等号成立，则码的伴随式数目恰好与不大于t个差错的错误图样错误数目相等。则所有伴随式与可纠正得小于等于t个差错全部错误图样一一对应。,67,9.5,循环码,循环码是一种特殊的线性分组码，属于线性分组码的一个重要子类，也是目前研究最为透彻的一类码，大多数有实用价值的纠错码都是循环码。,循环码与一般的线性分组码相比具有以下优点：循环码的编码及译码易于用简单的具有反馈连接的移位寄存器来实现,68,1,、循环码概念,循环码,除了具备线性分组码的封闭性外，还有循环性。,信息码元,码字,0 0 0,0 0 0 0 0 0 0,0 0 1,0 0 1 1 1 0 1,0 1 0,0 1 0 0 1 1 1,0 1 1,0 1 1 1 0 1 0,1 0 0,1 0 0 1 1 1 0,1 0 1,1 0 1 0 0 1 1,1 1 0,1 1 0 1 0 0 1,1 1 1,1 1 1 0 1 0 0,69,循环码,：如果,(,n,k,),线性分组码的任意码矢,C=(c,n,1,c,n,2,c,0,),的,i,次向左或向右循环移位，所得矢量,(c,n,1,i,c,n,2,i,c,0,c,n,1,c,n,i,),仍是,(n,，,k),码一个码矢，则称此线性码为,(,n,k,),循环码。,70,把码字,C,c,n,-1,c,n,-2,c,1,c,0,与一个不大于,n,-1,次的,码多项式,C,(,x,),对应,起来。,C,(,x,)=,c,n,-1,x,n,-1,+,c,n,-2,x,n,-2,+,+,c,1,x,+,c,0,对于二进制码，,c,i,0,1,i,=0,，,n,-1,。,2,、循环码的多项式描述,循环码的描述方式有很多，但工程上最有用的是采用多项式的描述，从而可以借助代数的工具对循环码进行分析，这也是循环码能被广泛应用的原因之一。,71,设循环码字,C,1,左移一位仍为码字，多项式描述为：,则有：,左移,i,位，则有：,72,归纳可知：,移,1,位：,C,2,(x)=xC,1,(x)mod(x,n,+1),移,2,位：,C,3,(x)=xC,2,(x)=x,2,C,1,(x)mod(x,n,+1),移,i,位：,C,i+1,(x)=xC,i,(x)=x,i,C,1,(x)mod(x,n,+1),移,n-1,位：,C,n,(x)=xC,n-1,(x)=x,n-1,C,1,(x)mod(x,n,+1),73,例,：,(7,3),循环码,可由任一个码矢，比如,(0011101),经过循环移位，得到其它,6,个非,0,码矢；,也可由相应的码多项式,(,x,4,+,x,3,+,x,2,+1),，乘以,x,i,(,i,=1,2,6),，再模,(,x,7,+1),运算得到其它,6,个非,0,码多项式。移位过程和相应的多项式运算如表所示。,74,循环,次数,码字,码多项式,0 0 0 0 0 0 0,0,0 0 1 1 1 0 1,1,0 1 1 1 0 1 0,2,1 1 1 0 1 0 0,3,1 1 0 1 0 0 1,4,1 0 1 0 0 1 1,5,0 1 0 0 1 1 1,6,1 0 0 1 1 1 0,75,