TWI280748B - Multi-stage code generator and decoder for communication systems - Google Patents

Description

1280748 ⑴ 玖、發明說明 (發明說明應敘明：發明所屬之技術領域、先前技術、内容、實施方式及圖式簡單說明） — 先前技術 - 本發明係有關於在通信系統中將資料編碼及解碼，而 更明確而言，係有關可將資料編碼及解碼以說明通信資料 Λ 的錯誤與間隙的通信系統。 # 在一通信通道上的一傳送器與一接收器之間的檔案傳 輸是描述的主題。最好是，一接收器想要接收由具某些位 準的一傳送器在一通道上傳送資料的的一正確副本。一考 φ 慮是如何處理在傳輸中遺失或竄改的資料，其中通道不具 有完美的忠實度（涵蓋所有實際可實施的系統）。遺失資料 (抹除）是時常是比破壞資料（錯誤）較容易處理，因為接收 器不能始終告訴破壞的資料何時會接收。許多錯誤修正碼 已發展來更正抹除及/或錯誤。典型上，使用的特殊碼是 根據有關資料傳輸通道不忠實與傳送資料本質的一些資 訊來選取。例如，一猝發錯誤碼可能最適合應用，其中通 道是已知具有長周期不忠實性。短暫較少發生的錯誤是可 _ 預期，一簡單核對碼是較佳。 選取一碼的另一考慮是用於傳輸的協定。在已知為”網 際網路π的網路使用情況，一封包協定是用於資料傳輸。 各 協定是稱為妄際網路協定或簡稱πιρπ。當一檔案或其他區 - 塊資料在一 IP網路上傳送時，它可劃分成同等大小輸入符 號，且輸入符號是置於連續封包。一輸入符號的”大小π 是以位元為單位測，量，而不管輸入符號是否實際分成一位 元流，其中當輸入符號是從2Μ個符號字母選取時，一輸 1280748

入符號可具有 ’ ^ I.U ,王之通信系 ’ 一封包導向編石馬方沐S 、立 .田y 5方法疋適合的。如果允許想要的 腺疮从秘安沾 ；H r 士 =., , K 統，一封 、〜δΤ怨要的接 器將原始檔案的正確副本復原，即使面對網路的抹除，— 傳輸是可稱為可靠的。在網際網路上，封包損失時常 生’因為不時發生的擁塞會使在一路由器中的緩衝機 達它的限制，而迫使它丢棄送入的封包。在傳輪期間防止 抹除的保護已是更多研究的課題。 傳輸控制協定（"TCP，，）是具有確認機制的普遍使用的一 點對點封包空制方法。Tcp對於一對一通信是很好的，其 中傳送者與接收者可協議傳輸何時發生及接收，且兩者可 協議將使用那個傳送器與接收器。然而，T c P不是時常適 於一對多、或多對多通信，其中傳送者與接收者可個別決 定何時及何地將傳送或接收資料。 透過使用TCP，.一傳送者可傳送排列的封包，且接收者 可確認每個封包的接收。如果一封包遺失，沒有確認會傳 送給傳送者，且傳送者可重新傳送封包。封包遺失是有許 多原因。隨著例如TCP/IP的協定，既然遺失封包可被重新 傳送，所以確認模式在反應沒有確認或反應來自接收者的 明確請求可允許封包遺失而不致造成整個失敗。不管任何 方式，一確認協定從接收者到傳送者需要一背通道，此背 通道在遺失封包量較大時，會高度使用。 雖然以確認為主之協定東常適於許多應用，且事實上 是廣泛使用在目前的網際網路，但是對於例如在頒予

Michael G· Luby 的美國專利案號 6,307,487名稱 ”Informati〇n

1280748 (3)

Additive Code Generator and Decoder for Communication Systems”（以後稱為nLuby In)而言，他們會是無效率，且 有時會完全不能實行。此外，以確認為主之協定並未能依 比例廣播，其中一傳送者是將一檔案同時傳送給多位使用 者。例如，假設一傳送者是在一衛星通道上將一檔案廣播 給多重使用者。每位接收者會經歷到封包損失的不同程度 。因檔案可靠度傳遞的確認資料（肯動或否定）而定的協定 從每位接收者到傳送者需要一背通道，且此提供是高度昂 貴。此外，此需要一複雜與強而有力的傳送者來適當處理 從接收者傳送的所有確認資料。另一缺點是如果不同接收 者遺失不同封包組，只由少數接收者將瑳失的封包重新傳 送會造成其他接收者無用重複封包的接收。 有時實際使用的另一以確認為主之.協定是以循環為主 之協定。一循環協定是將一輸入檔案劃分成相同長度輸入 符號，將每個輸入符號放置在一封包，然後持續循環及傳 送所有封包。一以循環為主之協定的一主要缺點是如果一 接收者錯失一封包，那麼在具有接收錯誤封包的機會之前 ，接收者必須等待另一整個周期。觀查此的另一方法是一 以循環為主之協定會造成大量無用的複製資料接收。例如 ，如果一接收者從循環開始而接收封包，接收會短暫停止 ，然後在循環開始來重新開始接收，便會接收大量無用的 重複封包。 提議來解決上述問題的一解決是要避免使用一以確認 為主之協定，坩是要使用前向錯誤修正（FEC)碼，例如資 1280748

(4) 訊加入碼的Reed-Solomon瑪或Tornado碼、或連鎖反鹿碼 ，以提高可靠度。隨著這些碼，輸出符號是從内容產生及 傳送，而不是只傳送構成内容的輸入符號。例如 Reed-Solomon碼或Tornado碼的抹除修正碼可於一固定長 ， 度内容來產生固定數量的輸出符號。例如，對於κ個輸入 身 符號而言，Ν個輸出符號可產生。這些ν個輸出符號包含& 個原始輸入符號及Ν-Κ個冗餘符號。如果儲存裝置允許， 那麼伺服器可將每個内容的輸出符號組計算一次，且使用 一循環協定來傳送輸出符號。 _ 使用一些FEC碼的一問題是他們需要過度計算能力或 記憶體來操作。另一問題是輸出符號數i量必須是在編碼之 别決疋。如果風伴的遺失率估計過高，此便會導致無效率 ，且如果封包的遺失率低於估計，便會導致失敗β 對於傳統FEC碼而言，產生的可能輸出符號數量是與内 容劃分成輸入符號數量相同大小.典型上，在傳送步驟之 前，多數或所有這些輸出符號是在一處理步驟產生。這些 輸出符號具有所有輸入符號可從長度等於原始内容或略· 長於原始内容的任何部分輸出符號再生的特性。 在Luby I描述的具體實施例（稱為”連鎖反應碼”）是提供 > 說明上述問題不同形式的前向錯誤修正。對於連鎖反應碼 ^ 而g，產生的可能輸出符號典型是大於輸出符號數量，且 來自可能輸出符號的一隨機輸出符號可非常快速產生。對 於連鎖反應碼而言，輸出符號是在與傳送步驟同時發生的 基礎上動；||產生。連鎖反應碼具有内容從一組内容略長於 -9-

1280748 (5) 原始内容的的隨機產生輸出符號的任何部分再生的特性。

在一連鎖反應碼的具體實施例中，每個輸入符號是以 一些輸入符號的互斥Or(以㊉表示的XOR運算）獲得。如果 K表示輸入符號的總數，一般而言，那麼每個輸入符號是 c*In(K)輸入符號的X〇R結杲，其中In(K)是K的自然對數 ，且c是一適當的常數。例如，其中Κ是60,000，一般而言 ，每個輸出符號是2 8.6 8個輸入符號的X0R結果，而且其 中Κ是10,000，一般而言，每個輸出符號是22.86個輸入符 號的X0R。當每個此運算包括從記憶體拾取資料、執行 XOR運算、及更新記憶體位置時，大量X0R結果會造成輸 出符號的輕長計算時間。

經由一連鎖反應編碼器所產生輸出符號的一特性是只 要足夠輸出符號接收，一接收器便可將原始檔案復原。明 確而言，若要以一較高可能性將原始K個輸入符號復原， 接收器需要大約K +A個輸出符號。A/Κ比率是稱為”相對接 收負荷”。相對接收負荷是因輸入符號數量K、與解碼器 的可靠度而定。例如，在一特殊具體實施例，而且其中K 是等於6 0，0 0 0，5 %的一相對接收負荷可確保解碼器能以 至少1 -1 (Γ8的機率將輸入檔案成功解碼，而且其中K是等 於1 0,000，15%的一相對接收負荷可確保解碼器的相同成 功機率。在一具體實施例中，連鎖反應碼的相對接收負荷 是以（13*sqrt(K) + 200)/K計算，其中sqrt(K)是輸入符號數 量K的平方根。在此具體實施例中，對於小K值而言，連 鎖反應碼的相對接收負荷會較大。 -10- (6) 1280748 在輸出符號使用XOR功能編碼的具體實施例中，一連鎖 w馬的主要計算是執行記憶體位置的運算。此 的數量是以與連鎖反應編碼器相同方式依比例決定。 連鎖反應，對於在一以封包為主之網樂上的通信是很 用。然而，他們是相當密集計$。例如，在連鎖反應碼 :-些特殊具體實施例巾，當輸入符號數量民是6〇,〇〇〇, -般而言’每個輸出符號的計算需要拾取2 8 68個隨機選 擇輸入符冑，且將他們做x〇R運算1為卜伺服器同時 服務的檔案數量是與每個輸出符號所需的運算數量成反 比’所以對於減少每個輸出符號所需的運算數量是有用的 。以3的因素將後者減少，透過3的因素可增加從一伺服器 同時服務的槽案數量。 、連鎖反應碼的另一特性是他們需要一相當大特定目標 成功可忐性的接收負荷 '輕如，如前述，在連鎖反應碼的 一套殊具體實施例中，如果K是i 0，0 〇 〇 ,那麼i 5 %的一 相：接收負荷可確保至少“Ο •、一解碼成功機率。接收 負荷於較小的κ值會增加。例如，在連鎖反應碼的一些套 殊具體實施例中，如果K是1 000，61 %的一相對接收負荷 可確保相同機率的成功解碼。而且，如一衛星網路内容高 速傳輸的某些應用需要方面，將目標錯誤機率減少到大約 M12數量需要甚至較大接收負荷。 發明内容 根據本發明的具體實施例，提供用以在一通信通道上 從一來源傳送給一目的地的資料編碼之方法。該方法是在 -11 - 1280748 _ (7) i 輸入符號的排列組上操作，且包括從該等輸入符號產生複 數個冗餘符號。該方法亦包括從包括該等輸入符號與該等 冗餘符號的符號組合組來產生複數個輸出符號，其中可能 輸出符號數量是遠大於在符號組合組中的符號數量，其中 至少一輸出符號是從符號組合組中超過一符號、及在符號 組合組中少於所有符號產生，以致於輸入符號的排列組可 從任何預定輸入符號數量再生成一想要的正確性程度。 根據本發明的另一具體實施例，提供用以在一通信通 道上從一來源傳送給一目的地的資料編碼之系統。該系統 包含一靜態編碼器是耦合成接收複數個輸入符號，複數個 輸入符號是從傳送資料產生。靜態編碼1器包括一冗餘符號 產生器，以根據輸入符號來產生複數個冗餘符號。此外， 系統包含一動態編碼器是耦合成接收複數個輸入符號與 複數個冗餘符號。動態編碼器包括一輸出符號產生器，以 便從包括複數個輸入符號與複數個冗餘符號的一符號組 合組產生複數個輸出符號，其中可能輸出符號數量是遠大 於在組合組中的符號數量，其中至少一輸出符號是從該組 合組中超過一符號及該組合組中少於所有符號產生，以致 於輸入符號的排列組可從任何預定數量的輸出符號再生 成一想要的正確性程度。 仍然根據本發明的另一具體實施例，提供用以在一通 信通道上接收從一來源所傳送資料之方法。該方法包括接 收輸出符號，其中每個輸出符號是從輸入符號與冗餘符號 的組合組中的至少一符號產生，其中至少一輸出符號是從 -12- 1280748 _ (8) 1^^^ 該組合組中超過一符號及該組合組中少於所有符號產生 ，其中可能輸出符號數量是遠大於在組合組中的符號數量 ，其中該等輸入符號是來自該等輸入符號的一排列組，而 且其中冗餘符號是從輸入符號產生。該方法亦包括只要接 收任何數量N的輸出符號，便從N輸出數量的組合組中將 至少一部分符號再生，該部分包括複數個再生輸入符號與 複數個再生冗餘符號。該方法進一步包括如果將來自N輸 出數量的至少一部分符號再生的步驟不會將輸入符號再 生成一想要的正確性程度，將來自複數個再生冗餘符號及 /或複數個再生輸入符號中一些再生輸入符號的至少一些 未再生輪入符號再生。 仍然根據本發明的另一具體實施例，提供用以在一通 信通道上接收從一來源所傳送資料之系統。該系統包含一 接收模組耦合到一通信通道，用以接收在通信通道上傳送 的輸出符號，其中每個輸出符號是從輸入符號與冗餘符號 的組合組中的至少一符號產生，其中至少一輸出符號是從 該組合組中超過一符號及該組合組中少於所有符號產生 ，其中可能輸出符號數量是遠大於在組合組中的符號數量 ，其中冗餘符號是來自輸入符號的一排列組，其中該等冗 餘符號是從輸入符號產生。此外，該系統包括一動態解碼 器，只要接預定數量N輸出符號，該動態解碼器便會將在 來自N個輸出符號的組合組中的一部分符號解碼，該部分 包括複數個解碼輸入符號與複數個解碼冗餘符號。該系統 進一步包含一靜態解碼，如有任何未解碼輸入符號，從複 -13 - (9) 1280748

數個解碼冗餘符號將該 入符號解碼。 等未解瑪輸入符號的至少 一些輸 仍然根據本發明的另一星妒香 旲粗貫施例，提供在一載波上 具體實施的一電腦資料信號。雷w次丄丨 現電細資料信號包括複數個輸 出符號，其中複數個輪出符妒矣-你^ 付說表不從包括輸入符號與冗餘 符號的-排列組的-符號組合級產生的符號，其中可能輸 出符號數量是遠大於在組合組中的符號數量，其中至少一 輸出符號是從該組合組中超禍 狀％ _ T %過一符號及該組合組中少於 所有符號產生，以致於資料作狹沾 ^ ^ οο 、 貝了寸七唬的一接收器可從預定數量 輸出符號將輸入符號的排列έ且具&士、 , φ P 、，及丹生成一想要的正確性程 度。 許多優點可經由本發明的方法達成。例如，在一特殊 具體實施例中，用以在一通道上傳送的資料編碼的計算代 1賈可減少。在另一特殊具體實施例中，將此資料解碼的計 异代價可減少。14些一或多個優點的達成是因具體實施例 而定。這些及其他優點是在本發明規格更詳細提供及在下 面坪細描述。 在此揭示本發明的本質與優點的進一步了解可透過參 考其餘部分的規格與附圖來了解。 實施方式 頒予Michael G· Luby的本揭示美國專利案號6,307,487 (Luby l)、與美國專利案號 6,320,520 名稱 ’’Information Additive Group Code Generator and Decoder for Communication Systems”（以下稱為"Luby II")，其整個揭 -14- 1280748 _ (10) 示在此是以引用方式併入本文。Luby I與Luby II提供根據 本發明而使用在某些具體實施例的系統與方法的說明。然 而，應了解這些系統與方法不是本發明需要的，且許多其 他變化、修改、或選擇亦可使用。 在此描述的特殊具體實施例中，表示”多階碼”的一編碼 方法將描述，及說明使用在此描述的各種術語的意義與範 圍。 如在此描述的多階編碼是以複數個階段將資料編碼。 典型上（但並非是始終如此），一第一階段是將一預定量冗 餘加入資料。一第二階段是然後使用一鏈反應碼等從原始 資料產生輸出符號、及透過編碼的第一階段計算的冗餘符 號。在本發明的一特殊具體實施例中，接收的資料是先使 用一鏈反應解碼處理解碼。如果處理並未成功完全接收原 始資料，一第二解碼步驟便可應用。 與下述鍵反應編碼相比較，在此描述的一些具體實施 例的一優點是使用較少算術運算產生輸出符號。一些特殊 具體實施例的另一優點是包括編碼的一第一階段與編碼 的一第二階段能在不同時間及/或不同裝置完成，如此可 將計算的負荷劃分。此會是一優點，例如，如果想要執行 一部分的實只與傳輸同時發生的編碼。特別是，第一階段 編碼的執行是優於傳輸，而第二階段編碼的執行是實質與 傳輸同時發生。然而，應了解在一些具體實施例中，第一 及第二編碼階段的執行能實與傳輸、及/或與一裝置同時 發生。在閱的此揭示之後，許多其他變化、修改、與選擇 1280748 __ οι) 對於熟諳此技者是顯然的。 在多階編碼的具體實施例中，冗餘符號是在第一編碼 階段期間從輸入檔案產生。在這些具體實施例中，在第二 編碼階段，輸出符號是從輸入檔案與冗餘符號產生。在這 些具體實施例的其中一些，輸出符號可依需要產生。只要 產生，這些輸出符號然後會放置在封包，及傳送給他們的 目的地，且每個封包包含一或多個輸出符號。非封包化傳 輸技術亦可取代使用。 如在此的使用，術語”檔案’’可視為儲存在一或多個來源 的任何資料，且是以一單元傳遞給一或多個目的地。如此 ，來自一檔秦伺服器或電腦儲存裝置的一文件、一影像、 與一檔案是可傳遞的”檔案”所有範例。檔案可能已知（例 如儲存在一硬碟的1Μ個位元組影像）、或可以是已知大小 (例如從一流來源輸出使用的一檔案）。在上述任何方式， 檔案是一連串的輸出符號，其中每個輸出符號在檔案具有 一位置及一值。 傳輸是將資料從一或多個發送器經由一通道傳送給一 或多個接收器而為了傳遞一檔案的處理。一發送器亦有時 稱為編碼器。如果一發送器是透過一理想通道而連接到任 何數量的接收器，當所有資料正確接收時，接收的資料便 會是輸入檔案的正確複製。在此，我們假設通道不是完美 的，兩想要的缺陷是資料抹除及資料不完全（可視為資料 抹除的特殊情況）。當逼接收器未開始接收資料時，資料 抹除便會發生，直到一些資料已傳遞給它為止，接收器會 -16-

1280748 (12) 在傳輸結束之前停止接收資料，接收者只選取接收一部分 的傳送資料，及/或接收器間接性停止及開始重新接收資 料。如一不完全資料範例，<一移動衛星發送器會傳送表示 一輸入檔案的傳輸資料，且在一接收器在範圍内之前開始 傳送。只要接收器是在範圍内，資料便會接收，直到衛星 移出範圍外為止，此時，接收器可將衛星碟形天線改變方 向（在不接收資料期間），以開始接收有關移入範圍内的另 一衛星所傳送的相同輸入檔案。從閱讀此描述應了解，既 然接收器處理資料會不完整（且接收器具有相同問題），所 以資料不完整性會是資料抹除的一特殊情況，好像接收器 在整個時間是在範圍内，但是通道會遺失所有資料，直到 接收器開始接收資料為止。而且，如在通信系統設計中眾 所周知，可偵測錯誤認為同樣可透過丟棄具有可偵測錯誤 的所有資料方塊或符號而抹除。 在一些通信系統中，一接收器可接收經由多個發送器 或使用多重連接的一發送器所產生的資料。例如，若要加 速下載，一接收器可同時連接到超過一發送器，以傳送相 同樓案的資料。如另一範例所示，在一多重傳輸中，多重 廣播資料流可傳送，以接收器連接一或多個資料流，以使 整個傳輸率符合將他們連接到發送器的通道頻寬。在所有 此情況，一考慮是要確保所有傳輸資料對於一接收器是獨 立使用，即是多重來源資料在資料流之間不是冗餘的，即 使當傳輸率於不同的資料流是明顯不同，及當有任何圖案 損失。 1280748 _ (13) 一般而言，一通信通道是連接用於資料傳輸的發送器 與接收器。通信通道可以是一即時通道，其中當通道獲得 資料時，通道可將資料從發送器移到接收器，或通信通道 可以是儲存從發送器傳送給接收器的一些或所有資料的 一儲存通道。後者範例是磁碟儲存或其他儲存裝置。在此 範例中，用以產生資料的程式或裝置可認為是發送器，用 以將資料傳送給儲存裝置。機構是發送器可用來獲得儲存 裝置的資料，儲存裝置本身與機構是接收器用來獲得從通 道收集來自儲存裝置的資料。如果這些機構或儲存裝置可 能會遺失資料，那麼在通信通道中便能以資料抹除處理。 當發送器與接收器是由符號可抹除的一通信通道分開 時，最好是不要傳送一輸入檔案的正確複製，但是可傳送 從輸入檔案產生的資料，以幫助抹除復原。一編碼器是處 理工作的一電路、裝置、模組或碼分段。檢視編碼器操作 的一方法是編碼器從輸入符號產生輸出符號，其中一連串 輸入符號是表示輸入檔案。如此，每個輸入符號在檔案中 具有一位置與一值。一編碼器是可將來自接收者接收輸出 符號的輸入符號重建的一電路、裝置、模組或碼分段。在 多階碼中，編碼器與解碼器是進一步分成子模組，其每個 可執行一不同工作。 在多階碼系統的具體實施例中，編碼器與解碼器可進 一步分成子模組，其每個可執行一不同工作。例如，在一 些具體實施例中，編碼器最好在此包含一靜態編碼器及一 動態編碼器。如在此的使用，一’'靜態編碼器”是可從一組 1280748 (14) 輸入符號產生許多冗餘符號的一靜態編碼器，其中冗餘符 號數量是在編碼之前決定。靜態編碼的範例包括 Reed-Solomon 碼、托那多（Tornado)碼、漢明（Hamming) 碼、低密度核對檢查（LDPC)碼等。術語〃靜態解碼器”在 此是用來當作一解碼器，其可將一靜態編碼器編碼的資料 解碼。 如在此的使用，一 π動態解碼器”是可從一組輸入符號產 生輸出符號的一解碼器，其中可能輸出符號數量是大於輸 入符號數量的倍數，而且其中產生的輸出符號數量不需要 是固定。一動態編碼器的範例是一連鎖反應編碼器，例如 在Luby I與Luby II中描述的編碼器。術語”動態解碼器π 在此是當作一解碼器，其可用來將一動態編碼器編碼的資 料解碼。 多階碼的具體實施例並未局限於輸入符號的任何特殊 類型。典型上，輸入符賀的值是從相同正整數Μ的2Μ個符 號的一字母選取。Μ值時常是根據例如應用、通信通道、 及/或輸出符號大小的使用而定。此外，一輸出符號大小 時常是根據應用、通道、及/或輸出符號大小而定。在一 些情況，如果輸出符號值與輸入符號值是相同大小（即是 ，以相同位元數量表示、或從相同字母選取），碼處理便 可簡化。如果是此情況，那麼當輸出符號值大小受限制時 ，輸入符號值大小便會受限制。例如，將輸出符號放置在 受限制大小封包中是想要的。如果傳送與輸出符號有關的 一關鍵值的一些資料，以復原在接收器上的關鍵值，輸出 -19- 1280748 (15) 符號最好是足夠小，以便在一封包冲適合輸出符號值及有 關該關鍵值的資料。

如一範例所示，如果一輸入檔案是一多倍的百萬位元 組檔案，輸入檔案可分成幾千、數千、或成千上萬的輸入 符號，且每個輸入符號可將數千、數百、或只有幾個位元 組編碼。如另一範例所示，對於一以封包為主之網際網路 通道而言，具1 024位元組大小負荷的一封包是適當的（一 位元是8位元）。在此範例中，假設每個封包包含一輸入符 號、與8位元組的輔助資訊，8128位元（（1024-8) *8)的一 輸出符號是適當的。如此，輸入符號大小能以M = ( 1 024-8) * 8或8 1 2 8個位元選取。如另一範例所示，一些衛星系統是 使用MPEG封包標準，其中每個封包的負荷包含188個位 元組。在此範例中，假設每個封包包含一輸出符號與4位 元組的輔助資訊，1472位元（188-4) *8)的一輸出符號大小 是適當的。如此，輸入符號大小能以M = (l 88-4) *8或1472 個位元選取。在使用多階碼的一般目的通信系統中，例如 輸入符號大小（即是Μ，由一輸入符號編碼的位元數量）特 殊應用參數可以是由應用所設定的變數。 每個輸出符號具有一值。在一較佳具體實施例中，我 們可考慮下面每個輸出符號亦具有稱為”關鍵值’’的一識 別符。最好是，每個輸出符號的關鍵值可容易由接收器決 定，以允許接收器從其他輸出符號來區別一輸出符號。最 好是，一輸出符號的關鍵值是不同於所有其他輸出符號的 / 關鍵值。有在先前技術中主要討論的各種不同形式。例 -20- 1280748 _ (16) 如，Luby I是描述使用在本發明具體實施例的不同主要形 式。 多階碼是特別有用，其中預期有資料抹除，或其中當 一傳輸開始與疾束時，接收者不會開始及結束接收。後者 情況在此視為”資料不完全”。關於抹除事件，多階碼是共 用在Luby I中所描述連鎖反應碼的許多優點。特別是，多 階輸出符號是額外資訊，所以任何適當數量的封包可用來 將一輸入檔案復原成一想要程度的正確性^當使用多階碼 時，這些狀況不會不利地影響通信處理，因為使用多階碼 產生的輸出符號是額外資訊。例如‘，如果一百個封包由於 雜訊猝發造成而遺失，一額外一百個封包可在取代抹除封 包遺失之後拾取。如杲數千封包遺失是因為當封包開始傳 送時一接收器不會變成一傳送器，接收器便只會從任何其 他傳輸周期拾取這些成千個封包，或甚至從另一傳送器。 隨著多階碼，一接收器不會被強迫來拾取任何特殊組封包 ，所以它可從一傳送器接收相同封包，切換到另一傳送器 ，遺失相同封包，錯失一定傳輸的開始或結束，及仍然復 原一輸入檔案。在沒有接收器-傳送器協調運作的結合與 退出傳輸的能力可幫助簡化通信處理。 在一些具體實施例中，使用多階碼傳送一檔案包括從 一輸入檔案產生、形成、或擷取輸入符號；計算冗餘符號 :將輸入與冗餘符號編碼成一或多個輸出符號，其中每個 輸出符號是根據所有其他輸出符號的獨立關鍵值而產生 ί ;及在一通道上將輸出符號傳送給一或多個接收器。此外 -21 - 1280748 _ (Π) ，在一些具體實施例中，使用多階碼將輸入檔案複製包括 從一或多個資料流接收相同組或一部分輸出符號，及將來 自接收輸出符號的值與關鍵值的輸入符號解碼。 本發明的觀點現將參考圖式描述。 系統概觀 圖1是使用多階碼的一通信系統1 0 0方塊圖。在通信系 統100中，一輸入檔案101或一輸入流105是提供給一輸入 符號產生器11 0。輸入符號產生器11 0可從輸入檔案或資料 流產生一連串一或多個輸入符號（is(0)、IS(1)、IS(2)、…） ，且每個輸入符號具有一值及一位置（如在圖1括弧内整數 所示）。如上所示，輸入符號（即是字母）的可能值典型是 2M個符號的一字母，所以每個輸入符號可編碼輸入檔案 的Μ位元。Μ值通常是由通信系統1 0 0的使用來決定，但 是一般目的系統包括輸入符號產生器1 1 0的一符號大小輸 入，所以Μ可隨著不同使用而變化。輸入符號產生器1 1 0 的輸出是提供給一編碼器1 1 5。 靜態關鍵值產生器1 3 0可產生靜態關鍵值S 0、S 1、...的 資料流。產生的靜態關鍵值數量通常是受限制，且是因編 碼器1 1 5的特殊具體實施例而定。靜態關鍵值的產生隨後 將詳細描述。動態關鍵值產生器1 20可產生每個輸出符號 的一動態關鍵值，其中每個輸出符號是由編碼器1 1 5產生 。每個動態關鍵值可產生，所以相同輸入檔案的大部分動 態關鍵值是唯一的。例如，Luby I描述可使用的關鍵值的 具體實施例。動態關鍵值產生器1 2 0與靜態關鍵值產生器 (18) 1280748 130的輸出是提供給編碼器ns。 從經由動態關鍵值產生器120提供的每個關鍵值〗是從 輸入符號產生器提供的輸入符號產生—輸出符號，且具有 一值B(I)。編碼器i i 5的操作將在下面詳細描述。每個輸 出符號值是根據它的關鍵值、一或多個輸入符號的相同功 能、及從輸入符號計算的可能一或多個冗餘符號產生。導 致一特殊輸出符號的整個輸入符號與冗餘符號在此稱為 輸出符號的"相關符號"或只是他的"關聯值"。功能（"值 函數"）與關聯值的選擇是根據下面詳述的一處理來完成 。典型上（但非始終如此），M於輸入符號與輸出符號是相 同，1即是他們兩碼是用於相同位元數量。 在一些具體實施例中，輸入符號數量κ是由編碼器i i 5 用來選取關聯值。如果K不是預先知冑，例如其中輸入是 -檔案流，κ只是一評估。值【亦可由編碼器ιΐ5用來配置 由編碼器115所產生輸入符號、及任何中間符號的儲存。 編碼器115是將輸出符號提供給一傳輸模組14〇。傳輸 模組i40亦提供來自動態關鍵值產生器12〇的每個此輸出 符號的關鍵值。傳輸模組140可傳送輸出符號，且是因所 使用關鍵值產生方法而定，傳輸模組14〇亦可在一通道上 將有關傳送輸出符號關鍵值的相同資料傳送給一接收模 組150。通道145是假設為一抹除通道，但不是通信系統1〇〇 受刃 赘得褕模組140適於將輸出符號、 及有關他們關冑值的任何需要資料傳送給通道145，且接 收模組15〇適於從通道⑷接收符號及有關他們關鍵值的 -23- 1280748

(19) 潛在性相同資料，模組1 4 0、1 4 5和1 5 0便可以是任何適去 硬體元件、軟體元件、實體媒體、或任何組合。如果匕值 是用來決定關聯值，K值可在通道145上傳送，或它可在 經編碼器1 1 5與解碼器1 5 5雙方同意之前設定。 如刖述’通道1 4 5可以是一即時通道，例如從—電視傳 送器到一電視接收器經由網際網路或一廣播鏈路的通道 、或從一點到任一點的一電話連接，或通道1 4 5可以是一 儲存通道，例如一 CD-ROM、磁碟機、Web網站笨。、s私 ~ 迷道 1 4 5甚至可以是一即時通道與一儲存通道的組合，例如冬 一人在一電話線上將一輸入檔案從一個人電腦傳送终一 網際網路服務提供器（ISP)時形成的一通道，輸入槽案是 儲存在一 Web伺服器上，且隨後在網際網路上傳送給一 'σ 禪 收者。 因為通道1 4 5是價設為一抹除通道，所以通信系統j 〇 〇 不是假設在接收模組150的輸出符號與進入傳輸模組14〇 的輸出符號之間的一對一對應。事實上，通信系統1 〇〇可 甚至不假設任何兩或多個封包的相關順序維持經由通道 1 4 5傳送，其中通道1 4 5包含一封包網路。因此，輸出符號 的關鍵值可使用一或多個上述關鍵值處理方法決定，且比 然以輸出符號存在接收模組1 5 0的順序決定。 接收模組1 5 0可將輸出符號提供給一解碼器1 5 5，且任 何資料接收模組1 5 0可接收有關這些輸出符號的關鍵值， 其中該等輸出符號是提供給一動態關鍵值再生器160°動 態關鍵值再生器1 60可將接收輸出符號的動態關鍵值再生 -24·

1280748 (20) ，及將這些動態關鍵值提供給解碼器丨5 5。靜態關鍵值產 生器163可將靜態關鍵值s〇、Si、…再生，及將他們提供 給解碼器1 5 5。靜態關鍵值產生器可在編碼與解碼處理期 間使用兩者來存取亂數產生器135。如果亂數是在此裝置 產生’此會是存取相同實體裝置的形式，或是存取用於亂 數產生的相同演算法，以達成同行為。解碼器1 5 5是使用 動態關鍵值再生器160與靜態關鍵值產生器163 —起提供 的關鍵值，且具對應輸出符號（I S (〇)、I s (1)、IS (2)、·） ’以復原一輸入檔案重組器i 6 5的接收輸入符號，該重組 器165可產生輸入檔案或輸入流1〇5的一副本丨7〇。 一編碼器 ί 圖2是在圖1顯示編碼器π 5的一具體實施例方塊圖。編 碼器115包含一靜態編碼器210、一動態編碼器22〇、與一 冗餘計算器23 0。靜態編碼器210可接收下列輸入：a)原始 資料符號IS(0)、IS(1)、…、，其是由輸入符號產 生器ll〇k供，及健存在一輸入符號緩衝器b)原始資 料符號數量K ; c)靜態關鍵值S〇、S i、···，其是由靜態關 鍵值產生器130提供；及d)冗餘符號數量r。只要接收這此 輸入，靜態編碼器205便可計算R個冗餘符號RE(〇)、rE(1) 、…RE(R-l)，且將在了面描述。典型上（但不是始終如此） ’經由靜態編碼器210產生的冗餘符號是儲存在輸入符號 緩衝器205。輸入符號緩衝器205可以只是邏輯，即是檔案 可實際儲存在一位置，且在符號緩衝器2〇5中的輸入符號 位置只是給予在原始檔案中這些符號位置的重新命名。 -25- 1280748 ___ (21) \'^^m 動態編碼器可接收輸入符號與冗餘符號，並且產生輸 出符號，此將在下面描述。在冗餘符號儲存在輸入符號緩 衝器20 5的一具體實施例中，動態編碼器220是從輸入符號 緩衝器2 0 5接收輸入符號與冗餘符號。 冗餘計算器230可從輸入符號數量K來計算冗餘符號數 量R。此計算是在下面進一步詳細描述。 在產生輸出符號速度是一重要資源的情況，輸入檔案 可使用靜態編碼器2 0 5來編碼，及在輸出符號傳輸開始之 前儲存在一中間裝置。此裝置可以是例如在不同於動態編 碼器220的一實體位置的一連接儲存裝置，它可包括在與 動態叙碼器2 2 0的相同實體裝置等。在檔案於使用動態編 碼器220編碼之前使用靜態編碼器205編碼的情況，實施動 態編碼器220的計算裝置不需要將資源致力於靜態編碼。 如此，它可將更多資源致力於動態編碼，為了要提高產生 輸入檔案的輸出符號的速度，產生其他檔案的輸出符號， 執行其他工作等。靜態編碼是否可在動態編碼之前執行是 因特殊實施而定。 靜態編4馬器概述 靜態編碼器2 1 0的一般操作將參考圖3和4描述。圖3是 描述靜態編碼方法的一具體實施例。在步驟3 0 5，保持追 蹤有多少冗餘符號產生的一變數j是設定成零。然後，在 步驟310，一第一冗餘符號RE(0)是以該等輸入符號IS(0) 、...IS (K-1)的其中至少一些輸入符號的函數F〇來計算。然 後，在步驟3 1 5，變數j會增量。其次，在步驟3 2 0，可測 1280748 (22) 式所有冗餘符號是否產生（即是j是否大於Κ·1?)。如果是 大於，那麼流程便會結束。否則，流程會處理步驟3 2 5。 在步驟325，RE(j)是以該等輸入符號is(0)、."IS(K_1)與 先前產生冗餘符號RE(0)、·.·、RE(j-l)的函數Fj來計算， 其中Fj不需要是因該等輸入符號的每一者或該等冗餘符 號的每一者而定的一函數。步驟315、320、和325會重複 ，直到R冗餘符號計算為止。 請即重新參考圖1和2 ’在一些具體實施例中，靜態編 碼器2 1 0是從靜態關鍵值產生器1 3 0接收一或多個靜態關 鍵值S 〇、S i、…。在這些具體實施例中，靜態編碼器2 i 〇 是使用靜態關鍵值來決定部份或全部函數Fj、F1、Fj」。 例如靜態關鍵值S 〇可用來決定函數f 〇，靜態關鍵值s !可用 來決定函數F!等。或者，一或多個靜態關鍵值s 〇、s i、… 可用來決定函數F 1等。在其他具體實施例中，不需要靜態 關鍵值，如此便不需要靜態關鍵值產生器130。 請即參考圖2和3，在一些具體實施例中，透過靜態編 碼器210產生的冗餘符號是儲存在輸入符號緩衝器205。圖 4是輸入符號緩衝器20 5的一具體實施例操作簡化說明。特 別是，靜態編碼器210能以輸入符號IS(0)、··.、lyn) 、RE(0)、…、RE(j-1)的函數Fj產生冗餘符號Re(j)，其中 該等輸入符號是從輸入符號緩衝器205接收，及將他儲存 到輸入符號缓衝器205。函數F〇、、…、FRq的正確形式 是因特殊應用而定' 典型上（但不是始終如此），函數F〇、 Fi、…、FR-!包括一些或所有他們對應引數的互斥〇R運算 1280748

(23) 。如刖述’這些函數可或不可實際使用由靜態關鍵值產生 器1 3 0所產生的靜態關鍵值。例如，在描述的一特殊具體 實施例中’第一較少函數可實施漢明碼，且不使用靜態關 鍵值S。 $ 1、.··’然而其餘函數可實施一低密度檢查碼及 使用靜態關鍵值。 動態編碼器 請即重新參考圖2,動態編碼器220是接收輸入符號iS(0) 、…、ISdl)、與冗餘符號RE(〇)、…、RE(R-1)、及每個 輸出符號的關鍵值I。包含原始輸入符號與冗餘符號的收 集在以下將可視為’，動態輸入符號”的收集。圖5是一動態 編碼器的一具體實施例簡化方塊圖。it編碼器是類似在 L u b y I it的編碼器的具體實施例。[u b y I是進一步詳細 描述此一編码器的操作。 動態編碼器5 00包括一加權選擇器51〇、一關聯器515、 一值函數選擇器520、與一計算器525。如圖5所示，K + R 個動態輸入符號是儲存在一動態符號緩衝器5 〇 5。在一具 體實施例中，動態符號緩衝器5 〇 5是圖2的輸入符號緩衝器 205。在其他具體實施例中，動態符號緩衝器50 5是從輪入 符號緩衝器205分開。動態關鍵值ι(透過在圖1顯示的動雜 關鍵值產生器120提供）是輸入加權選擇器510、關聯器515 、與值函數選擇器520動態輸入符號數目κ + R被提供給這 些組件510，51 5和520。計算器525被耦合以接收來自加權 選擇器510、關聯器515與值函數選擇器520的輸出，及從 動態符號緩衝器505接收符號。計算器525可產生輸出符號 -28- (24) 1280748

值。應了解，類似在圖5顯示元件的其他配置可使用，且 此疋根據本發明的一編碼起範例。例如，L u b y I和乙^ b y 11 疋拖述根據本發明使用在其他具體實施例的其他編螞器。 操作上，K + R個動態輸入符號是從輸入符號緩衝器$ 接收’及儲存在動態符號緩衝器5〇5。如前述，每個動賤 輸入符號具有一位置（例如，一輸入符號的位置可以是在 輸入樓案的原始位置）及一值。只要儲存的動態輪入符號 的位置決定，動態輸入符號可不需要以他們相對順序儲存 在動態符號緩衝器5 05。 透過使用關鍵值I與動態輸入符號數量K + R，加權選擇 器5 10可決定動態輸入符號的數量w(I)，其中該等動態輸 入符號是具有關鍵值I的輸出符號的”關聯值"。透過使用 關鍵值I、加權W(I)與動態輸入符號數量K + R，關聯器515 可決定與輸出符號有關的動態輸入符號位置的一清# AL(I)。應了解，如果關聯器515產生AL(I)，而無需在時 間之前知道W(I)，W(I)便不需要分開或計算。只要產生 AL(I)，W(I)便可容易決定，因為它是在AL(I)的關聯值數 量。 關聯器5 1 5是一映射，以接收一關鍵值I、一數值N、及 數值t，並且產生在0與^丨之間的整數值清單X(0)、···、 X(t-l)。例如，在圖5的動態編碼器5〇〇的情況中，N是等 於 K + R，t是等於 W(I)，且 AL(I)是清單 X(〇)、…、X(t-l)。 經由關聯器5 1 5提供的映射可使用各種不同形式。可存 取實際隨機或假隨機位元的來源’以使他的輸出是隨機的 -29- (25) 1280748 。然而’應該於相同關鍵 器與解碼器來選取產生冲目 隨機序列可透過具關鍵值 際隨機序列可用於計算_ 沒有假隨機序列會很有用 與解碼器溝通。 值I、相同N、及相同t透過編碼 同輸出。右要滿足此需求，一假 I的編瑪器與解碼器產生。一實 出，而不是一假隨機序列，假如 ’用於產生輸出的隨機序列需要

請集重新參考圖5 , 號的值B(I)可根據〜 。一適當值函數的特性是 輸出符號值B(I)與來自由 決定。既然值函數可滿足 只要I、W(I)、AL(I)是已知，輸出 值函數F(I)而經由計算器525計算

允許AL(I)指示的一關聯值可從 AL(I)所表示其他w(I)-l關聯值 此性值，所以使用在此步驟的一 較佳值函數是XOR值函數，它是容易計算，且容易反相。 然而’其他適當值函數可取代使用。例如，π是描 述可使用的其他適當值函數。 如果使用’值函數選擇器520可從關鍵值I及κ + R決定一 值函數F(I)。在一變化中，值函數F(I)於所有I是相同值函 數F。在此變化中，值函數選擇器52〇不需要，且計算器 525可使用值函數F構成。例如，值函數於所有I可以是x〇r ’即是輸出符號值是所關聯值的X〇r運算（互斥〇R)。 對於每個關鍵值I而言，加權選擇器5丨〇可從決定I及 K + R來決定一加權w(I)e在一變化中，加權選擇器51〇是 透過使用關鍵值I來選取W(I)，以先產生一亂數，然後使 用此數值來查閱在一分配表中儲存的W(I)值，或由加權選 擇器5 1 0存取。此一分配表如何形成及存取的更詳細描述

-30- 1280748 _ (26) 是在下面描述。只要加權選擇器510決定W(I)，此值便可 提供給關聯器5 1 5及計算器5 2 5。 透過使用清單AL(I)，加權W(I)與值函數F(I)是由值函 數選擇器520或一許選的值函數F提供，計算器525可存取 在動態符號緩衝器5 05中由AL(I)參考的W(I)動態輸入符 號，以計算目前輸出符號的值B(I)。用以計算AL(I)的一 程序範例是在下面描述，但是另一適當程序可取代使用。 最好是，程序可將選取當作一特定輸出符號關聯值的大致 相同機會提供給每個輸入符號，而且如果解碼器不具有它 可用的AL(I)，此是解碼器的替代的選擇方式。 動態編碼器5 00然後輸出1B(I)。事實上，動態編碼器500 可執行在圖6描述的動作，即是，產生一輸出符號值B(I) 來當作選擇輸入符號的一些值函數。在顯示的範例中，值 函數是XOR，輸出符號的加權W(I)是3，且關聯動態輸入 符號（關聯值）是在位置〇、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-l)相同位元數量，且接著具有與輸出 符號相同的位元數量。 產生的輸出符號然後會如上述傳送及接收。在此，假 設一些輸出符號遺失或未排序，或是由一或多個編碼器產 生。然而，假設接收的輸出符號是與他們的關鍵值指示接 收，且他們的值可確保正確性。如圖1所示，這些接收的 -31 - 1280748 Γ_ (27) 符號、及透過動態關鍵值再生器1 60從他們指示重建的對 應關鍵值、值Κ和R、及由靜態關鍵值產生器1 6 3重新產生 的靜態關鍵值S 〇、S 1、…是輸入解碼器1 5 5。 靜態編碼器 靜態編碼器的主要功能是以原始資料的復原可能面對 抹除的此一方式而將冗餘資訊加入原始資料。此冗餘資訊 可幫助一解碼器來復原一動態解碼器不能復原的輸入符 號。在典型應用方面，靜態編碼器從面對抹除保證復原到 所要正確程度所需的冗餘符號數量的觀點，及/或從編碼 處理及/或解碼處理計算代價的觀點是有效的。例如，在 ! 應用中，對於一特定目標抹除率是透過動態解碼器執行規 定而言，此目標是要使冗餘符號數量R儘可能小，如杲最 多一資料某部分ρ遺失，而可保證原始資料的快速復原。 可滿足這些需求的碼類型是LDPC碼，此在技術中眾所周 知的。雖然這些碼可在許多情況將原始資料復原，但是會 有除了原始輸入符號的兩或三個符號之外他們可復原每 個的不常見時後。如此，在一具體實施例中，在LDPC編 碼之前，輸入資料是使用一碼來先編碼，以便在如果有兩 或三個抹除時，可將原始資料復原。此先編碼會產生一第 一複數個冗餘符號。在此第一編碼之後，複數個原始符號 與第一複數個冗餘符號可使用一 LDPC編碼器來編碼。熟 諳此技者鍾眾所周知的且在下面簡短描述的擴充漢明碼 適於第^一位準編碼’如果有三個或更少棟除’它可將原始 資料復原，且透過增加少量的冗餘符號來復原。應了解， -32- 1280748 (28) 其他類型編妈亦可使用。例如，在一些應用方面，除了兩 或二個輸入符號之外的所有可復原。如此，在此應用方面 ’一 L D P C媽是適合的。此外，其他類型編碼對於例如 Reed-S〇lomon、Tornado等的特殊應用是適當的。因此， 應了解許多單獨類型編碼或組合可根據本發明的其他具 體實施例來使用。 圖7是根據本發明的的一靜態編碼器的特殊具體實施 例簡化方塊圖《靜態編碼器6〇〇包含一參數計算器605、一 漢明編碼器6 1 0、與一低密度核對檢查（L D P C)編碼器6 2 0 。參數計算器605可接收產生的輸入符號數量K與冗餘符 號數量R，並且產生參數D和EaD是表示由漢明編碼器610 產生的冗餘符號數量，且E是表示LDPC編碼器620產生的 冗餘符號數量。參數D是提供給漢明編碼器6 1 0，且參數E 是提供給L D P C編碼器6 2 0。 漢明編碼器610的耦合是從一輸入符號緩衝器625來接 收輸入符號IS(0)、…、is(K-l)、輸入符號數量K、與參數 D。在反應方面，漢明編碼器6 1 0可根據一漢明碼產生D +1 個冗餘符號HA(0)、HA(1)、…、HA(D)。在一具體實施例 中’輸入符號緩衝器625是圖2的輸入符號緩衝器205。漢 明編碼處理是將D + 1個冗餘符號加入原始K個輸入資料， 其中D是最小數值，以致於2d-D-12K。如熟諳此技者已知 ’几餘符號是以輸入符號的任何可能設定的一方式選取， 以致於不是所有他們皆為零，在複數個輸入符號與對應冗 餘符號之中的至少四個符號不是零。此特性可保證至少三 -33- 1280748 (29) 個參數的正確性。漢明編碼器6 1 0能以在錯誤修正與抹除 修正碼中熟諳此技者已知的任何方式實施。 LDPC編碼器620是耦合成可接收輸入符號IS(〇)、 ·、 IS(K-l)、輸入符號數量Κ + D+l與漢明碼冗餘符號、參數E 、與靜態關鍵值S〇、、…。LDPC編碼器620是根據一 LDPC 碼而產生E個冗餘符號。經由LDPC編碼器計算的冗餘符號 數量E是等於R-D-1 ’其中R是冗餘符號數量。如熟諳此技 者已知’有各種不同使用LDPC碼的編碼資訊方式。ldpc 碼是經由一繪圖結構來描述，該繪圖結構包含一組訊息節 點、一組檢查節點、與將訊息節點連接到檢查節點的邊緣 。該組有效LDPC碼字是這些i息節點設定值組，以致對 於每個檢查節點而言，相鄰訊息節點的XOR運算結果是零 。在某些應用方面，所有具有相同程度的訊息節點是最佳 ’即是連接到相同數量的檢查節點，而此可簡化編碼器實 施，且亦使解碼器的錯誤可能性計算更容易β在本發明的 一特殊具體實施例中，每個訊息節點連接的檢查節點數量 是4。可發現此數值可在編碼器的執行時間/計算負載與解 碼器失敗可能性之間提供一可接受的優缺點選擇。而且， 亦發現最好是檢查節點相鄰於在檢查節點組之中隨機選 取的一特定訊息節點。LDPC編碼器620能以在錯誤修正與 抹除修正碼的熟諳此技者中已知的任何方式實施。 圖8是描述是用在圖7顯示靜態編碼器的本發明的一具 體實施例操作。特別是，漢明編碼器6丨〇是從輸入符號緩 衝器20 5 (圖2)接收輸入符號，及產生D+1漢明編碼冗餘符 -34- 1280748 (30)

號，且該等漢明編碼冗餘符號是儲存在輪入符號緩衝器 2 0 5。然後，LDPC編碼器620是從輸入符號緩衝器20 5接收 輸入符號與D+1漢明編碼冗餘符號，及產生E個LDPC編碼 冗餘符號，其中該等LDPC編碼冗餘符號是儲存在輸入符 號緩衝器205。 如前述，在一些具體實施例中，LDPC編碼器620是接收 由圖1的靜態關鍵值產生器130產生的的靜態關鍵值s〇、Sj 、…。在一具體實施例中，靜態關鍵值產生器1 3 〇是一亂 數產生器’只要接收一來源訊息，其便會產生一連串亂數 (靜態關鍵值（S 〇、S i、…）。來源訊息可使用各種不同形式 J例如，可以是一實際亂數產生器的值。如另一範例所示 ，來源訊息能以一決定論方式從一 c P u時脈獲得的一字串 。不論來源訊息是什麼，它能與解碼器溝通，所以相同序 列的靜態關鍵值可透過解碼器產生。在許多應用方面，它 的優點是具有不會太大的來源訊息。在許多應用方面，來 源訊息可以是一 32位元整數值、或一 64位元整數值。 在圖6描述的靜態編碼器6 〇 〇的一特殊具體實施例中， 參數D是以最大的正數值D來計算，以致於2D-D“是大於 或等於輸入符號數量K。此外，參數β是以R-D“計算。圖 9是描述一參數計算器的一具體實施例的簡化流程圖，例 如圖7的參數計算器605，其可計算上述的參數〇和E。首 先’在步驟7 0 5 ’參數D是初始化成1。然後，在步驟7 1 〇 ，判斷2 - D -1是否小於K。如果不是，那麼流程便會到步 i 驟730。如果是肯定’流程便會處理步驟，其中參數〇 -35- 1280748 (31) 會增量。.然後，流程會返回處理步驟7 1 0。只要決定D， 那麼在步驟73 0，參數E便能以R-D-1來計算。 請即參考圖1，在一些特殊應用方面，在通道1 4 5上傳 送的檔案或流是相當小。例如，輸入檔案可以是一短聲頻 訊息或包含數千位元組的一 W e b網頁内容。上述一靜態編 碼器的特殊具體實施例在此情況可能較不理想。例如，一 些上述具體實施例會導致無效率使用記憶體與處理器速 度，因此較慢的資料重建。而且，一些上述具體實施例需 要一較大接收負荷來重建在系統使用者所設定可靠性參 數中的資料。此外，一些上述具體實施例會導致較低於所 要可靠的資料重建。 可發現當輸入符號數量減少時，解碼器的失敗可能性 會增加。亦發現此是主要的，因為如果原始内容的大小是 相當小，編碼處理便不會建立有關原始内容的足夠資訊。 因此，一編碼器的另一具體實施例用產生冗餘符號，以傳 遞有關原始符號的更多資訊。圖1 0是將描述的根據本發明 具體實施例的此一編碼器簡化流程圖。 首先，在步驟8 0 5，一變數i是初是化成0。變數i保持所 產生冗餘符號數量的追蹤。在步驟810，一數值t是以大於 或等於K/2的最小奇數整數值來計算。在步驟815，值P! 、P2、…、Pt是根據K、t、與一靜態關鍵值Si而產生。變 數Pi、P2、…、Pt是表示輸入符號的位置，且可用產生一 冗餘符號。在一特殊具體實施例中，例如圖5的關聯器5 1 5 的一關聯器是用產生Pi、P2、...、Pt。特別是，值t可當作 -36- 1280748

(32) W(I)輸入提供’值K可當作K + R輸入提供，且靜態關鍵值 Si可當作關鍵值I提供。注意，t的許多不同值可產生類似 碼效果，如此此特殊選擇只是一範例。 在步驟 820, RE(i)值是以值 is(p〇、is(PJ、…、IS(Pt) 的XOR運异來計异。在步驟825，變數|是增量1來準備下 一冗餘符號的計算’且在步驟830，可決定所有冗餘符號 是否計算。如果未計算，那麼流程便會返回步驟8丨5。 避_碼器概述

圖1 1是根據本發明而描述的—解碼器具體實施例的簡 化方塊圖。解碼器900可例如用來實施圖i的解碼器155。 靜怨解碼器9 0 〇包含一動態解码器9 〇 5及一靜態解碼器 9 1 〇。態解碼器9 0 5是從圖1的接收模組} 5 〇接收輸出符號 (a) B(Ib )、.··、及從動態關鐽值再生器1 60接收動態關 ，.值Ia Ib L、…。只要接收資料，動態解碼器90 5便會 嘗試重建輸入符號IS(0)、…、IS(K“）與冗餘符號re(〇)

、···RE(R-i)。本發明的一些具體實施例的一優點是動態 解碼器905不需要結束將所有輸入符號解碼。相反地，靜 態解碼器910可用來將動態解碼器9〇5不能復原的輸入符 號解碼。 經由動態解碼器905復原的輸入符號與冗餘符號是儲 存在一重建緩衝器915。只要完成動態解碼，#態解碼器 91〇便會嘗試將動態解碼器905不能復原的任何輸入符號 设原。特別是，靜態解碼器91〇是從重建緩衝器91 5接收輸 入符號與冗餘符號。此外，靜態解碼器910是從靜態關鍵 -37- 1280748 (33)

值產生器130(圖1)接收靜態關鍵值s〇、Si、…。請即重新 參考圖1，在一特殊具體實施例中，靜態關鍵值是透過經 由通信通道1 4 5而使一共同來源訊息與亂數產生器i 3 5通 信而產生，其中該亂數產生器1 3 5可驅動靜態關鍵值產生 器130。復原的輸入符號是提供給輸入檔案重組器165。 圖1 2疋根據本發明而描述用以解碼的一方法具體實施 例簡化流程圖。在步驟1 005，Q輸出符號是經由解碼器接 收。Q值亦是因解碼器可復原輸入符號的所要正確程度而 定。例如，如果解碼器能以較高可靠度復原所有輸入符號 ’那麼Q應該選擇大於輸入符號的數量。特別是，在一些 應用方面，當輸入符號數量較大時，Q便小於3 y❶大於原始 輸入符號數量。在其他應用方面，當輸入符號數量較小時 ，Q至少1 0%大於輸入符號數量。明確而言，Q能以輸入 符號數量K加上一數值A，其中A的選取可確保解碼器以較 高可靠度重建所有輸入符號。數值A的決定是在下面詳細 描述。如果對於不能解碼所有輸入符號的解碼器是可接受 (有時或始終），那麼Q可小於Κ +A，等於K或甚至小於κ。 很清楚，整個碼系統的一目標時常是要儘可能減少數值q ’而在與想要正確性程度的解碼處理成功上維持良好的可 能性保證。 在步驟1 0 1 0 ’動態解碼器9 〇 5可從Q接收的輸出符號將 輸入符號與冗餘符號再生。應了解，步驟1〇〇5與1〇1〇可實 質同時執行。例如’動態解碼器9 〇 5可在解碼器接收Q輸 / 出符號之前’開始將輸入符號與冗餘符號再生。 -38-

1280748 (34) 在動態解碼器9 0 5處理Q輸出符號之後，然後決定輸入 符號是否接收成想要正確性程度。想要正確性程度可以是 例如所有輸入符號、或一些數值、百分比等、小於所有輸 入符號。如果是如此，那麼流程便會結束。如果是否定’ 那麼流程便會執行步驟1 〇 2 0。在步驟1 0 2 0，靜態解碼器9 1 0 嘗試復原動態解碼器9 0 5不能復原的任何輸入符號。在靜 態解碼器9 1 0處理由動態解碼器9 0 5復原的輸入符號與冗 餘符號之後，然後流程便會結束。 圖1 3是根據本發明而描述一方法的另一具體實施例簡 化流程圖。此具體實施例是類似圖丨丨的描述，且包括步驟 1 〇 〇 5、1 〇 1 〇、1 〇 1 5和丨〇 2 5。但是，在步驟1 〇 2 5之後，流程 會執行步驟1030,其中可決定輸入符號是否以一想要的正 確性程度接收。如果是如此，那麼流程便會結束。如果是 否定’流程會執行步驟丨〇 3 5。在步驟丨〇 3 5，一或多個額外 輸出符號可接收°然後，流程會反回執行步驟1010,所以 動悲解碼器9 0 5及/或靜態解碼器9 1 0可嘗試將其餘未復原 的輸入符號復原。 圖1 4疋仍然根據本發明而描述用以解碼的一方法的另 …體貫％例簡化流程圖。在步驟丨〇 5 5，輸出符號是由解 碼為接收，且在步驟1〇6〇 ,動態解碼器9 0 5是將來自接收 輸出符號的輸入符說與冗餘符號再生。然後，在步驟1〇65 ’玎决疋動態解碼是否應該結束。此決定是根據處理的一 或多個輸出符號數量、復原的輸入符號數量、處理輸出符 號所使用的時間等而定β •39- 1280748 (35) 應了解步驟1 0 5 5、1 〇 6 〇、和1 〇 6 5可實同時執行。例如 ’當解妈器持續接收輸出符號時，動態解碼器905可開始 將輸入符號與冗餘符號再生。此外，當輸出符號接收及/ 或當輸出符號由動態解碼器905處理時，是否要停止動態 解碼處理的一評估會周期性執行。 在步驟1 065，如果決定動態解碼不會停止，那麼流程 便會返回步驟1055。但是，如果在步驟1〇65，可決定是否 結束動怨解碼，然後流程會執行步驟丨〇 7 〇。在步驟丨〇 7 〇 ’可決定輸入符號是否以一想要的正確性程度接收。如果 是如此，那麼流程便會結束。如果是否定，流程便會執行 步驟1 07 5。在步驟1 075，靜態解碼器91〇會嘗試動態解碼 器9 0 5不能復原的任何輸入符號復原。在靜態解碼器9 ^ 〇 處理由動態解碼器9 0 5接收的輸入符號與冗餘符號之後， 流程便會結束。 動態解碼器 圖1 5是根據本發明而顯示動態解碼器的一具體實施例 。動態解碼器1100包括與在圖5顯示動態編碼器5〇〇類似的 兀件。動態解碼器1100是類似在Luby I與Luby II中描述的 連鎖反應解碼器具體實施例。動態解碼器1 1 〇 〇包含一加權 選擇器510、一關聯器515、一值函數選擇器52〇、一輸出 符號緩衝器1105、一縮小器1115、一重建器112〇與一重建 緩衝器1125。當使用編碼器時，值函數選擇器52〇與在輸 出付號緩衝器1105中配置用於儲存值函數描述的空間是 選擇性使用’而且如果值函數於所有輸出符號是相同，便 -40- 1280748 (36) 可使用°顯不的重建緩衝器1125的數個登錄具一些重建的 輸入符號’及其他以問號表示未知的。例如，在圖1 5，在 位置0、2、5、6和K-1的輸入符號、及在位置〇和2的冗餘 符號已復原’且在位置1、3和4的輸入符號與在位置1的冗 餘符號尚未復原。 在操作上，對於使用關鍵值I與值Β(ι)的每個接收輸出 符號而5 ’解碼器Π00是執行下面。關鍵值I是提供給值 函數選擇器520、加權選擇器510、與關聯器515。透過使 用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 '與關聯器5 1 5是執行與動態編碼器2 2 0 (圖2)描述的相同 解踢器1 1 0 5操作。特別是經由在圖1 5的值函數選擇器5 2 0 、加權選擇器510、與關聯器515產生的值函數F(I)、加權 W (1 )、與清單A L (I)是與在圖5顯示對應元件相同的動態關 鍵值I。如果K和R是隨著不同輸入檔案而改變，他們便能 以任何傳統方式從編碼器到解碼器溝通，例如將它包括在 訊息標頭。 重建器1120會掃描輸出符號緩衝器11〇5，以尋找在此 儲存具有加權1(即是W(I)=1)的輸出符號，且AL(I)列出只 有一關聯值的位置。這些符號在此稱為一”可解碼組”的成 員。對於具上述特性的值函數而言，加權1的輸出符號是 -41 - 1280748 (37) 在可解碼組，因為一動態輸入符號值是從輸出符號決定。 當然，如果使用一值函數以允許動態輸入符號在除了具有 加權1之外的情況下來解碼。為了清楚，在此描述的範例 是假設該可解碼組是具有加權1的輸出符號，且其他值函 數可解碼情況的的這些範例擴充可從此描述而變得更顯 缺 〇 當重建器1 1 20尋找在可解碼組中的一輸出符號時，輸 出符號值B(I)或值函數F(I)是用來重建在AL(I)中歹出的 動態輸入符號，且重建的動態輸入符號是放置在輸入或冗 餘符號的適當位置上的重建緩衝器1125。如果表示的輸入 或冗餘符號已重建，重建器1 1 2 0將丟棄新重建的動態！輸入 符號、重寫既有重建輸入或冗餘符號、或將兩者相比較、 及如有不同便送出一錯誤。輸入或冗餘符號值只是輸出符 號值，其中值函數是所有關聯值的XOR運算。重建器1120 如此是將輸入與冗餘符號重建，但是只來自在可解碼組中 的輸出符號。只要來自可解碼組的一輸出符號用來將一輸 入或冗餘符號重建，它便可刪除，以節省輸出符號緩衝器 1 1 0 5的空間。刪除”用完”輸出符號亦可確保重建器1 1 2 0 不會持續重新造訪輸出符號。 最初，重建器1 1 20會等待，直到至少一輸出符號接收 為止，其中該至少一輸出符號是該可解碼組的成員。只要 使用一輸出符號，除了 一些其他輸出符號是一重建輸入或 冗餘符號及一另一輸入或冗餘符號的密切關係之外，可解 碼組便會重新空白。如此，將來自可解碼組成員的一輸入 -42 - 1280748 (38) 或冗餘符號重建會造成其他輸出符號加到該可解碼組。減 少輸出符號以將他們加到該可解碼組的處理是由縮小器 1 1 1 5執行。 縮小器1 1 1 5可掃描輸出符號緩衝器丨丨〇5與重建缓衝器 1125’以尋找具有清單al(I)的輸出符號，該清單AL(I) 是列出已復原的輸入或冗餘符號的位置。當縮小器丨丨i 5 使用關鍵值I尋找此一”可縮減”輸出符號時，縮小器丨丨i 5 可在位置h上獲得一接收動態輸入符號的值I $ (h),及如下 所示來修改B(I)、W(I)、與AL(I): B(I)是重新設定成β(Ι)Θ IS(h) W(I)是重新設定成w(I)-l 1 AL(I)重新設定成不包括h的AL(I) 在上述方程式，假設值函數是所有關聯值的XOR運算。 注思’ XOR是它本身反相，如果不是此情況，且另一值函 數最初是用來計算輸出符號，那麼此值函數的反相在此是 由滩小器1 1 1 5使用。很顯然，如果超過一關聯的值是已知 ’上述等效方程式可計算，以產生只與任何未知關聯值而 定的B(I)(因此，調整w(I)和L(I))。 縮小器1 1 1 5的動作是減少在輸出符號織衝器1 1 〇 5中輸 出符號的加權。當一輸出符號的加權減少到1 (或其他可解 碼條件於其他值函數發生），那麼輸出符號便會變成該可 解碼組的成員，其然後是由重建器1 120動作。實際上，只 要接收足夠量的輸出符號，縮小器1 1 15與重建器112〇可建 立一連鎖反應解碼，重建器1 1 20能將可解碼組解碼，以復 (39) 1280748 原更多動態輪入爲味^ 符破。縮小器1 1 1 5是使用這些重新復原輪 入或冗餘符號决# ,、 紐 ；減V更多輸出符號，所以他們能加到該可 解竭組等，直 π 夏到該可解碼組空白為止。 在圖1 5 S音-ΛΑ ^ ^ _ •、不的解稱器是以一簡單方式來部分重建輸入 兴*几符> _ 〜’而不考慮記憶體儲存裝置、計算周期或傳輸 日寸間。在般石民。σ “ 馬益記憶體，解碼時間或傳輸時間（抑制接收 輸出符號I I、θ β 此心 置）疋受限制，解碼器最佳化，以最佳使用者

^ 的 > 源。此最佳化範例是例如在Luby I和Luby Π k些最佳化亦可用於多階碼的動態解碼。此外，應 了解其他變化與等效解碼器可使用。

“圖1 6疋描述一靜態解碼器具體實施例的簡化方塊圖。 '資料疋使用例如圖7描述的一靜態編碼器來編碼時，此 具體實施例便可使用。靜態解碼器12〇〇包含一 LDpC解碼 器1 2 〇 5與一漢明解碼器1 2 1 0。L D P C解碼器1 2 0 5是從一重 建緩衝器1 2 1 5接收輸入符號與冗餘符號，且嘗試重建在動 怨解碼器解碼步驟之後未復原的重建緩衝器丨2丨5的這些 符號。在一些具體實施例中，重建緩衝器丨2丨5是重建緩衝 器1125(圖15)。LDPC解碼器12〇5是接收由靜態關鍵值產 生器1 3 0產生的靜態關鍵值s 〇、S !、…。此外，L D P C解码 器1 2 0 5是接收輸入符號數量κ、冗餘漢明符號數量D、與 冗餘LDPC符號數量E。LDPC解碼器1205是以熟諳此技者 所已知的一方式來儘可能接收許多輸入與冗餘符號，及將 這些值寫到在重建緩衝器1 2 1 5的他們對應位置。 1280748

(40) 漢明解瑪器1 2 1 0亦耦合成接收來自重建緩衝器丨2丨5的 輸入符號與冗餘符號。此外，漢明解瑪器丨2丨〇是接收輸入 符號數量K、與值D，其中d+丨是冗餘漢明符號數量。漢明 解碼裔1 2 1 0會嘗試將未由動態解碼器與[Dp c解碼器2 〇 〇 5 復原的這些輸入符號復原。雖然LDPC解碼器2005的目標 疋要復原許多可能的輸入與冗餘符號，但是漢明解碼器 2010只會嘗試復原輸入符號IS(〇)、IS(1)、…、is(n)。 LDPC解碼器與漢明解碼器的許多變化是熟諳此技者眾 所周知的’且可根據本發明使用在各種不同具體實施例。 在一特殊具體實施例中，漢明解碼器是使用一高斯消去演 算法實施。高斯消去演算法的許多變化對於熟諳此技者是 眾所周知的，且可根據本發明使用在各種不同具體實施例。 在某些應用方面，使用在圖i顯示不同類型解碼器i 5 5 疋比上述一者更理想。例如如果輸入符號數量K不是非常 大，例如小於1 〇〇〇 ,在輸出符號接收的可能處理中包括的 受化會使解碼器i 5 5收集明顯大於κ的許多輸出符號，為 了使動態與靜態解碼器修正所要抹除數量。在這些情況， 不同類型解碼器可使用。使用高斯消取將資料解碼的此 解码器具體實施例將參考圖丨7、1 8和1 9描述。 首先，請即重新參考圖1， 接枚輪出符號B (I a)、IB (b) ' 130接收關鍵值S〇、Si、...。 與冗餘符號值R。只要接收此 號1s(〇)、…、is(k-i)重建， 解碼器1 5 5是從接收模組1 5 〇 ···，及從靜態關鍵值產生器 此外，它接收輸入符號值κ 輸入，它便會嘗試將輸入符 其中該等輸入符號是傳遞給. •45· 1280748 (41) 輸入檔案重建器進一步處理。 請即參考圖1 7，解碼器1 3 〇 〇包含一動態矩陣產生器 1 3 0 5與一靜態矩陣產生器1 3 1 〇。動態矩陣產生器丨3 〇 5可接 收輸出符號B(Ia)、B(Ib)、…、動態關鍵值la、lb、…、與 參數K和R。此外，動態矩陣產生器13〇5是接收另一參數a ，其中該參數A是描述有多少輸出符號應該收集（即是收 集的輸出符號數量是K + A)。參數A的決定典型是因用於動 態與靜態編碼的方法而定，且將在下面詳細描述。在下面 描述中，收集的K + A輸出符號將可視為B(0)、B(l)、…、 B (K + A -1)。只要接收這些參數，線性方程式的系統便會 形成 C * 移項（IS(0)、…、IS(K-l)、RE(0)、…、RE(R」1) = 移項（B(0)、…、B(K + A-1))是透過勤態矩陣產生器1 3 0 5建 立，其中C是格式（K + A)x(K + R)的一矩陣。經由動態矩陣 產生器1 3 0 5產生的矩陣C將在下面詳細描述。 然後，靜態矩陣產生器1 3 1 0是從動態矩陣產生器丨3 〇 5 接收矩陣C，及使用關鍵值S 〇、S !、…來使矩陣c X R增加 更多列，以獲得一方程式系統： M* 移項（IS(0)、…、IS(K-l)、RE(0)、…、RE(R-1)) = 移項（B(0)、…、B(K + A-1)、0、···、〇)， 其中右邊向量的最後R登錄是零，而且其中Μ是格式 (K + A + R)x(K + R)。最後，線性方程式解決器1315的系統是 用來解決此系統方程式Μ及獲得一些或所有輸入符號 IS(0)、…、IS(K-l)。在一特殊具體貫施例中，線性方程 式解決器1 3 1 5的系統是使用一高斯消去演算法來解決線 -46- 1280748 (42) 性方程式的系統。 動態矩陣產生器丨3 〇 5與靜態矩陣產生器丨3丨〇將在下面 參考圖5的動態編碼器5 〇 〇與圖2的靜態編碼器2 0 5來詳細 描述。圖1 8是描述經由動態矩陣產生器丨3 〇 5使用的一方法 具體實施例簡化流程圖。在步驟1 4 0 5，動態矩陣產生器 12〇5是將格式（Κ + Α) χ (K + R)的矩陣c全部初始化成零。其 次’在步驟1410，關鍵值Ia、Ib、…的使用是與加權險擇 器51〇與關聯器515有關，以分別產生加權W(0)、…、 W(K + A-1)、與清單 al(0)、…、AL(K + A-1)。該等秋單 AL(k) 的每一者包含範圍〇、...、Κ + R-l的W(k)整數值。在步驟 ^15，這些整數值是用來記算，且AL(k) = (a(0)、… 、a(W(k)-l)，且登錄 c(k，a(0))、…、C(k，a(W(k)-l))SS 定成1。如前述，矩陣C從接收符號（B(0)、…、B(K + A-1)) 的觀點會導致未知（IS(0)、…、IS(K-1)、RE(0)、…、RE(R-l)) 的方程式系統。理由如下：只要動態編碼器選取加權W(k) 與關聯清單AL(k) = (a(0)、…、a(W(k)-l)))，對應輸出符號 B(k)可如下式獲得： B(k)二L(a(0))㊉ L(a(l))㊉、…、㊉ L(a(W(k)-l))， 其中L(j)表示在位置j的重建緩衝器1925的未知值。於在0 與K + A-1之間的所有k值的這些方程式可導致所要方程式 系統。 圖丨9是描述靜態矩陣產生器1 3 1 0使用的一方法具體實 施例簡化流程圖。此具體實施例將參考圖1 0描述。在圖1 〇 的井鱗82〇 ,注意，只要接收關鍵值Si，冗餘符號RE(i)便 -47-

1280748 (43) 能以1^(丨）=13(?1)©."©13(?〇計算，且？1、？2、...1>1是在 步驟815計算。此表示ISCP!)®…Θ IS(Pt)㊉RE(i) = 〇。從 重建緩衝器位置的觀點描述，此表示L(Pt)㊉·,.㊉L(Pt)㊉ L(i + K) = 0。Μ的設定值登錄（i，P〇、..Wt)、（i，UA)是等於 1，其中i是從K + A執行到K + A + R-l，一矩陣Μ可獲得，以 描述未知（IS(0)、…、IS(K-l)、RE(0)、…、RE(R-i))的線 性方程式系統，其中該等未知是與前述的接收符號B(〇) 、…、B(K + A-1)有關。 在步驟1 5 0 5，格式（K + R + A)x(K + R)的矩陣Μ初始化是讓 Μ的第Κ +Α列等於經由動態矩陣產生器1 3 0 5計算的矩陣c 。Μ的其备列是初始化成零。其次，在步驟1510，一變數 i是初始化成Κ + Α。此變數是保持Μ的最後R列。在步驟 15 12，冗餘符號i-K-A的關聯值數量t將會計算。此步驟是 類似圖8的步驟8 10。特別是，如杲t的另一選擇在圖8提供 的靜態編碼處理期間是最佳，那麼此選擇亦可用於在步驟 1 5 1 2計算的變數t。在步驟丨5丨5，關聯器5丨5是計算來自靜 態關鍵值Si的在〇與K-1之間的索引Pl、…、Pt ;輸入符號 數量K ;及整數值t。然後，矩陣μ的對應位置是在步驟1 5 3 〇 設定成1。在步驟1 5 4 0的增量與在步驟丨5 5 〇的測試可確保 Μ的所有最後R列可被造訪及計算。 在一些範例中，在圖1 7、1 8、和1 9顯示的具體實施例 比在此描述的其他具體實施例更理想，因為它允許比其他 具體實施例可相對收集較少成功解碼的輸出符號。解蝎器 的選擇是因廣泛的應用而定，且例如，不管收集的輪出符 -48 - (44) 1280748

號是否為一重要資源^ 一關聯器f施 清即重新參考圖5，關聯器5 1 5的一具體實施例是在 LUby⑽述。數值叹一質數。在操作上，當此具體實施 例用來计异AL(I)時，輪入大小K + R可調整，所以它會是 質數。在本發明中’冗餘符號數量的選擇是足夠大，所以 K + R是質數纟|應用方面，輸入N是質數的情況是相 當限制的。 用以實施N不需要是_質數的關聯器52〇的一方法的另 具體只；5e例疋在圖2〇顯示。首先，在步驟18〇5，一變數 k疋初始化成零。然後，在步驟1 8 1 0，一隨機整數γ可產 生。在一特殊具體實施例中，輸出符號的關鍵值I是用來 促成一亂數產生器。然後，在步驟1815，整數Y是取數值 N的杈數，以產生在〇與之間的一數值。在步驟丨82〇 , 想要數值Y是與先前產生（χ(〇)、χ(1)、…）的其他數值Y相 比較測試。如果數值γ是先前產生，那麼流程便會返回步 驟18 10。否則，在步驟1 82 5，將數值丫納入清單χ(〇)、χ(ι) 、…。接著’在步驟1830，決定是否已產生W(I)個數值。 若未產生，則流程返回步驟丨8丨〇。在圖8描述的流程結果 是w(i)數值x(0)、χ⑴、…、X(W(IM)的清單，其中在清單 的母個數值X是在〇與N-1之間的唯一整數值j然後，在步 驟83 5，清單AL⑴是設定成數值χ(〇)、χ(ι)、.,.x(w⑴-1)。 二-^Ajjjf器實施 編碼器/解碼器的實施與效率是因如圖2顯示的動態編 -49-

1280748 (45) 碼器2 2 0所產生的輸出符號的加權分配而定。特別是，用 以描述超過相較於輸入符號數量K的收集輸出符號數量 的參數A選擇是主要受到加權分配選擇的影響。加權選擇 的操作觀面是在一些重要加權分配描述之後接著說明。圖 21的方塊圖與圖22的流程圖是用來描述這些觀念。 在圖5顯示的加權選擇器5 1 0的工作如下述：只要接收 一關鍵值I與一長度K + R，加權選擇器便會輸入在〇到 Κ + R-l範圍稱為加權的一整數值W(I)。不像理想上可產生 具一致性隨機分配的一致性整數值的關聯器5 1 5，加權選 擇器5 1 0的輸出是不想要一致性，但是贊成加權，且將在 面描述。 如圖21所示，加權選擇器510包含兩處理WT_INIT 190 5 與 WT — INIT 1910 、與兩表格 WT —RBITS 1915 與 WT一DISTRIB 1 920。只有當第一關鍵值傳遞來將表格 WT — DISTRIB 1 920初始化，處理WT JNIT 1 905便會被喚

醒。W丁一DISTRIB 1 920的設計是系統的一重要觀念，且稍 後將詳細描述。處理WT — CALC 19 10會在每個呼叫被喚醒 ，以根據一關鍵值I產生一加權W (I)。如圖2 2的流程圖所 示，WT 一 CALC 1910是使用儲存在表WT — RB ITS 1915的關 鍵值I與隨機位元產生一亂數T(2005)。然後，T的值是用 來選取在表WT 一 DISTRIB 1920的一列數值Ν。 如圖21所示，在WT —DISTRIB 1 920的RANGE欄中的登 錄是在值MAX —VAL結束的正整數增量序列，且WT欄是在 M A X_WT結束的正整數增量序列。T的可能值組是在零與 -50- 1280748 _ (46) Μ ΑΧ —VAL-1之間的整數。一想要性值是Τ等於可能值範圍 中的任何值。Ν的值是透過搜尋RANGE欄來決定，直到Ν 發現可滿足 RANGE(N-1)ST< RANGE(N)(2010)為止。只要 發現一 Ν，W(I)的值便設定成WT(N)，即是表WT —DISTRIB 的WT欄的第N登錄，且此是傳回的加權（2015、2020)。在 圖2 1，對於顯示的表範例而言，如果Τ是等於3 8，5 0 0，那 麼Ν可發現是4，如此W(I)是設定成WT(4) = 8。在一較佳具 體實施例中，WT —DIST 1 920的列是以當N增加時， RANGE(N)-RANGE(N-1)值減少的此一方式組成。當使用 從第一列開始一連續搜尋時，此可滅少經由WT —DIST 1 9 2 0找出對應T值加權的平均搜尋時1間。在其他具體實施 例中，該等謝的其他配置是最佳的，且其他搜尋方法可使 用，例如二分搜尋法。 選取一加權分西己 一加權分配可於一特定碼處理選取，所以一輸入檔案 可使用下列來完重建：a)儘可能較少的輸出符號；b)儘可 能較少的運算；c)儘可能較可。典型上，所有這些最佳化 標準可藉者輸出符號的加權分配的正確選擇（即是在所有 I上的W(I)分配）、及在輸出符號上的關聯值分配（即是在 所有I上AI (I)的成員）達成。應強調的是當解碼處理可應用 ’而不官加權分配及關聯性選擇的分配’較佳具體實施例 值施 聯實 關 致 的導 取只 選化 別變 特小 而的 施配 實分 佳擇 最選 近當 接， 在 及 配 分配 權分 ， 加的時 用上變 使擇改 是選小 上 實 事 行 執 滿 圓 可 便 配 分 多 許 -51 - 1280748 ⑼

用以在一較佳具體實施例中決定分配的一方法現將描 述。使佣實際加權分配是因輸入符號數量K而定。分配是 在下面使用一範圍（Kmin，Kmax)、一因素β、與一相對負荷 α提供。此具有下義意：提供κ，其中KminSK<Kmax，冗餘 符號數量R是以大於或等於β*Κ的最小整數值來計算；收 集的輸出符號數量是至少（1+α)*Κ，即是上述參數Α是大 於或等於α*Κ的最小整數值。在使用關聯器520的第一版 的情況，然後R可額外滿足K + R是質數的條件，即是R是 大於或等於β*Κ的最小質數。如果應用不需要K + R質數， 那麼R能以大於或等於β*Κ的最小整數值來選取。 分配的本 > 是以格式表提供： 加權1 Ρ1 加權2 Ρ2 加權3 Ρ3 • * * ♦ ·

其中Ρ 1是加權1的對應可能性，Ρ2是加權2的對應可能性 等，而且其中PI、Ρ2、…的加總是1。此表示圖2 1的表 WT DISTRIB 1 920具有下列格式： 加權1 MAX_VAL*P 1 加權2 MAX —VAL*(P 1+P2) 加權3 MAX_VAL*(P1+P2 + P3) ί -52- 1280748 - (48) . 在此使用來計算表格的一般指南將在下面描述。設計 的一目標是要具有減少加權1的輸出符號的一非零數值， 以儘可能動態解碼處理。最好是，此值在動態解碼結束是 始終大於零。然而，一算術分析顯示如果一輸出符號的平 均加權是至少與輸入符號數量K的對數成比例，此會是可 能的，且此是設計在Luby I中描述的數個加權分配。本發 明的一些具體實施例可明顯將此平均加權減少到與K無 關的一固定常數。結杲，減少加權1的輸出符號數量在整 個動態解碼處理是不預期大於零。 加權分配設計的開始步驟是要獲得預期動態輸入符號 數量的表示，此值可在一部分X的動態輸入符號尚未復原 時，在動態解碼處理期間從該可解碼組中的輸出符號獲得 。此表示是加權1、2、…、k輸出符號的部分PI、P2、… 、Pk的函數，且在收集輸出符號數量及輸入與冗餘符號 數量之間比例。在下列，我們將此比例以γ表示。可看出 γ = (1 + α)/(1 + β)。此量的算術分析顯示此動態輸入符號的 預期數量能以下式表示： K*(l + p)*(x-e-(1”)*w(1-x)) (1) 其中X表示在動態解碼處理期間尚未復原的的動態輸入符 號部分，且ω(χ)是多項式：

Pl+2*P2*x + 3*P3*x2+... + k*Pk*xk*1 (2) 既然此數值指是本’質是統計的一預期量，所以是會變化的 。此變化分析暴露出是與預期未接收輸入符號數量平方根 -53 - 1280748 (49) 成比例，即是χ*Κ*(1 + β)的平方根。若要具有一合理保證 減少加權1的輸出符號相鄰的輸入符號數量是始終為正值 Ρ 1、…、Pk，且γ將以下式選取： Κ*( 1 + β)*(χ-^·(1+γ)*ω(1'χ))> e*sqrt(x*K*( 1+β)) (3) 其中此不等式將將所有χ值保持在一特定正實數ε與1之間 ，且c是大於1的正實數值。較大的c可較佳保證解碼處理 的成功。較小的ε是在動態解碼處理結束上的會有較少未 復原的輸入符號。較小ω( 1)是一輸出符號的平均加權。對 於這些限制，您可於一特定ε及一特定c來計算一多項式 ω(χ)，其中所有係數是非負值，且可滿足上述在ε與1之間 所有χ值的不等式，且其中ω(1)是儘可能小。在上述不等 式的一適當處理之後，此最佳化可經由各種方法完成，例 如單純演算法。. 實際表現將參考前述。上述常數c的選擇是保證整個解 碼器的錯誤可能性低於1 (Γ 1()。對於Κ>4925 1而言，錯誤可 能性是小於1 (Γ 12。這些表只是以可使用的加權分配來提 供。應了解其他加權分配亦可使用。 1280748 (50)

表1 K的範 :9900-14800 ， β=0·0081 ， α=0.1187 1 0.018235 2 0.477562 3 0.153565 4 0.102006 5 0.034651 7 0.048352 8 0.06084 18 0.058325 19 0.008401 70 0.008451 7 1 0.029613 表2 κ的範

：1 480 1 - 1 9680，β = 0.0121，α = 0.084 1 0.019314 2 0.483582 3 0.160754 4 0.081631 5 0.067541 8 0.094528 18 0.041968 19 0.019462 66 0.007987 67 0.023233 -55- 1280748 (51) K的範 表3 ：19681-29510 ， β=0.0151 ， α=0.0769 1 0.013531 2 0.488250 3 0.164810 4 0.070953 5 0.084243 8 0.050093 9 0.042547 19 0.055060 6 2 0.00501988 63 0.025491 表4 Κ的範

：29511-49250 ， β=0·0161 ， α=0.0674 1 0.013876 2 0.489087 3 0.1 62276 4 0.081638 5 0.069880 8 0.081339 9 0.014424 18 0.017712 19 0.040774 66 0.014680 67 0.0143 14 -56- 1280748 (52) K的範 表5 :4925 1 -64780，β = 0·015，α = 0.0 5 5 8 1 0.009117 2 0.492843 3 0.165983 4 0.072707 5 0.082303 8 0.056347 9 0.036917 19 0.055616 65 0.022195 66 0.005972

Κ的範 表6 :64781-79080 ， β=0·0114 ， α=0.05 1 0.007969 2 0.493570 3 0.166220 4 0.072646 5 0.082558 8 0.056058 9 0.037229 19 0.055590 65 0.025023 66 0.003 1 3 5 -57-

1280748 (53) 表7 K的範圍：79081-98623， β=0.01134， α=0.047 1 0.007544 2 0.49361 3 0.166458 4 0.071243 5 0.084913 8 0.049633 9 0.043365 19 0.045 23 1 20 0.010157 66 0.010479 67 0.017365

表8 Κ的範圍：98624-118349， β=0.01377， α-0.0424

1 0.006495 2 0.495044 3 0.168010 4 0.067900 5 0.089209 8 0.041731 9 0.050162 19 0.038837 20 0.015537 66 0.016298 67 0.010777 -58- 1280748 發明說明續ΐ: (54) 表9 Κ 的範圍：1 1 8 3 5 0，β = 0.01579，α = 0.03 93 1 0.004807 2 0.496472 3 0.166912 4 0.073374 5 0.082206 8 0.057471 9 0.035951 18 0.001167 19 0.054305 65 0.018235 66 0.009100

例如，如果Κ = 3 3,000，那麼冗餘符號數量會是大於 Κ*0.0161=531.3的最小整數R，以致於K + R是一質數。即 是，R = 533。收集的輸出符號數量是至少（1+0.0 6 74)*Κ， 其值是3 5 2 2 5。 表1的平均加權是大約6.7 5，且表2的平均加權是大約6 。當與前述Luby I的一具體實施例相比較，平均加權是明 顯較低，其中當反是60,000時，平均加權是28.68。 較少輸入符號的編碼 低相對負荷對於任何大小的輸入是較佳。從上表可看 出，當輸入符號數量K便成較小時，相對負荷α便會增加 。例如，如果輸入檔案具有10，000個位元組，且Κ是選取 -59- 1280748 _ (55) I聲糧麵 為1 0，0 0 0，所以每個符號包含1個位元組，那麼負荷是大 約1 1 %，此對於一些應用是不想要的。減少負荷的一方法 是在以減少輸入符號大小為代價來增加輸入符號數量Κ 。例如，當大約7%的負荷是想要時，Κ應該選擇40，0 00。 用 使 過 透 而 然 〇 元 位 個 2 是 小 大 的 *-gL· 符 入 輸 況 情 此 在非 是 決 解 的 題 小問 常此 入 輸 的 \ 大 高 的 例 施 實 陷體 缺具 算述 計ί 致 1 導圖 際在 實如 會 命 號據 符根 關一有， 用例率 使施效 來實算 去體計 消具的 斯他器 其 與 合 結 同 如 fcr 並 器 碼 解 此 使 即 ο 器 碼 解 任 述 碼 解 合 結 與 碼可 解荷 應 負 反的 鎖性 連能 的可 器敗 碼失 編小 態常 靜非 可器 與 ο ο : 8 ο 在22 。 是器 的量碼 要數編 想號態 是符動 用入 應輸 些 當 某， 在 言 決而 解確 此明 使 於 用 可 配 分 權 加 列 下 時 間 之 表10

Κ的範圍：800- 1 600，β = 0.08，α = 0·05 2 0.39 3 0.09 5 4 0.095 5 0.09 5 10 0.095 19 0.095 30 0.095 130 0.04 -60- 1280748 (56) I— 0.0 8 * K冗餘符號是根據例如圖1 0描述的靜態編碼器操 作而產生。解碼是使用例如在圖1 7描述的一解碼器來完 成。

如一範例所示，假設一輸入檔案具有1 6，0 0 0個位元組的 大小。輸入符號的選擇是每個包含1 6個位元組，所以輸入 符號數量Κ是1 000。在圖10的靜態編碼器是用來建立80個 冗餘符號。其次，定態編碼器220是與上述加權分配一起 使用，以產生輸出符號。接收器可收集（1+α)*Κ= 1050個 輸出符號，且將他們提供給圖1 7的解碼器。動態矩陣產生 器1305可建立格式1050 χ1080的矩陣。靜態矩陣產生器 1 3 3 0可建立格式1 1 3 0 X 1 0 8 0的矩陣，且將它傳遞給線性 方程式解決器1 340的系統，以嘗試將原始1 000個輸入符號 解碼，即是輸入樓案。 一些多階碼的一些特性

在上述多數範例中，輸入與輸出符號是在相同的位元 數量編碼，且每個輸出符號是放置在一封包（一封包是整 個接收或整個遺失的一傳輸單元）。在一些具體實施例中 ，通信系統是可修改，所以每個封包包含數個輸出符號。 一輸出符號的大小是根據許多因素而然後在將檔案分成 數個輸入符號中設定成可由輸入符號值大小決定的一大 小。除了當每個封包接收時，輸出符號整串到達之外，解 碼處理可實質保持不變。 輸入符號與輸出符號大小的設定是經常透過檔案大小 / 與輸出符號傳送的通信系統的要求。例如，如果一通信系 -61 - 1280748 (57) 統以其他方式將資料位元組群成一定義大小封包或數群 位元時，符號大小的設計是以封包或群大小開始。從此， 設計者可決定有多少輸出符號位元會在一封包或群中運 送，且決定輸出符號大小。為了簡化，設計者可設定等於 輸出符號大小的輸入符號，但是如果輸入資料以更方便產 生一不同輸入符號大小，它便可使用。 上述編碼處理是根據原始檔案而產生包括輸出符號的 的一封包流。在資料流的每個輸出符號產生是與所有其他 輸出符號無關，且在可建立的輸出符號數量上是沒有下限 與上限。一關鍵值是與每個輸出符號有關。該關鍵值與輸 入檔案的一些内容可決定輸出符號的值。結果，產生的輸 出符號不需要具有連續關鍵值，且在一些應用方面，隨機 產生關鍵值序列或假隨機產生序列是想要的。 多階碼具有如果原始檔案可分成K個相等大小輸入符 號，且每個輸出符號值是與一輸入符號值相同長度，那麼 檔案平均能以非常高可能性從K +A個輸出符號復原的特 性，其中A與K相比較是較小。例如，對於上面引用的加 權分配而言，如果K是大於19,681，A值超過α*Κ是至多 1 (Γ 12，且對於Κ的任何值而言，至多是1 0 4 G。既然特殊輸 出符號能以隨機或假隨機方式產生，且傳輸的特殊符號損 失是假設隨機，所以一些較小變化是存在復原輸入檔案所 需的實際輸出符號數量。在一些情況，如果接收器可從輸 出封包的一或多個來源收集更多封包，輸入檔案是仍然可 ； 復原，其中K + A封包的特殊收集是不組以將整個輸入檔案 -62- 1280748 (58) 解碼。 因為輸出符號數量只受到I解決的限制，所以超過K +A 個輸出符號可產生。例如，如果I是一 3 2位元數值，4 0億 個不同輸出符號可產生，然而檔案可包括K = 50,000的輸 入符號。在一些應用方面，只有這些40億個不同輸出符號 的少數可產生及傳送，且他是近似一輸入檔案能以非常少 部分可能輸出符號復原，及輸入檔案能以略多於Κ個輸出 符號復原的一優越可能性（甲設輸入檔案大小是與輸出符 號大小相同）。 在一些應用方面，不能將所有輸入符號解碼，或具有 相當低可能性將所有輸入符號解碼是可接k的。在此應用 方面，在接收K +A個輸出符號之後，一接收器可停止嘗試 將所有輪入符號解碼。或者，在接收少於K +A個輸出符號 之後，接收器可停止接收輸出符號。在一些應用方面，接 收器可甚至接收K或更少輸出符號。如此，應了解在本發 明的一些具體實施例中，想要正確性程度是不需要將所有 輸入符號復原。 此外，在不能完全復原是可接受的一些應用方面，資 料可編碼，以致於所有輸入符號不能復原，或者以致於輸 入符號的完全復原需要比輸入符號數量接收更多的輸出 符號。此一編碼通常需要較少計算代價，而且如此會是一 可接受方法來減少編碼的計算。 應了解在上述圖中的各種功能方塊能以硬體及/或軟體 組合實施，且在特殊實施方面，一些或所有方塊功能可組 -63- 1280748 (59) 合。同樣地，應料解在此描述的各種方法能以硬體及/或 軟體組合實施。 上述只是說明而不是限制。本發明的許多變化可從閱 讀此揭示而能使熟諳此技者變得更顯然。因此，本發明的 範圍不是參考上述來決定，相反是由附錄申請專利連同類 似的整個範圍來決定。 圖式簡覃說明

圖1係根據本發明具體實施例的一通信系統方塊圖； 圖2係根據本發明具體實施例的一編碼器方塊圖； 圖3係根據本發明具體實施例的用以產生冗餘符號之 一方法簡化方塊圖； 圖4係根據本發明具體實施例的一靜態編碼器基本操 作簡化方塊圖； 圖5係根據本發明具體實施例的一動態編碼器簡化方 塊圖， 圖6係根據本發明具體實施例的一動態編碼器基本操 作簡化方塊圖； 圖7係根據本發明具體實施例的一靜態編碼器簡化方 塊圖； 圖8係根據本發明具體實施例的一靜態編碼器基本操 作簡化方塊圖； 圖9係根據本發明具體實施例的用以計算編碼參數之 一方法簡化方塊圖； 圖1 0係根據本發明的另一具體實施例的一靜態編碼器 -64· 1280748 (60) 簡化流程圖； - 圖11係根據本發明具體實施例的一解碼器簡化方塊圖； . 圖1 2係根據本發明具體實施例的一解碼器操作簡化流 程圖； — 圖1 3係根據本發明的另一具體實施例的一解碼器操作 、 簡化流程圖； 圖1 4係仍然根據本發明的另一具體實施例的一解碼器 操作簡化流程圖； # 圖1 5係根據本發明具體實施例的一動態解碼器簡化方 塊圖； '圖1 6係根據本發明具體實施例的一靜態解碼器簡化方 塊圖； 圖1 7係根據本發明的另一具體實施例的一靜態解碼器 簡化方塊圖； 圖1 8係根據本發明具體實施例的一解碼器操作簡化流 程圖； # 圖1 9係根據本發明具體實施例的一解碼器另一操作簡 化流程圖； 圖20係根據本發明具體實施例的一聯合器簡化流程圖； 圖2 1係根據本發明特殊具體實施例的一加權選擇器簡 化方塊圖；及 圖2 2係根據本發明的另一具體實施例而經由一加權選 擇器使用的一處理簡化流程圖。 -65-

1280748 (61) 圖式代表符號說 明 100 通 信 系 統 101 輸 入 檔 案 系 105 輸 入 檔 案 流 110 輸 入 符 號 產 135 亂 數 產 生 器 130 靜 態 關 鍵 值 120， 160 動 態 關 鍵 值 115 編 碼 器 140 傳 輸 模 組 145 通 道 150 接 收 模 組 155， 1300 解 碼 器 165 輸 入 檔 案 重 170 輸 入 檔 案 210 靜 態 編 碼 器 220 動 態 編 碼 器 230 冗 餘 計 算 器 505 符 號 緩 衝 器 5 15 關 聯 器 5 10 加 權 選 擇 器 520 值 函 數 選 擇 525 計 算 器 600 靜 態 編 碼 器 統 生器 ~ 產生器 產生器 _ 組器 -66- 1280748 _ (62) 625 輸 入 符 號 緩 衝 器 6 10， 12 10 漢 明 編 碼 器 620， 120 5 L D P C編石! 器 605 參 數 計 算 器 90 5， 1100 動 態 解 媽 器 915， 1125, 12 15 重 建 缓 衝 器 900， 910， 1200 靜 態 解 石馬 器 1115 縮 小 器 1120 重 建 器 1105 輸 出 符 號 緩 衝 器 1305 動 態 矩 陣 產 生 器 13 10 靜 態 矩 陣 產 生 器 13 15 線 性 方 程 式 解 決器系統 -67-

Claims (1)

128奴94各〇〇9號專利申請案 中文申請專利範圍替換本(95年8月） W年&月I日修(更)正本 I〜|〇1 ♦ 拾、申請專利範圍 1. 一種用以在通信通道上將從一來源傳送給一目的地的 資料編碼之方法，該方法包含： 從欲傳送之輸入符號的一排列組產生複數個冗餘符 號；及

從包括該等輸入符號與該等冗餘符號的一符號組合 組產生複數個輸出符號，其中可能的輸出符號之數量 是遠大於在該符號組合組中的符號數量，其中至少一 輸出符號是從該組合組中多於一個符號及從該組合組 中少於所有的符號所產生，以致於該輸入符號的排列 組可從任何預定數量（N)的輸出符號再生成至一想要 的正確性程度。 2. 如申請專利範圍第1項之方法，其進一步包含在一通信 通道上傳送複數個輸出符號。

3. 如申請專利範圍第1項之方法，其進一步包含在一儲存 媒體上儲存複數個輸出符號。 4. 如申請專利範圍第1項之方法，其中N是大於在輸入符 號排列組中的輸入符號數量。 5. 如申請專利範圍第1項之方法，其中N是小於或等於在 輸入符號排列組中的輸入符號數量。 6. 如申請專利範圍第1項之方法，其進一步包含決定冗餘 符號數量R，以根據在輸入符號排列組中的輸入符號數 量K產生。 7.如申請專利範圍第6項之方法，其中K是輸入符號數量 82872-950731.DOC 1280748

的一評估值。 8. 如申請專利範圍第1項之方法，其中該等複數個符號是 根據一 LDPC碼產生。 9. 如申請專利範圍第1項之方法，其中該等複數個冗餘符 號包括複數個第一冗餘符號及複數個第二冗餘符號， 而且其中該產生複數個冗餘符號的步驟包含： 從該等輸入符號產生複數個第一冗餘符號；及 從該等第一冗餘符號與該等輸入符號產生複數個第 二冗餘符號。 10. 如申請專利範圍第9項之方法，其中該等複數個第一冗 餘符號是根據一漢明碼（H a m m i n g C 〇 d e )產生，而且其 中該等複數個第二冗餘符號是根據一 LDPC碼產生。 11. 如申請專利範圍第1 0項之方法，其進一步包含： 根據在輸入符號排列組中的輸入符號數量K來決定 第一冗餘符號數量D+1 ;及 根據產生的冗餘符號數量R及D-1來決定第二冗餘符 號數量E。 12. 如申請專利範圍第1 1項之方法，其進一步包含根據K 來決定R。 13. 如申請專利範圍第1 1項之方法，其中K是輸入符號數量 的一評估值。 14. 如申請專利範圍第1 1項之方法，其中D是最小整數值， 以致於2D-D-1 K ’而且其中E^R-D-l。 15. 如申請專利範圍第1項之方法，其中該想要正確性是該 82872-950731.DOC -2- 1280748

等輸入符號的完全復原。 16. 如申請專利範圍第1項之方法，其中該想要正確性是具 一高可能性的該等輸入符號的完全復原。 17. 如申請專利範圍第1項之方法，其中該想要正確性是G 個輸入符號的復原，其中G是小於在輸入符號排列組中 的輸入符號數量。 18. 如申請專利範圍第1項之方法，其中該等至多G個輸入 符號可從任何輸出符號再生，其中G是小於在輸入符號 排列組中的輸入符號數量。 19. 如申請專利範圍第1項之方法，其中對於每個冗餘符號 而言，該產生複數個冗餘符號包括： 根據一分配來決定t個不同輸入符號；及 將每個冗餘符號以該等t個不同輸入符號的XOR運 算來計算。 20. 如申請專利範圍第1 9項之方法，其中該t在所有冗餘符 號是相同。 21. 如申請專利範圍第20項之方法，其中該t是大於K/2的 最小奇數整數，其中K是在輸入符號排列組中的輸入符 號數量。 22. 如申請專利範圍第1 9項之方法，其中該分配是一致性 分配。 23. 如申請專利範圍第1項之方法，其進一步包含在一通信 通道上傳送該等複數個輸出符號，其中該產生複數個 輸出符號的步驟是與傳送該等複數個輸出符號的步驟 82872-950731.DOC

1280748 實質同時執行。 24. 如申請專利範圍第23項之方法，其中該產生複數個冗 餘符號的步驟是與傳送該等複數個輸出符號的步驟實 質同時執行。 25. 如申請專利範圍第2 3項之方法，其中該產生複數個冗 餘符號的步驟是在傳送該等複數個輸出符號的步驟之 前執行。 26. 如申請專利範圍第1項之方法，其中該產生複數個輸出 符號的步驟是使用一第一裝置執行，而且其中該產生 複數個冗餘符號的步驟是使用從該第一裝置分開的一 第二裝置執行。 27. —種用以在通信通道上將從一來源傳送給一目的地的 資料編碼之糸統5該糸統包含. 一靜態編碼器，其係耦合成接收複數個輸入符號， 該複數個輸入符號係從欲傳送之資料所產生的，該靜 態編碼器包括一冗餘符號產生器，以根據該等輸入符 號產生複數個冗餘符號；及 一動態編碼器，其係耦合成接收該複數個輸入符號 與複數個冗餘符號，該動態編碼器包括一輸出符號產 生器，以便從包括該等複數個輸入符號與該等複數個 冗餘符號的的一符號組合組產生複數個輸出符號，其 中可能之輸出符號的數量是遠大於在該組合組中的符 號數量，其中至少一輸出符號是從該組合組中多於一 個符號及從該組合組中少於所有的符號所產生，以致 82872-950731.DOC 1280748

於該輸入符號排列組可從任何預定數量（N)的輸出符 號再生成至一想要的正確性程度。 28. 如申請專利範圍第27項之系統，其中N是大於在輸入符 號排列組中的輸入符號數量。 29. 如申請專利範圍第27項之系統，其中N是小於或等於在 輸入符號排列組中的輸入符號數量。 30. 如申請專利範圍第2 7項之系統，其進一步包含一傳輸 模組，該傳輸模組是粞合到該動態編碼器與一通信通 道，以接收該等輸入符號，及在該通信通道上傳送該 等輸出符號。 31. 如申請專利範圍第2 7項之系統，其進一步包含一關鍵 值產生器，該關鍵值產生器是耦合到動態編碼器，以 產生每個輸出符號的一關鍵值，其中該動態編碼器是 根據該對應關鍵值而產生每個輸出符號。 32. 如申請專利範圍第2 7項之系統，其進一步包含一關鍵 值產生器，該關鍵值產生器是搞合到靜態編碼器，以 產生該等冗餘符號至少一些每一者的一關鍵值，其中 該靜態編碼器是耦合成接收每個關鍵值，而且其中該 靜態編碼器是根據該對應關鍵值而產生該等至少一些 冗餘符號的每一者。 33. 如申請專利範圍第27項之系統，其中該靜態編碼器包 括一 L D P C編碼器。 34. 如申請專利範圍第27項之系統，其中該靜態編碼器係 進一步包括：一第一靜態編碼器，其具有一第一冗餘 82872-950731.DOC 1280748

符號產生器；及一第二靜態編碼器，其具有一第二冗 餘符號產生器； 其中該等複數個冗餘符號包括一第一複數個冗餘符 號；及 一第二複數個冗餘符號； 其中該第一冗餘符號產生器是根據該等輸入符號而 產生第一複數個冗餘符號；及 其中該第二冗餘符號產生器是根據該等輸入符號與 該等第一複數個冗餘符號而產生該等第二複數個冗餘 符號。 35. 如申請專利範圍第3 4項之系統，其中該第一靜態編碼 器包括一漢明編碼器，而且其中該第二靜態編碼器包 括一 L D P C編碼器。 36. —種用以在一通信通道上接收從一來源傳送資料之方 法，該方法包含： 接收輸出符號，其中每個輸出符號是從在輸入符號 與冗餘符號組合組中的至少一符號產生，其中至少輸 出一符號是從該組合組中多於一個符號且少於該組合 組中所有符號所產生，其中可能之輸出符號的數量是 遠大於在該組合組中的符號數量，其中該等輸入符號 是來自輸入符號的一排列組，其中該等冗餘符號是從 該等輸入符號產生； 只要接收至少一部分輸出符號，便可自該等輸出符 號再生在組合組中的至少一部分符號，在該組合組中 82872-950731.DOC -6-

1280748 的部份符號包括複數個再生輸入符號及複數個再生冗 餘符號； 如果該自N個輸出符號再生至少一部分符號的步驟 不會將該等輸入符號再生成至一想要的正確性程度， 則自該複數個再生冗餘符號與複數個再生輸入符號再 生至少一些未再生的輸入符號。 37. 如申請專利範圍第3 6項之方法，其中該等冗餘符號包 括一第一複數個冗餘符號及一第二複數個冗餘符號， 其中該將至少一些未產生輸入符號再生的步驟包括： 從第一複數個冗餘符號的再生冗餘符號及複數個再 生輸入符號將該第二複數個冗餘符號的未產生輸入符 號與未產生冗餘符號的至少一者；及 如果從第一複數個冗餘符號的再生冗餘符號與複數 個再生輸入符號的再生步驟是不會將該等輸入符號再 生成一所要正確程度，將至少一未再生輸入符號從第 二複數個冗餘符號的冗餘符號與複數個解碼輸入符號 再生。 38. 如申請專利範圍第3 7項之方法，其中該第二複數個冗 餘符號的未再生輸入符號與未再生冗餘符號的一些是 使用一 LDPC解碼器再生；及 其中一些輸入符號是使用一漢明解碼器而從該等第 二複數個冗餘符號的冗餘符號再生。 39. 如申請專利範圍第3 6項之方法，其中該將至少一些未 再生輸入符號再生的步驟包括將所有未再生輸入符號 82872-950731.DOC

1280748 再生。 40. 如申請專利範圍第3 6項之方法，其中該將在組合組中 的至少一部分符號再生的步驟及該將至少一些未再生 輸入符號再生的步驟包括： 形成一第一矩陣，對於每個接收輸出符號而言，該 第一矩陣是表示在與該輸入符號有關的組合組中的符 號； 使用資訊來增強該第一矩陣，對於每個冗餘符號而 言，該資訊是表示與該冗餘符號有關的輸入符號；及 將至少一些輸入符號再生，作為由該增強的第一矩 陣所表示一方程式系統的解決。 41. 如申請專利範圍第3 6項之方法，其中N是大於或等於輸 入符號數量。 42. 如申請專利範圍第3 6項之方法，其中N是小於輸入符號 數量。 43. 如申請專利範圍第3 6項之方法，其中該將至少一些未 再生輸入符號再生包括將所有輸入符號再生。 44. 如申請專利範圍第3 6項之方法，其中該將至少一些未 再生輸入符號再生包括將少於所有輸入符號再生。 45. —種用以在一通信通道上接收從一來源傳送資料之系 統，該系統包括： 一接收模組，其是耦合到一通信通道，用以接收在 該通信通道上傳送的輸出符號，其中每個輸出符號是 從輸入符號與冗餘符號組合組中的至少一符號產生， 82872-95073i.DOC

1280748 其中至少一輸出符號是從在該組合組中超過一符號、 及組合組中的少於所有符號所產生，其中可能之輸出 符號的數量是遠大於在該組合組中的符號數量，其中 該等輸入符號是來自輸入符號的一排列組，其中該等 冗餘符號是從該等輸入符號產生； 一動態解碼器，只要接收至少一部分輸出符號，該 動態解碼器可自輸出符號解碼在該組合組中的一部分 符號，在該組合組中的部分符號包括複數個解碼的輸 入符號與複數個解碼的冗餘符號；以及 一靜態解碼器’如果有任何未解碼之輸入符號’便 可自該複數個解碼冗餘符號解碼至少一些未解碼之輸 入符號。 46. 如申請專利範圍第4 5項之系統，其中該靜態解碼器包 括一 LDPC解碼器。 47. 如申請專利範圍第4 5項之系統，其中該等冗餘符號包 括一第一複數個冗餘符號及一第二複數個冗餘符號， 其中該靜態解碼器包括： 一第一靜態解碼器，其是從該等第一複數個冗餘符 號與複數個解碼輸入符號、該等第二複數個冗餘符號 的未解碼輸入符號與未解碼冗餘符號的至少一者來解 碼；以及 一第二靜態解碼器，其是將來自談等第二複數個冗 餘符號的冗餘符號與該等複數個解碼輸入符號的至少 一未解碼輸入符號解碼。 82872-950731.DOC -9-

1280748 48. 如申請專利範圍第4 7項之系統，其中該第一靜態解碼 器包括一 LDPC解碼器，而且其中該第二靜態解碼器包 括一漢明解碼器。 49. 如申請專利範圍第4 5項之系統，其中該動態解碼器包 括一處理器，其中該處理器是構成來執行下列步驟： 形成一第一矩陣，對於每個接收輸出符號而言，該 第一矩陣是表示在與該輸入符號有關的該組合組中的 符號； 使用資訊來增強該第一矩陣，對於每個冗餘符號而 言，該資訊是表示與該冗餘符號有關的輸入符號；及 將至少一些輸入符號再生，作為由該增強的第一矩 陣所表示一方程式系統的解決。 50. 如申請專利範圍第3 6項之方法，其中只要接收任何數 量N的輸出符號，該將至少一部分符號再生的步驟便會 執行。 51. 如申請專利範圍第3 6項之方法，其中只要接收任何數 量N的輸出符號，該將至少一部分符號再生的步驟便可 執行，其中N是該等輸入符號可再生成一想要的正確 性。 52. 如申請專利範圍第3 6項之方法，其中該將至少一部分 符號再生的步驟能與接收該等輸出符號實質同時發 生。 82872-950731.DOC -10- 1280748 第0911；37009號專利申請案 中文圖式替換本(95年8月） 月(更)正本

82872-950731 205 1151280748

2 82872-950731 -2 - 300、1280748 305

82872-950731 1280748

4

82872-950731 4- 5001280748 POSITIONS 0 1 2 K-1 K K+R-1 K+R K+R K+R

82872-950731 6001280748

κ 625 κ R

LD(O), LD(1), …·，LD(E-1)

82872-950731 1280748

82872-950731 7001280748

705

82872-950731 800 1280748

是

圖ίο 82872-950731 900 1280748 B(la)，B(lb)，B(丨c)，…

圖11 82872-950731 -10- 10001280748

1005

82872-950731 -11 - 12 1005 10251280748

V

82872-950731 -12- 1055 10501280748

14 82872-950731 -13 - 11001280748 / KEY I K+R B(l)

輸出符號缓衝器 重建緩衝器 圖15 82872-950731 -14- 12001280748

1215

圖16 82872-950731 -15- 13001280748

B(g, B(lb)，B(g·… K, R, A S〇, Si,—

輸入符號

圖17 82872-950731 -16- 14001280748

S 18 82872-950731 -17- 15001280748

-18- 82872-950731 1280748 1800 /

是

圖20 82872-950731 19- 1280748

WT DISTRIB 圖21

圖22 82872-950731 -20-