红薇花 玟馨:循环冗余校验CRC的算法分析
来源:百度文库 编辑:中财网 时间:2024/05/05 19:46:29
循环冗余校验CRC的算法分析
西南交通大学计算机与通信工程学院 刘东
摘要
通信的目的是要把信息及时可靠地传送给对方,因此要求一个通信系统传输消息必须可靠与快速,在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性,通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC(Cyclic Redundancy Check)的差错控制原理及其算法实现。
关键字 通信 循环冗余校验 CRC-32 CRC-16 CRC-4
概述
在数字通信系统中可靠与快速往往是一对矛盾。若要求快速,则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少,从而在受到干扰后产生错误地可能性增加,传送信息地可靠性下降。若是要求可靠,则使得传送消息地速率变慢。因此,如何合理地解决可靠性也速度这一对矛盾,是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性,需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式(ARQ)、向前纠错方式(FEC)和混合纠错(HEC)。在传输过程误码率比较低时,用FEC方式比较理想。在传输过程误码率较高时,采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中,广泛采用ARQ方式,此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多,传统的有:奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等,这些方法都是增加数据的冗余量,将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验,再将得到的校验码和接受到的校验码比较,如果二者一致则认为传输正确。但这些方法都有各自的缺点,误判的概率比较高。
循环冗余校验CRC(Cyclic Redundancy Check)是由分组线性码的分支而来,其主要应用是二元码组。编码简单且误判概率很低,在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其 算法实现。
一、循环冗余校验码(CRC)
CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式,由 。如一个8位二进制数10110101可以表示为: 。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,和逻辑异或运算一致。
采用CRC校验时,发送方和接收方用同一个生成多项式g(x),并且g(x)的首位和最后一位的系数必须为1。CRC的处理方法是:发送方以g(x)去除t(x),得到余数作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。
CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于k(k为g(x)的阶数)的突发错误。所以CRC的生成多项式的阶数越高,那么误判的概率就越小。CCITT建议:2048 kbit/s的PCM基群设备采用CRC-4方案,使用的CRC校验码生成多项式g(x)= 。采用16位CRC校验,可以保证在 bit码元中只含有一位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16,其生成多项式g(x)= ;而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16,其生成多项式g(x)= 。CRC-32的生成多项式g(x)= 。CRC-32出错的概率比CRC-16低 倍 。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适,所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SIO)内,都采用了CRC校验码进行差错控制;以太网卡芯片、MPEG解码芯片中,也采用CRC-32进行差错控制。
二、CRC校验码的算法分析
CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下:
(1) 设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)。在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为 。
(2) 用生成多项式g(x)去除 ,求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。
(3) 用 以模2的方式减去y(x),得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。
从CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式 ,所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时 可以看做是由t(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。
为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,用一个CRC-4编码的例子来说明CRC的编码过程。
设待发送的数据t(x)为12位的二进制数据100100011100;CRC-4的生成多项式为g(x)= ,阶数r为4,即10011。首先在t(x)的末尾添加4个0构成 ,数据块就成了1001000111000000。然后用g(x)去除 ,不用管商是多少,只需要求得余数y(x)。下表为给出了除法过程。
除数次数 被除数/g(x)/结果 余数
0 1001000111000000 100111000000
10011
0000100111000000
1 100111000000 1000000
10011
000001000000
2 1000000 1100
10011
0001100
从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。
CRC校验由于实现简单,检错能力强,被广泛使用在各种数据校验应用中。占用系统资源少,用软硬件均能实现,是进行数据传输差错检测地一种很好的手段。
西南交通大学计算机与通信工程学院 刘东
摘要
通信的目的是要把信息及时可靠地传送给对方,因此要求一个通信系统传输消息必须可靠与快速,在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性,通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC(Cyclic Redundancy Check)的差错控制原理及其算法实现。
关键字 通信 循环冗余校验 CRC-32 CRC-16 CRC-4
概述
在数字通信系统中可靠与快速往往是一对矛盾。若要求快速,则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少,从而在受到干扰后产生错误地可能性增加,传送信息地可靠性下降。若是要求可靠,则使得传送消息地速率变慢。因此,如何合理地解决可靠性也速度这一对矛盾,是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性,需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式(ARQ)、向前纠错方式(FEC)和混合纠错(HEC)。在传输过程误码率比较低时,用FEC方式比较理想。在传输过程误码率较高时,采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中,广泛采用ARQ方式,此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多,传统的有:奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等,这些方法都是增加数据的冗余量,将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验,再将得到的校验码和接受到的校验码比较,如果二者一致则认为传输正确。但这些方法都有各自的缺点,误判的概率比较高。
循环冗余校验CRC(Cyclic Redundancy Check)是由分组线性码的分支而来,其主要应用是二元码组。编码简单且误判概率很低,在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其 算法实现。
一、循环冗余校验码(CRC)
CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式,由 。如一个8位二进制数10110101可以表示为: 。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,和逻辑异或运算一致。
采用CRC校验时,发送方和接收方用同一个生成多项式g(x),并且g(x)的首位和最后一位的系数必须为1。CRC的处理方法是:发送方以g(x)去除t(x),得到余数作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。
CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于k(k为g(x)的阶数)的突发错误。所以CRC的生成多项式的阶数越高,那么误判的概率就越小。CCITT建议:2048 kbit/s的PCM基群设备采用CRC-4方案,使用的CRC校验码生成多项式g(x)= 。采用16位CRC校验,可以保证在 bit码元中只含有一位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16,其生成多项式g(x)= ;而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16,其生成多项式g(x)= 。CRC-32的生成多项式g(x)= 。CRC-32出错的概率比CRC-16低 倍 。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适,所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SIO)内,都采用了CRC校验码进行差错控制;以太网卡芯片、MPEG解码芯片中,也采用CRC-32进行差错控制。
二、CRC校验码的算法分析
CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下:
(1) 设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)。在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为 。
(2) 用生成多项式g(x)去除 ,求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。
(3) 用 以模2的方式减去y(x),得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。
从CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式 ,所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时 可以看做是由t(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。
为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,用一个CRC-4编码的例子来说明CRC的编码过程。
设待发送的数据t(x)为12位的二进制数据100100011100;CRC-4的生成多项式为g(x)= ,阶数r为4,即10011。首先在t(x)的末尾添加4个0构成 ,数据块就成了1001000111000000。然后用g(x)去除 ,不用管商是多少,只需要求得余数y(x)。下表为给出了除法过程。
除数次数 被除数/g(x)/结果 余数
0 1001000111000000 100111000000
10011
0000100111000000
1 100111000000 1000000
10011
000001000000
2 1000000 1100
10011
0001100
从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。
CRC校验由于实现简单,检错能力强,被广泛使用在各种数据校验应用中。占用系统资源少,用软硬件均能实现,是进行数据传输差错检测地一种很好的手段。
关于数据收发的循环冗余校验(CRC)问题
给我做道题——网络—— CRC循环冗余码的算法
CRC循环校验是什么????????
crc循环冗余编码
什么是Ultra DMA循环冗余校验计数?
什么是Ultra DMA循环冗余校验计数?
请教高手!!急呀,请问谁有现成的CRC(循环冗余校验码)纠错源代码??
求教海明码和CRC循环冗余校验码的原理或课件下载或学习笔记??
我复制DVD的时候提示循环冗余校验错误,这是为什么?
什么是原码、反码、补码、移码、crc循环冗余码?
求CRC校验法 32位的
CRC:求软驱通信的CRC算法?是CRC-16还是CRC-32?
什么是原码、反码、补码、移码、crc循环冗余码?交换机的菊花链堆叠和矩阵堆叠有什么区别?
什么叫CRC校验????
如何生成和翻译CRC(循环冗余校验码) 最好给个例子我非常谢谢
网络题————CRC循环冗余码怎么算
网络题————CRC循环冗余码怎么算
crc校验的工具官方网在哪里的???
我们的考试题,CRC校验,请说的详细点。
crc算法在单片机上的实现
crc算法在单片机上的实现
求:循环冗余检查的解决
重装系统 出现循环冗余的错误
谁知道ECC内存的校验算法啊?