用於使用二進位奇偶校驗來重建丟失分組的方法
2023-05-31 23:29:36
專利名稱:用於使用二進位奇偶校驗來重建丟失分組的方法
技術領域：
本發明總的涉及通信系統，更具體地，涉及在通信系統中重建丟失的分組。
背景技術：
諸如網際網路的基於分組的通信網已證明當傳送諸如電子郵件消息、網頁等等的非延時敏感的信息時是很健壯的。基於分組的通信網也可被使用來傳送諸如話音信息的延時敏感的信息(也稱為實時業務)。例如，通過網際網路的話音協議(VoIP)可被使用於通過網際網路的話音通信。然而，諸如網際網路的非單能網絡被認為是有損失的。例如，當在路由器中的緩存器變為充滿時，網際網路分組常常在這些路由器中丟失。對於另一個例子，光網絡中的光纖可能發生故障，在這種情形下，打算沿這些光纖光纜傳送的分組可能丟失。雖然包括非延時敏感的信息的丟失的分組可以通過使用各種重發方案，諸如混合自動重複請求(HARQ)協議而被恢復，但實時業務具有非常嚴格的延時約束條件，典型地不允許丟失的分組被重發。
提出了許多技術，防止通過基於分組的網絡發送的實時分組丟失。一個技術是通過一個以上的信道同時傳送延時敏感的信息。在一個信道上丟失的分組然後可以從冗餘信道被恢復。然而，分組丟失的概率通常遠小於1，所以，分配專用的冗餘信道可能減小通信系統的效率。另一個技術是通過使用冗餘碼傳送分組。理論上，在丟失分組中的原始的數據可以通過使用具有等於原始的數據的長度的傳送的代碼的任何部分被恢復。具有這個特性的代碼被稱為最大距離可分離(MDS)代碼。MDS碼的一個例子是Reed-Solomon碼。然而，包括使用MDS碼的原始的數據典型地需要許多複雜的和費時的運算，諸如在Galois域(sq)上的乘法和加法，這使得這些碼在現實的通信系統中實施變為不實際的。
實際上，冗餘信道編碼方案通常給傳送的實時業務量添加適當程度的冗餘性。例如，提出了通過使用異或(XOR)運算組合來自幾個分組的信息的簡單的編碼方案。然而，簡單的XOR冗餘編碼方案需要相對較高程度的冗餘性，並且會很大地降低通信系統的效率。例如，奇偶校驗代碼可以在兩個數據分組上生成簡單的奇偶校驗分組，這樣，如果原先的媒體分組是a，b，c，d，則由發送者生成的分組可包括在第一信道上傳送的a，b，c，d分組的媒體流，該媒體流與在第二信道上傳送的、包括表示奇偶校驗函數f(a，b)，f(c，d)的信息的前向糾錯(FEC)數據流平行。在本例中，糾錯方案(應當指出，術語「方案」和「代碼」在本上下文可以交換地使用)引入50％的附加開銷，但如果分組b被丟失，則在分組a中的信息和奇偶校驗函數f(a，b)可被使用來恢復分組b的內容。
接近最佳的代碼，可被稱為(1+ε)-MDS碼，是在Alon和Luby，「ALinear Time Erasure-Resilient Code with Nearly Optimal Recovery」，IEEE Transactions on Information Theory，Vol.42，No.6，November1996中提出的。然而，對於實施接近最佳代碼所需要的運行時間正比於O(n/ε4)，其中n是數據長度，並且對於傳送編碼的數據所需要的分組長度正比於O(log(1/ε)/ε4)。因此，減小冗餘性水平到可接受的水平，例如減小ε的數值到遠小於1的某個數值，需要非常長的運行時間和非常長的分組長度。
發明內容本發明的目的是解決以上闡述的一個或多個問題的影響。以下給出本發明的簡化的概要，以便提供本發明的某些方面的基本了解。這個概要不是本發明的窮舉的概述。不打算表示本發明的關鍵的單元或闡述本發明的範圍。它的唯一的目的是以簡化的形式給出某些概念作為以後討論的更詳細說明的序言。
在本發明的一個實施例中，提供了可包括執行與至少一個第一分組相關聯的至少一個奇偶運算的方法。方法還可包括傳送與至少一個第一分組相關聯的信息和表示該至少一個奇偶運算的信息。在本發明的另一個實施例中，提供了可包括訪問與至少一個分組相關聯的信息和表示對與至少一個第一分組和至少一個第二分組相關聯的信息執行的至少一個奇偶運算的信息的方法。方法還可包括根據與至少一個第一分組相關聯的信息和表示對於與至少一個第一分組和至少一個第二分組相關聯的信息執行至少一個奇偶運算的信息確定至少一個第二分組相關聯的信息。
基於奇偶校驗運算的本發明的實施例可以是接近最佳的，例如，它們可包括接近最佳(1+ε)-MDS碼，其中ε的數值可以容易地小於0.05。用於上述的編碼方案的編碼時間近似正比於(1+ε)，解碼時間近似正比於分組和冗餘分組的總數，並且分組大小正比於(1+ε)。因此，ε的數值可被減小到遠小於1的數值而不用對於傳統的接近最佳編碼方案典型地需要的相對較長的運行時間和/或相對較長的分組長度。本發明的實施例的實施方案的計算複雜性相對於用於實施接近最佳代碼的傳統的技術還可以被減小。
通過結合附圖參照以下的說明可以理解本發明，其中相同的標號表示相同的單元，以及其中圖1概念地顯示按照本發明的通信系統的一個示例性實施例；圖2概念地顯示按照本發明的、可以在通信系統中，諸如圖1所示的通信系統，傳送的分組和冗餘分組的一個示例性實施例；圖3概念地顯示按照本發明的、形成冗餘信息的方法的一個示例性實施例；和圖4概念地顯示用於重建丟失的和/或損壞的分組的方法的一個示例性實施例。
雖然本發明易於得到各種修改和替換的形式，但本發明的具體的實施例在附圖上作為例子被顯示，並且在這裡詳細地描述。然而，應當看到，這裡的具體的實施例的說明不打算把本發明限於所公開的特定的形式，但相反，打算覆蓋屬於由所附權利要求
限定的本發明的精神和範圍的所有的修改、等價物和替換例。
具體實施方式下面描述本發明的說明性實施例。為了清晰起見，在技術說明書中不描述實際的實施方案的所有的特性。當然，將會看到，在任何這樣的實際的實施例的開發中，許多實施方案特定的決定應當被做成達到開發者的具體的目標，諸如遵循隨不同的實施例而不同的、與系統有關的和與商業有關的約束條件。而且，將會看到，這樣的開發努力可能是複雜和費時的，但無論如何是從本公開內容獲益的本領域技術人員擔負的例行程序。
本發明的部分和相應的詳細說明以軟體或算法和對計算機存儲器內數據比特的操作的符號表示法被給出。這些說明和表示法是本領域技術人員用來把它們的工作的實質有效地輸送本領域另外的技術人員的說明和表示法。算法，正如該術語在這裡使用的和正如它一般地使用的，被設想為導致想要的結果的一系列獨立自主的步驟。步驟是需要對物理量進行物理地操縱的步驟。通常，雖然不一定，這些量取能夠被存儲、傳送、組合、比較和操縱的光的、電的、或磁的信號的形式。經常，特別是為了通常的使用，把這些信號稱為比特、數值、單元、符號、字符、項目、號碼等等，證明是方便的。
然而，應當記住，所有的這些和類似的術語與適當的物理量有關，並且是被加到這些量的方便的標籤。除非專門指出，或正如從討論中看到的，諸如「處理」、「計算(computing或calculating)」、「確定」、或「顯示」等等的術語是指計算機或類似的電子計算設備的行動和處理過程，把計算機系統的寄存器和存儲器內的、被表示為物理的、電子的量的數據操縱和變換成計算機系統的存儲器或寄存器或其它這樣的信息貯存、傳輸或顯示設備的、被類似地表示為物理量的數據。
還應當指出，本發明的軟體實施方面典型地在某種形式的程序貯存媒體上被編碼或在某種類型的傳輸媒體被實施。程序貯存媒體可以是磁的(例如，軟盤或硬碟)或光的(例如，緊湊盤只讀存儲器，或「CDROM」)，並且可以是只讀的或隨機存取的。類似地，傳輸媒體可以是雙絞線、同軸電纜、光纖、或技術上已知的某些其它適當的傳輸媒體。本發明不限於任何給定的實施方案的這些方面。
現在參照附圖描述本發明。各種結構。系統和設備被示意地顯示在附圖上，僅僅用作為說明，並且不用本領域技術人員熟知的細節來遮蔽本發明。無論如何，附圖被包括來描述和說明本發明的例子。這裡使用的單字和詞組應當被理解和被解譯為具有與由本領域技術人員對這些單字和詞組理解的一致的意義。不打算通過對於術語或詞組的一致的使用法給術語或詞組加上專門的定義，即，與由本領域技術人員理解的普通的和慣用的意義不同的定義。就打算使術語或詞組具有專門的意義，即與由本領域技術人員理解的不同的意義的方面來說，這樣的專門的定義將在技術說明書中以直接地和不含糊地提供對於術語或詞組的專門的定義的定義方式被明顯地闡述。
圖1概念地顯示通信系統100的一個示例性實施例。在說明性實施例中，通信系統100包括網絡105，它可包括按照有線和/或無線協議的任何組合工作的、有線網和/或無線網的任何組合。例如，網絡105可包括按照網際網路協議工作的部分和按照通用移動電信業務(UMTS)協議工作的部分。然而，本領域技術人員將會看到，本發明不限於這些示例性協議。在替換的實施例中，網絡105可包括按照公共交換電話網(PSTN)協議、普通老式電話系統(POTS)協議、碼分多址(CDMA，CDMA2000)協議、藍牙協議、IEEE 802協議之一等等工作的部分。在一個實施例中，網絡105還可包括光學部分，包括一個或多個光纖光纜和其它支持設備。
各種不同的終端110(1-3)可以通信地耦合到網絡105。索引(1-3)可被使用來指單獨的終端110(1-3)或終端子集110(1-3)。然而，當指終端110整體時，可以不使用這些索引。在本申請中都採用這種編號用法。在說明性實施例中，終端110包括可被配置來用於通過網際網路協議的話音(VoIP)通信的臺式計算機110(1)，可被配置來用於通過光纖光纜傳送信號的電話110(2)，和移動單元110(3)。終端110可以通過一個或多個接口設備115被通信地耦合到網絡105。在說明性實施例中，臺式計算機110(1)經由路由器115(1)被通信地耦合到網絡105，電話110(2)經由光路由器115(2)被通信地耦合到網絡105，以及移動單元110(3)經由空中接口120被通信地耦合到基站路由器115(3)。用於操作終端110和接口設備115的技術對於本領域技術人員是已知的，為了清晰起見，這裡將只討論與本發明有關的、終端110和/或接口設備115的那些操作方面。
通信系統100還可包括一個或多個伺服器125，這些伺服器被通信地耦合到網絡105。伺服器125可被使用來經由網絡105提供信息給終端110。例如，伺服器125可以容納一個或多個網站，它可以給終端110提供通信服務。伺服器125也可被使用來接收、存儲和/或發送由終端110提供的信息。例如，伺服器125可以實施話音消息傳送系統，它可以接收來自終端110的話音消息，存儲該話音消息，然後在以後的時間把該話音消息傳送到另一個終端110。然而，從本公開內容獲益的本領域技術人員應當看到，伺服器125的這些示例性功能只打算是說明性的，而不是限制本發明。
信息在終端110、接口設備115和/或伺服器125之間以分組形式傳送。例如，網絡105可以接收來自終端110、接口設備115和/或伺服器125的分組，並且可以按照網際網路協議把分組分發到終端110、接口設備115和/或伺服器125。例如，在一個或多個終端110、接口設備115和/或伺服器125上實施的實時應用可以按照諸如實時輸送協議/用戶數據報文協議(RTP/UDP)的各種不同的協議發送和/或接收分組。示例性實時應用包括VoIP應用、視頻流應用等等。
分組實際上在包括網絡105、終端110、接口設備115和/或伺服器125的通信系統100的任何部分以及在有線、電纜、光纖光纜、空中接口等等上可能被丟失或損壞。因此，可以發送冗餘信息，並且使用它來重建丟失的或損壞的分組。在一個實施例中，冗餘信息是通過訪問在包括要被發送的信息的分組中的一個或多個比特和對於比特執行至少一個奇偶運算而被形成的。例如，在要被發送的每個分組中的一個比特可被訪問(例如，從存儲器或寄存器被讀出，或作為數據流的一部分被接收)，並且這些比特可以通過使用異或(XOR)運算被組合，以形成冗餘信息。冗餘信息可被包括在一個或多個冗餘分組，並且用原先的分組例如通過單個信道被傳送。如果一個原先的分組被確定為丟失和/或損壞的，則冗餘信息可以與成功地接收的信息相組合，以重建丟失和/或損壞的分組。
冗餘分組可以被形成在通信系統100內的任何位置，或位置的組合。丟失和/或損壞的分組也可以通過使用在通信系統100內的任何位置，或位置的組合處的冗餘信息而被重建。例如，冗餘分組可被形成在終端110、伺服器125或任何其它位置。丟失和/或損壞的分組可以通過使用在終端110、接口設備115、伺服器125或在網絡105內某些位置處的冗餘信息而被重建。本領域技術人員還應當看到，這些操作可以通過使用硬體、固件、軟體或它們的任何組合而被執行。
圖2概念地顯示可以在諸如圖1所示的通信系統100的通信系統中傳送的分組200和冗餘分組205的一個示例性實施例。在說明性實施例中，分組200和冗餘分組205被顯示為分開的分組，它們分別包括要被傳送的信息和通過使用要被傳送的信息而形成的冗餘信息。然而，本領域技術人員應當看到，本發明並不限於此。在替換實施例中，部分要被傳送的信息和部分冗餘信息可被組合在一起，並在一個或多個分組中被傳送。例如，代表要被傳送的信息的比特和代表冗餘信息的比特可以在單個分組內被交織。
在說明性實施例中，在冗餘分組205中比特的值通過對於從分組200選擇的比特執行奇偶運算而被確定。從本公開內容獲益的本領域技術人員應當看到，奇偶運算可包括被使用來確定與數據流有關的一個或多個奇偶校驗比特的任何運算。例如，冗餘分組205(1)可以通過從每個分組200中選擇第一比特(由虛線方塊表示)而被形成，如箭頭210所示。所選擇的比特然後可以通過使用諸如XOR運算的二進位奇偶運算而被組合，並且二進位奇偶運算的結果可被存儲作為冗餘分組205(1)中的一個或多個比特。對於另一個例子，冗餘分組205(2)可以通過選擇沿穿過分組200的45°線215上的比特(由虛線方塊表示)而被形成，例如，第二比特可以從第一分組200(1)中進行選擇，第三比特可以從第二分組200(2)中進行選擇，第四比特可以從第三分組200(3)中進行選擇，等等。所選擇的比特然後可以通過使用諸如XOR運算的二進位奇偶運算而被組合，並且二進位奇偶運算的結果可被存儲作為冗餘分組205(2)中的一個比特。在說明性實施例中，在205(2)中的第一比特是與200(3)中的第一比特相同的，在205(2)中的第二比特是200(2)中的第一比特與200(3)中的第二比特的XOR，在205(2)中的第三比特是200(1)中的第一比特、200(2)中的第二比特與200(3)中的第三比特的XOR，等等。對於再一個例子，冗餘分組205(3)可以通過選擇沿穿過分組200的135°線220上的比特(由虛線方塊表示)而被形成，例如，最後的比特可以從第一分組200(1)中進行選擇，倒數第二個比特可以從第二分組200(2)中進行選擇，等等。所選擇的比特然後可以通過使用諸如XOR運算的二進位奇偶運算而被組合，並且二進位奇偶運算的結果可被存儲作為冗餘分組205(3)中的一個或多個比特。
雖然在冗餘分組205中的比特是通過使用XOR運算被形成的，但從本公開內容獲益的本領域技術人員應當看到，本發明不限於XOR二進位奇偶運算。在替換實施例中，可以使用任何奇偶運算。例如，可以不用比特而使用字節為單位，並且在字節內的每個比特上的XOR可被記錄。這個方法可能降低效率(增加上面和下面描述的ε)，但它可使得計算並行地和更快速地進行。從本公開內容獲益的本領域技術人員應當看到，用於從分組200選擇比特來形成冗餘分組205是設計方案選擇的問題而與本發明無關。而且，分組200的數目和/或冗餘分組205的數目，以及被包括在分組200和/或冗餘分組205中的比特的數目也是設計方案選擇的問題而不與本發明無關。
再者，雖然在說明性實施例中使用三個冗餘分組，但本發明並不限於任何具體數目的冗餘分組。在替換實施例中，可以選擇任意數目的冗餘分組。例如，分組可被選擇為使得每個選擇的分組與每個原始的分組具有一個和僅僅一個交點，並且每對選擇的分組在兩條線之間具有一個和僅僅一個交點。因此，對於任意M個原始的數據分組，可以選擇N個保護分組來實現所謂的M+N保護。如果在這些M+N分組內的任意N個分組被丟失，則通過使用該N個保護分組，仍舊可恢復M個原始的分組的內容。
如果一個或多個分組200，或分組200的部分，在傳輸期間被損壞和/或丟失，則冗餘分組205可被使用來重建丟失的和/或損壞的分組200。例如，如果10個包括10比特的分組200被使用來構建三個包括10比特冗餘信息的冗餘分組205，則30％的發送的信息可被重建，如果它被丟失和/或損壞的話。例如，三個丟失的或損壞的分組200可以通過使用三個冗餘分組205被重建。用於通過使用冗餘分組重建丟失的和/或損壞的信息是本領域技術人員已知的，因此為了清晰起見，這裡只討論這些技術中與本發明有關的那些方面。
圖3概念地顯示形成冗餘信息的方法300的一個示例性實施例。在說明性實施例中，訪問在要被發送的一個或多個分組中的信息(在305)。例如，訪問在要被發送的多個分組的每個分組中的一個或多個比特(在305)。然後，可以對於訪問的信息執行奇偶運算(在310)。例如，來自多個分組的比特可以通過使用異或運算被組合。奇偶運算的結果然後可被使用來形成(在315)一個或多個冗餘分組。例如，異或運算的結果可被使用來形成一個或多個冗餘分組的比特。冗餘分組然後可以連同原先的分組一起被發送(在320)。
圖4概念地顯示用於重建丟失和/或損壞的分組的方法400的一個示例性實施例。在說明性實施例中，一個或多個分組可被確定為(在405)丟失和/或損壞的。用於確定分組是否為丟失的和/或損壞的技術是本領域技術人員已知的，並且為了清晰起見，這裡將不作進一步討論。響應於確定(在405)一個或多個分組是丟失和/或損壞的，可以訪問與該丟失和/或損壞的分組有關的冗餘分組以及其它成功地接收的分組(在410)。然後可以通過使用在與該丟失和/或損壞的分組有關的冗餘分組中的信息和在其它成功地接收的分組中的信息重建該丟失的和/或損壞的分組(在415)。
用於形成冗餘信息和通過使用上述的冗餘信息重建丟失的和/或損壞的分組的技術比起傳統的實踐具有許多優點。上述的基於二進位奇偶運算的編碼方案是接近最佳的(1+ε)-MDS碼。對於XOR編碼方案，ε＝(M-L)/L，其中M是原始的數據分組或信道的數目以及L是每個原始的數據分組的、以比特計的長度。因此，ε的數值可以容易地小於0.05。對於光學網絡，上述的編碼方案可以提供M+N保護，其中M是被使用來傳送原始信息的脈衝或信道的數目以及N是額外的冗餘脈衝的數目。用於上述的編碼方案的編碼時間大約正比於(1+ε)，解碼時間大約正比於分組與冗餘分組的總數，以及分組尺寸大約正比於(1+ε)。因此，ε的數值可以被減小到遠小於1，而不用由傳統的接近最佳編碼方案典型地需要的相對較長的運行時間和/或相對較長的分組長度。本發明的實施例的實施方案的計算複雜性也可以相對於傳統的用於實施接近最佳代碼的技術被減小。所以，上述的編碼方案可被使用來提供用於諸如VoIP、視頻流、使用RTP/UDP協議的其它應用等等的實時應用的冗餘信息。上述的技術也可被使用來通過把每個時分復用時隙看作為單個數據單元而提供光路徑保護。
上述的具體的實施例僅僅是說明性的，因為本發明可以以對於從這裡的教導獲益的本領域技術人員清楚的、不同的但等價的方式被修改和被實踐。而且，不打算給不同於下面的權利要求
中描述的、這裡顯示的結構或設計的細節加限制。所以，顯然，以上公開的具體的實施例可被改變或修改，比起所有的這樣的變化被認為屬於本發明的範圍和精神。因此，這裡尋求的保護是在下面權利要求
中闡述的內容。
權利要求
1.一種方法，包括對於與至少一個第一分組相關聯的信息執行至少一個奇偶運算；以及傳送與至少一個第一分組相關聯的所述信息和表示所述至少一個奇偶運算的信息。
2.權利要求
1的方法，包括訪問來自多個第一分組的每個的至少一個預定位置的至少一個比特。
3.權利要求
1的方法，其中執行奇偶運算的步驟包括執行二進位奇偶運算。
4.權利要求
1的方法，其中傳送表示所述奇偶運算的所述信息的步驟包括根據所述至少一個奇偶運算形成至少一個第二分組。
5.權利要求
1的方法，其中傳送與所述至少一個第一分組相關聯的所述信息和表示奇偶運算的信息的步驟包括根據與所述至少一個第一分組相關聯的所述信息和表示奇偶運算的所述信息形成至少一個第三分組。
6.一種方法，包括訪問與至少一個第一分組相關聯的信息和表示對與至少一個第一分組和至少一個第二分組相關聯的信息執行的至少一個奇偶運算的信息；以及根據與至少一個第一分組相關聯的信息和表示對與至少一個第一分組和至少一個第二分組相關聯的信息執行的至少一個奇偶運算的信息，確定與所述至少一個第二分組相關聯的信息。
7.權利要求
6的方法，其中訪問與至少一個第一分組相關聯的信息和表示所述至少一個奇偶運算的信息的步驟包括接收包括與至少一個第一分組相關聯的所述信息和表示所述至少一個奇偶運算的信息的至少一個第三分組。
8.權利要求
6的方法，其中訪問與至少一個第一分組相關聯的所述信息和表示對與至少一個第一分組和至少一個第二分組相關聯的信息執行的至少一個奇偶運算的所述信息的步驟包括訪問表示對於與至少一個第一分組和至少一個第二分組相關聯的所述信息執行的至少一個二進位奇偶運算的信息。
9.權利要求
6的方法，包括確定所述至少一個第二分組被丟失或被損壞。
10.權利要求
6的方法，其中確定與所述至少一個第二分組相關聯的所述信息包括確定與所述至少一個第二分組相關聯的至少一個比特。
專利摘要
本發明提供用於重建丟失的或損壞的分組的方法。該方法的一個實施例可包括對於與至少一個第一分組相關聯的信息執行至少一次奇偶運算。方法還可包括傳送與至少一個第一分組相關聯的信息和表示所述至少一次奇偶運算的信息。該方法的另一個實施例包括訪問與至少一個第一分組相關聯的信息和表示對於與至少一個第一分組和至少一個第二分組相關聯的信息執行的至少一次奇偶運算的信息。該方法還可包括根據與至少一個第一分組相關聯的信息和表示對於與至少一個第一分組和至少一個第二分組相關聯的信息執行的至少一次奇偶運算的信息，確定與所述至少一個第二分組有關的信息。
文檔編號H04L1/00GK1992583SQ200510135745
公開日2007年7月4日 申請日期2005年12月29日
發明者黃大威 申請人:朗迅科技公司導出引文BiBTeX, EndNote, RefMan