為編碼和解碼過程採用使碼元永久鈍化的fec碼的方法和裝置的製作方法

2023-07-08 01:21:21 1

專利名稱：為編碼和解碼過程採用使碼元永久鈍化的fec碼的方法和裝置的製作方法
為編碼和解碼過程採用使碼元永久鈍化的FEC碼的方法和裝置交叉引用本申請是於2009年10月23日提交、發明人名為M. Amin Shokrollahi等人且題為 「Method and Apparatus Employing FEC Codes with Permanent Inactivation ofSymbols for Encoding and Decoding Processes (為編碼和解碼過程採用使碼元永久鈍化的FEC碼的方法和裝置)」的美國專利申請號12/604，773的部分延續，且進一步要求發明人皆為M. Amin Shokrollahi 等人且皆題為「Method and Apparatus Employing FEC Codeswith Permanent Inactivation of Symbols for Encoding and Decoding Processes (為編碼和解碼過程採用使碼元永久鈍化的FEC碼的方法和裝置)」的以下臨時申請的優先權於2010年6月11日提交的美國臨時專利申請號61/353，910、於2009年11月2日提交的美國臨時專利申請號61/257，146、以及於2009年8月19日提交的美國臨時專利申請號61/235，285。以上引用的每篇臨時和非臨時申請藉此通用地通過援引納入於此。 以下參考的全部內容通用地通過援引納入於此I)授予 Michael G. Luby 的題為 「 Information Additive Code Generator andDecoder for Communication Systems (用於通信系統的信息加性碼生成器和解碼器)」的美國專利號6，307，487 (下文稱為「 Luby I」)；2)授予 Michael G. Luby 的題為「 Information Additive Group Code Generatorand Decoder for Communication Systems (用於通信系統的信息加性群碼生成器和解碼器)」的美國專利號6，320，520 (下文稱為「Luby II」)；3)授予M. Amin Shokrollahi 的題為「Multi-Stage Code Generator and Decoderfor Communication Systems (用於通信系統的多級碼生成器和解碼器)」的美國專利號7，068，729 (下文稱為 「ShokrolIahi I」)；4)授予 M. Amin Shokrollahi 的題為 「Systems and Processes for Decoding aChain Reaction Code Through Inactivation (用於通過鈍化來解碼鏈式反應碼的系統和過程)」的美國專利號6，856，263(下文稱為「511010'011&111 II」)；5)授予 M. Amin Shokrollahi 的題為 「Systematic Encoding and Decoding ofChain Reaction Codes (鏈式反應碼的系統編碼和解碼)」的美國專利號6，909, 383 (下文稱為 「ShokrolIahi III」)；6)授予 Michael G. Luby 和 M. Amin Shokrollahi 且題為 「In-PlaceTransformations with Applications to Encoding and Decoding Various Classes ofCodes (應用於編碼和解碼各類碼的原地變換)」的美國專利公開號2006/0280254 (下文稱為 「Luby III，，)；7)發明人名為 M. Amin Shokrollahi 且題為「Multiple Field Based CodeGenerator and Decoder for Communications Systems (用於通信系統的基於多域的碼生成器和解碼器)」的美國專利公開號2007/0195894 (下文稱為「Shokrollahi IV」)。發明領域本發明涉及在通信系統中編碼和解碼數據，尤其涉及以高效率方式編碼和解碼數據以計及所傳達數據中的差錯和間隙的通信系統。
背景技術：
用於通過通信信道在發送方與接收方之間傳輸文件的技術是許多文獻的主題。較佳地，接收方希望以某種確定性程度接收由發送方在信道上傳送的數據的確切副本。在信道不具有理想保真度的情況下(這囊括了幾乎所有在物理上可實現的系統)，所關心的是如何處理傳輸中丟失和混淆的數據。丟失的數據(擦除)通常比訛誤的數據(差錯)更容易處理，因為接收方不能總是辨別出何時訛誤的數據是接收出錯的數據。已開發出許多糾錯碼來糾正擦除和/或差錯。典型地，所使用的特定碼是基於關於數據正藉以傳送的信道的失真以及正被傳送的數據的特性的某些信息來選取的。例如，在知曉信道具有長失真期的場合，陣發差錯碼對於此應用可能是最合適的。在預期僅有短且不頻繁的差錯的場合，簡單的奇偶校驗碼可能是最佳的。如本文中所使用的，「源數據」是指在一個或更多個發送方處可用以及使用接收機通過從有或無差錯和/或擦除等的所傳送序列進行恢復來獲得的數據。如本文中所使用的，「經編碼數據」是指被傳達且能被用來恢復或獲得源數據的數據。在簡單情形中，經編碼數據是源數據的副本，但若接收到的經編碼數據(例如，由於差錯和/或擦除)不同於所傳送的經編碼數據，則在該簡單情形中，在缺少關於源數據的附加數據的情況下，源數據可能無法完全恢復。傳輸可通過空間或時間。在更複雜的情形中，經編碼數據是基於源數據在變換中生成的，並從一個或更多個發送方傳送給接收方。若發現源數據將成為經編碼數據的一部分，則編碼被稱為「系統的」。在系統編碼的簡單示例中，關於源數據的冗餘信息被追加到源數據末尾以形成經編碼數據。如本文中所使用的，「輸入數據」是指FEC(前向糾錯)編碼器裝置或FEC編碼器模塊、組件、步驟等(「FEC編碼器」)的輸入端出現的數據，而「輸出數據」是指FEC編碼器的輸出端出現的數據。相應地，將期望輸出數據出現在FEC解碼器的輸入端，且將期望該FEC解碼器基於它處理的該輸出數據而輸出該輸入數據或其對應數據。在一些情形中，輸入數據是或者包括源數據，且在一些情形中，輸出數據是或者包括經編碼數據。在其他情形中，發送方設備或發送方程序代碼可包括一個以上FEC編碼器，即源數據在一系列多個FEC編碼器中被變換成經編碼數據。類似地，在接收方，可存在一個以上應用於從收到經編碼數據生成源數據的FEC解碼器。數據可被視為被劃分成碼元。編碼器是從源碼元或輸入碼元的序列生成經編碼碼元或輸出碼元的計算機系統、設備、電子電路或諸如此類，且解碼器是從接收到或恢復出的經編碼碼元或輸出碼元恢復源碼元或輸入碼元的序列的配對物。編碼器和解碼器在時間和/或空間上被信道分開，且任何接收到的經編碼碼元可能與相應的所傳送經編碼碼元不完全相同，並且它們可能不按與它們被傳送的順序完全相同的順序被接收。碼元的「大小」可 以用比特來度量，無論該碼元實際上是否被斷成比特流，其中當碼元是選自有2M個碼元的字母表時，碼元具有M比特的大小。在本文中的許多示例中，碼元是以字節來度量的，且碼可能位於有256種可能性的域上(有256種可能的8比特模式)，但是應理解，可以使用不同的數據度量單位，且以各種方式來度量數據是公知的。
Luby I描述了使用諸如鏈式反應碼之類的代碼以計算高效、存儲器高效和帶寬高效的方式解決糾錯。由鏈式反應編碼器產生的經編碼碼元的一種屬性在於接收方只要已接收到足夠的經編碼碼元就能夠恢復出原始文件。具體而言，為了以高概率恢復原始的K個源碼元，接收方需要大約K+A個經編碼碼元。給定情形的「絕對接收開銷」由值A表示，而「相對接收開銷」可演算為比率A/K。絕對接收開銷是除了資訊理論最小數據量以外還需要接收多少額外數據的度量，且它可取決於解碼器的可靠性並且可作為源碼元數目K的函數而變化。類似地，相對接收開銷A/Κ是除了資訊理論最小數據量以外還需要接收多少額外數據相對於正被恢復的源數據的大小的 度量，且也可取決於解碼器的可靠性並且可作為源碼元數目K的函數而變化。鏈式反應碼對於基於分組的網絡上的通信極其有用。然而，它們有時可能是計算相當密集的。若在使用鏈式反應或其他無碼率(rateless)碼進行編碼的動態編碼器之前使用靜態編碼器來編碼源碼元，則解碼器或許能夠更頻繁或更容易地進行解碼。例如，此類解碼器在Shokrollahi I中示出。在其中示出的示例中，源碼元是靜態編碼器的輸入碼元，靜態編碼器產生的輸出碼元作為動態編碼器的輸入碼元，動態編碼器產生的輸出碼元是經編碼碼元，其中動態編碼器是能以相對於輸入碼元數目並非為固定比率的數量生成數個輸出碼元的無碼率編碼器。靜態編碼器可包括一個以上固定碼率編碼器。例如，靜態編碼器可包括漢明(Hamming)編碼器、低密度奇偶校驗(「LDPC」)編碼器、高密度奇偶校驗(「HDPC」)編碼器和/或諸如此類。鏈式反應碼具有以下屬性當在解碼器處從收到碼元恢復出一些碼元時，這些碼元或許能被用來恢復附加碼元，附加碼元又可被用來恢復更多碼元。較佳地，解碼器處碼元求解的鏈式反應可持續進行，以使得在收到碼元池被用盡之前恢復出所有合意碼元。較佳地，執行鏈式反應編碼和解碼過程的計算複雜度較低。解碼器處的恢復過程可涉及確定接收到哪些碼元，創建可將原始輸入碼元映射到接收到的那些經編碼碼元的矩陣，隨後將該矩陣求逆並執行該逆矩陣與收到經編碼碼元矢量的矩陣乘法。在典型的系統中，此舉的蠻力實現會耗費過多計算努力和存儲器需求。當然，對於特定的收到經編碼碼元集合，可能無法恢復出所有原始輸入碼元，即使在有可能恢復出所有原始輸入碼元的場合，要計算出結果可能也是計算昂貴的。ShokrollahiII描述了被稱為「鈍化(inactivation) 」的辦法,其中解碼在兩個步驟中發生。在第一步驟中，解碼器觀察它具有哪些可用的收到經編碼碼元、矩陣可能看似如何，並至少大致確定在給定這些收到經編碼碼元的情況下將允許鏈式反應過程完成的解碼步驟序列。在第二步驟中，解碼器根據所確定的解碼步驟序列來運行鏈式反應解碼。這可以按存儲器高效的方式(即，比存儲器效率較低的過程要求較少存儲器存儲進行操作的方式)進行。在鈍化辦法中，第一解碼步驟涉及操縱矩陣或其等效物以確定能解出的某個數目的輸入碼元並且當該確定中斷時，將輸入碼元之一指定為「鈍化碼元」並通過假定該鈍化碼元其實被解出了來繼續該確定過程，隨後在結束時，使用高斯消元法或其他某種方法對遠小於原始解碼矩陣的矩陣求逆來求解這些鈍化碼元。使用該確定，可對收到經編碼碼元執行鏈式反應序列以得到恢復出的輸入碼元，恢復出的輸入碼元可以是所有原始輸入碼元或合適的原始輸入碼元集合。
對於對解碼器強加了嚴格約束的一些應用，諸如在解碼器為具有有限存儲器和計算能力的低功率設備的場合，或者諸如當對可允許的絕對或相對接收開銷有嚴格約束時，可關於以上描述的鈍化辦法指出改善的方法。另外，用於在受最小子碼元大小約束的情況下將文件或大數據塊劃分成儘可能少的源塊、且隨後在受最大子塊大小約束的情況下將源塊拆分成儘可能少的子塊的方法可能是有用的。發明簡要概述根據依照本發明各方面的編碼器的一個實施例，發送方的編碼器在通信信道上從一個或更多個發送方向一個或更多個接收方傳送有序源碼元集合，其中該編碼器生成包括從源碼元生成的多個經編碼碼元的待發送數據。在第一步驟，使用可逆的方法從源碼元生成中間碼元，即，還存在用於從中間碼元生成源碼元的逆方法。在另一步驟，將中間碼元劃分成第一中間碼元集合和第二中間碼元集合，其中第一中間碼元集合中有至少一個中間碼元且第二中間碼元集合中有至少一個中間碼元，並且從來自這兩個集合中每個集合的至少一個中間碼元生成至少一個經編碼碼元。在一些變型中，存在兩個以上集合。在一些實施例中，生成第一和第二臨時碼元集合的值，其中第一臨時碼元集合的值取決於第一中間碼元集合的值且第二臨時碼元集合的值取決於第二中間碼元集合的值。經編碼碼元的值是從第一和第二臨時碼元集合生成的。在一些變型中，可生成的經編碼碼元的數目獨立於源碼元數目。還提供了解碼器實施例。根據依照本發明各方面的解碼器的一個實施例中，接收機的解碼器接收從中間碼元生成的經編碼碼元，其中中間碼元是使用可逆的方法從源碼元生成的，即，還存在用於從中間碼元生成源碼元的逆方法，並且其中至少一個中間碼元被指定為永久鈍化碼元且存在不在永久鈍化碼元當中的至少另一個中間碼元。解碼器從收到經編碼碼元解碼中間碼元集合，且解碼器計及至少一個永久鈍化碼元，並使用該逆方法從經解碼中間碼元集合生成源碼元。在解碼時，調度解碼步驟，且擱置對永久鈍化碼元的調度。永久鈍化碼元可使用新穎的或常規的方法來求解，並隨後被用來求解其他中間碼元。求解永久鈍化碼元(以及若使用了的其他運行中鈍化)的一種辦法可能是通過應用高斯消元法來求 解鈍化碼元。剩餘中間碼元中的一些基於恢復出的永久鈍化碼元和收到經編碼碼元的值來恢復。在解碼方法的一些變型中，永久鈍化碼元包括來自編碼實施例的第二中間碼元集合。在解碼方法的一些變型中，永久鈍化碼元包括中間碼元的子集，其中相應的編碼方法不是多級鏈式反應碼。此類編碼方法可包括用於該中間碼元的子集的Tornado碼、Reed-Solomon碼、鏈式反應碼(Luby I中描述的示例)或諸如此類中的一個或更多個。中間碼元被用於編碼和解碼，其中針對合意的性能特性集(諸如可解碼性)指示用於從源碼元生成中間碼元的方法以及相應的逆方法。在一些實施例中，中間碼元包括源碼元。在一些實施例中，中間碼元包括源碼元連同從源碼元生成的冗餘碼元，其中冗餘碼元可以是鏈式反應碼元、LDPC碼元、HDPC碼元、或其他類型的冗餘碼元。替換地，中間碼元可基於碼元之間的規定關係，例如中間碼元與源碼元之間的關係、以及中間碼元之間的附加LDPC和HDPC關係，其中解碼方法被用於基於該規定關係從源碼元生成中間碼元。這些方法和系統可由電子電路或由執行編程指令且具有用於實現編碼和/或解碼的恰適指令程序代碼 的處理設備實現。通過本發明可達成眾多益處。例如，在具體實施例中，編碼數據以在信道上傳輸的計算花銷得以減少。在另一個具體實施例中，解碼此類數據的計算花銷得以減少。在另一個具體實施例中，絕對和相對接收開銷減少相當多。取決於實施例，可達成這些益處中的一個或更多個。貫穿本說明更詳細且在以下更具體地提供這些及其他益處。對本文中公開的本發明的本質和優點的進一步理解可參照本說明的其餘部分和附圖來實現。附圖簡沭圖I是使用包括永久鈍化的多級編碼連同其他特徵和要素的通信系統的框圖。圖2是在本文中的其他各圖中使用的變量、陣列及諸如此類的表。圖3是圖I中所示的編碼器的具體實施例的框圖。圖4是更詳細地示出圖3的動態編碼器的框圖。圖5是解說永久鈍化(PI)編碼過程的流程圖。圖6是解說動態編碼過程的流程圖。圖7是演算用於碼元演算的權重的操作的流程圖。圖8解說了可存儲在存儲器中、可用於基於查找值來確定碼元的度的表。圖9示出了編碼或解碼過程中使用的矩陣。

圖10示出關於具體最小多項式表示圖9中所示的矩陣的各部分的方程。圖11是解說用於建立在編碼或解碼中使用的陣列的過程的流程圖。圖12解說了將由解碼器使用表示解碼器已知的R個靜態碼元或方程的子矩陣SE求解以從表示收到經編碼碼元的陣列DO恢復表示恢復出的源碼元的陣列CO的方程組的矩陣表示。圖13解說了使用OTF鈍化從圖12的矩陣的行/列置換得到的矩陣。圖14是描述用於生成圖12中的矩陣的過程的框圖。圖15解說了將由解碼器使用子矩陣SE和與永久鈍化碼元相對應的子矩陣求解以從表示收到經編碼碼元的陣列DO恢復表示恢復出的源碼元的陣列CO的方程組的矩陣表
/Jn ο圖16是解說用於生成如可在圖12的矩陣或圖15的矩陣中使用的LT子矩陣的過程的流程圖。圖17是解說用於生成如可在圖15的矩陣中使用的PI子矩陣的過程的流程圖。圖18是矩陣生成器的框圖。圖19是解說用於生成SE子矩陣的過程的流程圖。圖20是解說用於生成PI子矩陣的過程的流程圖。圖21是解說用於在解碼器中求解恢復出的碼元的過程的流程圖。圖22解說將由解碼器求解以從表示收到經編碼碼元的陣列DO恢復表示恢復出的源碼元的陣列CO的方程組在置換之後的矩陣表示。圖23解說將由解碼器求解且與圖26中所示的矩陣相對應的方程組的矩陣表示。圖24解說可用作解碼過程的一部分的矩陣表示。圖25解說可用作解碼過程的另一部分的矩陣表示。
圖26解說在部分求解之後將由解碼器求解的方程組的矩陣表示。
圖27是解說用於在解碼器中求解恢復出的碼元的另一過程的流程圖。圖28解說將由解碼器求解的方程組的矩陣表示。圖29解說將由解碼器求解的方程組的矩陣表示。圖30解說示例編碼系統，其可實現為硬體模塊、軟體模塊、或存儲在程序存儲中並由處理器執行的可能作為並非如該圖中所示地分開的綜合代碼單元的程序代碼的部分。圖31解說示例解碼系統，其可實現為硬體模塊、軟體模塊、或存儲在程序存儲中並由處理器執行的可能作為並非如該圖中所示地分開的綜合代碼單元的程序代碼的部分。所附的附錄A是用於編碼器/解碼器系統、糾錯方案、以及針對數據對象的可靠遞送的應用的具體實施例的代碼規範，有時帶有所使用的本發明的細節，其還包括系統編碼器/解碼器如何可用於對象遞送傳輸的規範。應理解，附錄A中描述的具體實施例並不限制本發明的示例且本發明的一些方面可使用附錄A的教示而其他方面可能不使用附錄A的教示。還應理解，附錄A中的限定性語句關於具體實施例的要求可能是限定性的，且此類限定性語句可能涉及或可能不涉及所要求保護的發明，且因此權利要求語言不受此類限定性語句限定。具體實施例的詳細描述用於實現本文中引述的編碼器和解碼器的各部分的細節由Luby I、Luby II、Shokrollahi I、Shokrollahi II、Shokrollahi 111 > Luby III、和 Shokrollahi IV 提供且出於簡明起見不在此全部重複。它們的全部公開內容通用地通過援引納入於此，且應理解，除非另行指出，否則其中的實現不是本發明所必要的，且還可以使用許多其他變型、修改或替換。如本文中所描述的多級編碼在多級內對源數據進行編碼。一般但不總是，第一級向源數據添加預定量的冗餘。第二級然後使用鏈式反應碼或諸如此類以從原始源數據以及由第一級編碼計算出的冗餘碼元產生經編碼碼元。在一個具體實施例中，使用鏈式反應解碼過程來首先解碼收到數據。若該過程沒有成功地完整恢復出原始數據，則可應用第二解碼步驟。本文中教示的一些實施例可應用於許多其他類型的代碼，例如應用於如網際網路工程任務組(IETF)請求註解(RFC) 5170中描述的代碼(下文稱為「 IETF LDPC碼」)、以及應用於美國專利號6，073，250、6，081，909和6，163,870中描述的代碼(下文稱為「Tornado碼」)，從而改善這些類型的代碼的可靠性和/或CPU和/或存儲器性能。本文中教示的一些實施例的一個優點在於與單獨的鏈式反應編碼相比需要較少的算術運算來產生經編碼碼元。包括第一級編碼和第二級編碼的一些具體實施例的另一優點在於第一級編碼和第二級編碼可以在分開的時間和/或由分開的設備完成，因此劃分了計算負荷，並使總計算負荷還有存儲器大小及存取模式要求最小化。在多級編碼的實施例中，在第一級編碼期間從輸入文件生成冗餘碼元。在這些實施例中，在第二級編碼中，從輸入文件和冗餘碼元的組合生成經編碼碼元。在這些實施例的一些中，可按需生成經編碼碼元。在其中第二級包括鏈式反應編碼的實施例中，每個經編碼碼元可以在不考慮其他經編碼碼元是如何生成的情況下生成。這些經編碼碼元一旦被生成然後就可被放入分組並被傳送到其目的地，其中每個分組包含一個或更多個經編碼碼元。還可以改為或者同時使用非分組化傳輸技術。如本文中使用的，術語「文件」是指存儲在一個或更多個源處且將作為一個單元被遞送到一個或更多個目的地的任何數據。因此，來自文件伺服器或計算機存儲設備的文檔、圖像和文件皆是能被遞送的「文件」的示例。文件可以有已知的大小(諸如存儲在硬碟上的一兆字節圖像)或可以有未知的大小(諸如從流送源的輸出獲取的文件)。無論是哪種，文件是源碼元的序列，其中每個源碼元在文件內有位置且具有值。「文件」還可用於指流送源的短部分，即數據流可被劃分成一秒區間，且每個此類一秒區間內的源數據塊可被視為「文件」。作為另一示例，來自視頻流送源的數據塊可基於例如由能播放該視頻流的視頻系統定義的該數據的優先級被進一步劃分成多個部分，且每個塊的每一部分可被視為「文件」。因此，術語「文件」被一般性地使用且不旨在是廣義限定性的。如本文中所使用的，源碼元表示待傳送或傳達的數據，且經編碼碼元表示基於源碼元生成的、在通信網絡上傳達或被存儲以實現對源碼元的可靠接收和/或再生的數據。中間碼元表示在編碼或解碼過程的中間步驟期間使用或生成的碼元，其中典型地存在用於從源碼元生成中間碼元的方法以及相應的用於從中間碼元生成源碼元的逆方法。輸入碼元表示在編碼或解碼過程期間向一個或更多個步驟輸入的數據，且輸出碼元表示在編碼或解碼過程期間從一個或更多個步驟輸出的數據。在許多實施例中，這些不同類型或標記的碼元可以是相同的或者至少部分地包括其他類型的碼元，且在一些示例中，這些術語被可互換地使用。在一示例中，假設待傳送的文件是有1，000個字符的文本文件，每個字符被視為源碼元。若這些1，000個源碼元按原樣被提供給編碼器，編碼器又輸出被傳送的經編碼碼元，則源碼元也是輸入碼元。然而，在其中這1，000個源碼元在第一步驟中被轉換成1，000個(或者更多或更少個)中間碼元且中間碼元被提供給編碼器以在第二步驟中生成經編碼碼元的實施例中，則在第一步驟中，源碼元是輸入碼元且中間碼元是輸出碼元，以及在第二步驟中，中間碼元是輸入碼元且經編碼碼元是輸出碼元，然而，源碼元是該兩步驟編碼器的總輸入碼元且經編碼碼元是該兩步驟編碼器的總輸出碼元。在此示例中，若編碼器是系統編碼器，則經編碼碼元可包括源碼元連同從中間碼元生成的修復碼元，而中間碼元不同於源碼元和經編碼碼元兩者。在此示例中，若編碼器替代地是非系統編碼器，則中間碼元可包括源碼元連同在第一步驟中使用例如LDPC和/或HDPC編碼器從源碼元生成的冗餘碼元,而經編碼碼元不同於源碼元和中間碼元兩者。在其他示例中，有更多碼元且每個碼元表示一個以上的字符。在發射機中存在源-中間碼元轉換的任一種情形中，接收機可具有相應的中間-源碼元轉換作為逆轉換。傳輸是通過信道從一個或更多個發送方向一個或更多個接收方傳送數據以遞送文件的過程。發送方有時也被稱為編碼器。若一個發送方通過理想信道連接到任何數量的接收方，則由於所有數據都將被正確接收，因此收到數據可能是源文件的確切副本。在此，假設信道不是理想的，這正是大多數實際信道的情形。在許多信道不理想中，兩種感興趣的不理想是數據擦除和數據不完整(其可被視為數據擦除的特殊情況)。數據擦除發生在信 道丟失或丟棄數據時。數據不完整發生在接收方在直到一些數據已掠過了接收方才開始接收數據、接收方在傳輸結束前停止接收數據、接收方選擇只接收所傳送數據的一部分、和/或接收方間歇地停止並再次開始接收數據時。作為數據不完整的示例，移動衛星發送方可能正在發射表示源文件的數據並在接收方處於射程內之前開始傳輸。一旦接收方處於射程內，數據可以被接收直到該衛星移出射程，此時接收方可以重定向其衛星天線(它在該時間期間不接收數據)以開始接收由移進射程內的另一衛星發射的關於相同輸入文件的數據。如從閱讀本描述應明白的，數據不完整是數據擦除的特殊情況，因為接收方可以將數據不完整視為如同接收方整段時間都處在射程內但信道丟失了直至接收方開始接收數據前的所有數據(且接收方有相同的問題)。而且，如在通信系統設計中公知的，可檢測差錯可通過簡單地丟棄所有具有可檢測差錯的數據塊或碼元而被認為等效於擦除。在一些通信系統中，接收方接收由多個發送方生成的數據、或由一個發送方使用多個連接生成的數據。例如，為了加快下載，接收方可同時連接到一個以上傳送關於相同文件的數據的發送方。作為另一示例，在多播傳輸中，多個多播數據流可以被傳送以允許接收方能連接到這些流中的一個或更多個流，從而將集總傳輸速率與將這些接收方連接到發送方的信道的帶寬匹配。在所有此類情形中，關注的是要確保所有所傳送數據對於接收方是能獨立使用的，即多個源數據在這些流之間不是冗餘的，即使當傳輸速率對於不同流相差很大時以及當有任意丟失模式時亦然。一般而言，通信信道是連接發送方和接收方以進行數據傳輸的信道。通信信道可以是實時信道，其中信道在獲得數據時就將數據從發送方移到接收方，或者通信信道可能是存儲信道，該信道在將數據從發送方運輸到接收方時存儲一些或全部的數據。後者的示例是盤存儲或其他存儲設備。在該示例中，生成數據的程序或設備可以被認為是將數據傳送給存儲設備的發送方。接收方是從存儲設備讀取數據的程序或設備。發送方用來將數據送到存儲設備上的機制、存儲設備本身以及接收方用來從存儲設備獲取數據的機制共同構成了信道。如果存在這些機制或存儲設備會丟失數據的機會，則它可被視為通信信道中的數據擦除。當發送方和接收方由其中碼元會被擦除的通信信道隔開，則優選不傳送輸入文件的確切副本，而是改為傳送從輸入文件生成的幫助擦除恢復的數據。編碼器是處理該任務的電路、設備模塊或代碼段。查看編碼器操作的一種方式在於編碼器從源碼元生成經編碼碼元，其中源碼元值序列表示輸入文件。每個源碼元因此將在輸入文件內有位置且具有值。解碼器是從由接收方接收到的經編碼碼元重構源碼元的電路、設備、模塊或代碼段。在多級編碼中，編碼器和解碼器有時進一步被分成各自執行不同任務的子模塊。在多級編碼系統的實施例中，編碼器和解碼器可被進一步分成各自執行不同任務的子模塊。例如，在一些實施例中，編碼器包括本文所謂的靜態編碼器和動態編碼器。如本文中使用的，「靜態編碼器」是從源碼元集合生成數個冗餘碼元的編碼器，其中冗餘碼元的數目是在編碼前確定的。當在多級編碼系統中使用靜態編碼時，源碼元與使用靜態編碼器從源碼元生成的冗餘碼元的組合往往被稱為中間碼元。潛在可能的靜態編碼代碼的示例包括Reed-Solomon碼、Tornado碼、漢明碼、諸如IETF LDPC碼之類的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描述了在本發明的實施例中可以採用的各種形式的關鍵字法。在其他優選實施例中，諸如在附錄A中描述的一個實施例中，經編碼碼元的關鍵字被稱為「經編碼碼元標識符」、或「編碼碼元標識符」，或更簡單地稱為「ESI 」。多級編碼在預期有數據擦除的場合或接收方沒有正好在傳輸開始和結束時開始和結束接收的場合尤其有用。後一種情況在此被稱為「數據不完整」。關於擦除事件，多級 編碼享有在Luby I中教示的鏈式反應編碼的許多益處。具體而言，經多級編碼的碼元是信息加性的，所以可以使用任何合適數量的分組來恢復輸入文件以達到合意準確度。在使用多級編碼時，這些狀況不會負面地影響通信過程，因為用多級編碼生成的經編碼碼元是信息加性的。例如，若由於噪聲突發引起數據擦除而導致一百個分組丟失，則可以在該突發後獲取額外的一百個分組來取代被擦除分組的丟失。如果因為在發射機開始傳送時接收機沒有調諧到該發射機而導致成千個分組丟失，則接收機可以僅從任何其他傳輸期或甚至從另一發射機獲取這成千個分組。使用多級編碼，接收機不限於獲取任何特定分組集合，所以它可以從一個發射機接收一些分組、切換到另一發射機、丟失一些分組、錯過給定傳輸的起始或結束，且仍能恢復輸入文件。在沒有接收機-發射機協調的情況下加入和離開傳輸的能力有助於簡化通信過程。在一些實施例中，使用多級編碼來傳送文件可以包括從輸入文件生成、形成或提取源碼元，計算冗餘碼元，將源碼元和冗餘碼元編碼成一個或更多個經編碼碼元一其中每個經編碼碼元是基於其關鍵字獨立於所有其他經編碼碼元生成的，以及將經編碼碼元在信道上傳送給一個或更多個接收方。另外，在一些實施例中，使用多級編碼來接收(以及重構)輸入文件的副本可以包括從一個或更多個數據流接收經編碼碼元的某個集合或子集，並從收到經編碼碼元的值和關鍵字來解碼源碼元。系統碼和非系統碼系統碼是其中源碼元在能被傳送的經編碼碼元當中的代碼。在這種情形中，經編碼碼元包括源碼元和從源碼元生成的也稱為修復碼元的冗餘碼元。出於各種原因，對於許多應用而言，系統碼優於非系統碼。例如，在文件遞送應用中，有用的是能夠在正使用數據生成修複數據的同時按順序次序開始傳送該數據，其中生成修複數據的過程可能要花費一定量的時間。作為另一示例，許多應用優選以未修改形式按順序次序向一個信道發送原始源數據，並向另一信道發送修複數據。此舉的一個典型原因是為了既支持未納入FEC解碼的舊式接收機，與此同時還向納入了 FEC解碼的增強型接收機提供更好的體驗，其中舊式接收機僅加入源數據信道，而增強型接收機加入源數據信道和修複數據信道兩者。在這些以及相關類型的應用中，有時可能是以下情形由接收機接收到的源碼元中的丟失模式和丟失分數與收到修復碼元中經歷的丟失模式和丟失分數有很大不同。例如，當源碼元在修復碼元之前被發送時，由於信道的突發性丟失狀況，源碼元中的丟失分數和模式可能與修復碼元中相應的丟失分數和模式有很大不同，且源碼元中的丟失模式與丟失是均勻隨機的情況下可能的典型丟失模式相去甚遠。作為另一示例，當在一個信道上發送源數據而在另一信道上發送修複數據時，這兩個信道上可能存在相當不同的丟失狀況。因此，具有在不同類型的丟失狀況下工作良好的系統FEC碼是合意的。儘管本文中的示例引述系統碼(其中輸出或經編碼碼元包括源或輸入碼元)或非系統碼，但除非另行指出，否則本文中的教示應被認為可應用於這兩種代碼。ShokrollahiIII教示了用於將非系統鏈式反應碼轉換成系統碼以使得如此構造的系統碼維持非系統碼的穩健性屬性的方法。具體而言，使用Shokrollahi III中教示的方法，所構造的系統碼具有以下屬性 丟失的源碼元和丟失的修復碼元之間就解碼器的可恢復性而言差別很小，即，對於給定的總丟失量，解碼恢復概率基本相同，幾乎獨立於源碼元中的丟失比例相比於修復碼元中的丟失比例。此外，經編碼碼元中的丟失模式並不顯著影響解碼恢復概率。比較而言，對於其他系統碼的構造，諸如針對Tornado碼或針對IETF LDPC碼描述的那些構造，在許多情形中，丟失的源碼元和丟失的修復碼元之間就解碼器的可恢復性而言差別很大，即，對於給定的總丟失量，解碼恢復概率寬泛地變化，取決於源碼元中的丟失比例相比於修復碼元中的丟失比例。此外，經編碼碼元中的丟失模式可能對解碼恢復概率有強影響。若經編碼碼元的丟失在所有經編碼碼元中是均勻隨機的，則Tornado碼和IETF LDPC碼有合理良好的恢復屬性，但恢復屬性隨著丟失模型偏離均勻隨機丟失而退化。因此，在這種意義上，Shokrollahi III中教示的實施例具有勝於系統碼的其他構造的優點。對於具有取決於丟失的源碼元和丟失的修復碼元的比例以及取決於丟失模式就解碼器的可恢復性而言有強影響的屬性的FEC碼，在適用的情況下克服這種屬性的一種辦法是按均勻隨機次序發送經編碼碼元，即按均勻隨機次序發送源碼元和修復碼元的組合，因此源碼元隨機地散布在修復碼元之間。按隨機次序發送經編碼碼元具有以下優點無論信道丟失模型如何、無論丟失是突發性的還是均勻隨機的還是其他某種丟失類型，對經編碼碼元的丟失仍是隨機的。然而，如上所述，這種辦法對於一些應用不是合意的，例如對於其中期望在修復碼元之前按順序發送源碼元、或其中源碼元是在與修復碼元不同的信道上 發送的應用。在此類情形中，希望其中經編碼碼元中的丟失模式對解碼器的恢復屬性影響不大的系統碼的構造,且本文中提供了一些示例。如本文中所使用的，「隨機」和「偽隨機」往往是等效的和/或可互換的且可取決於上下文。例如，隨機丟失可以指信道丟失了哪些碼元，其可以真正是隨機事件，而對碼元鄰元的隨機選擇可能實際上是根據非隨機過程的可重複偽隨機選擇，但與真正隨機選擇的情形具有相同或相似的屬性或行為。除非顯式地或通過上下文另行指出，否則將某事表徵為隨機的不意味著排除偽隨機。在針對此類系統FEC編碼器的一種辦法中，由包括多個編碼器子塊或子過程的編碼器獲得源碼元，這多個編碼器子塊或子過程之一作用為生成中間碼元的解碼器，這些中間碼元是另一子塊或子過程的輸入碼元。中間碼元隨後被施加到另一子塊或子過程，該另一子塊或子過程將這些中間碼元編碼成經編碼碼元，從而經編碼碼元包括從一個一致性過程生成的源碼元(連同附加的冗餘碼元)，藉此提供勝於作為使用一個過程(例如，複製)來獲取經編碼碼元集合的源碼元並使用另一過程來獲取該經編碼碼元集合的冗餘碼元的系統編碼器的編碼器的穩健性益處和其他益處。輸出編碼可以是鏈式反應編碼器、靜態編碼器或其他變型。附錄A描述了系統碼實施例。在閱讀本公開之後，本領域普通技術人員應能夠容易擴展Shokrollahi III的教示以應用於諸如Tornado碼和IETF LDPC碼之類的系統碼，從而產生這些代碼的也是系統碼但具有更好恢復屬性的新版本。具體而言，通過應用以下描述的一般性方法獲得的這些代碼的新版本被增強以具有以下屬性源碼元中的丟失比例相比於修復碼元中的丟失比例不會顯著影響解碼恢復概率，此外丟失模式不會顯著影響解碼恢復概率。因此，這些代碼能被有效地用在要求使用具有不會受源碼元和修復碼元中的不同分數丟失量或不同丟失模式強烈影響的恢復屬性的系統FEC碼的上述應用中。該新編碼方法能被一般性地應用於系統FEC碼、非系統FEC碼、固定碼率FEC碼和鏈式反應FEC碼的編碼以產生用於新的增強型系統FEC碼的總體編碼方法。還存在可應用的相應的新解碼方法。編碼器中的解碼器的示例
現在將提供編碼器中的解碼器的示例。令編碼方法E為(發射機中或別處的)編碼器針對從K個源碼元生成N個經編碼碼元的固定碼率(非系統或系統)FEC碼E使用的編碼方法，其中N至少為K。類似地，令解碼方法E為接收機中或別處的解碼器使用的針對FEC碼E的相應解碼方法。假設FEC碼E具有以下屬性N個經編碼碼元中的K個經編碼碼元的隨機集合足以使用解碼方法E以合理概率恢復原始的K個源碼元，其中合理概率可能例如為概率1/2。合理概率可以是由使用或應用設定的某個要求且可以為不同於1/2的值。應理解，特定碼的構造無需因特定恢復概率而異，但應用和系統可針對其特定穩健性程度來設計。在一些實例中，可通過考慮K個以上碼元並隨後使用解碼過程確定這些所考慮碼元中允許成功解碼的K個碼元的集合來提高恢復概率。 假設對於FEC碼E，ESI (經編碼碼元標識符)與每個經編碼碼元相關聯且該ESI標識該經編碼碼元。在不失一般性的情況下，ESI在本文中用0、1、2、…、N-I標記。在用於使用針對FEC碼E的方法生成的系統FEC碼F的系統編碼方法F的一個實施例中，K和N是輸入參數。FEC碼F的源碼元將具有ESI O、…、K-1，且FEC碼F的修復碼元將具有ESI K、…、N-I。針對FEC碼F的系統編碼方法F使用如下由硬體和/或軟體執行的針對FEC碼E的編碼方法E和解碼方法E從K個源碼元C (O)、…、C (K-I)生成N個經編碼碼元(I)隨機地置換與FEC碼E相關聯的N個ESI以得到FEC碼E經置換ESI集合X(O),…、X(N-I)，其中該經置換ESI集合被組織成使得能關於ESI的置換次序X(O)、…、X (K-I)從FEC碼E的頭K個經編碼碼元解碼出FEC碼E的K個源碼元，(2)對於每個i = 0，…，N-1，將FEC碼F的ESI i與FEC碼E的ESI X(i)相關聯，(3)對於每個i = O,…，K-1，將具有ESI X⑴的FEC碼E經編碼碼元的值設為源碼元C(i)的值，(4)向具有相應的FEC碼E ESI X(O),…、X(K-I)的源碼元C (O)、…、C(K-I)應用解碼方法E以生成經解碼碼元E(0)、…、E(K-l)，以及(5)向經解碼碼元E(O)、···、Ε (K-I)應用編碼方法E以生成具有相關聯FEC碼ESIO、…、N-I 的 FEC 碼 E 經編碼碼元 D (O)、...、D(N_1)，(6)編碼方法F的具有ESI O、I、…、N-1的經編碼碼元為D(X(O))、D(X(I))、…、D (X(N-I)) ο注意，編碼方法F的輸出為N個經編碼碼元，其中頭K個經編碼碼元為具有相關聯ESI 0、1、…、K-I的源碼元C (O)、···> C(K-I)0因此，編碼方法F產生對源數據的系統編碼。與剛才描述的編碼方法F相對應的解碼方法F的一個實施例如下，其中K和N是該方法貫穿始終使用的輸入參數。該解碼方法F從具有相關聯FEC碼F ESI Y(O),…、Y(K-I)的K個收到經編碼碼元D (O)、…、D (K-I)恢復K個源碼元C (O)、…、C (K-I)。收到碼元無需正好是所發送碼元。由硬體和/或軟體執行的該方法如下(I)隨機地置換與FEC碼E相關聯的N個ESI以得到FEC碼E經置換ESI集合X(O),…、X(N-I)，其中該經置換ESI集合被組織成使得能關於ESI的置換次序X(O)、…、X (K-I)從FEC碼E的頭K個經編碼碼元解碼出FEC碼E的K個源碼元，(2)向具有相關聯FEC碼E ESI X(Y(O))、…、X(Y(K-I))的經編碼碼元D (O)、…、D(K-I)應用解碼方法E以生成經解碼碼元E (O)、->E(K-1),(3)使用編碼方法E從E(O)、…、E(K-I)生成具有FEC碼E ESI X(O)、…、X(K-I)的經編碼碼元C (O)、-,C(K-I),(4)具有ESI O、…、K-I的FEC碼F的經解碼源碼元為C (O)、...、C(K_1)。如剛才所描述地操作的方法和裝置具有一些合意屬性。例如，考慮FEC碼E，其為系統碼且具有能以高概率解碼K個收到經編碼碼元的隨機集合的屬性，但還具有當接收到K個經編碼碼元且收到經編碼碼元中的源碼元比例不接近K/N時則其不能以高概率來解碼的屬性。在這種情形中，該實施例描述了使用FEC碼E的編碼和解碼方法的新FEC碼F，並且該新FEC碼F具有以下合意屬性其將從K個收到經編碼碼元的集合獨立於作為源碼元的收到經編碼碼元的比例以高概率進行解碼。上面的實施例有許多變形。例如，在編碼方法F的步驟⑴中，ESI的隨機置換可以是偽隨機的或者基於產生對ESI的良好選擇但既不是隨機也不是偽隨機的其他某種方法。在FEC碼E為系統碼的情形中，優選該置換中在步驟(I)中從系統ESI中選擇的頭K個ESI的分數與FEC碼E的碼率成比例，即與K/N成比例。優選由新編碼方法F在步驟(I)中作出的對ESI的隨機選取可由簡潔的數據量來表示，例如由用於公知或協定的偽隨機生成器的種子連同用於基於該種子和偽隨機生成器如何工作來選取ESI的協定方法來表示，從而該新解碼方法F可在步驟(I)中基於相同的種子以及用於生成ESI的偽隨機生成器和方法作出完全相同的ESI置換選取。一般而言，優選新編碼方法F在步驟(I)中生成ESI序列使用的過程和新解碼方法F在步驟(I)中生成ESI序列使用的過程兩者生成相同的ESI序列，以確保新解碼方法F是新編碼方法F的逆。還存在其他變形，其中例如不使用顯式ESI，經編碼碼元的唯一性標識符改為藉由其關於其他經編碼碼元的位置或藉由其他手段。在以上描述中，FEC碼E的原始ESI被FEC碼F重新映射，從而源碼元的有序集合以連貫次序被指派ESI O、…、K-I，且修復碼元被指派ESI K、…、N-1。其他變形是可能的，例如ESI的重新映射可在發送方處剛好在編碼方法F已生成經編碼碼元之後但在傳送經編碼碼元之前發生，並且ESI的逆重新映射可在接收方處當經編碼碼元被接收時但在經編碼碼元被解碼方法F處理以恢復原始源碼元之前發生。作為另一變形，在新編碼方法F的步驟(I)中，置換可通過首先選擇K+A個FEC碼E ESI，其中A是為了確保有高概率的可解碼性而選取的值，並隨後在解碼過程的模擬期間確定K+A個ESI中哪K個ESI在解碼期間實際被使用，並且所選擇的置換可將K+A個ESI的初始集合中在解碼期間實際被使用的K個ESI選擇為該置換的頭K個ESI。類似變形應用於新解碼方法F。作為編碼方法F的另一變形，用於生成隨機置換的種子是針對K的值預先計算出的，以確保與步驟(I)中產生的ESI置換相關聯的FEC碼E的頭K個經編碼碼元是可解碼 的，且隨後該種子總是被用於編碼方法F和相應的解碼方法F的步驟(I)中的K以生成步驟(I)中的置換。用於選取此類種子的方法包括隨機地選取種子直至找到確保步驟(I)中的可解碼性的一個種子並隨後選擇該種子。替換地，可由編碼方法F動態地生成具有這些屬性的種子，且隨後該種子可被傳達給解碼方法F。作為編碼方法F的另一變形，在步驟(I)中可選擇部分置換，即在新編碼方法F的步驟(I)中無需生成所有ESI，且若步驟(5)和(6)中不需要全部經編碼碼元則無需生成所有經編碼碼元，例如由於這些經編碼碼元對應於作為經編碼碼元的部分的源碼元或者由於需要生成少於N個經編碼碼元。在其他變形中，無需重新計算新解碼方法F的步驟(3)和
(4)中的所有經編碼碼 元，因為一些收到經編碼碼元可對應於正被恢復的一些源碼元。類似地，在新解碼方法F的步驟(2)中，無需解碼所有K個碼元E (O)、…、E(K-I)，例如若步驟
(2)中解碼出的一些碼元在用於生成經編碼碼元的後續步驟中是不需要的。以上描述的方法和實施例具有許多應用。例如，編碼方法F和解碼方法F及其變形可應用於Tornado碼和IETF LDPC碼以提供改善的接收開銷和解碼失敗概率性能。一般而言，這些新方法適用於任何固定碼率FEC碼。這些新方法的變形還可應用於無固定碼率的FEC碼，即可應用於其中可生成的經編碼碼元的數目獨立於源碼元的數目的諸如鏈式反應碼之類的FEC碼。Shokrollahi III包含用於創建用於鏈式反應碼的系統編碼和解碼方法的類似教示。在一些實施例中，用於這些代碼的編碼和解碼方法E是Luby I>Luby II、ShokrollahiI、Shokrollahi II、Luby III、Shokrollahi IV中教示的那些編碼和解碼方法。為了描述系統編碼器，描述編碼方法E和解碼方法E並使用以上描述且從這些參考知曉的一般原理往往就足以將這些方法變換成系統編碼方法F和系統解碼方法F。因此，在閱讀本公開和所引述的參考之際，本領域普通技術人員應當明白如何利用描述編碼方法E和解碼方法E的教示並將它們應用於系統編碼方法F和系統解碼方法F或諸如此類。鈍化如Shokrollahi II中教示的,鈍化解碼是每當從一組已知線性方程值求解一組未知變量時就可結合置信傳播來應用的一般方法，並且在實現基於線性方程組的高效編碼和解碼方法時尤其有益。為了區別Shokrollahi II中描述的鈍化解碼與下文中描述的永久鈍化解碼，使用「運行中」鈍化(在各處縮寫為「0TF鈍化」)來指代Shokrollahi II的方法和教示，而使用「永久鈍化」來指代本文中其中提前選擇鈍化的方法和教示。置信傳播解碼的一個原則在於，在解碼過程期間每當有可能時，解碼器就應當使用依賴於一個剩餘未知變量的(可能簡化的)方程來求解該變量，且該方程因此與該變量相關聯，以及隨後通過消元剩餘的未使用方程對該解出變量的依賴性來簡化這些剩餘的未使用方程。例如在 Tornado 碼、諸如 Luby I、Luby II、Shokrollahi I、Shokrollahi II、Luby III、Shokrollahi IV中描述的鏈式反應碼、以及IETF LDPC碼的一些實施例中已使用了此類簡單的基於置信傳播的解碼過程。OTF鈍化解碼在多個階段中進行。在OTF鈍化解碼方法的第一階段中，每當置信傳播解碼過程由於不存在依賴於僅一個剩餘未知變量的剩餘方程而不能繼續時，解碼器將「0TF鈍化」 一個或更多個未知變量並關於置信傳播過程將它們視為「解出」並從剩餘方程「消元」(即使它們其實未被消元)，由此可能允許置信傳播解碼過程繼續進行。在第一階段期間被OTF鈍化的變量隨後例如在第二階段中例如使用高斯消元法或計算更高效的方法來求解，並且隨後在第三階段中，這些被OTF鈍化的變量的值被用來完整地求解與第一解碼階段期間的方程相關聯的變量。
如Shokrollahi II中更詳細地教示的OTF鈍化解碼除鏈式反應碼之外還可應用於許多其他類型的代碼。例如，其可被應用於一般類的LDPC和LDGM碼，尤其是應用於IETFLDPC碼和Tornado碼，從而導致改善這些類型的代碼的可靠性(降低解碼失敗的概率)和/或CPU和/或存儲器性能(提高編碼和/或解碼的速度和/或減小所要求的存儲器大小和/或存取模式要求)。鏈式反應碼實施例結合OTF鈍化解碼的一些變形在Shokrollahi IV中描述。其他變形在本申請中描述。系統概覽 圖I是使用多級編碼的通信系統100的框圖。其類似於Shokrollahi I中所示的，但在該情形中，編碼器115計及哪些中間碼元被「永久鈍化」的指定並在動態編碼過程期間對這些中間碼元與沒有被永久鈍化的中間碼元不同地操作。同樣，解碼器155在解碼時也計及被永久鈍化的中間碼元。如圖I中解說的，K個源碼元(C(0)、…、C(K-I))被輸入編碼器115，且若對變得對解碼器155可用的碼元的解碼成功，則解碼器115可輸出這K個源碼元的副本。在一些實施例中，流被解析成有K個碼元的塊，且在一些實施例中，有大於K的某個數目的源碼元的文件被分成大小為K的碼元塊且如此被傳送。在其中優選塊大小Γ >K的一些實施例中，可向K個源碼元添加K' -K個填充碼元。這些填充碼元可具有值0，或編碼器115和解碼器155兩者已知的任何其他固定值(或者能在解碼器155處以其他方式確定的值)。應理解，編碼器115可包括多個編碼器、模塊或諸如此類，且解碼器155也可以是這種情形。如所解說的，編碼器115還接收來自動態關鍵字生成器120的動態關鍵字序列和來自靜態關鍵字生成器130的靜態關鍵字序列，動態關鍵字生成器120和靜態關鍵字生成器130各自可由隨機數生成器135驅動。動態關鍵字生成器120的輸出可簡單地為基數序列，但無需是這種情形。關鍵字生成器的操作可如Shokrollahi I中所示的。應理解，附圖中所示的各種功能塊可實現為指定輸入被提供作為輸入信號的硬體，或者它們可由執行存儲在指令存儲器中並按恰適次序執行以執行相應功能的指令的處理器實現。在一些情形中，使用專門硬體來執行這些功能和/或執行程序代碼。程序代碼和處理器不總是被示出，但普通技術人員在閱讀本公開之際將知道如何實現此類細節。編碼器115還接收來自鈍化指定器125的輸入以及沿本文中別處描述的線向系統100輸入的其他參數。鈍化指定器125的輸出可包括表示出於解碼目的被指定為「永久鈍化」的中間碼元的數目的值P( 「PI列表」指示哪P個中間碼元在該列表上)。如別處解釋的，用於編碼過程的中間碼元在一些實施例中恰好是K個源碼元，而在其他實施例中，存在除了只複製K個源碼元之外還從這K個源碼元生成中間碼元的某種類型的處理、轉換、編碼、解碼等。輸入參數可包括由關鍵字生成器和/或編碼器的編碼過程使用的隨機種子(以下更詳細地描述)、要生成的經編碼碼元的數目、要生成的LDPC碼元的數目、要生成的HDPC碼元的數目、要生成的中間碼元的數目、要生成的冗餘碼元的數目等，和/或這些值中的一些是從編碼器115可用的其他值計算出的。例如，要生成的LDPC碼元的數目可完全從固定公式和K的值演算出來。編碼器115從其輸入生成經編碼碼元序列(B(Itl)'B(I1)A(I2)^")並將它們提供給傳送模塊140，傳送模塊140還接收來自動態關鍵字生成器120的動態關鍵字值(Ic^ I1,
12、…)，但若存在傳達該信息的其他方法則可能不必如此。傳送模塊140可能以此處無需更詳細描述的常規方式來傳達給予信道145的內容。接收模塊150接收經編碼碼元和動態關鍵字值(在需要的場合)。信道145可以是穿過空間的信道(用於從一地傳送以在另一地接收)或穿過時間的信道(用於記錄到介質以例如在以後的時間回放)。信道145可能導致丟失一些經編碼碼元。因此，解碼器115從接收模塊150接收到的經編碼碼元B(Ia)、B(Ib)、…可能不等同於傳送模塊發送的經編碼碼元。這由不同的下標索引來指示。解碼器155優選能夠使用動態關鍵字重新生成器160、隨機數生成器163和靜態關鍵字生成器165重新生成用於收到碼元的關鍵字(這些關鍵字可能不同)，並接收各種解碼參數作為輸入。這些輸入中的一些輸入可能是硬編碼的(即，在設備的構造期間輸入的)以及一些輸入可能是可改變的輸入。圖2是在其他各圖中以及貫穿本公開最經常使用的變量、陣列及諸如此類連同標註概要的表。除非另行指出，否則K表示用於編碼器的源碼元的數目，R表示靜態編碼器生成的冗餘碼元的數目，以及L是「中間碼元」的數目，即源碼元與冗餘碼元的組合且因此L =K+R。如以下解釋的，在靜態編碼器的一些實施例中，生成兩種類型的冗餘碼元。在此處的許多示例中使用的具體實施例中，第一集合包括LDPC碼元且第二集合包括HDPC碼元。在不失一般性的情況下，本文中的許多示例將LDPC碼元的數目稱為S以及將HDPC碼元的數目稱為H。可能有兩種以上冗餘碼元，因此不要求R = S+H。LDPC碼元和HDPC碼元具有不同的度分布，且本領域普通技術人員在閱讀本公開之際將看出如何使用非LDPC或HDPC碼元的冗餘碼元，但其中冗餘碼元包括兩個(或更多個)碼元集合，其中每個集合的度分布與其他集合的度分布不同。如公知的，冗餘碼元集合的度分布是指度的分布，其中冗餘碼元的度是指該冗餘碼元所依賴的源碼元的數目。P表示中間碼元中的永久鈍化碼元的數目。永久鈍化碼元是被指定進行特定處置——即在置信傳播網絡中為了繼續進行置信傳播而被「擱置」或「鈍化」(並隨後在解出鈍化碼元之後回來求解)一的那些碼元，其中永久鈍化碼元與其他鈍化碼元的區別在於永久鈍化碼元是在編碼器處被指定進行此類處置。N表示解碼器155對其進行解碼嘗試的收到碼元的數目，且A是「開銷」碼元的數目，即超出K的收到經編碼碼元數目。因此，A = N-K。K、R、S、H、P、N和A是整數，典型地全部大於或等於1，但在具體實施例中，其中一些可以為I或0(例如，R = O是其中沒有冗餘碼元的情形，且P = O退回到ShokrollahiII的情形，其中僅存在OTF鈍化)。源碼元矢量記為(C(O), ···, C(K-I)),且冗餘碼元矢量記為(C(K), ···, C(L-I)) 0因此，在系統情形中，(C(O)，…，C(L-I))表示中間碼元矢量。這些中間碼元中的數目P個中間碼元被指定為「永久鈍化」。「PI列表」指示中間碼元中的哪些是被永久鈍化的中間碼元。在許多實施例中，PI列表簡單地指向末P個中間碼元,即C(L-P)、…、C(L-I)，但這不是必要條件。假設該情形僅是為了簡化本描述的其餘部分。不在PI列表上的中間碼元在本文中被稱為「LT中間碼元」。在該示例中，LT中間碼元將為C(0)、…、C(L-P-l)。D(O),…、D(N-I)表示收到經編碼碼元。、
應注意，在值陣列被描述為「N(0)、…、N(X) 」或諸如此類的場合，不應假定這要求至少3個值，因為其並非意在排除只有一個或兩個值的情形。使用永久鈍化的編碼方法圖3是圖I中所示的編碼器115的一個具體實施例的框圖。如其中所解說的，源碼元被存儲在輸入緩衝器205中且被提供給靜態編碼器210和動態編碼器220，靜態編碼器210和動態編碼器220還接收關鍵字輸入和其他輸入。靜態編碼器210可包括用於存儲內部值和程序指令的內部存儲215 (存儲器、緩衝器、虛擬存儲器、寄存器存儲等)。同樣，動態編碼器220可包括用於存儲內部值和程序指令的內部存儲225 (存儲器、緩衝器、虛擬存儲器、寄存器存儲等)。在一些實施例中，冗餘演算器230確定要創建的冗餘碼元的數目R。在一些實施例 中，靜態編碼器210生成兩個相異的冗餘碼元集合，且在具體實施例中，第一集合是頭S個冗餘碼元，即碼元C(K)、…、C(K+S-1)且它們是LDPC碼元，而第二集合是接下來H個冗餘碼元，即C(L-H)、…、C(L-I)且它們是HDPC碼元。若PI列表是末P個冗餘碼元，則所有H 個冗餘碼元可在PI列表上(若P彡H)或者所有P個冗餘碼元可為HDPC碼元(若P < H)。導致生成這兩個碼元集合的操作可能相當不同。例如，在以下描述的一些實施例中，用於生成LDPC冗餘碼元的操作是二進位操作，而用於生成HDPC碼元的操作是非二進位的。動態編碼器220的操作在圖4中更詳細地解釋。根據一個實施例，動態編碼器220包括兩個編碼器，PI編碼器240和LT編碼器250。在一些實施例中，LT編碼器250是鏈式反應編碼器，且PI編碼器240是特定類型的鏈式反應編碼器。在其他實施例中，這兩個編碼器可能非常相似，或者PI編碼器240不是鏈式反應編碼器。無論如何定義這些編碼器，它們都生成碼元，其中LT編碼器250從被指定為非永久鈍化的LT中間碼元C(O) ^'C(L-P-I)生成其碼元，而PI編碼器240從永久鈍化的中間碼元C(L-P)、…、C(L-I)生成其碼元。這兩種所生成的碼元進入組合器260，組合器260生成最終經編碼碼元270。在本發明的一些實施例中，一些永久鈍化碼元可參與LT編碼過程，且不是永久鈍化碼元的一些碼元可參與PI編碼過程。換言之，PI列表和包括LT中間碼元的碼元集合不必是非相交的。在優選實施例中，提供給組合器260的碼元可具有相同長度，且由組合器260執行的功能是對這些碼元的異或(XOR)運算以生成經編碼碼元270。然而，這對於本發明的運轉不是必要的。能夠預想可導致類似結果的其他類型的組合器。在其他實施例中，中間碼元被細分成兩個以上集合，例如，一個LT碼元集合和若干個(一個以上)PI碼元集合，每個PI碼元集合具有其相關聯的編碼器240。當然，每個相關聯的編碼器可被實現為在充當不同集合的不同編碼器時根據編碼過程對不同指令進行操作的共同計算元件或硬體元件。如可由PI編碼器240執行的PI編碼過程241的示例操作在圖5中例示。使用與要生成的經編碼碼元相對應的關鍵字I_a，在步驟261，編碼器確定正權重WP和包含WP個在L-P與L-I之間(含L-P和L-1)的整數的列表ALP。在步驟263，若列表ALP = (t(0)，…，t (WP-I))，則碼元X的值被設為X = C(t (O)) C(t(l)) θ… C (t (WP-I))，其中θ表示異
或運算。
在一些實施例中，權重WP固定為某個數字，諸如3或4或其他某個固定數字。在其他實施例中，權重WP可屬於可能的此類數字的小集合，諸如被選取成等於2或3。例如，如附錄A的實施例中所示，權重WP取決於通過如可由LT編碼器250執行的LT編碼過程251生成的碼元的權重。若LT編碼器250生成的權重為2，則WP取決於關鍵字I_a被選取為2或3，其中WP為2或3的次數比例大約相等；若LT編碼器250生成的權重大於3，則WP被選取為2。圖6是根據本發明的實施例之一且使用Luby I和Shokrollahi I的教示的LT編碼過程251的示例。在步驟267，使用關鍵字1_&來分別生成權重WL和列表AL。在步驟269，若列表 ALP= (j (O)，···，」(WL-I))，則碼元 X 的值被設為 X = C(j(0)) C(j ⑴) - C (j (WL-I))。圖7解說了演算權重WL的操作。如其中所示，在步驟272，創建與要生成的經編碼碼元相關聯的數字V，並且可基於該經編碼碼元的關鍵字I_a來計算數字V。它可以是經編碼碼元的索引、代表性標記等，或者是不同的數字，只要編碼器和解碼器能一致即可。在該示例中，V在O與22°之間，但在其他示例中，其他範圍是可能的(諸如O到232)。生成V可以使用隨機生成表以顯式方式進行，但如何生成這些隨機數的確切操作可以變化。假定編碼器能訪問表M，表M的示例在圖8中提供。稱為「度分布查找」表的表M包含兩列和多行。左列標記有權重WL的可能值，且右列標記有O與22°之間(含O和22°)的整數。對於V的任何值，該度分布查找表的M[d]列中正好有一個單元，其中M[d-1] <v^M[d]為真。對於這一個單元，d列中存在相應的值，且編碼器將它用作經編碼碼元的權重WL。例如，在經編碼碼元具有V = 900，000的場合，該經編碼碼元的權重將為WL = 7。靜態編碼器210能訪問元素SE(k,J),其中k = O, .",R-I且j = O,…，L_1。這些元素可屬於任何有限域，該域的元素α與碼元X之間存在運算*以使得α*Χ為碼元，且α*(Χ Y) = α *Χ α *Υ,其中 表示異或運算。此類域和運算已在Shokrollahi IV中詳述。靜態編碼器210的操作可描述為對於給定的源碼元序列C (O)、…、C(K-I)，計算滿足式I中所示關係的冗餘碼元序列C(K)、…、C(L-I)，其中Z(O)、…、Z(R-I)是編碼器和解碼器已知的值(例如，O)。
權利要求
1.一種經由一個或更多個能夠輸出電子信號的發射機電子地傳送數據的方法，其中待傳送的數據由有序源碼元集合表示且所述數據是作為表示所述電子信號的至少一部分的經編碼碼元序列來傳送的，所述方法包括 以電子可讀形式獲得所述有序源碼元集合； 從所述有序源碼元集合生成一組中間碼元，其中所述源碼元是能從該組中間碼元再生的； 指定中間碼元集合以使得每個中間碼元被指定為所述中間碼元集合之一的成員且至少存在第一中間碼元集合和第二中間碼元集合，並且其中每個中間碼元集合具有相關聯的相異的編碼參數且具有至少一個中間碼元作為成員；以及 生成多個經編碼碼元，其中經編碼碼元是從所述中間碼元中的一個或更多個中間碼元生成的，其中至少一個經編碼碼元是直接或間接從選自多個所述中間碼元集合的多個中間碼元生成的。
2.如權利要求I所述的方法，其特徵在於，所述第一中間碼元集合被指定為用於置信傳播解碼的碼元且所述第二中間碼元集合被指定為針對置信傳播解碼被鈍化的碼元。
3.如權利要求I所述的方法，其特徵在於，每個經編碼碼元是根據從所述第一中間碼元集合中的一個或更多個中間碼元生成的第一碼元與從所述第二中間碼元集合中的一個或更多個中間碼元生成的第二碼元的組合生成的。
4.如權利要求3所述的方法，其特徵在於，所述相異的編碼參數至少包括相異的度分布，以使得每個經編碼碼元是根據從具有第一度分布的所述第一中間碼元集合中的一個或更多個中間碼元生成的第一碼元與從具有不同於所述第一度分布的第二度分布的所述第二中間碼元集合中的一個或更多個中間碼元生成的第二碼元的組合生成的。
5.如權利要求3所述的方法，其特徵在於，所述第一碼元是使用向所述第一中間碼元集合應用的鏈式反應編碼過程生成的。
6.如權利要求3所述的方法，其特徵在於，所述第二碼元是從所述第二中間碼元集合隨機選取的固定數目個碼元的異或。
7.如權利要求3所述的方法，其特徵在於，所述第二碼元是從所述第二中間碼元集合隨機選取的第一數目個碼元的異或，並且其中所述第一數目取決於等於為了生成所述第一碼元而從所述第一集合選取的碼元數目的第二數目。
8.如權利要求3所述的方法，其特徵在於，所述組合是所述第一碼元與所述第二碼元的異或。
9.如權利要求I所述的方法，其特徵在於，所述中間碼元包括所述有序源碼元集合以及從所述有序源碼元集合生成的冗餘源碼元集合。
10.如權利要求9所述的方法，其特徵在於，所述冗餘碼元中的至少一些是使用GF[2]操作生成的，且其他冗餘碼元是使用GF[256]操作生成的。
11.如權利要求I所述的方法，其特徵在於，所述中間碼元是在編碼期間使用解碼過程從所述源碼元生成的，其中所述解碼過程基於所述中間碼元與所述源碼元之間的線性關係組。
12.如權利要求11所述的方法，其特徵在於，所述線性關係中的至少一些是GF[2]上的關係，且其他線性關係是GF[256]上的關係。
13.如權利要求I所述的方法，其特徵在於，能從給定的有序源碼元集合生成的相異經編碼碼元的數目獨立於該有序集合中的源碼元數目。
14.如權利要求I所述的方法，其特徵在於，為了生成經編碼碼元而執行的碼元操作的平均次數受獨立於該有序集合中的碼元數目的常數限制。
15.如權利要求I所述的方法，其特徵在於，所述第一碼元集合在大於所述第二碼元集合的數量級以上。
16.一種從源接收數據的方法，其中所述數據是通過分組通信信道在目的地接收的，並且其中所述數據能由從表示從所述源發送給所述目的地的所述數據的有序源碼元集合推導出的經編碼碼元集合表示，所述方法包括 獲得收到經編碼碼元集合； 從所述收到經編碼碼元集合解碼一組中間碼元； 將所述中間碼元中的每一個與中間碼元集合相關聯，其中所述中間碼元被關聯到至少兩個集合中，且其中一個集合被指定為永久鈍化碼元集合以調度用於從所述收到經編碼碼元恢復所述中間碼元的解碼過程；以及 根據所述解碼過程從所述中間碼元集合恢復所述有序源碼元集合的至少一些源碼元。
17.如權利要求16所述的方法，其特徵在於，所述解碼過程至少包括第一解碼階段，其中取決於第二永久鈍化碼元集合以及為第一碼元集合的子集的第三動態鈍化碼元集合生成簡化經編碼碼元集合；以及第二解碼階段，其中所述簡化經編碼碼元集合被用來解碼所述第二永久鈍化碼元集合和所述第三動態鈍化碼元集合；以及第三解碼階段，其中解碼出的第二永久鈍化碼元集合和第三動態鈍化碼元集合以及所述收到經編碼碼元集合被用來解碼所述第一碼元集合中的至少一些剩餘中間碼元。
18.如權利要求17所述的方法，其特徵在於，所述第一解碼階段使用置信傳播解碼結合鈍化解碼，和/或所述第二解碼階段使用高斯消元法。
19.如權利要求17所述的方法，其特徵在於，所述第三解碼階段使用回代、或者後向掃描繼以前向掃描。
20.如權利要求17所述的方法，其特徵在於，考慮所述第三動態鈍化碼元集合中的碼元數目少於源碼元數目的10 %和/或少於所述第二永久鈍化碼元集合中的碼元數目的10%,所述解碼過程對所述第三動態鈍化碼元集合進行操作。
21.如權利要求16所述的方法，其特徵在於，所述收到經編碼碼元作為LDPC碼生成的碼元或Reed-Solomon碼生成的碼元被操作。
22.如權利要求16所述的方法，其特徵在於，所述收到經編碼碼元集合的每個收到經編碼碼元就如是從所述第一碼元集合中的一個或更多個碼元生成的第一碼元與從所述第二碼元集合中的一個或更多個碼元生成的第二碼元的組合那樣被操作。
23.如權利要求22所述的方法，其特徵在於，每個收到經編碼碼元就如所述組合是所述第一碼元與所述第二碼元的異或那樣被操作。
24.如權利要求22所述的方法，其特徵在於，每個收到經編碼碼元就如所述第二碼元是從所述第二集合隨機選取的固定數目個碼元的異或那樣被操作。
25.如權利要求22所述的方法，其特徵在於，每個收到經編碼碼元就如所述第二碼元是從所述第二集合隨機選取的第一數目個碼元的異或那樣被操作，其中碼元的所述第一數目取決於為了生成所述第一碼元而從所述第一集合選取的碼元的第二數目。
26.如權利要求22所述的方法，其特徵在於，所述解碼過程就像所述第一碼元是基於鏈式反應碼從所述第一碼元集合選取的那樣進行操作。
27.如權利要求16所述的方法，其特徵在於，所述解碼過程就像所述第二永久鈍化碼元集合的大小與源碼元數目的平方根成比例那樣進行操作。
28.如權利要求16所述的方法，其特徵在於，所述解碼過程就像所述中間碼元包括所述有序源碼元集合以及從所述有序源碼元集合生成的冗餘碼元集合那樣進行操作。
29.如權利要求28所述的方法，其特徵在於，所述解碼過程就像所述冗餘碼元中的至少一些是使用GF[2]操作生成的且其他冗餘碼元是使用GF[256]操作生成的那樣進行操作。
30.如權利要求16所述的方法，其特徵在於，所述解碼過程就像所述中間碼元包括所述有序源碼元集合那樣進行操作。
31.如權利要求16所述的方法，其特徵在於，所述解碼過程就像所述中間碼元是使用解碼過程基於所述中間碼元與所述源碼元之間的線性關係組從所述源碼元生成的碼元那樣進行操作。
32.如權利要求31所述的方法，其特徵在於，所述解碼過程就像所述線性關係中的至少一些是GF[2]上的關係且其他線性關係是GF[256]上的關係那樣進行操作。
33.如權利要求16所述的方法，其特徵在於，所述解碼過程就像能接收到的不同的可能經編碼碼元的數目獨立於所述有序集合中的源碼元數目那樣進行操作。
34.如權利要求16所述的方法，其特徵在於，為了從所述收到經編碼碼元集合解碼所述源碼元集合要執行的碼元操作的平均次數受常數乘以源碼元數目限制，其中所述常數獨立於所述源碼元數目。
35.如權利要求16所述的方法，其特徵在於，所述解碼過程就像所述第一碼元集合中的碼元數目在大於所述第二永久鈍化碼元集合中的碼元數目的數量級以上那樣進行操作。
36.如權利要求16所述的方法，其特徵在於，所述解碼過程進行操作以使得從N=K+A個經編碼碼元的集合恢復所有K個源碼元的集合對於某個K、N和A至少具有1-(0. 01) ~(A+1)的下限的成功概率，其中A = O、I或2，其中所述下限獨立於源碼元數目。
37.一種用於使用耦合到數據網的伺服器來供應文件的方法，其中供應包括將所述文件的數據組織成一個或更多個塊，基於塊的數據生成所述塊的一個或更多個經編碼碼元，且其中至少一個塊在物理上或邏輯上被組織成多個子塊，且至少一個經編碼碼元在物理上或邏輯上被組織成多個子碼元，所述方法包括 將輸入文件劃分成整數數目個塊，其中每個塊包括至少一個子塊，且其中每個子塊包括至少一個源碼元； 基於存儲器約束確定表示子塊的最大大小的值WS ； 確定值SS，其中SS*AL表示以優選存儲器單位大小AL計的子碼元大小的下限； 確定所述整數數目個塊中的哪些塊將被組織成多個子塊，且對於每個此類塊，將該塊組織成具有由用於待發送的經編碼碼元的分組內的可用空間、每個所發送分組內將使用的碼元大小決定的大小的多個子塊，從而確保各源塊的源碼元數目落在閾值內且該數目等於文件中的源碼元數目Kt，以及確保每個子塊的子碼元大小至多為SS*AL並確保每個子塊的大小至多為WS ； 從塊生成經編碼碼元，其中子碼元是從子塊生成的以使得每個經編碼碼元取決於來自一個塊的數據；以及 輸出生成的經編碼碼元。
38.一種用於在使用耦合到數據網的客戶端的接收機處恢復數據塊的方法，其中塊包括一個或更多個子塊的編組，所述方法包括 接收從所述塊生成的多個經編碼碼元，其中每個經編碼碼元包括使用共同的操作集從至少一個子塊生成的多個子碼元； 基於存儲器約束確定表示子塊的最大大小的值WS ； 確定值SS，其中SS*AL表示以優選存儲器單位大小AL計的子碼元大小的下限；確定整數數目個塊中的哪些塊被組織成多個子塊，且對於每個此類塊，將該塊組織成具有由發送方設定的表示分組內的可用空間的第一參數、表示每個分組內使用的碼元大小的第二參數決定的大小的多個子塊，所述參數使得各源塊的源碼元數目落在閾值內且該數目等於文件中的源碼元數目Kt ； 從收到經編碼碼元解碼塊，其中子塊是從子碼元解碼的且所述子塊形成塊，其中每個子塊的子碼元大小至多為SS*AL且每個子塊的大小至多為WS ；以及輸出經解碼塊。
全文摘要
提供了對多個經編碼碼元的編碼，其中根據從第一中間碼元集合生成的第一碼元與從第二中間碼元集合生成的第二碼元的組合生成經編碼碼元，每個集合具有至少一個不同的編碼參數，其中這些中間碼元是基於源碼元集合生成的。還提供了解碼數據的方法，其中從收到經編碼碼元集合解碼一組中間碼元，這些中間碼元被組織成第一和第二碼元集合以進行解碼，其中第二集合中的中間碼元被永久鈍化以調度解碼過程從經編碼碼元恢復中間碼元，其中從解碼出的中間碼元集合恢復至少一些源碼元。
文檔編號H03M13/37GK102640422SQ201080037946
公開日2012年8月15日 申請日期2010年8月19日 優先權日2009年8月19日
發明者L·C·明德, M·A·肖克羅拉西, M·G·盧比 申請人:高通股份有限公司