CRC循环校验码详解课件.ppt

CRC校验 CRC产生背景 在数字通信系统中可靠与快速往往是矛盾的 如何合理地解决可靠与速度这一对矛盾呢 多项式编码 多项式编码 polynomialcode 也称为CRC cyclicredundancycheck 循环冗余校验码 多项式编码的思想是 将位串看成是系数为0或1的多项式 CRC校验保护的单位是数据块 数据块的大小根据实际情况而定 每一个数据块均被看作是一个二进制多项式 即所有系数均为二进制 即1或0 的多项式 当使用多项式编码时 发送方和接受方必须预先商定一个生成多项式 generatorpolynomial G x 生成多项式的最高位和最低位必须为1 多项式编码 特点 检错能力极强 开销小 易于用编码器及检测电路实现 从其检错能力来看 它所不能发现的错误的几率仅为0 0047 以下 从性能上和开销上考虑 均远远优于奇偶校验及算术和校验等方式 因而 在数据存储和数据通讯领域 CRC无处不在 著名的通讯协议X 25的FCS 帧检错序列 采用的是CRC CCITT WinRAR NERO ARJ LHA等压缩工具软件采用的是CRC32 磁盘驱动器的读写采用了CRC16 通用的图像存储格式GIF TIFF等也都用CRC作为检错手段 CRC应用 CRC的主要特点 检错能力极强 开销很小 易于实现 ARJ LHA ZIP等压缩软件采用的是CRC 32 GIF TIFF等图像存储格式 所有链路层或网络接口层协议中 例如HDLC DDCMP等众多领域 应用范围广 CRC原理 将待发送的位串看成系数为0或1的多项式 收发双方约定一个生成多项式G x 其最高阶和最低阶系数必须为1 发送方用位串及G x 进行某种运算得到校验码 并在帧的末尾加上校验码 使带校验码的帧的多项式能被G x 整除 接收方收到后 用G x 除多项式 若有余数 则传输有错 CRC校验和计算法 1 若生成多项式G x 为r阶 即r 1位位串 原帧为m位 其多项式为M x 则在原帧后面添加r个0 即循环左移r位 帧成为m r位 相应多项式成为xrM x 2 按模2除法用G x 对应的位串去除对应于xrM x 的位串 得余数R x T x xrM x R x CRC验证 发送方 接收方 设xrM x 除以G x 的商和余数分别为Q x 和R x 则有 xrM x G x Q x R x 即 接收方收到带CRC校验和的帧多项式T x xrM x R x 由于模2加减相当于异或运算 于是接收方模2除后商Q x 余数0 得证 举一个例子 下面 110011 0000000010101010 接收方校验方案 方案二 提取接收到序列的信息码元 重复发送方的操作xrM x 再除以生成多项式G x 如果余数R x R x 则证明传输正确 方案一 直接用接收到的序列除以生成多项式G x 如果余数R x 0 则证明传输正确 接收方校验方案 生成多项式G x 的国际标准 CRC 12 x12 x11 x3 x2 x 1 CRC 32 x32 x26 x23 x22 x16 x12 CRC 8 x8 x2 x 1 CRC 10 x10 x9 x5 x4 x2 1 CRC 16 x16 x15 x2 1 x11 x10 x8 x7 x5 x4 x2 x 1 CRC CCITT x16 x12 x5 1 模2运算 模2加法运算定义为 对应于逻辑异或 0 0 00 1 11 0 11 1 0例如0101 0011 0110 列竖式计算 0101 0011 0110 多项式的算术运算采用代数域理论的规则 加法没进位 减法没借位 加法和减法都等同于异或 异或计算为 1 1 00 0 01 0 10 1 1 模2运算 模2减法运算定义为 对应于逻辑异或 0 0 00 1 11 0 11 1 0例如0110 0011 0101 列竖式计算 0110 0011 0101 异或计算为 1 1 00 0 01 0 10 1 1 模2运算 模2乘法运算定义为 0 0 00 1 01 0 01 1 1例如1011 101 100111 列竖式计算 1011 101 10110000 1011 100111