[PCIe]CRC系列1 – CRC3

原创内容,转载请注明:  [https://www.ssdfans.com]  谢谢!

(本文将介绍了CRC相关的一些基础知识,并用CRC3为例推导了CRC的部分原理)
CRC是CyclicRedundancyCheck的缩写,是一种通过额外冗余bit来检查数据完整性的一种方法。一个比较容易类比的方法就是除法操作。例如我们有数据512,我们将512除以11得到46余数是6。那么我们可以将6作为校验信息一起传递给对方。接收端收到512和校验信息6后,也做相同的除法操作,如果得到的余数与收到的校验信息一致,我们认为收到的数据大概率是完整的。
我们将十进制转换成二进制,重新看一遍过程,原始数据是
    512 =  10 0000 0000
    11   =  1011
    10 0000 0000/1011 = 100 0110 余 110 
当传输过程中某一个bit被反转了,例如:
    10 0001 0000 (528)

接收端使用收到的数据进行除法操作,将会得到:

10 0001 0000/1011 = 100 1000 余 0

那么这个校验信息就不一样了,所以接收端认为数据或者校验信息在传输过程中可能出现了错误。

为了使得校验比较方便,我们可以将需要校验的信息放在数据的后面。由于除数是11(1011b),余数有可能是0(0000b)到10(1010b),所以我们可以将原数据向左移4位,空出来的空间存放校验信息。左移4位相当于把原数据乘以了24,即十进制的16。
512*16 = 8192
二进制表示:10 0000 0000 0000b
然后用8192/11 = 744 余8
不难算出,只要将8192加上3,这个新的数就可以被11整除。
所以我们可以将3作为这个原数据的校验信息,并放在原数据的后面一起传送,即:
10 0000 0000 0011b 
如果接收端接收到的数据无法被11整除,即有余数,那么证明接收到的内容可能在传输过程中被修改了。
 
例如,仍然是原数据的第六个bit被反转了,即:
 10 00010000 0011b (8451) 
那么接收端对接收到的内容进行运算会发现:
8451/11 = 768 余 3
并不能被11整除,所以内容可能在传输过程中被修改了。
我们仔细观察会发现,原本的信息是可以被11整除的,多出来的部分是由于某个bit反转而引起的,我们单独将该信息拿出来,可以得到:
1 0000 0000b (256)
如果将这个错误信息除11,我们会发现:
256/11 = 23 余 3
也是余3,是不是发现了什么?没有错,导致最后整个信息不整除的主要原因,是因为反转的bit与其所在的位置所表达的数不能够被11整除。
因为我们在数字世界传送信息的时候大部分都是01表示的二进制代码,所以信息中有任意一个bit被反转,都是2的多少次幂。所以只要除数不是偶数且不是1就可以检测出任意一个bit的错误。例如3(11b),5(101b),7(111b)等等。
由于除法操作可能需要借位,在实际的CRC计算中,采用的是异或(XOR)操作而避免了借位。同样的,如果数据仍然是10 0000 0000b,而‘除数’是1011b,这个‘除数’也被称之为二项式(polynomial),也可以表达成 X3+X+1。
 
那么我们一样将原数据左移,只不过这次我们只移动3位且补0,因为不使用减法操作,只要异或完的结果少于4位,我们就把那3位数作为‘余数’。具体操作如下:
首先将10 0000 0000b左移3位:
1 0000 0000 0000b,然后用1011b作为‘除数’:
异或操作的真值表:
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
其实就是相同就是0,不一样就是1。下面是长除的整个过程:

 

         1011100101
 1011/1000000000000
      1011
       1100
        1011
         1110
         1011
          1010
          1011
             1000
             1011
               1100
               1011
                111 ----------‘余数’ 
这里可以看到我们得到的‘余数’与实际的除法得到的余数有所不同,那么使用这种方式有什么好处呢?
我们接着往下看。
这个‘余数’被称为CRC3的值,作为校验信息可以直接替换掉数据的最后3位,这3位是原数据左移后,补了0的3个位置。当计算出CRC3的值后,可以直接把111b添加在后面,即:
1 0000 0000 0111b
因为异或的原因,这个数正好可以被1011b通过长除的方法整除,便利性与传统除法来说要好不少,大家可以参考前面标红的那句话。另外就是异或操作在数字设计中也比较容易实现。
 
接下来我们继续分析一下检错能力,前面提到设计过的二项式可以保证任意一个bit反转都可以被检测出来。如果需要保证连续相邻的两个bit都反转了也可以被检测出来怎样设计呢?那我们可以分析一下连续两个bit都反转的情况,错误信息的规律。例如我们可以用Xn+Xn-1来表示连续两个bit都反转的情况。因为原来的两个bit与11b进行异或都会取反,所以我们可以用Xn+Xn-1来表示11b并处在任意的位置。通过提取公因数得到:
Xn+Xn-1 = Xn-1(X+1)
所以我们设计的二项式只要不能被X+1整除,那么连续两个bit的错误信息就无法被该二项式整除。因此类似X2+1 或者X3+1这种二项式就是不错的选择。
Note:
二项式 X2+1就是101b
二项式 X3+1就是1001b 
 

Reference:

http://users.ece.cmu.edu/~koopman/crc/


以下是咱们金牌赞助商,某猎头公司的提供的信息:

全球五百强企业,工作地点深圳,岗位为学习岗型,需求9人;

需要技能:
 
1.熟悉CXL协议;
2.熟悉PCIe协议;
3.熟悉其他芯片高速协议
4.熟练掌握芯片前端数字逻辑设计 
5.熟练掌握芯片数字逻辑仿真验证;
6.逻辑思维能力强,主动性强,学习能力强。
6为必要条件,1-5任意满足一个,满足两个条件或以上,优先考虑
薪资待遇:

根据面试结果,待遇丰厚,年薪预计130%-200%或以上

有意者请发简历到fleeves@163.com
分类目录 国内动态, 未分类, 行业动态.
扫一扫二维码或者微信搜索公众号ssdfans关注(添加朋友->点最下面的公众号->搜索ssdfans),可以经常看到SSD技术和产业的文章(SSD Fans只推送干货)。
ssdfans微信群介绍
技术讨论群 覆盖2000多位中国和世界华人圈SSD以及存储技术精英
固件、软件、测试群 固件、软件和测试技术讨论
异构计算群 讨论人工智能和GPU、FPGA、CPU异构计算
ASIC-FPGA群 芯片和FPGA硬件技术讨论群
闪存器件群 NAND、3D XPoint等固态存储介质技术讨论
企业级 企业级SSD、企业级存储
销售群 全国SSD供应商都在这里,砍砍价,会比某东便宜20%
工作求职群 存储行业换工作,发招聘,要关注各大公司招聘信息,赶快来
高管群 各大SSD相关存储公司高管和创始人、投资人

想加入这些群,请微信扫描下面二维码,或搜索nanoarchplus,加阿呆为微信好友,介绍你的昵称-单位-职务,注明群名,拉你进群。SSD业界需要什么帮助,也可以找阿呆聊。