精华内容
下载资源
问答
  • 循环冗余码crc

    2015-10-12 22:16:00
    生成多项式(产生校验的多项式):G(x) 余数多项式:R(x) 商:Q(x) 生成多项式是四次的,所以某个多项式除以生成多项式的余式肯定是三次的,所以要加四位0000。 生成多项式的选择是经过实际应用选择出来的,...

    待编码的有效信息组多项式:M(x)

    生成多项式(产生校验码的多项式):G(x)

    余数多项式:R(x)

    商:Q(x)

    生成多项式是四次的,所以某个多项式除以生成多项式的余式肯定是三次的,所以要加四位0000。

     

    生成多项式的选择是经过实际应用选择出来的,要满足一定的要求。

    R(x)为r阶,在M(x)后面添上r个0(R(x)有r + 1 位)。

    M(x)*x^k = Q(x)*G(x) + R(x)

     

    模2运算

    crc码是基于模2运算而建立编码规律的校验码。模2运算的特点是不考虑进位和借位的运算。其规律如下:

    1、模2加和模2减的结果是相等的,即:0 +/- 1 = 1, 0 +/- 0 = 0, 1 +/- 0 = 1, 1 +/- 1 = 0。两个相同的数的模2和恒为0。

    2、模2乘是按模2和求部分积之和。(和十进制乘法类似)

    3、模2除是按模2减求部分余数。每求一位商应使部分余数减少一位。上商的原则是:当部分余数的首位为1时,上商1;当部分余数的首位为0时,上商0。当部分余数的位数小于除数的位数时,该余数即为最后余数。

                   1 1 1 0
                ────────
    1 0 1 1〕1 1 0 0 1 0 0
              -1 0 1 1
                 ──────
                   1 1 1 1
               - 1 0 1 1
                  ──────
                     1 0 0 0
                 - 1 0 1 1
                    ──────
                       0 1 1 0
                   - 0 0 0 0
                      ──────
                         1 1 0

    例如M(x)=1100

    G(x)=1011

    用1100000 除以 1011得crc码为1100010

    有效信息为4位,校验位为3位,所以有称为(7,4)码。

     

    校验方法:

    将收到的循环校验码用约定的生成多项式G(x)去除,如果无错,则余数应为0;如果某一位出错,则余数不为0,不同的出错为对应不同的余数。对余数补0后继续除下去,余数将按照一定的序列循环下去(循环码的由来)。

     

     

     

     

    具体可参考:http://bbs.csdn.net/topics/50365367

    以下是在这个网站摘录的笔记:

     

    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  1 001000111000000 100111000000
     1 0011
     0 000100111000000
    1  1 00111000000   1000000
     1 0011 
     0 00001000000
    2  1 000000 1100
     1 0011
     0 001100

    从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述:
    //reg是一个5 bits的寄存器
    把reg中的值置0. 
    把原始的数据后添加r个0. 
    While (数据未处理完) 
    Begin 
    If (reg首位是1) 
    reg = reg XOR 0011. 
    把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。 
    End
    reg的后四位就是我们所要求的余数。
    这种算法简单,容易实现,对任意长度生成多项式的G(x)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话,这种方法就不太适合 了。它一次只能处理一位数据,效率太低。为了提高处理效率,可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理,所以 一次处理8位比较合适。
    为了对优化后的算法有一种直观的了解,先将上面的算法换个角度理解一下。在上面例子中,可以将编码过程看作如下过程:
     由于最后只需要余数,所以我们只看后四位。构造一个四位的寄存器reg,初值为0,数据依次移入reg0(reg的0位),同时reg3的数据移出 reg。有上面的算法可以知道,只有当移出的数据为1时,reg才和g(x)进行XOR运算;移出的数据为0时,reg不与g(x)进行XOR运算,相当 与和0000进行XOR运算。就是说,reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit,所以有 种选择。上述算法可以描述如下,
    //reg是一个4 bits的寄存器
    初始化t[]={0011,0000}
    把reg中的值置0. 
    把原始的数据后添加r个0. 
    While (数据未处理完) 
    Begin 
    把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。
    reg = reg XOR t[移出的位]
    End
    上面算法是以bit为单位进行处理的,可以将上述算法扩展到8位,即以Byte为单位进行处理,即CRC-32。构造一个四个Byte的寄存器reg,初 值为0x00000000,数据依次移入reg0(reg的0字节,以下类似),同时reg3的数据移出reg。用上面的算法类推可知,移出的数据字节决 定reg和什么样的数据进行XOR。由于有8个bit,所以有 种选择。上述算法可以描述如下:
    //reg是一个4 Byte的寄存器
    初始化t[]={…}//共有 =256项
    把reg中的值置0. 
    把原始的数据后添加r/8个0字节. 
    While (数据未处理完) 
    Begin 
    把reg中的值左移一个字节,读入一个新的字节并置于reg的第0个byte的位置。
    reg = reg XOR t[移出的字节]
    End
    算法的依据和多项式除法性质有关。如果一个m位的多项式t(x)除以一个r阶的生成多项式g(x), ,将每一位 (0=<k<m)提出来, 在后面不足r个0后,单独去除g(x),得到的余式位 。则将 后得到的就是t(x)由生成多项式g(x)得到的余式。对于CRC-32,可以将每个字节 在后面补上32个0后与生成多项式进行运算,得到余式和此字节唯一对应,这个余式就是上面算法种t[]中的值,由于一个字节有8位,所以t[]共 有 =256项。多项式运算性质可以参见参考文献[1]。这种算法每次处理一个字节,通过查表法进行运算,大大提高了处理速度,故为大多数应用所采用。


    摘自:循环冗余校验 CRC的算法分析和程序实现
    西南交通大学计算机与通信工程学院  刘东

    转载于:https://www.cnblogs.com/little-snake/p/4873028.html

    展开全文
  • 线性反馈移位寄存器LFSR和循环冗余码CRC0 前言1 数学基础1.1 逻辑异或1.2 模2乘法 和 模2除法2 线性反馈移位寄存器LFSR2.1 抽头和特征多项式3 循环冗余码CRC 0 前言 线性反馈移位寄存器(Linear Feedback Shift ...

    0 前言

    线性反馈移位寄存器(Linear Feedback Shift Register,LFSR)和循环冗余码(Cyclic Redundancy Check,CRC)是微控制器中常用的底层原理。

    LFSR用于生成伪随机数,后者用于生成检错码。他们的数学原理都是一样的。

    1 数学基础

    1.1 逻辑异或

    异或运算使用符号或者nor表示,真值表如下
    F = A ⊕ B

    A B F
    0 0 0
    0 1 1
    1 0 1
    1 1 0

    异或运算可以有3种理解方式:

    1 相同得1,不同得0

    2 二进制加法,只留模2的余数,抛弃进位(模2加法)

    3 二进制减法,大数减小数,不借位(模2减法)

    1.2 模2乘法 和 模2除法

    两个二进制数的模2乘法是指在乘法竖式运算中需要做加法的地方都使用异或运算

    模2乘法1010 * 101=100010,下图红框中,1⊕0⊕1=0,没有进位

    在这里插入图片描述
    两个二进制数的模2除法是指在除法竖式运算中需要做减法的地方都使用异或运算

    模2除法10000 / 101=1011,下图红框中,0⊕1=1,没有借位
    在这里插入图片描述

    2 线性反馈移位寄存器LFSR

    以斐波那契(外部LFSR)为例,有n个二进制寄存器R0-Rn-1,每个寄存器值为01
    在这里插入图片描述
    k阶段,寄存器存在初值,(Rn-1, … R1, R0),称为seed
    k+1阶段,寄存器的值变为:

    k+1阶段
    Rn-1 = Rn-2
    Rn-2 = Rn-3
    R0 = f(R1, R2, …, Rn-1) = (Rn-1*gn)⊕(Rn-2*gn-1)⊕…⊕(R0*g1)*g0

    也就是说寄存器存储的结果 (Rn-1, … R1, R0) 每个时钟周期改变一次,其中R1-Rn-1是位移产生,R0是线性反馈函数 f(Rn-1, … R1, R0) 产生,所以称为线性反馈移位寄存器。

    线性反馈移位寄存器总是假定g0,gn1,否则 (Rn-1, … R1, R0) 将在n个周期后恒定为0

    2.1 抽头和特征多项式

    f(Rn-1, … R1, R0) = (Rn-1*gn)⊕(Rn-2*gn-1)⊕…⊕(R0*g1)*g0 可以用多项式表示为:

    G(x)=gnxn+gn-1xn-1+…+g1x+g0

    G(x)称为LFSR的特征多项式

    影响线性反馈寄存器下一个状态的 gi = 01叫做抽头,抽头的设定会决定线性反馈寄存器存储的结果 (Rn-1, … R1, R0) 的变化规律。

    通常N位的线性反馈寄存器最多有 2N 个不同的状态。但是如果出现初值为N个0的情况,线性反馈寄存器陷入死循环,要排除掉。所以N位线性反馈寄存器能产生最长的不重复序列为 2N-1。

    抽头的位置会影响LSFR的最大输出状态的个数
    例如:3位的抽头为(g3, g2, g1, g0) = (1, 1, 0, 1)会产生7个状态(多项式对应为:G(x)=x3+x2+1)
    若抽头为(g3, g2, g1, g0) = (1, 0, 1, 1),会产生2个状态(多项式对应为:x3+x+1)。

    使最大输出序列长度为2N-1的不可约多项式称为LFSR的本原多项式,本原多项式产生的寄存器序列为M序列

    当N位下,本原多项式不是唯一的。下表为不同的位下的本原多项式:
    在这里插入图片描述
    在这里插入图片描述

    2.2 3阶线性反馈移位寄存器实例

    在这里插入图片描述
    上图为3阶线性反馈移位寄存器
    抽头为(g3, g2, g1, g0) = (1, 1, 0, 1)
    多项式对应为:G(x)=x3+x2+1
    线性反馈函数R0 = f(R2, R1, R0) = R1⊕R2
    初始值为SEED = (R2, R1, R0) = (1, 0, 1)

    3阶线性反馈移位寄存器周期为7:

    k周期 (R2, R1, R0)
    0 (1, 0, 1)
    1 (0, 1, 1)
    2 (1, 1, 1)
    3 (1, 1, 0)
    4 (1, 0, 0)
    5 (0, 0, 1)
    6 (0, 1, 0)
    7 (1, 0, 1)

    通过设定seed和抽头,LFSR最多可产生2N-1个序列,这些序列之间看似是随机产生的,之所以称之为伪随机,是因为这些数是通过具体的关系式产生,最终会实现循环。

    3 循环冗余码CRC

    现实的通信链路都不会是理想的。这就是说,比特在传输的过程中可能会产生差错:1可能会变成0,0可能会变成1,这就叫做比特差错。
    因此,为了保证数据传输的可靠性,在计算机网络传输数据时,必须采用各种差错检测措施。
    目前在数据链路层广泛使用了循环冗余检测CRC的检测技术

    3.1 CRC的原理

    CRC运算实际上就是在数据长为k的后面添加供差错检测用的n位冗余码,然后构成帧k+n位发送出去。

    在这里插入图片描述
    选择一个生成多项式,作为对接收的帧进行除法运算时的除数,生成多项式可以写为二进制形式;生成多项式的要求:
    ①最高位和最低位必须为1;
    ②当CRC码的任何一位发生错误时,新帧除生成多项式后余数不为0;
    ③不同位发生错误时,余数应该是不同的;

    计算n位冗余码
    现假定待传输的数据M = 101001(k = 6),除数p = 1101 (n = 3,p比n多一位)
    这n位冗余码可以用下面的方法得出。
    (1)用二进制的模2运算进行(2^n)乘M的运算,相当于在M后面添加n个0。
    即M后面添加3个0
    (2)现在得到M = 101001000(k+n = 9)位的数除以除数p(n = 3)位,
    得到余数R =001(n位),R就是冗余码FCS

    现在加上CRC后发送的帧是101001001

    在接收端把接收到的数据M = 101001001以帧为单位进行CRC检验:把收到的每一个帧都除以相同的除数p(模2运算),然后检查得到的余数R。
    如果在传输过程中没有差错,那么经过检验后得到余数R肯定是0。
    (读者可以自己检验下,被除数现在是M = 101001001,除数P= 1101,看余数是否为0)
    总之,在接收端对接收到的每一个帧经过CRC检验后,有两种情况:
    (1)余数R = 0,则判断这个帧没有问题,就接受
    (2)余数R != 0,则判断这个帧有差错,就丢弃。

    3.2 CRC的实例

    假设CRC生成多项式G(X)=X5+X4+X+1,要发送的二进制数据帧为100101110,求CRC校验码:

    ①把生成多项式转换为二进制数:110011;

    ②由生成多项式的位数为6可知,CRC校验码的位数为5,所以在数据帧后加5个0,变为10010111000000,将这个数使用模2除法除以生成多项式110011,得到余数即CRC校验码11010;
    在这里插入图片描述
    ③用得到的CRC校验码替换掉数据帧中的5个0,形成新的帧10010111011010,将这个新帧发送给接收端;

    ④接收端收到新帧后,用新帧除以上面的多项式110011(模2除法),如果余数为0,该数据帧在传输过程中没有出错,否则出错;(经验证余数为0)

    展开全文
  • 循环冗余码CRC

    2010-03-23 10:07:00
    本文摘自 高传善、钱松荣、毛迪林 编著的> 本文摘自 高传善、钱松荣、毛迪林 编著的>

    本文摘自 高传善、钱松荣、毛迪林 编著的<<数据通信与计算机网络>>

     

     

     

     

     

     

     

     

    本文摘自 高传善、钱松荣、毛迪林 编著的<<数据通信与计算机网络>>

    展开全文
  • 循环冗余码 CRC 的基本思想、 步骤 、示例

    2.循环冗余码(CRC)

    • 将任何一个由二进制位串组成的代码,与一个只含有 0 和 1 两个系数的多项式建立一一对应关系。
    • 多项式的算数运算采用 代数域理论的规则,以 2 为模来完成,即加法没有进位,减法没有借位,模2加法和模2减法都等同于异或

    CRC 的基本思想:发送方和接受方先商定一个生成多项式 G(X),发送方编码和接受方校验都是利用预先商定的生成多项式来得到。假设 G(X) 的阶为 r,发送方要发送的信息位为 k位,CRC 的基本思想是在信息位的尾部追加一个 r位的冗余位,使得信息位与冗余位构成的码字所对应的多项式能够被 G(X)除尽。当接收方收到码字后,用其除以 G(X),如果有余数则表明传输过程中有错误

    CRC 的步骤

    1. 确定生成多项式 G(X)、信息位对应的多项式 K(X)、冗余位的位数 r(CRC中r等于 G(X) 的阶)
    2. 在信息位的后面加上 r 个 0,对应的多项式的 X^rK(X)
    3. 用 X^rK(X) 除以 G(X) 得到的余式就是冗余位对应的多项式 R(X)
    • 这里的除法就是多项式的模2除法,模 2除法中用到的减法是模 2减法
    1. 得到信道上发送的码字多项式 T(X)=X^rK(X)+R(X)
    2. 校验。若传输过程无差错,则接受方收到的码字多项式能被 G(X) 整除;若不能被 G(X) 整除,则说明传输过程中产生了差错。

    在这里插入图片描述
    在这里插入图片描述
    CRC的一些性质:
    在这里插入图片描述

    数据链路层-差错控制(奇偶校验,定比码,正反码)
    数据链路层-差错控制(海明码)

    展开全文
  • 在数据链路层中,最广泛应用的检错码是一种漏检率很低也便于硬件实现的循环冗余校验码CRC(Cyclic Redundancy Code)。 1、CRC码 CRC码又称多项式码,任何一个由二进制位数串组成的代码都可由一个只含有0和1两个系数...
  • 理解循环冗余码CRC

    千次阅读 2010-08-25 09:05:00
    在计算机网络和数据通信中用E得最广泛的检错码,是一种漏检率低得多也便于实现的循环冗余码CRC (Cyclic Redundancy .Code),CRC码又称为多项式码。 任何一个由二进制数位串组成的代码,都可以惟一地与一个只含有0...
  • 循环冗余码CRC使用matlab实现

    千次阅读 2020-07-06 10:46:33
    crc编码
  • 对于CRC的编码原理、编码过程、相关性质进行了介绍。
  • 用verilog编程,用四位的对象inf保存输入的信息数据,四位的对象gx保存输入的生成多项式,七位的reg类型的对象outcrc保存要输出的crc码,四位的reg类型的对象temp保存再次模二除的被除数。
  • 1. 最终发送的数据 = 要发送的数据 + 帧检验序列FCS(冗余码) 2. 利用生成多项式计算冗余码 计算冗余码的方法: 1. 加0, 要根据生成多项式中的阶为, 则加个0. (例题中生成多项式为10011, 也就是, 式中的最高阶为4,...
  • CRC 循环冗余码

    2020-09-13 13:45:49
    循环冗余码CRC),又称为多项式码,是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。CRC 的工作方法是在发送端产生一个冗余码,附加在信息位后面一起发送到接收端,接收...
  • 文章目录循环冗余校验码CRCCRC介绍例题详解例题1例题2总结 循环冗余校验码CRC CRC介绍 1.收发方约定好一个生成多项式G(x) 2.发送方基于待发送的数据和生成多项式计算出差错检验码(冗余码),将其添加到待传输数据的...
  • 文章目录前言一、进制转换1.1 二进制转换为八进制数和十六进制数1.2 任意进制数转换为十进制数1.3 十进制转换为任意进制二、校验求取2.1海明校验2.2循环冗余校验CRC码总结 前言 了解进制间的相互转换: 二...
  • 循环冗余校验码CRC

    2017-06-11 20:29:10
    关于CRC循环冗余校验的基本原理及作用。
  • CRC循环冗余码 CRC循环冗余码是在通信领域经常用来用作检错编码的方式。 计算冗余码 我们可以通过以下步骤计算出冗余码: (1)加0:在要发送的数据后加r个0,其中r为生成多项式G(x)的阶为(一般来说,多项式为N位...
  • 循环冗余校验 CRC 原理

    千次阅读 2012-02-28 12:21:20
    在计算机网络和数据通信中用E得最广泛的检错码,是一种漏检率低得多也便于实现的循环冗余码CRC (Cyclic Redundancy .Code),CRC码又称为多项式码。 任何一个由二进制数位串组成的代码,都可以惟一地与一个只含有0和1...
  • 循环冗余检验 CRC

    千次阅读 2019-03-30 21:10:37
    一、总体流程: 把要发送的每组数据M(k位)除以除数P(n+1位),计算出冗余码FCS(n位),将原始数据乘以2n(相当于把M左移了n位...在数据链路层传送的帧中,广泛使用了循环冗余检验 CRC 的检错技术。 在发送端,先把...
  • 循环冗余检错码CRC

    千次阅读 2018-05-19 20:05:40
    模2运算模2加以及模2减等同于异或运算,即相同得0,相异得1模2乘法模2除法样例如下循环冗余检错码CRC任何一个k位的帧看成为一个k-1次的多项式M(x):1011001 看成 x^6+x^4+x^3+1(k项k-1阶多项式)设定一个多项式编码...
  • 循环冗余码校验CRC

    2011-12-30 08:11:27
    CRC的计算过程,还有CRC的介绍文字,是本人考试之前整理的,
  • Verilog语言实现并行(循环冗余码CRC校验 1 前言 (1) 什么是CRC校验? CRC即循环冗余校验码:是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC...
  • 四、循环冗余校验  在串行传送(磁盘、通讯)中,广泛采用循环冗余校验CRC)。...循环冗余校验CRC)的基本原理是:在K位信息后再拼接R位的校验,整个编码长度为N位,因此,这种编码又叫
  • 循环冗余检验CRC

    2020-08-18 10:30:42
    数据部分M(k个bit) and 商定除数P(n+1),n是冗余码的长度。 发送的帧:数据部分+冗余码 冗余码求法: M后添加n个0 除以商定除数P 得到余数R,R即冗余码 R = 0,接受 R ≠ 0,有错,丢弃 例题: 设M = 101001...
  • Cyclic Redundancy Check循环冗余检验,是基于数据计算一组效验,用于核对数据传输过程中是否被更改或传输错误。完整的CRC-32标准所包含的内容:引用Name : "CRC-32"Width : 32Poly : 04C11DB7Initial value : ...
  • Java实现循环冗余码CRC)生成算法

    千次阅读 2017-09-06 20:14:13
    Java实现循环冗余码CRC)生成算法一、CRC生成算法原理1.1 多项式编码 多项式编码(polynomial code),也称为CRC(cyclic redundancy check,循环冗余校验码),多项式编码的思想是:将位串看成是系数为0或1的...
  • CRC循环冗余码校验

    2012-05-21 21:55:10
    CRC循环冗余码校验,计算机网络课程中会用到。JAVA实现
  • 循环冗余校验 CRC

    2020-06-20 22:20:42
    算法:双方预先规定好一个二进制数,即生成多项式,这个多项式最高最低位均为1。多项式短于帧长度。 设生成多项式为r+1位,即将发送的帧长为m位,则帧在后面加上r个0,得到一个m+r位的数。 ...
  • CRC循环冗余码

    千次阅读 2017-06-28 16:23:19
    CRC循环冗余校验:是数据通信领域最常用的一种差错校验,其特征是信息字段和校验字段长度可以任意选定。CRC的原理: 在K位信息后再拼接R位的校验,整个编码长度为N位,因此,这种编码也叫(N,K)。...
  • 循环冗余校验CRC

    2020-06-28 21:02:04
    与海明校验类似,CRC码也是数据通讯中常用的校验方式。 CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。 结构 与海明校验数据位和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,372
精华内容 548
关键字:

循环冗余码crc