9--第9章

null信道的纠错编码 *西北大学信息学院*信道的纠错编码 第9章内容*西北大学信息学院*内容 结束null*西北大学信息学院*信源编码 提高数字信号有效性 将信源的模拟信号转变为数字信号 降低数码率, 压缩传输频带(数据压缩) 信道编码 提高数字通信可靠性 数字信号在信道的传输过程中,由于实际信道的传输特性不理想以及存在加性噪声,在接收端往往会产生误码。 编码9.1 差错和差错控制系统分类*西北大学信息学院*9.1 差错和差错控制系统分类差错率是衡量传输质量的重要指标之一，它有几种不同的定义。 码元差错率/符号差错率 指在传输的码元总数中发生差错的码元数所占的比例(平均值),简称误码率。 是指信号差错概率 比特差错率 /比特误码率： 在传输的比特总数中发生差错的比特数所占比例 是指信息差错概率 对二进制传输系统,符号差错等效于比特差错；对多进制系统，一个符号差错对应多少比特差错却难以确定。差错率*西北大学信息学院*差错率根据不同的应用场合对差错率有不同的 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 : 在电报传送时,允许的比特差错率约为: 10－4～10－5； 计算机数据传输,一般要求比特差错率小于: 10－8～10－9； 在遥控指令和武器系统的指令系统中,要求有更小的误比特率或码组差错率。 差错图样*西北大学信息学院*差错图样为定量地描述信号的差错,定义差错图样E E=C－R (模M ) 最常用的二进制码可当作特例来研究，其差错图样等于收码与发码的模2加，即 E = C⊕R 或 C = R⊕E 设发送的码字C 1 1 1 1 1 1 1 1 1 1 接收的码字R 1 0 0 1 0 0 1 1 1 1 差错的图样E 0 1 1 0 1 1 0 0 0 0 差错图样中的“1”既是符号差错也是比特差错，差错的个数叫汉明距离。0:传输中无错 1:传输中有错 差错图样*西北大学信息学院*差错图样随机差错： 差错是相互独立的,不相关 存在这种差错的信道是无记忆信道或随机信道 突发差错： 指成串出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串字 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 0 突发长度= 4突发长度= 6差错控制系统分类 *西北大学信息学院*差错控制系统分类 前向纠错(FEC)： 发送端的信道编码器将信息码组编成具有一定纠错能力的码。 接收端信道译码器对接收码字进行译码,若传输中产生的差错数目在码的纠错能力之内时,译码器对差错进行定位并加以纠正。 差错控制系统分类 *西北大学信息学院*差错控制系统分类 自动请求重发(ARQ)： 发端发送检错码， 收端译码器判断当前码字传输是否出错； 当有错时按某种 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 通过一个反向信道请求发送端重传已发送的码字(全部或部分)。差错控制系统分类 *西北大学信息学院*差错控制系统分类 混合纠错(HEC)： 是FEC与ARQ方式的结合。 发端发送同时具有自动纠错和检测能力的码组,接收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。 如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。 差错控制系统分类 差错控制系统分类 信息反馈(IRQ)： 回程校验。 接收端把收到的码全部由反馈信道送回发送端，在发送端将原发送的码与反馈送回的马进行比较，发现错误后，把错误码再次重发，直到接收端正确接收为止。 *西北大学信息学院*9.2.1 纠错码分类 *西北大学信息学院*9.2.1 纠错码分类 从功能角度讲，差错码分为检错码和纠错码 检错码：用于发现差错 纠错码：能自动纠正差错 纠错码与检错码在理论上没有本质区别，只是应用场合不同，而侧重的性能参数也不同。纠错码分类 *西北大学信息学院*纠错码分类 按照对信息序列的处理方法，有分组码和卷积码 分组码： 将k个信息码元分成一组,由这k个码元按照一定规则产生r个监督码元,组成长度n = k + r的码字 卷积码： 先将信息序列分组,不同的是编解码运算不仅与本组信息有关,而且还与前面若干组有关。kk010 101 010 001 110 010xxxx 101xxxx 010 xxxxrnr纠错码分类 *西北大学信息学院*纠错码分类 按照码元与原始信息位的关系，分为 线性码：所有码元均是原始信息元的线性组合,编码器不带反馈回路。 非线性码：码元并不都是信息元的线性组合,可能还与前面已编的码元有关,编码器可能含反馈回路。 由于非线性码的分析比较困难，早期实用的纠错码多为线性码，但当今发现的很多好码恰恰是非线性码。纠错码分类 *西北大学信息学院*纠错码分类 按照适用的差错类型，分成: 纠随机差错码:用于随机差错信道,其纠错能力用码组内允许的独立差错的个数来衡量。 纠突发差错码:针对突发差错而设计,其纠错能力主要用可纠突发差错的最大长度来衡量。9.2.2 矢量空间与码空间*西北大学信息学院*9.2.2 矢量空间与码空间块码：也叫（n,k)分组码，是最基本的纠错码 把信息流切割为k符号一组的独立块后， 编成由n个码元组成的码字。 设有n重有序元素的集合V={vi},vi=(vi0,vi1,…vij,…,vi(n-1),),vij∈F. F－码元所在的数域 满足条件： ① V中矢量元素在矢量加运算下构成加群； ② 存在任意a∈F和vi∈V, 存在 a·vi ∈V ③ 分配率、结合率成立 V是数域F上的 n维矢量空间，也称n维线性空 间，n维矢量称 n重，码字叫码矢 矢量空间与码空间*西北大学信息学院*矢量空间与码空间码矢的运算法则遵从矢量运算法则 矢量加 标乘 点积和内积 矢量空间各元素有可能线性相关也可能线性无关 如果存在一组与线性无关的矢量V1， V2,…Vn则这些矢量的线性组合的集合就构成了一个矢量空间 矢量空间的基底－V1，V2,…Vn n个基底“张成” n维矢量空间V n。矢量空间与码空间*西北大学信息学院*矢量空间与码空间每个空间或子空间中必然包含零矢量。 “重数”：构成矢量的有序元素的个数 “维数”：张成矢量空间的基底的个数 从概念上来讲，维数不可能大于重数，而当维数小于重数时就说明是个子空间 某矢量空间的任意元素与另一矢量空间的任意元素正交，则这两个矢量空间正交。正交的两个子空间互为对偶空间，其中一个空间是另一个空间的零空间。矢量空间与码空间*西北大学信息学院*矢量空间与码空间码字Ci是个码元的有序排列，是 维 重矢量空间V 的元素之一。而矢量空间V 的元素并不一定是码字。 码字C i写作(ci0,ci1,…ci(n-1)) ,将码字的集合写作C，称为码集。 分组编码的任务： 1. 选择一个维 重子空间作为码空间。 2. 确定由维 重信息空间到 维 重码空间的映射方法9.2.3 码距 纠错能力，MDC码及重量谱*西北大学信息学院*9.2.3 码距 纠错能力，MDC码及重量谱定理1 任何最小距离dmin的线性分组码，其检错能力为（ dmin -1），纠错能力为： t=INT [dmin -1/2] 最小距离 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明码集中时各码字差异的程度，差异越大越容易区分，抗干扰能力越强，是衡量分组码性能最重要的指标之一。null*西北大学信息学院*汉明重量/码字重量/W：码字中非0码元符号的个数，称为该码字的汉明重量。 在二元线性码中，码字重量就是码字中含“1”的个数。 最小重量/Wmin ：线性分组码CI中，非0码字重量最小值，叫做码CI的最小重量： Wmin =min{W(V),V∈CI ,V≠0} 最小距离与最小重量的关系：线性分组码的最小距离等于它的最小重量。 null*西北大学信息学院*定理2 线性分组码的最小距离dmin等于码集中时非零码字最小重量: dmin＝min {W(Ci)} Ci∈C及Ci≠0 定理3 (n,k)线性分组码最小距离等于dmin充要条件是： 校验矩阵H 中有(dmin -1)列线性无关. null*西北大学信息学院*汉明球：以码字C为中心，半径为 t 的汉明球是与 C 的汉明距离≤ t 的向量全体 SC(t) 任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离dmin。null*西北大学信息学院*最小距离与检错能力： dmin=l+1 或 l=dmin－1null*西北大学信息学院*最小距离与检、纠错能力: dmin=t+l+1 或 t+l=dmin－1MDC码及重量谱*西北大学信息学院*MDC码及重量谱MDC 若某码的最小距离达到了可能取得的最大值即dmin= (n-k+1),则称该线性分组码为极大最小距离码（maximized disdance code, MDC） RS(reed-solomon)码就是MDC 码 重量谱又称距离谱，就是码距的分布特性，其中的最小重量就是dmin 。 用多项式表示为 null*西北大学信息学院* A(x)=A0+A1x+A2x2＋A3x3＋…+Anxn =∑i=1nAixi 表明在码长n 的码集里，包含重量为0的码字A0个(线性码一定包含一个重量为0的全0码)，重量为1的码字A1个，重量为n的码字An个null*西北大学信息学院*一.从信道编码定理的 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 出发 1.增大信道容量C ①扩展带宽②加大功率 ③降低噪声 2.减小码率R 对于Q进制（N,K）分组码，码率R＝KlbQ/N. ①Q,N不变而减小K，降低信息源速率 ②Q,K不变而增大N，提高符号速率 ③N, K不变而减小Q，减小信道的输入输出符号集 3.增大码长N 二.从概念上分析纠错编码的基本原理，可以把纠错能力的获取归结为两条： 1.利用冗余度 2.噪声均化 null*西北大学信息学院*传输冗余比特必然要动用冗余的资源。 时间： 比如一个比特重复发几次,或一段消息重复发几遍,或根据收端的反馈重发受损信息组。 频带： 插入冗余比特后传输效率下降,若要保持有用信息的速率不变,方法之一是增大符号传递速率(波特率),结果就占用了更大的带宽。 功率： 采用多进制符号,用8进制ASK符号代替4进制ASK符号来传送2比特信息,可腾出位置另传1冗余比特。 8进制ASK符号的平均功率肯定比4进制时要大,这就是动用冗余的功率资源来传输冗余比特。 设备复杂度： 加大码长,采用网格编码调制,是在功率、带宽受限信道中实施纠错编码的有效方法,代价是算法复杂度的提高,需动用设备资源。噪声均化的方法有3种*西北大学信息学院*噪声均化的方法有3种1.增加码长 2.卷积 －卷积码在一定束缚长度内的若干码字之间也加进了相关性，而是一串码字来做判决，再加上适当的编译码方法，达到噪声均化目的 3.交错 －交错是对付突发差错的有效措施。交错的效果取决于信道噪声的特点和交错方式。null*西北大学信息学院*最大似然译码 译码过程 由图6.1.2可见：译码器接收到一个接收码字 R 后，按编码规则对 R 进行译码后输出信息码组的估值 m’； 信息码组与码字 C 之间是有固定规则的，这相当于信道译码器能给出码字 C 的估值 C’。当C’≠C时就出现了译码错误。因为只有当 C’=C 时，m’=m。几种简单纠检错码*西北大学信息学院*(1)偶（或奇）校验方法 p 为偶校验位 m0+m1+m2+…+mk－1+p=0 (mod 2) 则 C =(m0,m1,m2,…,mk－1,p) 为一个偶校验码字。 C 中一定有偶数个“1” 所有可能的 C 的全体称为一个码率为 k/(k+1) 的(k+1,k) 偶校验码； 当差错图案 E 中有奇数个“1”，即 R 中有奇数个位有错时，可以通过校验方程是否为0判断有无可能传输差错。 校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错。几种简单纠检错码null*西北大学信息学院*(2)多个奇偶校验位 一个校验位可以由信息位的部分或全部按校验方程产生； 例如 C 是一个对阵列消息进行垂直与水平校验以及总校验的码字； 其码率为当校验位数增加时，可以检测到差错图案种类数也增加，同时码率减小。null*西北大学信息学院*(3) 重复消息位方法 n重复码：码率为 1/n，仅有两个码字 C0和 C1，传送1比特(k=1)消息； C0=(00…0)，C1=(11…1) n重复码可以检测出任意小于 n/2 个差错的错误图案 BSC信道：pb≤1/2，n比特传输中发生差错数目越少，概率越大 (1－pb)n> pb(1－pb)n －1>… > pbt(1－pb)n －t>… > pbn 总认为发生差错的图案是差错数目较少的图案，当接收到重复码的接收序列 R 中“1”的个数少于一半时，认为发送的是C0，否则认为是 C1。null*西北大学信息学院*(4) 等重码/定比码 设计码字中的非0符号个数恒为常数，即 C 由全体重量恒等于 m 的 n 重向量组成。 5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。 9.3　线性分组码*西北大学信息学院*9.3　线性分组码 9.3.1 线性分组码的生成矩阵和校验距阵1239.3.4 完备码9.3.2 伴随式与标准阵列译码9.3.1 线性分组码的生成矩阵和校验距阵*西北大学信息学院*9.3.1 线性分组码的生成矩阵和校验距阵 校验矩阵 生成矩阵 null*西北大学信息学院*线性分组码的编码：线性分组码的编码过程分为两步： 把信息序列按一定长度分成若干信息码组，每组由 k 位组成； 编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成 n 重 (n>k) 码字，其中 (n－k) 个附加码元是由信息码元的线性运算产生的。 信息码组长 k 位，有 2k 个不同的信息码组，则有 2k 个码字与它们一一对应。null*西北大学信息学院*码矢：一个 n 重的码字可以用矢量来表示 C=(Cn－1,Cn－1,…,C1,C0 ) 所以码字又称为码矢。 (n,k) 线性码：信息位长为 k，码长为 n 的线性码。 编码效率/编码速率/码率/传信率：R=k /n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。null*西北大学信息学院*(1) 一致监督方程 编码就是给已知信息码组按预定规则添加监督码元，以构成码字。 在 k 个信息码元之后附加 r(r=n－k) 个监督码元，使每个监督元是其中某些信息元的模2和。 举例：k=3, r=4，构成 (7,3) 线性分组码。设码字为 (C6,C5,C4,C3,C2,C1,C0) C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1” 监督元可按下面方程组计算null*西北大学信息学院*一致监督方程/一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。 由于一致监督方程是线性的，即监督元和新信源之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。null*西北大学信息学院*(2) 举例 信息码组 (101)，即C6=1, C5=0, C4=1 代入 (6.2.1) 得： C3=0, C2=0, C1=1, C0=1 由信息码组 (101) 编出的码字为 (1010011)。其它7个码字如表6.2.1。null*西北大学信息学院*(3) 一致监督矩阵 为了运算方便，将式(6.2.1)监督方程写成矩阵形式，如右所示 可写成 H CT=0T或C HT=0 CT、HT、0T分别表示C、H、0的转置矩阵。null*西北大学信息学院*系数矩阵 H 的后四列组成一个 (4×4) 阶单位子阵，用 I4 表示，H 的其余部分用 P 表示null*西北大学信息学院*推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r(r=n－k) 个监督元与信息元之间的关系可由下面的线性方程组确定。 令上式的系数矩阵为 H，码字行阵列为 C null*西北大学信息学院*对H 各行实行初等变换，将后面 r 列化为单位子阵，于是得到下面矩阵，行变换所得方程组与原方程组同解。 监督矩阵H 的标准形式：后面 r 列是一单位子阵的监督矩阵H。(4)生成矩阵*西北大学信息学院*(4)生成矩阵线性分组码码空间C是由k个线性无关的gk-1,…g1,… g0基底张成的维重子空间，码空间的所有元素都可以写成个基底的线性组合，即 C=mk-1 gk-1 +…+m1g1+m0g0 (6-3-1) 用gi表示第基底并写成矩阵形式 gi＝［ gi(n-1), gi(n-2),… ，gi1, gi0］(6-3-2) 再将k个基底排列成k行n列的G矩阵： null*西北大学信息学院*G=[gk-1,…g1 g0]T= g(k-1)(n-1) … g(k-1)1 g(k-1)0 g1(n-1) g11 g10 g0(n-1) g01 g00 (6-3-3) 对照式（6－3－1），得C=mG 其中m＝[mk-1, …m1 m0]是1×k的信息元矩阵，由于k个基底即G的k个行矢量线性无关，G的秩一定为k。当信息元确定，码字仅由G决定，因此称这个k×n矩阵G为该（n,k）线性分组码的生成矩阵。null*西北大学信息学院*线性系统分组码 通过行初等变换，将 G 化为前 k 列是单位子阵的标准形式 校验矩阵*西北大学信息学院*校验矩阵于任何一个(n,k)分组码的码空间C相对应，一定存在一个对偶空间D。将D空间的n-k个基底排列以来可以构成一个(n-k)×n矩阵，将这个矩阵称为码空间C的校验矩阵H C和D的对偶是相互的，G是C的生成矩阵又是D的校验矩阵，而H是D 的生成矩阵，又是C的校验矩阵，如下图码空间与映射*西北大学信息学院*码空间与映射K维k重信息组空间mk维n重码空间c Gn-k维n重对偶空间D Hn维n重空间Vnnull*西北大学信息学院*生成矩阵与一致监督矩阵的关系 由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足Hr×nCTn×1=0Tr×1，则有 Hr×nGTn×k=0Tr×k 或 Gk×nHTn×r=0k×r 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换。null*西北大学信息学院*举例 已知(7,4)线性系统码的监督矩阵为null*西北大学信息学院*对偶码：对一个(n,k)线性码 CI，由于Hr×nGTn×k=0Tr×k，如果以G 作监督矩阵，而以H 作生成矩阵，可构造另一个码CId，码CId是一个(n,n－k)线性码，称码CId为原码的对偶码。 例如： (7,4)线性码的对偶码是(7,3)码： (7,3)码的监督矩阵H(7,3)是(7,4)码生成矩阵G(7,4) (7,3) 码的生成矩阵 G(7,3) 是 (7,4) 码监督矩阵 H(7,4) 9.3.2伴随式与标准阵列译码*西北大学信息学院*9.3.2伴随式与标准阵列译码 码字C＝(cn-1,…c1,c0)在传输过程中受到各种干扰，接受端的收码R＝(rn-1,…r1,r0)已不一定等于发码C，两者间的差异就是差错。我们定义差错式样为差错图案E： E= (en-1, …e1,e0) =R-C =(rn-1-cn-1， …r1-c1,r0-c0) 对于二进制码模二减等同于模二加： E=R+C 及 R=C+E 码字与校验矩阵的正交性CHT=0,可检验R是否有错。 null*西北大学信息学院* RHT=(C+E)HT=CHT+EHT=0+EHT=EHT 当等于零时收码无误，不等于零时有误 定义RHT运算结果为伴随式S S=(sn-k-1,…s1,s0)= RHT=EHT 编码mG○＋计算RHT=S计算EC=R+E输出mcER编译码过程框图null*西北大学信息学院*举例： (7,3)码接收矢量 R 的伴随式计算 设发送码矢C=1010011，接收码字R＝1010011，R与C相同。 null*西北大学信息学院*若接收字中有一位错误null*西北大学信息学院*当码元错误多于1个时 标准阵列译码*西北大学信息学院*标准阵列译码 实时译码过程中我们可以构造标准阵列译码表，用存储，查询量的增大换取实时计算量的减小. 构造标准阵列译码的一般方法 1）用概率译码确定各伴随式对应的差错图案 2）确定标准阵列译码表的第一行和第一列 3）在码表的第j行，第i列填入从Ci+Ejnull*西北大学信息学院*标准阵列构造方法 先将 2k 个码矢排成一行，作为标准阵列的第一行，并将全0码矢C1=(00…0)放在最左面的位置上； 然后在剩下的 (2n－2k) 个 n 重中选取一个重量最轻的 n 重 E2 放在全0码矢 C1 下面，再将 E2 分别和码矢 相加，放在对应码矢下面构成阵列第二行; 在第二次剩下的 n 重中，选取重量最轻的 n 重 E3，放在 E2 下面，并将 E3 分别加到第一行各码矢上，得到第三行； …，继续这样做下去，直到全部 n 重用完为止。得到 (n,k) 线性码的标准阵列。标准阵列译码表*西北大学信息学院*标准阵列译码表null*西北大学信息学院*线性码纠错极限定理：二元 (n,k) 线性码能纠 2n－k 个错误图样。这 2n－k 个可纠的错误图样，包括0矢量在内，即把无错的情况也看成一个可纠的错误图样。 陪集：标准阵列的每一行叫做码的一个陪集。 陪集首：每个陪集的第一个元素叫做陪集首。 每一列包含 2n－k 个元素，最上面的是一个码矢，其它元素是陪集首和该码矢之和，例如第 j 列为null*西北大学信息学院*若发送码矢为 Cj，信道干扰的错误图样是陪集首，则接收矢量 R 必在 Dj 中； 若错误图样不是陪集首，则接收矢量 R不在 Dj 中，则译成其它码字，造成错误译码； 当且仅当错误图样为陪集首时，译码才是正确的。 可纠正的错误图样：这 2n－k 个陪集首称为可纠正的错误图样。9.3.3 完备码*西北大学信息学院*9.3.3 完备码完备码特性：围绕 2k 个码字，汉明距离为t=[(dmin－1)/2]的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码与发送码的距离至多为 t，这时所有重量≤t的错误图样都能用最佳（最小距离）译码器得到纠正，而所有重量≥t+1的错误图样都不能纠正。 满足方程 2n-k＝ ∑i=0t（n i）的二元（n,k）线性分组码称为完备码。 null*西北大学信息学院*null*西北大学信息学院*汉明码（Hamming code） 汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。 null**汉明码的结构参数： 纠一个错误的线性码，其最小距离 dmin=3 ；监督矩阵任意两列线性无关/ H 的任两列互不相同；没有全0的列。 监督元个数 n－k=r；H 阵中每列有 r 个元素，至多可构成 2r－1种互不相同的非0列。 对于任意正整数 m≥3，汉明码的结构参数为 码长： n=2m－1 信息位数： k=2m－m－1 监督位数： n－k=m 码的最小距离：dmin=3(t=1)null**汉明码监督矩阵构成的两种方式 构成 H 阵的标准形式，H=[Q Im]，其中 Im 为 m 阶单位子阵，子阵 Q 是构造 Im 后剩下的列任意排列。用这种形式的 H 阵编出的汉明码是系统码。 按m重表示的二进制顺序排列。按这种形式 H 阵编出的码是非系统码。当发生可纠的单个错误时，伴随式为 H 阵中对应的列，所以伴随式的二进制数值就是错误位置号，有时这种码译码比较方便。 由于汉明码可纠的错误图样数为 null**构造 (7,4) 汉明码的一致监督矩阵并设计编、译码器。 解：监督矩阵为 (3×7) 矩阵null**构造 (7,4) 汉明码的伴随式null**构造 (7,4) 汉明码的纠错译码电路null*西北大学信息学院* 9.4 循环码循环码的多项式描述循环码的生成多项式系统循环码 多项式运算电路null*西北大学信息学院*(1) 循环码的性质 循环码是线性分组码的一个重要子类； 由于循环码具有优良的代数结构，使得可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法； 循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。 循环码的多项式描述null*西北大学信息学院*(2) 循环码的定义 循环码：如果 (n,k) 线性分组码的任意码矢 C=(Cn－1,Cn－2,…,C0) 的 i 次循环移位，所得矢量 C(i)=(Cn－1－i,Cn－2－i,…,C0,Cn－1,…,Cn－i) 仍是一个码矢，则称此线性码为 (n,k) 循环码。循环码的多项式描述null*西北大学信息学院*(3) 码多项式 码多项式：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为 C(x)=Cn－1xn－1+Cn－2xn－2+…+C0) 码多项式 i 次循环移位的表示方法 记码多项式C(x)的一次左移循环为 C(1)(x) ，i 次左移循环为 C(i)(x) 循环码的多项式描述null*西北大学信息学院*码多项式的模 (xn+1) 运算 0和1两个元素模2运算下构成域。 循环码的多项式描述null*西北大学信息学院*若 p 为素数，则整数全体在模 p 运算下的剩余类全体 在模 p 下构成域。 以 p=3 为模的剩余类全体 模2运算的规则如下： 循环码的多项式描述null*西北大学信息学院*码矢 C 循环 i 次所得码矢的码多项式 C(x) 乘以 x，再除以 (xn+1)，得循环码的多项式描述null*西北大学信息学院*上式表明：码矢循环一次的码多项式 C(1)(x) 是原码多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作 因此， C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即 结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再模 (xn+1)。 循环码的多项式描述null*西北大学信息学院*(4) 举例：(7,3) 循环码， 可由任一个码矢，比如 (0011101) 经过循环移位，得到其它6个非0码矢； 也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,…,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。 循环码的多项式描述null*西北大学信息学院* 循环码的多项式描述循环码的循环移位null*西北大学信息学院*(1) 循环码的生成矩阵 根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在 (n,k) 循环码的 2k 个码字中，取前 (k－1) 位皆为0的码字 g(x)（其次数r=n－k），再经 (k－1) 次循环移位，共得到 k 个码字： g(x),xg(x),…,xk－1 g(x) 循环码的生成多项式 这 k 个码字显然是相互独立的，可作为码生成矩阵的 k 行，于是得到循环码的生成矩阵 G(x)null*西北大学信息学院*(2) 循环码的生成多项式 码的生成矩阵一旦确定，码就确定了； 这就说明： (n,k) 循环码可由它的一个 (n－k) 次码多项式 g(x) 来确定； 所以说 g(x) 生成了 (n,k) 循环码，因此称 g(x) 为码的生成多项式。循环码的生成多项式null*西北大学信息学院*(3) 生成多项式和码多项式的关系 定理：在 (n,k) 循环码中，生成多项式 g(x) 是惟一的 (n－k) 次码多项式，且次数是最低的。 [证明]： 先证在 (n,k) 循环码系统中存在 (n－k) 次码多项式。 因为在 2k 个信息组中，有一个信息组为 ，它的对应码多项式的次数为 n－1－(k－1)=n－k (n－k) 次码多项式是最低次码多项式。 若 g(x) 不是最低次码多项式，那么设更低次的码多项式为g’(x) ，其次数为 (n－k－1)。 g’(x) 的前面 k 位为0，即 k个信息位全为0，而监督位不为0，这对线性码来说是不可能的，因此 g(x) 是最低次的码多项式，即 gn－k 必为1。循环码的生成多项式null*西北大学信息学院*g0=1，否则经 (n－1) 次左移循环后将得到低于 (n－k) 次的码多项式。 g(x) 是惟一的 (n－k) 次多项式。 如果存在另一个 (n－k) 次码多项式，设为 g’’(x) ，根据线性码的封闭性，则 g(x) + g’’(x) 也必为一个码多项式。由于 g(x)和 g’’(x) 的次数相同，它们的和式的 (n－k) 次项系数为0，那么 g(x) + g’’(x) 是一个次数低于 (n－k) 次的码多项式，前面已证明 g(x) 的次数是最低的，因此 g’’(x) 不能存在，所以 g(x) 是惟一的 (n－k) 次码多项式。循环码的生成多项式null*西北大学信息学院*定理：在 (n,k) 循环码中，每个码多项式 C(x) 都是 g(x) 的倍式；而每个为 g(x) 倍式且次数小于或等于 (n－1) 的多项式，必是一个码多项式。 [证明]： 设 m=(mk－1,mk－2,…,m0) 为任一信息组，G(x) 为该 (n,k) 循环码的生成矩阵，则相应的码多项式为 循环码的生成多项式null*西北大学信息学院*上式表明：循环码的任一码多项式为 g(x) 的倍式。 显然，凡是为 g(x) 的倍式且次数小于或等于 (n－1) 的多项式，一定能分解成上式的形式，因而它就是信息多项式 m(x)=(mk－1xk－1+mk－2 1xk－2+…+m0) 并由生成矩阵 G(x) 所生成的码多项式。 定理:全部码多项式都是最低次的 (n－k) 次码多项式的倍式，则此线性码为一个 (n,k) 循环码。 注：一般说来，这种循环码仍具有把 (n,k) 线性码码中任一非0码矢循环移位必为一码矢的循环特性，但从一个非0码矢出发，进行循环移位，就未必能得到码的所有非0码矢了。所以称这种循环码为推广循环码。 循环码的生成多项式null*西北大学信息学院*码字循环关系图 单纯循环码的码字循环图：(7,3)循环码循环码的生成多项式null*西北大学信息学院*推广循环码的码字循环图：(6,3)循环码循环码的生成多项式null*西北大学信息学院*(4) 如何寻找一个合适的生成多项式 由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。 这说明：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。 所以：作一循环码的关键，就在于寻找一个适当的生成多项式。 循环码的生成多项式null*西北大学信息学院*定理： (n,k) 循环码的生成多项式 g(x) 是 (xn+1)的因式，即 xn+1=h(x)g(x)。 [证明]： 由于 xk g(x) 是 n 次多项式，可表示为 xk g(x)=1(xn+1)+ g(k)(x) (6.3.1) 式中 g(k)(x) 是码多项式 g(x) 乘以 xk 除以 (xn+1) 的余式。 根据循环码的移位关系，它是 g(x) 循环移位 k 次所得到的码多项式，因而 g(k)(x) 是 g(x) 的倍式。 设 g(k)(x)=m(x)g(x) 代入式(6.3.1)得 (xn+1)=[xk+m(x)]g(x) 上式表明： g(x) 是 (xn+1) 的因式。循环码的生成多项式null*西北大学信息学院*定理：若 g(x) 是一个 (n－k) 次 多项式，且为(xn+1) 的因式，则 g(x) 生成一个 (n,k) 循环码。 [证明]： 由于 g(x) 是一个 (n－k) 次多项式，且为 (xn+1) 的因式，所以 g(x), xg(x),…, xk－1  g(x) 是 k 个次数小于 n，并且彼此独立的多项式； 循环码的生成多项式 将此多项式用作码的生成矩阵的 k 行，得到 (n,k) 线性码的生成矩阵；null*西北大学信息学院*设信息组 m=(mk－1,mk－2,…,m0)，则相应的码字为 C(x)=mG(x)=(mk－1xk－1+mk－2 1xk－2+…+m0)g(x)= m(x)g(x) C(x)≤n－1； m(x) 是 2k 个信息多项式的表示式； 所以 C(x) 即为相应 2k 个码多项式的表示式。 因此，g(x) 生成一个 (n,k) 线性码。 C(x) 是 (n－k) 次多项式 g(x) 的倍式，所以 g(x) 生成一个 (n,k)循环码。 结论：当求作一个(n,k)循环码时，只要分解多项式(xn+1) ，从中取出(n－k)次因式作生成多项式即可。循环码的生成多项式null*西北大学信息学院*举例：求 (7,3) 循环码的生成多项式。 [解]： 分解多项式 xn+1，取其4次因式作生成多项式 x7+1= (x+1) (x3+x2+1) (x3+x+1) 可将一次和任一个三次因式的乘积作为生成多项式，因而可取 g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1 或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1 循环码的生成多项式null*西北大学信息学院*(5) 循环码的监督多项式和监督矩阵 循环码的监督多项式：设 g(x) 为 (n,k) 循环码的生成多项式，必为 (xn+1) 的因式，则有 xn+1=h(x)g(x)，式中h(x) 为 k 次多项式，称为 (n,k) 循环码的监督多项式。 (n,k) 循环码也可由其监督多项式完全确定。 举例： (7,3) 循环码 x7+1= (x3+x+1)(x4+x2+x+1) 4次多项式为生成多项式 g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0 3次多项式是监督多项式 h(x)=x3+x+1=h3x3+h2x2+h1x+h0 循环码的生成多项式null*西北大学信息学院*循环码的监督矩阵 由等式 x7+1= h(x)g(x) 两端同次项系数相等得 将上面的方程组 写成矩阵形式循环码的生成多项式null*西北大学信息学院*上式中，列阵的元素是生成多项式 g(x) 的系数，是一个码字，那么第一个矩阵则为(7,3)循环码的监督矩阵，即 循环码的生成多项式null*西北大学信息学院*循环码监督矩阵的构成 由式 (6.3.2) 可见，监督矩阵的第一行是码的监督多项式 h(x) 的系数的反序排列，第二、三、四行是第一行的移位； 可用监督多项式的系数来构成监督矩阵循环码的生成多项式null*西北大学信息学院*(n,k) 循环码的监督矩阵 对偶问题 如果 xn+1=h(x)g(x)，其中 g(x) 为 (n－k) 次多项式，以 g(x)为生成多项式，则生成一个 (n,k) 循环码； 以 h(x) 为生成多项式，则生成 (n,n－k) 循环码； 这两个循环码互为对偶码。 循环码的生成多项式null*西北大学信息学院*(1) 系统循环码构成 设信息向量 m=(mk－1,mk－2,…,m0) 信息多项式 m(x)=mk－1xk－1+mk－2 xk－2+…+m0 码多项式的高次幂部分等于m(x)，即 C(x)=cn－1xn－1+…+ cn－kxn－k+ cn－k－1xn－k－1 …+c1x +c0 =xn－k m(x)+q(x) q(x)的次数