山西科技 　SHANXI SCIENCE AND TECHNOLOGY 2005 年第 5 期 　9 月 5 日出版 ●应用技术 16 位循环冗余校验码 (CRC) 的 原理和性能分析 张平安 (山西省专用通信局) 摘 　要 :CRC 是一种数据通信中广泛应用的检错方法 ,文章从编码的数学原理出发 ,分析了 CRC 的编码本质 、生成/ 校验矩阵 、最小码重等参数 ,推导了编码应用中的检错概率 、 漏检错误概率结论 ,给出了利用 CRC 纠正单比特错误的实现算法和仿真性能 。 关键词 :CRC ;循环码 ;漏检错误概率 ;单比特错误 中图分类号 :TN915. 85 　　　　文献标识码 :A 文章编号 :1004 - 6429 (2005) 05 - 0123 - 03 　　在数据通信中一般采用误码率作为通信质量的衡量标准 , 但是误码率是一种整体平均的衡量 ,是一种长时间性能评估 , 不能提供对特定码元和码元组的置信度评估 ,不能提供短时间 内的通信质量评价 。一种常用的解决方法是将数据分组传输 , 每组码元采用称为帧校验序列 ( FCS , Frame Check Sequence) 的 差错控制编码进行编码/ 解码 ,从而获得具体每一帧的误码性 能和置信度 。 在帧校验序列的实现中 ,循环冗余校验码 (CRC ,Cyclic Re dundancy Check Code) 以其高效率 、高性能获得了广泛应用 ,其 中具有 16 个冗余比特的 CRC 编码进入了多个国际通信标准 , 本文的研究重点就是 16 位冗余 CRC 编码 。常见的 16 位 CRC 多项式有两个 : CRC CCITT g ( x) = x16 + x12 + x5 + 1 = ( x + 1) ( x15 + x14 + x13 + x12 + x4 + x3 + x2 + x + 1) CRC ANSI g ( x) = x16 + x15 + x2 + 1 = ( x + 1) ( x15 + x + 1) 这两个多项式都由两部分组成 ,前部分是因式 ( x + 1) ,可以提 供具有差分运算的功能 ,后一部分是一个周期为 215 - 1 = 32767 的本原多项式 ,可以证明两个本原多项式的周期都是 32767 ,即 ( x32767 + 1) mod( g ( x) ) = 0 ,生成多项式的组成和周期在很大程 度上决定了 CRC 的性能 。 1 　CRC 的数学原理和本质 CRC 的基本原理在一般的通信教科书中都有较为详细的 描述 ,这里只给出简单的数学描述 ,本文的目的是找出数学原 理中和编码性能相关的部分 ,本文不考虑发送接收长度不相等 的情况 ,实际应用中可以通过其他方法进行控制 。为了推导方 便全文设定下列符号 : 1. 1 　CRC 编码的原理 作者简介 :张平安 ,男 ,1956 年出生 ,毕业于山西大学计算 机系 ,副局长 ,030071 ,太原市迎泽大街 369 号 收稿日期 :2005 - 07 - 29 名称 生成 多项式 信息 多项式 编码发送 多项式 编码接收 多项式 差错 多项式 商多项式 余多项式 符号 g(x) m(x) s(x) r (x) e (x) p (x) q (x) 简单描述 最高次数 r = 16 ,周期 32767 长度为 k ,k 小于 32767 长度为 n ,n - k + r 长度为 n ,n = k + r 长度为 n ,r (x) = s(x) + e (x) 最高次数小于 r CRC 编码分析在 GF(2) 上进行 ,分析的工具是近世代数的多项 式理论 。基本过程如下 : 设 　m ( x) xr = p ( x) g ( x) + q ( x) , p ( x) 为商式 , q ( x) 为余式两边同时加余式 q ( x) m ( x) xr + q ( x) = p ( x) g ( x) + q ( x) + q ( x) = p ( x) g ( x) 令 s ( x) = m ( x) xr + q ( x) = p ( x) g ( x) 显然 s ( x) mod g ( x) = 0 ,即发送编码多项式可以被生成多项式 整除 。如果传输中没有错误则 r ( x) = s ( x) ,应有 r ( x) mod g ( x) = 0。 很明显如果信息传输的过程中没有发生错误 ,则接收到的 信息多项式一定可以被生成多项式整除 ,这就是 CRC 的检错 原理 。 值得注意的是这一命题的逆命题并不成立 ,也就是说接收 到的信息多项式可以被生成多项式整除 ,并不代表信息在传输 中没有发生错误 ,下文将对这一问题仔细分析 。 1. 2 　CRC 编码的本质 ·321· 

山西科技 　SHANXI SCIENCE AND TECHNOLOGY 2005 年第 5 期 　9 月 5 日出版 分组码的性质指出 ,码字的最小码距决定纠错能力 ,而最 小码距等于非零码字的最小码重 。CRC - ANSI 和 CRC - CCITT 的最小码重分析如下 : ●　由于生成多项式本身码重为 4 ,且都属于码字 ,所以 2 CRC 在本质上一种缩短循环码 ,是分组码的一种特例 ,同 时由于编码后的前 k 位是信息 ,所以是一种系统循环码 。因此 当 n 小于 2r - 1 时 ,除了不具有循环码的循环性外具有分组码 和循环码的全部特性 : 1) [ n ,k]循环码构成 n 维线性空间的一个 k 维子空间 ,在 最小码重 d 小于等于 4 ; 长度为 n 中 2n 个组和中仅有 2k 个组和属于码空间 ; ●　由于所有码字中非零项的个数为偶数个 ,所以最小码 2) 任意两个码字的和仍然是一个码字 ; 3) 码的最小距离等于非零码的最小重量 ; 下面分析传输有错情况下的 s ( x) 、r( x) 和 e ( x) 关系 : r( x) mod g ( x) = ( s ( x) + e ( x) ) mod g ( x) = s ( x) mod g ( x) + e ( x) mod g ( x) = e ( x) mod g ( x) , 重不等于 1、3 ; ●　任何包含两个非零项的码字可以表示为 xn ( xm - n + 1) ,其中 xn 不能被 g ( x) 整除 , ( xm - n + 1) 也不能被 g ( x) 整除 , 否则与 g ( x) 的周期为 32767 相矛盾 。 综上所述 : 推论 3 :CRC - ANSI 和 CRC - CCITT 的最小码重 w 和最小 由此可得到的结论 :CRC 编码的检错能力与信息码序列无 码距 d 为 4。 关 ,只和差错序列有关 。分析下列两种情况 : 根据分组码的纠错能力可知 ,最小码距 d 为 4 的 CRC 蝙 1) e ( x) mod g ( x) ≠0 ,CRC 可以检出传输有错 ,通信系统一 码至少具有下列性能 : 般采用 ARQ 机制进行重传 : 2) e ( x) mod g ( x) 20 ,且 e ( x) ≠0 ,CRC 检错失效 ,产生漏检 , 可以看出此时的 e ( x) 也属于一个码字 ,即 r( x) , s ( x) , c ( x) 都 是合法的码字 ,这种情况下 CRC 就是失去了检错的能力 。 推论 1 :当错误图样多项式 e ( x) 是码空间的一个样本时 , CRC 无法检出错误 ,这时 r ( x) 、s ( x) 和 e ( x) 都是属于码空间 的合法码字 。 1. 3 　CRC 编码几个参数 1) 生成矩阵/ 校验矩阵 由于 RIC 是循环码的一种特例 ,所以可以按照循环码用生 成多项式 g ( x) 的通用方法来生成 CRC 码的生成矩阵和校验 矩阵 。 2) 码重分布 码重分布是指一个 [ n ,k ]线性分组码的码字重量分组 ,它 是计算各种错误概率的主要依据之一 ,也是研究码结构的重要 窗口 ,通过它可以透彻地了解码的内部结构 。 设 Ai 为[ n ,k]分组码中重量为 i 的码字数目 ,则集合{A0 , A1 , …,An}称为该分组码的重量分组 。一般而言求出一个码 组的算法复杂度是 2k ,属于一个 NP 完全问题 。当 K > n - k 时 就是信息位的数目大于校验位数目 ,可以求取对偶码的重量分 布利用 Mac - Willians 恒等式获得 ,这样可以将算法复杂度降 低到 2n - k ,在本文中提到的两种 CRC 方案里 r = n - k = 16 ,这种 复杂度下可以利用计算机搜索获得 ,文献提供了具体的实现方 法 。 这里给出一个 CRC 缩短循环码的特殊性质 ,这一性质对 (1) 　可以纠正所有 1 个错误 ; (2) 　可以检出所有 3 个以下错误 ; 事实上出于 CRC 的特殊设计 ,其检错能力远远高于通用 的分组码 。 2 　CRC 性能分析 衡量编码方案的标准是检错能力和译码错误概率 ,一般译 码错误概率可以分成不可检错概率 、译码失效概率和译码错误 概率 ,由于 CRC 编码主要用于 ARQ 机制中的检错 ,所以我们重 点分析它的检错性能 。 2. 1 　检错性能分析 CRC 的检错性能由最小码距和编码本身的特性距定 ,文献 都给出了部分性能 ,本文拓展描述如下 : 1) 所有奇数个错误 。由 CRC 码字的性质可知 ,所有的码 字的重量都是偶数 ,所有重量为奇数的错误都不属于码空间 , 都可以被检出 。 2) 检所有单个突发错误 。 推论 4 :CRC 可以检出任意长度的单个突发错误 。 证明如下 : 设 e ( x) = xm + i + xm + i - 1 + …+ xm = xm ( xi + xi - 1 + …+ 1) = xm ( xi + 1 + 1) / ( x + 1) 对于任意 i < 2n - k , m ≥0 , i ≥0 , xm mod g ( x) ≠0 ; ( xi - 1 + 1) mod( g ( x) ) ≠0 ; 所以即 e ( x) mod g ( x) ≠0 ,即 e ( x) 不属于码空间 ,则必定 分析码距和差错误码率有着重要的作用 。 可以被检出 。 推论 2 :以 CRC - ANS1 和 CRC - CCITT 多项式为生成多项 式的缩短循环码中非零项的个数为偶数个 ,即码重分布中奇次 项都为零 ,或者说码字本身具有偶校验特性 。 证明如下 : 由于 CRC - ANSI 和 CRC - CCITT 多项式中都包含 ( x + 1) 项 ,所以任何码字都可以被 (x + 1) 整除 。即 s ( x) mod( x + 1) = 0 同时 　　xm mod( x + 1) = 1 　　( xm + xn) mod( x + 1) = 0 m ≠n ,m ≥0 ,n ≥0 所以 ,当且仅当码字多项式中包含偶数个非零项时才能被 x + 1 整除 ,证毕 。 3) 最小码重/ 码距 ·421· 3) 检所有两个错误 设 e ( x) = xm + i + xm = xm ( xi + 1) = xm ( xi + 1) ,显然 e ( x) 的两项因式都不是 g ( x) 的因式 ,所以 e ( x) 也不属于码空间 , 可以被检出 。这一点也可以用距小码距为 4 来证明 。 2. 2 　漏检错误概率分析 由推论 1 可知当错误图样 e ( x) 为码空间上的一个矢量 时 ,CRC 检错功能失效 ,产生不可检测错误 (undetected error) ,系 统无法进行重传或者纠错 ,传输的信息被丢失 。因此在通信系 统设计中必须对 CRC ,的漏检概率 (probability of undetected er ror ,Pud) 进行分析 ,并采取必要的技术措施 ,这一点在高速数据 传输中尤其重要 。 在[ n ,k]CRC 循环码中 ,设传输信道为 BSC 信道 ,误码率为 

2 张平安 :16 位循环冗余校验码 (CRC) 的原理和性能分析 2005 年第 5 期 　9 月 5 日出版 p ,则各种的概率分布如下 : 正确传输的概率 : 　　Pok = (1 - p) n 发生错误的概率 : 　　Po = 1 - Pok = 1 - (1 - p) n 单个码重为 w 的错误发生的概率 : pew = pw (1 - p) n - w 设码重分布为[A0 ,A1 ,A2 , …,An ] ,则发生不可检测的概率 为 n Ai Pi (1 - P) n - i Pud = ∑ i = 0 所以 ,求解的关键在于求出 CRC 的码重分布 ,一般在 P < 0. 5 , k > n - k 时需要借助对偶码来降低求解的复杂度 。一般 而言对于 n 比较大的情况 ,精确求解 Pud是很困难的 。 这里可以通过整体分析的方法获得平均的 Pud ,对于 [ n , k]CRC 编码而言 ,存在 2n 个接收矢量 r ( x) ,2k 个码元矢量 s ( x) ,其中 2k - 1个非零矢量可以是可能的不可检测错误矢量 e ( x) ,在信道误码率为 p 的 BSC 信道上 ,不可检测错误发生的 概率为 Pud = 2k (1 - (1 - p) n) / 2n < 1/ 2 n - k 因此 ,可以将 1/ 2n - k作为 Pud分析的上限 ,对于 CRC - ANSI 和 CRC - CCITT 而言 ,Pud 的上限是 1/ 216 ,约为 1. 52 ×105 ,就是 说大约 65 000 个数据包中才会发生一个不可检测错误 ,这对于 中低速的串行已经足够好了 ,甚至可以忽略 。但是近年来随着 高速数据通信的飞速发展 ,不可检测错误的影响已经不可忽 视 ,例如在 CISCO GSR12000 路由器中每秒钟转发的数据包可 以达到 4 500 万个 ,就是每秒钟可能会发生多达 686 次不可检 测错误 ,这种情况不可以忽略不记 ,一般要考虑更高次数的 CRC - 32 或者其它措施 。 2. 3 　单比特错误纠正的原理和方法 作为分组码的一种特例 ,CRC 本身具有一定的纠错能力 , CRC - ANSI 和 CRC - CCITT 都具纠正单比特错误的能力 ,在传 统的低速通信中由于误码较高 ,发生单比特错误的比例较小 , 纠错的效率不高 ;随着光纤通信的等低误码率信道的出现 ,发 生单比特错误在总的错误中的比例大大提高 ,因此采用单比特 纠正错误可以大大提高信道的吞吐量和降低对反向信道占用 , 一种典型应用 (CRC - CCITT ,帧长 1 024 比特) 下的单比特纠错 性能如下表 。 CRC - CCTT 多项式 ,帧长 1 024 比特的单比特纠错性能 误码率 1E - 2 1E - 3 1E - 4 1E - 5 1E - 6 1E - 7 1E - 8 帧错误概率 0. 999 966 0. 641 029 0. 0 973 362 0. 0 101 878 0. 00 102 348 0. 000 102 395 1. 023 99e - 005 单比特错误概率 0. 0000 350 836 0. 367 955 0. 092 442 0. 0 101 358 0. 00 102 295 0. 00 010 239 1. 023 099e - 005 百分比 0. 000 350 848 0. 574 007 0. 949 719 0. 994 894 0. 999 489 0. 999 949 0. 999 995 纠错后的帧错误率 0. 999 615 0. 273 074 0. 00 489 412 5. 202 21e - 005 5. 231 9e - 007 5. 237 35e - 009 5. 242 87e - 011 　　由上表可知 ,当错误发生的数学期望 np < = l 时 ,单比特 是帧错误的主要组成 ,在低误码率时这一点尤其明显 ,利用 CRC 的单比特纠错特性 ,可以显著地降低误码率 ,并提高网络 的吞吐量 。 纠正单比特错误的方法也很简单 ,首先将单比特错误图样 依次送入编码器进行编码 ,选取最后输出 n - k 为构成一个长 度为 n 的表 ,如果 r ( x) 不能被 g ( x) 整除 ,将余数和表中的数 据逐个对比 ,如果相等则纠正相应位置的单个化特 ,如果全部 不等 ,则发生超过一个错误 ,需要进行 ARQ 重传 。 3 　结论 综上所述 ,CRC 编码虽然存在一定的不可检测错误 ,但仍 然是一种高效率 、高性能的检错方式 。16 位的 CRC - ANSI 和 CRC - CCITT 具有纠正所有单错误 、检测所有奇数比特错误 、检 测所有单个突发错误 、检测所有 2 比特错误的能力 ,和 ARQ 机 制结合可以提供高可信度的数据通信 ,在低误码信道上采用单 比特纠错可以有效地提高系统的吞吐量 。值得注意的是在高 速数据通信中不可检测错误则不可以忽略不记 。 参考文献 [1 ] 　王新梅 ,肖国镇. 纠错码 —原理与方法 (修订版) [M]. 西 安 :西安电子科技大学出版社 ,2001 (4) . [2 ] 　刘玉君. 信道编码 (修订版) [M]. 郑州 :河南科学技术出 版社 ,2001 (9) . [3 ] 　周祖荣 ,张鹏远. 对帧校验序列的研究[J ]. 青岛科技大学 (校对 :刘元力) 学报. 2003 (2) . An Analysis of the Principle and Performance of 16 - bit Circulation Redundancy Check ( CRC) Zhang Pingan 　　ABSTRACT :CRC is widely used in checking mistakes in digital communication. This article has , from the principle of coding , analyzed the coding nature and generation/ checking matrix , derived the mistake - checking and omission probability in coding and given the realizing algo rithm and emulating performance of correcting single bit mistakes with CRC. KEY WORDS :circulation check ; omission probability ; single bit mistake ·521·