曹素华 -- 差错检测与CRC.ppt

差错检测与CRC校验 UMTS工作组曹素华 caosh 内容概要 差错类型 A 检测方式概述 B CRC检测原理 C 伽罗域基本知识 C1 CRC编码 C2 A 差错类型 A 单个比特错误 定义 在给定数据单元只有一个bit发生改变 例子 发送 00000010 ASCIIcode STX正文开始 接收 00001010 ASCIIcode LF换行 0 1 2020 2 7 UMTS工作组曹素华 5 A 多个比特错误 定义 在给定数据单元有两个或者多个不连续的bit发生改变 两个bit错误 2020 2 7 UMTS工作组曹素华 6 A 突发错误 定义 在给定数据单元连续两个或者更多个bit发生改变 2020 2 7 UMTS工作组曹素华 7 B 检测方式概述 将每个数据块单元发送两次 进行逐bit比较 效率 时间 加冗余bit数据通信中常用冗余的方法来解决通信的可靠性问题 2020 2 7 UMTS工作组曹素华 8 B 冗余校验的分类 垂直冗余校验 VRC 纵向冗余校验 LRC 循环冗余校验 CRC 检验和 2020 2 7 UMTS工作组曹素华 9 B 垂直冗余校验 VRC 奇偶校验 在数据块加冗余bit 以保证数据中 1 的个数为奇数或者偶数 偶校验产生器 1 发送端 校验 1的总数为偶数 Y AcceptN Reject 2020 2 7 UMTS工作组曹素华 10 B 纵向冗余校验 LRC 本质 2 DVRC目的 检测多个差错bit和突发错误方法 将确定数据分组 保证单个数据块和数据块的相应bit都具有VRC校验 2020 2 7 UMTS工作组曹素华 11 01010101 B 纵向冗余校验 LRC VCRs VCRbit LRC VCRbit 2020 2 7 UMTS工作组曹素华 12 B 循环冗余校验 CRC 功能最为强大方法 将冗余bit序列加在数据之后 使得新的数据单元正好能被预定的二进制数除尽 发送端和接收端都需要做 如果接收端发现了余数 则舍弃该数据块 2020 2 7 UMTS工作组曹素华 13 B 循环冗余校验 CRC 数据 除法器 余数 发送端 接收端 比预设除法器位数 n 1 少1 如果所得到的余数少于n位 则所缺少的左边的位假定为0 若余数为0 那么CRC部分为全0 0 接受非0 拒绝 2020 2 7 UMTS工作组曹素华 14 B 校验和 方式 发送数据时计算校验和并且将其同分组数据一起发送接收方进行类似运算并决定数据取舍校验和 将分组数据取固定长度 取反码算术运算相加 结果也为同样长度 最后取反码就得到校验和 接收端 类似反运算即可校验 2020 2 7 UMTS工作组曹素华 15 B 校验和 例子 数据校验和 包只在 头部校验 取固定长度取值 2020 2 7 UMTS工作组曹素华 16 CRC检测原理 伽罗域基本知识CRC编码软件硬件实现 2020 2 7 UMTS工作组曹素华 17 C1 伽罗域介绍 GaloisField GF 数据 地址 校验码等都可以看成是属于GF 2m 中的元素或称符号取m 8 GF 28 表示域中有256个元素 除0 1之外的254个元素由本原多项式P x 生成 本原多项式的特性是得到的余式等于0 2020 2 7 UMTS工作组曹素华 18 加法 0 3 001 011 010 1减法与加法相同乘法 5 4 5 4 mod7 2除法 5 3 2 3 5 2 2 7 5对数 log 5 5 C1 伽罗域介绍 GaloisField GF 域的运算 2020 2 7 UMTS工作组曹素华 19 域的构造 取m 3 假设本原多项式 设 为其一根 即 3 1GF 23 中的元素可计算如下 C1 伽罗域介绍 GaloisField GF 2020 2 7 UMTS工作组曹素华 20 本原元 一个元素能产生GF 2n 所有非零元素GF 24 元素a4 24 0 1 24 1 24 24 4 216 21 24 14 256 211元素的阶 ak的阶 本原多项式 如果一个多项式f x 能够产生2n个不同元素 包括0 则为本原多相式 如 本原多项式f x 1 x2 x5 即能构造域GF 25 2n 1 GCD 2n 1 K GCD n k 为求最大公约数函数 C1 伽罗域介绍 GaloisField GF 2020 2 7 UMTS工作组曹素华 21 最小多项式 GF 2n 中部分元素具有相同的阶 且均为某个多项式的根 取这类多项式的最低次数的多项式即为最小多项式共轭类 最小多项式相同的元素的组合 GF 2n 中的元素可以按照共轭类分组 C1 伽罗域介绍 GaloisField GF 2020 2 7 UMTS工作组曹素华 22 C2 CRC编码 编码例子 已知 信息码 110011信息多项式 K X X5 X4 X 1 生成码 11001 生成多项式 G X X4 X3 1 r 4 2020 2 7 UMTS工作组曹素华 23 Step1 X5 X4 X 1 X4的积是X9 X8 X5 X4对应的码是1100110000Step2 积 G X 100001 Q X G x 11001 1100110000 F X Xr1100110000110011001 R X 冗余码 冗余码是1001 码字就是1100111001 C2 CRC编码 2020 2 7 UMTS工作组曹素华 24 解码验证步骤接收码字 1100111001多项式 T X X9 X8 X5 X4 X3 1生成码 11001生成多项式 G X X4 X3 1 r 4 step1 用字码除以生成码 余数为0 所以码字正确 step2 因r 4 所以冗余码是 1001 信息码是 110011 C2 CRC编码 2020 2 7 UMTS工作组曹素华 25 一些见于标准的CRC资料 最高幂次项系数是固定的1 故在简记式中 将最高的1统一去掉了 如04C11DB7实际上是104C11DB7 2020 2 7 UMTS工作组曹素华 26 C2 CRC校验硬件实现 二进制本原多项式的线性反馈移位寄存器机理 考虑二进制一般既约多项式 f x cnxn cixi c2x2 c1x 1 ci GF 2 硬件实现用除法电路 主体移位寄存器和模2加法器 异或单元 组成 产生分为两种结构 SSRG 简单移位寄存产生器MSRG 模块式移位寄存产生器 2020 2 7 UMTS工作组曹素华 27 C2 SSRG 简单移位寄存产生器 2020 2 7 UMTS工作组曹素华 28 矩阵表示 C2 SSRG 简单移位寄存产生器 2020 2 7 UMTS工作组曹素华 29 C2 MSRG 模块移位寄存产生器 2020 2 7 UMTS工作组曹素华 30 矩阵表示 C2 MSRG 模块移位寄存产生器 2020 2 7 UMTS工作组曹素华 31 C2 SSRG与MSRG的关系 SSRG与MSRG最后的输出就是一个长度为2n的PN序列 但是二者不相同 产生相同的PN序列 SSRG与MSRG应该取互反的 即 假设SSRG用f x 来得到 那么MSRG就要用g x xn f x 1 来得到 2020 2 7 UMTS工作组曹素华 32 C2 硬件实现的例子 SSRG MSRG 2020 2 7 UMTS工作组曹素华 33 C2 硬件实现状态表 R3输出 0010111R2输出 0101110R1输出 1011100 R3输出 0011101R2输出 0100111R1输出 1001110 2020 2 7 UMTS工作组曹素华 34 C2 CRC ITU为例x16 x12 x5 1 16级移位寄存器和3个加法器组成 编码 解码前将各寄存器初始化为 1 信息位随着时钟移入 当信息位全部输入后 从寄存器组输出CRC结果 编码解码结构相同 2020 2 7 UMTS工作组曹素华 35 C2 CRC软件实现 比特型算法 定义一个寄存器组 初始化为全 1 依照电路图 每输入一个信息位 相当于一个时钟脉冲到来 从高到低依次移位 移位前信息位与bit0相加产生临时位 其中bit15移入临时位 bit10 bit3还要加上临时位 当全部信息位输入完成后 从寄存器组取出它们的值 这就是CRC码 CRC ITU为例x16 x12 x5 1 2020 2 7 UMTS工作组曹素华 36 数字通信系统一般是对一帧数据进行CRC校验 而字节是帧的基本单位 最常用的是一种按字节查表的快速算法 根据 计算本字节后的CRC码 等于上一字节余式CRC码的低8位左移8位 加上上一字节CRC右移8位和本字节之和后所求得的CRC码 把8位二进制序列数的CRC 共256个 全部计算出来 放在一个表里 编码时只要从表中查找对应的值进行处理 字节型算法 C2 CRC软件实现 2020 2 7 UMTS工作组曹素华 37 CRC ITU的计算算法如下 a 寄存器组初始化为全 1 0 xFFFF b 寄存器组向右移动一个字节 c 刚移出的那个字节与数据字节进行异或运算 得出一个指向值表的索引 d 索引所指的表值与寄存器组做异或运算 f 数据指针加1 如果数据没有全部处理完 则重复步骤b g 寄存器组取反 得到CRC 附加在数据之后 字节型算法编码CRC ITU为例x16 x12 x5 1 2020 2 7 UMTS工作组曹素华 38 a 寄存器组初始化为全 1 0 xFFFF b 寄存器组向右移动一个字节 c 刚移出的那个字节与数据