第五章纠错编码

1、第五章 纠错编码1第五章第五章 纠错编码纠错编码5.1 5.1 纠错编码的基本概念纠错编码的基本概念5.2 5.2 线性分组码线性分组码5.35.3 循环码循环码5.4 5.4 卷积码卷积码 25.1 纠错编码的基本概念纠错编码的基本概念5.1.1 5.1.1 纠错编码的任务纠错编码的任务5.1.2 5.1.2 纠错编码的分类纠错编码的分类5.1.35.1.3 译码准则译码准则5.1.4 5.1.4 香农第二定理香农第二定理345.1 信道编码的任务信道编码的任务5.1 信道编码信道编码5l信源编码信源编码l提高数字信号提高数字信号l将信源的模拟信号转变为数字信号将信源的模拟信号转变为数字信号

2、l降低数码率降低数码率,压缩传输频带压缩传输频带(数据压缩数据压缩)l信道编码信道编码l提高数字通信提高数字通信 数字信号在信道的传输过程中数字信号在信道的传输过程中,由于实际由于实际信道信道的的传输特性不理想传输特性不理想以及存在加性以及存在加性噪声噪声,在接收端往在接收端往往会产生往会产生误码误码。5.1 信道编码的任务信道编码的任务6 信道编码信道编码：就是按一定的规则给信源输出序列增加：就是按一定的规则给信源输出序列增加某些冗余符号，使其变成满足一定数学规律的码序列某些冗余符号，使其变成满足一定数学规律的码序列（或码字），再经信道进行传输。（或码字），再经信道进行传输。（提高传输的可靠

3、性）（提高传输的可靠性） 信道译码信道译码：就是按与编码器同样的数学规律去掉接：就是按与编码器同样的数学规律去掉接收序列中的冗余符号收序列中的冗余符号, , 恢复信源消息序列。恢复信源消息序列。 一般地说，所加的冗余符号越多，纠错能力就越强，一般地说，所加的冗余符号越多，纠错能力就越强，但传输效率降低。因此在信道编码中明显体现了传输有但传输效率降低。因此在信道编码中明显体现了传输有效性与可靠性的矛盾。效性与可靠性的矛盾。 编码信道模型编码信道模型7011011,0,1, , 0,1ninicc cccRr rrr消息消息cRm 信道编码信道编码 编码信道编码信道 信道译码信道译码 m码字码字接

4、收向量接收向量消息消息编码信道模型R噪声源噪声源错误图样E编码信道模型编码信道模型8l消息序列m总以k个码元为一组传输，称k个码元的码组为信息码组。l信道编码器按一定规则对每个信息码组附加一些多余的码元，构成长为n个码元的码组c（信道编码）。l附加的r=n-k个码元称为监督码元错误图样错误图样9 为了定量描述信号的差错，使用差错图样表示发送和接收码之“差”，设发送的码为C，接收码为R，对于M进制码，差错图样E为E=(CR)(modM)对于二进制码而言，减法运算就是模2加法运算，于是有ECR例如:C=10000,E=01000,R=? R=(11000)105.1 信道编码的任务信道编码的任务1

5、0检错与纠错原理检错与纠错原理 l0:晴,1:雨l若10,01。收端无法发现错误00晴1001110011雨能发现一个错误禁用码组 插入1位监督码后具有检出1位错码的能力,但不能予以纠正。115.1 信道编码的任务信道编码的任务11000晴010001111000111雨晴 在只有1位错码的情况下,可以判决哪位是错码并予以纠正,可以检检出2位或2位以下的错码。100011101110雨检错和纠错方式检错和纠错方式12l自动请求重发(ARQ)：l发端发送检错码，l收端译码器判断当前码字传输是否出错；l当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字(全部或部分)。优点：优点： 编译码

6、设备比较简单。 在一定的多余度码元下，系统具有极强的纠错能力。 能获得极低的误码率。 由于检错码的检错能力与信道干扰的变化基本无关，因此这种系统的适应性很强，特别适应于短波、 散射、 有线等干扰情况特别复杂的信道中。 ARQ缺点：缺点： 控制电路比较复杂。 传送消息的连贯性和实时性较差。由于反馈重发的次数与信道干扰情况有关，若信道干扰很频繁，则信道经常处于重发消息的状态。ARQ检错和纠错方式检错和纠错方式l前向纠错(FEC)：l发送端的信道编码器将信息码组编成具有一定纠错能力的码。l接收端信道译码器对接收码字进行译码,若传输中产生的差错数目在码的纠错能力之内时,译码器对差错进行定位并加以纠正。

7、优点：优点： 不需要反馈信道，能够实现一对多的同步广播通信，而且译码实时性好，控制电路也比ARQ简单。随着编码理论的发展和大规模集成技术的发展，复杂算法的译码设备越来越简单，成本越来越低，所以这种方式在实际中得到越来越广泛的应用。FEC缺点：缺点： 这种工作方式是假设纠错码的纠错能力足够纠正信息序列传输中的错误，也就是纠错码与信道的干扰是相匹配的，所以对信道的适应性较差。 为了获得合适的误码率，往往按照信道最差的情况设计纠错码，增加的冗余码元比检错码要多，编码效率一般较低。 FEC检错和纠错方式检错和纠错方式l混合纠错混合纠错(HEC)：l是是FEC与与ARQ方式的结合。方式的结合。l发端发送

8、同时具有自动纠错和检测能力的码发端发送同时具有自动纠错和检测能力的码组组,收端收到码组后收端收到码组后,检查差错情况检查差错情况,如果差错在如果差错在码的纠错能力以内码的纠错能力以内,则自动进行纠正。则自动进行纠正。l如果信道干扰很严重如果信道干扰很严重,错误很多错误很多,超过了码的纠超过了码的纠错能力错能力,但能检测出来但能检测出来,则经反馈信道请求发端则经反馈信道请求发端重发这组数据。重发这组数据。l信息反馈信息反馈(IRQ)：l收端把收到的数据收端把收到的数据,原封不动地通过反馈信道原封不动地通过反馈信道送回到发端送回到发端,发端比较发的数据与反馈来的数发端比较发的数据与反馈来的数据据,

9、从而发现错误从而发现错误,并且把错误的消息再次传送并且把错误的消息再次传送,直到发端没有发现错误为止。直到发端没有发现错误为止。优点：优点：由于该方式避免了FEC要求的复杂设备和ARQ方式的信息连贯性差的缺点，并且可以达到较低的误码率，因此在实际中得到了广泛应用。 HEC总结：信道编码的概念l目的：降低错误的译码概率PEl对象：信息序列l方法：信息码+附加码元，收端按照一定译码准则检纠错。l实质：增加冗余度。205.1.2 信道（纠错）编码的分类l按照接收端工作状态分为： 检错码 纠错码 纠删码l根据纠正错误的类型 纠随机错误码 纠突发错误码21225.1.2 信道（纠错）编码的分类22l随机

10、差错：l差错是相互独立的,不相关l存在这种差错的信道是无记忆信道或随机信道l突发差错：l指成串出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串字lE: 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突发长度= 65.1.2 信道（纠错）编码的分类l按照发送端编码方式分为：235.1.3译码准则245.1.3译码准则25),.,2 , 1;,.,2 , 1()(sjriabFij5.1.3译码准则26（1）对输入符号集为X=a1,a2,ar，输出符号集为Y= b1,b2,bs的信道来说，一共可构成rs种不同的译码规则。

11、不同的译码规则会引起不同的可靠程度。5.1.3译码准则27 最小错误译码准则（最小错误译码准则（MEPD） 最大后验概率准则（最大后验概率准则（MPPD） 最大联合概率准则（最大联合概率准则（MJPD） 最大似然概率准则（最大似然概率准则（MLD）()()()ijjjiF bap b ap b a，（ =1.r）()()()ijjijF bap a bp ab，（ =1.r）()()()ijjijF bap a bp a b，（ =1.r）()minjEF baP，信道输入等概时，MLD和MJPD等价5.1.4香农第二定理285.1.4香农第二定理29表述二：表述二：设离散无记忆信道的信道容量

12、为C，信息传输率为R，对于任意小的正数，当Rk) 码字，其中 (nk) 个附加码元是由信息码元的线性运算产生的。l信息码组长信息码组长 k 位，有位，有 2k 个不同的信息码组，则应该有个不同的信息码组，则应该有 2k 个码字与它们一一对应。个码字与它们一一对应。5.2.1 线性分组码的基本概念线性分组码的基本概念5.2 线性分组码325.2.1 线性分组码的基本概念线性分组码的基本概念l线性分组码线性分组码：通过预定的线性运算将长为：通过预定的线性运算将长为 k 位的信位的信息码组变换成息码组变换成 n 长的码字长的码字 ( nk )。由。由 2k 个信息码组个信息码组所编成的所编成的 2k

13、个码字集合，称为个码字集合，称为线性分组码线性分组码。l码矢码矢：一个：一个 n 长的码字可以用矢量来表示长的码字可以用矢量来表示C C = (Cn1,Cn2,C1,C0 ) 所以码字又称为码矢。所以码字又称为码矢。l( n, k ) 线性码线性码：信息位长为：信息位长为 k，码长为，码长为 n 的线性码的线性码l编码效率编码效率/编码速率编码速率/码率：码率：R=k /n。它说明了信道的。它说明了信道的利用效率，利用效率，R是衡量码性能的一个重要参数是衡量码性能的一个重要参数。5.2 线性分组码335.2.1 线性分组码的基本概念线性分组码的基本概念线性体现在线性体现在：输入输出的关系为线性

14、映射关系输入输出的关系为线性映射关系码元中每个码字由信源做模二加运算得到码元中每个码字由信源做模二加运算得到线性分组码的特点线性分组码的特点：在码集中存在全在码集中存在全0码字码字满足封闭性满足封闭性5.2 线性分组码345.2.1 线性分组码的基本概念线性分组码的基本概念定理定理：线性分组码的最小距离等于最小非零码字重量。：线性分组码的最小距离等于最小非零码字重量。定理中涉及到的基本概念定理中涉及到的基本概念汉明重量汉明重量：码字中非：码字中非0码的个数。码的个数。最小汉明重量最小汉明重量：码集中非：码集中非0码字汉明重量的最小值。码字汉明重量的最小值。汉明距离汉明距离：两个等长码：两个等长

15、码C和和C中，对应位码元不同的取中，对应位码元不同的取值个数。值个数。最小汉明距离最小汉明距离：码集中所有码字距离的最小值。：码集中所有码字距离的最小值。0min( )dw c5.2 线性分组码355.2.2 线性分组码的编码线性分组码的编码一、生成矩阵一、生成矩阵 G 中每一行 gi = ( gi 1, gi 2, , gi n ) 都是一个码字；l生成矩阵的定义生成矩阵的定义：由于矩阵 G 生成了 (n,k) 线性码中的任何一个码字，称矩阵 G 为 (n,k) 线性码的生成矩阵。l(n,k) 线性码的每一个码字都是生成矩阵 G 的行的线性组合。cmG5.2 线性分组码365.2.2 线性分

16、组码的编码线性分组码的编码一、生成矩阵一、生成矩阵l标准生成矩阵：标准生成矩阵： 通过行初等变换，将 G 化为前 k 行和k 列是单位子阵的标准形式标准形式11121()21222()12()100010GIQ001n kn kk nkk rkkk n kqqqqqqqqq 5.2 线性分组码375.2.2 线性分组码的编码线性分组码的编码二、编码二、编码l线性系统分组码线性系统分组码：用标准生成矩阵用标准生成矩阵 GGkn 编成的码编成的码字，前面字，前面 k 位为信息数字，后面位为信息数字，后面 r=nk 位为校验位为校验字，这种信息数字在前校验数字在后的线性分组码字，这种信息数字在前校验

17、数字在后的线性分组码称为线性系统分组码。称为线性系统分组码。l当生成矩阵当生成矩阵 G G 确定之后，确定之后，(n,k) 线性码也就完全被线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样确定了，只要找到码的生成矩阵，编码问题也同样被解决了。被解决了。38举例举例： 已知一个已知一个 (7,4) 线性码的生成矩阵线性码的生成矩阵G如下图示，当输入信息码元为如下图示，当输入信息码元为1010时，试求输出的码字。时，试求输出的码字。n由矩阵乘法规则可知：由矩阵乘法规则可知： C C = = m m G G 的结果，就是矩阵的结果，就是矩阵 G G 中，与中，与 m m 中为中为“1 1

18、” ”的元素相对应的的元素相对应的行按位模行按位模 2 2 加的结果。加的结果。5.2.2 线性分组码的编码4 71 41 71 44 710001010100111G00101100001011m(1010)10001010100111CmG1010(1010011)00101100001011395.2.2 线性分组码的编码练习：练习： 已知某线性分组码的生成矩阵为已知某线性分组码的生成矩阵为l试问试问：l（1）n = ? k = ? , 该码组集合中的码字有多少？该码组集合中的码字有多少？l（2）若信息码元若信息码元 m 分别是分别是 1100 和和1111时时 , 写出其对应的输出码字

19、。写出其对应的输出码字。10000110100101G00101100001111405.2.3 线性分组码的译码一、一致校验矩阵一、一致校验矩阵l推广到一般情况：对推广到一般情况：对 (n,k) 线性分组码，每个码字中的线性分组码，每个码字中的 r(r=nk) 个监督元与信息元之间的关系可由下面的线性个监督元与信息元之间的关系可由下面的线性方程组确定方程组确定000022110222212101212111ChChChChChChChChChrnnrnrnnnnnn415.2.3 线性分组码的译码一、一致校验矩阵一、一致校验矩阵l令系数矩阵为令系数矩阵为 HH，码字行阵列为，码字行阵列为 C

20、 C矩阵。线性分组码的一致监督为称或则：),(H0HC0CHCH11110211212222111211knCCChhhhhhhhhrTrnnTrTnnrnnnrnrrnnnr425.2.3 线性分组码的译码一、一致校验矩阵特性一、一致校验矩阵特性:l对对H H 各行实行初等变换，将后面各行实行初等变换，将后面 r 列化为单位子阵，于是列化为单位子阵，于是得到下面矩阵得到下面矩阵(行变换所得方程组与原方程组同解行变换所得方程组与原方程组同解)。l校验矩阵校验矩阵H H 的标准形式的标准形式：后面：后面 r 列是一单位子阵的校验矩列是一单位子阵的校验矩阵阵HH。lH H 阵的每一行都代表一个校验

21、方程，它表示与该行中阵的每一行都代表一个校验方程，它表示与该行中“1”相对应的码元的模相对应的码元的模2和为和为0。100010001H212222111211rnrrkknrppppppppp435.2.3 线性分组码的译码 GIQHPI(P)G HIQPIIQ(P)Q0IGIQH(Q)ISkk rSr krTTTTr kSSkk rr krkk rr kk rk rrSkk rTSk rr生成矩阵与一致校验矩阵的关系生成矩阵与一致校验矩阵的关系:l由于生成矩阵由于生成矩阵GG的每一行都是一个码字，所以的每一行都是一个码字，所以G G 的每行都满的每行都满足足HHrnC CTn1=0 0Tr

22、1，则有，则有HHrnGGTnk=0 0Trk 或或 GGknHHTnr=0 0krl线性系统码的监督矩阵线性系统码的监督矩阵 H H 和生成矩阵和生成矩阵 G G 之间可以直接互换之间可以直接互换。445.2.3 线性分组码的译码例例: 已知已知(7,4)线性系统码的监督矩阵为线性系统码的监督矩阵为1101000011010011100101010001G100101101011100010111H)4,7()4,7(阵可直接写出它的生成矩455.2.3 线性分组码的译码标准阵列译码l标准阵列构造方法标准阵列构造方法l先将先将 2k 个码矢排成一行，作为个码矢排成一行，作为标准阵列标准阵列的

23、第一行，并将的第一行，并将全全0码矢码矢C C1=(000)放在最左面的位置上；放在最左面的位置上；l然后在剩下的然后在剩下的 (2n2k) 个个 n 重中选取一个重量最轻的重中选取一个重量最轻的 n 重重 E E2 放在全放在全0码矢码矢 C C1 下面，再将下面，再将 E E2 分别和码矢分别和码矢 相加，放在对应码矢下面，构成阵列第二行；相加，放在对应码矢下面，构成阵列第二行；l在第二次剩下的在第二次剩下的 n 重中，选取重量最轻的重中，选取重量最轻的 n 重重 E E3，放在，放在 E E2 下面，并将下面，并将 E E3 分别加到第一行各码矢上，得到第三分别加到第一行各码矢上，得到第

24、三行；行；l，继续这样做下去，直到全部，继续这样做下去，直到全部 n 重用完为止。得到下重用完为止。得到下页表格所示的页表格所示的 (n,k) 线性码的标准阵列。线性码的标准阵列。46码字 CC1(=0) (陪集首) CC2 CC E E2 CC2+ E E2 CCi + E E2 E E3 CC2+ E E3 CCi + E E3 禁 用 码 组 5.2.3 线性分组码的译码标准阵列译码475.2.3 线性分组码的译码标准阵列译码标准阵列的特性：标准阵列的特性：定理定理：在标准阵列的同一行中没有相同的矢量，而且：在标准阵列的同一行中没有相同的矢量，而且 2n 个个 n 重中任一个重中任一个

25、n 重在阵列中出现一次且仅出现一次。重在阵列中出现一次且仅出现一次。L陪集陪集：标准阵列的每一行叫做码的一个陪集。：标准阵列的每一行叫做码的一个陪集。L陪集首陪集首：每个陪集的第一个元素叫做陪集首。：每个陪集的第一个元素叫做陪集首。485.2.3 线性分组码的译码伴随式译码伴随式和错误检测：伴随式和错误检测：l用监督矩阵译码用监督矩阵译码：接收到一个码字：接收到一个码字 R R 后，检验后，检验 HH R RT=0 0T 是否成立：是否成立：lHRT =0T是否成立是检验码字出错与否的依据。l若关系成立，则认为 R 是一个码字；l否则判为码字在传输中发生了错误；l伴随式伴随式/监督子监督子/校

26、验子校验子：S S=R R HHT或或S ST=HH R RT。l如何纠错？如何纠错？l设发送码矢 C=(Cn1,Cn2,C0)l信道错误图样为 E=(En1,En2,E0) ，l其中其中Ei=0，表示第，表示第i位无错；位无错；lEi=1，表示第，表示第i位有错。位有错。i=n1,n2,0。495.2.3 线性分组码的译码伴随式译码l接收码字接收码字 R R =(Rn1,Rn2,R0)=C C+E E =(Cn1+En1, Cn2+En2, , C0 +E0)l求接收码字的伴随式（接收码字用监督矩阵进行检验）求接收码字的伴随式（接收码字用监督矩阵进行检验） S ST=HH R RT=HH (

27、C C+E E)T=HH C CT+HH E ETl由于由于HH C CT=0 0T，所以，所以 S ST=HH E ETl设设HH=(h h1,h h2,h hn)，其中，其中h hi表示表示HH的列。代入上式得到的列。代入上式得到505.2.3 线性分组码的译码伴随式译码 总结总结：l伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；伴随式仅由错误图样决定；l伴随式是错误的判别式：伴随式是错误的判别式：l若S=0，则判为没有出错，接收码字是一个码字；l若S0，则判为有错。l不同的错误图样具有不同的伴随式，它们是一一对

28、应的。不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式对二元码，伴随式S是是H H 阵中与错误码元对应列之和阵中与错误码元对应列之和。51伴随式译码举例：伴随式译码举例： 某某(7,3) 线性系统码线性系统码l设发送码字设发送码字C C = 1010011，接收码字，接收码字R R 1010011，R R与与C C相同。相同。无错。因此，译码器判接收字代入得和计算伴随式，把根据接收字道就是发送的码字，但接收端译码器并不知TTT0HRSRHRH10001100100011001011100011015.2.3 线性分组码的译码伴随式译码52l若接收码字中有一位错误若接收码字中有

29、一位错误正确。错能力相符，所以译码中错误码元数与码的纠由于接收字的第二位是错的。因此判定接收字的第二列，等于且码是纠单个错误的码，译码器判为有错。由于伴随式为接收码字发送码矢RRHS0SRHSRCTTTT)3 , 7(,111011001111000110010001100101110001101111001110100115.2.3 线性分组码的译码伴随式译码535.2.3 线性分组码的译码伴随式译码l当码元错误多于1个时位上，只是发现有错。无法判定错误出在哪些同，阵中的任何一列都不相但与，不等于是第一列和第四列之和由于伴随式为接收码字发送码矢H0SRHSRCTTT0110110110010

30、0011001000110010111000110100110111010011545.2.3 线性分组码的译码伴随式译码以上定理是纠错码理论中最重要的基本定理之一，它说明了一个距离为d的线性分组码，既可用来纠正个错误，又可用来检测e d1个错误。 21dt定理定理 对于任一个（对于任一个（n，k）线性分组码，若要在码字内线性分组码，若要在码字内 检测检测e个错误，则要求码的最小距离个错误，则要求码的最小距离d e1； 纠正纠正t个错误，则要求码的最小距离个错误，则要求码的最小距离d 2t1； 纠正纠正t个错误同时检测个错误同时检测e（ t）个错误，则要求个错误，则要求d te1。555.2.

31、4 汉明码 对于给定的正整数m3，二进制汉明码的信息位数量、 码字长度与m之间满足下列关系:k=2mm1 n=2n-k1所以汉明码实际就是(2m1，2mm1)分组码。 当m=3时，则为(7，4)码。 二进制汉明码的最小汉明距离为d0=3。 565.2.4 汉明码 例例 构造构造m=3的汉明码。的汉明码。 解解 由于由于m=3，根据汉明码的性质可知，根据汉明码的性质可知k=2mm1=4 n=2m1=7所以所以m=3的汉明码是的汉明码是(7，4)分组码。分组码。 除了矢量除了矢量0之外的所有之外的所有排列为排列为(001)，(010)，(011)，(100)，(101)，(110)，(111)，为

32、，为了产生系统码，将了产生系统码，将(100)，(010)，(001)放在矩阵的最后放在矩阵的最后3列，列，得到校验矩阵为得到校验矩阵为575.2.4 汉明码011110010110101101001H于是得到生成矩阵为于是得到生成矩阵为1000011010010100101100001111G585.3 循环码5.3.1 循环码的基本概念循环码的基本概念数学定义数学定义：设：设C为某为某( n, k )线性分组码的码组集合，如果对线性分组码的码组集合，如果对C中任中任意一个码组意一个码组c = ( an-1 an-2 a1 a0 )，它的循环移位，它的循环移位c(1) = ( an-2an-

33、3 a1 a0 an-1 )也属于也属于C，则称该，则称该( n, k )码为循环码码为循环码其中其中c(i )表示表示c码组循环移位码组循环移位i次。次。例如：某例如：某( 7, 4 )循环码组集合中的一个码组为循环码组集合中的一个码组为( 1000101 )，向左，向左循环移位一次后的码组循环移位一次后的码组( 0001011 )仍为码组集合中第一个许用仍为码组集合中第一个许用码组码组595.3 循环码605.3 循环码615.3.2 循环码的描述循环码的描述 1、循环码多项式描述、循环码多项式描述621、循环码多项式描述、循环码多项式描述码多项式的模运算码多项式的模运算正整数的模运算正整

34、数的模运算若一正整数若一正整数M除以正整数除以正整数N，所得到的商为，所得到的商为Q，余数为，余数为R，可表示为，可表示为其中其中Q为整数，则在模为整数，则在模N运算下，上式的结果为：运算下，上式的结果为：多项式的模运算与正整数的模运算相同，一般利用长除法计算商式和余式多项式的模运算与正整数的模运算相同，一般利用长除法计算商式和余式有两个多项式有两个多项式a(x)和和p(x)，一定存在有唯一的多项式，一定存在有唯一的多项式Q(x)和和r(x)，使得：，使得： 称称Q(x)是是a(x)除以除以p(x)的商式，的商式，r(x)是是a(x)除以除以p(x)的余式，在模的余式，在模p(x)运算下运算下

35、且有且有 即：除到余式的次数小于除式为止，当能整除时即：除到余式的次数小于除式为止，当能整除时次数为次数为00 MRQRNNN) mod，记模( NNRM为( )( ) ( )( )a xQ x p xr x)(mod )()(xpxrxa0deg ( )deg( ) r xp x63定理：对于( 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)( )mod(1)mod(1)( )( ),

36、( )( ) nniixxcxxc xcxx c x-1-21210( )() nnnnc xaxaxa xa-121-2-121-1-210-1-1101)1-1(-( )(1)( )nnnnnnnnnnnnxc xaxaxa xa xaxaaxcaaxxxxaa (1)1mod(1)mod(1)(1)( )(1)( )( )nnnnxxxc xaxcxcx1、循环码多项式描述、循环码多项式描述码多项式的模运算码多项式的模运算1、循环码多项式描述、循环码多项式描述码多项式的模运算码多项式的模运算例如例如：(7 , 4)循环码的第循环码的第12个码组个码组c12为：为：1011000，则其码多

37、项，则其码多项式为：式为： c(x)=x6 + x4 + x3 请写出请写出c12左循环移位左循环移位3次的码组次的码组解：解：i = 3，则，则 x3c(x) = x9 + x7 + x6 其对应码组为：其对应码组为：1000101，它是，它是( 7, 4 )循环码中的第循环码中的第4个码组个码组c47362mod1( )1xx c xxx279769276276211 1 1xxxxxxxxxxxxx651、循环码多项式描述、循环码多项式描述生成多项式生成多项式 定义定义：记：记C(x)为为( n, k )循环码的所有码组对应的多项式的集合循环码的所有码组对应的多项式的集合，若，若g(x)

38、是是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)的倍式一定是码多项式；的倍式一定是码多项式； 3）g(x)的最高次为的最高次为n-k，且是唯一的；，且是唯一的； 4）g(x)是是xn + 1

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

40、以C(x)的次数不会高于（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比特信息为比特信息为(000

41、1)，对应的信，对应的信息多项式为息多项式为X1(x)=1，所以码字多项式为，所以码字多项式为C1(x)=m1(x)g1(x)=(x3+x2+1)对应码字为对应码字为C1=(0001101)当当4比特信息为比特信息为(0010)时，对应的信息多项式为时，对应的信息多项式为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，码字多项式为，码字多项式为331324

42、332( )( )( ) (1)(1) ()(1)Cxmx gxxxxxxxxx 注意到二进制多项式加法为同阶次项的系数进行半加注意到二进制多项式加法为同阶次项的系数进行半加运算，所以运算，所以x3+x3=(1+1)x3=0 x3=0于是得到于是得到C3(x)=x4+x2+x+12、循环码的构造、循环码的构造对应码字为对应码字为C3=(0010111)以此类推，可以得到其他码字。以此类推，可以得到其他码字。 2、循环码的构造、循环码的构造多项式xn+1总是可以分解为两个多项式之积:xn+1=g(x)h(x)其中，g(x)表示(n，k)循环码的生成多项式，而h(x)则为校验多项式，其阶数为k。

43、所以使用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+xk3、循环码的生成矩阵、循环码的生成矩阵l定理定理：(n(n，k)k)循环码的生成矩阵循环码的生成矩阵G G由由g(x)g(x)唯一确定，其唯一确定，其第一行对应于第一行对应于g(x)g(x)的系数，第二行对应于的系数，第二行对应于xg(x)xg(x)的系数的系数，第，第k k行对应于行对应于 的系数。的系数。lG Gk k* *n n：k k行行n n列，则列，则l生成的循环码码字

44、：生成的循环码码字：C=mGC=mG)(1xgxknkrrrggggggggG10010000000000k-1k-1个个r+1r+1个个1322102210.)(.)(rrrrxgxgxgxgxxgxgxgxggxg多项式xn+1总是可以分解为两个多项式之积:xn+1=g(x)h(x)其中，g(x)表示(n，k)循环码的生成多项式，而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+xk3、循环

45、码的生成矩阵、循环码的生成矩阵例：求二进制例：求二进制(7(7，4)4)循环码的循环码的l（1）生成矩阵。l解解：（：（1 1）设选设选 ，g(x)g(x)按升幂按升幂排列：则排列：则G Gk k* *n n=G=G4 4* *7 7为为l（2 2）求输入消息）求输入消息m=1001m=1001时的输出码字时的输出码字: : 解：解：C=mG C=mG 代入得代入得c=1010011c=1010011 321)(xxxg110100001101000011010000110174G其中，g(x)表示(n，k)循环码的生成多项式，而h(x)则为校验多项式，其阶数为k。 所以使用h(x)可以产生相

46、应的对偶码。 定义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+xk3、循环码的生成矩阵、循环码的生成矩阵l(3)(3)若已知消息多项式若已知消息多项式m(x)=1+xm(x)=1+x3 3，求该（，求该（7 7，4 4）循环码的输出码字：）循环码的输出码字： c(x)= m(x)g(x)c(x)= m(x)g(x) 得得c(x)=(1+xc(x)=(1+x3 3)(1+x)(1+x2 2+x+x3 3) ) =1+x =1+x2 2+x+x5 5+x+x6 6 所以所以c

47、=1010011c=1010011例：求二进制例：求二进制(7(7，4)4)循环码的循环码的4、循环码的校验矩阵l循环码的循环码的校验多项式校验多项式h(x) h(x) l(n,k)(n,k)循环码的校验多项式循环码的校验多项式h(x)h(x)定义为：定义为： l由于循环码是线性分组码，因此满足由于循环码是线性分组码，因此满足CHCHT T=0=0l同理循环码满足：同理循环码满足：c(x)h(x)=0c(x)h(x)=0。 kkkrnxhxhhxhxxhxxgxgxxh10)(1)(1)()(/ ) 1()(记作，4、循环码的校验矩阵654326534332323432423332424332

48、323323711)1)(1 ()()6 , 7()1 ()()3(11)1)(1 ()()4 , 7()1 ()()2(11)1)(1 ()()4 , 7()1 ()() 1 ()1)(1)(1 (1xxxxxxxxxxxxxxxxxxxhxxgxxxxxxxxxxxxhxxxgxxxxxxxxxxxxhxxxgxxxxxx 则它的校验多项式为循环码的生成多项式作为若选则它的校验多项式为循环码的生成多项式作为若选则它的校验多项式为循环码的生成多项式作为若选例：4、循环码的校验矩阵l校验矩阵校验矩阵H Hr r* *n n：将：将h(x)h(x)的系数按的系数按幂次的降序幂次的降序排列：作为矩

49、阵的第一行；将第一行向右移排列：作为矩阵的第一行；将第一行向右移一位作为一位作为G G的第二行；的第二行；。则。则l由于是循环码是线性的，因此满足：由于是循环码是线性的，因此满足：GHGHT T=0=00001000000000hhhhhhhHkkkknrr-1r-1个个k+1k+1个个1322102210.)(.)(kkkkxhxhxhxhxxhxhxhxhhxh4、循环码的校验矩阵l例：求二进制（7，4）循环码的校验矩阵73432101110001011100010111H11101)(1)(列行，对应的校验矩阵为按降幂排列：选nrxhxxxxh5、系统循环码l（n,k）循环码为系统码l已

50、知待发送的消息为：已知待发送的消息为：m=(mm=(m0 0m m1 1m mk-1k-1) )，则则l分析：系统循环码分析：系统循环码C=(C=(校验位，信息位校验位，信息位) ) l思路：将思路：将k k位信息位整体向右移位位信息位整体向右移位r r位，再加上位，再加上校验位。校验位。l按照以上思路可得按照以上思路可得系统循环码的码多项式系统循环码的码多项式为为1110)(kkxmxmmxm消息多项式：)(mod)()()()()(xgxmxxpxpxmxxcrr其中：80例：求输入消息例：求输入消息m=1001m=1001时的（时的（7 7，4 4）系）系统循环码码字统循环码码字l解：3

51、1)(xxm消息多项式：233323( )( )( )( )( )mod ( )7,4( )1( )(1)mod(1)11100001001 1101101001rrc xx m xp xp xx m xg xg xxxp xxxxxxpc 系统循环码其中：设选择（）循环码的则系统循环码码字先将先将m右移右移r位位(此题此题r=3)，再加上，再加上p(x)对对应的校验码应的校验码p注意校验位的位注意校验位的位数，不足的补数，不足的补0系统循环码的生成矩阵81l系统循环码码字系统循环码码字的第二种求法：的第二种求法：c=mGc=mGs sl生成矩阵生成矩阵G Gs s 又有两种求法：又有两种求法

52、：l求法求法1 1：由：由g(x)g(x)GG 初等行变换初等行变换Gs Gs l求法求法2 2： 的系数：余式行：的第的系数：余式行：的第的系数：余式行：的第即，矩阵的各行：求余得的各位拆开分别对将)()(mod)()()(mod)(2)()(mod)(1)()(,1111110001110 xpxgxxxpkQxpxgxxxpQxpxgxxxpQQxgmxmxmmxmIQGkkrkrrkknkkrks82系统循环码的一致校验矩阵l系统循环码的一致校验矩阵Hsl例：已知二进制（7，4）循环码，求l（1 1）求系统生成矩阵）求系统生成矩阵l（2 2）输入消息）输入消息m=1001m=1001时

53、的输出的系统循环码码时的输出的系统循环码码字字 l（3 3）求一致校验矩阵）求一致校验矩阵nrTrsQIH,l解：（解：（1 1）选）选g(x)=1+x+xg(x)=1+x+x3 3可得生成矩阵可得生成矩阵G:G: 由于是求系统循环码的生成矩阵，则矩阵由于是求系统循环码的生成矩阵，则矩阵中必含有中必含有I I4 4的单位阵，而直接求得的的单位阵，而直接求得的G G中不含单中不含单位阵，所以它不是系统循环码的位阵，所以它不是系统循环码的G G。 需求系统循环码的需求系统循环码的GsGs：101100001011000010110000101174G系统循环码的一致校验矩阵l通过初等行变换得系统循

54、环码的生成矩阵通过初等行变换得系统循环码的生成矩阵GsGs1000101010011100101100001011,ksIQG（2 2）因此：）因此： m m的系统循环码为的系统循环码为c=mGc=mGs s 代入代入m=1001m=1001得得 C=0111001C=0111001系统循环码的一致校验矩阵l（3 3）一致校验矩阵）一致校验矩阵111010001110101101001,3TTrsQIQIH系统循环码的一致校验矩阵l（4 4）生成的）生成的系统循环码字系统循环码字集合：集合： C=mGC=mGS SmC=mGS0001101000100101110010001101000110100011010001011100101111111111111000101010011100101100001011SG由由于于所所以以系统循环码的一致校验矩阵5.4 卷积码概念图（3，1，2）卷积码编码器 当输入信息元为mi时， D0、D1中分别存放着此前输入的mj1和mj2， 经运算可得到两个校验元p