差错检测与CRC课件

差错检测

与

CRC

校验

UMTS

工作组

曹素华

caosh@8/8/20231UMTS工作组曹素华差错检测

与

CRC校验

UMTS工作组

内容概要 差错类型(A) 检测方式概述(B) CRC检测原理(C) 伽罗域基本知识(C1) CRC编码(C2)8/8/20232UMTS工作组曹素华内容概要 差错类型(A) 伽罗域基本知识(C1)7/2(A)差错类型8/8/20233UMTS工作组曹素华(A)差错类型7/28/20233UMTS工作组曹素华(A)单个比特错误定义：在给定数据单元只有一个bit发生改 变比如一个字节、一个字符、一个数据单元或者数据包例子：

发送：00000010(ASCIIcode:STX正文开始)接收：00001010(ASCIIcode:LF换行)发送00000010接收00001010018/8/20234UMTS工作组曹素华(A)单个比特错误定义：在给定数据单元只有一个bit发生改 (A)多个比特错误定义：在给定数据单元有两个或者多个不 连续的bit发生改变发送01000010接收00001010两个bit错误8/8/20235UMTS工作组曹素华(A)多个比特错误定义：在给定数据单元有两个或者多个不 (A)突发错误定义：在给定数据单元连续两个或者更多 个bit发生改变所发送的数据01000010010000100011111000001010所接收的数据8/8/20236UMTS工作组曹素华(A)突发错误定义：在给定数据单元连续两个或者更多 个b

(B)检测方式概述将每个数据块单元发送两次，进行逐bit比较(效率、时间)加冗余bit数据通信中常用冗余的方法来解决通信的可靠性问题8/8/20237UMTS工作组曹素华(B)检测方式概述将每个数据块单元发送两次，进行逐bit比(B)冗余校验的分类垂直冗余校验(VRC)纵向冗余校验(LRC)循环冗余校验(CRC)检验和8/8/20238UMTS工作组曹素华(B)冗余校验的分类垂直冗余校验(VRC)7/28/2023(B)垂直冗余校验(VRC)奇偶校验：在数据块加冗余bit，以保证数据中“1”的个数为奇数或者偶数1100001数据偶校验产生器111000011发送端校验函数接收端校验：1的总数为偶数？Y:AcceptN:Reject8/8/20239UMTS工作组曹素华(B)垂直冗余校验(VRC)奇偶校验：在数据块加冗余bit，(B)纵向冗余校验(LRC)本质：2－DVRC目的：检测多个差错bit和突发错误方法：将确定数据分组，保证单个数据块和数据块的相应bit都具有VRC校验1110011111011101001110011010100110101010数据移动方向LRC数据8/8/202310UMTS工作组曹素华(B)纵向冗余校验(LRC)本质：2－DVRC111001整个数据块移动方向01010101100101011001110010111011111001111110011111011101001110011010100110101010数据移动方向LRC数据单元数据方向(B)纵向冗余校验(LRC)VCRsVCRbitLRCVCRbit8/8/202311UMTS工作组曹素华整个数据块移动方向011101111111001111101(B)循环冗余校验(CRC)功能最为强大方法：将冗余bit序列加在数据之后，使得新的数据单元正好能被预定的二进制数除尽。（发送端和接收端都需要做）如果接收端发现了余数，则舍弃该数据块8/8/202312UMTS工作组曹素华(B)循环冗余校验(CRC)功能最为强大7/28/20231(B)循环冗余校验(CRC)数据数据CRC除法器余数数据CRC00…0n位除法器n+1位取余数CRCn位发送端接收端比预设除法器位数(n+1)少1如果所得到的余数少于n位，则所缺少的左边的位假定为0；若余数为0，那么CRC部分为全00:接受非0:拒绝8/8/202313UMTS工作组曹素华(B)循环冗余校验(CRC)数据数据CR(B)校验和方式：发送数据时计算校验和并且将其同分组数据一起发送接收方进行类似运算并决定数据取舍校验和：将分组数据取固定长度，取反码算术运算相加（结果也为同样长度），最后取反码就得到校验和。接收端：类似反运算即可校验8/8/202314UMTS工作组曹素华(B)校验和方式：发送数据时计算校验和并且将其同分组数据一(B)校验和例子：ＩＰ数据校验和，ＩＰ包只在ＩＰ头部校验，取固定长度取值：１６ｂｉｔｓ４，５，００１０００１０１００００００００28０００００００００００１１１００１０００００００００００００００１０，０００００００００００００００００７，９０００００１１１００００１００１和０１１１０１０００１００１１１０校验和０１１１０１０００１００１１１０４５０28４１７１００１０．１２．１４．５１２．６．７．９（校验部分）8/8/202315UMTS工作组曹素华(B)校验和例子：ＩＰ数据校验和，ＩＰ包只在ＩＰ头部校验，CRC检测原理 伽罗域基本知识 CRC编码软件硬件实现8/8/202316UMTS工作组曹素华CRC检测原理 伽罗域基本知识7/28/202316UMT（C1）伽罗域介绍(GaloisField:GF)数据、地址、校验码等都可以看成是属于GF(2m)中的元素或称符号

取m=8，GF(28)表示域中有256个元素，除0，1之外的254个元素由本原多项式P(x)生成。本原多项式的特性是得到的余式等于0。

8/8/202317UMTS工作组曹素华（C1）伽罗域介绍(GaloisField:GF)数据、地加法：α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)域的运算：8/8/202318UMTS工作组曹素华加法：α0＋α3=001＋011=010=α1(域的构造（取m=3）假设本原多项式：设α为其一根，即：α3=α＋1

GF(23)中的元素可计算如下：

0mod(α3＋α＋1)=0(000)α0mod(α3＋α＋1)=α0=1(001)α1mod(α3＋α＋1)=α1(010)α2mod(α3＋α＋1)=α2(100)α3

mod(α3＋α＋1)=α＋1(011)α4

mod(α3＋α＋1)=α2＋α(110)α5mod(α3＋α＋1)=α2＋α1＋1(111)α6mod(α3＋α＋1)=α2＋1(101)（C1）伽罗域介绍(GaloisField:GF)8/8/202319UMTS工作组曹素华域的构造（取m=3）设α为其一根，即：α3=α＋10本原元：一个元素能产生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-1GCD(2n-1,K)GCD(n,k)为求最大公约数函数（C1）伽罗域介绍(GaloisField:GF)8/8/202320UMTS工作组曹素华本原元：一个元素能产生GF(2n)所有非零元素2n-1GCD最小多项式：GF(2n)中部分元素具有相同的阶，且均为某个多项式的根，取这类多项式的最低次数的多项式即为最小多项式共轭类：最小多项式相同的元素的组合，GF(2n)中的元素可以按照共轭类分组共轭类最小多项式根的阶{0}

{1}M0(x)=1+x1{aa2a4}M1(x)=1+x2＋x37{a3a6a5}M2(x)=1+x

＋x37（C1）伽罗域介绍(GaloisField:GF)8/8/202321UMTS工作组曹素华最小多项式：GF(2n)中部分元素具有相同的阶，且均为某个（C2）CRC编码编码例子： 已知：信息码:110011信息多项式: K(X)=X5+X4+X+1，

生成码:11001，生成多项式: G(X)=X4+X3+1(r=4)

8/8/202322UMTS工作组曹素华（C2）CRC编码编码例子：7/28/202322UMTSStep1)：(X5+X4+X+1)*X4的积是X9+X8+X5+X4

对应的码是1100110000Step2)：积／G(X)

100001←Q(X)

G(x)→11001)1100110000←F(X)*Xr

11001

10000

11001

1001←R(X)(冗余码)冗余码是1001,码字就是1100111001

（C2）CRC编码8/8/202323UMTS工作组曹素华Step1)：(X5+X4+X+1)*X4的积是X9+X解码验证步骤

接收码字: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编码8/8/202324UMTS工作组曹素华解码验证步骤（C2）CRC编码7/28/202324UMT一些见于标准的CRC资料

名称

生成多项式

简记式*

应用举例

CRC-4

x4+x+1

ITUG.704

CRC-12

x12+x11+x3+x+1

CRC-16

x16+x12+x2+1

1005

IBMSDLC

CRC-ITU

x16+x12+x5+1

1021

ISOHDLC,ITUX.25,V.34/V.41/V.42,PPP-FCS

CRC-32

x32+x26+x23+...+x2+x+1

04C11DB7

ZIP,RAR,IEEE802LAN/FDDI,IEEE1394,PPP-FCS

CRC-32c

x32+x28+x27+...+x8+x6+1

1EDC6F41

SCTP

最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7

8/8/202325UMTS工作组曹素华一些见于标准的CRC资料

名称

生成多项式

简记式*

（C2）CRC校验硬件实现二进制本原多项式的线性反馈移位寄存器机理：考虑二进制一般既约多项式：f(x)=cnxn+...+cixi+...+c2x2+c1x+1,ci∈GF(2)硬件实现用除法电路（主体移位寄存器和模2加法器(异或单元)组成）产生分为两种结构： SSRG:简单移位寄存产生器 MSRG:模块式移位寄存产生器8/8/202326UMTS工作组曹素华（C2）CRC校验硬件实现二进制本原多项式的线性反馈移位寄存（C2）SSRG:简单移位寄存产生器8/8/202327UMTS工作组曹素华（C2）SSRG:简单移位寄存产生器7/28/202327矩阵表示：（C2）SSRG:简单移位寄存产生器8/8/202328UMTS工作组曹素华矩阵表示：（C2）SSRG:简单移位寄存产生器7/28/2（C2）MSRG:模块移位寄存产生器8/8/202329UMTS工作组曹素华（C2）MSRG:模块移位寄存产生器7/28/202329矩阵表示：（C2）MSRG:模块移位寄存产生器8/8/202330UMTS工作组曹素华矩阵表示：（C2）MSRG:模块移位寄存产生器7/28/2（C2）SSRG与MSRG的关系SSRG与MSRG最后的输出就是一个长度为2n的PN序列(但是二者不相同)产生相同的PN序列，SSRG与MSRG应该取互反的。即：假设SSRG用f(x)来得到，那么MSRG就要用g(x)=xn×f(x-1)来得到

8/8/202331UMTS工作组曹素华（C2）SSRG与MSRG的关系SSRG与MSRG最后的输出（C2）硬件实现的例子SSRG：MSRG：8/8/202332UMTS工作组曹素华（C2）硬件实现的例子SSRG：MSRG：7/28/2023（C2）硬件实现状态表时钟SSRGMSRGR3R2R1状态矢量R3R2R1状态矢量T=000110011T=1010а010аT=2101а3100а2T=3011а5101а3T=4111а4111а4T=5110а6011а5T=6100а2110а6R3输出：0010111R2输出：0101110R1输出：1011100R3输出：0011101R2输出：0100111R1输出：10011108/8/202333UMTS工作组曹素华（C2）硬件实现状态表时钟SSRGMSRGR3R2（C2）CRC-ITU为例

x16+x12+x5+1

16级移位寄存器和3个加法器组成，编码、解码前将各寄存器初始化为“1”，信息位随着时钟移入。当信息位全部输入后，从寄存器组输出CRC结果。(编码解码结构相同)

8/8/202334UMTS工作组曹素华（C2）CRC-ITU为例

x16+x12+x5+1

1(C2)CRC软件实现比特型算法：定义一个寄存器组，初始化为全"1"。依照电路图，每输入一个信息位，相当于一个时钟脉冲到来，从高到低依次移位。移位前信息位与bit0相加产生临时位，其中bit15移入临时位，bit10、bit3还要加上临时位。当全部信息位输入完成后，从寄存器组取出它们的值，这就是CRC码。

CRC-ITU为例

x16+x12+x5+18/8/202335UMTS工作组曹素华(C2)CRC软件实现比特型算法：定义一个寄存器组，初始化数字通信系统一般是对一帧数据进行CRC校验，而字节是帧的基本单位。最常用的是一种按字节查表的快速算法.根据：计算本字节后的CRC码，等于上一字节余式CRC码的低8位左移8位，加上上一字节CRC