第五章纠错编码.ppt

1、第五章 纠错编码,1,第五章 纠错编码,5.1 纠错编码的基本概念 5.2 线性分组码 5.3 循环码 5.4 卷积码,2,5.1 纠错编码的基本概念,5.1.1 纠错编码的任务 5.1.2 纠错编码的分类 5.1.3 译码准则 5.1.4 香农第二定理,3,4,5.1 信道编码的任务,5.1 信道编码,5,信源编码 提高数字信号有效性 将信源的模拟信号转变为数字信号 降低数码率,压缩传输频带(数据压缩) 信道编码 提高数字通信可靠性 数字信号在信道的传输过程中,由于实际信道的传输特性不理想以及存在加性噪声,在接收端往往会产生误码。,5.1 信道编码的任务,6,信道编码：就是按一定的规则给信源

2、输出序列增加某些冗余符号，使其变成满足一定数学规律的码序列（或码字），再经信道进行传输。（提高传输的可靠性） 信道译码：就是按与编码器同样的数学规律去掉接收序列中的冗余符号, 恢复信源消息序列。 一般地说，所加的冗余符号越多，纠错能力就越强，但传输效率降低。因此在信道编码中明显体现了传输有效性与可靠性的矛盾。,编码信道模型,7,消息,编码信道模型,噪声源,错误图样E,编码信道模型,8,消息序列m总以k个码元为一组传输，称k个码元的码组为信息码组。 信道编码器按一定规则对每个信息码组附加一些多余的码元，构成长为n个码元的码组c（信道编码）。 附加的r=n-k个码元称为监督码元,错误图样,9,为了

3、定量描述信号的差错，使用差错图样表示发送和接收码之“差”，设发送的码为C，接收码为R，对于M进制码，差错图样E为E=(CR)(modM)对于二进制码而言，减法运算就是模2加法运算，于是有,例如:C=10000,E=01000,R=? R=(11000),10,5.1 信道编码的任务,10,检错与纠错原理,0:晴,1:雨 若10,01。收端无法发现错误,00晴,10,01,11,00,11雨,能发现 一个错误,禁用码组,插入1位监督码后具有检出1位错码的能力,但不能予以纠正。,11,5.1 信道编码的任务,11,000晴,010,001,111,000,111雨,晴,在只有1位错码的情况下,可以

4、判决哪位是错码并予以纠正,可以检出2位或2位以下的错码。,100,011,101,110,雨,检错和纠错方式,12,自动请求重发(ARQ)： 发端发送检错码， 收端译码器判断当前码字传输是否出错； 当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字(全部或部分)。,优点： 编译码设备比较简单。 在一定的多余度码元下，系统具有极强的纠错能力。 能获得极低的误码率。 由于检错码的检错能力与信道干扰的变化基本无关，因此这种系统的适应性很强，特别适应于短波、 散射、 有线等干扰情况特别复杂的信道中。,ARQ,缺点： 控制电路比较复杂。 传送消息的连贯性和实时性较差。由于反馈重发的次数与信道干

5、扰情况有关，若信道干扰很频繁，则信道经常处于重发消息的状态。,ARQ,检错和纠错方式,前向纠错(FEC)： 发送端的信道编码器将信息码组编成具有一定纠错能力的码。 接收端信道译码器对接收码字进行译码,若传输中产生的差错数目在码的纠错能力之内时,译码器对差错进行定位并加以纠正。,优点： 不需要反馈信道，能够实现一对多的同步广播通信，而且译码实时性好，控制电路也比ARQ简单。随着编码理论的发展和大规模集成技术的发展，复杂算法的译码设备越来越简单，成本越来越低，所以这种方式在实际中得到越来越广泛的应用。,FEC,缺点： 这种工作方式是假设纠错码的纠错能力足够纠正信息序列传输中的错误，也就是纠错码与信

6、道的干扰是相匹配的，所以对信道的适应性较差。 为了获得合适的误码率，往往按照信道最差的情况设计纠错码，增加的冗余码元比检错码要多，编码效率一般较低。,FEC,检错和纠错方式,混合纠错(HEC)： 是FEC与ARQ方式的结合。 发端发送同时具有自动纠错和检测能力的码组,收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。 如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。 信息反馈(IRQ)： 收端把收到的数据,原封不动地通过反馈信道送回到发端,发端比较发的数据与反馈来的数据,从而发现错误,并且把错误的消息再次传送,直到发端没

7、有发现错误为止。,优点：由于该方式避免了FEC要求的复杂设备和ARQ方式的信息连贯性差的缺点，并且可以达到较低的误码率，因此在实际中得到了广泛应用。,HEC,总结：信道编码的概念,目的：降低错误的译码概率PE 对象：信息序列 方法：信息码+附加码元，收端按照一定译码准则检纠错。 实质：增加冗余度。,20,5.1.2 信道（纠错）编码的分类,按照接收端工作状态分为： 检错码 纠错码 纠删码 根据纠正错误的类型 纠随机错误码 纠突发错误码,21,22,5.1.2 信道（纠错）编码的分类,22,随机差错： 差错是相互独立的,不相关 存在这种差错的信道是无记忆信道或随机信道 突发差错： 指成串出现的错

8、误,错误与错误间有相关性,一个差错往往要影响到后面一串字 E: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0,突发长度= 4,突发长度= 6,5.1.2 信道（纠错）编码的分类,按照发送端编码方式分为：,23,5.1.3译码准则,24,1. 信道传输模式,5.1.3译码准则,25,2. 译码规则（译码函数）,使每一种可能的输出符号bj(j=1,2,s)与一个惟一的输入符号ai(i=1,2,r)一一对应。函数F(bj)=ai即为译码函数或译码规则。,依据一定的判决准则设计一个单值函数,5.1.3译码准则,26,2. 译码规则（译码函数）,注：（1

9、）对输入符号集为X=a1,a2,ar，输出符号集为Y= b1,b2,bs的信道来说，一共可构成rs种不同的译码规则。,例：二进制对称信道，其输入符号集为X=0,1,输出符号 集为Y=0,1，则可构成rs=22=4种译码规则。 译码规则(1)：F(0)=0,F(1)=0译码规则(2)：F(0)=0,F(1)=1译码规则(3)：F(0)=1,F(1)=0译码规则(4)：F(0)=1，F(1)=1,（2） 不同的译码规则会引起不同的可靠程度。,5.1.3译码准则,27,译码常用准则则（译码函数）,最小错误译码准则（MEPD） 最大后验概率准则（MPPD） 最大联合概率准则（MJPD） 最大似然概率准

10、则（MLD）,信道输入等概时，MLD和MJPD等价,5.1.4香农第二定理,28,5.1.4香农第二定理,29,表述二：设离散无记忆信道的信道容量为C，信息传输率为R，对于任意小的正数，当RC时，存在码长为n的一组码和相应的译码规则，使得译码平均错误概率PE小于。,5.1.4香农第二定理,30,注：（1）定理指出：总能找到一种抗干扰信道编码，只要其码长N足够长，它的最小平均错误译码概率Pemin就可任意小，信道信息传输率(码率)R可无限接近信息容量C。（2）这个定理是一个存在定理，指出错误率趋于0的编码方法是存在的。（3）定理表明，在错误率趋于0的同时，还可以使R趋于C，这是具有理论指导意义的

11、。,5.2 线性分组码,31,线性分组码的编码过程分为两步： 把信息序列按一定长度分成若干信息码组，每组由 k 位组成； 编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成 n 重 (nk) 码字，其中 (nk) 个附加码元是由信息码元的线性运算产生的。 信息码组长 k 位，有 2k 个不同的信息码组，则应该有 2k 个码字与它们一一对应。,5.2.1 线性分组码的基本概念,5.2 线性分组码,32,5.2.1 线性分组码的基本概念,线性分组码：通过预定的线性运算将长为 k 位的信息码组变换成 n 长的码字 ( nk )。由 2k 个信息码组所编成的 2k个码字集合，称为线性分组

12、码。 码矢：一个 n 长的码字可以用矢量来表示 C = (Cn1,Cn2,C1,C0 ) 所以码字又称为码矢。 ( n, k ) 线性码：信息位长为 k，码长为 n 的线性码 编码效率/编码速率/码率：R=k /n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。,5.2 线性分组码,33,5.2.1 线性分组码的基本概念,线性体现在： 输入输出的关系为线性映射关系 码元中每个码字由信源做模二加运算得到 线性分组码的特点： 在码集中存在全0码字 满足封闭性,5.2 线性分组码,34,5.2.1 线性分组码的基本概念,定理：线性分组码的最小距离等于最小非零码字重量。 定理中涉及到的基本概念

13、 汉明重量：码字中非0码的个数。 最小汉明重量：码集中非0码字汉明重量的最小值。 汉明距离：两个等长码C和C中，对应位码元不同的取值个数。 最小汉明距离：码集中所有码字距离的最小值。,5.2 线性分组码,35,5.2.2 线性分组码的编码 一、生成矩阵,G 中每一行 gi = ( gi 1, gi 2, , gi n ) 都是一个码字； 生成矩阵的定义：由于矩阵 G 生成了 (n,k) 线性码中的任何一个码字，称矩阵 G 为 (n,k) 线性码的生成矩阵。 (n,k) 线性码的每一个码字都是生成矩阵 G 的行的线性组合。,5.2 线性分组码,36,5.2.2 线性分组码的编码 一、生成矩阵,标

14、准生成矩阵： 通过行初等变换，将 G 化为前 k 行和k 列是单位子阵的标准形式,5.2 线性分组码,37,5.2.2 线性分组码的编码 二、编码,线性系统分组码：用标准生成矩阵 Gkn 编成的码字，前面 k 位为信息数字，后面 r=nk 位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。 当生成矩阵 G 确定之后，(n,k) 线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。,38,举例： 已知一个 (7,4) 线性码的生成矩阵G如下图示，当输入信息码元为1010时，试求输出的码字。,由矩阵乘法规则可知： C = m G 的结果，就是矩阵 G 中，与

15、 m 中为“1”的元素相对应的行按位模 2 加的结果。,5.2.2 线性分组码的编码,39,5.2.2 线性分组码的编码,练习： 已知某线性分组码的生成矩阵为,试问： （1）n = ? k = ? , 该码组集合中的码字有多少？ （2）若信息码元 m 分别是 1100 和1111时 , 写出其对应的输出码字。,40,5.2.3 线性分组码的译码,一、一致校验矩阵,推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r(r=nk) 个监督元与信息元之间的关系可由下面的线性方程组确定,41,5.2.3 线性分组码的译码,一、一致校验矩阵,令系数矩阵为 H，码字行阵列为 C,42,5.2.3

16、线性分组码的译码,一、一致校验矩阵特性: 对H 各行实行初等变换，将后面 r 列化为单位子阵，于是得到下面矩阵(行变换所得方程组与原方程组同解)。 校验矩阵H 的标准形式：后面 r 列是一单位子阵的校验矩阵H。 H 阵的每一行都代表一个校验方程，它表示与该行中“1”相对应的码元的模2和为0。,43,5.2.3 线性分组码的译码,生成矩阵与一致校验矩阵的关系: 由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足HrnCTn1=0Tr1，则有 HrnGTnk=0Trk 或 GknHTnr=0kr 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换。,44,5.2.3 线性分组码的译码

17、,例: 已知(7,4)线性系统码的监督矩阵为,45,5.2.3 线性分组码的译码标准阵列译码,标准阵列构造方法 先将 2k 个码矢排成一行，作为标准阵列的第一行，并将全0码矢C1=(000)放在最左面的位置上； 然后在剩下的 (2n2k) 个 n 重中选取一个重量最轻的 n 重 E2 放在全0码矢 C1 下面，再将 E2 分别和码矢 相加，放在对应码矢下面，构成阵列第二行； 在第二次剩下的 n 重中，选取重量最轻的 n 重 E3，放在 E2 下面，并将 E3 分别加到第一行各码矢上，得到第三行； ，继续这样做下去，直到全部 n 重用完为止。得到下页表格所示的 (n,k) 线性码的标准阵列。,4

18、6,5.2.3 线性分组码的译码标准阵列译码,47,5.2.3 线性分组码的译码标准阵列译码,标准阵列的特性： 定理：在标准阵列的同一行中没有相同的矢量，而且 2n 个 n 重中任一个 n 重在阵列中出现一次且仅出现一次。,陪集：标准阵列的每一行叫做码的一个陪集。 陪集首：每个陪集的第一个元素叫做陪集首。,48,5.2.3 线性分组码的译码伴随式译码,伴随式和错误检测： 用监督矩阵译码：接收到一个码字 R 后，检验 HRT=0T 是否成立： HRT =0T是否成立是检验码字出错与否的依据。 若关系成立，则认为 R 是一个码字； 否则判为码字在传输中发生了错误； 伴随式/监督子/校验子：S=RH

19、T或ST=HRT。 如何纠错？ 设发送码矢 C=(Cn1,Cn2,C0) 信道错误图样为 E=(En1,En2,E0) ， 其中Ei=0，表示第i位无错； Ei=1，表示第i位有错。i=n1,n2,0。,49,5.2.3 线性分组码的译码伴随式译码,接收码字 R =(Rn1,Rn2,R0)=C+E =(Cn1+En1, Cn2+En2, , C0 +E0) 求接收码字的伴随式（接收码字用监督矩阵进行检验） ST=HRT=H(C+E)T=HCT+HET 由于HCT=0T，所以 ST=HET 设H=(h1,h2,hn)，其中hi表示H的列。代入上式得到,50,5.2.3 线性分组码的译码伴随式译码

20、,总结： 伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定； 伴随式是错误的判别式： 若S=0，则判为没有出错，接收码字是一个码字； 若S0，则判为有错。 不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式S是H 阵中与错误码元对应列之和。,51,伴随式译码举例： 某(7,3) 线性系统码 设发送码字C = 1010011，接收码字R 1010011，R与C相同。,5.2.3 线性分组码的译码伴随式译码,52,若接收码字中有一位错误,5.2.3 线性分组码的译码伴随式译码,53,5.2.3 线性分组码的译码伴随式译码,当码元错误多于1个时,54,5.2.

21、3 线性分组码的译码伴随式译码,以上定理是纠错码理论中最重要的基本定理之一，它说明了一个距离为d的线性分组码，既可用来纠正 个错误，又可用来检测e d1个错误。,55,5.2.4 汉明码,对于给定的正整数m3，二进制汉明码的信息位数量、 码字长度与m之间满足下列关系:k=2mm1 n=2n-k1所以汉明码实际就是(2m1，2mm1)分组码。 当m=3时，则为(7，4)码。,二进制汉明码的最小汉明距离为d0=3。,56,5.2.4 汉明码,例 构造m=3的汉明码。 解 由于m=3，根据汉明码的性质可知k=2mm1=4 n=2m1=7,所以m=3的汉明码是(7，4)分组码。 除了矢量0之外的所有排

22、列为(001)，(010)，(011)，(100)，(101)，(110)，(111)，为了产生系统码，将(100)，(010)，(001)放在矩阵的最后3列，得到校验矩阵为,57,5.2.4 汉明码,于是得到生成矩阵为,58,5.3 循环码,5.3.1 循环码的基本概念,数学定义：设C为某( n, k )线性分组码的码组集合，如果对C中任意一个码组c = ( an-1 an-2 a1 a0 )，它的循环移位c(1) = ( an-2an-3 a1 a0 an-1 )也属于C，则称该( n, k )码为循环码 其中c(i )表示c码组循环移位i次。 例如：某( 7, 4 )循环码组集合中的一个

23、码组为( 1000101 )，向左循环移位一次后的码组( 0001011 )仍为码组集合中第一个许用码组,59,5.3 循环码,60,5.3 循环码,61,5.3.2 循环码的描述 1、循环码多项式描述,码多项式是描述循环码的主要方法 对于任一长为n的码组 c = ( an-1 an-2 a1 a0 ) 可用一多项式来表示： c(x) = ( an-1 xn-1 + an-2 xn-2 + + a1 x1 + a0 ) 此多项式称码多项式，式中每项的各分量an-1 , an-2 , , a1 , a0是多项式的系数 系数不为零的x的最高次数为多项式c(x)的次数，或称多项式的阶数，deg c(

24、x) 例如：某码组( 1100101 )对应的码多项式可表示为 c7(x) = 1 x6+1 x5+ 0 x4 + 0 x3 + 1 x2 + 0 x +1 = x6 + x5 + x2 +1 码多项式与码组的关系：本质上是一回事，仅是表示方法的不同而已,62,1、循环码多项式描述码多项式的模运算,正整数的模运算 若一正整数M除以正整数N，所得到的商为Q，余数为R，可表示为 其中Q为整数，则在模N运算下，上式的结果为： 多项式的模运算与正整数的模运算相同，一般利用长除法计算商式和余式 有两个多项式a(x)和p(x)，一定存在有唯一的多项式Q(x)和r(x)，使得： 称Q(x)是a(x)除以p(

25、x)的商式，r(x)是a(x)除以p(x)的余式，在模p(x)运算下 且有 即：除到余式的次数小于除式为止，当能整除时次数为0,63,定理：对于( n, k )循环码，若c(x)对应码组c = (an-1an-2 a1a0 )， c(1)的一次循环移位c(1) = ( an-2an-3 a1a0 an-1 )及c(i )(x)对应的c码循环移位i次c(i )，则有： 证明：码组c的多项式为： 则有：,1、循环码多项式描述码多项式的模运算,1、循环码多项式描述码多项式的模运算,例如：(7 , 4)循环码的第12个码组c12为：1011000，则其码多项式为： c(x)=x6 + x4 + x3

26、请写出c12左循环移位3次的码组 解：i = 3，则 x3c(x) = x9 + x7 + x6 其对应码组为：1000101，它是( 7, 4 )循环码中的第4个码组c4,65,1、循环码多项式描述生成多项式,定义：记C(x)为( n, k )循环码的所有码组对应的多项式的集合，若g(x)是C(x)中除0多项式以外次数最低的多项式，则称g(x)为这个循环码的生成多项式 其一般形式为： g(x) = xr + gr-1 xr-1 + + g1 x1 + 1 g(x)具有以下性质： 1）g(x)的0次项是1； 2）循环码的每一码多项式c(x)都是g(x)的倍式，且每一个小于等于n-1次的g(x)

27、的倍式一定是码多项式； 3）g(x)的最高次为n-k，且是唯一的； 4）g(x)是xn + 1的一个因子,因为g(x)是n-k次的多项式，故xkg(x)为一个n次多项式 则xkg(x)除以xn+1的商必为1，余式记为b(x) 即：xkg(x)=1 (xn+1) + b(x) 表示g(x)向左移动k次，并且仍为许用码组，即：是g(x)的倍式，则有： b(x) = u(x)g(x) 则xn+1= g(x)xk + u(x) = h(x)g(x) 即证明g(x)为xn+1的一个因子 因此，这一性质也就指出了g(x)的求解方法，即对多项式xn+1进行分解： xn+1 = (x+1)(xn-1 + xn

28、-2 + x +1) 例如：( 7, k )循环码的生成多项式，x7+1可以作如下分解（分到不能分为止）： (x+1)(x3+ x2+1)(x3+ x +1),生成多项式,66,例：求(7，4)循环码的生成多项式。 解：生成多项式g(x)：r=n-k=7-4= 3次首一多项式 即将 因式分解： 选择 或 任一均可作为（7，4）循环码的生成多项式。,常数项为1，最高项为3次,（n，k）循环码的构造步骤：对（xn+1）做因式分解，找出其n-k次因式；以n-k次因式为生成多项式g(x),与信息多项式m(x)相乘，即得到码多项式： C(x)=m(x)g(x) 因m(x)不高于（k-1）次，所以C(x)

29、的次数不会高于（k-1）+（n-k）=（n-1）次。,2、循环码的构造,讨论长度n=7的循环码。 解 多项式x7+1可以分解为下列形式:x7+1=(x+1)(x3+x2+1)(x3+x+1),为了产生(7，4)循环码，可以取下列两个多项式之一作为生成多项式:g1(x)=x3+x2+1 g2(x)=x3+x+1其中，g1(x)和g2(x)产生的码是等价的。,2、循环码的构造,具体产生过程为： 假设4比特信息为(0001)，对应的信息多项式为X1(x)=1，所以码字多项式为C1(x)=m1(x)g1(x)=(x3+x2+1)对应码字为C1=(0001101)当4比特信息为(0010)时，对应的信息

30、多项式为X2(x)=x，码字多项式为C2(x)=m2(x)g1(x)=x(x3+x2+1)=x4+x3+x对应码字为C2=(0011010),2、循环码的构造,当4比特信息为(0011)时，对应的信息多项式为m3(x)=x+1，码字多项式为,注意到二进制多项式加法为同阶次项的系数进行半加运算，所以 x3+x3=(1+1)x3=0 x3=0 于是得到 C3(x)=x4+x2+x+1,2、循环码的构造,对应码字为C3=(0010111)以此类推，可以得到其他码字。,2、循环码的构造,多项式xn+1总是可以分解为两个多项式之积:xn+1=g(x)h(x)其中，g(x)表示(n，k)循环码的生成多项式

31、，而h(x)则为校验多项式，其阶数为k。 所以使用h(x)可以产生相应的对偶码。 定义h(x)的倒数多项式为：xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk,3、循环码的生成矩阵,定理：(n，k)循环码的生成矩阵G由g(x)唯一确定，其第一行对应于g(x)的系数，第二行对应于xg(x)的系数，第k行对应于 的系数。 Gk*n：k行n列，则 生成的循环码码字：C=mG,多项式xn+1总是可以分解为两个多项式之积:xn+1=g(x)h(x)其中，g(x)表示(n，k)循环码的生成多项式，而h(x)

32、则为校验多项式，其阶数为k。 所以使用h(x)可以产生相应的对偶码。 定义h(x)的倒数多项式为：xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk,3、循环码的生成矩阵,例：求二进制(7，4)循环码的,（1）生成矩阵。 解：（1）设选 ，g(x)按升幂排列：则Gk*n=G4*7为 （2）求输入消息m=1001时的输出码字: 解：C=mG 代入得c=1010011,其中，g(x)表示(n，k)循环码的生成多项式，而h(x)则为校验多项式，其阶数为k。 所以使用h(x)可以产生相应的对偶码。 定义h

33、(x)的倒数多项式为：xkh(x-1)=xk(x-k+hk-1x-k+1+hk-2x-k+ + + 2h1x-1+1) =1+hk-1x+hk-2x2+h1xk-1+xk,3、循环码的生成矩阵,(3)若已知消息多项式m(x)=1+x3，求该（7，4）循环码的输出码字： c(x)= m(x)g(x) 得c(x)=(1+x3)(1+x2+x3) =1+x2+x5+x6 所以c=1010011,例：求二进制(7，4)循环码的,4、循环码的校验矩阵,循环码的校验多项式h(x) (n,k)循环码的校验多项式h(x)定义为： 由于循环码是线性分组码，因此满足CHT=0 同理循环码满足：c(x)h(x)=0

34、。,4、循环码的校验矩阵,4、循环码的校验矩阵,校验矩阵Hr*n：将h(x)的系数按幂次的降序排列：作为矩阵的第一行；将第一行向右移一位作为G的第二行；。则 由于是循环码是线性的，因此满足：GHT=0,4、循环码的校验矩阵,例：求二进制（7，4）循环码的校验矩阵,5、系统循环码,（n,k）循环码为系统码 已知待发送的消息为：m=(m0m1mk-1)，则 分析：系统循环码C=(校验位，信息位) 思路：将k位信息位整体向右移位r位，再加上校验位。 按照以上思路可得系统循环码的码多项式为,80,例：求输入消息m=1001时的（7，4）系统循环码码字,解：,先将m右移r位(此题r=3)，再加上p(x)

35、对应的校验码p,注意校验位的位数，不足的补0,系统循环码的生成矩阵,81,系统循环码码字的第二种求法：c=mGs 生成矩阵Gs 又有两种求法： 求法1：由g(x)G初等行变换Gs 求法2：,82,系统循环码的一致校验矩阵,系统循环码的一致校验矩阵Hs 例：已知二进制（7，4）循环码，求 （1）求系统生成矩阵 （2）输入消息m=1001时的输出的系统循环码码字 （3）求一致校验矩阵,解：（1）选g(x)=1+x+x3可得生成矩阵G: 由于是求系统循环码的生成矩阵，则矩阵中必含有I4的单位阵，而直接求得的G中不含单位阵，所以它不是系统循环码的G。 需求系统循环码的Gs：,系统循环码的一致校验矩阵,通过初等行变换得系统循环码的生成矩阵Gs,（2）因此： m的系统循环码为c=mGs 代入m=1001得 C=0111001,系统循环码的一致校验矩阵,（3）一致校验矩阵,系统循环码的一致校验矩阵,（4）生成的系统循环码字集合： C=mGS,由于,所以,系统循环码的一致校验矩阵,5.4 卷积码概念,图（3，1，2）卷积码编码器,当输入信息元为mi时， D0、D1中分别存放着此前输入的mj1和mj2， 经运算可得到两个校验元pj，1和pj，2，即 pj，1mjmj1 pj，2mjmj2,5.4 卷积码概念,在编码器输出端，由旋转开关实现并串转换显然，cj中