CRC循环校验码详解.ppt

CRC校验码设计 中科大软件学院2012 8 19 CRC产生背景 在数字通信系统中可靠与快速往往是矛盾的 如何合理地解决可靠与速度这一对矛盾呢 纠错码 在每一个发送的数据块中包含足够的冗余信息 以便接收方可以推断出被发送的数据中肯定有哪些内容 检错码 包含一些冗余信息 但是这些信息只能让接收方推断出发生了错误 但推断不出发生了哪个错误 然后接收方可以请求重传 参考 计算机网络 中3 2节错误检测和纠正海明码 CRC校验码的区别在无线链路 光纤 铜线上应用的区别checksum 3A0101FFF1002C CRC产生背景 多项式编码 特点 检错能力极强 开销小 易于用编码器及检测电路实现 从其检错能力来看 它所不能发现的错误的几率仅为0 0047 以下 从性能上和开销上考虑 均远远优于奇偶校验及算术和校验等方式 因而 在数据存储和数据通讯领域 CRC无处不在 著名的通讯协议X 25的FCS 帧检错序列 采用的是CRC CCITT WinRAR NERO ARJ LHA等压缩工具软件采用的是CRC32 磁盘驱动器的读写采用了CRC16 通用的图像存储格式GIF TIFF等也都用CRC作为检错手段 多项式编码 多项式编码 polynomialcode 也称为CRC cyclicredundancycheck 循环冗余校验码 多项式编码的思想是 将位串看成是系数为0或1的多项式 CRC校验保护的单位是数据块 数据块的大小根据实际情况而定 每一个数据块均被看作是一个二进制多项式 即所有系数均为二进制 即1或0 的多项式 当使用多项式编码时 发送方和接受方必须预先商定一个生成多项式 generatorpolynomial G x 生成多项式的最高位和最低位必须为1 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 3 按模2减法 即模2加 从对应于xrM x 的位串中减去 加上 余数R x 结果即传送的带校验和的帧多项式T 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 得证 举一个例子 1 发送数据110011 2 生成多项式G x x4 x3 1 3 将要发送的数据系列左移4位 新的序列为1100110000 4 按模2算法 将生成的新序列除以生成多项式序列 5 将余数多项式比特序列加到新的序列中即得发送端传送序列 下面 110011 1001 接收方校验方案 方案二 提取接收到序列的信息码元 重复发送方的操作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 差错检测循环冗余校验码 CRC CyclicRedundancycheck 编码 对于一个码长为n 信息码元为k位的循环码 n k 其构成形式为 差错检测循环冗余校验码 CRC CyclicRedundancycheck 若生成多项式G x 为r阶 即r 1位位串 原帧为m位 其多项式为M x 则在原帧后面添加r个0 即循环左移r位 帧成为m r位 相应多项式成为xrM x 按模2除法用G x 对应的位串去除对应于xrM x 的位串 得余数R x 按模2减法 即模2加 从对应于xrM x 的位串中减去 加上 余数R x 结果即传送的带校验和的帧多项式T x 例 m x x9 x8 x6 x4 x3 x 1 k 10 3 1101011011 0000 10011 模二除 商数 1100001010余数 1110r x x3 x2 x 0 所需的循环编码C x 为 C x xn m x r x 1101011011 1110 设编码的信息码元为1101011011 1 假设G x x4 x 1系数形成的位串为10011则将m x x4余数取4位 2 x4 m x 1101011011 0000 另一个例子 多项式除法 1101011011 000010011 10011 1001110011 1011010011 1010010011 1110 1100001010 1101011011 0000 10011 另一个例子 模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 模2运算 模2除法运算定义为 0 1 01 1 1模二除法是利用模二减求余数的 余数最高位为 1 则商 1 否则商 0 每商1位则余数减少一位 直到余数位数少于除数位数 1110 1011 1100100 1011 1111 1011 1000 1011 0110 0000 110 位运算 按位与运算按位与运算符 是双目运算符 其功能是参与运算的两数各对应的二进位相与 只有对应的两个二进位均为1时 结果位才为1 否则为0 参与运算的数以补码方式出现 例如 9 5可写算式如下 00001001 9的二进制补码 00000101 5的二进制补码 00000001可见9 5 1 按位或运算按位或运算符 是双目运算符 其功能是参与运算的两数各对应的二进位相或 只要对应的二个二进位有一个为1时 结果位就为1 参与运算的两个数均以补码出现 例如 9 5可写算式如下 00001001 0000010100001101 十进制为13 可见9 5 13求反运算符 为单目运算符 具有右结合性 其功能是对参与运算的数的各二进位按位求反 例如 9的运算为 0000000000001001 结果为 1111111111110110 位运算 按位异或运算按位异或运算符 是双目运算符 其功能是参与运算的两数各对应的二进位相异或 当两对应的二进位相异时 结果为1 参与运算数仍以补码出现 例如9 5可写成算式如下 00001001 0000010100001100 十进制为12 左移运算左移运算符 是双目运算符 其功能是把 左边的运算数的各二进位全部右移若干位 右边的数指定移动的位数 例如 设a 15 a 2表示把000001111右移为00000011 十进制3 CRC校验码设计 实验要求 1 完成基本CRC校验码生成的功能 位数不限 2 尝试完成CRC 16 CRC 16 发送数据为 0X02 生成多项式 0X18005 余数为 0X800F