一种并行CRC校验码的计算方法及系统

摘要

本申请公开了一种并行CRC校验码的计算方法及系统，其中，所述并行CRC校验码的计算方法采用了参数化的方法，实现了根据需要改变并行度和生成多项式，从而提高所述并行CRC校验码的计算方法的可移植性的目的，并且所述并行CRC校验码采用移位操作和异或运算提到了传统并行CRC校验码计算方法中矩阵高次幂的求解，减少了运算量，在算法层上比直接计算减少了大约75％的计算时间。

说明书

本申请要求于2017年2月20日提交中国专利局、申请号为201710089849.4、 发明名称为“一种并行CRC校验码的计算方法及系统”的中国专利申请的优 先权，其全部内容通过引用结合在本申请中。

技术领域

本申请涉及通信技术领域，更具体地说，涉及一种并行CRC校验码的计 算方法及系统。

背景技术

在数据通信过程中，为了解决数据通信中的错误检测问题，一般在将要 传输的信息码之后添加一定位数的校验码以实现检错过程。在众多的校验方 法中，循环冗余检查(Cyclic Redundancy Check,CRC)校验由于其优秀的错 误检测能力，被广泛应用于数据通信技术领域。

CRC校验的基本思想是在要发送的信息码之后附加一个二进制序列的 CRC校验码，生成一个新的信息码发送给接收端。其中，CRC校验码需要能 够使生成的新的信息码能与发送端和接收端共同选定的某个特定数整除，这 个特定数由生成CRC校验码的生成多项式确定，在新的信息码到达接收端后， 接收端对接收到的新的信息码采用“模2除法”除以这个特定数，如果结果没 有余数，则说明新的信息码没有出现错误，如果结果有余数，则说明该信息 码在传输过程中出现了错误。

CRC校验码的计算分为串行和并行两种方式，串行CRC校验码的计算方 法每次只能计算一位待生成数据；而并行CRC校验码的计算方法具有一个并 行度的参数，每次可以计算并行度位数的待生成数据。在实际的应用过程中， 为了提高计算效率通常采用并行CRC校验码的计算方法进行CRC校验码的计 算。但在现有技术中，并行CRC校验码的计算方法通常为查表法，即根据特 定的并行度生成特定的校验码表格以进行查表获得，这种方法在当并行度改 变时，又需要生成新的校验码，可移植性低，无法根据需要改变并行度和生成多项式。

发明内容

为解决上述技术问题，本发明提供了一种并行CRC校验码的计算方法及 系统，以实现提高并行CRC校验码的计算方法的可移植性的目的。

为实现上述技术目的，本发明实施例提供了如下技术方案：

一种并行CRC校验码的计算方法，用于计算待生成数据 data＝[d_k-1d_k-2d_k-3…d₀]的CRC校验码，所述并行CRC校验码的计算方法包括：

S101：获取生成多项式poly＝[p_n-1p_n-2p_n-3…p₀]和并行度w；

S102：利用所述生成多项式生成第一临时矩阵temp；其中，

S103：利用所述生成多项式生成第二临时矩阵

S104：利用所述待生成数据中未处理数据的前w位生成中间系数向量

S105：将所述中间系数向量与所述第一临时矩阵按列作与运算，获得第 一中间矩阵

S106：将所述第一中间矩阵的列向量按列依次进行缩减异或运算，获得 第二中间矩阵factor＝[f_n-1f_n-2f_n-3…f₀]；

S107：将所述第二中间矩阵按位依次与所述第二临时矩阵中的列向量作 与运算，获得第三中间矩阵

S108：将所述第三中间矩阵的所有列作按位异或运算，获得校验向量判断所述待生成数据中未处理数据是否为零，如果是， 则将所述校验向量作为所述待生成数据的CRC校验码；如果否，则利用所述 校验向量更新所述中间系数向量的前n行，利用所述待生成数据中未处理数 据的前w位更新所述中间系数向量的后w行，并返回将所述中间系数向量与 所述第一临时矩阵按列作与运算，获得第一中间矩阵的步骤。

可选的，步骤S108包括：

将所述第三中间矩阵的所有列作按位异或运算，获得校验向量判断所述待生成数据中未处理数据是否为零，如果是， 则将所述校验向量作为所述待生成数据的CRC校验码；如果否，则判断所述 待生成数据中未处理数据的位数是否小于或等于所述并行度，若否，则返回 将所述中间系数向量与所述第一临时矩阵按列作与运算，获得第一中间矩阵 的步骤，若是，则利用所述待生成数据中未处理数据和所述校验向量对所述 中间系数向量进行修正，并返回将所述中间系数向量与所述第一临时矩阵按 列作与运算，获得第一中间矩阵的步骤。

可选的，所述利用所述待生成数据中未处理数据和所述校验向量对所述 中间系数向量进行修正包括：

将所述待生成数据中未处理数据倒序赋予所述中间系数向量的最后M 行，M的取值与所述待生成数据中未处理数据的位数相同；

将所述校验向量中的数据赋予所述中间系数向量的倒数M+1至倒数M+n 行；

将所述中间系数向量的前w-M行用零填充。

可选的，所述获取生成多项式poly＝[p_n-1p_n-2p_n-3…p₀]和并行度w之后，所>

S1012：判断获取的并行度是否大于所述待生成数据位数与所述生成多项 式位数的和，如果是，则将所述待生成数据位数与所述生成多项式位数的和 作为所述并行度；如果否，则判断获取的并行度是否小于1，若是，则将1作 为所述并行度。

一种并行CRC校验码的计算系统，用于计算待生成数据 data＝[d_k-1d_k-2d_k-3…d₀]的CRC校验码，所述并行CRC校验码的计算系统包括：

获取模块，用于获取生成多项式poly＝[p_n-1p_n-2p_n-3…p₀]和并行度w；

第一临时矩阵生成模块，用于利用所述生成多项式生成第一临时矩阵 temp；其中，

第二临时矩阵生成模块，用于利用所述生成多项式生成第二临时矩阵

中间系数向量生成模块，用于利用所述待生成数据中未处理数据的前w 位生成中间系数向量

第一中间矩阵生成模块，用于将所述中间系数向量与所述第一临时矩阵 按列作与运算，获得第一中间矩阵

第二中间矩阵生成模块，用于将所述第一中间矩阵的列向量按列依次进 行缩减异或运算，获得第二中间矩阵factor＝[f_n-1f_n-2f_n-3…f₀]；

第三中间矩阵生成模块，用于将所述第二中间矩阵按位依次与所述第二 临时矩阵中的列向量作与运算，获得第三中间矩阵

校验向量生成模块，用于将所述第三中间矩阵的所有列作按位异或运算， 获得校验向量判断所述待生成数据中未处理数据是否为 零，如果是，则将所述校验向量作为所述待生成数据的CRC校验码；如果否， 则利用所述校验向量更新所述中间系数向量的前n行，利用所述待生成数据 中未处理数据的前w位更新所述中间系数向量的后w行，并返回所述第一中 间矩阵生成模块。

可选的，所述校验向量生成模块具体用于将所述第三中间矩阵的所有列 作按位异或运算，获得校验向量判断所述待生成数据中 未处理数据是否为零，如果是，则将所述校验向量作为所述待生成数据的CRC 校验码；如果否，则判断所述待生成数据中未处理数据的位数是否小于或等 于所述并行度，若否，则返回所述第一中间矩阵生成模块，若是，则利用所 述待生成数据中未处理数据和所述校验向量对所述中间系数向量进行修正， 并返回所述第一中间矩阵生成模块。

可选的，所述校验向量生成模块利用所述待生成数据中未处理数据和所 述校验向量对所述中间系数向量进行修正具体用于将所述待生成数据中未处 理数据倒序赋予所述中间系数向量的最后M行，M的取值与所述待生成数据 中未处理数据的位数相同；

将所述校验向量中的数据赋予所述中间系数向量的倒数M+1至倒数M+n 行；

将所述中间系数向量的前w-M行用零填充。

可选的，还包括：

并行度修正模块，用于判断获取的并行度是否大于所述待生成数据位数 与所述生成多项式位数的和，如果是，则将所述待生成数据位数与所述生成 多项式位数的和作为所述并行度；如果否，则判断获取的并行度是否小于1， 若是，则将1作为所述并行度。

从上述技术方案可以看出，本发明实施例提供了一种并行CRC校验码的 计算方法及系统，其中，所述并行CRC校验码的计算方法采用了参数化的方 法，实现了根据需要改变并行度和生成多项式，从而提高所述并行CRC校验 码的计算方法的可移植性的目的，并且所述并行CRC校验码采用移位操作和 异或运算提到了传统并行CRC校验码计算方法中矩阵高次幂的求解，减少了 运算量，在算法层上比直接计算减少了大约75％的计算时间。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实 施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面 描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不 付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。

图1为本申请的一个实施例提供的一种并行CRC校验码的计算方法的流 程示意图；

图2为本申请的一个实施例提供的一种并行CRC校验码的计算系统的结 构示意图；

图3为本申请的另一个实施例提供的一种并行CRC校验码的计算系统的 结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行 清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而 不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做 出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本申请实施例提供了一种并行CRC校验码的计算方法，如图1所示，用于 计算待生成数据data＝[d_k-1d_k-2d_k-3…d₀]的CRC校验码，所述并行CRC校验码的计>

S101：获取生成多项式poly＝[p_n-1p_n-2p_n-3…p₀]和并行度w；

S102：利用所述生成多项式生成第一临时矩阵temp；其中，

具体地，所述第一临时矩阵生成方法为将最后一行左边第一个数值设置 为1，该行之后的数值为生成多项式的高(n-1)位(即生成多项式的前n-1 个系数的二进制表示)；所述第一临时矩阵其他行的生成方法为：将其后一 行(例如：对于倒数第二行而言，其后一行为倒数第一行)的左边第一位数 与生成多项式的高(n-1)位按位作与运算，将此结果与其后一行除去左边第 一位的n-1位数据作按位异或运算，得到的结果就是该行从左起n-1位的数据， 该行最右边的一位数据是该行后一行数据最左边的一位数据。

S103：利用所述生成多项式生成第二临时矩阵

S104：利用所述待生成数据中未处理数据的前w位生成中间系数向量

S105：将所述中间系数向量与所述第一临时矩阵按列作与运算，获得第 一中间矩阵

需要说明的是，所述第一中间矩阵中，

S106：将所述第一中间矩阵的列向量按列依次进行缩减异或运算，获得 第二中间矩阵factor=[f_n-1f_n-2f_n-3…f₀]；

需要说明的是，所述第二中间矩阵中，

S107：将所述第二中间矩阵按位依次与所述第二临时矩阵中的列向量作 与运算，获得第三中间矩阵

S108：将所述第三中间矩阵的所有列作按位异或运算，获得校验向量判断所述待生成数据中未处理数据是否为零，如果是， 则将所述校验向量作为所述待生成数据的CRC校验码；如果否，则利用所述 校验向量更新所述中间系数向量的前n行，利用所述待生成数据中未处理数 据的前w位更新所述中间系数向量的后w行，并返回将所述中间系数向量与 所述第一临时矩阵按列作与运算，获得第一中间矩阵的步骤。

在所述校验向量中，

在上述实施例的基础上，在本申请的一个实施例中，所述获取生成多项 式poly＝[p_n-1p_n-2p_n-3…p₀]和并行度w之后，所述利用所述生成多项式生成第一>

S1012：判断获取的并行度是否大于所述待生成数据位数与所述生成多项 式位数的和，如果是，则将所述待生成数据位数与所述生成多项式位数的和 作为所述并行度；如果否，则判断获取的并行度是否小于1，若是，则将1作 为所述并行度。

在本实施例中，增加步骤S1012的目的是对输入异常的并行度进行修正， 以避免获取的并行度异常而可能造成的错误。

在上述实施例的基础上，在本申请的一个优选实施例中，步骤S108包括：

将所述第三中间矩阵的所有列作按位异或运算，获得校验向量判断所述待生成数据中未处理数据是否为零，如果是， 则将所述校验向量作为所述待生成数据的CRC校验码；如果否，则判断所述 待生成数据中未处理数据的位数是否小于或等于所述并行度，若否，则返回 将所述中间系数向量与所述第一临时矩阵按列作与运算，获得第一中间矩阵 的步骤，若是，则利用所述待生成数据中未处理数据和所述校验向量对所述 中间系数向量进行修正，并返回将所述中间系数向量与所述第一临时矩阵按 列作与运算，获得第一中间矩阵的步骤。

具体地，所述利用所述待生成数据中未处理数据和所述校验向量对所述 中间系数向量进行修正包括：

将所述待生成数据中未处理数据倒序赋予所述中间系数向量的最后M 行，M的取值与所述待生成数据中未处理数据的位数相同；

将所述校验向量中的数据赋予所述中间系数向量的倒数M+1至倒数M+n 行；

将所述中间系数向量的前w-M行用零填充。

需要说明的是，修正后的中间系数向量的形式如下式所示：

最后一次运算过程中获得的第三中间矩阵如下式所示：

最后一次运算过程中获得的校验向量如下式所示：

其中，

在上述实施例的基础上，在本申请的一个具体实施例中，以一个位长为7 的待生成数据1011001为例，对所述并行CRC校验码的计算方法进行检验，假 设生成多项式为，其对应的二进制码为1001(省略掉最高 位1)，真正要计算的是10110010000(在待生成数据之后补生成多项式位数 个0)。为体现本方法的特性，选择一个不能被整除的并行度7，因此需要计 算两次(待生成数据位7位，生成多项式4位，它们之和除以并行度7，结果向 上取整得2)。

第一次计算数据10110010000(在1011001之后补生成多项式位数个0)的 高7位：

(1)生成第一临时矩阵temp此矩阵最后一行为生成多项式对应代码1001 整体向右移一位后最高位置1，结果为1100。倒数第二行为1100的最高位与生 成多项式作与，结果为1001，此结果与1100向左循环移一位的结果1001的前 三位按位作异或运算，得到0001。倒数第三行为0001的最高位与生成多项式 作与，结果为0000，此结果与0001向左循环移一位的结果0010的前三位按位 作异或运算，得到0010。依次类推，直到得到一个11行4列的矩阵：

(2)构建第二临时矩阵

(3)构建中间系数向量h，起始时前4行为0，之后7行为待生成数据的高 7位：

(4)将h与temp按列作与运算，产生qand：

(5)将qand的列向量依次进行缩减异或，得到了4个结果值，获得 factor＝[1011]。

(6)将factor的每一位与F的每列依次作与运算，得到

(7)将sand的所有列按位异或，得到一个列向量就是数据10110010000 (在1011001之后补生成多项式位数个0)的前7位CRC的计算结果。

第二次计算数据10110010000(在1011001之后补生成多项式位数个0)的 低4位：

(8)修改h，将待生成数据中剩下的将要计算CRC码的数据赋值给列向 量的最后几行，然后将之前步骤算出的中间CRC结果添加到其上的行，最 后开始的行用零填充。

(9)将h与temp按列作与运算，产生qand。

(10)将qand的列向量依次进行缩减异或，得到了4个结果值，得到： factor＝[0101]

(11)将factor每一位与F每列依次作与运算，得到

(12)将sand所有列按位异或，得到一个列向量就是数据10110010000(在 1011001之后补生成多项式位数个0)的最终CRC的计算结果：

所以最后的计算结果是1010，即为待生成数据1011001的CRC校验码，把 这个值替换数据10110010000(在1011001之后补生成多项式位数个0)的后4 个0，得到10110011010，前七位是信息码，后四位是CRC校验码。

相应的，本申请实施例还提供了一种并行CRC校验码的计算系统，如图 2所示，用于计算待生成数据data＝[d_k-1d_k-2d_k-3…d₀]的CRC校验码，所述并行>

获取模块100，用于获取生成多项式poly＝[p_n-1p_n-2p_n-3…p₀]和并行度w；

第一临时矩阵生成模块200，用于利用所述生成多项式生成第一临时矩阵 temp；其中，

第二临时矩阵生成模块300，用于利用所述生成多项式生成第二临时矩阵

中间系数向量生成模块400，用于利用所述待生成数据中未处理数据的前 w位生成中间系数向量

第一中间矩阵生成模块500，用于将所述中间系数向量与所述第一临时矩 阵按列作与运算，获得第一中间矩阵

第二中间矩阵生成模块600，用于将所述第一中间矩阵的列向量按列依次 进行缩减异或运算，获得第二中间矩阵factor＝[f_n-1f_n-2f_n-3…f₀]；

第三中间矩阵生成模块700，用于将所述第二中间矩阵按位依次与所述第 二临时矩阵中的列向量作与运算，获得第三中间矩阵

校验向量生成模块800，用于将所述第三中间矩阵的所有列作按位异或运 算，获得校验向量判断所述待生成数据中未处理数据是 否为零，如果是，则将所述校验向量作为所述待生成数据的CRC校验码；如 果否，则利用所述校验向量更新所述中间系数向量的前n行，利用所述待生 成数据中未处理数据的前w位更新所述中间系数向量的后w行，并返回所述 第一中间矩阵生成模块500。

需要说明的是，所述第一临时矩阵生成方法为将最后一行左边第一个数 值设置为1，该行之后的数值为生成多项式的高(n-1)位(即生成多项式的 前n-1个系数的二进制表示)；所述第一临时矩阵其他行的生成方法为：将其 后一行(例如：对于倒数第二行而言，其后一行为倒数第一行)的左边第一 位数与生成多项式的高(n-1)位按位作与运算，将此结果与其后一行除去左 边第一位的n-1位数据作按位异或运算，得到的结果就是该行从左起n-1位的 数据，该行最右边的一位数据是该行后一行数据最左边的一位数据。

所述第一中间矩阵中，

所述第二中间矩阵中，

在所述校验向量中，

在上述实施例的基础上，在本申请的一个实施例中，如图3所示，所述CRC 校验码的计算系统还包括：

并行度修正模块900，用于判断获取的并行度是否大于所述待生成数据位 数与所述生成多项式位数的和，如果是，则将所述待生成数据位数与所述生 成多项式位数的和作为所述并行度；如果否，则判断获取的并行度是否小于1， 若是，则将1作为所述并行度。

在本实施例中，增加所述并行度修正模块900的目的是对输入异常的并 行度进行修正，以避免获取的并行度异常而可能造成的错误。

在上述实施例的基础上，在本申请的一个优选实施例中，所述校验向量 生成模块800具体用于将所述第三中间矩阵的所有列作按位异或运算，获得 校验向量判断所述待生成数据中未处理数据是否为零， 如果是，则将所述校验向量作为所述待生成数据的CRC校验码；如果否，则 判断所述待生成数据中未处理数据的位数是否小于或等于所述并行度，若否， 则返回所述第一中间矩阵生成模块500，若是，则利用所述待生成数据中未处 理数据和所述校验向量对所述中间系数向量进行修正，并返回所述第一中间 矩阵生成模块500。

具体地，所述校验向量生成模块800利用所述待生成数据中未处理数据 和所述校验向量对所述中间系数向量进行修正具体用于将所述待生成数据中 未处理数据倒序赋予所述中间系数向量的最后M行，M的取值与所述待生成 数据中未处理数据的位数相同；

将所述校验向量中的数据赋予所述中间系数向量的倒数M+1至倒数M+n 行；

将所述中间系数向量的前w-M行用零填充。

需要说明的是，修正后的中间系数向量的形式如下式所示：

最后一次运算过程中获得的第三中间矩阵如下式所示：

最后一次运算过程中获得的校验向量如下式所示：

其中，

在上述实施例的基础上，在本申请的一个具体实施例中，以一个位长为7 的待生成数据1011001为例，对所述并行CRC校验码的计算系统进行检验，假 设生成多项式为，其对应的二进制码为1001(省略掉最高 位1)，真正要计算的是10110010000(在待生成数据之后补生成多项式位数 个0)。为体现本方法的特性，选择一个不能被整除的并行度7，因此需要计 算两次(待生成数据位7位，生成多项式4位，它们之和除以并行度7，结果向 上取整得2)。

第一次计算数据10110010000(在1011001之后补生成多项式位数个0)的 高7位：

(1)生成第一临时矩阵temp此矩阵最后一行为生成多项式对应代码1001 整体向右移一位后最高位置1，结果为1100。倒数第二行为1100的最高位与生 成多项式作与，结果为1001，此结果与1100向左循环移一位的结果1001的前 三位按位作异或运算，得到0001。倒数第三行为0001的最高位与生成多项式 作与，结果为0000，此结果与0001向左循环移一位的结果0010的前三位按位 作异或运算，得到0010。依次类推，直到得到一个11行4列的矩阵：

(2)构建第二临时矩阵

(3)构建中间系数向量h，起始时前4行为0，之后7行为待生成数据的高 7位：

(4)将h与temp按列作与运算，产生qand：

(5)将qand的列向量依次进行缩减异或，得到了4个结果值，获得 factor＝[1011]。

(6)将factor的每一位与F的每列依次作与运算，得到

(7)将sand的所有列按位异或，得到一个列向量就是数据10110010000 (在1011001之后补生成多项式位数个0)的前7位CRC的计算结果。

第二次计算数据10110010000(在1011001之后补生成多项式位数个0)的 低4位：

(8)修改h，将待生成数据中剩下的将要计算CRC码的数据赋值给列向 量的最后几行，然后将之前步骤算出的中间CRC结果添加到其上的行，最 后开始的行用零填充。

(9)将h与temp按列作与运算，产生qand。

(10)将qand的列向量依次进行缩减异或，得到了4个结果值，得到： factor＝[0101]

(11)将factor每一位与F每列依次作与运算，得到

(12)将sand所有列按位异或，得到一个列向量就是数据10110010000(在 1011001之后补生成多项式位数个0)的最终CRC的计算结果：

所以最后的计算结果是1010，即为待生成数据1011001的CRC校验码，把 这个值替换数据10110010000(在1011001之后补生成多项式位数个0)的后4 个0，得到10110011010，前七位是信息码，后四位是CRC校验码。

综上所述，本申请实施例提供了一种并行CRC校验码的计算方法及系统， 其中，所述并行CRC校验码的计算方法采用了参数化的方法，实现了根据需 要改变并行度和生成多项式，从而提高所述并行CRC校验码的计算方法的可 移植性的目的，并且所述并行CRC校验码采用移位操作和异或运算提到了传 统并行CRC校验码计算方法中矩阵高次幂的求解，减少了运算量，在算法层 上比直接计算减少了大约75％的计算时间。

进一步的，本申请实施例提供的并行CRC校验码的计算方法可以实现任 意并行度的CRC校验码的生成和检验，消除了并行度的特定限制。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都 是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用 本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易 见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下， 在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例， 而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。