精华内容
下载资源
问答
  • 计算循环冗余校验码计算

    万次阅读 2015-07-07 09:44:18
    计算循环冗余校验码计算

    循环冗余校验码的计算是计算机组成原理的一大考点,具体算法如下:


    A、编码原理:   

                               现假设有:   有效信息:M   ;  

                   除数G(生成多项式)   有:   M/G=Q+R/G

                              此时,可选择R作为校验位,则MR即为校验码。

                             

    B、校验原理:  (M-R/G=Q+0/G   

                                说明:以接收到的校验码除以约定的除数,若余数为0,则可认为接收到的数据是正确的。

                         

                             例:有效信息1101,生成多项式样1011

                   求循环校验码解:  

                                             有效信息1101(k=4),即M(x)=x3+x2+x0    生成多项式1011(r+1=4,r=3),

                                                     G(x)=x3+x1+x0    M(x)·x3=x6+x5+x3,即1101000(对1101左移三位)   

                                            M(x)·x3/G(x)=1101000/1011=1111+001/1011    即1010CRC是:1101001

                           

                                                    如下图进行计算:

                

                                                    


                                            循环校验码的来源余数与出错序号间处理存在对应模式,

                                           该模式只与只与码制和生成多项式有关,与具体的码字无关。

                                            生成多项式满足的条件:任一位发生错误都应使余数不为0不同的位发生的错误余数应不同。


    展开全文
  • 循环冗余校验码计算CRC

    万次阅读 2015-05-15 17:19:30
    循环冗余校验码,CRC

    CRC循环冗余检验码的计算题

    1、若信息码字为11100011,生成多项式 G(X)=X5+X4+X+1,则计算出的 CRC 校验码为?

    x的最高次幂5则 信息码(被除数)补五个0为:1110001100000 除数为 110011

    ------------10110110
    --------------------- 
    110011/1110001100000
    -------110011
    ------------------
    ---------101111
    ---------110011
    ------------------
    ----------111000
    ----------110011
    ------------------
    ------------101100
    ------------110011
    ------------------------
    -------------111110
    -------------110011
    -------------------------
    ---------------11010

    2、信息码为101110101,生成多项式X4+X2+1,求冗余位???

    算法同上 被除数补四个0 为:1011101010000 除数为:10101

    答案:1100

    展开全文
  • 循环冗余校验码

    2020-07-15 10:06:54
    循环冗余校验码

    循环冗余校验码

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 相关文章: 校验码——码距 校验码——海明码及码距 校验码——CRC循环冗余校验码 一、循环冗余校验码 ... 在串行传送(磁盘、通讯)中,广泛采用循环冗余校验码... 循环冗余校验码(CRC)的基本原理是:在...

    相关文章:

           校验码——码距   https://blog.csdn.net/weixin_44330072/article/details/106860286

           校验码——奇偶校验码   https://blog.csdn.net/weixin_44330072/article/details/106859838

           校验码——海明码及码距   https://blog.csdn.net/weixin_44330072/article/details/106695425

       

           其实校验码就是在码距的原理上产生的,码距越大校验能力,纠错能力越强,所以奇偶校验码、海明码、CRC码究其原理都是利用一系列规则提升一段码字的码距而已。

     

    一、循环冗余校验码

           在串行传送(磁盘、通讯)中,广泛采用循环冗余校验码(CRC)。CRC也是给信息码加上几位校验码,以增加整个编码系统的码距和查错纠错能力。
           CRC的理论很复杂,一般书上只介绍已有生成多项式后计算校验码的方法。检错能力与生成多项式有关,只能根据书上的结论死记。
           循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为 N位,因此,这种编码又叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式。
           校验码的具体生成过程为:假设发送信息用信息多项式C(X)表示,将C(x)左移R位,则可表示成C(x)*2R,这样C(x)的右边就会空出R位,这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。

    几个基本概念

    1、多项式与二进制数码
           多项式和二进制数有直接对应关系:x的最高幂次对应二进制数的最高位,以下各位对应多项式的各幂次,有此幂次项对应1,无此幂次项对应0。可以看出:x的最高幂次为R,转换成对应的二进制数有R+1位。
           多项式包括生成多项式G(x)和信息多项式C(x)。
           如生成多项式为 G(x)=x^{4}+x^{3}+x+1 , 可转换为二进制数码11011。
           而发送信息位 1111,可转换为数据多项式为 C(x)=x^{3}+x^{2}+x+1 。
    2、生成多项式
           是接受方和发送方的一个约定,也就是一个二进制数,在整个传输过程中,这个数始终保持不变。
           在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。
    应满足以下条件:
           a、生成多项式的最高位和最低位必须为1。
           b、当被传送信息(CRC码)任何一位发生错误时,被生成多项式做模2除后应该使余数不为0。
           c、不同位发生错误时,应该使余数不同。
           d、对余数继续做模2除,应使余数循环。
    将这些要求反映为数学关系是比较复杂的。但可以从有关资料查到常用的对应于不同码制的生成多项式如图9所示:

    NK码距dG(x)多项式G(x)
    743x^{3}+x+11011
    743x^{3}+x^{2}+11101
    734x^{4}+x^{3}+x^{2}+111101
    734x^{4}+x^{2}+x+110111
    15113x^{4}+x+110011
    1575x^{8}+x^{7}+x^{6}+x^{4}+1111010001
    31263x^{5}+x^{2}+1100101
    31215x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+111101101001
    63573x^{6}+x+11000011
    63515x^{12}+x^{10}+x^{5}+x^{4}+x^{2}+11010000110101
    10411024 x^{16}+x^{15}+x^{2}+111000000000000101

                                                                                           图9 常用的生成多项式

    3、模2除(按位除)
           模2除做法与算术除法类似,但每一位除(减)的结果不影响其它位,即不向上一位借位。所以实际上就是异或。然后再移位移位做下一位的模2减。步骤如下:
           a、用除数对被除数最高几位做模2减,没有借位。
           b、除数右移一位,若余数最高位为1,商为1,并对余数做模2减。若余数最高位为0,商为0,除数继续右移一位。
           c、一直做到余数的位数小于除数时,该余数就是最终余数。

    【例】1111000除以1101:  
     



    CRC码的生成步骤
           1、将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。
           2、将信息码左移R位,相当与对应的信息多项式C(x)*2R
           3、用生成多项式(二进制数)对信息码做模2除,得到R位的余数。
           4、将余数拼到信息码左移后空出的位置,得到完整的CRC码。

    【例】假设使用的生成多项式是 G(x)=x^{3}+x+1 。4位的原始报文为1010,求编码后的报文。

    解:

           1、将生成多项式 G(x)=x^{3}+x+1 转换成对应的二进制除数1011。
           2、此题生成多项式有4位(R+1),要把原始报文C(x)左移3(R)位变成1010000
           3、用生成多项式对应的二进制数对左移4位后的原始报文进行模2除:

                     1 0 0 1
            ___________________
            |               
    1 0 1 1 |  1 0 1 0 0 0 0
            /  1 0 1 1      
             ——————————————————
                 0 0 1 0
                 0 0 0 0
             ——————————————————
                   0 1 0 0
                   0 0 0 0
             ——————————————————
                     1 0 0 0
                     1 0 1 1
             ——————————————————
                       0 1 1  (余数,校验位)

           4、编码后的报文(CRC码):

           1 0 1 0 0 0 0
        +          0 1 1
      ————————————————————
           1 0 1 0 0 1 1

    CRC的和纠错

           在接收端收到了CRC码后用生成多项式为G(x)去做模2除,若得到余数为0,则码字无误。若如果有一位出错,则余数不为0,而且不同位出错,其余数也不同。可以证明,余数与出错位的对应关系只与码制及生成多项式有关,而与待测?字(信息位)无关。图10给出了G(x)=1011,C(x)=1010的出错模式,改变C(x)(码字),只会改变表中码字内容,不改变余数与出错位的对应关系。

    收到的CRC码字余数出错位
    A_{7}A_{6}A_{5}A_{4}A_{3}A_{2}A_{1}
    1010011000
    10100100011
    10100010102
    10101111003
    1011011011

    4

    10000111105
    11100111116
    00100111017

                                                                             图10  (7,4)CRC码的出错模式(G(x)=1011)

           如果循环码有一位出错,用G(x)作模2除将得到一个不为0的余数。如果对余数补0继续除下去,我们将发现一个有趣的结果;各次余数将按图10顺序循环。例如第一位出错,余数将为001,补0后再除(补0后若最高位为1,则用除数做模2减取余;若最高位为0,则其最低3位就是余数),得到第二次余数为010。以后继续补0作模2除,依次得到余数为100,0ll…,反复循环,这就是“循环码”名称的由来。这是一个有价值的特点。如果我们在求出余数不为0后,一边对余数补0继续做模2除,同时让被检测的校验码字循环左移。图10说明,当出现余数 (101)时,出错位也移到A7位置。可通过异或门将它纠正后在下一次移位时送回A1。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时,循环码校验能有效地降低硬件代价,这是它得以广泛应用的主要原因。

    【例】对图10的CRC码(G(x)=1011,C(x)=1010),若接收端收到的码字为1010111,用G(x)=1011做模2除得到一个不为0的余数100,说明传输有错。将此余数继续补0用G(x)=1011作模2除,同时让码字循环左移1010111。做了4次后,得到余数为101,这时码字也循环左移4位,变成1111010。说明出错位已移到最高位A7,将最高位1取反后变成0111010。再将它循环左移3位,补足7次,出错位回到A3位,就成为一个正确的码字1010011。

           其中一直好奇一个问题:为什么余数是100就是第三位出错,余数是101就是第七位出错呢。其实CRC码的出错模式是由它自己的校验码而决定的,所以应该就是发送方决定的,接收方并不知道。知道了才能纠错。这方面也没有特别固定的资料,有些书上说CRC码并不能纠错,只能重传,也有些说纠错很复杂不讨论等。但是也有比如武大考研题目就出了纠错的题,就很迷~

                         |
                  1 0 0 1|1 0 1 1 1
          _______________|___________
         |               |
    1011 |  1 0 1 0 1 1 1|
         /  1 0 1 1      |
          ———————————————|———————————
              0 0 1 1    |
              0 0 0 0    |
          ———————————————|———————————
                0 1 1 1  |
                0 0 0 0  |
          ———————————————|———————————
                  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 0
                        1|0 1 1
          ———————————————|———————————
                         |1 1 1 0
                         |1 0 1 1
          ———————————————|———————————
                         |  1 0 1 0
                         |

    通信与网络中常用的CRC

           在数据通信与网络中,通常k相当大,由一千甚至数千数据位构成一帧,而后采用CRC码产生r 位的校验位。它只能检测出错误,而不能纠正错误。一般取r=16,标准的16位生成多项式有CRC-16=X_{16}+X_{15}+X_{2}+1 和 CRC-CCITT=X_{16}+X_{15}+X_{2}+1。
           一般情况下,r位生成多项式产生的CRC码可检测出所有的双错、奇数位错和突发长度小于等于 r的突发错以及(1-2-(r-1))的突发长度为r+1的突发错和(1-2-r)的突发长度大于r+1的突发错。例如,对上述r=16的情况,就能检测出所有突发长度小于等于16的突发错以及99.997%的突发长度为17的突发错和99.998%的突发长度大于17的突发错。所以CRC码的检错能力还是很强的。这里,突发错误是指几乎是连续发生的一串错,突发长度就是指从出错的第一位到出错的最后一位的长度(但是,中间并不一定每一位都错)。

    【例1】某循环冗余码(CRC)的生成多项式 G(x)=x3+x2+1,用此生成多项式产生的冗余位,加在信息位后形成 CRC 码。若发送信息位 1111 和 1100 则它的 CRC 码分别为_A_和_B_。由于某种原因,使接收端收到了按某种规律可判断为出错的 CRC 码,例如码字_C_、_D_、和_E_。(1998年试题11)

    供选择的答案:

           A:             ① 1111100        ② 1111101       ③ 1111110       ④ 1111111
           B:             ① 1100100       ② 1100101      ③ 1100110      ④ 1100111
           C~E:       ① 0000000       ② 0001100      ③ 0010111      ④ 0011010   ⑤ 1000110    ⑥ 1001111    ⑦ 1010001    ⑧ 1011000

    解:

           A:G(x)=1101,C(x)=1111 C(x)*23 ÷ G(x)=1111000 ÷ 1101=1011余111
                 得到的CRC码为1111111
           B:G(x)=1101,C(x)=1100 C(x)*23 ÷ G(x)=1100000 ÷ 1101=1001余101
                 得到的CRC码为1100101
           C~E:
                 分别用G(x)=1101对①~⑧作模2除:
                        ① 0000000 ÷ 1101 余000
                        ② 1111101 ÷ 1101 余001
                        ③ 0010111 ÷ 1101 余000
                        ④ 0011010 ÷ 1101 余000
                        ⑤ 1000110 ÷ 1101 余000
                        ⑥ 1001111 ÷ 1101 余100
                        ⑦ 1010001 ÷ 1101 余000
                        ⑧ 1011000 ÷ 1101 余100
           所以_C_、_D_和_E_的答案是② 、⑥ 、⑧。

    【例2】计算机中常用的一种检错码是CRC,即 _A_ 码。在进行编码过程中要使用 _B_ 运算。假设使用的生成多项式是 G(X)=X4+X3+X+1, 原始报文为11001010101,则编码后的报文为 _C_ 。CRC码 _D_ 的说法是正确的。
    在无线电通信中常采用它规定码字长为7位.并且其中总有且仅有3个“1”。这种码的编码效率为_E_。

    供选择的答案:

           A:   ① 水平垂直奇偶校验           ② 循环求和                            ③ 循环冗余                           ④ 正比率
           B:   ① 模2除法                           ② 定点二进制除法                 ③ 二-十进制除法                ④ 循环移位法
           C:   ① 1100101010111              ② 110010101010011             ③ 110010101011100            ④ 110010101010101
           D:   ① 可纠正一位差错                                                             ② 可检测所有偶数位错         
                    ③ 可检测所有小于校验位长度的突发错                             ④ 可检测所有小于、等于校验位长度的突发错
           E:   ① 3/7                                   ② 4/7                                     ③ log_{2}3 / log_{2}7                       ④ (log_{2}35)/7

    解:从前面有关CRC的论述中可得出:

           A:② 循环冗余
           B:① 模2除法
           C:G(x)=11011,C(x)=11001010101,C(x)*24 ÷ G(x)=110010101010000 ÷ 11011 余0011
                  得到的CRC码为② 110010101010011
           D:从前面有关通信与网络中常用的CRC的论述中可得出:④ 可检测所有小于、等于校验位长度的突发错
           E:定比码又叫定重码,是奇偶校验的推广。在定比码中,奇数或偶数的性质保持不变,然而附加一种限制,每个字中1的总数是固定的。随用途之不同,定比码要求的附加校验位可能多于一个,但较之单一的奇偶校验将增加更多的检错能力。
           所谓7中取3定比码,就是整个码字长度为7位,其中1的位数固定为3。所有128个7位代码(0000000~1111111)中只有1的位数固定为3的才是其合法码字。可以用求组合的公式求出其合法码字数为:C73=7!/(3!* (7-3)!)=7*6*5/(1*2*3)=35
           编码效率=合法码字所需位数/码字总位数=(log_{2}35)/7

     

    做题攻略:

    【题1】假定要传输的数据长度为10位,对每个数据块进行CRC校验,根据CRC校验规则,要能检测并纠正一位错误,对应的CRC码的总位数为(   )。

                A. 4                                        B. 10                                      C. 13                                    D. 14

           利用 k+r\leqslant 2^{r}-1 来计算,k是信息位,r是校验位。选D

    【题2】设G(x)=1011,某(7,4)CRC校验码的编码序列为C_{7}C_{6}C_{5}C_{4}C_{3}C_{2}C_{1},假定CRC编码传输过程中最多只能发生一位错误,已知 C_{1}位出错时得到的余数是001,则 C_{4}位出错时接收方进行校验得到的余数是(   )。

                A. 010                                        B. 100                                      C. 011                                    D. 110

           将余数(本题中是001)继续用校验码模2除的话出错位将左移。也就是001补0变成0010用1011进行模2除得到的余数将是 C_{2}出错时得到的余数,所以继续进行上述操作两次,将能得到C_{4}位出错时得到的余数。选C

    【题3】设计待校验的信息为8位,假定传输中最多只发生一位错误,采用CRC校验时,生成多项式的二进制位数至少需要(   )。

                A. 3                                        B. 4                                      C. 5                                    D. 6

           跟第一道题类似,通过公式能算出来需要4位校验码,5位生成多项式二进制数才能得到4位余数来做校验码。选C

    【题4】设待校验的信息长度为K位,生成多项式为G(x),下列关于CRC校验的描述中正确的是(   )。

           A. 只有一位出错时,接收端进行校验得到的余数只与出错位的位置有关,与K位信息的取值和G(x)的取值无关
           B. 只有一位出错时,接收端进行校验得到的余数与出错位位置和G(x)的取值有关,与K位信息的取值无关
           C. 只有一位出错时,接收端进行校验得到的余数与出错位位置、G(x)及K位信息的取值都有关
           D. CRC校验得到的无错结论不一定是正确的

           根据上文内容本题很简单。选BD

    展开全文
  • I/O端口和寄存器用统一的地址空间,所有访存指令可以访问I/O端口 计算题 原码补码反码 首先要了解,转换为原码补码反码后是要在最高位加一位符号位的 如果有题目是用补码求原码或者真值,先将补码取反加一得到原码...
  • 在串行传送(磁盘、通讯)中,广泛采用循环冗余校验码(CRC)。CRC也是给信息码加上几位校验码,以增加整个编码系统的码距和查错纠错能力。 本文介绍了循环冗余校验码的基本原理,内含例题。
  • (17)采用CRC进行差错校验,生成多项式为G(X)=X4+X+1,信息码字为10111,则...CRC(Cyclic Redundancy Check)循环冗余校验码 是常用的校验码,在早期的通信中运用广泛,因为早期的通信技术不够可靠(不可靠性的来...
  • CRC循环冗余校验码

    千次阅读 2017-06-19 16:31:57
    CRC循环冗余校验码是一种差错检测方式,数据在传输时,给数据后方加上一定长度的冗余码对其进行校验。是数据通信领域中最常用的一种查错校验,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是...
  • 循环冗余校验码 CRC校验

    千次阅读 2013-11-23 17:40:43
    四、循环冗余校验码  在串行传送(磁盘、通讯)中,广泛采用循环冗余校验码(CRC)。CRC也是给信息码加上几位校验码,以增加整个编码系统的码距和查错纠错能力。  CRC的理论很复杂,一般书上只介绍已有生成...
  • CRC校验(循环冗余校验码

    千次阅读 2017-06-21 14:23:53
    CRC即循环冗余校验码:是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是一种数据传输检错功能,对数据进行多项式计算,并将得到的结果附在帧的后面...
  • 细说循环冗余校验码

    万次阅读 多人点赞 2017-07-12 20:01:08
    初识循环冗余校验码: 为了保证数据传输的可靠性,在计算机网络传输数据时,必须采用各种差错检验措施,目前广泛使用的是循环冗余(CRC)检验的检错技术。 CRC检验原理: 在发送端,先把数据划分为组,假定每个组...
  • 循环冗余校验码CRC怎么算

    千次阅读 2020-11-23 22:58:45
    文章目录循环冗余校验码CRCCRC介绍例题详解例题1例题2总结 循环冗余校验码CRC CRC介绍 1.收发方约定好一个生成多项式G(x) 2.发送方基于待发送的数据和生成多项式计算出差错检验码(冗余码),将其添加到待传输数据的...
  • 【计算机网络】CRC校验码||循环冗余码详解及计算习题
  • 循环冗余校验码CRC

    2017-07-02 19:21:37
    CRC:循环冗余校验码 CRC是数据通信领域中最常用的一种差错校验码,其特征信息是信息字段和校验字段的长度可以任意选定。CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而...
  • 循环冗余校验码例题[转帖]

    万次阅读 2012-10-03 18:06:26
    循环冗余校验码是模2除,也就是说他是异或算法。而假如我们接受到得CRC码在除以循环冗余检验校验码时有余数说明,在传输过程中,出错了! 在串行传送(磁盘、通讯)或者TCP/IP协议中,广泛采用循环...
  • 奇偶校验码是 奇校验码 和 偶校验码 的统称. 它们都是通过在要校验的编码上加一位校验位组成. 如果是 奇校验 加上校验位后,编码中1的个数为 奇数个 如果是 偶校验 加上校验位后,编码中1的个数为 偶数个 水平奇偶校验...
  • CRC循环冗余校验码 我们知道不同的校验码都有着独特的校验方法,CRC校验码则是根据余数来进行校验的。 简单的来讲就是现在我要给你发送数据,我们来保证这串数据除以5没有余数,那么你拿到数据后想要判断它有没有...
  • CRC循环冗余校验码总结

    万次阅读 多人点赞 2015-04-28 15:53:45
    先在此说明下什么是CRC:循环冗余码校验 英文名称为Cyclical Redundancy Check,简称CRC,它是利用除法及余数的原理来作错误侦测(Error Detecting)的。实际应用时,发送装置计算出CRC值并随数据一同发送给接收装置...
  • 二进制数据经过传送、存取等环节...所有解决此类问题的方法就是在原始数据(数码位)基础上增加几位校验冗余)位。 一、距 一个编码系统中任意两个合法编码(码字)之间不同的二进数位(bit)数叫这
  • 先在此说明下什么是CRC:循环冗余码校验 英文名称为Cyclical Redundancy Check,简称CRC,它是利用除法及余数的原理来作错误侦测(Error Detecting)的。实际应用时,发送装置计算出CRC值并...
  • 海明校验+循环冗余校验码

    千次阅读 2008-10-22 10:12:00
    海明校验+循环冗余校验码 海明校验我们在前面指出过要能纠正信息字中的单个错误,所需的最小距离为3。实现这种纠正的方法之一是海明码。 海明码是一种多重(复式)奇偶检错系统。它将信息用逻辑形式编码,以便能够检错...
  • 循环冗余校验码(CRC)的基本原理

    千次阅读 2008-09-13 15:42:00
    循环冗余校验码(CRC)的基本原理 循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码又叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂...
  • 现在此说明下什么是CRC:循环冗余码校验 英文名称为Cyclical Redundancy Check,简称CRC,它是利用除法及余数的原理来作错误侦测(Error Detecting)的。实际应用时,发送装置计算出CRC值并随数据一同发送给接收装置,...
  • 用在海明中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。实现得合适时,这个系统对于错误的数位无论是原有信息位中的,还是附加校验...

空空如也

空空如也

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

循环冗余校验码计算题