用於通信系統的多級碼發生器和解碼器的製作方法

2023-05-16 05:17:31

專利名稱：用於通信系統的多級碼發生器和解碼器的製作方法
技術領域：
本發明涉及通信系統內的編碼和解碼，尤其是對數據進行編碼和解碼以考慮通信的數據內的差錯和間隔。
在通信信道上發送者和接收者間的文件傳輸是許多文獻的主題。最好，接收者期望能接收到有一定確信度的發送者在信道上發送的數據的準確副本。當信道沒有完美的確信度時(這是大多數物理可實現系統的情況)，要考慮的問題是如何處理傳輸中的丟失或誤傳。丟失的數據(擦除)比受損的數據(差錯)要更容易處理，因為接收者不能知道何時接收到了錯誤的受損數據。研發了許多差錯糾正編碼以糾正擦除和/或差錯。一般，使用的特定碼是基於數據發送通信的信道的不保真度和發送的數據的性質而經選擇的。例如，在信道有較長時間的不保真度時，最適合該情況的是糾突發差錯碼。在只有較短不頻繁的差錯時，最好是簡單的一致校驗碼。
在選擇編碼時的另一考慮是用於傳輸的協議。在稱為「網際網路」的全球互連網絡中，使用分組協議用於數據傳輸。該協議被稱為網際網路協議或簡稱「IP」。當文件或其他數據塊在IP網絡上傳輸時，它被分成等大小的輸入碼元，且輸入碼元被放入連續的分組。不管輸入碼元是否實際被分成比特流，輸入碼元的「大小」可以用比特測量，其中當輸入碼元從2M的字母表中選出，輸入碼元大小為M比特。在該種基於分組的通信系統中，面向分組的編碼方案比較合適。如果接收者能在網絡內有擦除的情況下恢復原始文件的準確副本，則稱該傳輸是可靠的。在網際網路上，分組丟失經常發生，因為偶發的擁塞引起路由器內的緩衝機制達到其極限，迫使它丟失進入的分組。傳輸期間的擦除保護是許多研究的主題。
傳輸控制協議(「TCP」)是有確認機制的一種普遍使用的點到點分組控制方案。TCP對於一到一的通信性能頗佳，其中發送者和接收者在何時進行傳輸並接收傳輸以及使用的發射機和接收機上取得一致。然而，TCP一般不適合一到多或多到多的通信，其中發送者和接收者獨立地確定何時以及哪裡他們會發送和接收數據。
使用TCP，發送者發送排序的分組，接收者確認每個分組的接收。如果丟失了分組，則沒有確認會被發送回發送者，且發送者會重發分組。分組丟失有多個原因。諸如TCP/IP協議中，確認規則使得分組不是完全失敗地丟失，因為丟失的分組的可以或根據沒有確認或根據來自接收者的顯式請求而被重發。無論哪種方法，確認協議要求來自接收者到發送者的返回信道，該信道在丟失的分組數很大時使用率非常高。
雖然基於確認的協議一般適用於許多應用，且實際上在當前的網際網路上被廣泛使用，但是它們效率不高，且有時對於諸如在給Michael G.Luby的美國專利號6307487內可以完全不可行，該專利題為「Information Additive CodeGenerator and Decoder for Communication Systems」(以下被稱為「Luby I」)。另外，基於確認的協議不適合廣播，其中一個發送者同時發送一個文件到多個用戶。例如，假設發送者在衛星信道上廣播一個文件到多個接收者。每個接收者經歷不同的分組丟失模式。依賴確認數據(或是肯定或是否定)以進行可靠的文件發送的確認協議需要來自每個接收者到發送者的返回信道，要提供這些信道代價極大。另外，這需要複雜並強大的發送者以能合適地處理來自接收者的所有確認數據。另一缺點是如果不同的接收者丟失不同的分組集合，重新廣播只有一些接收者丟失的分組會引起其他接收者無用的重複分組接收。
有時在實際中使用的基於確認協議的另一方法是基於旋轉的協議。旋轉協議將輸入文件分成等長度的輸入碼元，將每個輸入碼元放入分組，並連續循環通過並發送所有分組。該旋轉協議的主要缺點是如果接收者即使丟失了一個分組，則接收者必須等待整個循環才能接收到丟失的那個分組。另一種角度看，即基於旋轉的協議會引起大量的無用複製數據接收。例如，如果接收者接收到來自旋換開始的分組，停止接收一段時間，然後開始在旋轉的開始再次接收，則會接收到大量無用的重複分組。
一種提出的解決以上問題的方案是避免使用基於確認的協議，而是使用前向差錯糾正(FEC)碼，諸如Reed-Solomon碼或Tornado碼，或是信息可加碼的鏈式反應碼以增加可靠性。使用這些編碼，輸出碼元從內容中被生成，且被發送，而不是只發送組成內容的輸入碼元。擦除糾正編碼諸如Reed-Solomon或Tornado編碼為固定長度的內容生成固定數目的輸出碼元。例如，對於K個輸入碼元，可能生成N個輸出碼元。這些N個輸出碼元可以包括K個原始輸入碼元以及N-K個冗餘碼元。例如存儲允許，則伺服器可以為每個內容只計算輸出碼元集合一次，並使用旋轉協議發送輸出碼元。
一些FEC編碼的一個問題在於需要過度的計算功率或存儲器進行操作。另一問題是輸出碼元的數目必須在編碼過程前預先被確定。如果過度估計分組丟失率則會導致低效，且如果過低估計分組丟失率，則會導致失敗。
對於傳統的FEC編碼，可以生成的可能的輸出碼元數與內容被劃分的輸入碼元數是相同量級的。一般，大多數或所有的這些輸出碼元在發送步驟前的預處理步驟內生成。這些輸出碼元的特性為所有的輸入碼元可以從長度等於原始內容或比原始內容稍微長一點的輸出碼元任何子集合內重新生成。
Luby I內描述的實施例(在此被稱為「鏈式反應碼」)提供了一種不同於前向差錯糾正的形式，解決以上問題。對於鏈式反應碼，可以被生成的可能輸出碼元池一般數量要大於輸入碼元的數目，且來自可能池的隨機輸出碼元可以很快地被生成。對於鏈式反應碼，輸出碼元可以按在發送步驟進發基礎上需要的在運行中被生成(on the fly)。鏈式反應碼的特性是內容的所有輸入碼元可以從長度略微長於原始內容的隨機生成輸出碼元集合的子集合中重新生成。
在鏈式反應碼的一實施例中，每個輸出碼元作為一些輸入碼元的異或(XOR，用表示)而獲得。如果K表示總輸入碼元數，則每個輸出碼元平均上是c*ln(K)個輸入碼元的XOR，其中ln(K)是K個自然對數，且c是合適的常量。例如，當K等於60000時，每個輸出碼元平均上是28.68個輸入碼元的XOR，且當K＝10000時，每個輸出碼元平均上是22.86個輸入碼元的XOR。大量的XOR導致輸出碼元更長的計算時間，因為每個該種操作涉及從存儲器獲取數據、實現XOR操作並更新存儲器位置。
鏈式反應碼器生成的輸出碼元的一特性是接收機能一旦接收到足夠的輸出碼元時能恢復原始文件。尤其是，為了以較高概率恢復原始K輸入碼元，接收機需要大致K+A個輸出碼元。比率A/K被稱為「相對接收開銷」。相對接收開銷取決於輸入碼元的數目K，且取決於解碼器的可靠性。例如，在一特定實施例中，且K等於60000，5％的相對接收開銷保證解碼器以至少1-10-8的概率成功地對輸入文件解碼，且當K等於10000時，15％的相對接收開銷保證解碼器相同的成功概率。在一實施例中，鏈式反應碼的相對接收開銷可以由(13*sqrt(k)+200)/K而計算，其中sqrt(K)是輸入碼元K個數目的平方根。在該實施例中，鏈式反應碼的相對接收開銷對於小值的K更大。
在一些實施例中，輸出碼元使用XOR函數進行編碼，連鎖解碼器的主計算操作實現存儲器位置的XOR。該XOR的數目的大小比例與鏈式反應碼器相同。
鏈式反應碼在基於分組網絡的通信非常有用。然而，其計算量也相對較強。例如，在鏈式反應碼的一些特定實施例中，當輸入碼元K的數目為60000時，則計算每個輸出碼元需要平均獲取28.68個隨機選擇的輸入碼元並對其進行XOR。由於伺服器可以同時服務的文件數與每個輸出碼元需要的操作數成反比，則減少每個輸出碼元需要的操作數會有用。例如減少後者例如為3倍，則增加了可以從一個伺服器被同時服務的文件數為3的因子。
鏈式反應碼的另一特性需要接收開銷，該開銷對於給定的目標成功概率相對較大。例如，如上指出，在鏈式反應碼的一些特定實施例中，如果K＝10000，則15％的相對接收開銷保證了至少1-10-8的解碼成功概率。接收開銷對於更小的K要增加。例如，在一些鏈式反應碼的特定實施例中，如果K為1000，則61％的相對接收開銷保證了相同概率的成功解碼。而且，降低目標差錯概率到10-12左右的一數目，如在諸如衛星網絡上的高速內容傳輸的一些應用中要求的，該數目需要更大的接收開銷。
本發明的簡要描述 根據本發明的一實施例，提供了一種用於在通信信道上從源到目的地的數據傳輸編碼的方法。該方法對輸入碼元的排序集合進行操作，並包括從輸入碼元生成多個冗餘碼元。該方法還包括從包括輸入碼元和冗餘碼元的碼元組合集合生成多個輸出碼元，其中可能的輸出碼元數遠遠大於碼元的組合集合內的碼元數，其中從碼元的組合集合內多於一個碼元且從碼元的組合集合內少於所有碼元中生成至少一個輸出碼元，使得輸入碼元的排序集合可以從輸出碼元的任何預定數經重新生成達到期望的準確度。
根據本發明另一實施例，提供了一系統，用於在通信信道上從源到目的地的數據編碼。該系統包括被耦合以接收多個輸入碼元的靜態編碼器，多個輸入碼元從要發送的數據中生成。靜態編碼器包括冗餘碼元發生器，所述發生器基於輸入碼元生成多個冗餘碼元。系統附加地包括被耦合以接收多個輸入碼元和多個冗餘碼元的動態編碼器，動態編碼器包括輸出碼元發生器，所述發生器從包括多個輸入碼元和多個冗餘碼元的碼元組合集合中生成多個輸出碼元，其中可能輸出碼元數遠遠大於組合集合內的碼元數，其中從多於組合集合的碼元且小於組合集合的所有碼元中生成至少一個輸出碼元，使得輸入碼元的排序集合可以從輸出碼元的任何預定數中重新生成達到期望的準確度。
根據本發明的另一實施例，提供了在通信信道上對從源發送的數據進行接收的方法，該方法包括接收輸出碼元，其中每個輸出碼元從輸入碼元和冗餘碼元的組合集合內的至少一個碼元生成，其中至少一個輸出碼元從多於組合集合內的一個碼元且小於組合集合內所有碼元中生成，其中可能的輸出碼元數遠遠大於組合集合內的碼元數，其中輸入碼元來自輸入碼元的排序集合，其中冗餘碼元從輸入碼元中生成。該方法還包括在接收到任何預定數目N輸出碼元時，從N個輸出碼元重新生成組合集合內至少一個碼元的子集，所述子集包括多個重新生成的輸入碼元以及多個重新生成的冗餘碼元。該方法進一步包括如果從N個輸出碼元重新生成碼元的至少一個子集的步驟沒有按照期望的準確度重新生成輸入碼元，則從多個重新生成的冗餘碼元和/或多個重新生成的輸入碼元的一些重新生成至少一些未經重新生成的輸入碼元。
根據本發明的另一實施例，提供一系統用於接收在通信信道上從源發送的數據。該系統包括一接收模塊，所述模塊耦合到通信信道用於接收在通信信道上發送的輸出碼元，其中每個輸出碼元從輸入碼元和冗餘碼元的組合集合內的至少一個碼元生成，其中至少一個輸出碼元從組合集合內多於一個碼元以及組合集合內少於所有碼元中生成，其中可能的輸出碼元數遠遠大於組合集合內的碼元數，其中輸入碼元來自輸入碼元的排序集合，其中冗餘碼元從輸入碼元生成。系統還附加地包括動態解碼器，在接收到輸出碼元的預定數量N後，對來自N個輸出碼元的組合集合內的碼元子集進行解碼，所述組合集合內的碼元子集包括多個解碼後的輸入碼元和多個解碼後的冗餘碼元。系統還包括靜態解碼器，從多個解碼後的冗餘碼元對未經解碼的輸入碼元(如果有的話)的至少一些進行解碼。
根據本發明的另一實施例，提供體現在載波上的計算機數據信號。計算機數據信號包括多個輸出碼元，其中多個輸出碼元表示從包括輸入碼元和冗餘碼元的排序集合的碼元組合集合生成的碼元，其中冗餘碼元從輸入碼元中被生成，其中可能的輸出碼元數遠遠大於碼元組合集合內的碼元數，其中至少一個輸出碼元從碼元的組合集合內多於一個碼元以及碼元組合集合內少於所有碼元中生成，且使得數據信號接收機能從輸出碼元的任何預定數量按期望的準確度重新生成輸入碼元的排序集合。
本發明可以獲得多種好處。例如，在特定實施例中，減少了在信道上傳輸的數據編碼的計算化費。在另一特定實施例中，減少了對該種數據解碼的計算代價。取決於實施例，可以獲得一個或多個該種好處。這些和其它好處在本發明說明中更詳細地描述，尤其在以下。
在此揭示的本發明的性質和優勢的進一步理解可以通過參考規範和所附附圖實現。 附圖的簡要描述

圖1是根據本發明的一實施例的通信系統框圖； 圖2是根據本發明的一實施例的編碼器框圖； 圖3是根據本發明的一實施例生成冗餘碼元方法的簡化框圖； 圖4是根據本發明的一實施例的靜態編碼器基本操作的簡化框圖； 圖5是根據本發明的一實施例的動態編碼器的簡化框圖； 圖6是根據本發明的一實施例的動態編碼器基本操作的簡化框圖； 圖7是根據本發明一實施例的靜態編碼器的簡化框圖； 圖8是根據本發明一實施例的靜態編碼器的基本操作簡化框圖； 圖9是根據靜態編碼器的特定實施例用於計算編碼參數的方法簡化圖； 圖10是根據本發明的另一實施例的靜態編碼器的簡化流圖； 圖11是根據本發明的一實施例的解碼器的簡化框圖； 圖12是根據本發明的一實施例的解碼器操作簡化流圖； 圖13是根據本發明的另一實施例的解碼器操作簡化流圖； 圖14是根據本發明的另一實施例的解碼器操作的簡化流圖； 圖15是根據本發明的一實施例的動態解碼器的簡化框圖； 圖16是根據本發明的一實施例的靜態解碼器的簡化框圖； 圖17是根據本發明的另一實施例的靜態解碼器的簡化框圖； 圖18是根據本發明的實施例的解碼器操作的簡化流圖； 圖19是根據本發明的實施例的解碼器另一操作的簡化流圖； 圖20是根據本發明的一實施例的關聯器的簡化流圖； 圖21是根據本發明的一特定實施例的加權選擇器的簡化框圖； 圖22是根據本發明的實施例被加權選擇器使用的過程簡化流圖。 特定實施例的詳細說明 本揭示參考美國專利號6307487(Luby I)和美國專利號6320520，兩個專利發布給Michael G.Luby，題為「Information Additive Group Code Generatorand Decoder for Communication Systems」(此後被稱為「Luby iII」)，整個揭示在此引入作為各種目的的參考。Luby I和II提供可以用於根據本發明的一些實施例中使用的系統的方法的原理。然而可以理解，本發明不需要這些系統和方法，還可以使用其它的變體、修改或其它。
在此描述的特定實施例中，描述了被稱為「多級編碼」的編碼方案，先對在該描述中使用的各項的意義和範圍作解釋。
多級編碼如在此描述的對數據在多級內進行編碼。一般但不總是，第一級向數據加入預定量的冗餘。第二級然後使用鏈式反應碼或類似的，以從原始數據生成輸出碼元，以及由第一級編碼計算的冗餘碼元。在本發明的一個特定實施例中，接收到的數據首先使用連鎖解碼過程進行解碼。如果該過程不能成功地完整恢復原始數據，則應用第二解碼步驟。
在此描述的一些實施例的好處在於與以下將描述的鏈式反應碼相比，只需要較少的算術操作。一些包括第一級編碼和第二級編碼的特定實施例的其它優勢在於編碼的第一級和編碼的第二級可以在分開的時間和/或分開的設備完成，因此劃分了計算負載。例如如果希望在傳輸時進發地實現編碼的一部分，這會是有利的。特別是，第一級編碼可以在傳輸前實現，而第二級編碼可以與傳輸進發地實現。然而可以理解，在一些實施例中，第一和第二級編碼可以與/或一個設備大致與傳輸進發地進行。許多其它的變體、修改和變化對於領域內的技術人員在閱讀本申請後會明顯。
在多級編碼的實施例中，冗餘碼元在第一級編碼時從輸入文件生成。在這些實施例中，在第二級編碼中，輸出碼元從輸入文件和冗餘碼元的組合中生成。在一些這些實施例中，輸出碼元可以如需要被生成。在第二級包括鏈式反應碼的實施例中，每個輸出碼元可以不用管其它輸出碼元是如何生成的而經生成。一旦生成了，這些輸出碼元然後可以放入分組並發送到其目的地，每個分組包含一個或多個輸出碼元。還可以使用非分組化傳輸技術作為替代。
如在此使用的，「文件」一詞指任何存儲在一個或多個源處且作為一個單元發送到一個或多個目的地的數據。因此，來自文件伺服器或計算機存儲設備的文檔、圖像和文件是可以被發送的「文件」的示例。文件可以是已知的大小(諸如存儲在硬碟上的一兆字節圖像)或可以是未知的大小(諸如從流源輸出獲得的文件)。無論是哪種，文件是輸入碼元的序列，其中每個輸入碼元在文件內有一位置和值。
傳輸是通過信道從一個或多個發送者到一個或多個接收者的數據發送過程以傳送一文件。發送者有時還被稱為編碼器。如果一個發送者通過完美信道連接到任何數量的接收者，如果所有的數據都被正確接收，則接收到的數據可以是輸入文件的準確副本。在此，我們假設信道不是完美的，這一般是實際信道的情況。在許多信道不完美中，兩種在此感興趣的是數據擦除和數據不完整(這可以被視為數據擦除的特殊情況)。數據擦除發生在信道丟失或丟棄數據時。數據不完整發生在當接收者在一些數據已經經過而接收者還未開始接收數據、當接收者在傳輸結束前停止接收數據、當接收者只選擇接收一部分發送的數據和/或當接收者間歇斷地停止並再次開始接收數據。作為數據不完整的示例，移動衛星發送者可能發送表示輸入文件的數據並在接收者在範圍內前開始傳輸。一旦接收者在範圍內，數據可以被接收直到衛星移出範圍，在該點接收者可以重新調整其碟形衛星天線(在該時間內它不接收數據)以開始接收另一移入範圍內的衛星發送的相同輸入文件的數據。如從讀該描述中清楚看出的，數據不完整性是數據擦除的特殊情況，因為接收者可以將數據不完整性(且接收者有相同的問題)視為如同接收者整段時間都在，但信道丟失了在接收者開始接收數據前的所有數據。而且，如在通信系統設計內已知的，可檢測差錯可以被認為等價於簡單地丟棄所有有檢測到差錯的數據塊或碼元的擦除。
在一些通信系統中，接收者接收多個發送者生成的數據，或是使用多個連接的一個發送者的數據。例如為了加快下載，接收者可以同時連接到多於一個發送相同文件的發送者。作為另一示例，在多播傳輸中，多個多波數據流可以被發送以使的接收者能將一個或多個這些流連接以匹配與連接到發送者的信道帶寬匹配的集體傳輸速率。在所有該種情況下，要保證所有發送的數據對於接收者是獨立使用的，即多個源數據在流間不是冗餘的，即使當傳輸速率對於不同流非常不同時或當有任意丟失模式時。
一般，通信信道是連接數據傳輸的發送者和接收者的信道。通信信道可以是實時信道，其中信道在信道獲得數據時將數據從發送者移到接收者，或通信信道可能是存儲信道，該信道在將數據從發送者轉移到接收者過程中存儲一些或所有的數據。後者的示例是盤存儲或其它存儲設備。在該示例中，生成數據的程序或設備可以被認為是發送者，將數據發送到存儲設備。接收者是從存儲設備讀取數據的程序或設備。發送者使用的將數據送到存儲設備的機制、存儲設備本身以及接收者使用的從存儲設備獲得數據的機制共同形成了信道。如果這些機制或存儲設備會丟失數據，則它可以被視為通信信道內的數據擦除。
當發送者和接收者為通信信道隔開，且該通信信道內碼元被擦除，則最好不要發送輸入文件的準確副本，而是發送從輸入文件生成的數據，該數據能幫助恢復擦除。編碼器是處理該任務的電路、設備模塊或編碼片段。一種觀看編碼器操作的方式是編碼器從輸入碼元生成輸出碼元，其中輸入碼元值序列表示輸入文件。每個輸入碼元因此在輸入文件內有一位置和一值。解碼器是電路、設備、模塊或編碼片段，它們從接收者接收到的輸出碼元重建輸入碼元。在多級編碼中，編碼器和解碼器進一步被分成子模塊，每個實現不同的任務。
在多級編碼系統的實施例中，編碼器和解碼器可以被進一步分成子模塊，每個實現不同的任務。例如，在一些實施例中，編碼器包括在此被稱為靜態編碼器和動態編碼器。如在此使用的，「靜態」編碼器是從輸入碼元集合生成多個冗餘碼元的編碼器，其中冗餘碼元數在編碼前被確定。靜態編碼碼示例包括Reed-Solomon編碼、Tornado編碼、漢明碼、低密度一致校驗(LDPC)編碼等。「靜態解碼器」一詞在此被稱為解碼器，該解碼器可以對由靜態編碼器編碼的數據解碼。
如在此使用的，「動態編碼器」是從輸入碼元集合生成輸出碼元的編碼器，其中可能的輸出碼元的數量級大於輸入碼元數，且其中要生成的輸出碼元數不需要是固定的。動態編碼器的一例是鏈式反應碼器，諸如Luby I和Luby II內描述的編碼器。「動態解碼器」一詞在此用於指可以對由動態編碼器編碼的數據解碼的解碼器。
多級編碼的實施例不受到任何特定類型的輸入碼元的限制。一般，輸入碼元的值從對一些正整數M的2M個碼元的字母表中被選擇。在該情況下，輸入碼元可以用來自輸入文件的M比特數據的序列表示。M的值一般基於例如使用的應用程式、通信信道和/或輸出碼元的大小而確定。另外，輸出碼元的大小還經常基於應用、信道和/或輸入碼元的大小而經確定。在一些情況下，如果輸出碼元值和輸入碼元值大小相同(即用相同數量的比特表示，或從相同的字母表選出)，則編碼過程可以被簡化。如果是該情況，則輸入碼元值大小在輸出碼元值受限時受到限制。例如，可能期望將輸出碼元放入有限大小的分組內。如果與輸出碼元相關的密鑰的一些數據為了在接收機處恢復密鑰而被發送，則輸出碼元最好較小，以在一個分組內包括輸出碼元值和關於密鑰的數據。
作為一例，如果輸入文件是多兆字節的文件，則輸入文件可能被分成幾千、幾萬或幾百萬的輸入碼元，每個輸入碼元對幾千、幾百或幾個字節編碼。作為另一示例，對於基於分組的網際網路信道，1024位元組大小的有效負荷分組可能比較合適(一字節為8比特)。在該示例中，假設每個分組包含一個輸出碼元和8位元組輔助信息，輸出碼元大小為8128比特((1024-8)*8)比較合適。因此，輸入碼元大小可以被選為M＝(1024-8)*8，即8128比特。作為另一示例，一些衛星系統使用MPEG分組標準，其中每個分組的有效負荷包括188個字節。在該示例中，假設每個分組包含一個輸出碼元和4位元組輔助信息，則輸出碼元大小為1472比特((188-4)*8)比較合適。因此，輸入碼元大小可以被選為M＝(188-4)*8，即1472比特。在使用多級編碼的通用通信系統內，諸如輸入碼元大小(即M為輸入碼元編碼的比特數)的應用專用參數可以是應用設定的變量。
每個輸出碼元有一個值。在一個以下考慮的最優實施例中，每個輸出碼元還與一標識符相關，該標識符被稱為「密鑰」。最好，每個輸出碼元的密鑰可以簡單地由接受者確定以允許接收者能互相區別輸出碼元。最好，一輸出碼元的密鑰不同於其他輸出碼元的密鑰。在本領域內有許多各種形式的密鑰。例如，Luby I描述了各種形式的可以在本發明的實施例中使用的密鑰。
多級編碼在期望有數據擦除或接收者不在傳輸正好開始和結束的時候開始時特別有用。後者的情況在此被稱為「數據不完整性」。關於擦除事件，多級編碼共享許多在Luby I內描述的鏈式反應碼的好處。特別是，多級輸出碼元是信息可加的，所以任何合適數量的分組可以被用於以一定準確性恢復輸入文件。這些條件不會負面影響使用多級編碼的通信過程，因為用多級編碼生成的輸出碼元是信息附加的。例如，如果因為引起數據擦除的噪聲突發而丟失了一百個分組，則可以在突發後發送額外的一百個分組以替代擦除的分組的丟失。如果因為由於接收機沒有調諧到發射機開始發送時的發射機而丟失了成千個分組，則接收機可以從任何其他傳輸時間段甚至從另一發射機開始重新接收這些成千個分組。使用多級編碼，接收機不限於接收任何特定分組集合，所以它可以從一個發射機接收一些分組，切換到另一發射機，丟失一些分組，失去給定傳輸的開始或結束，且仍恢復輸入文件。加入並離開傳輸而不需要接收機-發射機協調的能力可以幫助簡化通信過程。
在一些實施例中，使用多級編碼發送文件可以包括從輸入文件生成、形成或抽取輸入碼元，計算冗餘碼元、將輸入和冗餘碼元編碼成為一個或多個輸出碼元，其中每個輸出碼元基於其獨立於所有其他輸出碼元的密鑰而經生成，並將輸出碼元在信道上發送到一個或多個接收者。另外，在一些實施例中，使用多級編碼接收(重建)輸入文件的副本可以包括從一個或多個數據流接收輸出碼元的一些集合或子集，並從值和接收到的輸出碼元的密鑰對輸入碼元解碼。
本發明的各方面現在將參考附圖進行描述。
系統概述 圖1是使用多級編碼的通信系統100的框圖。在通信系統100內，向輸入碼元發生器110提供輸入文件101或輸入流105。輸入碼元發生器110從輸入文件或流生成一個或多個輸入碼元的序列(IS(0)，IS(1)，IS(2)，...)，每個輸入碼元有值和位置(在圖1內用括號內的整數表示)。如上所述，對於輸入碼元的可能值，即其字母表一般是2M個碼元，使得每個輸入碼元編碼為輸入文件的M個比特。值M一般通過使用通信系統100確定，但通用系統可以包括輸入碼元發生器110的碼元大小輸入，使得M可以隨每次使用而改變。輸入碼元發生器110的輸出可以被提供給編碼器115。
靜態編碼器130生成靜態密鑰流S0，S1...。生成的靜態密鑰數一般是有限的，且取決於編碼器115的特定實施例。靜態密鑰的生成在以下將接著更詳細地描述。動態密鑰發生器120為每個要由編碼器115生成的輸出碼元生成一動態密鑰。每個動態密鑰被生成，使得同一輸入文件的動態密鑰的很大部分是唯一的。例如，Luby I描述可以使用的密鑰發生器的實施例。動態密鑰發生器120和靜態密鑰發生器130的輸出被提供給編碼器115。
從動態密鑰發生器120提供的每個密鑰I，編碼器115從輸入碼元發生器提供的輸入碼元生成輸出碼元，其值為B(I)。編碼器115的操作在以下將詳述。每個輸出碼元的值基於其密鑰、一個或多個輸入碼元的一些函數以及可能從輸入碼元經計算的一個或多個冗餘碼元被生成。引起特定輸出碼元的輸入碼元和冗餘碼元的集合在此被稱為輸出碼元的「關聯碼元」或只是其「關聯」。函數(「值函數」)的選擇以及相關是根據以下更詳細描述的過程完成的。一般，但不總是，M對於輸入和輸出碼元是相同的，即它們都編碼為相同數目的比特。
在一些實施例中，輸入碼元數K為編碼器115用於選擇關聯。如果K事先未知，諸如輸入是流文件，則K可以只是一個估計。值K還可以為編碼器115用於為輸入碼元和任何由編碼器115生成的中間碼元分配存儲。
編碼器115提供輸出碼元給發射模塊140。發射模塊140還被提供了來自動態密鑰發生器120的每個該種輸出碼元的密鑰。發射模塊140發送輸出碼元，且取決於使用的密鑰方法，發送模塊140可能在信道145上將一些關於發送的輸出碼元的密鑰的一些數據發送到接收模塊150。信道145被假設為擦除信道，但這不是通信系統100的合適操作的需要。模塊140、145和150還可以是任何合適的硬體組件、軟體組件、物理媒質或其任何組合，只要發射模塊140用於將輸出碼元和任何關於密鑰需要的數據發送到信道145，且接收模塊150用於從信道145接收碼元，以及潛在的一些關於其密鑰的數據。K的值如果被用於確定關聯，則可以在信道145上被發送，或可以事先按照編碼器115和解碼器155的同意而被設定。
如上解釋的，信道145可以是實時信道，諸如通過網際網路的路徑或從電視發射機到電視接收機或從一點到另一點的電話連接的廣播鏈路，或信道145可以是存儲信道，諸如CD-ROM、盤驅動、全球資訊網站等。信道145甚至可以是實時信道和存儲信道的組合，諸如當個人將輸入文件在電話線上從個人計算機發送到網際網路服務提供商(ISP)時形成的信道，輸入文件被存儲在全球資訊網伺服器上，接著通過網際網路被發送到接收者。
由於信道145被假設是擦除信道，通信系統100不假設從接收模塊150出來的輸出碼元和進入發射模塊140的輸出碼元間的一對一對應。實際上，當信道145包括分組網絡時，通信系統100可能甚至不能假設在通過信道145時保留了任何兩個或多個分組的相對順序。因此，輸出碼元的密鑰使用一個或多個上述的密鑰方案被確定，且不一定按輸出碼元離開接收模塊150的順序確定。
接收模塊150將輸出碼元提供給解碼器155，且任何數據接收模塊150接收這些輸出碼元的密鑰，這些密鑰被提供給動態密鑰重新發生器160。動態密鑰重新發生器160重新生成接收到的輸出碼元的動態密鑰並將這些動態密鑰提供給解碼器155。靜態密鑰發生器163重新生成靜態密鑰S0，S1，...並將其提供給解碼器155。靜態密鑰發生器訪問在編碼和解碼過程中都使用的隨機數發生器135。如果隨機數在該種設備上生成，則這可以是以對相同物理設備的訪問形式，或是對用於生成隨機數的相同算法的訪問形式以獲得相同的行為。解碼器155使用動態密鑰發生器160和靜態密鑰發生器163提供的密鑰連同對應的輸出碼元以恢復輸入碼元(同樣IS(0)，IS(1)，IS(2)，...)。解碼器155將恢復的輸入碼元提供給輸入文件組裝器165，該組裝器生成輸入文件101的副本170或輸入流105。
編碼器 圖2是圖1內示出的編碼器115的一個特定實施例框圖。編碼器115包括靜態編碼器210、動態編碼器220以及冗餘計算器230。靜態編碼器210接收以下輸入a)輸入碼元發生器110提供的原始輸入碼元(IS(0)，IS(1)，...，IS(K-1))並存儲在輸入碼元緩衝器205內；b)原始輸入碼元數K；c)由靜態密鑰發生器130提供的靜態密鑰S0，S1，...；以及d)冗餘碼元數R。在接收到這輸入後，靜態編碼器205計算R個冗餘碼元RE(0)，RE(1)，...，RE(R-1)，如下描述。一般但不總是冗餘碼元與輸入碼元有相同大小。在一特定實施例中，靜態編碼器210生成的冗餘碼元被存儲在輸入碼元緩衝器205內。輸入碼元緩衝器205可以只是邏輯的，即文件可以物理地被存儲在一個地方，且碼元緩衝器205內的輸入碼元的位置只能是原始文件內的這些碼元位置的重命名。
動態編碼器接收輸入碼元和冗餘碼元，且如以下詳述地生成輸出碼元。在一實施例中，其中冗餘碼元被存儲到輸入碼元緩衝器205內，動態編碼器220從輸入碼元緩衝器205接收輸入碼元和冗餘碼元。
冗餘計算器230從K個輸入碼元計算R個冗餘碼元。該計算在以下詳述。
在生成輸出碼元的速度是關鍵因素的情況下，輸入文件可以使用靜態編碼器205被編碼並在輸出碼元傳輸開始前存儲在中間設備上。該設備可以是例如附加的位於不同於與動態編碼器220的物理位置的存儲設備，它可以被包括在與動態編碼器220等相同的物理設備內等。在使用動態編碼器220編碼前文件使用靜態編碼器205被編碼的情況下，實現動態編碼器220的計算設備不需要將資源用於靜態編碼。因此，它可以將資源更多地用於動態編碼以例如增加輸入文件的生成輸出碼元速度、生成其它文件的輸出碼元、實現其他任務等。靜態編碼是否能或應該在動態編碼前實現取決於特定的實現。
靜態編碼器概覽 靜態編碼器210的一般操作參考圖3和4描述。圖3是說明靜態編碼方法的一實施例的簡化流程圖。在步驟305，變量j跟蹤已生成多少冗餘碼元，該值被設定為零。然後，在步驟310，第一冗餘碼元RE(0)作為輸入碼元IS(0)，...，IS(K-1)的至少一些的F0的子數被計算。然後在步驟315，變量j遞增。接著，在步驟320，測試是否所有的冗餘碼元均被生成了(即j是否大於R-1？)。如果是，則流程結束。否則，流程進行到步驟325。在步驟325，RE(j)作為輸入碼元IS(0)，...，IS(K-1)和先前生成的冗餘碼元RE(0)，...，RE(j-1)的函數Fj經計算，其中Fj不需要是取決於每個輸入碼元或每個冗餘碼元的函數。步驟315、320和325經重複直到已計算了R個冗餘碼元。
回到圖1和2，在一些實施例中，靜態編碼器210從靜態密鑰發生器130接收一個或多個靜態密鑰S0，S1，...。在這些實施例中，靜態編碼器210使用靜態密鑰以確定一些或所有的函數F0，F1，...Fj-1。例如，靜態S0可以用於確定函數F0，靜態密鑰S1可以被用於確定函數F1等。或一個或多個靜態密鑰S0，S1，...可以被用於確定函數F0，一個或多個靜態密鑰S0，S1，...可以用於確定函數F1等。在其他實施例中，不需要靜態密鑰，因此不需要靜態密鑰發生器130。
回到圖2和3，在一些實施例中，靜態編碼器210生成的冗餘碼元可以被存儲在輸入碼元緩衝器205。圖4是靜態編碼器210的一實施例的操作的簡化說明。尤其是，靜態編碼器210用從輸入碼元緩衝器205接收到的輸入碼元IS(0)，...，IS(K-1)，RE(0)，...，RE(j-1)的函數Fj生成冗餘碼元RE(j)，並將其存儲回輸入碼元緩衝器205。函數F0，F1，...FR-1的準確形式取決於特定應用。一般但不總是，函數F0，F1，...FR-1包括一些或所有它們對應的參變量的異或。如上描述，這些函數可以或實際上可能不能使用圖1的靜態密鑰發生器130生成靜態密鑰。例如，在以下描述的一個特定實施例，第一幾個函數實現漢明碼且不使用靜態密鑰S0，S1，...，其中剩餘的函數實現低密度一致校驗編碼並顯式使用靜態密鑰。
動態編碼器概覽 回到圖2，動態編碼器220接收輸入碼元IS(0)，...，IS(K-1)以及冗餘碼元RE(0)，...，RE(R-1)以及要生成的每個輸出碼元的密鑰I。該集合包括原始輸入碼元及冗餘碼元，此後會被稱為「動態輸入碼元」集合。圖5是動態編碼器的一實施例的簡化框圖。該編碼器類似於Luby I內描述的一實施例。Luby I描述該種編碼器的操作的進一步細節。
動態編碼器500包括加權選擇器510、關聯器515、值函數選擇器520和計算器525。如圖5示出，K+R個動態輸入碼元被存儲在動態碼元緩衝器505內。在一實施例中，動態碼元緩衝器505是圖2的輸入碼元緩衝器205。在另一實施例中，動態碼元緩衝器505與輸入碼元緩衝器205分開。動態密鑰I(由圖1示出的動態密鑰發生器120提供)是加權選擇器510、關聯器515和值函數選擇器520的輸入。動態輸入碼元數K+R被提供給這些三個組件510、515和520。計算器525經耦合以接收來自加權選擇器510、關聯器515和值函數選擇器520的輸出並接收來自動態碼元緩衝器505的碼元。計算器525生成輸出碼元值。應理解可以使用圖5內示出的元件的等價安排，且這裡只是根據本發明的編碼器的一個示例。例如，Luby I和Luby II描述其他可以用於根據本發明其他實施例的編碼器。
在操作中，從輸入碼元緩衝器205接收K+R個動態輸入碼元，並存儲在動態輸入碼元緩衝器505內。如上解釋的，每個動態輸入碼元有一位置(例如，輸入碼元的位置可以是其在輸入文件內的原始位置)和值。動態輸入碼元不需要按其相應的順序存儲在動態輸入碼元緩衝器505內，只要能確定存儲的動態輸入碼元的位置。
使用密鑰I和動態輸入碼元數目K+R，加權選擇器510確定是要與帶有密鑰I的輸出碼元的「關聯」的動態輸入碼元數目W(I)。使用密鑰I、加權W(I)以及動態輸入碼元數K+R，關聯器515確定與輸出碼元相關的動態輸入碼元位置列表AL(I)。應理解如果關聯器515能事先在不知道W(I)情況下生成AL(I)，則W(I)不需要分開或顯式地計算。一旦生成了AL(I)，則W(I)可以被簡單地確定，因為它是AL(I)內的關聯的數目。
並聯器515是一映射，它接收輸入密鑰I、數N以及數t並生成0到N-1間的整數的列表X(0)，...，X(t-1)。最好，這些整數不同且在其範圍上均勻分布。例如，在圖5的動態編碼器500情況下，N等於K+R，t等於W(I)，且AL(I)是列表X(0)，...，X(t-1)。
關聯器515給出的映射可以採用各種形式。它可以訪問真隨機或偽隨機比特源以使其輸出隨機。然而，對於相同密鑰I、相同N和相同t，它應被選擇生成編碼器和解碼器相同的輸出。為了滿足該要求，可以使用以密鑰I為種子的編碼器和解碼器生成偽隨機序列。取代偽隨機序列，可以使用真隨機序列以計算輸出，但為了使之有用，用於生成輸出的隨機序列需要被傳遞到解碼器。
再回到圖5，一旦已知I、W(I)和A(I)，輸出碼元的值B(I)由計算器525基於值函數F(I)經計算。合適值函數的一特點是它允許由AL(I)指明的關聯的值從輸出碼元值B(I)和由AL(I)指明的其他W(I)-1個關聯的值而被確定。在該步驟內使用的一個最優值函數是XOR值函數，因為它滿足該特性，它容易計算並容易求反。然而，還可以使用其他合適的值函數。例如Luby II描述了其他可以使用的合適值函數。
如果被使用，值函數選擇器520從密鑰I和K+R確定值函數F(I)。在一變體中，值函數F(I)對於所有I是相同的值函數F。在該變體，值函數選擇器器520不需要，且計算器525可以用值函數F經配置。例如，值函數可以對於所有I為XOR，即輸出碼元值是所有其關聯的值的XOR(異OR)。
對於每個密鑰I，加權選擇器510從I和K+R確定加權W(I)。在一變體中，加權選擇器510通過使用密鑰選擇W(I)，以首先生成隨機查找數，然後使用該數字在存儲其中或由加權選擇器510可訪問的分布表格內查找W(I)的值。如何形成和訪問該種分布表格在以下進行詳細描述。一旦加權選擇器510確定了W(I)，該值被提供給關聯器515和計算器525。
使用列表AL(I)、加權W(I)和值函數選擇器520提供的值函數F(I)或預選的值函數F，計算器525訪問動態輸入碼元緩衝器505內由AL(I)引用的W(I)個動態輸入碼元以為當前輸出碼元計算值B(I)。計算AL(I)的過程示例如下，但可以使用其他的合適過程。最好，過程給予每個輸入碼元大致相等的機會被選擇為給定輸出碼元的關聯，且選擇方式使得如果解碼器沒有可用的AL(I)，則解碼器可以複製。
動態解碼器500然後輸出B(I)。實際上，動態解碼器500實現圖6內說明的行為，即生成輸出碼元值B(I)作為選擇的輸入碼元的一些值函數。在示出的示例中，值函數為XOR，輸出碼元的加權W(I)為3，關聯聯的動態輸入碼元(關聯)在位置0、2和K+R-2且有相應的值IS(0)、IS(2)以及RE(R-2)。因此對於I的值，輸出碼元被計算為 B(I)＝IS(0)IS(2)RE(R-2) 在使用XOR值函數情況下，可以理解冗餘碼元有與原始碼元IS(0)，...，IS(K-1)相同的比特數，且這些依次也與輸出碼元有相同的比特數。
生成的輸出碼元然後被發送並如上述被接收。在此，假設可能丟失一些輸出碼元或可能排序出錯，或它們可能由一個或多個編碼器生成。然而假設被接收到的輸出碼元還接收到其密鑰和其值B(I)準確度保證的指示。如圖1示出，這些接收到的輸出碼元，連同從其動態密鑰發生器160、值K+R以及靜態密鑰發生器163生成的靜態密鑰S0，S1，...的指示重建的對應密鑰是解碼器155的輸入。
靜態編碼器 靜態編碼器的主要功能是向原始數據加入冗餘信息，使得在有擦除情況下有可能恢復原始數據。該種冗餘信息可以幫助解碼器恢復動態解碼器不能恢復的輸入碼元。在一般的應用中，靜態編碼器在有擦除情況下保證能恢復到期望準確度需要的冗餘碼元數目的意義上是有效的，以及/或在編碼過程和/或解碼過程的計算代價上是有效的。例如，對於給定目標擦除率p，該擦除率在應用中由動態解碼器的性能決定，目標是使得冗餘碼元數R儘可能地小，而同時保證如果最多丟失數據的p部分時能快速恢復原始數據。滿足該要求的一類碼為LDPC碼，這對於領域內的技術人員是已知的。雖然這些碼可以在許多情況下恢復原始數據，但在不經常的情況下，這些碼能恢復除了兩三個原始輸入碼元外的所有碼元。因此在一些實施例中，在LDPC編碼前，輸入數據首先使用在有兩三個擦除情況下可以恢復原始數據的編碼。第一編碼生成第一組冗餘碼元。在第一編碼後，多個原始碼元和第一組冗餘碼元使用LDPC編碼器經編碼。擴展的漢明碼對於本領域內的技術人員是眾知的，且在以下簡要描述，適合於第一層的編碼的目的，因為它能在有兩三個擦除的情況下恢復原始數據，且通過加入很小量的冗餘碼元而完成。可以理解還可以使用其他類型的編碼。例如，在一些應用中，可以接受恢復了除兩三個輸入碼元外的所有碼元。因此，在該種應用中，LDPC碼單獨就足夠了。另外，其他類型的編碼對於特定應用可能也是合適的，諸如Reed-Solomon、Tornado等。因此，可以理解根據本發明的其他實施例可以單獨使用許多類型的編碼或組合地使用。
圖7是根據本發明的靜態編碼器的一特定實施例簡化框圖。靜態編碼器600包括參數計算器605、漢明編碼器610以及低密度一致校驗(LDPC)編碼器620。參數計算器605接收K個輸入碼元和要生成的R個冗餘碼元，並生成參數D和E。D指示由漢明編碼器610生成的冗餘碼元數，E指示由LDPC編碼器620生成的冗餘碼元數。參數D提供給漢明編碼器610，參數E被提供給LDPC編碼器620。
漢明編碼器610經耦合以從輸入碼元緩衝器625接收輸入碼元IS(0)，...，IS(K-1)、輸入碼元數K以及參數D。作為響應，漢明編碼器610根據漢明碼生成D+1個冗餘碼元HA(0)，HA(q)，...，HA(D)。在一實施例中，輸入碼元緩衝器625是圖2的輸入碼元緩衝器205。漢明編碼過程向原始K個輸入碼元加入D+1個冗餘碼元，其中D是使得2D-D-1≥K的最小數。如本領域內的技術人員眾知的，冗餘碼元的選擇是使得對於所有的輸入碼元的可能設置，使得它們不是全為零，至少在多個輸入碼元以及對應的冗餘碼元中的至少四個不為零。該特性保證了至少能糾正三個擦除。漢明編碼器610可以以任何領域內的技術人員已知的差錯糾正和擦除糾正編碼的多種方式實現。
LDPC編碼器620經耦合以接收輸入碼元IS(0)，...，IS(K-1)、輸入碼元數K+D+1和經漢明編碼的冗餘碼元、參數E以及靜態密鑰S0，S1，...。作為響應，LDPC編碼器620根據LDPC編碼生成E個冗餘碼元。LDPC編碼器計算的冗餘碼元的數目E等於R-D-1，其中R是冗餘碼元數目。如本領域內的技術人員已知的，有多種使用LDPC碼對信息編碼的方式。LDPC編碼用圖形結構的方式描述，該圖形結構包括消息節點集合、校驗節點集合以及連接消息節點到校驗節點的邊。有效LDPC碼字集合是使得對於每個校驗節點，相鄰消息節點的XOR為零的消息節點的這些設置的集合。在一些應用中，最好消息節點有相同的度，即連接到相同數目的校驗節點，這樣簡化了編碼器的實現，且使得解碼器的差錯概率計算變得更簡單。在本發明的一特定實施例中，每個消息節點連接到的校驗節點的數目為四。已經知道該數目提供在編碼器的運行時間/計算負載以及解碼器的失敗概率間可接受的折衷。而且，已知較佳地是隨機地在校驗節點集合間隨機選擇與給定消息節點相鄰的校驗節點。LDPC編碼器620可以以領域內技術人員已知的差錯糾正和擦除糾正編碼的任何一種方式實現。
圖8說明使用圖7示出的靜態編碼器的本發明一實施例操作。尤其是，漢明編碼器610從輸入碼元緩衝器205(圖2)接收輸入碼元，並生成D+1個經漢明編碼的冗餘碼元，這些碼元被存儲在輸入碼元緩衝器205內。然後，LDPC編碼器620從輸入碼元緩衝器205接受輸入碼元和D+1個經漢明編碼的冗餘碼元，並生成E個LDPC經編碼的冗餘碼元，這些碼元被存儲在輸入碼元緩衝器205內。
如上所述，在一些實施例中，LDPC編碼器620接收圖1的靜態密鑰發生器130生成的靜態密鑰S0，S1，...。在一實施例中，靜態密鑰發生器130是隨機數發生器，它在接收到種子(seed)後生成隨機查詢數序列(靜態密鑰S0，S1，...)。種子可以取各形式。例如，可以是真隨機數發生器的值。作為另一例，種子可以是從CPU時鐘以確定方式獲得的字符串。無論種子是什麼，它應被傳遞到解碼器，使得相同的靜態密鑰序列可以由解碼器生成。在許多應用中，比較有利的是種子不太大。在許多應用中，種子是32比特整數，或64比特整數。
在圖6內說明的靜態編碼器600的一特定實施例中，參數D作為使得2D-D-1大於或等於輸入碼元數K的最大整數而被計算。另外，參數E被計算為R-D-1。圖9是說明參數計算器的一實施例的簡化流程圖，諸如圖7的參數計算器605，該計算器如上所述計算參數D和E。首先，在步驟705，參數D被初始化為一。然後在步驟710，確定2D-D-1是否小於K。如果不是，則流程進行到步驟730。如果是，則流程進行到步驟720，其中遞增參數D。然後，流回到步驟710。一旦D經確定，則在步驟730，參數E被計數為R-D-1。
再回到圖1，在一些特定應用中，在信道145上要發送的文件或流相當小。例如，輸入文件可以是較短的音頻消息或包括幾萬字節的Web網頁內容。則上述的靜態編碼器的特定實施例可能在該種情況下性能次於最優。例如，一些上述的實施例會導致存儲器和處理器速度的低效使用，因此減緩了數據的重建。而且，上述的一些實施例可能需要更大的接收開銷以在由系統的用戶設定的可靠性參數內重建數據。另外，一些上述的實施例可能導致重建的數據的可靠性小於所期望的。
已知解碼器的失敗概率當輸入碼元數目減少時增加。而且還已知這很大程度上是因為如果原始內容相對較小，則編碼過程沒有建立關於原始內容的足夠信息。因此，可以使用編碼器的另一實施例，它生成可以傳遞更多關於原始碼元的信息的冗餘碼元。圖10是根據本發明的一實施例的該種編碼器的簡化流程，以下將描述。
首先在步驟805，變量i被初始化為零。變量i跟蹤已經生成的冗餘碼元數。在步驟810，數字t作為大於或等於K/2的最小奇數而經計算。在步驟815，值P1，P2，...，Pt基於K、t和靜態密鑰Si而經生成。值P1，P2，...，Pt指明用於生成冗餘碼元的輸入碼元位置。在一特定實施例中，，諸如圖5的關聯器515的關聯器被用於生成P1，P2，...，Pt。特別是，值t可以作為W(I)輸入被提供，值K可以作為K+R個輸入被提供，且靜態密鑰Si可以作為密鑰I輸入被提供。值得注意的是許多不同的t的值會生成類似的編碼效果，且因此特定的選擇只是示例。
在步驟820，RE(i)的值被計算為值IS(P)1，IS(P2)，...，IS(Pt)的XOR。在步驟825，變量i遞增一以準備計算下一冗餘碼元，且在步驟830，確定是否計算了所有冗餘碼元。如果沒有，流程返回步驟815。
解碼器概述 圖11是說明根據本發明的解碼器的一實施例的簡化框圖。解碼器900可以例如用於實現圖1的解碼器155。
解碼器900包括動態解碼器905和靜態解碼器910。動態解碼器905從圖1內的接收模塊150接收輸出碼元B(Ia)，B(Ib)，...且從動態密鑰重新發生器160接收動態密鑰Ia，Ib，Ic，...。在接收到這些數據時，動態解碼器905試圖重建輸入碼元IS(0)，...，IS(K-1)以及冗餘碼元RE(0)，...，RE(R-1)。本發明的一些實施例的優勢在於動態解碼器905不需要完成所有輸入碼元的解碼。而是靜態解碼器910可以用於對動態解碼器905未恢復的輸入碼元進行解碼。
動態解碼器905恢復的輸入碼元和冗餘碼元被存儲在重建緩衝器915內。在完成動態解碼後，靜態解碼器910試圖恢復任何動態解碼器905未恢復的輸入碼元，如果有的話。尤其是，靜態解碼器910從重建緩衝器915接收輸入碼元和冗餘碼元。另外，靜態解碼器910從靜態密鑰發生器130(圖1)(如果使用的話)接收靜態密鑰S0，S1，...。回到圖1，在一特定實施例中，靜態密鑰可以通過將公共種子通過通信信道145傳遞到隨機數發生器135而經重新生成，該發生器135驅動靜態密鑰發生器130。恢復的輸入碼元被提供給輸入文件組裝器165。
圖12是根據本發明說明用於解碼的方法的一實施例簡化流圖。在步驟1005，Q個輸出碼元由解碼器接收。Q的值可以取決於輸入碼元數和使用的特定動態解碼器。Q的值還可以取決於解碼器能恢復輸入碼元的期望準確度。例如，如果期望解碼器以高概率恢復所有的輸入碼元，則Q應被選為大於輸入碼元數。特別是在一些應用中，當輸入碼元數很大，Q可以比原始輸入碼元數大不到3％。在其他應用中，當輸入碼元數較小，則Q可以比輸入碼元數至少大10％。尤其是Q可以被選為輸入碼元的數K加上數A，其中A被選擇保證解碼器可以以較高的概率重新生成所有的輸入碼元。確定數字A在以下描述。如果對於解碼器不能對所有的輸入碼元解碼(要麼有時要麼一直)是可接受的，則Q可以小於K+A，等於K或甚至小於K。很清楚地是，整個編碼系統的一個目的經常是儘可能地減少Q，而同時以期望的準確度維持較佳概率保證解碼器過程的成功。
在步驟1010，動態解碼器905從Q個接收到的輸出碼元重新生成輸入碼元和冗餘碼元。可以理解，步驟1005和1010可以大致進發地實現。例如，動態編碼器905可以在解碼器接收Q個輸出碼元前開始重新生成輸入碼元和冗餘碼元。
在動態解碼器905處理了Q個輸出碼元後，可以確定輸入碼元是否被恢復到一定的準確度。期望的準確度可以是例如所有的輸入碼元或小於所有輸入碼元的一定數目、百分比等。如果是，則流程結束。如果不是，則流程進行到步驟1020。在步驟1020，靜態解碼器910試圖恢復任何動態解碼器905不能恢復的輸入碼元。在靜態編碼器910處理了動態編碼器恢復的輸入碼元以及冗餘碼元後，流程結束。
圖13是根據本發明用於解碼的方法的另一實施例的簡化流圖。該實施例類似於關於圖11的描述，且包括相同的步驟1005、1010、1015和1025。但是，在步驟1025後，流程進行到步驟1030，其中確定輸入碼元是否被恢復到期望的準確度。如果是，則流程結束。如果不是，則流程進行到步驟1035。在步驟1035，接收一個或多個附加輸出碼元。然後，流程回到步驟1010，使得動態解碼器905和/或靜態解碼器910可以試圖恢復剩餘的未經恢復的輸入碼元。
圖14是根據本發明用於解碼方法的另一實施例的簡化流圖。在步驟1055，由解碼器接收輸出碼元，且在步驟1060，動態解碼器905從接收到的輸出碼元重新生成輸入碼元和冗餘碼元。然後在步驟1065，確定是否應中止動態解碼。該確定是基於處理的輸出碼元數、恢復的輸入碼元數、附加輸入碼元正在被恢復的當前速率、處理輸出碼元花費的時間等中的一個或多個。
需要理解的是步驟1055、1060和1065可以大致進發地實現。例如，動態解碼器905可以在解碼器繼續接收輸出碼元時開始重新生成輸入碼元和冗餘碼元。另外，評估是否停止動態解碼過程可以在正在接收輸出碼元和/或輸出碼元正在被動態解碼器905處理時周期性地實現。
在步驟1065，如果確定不停止動態解碼，則流程回到步驟1055。但是，如果在步驟1065，確定結束動態解碼，則流程進行到步驟1070。在步驟1070，確定輸入碼元是否被恢復到期望的準確度。如果是，則流程結束。如果不是，則流程繼續進行到步驟1075。在步驟1075，靜態解碼器910試圖恢復任何動態解碼器905不能恢復的輸入碼元。在靜態解碼器910處理了由動態編碼器905恢復的輸入碼元和冗餘碼元後，流程結束。
動態解碼器 圖15根據本發明示出動態解碼器一實施例。動態解碼器1100包括如圖5內示出的動態解碼器500類似的元件。解碼器1100類似於Luby I和Luby II內描述的連鎖解碼器的實施例。動態解碼器1100包括加權選擇器510、關聯器515，值函數選擇器520、輸出碼元緩衝器1105、縮減器1115、重建器1120以及重建緩衝器1125。如同編碼器，值函數選擇器520以及在輸出碼元緩衝器1105內分配給存儲值函數的描述的空間是可選的，且如果值函數對於所有的輸出碼元相同，則可以不使用。示出重建緩衝器1125的幾項，一些輸入碼元經重建，其他仍未知，用問號表示。例如，在圖15內，在位置0、2、5、6和K-1的輸入碼元以及在位置0和2的冗餘碼元已經被恢復了，且在位置1、3和4以及位置1處的冗餘碼元仍要被恢復。
在操作中，對於有密鑰I和值B(I)的每個接收到的輸出碼元，解碼器1100進行以下操作。密鑰I被提供給值函數選擇器520、加權選擇器510和關聯器515。使用K+R以及動態密鑰I，加權選擇器510確定加權W(I)。使用K+R、動態密鑰I以及W(I)，關聯器515生成與輸出碼元相關聯的輸入和冗餘碼元的W(I)個位置的列表AL(I)。可選地，使用K+R和I，值函數選擇器520選擇值函數F(I)。然後I、B(I)、W(I)和AL(I)以及可選的F(I)被存儲在輸出碼元緩衝器1105的行內。值函數選擇器520、加權選擇器510以及關聯器515如同對動態編碼器220(圖2)的描述對解碼器1105實現相同的操作。特別是，由圖15內的值函數選擇器520、加權選擇器510和關聯器515生成的值函數F(I)、加權W(I)和列表AL(I)對於相同的動態密鑰I如同對於圖5內示出的對應部分相同。如果K和R隨不同的輸入文件而不同，則它們可以以常規的方式從編碼器傳遞到解碼器，諸如將其包括在消息頭部。
重建器1120掃描輸出碼元緩衝器1105以尋找存儲在那裡的帶有加權一即W(I)＝1以及AL(I)只列出一個關聯的輸出碼元。這些碼元在此被稱為「可解碼集合」的成員。對於帶有上述特性的值函數，加權一的輸出碼元在可解碼集合內，因為動態輸入碼元值可以從該輸出碼元被確定。當然，如果使用值函數，則會使得動態輸入碼元在除了帶有加權一的條件下經解碼，該條件會被用於確定是否輸出碼元在可解碼集合內。為了清楚起見，在此描述的示例假設可解碼集合是那些帶有加權一的輸出碼元，且這些示例擴展到其他值函數可解碼條件從該描述中應很清楚。
當重建器1120找到在可解碼集合內的一個輸出碼元時，輸出碼元值B(I)以及可選的值函數F(I)用於重建在AL(I)內列出的動態輸入碼元，且重建後的動態輸入碼元放入重建緩衝器1125對該輸入或冗餘碼元合適的位置。如果指示的輸入或冗餘碼元已經被重建，則重建器1120可丟棄新重建的動態輸入碼元，覆蓋現存的重建後輸入或冗餘碼元，或者如果兩者不同，比較兩者並生成差錯。在值函數是所有關聯的XOR情況下，輸入或冗餘碼元值簡單地是輸出碼元值。重建器1120因此只從可解碼集合內的輸出碼元重建輸入和冗餘碼元。一旦來自可解碼集合的輸出碼元被用於重建輸入或冗餘碼元，則它可以被刪除以節省在輸出碼元緩衝器1105內的空間。刪除「使用過」的輸出碼元還保證了重建器1120不會連續地重新訪問該輸出碼元。
開始時，重建器1120等待直到至少接收了一個輸出碼元，該輸出碼元是可解碼集合的成員。一旦使用了這一個輸出碼元，可解碼集合會再次變空，除了一些其他輸出碼元可能只是這一個重建後的輸入或冗餘碼元和一個其他的輸入或冗餘碼元的函數。因此，從可解碼集合的成員重建一個輸入或冗餘碼元會引起其他輸出碼元被加入可解碼集合。輸出碼元減少以將其加入可解碼集合的過程由縮減器1115實現。
縮減器1115掃描輸出碼元緩衝器1105和重建緩衝器1125以找到一些輸出碼元，這些碼元的列表AL(I)列出已經被恢復的輸入或冗餘碼元的位置。當縮減器1115找到該種帶有密鑰I的「可縮減」的輸出碼元，縮減器1115獲得在位置h處的恢復後的動態輸入碼元的值IS(h)並修改B(I)、W(I)以及AL(I)，如下 B(I)被設定為B(I)IS(h) W(I)被設定為W(I)-1 AL(I)被設定為除了h以外的AL(I) 在上述等式中，假設值函數是所有關聯的值的XOR。值得注意的是XOR是其本身的反-如果情況不是這樣，且原來使用另一值函數以計算輸出碼元，則該值函數的反在此被縮減器1115使用。如應很明顯的。如果已知多餘一個關聯的值，則以上等式的等價可以經計算以使得B(I)只取決於任何未知的關聯值(並相應地調整W(I)和L(I))。
縮減器1115的行為減少了輸出碼元緩衝器1105內的輸出碼元的加權。當輸出碼元的加權被減少到一(或對其他值函數發生其他可解碼條件)，則該輸出碼元成為可解碼集合的成員，可以由重建器1120對其進行操作。實際上，一旦接收到充分數量的輸出碼元，縮減器1115和重建器1120建立連鎖解碼，重建器1120對可解碼集合解碼以恢復更多的動態輸入碼元，縮減器1115使用這些剛恢復的輸入或冗餘碼元以減少更多的輸出碼元，使得它們被加入可解碼集合等，直到可解碼集合為空。
圖15內示出的解碼器部分以直接方式部分地重建輸入和冗餘碼元，而不考慮存儲器存儲、計算周期或傳輸時間。當解碼器存儲、解碼時間或傳輸時間(這限制了接收到的輸出碼元數)受限時，解碼器可以經優化以更好地使用這些受限的資源。該種優化的示例在例如Luby I和Luby II內經描述。這些優化可以被用於多級編碼的動態解碼。另外，可以理解可以使用其他的變體和等價的解碼器。
靜態解碼器 圖16是說明靜態解碼器的一實施例的簡化框圖。該實施例可以在數據用諸如圖7內描述的靜態編碼器編碼時被使用。靜態解碼器1200包括LDPC解碼器1205以及漢明解碼器1210。LDPC解碼器1205從重建緩衝器1215接收輸入碼元以及冗餘碼元，並試圖重建這些在動態解碼器的解碼步驟之後未經恢復的重建緩衝器1215的碼元。在一些實施例中，重建緩衝器1215是重建緩衝器1125(圖15)。LDPC解碼器1205接收由靜態密鑰發生器130生成的靜態密鑰S0，S1，...。另外，LDPC解碼器1205接收K個輸入碼元，D個冗餘漢明碼元以及E個冗餘LDPC碼元。LDPC解碼器1205以本領域內技術人員已知的方式儘可能多地恢復輸入和冗餘碼元，並將這些值寫入重建緩衝器1215內對應的位置。
漢明解碼器1210還經耦合以從重建緩衝器1215接收輸入碼元和冗餘碼元。另外，漢明解碼器1210接收輸入碼元數K、數字D，其中D+1是冗餘漢明碼元數。漢明解碼器1210試圖恢復這些未被動態解碼器和LDPC解碼器2005恢復的輸入碼元。雖然LDPC解碼器2005的目的是恢復儘可能多的輸入和冗餘碼元，漢明解碼器2010隻試圖恢復輸入碼元IS(0)，IS(1)，...，IS(K-1)。
LDPC解碼器和漢明解碼器的許多變體對於本領域內的技術人員是熟知的，且可以用於本發明的各個實施例中。在一特定實施例中，漢明解碼器使用高斯消去(elimination)算法實現。高斯消去算法的許多變體在本領域內已知，且可以根據本發明用於各個實施例。
在一定應用中，更優地是使用圖1內示出的不同於上述一個類型的解碼器155。例如，如果輸入碼元數K不很大，例如小於1000，則輸出碼元的接收概率過程內涉及的方差可以強迫解碼器155收集多個輸出碼元，這些輸出碼元遠顯著大於K為了能使動態和靜態解碼器糾正規定數目的擦除。在這些情況中，可以使用不同類型的解碼器。該種使用高斯消去的解碼器的實施例在以下參考圖17、18和19進行描述。
首先，回到圖1，解碼器155從接收模塊150接收輸出碼元B(Ia)，B(Ib)，...，從動態密鑰重新發生器160接收密鑰Ia，Ib，...，且從靜態密鑰發生器130接收密鑰S0，S1，...。另外，它接收輸入碼元的值K以及冗餘碼元的值R。在接收到該輸入後，它試圖重建輸入碼元IS(0)，...，IS(K-1)，這些碼元被傳遞到輸入文件組裝器165以作進一步處理。
現在參考圖17，解碼器1300包括動態矩陣發生器1305和靜態矩陣發生器1310。動態矩陣發生器1305接收輸出碼元B(Ia)，B(Ib)，...、動態密鑰Ia，Ib，...以及參數K和R。另外，動態矩陣發生器1305接收其他參數A，這些參數描述應收集多少輸出碼元(即收集的輸出碼元數為K+A)。參數A的確定一般取決於用於動態和靜態編碼的方法，且在以下會經詳述。在以下的描述中，收集的K+A個輸出碼元被稱為B(0)，B(1)，...，B(K+A-1)。在接收到這些參數後，具有形式為C*轉置的線形方程組(IS(0)，...，IS(K-1)，RE(0)，...，RE(R-1))＝轉置(B(0)，...，B(K+A-1))，該系統由動態矩陣發生器1305設定，其中C是形式為(K+A)×(K+R)的矩陣。由動態矩陣發生器1305的生成矩陣C在以下將詳述。
然後靜態矩陣發生器1310從動態矩陣發生器1305接收矩陣C，並使用密鑰S0，S1，...以向矩陣C加入R行以獲得方程組 M*轉置(IS(0)，...，IS(K-1)，RE(0)，...，RE(R-1))＝ 轉置(B(0)，...，B(K+A-1)，0，...0) 其中右邊向量的最後R項為零，且其中M為(K+A+R)×(K+R)格式。最終，使用線性方程組求解1315以求解該方程組M並獲得輸入碼元IS(0)，...，IS(K-1)的一些或所有。在一特定實施例中，線性方程組求解器1315使用高斯消去算法以求解線性方程組。
動態矩陣發生器1305和靜態矩陣發生器1310現在參考圖5的動態編碼器500和圖2內的靜態編碼器205進一步詳細描述。圖18是說明動態矩陣發生器1305使用的方法的實施例。在步驟1405，動態矩陣發生器1205初始化形式為(K+A)×(K+R)的矩陣C全為零。下一步，在步驟1410，密鑰Ia，Ib，...連同加權選擇器510和關聯器515一起用於生成加權W(0)，...，W(K+A-1)以及相應的列表AL(0)，...，AL(K+A-1)。每個列表AL(k)包括在範圍0，...，K+R-1內的W(k)個整數。在步驟1415內，這些整數用於用AL(k)＝(a(0)，...，a(W(k)-1)計算C(k，l)，且項C(k，a(0))，...，C(k，a(W(k)-1))被設定為1。如上所述，矩陣C生成未知(IS(0)，...，IS(K-1)，RE(0)，...，RE(R-1))關於(B(0)，...，B(K+A-1))的方程組。原因如下一旦動態編碼器選擇加權W(k)以及關聯列表AL(k)＝(a(0)，...，a(W(k)-1)，則對應的輸出碼元B(k)可以獲得為B(k)＝L(a(0))L(a(1))...L(a(W(k)-1))， 其中L(j)表示在位置j處的重建緩衝器1925的未知值。這些方程為0到K+A-1間的所有k值累加，形成期望的方程組。
圖19是說明靜態矩陣發生器1310使用的方法的一實施例簡化流圖。該實施例參考圖10說明。在圖10的步驟820內，值得注意的是冗餘碼元RE(i)作為RE(i)＝IS(P1)...IS(Pt)經計算，且P1，P2，...，Pt如在步驟815內在接收到密鑰Si後經計算。這意味著IS(P1)...IS(Pt)RE(i)＝0。用重建緩衝器的位置說明，這意味著L(P1)...L(Pt)L(i+k)＝0。將M的(i，P1)，...，(i，Pt)，(i，i-A)項設定為1，其中i從K+A到K+A+R-1，獲得矩陣M，該矩陣描述未知的(IS(0)，...，IS(K-1)，RE(0)，...，RE(R-1))關於(B(0)，...，B(K+A-1))的線性方程組，如上所述。
在步驟1505，格式為(K+A+R)×(K+R)的矩陣M通過使得M的前K+A行等於動態矩陣發生器1305計算的矩陣C而經初始化。M的剩餘行經初始化為零。下一步在步驟1510，變量i經初始化為K+A。該變量跟蹤M的最後R行。在步驟1512，計算與冗餘碼元i-K-A的相關聯的數t。該步驟類似於圖8的步驟810。特別是如果在圖8給出的靜態編碼過程中偏好另一t選擇，則還可以為步驟1512內計算的變量t採取該選擇。在步驟1515，關聯器414從靜態密鑰Si、輸入碼元數K以及整數t計算在0到K-1之間的索引P1，P2，...，Pt。然而，矩陣M的對應位置在步驟1530內被設定為1。步驟1540內的遞增和步驟1550內的測試保證了M的所有最後R行被訪問且經計算。
在一些實施例中，圖17、18和19內示出的實施例可以比在此描述的其他實施例更優，因為比起其他實施例，它允許相對收集更少的輸出碼元以進行正確解碼。解碼器的選擇很大程度上取決於應用，且取決於例如收集的輸出碼元數是否是關鍵資源。
關聯器實現 回到圖5，關聯器515的一實施例在Luby I內描述。數N應是質數。在操作中，當該實施例用於計算AL(I)時，輸入大小K+R可以經調整使得它是質數。在本發明中，冗餘碼元數目被選得充分大使得K+R為質數。在一些應用中，輸入N是質數的條件非常有限制性。
另一用於實現關聯器520的方法的實施例在圖20內示出，其中N不需要為質數。首先在步驟1805，變量k被初始化為零。然後，在步驟1810處，生成隨機整數Y。在一特定實施例中，輸出碼元的密鑰被用作隨機數發生器的種子。然後，在步驟1815，對整數Y與進行模數N運算以生成0到N-1間的數。在步驟1820，候選數Y與其它先前生成的Y個(X(0)，X(1)，...)相比經測試。如果Y已經先前被生成，則流程回到步驟1810。否則，在步驟1825，它被包括在列表X(0)，X(1)，...內。則在步驟1830，確定是否生成了W(I)個數。如果沒有，則流程回到步驟1810。圖8內說明的流程結果是W(I)個數X(0)，X(1)，...，X(W(I)-1)的列表，其中列表內的每個數X是0到N-1間的唯一整數。然後，在步驟835內，列表AL(I)被設定為數X(0)，X(1)，...，X(W(I)-1)。
加權選擇器實現 編碼器/解碼器的性能的效率取決於圖2內示出的動態編碼器220生成的輸出碼元的加權分布，且一些分布優於其他分布。尤其是參數A的選擇主要受到加權分布選擇的影響，該參數A描述與輸入碼元數K相比收集到數據碼元數超出情況。加權選擇的操作方面在以下描述，接著是一些重要的加權分布的描述。圖21的框圖和圖22的流圖用於說明這些概念。
圖5內示出的加權選擇器510的任務如下在接收到密鑰I和長度K+R後，加權選擇器輸出在範圍0到K+R-1內的整數W(I)，該整數被稱為加權。不同於關聯器515，加權選擇器510的輸出希望不是均勻，而是偏斜的，更集中於一些加權，而關聯器則理想地用均勻隨機分布均勻地生成整數。
如圖21示出，加權選擇器510包括兩個處理過程WT_INIT 1905和WT_CALC1910，以及兩個表格WT_RBITS 1915和WT_DISTRIB 1920。處理過程WT_INIT 1905隻在當第一密鑰被傳遞以初始化表格WT_DISTRIB 1920時被調用。WT_DISTRIB1920的設計是系統的重要方面，且之後將更詳細描述。過程WT_CALC 1910在每次被調用時被啟用以基於密鑰I生成加權W(I)。如在圖22的流程圖內示出的，WT_CALC 1910使用存儲在表格WT_RBITS 1915內的密鑰和隨機比特以生成隨機數T(2005)。然後，T的值被用於在表格WT_DISTRIB 1920內選擇行號N。
如圖21示出，WT_RBITS 1920內的RANGE列內的項是遞增的正整數序列，結束於值MAX_VAL，且WT列是遞增的正整數序列，結束於值MAX_WT。T的可能值集合是在零到MAX_VAL-1間的整數。期望的特性是T等概率地可能是可能值範圍內的任何值。N的值是通過搜索RANGE列直到找到一N而確定的，該N滿足RANGE(N-1)≤T＜RANGE(N)(2010)。一旦找到N，值W(I)被設定為WT(N)即表格WT_DISTRIB的WT列的第N項，且這是返回的加權(2015，2020)。在圖21內，對於示出的示例表格，如果T等於38500，則N被確定為4，且因此W(I)被設定為WT(4)＝8。在最優實施例中，WT_DIST 1920的行經組織使得RANGE(N)-RANGE(N-1)隨N遞增時值遞減。這最小化了通過WT_DIST 1920的平均搜索時間，即當使用從第一行開始的順序搜索時對應值T的加權的時間。在其他實施例中，其他行的組織方式可能是更優的，且可以使用其他的搜索方法，諸如二分搜索。
選擇加權分布 應為給定的編碼過程選擇加權分布，使得輸入文件可以完整地被重建，使用a)儘可能少的輸出碼元，b)儘可能少的操作，以及c)儘可能高的可靠性。一般，這些最優準則可以通過準確地為輸出碼元選擇正確的加權分布(即在所有I上的W(I)的分布)以及在輸出碼元上的關聯的分布(即在所有I上的AL(I)的成員)而達到。要強調的是雖然可以不管加權重分布和關聯選擇上的分布而應用解碼過程，但最優實施例會使用為接近最佳性能而選擇的加權分布和關聯選擇上的分布。實際上，許多分布性能很好，因為選擇的分布內的較小變化只會導致性能內較小的變化。
現在描述一種用於在最優實施例中確定分布的方法。使用的實際加權分布取決於輸入碼元的數目K。分布給出如下，連同範圍(Kmin，Kmax)、因子β以及相對開銷α。這有以下意義給定K，其中Kmin≤K≤Kmax，則冗餘碼元數目R是用大於或等於β*K的最小整數計算的，收集的輸出碼元數應至少為(1+α)*K，即上述的參數A是大於或等於α*K的最小整數。在使用第一個關聯器520的版本情況下，R應附加地滿足K+R是質數的條件，即R是大於等於β*K的最小質數。如果應用不需要K+R為質數，則R可以被選擇為大於或等於β*K的最小整數。
分布本身以以下形式的表格給出加權1 P1加權2 P2加權3 P3… … 其中P1是加權1的對應概率，P2是加權2的對應概率等，且其中P1、P2，...的和為一。這意味著圖21的表格WT_DISTRIB 1920有以下形式 加權1 MAX_VAL*P1加權2 MAX_VAL*(P1+P2)加權3 MAX_VAL*(P1+P2+P3)… … 將描述用於計算在此的表格的一般規則。設計的一個目標是使得目前的具有減少加權碼元的一個非零數的輸出碼元儘可能地在進入動態解碼過程。最好，該數目能在到動態解碼結束前的整個過程中一直大於零。然而，數學分析示出這只在如果輸出碼元的平均加權至少與輸入碼元數K的對數成正比時才可能，且這是Luby I內描述的幾種加權分布的設計。本發明的一些實施例將該平均加權大大減少到固定的獨立於K的恆量。結果，減少加權碼元的輸出碼元數不能期望在整個動態解碼過程期間大於零。
設計加權分布的初始步驟是獲得期望的動態輸入碼元的數目表達式，其值在動態輸入碼元的部分x尚未被恢復時，可以從在動態解碼過程中當前可解碼集合內的輸出碼元獲得。該表達式是加權1，2，...，k的輸出碼元的部分P1，P2，..，Pk以及收集的輸出碼元數和輸入和冗餘碼元數之比的函數。以下，該比用γ表示。可見γ＝(1+α)/(1+β)。該量的數學分析示出該種動態輸入碼元的期望數目可以表示為 K * ( 1 + ) * ( x - e - ( 1 + ) * ( 1 - x ) ) , - - - ( 1 ) 其中x表示在動態解碼過程中尚未被恢復的動態輸入碼元部分，且

為多項式P1+2*P2*x+3*P3*x2+...+k*Pk*xk-1. (2) 由於該數目只是一個量的期望，這個量是統計性質的，所以會有變化。該變化的分析顯示它與還未恢復的輸入碼元的期望數目即與x*K*(1+β)的方根成正比。為了合理地保證是與減少加權碼元的輸出碼元的相鄰的輸入碼元數總為正，則P1，...，Pk和γ的選擇應使得 K * ( 1 + ) * ( x - e - ( 1 + ) * ( 1 - x ) ) > c * sqrt ( x * K * ( 1 + ) ) , - - - ( 3 ) 其中該不等性對於在給定正實數ε和1間的所有x值均成立，且c是大於一的正實數。c越大，越能保證解碼過程的成功。ε越小，則在動態解碼過程最後會有更少的未經恢復輸入碼元。

越小，輸出碼元的平均加權越小。給定這些限制，可以為給定的ε和給定的c計算多項式

，其中所有的係數非負，這滿足了ε和1之間的所有x值的上述不等性，且對此

儘可能地小。該最優化可以由各種方法完成，例如在適當地操作上述不等性後使用單純形算法。
現在實際表格根據以上描述被給出。以上描述內的恆量c的選擇是為了保證總解碼器擦除概率小於10-10。對於K＞49251，差錯概率小於10-12。這些表格僅作為可以被使用的加權分布示例而被提供。可以理解還可以使用其他加權分布。
表格1 K範圍9900-14800，β＝0.008l，α＝0.1187 10.01823520.47756230.15356540.10200650.03465170.04835280.06084180.058325190.008401700.008451710.029613 表格2 K範圍14801-19680，β＝0.00121，α＝0.08410.01931420.48358230.16075440.08163150.06754180.094528180.041968190.019462660.007987670.023233 表格3 K範圍19681-29510，β＝0.0151，α＝0.0769 10.01353120.48825030.16481040.07095350.08424380.05009390.042547190.055060620.00501988630.025491 表格4 K範圍29511-49250，β＝0.0161，α＝0.067410.01387620.48908730.16227640.08163850.06988080.08133990.014424180.017712190.040774660.014680670.014314 表格5 K範圍49251-64780，β＝0.015，α＝0.0558 10.00911720.49284330.16598340.07270750.08230380.05634790.036917190.055616650.022195660.005972 表格6 K範圍64781-79080，β＝0.0114，α＝0.0510.00796920.49357030.16622040.07264650.08255880.05605890.037229190.055590650.025023660.003135 表格7 K範圍79081-98623，β＝0.01134，α＝0.04710.00754420.4936130.16645840.07124350.08491380.04963390.043365190.045231200.010157660.010479670.017365表格8 K範圍98624-118349，β＝0.01377，α＝0.0424 10.00649520.49504430.16801040.06790050.08920980.04173190.050162190.038837200.015537660.016298670.010777 表格9 K範圍118350-∞，β＝0.01579，α＝0.039310.00480720.49647230.16691240.07337450.08220680.05747190.035951180.001167190.054305650.018235660.009100 例如，如果K＝33000，則冗餘碼元的數目可以是大於K*0.0161＝531.3的最小整數R，使得K+R為質數。即R＝533。收集的輸出碼元數應至少為(1+0.0674)*K即35225。
表格1的平均加權大致為6.75，且表格2到9的平均加權大致為6。這些平均加權與先前描述的Luby I的一實施例相比大大減少，先前的情況在K等於60000時平均加權為28.68。
較少輸入碼元的編碼 對於任何大小的輸入文件最好是相對較低的開銷。如以上表格中可見，隨著輸入碼元數K變得較小，相對開銷α增加。例如，如果輸入文件有10000位元組，且K被選為10000使得每個碼元包括一個字節，則開銷大致為11％，這對於一些應用是不期望的。一種減少開銷的方法是增加輸入碼元數K，其代價是減少輸入碼元大小。例如，在期望大致7％的開銷時，K被選為40000。在該情況下，輸入碼元的大小會是2比特。然而使用非常小大小的輸入碼元實際上會導致計算不足。
該問題的解決方法是使用基於高斯消去法的解碼器，諸如圖17內描述的實施例。即使與其他實施例內描述的任何靜態編碼器組合的連鎖解碼器相比，該解碼器計算效率沒有那麼有效，與解碼器的非常小的失敗概率和開銷的組合使得該解決方法在一些應用內是期望的。
尤其是，當輸入碼元數K在800到9899之間時，以下的加權分布可以用於動態編碼器220 表格10 K範圍800-1600，β＝0.08，α＝0.0520.3930.09540.09550.095100.095190.095300.0951300.04 根據諸如圖10內描述的靜態編碼器的操作生成0.08*K冗餘碼元。解碼使用諸如圖17內描述的解碼器完成。
作為一示例，假設輸入文件大小為16000位元組。輸入碼元的選擇使得它們每個包括16個字節，使得輸入碼元的數目K為1000。圖10內的靜態編碼器用於建立80個冗餘碼元。下一步，動態編碼器220與上述的加權分布一起用於生成輸出碼元。接收機收集(1+α)*K＝1050個輸出碼元並將其提供給圖17的解碼器。動態矩陣發生器1305建立格式為1050×1080的矩陣C。靜態矩陣發生器1330建立格式1130×1080的矩陣M，並將其送到線性方程組求解器1340的系統，該系統試圖對原始1000個輸入碼元(即輸入文件)解碼。
一些多級編碼的一些特性 如上所述的大多數的示例，輸入和輸出碼元對相同數量的比特進行編碼，且每個輸出碼元被放入一個分組(分組是或者整個被接收到或者整個被丟失的傳輸單元)。在一些實施例中，通信系統經修改使得每個分組包含幾個輸出碼元。輸出碼元值大小被設定到基於多個因子將文件初始分成輸入碼元時的輸入碼元值大小所確定的大小。解碼過程保持基本不變，除了輸出碼元在接收到每個分組時成串到達。
輸入碼元和輸出碼元大小的設置一般由文件的大小和輸出碼元要在其上發送的通信系統決定。例如，如果通信系統將數據比特分組成所定義的大小的分組或以其他方式分組比特，則碼元大小的設計開始於該分組進行分或組的大小。此後，設計者可以確定在一個分組或一組內可以攜帶多少輸出碼元，並確定輸出碼元大小。為了簡潔，設計者可能會使得輸入碼元大小設置為等於輸出碼元大小，且如果輸入數據使得不同的輸入碼元大小更方便，則也可以使用不同大小。
上述的編碼過程基於原始文件生成包含輸出碼元的分組流。流內的每個輸出碼元獨立於所有其他的輸出碼元經生成，且在可以建立的輸出碼元數上沒有上下界。一密鑰與每個輸出碼元關聯。該密鑰以及輸入文件的一些內容確定輸出碼元值。接連生成的輸出碼元不需要連續的密鑰，且在一些應用中，最好能隨即生成密鑰序列或偽隨機地生成該序列。
多級解碼的特性是如果原始文件可以被分成K個等大小的輸入碼元，且每個輸出碼元值長度與輸入碼元值的長度相同，則文件可以從平均K+A個輸出碼元中以很高的概率恢復，其中A與K相比較小。例如，對於上述的加權分布，如果K大於19681，則A值超過α*K的概率最多為10-12，對於K的任何值，最多為10-10。由於特定的輸出碼元以隨機或偽隨機順序生成，且傳輸中的特定輸出碼元的丟失被假設為隨機，則在恢復輸入文件需要的輸出碼元的實際數量上存在某些小方差。在一些情況下，其中特定的K+A分組的集合不足以對整個輸入文件解碼，如果接收機可以從一個或多個輸出分組源收集到更多的分組，則輸入文件仍可以被恢復。
由於輸出碼元數隻受到I的解析度的限制，則可以生成大大多於K+A個輸出碼元。例如，如果I為32比特數，則可以生成四十億不同的輸出碼元，然而文件僅可以包括K＝50000個輸入碼元。在一些應用中，這些四十億個輸出碼元只有一小部分被生成且被發送，且幾乎肯定輸入文件可以用很小部分的可能輸出碼元以及極佳的概率被恢復，輸入文件可以用稍微多於K個輸出碼元被恢復(假設輸入碼元大小與輸出碼元大小相同)。
在一些應用中，可能可以接受不能對所有的輸入碼元解碼，或以相對較低的概率對所有輸入碼元解碼。在該種應用中，接收機可以在接收到K+A個輸出碼元後停止試圖對所有的輸入碼元解碼。或接收機可以在接收到少於K+A個輸出碼元後停止接收輸出碼元。在一些應用中，接收機可能只能接收到K個或更少的輸出碼元。因此，可以理解在本發明的一些實施例中，期望的準確度可能不是所有輸入碼元的完整恢復。
而且，在一些不完整恢復可接受的應用中，數據可以經編碼使得所有的輸入碼元都不能被恢復，或使得完整的輸入碼元需要接收到比輸入碼元數更多的輸出碼元。該種編碼一般要求的計算代價較少，且因此是減少編碼計算代價的可接受方法。
可以理解的是，上述圖內的各種功能框可以用硬體和/或軟體的組合實現，且在特定實現中，可以組合一些框的一些或所有功能。類似地，可以理解，這是描述的各個方法可以用硬體和/或軟體的組合而實現。
以上描述是說明性的，而不是限制型的。本發明的許多變體對於領域內的技術人員在閱讀了本揭示後會變得明顯。本發明的範圍因此不是由描述確定，而是由以下所附的權利要求書以及其等價的完整範圍確定。
權利要求
1.一種用於在通信信道上從源到目的地的數據傳輸的編碼的方法，其特徵在於包括
從要發送的輸入碼元的排序集合生成多個冗餘碼元；以及
從包括輸入碼元和冗餘碼元的碼元組合集合生成多個輸出碼元，其中可能的輸出碼元數遠遠大於碼元的組合集合內的碼元數，其中從碼元的組合集合內多於一個碼元且從碼元的組合集合內少於所有碼元中生成至少一個輸出碼元，使得輸入碼元的排序集合可以從輸出碼元的任何預定數N經重新生成達到期望的準確度。
2.如權利要求1所述的方法，其特徵在於還包括在通信信道上發送多個輸出碼元。
3.如權利要求1所述的方法，其特徵在於進一步包括在存儲媒質上存儲多個輸出碼元。
4.如權利要求1所述的方法，其特徵在於N大於輸入碼元的排序集合內的輸入碼元數。
5.如權利要求1所述的方法，其特徵在於N小於或等於輸入碼元的排序集合內的輸入碼元數。
6.如權利要求1所述的方法，其特徵在於還包括基於輸入碼元的排序集合內的輸入碼元的數目K確定要生成的冗餘碼元的數目R。
7.如權利要求6所述的方法，其特徵在於K是輸入碼元數的估計。
8.如權利要求1所述的方法，其特徵在於多個冗餘碼元根據LDPC碼生成。
9.如權利要求1所述的方法，其特徵在於多個冗餘碼元包括多個第一冗餘碼元和多個第二冗餘碼元，且其中生成多個冗餘碼元的步驟包括
從輸入碼元生成多個第一冗餘碼元；以及
從第一冗餘碼元和輸入碼元生成多個第二冗餘碼元。
10.如權利要求9所述的方法，其特徵在於多個第一冗餘碼元根據漢明碼生成，且其中多個第二冗餘碼元根據LDPC碼生成。
11.如權利要求10所述的方法，其特徵在於還包括
基於輸入碼元的排序集合內的輸入碼元數K確定第一冗餘碼元的數目D+1；以及
基於要生成的冗餘碼元的數目R和D+1確定第二冗餘碼元數E。
12.如權利要求11所述的方法，其特徵在於還包括基於K確定R。
13.如權利要求11所述的方法，其特徵在於K是輸入碼元數的估計。
14.如權利要求11所述的方法，其特徵在於D是使得2D-D-1＞＝K的最小整數。其中E＝R-D-1。
15.如權利要求1所述的方法，其特徵在於期望的準確度是輸入碼元的完整恢復。
16.如權利要求1所述的方法，其特徵在於期望的準確度是輸入碼元以較高概率的完整恢復。
17.如權利要求1所述的方法，其特徵在於期望的準確度是G個輸入碼元的恢復，其中G小於輸入碼元的排序集合內的輸入碼元數。
18.如權利要求1所述的方法，其特徵在於最多可以從任何數量的輸出碼元中重新生成最多G個輸入碼元，其中G小於輸入碼元的排序集合內的輸入碼元數。
19.如權利要求1所述的方法，其特徵在於生成多個冗餘碼元，對於每個冗餘碼元包括
根據一分布確定t個不同的輸入碼元；以及
按照t個不同輸入碼元的XOR計算每個冗餘碼元。
20.如權利要求19所述的方法，其特徵在於t對於所有冗餘碼元相同。
21.如權利要求20所述的方法，其特徵在於t是大於K/2的最小奇整數，其中K是輸入碼元的排序集合內的輸入碼元數。
22.如權利要求19所述的方法，其特徵在於所述分布是均勻分布。
23.如權利要求1所述的方法，其特徵在於還包括在通信信道上發送多個輸出碼元，其中生成多個輸出碼元的步驟是與發送多個輸出碼元的步驟大致上進發進行的。
24.如權利要求23所述的方法，其特徵在於生成多個冗餘碼元的步驟是與發送多個輸出碼元步驟大致進發進行的。
25.如權利要求23所述的方法，其特徵在於生成多個冗餘碼元的步驟是在發送多個輸出碼元步驟之前進行的。
26.如權利要求1所述的方法，其特徵在於生成多個輸出碼元的步驟是使用第一設備實現的，且其中生成多個冗餘碼元的步驟是使用與第一設備分離的第二設備實現。
27.一系統，用於在通信信道上對從源到目的地傳輸的數據編碼，其特徵在於包括
被耦合以接收多個輸入碼元的靜態編碼器，多個輸入碼元從要發送的數據中生成，靜態編碼器包括冗餘碼元發生器，所述發生器基於輸入碼元生成多個冗餘碼元；以及
被耦合以接收多個輸入碼元和多個冗餘碼元的動態編碼器，動態編碼器包括輸出碼元發生器，所述發生器從包括多個輸入碼元和多個冗餘碼元的碼元組合集合中生成多個輸出碼元，其中可能輸出碼元數遠遠大於組合集合內的碼元數，其中從多於組合集合的碼元且小於組合集合的所有碼元中生成至少一個輸出碼元，使得輸入碼元的排序集合可以從輸出碼元的任何預定數N中重新生成達到期望的準確度。
28.如權利要求27所述的系統，其特徵在於N大於輸入碼元排序集合內的輸入碼元數。
29.如權利要求27所述的方法，其特徵在於N小於或等於輸入碼元的排序集合內的輸入碼元數。
30.如權利要求27所述的系統，其特徵在於還包括發射模塊，所述模塊耦合到動態編碼器和通信信道，並在通信信道上接收輸出碼元並發送輸出碼元。
31.如權利要求27所述的系統，其特徵在於還包括密鑰發生器，所述密鑰發生器耦合到動態編碼器，所述動態編碼器為每個要生成的輸出碼元生成一密鑰，其中動態編碼器經耦合以接收每個密鑰，且其中動態編碼器基於對應的密鑰生成每個輸出碼元。
32.如權利要求27所述的系統，其特徵在於還包括密鑰發生器，所述密鑰發生器耦合到靜態編碼器，所述靜態編碼器為至少一些要生成的冗餘碼元的每個生成密鑰，其中靜態編碼器經耦合以接收每個密鑰，且其中靜態編碼器基於對應的密鑰生成至少一些冗餘碼元的每個。
33.如權利要求27所述的系統，其特徵在於靜態編碼其包括LDPC編碼器。
34.如權利要求27所述的系統，其特徵在於靜態編碼器還進一步包括帶有第一冗餘碼元發生器的第一靜態編碼器，且第二靜態編碼器具有第二冗餘碼元發生器；
其中多個冗餘碼元包括第一組冗餘碼元以及
第二組冗餘碼元；
其中第一冗餘碼元發生器基於輸入碼元生成第一組冗餘碼元；以及
其中第二冗餘碼元發生器基於輸入碼元和第一組冗餘碼元生成第二組冗餘碼元。
35.如權利要求34所述的系統，其特徵在於第一靜態編碼器包括漢明編碼器，其中第二靜態編碼器包括LDPC編碼器。
36.在通信信道上從源接收發送的數據的方法，其特徵在於該方法包括
接收輸出碼元，其中每個輸出碼元從輸入碼元和冗餘碼元的組合集合內的至少一個碼元生成，其中至少一個輸出碼元從多於組合集合內的一個碼元且少於組合集合內所有碼元中生成，其中可能的輸出碼元數遠遠大於組合集合內的碼元數，其中輸入碼元來自輸入碼元的排序集合，其中冗餘碼元從輸入碼元生成；
在接收到至少輸出碼元的一個子集後，從輸出碼元重新生成組合集合內的至少一個碼元的子集，所述組合集合內的碼元子集包括多個重新生成的輸入碼元以及多個重新生成的冗餘碼元；
如果從N個輸出碼元重新生成碼元的至少一個子集的步驟沒有按照期望的準確度重新生成輸入碼元，則從多個重新生成的冗餘碼元和多個重新生成的輸入碼元重新生成至少一些未經重新生成的輸入碼元。
37.如權利要求36所述的方法，其特徵在於冗餘碼元包括第一組冗餘碼元和第二組冗餘碼元，其中至少重新生成一些未經重新生成的輸入碼元的步驟包括
從第一組冗餘碼元的重新生成的冗餘碼元以及多個經重新生成的輸入碼元，重新生成未經重新生成的輸入碼元的至少一個以及第二組冗餘碼元的未經重新生成冗餘碼元；以及
如果從第一組冗餘碼元的重新生成冗餘碼元和多個重新生成輸入碼元的重新生成步驟沒有按期望的準確度重新生成輸入碼元，則從第二組冗餘碼元的冗餘碼元和多個解碼後輸入碼元重新生成至少一個未經重新生成的輸入碼元。
38.如權利要求37所述的方法，其特徵在於一些未經重新生成的輸入碼元和第二組冗餘碼元的未經重新生成的冗餘碼元使用LDPC解碼器重新生成，以及
其中一些輸入碼元使用漢明解碼器從第二組冗餘碼元的冗餘碼元經重新生成。
39.如權利要求36所述的方法，其特徵在於重新生成至少一些未被重新生成的輸入碼元的步驟包括重新生成所有未被重新生成的輸入碼元。
40.如權利要求36所述的方法，其特徵在於重新生成組合集合內的碼元子集合的步驟以及重新生成至少一些未經重新生成的輸入碼元的步驟包括
形成第一矩陣，所述矩陣為每個接收到的輸出碼元指示與輸出碼元相關聯的組合集合內的碼元；
使用信息增廣所述第一矩陣，所述信息為每個冗餘碼元指示與冗餘碼元相關的輸入碼元；以及
重新生成至少一些輸入碼元，作為由增廣的第一矩陣指明的方程組的解。
41.如權利要求36所述的方法，其特徵在於N大於或等於輸入碼元數。
42.如權利要求36所述的方法，其特徵在於N小於輸入碼元數。
43.如權利要求36所述的方法，其特徵在於重新生成至少一些未經生成的輸入碼元包括重新生成所有的輸入碼元。
44.如權利要求36所述的方法，其特徵在於重新生成至少一些未經生成的輸入碼元包括重新生成少於所有的輸入碼元。
45.一系統用於接收在通信信道上從源發送的數據，其特徵在於包括
接收模塊，所述模塊耦合到通信信道用於接收在通信信道上發送的輸出碼元，其中每個輸出碼元從輸入碼元和冗餘碼元的組合集合內的至少一個碼元生成，其中至少一個輸出碼元從組合集合內多於一個碼元以及組合集合內少於所有碼元中生成，其中可能的輸出碼元數遠遠大於組合集合內的碼元數，其中輸入碼元來自輸入碼元的排序集合，其中冗餘碼元從輸入碼元生成；
動態解碼器，在接收到輸出碼元的至少一子集合後，對來自輸出碼元的的組合集合內的碼元子集進行解碼，所述組合集合內的碼元子集包括多個解碼後的輸入碼元和多個解碼後的冗餘碼元；以及
靜態解碼器，從多個解碼後的冗餘碼元對未經解碼的輸入碼元(如果有的話)的至少一些進行解碼。
46.如權利要求45所述的系統，其特徵在於所述靜態解碼器包括LDPC解碼器。
47.如權利要求45所述的系統，其特徵在於冗餘碼元包括第一組冗餘碼元和第二組冗餘碼元，其中靜態編碼器包括
第一靜態解碼器，所述解碼器從第一組冗餘碼元的解碼後冗餘碼元和多個解碼後輸入碼元，對未經解碼的輸入碼元和第二組冗餘碼元的未經解碼的冗餘碼元的至少一個進行解碼；
第二靜態解碼器，從第二組冗餘碼元的冗餘碼元和多個解碼後的輸入碼元對至少一個未經解碼的輸入碼元解碼。
48.如權利要求47所述的系統，其特徵在於第一靜態編碼器包括LDPC解碼器，且其中第二靜態解碼器包括漢明解碼器。
49.如權利要求45所述的系統，其特徵在於動態解碼器包括一處理器，用於執行以下步驟
形成第一矩陣，所述矩陣為每個接收到的輸出碼元指示與輸出碼元相關聯的組合集合內的碼元；
使用信息增大所述第一矩陣，所述信息為每個冗餘碼元指示與冗餘碼元相關聯的輸入碼元；以及
重新生成至少一些輸入碼元，作為由增廣的第一矩陣指明的方程組的解。
50.體現在載波中的計算機數據信號，其特徵在於包括
多個輸出碼元，其中多個輸出碼元表示從包括輸入碼元和冗餘碼元的排序集合的碼元組合集合生成的碼元，其中冗餘碼元從輸入碼元被生成，其中可能的輸出碼元數遠遠大於碼元組合集合內的碼元數，其中至少一個輸出碼元從碼元的組合集合內多於一個碼元以及從碼元組合集合內少於所有碼元生成；
使得數據信號接收機能從輸出碼元的任何預定數量N按期望的準確度重新生成輸入碼元的排序集合。
51.如權利要求36所述的方法，其特徵在於重新生成碼元的至少一子集的步驟在接收到預定數量N的任何輸出碼元後執行。
52.如權利要求36所述的方法，其特徵在於重新生成碼元的至少一子集的步驟是在接收到數量N的任何輸出碼元後執行，其中的N使得輸入碼元可以被重新生成達到所希望的準確度。
53.如權利要求36所述的方法，其特徵在於重新生成碼元的至少一子集的步驟在大致與接收到輸出碼元進發地執行。
全文摘要
提供了一種用於在通信信道(145)上從源(101)到目的地(170)的數據傳輸編碼的方法。從要發送的輸入碼元的排序集合生成多個冗餘碼元。從包括輸入碼元和冗餘碼元的碼元組合集合生成多個輸出碼元，其中可能的輸出碼元數遠遠大於碼元的組合集合內的碼元數，其中從碼元的組合集合內多於一個碼元且從碼元的組合集合內少於所有碼元生成至少一個輸出碼元，使得輸入碼元的排序集合可以從輸出碼元的任何預定數N經重新生成達到期望的準確度。
文檔編號H04L25/49GK1620760SQ0282811
公開日2005年5月25日 申請日期2002年12月23日 優先權日2001年12月21日
發明者A·M·肖克羅拉希, S·拉森, M·路比 申請人:數字方敦股份有限公司