《第九章差错控制编码精选文档.ppt》由会员分享，可在线阅读，更多相关《第九章差错控制编码精选文档.ppt（88页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章 差错控制编码本讲稿第一页，共八十八页第九章第九章 差错控制编码差错控制编码这章讲述的内容这章讲述的内容l 差错控制编码的概念差错控制编码的概念l 汉明码汉明码l 线性分组码线性分组码l 循环码循环码l 卷积码卷积码本讲稿第二页，共八十八页9.1 引言引言 数字信号在传输中，遇噪声和干扰，在收端判决时可能会判错。减小数字信号在传输中，遇噪声和干扰，在收端判决时可能会判错。减小误码率的措施有误码率的措施有:l 合理选择调制方式合理选择调制方式信号正交信号正交,合适的系统带宽合适的系统带宽,信道因素信道因素；l 增大发送信号功率；增大发送信号功率；l 改善传输特性；改善传输特性；l 合理选择
2、接收方式相干、非相干、最佳合理选择接收方式相干、非相干、最佳l 差错控制编码差错控制编码l 优良的同步系统优良的同步系统(准确的同步准确的同步)本讲稿第三页，共八十八页差错控制编码方式差错控制编码方式(有针对性有针对性)汉明码、循环码汉明码、循环码加性高斯白噪声。误码的出现是分散的。加性高斯白噪声。误码的出现是分散的。卷积码、循环码卷积码、循环码脉冲噪声；衰落。误码的出现是集中的。脉冲噪声；衰落。误码的出现是集中的。差错控制方法差错控制方法1.反馈检验法：收端收到码组后，反馈回发端，与原发码组比较确认。反馈检验法：收端收到码组后，反馈回发端，与原发码组比较确认。传输效率低；双向信道；设备技术简
3、单。传输效率低；双向信道；设备技术简单。2.检错重发法检错重发法:收端收到码组后，检查出错误后，要求重法。只需收端收到码组后，检查出错误后，要求重法。只需很少的监督元；检错编码对信道适应能强；很少的监督元；检错编码对信道适应能强；双向信道；不能用双向信道；不能用于实时传输；信道噪声大时，出现于实时传输；信道噪声大时，出现“重发循环重发循环”。3.例如：例如：本讲稿第四页，共八十八页信信源源信道编码信道编码及缓冲存及缓冲存储器储器双双向向信信道道信道译码信道译码指令发生器指令发生器发送控制发送控制输出缓冲输出缓冲存储器存储器NYN“重发重发”N自动请求重发系统自动请求重发系统ARQ(Automa
4、tic Repeat reQuest)本讲稿第五页，共八十八页3.前向纠错法：收端收到码组后，能检查出错码的位置，自前向纠错法：收端收到码组后，能检查出错码的位置，自 动纠错。单向信道；实时传输；监督元位数多动纠错。单向信道；实时传输；监督元位数多,影响传输影响传输 效率；设备技术复杂。效率；设备技术复杂。4.混合法：检纠结合。噪声大错码多按检错重发工作，噪声混合法：检纠结合。噪声大错码多按检错重发工作，噪声 小错码少按前向纠错工作。小错码少按前向纠错工作。后三种方法，需接收端自动检查错误或自动纠正错误。后三种方法，需接收端自动检查错误或自动纠正错误。怎样的编码怎样的编码(算法算法)，能实现这
5、些功能？，能实现这些功能？本讲稿第六页，共八十八页9.2 基本原理基本原理1.例如：用例如：用“0”、“1”传输天气预报信号。传输天气预报信号。晴晴“0”阴阴“1”因噪声传输出错因噪声传输出错“1/0”阴阴“0/1”晴晴如用如用2位二进码位二进码“00”、“11”传输以上天气预报信号传输以上天气预报信号一般把一般把“00”,“11”称为许用码组，而称为许用码组，而“01”、“10”称为禁用码组。称为禁用码组。把原信息位后附加的码元称为监督位。把原信息位后附加的码元称为监督位。晴晴“00”阴阴“11”因噪声传输出错因噪声传输出错“10/00”“10/11”“01/11”“01/00”可检错，但不
6、可检错，但不知哪位错知哪位错“11/00”“00/11”不可检错误不可检错误(超出超出检错范围检错范围)本讲稿第七页，共八十八页如用如用3位二进码位二进码“000”、“111”传输以上天气预报信号传输以上天气预报信号晴晴“000”(阴阴“111”)出错出错“100/000”；“010/000”；“001/000”仅错仅错2位可检错，但不知哪位错。位可检错，但不知哪位错。“111/000”不可检错误不可检错误(超出检错范围超出检错范围)“101/000”；“011/000”；“110/000”仅错仅错1位的概率最大，自动纠位的概率最大，自动纠1位错码。位错码。差错控制编码码组差错控制编码码组(系
7、统码系统码)构成构成信息位信息位 监督位监督位监督元与信息元监督元与信息元 满足线性方程称为线性码。满足线性方程称为线性码。监督元只监督本码组的信息元称为线性分组码监督元只监督本码组的信息元称为线性分组码(汉明码汉明码;循环码循环码)。监督元除监督本码组的信息元还监督前监督元除监督本码组的信息元还监督前(N-1)个码组的信息元，称个码组的信息元，称为线性非分组码为线性非分组码(卷积码卷积码)。本讲稿第八页，共八十八页2.分组码分组码(1).线性分组码定义线性分组码定义k位信息元位信息元r位监督元位监督元码组长度码组长度nk+rr/n 称为多余度（冗余度）。越大纠、检能力越强。称为多余度（冗余度
8、）。越大纠、检能力越强。k/n 称为编码效率。越大纠、检能力越弱。称为编码效率。越大纠、检能力越弱。用（用（n，k）表示线性分组码。）表示线性分组码。本讲稿第九页，共八十八页(2).码重码重W、码距、码距d、以及最小码距、以及最小码距d0码重码重W：分组码中：分组码中“1”码的位数。码的位数。(11010100),W=4。码距码距d：分组码中两个码组对应位取不同值的位数。即两码：分组码中两个码组对应位取不同值的位数。即两码 组模组模2加所得码组的码重。加所得码组的码重。(1 1 1 1 0 1 1 0)(1 1 0 1 0 1 0 0)(0 0 1 0 0 0 1 0)d=6最小码距最小码距d
9、0:l 某种编码生成的码组集合中，各个码组间距离的最小值。某种编码生成的码组集合中，各个码组间距离的最小值。本讲稿第十页，共八十八页l 线性分组码具有线性分组码具有封闭性封闭性(码组集合中任意两个码组模码组集合中任意两个码组模2和和 所得码组仍为该集合中的码组所得码组仍为该集合中的码组)。所以。所以码组集合中，码组码组集合中，码组 的最小重量就等于最小码距。全零码除外。的最小重量就等于最小码距。全零码除外。l 最小码距最小码距d0，直接关系到检错、纠错的能力。直接关系到检错、纠错的能力。d0 越大检越大检 错、纠错的能力越强。错、纠错的能力越强。(3).最小码距最小码距d0与纠检能力的关系：与
10、纠检能力的关系：当许用码组集合当许用码组集合M一定，一定，d0 一定，一定，只检只检 个以下个以下(含含 个个)的错码的错码,要求要求或或或或只纠只纠 个以下个以下(含含 个个)的错码的错码,要求要求既检既检 个又纠个又纠 个错码，要求个错码，要求本讲稿第十一页，共八十八页A、B码组为许用码集合中码距为码组为许用码集合中码距为d0 的的(但不唯一但不唯一)。禁用码组都落在检错圆上。禁用码组都落在检错圆上。许用码组都落在检错圆外。但码距大于等于许用码组都落在检错圆外。但码距大于等于d0。只检方式只检方式ABd0检错圆检错圆0123本讲稿第十二页，共八十八页A、B码组为许用码集合中码距为码组为许用
11、码集合中码距为d0 的，的，(但不唯一但不唯一)。禁用码组都落在纠错圆上。禁用码组都落在纠错圆上。许用码组都落在纠错圆外。但码距大于等于许用码组都落在纠错圆外。但码距大于等于d0。纠错园上的码组都纠为圆心上的码组。纠错园上的码组都纠为圆心上的码组。Ad0B012345纠错圆纠错圆只纠方式只纠方式本讲稿第十三页，共八十八页AB1t检、纠结合方式检、纠结合方式纠错圆纠错圆检错圆检错圆d0本讲稿第十四页，共八十八页如前例如前例 晴晴阴阴d02只检一位错不能纠错只检一位错不能纠错晴晴阴阴d03只检方式，能检只检方式，能检2位错位错只纠方式，能纠只纠方式，能纠1位错位错不能检纠结合不能检纠结合晴晴阴阴多
12、云多云雨雨d01无检纠能力无检纠能力本讲稿第十五页，共八十八页3.差错控制编码的效果差错控制编码的效果 如果误码率为如果误码率为P103，在码长为，在码长为n7的码组中，恰好的码组中，恰好发生发生r个错码的概率为个错码的概率为能纠能纠1位错，出错的概率由位错，出错的概率由103降为降为105。能纠能纠2位错，出错的概率由位错，出错的概率由103降为降为109。本讲稿第十六页，共八十八页9.3 常用的简单编码常用的简单编码an-1an-2 a2a1a001.偶监督码偶监督码(an-1,an-2 a2,a1,a0)奇数个奇数个1 a0 1 偶数个偶数个1 a0 0信息位信息位监督位监督位接收校验接
13、收校验:an-1an-2 a2a1a001码组中码组中1码个数为偶数码个数为偶数“无错或无奇数个错无错或无奇数个错”“有奇数个错有奇数个错”模模2加加检错能力：能检奇数个错码。检错能力：能检奇数个错码。本讲稿第十七页，共八十八页an-1an-2 a2a1a012.奇监督码奇监督码(an-1,an-2 a2,a1,a0)奇数个奇数个1 a0 0 偶数个偶数个1 a0 1信息位信息位监督位监督位接收校验接收校验:an-1an-2 a2a1a010码组中码组中1码个数为奇数码个数为奇数“无错或无奇数个错无错或无奇数个错”“有奇数个错有奇数个错”检错能力：能检奇数个错码。检错能力：能检奇数个错码。本讲
14、稿第十八页，共八十八页3.2维奇偶监督码维奇偶监督码(块奇偶监督码）块奇偶监督码）多个码组构成方阵多个码组构成方阵对方阵的行、列方对方阵的行、列方向都进行奇或偶监向都进行奇或偶监督码的编码。督码的编码。能检奇数个错；能检奇数个错；可能检偶数个错可能检偶数个错(但错码构成矩形形状错不可检但错码构成矩形形状错不可检);适合检突发错误。适合检突发错误。本讲稿第十九页，共八十八页9.4 线性分组码线性分组码an-1an-2a0k位信息元位信息元r位监督元位监督元线性方程组线性方程组一一.汉明码汉明码 纠一个分组中的纠一个分组中的1位错码位错码 t1，d0=3偶监督码是最简单的偶监督码是最简单的线性分组
15、（线性分组（n,n-1）,一个监督元。一个监督元。如偶监督码如偶监督码an-1an-2 a1a0=S01无错无错(极大的概率极大的概率)有错有错S称为校正子称为校正子(伴随式伴随式)。一个校正子只有两个状态，可表示。一个校正子只有两个状态，可表示有错与无错两个信息，而不能指出错码的位置。有错与无错两个信息，而不能指出错码的位置。监督关系式监督关系式本讲稿第二十页，共八十八页如果增加一位监督元，如果增加一位监督元，a1、a0，增加一个监督关系式，增加一个监督关系式监督关系为监督关系为a1与与an-1,an-2 a2中部分码元构成监督关系中部分码元构成监督关系a0与与an-1,an-2 a2中部分
16、码元构成监督关系中部分码元构成监督关系an-1an-2 a1=S1an-1an-2 a0=S2两个校正子，能表示两个校正子，能表示4种信息。种信息。设想设想r个监督元，个监督元，r个监督式，个监督式，r个校正子，个校正子，(S1 S2 Sr)2r种状态种状态全零无错全零无错2r 1n表示表示n位码组中位码组中1位错码的位错码的n个位置。个位置。线性无关线性无关本讲稿第二十一页，共八十八页所以，一般码长为所以，一般码长为n，信息位数为，信息位数为k，监督位数，监督位数rnk。如果希望用如果希望用r个监督位构造出个监督位构造出r个监督关系式来指示一位个监督关系式来指示一位错码的错码的n种可能位置，
17、则要求种可能位置，则要求(S1 S2 Sr)0 0 0 10 0 1 00 0 1 1 1 1 1 1an-1,an-2 a2,a1,a0本讲稿第二十二页，共八十八页对于（对于（7,4）汉明码，）汉明码，r3，满足，满足2317。能纠能纠7位中的位中的1位错码位错码。3个监督位构造出个监督位构造出3个监督关系个监督关系a2与与a6 a5 a4构成偶监督关系构成偶监督关系a1与与a6 a5 a3构成偶监督关系构成偶监督关系a0与与a6 a4 a3构成偶监督关系构成偶监督关系a6+a5+a4+a2=0或或S1a6+a5+a3+a1=0或或S2a6+a4+a3+a0=0或或S3S1S2S3错码位置错
18、码位置S1S2S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000仅无仅无1位错位错得出得出关系关系(线性无关线性无关)本讲稿第二十三页，共八十八页a6+a5+a4+a2=0a6+a5+a3+a1=0a6+a4+a3+a0=04 比特信息元比特信息元 a6、a5、a4、a3确定后，根据监督关系式求出确定后，根据监督关系式求出 3 比特监督元比特监督元 a2、a1、a0。a2=a6+a5+a4a1=a6+a5+a3a0=a6+a4+a3监督关系式也可以表示成监督关系式也可以表示成1a2=1a6+1a5+1a4+0a31a1=1a6+1a5+0a4+1a
19、31a0=1a6+0a5+1a4+1a3码元系数为码元系数为1的表示码元之间存在监督关系，的表示码元之间存在监督关系，0则没有则没有(7,4)汉明码编码汉明码编码用矩阵表示用矩阵表示本讲稿第二十四页，共八十八页监督关系式还可以用矩阵表示监督关系式还可以用矩阵表示或或a2 a1 a0=a6 a5 a4 a31 1 1 1 1 0 1 0 1 0 1 1=P1 1 1 0 1 1 0 1 1 0 1 1a6a5a4a3a2a1a0a6a5a4a3=a6 a5 a4 a3QPT13134414113144314监督序列生监督序列生成矩阵成矩阵本讲稿第二十五页，共八十八页a2 a1 a0=a6 a5
20、a4 a31 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1a6 a5 a4 a3=I42131443a6 a5 a4 a3 a2 a1 a01 0 0 0 0 1 0 0 0 0 1 0 0 0 0 11 1 1 1 1 0 1 0 1 0 1 1 a6 a5 a4 a3144717G47本讲稿第二十六页，共八十八页a6 a5 a4 a3 a2 a1 a01 0 0 0 0 1 0 0 0 0 1 0 0 0 0 11 1 1 1 1 0 1 0 1 0 1 1 a6 a5 a4 a3I4Q信息元矩阵信息元矩阵G典型生成矩阵典型生成
21、矩阵A汉明码汉明码(系统码系统码)矩阵矩阵144717 Aa6 a5 a4 a314G47G47将信息元将信息元a6 a5 a4 a3，共共2k个不同的信息序列，分别代入方个不同的信息序列，分别代入方程组，得到程组，得到a6 a5 a4 a3 a2 a1 a0共共2k个许用码组。见下表。个许用码组。见下表。本讲稿第二十七页，共八十八页(7,4)汉明码，汉明码，d0=3，许用码组集合。，许用码组集合。为生成矩阵。为生成矩阵。A许用码组许用码组A许用码组许用码组信息位信息位监督位监督位信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001000111000
22、1011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111112341234本讲稿第二十八页，共八十八页结论结论1：(7,4)汉明码属汉明码属(n,k)线性分组码之一。线性分组码之一。编码方法为编码方法为A许用码组许用码组系统码系统码a6a5a4a3K位信息位位信息位IkQkrG典型生成阵典型生成阵 典型生成矩阵典型生成矩阵G，左半部分为，左半部分为k阶单位阵阶单位阵Ik，右半部分右半部分为监督序列生成矩阵为监督序列生成矩阵Q 。kr G的各行线性无关。的各行线性无
23、关。G的各行也在许用码组集合中。的各行也在许用码组集合中。监督关系监督关系Q不同时，构成的不同时，构成的(n,k)线性分组码不同。线性分组码不同。本讲稿第二十九页，共八十八页(7,4)汉明码译码汉明码译码1a2=1a6+1a5+1a4+0a31a1=1a6+1a5+0a4+1a31a0=1a6+0a5+1a4+1a31a6+1a5+1a4+0a3+1a2+0a1+0a0=01a6+1a5+0a4+1a3+0a1+1a1+0a0=01a6+0a5+1a4+1a3+0a2+0a1+1a0=0a6a5a4a3a2a1a01 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 13
24、7=0007131IrPH一致监督矩阵一致监督矩阵AT0T全零校正子全零校正子监督关系式监督关系式本讲稿第三十页，共八十八页a6a5a4a3a2a1a01 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 137=0007131IrPH0TATH或或0AHT377131137317 一致监督矩阵一致监督矩阵 H 。左边部分为监督序列生成矩阵。左边部分为监督序列生成矩阵 P ，右边部分为右边部分为r阶单位阵阶单位阵Ir。rnrn H 各行线性无关。各行也在许用码组集合中。各行线性无关。各行也在许用码组集合中。H 给定后信息位和监督位的关系就完全确定。给定后信息位和监督位的关
25、系就完全确定。“1”码的位置码的位置表示相应码元之间存在着监督关系。表示相应码元之间存在着监督关系。本讲稿第三十一页，共八十八页结论结论2:一致监督矩阵一致监督矩阵 H 。左边部分为监督序列生成矩阵。左边部分为监督序列生成矩阵 P ，右边部分为右边部分为r阶单位阵阶单位阵Ir。rkrn H 各行线性无关。各行线性无关。H 给定后信息位和监督位的关系就完全确定。给定后信息位和监督位的关系就完全确定。“1”码的位码的位置表示相应码元之间存在着监督关系。置表示相应码元之间存在着监督关系。如果接收码组如果接收码组B等于发送码组等于发送码组A，全零校正子表示无错。此种信道译码方式称为全零校正子表示无错。
26、此种信道译码方式称为校正子检验校正子检验。0AHT1rnr1nBHT1n伴随式检验伴随式检验本讲稿第三十二页，共八十八页校正子检验校正子检验检错原理：如果接收码组为检错原理：如果接收码组为B(用矩阵表示用矩阵表示)，有，有B =A，无错，则，无错，则 BHT=0，校正子，校正子 S 0 检验无错码。检验无错码。B A，有错，则，有错，则 BHT 0，校正子，校正子 S 0 检验有错码。检验有错码。纠错原理：如果纠错原理：如果B A，而，而B AE，或或BA+EE en-1en-2e1e01n称为错误图样行矩阵。称为错误图样行矩阵。ei0 bi =ai1 bi ai无错无错有错有错E中中1元素元
27、素(1码)的位置就是错码的位置。的位置就是错码的位置。本讲稿第三十三页，共八十八页根据校正子检验根据校正子检验B HT =(A+E)HT =A HT+E HT E HT S1nnr1nnrnr1n1n1nnrnr 校正子矩阵校正子矩阵S1r=1nnrE HT =HT或或ST =H E =Hr1rnn1如果纠如果纠n位码组中的位码组中的1位错码，校正子位错码，校正子 S 有有n种状态种状态(2r-1n)，错误图样错误图样E也有也有n种状态。即种状态。即Snr=nnnrE HT=HTnr或或ST =H Ernrn nn=Hrn1r1rr1本讲稿第三十四页，共八十八页(7，4）汉明码纠）汉明码纠1位
28、错位错S73=7773E HT=HT731 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 11 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1S73=1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1a6错错a5错错a4错错a3错错a2错错a1错错a0错错汉明码的哪一位有错，校正子汉明码的哪一位有错，校正子S 就等于就等于H矩阵相应顺序的列矩阵相应顺序的列校正子校正子S 等于等于H矩阵某一列
29、，将指示汉明码相应顺序的那位错。矩阵某一列，将指示汉明码相应顺序的那位错。本讲稿第三十五页，共八十八页或或ST =H Ernrn nn=HrnST =H E373777=H371 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 11 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1a6错错a5错错a0错错本讲稿第三十六页，共八十八页例：例：A=0110011B=01110111 1 1 0 1 0 01 1 0 1 0 1 0
30、1 0 1 1 0 0 10111011=011011a3错错H00100111 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1=110B=0010011a5错错本讲稿第三十七页，共八十八页三三.线性分组码的一般原理线性分组码的一般原理(n,k)线性分组码，可写出线性分组码，可写出r个线性无关的监督关系式构成个线性无关的监督关系式构成方程组。有方程组。有r个校正子的个校正子的2r1个校正子码：个校正子码：指示出指示出t个错码的位置。只纠方式。个错码的位置。只纠方式。可检出可检出e个错码。只检方式。个错码。只检方式。指示出指示出t个错码的位置，同时检出个错码的位置
31、，同时检出e个错码。检、纠结合。个错码。检、纠结合。由由r个监督关系得到监督位生成矩阵个监督关系得到监督位生成矩阵P rk，Q kr,G H knIk QP Irrn典型生成阵为典型生成阵为一致监督阵为一致监督阵为(1).(2).Q=PT;本讲稿第三十八页，共八十八页(3).汉明界（汉明界（确定线性分组码确定线性分组码n、k与与d0的关系）的关系）当给定纠错位数当给定纠错位数t时，不加证明的给出时，不加证明的给出“线性分组码最小线性分组码最小码距下界码距下界”nklog2ti0Cnit(d01)/2或或2 nkti0Cnit(d01)/2例例1，t1，d0 3由上式可计算出由上式可计算出2 n
32、kti0CniCn0Cn1本讲稿第三十九页，共八十八页2 7k1i0Cni 确定确定n、k，欲得到确保，欲得到确保t1，d03 的的n与与k各确定值，必首先选定各确定值，必首先选定n与与k中之一。中之一。2 7k8k 4，r743max=8n 6，r633mix如已选定如已选定n7如已选定如已选定k3C70C712 n31i0Cni=1+nCn0Cn1本讲稿第四十页，共八十八页例例2，t2，d0 5，2 nkti0CniCn0Cn1Cn22 7k292 7k29k 2，r725max如已选定如已选定n72 n5n 11，r6mix如已选定如已选定k5ti0CniC70C71C721+7+212
33、 n52i0CniCn0Cn1Cn21(n2+n)/21(n2+n)/2本讲稿第四十一页，共八十八页9.6 循环码循环码一一.特点特点*属线性分组码。具有线性分组码的所有特性。属线性分组码。具有线性分组码的所有特性。*循环性循环性 许用码集合中，任意码组许用码集合中，任意码组(字字)循环左移循环左移(或右移或右移)一位之后，仍是集合中的码，全零码除外。一位之后，仍是集合中的码，全零码除外。序序号号信息位信息位监督位监督位序序号号信息位信息位监督位监督位a6 a5a4a3 a2 a1 a0 a6 a5a4a3 a2 a1 a0 0000000041001011100101115101110020
34、101110611001013011100171110010例例1:(7,3)循环码，循环码，W=4，d0 41253764本讲稿第四十二页，共八十八页*一个长为一个长为n的循环码，它必是按模的循环码，它必是按模(xn+1)运算的余式。运算的余式。码多项式码多项式一个长为一个长为n的循环码的循环码(an-1 an-2a1 a0)用码多项式用码多项式 T(x)表示表示T(x)an-1 xn-1+an-2 xn-2+a1 x1+a0(an-1 an-2a1 a0)例例2：1 1 1 0 0 1 0T(x)x6+x5+x4+x其中：码元是多项式各项的系数；其中：码元是多项式各项的系数；x 仅起占位符
35、的作用仅起占位符的作用本讲稿第四十三页，共八十八页按模运算按模运算整数按模运算：整数整数按模运算：整数m按模按模n运算等于被运算等于被n除所得余数；除所得余数；m/n=Q+p/nmp记为记为也称按也称按n模运算模运算m与与p同余同余例例3：51 模模2、模、模4，20 模模2。码多项式码多项式F(x)按模按模N(x)运算：运算：F(x)/N(x)=Q(x)+R(x)/N(x)F(x)R(x)例例4：x4+x+1 x2+x+1（模模 x3+1）xx3+1x4+0+x2+01x4 +xx2+x+1余式余式(次数小于除式的次数次数小于除式的次数)本讲稿第四十四页，共八十八页T(x)an-1 xn-1
36、+an-2 xn-2+a1 x1+a0T(x)是长为是长为n的许用码组的码多项式的许用码组的码多项式而而xi T(x)an-1 xn-1+i+an-2 xn-2+i+a1 x1+i+a0 xixi T(x)按模按模(xn+1)运算运算 余式余式T(x)是是T(x)左移循环左移循环 i 位后的码组，仍是许用码组。所以位后的码组，仍是许用码组。所以*一个长为一个长为n的循环码，它必是按模的循环码，它必是按模(xn+1)运算的余式。运算的余式。xi T(x)T(x)an-1 xn-1+i+an-2 xn-2+i+a1 x1+i+a0 xixn+1an-1 xi-1+an-2 xi-2+an-ian-
37、1 xn-1+ian-1 xi-1an-2 xn-2+i+a1 x1+i+a0 xian-1 xi-1an-i-1 xn-1+an-i-2 xn-2+a1 x1+an-i本讲稿第四十五页，共八十八页二二.循环码的生成多项式循环码的生成多项式g(x)典型生成矩阵典型生成矩阵G为了产生许用码组，要找到循环码的为了产生许用码组，要找到循环码的生成多项式生成多项式g(x)或或G。分析分析1：g(x)的特征的特征已知已知G可以由可以由k个许用码组求出。个许用码组求出。在（在（n，k）循环码中，全零码除外有）循环码中，全零码除外有2k1个许用码组。个许用码组。设设g(x)是是a00，前，前k-1位全为零位
38、全为零(an-k 0)的码组对应的码组对应的的n-k次多项式，且唯一。（如果有两个，根据封闭性，相加次多项式，且唯一。（如果有两个，根据封闭性，相加an-k=0出现出现k连连0，不是许用码组。），不是许用码组。）an-1 an-2 an-k an-k-1 a1 a0krg(x)an-k xn-k an-k-1 xn-k-1 a1 x a0本讲稿第四十六页，共八十八页g(x)an-k xn-k an-k-1 xn-k-1 a1 x a0 xg(x)xk-1g(x)an-k xn-1 an-k-1 xn-2 a1 x a0 补补(k-1)位零位零0 0 0 an-k an-k-1 a1 a0k-1
39、r+1而而g(x)、xg(x)、xk-1 k个码多项式线性无关。个码多项式线性无关。将它们按行排好，作为生成矩阵将它们按行排好，作为生成矩阵G(x)左移循环左移循环1位对应的码多项式位对应的码多项式本讲稿第四十七页，共八十八页xk-1g(x)xk-2g(x)xg(x)g(x)G(x)如例如例1，(7，3)循环码，循环码，许用码中唯一的一个前许用码中唯一的一个前2位全零的码组是位全零的码组是 0 0 1 0 1 1 1 a6 a5 a4 a3 a2 a1 a0g(x)x4+x2+x+1xg(x)x5+x3+x2+xx2g(x)x6+x4+x3+x2 G(x)x6+x4+x3+x2x5+x3+x2
40、+xx4+x2+x+1g(x)xg(x)x2g(x)本讲稿第四十八页，共八十八页G(x)x6+x4+x3+x2x5+x3+x2+xx4+x2+x+1Gx1 0 1 1 1 0 00 1 0 1 1 1 00 0 1 0 1 1 1初等行变换初等行变换 1 0 0 1 0 1 10 1 0 1 1 1 00 0 1 0 1 1 1典型生成矩阵典型生成矩阵G所以信息序列乘以所以信息序列乘以G(x)，得循环码多项式。得循环码多项式。所以信息序列乘以所以信息序列乘以G，得循环码组，得循环码组(系统码系统码)。本讲稿第四十九页，共八十八页所以信息序列乘以所以信息序列乘以G(x)，得循环码多项式得循环码多
41、项式T(x)，即，即T(x)如如(7,3)循环码的信息元循环码的信息元a6 a5 a4，a6 a5 a4G(x)a6 a5 a4g(x)xg(x)x2g(x)a6 x2g(x)a5 x g(x)a4 g(x)（a6 x2 a5 x a4）g(x)m(x)g(x)信息码多项式信息码多项式所以所有循环码多项式所以所有循环码多项式T(x)，都可以被，都可以被g(x)整除。整除。或任意循环码多项式或任意循环码多项式T(x)，都是都是g(x)的倍式。的倍式。本讲稿第五十页，共八十八页分析分析2：寻找（：寻找（n，k）循环码的生成多项式）循环码的生成多项式假设假设 T(x)h(x)g(x)T(x)g(x)
42、xkT(x)n次多项式次多项式xkT(x)xn+1=Q(x)+T(x)xn+1=1xkT(x)xn+1+T(x)xk g(x)xk T(x)xn+1+T(x)xn+1xk+h(x)g(x)h(x)次数不大于次数不大于(k-1)g(x)是是(n-k)次次T(x)次数不大于次数不大于(n-1)多项式多项式g(x)，应该是，应该是(xn+1)的一个的一个(n-k)次因式。次因式。所以所以(n，k)循环码的生成循环码的生成本讲稿第五十一页，共八十八页所以只要知道所以只要知道 n、k 值。从值。从(xn+1)的分解因式中找出的分解因式中找出(n-k)次次 因式，即可作为（因式，即可作为（n，k）循环码的
43、）循环码的g(x)。例例5:g(x)应该是应该是4次因式，即次因式，即x7+1(x+1)(x3+x2+1)(x3+x+1)作为（作为（7，3）循环码的）循环码的 g(x),有有g(x)(x+1)(x3+x2+1)x4+x2+x+1 g(x)(x+1)(x3+x+1)x4+x3+x2+1或或本讲稿第五十二页，共八十八页三三 编、译码方法编、译码方法 根据纠、检要求，按汉明界确定根据纠、检要求，按汉明界确定n、k 值。值。从从(xn+1)的分解因式中选出的分解因式中选出(n-k)次因式，作为次因式，作为g(x)。根据所有循环码多项式根据所有循环码多项式T(x)，都可以被，都可以被g(x)整除的原则
44、编码。整除的原则编码。如果信息码多项式为如果信息码多项式为m(x),xn-k m(x)g(x)=Q(x)+r(x)g(x)所编码组为所编码组为T(x)xn-k m(x)+r(x)信息位在前信息位在前监督位在后监督位在后本讲稿第五十三页，共八十八页译码：译码：检错检错 接收码组是否能被接收码组是否能被 g(x)整除。整除。余式为零，无错。余式为零，无错。余式为非零，有错。余式为非零，有错。纠错纠错方法方法2：校正子检验：校正子检验方法方法1：将余式用查表法：将余式用查表法 求出错误图样求出错误图样 接收码组错误图样正确码组接收码组错误图样正确码组本讲稿第五十四页，共八十八页9.6 卷积码卷积码n
45、一般描述（参量的定义）一般描述（参量的定义）n卷积码的图形描述（树状图、网格图、状态图）卷积码的图形描述（树状图、网格图、状态图）n卷积码的解析描述卷积码的解析描述（生成矩阵（生成矩阵、生成多项式、生成多项式、冲激响应、冲激响应、基本生成矩阵基本生成矩阵）n卷积码的译码（维特比译码）卷积码的译码（维特比译码）本讲稿第五十五页，共八十八页1.一般描述（参量的定义）一般描述（参量的定义）l 卷积码属线性非分组码。卷积码属线性非分组码。l 卷积码表示为（卷积码表示为（n，k，N），通常），通常n，k都很小。都很小。其中的参量定义为：其中的参量定义为：n：子码长子码长（子码位数）。（子码位数）。k：子
46、码中：子码中信息段长信息段长（信息段位数）。（信息段位数）。N：以子码为单位的：以子码为单位的卷积码约束度。卷积码约束度。l 卷积编码器把卷积编码器把k比特信息段编成比特信息段编成n比特的子码，所编比特的子码，所编n比特的比特的 子码不仅与当前信息段有关，而且还与前子码不仅与当前信息段有关，而且还与前(N1)个信息段有个信息段有 关联。关联。约束长度为约束长度为Nn比特。编码效率为比特。编码效率为k/n。本讲稿第五十六页，共八十八页2.一般结构一般结构(n,k,N)卷积码编码器一般包括卷积码编码器一般包括:Nk级的输入移位寄存器级的输入移位寄存器;一组一组n个模个模2相加器相加器;n级输出移位
47、寄存器。级输出移位寄存器。12.k12.k 12.k12n-1nNk输入输入输出输出mX(m)本讲稿第五十七页，共八十八页3.卷积编码器的工作过程卷积编码器的工作过程M3M2M1例例1.（3,1,3）卷积编码器）卷积编码器y1,jy2,jy3,jmj1y2,j=mj2+mjmj2mjy3,j=mj2mj1+mjmjy1,jy2,jy3,jy1,j=mj（n，k，N）tM2M1起记忆作用的起记忆作用的移存器移存器本讲稿第五十八页，共八十八页9.6.1 卷积码的图形描述卷积码的图形描述1.树状图树状图卷积编码器的工作过程可用图形描述卷积编码器的工作过程可用图形描述由树杈、节点、子码组成。由树杈、节
48、点、子码组成。如例如例1，编码器的树状图。，编码器的树状图。寄存器初始状态为寄存器初始状态为00。对于第对于第j个输入信息段，相个输入信息段，相应有应有2(j-1)个节点、个节点、2(j-1k)个树杈。当个树杈。当jN时，树状时，树状图表示出节点的所有可能的图表示出节点的所有可能的状态和所有可能的树杈以及状态和所有可能的树杈以及所有可能的子码。当所有可能的子码。当jN,树树状图出现节点自上而下重复状图出现节点自上而下重复取取jN时的这段结构。时的这段结构。cd000111aba001110cda011100ab010101cdb000111ab001110cdc011100ab010101cd
49、d000000baab111001110011100010101111001110000111jNabcd本讲稿第五十九页，共八十八页树杈树杈(支路、路径支路、路径)表示编码器的工作过程表示编码器的工作过程(路径路径)。每个节点可引出。每个节点可引出2k个树杈。个树杈。对于例对于例1，k1，每个节点可引出每个节点可引出2个树杈。上支杈表示输个树杈。上支杈表示输入入“0”时编码器的输出路径，下支杈表示输入时编码器的输出路径，下支杈表示输入“1”时编码器的输出路时编码器的输出路径。径。“树杈上的码是输出子码树杈上的码是输出子码”。节点节点 表示表示(起记忆作用的起记忆作用的)移存器的状态。移存器的
50、状态。一般共有一般共有k(N-1)个这样的寄存器，共有个这样的寄存器，共有2k(N-1)种不同的状态。种不同的状态。如例如例1，起记忆作用的移存器是，起记忆作用的移存器是M1M2，有，有4种状态种状态(4个不同的个不同的节点节点)。a=00；b=01；c=10；d=11。M1M2：本讲稿第六十页，共八十八页cd000111aba001110cda011100ab010101cdb000111ab001110cdc011100ab010101cdd000000baab111001110011100010101111001110000111输入输入1，移存器，移存器输出的卷积码为输出的卷积码为11