武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
3
CRC产生的背景 产生的背景
1.为追求 快速性
采用差 错控制
2.为追求 可靠性
每个码元 所占时间 缩短
波形变窄
能量减少
可用的 通信系统 传送消息
速率变慢
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
4
CRC的特点 的特点
循环冗余校验码（CRC） 循环冗余校验码（CRC） 的原理、 的原理、实现及应用
指导老师：肖萍萍 指导老师： 负责成员：CRC研究小组 负责成员：CRC研究小组 时间：2010.10.18～ 时间：2010.10.18～11.16
武汉邮电科学研究院
CRC原理的实现与应用
CRC产生的背景及原理 CRC产生的背景及原理 CRC软件的实现 CRC软件的实现
CRC寄存器内的数据从高到低进行第一次移位， CRC寄存器内的数据从高到低进行第一次移位，在最高位补 寄存器内的数据从高到低进行第一次移位 而最低位(已被移出CRC寄存器)如果为1 CRC寄存器 零，而最低位(已被移出CRC寄存器)如果为1，则把寄存器与 生成多项式码进行异或运算，如果LSB为零， 保持; LSB为零 生成多项式码进行异或运算，如果LSB为零，则保持; 重复8次步骤2的移位， 第一个8bits数据处理完毕， 重复8次步骤2的移位，则第一个8bits数据处理完毕，用 8bits数据处理完毕 此时CRC寄存器的值与下一个8bits CRC寄存器的值与下一个8bits数据异或并进行如前一 此时CRC寄存器的值与下一个8bits数据异或并进行如前一 个数据似的8次移位; 个数据似的8次移位;
DLC协议 的应用 协议
HDLC协议简介 HDLC协议简介
HDLC是一个第二层协议,它用于来连接点到点的串行设 HDLC是一个第二层协议, 是一个第二层协议 它运行在广域网两个不同的地方。 备，它运行在广域网两个不同的地方。每个路由器将 会解封装HDLC的数据包对它们进行转发到LAN HDLC的数据包对它们进行转发到LAN或者是丢 会解封装HDLC的数据包对它们进行转发到LAN或者是丢 HDLC完整的帧由标志字段 完整的帧由标志字段（ ）、地址字段 地址字段（ 弃。 HDLC完整的帧由标志字段（F）、地址字段（A）、 控制字段（ ）、信息字段 信息字段（ ）、帧校验序列字段 控制字段（C）、信息字段（I）、帧校验序列字段 FCS）等组成。 （FCS）等组成。
武汉邮电科学研究院
下面 100001 11001 1100110000 11001 10000 11001 1001
1100111001 110011 1001 。
9
2010年12月8日星期三 年 月 日星期三
接收方校验方案
接收方 校验方案
方案一：直接 方案一： 用接收到的序 列除以生成多 项式G(x), G(x),如 项式G(x),如 果余数R (x) 果余数R’(x) 0,则证明传 = 0,则证明传 输正确。 输正确。
18
3.CRC校验生成程序 校验生成程序
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
19
CRC校验生成程序 校验生成程序
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
20
4.CRC校验检错模块 校验检错模块
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
1111111101000011 01111111101000011
上下进行异或运算
1010000000000001 1101111110100000
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
29
步骤三
将得到的数 据再向右移 位 CRC-16生成 CRC-16生成 多项式
1111111101000011 001111111101000011
21
5.CRC校验检测模块程序 校验检测模块程序
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
22
CRC校验检测模块程序 校验检测模块程序
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
23
CRC的应用---HDLC协议
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
25
2.PPP/HDLC发送端框图 发送端框图
帧标志 串行发送
原始数据
并行转换
0处理 插0处理
CRC计算 计算
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
26
3.生成过程 生成过程
1
在开始时CRC寄存器的每一位都预置为1, CRC寄 在开始时CRC寄存器的每一位都预置为1, 把CRC寄 CRC寄存器的每一位都预置为 存器与8bits的数据进行异或运算; 存器与8bits的数据进行异或运算; 8bits的数据进行异或运算
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
6
CRC 校验和计算法
1.若生成多项式 位位串) 1.若生成多项式 G(x) 为 r 阶(即r＋1位位串)， M(x)， 原帧为 m 位， 其多项式为 M(x)，则在原帧后 即循环左移r 面添加 r 个 0，即循环左移r位，帧成为 m+r 位，相应多项式成为 xrM(x); 2.按模 按模2 G(x)对应的位串去除对应于 2.按模2除法用 G(x)对应的位串去除对应于 xr 的位串, R(x)； M(x) 的位串, 得余数 R(x)； 3.按模 减法(即模2 按模2 3.按模2减法(即模2加)从对应于 xr M(x) 的位 串中减去(加上) R(x),结果即传送的带校验 串中减去(加上)余数 R(x),结果即传送的带校验 和的帧多项式T(x) T(x)。 和的帧多项式T(x)。
15
CRC硬件实现过程 CRC硬件实现过程
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
16
1.硬件原理框图 硬件原理框图
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
17
2.CRC校验生成模块 校验生成模块
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
上下进行异或运算
1010000000000001 1001111111010001
重复8次步骤 的移位 数据处理完毕， 重复 次步骤2的移位，则第一个 次步骤 的移位， 第一个8bits数据处理完毕，用此 数据处理完毕 寄存器的值与下一个8bits数据异或并进行如前一个 时CRC寄存器的值与下一个 寄存器的值与下一个 数据异或并进行如前一个 数据似的8次移位 数据似的 次移位; 次移位
1111111111111111
上下进行异或运算
0000000010111100 1111111101000011
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
28
步骤二
高位补0 高位补
若最低位是1， 若最低位是 ， 则需要异或
将得到的数 据向右移位 CRC-16生成 CRC-16生成 多项式
2.核心步骤算法解释 核心步骤算法解释
如何进行两列数字序列的除法运算得到余式-如何进行两列数字序列的除法运算得到余式 ----校验码 校验码R(X) 校验码
3.仿真演示 仿真演示
通过输入任意的信息码元序列，经过 通过输入任意的信息码元序列，经过CRC-4 的校验，在接收端进行检错 的校验，
武汉邮电科学研究院
T(x) = xrM(x) + R(x)
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
7
用CRC 运算能进行校验的证明：
发
设 xr M(x) 除以 G(x) 的商和余数分别为 Q(x) R(x)。则有: 和 R(x)。则有:
xrM(x) = G(x) Q(x) + R(x)
接收方收到带CRC校验和的 接收方收到带CRC校验和的 CRC 帧多项式T(x) 帧多项式T(x) = xr M(x) R(x)。 + R(x)。
课题框架
CRC硬件的实现 CRC硬件的实现 CRC在HDLC帧中的应用 CRC在HDLC帧中的应用
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
2
CRC产生的背景 产生的背景
可靠性 可靠性
快速性 快速性
在数字通信系统中可靠与快速往往是矛盾的。 在数字通信系统中可靠与快速往往是矛盾的。 如何合理地解决可靠与速度这一对矛盾呢？ 如何合理地解决可靠与速度这一对矛盾呢？
CRC的主要 CRC的主要 特点
开销很小
易于实现
武汉邮电科学研究院
2010年12月8日星期三 年 月 日星期三
5
CRC原理 原理
将待发送的位串看成系数为 0 或 1 的多项式； 的多项式；
收发双方约定一个生成多项式 G(x)（其最高阶 G(x)（ 和最低阶系数必须为1），发送方用位串及 和最低阶系数必须为1），发送方用位串及 G(x) 进行某种运算得到校验和， 进行某种运算得到校验和，并在帧的末尾加上校 验和， 整除; 验和，使带校验和的帧的多项式能被 G(x) 整除; 接收方收到后， 除多项式，若有余数， 接收方收到后，用 G(x) 除多项式，若有余数， 则传输有错。 则传输有错。
检错能力 极强 应用范围广
1. ARJ,LHA,ZIP 等压缩软件采 用的是CRC 32； CRC用的是CRC-32； 2. GIF,TIFF等图 GIF,TIFF等图 像存储格式； 像存储格式； 3. 所有链路层或 网络接口层协 议中， 议中，例如 HDLC、 HDLC、DDCMP 等众多领域。 等众多领域。