关于CRC基础知识的一些问题

Question

我是一名电子工程师,并没有发现从纯粹的数学角度考虑CRC非常重要.但是,我有以下问题:

1. 当我们计算CRC时,为什么要在消息中添加n个零,n是生成多项式的次数？我已经在modulo-2 long division以及CRC的硬件实现中看到了这一点

2. 为什么我们希望生成多项式可以被(x + 1)整除？

3. 为什么我们希望生成多项式不能被x整除？

Answer 1

1. 我们n在计算n-bit CRC 时添加零,因为当将CRC附加到消息并发送整个(电信中的常规做法)时:
   • 这允许接收侧像消息的其余部分一样处理CRC的比特,从而导致任何无差错传输的已知余数.这是当该消息的末尾是由一些指示尤其有用如下的CRC(一种常见的做法); 在接收端它节省了一个n比特缓冲器,并且在发送端它几乎没有增加复杂性(x(n)在CRC传输期间,AND门强制消息比特减少的额外条款为零,并且执行n额外的减少步骤,因为CRC是发送).
     在数学上,发送的CRC是(M(x) * x^n) mod P(x) = R(x)(可能在一些常数内,或者/或者可能在开始时添加一些规定的位M(x),对应于CRC寄存器的初始化),并且在接收侧计算的CRC在串联M(x)和R(x),即
     (M(x) * x^n + R(x)) mod P(x)零(或称为常数).
   • 它确保影响消息结束和连续CRC的错误突发受益于多项式选择所提供的全部保护.特别是,如果我们计算C(x)为M(x) mod P(x),当错误检测中使用的大多数多项式确保检测到任何两位错误达到某个大的消息大小时,翻转最后一位M(x)和最后一位C(x)将不会被检测到.
2. 通常的做法是将用于错误检测的CRC多项式整除x+1,因为它确保检测到影响奇数位的任何错误.然而,这种做法并不普遍,并且它有时会阻止选择更好的多项式以获得更好的一些有用定义,包括最大化消息长度以便m总是检测到错误(假设没有同步丢失),对于某些组合m和n.特别是,如果我们希望能够检测到尽可能长的消息(ⁿ包括n-bit CRC的2 -1位)的任何2位错误,我们需要多项式是原始的,因此不可简化,因此(对于n> 1)不能被整除x+1.
3. 通常的做法是使用于错误检测的CRC多项式不能被整除x,因为否则生成的CRC的最后一位将是恒定的,并且无助于检测其余信息+ CRC中的错误.