用於通信系統中錯誤檢測的方法及設備的製作方法
2023-07-31 12:11:06
專利名稱：用於通信系統中錯誤檢測的方法及設備的製作方法
技術領域：
本發明涉及在基於包的通信系統中檢測發射相關的錯誤。
背景技術：
本章節引入可幫助讀者獲得對本發明的各種方面的更好理解的各種發麵且不應理解為包含現有技術或非現有技術中的陳述內容。通信系統的ー個目的是確保由既定接收方接收的消息為所發 射的消息的未更改的副本。為此原因，通信系統通常使用使接收方能夠在發射期間確定所接收的消息是否被更改的錯誤檢測技木。一種用於檢測信道引發的消息錯誤的技術是基於循環冗餘校驗(CRC)碼。CRC碼通常將數字數據符號的序列(舉例來說，表示數據消息)變換以產生數字校驗符號的序列。所述數字校驗符號的序列伴隨著數字數據符號的序列一起發射，且接收方使用數字校驗符號的序列來評估所接收的數字數據符號的序列是否為最初所發射的同一序列。ー些系統產生此種數字校驗符號的序列及通過使用反饋移位寄存器來檢測數字校驗符號的發射序列的發射錯誤。舉例來說，ニ進位CRC碼可由移位寄存器來實施，所述移位寄存器經由異或(XOR)邏輯通過反饋來控制。所述移位寄存器的存儲器元件的內容通常對應於通過將數字數據符號序列除以固定生成多項式所產生的餘項序列。所述餘項序列通常附加到數字數據符號序列的末端以發射至數據包的接收方。在此種系統中，所述餘項序列通常是在數據包的發射之前連續地逐位計算。
發明內容
一個實施例為處理位於不相連原始區段的第一序列中的數據包的第一方法。所述第一區段的每ー原始區段具有相同的長度。所述第一方法包含通過修改其中ー個或ー個以上符號來修改第一序列的原始區段中的第一者。數據包的開始是位於原始區段中的第一者中且位於其中的第一數字數據符號之後。第一方法還包括通過修改其中的ー個或ー個以上數字數據符號來修改第一序列的原始區段中的最後ー者。數據包的結束位於原始區段中的最後ー者中且位於其中的最後數字數據符號之前。第一方法還包含通過對源自第一序列的不相連區段的第二序列有效地執行多項式除法來確定餘項序列。所述第二序列的每一區段對應於且源自於所述第一序列的原始區段中的一者。所述第二序列的區段具有所述第一序列的原始區段的長度。所述第二序列的衍生區段中的第一者是所述原始區段中的所述經修改的第一者。所述第二序列的所述衍生區段中的最後ー者源自於所述原始區段中的所述經修改的最後ー者。在所述第一方法的一些實施例中，不包含數據包的開始或末端的每ー衍生區段可等同於所述原始區段中的對應ー者。在所述第一方法的任何實施例中，修改步驟可包含掩蔽原始區段的在數據包外的部分以使得所述部分將以預定量有助於由多項式除法確定的餘項。
在所述第一方法的任何實施例中，修改所述原始區段中的第一者可包含修改在數據包的開始處的符號。在一些此種實施例中，所述修改步驟可包含掩蔽原始區段的在數據包外的部分以使得所述經掩蔽部分將以預定量有助於由所述多項式除法確定的餘項。在所述第一方法的任何實施例中，所述原始區段中的最後ー者的修改可修改在所述數據包的結束處的符號。在一些此種實施例中，所述修改步驟可包含掩蔽原始區段的在數據包外的部分以使得當所述數據包的循環冗餘校驗歸零時所述經掩蔽部分將不會有助於由多項式除法確定的餘項。在所述第一方法的任何實施例中，所述第一方法可進ー步包含通過執行從第一序列的符號序列的逐符號減法而產生第三序列以使得位於第三序列中的數據包變為基於多項式除法的錯誤控制碼的有效碼字。在ー些上述方法的此種實施例中，可從通過對第二序列執行多項式除法所確定的餘項中發現符號的序列。在所述第一方法的任何實施例中，所述第一方法可進ー步包含響應於數據包的結 束是在所述第一序列的區段中的特定一者中而將數據包的循環冗餘校驗的評估值寫入第一序列的區段中的所述特定一者中。在一些此種實施例中，所述修改可進ー步包含接收指示包的結束在所述第一序列的區段中的所述特定一者中的位置的數字。所述寫入可包含基於所述接收的數字而確定將寫入評估值的位置。第二方法的一個實施例涉及處理相等長度的不相連數據區段的序列。所述序列包含特定數據包。所述第二方法包含掩蔽所述數據區段中的一者的一部分。所述特定數據包的一部分是在所述數據區段中的所述ー者中且在經掩蔽部分外。所述第二方法包含修改所述特定數據包的開始及/或末端且基於所述經掩蔽區段及所述經修改的特定數據包來計算所述特定數據包的循環冗餘校驗。在所述第二方法的一些實施例中，所述第二方法可包含將計算出的循環冗餘校驗與零作比較。在所述第二方法的任何實施例中，所述計算循環冗餘校驗可包含至少部分地基於與數據包一起發射的另一循環冗餘校驗來計算校驗序列值。
在所述第二方法的任何實施例中，所述第二方法可包含識別數據區段中的所述特定ー者內的包結束。在所述第二方法的任何實施例中，所述第二方法可包含倒轉所述數據包的開始處的ー個或ー個以上符號。在所述第二方法的任何實施例中，所述第二方法可包含倒轉所述數據包的結束處的ー個或ー個以上符號。另ー個實施例為ー種用於處理位於不相連原始區段的第一序列中的數據包的系統。所述第一序列的每ー原始區段具有相同的長度。所述系統包含掩蔽単元，其經配置以修改所述第一序列的原始區段中的第一者中的ー個或ー個以上符號，其中所述數據包的開始是在所述原始區段中的所述第一者中且在其中的第一符號之後。所述掩蔽單元經配置以修改在所述第一序列的原始區段中的最後ー者中的ー個或ー個以上符號，其中所述數據包的結束位於所述原始區段中的所述最後一者中且在其中的最後符號之前。所述系統包含循環冗餘校驗計算単元，其經配置以通過對不相連連續區段的第二序列執行多項式除法來確定餘項。所述第二序列的每一區段對應於且源自於所述原始區段中的一者。所述第二序列的區段具有所述原始區段的長度。所述第二序列的衍生區段中的第一者是所述原始區段中的所述經修改的第一者。所述第二序列的衍生區段中的最後ー者是所述原始區段中的所述經修改的最後ー者。在所述系統的一些實施例中，掩蔽単元可經配置以掩蔽原始區段的在數據包外的部分以使得當數據包的循環冗餘校驗歸零時所述部分將不會有助於由多項式除法確定的餘項。在所述系統的上述實施例中的任一者中，所述掩蔽単元可經配置以通過修改數據包的開始處的符號而修改所述原始區段中的第一者以及通過修改數據包的結束處的符號而修改所述原始區段中的最後ー者。
通過閱讀下面的具體實施方式
及參考附圖可清楚各種實施例的優勢，其中 圖IA圖解地說明使用CRC碼來檢驗錯誤(舉例來說，由在物理通信信道上發射數字數據包所產生的錯誤)的數字數據通信系統；圖IB圖解地說明例如在如圖IA中說明的數據通信系統中處理數字數據符號的序列以產生用於CRC碼字的最終序列的方法；圖2是說明解碼數字數據符號的序列(舉例來說，如圖IB中說明)以確定序列的發射是否引起錯誤的方法(舉例來說，用於圖IA中說明的接收器中的方法)的流程圖；圖3是說明編碼數字數據符號的序列中的消息部分(舉例來說，如圖IB中說明)以對其附加CRC校驗序列的方法(舉例來說，用於圖IA中說明的發射器中的方法)的流程圖；圖4A是說明例如用於圖IA中說明的發射器的編碼器的一個實施例的框圖，其中所述編碼器例如使用圖IB及3中的方法將CRC校驗序列附加到每ー待發射的數據包；圖4B是說明例如用於圖IA的接收器的解碼器的一個實施例的框圖，其中所述解碼器例如使用圖IB及2中說明的方法基於CRC校驗序列來評估所接收的數據包是否有錯誤；圖5說明例如在圖4A中說明的編碼器及/或圖4B中說明的解碼器中通過圖1B、2及3的方法的ー個特殊實施例對實例數據包的處理；圖6是說明例如在圖4A至4B中說明的編碼器及解碼器的ー些特殊實施例中可使用的組合的掩蔽単元及部分餘項附加単元的一個實施例的框圖；圖7是說明圖6中說明的組合的掩蔽単元及部分餘項附加単元的操作的狀態圖；及圖8是說明可用於圖4A中說明的編碼器的一些實施例中的逆向計算單元的特殊實施例的框圖。
具體實施例方式各種實施例涉及用於檢測基於數字數據包的通信系統中的發射錯誤的系統的設備、系統及方法。圖IA說明在數字數據包中發射信息的通信系統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校驗序列方法以外的方法。圖IB圖解地說明處理在通信系統中的數字數據符號的流的方法，其使用ニ進位 CRC碼來檢測數據發射錯誤，例如，所述方法的步驟可在圖IA的發射器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。在圖IB中，通過展示在數據包的合適的位位置之下插入「+1 (t)」來圖解地說明兩個實施例，S卩，說明所述第二實施例的額外的掩蔽操作。所述方法包含計算通過將經掩蔽第二序列36除以對應於CRC生成多項式G (t)的序列所得的餘項序列的值。所述餘項為由多項式R(b)v(t)如實地表示的序列。在接收器處，所述餘項序列的計算值指示所接收的數據包中不存在或存在某些類型的數據發射錯誤。在用於編碼的實施例中，所述方法包含產生將從發射器發射至接收器的第三序列38。所述第三序列38是通過將數據包的保留部分40替換為CRC校驗序列(在上面描述的第一實施例中)或此種CRC校驗序列的ー補碼(在上面描述的第一實施例中)來形成。此處，所述CRC校驗序列或其一補碼是由多項式「F(t)+D(t)」來表示，其中多項式F(t)如實地表示第一序列32中的保留部分的原始序列且D(t)表示調整序列，其促使34變為碼字。下面更詳細地描述圖IB中說明的步驟及其中的符號。此處，數據包含有不相連消息及保留部分，其中所述部分兩者由有限符號字母表A中的數字符號的有限序列形成。所述字母表A可為有限Galois域，舉例來說，模2整數或具有固定預選擇長度的I和O的串。所述消息部分是k個數字符號的流IV1UkyU1Utl，其如實地表示為如下形式的k次多項式U (t)U (t)在多項式U(t)中，「t」的冪決定了第一流中對應數字符號的臨時位置。所述保留部分可緊接地位於(舉例來說)所述消息部分之後。在編碼之前，所述保留部分保持m個數字符號的流しし…もち，其如實地表示為如下形式的m次多項式F⑴F(t) = ^「+^パ+…+も七+ち。編碼是用固定長度「m」的CRC校驗序列部分或其一補碼重寫數據包的保留部分。所述CRC校驗序列具有形式Cm_lCnivClC(l G Am，其以如下形式的CRC校驗序列多項式如實地表示C (t) = c^t111 kcdt1112+…+C^t+Co。 在第一實施例中，舉例來說，相對於圖IB中所描繪，對應消息及CRC校驗序列部分形成符號長度為n = k+m的碼字，其如實地由多項式X(t)表示，其滿足X (t) =U (t) tm+C (t)。在多項式X(t)中，較高階「t」項對應於數字數據包自身的消息部分的數字數據符號，且較低階「t」項對應於所述數字數據包的CRC校驗序列部分的數字符號。此處，碼字是指「t」的多項式，其可由預先選擇及固定的「t」的CRC生成多項式完全地除盡，即所述多項式是可除盡的而沒有非零餘項。所述預先選擇及固定的CRC生成多項式G(t)可寫成G(t) = gn.f+g^f^ + g^t^2 + -** +g!t+g0, gnrfgm-2... g0 G A"*，g。關 0 且關 0。舉例來說，可用的CRC生成多項式G(t)是特殊的CRC生成多項式G(t) = t32+t26+t23+t22+t16+t12+tn+t10+t8+t7+t5+t4+t2+t+l。 (I)等式(I)的所述特殊CRC生成多項式被稱為CRC-32多項式且由若干標準指定，舉例來說，IEEE 802. 3乙太網標準。文中描述的方法及設備的各種實施例可經配置以使用CRC-32多項式或另ー多項式作為CRC生成多項式。在此種第一實施例中，選擇CRC校驗序列多項式C⑴使得U(t) *tm+C(t)可被CRC生成多項式G(t)除盡，即，使得U(t) *tm+C(t)是碼字。特別地，U(t) 除以CRC生成多項式G(t)的餘項R(t)被定義為
r U(f\. fm、R(t) = remainder -。(2)
lV ^(0 )這裡，餘項多項式R(t)對應於數字符號序列因此,所述CRC校驗序列多項式可滿足C(t) = _R(t)，其中任一係數的負號是所述係數在代數A中的加性逆元。在ニ進位CRC碼中，-R (t) = R(t)，因為ニ進位CRC碼的代數A是整數模2，且對於整數模2來說，1+1 = O。因此,所述CRC校驗序列多項式針對此代數為R(t)。在使用這種CRC碼的實施方案的數據通信系統中，發射器(例如，圖IA中說明的發射器)發送數字數據符號的流。在流中，每ー發射的數字數據包包含一起對應於碼字X(t)的単獨消息部分及CRC校驗序列部分。每ー數字數據包還可包含単獨的包標頭及/或包容器，其並非所述數據包的所述消息及CRC校驗序列部分的部分。響應於對應於碼字X(t)的數據包的發射，接收器接收到對應於多項式Y(t)的數字數據符號的序列，其中Y(t)= X(t)+E(t)。這裡，E(t)是如實地表示所接收的數據包中的錯誤的位置及值的多項式。為了確定是否已發生發射錯誤，接收器(例如，圖IA中說明的接收器14)評估Y(t)除以CRC生成多項式G(t)的多項式除法的餘項。當無任何發射錯誤時，Y(t)除以CRC生成多項式G(t)的餘項是具有零係數的多項式，即，Y(t)為碼字。當存在ー個或ー個以上發射錯誤時，此除法的餘項可能為非零，即，錯誤是可檢測的，除非E(t)自身是碼字。舉例來說，對於特殊的m階生成多項式，作為小於m次的多項式的循環移位的任何錯誤序列均產生並非碼字的多項式E(t)。因此，在接收的數據包中，此種錯誤可經由確定對應的多項式Y(t)是否為碼字來檢測。在第二實施例中，舉例來說，相對於圖IB描述的第二實施例，編碼包含用全一序列初始化將保持餘項R(t)的「m」個存儲器元件，及有效地評估多項式U(t) tm+I (t) * tk除以CRC生成多項式G(t)的多項式除法的餘項R(t)，其中I (t) = tm_1+tm_2+-+t+l0因此，多項式R(t)滿足
權利要求
1.ー種處理位於不相連原始區段的第一序列中的數據包的方法，所述第一序列的每ー原始區段具有相同長度，所述方法包括 通過修改其中的ー個或ー個以上符號來修改所述第一序列的所述原始區段中的第一者，數據包的開始位於所述原始區段中的所述第一者中且在其中的第一符號之後； 通過修改其中的ー個或ー個以上符號來修改所述第一序列的所述原始區段中的最後一者，所述數據包的結束位於所述原始區段中的所述最後一者中且在其中的最後符號之前；及 通過對不相連導出區段的第二序列執行多項式除法來確定餘項，所述第二序列的每ー區段對應於且從所述原始區段中的ー者導出，所述第二序列的所述區段具有所述原始區段的所述長度，所述第二序列的所述導出區段中的第一者是所述原始區段中的所述經修改的第一者，所述第二序列的所述導出區段中的最後ー者是所述原始區段中的所述經修改的最後一者。
2.根據權利要求I所述的方法，其中不包含所述數據包的所述開始或結束的每ー導出區段等同於所述原始區段中的對應ー者。
3.根據權利要求I或2所述的方法，其中所述修改步驟包含掩蔽所述原始區段的在所述數據包外的部分以使得所述經掩蔽部分將以預定的量有助於由所述多項式除法確定的所述餘項。
4.根據權利要求1、2或3所述的方法，其中所述修改步驟包含掩蔽所述原始區段的在所述數據包外的部分以使得當所述數據包的循環冗餘校驗歸零時所述經掩蔽部分將不會有助於由所述多項式除法確定的所述餘項。
5.根據權利要求I所述的方法，其進ー步包括 響應於所述數據包的所述結束位於所述第一序列的所述區段中的特定一者中而將所述數據包的循環冗餘校驗的評估值寫入到所述第一序列的所述區段中的所述特定一者中。
6.一種處理相等長度的不相連數據區段的序列的方法，所述序列包含特定數據包，所述方法包括 掩蔽所述數據區段中的一者的一部分，所述特定數據包的一部分位於所述數據區段中的所述ー者中且在所述經掩蔽部分外； 修改所述特定數據包的開始及/或結束 '及 基於所述經掩蔽區段及所述經修改的特定數據包而計算所述特定數據包的循環冗餘校驗。
7.根據權利要求6所述的方法，其包括將所述計算的循環冗餘校驗與零作比較；且其中所述計算循環冗餘校驗包括至少部分地基幹與所述數據包一起發射的另ー循環冗餘校驗來計算校驗序列值。
8.ー種用於處理位於不相連原始區段的第一序列中的數據包的系統，所述第一序列的每ー原始區段具有相同的長度，所述系統包括 掩蔽単元，其經配置以修改所述第一序列的所述原始區段中的第一者中的ー個或ー個以上符號，其中所述數據包的開始是在所述原始區段中的所述第一者中且在其中的第一符號之後，所述掩蔽單元經配置以修改所述第一序列的所述原始區段中的最後ー者中的ー個或ー個以上符號，其中所述數據包的結束位於所述原始區段中的所述最後一者中且在其中的最後符號之前 '及 循環冗餘校驗計算單元，其經配置以通過對不相連連續區段的第二序列執行多項式除法來確定餘項，所述第二序列的每一區段對應於且從所述原始區段中的一者導出，所述第二序列的所述區段具有所述原始區段的所述長度，所述第二序列的所述導出區段中的第一者是所述原始區段中的所述經修改的第一者，所述第二序列的所述導出區段中的最後一者是所述原始區段中的所述經修改的最後一者。
9.根據權利要求8所述的系統，其中所述掩蔽單元經配置以掩蔽所述原始區段的在所述數據包外的部分以使得當所述數據包的循環冗餘校驗歸零時所述部分將不會有助於由所述多項式除法確定的所述餘項。
10.根據權利要求9所述的系統，其中所述掩蔽單元經配置以通過修改在所述數據包的所述開始處的符號來修改所述原始區段中的所述第一者且通過修改在所述數據包的所述結束處的符號來修改所述原始區段中的所述最後一者。
全文摘要
本發明揭示一種處理在相同長度的不相連原始區段的第一序列中的數據包的方法。所述方法包含通過修改其中的一個或一個以上符號而修改所述第一序列的所述原始區段中的第一者。所述數據包的開始位於所述原始區段中的所述第一者中且定位於其中的第一數字數據符號之後。所述方法還包含通過修改其中的一個或一個以上數字數據符號而修改所述第一序列的所述原始區段中的最後一者。所述數據包的結束位於所述原始區段中的所述最後一者中且位於其中的最後數字數據符號之前。所述方法還包含通過對從所述第一序列導出的不相連區段的第二序列有效地執行多項式除法而確定餘項序列。所述第二序列的每一區段對應於且從所述第一序列的所述原始區段中的一者導出。所述第二序列的所述區段具有所述第一序列的所述原始區段的所述長度。所述第二序列的所述導出區段中的第一者是所述原始區段中的所述經修改的第一者。所述第二序列的所述導出區段中的最後一者是從所述原始區段中的所述經修改的最後一者導出的。
文檔編號H04L1/16GK102771074SQ201080049570
公開日2012年11月7日 申請日期2010年11月4日 優先權日2009年11月4日
發明者安德烈亞斯·伯恩哈德·左特曼, 艾德連恩·J·德林德凡委金戈登 申請人:阿爾卡特朗訊