（信号与信息处理专业论文）通信系统中的crc算法的研究和工程实现.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师吴文礼教授、牛凯博士的指导下进行的 研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列 的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：豳亟2 查 本人承担一切相关责任。 日期：2 1 堑墨i l r 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学 本人签名 导师签名 适用本授权书。 日期： 日期： 如毋 n t 时，岛= 0 ，g 。一t 0 ；当f i 时，岛= 0 ，丸o 。 由 ( z ) ：! 要得 ( x ) g ( x ) ：x 一十1 ，从而9 0 ：1 。由互反多项式定义得 g 【x ) k ( 工) = 击 。7 ，= 0 e 甘于g ( x ) ( x ) = 算”+ 1 zo ( m o d ( x ”+ 1 ) ) ，即 g ( x ) ( 工) 三( g o o + g l 吃一1 + - + g 。l 五1 ) + ( g o 啊+ g l 矗。+ + g 。一1 2 ) z + + ( g o l + g l 。一2 + + g 。一l o ) 工“一1 ( m o d ( z “+ 1 ) ) s o ( m o d ”+ 1 ) ) 从而j “，z o ，x 1 ，x “的系数全为o ，即 g o 。一l + g i ，一2 + + g 。一1 矗o = ( g o ，g l ，占。一1 ) ( 。一l ， 。一2 ， 9 1 吃一1 + 。+ 亭。一1 j 1 1 + g o o = ( g l ，9 2 ，g 。一1 ，占o ) ( 。一i ， 。一2 ， ，) 7 = o ) 7 = o g 。一i 。一1 t g o 五。一2 + + g 。一2 o = ( g 。一2 ，g o ，g i ，一，g 。一2 ) ( 。一i ， 。一2 ，) 7 = o 1 9 即 = ( k 一，k 一2 ，- ，) 与g o = ( g o ，g 。，一，g 。_ 1 ) ，q = ( 9 1 ，9 2 ，g 。一1 ，g o ) ， 瓯一1 = ( g ，g o ，自，g h ) 都正交，而g o ，g l ，g h 是c 的基，故 c 1 。又 伊是循环码，则日。= ( 以， 。， 。，+ 。) c 1 ，从而何。对应的多项 式恰好是k ( 砷，则k ( 砷( c 1 ) 。又 = 。= = = 0 ， o ，故 肋f ( z ) = 七，而d i m c l = h d i m c = n 一i ，从而( c 1 ) 的生成多项式是k 次的， 故k ( 曲是c 1 的生成多项式。证毕。 设g 0 ，g l i 一，g 。是二元k ，后】循环码c 的基，、则c 的生成矩阵为 g = ( g o ，g 1 ，g 。) 7 。 设 k ( 砷是 c 1 的生成多项式，则 k ( x ) ，妫。( x ) ，x ”“ 。( x ) 是f ( c 1 ) 的基，对应的码字分别记为 风，q ，日m 一，令= o 日l ： “ 则h 是码c 的生成矩阵，且g 7 = 0 。 由于循环码定是线性码，因此v c f 为码c 的码字的充要条件是7 = o 。 定理7g f ( q ) ( q 为素数或素数的幂) 上的 n ，k 循环码中，存在唯一的n k 次 首一多项式 g ( x ) = x ”“+ g 一l x ”“1 + + 蜀x + g o ，每一码多项式c ( x ) 都是g ( x ) 的倍式，且 每一个小于等于( n 1 ) 次的g ( x ) 倍式一定是码多项式( 循环码的移位后所得到的 码字用多项式表示) 。 证明令g ( z ) = 工+ g ，。x 1 + + g l x + 9 0 是循环码次数最低的非零码多项 式，由于码的循环特性，醒( x ) ，x 2 9 ( x ) ，x ”g ( x ) 也必是码多项式。因为循环 码是线性码，所以楞( x ) ，x 2 9 ( x ) ，工”1 9 ( 曲的线性组合： m 。一卜，工舻卜7 9 ( 工) + + 阡l l 昭( 石) + 所o g ( 工) = g ( 工) 时( 彳) ，m f 1 5 f ( g ) ，f = o ，1 ，再一l 一， 也必在循环码中，是个码多项式。所以每一个小于等于( n 一1 ) 次的g ( x ) 倍式一 定是码多项式。 反之，若c ( x ) 是一码多项式，则由欧几里得除法可知： c ( x ) = 碍( x ) g ( z ) + r ( x ) ，o s a 。“茸) a 。g ( 算) 或r ( x ) = o ，( 主) = c ( x ) 一g ( 工) 占( z ) 由于是线性码，所以c ( 孑) 一g ( x ) g ( 石) = r ( z ) 也必是码多项式。但 a 。，( z ) 2 时是q 进制码。二元分 组码是最基本、最重要的。 k 位二进制信息组有2 。种组合，构成g f ( 2 ) 上的k 维k 重矢量空间：而n 位 二进制数共有2 ”种组合，构成g f ( 2 ) 上的n 维n 重矢量空浏，通常2 ” 2 。纠 错编码的任务是在n 维n 重矢量空间的2 “种可能组合中选择2 个构成个子空 间，或称许用码码集c ，然后设法将k 比特信息组一一对应地映射到许用码码集 c 。不同的编码算法对应不同的码集以及不同的映射算法，把这样得到的码称为 ( n ，k ) 线性分组码。不编码时，一个二进制码元可携带1 比特信息( 传信率为1 b 符号) ；编码后，n 个二进制码元携带k 比特信息( 传信率为( k n ) b 符号) 。定义 k n = r c 为二元分组码的码率，或者说是效率。 一 在g f ( 2 ) 上。汉明重量：n 重矢量r 中，非零元素的个数称为该n 重的汉明 距离，简称重量，用w ( r ) 表示。汉明距离：逐位比较两个n 重矢量r l 和r 2 的 对应各位，其中取值不同的元素的个数称为r l 和r 2 的汉明距离，用d ( r 1 ，r 2 ) 表示。 信息码元与监督码元 信息码元又称信息序列或信息位，这是发端由信源编码后得到的被传送的信 息数据比特，通常以k 表示。由信息码元组成的信息组为：m = ( 埘。，m 。，m 。) 在二元码情况下，每个信息码元m 的取值只有0 或l ，故总的信息码字数共有2 个，即不同信息码元取值的组合菇有2 次方组。 监督码元又称监督位或附加数据比特，这是为了检纠错码而在信道编码时加 入的判断数据位。通常以r 表示，即为：n = k + r 或r = n k 。 经过分组编码后的码又称为( n ，k ) 码，即表示总码长为n 位，其中信息码长( 码 元数) 为k 位，监督码长( 码元数) 为r = n k 。通常称其为长为n 的码字( 或码字、 码矢) 。 许用码字与禁用码字 信道编码后的总码长为n ，总的码字数应为2 的n 次方，即为2 的k + f 次方。 其中被传送的信息码字有2 的k 次方个，通常称为许用码字；其余的码字共有( 2 的n 次方减去2 的n 次方) 个，不传送，称为禁用码字。发端误码控制编码的任 务正是寻求某种规则从总码字( 2 “) 中选出许用码字；而收端译码的任务则是利 用相应的规则来判断及校正收到的码字符合许用码字。通常又把信息码元数目k 与编码后的总码元数目( 码字长度) n 之比称为信道编码的编码效率或编码速率， 表示为：r 划n _ k k + r ，这是衡量纠错码性能的一个重要指标，一般情况下，监 督位越多( 即r 越大) ，检纠错能力越强，但相应的编码效率也随之降低了。 码重与码距，最小码距 在分组编码后，每个码字中码元为“1 ”的数目称为码的重量，简称码重。两 个码字对应位置上取值不同( 1 或o ) 的位数，称为码字的距离，简称码距，又称 汉明距离，通常用d 表示。例如：0 0 0 与1 0 1 之间码距d = 2 ：0 0 0 与1 1 1 之间码 距d = 3 。对于( n ，k ) 码，许用码字为2 个，各码字之间距离最小值称为最小码距。 2 2 2 码多项式表示 循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码。它有 许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码， 且易于实现；同时循环码的性能也较好，具有较强的检错和纠错能力。 循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一 许用码字经过循环移位后，所得到的码字仍然是许用码字。若( d 。，口神，q ，) 为一循环码字，则( d “，口，q ，口o ，口) 、( 口o ，口，l - ，口1 ) 、还是许用码字。 也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码字。表 2 2 给出了一种( 7 ，3 ) 循环码的全部码字。由此表可以直观地看出这种码的循环 特性。例如，表中的第2 码字向右移一位，即得到第5 码字；第6 码字组向右移 一位，即得到第3 码字。 为了利用代数理论研究循环码，可以将码字用代数多项式来表示，这个多项 式被称为码多项式，对于许用循环码爿= ( 4 。，a 。，q ，口。) ，可以将它的码多 项式表示为： a ( 曲= d 。一l x “一1 + 口h 一2 x “一2 + + 口1 z + 口。 对于二进制码字，多项式的每个系数不是0 就是1 ，x 仅是码元位置的标志。 因此，这里并不关心x 的取值。而表2 2 中的任一码字可以表示为： 爿( x ) = 口6 并6 + 口5 x 5 + + 口l x + 4 0 表2 2 一种( 7 ，3 ) 循环码的全部码字 码字 序号 信息位 监督位 a 6a 5a 4a 3a 2a 1a o 10 0 0o o o o 20 0 10 1 1 l 3o l o1 1 1 0 40 1 11 0 0 1 51 0 01 0 h 61 0 11 1 0 0 71 1 0o 1 0 1 81 1 1o o l 0 例如，表中的第7 码字可以表示为： 4 ，( x ) = 1 工6 + 1 x 5 + o 五4 + o x 3 + 1 x 2 + 0 工+ 1 = x 6 + x 5 + x 2 + 1 在整数运算中，有模n 运算。例如，在模2 运算中，有1 + 1 = 2 = o ( 模2 ) ， l + 2 = 3 = l ( 模2 ) ，2 x 3 = 6 ；0 ( 模2 ) 等。因此，若一个整数m 可以表示为： 竺：q + 里p n ，q 是整数 则在模n 运算下，有m ；p ( 模n ) ，也就是说，在模n 运算下，一整数m 等于 其被n 除所得的余数。 在码多项式运算中也有类似的按模运算法则。若一任意多项式f ( x ) 被一个n 次多项式n ( x ) 除，得到商式q ( x ) 和一个次数小于n 的余式r ( x ) ，也就是： 怒咧班怒 则可以写为：f ( x ) 一r ( x ) ( 模n ( x ) ) 。 这时，码多项式系数仍按模2 运算，即只取值o 和1 ，假设：计算石4 + x 2 + l 除以x 3 + 1 的值可得： 工4 + x 2 + 1 + 1 工2 + x + 1 工+ - 一 一+ 1 注意，在上述运算中，由于是模2 运算，因此，加法和减法是等价的，在式 子中通常用加法运算符，具体模2 运算的规则定义参见“二进制模2 算法”一小 节。 这样也可以表示为： 工4 + x 2 + 1 鲁z 2 + x + 1 ( 模工3 + 1 ) 在循环码中，若a ( x ) 是一个长为n 的许用码字，则算一( x ) 在按模x 。+ 1 运 算下，亦是一个许用码字，也就是假如：x 爿( x ) = 4 ( x ) ( 模x ”+ 1 ) ，可以证明4 ( x ) 亦是一个许用码字，并且，爿( x ) 正是a ( x ) 代表的码字向左循环移位i 次的结果。 例如，由彳，( 功= z 6 + j 5 + x 2 + l 表示的循环码，其码长n = 7 ，现给定i = 3 ，则： 工3 一7 ( x ) = 工3 - ( x 6 + 5 + x 2 + 1 ) = ( z 9 + x 8 + 工5 + 工3 ) = ( x 5 + z 3 + 五2 + x ) ( 桴k 7 + 1 ) 其对应的码字为o 1 0 1 ll o ，它正是表2 2 中第3 码字。 通过上述分析和演算可以得到了一个重要的结论：一个长度为n 的循环码， 它必为按模( 石”+ 1 ) 运算的一个余式。 2 2 3 生成多项式和生成矩阵 循环码除全o 码字外的其余全部码字称为生成多项式，用g ( x ) 表示。可以 证明生成多项式g ( x ) 具有以下特性： ( 1 ) g ( x ) 是一个常数项为l 的r = n k 次多项式； ( 2 ) g ( x ) 是工”+ 1 的一个因式； ( 3 ) 该循环码中其它码多项式都是g ( x ) 的倍式。 为了保证构成的生成矩阵g 的各行线性不相关，通常用g ( x ) 来构造生成矩 阵，这时，生成矩阵g ( x ) 可以表示成为： g ( 工) = z “1 g ( 功 x “( 曲 x g ( 工) g ( x ) 其中g ( ) = x 7 + 口，_ 】x “+ + 4 i z + 1 ，因此，一旦生成多项式g ( x ) 确定以 后，该循环码的生成矩阵就可以确定，进而该循环码的所有码字就可以确定。显 然，g ( 功= z g ( 工) g ( 砷 不符合g = 【，。q 】形式，所以此生成矩阵不是典型形式 不过，可以通过简单的代数变换将它变成典型矩阵。 现在以表2 2 的( 7 ，3 ) 循环码为例，来构造它的生成矩阵和生成多项式，这 个循环码主要参数为，n = 7 ，k = 3 ，r = 4 。从表中可以看到，其生成多项式可以 用第1 码字构造： g ( x ) = 一1 ( 功= 工4 + t 2 + x + 1 卜2 占( x ) g ( 。) ：l 昭o ) i ： l g ( 工)j r l o ll l o o g = io l o l l l o | l o o l 0 1 1 1 j x 6 + x 4 + x 3 + 工2 工5 + x 3 + x 2 + 工 工4 + 工2 + z + 1 ) 石)烈 l 2 扣 扣 工 x 在上面的例子中，是利用表2 2 给出的( 7 ，3 ) 循环码的所有码字，构造了它 的生成多项式和生成矩阵。但在实际循环码设计过程中，通常只给出码长和信息 位数，这就需要设计生成多项式和生成矩阵，这时可以利用g ( x ) 所具有基本特 性进行设计。 首先，生成多项式g ( x ) 是工“+ l 的一个因式，其次g ( x ) 是一个r 次因式。因 此，就可以先对进行因式分解，找到它的r 次因式。下面仍以( 7 ，3 ) 循环码为例 进行分析。 第一步：对z “+ 1 进行因式分解得： x 7 + 1 = ( 并+ 1 ) 0 3 + 工2 + 1 ) ( 工3 + 工+ 1 ) 第二步：构造生成多项式g ( x ) 为了求( 7 ，3 ) 循环码的生成多项式g ( x ) ，要从式 x 7 + 1 = 缸+ 1 ) ( 工3 + z 2 + 1 ) ( z 3 + z + 1 ) 中找到r = n k 次的因子。不难看出，这样的 因子有两个，即： ( 工+ 1 ) ( x 3 + x 2 + 1 ) = x 4 + 石2 + x + 1 ( z + 1 ) ( x 3 + z + 1 ) = z 4 + x 3 + 工2 + 1 以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出的 循环码码字就不同。用式o + 1 ) ( 工3 + 石2 + 1 ) = x 4 + x 2 + 石+ 1 作为生成多项式产生 的循环码即为表2 2 所列。 当然，在得到生成矩阵g 以后，可以通过线性变化，使之成为典型矩阵，然 后利用这时生成矩阵g 和监督矩阵h 的关系，得到监督矩阵h 。除此之外，还可 以利用循环码的特点来确定监督矩阵h 。 由于( n ，k ) 循环码中g ( x ) 是x “+ 1 的因式，因此可令： m ) = 蔷一一，1 + 这里h ( x ) 称为监督多项式。与g c 砷= 督矩阵表示为 x g ( 功 g ( z ) 所表示的g ( x ) 相对应，监 ) 工、，烈 i 2 一 一 t t x x 日( 功= 并4 一“ + ( 曲 x 肛- 幸( x ) z 五+ ( x ) ( 工) 其中 幸( 功= 工+ 鱼z + 2 z 卜2 + + 七- l 工+ 1 是逆多项式。 对于表2 2 中的( 7 ，3 ) 循环码，g ( 对= x 4 + 工3 + z 2 + l ，则： 坼) = 蔷d “+ 1 j 州加 川 日( 并) = 2 2 4 检错性能 工6 + x 4 + 工， 工5 + 石3 + x 2 z 4 + z 2 + z + 茁+ 1 j 日= 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 o 0 0 1 0 1 l 当一个码字通过二进制对称信道( b s c ，也就是一种无记忆信道，随机信道， 数据序列中出现的错误彼此无关) 传输时，如果由于干扰变成了另一码字，则检 错译码器就不能发现此种类型的错误，产生了不可见错误。由于能够较容易地计 算 b 七 线性码集合中的平均不可检错误概率，可以以此作为估计码的不可检错 误概率的上限。 定理8 二进制 力，七】线性分组码集合中，码的平均不可检错误概率为 = 2 巾“( 卜( 1 一见) ) ，式中见是二进制对称信道b s c 的误码率。 通常情况下，1 一( 1 一以) 1 ，所以，岛= 2 山“ 圪是在所有2 “”“一1 个 n ，明分组码构成的码集合中的平均不可检错误的 概率。因此在o 见1 2 时，必定在该集合中存在有不可检错误概率i = 2 巾i ” 的二进制码，称这类码为最佳检错码。显然，如果能够证明任何码的如是置的 单调增函数，那么，当见= 1 2 时，所有2 “个n 重在接收端出现的机会均等，其 概率是2 一，在这2 “个中仅有2 + 个是码字。其中之一是发送端发来的码字。因此， 当见= l 2 时，【n ，七】分组码的不可检错误的概率为 匕( 1 2 ) = ( 2 一1 ) 2 = 2 一“一2 4 2 一“ 说明在最大误码率情况下，圪不会超过2 嘶。可知2 巾“是不可检错误概 率的上限。 有关定理8 的详细证明、最佳码的构造与性质、不可检错误概率的上下限及 近似计算请参阅文献 11 今井秀树著的符号理论。 循环码作为检错码时，它可以检查出成区间的错误，为此先介绍一个概念。 定义设e ( ) = + e l z + + g x ”1 r ，如果g ( 工) 的系数有连续b 个，比如第 州十1 ，小+ 2 ，聊+ 6 个，使得当j m + b 时，但“o ，+ 6 o ，则称p ( z ) 为一个长为b 的成区间的差错模式。 设发送的码字为c ( x ) ，收到的码字为“( x ) 。如果p ( x ) = “( 工) 一c ( 石) 是一个长 为b 的成区间差错模式，则称c ( x ) 在传送的过程中出现一个长为b 的成区间错误。 定理9 设c 是一个q 元 厅，n r 循环码，则c 可以检查出任意长为6 ，的 成区间错误。 证明设c o ) = c o + c i x + + c h 算”1 r 是发送的码字，在传送的过程中出 现了一个长6 r 的成区间错误e ( x ) = e o + e l x + + 8 。l x ”1 b ，则e ( x ) 存在相 连的b 个系数，记为第聊+ l ，研+ 2 ，m + 6 个，使得当， 聊+ 6 时， 巳= o ，而“0 ，+ 6 o ，于是， e ( x ) = e o + e i x + - + e 。一1 x “= x ”“( e 。，十l + e h ，+ 2 x + - - + e 。+ 6 x 扣1 ) ，令 口( 工) = 已。+ 】+ e 。+ 2 工+ + + 6 z 扣1 ，贝0 d e g ( 4 ( 工) ) = 6 一l ，一l 。 其中d e g ( ，( 工) ) 是求多项式的次数。 设g ( x ) 是循环码c 的生成多项式，则d e 颤g ( 工) ) = r 且g ( x ) 不能整除n ( x ) 。因 为g ( 笫) 的零次项的系数不为零，所以g ( z ) 不能整除e ( x ) ，否则，假设g ( 工) f e ( x ) ， 即g ( x ) l x “4 ( z ) ，因为g ( x ) 与工”1 互素，所以g ( z ) 口( 工) ，导致矛盾。又因为c ( 工) 是码字，所以g ( x ) l c ( x ) ，因此，我们有g ( x ) 不能整除c ( x ) + e ( 算) 。这说明 c ( z ) + 8 ( x ) 不是码字，即循环码c 可以查出长为6 r 的成区间错误。 有关定理9 的详细证明请参阅文献 1 0 王新梅和肖国镇编著的纠错码一原 理与方法。 第三章循环冗余校验码( c r c ) 在数据通信与网络中，通常信息码元的码元数k 相当大，由一千甚至数千数 据位构成一帧，而后采用循环码的生成多项式产生r 位的校验位，这时信息码元 和校验位构成的码宇不一定是严格定义的循环码，而是在数据通信与网络中广泛 采用的循环冗余校验码( c r c ) ，它是从循环码中派生的缩短循环码，是一类很重 要的检错码。循环冗余校验码的英文全称为c y c l i cr e d u n d a n c yc h e c k s ，所以 缩写为c r c ，它只能检测出错误，而不能纠正错误。c r c 也是给信息码加上几位 校验码，以增加整个编码系统的码距和查错纠错能力。 c r c 利用循环码的误码检测特性进行误码检测，它是从循环差错控制编码中 分出的一类检错码。循环码的已编码码字可被生成多项式g ( x ) 整除。收端可以 利用这一特点进行检错，若收码字不能被g ( x ) 整除，则有错。 3 1 缩短循环码 相对而言，x 1 一l 的因式数目不多，它们所能组合出来的因式次数也是有限 的，并不是任何( n ，k ) 的取值都能产生循环码。为了满足实际中对n 和k 的多种 要求和限制，同般线性分组码一样，循环码也经常使用缩短码的形式，即缩短 循环码。 缩短循环码是在( n ，k ) 循环码的2 个码字中挑选出前i 个信息位均为o 值的 码字( 有2 。1 个这样的码字) 作为( n i ，k i ) 缩短循环码的码字。缩短循环码的码 集是( n ，k ) 循环码集的子集，因此它的码字也一定能被g ( x ) 除尽，即它是g ( x ) 的倍式。缩短循环码的所有码多项式的次数不会超过n i 一1 次；反之，所有次数 小于等于n i 1 次且能被g ( x ) 整除的多项式必是( 旷i ，k i ) 缩短码的码多项式。 由于缩短循环码是挑选前i 个信息位均为0 值的码字，删去前i 位而缩短的，在 此过程中没有删除过“1 ”，因此缩短后的码重不变，于是( n i ，k i ) 缩短循环码 的纠错能力与原( n ，k ) 循环码相同，只是编码率降低了。 缩短循环码的生成矩阵和校验矩阵可在原循环码的生成矩阵和校验矩阵的 基础上去掉一部分行、列而得到。 比如，由以矿+ 工+ 1 为生成多项式生成的( 7 ，4 ) 系统循环码求缩短为( 5 ，2 ) 缩短循环码的生成矩阵和校验矩阵。 3 2 分析：j 7 + 1 = ( 工+ 1 ) ( 工3 + 工2 + 1 ) ( x 3 + 石+ 1 ) 。本题n 一i = 7 4 = 3 ，l 习此， 生成多项式的次数为3 。x 7 + l 有两个3 次因式，取其中任意一个都能生成( 7 ，4 ) 循环码。现取g ( x ) = 工3 + x + 1 ) ，则 ( = ( x + 1 ) ( x 3 + x 2 + 1 ) = x 4 + x 3 + 工2 + 1 。 由g = 吕( 工) 喀( 算) 可得g = = o oo 0o 1 o1o 101 o o o lo 0 01o o o1 lol oll llo l0 0 1o1 ll1 110 011 对矩阵的行进行运算，化简得 o o111o1 h = fo 111o 1 o l ，对矩阵的行进行运算，化简得 l l l1o1o o j 1 1 1 01 0o 带i o1 l1o1 o i 这样，( 5 ，2 ) 缩短循环码的生成矩阵变为2 5 ，去除g 矩阵的最上边两行 和最左边两列，即得缩短循环码的生成矩阵g 。同理，缩短的校验矩阵由3 7 变 为3 5 ，只要去除原校验矩阵的最左边两列，即得缩短循环码的校验矩阵h 。 g 黜加r 骶蚓 ， l0 l0 0 i 由信息组可能的4 种组合( o o ) 、( 0 1 ) 、( 1 0 ) 、( 1 1 ) 与g s 相乘后可得全部的 缩短循环码码字，共4 个，它们是( 0 0 0 0 0 ) 、( 1 0 1 1 0 ) 、( 0 1 0 1 1 ) 、( 1 1 1 0 1 ) 。 从上例的4 个码字看到：对于缩短循环码而言，任意码字的循环移位不再一 定是码字，它已失去了循环码的外部特性，不是典型意义上的“循环”码了。但 它是循环码的子集，可以想象为它仍由( 7 ，4 ) 循环编码器产生，只是传输时有选 择地少传2 位，仅输出码字的前5 位而已。因此它仍然具有循环码编码器实现简 单的优点，工程实现时只需对原( n ，k ) 循环码编译码电路稍做修改就可以了。 循环冗余检验码( c r c ) 是一种系统的缩短循环码，它只能检测出错误，而不 能纠正错误。广泛应用于帧校验。c r c 码的结构如图所示： 卜一。咖位一 际面_ 磊五 ( 先发送) 高次+ 一低次 图3 1 图3 1 中，m ( x ) 的k 个系数对应k 位信息，r ( x ) 的n k 个系数对应n 一七个 校验位。从信道编码角度来看，整个n 位帧( 或称分组、信元、单元、包等) 就是 一个码字，习惯上仅把h 一七校验位部分称为c r c 码。 图3 一l 中，m ( x ) 为( k 1 ) 次多项式，r ( x ) 为( n k 一1 ) 次多项式，c ( x ) 为( n 一1 ) 次多项式，g ( x ) 为( h 一七) 次多项式。 对于系统循环码，在发送端：c ( x ) = 工”m ( x ) + “工) ，其中r ( x ) 等于算”。m ( x ) 除以g ( x ) 后的余式。 接收码流如无误码，应有接收码r ( x ) 等于发送码c ( x ) ，即 c ( z ) = r ( x ) = x ”，l ( x ) + r ( 石) = 口( x ) g ( x ) ，这时，接收码应能被生成多项式g ( x ) 整除。反之，如果不能整除，必是传输中出了误码。 循环冗余校验码的“循环”表现在g ( x ) 是循环码生成多项式，“冗余”表现 为校验位n 一七长度一定。既然是循环码，应有g ( x ) ( z ) = 工“+ 1 ，即n 一_ i 是n 的因子，一旦h 一女固定，则n 也固定，或只有很少几种取值。但在帧校验的实 际应用中，帧长n 是不定的，而且可以连续变化。所以工程应用的c r c 码不是按 g ( x ) i o “+ 1 ) 设计的原始的( ，) 循环码，而是该码的缩短码。即先设计循环 码( n 。，) ，再缩短任意i 位得到( h 。一f ，一f ) = ( n ，尼) 的c r c 码。由于缩短，c r c 码失去了循环码外部的循环特性，但循环码的内在特性依然存在，其纠错能力可 以通过循环码来分析，编解码电路也可利用循环码来实现。 c r c 码的信息位虽然是可变长度的，但也受最大长度的限制。以c r c 1 6 为 例，它的生成多项式g ( x ) = z 1 6 + x 1 5 + 工2 + 1 = ( z + 1 ) ( 工1 5 + x + 1 ) ，其中x 1 5 + x + 1 是本原多项式，能够整除的矿+ l 中，n 的最小值是2 ”一1 ；3 2 7 6 7 ，所以原始循 环码长n = 3 2 7 6 7 ，n k = 3 2 7 5 l ，是( 3 2 7 6 7 ，3 2 7 5 1 ) 循环码。该码共有码字2 3 2 7 5 1 个，其 中最高位为0 的占一半( 2 ”1 个) ，前2 位为o 的又是其中的一半( 2 3 2 7 5 1 。2 个) ， 前3 位为。的有2 ”。个，以此类推，前i 位为。的有2 ”7 ”。个，将前i 位 为0 的码看作一个子集，去掉前面i 个o 构成( 一f ，一f ) 缩短码，这就是可变 长度的( h ，七) c r c 码，它保留了( 3 2 7 6 7 ，3 2 7 5 1 ) 循环码的特性，也决定了用c r c 一1 6 校验时的最大信息长度不能超过3 2 7 5 1 。 注意，c r c i t u t 、c r c 一1 6 、c r ci s 一9 5c d 姒和c r c 一1 2 都含有因子x + 1 。可 以证明，若生成多项式g ( x ) 含有因子x + l ，则此码不含奇数重量码字，因此x + l 的作用等效于奇偶校验。事实上，上面列举的c r c 码生成多项式的项数除c r c 一3 2 外确实都是偶数。 偶重c r c 为什么能够检出所有奇数个差错? 其原因可以这样来理解：循环码所在的k 维n 重码空间是由k 个基底“张” 成的，所有码字都是这k 个基底的线性组合。而这k 个基底又是一个基底的循环， 所以，所有基底都是等重的。如果基底是偶数重量，则偶数重量基底的线性组合 仍然是偶数重量( 组合时，要么两个“l ”在同一位置加成“0 ”，重量减2 ；两个 “l ”加到不同位置，重量加2 ) ，因此所有码字的重量均应为偶数。 换一个角度，想要判断二元域多项式的重量是奇数还是偶数，只要将x = 1 代入该多项式。若多项式重量为偶数，则各项之和应为0 ；若多项式重量为奇数， 则各项之和应为1 ：于是根据和的“o ”或“l ”可以判断码重的奇偶。对于偶重 的c r c 生成多项式，比如c r c i t u t 的生成多项式： g ( x ) l ，：】= g ( 1 ) = ( x 1 6 + x u + 工3 + 1 ) l 水1 = 1 + l + l + 1 = o ( m o d 2 ) 它所生成的任何码字c ( x ) l 。，= c ( 1 ) = 巩( 1 ) g ( 1 ) = m ( 1 ) 0 = o ( m o d 2 ) ，因此， 所有码字重量均应为偶数。 3 2 循环冗余码编码、译码 编码过程 在编码时，首先需要根据给定循环冗余码的参数确定生成多项式g ( x ) ，也 就是从工“+ 1 的因子中选一个( n k ) 次多项式作为g ( x ) ；然后，利用循环冗余码 的编码特点，即所有循环码多项式a ( x ) 都可以被g ( x ) 整除，来定义生成多项式 g ( x ) 。 根据上述原理可以得到一个较简单的系统循环码编码方法：设要产生( n k ) 循环码，m ( x ) 表示信息多项式，则其次数必小于k ，而工”m ( x ) 的次数必小于 n ，用x “m ( x ) 除以g ( x ) ，可得余数r ( x ) ，r ( x ) 的次数必小于( n k ) ，将r ( x ) 加到信息位后作监督位，就得到了系统循环码。下面就将以上各步处理加以解释。 ( 1 ) 用x ”乘m ( x ) 。这一运算实际上是把信息码后附加上( n k ) 个“o ”。例 如，信息码为1 1 0 ，它相当于m ( x ) = 工2 + x 。当n k = 7 3 = 4 时，算”2 m ( x ) = x 6 + x 5 ，它相当于1 1 0 0 0 0 0 。而希望得到的系统循环码多项式应当是a ( x ) = ( 2 ) 求r ( x ) 。由于循环码多项式a ( x ) 都可以被g ( x ) 整除，也就是 塑：( ( x ) ：芝：! ! 型：! ：型盟+ 盟 ( 3 2 一1 ) g ( z ) 、7 g ( z )g ( 算)占( 工) 因此，用x ”2 m ( x ) 除以g ( x ) ，就得到商q ( x ) 和余式r ( x ) ，即 1 2 盟：q ( 工) + 掣 ( 3 _ 2 _ 2 ) g ( x ) 、7 g ( x ) 这样就得到了r ( x ) 。 ( 3 ) 编码输出系统循环码多项式a ( x ) 为： 4 ( x ) = 算”一- m ( x ) + ，( 工) ( 3 2 3 ) 例如，对于( 7 ，3 ) 循环码，若选用占( 功= z 4 + j 2 + z + 1 ，信息码1 l o 时， ( 3 2 4 ) ! ! 旦婴! ：1 l l + 生 1 0 1 1 11 0 1 1 l 这时的编码输出为：1 1 0 0 l o l 。 上述三步编码过程，在硬件实现时，可以利用除法电路来实现，这里的除法 电路采用一些移位寄存器和模2 加法器来构成。 顺便指出，由于数字信号处理器( d s p ) 和大规模可编程逻辑器件( c p l d 和 f p g a ) 的广泛应用，目前已多采用这些先进器件和相应的软件来实现上述编码。 译码过程 对于接收端译码的要求通常有两个：检错与纠错。循环冗余码检验，只需要 达到检错目的即可，因此它的译码十分简单，可以由式( 3 2 一1 ) ，通过判断接收 到的码字多项式b ( x ) 是否能被生成多项式g ( x ) 整除作为依据。当传输中未发生 错误时，也就是接收的码字b ( x ) 与发送的码a ( x ) 组相同，即a ( x ) = b ( x ) ，则接 收的码字b ( x ) 必能被g ( x ) 整除；若传输中发生了错误，则a ( x ) b ( x ) ，b ( x ) 不 能被g ( x ) 整除。因此，可以根据余项是否为零来判断码字中有无错码。 需要指出的是，有错码的接收码字也有可能被g ( x ) 整除，这时的错码就不 能检出了。这种错误被称为不可检错误，不可检错误中的错码数必将超过这种编 码的检错能力。 循环冗余码译码器也可用除法电路组成。由于循环冗余码的码字都是g ( x ) 的倍式，能被g ( x ) 整除，即余式为0 。因此，可根据接收的码字能否被g ( x ) 整 除，来判断接收码字是否有错。 3 3c r c 的代数推导 下面在代数原理的推导中，以c r c 的生成多项式的阶数为1 6 位的为例，详 细按比特、字节计算c r c 的代数过程。 假设要产生的c r c 码为1 6 位，则c r c 的代数推导过程如下： 1 6 位c r c 码产生的规则是：先将要发送的二进制序列左移1 6 位( 即乘以2 “) 后，再除以一个多项式，最后得到的余数即是c r c 码，如式3 3 一l 所示： 等咧卅器g ( x ) g ( x ) ( 3 3 1 ) 其中b ( x ) 表示n 位的二进制序列，g ( x ) 为多项式，r ( x ) 是余数( 即c r c 码) 。 求c r c 所采用模2 加减法运算法则，即不带进位和借位的按位加减，这种运 算实际上就是逻辑上的异或运算。生成c r c 多项式如下，其中c r c 1 6 ，c r c c c i t t 产生1 6 位的c r c ，而c r c 一3 2 则产生3 2 位的c r c 。 接收端将接收的二进制序列( 包括信息码和c r c 码) 除以多项式，如果余数为 o 则说明传输中无错，否则说明传输有误。有关于其原理前面已讲过，在此不再 多述。用软件计算用软件计算c r c 时，接收端可以将接收到的信息码求c r c ，比 较结果和接收到的c r c 是否相同。 3 3 1 比特计算c r c 对一个一迸制序列刚以_ 襄不为： 。 占( x ) = b ( x ) 2 “+ & 一l ( z ) 2 “一十十羁( x ) 2 + 岛( x ) 求此二迸制序列的c r c 时，先乘以2 协( 即左移1 6 位) 后，再除以一个多项式，最 后得到的余数即是c r c ，如式( 3 3 2 ) 所示： 型型! ：堡盟芝2 。+ 堡= i ! 型：2 一+ + 竺趔坐，- + 当赴芝，。 g ( 石)g ( x ) g ( 曲 。 g ( x ) 山面：广z ( 3 3 2 ) 可以设： 等吲咖器 阻。_ 3 ) 将( 3 3 3 ) 代入( 3 3 2 ) ，得： 等咆+ 器皿”+ 等+ 等型+ 等掣 吲n z 嘴+ 等m “+ “+ 等+ 等掣 ( 3 3 4 ) 再设 筹+ 筹缘心) + 锗 s - 5 ) 将( 3 3 5 ) 代入( 3 3 4 ) ，如上类摊，最后得到： 等吲班啪矽+ q o ( 小粥 根据c r c 的定义，很显然，1 6 位二进制余数r o ( x ) 即是我们要求的c r c 码。 式( 3 3 5 ) 是编程计算c r c 码的关键，它说明计算本位后的c r c 码等于上一位c r c 码乘以2 后除以多项式，所得的余数再加上本位除以多项式所得的余数。 3 3 2 按字节计算c r c 对一个二进制序列可以按字节表示为： b ( 工) = e ( 功2 8 “+ 峨一l ( 功2 8 ”1 + + 墨( 曲2 6 + 或( x ) 其中b n ( x ) 为一个字节( 8 位) 。 求此二进制序列韵c r c 码时，先乘以2 “( 即左移1 6 位) 后，再除以一个多项 式，最后得到的余数即是c r c 码，如式( 3 。3 6 ) 所示： 筹= 等岔”+ 等k - + 等+ 等 g ( g ( x ) g ( z ) “ “一 g ( z ) 。1 ；石r 。 ( 3 3 6 ) 可以设： 等吲小船 将( 3 3 7 ) 代入( 3 3 6 ) ，得： 等堋卅鬻m 8 “+ 警沪+ 等+ 等 吲n z 锩筝+ 筹妒舢叫+ 因为： r ( z ) 2 8 = b 8 ( x ) 2 8 + b 8 ( z ) ) 2 8 ( 3 3 9 ) 其中b 。( z ) 是兄( 工) 的高8 位，如。( z ) 是咒( x ) 的低8 位。 将( 3 3 9 ) 代入( 3 3 8 ) ，经整理得到： 筹叫等+ 警犯跏+ ”+ 等z 8 + 等 ( 3 3 1 0 ) 再设： 等+ 睑铲哦如) + 等 。一n ) g ( 工) g ( 工) ”叫。 g ( x ) 将( 3 3 1 1 ) 代入( 3 3 1 0 ) ，如上类推，最后得到： 罨筹吲班8 班咐_ 1 ) + 吲卅筹 根据c r c 的定义，很显然，1 6 位二进制余数r 0 ( x ) 即是我们要求的c r c 码。 式( 3 - j 枷是编程计算c r c 码的关键，它说明计算本字节后的c r c 码等于上一字节 余式c r c 的低8 位左移8 位( 即乘以2 5 6 ) 后，再加上上一字节右移8 位( 即取高 位) 和本字节之和后求得的c r c 码。如果我们把8 位二迸制序列数的c r c 码全部 计算出来，放在一个表里，采用查表法，可以大大提高计算速度。由此不难理解 以后讲的袁驱动法的原理和对应的c 语言程序。 很显然，按字节c r c 码时，由于采用查表法，大大提高了计算速度，但对于 广泛运用的8 位微处理器，代码空间有限，对于要求2 5 6 个余式表有些困难，所 以，可采用按半字节的方法。 同理，对个二进制序列可以按半字节表示为： 曰( 工) = 吃( x ) 2 4 1 + 最一l ( z ) 2 4 一+ + e ( z ) 2 4 + 岛( 工) 其中b n ( x ) 为半个字