计算CRC编码的方法和装置

摘要

本申请提供一种计算CRC编码的方法，包括：获取待编码的第一序列；使用至少一个多项式对该待编码的第一序列进行编码，生成第二序列；使用本原多项式对该第二序列进行编码，生成针对第一序列的校验序列，该至少一个多项中每个多项式为该本原多项式的倍式，该至少一个多项式中每个多项式的项数少于该本原多项式的项数。该方法能够降低计算CRC编码的复杂度，提高CRC编码的效率和性能。

权利要求

1.一种计算CRC编码的方法，其特征在于，包括：获取待编码的第一序列；

使用至少一个多项式对所述待编码的第一序列进行编码，生成第二序列；

使用本原多项式对所述第二序列进行编码，生成针对第一序列的校验序列，所述至少一个多项式中每个多项式为所述本原多项式的倍式，所述至少一个多项式中每个多项式的项数少于所述本原多项式的项数。

2.根据权利要求1所述的方法，其特征在于，所述至少一个多项式包括第一多项式，所述第一多项式Q1(x)满足：Q1(x)＝(x369+x31+1)·xa

其中，xa为调整系数，a是根据寄存器的容量确定的，且a为大于或等于0的整数，所述寄存器用于存储所述第一序列。

3.根据权利要求2所述的方法，其特征在于，所述至少一个多项式包括第二多项式，所述第二多项式Q2(x)满足：Q2(x)＝(x65535+1)·xb

其中，xb为调整系数，b是根据寄存器的容量确定的，且b为大于或等于0的整数，所述寄存器用于存储所述第一序列。

4.根据权利要求3所述的方法，其特征在于，所述对待编码的第一序列使用至少一个多项式对所述待编码的第一序列进行编码，生成第二序列，包括：对所述待编码的第一序列使用所述第二多项式进行编码，生成第三序列；

对所述第三序列使用所述第一多项式进行编码，生成所述第二序列。

5.根据权利要求1至4中任一项所述的方法，其特征在于，所述方法还包括：根据所述第一序列的长度，确定所述至少一个多项式。

6.根据权利要求2所述的方法，所述第一序列的长度为4096。

7.根据权利要求6所述的方法，其特征在于，所述第二序列的长度为394或422。

8.根据权利要求3所述的方法，其特征在于，所述第一序列的长度为4194304。

9.一种计算CRC编码的装置，其特征在于，包括：获取模块，用于获取待编码的第一序列；

处理模块，用于使用至少一个多项式对所述待编码的第一序列进行编码，生成第二序列；

所述处理模块还用于，使用本原多项式对所述第二序列进行编码，生成针对第一序列的校验序列，所述至少一个多项式中每个多项式为所述本原多项式的倍式，所述至少一个多项式中每个多项式的项数少于所述本原多项式的项数。

10.根据权利要求9所述的装置，其特征在于，所述至少一个多项式包括第一多项式，所述第一多项式Q1(x)满足：Q1(x)＝(x369+x31+1)·xa

其中，xa为调整系数，a是根据寄存器的容量确定的，且a为大于或等于0的整数，所述寄存器用于存储所述第一序列。

11.根据权利要求10所述的装置，其特征在于，所述至少一个多项式包括第二多项式，所述第二多项式Q2(x)满足：Q2(x)＝(x65535+1)·xb

其中，xb为调整系数，b是根据寄存器的容量确定的，且b为大于或等于0的整数，所述寄存器用于存储所述第一序列。

12.根据权利要求11所述的装置，其特征在于，所述处理模块还用于，对所述待编码的第一序列使用所述第二多项式进行编码，生成第三序列；对所述第三序列使用所述第一多项式进行编码，生成所述第二序列。

13.根据权利要求9至12中任一项所述的装置，其特征在于，所述处理模块还用于，根据所述第一序列的长度，确定所述至少一个多项式。

14.根据权利要求10所述的装置，所述第一序列的长度为4096。

15.根据权利要求14所述的装置，其特征在于，所述第二序列的长度为394或422。

16.根据权利要求11所述的装置，其特征在于，所述第一序列的长度为4194304。

17.一种计算CRC编码的装置，其特征在于，包括：接口，用于获取待编码的第一序列；

存储器，用于存储程序；

处理器，用于执行所述存储器中存储的程序，当所述存储器中的程序被执行时，所述处理器用于：通过所述接口获取待编码的第一序列；使用至少一个多项式对所述待编码的第一序列进行编码，生成第二序列；使用本原多项式对所述第二序列进行编码，生成针对第一序列的校验序列，所述至少一个多项式中每个多项式为所述本原多项式的倍式，所述至少一个多项式中每个多项式的项数少于所述本原多项式的项数。

18.根据权利要求17所述的装置，其特征在于，所述至少一个多项式包括第一多项式，所述第一多项式Q1(x)满足：Q1(x)＝(x369+x31+1)·xa

其中，xa为调整系数，a是根据寄存器的容量确定的，且a为大于或等于0的整数，所述寄存器用于存储所述第一序列。

19.根据权利要求18所述的装置，其特征在于，所述至少一个多项式包括第二多项式，所述第二多项式Q2(x)满足：Q2(x)＝(x65535+1)·xb

其中，xb为调整系数，b是根据寄存器的容量确定的，且b为大于或等于0的整数，所述寄存器用于存储所述第一序列。

20.根据权利要求19所述的装置，其特征在于，所述处理器还用于，对所述待编码的第一序列使用所述第二多项式进行编码，生成第三序列；对所述第三序列使用所述第一多项式进行编码，生成所述第二序列。

21.根据权利要求17至20中任一项所述的装置，其特征在于，所述处理器还用于，根据所述第一序列的长度，确定所述至少一个多项式。

22.根据权利要求18所述的装置，所述第一序列的长度为4096。

23.根据权利要求22所述的装置，其特征在于，所述第二序列的长度为394或422。

24.根据权利要求19所述的装置，其特征在于，所述第一序列的长度为4194304。

说明书

计算CRC编码的方法和装置

技术领域

[0001] 本申请涉及信息技术领域，并且更具体地，涉及计算CRC编码的方法和装置。

背景技术

[0002] 在存储系统中，循环冗余校验(Cyclic Redundancy Check,CRC)编码是一种循环码，在存储系统中的CRC编码通常使用基于伽罗华域GF(2)的本原多项式设计CRC编码方案。

[0003] CRC编码原理：假设一个L比特的信息序列(信息取值为0或1)，aL-1,aL-2,…,a0，其中信息序列可以为待处理的数据，比如待存储或发送的数据，L比特的信息序列能够表示为一个多项式：

[0004] C(x)＝aL-1x^(L-1)+aL-2x^(L-2)+aL-3x^(L-3)+…+a0

[0005] 其中，aL-1是信息序列的最高有效位(Most Significant Bit，MSB)，a0是信息序列的最低有效位(Least Significant Bit,LSB)，x^(L-1)表示X的L-1次幂或X的L-1次方。

[0006] 另外，m阶本原多项式G(m)满足：

[0007] G(x)＝gmx^m+gm-1x^(m-1)+gm-2x^(m-2)+…+g0

[0008] 则，计算C(x)的CRC编码可以表示为CRC(C(x))＝C(x)*x^m mod G(x)

[0009] 从上面的式子可以看出，CRC编码表示的是C(x)*x^m除以另一个固定的数G(x)之后的余数，其中“*”表示乘。

[0010] 在存储系统中，为了对有效数据进行检错，存储系统会对数据进行CRC编码，从而数据在存储或传输过程中发生错误后，存储系统能快速的进行数据一致性校验，因此CRC编码是存储系统中的必备特性。

[0011] 已知一种现有的CRC编码方法，该方法在进行CRC编码操作时需要大量的移位操作和异或运算，增加了计算的复杂度，需要消耗大量的计算资原，从而影响了CRC编码的效率与性能。

发明内容

[0012] 本申请提供一种计算CRC编码的方法，能够降低计算CRC编码的复杂度，提高CRC编码的效率和性能。

[0013] 第一方面，提供了一种计算CRC编码的方法，包括：获取待编码的第一序列；使用至少一个多项式对所述待编码的第一序列进行编码，生成第二序列；使用本原多项式对所述第二序列进行编码，生成针对第一序列的校验序列，所述至少一个多项中每个多项式为所述本原多项式的倍式，所述至少一个多项式中每个多项式的项数少于所述本原多项式的项数。

[0014] 在使用本原多项式计算待编码的数据(例如，第一序列)的CRC编码之前，通过本原多项式的至少一个倍式计算待编码的数据的CRC编码，获得中间序列(例如，第二序列)，再对该中间序列使用本原多项式计算该中间序列的CRC编码，从而避免仅使用本原多项式计算待编码的数据的CRC编码时，由于循环移位操作与异或运算的次数较多导致的CRC编码的计算复杂度较高的问题。

[0015] 作为一种可选的实现方式，所述至少一个多项式包括第一多项式，所述第一多项式Q1(x)满足：

[0016] Q1(x)＝(x369+x31+1)·xa

[0017] 其中，xa为调整系数，a是根据寄存器的容量确定的，且a为大于或等于0的整数，所述寄存器用于存储所述第一序列。

[0018] 具体地，作为示例而非限定，对于长度为4096的第一序列，在计算其CRC编码时，可以先使用本原多项式的倍式Q1(x)对其进行编码，获得第二序列(例如，该第二序列的长度为394或422)，再对该第二序列使用本原多项式进行编码，最终获得该第一序列的CRC编码。从而减少计算该第一序列时的循环移位操作与异或运算的次数，提高CRC编码的效率和性能。

[0019] 作为另一种可选的实现方式，所述至少一个多项式包括第二多项式，所述第二多项式Q2(x)满足：

[0020] Q2(x)＝(x65535+1)·xb

[0021] 其中，xb为调整系数，b是根据寄存器的容量确定的，且b为大于或等于0的整数，所述寄存器用于存储所述第一序列。

[0022] 具体地，作为示例而非限定，对于长度为4194304的第一序列，在计算其CRC编码时，可以先使用本原多项式的倍式Q2(x)对其进行编码，获得第二序列，再对该第二序列使用本原多项式进行编码，最终获得该第一序列的CRC编码，从而减少计算该第一序列时的循环移位操作与异或运算的次数，提高CRC编码的效率和性能。

[0023] 此外，通过调整系数对该本原多项式的倍式(例如，Q1(x)或Q2(x))进行调整(例如，经过调整，使得根据本原多项式的倍式对第一序列划分后获得的每个数据段均能够占满整数个寄存器)，使得利用调整后的本原多项式的倍式计算第一序列的CRC编码时能够充分利用寄存器的硬件资源。

[0024] 作为示例而非限定，所述对待编码的第一序列使用至少一个多项式进行编码，生成第二序列，包括：对所述待编码的第一序列使用所述第二多项式进行编码，生成第三序列；对所述第三序列使用所述第一多项式进行编码，生成所述第二序列。

[0025] 具体地，对于较长的第一序列(例如，第一序列的长度为4194304)，在计算该第一序列的CRC编码时，可以先使用本原多项式的一个倍式(例如，Q2(x))对该第一序列进行编码，获得一个中间序列(例如，第三序列)，再使用本原多项式的另一个倍式(例如，Q1(x))对该第三序列进行编码，获得另一个中间序列(例如，第二序列)，再对该第二序列使用本原多项式进行编码，最终获得该第一序列的CRC编码，从而减少计算该第一序列时的循环移位操作与异或运算的次数，提高CRC编码的效率和性能。

[0026] 对于本原多项式而言，一个本原多项式通常会存在多个该本原多项式的倍式，对于待编码的第一序列，需要从该本原多项式的多个倍式中确定用于计算该第一序列的CRC编码的倍式。

[0027] 作为示例而非限定，可以根据该第一序列的长度，从该本原多项式的多个倍式中确定用于计算该第一序列的CRC编码的倍式。

[0028] 例如，当该第一序列的长度为4096时，从该本原多项式的多个倍式中将Q1(x)确定为用于计算该第一序列的CRC编码的倍式。

[0029] 此外，在确定用于计算该第一序列的CRC编码的倍式时，还可以进一步遵循以下原则：

[0030] 本原多项式的倍式的有效项的项数较少，和/或本原多项式的倍式的最高项的指数与次高项的指数的差值较大。

[0031] 第二方面，提供一种计算CRC编码的装置，所述装置用于执行上述第一方面或第一方面的任一可能的实现方式中的方法。具体地，所述装置可以包括用于执行第一方面或第一方面的任一可能的实现方式中的方法的模块。

[0032] 第三方面，提供一种计算CRC编码的装置，所述装置包括接口、存储器和处理器，所述存储器用于存储指令，所述处理器用于执行所述存储器存储的指令，并且对所述存储器中存储的指令的执行使得所述处理器执行第一方面或第一方面的任一可能的实现方式中的方法。

[0033] 第四方面，提供一种芯片，所述芯片包括接口、存储器和处理器，所述存储器用于存储指令，所述处理器用于执行所述存储器存储的指令，并且对所述存储器中存储的指令的执行使得所述处理器执行第一方面或第一方面的任一可能的实现方式中的方法。

[0034] 第五方面，提供一种计算机可读存储介质，所述计算机可读存储介质中存储有指令，当所述指令在计算机上运行时，使得计算机执行第一方面或第一方面的任一可能的实现方式中的方法。

[0035] 第六方面，提供一种包含指令的计算机程序产品，当该计算机程序产品在计算机上运行时，使得计算机执行第一方面或第一方面的任一可能的实现方式中的方法。

附图说明

[0036] 图1是本申请实施例的存储阵列架构示意图。

[0037] 图2是本申请实施例的存储阵列的控制器的示意图。

[0038] 图3是本申请实施例的分布式块存储系统的示意图。

[0039] 图4是分布式块存储系统的服务器的示意性结构框图。

[0040] 图5是现有技术的CRC编码示意图。

[0041] 图6是本申请实施例提供的计算CRC编码的方法的示意性流程图。

[0042] 图7是本申请实施例提供的划分第一序列的示意图。

[0043] 图8是本申请实施例提供的计算CRC编码的原理性示意图。

[0044] 图9是本申请实施例提供的计算CRC编码的另一原理性示意图。

[0045] 图10是本申请实施例提供的划分第一序列的另一示意图。

[0046] 图11是本申请实施例提供的计算CRC编码的另一原理性示意图。

[0047] 图12为本申请实施例提供的计算CRC编码的装置的示意性框图。

[0048] 图13为本申请实施例提供的计算CRC编码的装置的另一示意性框图。

具体实施方式

[0049] 下面将结合附图，对本申请实施例中的技术方案进行描述。

[0050] 首先对适用于本申请实施例的存储系统进行介绍。

[0051] 如图1所示，本申请实施例中的存储系统，可以为存储阵列(如 的18000系列， V3系列)。存储阵列包括存储控制器101和多块硬盘，其中，硬盘包含固态硬盘(Solid State Disk,SSD)、机械硬盘或者混合硬盘等。机械硬盘如HDD(Hard Disk Drive)。如图2所示，控制器101包含中央处理单元(Central Processing Unit,CPU)201、存储器202和接口203，存储器202中存储计算机指令，CPU201执行存储器202中的计算机指令对存储系统进行管理及数据访问操作。另外，为节省CPU201的计算资原，现场可编程门阵列(Field Programmable Gate Array,FPGA)或其他硬件也可以用于执行本申请实施例中CPU201全部操作，或者，FPGA或其他硬件与CPU201分别用于执行本申请实施例CPU201的部分操作。为方便描述，本申请实施例统一用处理器来指CPU201和存储器202的组合，以及上述各种实现，处理器与接口203通信。接口203可以为网络接口卡(Networking Interface Card,NIC)、主机总线适配器(Host Bus Adaptor,HBA)，天线等。

[0052] 如图1和图2所描述的存储阵列，控制器101用于获取数据，如接收主机或客户端发送的数据，使用本申请实施例提供的计算CRC编码的方法计算数据的CRC编码。

[0053] 进一步的，本申请实施例的存储系统还可以为分布式文件存储系统(如 的9000系列)，分布式块存储系统(如 的 系列)等。以
的 系列。示例性的如图3所示，分布式块存储系统包括多台服务器，如服务器
1、服务器2、服务器3、服务器4、服务器5和服务器6，服务器间通过InfiniBand或以太网络等互相通信。在实际应用当中，分布式块存储系统中服务器的数量可以根据实际需求增加，本申请实施例对此不作限定。

[0054] 分布式块存储系统的服务器中包含如图4所示的结构。如图4所示，分布式块存储系统中的每台服务器包含中央处理单元(Central Processing Unit,CPU)401、内存402、接口403、硬盘1、硬盘2和硬盘3，内存402中存储计算机指令，CPU401执行内存402中的程序指令执行相应的操作。接口403可以为硬件接口，如网络接口卡(Network Interface Card,NIC)或主机总线适配器(Host Bus Adaptor,HBA)等，也可以为程序接口模块等。硬盘包含固态硬盘(Solid State Disk,SSD)、机械硬盘或者混合硬盘。机械硬盘如HDD(Hard Disk Drive)。另外，为节省CPU401的计算资原，现场可编程门阵列(Field Programmable Gate Array,FPGA)或其他硬件也可以代替CPU401执行上述相应的操作，或者，FPGA或其他硬件与CPU401共同执行上述相应的操作。为方便描述，本申请实施例将CPU401与内存402、FPGA及其他替代CPU401的硬件或FPGA及其他替代CPU401的硬件与CPU401的组合统称为处理器。接口403可以为网络接口卡(Networking Interface Card,NIC)、主机总线适配器(Host Bus Adaptor,HBA)，天线等。

[0055] 如图3和图4所描述的分布式块存储系统，服务器的处理器用于获取数据，如接收主机或客户端发送的数据，使用本申请实施例提供的计算CRC编码的方法计算数据的CRC编码。

[0056] 除图1-4所示的场景外，本申请实施例还可以应用到数据传输场景，为了保证数据传输的可靠性，如计算机网络、各种通信网络中传输数据时使用本申请实施例所提供的计算数据CRC编码方法。如计算机获取数据，如计算机上应用程序产生的数据，计算数据的CRC编码。

[0057] 下面对计算待编码数据的CRC编码的一般方法做简单介绍。

[0058] 通常采用流水线(pipeline)的方式结合查表法进行CRC编码，如图5所示：

[0059] a)把数据分成若干个片段(Segment)，如Segment 0至Segment N，其中N为不小于1的自然数。

[0060] b)对每个段单独进行CRC编码，分别得到crc 0至crc N。

[0061] c)将每个段编码得到的crc和特定的常量系数(Constant)进行无进位乘法(Carry-less Multiplication,CLMUL)。例如，将crc0与Constant 0进行CLMUL，将crc 1与Constant 1进行CLMUL，……，将crc N与Constant N进行CLMUL，分别得到CLMUL 0，CLMUL 1，CLMUL 2，……，CLMUL N。

[0062] d)将每段CLMUL的结果进行CRC编码，分别得到C0，C1，C2，……，CN。

[0063] e)将C0，C1，C2，……，CN进行异或(Exclusive OR,XOR)运算，得到最终的CRC编码结果CRC F。

[0064] 然而，该CRC编码方法中的步骤b和d中的CRC编码操作需要大量的移位操作和异或运算，增加了计算的复杂度，需要消耗大量的计算资原，从而影响了CRC编码的效率与性能。

[0065] 针对该问题，本申请提出一种计算CRC编码的方法，该方法使用本原多项式的倍式对待编码的数据进行编码，获得中间序列，对该中间序列使用本原多项式计算其CRC编码，该方法能够减少CRC编码时需要的移位操作与异或运算的次数，从而降低计算CRC编码的复杂度，提高CRC编码的效率和性能。

[0066] 为更好的理解本申请实施例，首先本申请实施例结合图1所示的存储系统介绍CRC编码的基本原理是：控制器101接收数据后，例如K位数据，将K位数据作为信息序列，在K位信息序列后再拼接N位的校验码，整个编码长度为R位。因此，这种编码也叫(R，K)码。对于一个给定的(R，K)码，可以证明存在一个最高次幂为R-K＝N的多项式G(x)，根据G(x)可以生成K位序列的CRC编码，而G(x)叫做这个CRC编码的生成多项式。N位校验码的具体生成过程为：假设要存储的数据称为信息序列，一个信息序列可以用多项式C(X)表示，将C(x)左移N位(可表示成C(x)*X^N)，这样C(x)的右边就会空出N位，这就是CRC编码的位置。本申请实施例基于用C(x)*X^N和生成多项式G(x)得到校验码，即用C(x)*X^N除以G(x)得到的余数作为N位CRC编码。其中，任意一个由二进制位串组成的数据都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：数据为1010111对应的多项式为X^6+X^4+X^2+X+1，其中，X^6表示X的6次幂或x的6次方，x为伪变量，幂指数(也称为指数)用于指示各位间的排列位置，“+”表示异或。多项式为X^5+X^3+X^2+X+1对应的数据为101111。在T10技术委员会制定的CRC16的本源多项式为0x18BB7，写成二进制为0001 1000 1011 1011 0111，对应的多项式为X^16+X^15+X^11+X^9+X^8+X^7+X^5+X^4+X^2+X^1+1。按照现有的CRC16编码方法，需要将信息序列划分为大小为16位的数据段，信息序列划分出来的数据段从最高位(从左到右)分别为第1数据段、第2数据段、……、第N数据段。其中，N为不小于2的自然数。首先，第1数据段要分别左移15位，左移11位，左移9位，左移8位，左移7位t，左移5位，左移4位，左移2位，左移1位，左移0位，将第1数据段进行上述移位后的得到的数据段进行异或，将异或结果与第2数据段进行异或得到的异或结果，再与第3数据段及第N数据段重新构成数据序列，然后将新的数据序列按照16位划分得到新的数据段，再执行上述移位及异或操作，直到最后信息序列长度等于16位。

[0067] 因此，得到如下公式(1)CRC(C(x))＝(xdeg(G(x))C(x))(mod(G(x))；其中，CRC(C(x))表示信息序列C(x)的CRC编码；G(x)表示本原多项式，如T10的CRC16的本原多项式为X^16+X^15+X^11+X^9+X^8+X^7+X^5+X^4+X^2+X^1+1；deg(G(x))表示本原多项式的最高项的指数，如T10的CRC16的本原多项式的最高项的指数为16，即最高位的指数；xdeg(G(x))C(x)表示将信息序列C(x)左移本原多项式的最高项的指数位，mod表示取模。

[0068] 结合公式(1),令Q(x)＝G(x)T(x)，则CRC(C(x))＝R(x)(mod(G(x)))；其中，R(x)＝(xdeg(G(x))C(x))(mod(Q(x)))，Q(x)表示G(x)的倍式，T(x)表示某一个多项式，用于表示Q(x)是G(x)的倍式，R(x)表示信息序列C(x)左移16bit得到的多项式除以Q(x)的余数。其中，Q(x)所含的有效的最高项的指数和有效的次最高项的指数之差大于1，从而相对G(x)可以减少循环移位操作次数，进一步的，可以选择含有效的项数的个数少的Q(x)可以进一步减少异或运算的次数，从而大幅降低了CRC编码复杂度，例如选择有效的项数最少的倍式。本申请实施例中，多项式的有效项是指系数为1的项，例如，如T10的CRC16的本原多项式中X^16、X^15、X^11、X^9、X^8、X^7、X^5、X^4、X^2、X^1、1的系数均为1，为有效的项。

[0069] 下面，结合图6至图11对本申请实施例提供的计算CRC编码的方法进行说明。

[0070] 图6为本申请实施例提供的计算CRC编码的方法600的示意性流程图。该方法600可以由图1和图2中的控制器或图4和图5中的服务器的处理器执行。该方法至少包括以下步骤。

[0071] 601，获取待编码的第一序列。

[0072] 具体地，控制器或服务器的处理器获取待编码的数据(例如，待编码的第一序列)。

[0073] 作为一种可选的实现方式，控制器或服务器的处理器接收主机或客户端发送的待编码的第一序列，进而计算该待编码的第一序列的CRC编码。

[0074] 602，使用至少一个多项式对待编码的第一序列进行编码，生成第二序列，该至少一个多项式中的每个多项式为本原多项式的倍式。

[0075] 下面以该本原多项式为T10的CRC16的本原多项式为例对本申请实施例的计算CRC编码的方法进行说明。

[0076] 具体地，对获取的待编码的第一序列使用至少一个多项式进行编码，生成中间序列(例如，第二序列)，其中，该至少一个多项式为本原多项式的倍式。

[0077] 例如，将待编码的第一序列使用多项式C(x)进行表示，将至少一个多项式记为Q(x)，将本原多项式记为G(x)，Q(x)为G(x)的倍式，即Q(x)＝G(x)T(x)，T(x)表示某一个多项式，用于表示Q(x)是G(x)的倍式，即，通过C(x)对Q(x)进行取模，将取模获得的余数(即，中间序列)表示为多项式R(x)，则R(x)＝(xdeg(G(x))C(x))(mod(Q(x)))。

[0078] 603，使用本原多项式对该第二序列进行编码，生成针对第一序列的校验序列，该至少一个多项式中每个多项式的项数少于该本原多项式的项数。

[0079] 具体地，对601中生成的第二序列使用本原多项式进行编码，生成针对第一序列的校验序列，其中，该至少一个多项式中每个多项式的项数少于该本原多项式的项数。

[0080] 例如，使用第二序列对应的多项式R(x)对本原多项式G(x)进行取摸，取模获得的余数为针对该待编码的第一序列生成的校验序列，该校验序列即为针对该第一序列计算的CRC编码，将针对该第一序列计算的CRC编码记为CRC(C(x))，则CRC(C(x))＝R(x)(mod(G(x)))。

[0081] 因此，在使用本原多项式计算待编码的数据(例如，第一序列)的CRC编码之前，通过本原多项式的至少一个倍式计算待编码的数据的CRC编码，获得中间序列(例如，第二序列)，再对该中间序列使用本原多项式计算该中间序列的CRC编码，从而避免仅使用本原多项式计算待编码的数据的CRC编码时，由于循环移位操作与异或运算的次数较多导致的CRC编码的计算复杂度较高的问题。

[0082] 下面同样以本原多项式为T10的CRC16的本原多项式为例对计算待编码数据的CRC编码的几个实施例进行说明。

[0083] 实施例1

[0084] 作为示例而非限定，该至少一个多项式包括第一多项式，该第一多项式Q1(x)满足：

[0085] Q1(x)＝(x^369+x^31+1)·x^a   (2)

[0086] 其中，x^a为调整系数，a是根据寄存器的容量确定的，且a为大于或等于0的整数，该寄存器用于存储该第一序列。

[0087] 具体地，例如，该第一序列的长度为4096，该本原多项式的倍式(例如，第一多项式)Q1(x)满足：

[0088] Q1(x)＝(x^369+x^31+1)   (3)

[0089] 此时，式(2)中的a的取值为0。

[0090] 在计算该第一序列的CRC编码时，主要包括以下步骤：

[0091] a，在计算该第一序列的CRC编码时，在该第一序列后补入16个的比特“0”，即，补“0”后的第一序列的长度为4112；

[0092] b，将补“0”后的第一序列划分为多个数据段，如图7所示，划分得到的数据段从最高位(从左至右)开始分别为：第1数据段、第2数据段、第3数据段…第11数据段、第12数据段，其中，第1数据段至第11数据段中每个数据段均包含369比特的数据，第12数据段包含53比特的数据，该53比特的数据中包含补入的16个取值为0的比特；

[0093] c，如图8所示，将第1数据段分别左移31位、左移0位，将第1数据段左移31位得到的数据段与左移0位得到的数据段进行异或运算，将异或运算得到的数据段A与第2数据段进行异或运算，再将数据段A与第2数据段进行异或运算后得到的数据段B与第3数据段至第12数据段重新构造新的数据序列；

[0094] d，对该重新构造的数据序列重复步骤b、c，生成第二序列；

[0095] 可选地，该第二序列的长度可以为394；

[0096] e，对该长度为394的第二序列使用T10的CRC16的本原多项式计算CRC编码，最终得到针对第一序列的CRC编码。

[0097] 关于使用T10的CRC16的本原多项式计算CRC编码的方法请参照上述相关描述，为了简洁，此处不再赘述。

[0098] 在实施例1中，式(2)中的xa为调整系数，在计算待编码序列的CRC编码时，可以根据用于存储该第一序列的寄存器的容量，通过该调整系数xa对本原多项式的倍式进行调整。

[0099] 例如，当寄存器的容量为128比特时，对于第一序列而言，为了使得对第一序列划分得到的某一个数据段占用完整的3个容量为128比特的寄存器，通过调整系数x15对该式(3)进行调整，调整后的本原多项式的倍式满足：

[0100] Q1(x)＝(x^369+x^31+1)·x^15＝x^384+x^46+x^15   (4)

[0101] 通过调整系数对该本原多项式的倍式进行调整(例如，经过调整，使得根据本原多项式的倍式对第一序列划分后获得的每个数据段均能够占满整数个寄存器)，使得利用调整后的本原多项式的倍式计算第一序列的CRC编码时能够充分利用寄存器的硬件资源。

[0102] 实施例2

[0103] 实施例2与实施例1的不同之处在于步骤c至步骤e，在实施例2中，步骤c为：

[0104] 如图9所示，将第1数据段分别左移31位、左移0位，将第1数据段左移31位得到的数据段与左移0位得到的数据段进行异或运算，将异或运算得到的数据段分为两部分，分别为数据段C与数据段D，数据段C包含高位的31比特，数据段D包含处高位的31比特外的369比特。

[0105] 将数据段C分别左移31位、左移0位，将左移31位得到的数据段与左移0位得到的数据段进行异或运算，并将该异或运算得到的数据段E与数据段D和第2数据段进行异或运算后得到的数据段F进行异或运算，将该异或运算得到的数据段G与第3数据段至第12数据段重新构造新的数据序列。

[0106] 在实施例2中，步骤d为：

[0107] 对该重新构造的数据序列重复实施例1中的步骤b与实施例2中的步骤c，生成第二序列。

[0108] 可选地，该第二序列的长度为369+53＝422。

[0109] 在实施例2中，步骤e为：

[0110] 对该长度为422的第二序列使用T10的CRC16的本原多项式计算CRC编码，最终得到针对第一序列的CRC编码。

[0111] 关于使用T10的CRC16的本原多项式计算CRC编码的方法请参照上述相关描述，为了简洁，此处不再赘述。

[0112] 实施例3

[0113] 作为示例而非限定，该至少一个多项式包括第二多项式，该第二多项式Q2(x)满足：

[0114] Q2(x)＝(x65535+1)·xb   (5)

[0115] 其中，xb为调整系数，b是根据寄存器的容量确定的，且b为大于或等于0的整数，该寄存器用于存储该第一序列。

[0116] 具体地，例如，该第一序列的长度为4194304，该本原多项式的倍式(例如，第一多项式)Q1(x)满足：

[0117] Q2(x)＝(x65535+1)   (6)

[0118] 此时，式(5)中的b的取值为0。

[0119] 在计算该第一序列的CRC编码时，主要包括以下步骤：

[0120] a，在计算该第一序列的CRC编码时，在该第一序列后补入16个的比特“0”，即，补“0”后的第一序列的长度为4194320；

[0121] b，将补“0”后的第一序列划分为多个数据段，如图10所示，划分得到的数据段从最高位(从左至右)开始分别为：第1数据段、第2数据段、第3数据段…第64数据段、第65数据段，其中，第1数据段至第64数据段中每个数据段均包含65536比特的数据，第65数据段包含80比特的数据，该80比特的数据中包含补入的16个取值为0的比特；

[0122] c，如图11所示，将第1数据段与第2数据段进行异或运算，将异或运算得到的数据段H与第3数据段值第65数据段重新构造新的数据序列；

[0123] d，对该新的数据序列重复步骤b、c，生成第二序列；

[0124] 可选地，该第二序列的长度可以为65535+80＝65615；

[0125] e，对该长度为65615的第二序列使用T10的CRC16的本原多项式计算CRC编码，最终得到针对第一序列的CRC编码。

[0126] 关于使用T10的CRC16的本原多项式计算CRC编码的方法请参照上述相关描述，为了简洁，此处不再赘述。

[0127] 在实施例3中，式(5)中的xb为调整系数，在计算待编码序列的CRC编码时，可以根据用于存储该第一序列的寄存器的容量，通过该调整系数xb对本原多项式的倍式进行调整。

[0128] 在实施例3中，作为另一种可选的实现方式，对待编码的第一序列使用至少一个多项式进行编码，生成第二序列，包括：对该待编码的第一序列使用该第二多项式进行编码，生成第三序列；对该第三序列使用该第一多项式进行编码，生成该第二序列。

[0129] 具体地，对于待编码的第一序列，在使用本原多项式对该第一序列编码之前，使用两个该本原多项式的倍式(例如，第一多项式与第二多项式)对该第一序列进行编码。

[0130] 例如，在实施例3中，再使用第二多项式(式6)对该第一序列进行编码后，生成长度为65615的数据序列，再使用第一多项式(式3)对该长度为65615的数据序列进行编码，生成该第二序列，最终对该第二序列使用T10的CRC16的本原多项式计算CRC编码，最终得到针对第一序列的CRC编码。

[0131] 关于使用式(3)对长度为65615的数据序列进行编码，生成该第二序列的先关描述请参照实施例1与实施例2中的相关描述，为了简洁，此处不再赘述。

[0132] 需要说明的式，上述图8、图9与图11中的“+”代表异或运算。

[0133] 需要说明的是，实施例3仅以使用两个该本原多项式的倍式对该第一序列进行编码，生成第二序列为例进行说明，但本申请并不限定于此。例如，还可以使用三个或三个以上的本原多项式的倍式对该第一序列进行编码，生成第二序列。

[0134] 还需要说明的是，实施例1至实施例3中列举的本原多项式的倍式仅为示例性说明，并不对本申请构成任何限定。例如，在对实施例1中的长度为4096的第一序列编码时，使用的本原多项式的倍式除实施例1中列举的式(3)外，还可以为其他形式的本原多项式的倍式。

[0135] 本申请还提供了一种确定本原多项式的倍式的方法，下面对该方法进行详细说明。

[0136] 假定本原多项式的倍式满足：

[0137] Q(x)＝x^i+x^j   (7)

[0138] 其中，j为大于或等于0的整数，且j＜i。

[0139] 对于式(7)，确定了i、j的取值，即确定了本原多项式的倍式。该方法具体为：

[0140] a，将长度为n的序列中的每个比特取值初始化为0，例如，n的取值可以为524288；

[0141] b，对于长度为n的序列，设置该序列中的索引号为i与索引号为j的比特的取值为1，其余比特的取值为0，其中，1≤i≤n-1，0≤j＜i，对于i的每个取值，j均需要从0遍历到i-
1；

[0142] c，使用本原多项式(例如，T10的CRC16的本原多项式)计算步骤b中获得的长度为n的序列的CRC编码；

[0143] d，若步骤c中计算获得的该长度为n的序列的CRC编码结果为0，则步骤b中的索引号i与索引号j分别为该本原多项式的倍式(式7)的最高项的指数与次高项的指数。

[0144] 例如，对于该长度为n的序列，设置该序列中的索引号为200与索引号为50的比特的取值为1，其余比特的取值被设置为0，当使用本原多项式计算该序列的CRC编码的结果为0时，说明该长度为n的序列对应的多项式为该本原多项式的倍式，该索引号200与该索引号
50分别为该倍式的最高项的指数与次高项的指数，即该本原多项式的倍式满足：

[0145] Q(x)＝(x^200+x^50)   (8)

[0146] 对于本原多项式而言，根据上述方法能够确定多个该本原多项式的倍式，对于待编码的第一序列，需要从该本原多项式的多个倍式中确定用于计算该第一序列的CRC编码的倍式。

[0147] 作为示例而非限定，可以根据该第一序列的长度，从该本原多项式的多个倍式中确定用于计算该第一序列的CRC编码的倍式。

[0148] 例如，当该第一序列的长度为4096时，从该本原多项式的多个倍式中将式3确定为用于计算该第一序列的CRC编码的倍式。

[0149] 此外，在确定用于计算该第一序列的CRC编码的倍式时，还可以进一步遵循以下原则：

[0150] 本原多项式的倍式的有效项的项数尽可能少，和/或本原多项式的倍式的最高项的指数与次高项的指数的差值尽可能大。

[0151] 需要说明的是，上述仅以本原多项式的倍式满足式7为例进行说明，但本申请并不限定于此，例如，本原多项式的倍式还可以满足：

[0152] Q(x)＝x^i+x^j+x^k   (9)

[0153] 其中，k为大于或等于0的整数，且k＜j＜i。

[0154] 还需要说明的是，本申请仅以本原多项式为T10的CRC16的本原多项式为例对本申请的计算CRC编码的方法进行说明，但本申请提供的计算CRC编码的方法并不限定于此。例如，本申请提供的计算CRC编码的方法还可以适用于使用基于其他标准制定的本原多项式计算待编码序列的CRC编码的方法中。

[0155] 上文结合图6至图11，描述了本申请实施例提供的计算CRC编码的方法，下面结合图12至图13描述本申请实施例提供的计算CRC编码的装置。

[0156] 图12为本申请实施例提供的计算CRC编码的装置700的示意性框图，该计算CRC编码的装置包括获取模块701与处理模块702。

[0157] 获取模块701，用于获取待编码的第一序列。

[0158] 处理模块702，用于使用至少一个多项式对该待编码的第一序列进行编码，生成第二序列。

[0159] 该处理模块702还用于，使用本原多项式对该第二序列进行编码，生成针对第一序列的校验序列，该至少一个多项中每个多项式为该本原多项式的倍式，该至少一个多项式中每个多项式的项数少于该本原多项式的项数。

[0160] 可选地，该至少一个多项式包括第一多项式，该第一多项式Q1(x)满足：

[0161] Q1(x)＝(x369+x31+1)·xa

[0162] 其中，xa为调整系数，a是根据寄存器的容量确定的，且a为大于或等于0的整数，该寄存器用于存储该第一序列。

[0163] 可选地，该至少一个多项式包括第二多项式，该第二多项式Q2(x)满足：

[0164] Q2(x)＝(x65535+1)·xb

[0165] 其中，xb为调整系数，b是根据寄存器的容量确定的，且b为大于或等于0的整数，该寄存器用于存储该第一序列。

[0166] 可选地，该处理模块702还用于，对该待编码的第一序列使用该第二多项式进行编码，生成第三序列；对该第三序列使用该第一多项式进行编码，生成该第二序列。

[0167] 可选地，该处理模块702还用于，根据该第一序列的长度，确定该至少一个多项式。

[0168] 可选地，该第一序列的长度为4096。

[0169] 可选地，该第二序列的长度为394或422。

[0170] 可选地，该第一序列的长度为4194304。

[0171] 图13为本申请实施例提供的计算CRC编码的装置800的示意性框图，该计算CRC编码的装置包括接口801、存储器802与处理器803。

[0172] 接口801，用于获取待编码的第一序列。

[0173] 存储器802，用于存储程序。

[0174] 处理器803，用于执行该存储器中存储的程序，当该存储器中的程序被执行时，该处理器803用于，通过该接口801获取待编码的第一序列；使用至少一个多项式对该待编码的第一序列进行编码，生成第二序列；使用本原多项式对该第二序列进行编码，生成针对第一序列的校验序列，该至少一个多项中每个多项式为该本原多项式的倍式，该至少一个多项式中每个多项式的项数少于该本原多项式的项数。

[0175] 可选地，该至少一个多项式包括第一多项式，该第一多项式Q1(x)满足：

[0176] Q1(x)＝(x369+x31+1)·xa

[0177] 其中，xa为调整系数，a是根据寄存器的容量确定的，且a为大于或等于0的整数，该寄存器用于存储该第一序列。

[0178] 可选地，该至少一个多项式包括第二多项式，该第二多项式Q2(x)满足：

[0179] Q2(x)＝(x65535+1)·xb

[0180] 其中，xb为调整系数，b是根据寄存器的容量确定的，且b为大于或等于0的整数，该寄存器用于存储该第一序列。

[0181] 可选地，该处理器803还用于，对该待编码的第一序列使用该第二多项式进行编码，生成第三序列；对该第三序列使用该第一多项式进行编码，生成该第二序列。

[0182] 可选地，该处理器803还用于，根据该第一序列的长度，确定该至少一个多项式。

[0183] 可选地，该第一序列的长度为4096。

[0184] 可选地，该第二序列的长度为394或422。

[0185] 可选地，该第一序列的长度为4194304。

[0186] 本申请提供了一种芯片，该芯片包括接口、存储器和处理器，该存储器用于存储指令，该处理器用于执行该存储器存储的指令，并且对该存储器中存储的指令的执行使得该处理器执行本申请实施例的计算CRC编码的方法。

[0187] 本申请提供了一种计算机可读存储介质，该计算机可读存储介质中存储有指令，当该指令在计算机上运行时，使得计算机执行本申请实施例的计算CRC编码的方法。

[0188] 本申请提供了一种包含指令的计算机程序产品，当该计算机程序产品在计算机上运行时，使得计算机执行本申请实施例的计算CRC编码的方法。

[0189] 应理解，本申请实施例中提及的处理器可以是中央处理单元(Central Processing Unit，CPU)，还可以是其他通用处理器、数字信号处理器(Digital Signal Processor，DSP)、专用集成电路(Application Specific Integrated Circuit，ASIC)、现成可编程门阵列(Field Programmable Gate Array，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。

[0190] 还应理解，本申请实施例中提及的存储器可以是易失性存储器或非易失性存储器，或可包括易失性和非易失性存储器两者。其中，非易失性存储器可以是只读存储器(Read-Only Memory，ROM)、可编程只读存储器(Programmable ROM，PROM)、可擦除可编程只读存储器(Erasable PROM，EPROM)、电可擦除可编程只读存储器(Electrically EPROM，EEPROM)或闪存。易失性存储器可以是随机存取存储器(Random Access Memory，RAM)，其用作外部高速缓存。通过示例性但不是限制性说明，许多形式的RAM可用，例如静态随机存取存储器(Static RAM，SRAM)、动态随机存取存储器(Dynamic RAM，DRAM)、同步动态随机存取存储器(Synchronous DRAM，SDRAM)、双倍数据速率同步动态随机存取存储器(Double Data Rate SDRAM，DDR SDRAM)、增强型同步动态随机存取存储器(Enhanced SDRAM，ESDRAM)、同步连接动态随机存取存储器(Synchlink DRAM，SLDRAM)和直接内存总线随机存取存储器(Direct Rambus RAM，DR RAM)。

[0191] 需要说明的是，当处理器为通用处理器、DSP、ASIC、FPGA或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件时，存储器(存储模块)集成在处理器中。

[0192] 应注意，本文描述的存储器旨在包括但不限于这些和任意其它适合类型的存储器。

[0193] 本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本申请的范围。

[0194] 所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统、装置和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

[0195] 在本申请所提供的几个实施例中，应该理解到，所揭露的系统、装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

[0196] 所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

[0197] 另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。

[0198] 所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本申请各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(Read-Only Memory，ROM)、随机存取存储器(Random Access Memory，RAM)、磁碟或者光盘等各种可以存储程序代码的介质。

[0199] 以上所述，仅为本申请的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应以所述权利要求的保护范围为准。