CN102771074B - 用于通信系统中错误检测的方法及设备 - Google Patents

Abstract

本发明揭示一种处理在相同长度的不相连原始区段的第一序列中的数据包的方法。所述方法包含通过修改其中的一个或一个以上符号而修改所述第一序列的所述原始区段中的第一者。所述数据包的开始位于所述原始区段中的所述第一者中且定位于其中的第一数字数据符号之后。所述方法还包含通过修改其中的一个或一个以上数字数据符号而修改所述第一序列的所述原始区段中的最后一者。所述数据包的结束位于所述原始区段中的所述最后一者中且位于其中的最后数字数据符号之前。所述方法还包含通过对从所述第一序列导出的不相连区段的第二序列有效地执行多项式除法而确定余项序列。所述第二序列的每一区段对应于且从所述第一序列的所述原始区段中的一者导出。所述第二序列的所述区段具有所述第一序列的所述原始区段的所述长度。所述第二序列的所述导出区段中的第一者是所述原始区段中的所述经修改的第一者。所述第二序列的所述导出区段中的最后一者是从所述原始区段中的所述经修改的最后一者导出的。

Description

用于通信系统中错误检测的方法及设备

技术领域

本发明涉及在基于包的通信系统中检测发射相关的错误。

背景技术

本章节引入可帮助读者获得对本发明的各种方面的更好理解的各种发面且不应理解为包含现有技术或非现有技术中的陈述内容。

通信系统的一个目的是确保由既定接收方接收的消息为所发射的消息的未更改的副本。为此原因，通信系统通常使用使接收方能够在发射期间确定所接收的消息是否被更改的错误检测技术。一种用于检测信道引发的消息错误的技术是基于循环冗余校验(CRC)码。CRC码通常将数字数据符号的序列(举例来说，表示数据消息)变换以产生数字校验符号的序列。所述数字校验符号的序列伴随着数字数据符号的序列一起发射，且接收方使用数字校验符号的序列来评估所接收的数字数据符号的序列是否为最初所发射的同一序列。

一些系统产生此种数字校验符号的序列及通过使用反馈移位寄存器来检测数字校验符号的发射序列的发射错误。举例来说，二进制CRC码可由移位寄存器来实施，所述移位寄存器经由异或(XOR)逻辑通过反馈来控制。所述移位寄存器的存储器元件的内容通常对应于通过将数字数据符号序列除以固定生成多项式所产生的余项序列。所述余项序列通常附加到数字数据符号序列的末端以发射至数据包的接收方。在此种系统中，所述余项序列通常是在数据包的发射之前连续地逐位计算。

发明内容

一个实施例为处理位于不相交原始区段的第一序列中的数据包的第一方法。所述第一区段的每一原始区段具有相同的长度。所述第一方法包含通过修改其中一个或一个以上符号来修改第一序列的原始区段中的第一者。数据包的开始是位于原始区段中的第一者中且位于其中的第一数字数据符号之后。第一方法还包括通过修改其中的一个或一个以上数字数据符号来修改第一序列的原始区段中的最后一者。数据包的结束位于原始区段中的最后一者中且位于其中的最后数字数据符号之前。第一方法还包含通过对源自第一序列的不相交区段的第二序列有效地执行多项式除法来确定余项序列。所述第二序列的每一区段对应于且源自于所述第一序列的原始区段中的一者。所述第二序列的区段具有所述第一序列的原始区段的长度。所述第二序列的衍生区段中的第一者是所述原始区段中的所述经修改的第一者。所述第二序列的所述衍生区段中的最后一者源自于所述原始区段中的所述经修改的最后一者。

在所述第一方法的一些实施例中，不包含数据包的开始或末端的每一衍生区段可等同于所述原始区段中的对应一者。

在所述第一方法的任何实施例中，修改步骤可包含掩蔽原始区段的在数据包外的部分以使得所述部分将以预定量有助于由多项式除法确定的余项。

在所述第一方法的任何实施例中，修改所述原始区段中的第一者可包含修改在数据包的开始处的符号。在一些此种实施例中，所述修改步骤可包含掩蔽原始区段的在数据包外的部分以使得所述经掩蔽部分将以预定量有助于由所述多项式除法确定的余项。

在所述第一方法的任何实施例中，所述原始区段中的最后一者的修改可修改在所述数据包的结束处的符号。在一些此种实施例中，所述修改步骤可包含掩蔽原始区段的在数据包外的部分以使得当所述数据包的循环冗余校验归零时所述经掩蔽部分将不会有助于由多项式除法确定的余项。

在所述第一方法的任何实施例中，所述第一方法可进一步包含通过执行从第一序列的符号序列的逐符号减法而产生第三序列以使得位于第三序列中的数据包变为基于多项式除法的错误控制码的有效码字。在一些上述方法的此种实施例中，可从通过对第二序列执行多项式除法所确定的余项中发现符号的序列。

在所述第一方法的任何实施例中，所述第一方法可进一步包含响应于数据包的结束是在所述第一序列的区段中的特定一者中而将数据包的循环冗余校验的评估值写入第一序列的区段中的所述特定一者中。在一些此种实施例中，所述修改可进一步包含接收指示包的结束在所述第一序列的区段中的所述特定一者中的位置的数字。所述写入可包含基于所述接收的数字而确定将写入评估值的位置。

第二方法的一个实施例涉及处理相等长度的不相交数据区段的序列。所述序列包含特定数据包。所述第二方法包含掩蔽所述数据区段中的一者的一部分。所述特定数据包的一部分是在所述数据区段中的所述一者中且在经掩蔽部分外。所述第二方法包含修改所述特定数据包的开始及/或末端且基于所述经掩蔽区段及所述经修改的特定数据包来计算所述特定数据包的循环冗余校验。

在所述第二方法的一些实施例中，所述第二方法可包含将计算出的循环冗余校验与零作比较。

在所述第二方法的任何实施例中，所述计算循环冗余校验可包含至少部分地基于与数据包一起发射的另一循环冗余校验来计算校验序列值。

在所述第二方法的任何实施例中，所述第二方法可包含识别数据区段中的所述特定一者内的包结束。

在所述第二方法的任何实施例中，所述第二方法可包含倒转所述数据包的开始处的一个或一个以上符号。

在所述第二方法的任何实施例中，所述第二方法可包含倒转所述数据包的结束处的一个或一个以上符号。

另一个实施例为一种用于处理位于不相交原始区段的第一序列中的数据包的系统。所述第一序列的每一原始区段具有相同的长度。所述系统包含掩蔽单元，其经配置以修改所述第一序列的原始区段中的第一者中的一个或一个以上符号，其中所述数据包的开始是在所述原始区段中的所述第一者中且在其中的第一符号之后。所述掩蔽单元经配置以修改在所述第一序列的原始区段中的最后一者中的一个或一个以上符号，其中所述数据包的结束位于所述原始区段中的所述最后一者中且在其中的最后符号之前。所述系统包含循环冗余校验计算单元，其经配置以通过对不相交连续区段的第二序列执行多项式除法来确定余项。所述第二序列的每一区段对应于且源自于所述原始区段中的一者。所述第二序列的区段具有所述原始区段的长度。所述第二序列的衍生区段中的第一者是所述原始区段中的所述经修改的第一者。所述第二序列的衍生区段中的最后一者是所述原始区段中的所述经修改的最后一者。

在所述系统的一些实施例中，掩蔽单元可经配置以掩蔽原始区段的在数据包外的部分以使得当数据包的循环冗余校验归零时所述部分将不会有助于由多项式除法确定的余项。

在所述系统的上述实施例中的任一者中，所述掩蔽单元可经配置以通过修改数据包的开始处的符号而修改所述原始区段中的第一者以及通过修改数据包的结束处的符号而修改所述原始区段中的最后一者。

附图说明

通过阅读下面的具体实施方式及参考附图可清楚各种实施例的优势，其中：

图1A图解地说明使用CRC码来检验错误(举例来说，由在物理通信信道上发射数字数据包所产生的错误)的数字数据通信系统；

图1B图解地说明例如在如图1A中说明的数据通信系统中处理数字数据符号的序列以产生用于CRC码字的最终序列的方法；

图2是说明解码数字数据符号的序列(举例来说，如图1B中说明)以确定序列的发射是否引起错误的方法(举例来说，用于图1A中说明的接收器中的方法)的流程图；

图3是说明编码数字数据符号的序列中的消息部分(举例来说，如图1B中说明)以对其附加CRC校验序列的方法(举例来说，用于图1A中说明的发射器中的方法)的流程图；

图4A是说明例如用于图1A中说明的发射器的编码器的一个实施例的框图，其中所述编码器例如使用图1B及3中的方法将CRC校验序列附加到每一待发射的数据包；

图4B是说明例如用于图1A的接收器的解码器的一个实施例的框图，其中所述解码器例如使用图1B及2中说明的方法基于CRC校验序列来评估所接收的数据包是否有错误；

图5说明例如在图4A中说明的编码器及/或图4B中说明的解码器中通过图1B、2及3的方法的一个特殊实施例对实例数据包的处理；

图6是说明例如在图4A至4B中说明的编码器及解码器的一些特殊实施例中可使用的组合的掩蔽单元及部分余项附加单元的一个实施例的框图；

图7是说明图6中说明的组合的掩蔽单元及部分余项附加单元的操作的状态图；及

图8是说明可用于图4A中说明的编码器的一些实施例中的逆向计算单元的特殊实施例的框图。

具体实施方式

各种实施例涉及用于检测基于数字数据包的通信系统中的发射错误的系统的设备、系统及方法。

图1A说明在数字数据包中发射信息的通信系统10的一个实例。所述通信系统10包含发射器12、接收器14及将发射器12连接到接收器14的物理通信信道16。所述发射器12包含输入数据处理器18及编码器400A。所述数据处理器18接收用于发射的数据及从其产生数据数字包的流。每一数字数据包可包含(举例来说)标头、消息部分及保留部分。所述编码器400A在将数据包发射至物理通信信道16之前将CRC校验序列插入到所述数据包中的一者或一者以上的保留部分中。所述接收器14包含解码器400B及输出数据处理器20。所述解码器400B校验所接收的数据包是否有发射错误，即基于其中的CRC校验序列来校验，且向输出数据处理器20指示经发现具有错误的数据包。输出数据处理器20可从由解码器400B发现无错误的数据包的消息部分提取数据。接收器14可经配置以发信号至发射器12以再发射由解码器400B发现具有发射错误的数据包。物理通信信道16支持在发射器12与接收器14之间的数据通信。物理通信信道16可包含一个或一个以上常规的光纤传输线、无线传输媒体、及/或有线传输媒体、或其混合物。通信系统10可经配置以提供数据包的额外封装及/或用于错误检测及/或纠正的其它方法的额外开销，举例来说，除了基于CRC校验序列方法以外的方法。

图1B图解地说明处理在通信系统中的数字数据符号的流的方法，其使用二进制CRC码来检测数据发射错误，例如，所述方法的步骤可在图1A的发射器12及/或接收器14中执行。

所述方法包括对第一序列32操作，所述第一序列32包含总共(a+k+m+b)个数字数据符号。所述第一序列32由等长度的连续区段形成。所述第一序列32包含长度为(k+m)的序列34，其形成消息及所关注数据包的保留部分。所述消息部分由多项式U(t)如实地表示，且所述保留部分由多项式F(t)如实地表示。在所述第一序列中，所述消息部分的前面附加“a”个数据符号的序列，且所述保留部分的后面附加“b”个数据符号的序列。

所述方法包含掩蔽所述第一序列32以产生由多项式V(t)如实地表示的第二序列36。在第一实施例中，所述掩蔽通过将第一序列32的并非位于所述消息中或所述数据包的保留部分中的那些位设定为零来产生第二序列36。在替代第二实施例中，所述掩蔽通过执行所述第一实施例的掩蔽步骤且还形成所述第一序列32中的所述消息部分的前“m”位及所述保留部分的“m”位的一补码来产生第二序列36。在图1B中，通过展示在数据包的合适的位位置之下插入“+I(t)”来图解地说明两个实施例，即，说明所述第二实施例的额外的掩蔽操作。

所述方法包含计算通过将经掩蔽第二序列36除以对应于CRC生成多项式G(t)的序列所得的余项序列的值。所述余项为由多项式R^(b)v(t)如实地表示的序列。在接收器处，所述余项序列的计算值指示所接收的数据包中不存在或存在某些类型的数据发射错误。

在用于编码的实施例中，所述方法包含产生将从发射器发射至接收器的第三序列38。所述第三序列38是通过将数据包的保留部分40替换为CRC校验序列(在上面描述的第一实施例中)或此种CRC校验序列的一补码(在上面描述的第一实施例中)来形成。此处，所述CRC校验序列或其一补码是由多项式“F(t)+D(t)”来表示，其中多项式F(t)如实地表示第一序列32中的保留部分的原始序列且D(t)表示调整序列，其促使34变为码字。下面更详细地描述图1B中说明的步骤及其中的符号。

此处，数据包含有不相交消息及保留部分，其中所述部分两者由有限符号字母表A中的数字符号的有限序列形成。所述字母表A可为有限Galois域，举例来说，模2整数或具有固定预选择长度的1和0的串。所述消息部分是k个数字符号的流u_k-1 u_k-2…u₁ u₀，其如实地表示为如下形式的k次多项式U(t)：

U(t)＝u_k-1t^k-1+u_k-2t^k-2+...+u₁t+u₀。

在多项式U(t)中，“t”的幂决定了第一流中对应数字符号的临时位置。所述保留部分可紧接地位于(举例来说)所述消息部分之后。在编码之前，所述保留部分保持m个数字符号的流f_m-1 f_m-2 ... f₁ f₀，其如实地表示为如下形式的m次多项式F(t)：

F(t)＝f_k-1t^m-1+f_m-2t^m-2+...+f₁t+f₀。

编码是用固定长度“m”的CRC校验序列部分或其一补码重写数据包的保留部分。所述CRC校验序列具有形式c_m-1 c_m-2 ... c₁c ₀∈A^m，其以如下形式的CRC校验序列多项式如实地表示：

C(t)＝c_m-1t^m-1+c_m-2t^m-2+...+c₁t+c₀。

在第一实施例中，举例来说，相对于图1B中所描绘，对应消息及CRC校验序列部分形成符号长度为n＝k+m的码字，其如实地由多项式X(t)表示，其满足：

X(t)＝U(t)·t^m+C(t)。

在多项式X(t)中，较高阶“t”项对应于数字数据包自身的消息部分的数字数据符号，且较低阶“t”项对应于所述数字数据包的CRC校验序列部分的数字符号。

此处，码字是指“t”的多项式，其可由预先选择及固定的“t”的CRC生成多项式完全地除尽，即所述多项式是可除尽的而没有非零余项。所述预先选择及固定的CRC生成多项式G(t)可写成：

G(t)＝g_mt^m+g_m-1t^m-1+g_m-2t^m-2+...+g₁t+g₀，其中g_m-1 g_m-2 ... g₀∈A^m，g₀≠0且g_m≠0。

举例来说，可用的CRC生成多项式G(t)是特殊的CRC生成多项式：

G(t)＝t³²+t²⁶+t²³+t²²+t¹⁶+t¹²+t¹¹+t¹⁰+t⁸+t⁷+t⁵+t⁴+t²+t+1。  (1)

等式(1)的所述特殊CRC生成多项式被称为CRC-32多项式且由若干标准指定，举例来说，IEEE802.3以太网标准。文中描述的方法及设备的各种实施例可经配置以使用CRC-32多项式或另一多项式作为CRC生成多项式。

在此种第一实施例中，选择CRC校验序列多项式C(t)使得U(t)·t^m+C(t)可被CRC生成多项式G(t)除尽，即，使得U(t)·t^m+C(t)是码字。特别地，U(t)·t^m除以CRC生成多项式G(t)的余项R(t)被定义为：

$R\left(t\right)=\mathrm{remainder}\left(\frac{U\left(t\right)\·t^m}{G\left(t\right)}\right).---\left(2\right)$

这里，余项多项式R(t)对应于数字符号序列r_m-1 r_m-2 ... r₁ r₀。因此，所述CRC校验序列多项式可满足C(t)＝-R(t)，其中任一系数的负号是所述系数在代数A中的加性逆元。在二进制CRC码中，-R(t)＝R(t)，因为二进制CRC码的代数A是整数模2，且对于整数模2来说，1+1＝0。因此，所述CRC校验序列多项式针对此代数为R(t)。

在使用这种CRC码的实施方案的数据通信系统中，发射器(例如，图1A中说明的发射器)发送数字数据符号的流。在流中，每一发射的数字数据包包含一起对应于码字X(t)的单独消息部分及CRC校验序列部分。每一数字数据包还可包含单独的包标头及/或包容器，其并非所述数据包的所述消息及CRC校验序列部分的部分。响应于对应于码字X(t)的数据包的发射，接收器接收到对应于多项式Y(t)的数字数据符号的序列，其中Y(t)＝X(t)+E(t)。这里，E(t)是如实地表示所接收的数据包中的错误的位置及值的多项式。为了确定是否已发生发射错误，接收器(例如，图1A中说明的接收器14)评估Y(t)除以CRC生成多项式G(t)的多项式除法的余项。当无任何发射错误时，Y(t)除以CRC生成多项式G(t)的余项是具有零系数的多项式，即，Y(t)为码字。当存在一个或一个以上发射错误时，此除法的余项可能为非零，即，错误是可检测的，除非E(t)自身是码字。举例来说，对于特殊的m阶生成多项式，作为小于m次的多项式的循环移位的任何错误序列均产生并非码字的多项式E(t)。因此，在接收的数据包中，此种错误可经由确定对应的多项式Y(t)是否为码字来检测。

在第二实施例中，举例来说，相对于图1B描述的第二实施例，编码包含用全一序列初始化将保持余项R(t)的“m”个存储器元件，及有效地评估多项式U(t)·t^m+I(t)·t^k除以CRC生成多项式G(t)的多项式除法的余项R(t)，其中I(t)＝t^m-1+t^m-2+...+t+1。因此，多项式R(t)满足：

$R\left(t\right)=\mathrm{remainder}\left(\frac{U\left(t\right)\·t^m+I\left(t\right)\·t^k}{G\left(t\right)}\right)---\left(3\right)$

在这些第二实施例中，用于数据包的消息及保留部分的第三序列的发射部分如实地由码字X(t)表示，其满足X(t)＝U(t)·t^m+C(t)其中C(t)＝R(t)+I(t)＝F(t)+D(t)。此处，对于CRC译码的这些第二实施例，如果将多项式除以CRC生成多项式G(t)产生“m”阶全一多项式，其中数据包的保留部分具有长度“m”，那么数据包由作为码字的多项式如实地表示。因此，接收器可用全一序列初始化特定用于CRC校验序列的存储器元件，且随后确定对应于Y(t)的所接收序列(即，X(t)+E(t))除以CRC生成多项式G(t)的多项式除法的余项是否产生全零序列以决定数据包是否具有发射错误。在IEEE802.3标准中的媒体接入控制(MAC)层将此替代程序与等式(1)的标准CRC-32生成多项式G(t)一起使用。

图2及3说明基于在由关于0及1的模加法定义的二进制代数上的循环冗余码(CRC)的用于处理数据包的方法200、300。编码方法300涉及例如在图1A中说明的编码器400A中通过评估用于数据包的消息部分的CRC校验序列且将CRC校验序列或其一的补码附加到消息部分来准备用于发射的每一数据包。所述附加步骤形成对应于CRC码字的序列。编码方法200涉及例如在图1A中说明的解码器400B中通过确定数据包是否对应于CRC码字而确定所接收的数据包是否具有CRC可检测的发射错误。“码字”的定义已经关于图1B的第一及第二实施例有所描述。

在步骤210及310处，方法200、300包含以逐区段的方式接收在其中具有数字数据包的第一序列的区段，举例来说，所述接收可在如图1A中所说明的编码器400A或解码器400B中执行。所述第一序列是“q”个区段的序列，其中每一区段具有相同的长度“s”。

每一第一序列包含：数据包的消息部分，其位的序列对应于多项式U(t)；及数据包的保留部分，其“m”位的序列对应于多项式F(t)，即，在图2到3的这些方法200、300中。所述保留部分可紧接在所述数据包的消息部分之后。所述消息及保留部分通常位于数据包的消息部分中，举例来说，在包标头之后。在所述第一序列中，“a”个位在对应于U(t)t^m+F(t)的序列之前，且“b”个位在对应于U(t)t^m+F(t)的序列之后。因此，q·s＝n+a+b，其中“q”是第一序列中的区段的数目，“s”是一区段中的位的数目，且“n”是对应于U(t)t^m+F(t)的序列中的位的数目。

此处，整数“a”、“b”及“n”的值可能由于数据包在第一序列中的不同的可能位置及数据包的不同的可能长度而在数据包到数据包之间变化。在下面描述的实例中，每一区段的长度足够短以确保不超过两个连续数据包的消息部分位于同一区段中。在一些其它的实施例中，区段可较长，使得一个数据包的消息部分的一部分、为零的消息部分、一个或一个以上随后的数据包及另一数据包的消息部分的部分可在一个区段中。

在步骤220及320处，所述方法200、300包含在接收到第一序列的“q”个区段时顺序地掩蔽所述区段，举例来说，所述掩蔽可在如图1A中说明的编码器400A或解码器400B中执行。在逐段方式中，所述掩蔽产生第二序列的区段，其中：

i)在对应于U(t)t^m+F(t)的序列之前的“a”个位为零，及

ii)在对应于U(t)t^m+F(t)的序列之后的“b”个位为零。

在一些特殊的实施例中，举例来说，相对于图1B描述的上述的第二实施例，掩蔽步骤220及330还包括：

i)倒转对应于U(t)t^m+F(t)的序列的起始“m”个位，及/或

ii)倒转对应于U(t)t^m+F(t)的序列的最终“m”个位。

这些特殊实施例执行数据包的消息部分及保留部分的串联的初始“m”个位及最终“m”个位的此选择倒转(即，求一补码)。在此种实施例中，区段的第二序列由如下形式的多项式V(t)如实地表示：

V(t)＝0·t^qs-1+...+0·t^n+b+(U(t)·t^m+I(t)·t^k+F(t)+I(t))·t^b+0·t^b-1+...+0·t+0。   (4)

在步骤230及330处，方法200、300包括以对应于将多项式V(t)递归地除以CRC生成多项式G(t)的逐段方式处理对应于多项式V(t)的第二序列。步骤230及330包括计算对应于多项式的余项序列，其为将多项式V(t)除以CRC生成多项式G(t)的除法的余项。因此，处理步骤230、330有效地执行将V(t)除以CRC生成多项式G(t)的除法而非执行将数据包的消息部分U(t)除以CRC生成多项式G(t)的除法。

在步骤240处，方法200基于步骤230处计算的余项来确定所述第一序列的对应于数据包的消息部分及保留部分的部分是否形成CRC码字。如果第一序列的此部分经确定为码字，那么方法200包含在250处发信号说明所述数据包无发射错误。如果第一序列的此部分经确定为不是码字，那么方法200包含在260处发信号说明所述数据包具有发射错误。

在步骤340处，方法300包括调整数据包的保留部分以使得数据包的消息部分及保留部分形成对应于CRC码字的序列。步骤340可包括确定对应于校验序列差分多项式D(t)的序列且创建用于数据包的消息部分及保留部分的最终序列。所述最终序列由多项式U(t)·t^m+D(t)+F(t)如实地表示。

在以上描述的第一实施例中，根据V(t)的形式得到：

$R_v^{\left(b\right)}\left(t\right)\≡\mathrm{remainder}\left(\frac{V\left(t\right)}{G\left(t\right)}\right)=\mathrm{remainder}\left(\frac{R\left(t\right)\·t^b}{G\left(t\right)}\right)---\left(5\right)$

如果计算的余项多项式的序列为长度至少为m的全零序列，则F(t)＝C(t)，且步骤340确定D(t)＝0。如果代替地，计算的余项多项式是非零多项式，其长度等于或小于m，则C(t)＝F(t)+D(t)，其中非零校验序列差分多项式D(t)满足：

$\mathrm{remainder}\left(\frac{D\left(t\right)\·t^b}{G\left(t\right)}\right)=R_V^{\left(b\right)}\left(t\right)---\left(6\right)$

然后，步骤340可有效地包括经由逆向计算求解等式(6)以从用于计算的余项多项式的计算序列获得用于校验序列差分多项式D(t)的符号序列。

步骤340可包括通过针对用于多项式V(t)的序列中的不同数目“b”个后续零来递归地求解与余项相关的另一等式，来从计算的余项多项式逆向计算多项式特别地，所述与余项相关的等式可根据倒序生成多项式以倒序形式重写。举例来说，可通过求解如下等式来从包括的余项获得

$R_V^{(i-\mathrm{\δ})}\left(t^{-1}\right)\·t^m=\mathrm{remainder}\left(\frac{R_V^{\left(i\right)}\left(t^{-1}\right)\·t^{m+\mathrm{\δ}}}{G\left(t^{-1}\right)\·t^m}\right)$ 其中1≤δ＜i。    (7)

即，第(i-δ)余项多项式的系数等于从将第i倒序余项多项式除以倒序固定多项式G(t^-1)·t^m即G(t^-1)·t^m＝g₀t^m+g₁t^m-1+…+g_m-1t+g_m所获得的余项。为此原因，上述递归过程还可以倒序形式的余项执行以从计算的余项多项式获得 举例来说，下面结合图8更具体描述针对某一范围内“b”值的任意范围执行此计算的一个方法。

在上述的第二实施例中，所述校验序列差分多项式D(t)是在多项式R(t)+I(t)与多项式F(t)之间的差，其对应于在所述第一序列中的数据包的保留部分。多项式R(t)+I(t)对应于用于数据包的消息部分的多项式U(t)+I(t)·t^(k-m)除以CRC生成多项式G(t)的除法的余项的一补码。在此实施例中，多项式R(t)的序列也可通过基于等式6至8的修改版本从计算的余项多项式的序列的逆向计算来找到，其说明第二实施例的上述等式(4)中所示的多项式V(t)中的倒转。所属领域的技术人员将能够容易地基于以上等式4至8的描述来确定所述修改的等式。

在步骤340处，方法300还顺序地发射给目的接收器一个最终序列，其中数据包具有原始消息部分且其中消息部分及保留部分形成如实地由多项式U(t)·t^m+D(t)+F(t)表示的CRC码字。

在以下描述的实施例中，“字”通常为“一个字节”。

图4A及4B分别说明编码器400A及解码器400B。编码器400A可(举例来说)执行图3的编码方法300，且解码器400B可(举例来说)执行图2的解码方法200。编码器400A及解码器400B是(举例来说)常规的数字硬件装置，举例来说，其由包含门、触发器、寄存器、加法器及/或乘法器的电路形成。图4A至4B中说明的编码器400A及解码器400B可(举例来说)分别为图1A中说明的编码器400A及解码器400B。编码器400A及/或解码器400B可位于网络接口卡(NIC)或运输网络元件(TNE)中，举例来说，用于有线、无线或基于光学包的通信的收发器的以太网NIC或TNE中。

如图4A及4B中所示，编码器400A及解码器400B包含一组数字数据处理单元。所述组数字处理单元包含分段单元410、掩蔽单元420、部分余项附加单元425、区段除法单元430、435、余项处理单元440及一个或一个以上数字缓冲器460、462、464、466。所述编码器还具有逆向计算单元470及校验序列调整单元480。所述解码器400B还具有校验序列验证单元490。各种所述数字处理单元以大致时间上顺序的逐段方式处理所接收的数据符号流，在所述方式中每一区段具有相同的长度。

分段单元410接收数字数据符号的流且连续地发射每一连续的等长的区段到掩蔽单元420及将关于每一区段的信息发射到掩蔽单元420及部分余项附加单元425。分段单元410在输入401处接收流且在输出412处输出所述流的区段。对于每一数据包，分段单元410输出“q”个连续区段的序列，其中“q”可在数据包到数据包之间变化。但是，每一区段是S w字节长，即s个位，其中s＝wS且w是一个字中的位的数目。在下面的描述中，区段被假定是字节对准的。结果可容易地扩展以处理非字对准的区段。

对于每一区段，分段单元410将对应于区段的信息发射到输出端口414。所述信息识别及定位位于对应区段中的任何数据包开始及/或数据包结束。如果区段具有数据包开始，那么分段单元410输出值为1的包开始(SOP)信号及识别区段中的数据包开始的位置的包开始索引(SPI)。如果区段不具有数据包开始，那么分段单元410输出值为0的SOP信号。如果区段具有数据包结束，那么分段单元410输出值为1的包结束(EOP)信号及识别区段中的数据包结束的位置的包结束索引(EPI)。如果区段不具有数据包结束，那么分段单元410输出值为0的EOP信号。分段单元410可通过读取数据包的包标头中的包长度识别符(PLI)来识别及定位数据包开始及/或数据包结束。

下面，通过数字(S-1)到0以发射顺序将区段的连续字编索引，其中较高的索引对应于较早发射的字。所述SPI及EPI信号可由二进制信号的长度为“j”的矢量表示(即，2^j-1＜S≤2^j)，所述二进制信号通过二进制数字表示每一索引。举例来说，SPI的值指向用于数据包的消息部分(即，对应于多项式U(t)的部分)的第一个字，且举例来说，EPI的值指向数据包的保留或CRC校验序列部分的最后一个字。

在经由输出412从分段单元410接收到区段时，掩蔽单元420以逐段的方式掩蔽区段的位。从第一序列的每q个区段(即，其中具有整个数据包)，掩蔽单元420产生对应区段的第二序列，其中所述第二序列对应于多项式V(t)，其已经有所描述。在此种第二序列中，掩蔽单元420将在数据包的消息部分及保留部分外的每一位设定为零，且将在对应于U(t)t^m+F(t)的序列之前的每一位设定为零且将在对应于U(t)t^m+F(t)的序列之后的每一位设定为零。因此，掩蔽单元420将所述第一序列的前“a”个位设定为“0”且将每一第一序列的最后“b”个位设定为“0”。在以上描述的第二实施例中，掩蔽单元420还倒转(即，一补码)对应于消息部分及保留部分的串联的序列(即，对应于多项式U(t)t^m+F(t)的序列)的前“m”个位及最后“m”个位。

掩蔽单元420顺序地输出所述第二序列的每一区段到部分余项附加单元425。所述部分余项附加单元425对长度为“m”的部分余项序列进行移位以便将部分余项添加至由所述第二序列的每一非前导区段的最高有效“m”个位形成的序列。此处，每一部分余项序列是将同一第二序列的先前区段的区段除法单元430、435中的一者除以对应于CRC生成多项式G(t)的序列的除法的余项。此种部分余项经由线路441从余项处理单元440被反馈到部分余项附加单元425。

所述区段除法单元430、435以顺序的逐段方式对每一接收的区段操作，举例来说，对应于经掩蔽的多项式V(t)的区段的每一区段。经由所述逐段除法，区段除法单元430、435输出部分余项的序列。因为区段除法单元430、435接收非前导区段，其与来自先前区段除法的经适当移位的部分余项结合，所以最终部分余项(即，通过第二序列的最后区段的除法在区段除法单元430、435中的一者中产生)对应于余项多项式R^(b) _V(t)的序列。即，由区段除法单元430、435输出的最终部分余项序列对应于通过将经掩蔽多项式V(t)除以CRC生成多项式G(t)将产生的余项。

在一些实施例中，部分余项附加单元425输出所述第二序列的所述组区段到一个区段除法单元430、435且输出下一第二序列的区段到另一区段除法单元435、430。在这些实施例中，区段除法单元430、435中的一者执行一个数据包的每一此种区段除以CRC生成多项式G(t)的除法，且另一区段除法单元435、430执行在流中的下一数据包的每一此种区段除以CRC生成多项式G(t)的除法。

在其它实施例中，部分余项附加单元425基于正被处理的数据包占据的区段的量而选择性地发射区段到区段除法单元430、435。特别地，如果所述区段具有数据包结束，且当前数据包在其中具有多于下一数据包的位，那么当前数据包的区段将被发射到第一区段除法单元430，且具有下一数据包的缩短区段将被发射到第二区段除法单元435。否则，如果当前数据包具有少于下一数据包的位，那么下一数据包的区段将被发射到第一区段除法单元430，且具有当前数据包的余项的缩短区段将被发射到第二区段除法单元435。

余项处理单元440将余项多项式R^(b) _V(t)的序列路由至输出442用于进一步处理。所述进一步处理可由校验序列验证单元490执行或由逆向计算单元470执行。对于每一数据包，余项处理单元440基于对应数据包的SOP、SPI、EOP及EPI信息从区段除法单元430、435的一者中选择余项多项式R^(b) _V(t)的序列。如已经描述的，余项处理单元440还将来自区段除法单元430、435的部分余项反馈到部分余项附加单元425。

在以上描述的第二实施例中，当数据包的保留部分的结束位于所述第二序列的最后区段的开始附近时发生特殊情形。在此种情形中，余项处理单元440可经配置以添加修正项到由区段除法单元430、435的一者针对所述第二序列的最后区段所评估的部分余项。更特别地，所述修正项补偿了当计算对应的部分余项时本应已倒转但在第二序列的倒数第二区段中并未倒转的一个或一个以上字节。所述修正项是由将倒数第二区段的经适当移位的丢失的一序列除以CRC生成多项式G(t)所产生的余项。所属领域的技术人员将能够容易地制作余项处理单元440将能够用来在这些特殊情形中应用此种修正项的查找表或组合电路。

在一些实施例中(图4A至4B中未说明)，部分余项附加单元425不存在，且掩蔽单元420顺序地将第二序列的每一区段直接输出到区段除法单元430、435中的一者。然后，余项处理单元440修改由在区段除法单元430、435中第二序列的最后区段除以对应于CRC生成多项式G(t)的序列的除法所产生的最终部分余项。特别地，所述修改包括添加从区段除法单元430、435进行的第二序列的较早区段的除法的部分余项计算的修正。所述调整修正最终部分余项以使得余项处理单元440将仍在端口442处输出对应于余项多项式R^(b) _V(t)的余项序列，即，通过将经掩蔽的第二序列V(t)除以CRC生成多项式G(t)而获得的余项。

在所述经掩蔽的第二序列中，可存在并非对应数据包的部分的后续固定数字数据符号，举例来说，对应于多项式V(t)的后续“0”的条目。如前面已经讨论的，如根据经掩蔽多项式V(t)的经掩蔽序列计算出的多项式R^(b) _V(t)的余项序列可不对应于数据包自身的CRC余项多项式C(t)。因此，对于一些数据包，逆向计算单元470可执行CRC余项多项式R(t)的正确CRC余项序列或(举例来说)如上文讨论的校验序列差分多项式D(t)的差分序列的逆向计算。在逆向计算单元470中，这些计算是基于长度“m”的余项多项式R^(b) _V(t)，其是从余项处理单元440的输出端口442接收。此种逆向计算还基于如上文已经描述的V(t)的序列中已知固定形式的“b”个后续零，即，从逆向计算单元470经由线路465接收的EOP及EPI信号已知。

在编码器400A中，逆向计算单元470经由输出端口472将用于CRC余项多项式R(t)的CRC校验序列或用于校验序列差分多项式D(t)的差分序列输出到校验序列调整单元480。

在编码器400A中，校验序列调整单元480将逆向计算的校验序列R(t)插入到对应数据包的保留部分中以产生用于发射至物理通信信道的经变换第一序列。在所述经变换第一序列中，用于数据包的消息部分及保留部分的序列如实地由多项式U(t)·t^m+F(t)+D(t)表示，而非由多项式U(t)·t^m+F(t)如实地表示的输入序列来表示。所述经变换的第一序列在输出端口482处输出。对于每一数据包，校验序列调整单元480从逆向计算单元470的输出端口472接收多项式R(t)或D(t)的序列。

校验序列调整单元480及逆向计算单元470经由数据线469在适当的时间接收数据包的区段。所述数据线包含提供适当长度的延迟的缓冲器460、466。校验序列调整单元480、逆向计算单元470及余项处理单元440经由数据线469在适当的时间接收数据包的EOP、EPI、SOP、SPI信号。控制线465包含提供适当长度的延迟的缓冲器462、464。

在解码器400B中，校验序列验证单元490在输出492处输出控制信号，其指示对应的数据包是否为码字。校验序列验证单元490基于从余项处理单元440接收的多项式R^(b) _V(t)的序列的形式来确定待输出的控制信号的值。如果多项式R^(b) _V(t)是长度“m”的全零多项式，那么校验序列验证单元490通常输出指示对应数据包为无发射错误的信号。但是，如果所述多项式R^(b) _V(t)是长度“m”的另一多项式，那么校验序列验证单元490通常输出指示对应的数据包具有发射错误的信号。

为了简要地概述，在编码器400A中，掩蔽单元420将来自分段单元410的区段的第一序列变换为对应于经掩蔽多项式V(t)的经掩蔽区段的第二序列，举例来说，等式(5)。在编码器400A中，例如根据等式(6)，区段除法单元430、435及余项处理单元440一起产生对应于余项多项式的区段的序列。逆向计算单元470例如基于等式(9)根据余项多项式来有效地确定CRC校验序列调整多项式D(t)或CRC余项多项式R(t)，且此多项式的序列可进一步用于校验序列调整单元480中。

在替代实施例中，其它数字装置可替代掩蔽单元420、部分余项附加单元425、区段除法单元430、435及余项处理单元440的组合。举例来说，如果区段含有至多一个数据包的部分，那么其可不必具有两个区段除法单元435、430及/或余项处理单元440。

如以上所描述，本文中描述的一个或一个以上实施例涉及用于产生数据包的CRC校验序列及在发射之前将所产生的CRC序列或其一补码写入到数据包中的系统或方法。

区段处理的实例及其它实例性实施例

图5说明经由图4A的编码器400A的一些实施例的实例性数据包的处理。所述数据包位于数字数据符号的第一序列510中，所述第一序列510由四个连续的、不相交的、等长度的区段522、524、526、528形成。所述处理包含产生经掩蔽区段570的第二序列及根据区段的第二经掩蔽序列计算CRC校验序列580。下面，将关于图6描述所述处理，图6为图4A的掩蔽单元420及部分余项附加单元425的实例的框图。所述掩蔽单元420及部分余项附加单元425是基于图7中展示的有限状态机(FSM)700而操作。

在图5中，四个区段522、524、526、528的第一序列510包含数据包，其具有消息部分514及用于CRC校验序列的保留部分516。第一及第四区段522、528具有不属于所述数据包的部分512、518，即，所述数据包的数据及保留部分514、516。

图5说明处理图4A的分段单元410、掩蔽单元420、部分余项附加单元425、区段除法单元430、435、余项处理单元440及逆向计算单元470。分段单元410将第一序列510的区段522、524、526、528及定义其中数据包的结束及开始的位置的信息顺序地输出到掩蔽单元420。掩蔽单元420将第一序列510的区段522、524、526、528顺序地变换为第二序列570的经掩蔽区段536、546、556、556。所述变换包括将第一序列510的不在所述数据包中的初始及最终部分512、518掩蔽为零，即，各自为6字节，且可包含对数据包的相同数目的初始及最终字节进行一倒转，即，在实例中各自为4字节(由虚线指示字节的倒转)。部分余项附加单元425将来自前导区段522、524、526的较早多项式除法(即，在区段除法单元430、435中)的中间或部分余项538、548、558添加到非前导区段524、526、528的最高有效字节。在此种实施例中，部分余项538、548、558经由余项处理单元440或经由区段除法单元430、435被反馈至掩蔽单元420。每一区段除法单元430、435将每一经掩蔽区段536、546、556、566(即，具有非前导经掩蔽区段524、526、528的附加部分余项)除以对应于CRC生成多项式G(t)的序列，从而产生部分余项538、548、558、568。余项处理单元440将对应于余项多项式R^(b) _V(t)的最后区段的余项568输出到逆向计算单元470。逆向计算单元470根据最后区段余项568计算对应于CRC余项多项式R(t)的CRC校验序列580或对应于差分多项式D(t)的CRC差分序列。

图6及8说明图4A至4B的掩蔽单元420、部分余项附加单元425及逆向计算单元470的特殊实施例。

参考图6，分段单元410将长度为s的区段，即图5中的Sw或20字节，发射到掩蔽单元420的掩蔽模块620、630、640。掩蔽单元420还可包含掩码生成模块610，其接收有关数据包的结束及开始区段索引的位置的信息。

掩码生成模块610根据图7中说明的实例性有限状态机(FSM)700解译此信息。在初始化处，所述FSM是在INIT/IDLE状态710中。只要所接收的SOP的值为“0”，所述FSM就保持为INIT/IDLE状态。如果稍后接收的(SOP，EOP)对指示SOP＝1及EOP＝0，那么对应区段具有数据包的开始，举例来说，图5的区段522。如果数据包也不具有数据包的结束，举例来说如图5的区段522，那么FSM改变为包开始(PB)状态720。如果所述区段也具有数据包的结束，即如果EOP＝1，那么FSM改变为满包(PF)状态760。在PB状态720中，图6的掩蔽单元420将在数据包外的区段的任何初始部分设定为0序列且倒转数据包本身的前m个位，举例来说，图5中的mw＝4字节。为了执行这些变换，掩码生成模块610产生掩码M^(S)及X^(S)以具有由所接收的SPI信号的值界定的形式。如果在下一区段中SOP及EOP的值为零，举例来说，图5的区段524，那么FSM改变为包中间(PM)状态730。在FSM处于PM状态中的第一时间，编码器确定数据包是否在最后区段的结束处开始，使得先前区段的掩码X^(S)的任何余项被反馈到掩蔽单元620以倒转当前区段的首先的字(如X_p ^(S)指定，至多((m/w)-1)个字将被倒转)。否则，PM状态通常不执行区段的掩蔽。FSM700将保留在状态PM730中直到EOP的值改变为1以指示包的结束位于区段中。

所述FSM保留在PM状态730中直到EOP的值改变为1。如果SOP的值仍为0，那么所述FSM响应于EOP改变为1而改变为包结束(PE)状态740。对于PE状态740，掩码生成模块610产生两个掩码M^(E)及X^(E)，其被反馈到掩蔽模块620以将在数据包外的区段的部分设定为零且按位倒转数据包的结束处长度为m的部分。如果SOP与EOP的值一起改变为1，那么所述区段含有正被处理的数据包的结束及下一数据包的开始。EOP及SOP的此种值引起FSM改变为双重包(PD)状态750，在其中使用区段除法单元430、435两者。

在PD状态750中，存在两个处理例子。在第一个例子中，所述区段具有数据包的结束部分，其长于在所述区段中的下一个数据包的开始部分。在此例子中，例如在PE状态740中在掩蔽模块620中处理数据包的结束部分，且区段除法单元430使用掩码M^(E)及X^(E)。在此例子中，以与在PB状态720中相似的方式在掩蔽模块640及区段除法单元435中并行处理具有少于H个字的新数据包的开始部分，即使用掩码M^(S)及X^(S)的H个最低有效位。在第二个例子中，所述区段具有数据包的结束部分，其短于区段中的下一个数据包的开始部分。在此例子中，类似于PE状态740，使用两个掩码M^(E)及X^(E)的H个最高有效位在掩蔽模块630及区段除法单元435中处理具有少于H个字的数据包的结束。在此例子中，类似于PB状态720，使用两个掩码M^(S)及X^(S)在掩蔽模块620及区段除法单元430中处理新数据包的开始部分。

最后，如果FSM700在INIT/IDLE状态710中或PE状态740中且SOP及EOP的值都变为1，那么所述FSM改变为PF状态760。在PF状态760中，整个包包含于一个区段中。在此例子中，通过应用四个掩码M^(S)、X^(S)、M^(E)、及X^(E)在掩蔽模块620中修改区段，且CRC余项由区段除法单元430确定。

FSM700可包含同时地校验有关包的开始及/或包的结束的信息的有效性。举例来说，在PM状态730中，如果SOP变为1，那么FSM可发送错误消息，且FSM可随后回到INIT/IDLE状态710。所述FSM可包含执行SPI及EPI信号的范围的有效性的其它校验。举例来说，在PD状态750中，EPI及SPI信号应指示在数据包的结束与下一个数据包的开始之间的距离等于或大于预定义的包间间隙长度。

图6说明掩蔽生成模块610及掩蔽模块620、630及640的实施例。当SOP＝1时，掩码生成模块610处理表示包索引的开始i_S的SPI信号以产生二进制掩码M^(S)，所述掩码M^(S)的分量具有从(S-1)到0的索引，即对应于S个字。具有大于i_S的索引的分量为零，且具有小于或等于i_S的分量为一。掩码生成模块610产生二进制掩码X^(S)，其指示哪些字是待倒转的。在二进制掩码X^(S)中，分量i_S至max(i_S-m/w+1，0)为一，且其它分量为零。如果(i_S-m/w+1)＜0，那么二进制掩码X^(S)的对应于下一个区段的分量(S-1)到(S-(i_S-m/w+1))也是一。所述掩码M^(S)及X^(S)分布到掩蔽模块620、630及640，且以取决于FSM700状态的方式选择性地使用。

在一个实施例中，掩蔽用零替代在数据包外的第一序列的每一数字数据符号且倒转数据包的前导及最终数字数据符号。掩码M^(S)的零值分量识别区段的不在数据包中的部分，且掩码M^(S)的单位值分量识别第一序列的在数据包中的部分。第一序列的字可通过以由M^(S)的对应分量控制的w个与门处理所述字而选择性地被设定为零或保持不变。如果掩码M^(S)的分量是零，那么所述与门用零替代对应的字，且如果掩码M^(S)的分量是一，那么所述与门不改变对应的字。类似地，掩码X^(S)的单位值分量识别待倒转的区段的部分。第一序列的字通过以由X^(S)的对应分量控制的w个异或门进行的此处理而选择性地被设定为倒转或保持不变。如果掩码X^(S)的分量是一，那么所述异或门用一倒转替代对应的字，且如果所述掩码X^(S)的分量是零，那么所述异或门不改变对应的字。

在图5中，长度20(字节/字)的区段522将指示在包的开始之前的六个字节的信息输入到掩蔽单元420。为此原因，掩码生成模块610用零替代前六个字节。所述掩码生成模块还引起区段的第7至10字节被倒转。

参考图6，掩蔽及部分余项附加单元420、425的组合可响应于在掩码生成模块610中检测到新的数据包的开始而重新开始余项计算。更特别地，掩蔽模块620及630可具有多路复用器，其在反馈余项与零输入之间进行选择以作为反馈余项。当SOP的值是一时，所述多路复用器选择零输入以重新开始多项式除法以评估余项多项式的序列。

再参考图4A、4B、5及6，部分余项附加单元及余项处理单元425、440可能够通过将先前计算的部分余项538、548、558附加至其最高有效部分来更新第二序列570的非前导区段546、556、566。每一部分余项538、548、558、568的计算包括在区段除法单元430、435中将此种经更新及掩蔽的区段536、546、556、566除以固定除数序列，例如CRC生成多项式G(t)。在此方式中，当数据包经由个别区段536、546、556、566上的迭代计算而伸展越过多个区段时，掩蔽单元420、部分余项附加单元425及余项处理单元440支持余项多项式R^(b) _V(t)的余项的计算。

举例来说，如下文的图5的实例中迭代地计算所述余项。在第一迭代中，FSM700进入PB状态720且形成及应用M^(S)掩码532及X^(S)掩码534到第一序列的区段522以获得第二序列570的第一经掩蔽区段536。然后，在区段除法单元430中处理经掩蔽区段536以获得第一部分余项538。在下一个迭代中，FSM700进入PM状态730，且掩蔽单元420把下一个区段524作为输入且产生用于给定的FSM状态的掩码以形成第二区段546，从而形成第二序列570的第二区段。部分余项538被反馈到部分余项附加单元425且被添加到下一个区段546的最高有效部分，之后区段除法单元430处理所得区段以确定下一个部分余项548。在下一迭代中，FSM700进入PM状态730，且在单元420中处理区段526以获得第二序列570的第三区段556。部分余项548被反馈到部分余项附加单元425且被添加到下一个区段556的最高有效部分，之后区段除法单元430处理所得区段以确定下一个部分余项558。在最后的迭代中，FSM700改变为PE状态740且形成及应用M^(E)掩码562及X^(S)掩码564到第一序列的区段528以形成第二序列570的最后区段566。另外，部分余项558被反馈到部分余项附加单元425且被添加到下一个区段566的最高有效部分，之后区段除法单元430处理所得区段以确定下一个部分余项568，其将通过将经掩蔽第二序列570除以CRC生成多项式G(t)来产生。

上述程序使得区段除法单元430、435能够以相同的方式计算部分余项538、548、558、568而不管第一序列510的区段522中的数据包的开始的位置。余项处理单元440可使用信号信息来确定包的结束是否在区段中从而确定余项是否应输出。

掩码生成模块610可产生位级倒转掩码X^(B)，其也可被传输至掩蔽模块620、630、640中的一者或一者以上。如果包含在包中的校验序列区段横越两个区段，那么可使用位级倒转信号来命令掩蔽模块620、630及640在位级上执行区段的(m/w)个最高有效字的其相应部分的倒转。

举例来说，在数据包的最后(m/w)个字待倒转的实施例中，可采用位级倒转来考虑区段的前((m/w)-1)个字中的包结束。使用此位级倒转是因为本应倒转的一个或一个以上字未被倒转，因为所述字是以先前区段来处理。虽然展示l个掩码信号耦合到全部的掩蔽模块620、630、640，且分别具有宽度S、(S-H)及H，但在替代实施例中，l个掩码中的一些可仅仅耦合到属于待倒转的数目的字的范围内的那些掩蔽模块。

S字掩蔽模块620及(S-H)字及H字掩蔽模块630及640可包含多组与门及多组异或门。所述多组与门及异或门用以实现字级掩蔽及从线路441至第二序列的区段的部分余项的添加。所述组异或门实现对掩蔽模块620、630及640的传入位中的一者或一者以上的倒转，且所述组异或门实现进入掩蔽模块的数据区段412的部分的每一位(即，整个字)的倒转。在替代实施例中，其它逻辑装置及/或结构可替代所述多组与门及/或多组异或门以实现此种掩蔽功能。

如上文描述，掩蔽单元420可通过将区段的不属于包的字设定为零来掩蔽数据区段的字，或可对在数据包的开始及/或结束处的一个或一个以上字进行一倒转。

参考图5，处理以接收第一序列的区段开始。接着，掩码生成模块610基于来自分段单元410的输出端口414的信息及有限状态机700的当前状态来确定新的包是否在所接收的区段中开始。如果新的包的确在区段中开始，举例来说，区段522，那么掩蔽生成模块610可产生掩码向量以设定在所述新的数据包的开始前的字节及/或倒转所述新的数据包的前m/w个字。在图5中，新的数据包的开始是在区段522中的第七字节，且掩蔽生成模块610产生掩码向量M^(S)534及倒转掩码向量X^(S)536以在掩蔽模块620中掩蔽所述区段522的前六个字且倒转第7至10字。

如果所接收的区段不具有新数据包的开始，那么掩蔽生成模块610确定所述数据包的结束是否在所述区段中，如状态PM730所指示。如果在所接收的区段中不存在数据包的结束，那么掩蔽单元620将不掩蔽或倒转所述区段的字节。然而，如果数据包的确在所接收的区段中结束，那么掩码生成模块610确定所述包的结束是否属于所述区段的前(m/w)-1个字内(PE状态740及PD状态750)。

如果所述数据包的结束是在区段的前(m/w)-1个字内，那么掩蔽单元420可通过将所述字设定为零来掩蔽在所述包的结束之后的字及/或可倒转数据包的最后(m/w)个字。在一个实施例中，掩蔽单元420用掩码M^(E)掩蔽在所述数据包之后的字且用掩码X^(E)倒转所述数据包的最后(m/w)个字。

如果所述数据包的结束不属于数据区段的前(m/w)-1个字内，那么在处理是根据IEEE802.3或其它适当的标准的情况下被倒转的一个或一个以上字节可能已经在先前被无倒转地处理，因为数据包的结束不会发生于含有本应已倒转的一个或一个以上字的区段中。因此，如果数据包的结束发生于区段412的前(m/w)-1个字中内(例如，在PE状态740及PD状态750中)，那么掩蔽单元420掩蔽在数据包的结束之后的字。

参考图4A至4B，余项处理单元440可计算其中具有数据包的部分的最后区段的余项。特别地，在PE及PF状态740、760中，区段除法单元430将以已经描述的方式计算最后区段的余项。将理解，如果余项处理单元440反馈部分余项，那么由区段除法单元430针对最后数据区段计算的余项是整个数据包以及替代在数据包的结束之后的字节的零的余项。每当已经到达包的结束时余项处理单元440便产生此余项。如果余项处理单元440不反馈部分余项，那么余项处理单元440确定线路441处的余项多项式乘以“t^s”，之后将来自此计算的所得余项从区段除法单元430的输出端口添加以形成余项多项式R^(b) _V(t)的序列。在PD状态750中，掩蔽单元420选择任一区段除法单元430、435来确定最后包的余项，且余项处理单元440选择任一区段除法单元430、435的输出来确定余项多项式R^(b) _V(t)的序列。

根据在数据包的结束之后具有额外零值的经掩蔽多项式V(t)计算出的余项多项式R^(b) _V(t)可单独地与数据包的CRC校验序列多项式R(t)有所不同。

参考图8，逆向计算单元470经配置以通过移除经掩蔽多项式V(t)中的后续零的影响来根据余项多项式R^(b) _V(t)逆向计算CRC校验序列多项式R(t)。更特别地，逆向计算单元470包含多个逆向计算模块820-0，820-1，...，820-(p-1)，其中每一计算模块820-0，820-1，...，820-(p-1)经配置以计算在含有数据包的结束的区段已被缩短由来自线路445的控制信号指定的特定量的情况下会得到什么余项。举例来说，逆向计算模块820-0经配置以计算在多项式除法在区段的结束之前一个字节已停止的情况下会得到什么CRC校验序列。大体上，逆向计算模块820-k经配置以计算在多项式除法在区段的结束之前2^k个字节已停止的情况下会得到什么校验序列。

所说明的逆向计算单元470可包含p个连续串联的逆向计算模块，每一此模块经配置以针对满足0≤q＜p的不同的“q”值逆向计算2^q个字节。

通过选择逆向计算模块820-0，820-1，...，820-(p-1)的组合，逆向计算单元470可针对在0与2^p-1之间的任何b值根据余项多项式R^(b) _V(t)选择性地逆向计算CRC校验序列多项式R(t)。更特别地，在图8中说明的实施例中，逆向计算单元470包含多个多路复用器830-0，830-1，...，830-(p-1)，其操作以基于经掩蔽为零的后续字节的数目的总和(即，b)来激活或旁路所选择的逆向计算模块820-0，820-1，...，820-(p-1)。此处，逆向计算模块820-k针对δ＝2^k实施等式(7)的硬件装置。

举例来说，如果区段528的最后7个字节被掩蔽为零，那么包的CRC余项或CRC校验序列多项式R(t)580经逆向计算7个字节。即，在线路445处的信号指示二进制数“00111”。因此，对应于逆向计算1个字节、2个字节及4个字节的多路复用器830-0，830-1，...，830-2将被激活，且用于逆向计算8个字节及16个字节的逆向计算模块将被旁路以产生7个字节的总的逆向计算。

上述余项R(t)的逆向计算是可行的，因为最终的经掩蔽区段的结束处的零确定性地影响余项的评估。为此原因，可根据计算的余项多项式R^(b) _V(t)及数据包的结束的位置来找到实际的CRC校验序列。此外，逆向计算单元470可使得区段除法单元430、435能够以相同的方式执行余项计算而不管数据包的结束的位置如何。区段除法单元430、435处理连续的等长的区段的序列，其相对于将需要较并行或串行的除法单元来确定所需余项的替代CRC编码器可改进图4A的编码器400A的效率及/或减小图4A的编码器400A的尺寸及制作成本。

再参考图4A，在CRC余项多项式R(t)的序列的逆向计算之后，逆向计算单元470经由输出端口472将长度为m的CRC校验序列或先前所描述的差分多项式D(t)的长度为m的序列输出到校验序列区段调整单元480。逆向计算单元470还经由输出端口474将关于数据包的保留部分的位置的信息输出到校验序列区段调整单元480。校验序列调整单元480使用位置信息以识别延迟线路469上的原始数据流中的数据包的保留部分且在输出端口482处产生数据流，其中对应数据包的保留部分中具有CRC校验序列。

最后，此种附加CRC校验序列的数据包可经由多种合适的发射器及发射协议(举例来说，以太网、千兆位以太网或演进仅语音/数据)从输出端口482发射到通信信道。

当数据包到达其目的地时，接收器可使用图4B的解码器400B计算数据包的CRC余项以用于识别在发射期间可能已发生的错误。如果发现所接收的数据包不是CRC码字，那么存在包的一个或一个以上位在发射期间被更改的高可能性。

虽然本发明可经受各种修改及替代形式，但本文已结合附图以实例的方式详细描述了特殊的实施例。然而，应理解本发明不打算限于所揭示的特定的形式。而是本发明将涵盖所附权利要求所界定的本发明的精神及范围内的全部修改、等效物及替代物。

Claims (11)

1.一种处理位于不相交原始区段的第一序列中的数据包的方法，所述第一序列的每一原始区段具有相同长度，所述方法包括：

通过修改所述第一序列的所述原始区段中的第一者中的一个或一个以上符号来修改所述第一序列的所述原始区段中的第一者，数据包的开始位于所述原始区段中的所述第一者中且在其中的第一符号之后；

通过修改所述第一序列的所述原始区段中的最后一者中的一个或一个以上符号来修改所述第一序列的所述原始区段中的最后一者，所述数据包的结束位于所述原始区段中的所述最后一者中且在其中的最后符号之前；及

通过对不相交导出区段的第二序列执行多项式除法来确定余项，所述第二序列的每一区段对应于所述原始区段中的一者且从所述原始区段中的一者导出，所述第二序列的所述区段具有所述原始区段的所述长度，所述第二序列的所述导出区段中的第一者是所述原始区段中的经修改的第一者，所述第二序列的所述导出区段中的最后一者是所述原始区段中的经修改的最后一者。

2.根据权利要求1所述的方法，其中不包含所述数据包的所述开始或结束的每一导出区段等同于所述原始区段中的对应一者。

3.根据权利要求1或2所述的方法，其中所述修改步骤包含掩蔽所述原始区段的在所述数据包外的部分以使得经掩蔽部分将以预定的量有助于由所述多项式除法确定的所述余项。

4.根据权利要求1或2所述的方法，其中所述修改步骤包含掩蔽所述原始区段的在所述数据包外的部分以使得当所述数据包的循环冗余校验归零时经掩蔽部分将不会有助于由所述多项式除法确定的所述余项。

5.根据权利要求3所述的方法，其中所述修改步骤包含掩蔽所述原始区段的在所述数据包外的部分以使得当所述数据包的循环冗余校验归零时所述经掩蔽部分将不会有助于由所述多项式除法确定的所述余项。

6.根据权利要求1所述的方法，其进一步包括：

响应于所述数据包的所述结束位于所述第一序列的所述区段中的特定一者中而将所述数据包的循环冗余校验的评估值写入到所述第一序列的所述区段中的所述特定一者中。

7.一种处理相等长度的不相交数据区段的序列的方法，所述序列包含特定数据包，所述方法包括：

掩蔽所述数据区段中的一者的一部分，所述特定数据包的一部分位于所述数据区段中的所述一者中且在经掩蔽部分外；

修改所述特定数据包的开始及/或结束；及

基于经掩蔽区段及经修改的特定数据包而计算所述特定数据包的循环冗余校验。

8.根据权利要求7所述的方法，其包括将所述计算的循环冗余校验与零作比较；且

其中所述计算循环冗余校验包括至少部分地基于与所述数据包一起发射的另一循环冗余校验来计算校验序列值。

9.一种用于处理位于不相交原始区段的第一序列中的数据包的系统，所述第一序列的每一原始区段具有相同的长度，所述系统包括：

掩蔽单元，其经配置以修改所述第一序列的所述原始区段中的第一者中的一个或一个以上符号，其中所述数据包的开始是在所述原始区段中的所述第一者中且在其中的第一符号之后，所述掩蔽单元经配置以修改所述第一序列的所述原始区段中的最后一者中的一个或一个以上符号，其中所述数据包的结束位于所述原始区段中的所述最后一者中且在其中的最后符号之前；及

循环冗余校验计算单元，其经配置以通过对不相交连续区段的第二序列执行多项式除法来确定余项，所述第二序列的每一区段对应于所述原始区段中的一者且从所述原始区段中的一者导出，所述第二序列的所述区段具有所述原始区段的所述长度，所述第二序列的所述导出区段中的第一者是所述原始区段中的经修改的第一者，所述第二序列的所述导出区段中的最后一者是所述原始区段中的经修改的最后一者。

10.根据权利要求9所述的系统，其中所述掩蔽单元经配置以掩蔽所述原始区段的在所述数据包外的部分以使得当所述数据包的循环冗余校验归零时所述部分将不会有助于由所述多项式除法确定的所述余项。

11.根据权利要求10所述的系统，其中所述掩蔽单元经配置以通过修改在所述数据包的所述开始处的符号来修改所述原始区段中的所述第一者且通过修改在所述数据包的所述结束处的符号来修改所述原始区段中的所述最后一者。