使用一组多项式来确定消息余式

摘要

描述了一种用于确定消息余式的方法。该方法包括：载入从第一多项式g(x)导出的一组多项式中的每一个的至少一部分，和使用一组级确定余式。所述级中的个别级将各个导出多项式级应用到前述一个级组中前一个级输出的数据。

说明书

技术领域

[0001]本发明涉及一种用于确定消息m(x)的余式的方法、装置和设备。

背景技术

[0002]例如，由于多种原因可能会损坏通过网络连接传输或从存储设备取回的数据。例如，有噪声的传输线可将“1”信号改变为“0”，或反之亦然。为了检测损坏，数据经常伴随有从该数据导出的一些值，如校验和。数据的接收机可重新计算校验和并与原始校验和相比较来确认数据可能无误传输。

[0003]识别数据损坏的常用技术被称为循环冗余校验(CRC)。虽然不是字面上的校验和，但是以非常相同的方式使用CRC值。即，原始计算的CRC与重新计算的CRC的比较可可以以非常高的概率识别数据损坏。CRC计算基于把消息比特解释为多项式，其中消息的每个比特代表一个多项式系数。例如，消息“1110”相应于多项式x³+x²+x+0。消息除以称为密钥的另一个多项式。例如，其它多项式可能是“11”或x+1。CRC是消息除以密钥的余数。但是，CRC多项式除法稍微不同于普通的除法，因为它在有限域GF(2)(即，模2的整数集)计算。更简单提出：偶数系数变成零且奇数系数变成一。

[0004]已开发了多种技术来执行CRC计算。第一种技术使用专用CRC电路来实现特定多项式密钥。这个方法可产生具有很小面积(footprint)的速度很快的电路。但是考虑到使用的多项式密钥，速度和大小经常以不灵活为代价实现。另外，支持多个密钥可几乎线性地增加支持的每个密钥的电路面积。

[0005]第二种常用技术特征是CRC查找表，在该表中对于给定的多项式以及数据输入和余数的组，计算和存储了所有可能的CRC结果。确定CRC成为执行表格查找的简单方式。但是，这个方法一般具有相对大的电路面积且可需要完全重新填充查找表，来改变正使用的多项式密钥。

[0006]第三种技术是可编程CRC电路。这几乎允许在合理有效的芯片面积(die area)数量内支持任何多项式。不幸的是，这个方法比上述方法的性能低得多。

发明内容

[0007]根据本发明的一个方面，提供了用于确定消息m(x)的余式的方法，该方法包括：载入从第一多项式g(x)导出的一组多项式中的每一个的至少一部分；和使用一组级来确定相应于m(x)mod g(x)的消息余式，该组级中的个别级将该组多项式中相应一个的至少一部分应用到该组级中前一个级输出的数据。

[0008]根据本发明的另一个方面，提供了一种关于第一多项式g(x)在有限域GF(2)确定消息m的余式的装置，该装置包括：一组存储元件，存储从第一多项式g(x)导出的一组多项式中的每一个的至少一部分；和一组级，耦合到该组存储元件中相应的存储元件，该组级中相应的级包括数字逻辑门，将存储在该组存储元件中相应存储元件中的值应用到该级的相应输入。

[0009]根据本发明的另一个方面，提供了一种设备，包括：至少一个媒体接入控制器(MAC)，从网络接收消息；至少一个处理器，可通信地耦合到该至少一个媒体接入控制器；该设备包括关于第一多项式g(x)在有限域GF(2)确定消息的余式的电路，该电路包括：一组存储元件，存储从第一多项式g(x)导出的一组多项式；和一组级，耦合到该组存储元件中相应的存储元件，该组级中的相应级包括数字逻辑门，将存储在该组存储元件中相应存储元件中的值应用到相应级的相应输入。

附图说明

[0010]图1是示出了应用一组预先计算的多项式来确定多项式除法余式的一组级的示图。

[0011]图2是一组预先计算的多项式的示图。

[0012]图3是示出了对预先计算的多项式和输入数据执行并行操作的级的示图。

[0013]图4A和4B是采样级的数字逻辑门的示图。

[0014]图5是计算多项式除法余式的系统示图。

具体实施方式

[0015]图1示出了可编程循环冗余校验(CRC)电路100的采样实施方式。电路100可粗略地实现与查找表CRC实施方式一样的性能并且仅稍微比在典型多项式上操作的专用CRC电路实施方式慢。从芯片面积的观点，电路100可能是比查找表方法小的数量级且在专用电路实施方式的数量级内。

[0016]电路100使用一系列从多项式密钥导出的预先计算的多项式100a-100d。预先计算的多项式100a-100d的比特载入存储元件(如，寄存器或存储单元)并馈入一系列级106a-106d，在途中这些级依次将初始消息减少到较小的中间值，从而在级106d输出最终CRC结果。例如，如所示出的，级106a-106d输出的数据宽度r_b-r_d随着每个连续的级而减小。构建预先计算的多项式100a-100d和级106d-106a，以使得关于最终的余式，初始输入r_a和级输出r_b-r_d相互之间是同余的(即，r_a≡r_b≡r_c≡r_d)。另外，预先计算的多项式100a-100d允许级106a-106d并行执行许多计算，减少确定CRC余式所需的门延迟的数量。对应不同密钥重新编程电路110可以简单地是将预先计算的多项式的合适组载入存储元件100a-100d的方式。

[0017]图2示出了预先计算的一组多项式的采样，g_i(x)，100a-100d(如，g₄、g₂、g₁和g₀)。通过检查，这些多项式100a-100d具有这样的特性，即该组中的每个连续多项式100a-100d特征是前导的1比特(第i+k比特)后跟随i个零102(阴影)并以生成(CRC)多项式(如，g₀)的次数的数据104的k个比特结束。这些多项式100a-100d的形式使得每一级106a-106d能够将输入数据减少到较小但CRC等效的值。例如，从一些9比特多项式g₀(x)导出一组多项式{g₄(x)，g₂(x)，g₁(x)}之后，可对16比特的输入数据确定CRC。在操作期间，应用g₄(x)将输入数据从16个比特减少到12个比特，接下来g₂(x)可将输入数据从12个比特减少到10个比特，依此类推，直到最后的级106d输出8个比特余式。另外，如下面更详细地描述，给定级106a-106d可使用多项式100a-100d来并行处理输入数据的互不相交的区域。

[0018]更严格地，令g(x)是k+1比特的k次CRC多项式，其中一直设置前导比特以使得余式可跨度k个比特。多项式g(x)被定义为：

$g\left(x\right)=[x^k+\underset{i=0}{\overset{k-1}{\Sigma }}{g}_i{x}^i]$

g_j∈GF(2)

[0019]接着，多项式g_i(x)被定义为：

g_i(x)＝x^k+i+[x^k+i modg(x)]

[0020]根据g_i(x)的这个定义，可计算多项式序列作为原始多项式g(x)和i的选择值的函数。

[0021]CRC多项式g(x)除g_i(x)：

g(x)|g_i(x)

证明

g_i(x)＝x^k+i+[x^k+i modg(x)]

＝x^k+i+[x^k+i-a_i(x)g(x)]

-对于一些a_i(x)

＝a_i(x)g(x)

根据这个，可定义一个递归，其中在每个级，消息m(x)部分减少一个预先计算的多项式。

[0022]令m(x)为2^L比特的消息，r(x)是k比特结果：

r_j，m_j∈GF(2)

r(x)＝[m(x)·x^k modg(x)]

其中，m(x)通过x^k移位，创建空间将最后生成的CRC余式附加到消息m(x)中。因此对于i≥1：

r₀(x)＝m(x)·x^k

$r_i\left(x\right)=\left[r_{i-1}\left(x\right)\mathrm{mod}{g}_{2^{L-1}}\left(x\right)\right].$

因此，r_i(x)≡r₀(x)modg(x)，这由对i的归纳证明：

r₁(x)≡r₀(x)modg(x)

证明

$r_1\left(x\right)=r_0\left(x\right){\mathrm{mod}g}_{2^{L-1}}\left(x\right)$

$=r_0\left(x\right)\mathrm{mod}\left[a_{2^{L-1}}\left(x\right)g\left(x\right)\right]$

r_i(x)≡r_i-1(x)modg(x)

证明

$r_i\left(x\right)=r_{i-1}\left(x\right)\mathrm{mod}{g}_{2^{L-1}}\left(x\right)$

$=r_{i-1}\left(x\right)\mathrm{mod}\left[a_{2^{L-1}}\left(x\right)g\left(x\right)\right]$

[0023]最后，r_L(x)＝r(x)，这从以上的观测结果得出：

r_L(x)＝[r_L-1(x)modg₀(x)]

＝[m(x)·x^k-b(x)·g(x)]modg₀(x)

-对于一些b(x)

＝m(x)·x^k modg(x)

[0024]这些等式提供能以更多种电路实现的CRC计算的方法。例如，图3示出了实施上述方法的电路的高层结构。如所示出的，通过从级输入中减去预先计算的多项式g_i(x)的k个最低有效位104的倍数，给定级106a-106d可减少输入数据r。再次，虽然较小宽度，对于CRC计算，最后作为结果产生的级输出与输入是同余的。

[0025]示出的采样实施方式特征是级106a-106d，它们将g_i(x)的k个最低有效位104和输入数据的各个位进行相与110a-110d(例如相乘)。步骤不需要g_i(x)的i个零102和初始的“1”，因为他们不影响级计算的结果。因此，电路仅需要存储g_i(x)的k个最低有效位。

[0026]为了示例操作，假定r₀具有开始“1010...”的值，且g₄(x)的k个最低有效位具有“001010010”的值，第一个110a和第三个110c与门会输出“001010010”，同时第二110b和第四个110d与门会输出0。如图3中的阴影节点所示出的，可将与门110a-110d的输出排成一行来根据输入数据的各个比特的位置移位(即，相乘)门110a-110d输出。即，将在输入数据最高有效位上操作的门110a的输出移位i-1位，且每个随后的门110b-110d将这个移位递减1位。例如，关于输入数据将相应于r₀的最高有效位的门110a的输出移位3位，将相应于r₀的下一个最高有效位的门110b的输出移位2位，等等。接着，可通过门110a-110d的输出的移位排列来减(例如，异或)输入数据。减的结果将输入数据减少对于i＞0的多项式中等于零102的数目的位数。实质上，输入数据r₀的i个最高有效位作为选择器，使得输入数据减g_i(x)的k个最低有效位的某些倍数或输出不改变输入数据的零。

[0027]如所示出的，级106a的与门110a-110d可并行操作，因为他们工作在输入数据的互不相交的部分。即，每个与门110a-110d可同时并行处理r₀的不同位。这个并行处理可显著加速CRC计算。另外，不同的级也可并行处理数据。例如，级106b的门110e可在恰好靠近操作开始的地方执行它的选择，因为不改变r₀的最高有效位到达级106b。

[0028]图4A描述了遵守图3示出的结构的采样级106a实施方式的数字逻辑门。在这个例子中，级106a接收16位输入值(例如，r₀＝输入数据[15:0])和g₄(x)的k个最低有效位。级106a使用i组与门110a-110d处理输入值的第i个最高有效位，其中每个输入数据位与g₄(x)的k个最低有效位的每个经与门110a-110d相与。图4A中的每组k个与门110a-110d与图3中单个与门的概念描述一致。与门阵列110a-110d的输出基于输入数据比特位置排列并馈送到异或门112a-112d树，该异或门树从输入数据的剩余位减去移位的与门110a-110d输出(即，输入数据减去i个最高有效位)。

[0029]图4B描述了接收output_1数据[11:0]并生成输出output_2数据[9:0]的随后级106b的数字逻辑门。级106b接收级106a输出的12比特值并使用g₂(x)将12比特值减少到CRC同余的10比特值。级106a，106b共享与门和异或树的i阵列的相同基本结构，该与门对g_i(x)的k个最低有效位操作，异或树从级输入减去移位的与门输出以生成级输出值。可相似地构造用于i的不同值的其他级。

[0030]图3，4A和4B示出的结构仅仅是示例且可使用更多种其他实施方式。例如，在采样图中，每个级106a-106d并行处理输入数据的第i个最高有效位。在其他实施方式中，可并行使用大于或小于i的多个比特，但是，这可能不会减少给定级的输出数据的大小。

[0031]以上示出的结构可用于推导预先计算的多项式。例如，可通过清零与g_i(x)相关的存储元件并加载具有多项式密钥的k个最低有效位的g₀来执行此推导。可通过将x^k+i作为数据输入应用到该电路并将g₀级输出的作为结果最后产生的k个最低有效位作为与g_i相关的值存储，来确定与连续g_i相关的比特。例如，为了推导g₂的多项式，可将x^k+2应用为电路，可装载g₀级的作为结果最后产生的k比特输出作为g₂多项式的值。

[0032]图5描述了使用上述技术的采样CRC实施方式。该实施方式按32比特的段120对较大消息的连续部分起作用。如所示出的，采样实施方式通过任何预先存在的余式122对消息的给定部分120进行移位处理124，126和异或处理128，并使用级106a-106f和各个预先计算的多项式g_i(x)的k个比特计算CRC余式。此外，连续的级106a-106e将输入数据减少i比特，直到级106f输出余式值。接着，电路将余数馈送回122，用于处理下一个消息部分124。应用最终消息部分120之后剩余的余式是作为整体对消息确定的CRC值。这可附加到消息或与接收到的CRC值相比较，来确定数据损坏是否可能发生。

[0033]图5中示出的系统特征是(L+1)个级106a-106f，其中多项式是i＝{0，2^n-1，n＝1到L}的形式。但是，i的这个严格的几何级数是不必要的且i的其他值可用于减少消息。另外，在较低的多项式级(例如，i＜4)，放弃图3，4A和4B中描述的级结构并以传统的位串行或其他的方式使用g₀来处理输入值可能更有效。

[0034]上述技术可用于提高CRC计算速度，功率效率和电路面积。同样地，上述技术可应用在如网络处理器，安全处理器，芯片组，ASIC(专用集成电路)和处理器或处理器核内的功能单元的多种环境，在那里处理高时钟速度，同时支持任意多项式的能力是特别重要的。作为一个例子，上述CRC电路可集成到具有一个或多个媒体接入控制器(如，以太网MAC)的设备，该控制器耦合到一个或多个处理器或处理器核。在网络接口卡(NIC)，芯片组中，这样的电路可集成到处理器本身作为协处理器，等等。CRC电路可对网络分组内包括的数据(例如，分组报头和/或有效载荷)执行操作。另外，虽然结合CRC计算进行了描述，这个技术可应用到如对GF(2)的其他余式计算(例如，椭圆曲线密码术)的多种计算中。

[0035]这里使用的术语电路包括硬线电路，数字电路，模拟电路，可编程电路等的实施方式。可编程电路可对布置在存储介质上的计算机指令进行操作。

[0036]其他实施例在下面的权利要求的范围之内。