1、差 错 检 测与CRC 校 验UMTS 工 作 组曹素华内容概要v 差错类型(A)v 检测方式概述(B)v CRC检测原理(C)伽罗域基本知识(C1)CRC编码(C2)(A)差错类型差错类型单比特多比特突发(A)单个比特错误定义：在给定数据单元只有一个bit发生改 变比如一个字节、一个字符、一个数据单元或者数据包例子：发送：0000 0010 (ASCII code:STX 正文开始)接收：0000 1010(ASCII code:LF 换行)发 送0 0 0 0 0 0 1 0接 收0 0 0 0 1 0 1 00 12023-5-7UMTS工作组 曹素华5(A)多个比特错误定义：在给定数据
2、单元有两个或者多个不连续的bit发生改变发 送0 1 0 0 0 0 1 0接 收0 0 0 0 1 0 1 0两个bit 错误2023-5-7UMTS工作组 曹素华6(A)突发错误定义：在给定数据单元连续两个或者更多个bit发生改变 所 发 送 的 数 据0100 0 0 1 0 0 1 0 0 0 0 1 00011 1 1 1 0 0 0 0 0 1 0 1 0 所 接 收 的 数 据2023-5-7UMTS工作组 曹素华7(B)检测方式概述 将每个数据块单元发送两次，进行逐bit比较(效率、时间)加冗余bit 数据通信中常用冗余的方法来解决通信的可靠性问题2023-5-7UMTS工作组
3、 曹素华8(B)冗余校验的分类 垂直冗余校验(VRC)纵向冗余校验(LRC)循环冗余校验(CRC)检验和2023-5-7UMTS工作组 曹素华9(B)垂直冗余校验(VRC)奇偶校验：在数据块加冗余bit，以保证数据中“1”的个数为奇数或者偶数1100001数据偶校验产生器111000011发送端校验函数接收端校验：1的总数为偶数？Y:AcceptN:Reject2023-5-7UMTS工作组 曹素华10(B)纵向冗余校验(LRC)本质：2D VRC 目的：检测多个差错bit和突发错误 方法：将确定数据分组，保证单个数据块和数据块的相应bit都具有VRC校验1110011111011101001
4、110011010100110101010数 据 移 动 方 向LRC数 据2023-5-7UMTS工作组 曹素华11整个数据块移动方向01010101100101011001110010111011111001111110011111011101001110011010100110101010数 据 移 动 方 向LRC数 据单元数据方向(B)纵向冗余校验(LRC)VCRsVCR bitLRCVCR bit2023-5-7UMTS工作组 曹素华12(B)循环冗余校验(CRC)功能最为强大 方法：将冗余bit序列加在数据之后，使得新的数据单元正好能被预定的二进制数除尽。（发送端和接收端都需要做
5、）如果接收端发现了余数，则舍弃该数据块2023-5-7UMTS工作组 曹素华13(B)循环冗余校验(CRC)数 据数 据CRC除 法 器余 数数数 据据CRC000n位除 法 器n+1 位取余数CRCn位发 送 端接 收 端比预设除法器位数(n+1)少1如果所得到的余数少于n位，则所缺少的左边的位假定为0；若余数为0，那么CRC部分为全00:接受非0:拒绝2023-5-7UMTS工作组 曹素华14(B)校验和方式：发送数据时计算校验和并且将其同分组数据一起发送接收方进行类似运算并决定数据取舍校验和：将分组数据取固定长度，取反码算术运算相加（结果也为同样长度），最后取反码就得到校验和。接收端：类
6、似反运算即可校验2023-5-7UMTS工作组 曹素华15(B)校验和 例子：数据校验和，包只在头部校验，取固定长度取值：，28，和校验和28（校验部分）2023-5-7UMTS工作组 曹素华16CRC检测原理 伽罗域基本知识 CRC编码 软件硬件实现2023-5-7UMTS工作组 曹素华17（C1）伽罗域介绍(Galois Field:GF)数据、地址、校验码等都可以看成是属于GF(2m)中的元素或称符号 取m=8，GF(28)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式 的特性是 得到的余式等于0。2023-5-7UMTS工作组 曹素华18加法：0
7、3=001011=010=1减法与加法相同乘法：54=(54)mod7=2除法：5/3=2 3/5=2=(27)=5对数：log(5)=5(C1)伽罗域介绍(Galois Field:GF)v域的运算：2023-5-7UMTS工作组 曹素华19 域的构造（取m=3）假设本原多项式：设为其一根，即：3=1 GF(23)中的元素可计算如下：0 0mod(mod(3 31)=01)=0(000)(000)0 0mod(mod(3 31)=1)=0 0=1=1(001)(001)1 1mod(mod(3 31)=1)=1 1(010)(010)2 2mod(mod(3 31)=1)=2 2(100)(
8、100)3 3 mod(mod(3 31)=1)=1 1(011)(011)4 4 mod(mod(3 31)=1)=2 2(110)(110)5 5 mod(mod(3 31)=1)=2 21 11 1(111)(111)6 6 mod(mod(3 31)=1)=2 21 1(101)(101)（C1）伽罗域介绍(Galois Field:GF)2023-5-7UMTS工作组 曹素华20 本原元：一个元素能产生GF(2n)所有非零元素GF(24)元素a4：(24)0=1,(24)1=24,(24)4=216=21,(24)14=256=211 元素的阶：ak的阶=本原多项式：如果一个多项式f
9、(x)能够产生2n个不同元素(包括0),则为本原多相式。如：本原多项式f(x)=1+x2+x5,即能构造域GF(25)2n-1GCD(2n-1,K)GCD(n,k)为求最大公约数函数（C1）伽罗域介绍(Galois Field:GF)2023-5-7UMTS工作组 曹素华21 最小多项式：GF(2n)中部分元素具有相同的阶，且均为某个多项式的根，取这类多项式的最低次数的多项式即为最小多项式 共轭类：最小多项式相同的元素的组合，GF(2n)中的元素可以按照共轭类分组共轭类共轭类最小多项式最小多项式根的阶根的阶01M0(x)=1+x1a a2 a4 M1(x)=1+x2x37a3 a6 a5 M2
10、(x)=1+x x37（C1）伽罗域介绍(Galois Field:GF)2023-5-7UMTS工作组 曹素华22（C2）CRC编码 编码例子：已知：信息码:110011信息多项式:K(X)=X5+X4+X+1，生成码:11001，生成多项式:G(X)=X4+X3+1(r=4)2023-5-7UMTS工作组 曹素华23 Step1)：(X5+X4+X+1)*X4的积是X9+X8+X5+X4对应的码是1100110000 Step2)：积G(X)1 0 0 0 0 11 0 0 0 0 1Q(X)Q(X)G(x)G(x)1 1 0 0 1)1 1 0 0 1 1 0 0 0 01 1 0 0
11、1)1 1 0 0 1 1 0 0 0 0F(X)F(X)*X Xr r 1 1 0 0 11 1 0 0 1 1 0 0 0 01 0 0 0 0 1 1 0 0 11 1 0 0 11 0 0 11 0 0 1R(X)(R(X)(冗余码冗余码)冗余码是1001,码字就是1100111001 （C2）CRC编码2023-5-7UMTS工作组 曹素华24 解码验证步骤 接收码字:1100111001多项式:T(X)=X9+X8+X5+X4+X3+1生成码:11001 生成多项式:G(X)=X4+X3+1(r=4)step1：用字码除以生成码，余数为0，所以码字正确。step2：因r=4，所以冗
12、余码是：1001，信息码是:110011（C2）CRC编码2023-5-7UMTS工作组 曹素华25一些见于标准的CRC资料 名称名称 生成多项式生成多项式 简记式简记式*应用举例应用举例 CRC-4 x4+x+1 ITU G.704 CRC-12 x12+x11+x3+x+1 CRC-16 x16+x12+x2+1 1005 IBM SDLC CRC-ITU x16+x12+x5+1 1021 ISO HDLC,ITU X.25,V.34/V.41/V.42,PPP-FCS CRC-32 x32+x26+x23+.+x2+x+1 04C11DB7 ZIP,RAR,IEEE 802 LAN/F
13、DDI,IEEE 1394,PPP-FCS CRC-32c x32+x28+x27+.+x8+x6+1 1EDC6F41 SCTP 最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7 2023-5-7UMTS工作组 曹素华26（C2）CRC校验硬件实现v二进制本原多项式的线性反馈移位寄存器机理：考虑二进制一般既约多项式：f(x)=cnxn+.+cixi+.+c2x2+c1x+1,ci GF(2)GF(2)硬件实现用除法电路（硬件实现用除法电路（主体移位寄存器和模主体移位寄存器和模2加法加法器器(异或单元异或单元)组成组成）产生分为两种结构
14、：产生分为两种结构：SSRG:简单移位寄存产生器简单移位寄存产生器MSRG:模块式移位寄存产生器2023-5-7UMTS工作组 曹素华27R1R2+C1C2+Rn-1Cn-2+RnC2+时钟xx2Xn-1xnSSRG 结 构（C2）SSRG:SSRG:简单移位寄存产生器简单移位寄存产生器2023-5-7UMTS工作组 曹素华28)()1(1txtxnn)()1(12txtx)()(.)()()1(1122111txctxctxctxtxnnn)()1(tXTtXS矩阵表示：矩阵表示：)()(1)(1)(tnxtnxtxtX123211100000001000000100000010cccccT
15、nnnS（C2）SSRG:SSRG:简单移位寄存产生器简单移位寄存产生器2023-5-7UMTS工作组 曹素华29（C2C2）MSRG:MSRG:模块移位寄存产生器模块移位寄存产生器R1R2C1C2Rn-1Cn-2+RnC2+时钟xx2Xn-1xn+MSRG 结 构2023-5-7UMTS工作组 曹素华30)()()1(11txctxtxnnnn)()()1(112txctxtxn)()1(1txtxn矩阵表示：矩阵表示：000001100000010000010000011321ccccTnnnM（C2C2）MSRG:MSRG:模块移位寄存产生器模块移位寄存产生器2023-5-7UMTS工作
16、组 曹素华31（C2）SSRG与MSRG的关系 SSRG与MSRG最后的输出就是一个长度为2n的PN序列(但是二者不相同)产生相同的PN序列，SSRG与MSRG应该取互反的。即：假设SSRG用f(x)来得到，那么MSRG就要用 g(x)=xn f(x-1)来得到 2023-5-7UMTS工作组 曹素华32（C2）硬件实现的例子321)(xxxfR1R2+xx2R3x3011100010STSSRG：MSRG：R1R2xx2R3x3+001100011MT2023-5-7UMTS工作组 曹素华33321)(xxxf（C2）硬件实现状态表时钟时钟SSRGMSRGR3 R2 R1状态矢量状态矢量R3
17、 R2 R1状态矢量状态矢量T=00 0 110 0 11T=10 1 00 1 0T=21 0 13 31 0 02 2T=30 1 15 51 0 13 3T=41 1 14 41 1 14 4T=51 1 06 60 1 15 5T=61 0 02 21 1 06 6R3 输出：输出：0 0 1 0 1 1 1R2 输出：输出：0 1 0 1 1 1 0R1 输出：输出：1 0 1 1 1 0 0R3 输出：输出：0 0 1 1 1 0 1R2 输出：输出：0 1 0 0 1 1 1R1 输出：输出：1 0 0 1 1 1 02023-5-7UMTS工作组 曹素华34（C2）CRC-IT
18、U为例 x16+x12+x5+1 16级移位寄存器和3个加法器组成，编码、解码前将各寄存器初始化为“1”，信息位随着时钟移入。当信息位全部输入后，从寄存器组输出CRC结果。(编码解码结构相同)2023-5-7UMTS工作组 曹素华35(C2)CRC软件实现 比特型算法比特型算法：定义一个寄存器组，初始化为全1。依照电路图，每输入一个信息位，相当于一个时钟脉冲到来，从高到低依次移位。移位前信息位与bit0相加产生临时位，其中bit15移入临时位，bit10、bit3还要加上临时位。当全部信息位输入完成后，从寄存器组取出它们的值，这就是CRC码。CRC-ITU为例 x16+x12+x5+12023
19、-5-7UMTS工作组 曹素华36v数字通信系统一般是对一帧数据进行CRC校验，而字节是帧的基本单位。最常用的是一种按字节查表的快速算法.v根据：计算本字节后的CRC码，等于上一字节余式CRC码的低8位左移8位，加上上一字节CRC右移8位和本字节之和后所求得的CRC码。v把8位二进制序列数的CRC(共256个)全部计算出来，放在一个表里，编码时只要从表中查找对应的值进行处理 字节型算法(C2)CRC软件实现2023-5-7UMTS工作组 曹素华37vCRC-ITU的计算算法如下：a.寄存器组初始化为全1(0 xFFFF)。b.寄存器组向右移动一个字节。c.刚移出的那个字节与数据字节进行异或运算
20、，得出一个指向值表的索引。d.索引所指的表值与寄存器组做异或运算。f.数据指针加1，如果数据没有全部处理完，则重复步骤b。g.寄存器组取反，得到CRC，附加在数据之后。字节型算法编码CRC-ITU为例 x16+x12+x5+1 2023-5-7UMTS工作组 曹素华38a.寄存器组初始化为全1(0 xFFFF)。b.寄存器组向右移动一个字节。c.刚移出的那个字节与数据字节进行异或运算，得出一个指向值表的索引。d.索引所指的表值与寄存器组做异或运算。e.数据指针加1，如果数据没有全部处理完，则重复步骤b(数据包括CRC的两个字节)。f.寄存器组的值是否等于“MagicValue”(0 xF0B8)，若相等则通过，否则失败字节型算法解码验证算法CRC-ITU为例 x16+x12+x5+1 2023-5-7UMTS工作组 曹素华39其他编码及比较v 汉明码v BCHv RS码v Turbo Code
