用於對已編碼符號進行重編碼的網絡重編碼方法和設備的製作方法

2023-05-09 21:51:31 1

專利名稱：用於對已編碼符號進行重編碼的網絡重編碼方法和設備的製作方法
技術領域：
本發明涉及符號數據處理，以及更具體地，涉及對接收到的已編碼符號進行解碼， 並對要發送到與網絡相連的通信設備的符號數據進行編碼。這裡，「符號」指的是數據 塊或數據分組。
背景技術：
如本領域技術人員所知，數據在通信設備之間進行傳輸期間可能發生丟失或損 壞。在這種情況下，接收機可以要求發送方再次發送丟失或損壞的數據，或者可以在一開始 就發送兩份數據。另一種解決方案是通過碼，並且更具體地通過容錯碼，來對要發送的數據 進行編碼。在這種情況下，不必等到已接收到內容的每一個數據便能夠對其解碼，這是因為 只需要這些內容的(足夠的)一部分來重建發送方所發送的所有數據。在編碼方法之中，被稱為「網絡編碼」的方法提供了若干優勢。這種編碼方法 是由 Rudolf Ahlswede 等人在"Network informationflow", IEEE Transactions On Information Theory 2000中提出的。例如，這種編碼方法可用在無線和/或網際網路網絡 中。網絡編碼允許網絡的內部(或中間)路由器在接收到數據a和b時發送c = f (a，b) 類型的數據組合，而不是僅轉發接收到的數據a或b。因此，網絡編碼使得可以在網絡上達 到最大流量，而路由則不夠強大以至於無法在一些網絡中達到最大流量。然而，這要求路由 器能夠在發送接收到的數據之前，對接收到的數據進行計算，以對其進行編碼，以及最終的 接收機能夠對其接收到的已編碼數據進行解碼。由於已經證明了計算可以達到最大流量的函數f的集合是NP-Hard的，已經提 出了 一些概率統計方案。例如，Τ.Η0 等人已經在"A random linear network codingapproach to multicast」，IEEE Transaction on Information Theory 2006 中提出了一種使用無比率 隨機線性網絡編碼(RLNC)的方案。該方案具有若干優勢實現起來較為簡單，並可以是完 全分布式的。根據該方案，網絡中的每一個路由器將其接收到(輸入)的數據的隨機線性 組合轉發到其網絡中的其它路由器。接收機還接收係數矩陣和當該矩陣是可逆時允許接收 機通過Gauss或Gauss-Jordan消元法對接收到的數據進行解碼的數據。在網絡編碼允許獨立地產生符號時，可以產生無限的符號流。然而，不僅在編碼 期間，在解碼期間隨機線性網絡編碼也涉及複雜的計算。此外，當RLNC操作於Gallois域 GF(2k)時，其不適於在缺少有限域上的算法的通用處理器上進行編碼和解碼。N. Thomos 禾口 P. Frossard 已在"Collaborative video streaming withRaptor network coding」，ICME 2008中提出使用Raptor編碼的另一種方案。該方案引入了重編 碼方法，該重編碼方法是通過XOR布爾操作的方式將一對已編碼符號合併。然而，該方案在 解碼期間還要求高斯消元法，因而raptor網絡編碼失去了其在性能和屬性方面的優勢。Puducheri S.等人己在「Coding Schemes for an erasure relaychannelTroc. IEEE International Symposium on Information Theory, ISIT 2007，24 June 2007，pages 666-670中提出了另一種方案。

發明內容
因此，本發明的目的是提出一種使用被稱為Luby Transform碼(或LT碼)的無 比率碼的網絡重編碼方法和設備，LT碼的結構允許使用低複雜度的編碼器和解碼器。應該想至丨J, LT碼是Michael Luby 在 IEEE Symposium onFoundations of Computer Science 2002中所提出的奇偶校驗碼。LT碼可以由在輸入節點與輸出節點之間建立對應 關係的Tanner圖來表示。Tanner圖的每一個輸出節點是要解碼的已編碼符號(或LT碼符 號(或為LT碼字))，該已編碼符號是從網絡接收到的，並且(通過邊界)與一個或更多個 被稱為輸入節點的未編碼(或已解碼)的要發現的符號相連結，並且Tanner圖的每一個輸 出節點表示這些輸入節點之間的XOR布爾操作的結果。因此，當通信設備(例如，路由器或 用戶終端)的解碼器接收到具有表示對應鏈路的數據的已編碼符號(即，LT碼符號)時， 這些已編碼符號構成了 Tanner圖的輸出節點，Tanner圖的輸出節 點必須例如通過「置信傳 播(BP)解碼方法」來解碼，以產生構成Tanner圖的輸入節點的未編碼(或已解碼)的符 號。輸出節點與輸入節點之間的鏈路(或邊界)數限定了該輸出節點的度。因此，可以構 建Tanner圖的輸出節點的度的分布。LT碼要通過置信傳播解碼方法有效地進行解碼的能 力取決於其具體的度的分布。由於LT碼的度的分布是所謂的「魯棒孤子」分布，因而這種 效率更加重要。本發明提供了一種網絡重編碼方法，旨在對要發送到網絡的至少一個通信設備的 已編碼符號(或數據)進行重編碼，並且包括以下步驟通過將所選擇的輸入節點和/或具 有已知值、並被稱為部分解碼節點的輸出節點進行合併來對LT碼符號所定義的輸出節點 進行重編碼，以生成定義準備要發送的已產生輸出節點的新LT碼符號，該LT碼符號表示已 編碼符號，並且分別表示對其值要被發現的已解碼符號進行定義的輸入節點之間的XOR布 爾操作的結果，該輸出節點與該輸入節點在Tanner圖中相連結。根據本發明的方法可以包括單獨考慮或合併考慮的附加特徵，特別是-可以通過部分解碼節點之間的XOR布爾操作來合併該部分解碼節點；-可以通過在已產生輸出節點的度的當前分布的度之中，確定與第一被選參考分 布同樣的度具有最大差的度來開始，並且這使得能夠生成具有該度的已產生輸出節點，然 而可以通過合併至少一個部分解碼節點(即，在內部重編碼步驟期間臨時產生的節點)來 生成具有該度的已產生輸出節點；一可以通過所選試探法確定一個度，以便能夠生成具有該度的已產生輸出節點；一在已經生成已產生輸出節點後，可以將輸入節點的當前分布與第二被選參考 分布進行比較，以確定至少一個輸入節點是否已被過多地用於生成已產生輸出節點，並且 在肯定的情況下，如果該輸入節點允許在已產生輸出節點與連結到所述已產生輸出節點的 輸入節點合併時使已產生輸出節點的度保持不變，那麼可以用過少使用的輸入節點來代替 所述過多地用於所述已產生輸出節點的輸入節點的至少一個，以歸一化輸入節點的當前分 布；—可以將已產生輸出節點與包括所述過多使用的輸入節點、並具有等於2的度 的輸出節點進行合併；
一在己生成準備發送的已產生輸出節點後，可以對已產生輸出節點的度的當前分 布和輸入節點的當前分布進行更新；一該探索法可以在於檢查要產生的輸出節點的度是否低於或等於包括已解碼 輸入節點和具有至少一個相鄰節點(即，其在Tarmer圖中連結到的輸出節點)的輸入節點 在內的覆蓋的輸入節點的數目；該試探法還可以在於檢查條件
是否被驗證，其中，d是所確定的
要產生的輸出節點的度，以及n(k)是度k小於已知的d的部分解碼節點的數目。
本發明還提供了一種網絡重編碼設備，旨在對要發送到網絡的至少一個通信設備 的已編碼符號(或數據)進行重編碼，並包括重編碼裝置，布置用於通過將所選擇的輸入節 點和/或具有己知值並被稱為部分解碼節點的輸出節點相合併來對由LT碼符號所定義的 輸出節點進行重編碼，以生成定義準備要發送的已產生輸出節點的新LT碼符號，所述LT碼 符號表示已編碼符號，並且分別表示對其值已被發現的已解碼符號進行定義的輸入節點之 間的XOR布爾操作的結果，所述輸出節點與所述輸入節點在Tanner圖中相連結。根據本發明的網絡重編碼設備可以包括單獨考慮或合併考慮的附加特徵，特別 是-其重編碼裝置可以布置用於通過執行部分解碼節點之間的XOR布爾操作來合併 部分解碼節點；-其重編碼裝置可以布置用於在已產生輸出節點的度的當前分布的度之中，確定 與第一被選參考分布同樣的度具有最大差的度，並且這使得能夠生成具有該度的已產生輸 出節點，然後用於合併至少一個部分解碼節點，以生成具有該度的已產生輸出節點；-其重編碼裝置可以布置用於應用所選的試探法來確定一個度，以便能夠生成具 有該度的已產生輸出節點；—其重編碼裝置可以布置用於在已生成已產生輸出節點後，將輸入節點的當前 分布與第二被選參考分布進行比較，以確定至少一個輸入節點是否已被過多地用於生成已 產生輸出節點，並且在肯定的情況下，如果該輸入節點允許已產生輸出節點與連結到所述 已產生輸出節點的輸入節點時合併時使所述已產生輸出節點的度保持不變，那麼用過少使 用的輸入節點來替換過多地用於已產生輸出節點中的輸入節點的至少一個，以歸一化輸入 節點的當前分布；—其重編碼裝置可以布置用於將已產生輸出節點與包括過多使用的輸入節點、 並具有等於2的度的輸出節點進行合併；—其重編碼裝置可以布置用於將已產生輸出節點與包括兩個過多使用、並具有 等於1的度的輸入節點在內的輸出節點進行合併；一其重編碼裝置可以布置用於在已生成準備發送的已產生輸出節點後，對已產生 輸出節點的度的當前分布和輸入節點的當前分布進行更新；一其重編碼裝置可以布置用於應用試探法，該試探法在於檢查要產生的節點的 度是否低於或等於包括已解碼輸入節點和具有至少一個相鄰節點的輸入節點在內的覆蓋 的輸入節點的數目；-—其重編碼裝置可以布置用於應用試探法，該試探法還在於檢查條件dd≤∑d.n幻是否被驗證，其中，d是所確定的要產生的輸出節點的度，以及n(k)是度k的i
部分解碼節點的數目，k小於已知的d。本發明還提供了一種解碼器，旨在裝備可連接到網絡的通信設備，並且包括解碼 裝置，布置用於-將所選解碼方法應用到接收到的由LT碼符號定義的輸出節點，以得到其對應的 連結到的輸入節點，該LT碼符號表示已編碼符號，並且分別表示對其值已被發現的已解碼 符號進行定義的輸入節點之間的XOR布爾操作的結果，該輸出節點與該輸入節點在Tanner 圖中相連結，以及-存儲定義了輸入節點和輸出節點的數據，該數據與對這些輸入節點和輸出節點 與同一 Tarmer圖中的其它輸出節點和輸入節點所具有的鏈路的數目進行表示的度相對應 (換言之，維持允許對所選度的節點進行隨機訪問的索引)。該解碼器還可以包括以上所呈現的類型、並且耦合到其解碼裝置的網絡重編碼設 備。該解碼器還可以進一步包括檢測裝置，布置用於在存在要解碼的輸出節點的情況 下，確定其解碼裝置先前是否已經接收到要解碼的輸出節點，並且在肯定的情況下，產生消 息，以通過信號通知要解碼的輸出節點先前已經被接收到(並且先前很有可能是在解碼步 驟期間獲得的)，並且不必再次將其插入Tarmer圖。


在對此後詳細的說明書和附圖進行研究後，本發明的其它特徵和優勢將變得顯而 易見，在附圖中圖1示意性且功能性地示出了通過網絡彼此連接、並且每一個都包括編碼器的三 個用戶通信設備，以及根據本發明的解碼器的實施方式的示例，圖2示意性地示出了根據本發明的解碼器的Tarmer圖，圖3是示出度的魯棒孤子分布(黑色)的示例和實際(或當前)計算的產生的輸 出節點的度的分布(灰色)的示例的圖，圖4是示出輸入節點的均勻分布(水平線)的示例和所產生的輸入節點的當前 (呈現的)分布(黑色)的示例的圖，以及圖5示意性地示出了允許以度2的輸出節點對所產生的度4的輸出節點進行改善 的方法子步驟。
具體實施例方式附圖不僅可以用於使得本發明變得完整，如果需要的話，也可以對本發明的定義 做出貢獻。本發明的目的是提供一種網絡重編碼方法和對應的網絡重編碼設備(D)，旨在對 LT碼符號進行重編碼，以便允許在通過網絡彼此連接的通信設備中使用低複雜度的編碼器 和解碼器。在隨後的描述中，將考慮到網絡是其中通信設備(CEi)能夠至少以廣播或ad-hoc模式彼此發送內容的移動(或蜂窩，或無線)通信網絡(CN)。然而，本發明不限於這種網 絡。實際上，值得注意的是，如果網絡允許通信設備以對等(P2P)模式彼此通信，則該網絡 也可以是有線(或固定)類型的，例如DSL網絡或者光纖網絡，不然就是電纜網絡。此外，只要能夠彼此建立通信，通信設備(CEi)可以是意類型的。因此， 假定通信 設備(CEi)包括了通信數據機(或任何等效的通信裝置)，則通信設備(CEi)可以是路 由器、固定的個人計算機、膝上電腦、內容接收機(例如，位於用戶房屋中的家庭網關或機 頂盒(STB))、移動或蜂窩電話、固定電話、或個人數字助(PDA)。在隨後的描述中，將考慮用戶設備(CEi)屬於用戶，並且是行動電話。在圖1中僅 示出了三個行動電話CEl到CE3(i = 1 to 3)，然而在行動網路中，通常有多得多的通信設 備能夠彼此交換至少部分編碼內容。在所示出的示例中，每一個行動電話CEi包括經典型編碼器ED和根據本發明的解 碼器DC。然而重要的是，應該注意到，一些通信設備CEi，特別是初始提供內容的那些通信 設備CEi，可以僅包括經典型的編碼器ED，並有可能包括經典型的解碼器，而其他一些通信 設備CEi，特別是接收和轉發內容的那些通信設備CEi，可以僅包括根據本發明的解碼器DC 或適於根據本發明的經典型的解碼器、以及根據本發明的網絡重編碼設備D。這裡，「經典型的編碼器」指的是能夠對未編碼的(內容)數據(或符號(內容) 數據)進行編碼以產生LED碼符號的編碼器。此外，這裡的「經典型的解碼器」指的是能夠 通過已知的並且經典的解碼方法對經典型的編碼器ED或根據本發明的網絡重編碼設備D 所產生的LT碼符號進行解碼的解碼器。此外，「根據本發明的解碼器」指的是新型解碼器， 艮口，能夠通過已知並且經典的解碼方法對LT碼符號進行解碼，並適於簡化其本地耦合的或 包括的、根據本發明的網絡重編碼設備D的操作。在隨後的描述中，作為非限制的示例將考 慮到解碼方法是所謂的「置信傳播(BP)解碼方法」。然而，本發明不限於這種解碼方法。
如圖所示，根據本發明的網絡重編碼設備D包括重編碼模塊冊，配置用於訪問相 關聯的解碼器DC，並特別地訪問其內部狀態(並因而訪問其Tanner圖和相關聯的數據)， 以對其行動電話CEi先前從一個或更多其它行動電話CEi』接收到的符號進行重編碼。如前所述，這些LT碼符號表示已編碼符號。將LT碼符號發送到數據塊內，該數據 塊具有表示LT碼符號與具有已知值的未編碼符號數據的對應連結的關聯數據。LT碼符號是一個或更多符號數據的值的合併結果，更具體地，符號數據之間的 XOR布爾操作的結果。換言之，輸出節點的鏈路指定已經通過XOR布爾操作進行合併的未編 碼符號來生成LT碼符號。因此，當通信設備CEi的解碼器DC接收具有表示其各自鏈路的數據的編碼符號 (即，LT碼符號)時，必須使用該相關聯的數據來對這些編碼符號進行解碼，以恢復對應的 未編碼符號。為此，解碼器DC的解碼模塊DDM將接收到的LT碼符號(或編碼符號)饋入 Tanner圖，該接收到的LT碼符號定義輸出節點ON。同時，要恢復的未編碼符號定義Tanner 圖中連結到相關聯的輸出節點的輸入節點IN。圖2中示出了 Tarmer圖的有限示例。在該示例中，將10個輸出節點0N(a_j)鏈 接到一個或更多8個一組(A-H)的輸入節點IN。更具體地-輸出節點a連結到輸入節點A、B和C，從而作為其通過兩次XOR布爾操作的合併 結果(a = A B C)，
-輸出節點b連結到輸入節點B，從而與B相等，-輸出節點c連結到輸入節點D和E，從而作為其通過一次XOR布爾操作的合併的 結果(C = D E)，-輸出節點d連結到輸入節點A和F，從而作為其通過一次XOR布爾操作的合併的 結果(d = A F)，-輸出節點e連結到輸入節點E和H，從而作為其通過一次XOR布爾操作的合併的 結果(e = E H)，-輸出節點f連結到輸入節點F和G，從而作為其通過一次XOR布爾操作的合併的 結果(f = F G)，-輸出節點g連結到輸入節點B和G，從而作為其通過一次XOR布爾操作的合併的 結果(g = B G)，-輸出節點h連結到輸入節點D、E和F，從而作為其通過兩次XOR布爾操作的合併 的結果(h = D E F)，-輸出節點i連結到輸入節點G和H，從而作為其通過一次XOR布爾操作的合併的 結果(i = G H)，以及，-輸出節點j連結到輸入節點C，從而與C相等。重要的是，應該注意到，輸出節點ON與輸入節點IN之間的鏈路(或邊界)數定義 了該輸出節點ON的度。因此，在上述示例中-a的度等於3，_b的度等於1，-C的度等於2，-d的度等於2，_e的度等於2，-f的度等於2，-g的度等於2，-h的度等於3，-i的度等於2，以及_j的度等於1。通過隨後描述中的定義-「輸入節點」是表示Tarmer圖中原始數據的節點，-「解碼輸入節點」是其值已知的輸入節點。「解碼輸入節點」永遠不會有任何鏈路 (或邊緣)，並且永遠不會被呈現在Tarmer圖的輸出節點ON中。未解碼輸入節點不具有已 知的值，並且不能在重編碼的同時使用，-「覆蓋的輸入節點」是被解碼的輸入節點，或具有至少一個相鄰節點(即，在 Tarmer圖中與之連結的輸出節點)的輸入節點，_ 「輸出節點」是表示已編碼符號的節點。其可以是已經接收到的或者可以從解碼 步驟中產生，-「部分解碼節點」(或，「已知節點」)是已解碼輸入節點或具有已知值的輸出節
佔，
-「已產生輸出節點」是網絡重編碼設備D產生的節點，並準備發送至一個或更多 通信設備CEi，以及-「部分產生節點」是網絡重編碼設備D在內部重編碼步驟期間臨時產生的節點。解碼器DC將Tanner圖存儲到諸如存儲器之類的存儲裝置中。重編碼模塊RM布置用於通過合併所選擇的部分解碼節點(或已知節點)來對輸 出節點進行 重編碼，以生成定義準備要發送的已產生輸出節點的新LT碼符號，該部分解碼 節點(或已知節點)即輸入節點和/或具有已知值的輸出節點。優選地，這些合併是部分解碼節點之間的X0R布爾操作。然而也可以是例如有限 域(GF(pq))內的線性組合。然而，這需要存儲針對所有邊界(或鏈路)上的線性組合的係數。優選地，根據本發明的網絡重編碼設備D(特別是其重編碼模塊RM)至少部分地 由軟體模塊組成。然而，它也可以由電子電路或硬體模塊組成，或者是硬體和軟體模塊的 組合(在這種情況下，重編碼設備D還包括允許在硬體與軟體模塊之間交互的軟體接口)。 在專門由軟體模塊組成的情況下，可以將其存儲在通信設備CEi的存儲器中(例如，在通信 設備CEi的解碼器DC中)，或在任何可被通信設備CEi所讀取的計算機軟體產品中，例如 CD-ROM。為了對輸出節點ON進行重編碼，重編碼模塊RM執行此後所述的網絡重編碼方法。例如，該方法包括第一步驟在到目前為止已經產生的輸出節點ON的度的當前 (或實際)分布的度dj之中，確定與第一被選參考分布相同的度具有最大差的一個度，以便 能夠生成具有該度的已產生輸出節點。 該第一被選參考分布可以是所謂的魯棒孤子分布。注意到，該分布是在離散集合上的。在圖3的圖中示出了已產生輸出節點的度的魯棒孤子分布(黑色)的示例和已產 生輸出節點的度的實際(或當前)分布(灰色)的示例。例如，重編碼模塊RM可以首先針對每一度計算當前分布與第一被選參考分布之 間的差。然後，可以將結果排序。在圖3示出的示例中，可以觀察到，兩個分布的相同度之 間的最大差出現在等於4的度上，然後在等於2的度上，然後在等於16的度上，然後在等於 5的度上，等等。可以通過重編碼模塊RM根據與輸出節點相關的信息來計算已產生輸出節點的度 的當前分布，該信息是重編碼模塊冊先前產生的，並存儲在諸如存儲器之類的存儲裝置 中。對當前分布與第一被選參考分布之間的度差的計算旨在優選地針對下一個要產 生的輸出節點，確定必須使用的當前分布的度，以使得該當前分布更接近於第一被選參考 分布。事實上，本領域技術人員知道LT碼的性能取決於其分布，因此，當LT碼符號的當前 分布維持與最佳分布(如，魯棒孤子分布)接近時，這些性能是最佳的。因此，一旦重編碼模塊RM已經計算出當前分布與第一被選參考分布之間的度 差，重編碼模塊RM可以對結果進行排序，以得到用於增強當前分布的度建議(degree suggestion)的列表。然後，針對每一個度dj的建議，重編碼模塊RM可以檢查是否能夠產生度dj的節點。為此，可以使用試探法。例如，該試探法可以是檢查將要產生的輸出節點的度d是否低於或等於覆蓋的輸 入節點(即，已解碼輸入節點和具有至少一個相鄰節點的輸入節點)的數目。解碼器DC保 持該數目的值最新。為了給出更好的結果，可以在例如稍後所描述的另一種條件下來完成這種試探法。由於無法使用具有度d勺輸出節點來產生度d小於Jd<r)的輸出節點，重編碼模
塊RM可以檢查條件
是否被驗證，其中，d是所確定的要產生的輸出節點的度，
以及n(k)是度為k的部分解碼節點的數目，k小於已知的d。換言之，必須檢查是否有足夠 的度為小於d的k(k 1的節點增加到所產生的度為Ds的節 點時，衝突的數目遵循參數(k，Ds-n0, ncovered-n0)的超幾何定律，如下給出該參數的平均數 Cs+1 Cs+1 = k* (Ds-n0) / (ncovered-n0)。因此，一旦已經增加第S+1個節點，節點的度Ds+1為Ds+1 = Ds+k_2*Cs+1，其中，D0 = (還可以設置隊=0並且在最後一步增加IV然而這需要使用隨後對cs+1的定義cs+1 = k* (Ds/ (ncovered-n0))為了檢查是否可以產生度為d的節點，可以執行隨後的兩個子步驟。第一子步驟是檢查要產生的節點的度d是否低於或等於覆蓋的輸入節點的數目。第二子步驟是增加所有度k小於或等於所希望(或期望)的度d(k< d)的 節點，以計算度D(即，一旦已經執行每一項合併所產生的度)。如果D彡d，可以推導 出可以產生度為d的節點。可以使用檢查是否可以產生度為L的節點的算法來遞歸地 計算D。不在「一擊」中聚集所有的節點，而是僅在可以增大當前度時才聚集節點。事 實上，如果在一擊中聚集節點，該聚集的結果可以是度小於其任何一個的節點(例如， (a b c d) (a b c) = d)。因此，在每一次迭代中，僅保持先前值的最大值， 並且每次一個節點地增加該值。這可以通過如下的例證來實現D = 0For k = d to 2For i = 1 to n(k)[其中，n(k)是度為k的已知節點的數目]
D = max (D, D+k一2氺k氺(D) / (ncovered一n0))EndForEndForReturn D+n0 彡 L.通過用另一個第二子步驟來代替前述試探法的第二子步驟，可以改進前述的試探 法，以便在避免超過所選的目標的同時考慮到可能的衝突。假定只在其度低於或等於L與D之間的差時才增加節點，該其它第二子步驟在於 從高的度到低的度漸進地增加節點。換言之，由於不想產生具有太高的度的已編碼符號，該 節點不能超過要產生的重編碼符號中的剩餘空間。因此，如果例如想要產生度為6的節點， 則不能增加兩個度為5的節點，而是必須增加一個度為5的節點和一個度為1的節點。這 可以通過如下的例程來實現D = 0For k = d to 2For i = 1 to n(k)[其中，n(k)是度為k的已知節點的數目]D = max(D, D+k-2*Econflicts(k, D))[其中，當將所有節點引入具有 nc。vered 個覆蓋的輸入節點和 個已解碼輸入節點的Tanner圖中時，Econflicts(k, D)等於k*D/ (ncovered-n0)，並與在將度為k的節點增加到度為D的部分產生節點時可以期望的衝突數相 對應。由於針對k= 1沒有衝突，度為D的節點不能具有任何與已解碼輸入節點的鏈路(或 邊界)。因此，在E。。nfli。ts(0，D) = 0的情況下，將總是在最後一步增加nQ。]If L 彡 D+n0 Then Return TRUEIf k > L-D Then Break (for i = 1 to n(k)loop)EndForEndForReturn FALSE.仍然可以改進前述的試探法，以考慮到可能的衝突，並在考慮到衝突的同時避免 超過所選的目標。實際上，可能考慮到，可以增加度k大於L-D(k>L-D)的節點，並且在發 生足夠的衝突時，可以具有度為L的節點。這可以通過如下的例程來實現D = 0For k = d to 2For i = 1 to n(k)[其中，n(k)是度為k的已知節點的數目]D = max (D，D+k_2*Ec。nflicts (k，D))If L ^ D+n0 Then Return TRUEIf k-2*Econflicts(k，D) > L-D Then Break (for i = 1 to n(k)loop)EndForEndForReturn FALSE.同樣重要的是，應該注意到，試探法的選擇將對計算成本和LT碼的性能造成影
響。試探法越簡單，則計算成本將越低，同時性能將越低。
如果所使用的試探法顯示出可以產生度為d的輸出節點，則重編碼模塊RM通過合 並至少一個部分解碼節點以生成具有度d的已產生輸出節點來完成第一方法步驟。否則， 嘗試隨後的度建議，直到發現可以滿足的度建議。最後一種情況將會發生，這是因為至少可 以複製先前接收到的節點中的一個。因此，嘗試產生其度具有已產生符號的最高缺陷的已 編碼符號是很有意義的。為了產生度為d的節點，重編碼模塊RM可如下進行。可以從度為d的部分解碼節點開始，並增加部分解碼節點，直到具有度為d的節點 為止。每一次增加部分解碼節點，得到等於先前值與所增加的部分解碼節點的值進行X0R 的新結果。然後，將有助於所增加的部分解碼節點的輸入節點增加到有助於所產生節點的 節點列表。在該節點產生期間，重編碼模塊RM以度為d的節點開始，並隨後具有一直下降到1 的度的節點。事實上，優選首先使用最大的符號，然後使用小的符號來完成已產生節點，以 成功地準確到達所期望的度d。因此，決不允許合併降低正在產生的節點的度。此外，如果 部分解碼節點的度低於或等於所期望的度d和正在產生的節點的當前度之差，優選僅嘗試 增加該部分解碼節點。一旦正在產生的節點具有所期望的度d，重編碼模塊RM便停止第一 方法步驟。上述的節點產生可以通過如下的例程來實現，其中，L是在第一方法步驟的第一部 分中確定的期望度，以及G是部分產生節點L = Result of the first part of the first setp
G=0For k = d to 1While some node N of degree k as not been triedand k 彡 L-degreeOf (G) doN = Choose a random node of degree LIf degreeOf (G+N) > degreeOf (G)thenG = G+N(X0R their Value, add input nodes and removeinput nodes present twice)EnflfEndffhileEndForReturn G.重要的是，應該注意到，當重編碼模塊RM使用考慮到可能的衝突發生的試探法 時，可以允許正在產生的節點的度暫時下降。這等於放寬了上述節點產生機制的限制之一。 然而，如果部分解碼節點的度低於或等於所期望的度與正在產生的節點的當前度之差，則 仍然增加該部分解碼節點。該節點產生的變型可以通過如下的例程來實現L = Result of the first part of the first setp
G=0
For k = d to 1While some node n of degree k as not been triedand k 彡 L-degreeOf (G) doN = Choose a random node of degree LG = G+L(X0R their Value, add input nodes and removeinput nodes present twice)EndffhileEndForReturn G. 可以放寬限制來增強前述節點產生機制，該限制是僅在部分解碼節點的度低於 或等於所期望的度與正在產生的節點的當前度之間的差時才增加該部分解碼節點。在 該變型中，仍然考慮到了衝突。例如，當正在產生度為L的節點N時，只有在L-D ^ d-2. EConflicts(d,D)時，重編碼模塊RM才可以嘗試將度為d的部分解碼節點增加到所產生的 度為D的節點。如果使用最後描述的試探法，則該節點產生的變型會更有用。這可以通過 如下的例程來實現L = Result of the first part of the first setp
G=0For k = d to 1While some node n of degree k as not been triedand k_2. EConflicts (k, degreeOf (G) _iadded) ( L_degreeOf (G)and degreeOf (G) < L doN = Choose a random node of degree LG = G+N(X0R their Value, add input nodes andremove input nodes present twice)EndffhileEndForReturn G.在有很多度較低(例如，1、2或3)的節點的情況下，可以決定僅使用低度的節點
來構建高度的節點，而不是通過增加具有可能的最高的度的節點來開始。為此，可以例如將 從1到1 (為了僅使用度為1的節點)、或從2到1 (為了僅使用度為1和2的節點)、或否 則從3到1(為了僅使用度為1、2和3的節點)的「For loop」用到最近的例程中。例如，還可以根據節點的得分(即，其與第二被選參考分布之差)來選擇要增加的 度為1的節點，而不是選擇度為1的隨機節點。這僅要求根據節點的得分來對度為1的節 點進行排序，得分可從第二被選參考分布推導出。在已經使用第一方法步驟生成已產生輸出節點後，可以通過第二方法步驟來改善 該已產生輸出節點。該第二方法步驟可以是對Tanner圖中的輸入節點的當前分布進行歸一化，以便維持與諸如均勻分布之類的最優分布(或第二被選參考分布)接近。為此，重編碼模塊RM可以將輸入節點的當前分布與第二被選參考分布相比較，以 確定至少一個輸入節點，該至少一個輸入節點已經被過多用於生成已產生輸出節點，並允 許在已產生輸出節點與連結到已產生輸出節點的輸入節點合併時使已產生輸出節點的度 保持不變。輸入節點的當前分布可以由重編碼模塊RM根據與輸出節點相關的信息計算得 到，該信息由重編碼模塊冊先前產生並存儲在諸如存儲器之類的存儲裝置中。在圖4的圖中示出了輸入節點的均勻分布(水平線)的示例和已產生輸入節點的 度的當前(呈現的)分布(黑色)的示例。均勻的輸入節點分布是在其中所有輸入節點以 相同的次數使用的分布。在圖4示出的示例中，可以觀察到，應該避免再次發送輸入節點A或F，而是應該發 送輸入節點C或E。當重編碼模塊RM已經確定至少一個使用過多的輸入節點時，可以通過過少使用 的輸入節點來代替這些在已產生輸出節點中過多使用的輸入節點(這是已經確定的)中的 至少一個，以對輸入節點的當前分布進行歸一化。使用包括過多使用的輸入節點、並選擇等於2的度的輸出節點是有有益的。事實 上，回想起來，LT碼符號(當其非常長時)具有多於50%的度等於2的(已編碼)輸出節 點。因此，由於x x = 0，如果有部分產生節點s = a b c d和度為2的輸出節點 t = a e，可以生成已產生輸出節點r = s t = e b c d(移除輸入節點a(在這 裡視為使用過多)，用輸入節點e(在這裡視為使用過少)來代替)。圖5中示出了允許使用度為2的輸出節點Y ( Y = A E)來改善度為4的已產 生輸出節點5(5 = A B C D)的方法子步驟的示例。由於A A = 0，改善的已產 生輸出節點0的度仍然為4，然而過多使用的輸入節點A已經由過少使用的輸入節點E所 代替(S = E B C D)。為了進行已產生輸出節點的改善，重編碼模塊RM可以如下進行。針對包括在要改 善的已產生輸出節點中的每一個輸入節點N，重編碼模塊RM搜索度為2的、包含該輸入節 點N的所有輸出節點。然後，重編碼模塊RM可在這些輸出節點中搜索能夠最好地增強要改 善的已產生輸出節點的得分的節點。如果增強是正向的，則執行合併(X0R)。然後，可以轉 到另一個包括在要改善的已產生輸出節點中的輸入節點N，並重複該處理。如果發生衝突， 即，如果要改善的已產生輸出節點的度減小，則不執行合併(X0R)。重要的是，應該注意到，在上述衝突的情況下，假設發現兩個度為1的輸入節點在 一起提供比發生衝突的度為2的輸出節點更好的得分，則可能允許要執行的合併，而不是 簡單地禁止合併的發生。這使得可以引入更多的多樣性，並在合併中更頻繁地使用度為1 的節點。在已經生成準備要發送的(已改善的)已產生輸出節點後，重編碼模塊RM可以更 新表示已產生輸出節點的度的當前分布和Tanner圖的輸入節點的當前分布的信息，以在 隨後的重編碼期間使用更新後的分布，該信息存儲在存儲裝置中。輸入節點的分布的更新 可以通過為包括在已產生輸出節點中的每一個輸入節點增加一次出現(occurrence)來完 成。
在已產生輸出節點的真實的度與想要的度不同，並且在第二方法步驟期間允許已 產生輸出節點的度下降的情況下，可以保存想要(或期望)產生的度(即，在第一方法步驟 的第一部分期間確定的度)，而不是保存真實產生的度。當試探法足夠精確時，該動作不是 必要的。為了減輕網絡重編碼設備D的任務，適配解碼器DC的經典解碼模塊DDM自適應是 有益的。更具體地，當解碼模塊DDM已經對接收到的LT碼符號進行解碼後，解碼模塊DDM 更新自身的Tanner圖，網絡重編碼設備D使用該Tanner圖來根據輸出和輸入節點各自的 度對該輸出和輸入節點進行搜索。因此，優選地，將解碼器DC的解碼模塊DM修改用於存儲 與解碼模塊DM的Tanner圖中輸入節點和輸出節點各自的度相對應的、對輸入節點和輸出 節點進行定義的數據。例如，為了易於訪問網絡重編碼設備D，可以以索引的形式存儲這些 數據。因此，解碼模塊DM保存索引表，該索引表允許重編碼模塊RM隨機選擇具有特定度的 節點，並且還知道每一度有多少節點呈現在解碼器DC的Tanner圖中。 優選地，根據本發明的修改後的解碼模塊DDM至少部分由軟體模塊組成。然而，它 也可以由電子電路)或硬體模塊組成，或者是硬體和軟體模塊的組合(在這種情況下，它還 包括允許在硬體和軟體模塊之間交互的軟體接口)。在專門由軟體模塊組成的情況下，可將 它存儲在解碼器DC的存儲器中，或在任何可被通信設備CEi讀取的計算機軟體產品，例如 CD-ROM。此外，還可修改解碼器DC，以便能夠檢測節點的冗餘度，並且因此簡化網絡重編碼 設備D的任務。實際上，根據本發明的網絡重編碼方法增大了節點冗餘度，這是因為根據本 發明的網絡重編碼方法傾向於生成更多LT碼符號冗餘塊，這增大了解碼複雜度(計算和空 間兩方面的複雜度)，並降低了(使用解碼器的數據的)網絡重編碼設備D的性能。因此，本發明提出向解碼器DC增加檢測模塊DTM，檢測模塊DTM布置用於在存在 要解碼的輸出節點的情況下，確定解碼模塊DDM是否先前接收到過該輸出節點，並且在肯 定的情況下，產生消息來通過信號通知先前已經對該輸出節點進行了解碼並且不必再次將 其插入解碼器的Tanner圖。重要的是，應該注意到，當接收到輸出節點時可以使用檢測模塊DTM(以確定 該輸出節點先前是否已經被接收到解碼)，或者在解碼期間(例如，在將輸出節點x = a b c d部分解碼以生成另一個輸出節點y = a c d時)使用檢測模塊DTM。在 後一種情形下，檢測器模塊DTM可以檢查y是否已知。例如，檢測模塊DTM可以快速計算針對接收到的輸出節點的密鑰，並查看所存儲 的、具有快速讀和插入訪問的數據結構，例如二叉查找樹(例如，RB樹(「紅黑樹」-一種自 平衡的二叉樹))或散列表。如果可以發現已經插入了另一個密鑰，則檢測模塊DTM可以得 出結論已經接收到同一個輸出節點，並且不需要對其再次解碼。因此，檢測模塊DTM產生 消息，以使得簡單地丟棄接收到的輸出節點，而不是將其插入解碼器DC的Tanner圖中。由於大多數輸出接點具有較低的度(等於2或3)，並且兩個度為2的輸出節點相 同的概率比兩個度為4的輸出節點相同的概率高很多，因此可以抑制對度為1、2或3的輸 出節點的冗餘檢測。在這種情況下，檢測模塊DTM可以實現一種散列方法，該散列方法旨在 針對任何度為1、2或3的輸出節點x計算密鑰h (x)，以使得M力=H^) ^x = x'。該雜散方 法可以如下所示。
首先，檢測模塊DTM可以以遞增的順序(例如，考慮到其標識符)對混合已編碼 符號(或輸出節點)的原始符號進行排序。然後，檢測模塊DTM可以計算密鑰h(x)= Sl+S2 (L+1)+s3 (L+1)2，其中，x = a b c，Sl = ia+l, s3 = ib+l, s2 = i。+l，L 是符號 (或LT碼符號)長度，以及ix是對符號(或輸入節點)x進行標識的整數，取0到L-1之間 的值。如果符號的度為2，簡單地設置s3 = 0，以及如果符號的度為1，則簡單地設置s3 = 0 以及s2 = 0。該散列方法僅要求少量(恆定的)加法和乘法，以計算密鑰h(x)。此外，由於可以 顯示出其長度等於31og2(L+l)，這種計算出的密鑰不要求很多存儲空間。此外，該冗餘檢測 方法伴隨著低成本，例如，針對長度L = 65536的輸出碼，將涉及到通常可由通用處理器提 供的64比特的比較。優選地，根據本發明的檢測模塊DTM至少部分由軟體模塊組成。然而其也可以由 電子電路或硬體模塊組成，或者是硬體和軟體模塊的組合(在這種情況下，它還包括允許 在硬體和軟體模塊之間交互的軟體接口)。在專門由軟體模塊組成的情況下，可以將其存儲 在通信設備CEi的存儲器中(例如，在通信設備CEi的解碼器DC中)，或者在任何可被通信 設備CEi讀取的計算機軟體產品，例如CD-ROM。本發明提供了若干優點，具體為-允許產生低複雜度的網絡碼，-可以在廣泛的應用範圍內使用，這是它允許產生在計算方面比隨機線性網絡碼 (RLNC)更為高效的網絡碼，網絡碼可以使用置信傳播解碼代替高斯消元法，並且從而避免 了使用 Gallois 域(GF(2k))算法。本發明不限於上述僅作為示例的網絡重編碼方法、網絡重編碼設備和解碼器的實 施例，而是包含本領域普通技術人員可以考慮到的在權利要求保護範圍內的所有備選實施 例。
權利要求
一種網絡重編碼方法，用於對要發送到與網絡相連的至少一個通信設備(CE)的已編碼符號進行重編碼，其特徵在於包括以下步驟通過將所選擇的輸入節點和/或具有已知值並被稱為部分解碼節點的輸出節點相合併來對由LT碼符號所定義的輸出節點進行重編碼，以生成定義準備要發送的已產生輸出節點的新LT碼符號，所述LT碼符號表示已編碼符號，並且分別表示對其值已被發現的已解碼符號進行定義的輸入節點之間的XOR布爾操作的結果，所述輸出節點與所述輸入節點在Tanner圖中相連結；其特徵在於，在所述合併步驟期間，通過在所述部分解碼節點之間進行XOR布爾操作來合併所述部分解碼節點；以及，在所述合併步驟期間，通過在已產生輸出節點的度的當前分布的度之中，確定與第一被選參考分布相同的度具有最大差的度來開始，並且這使得能夠生成具有所述第一被選參考分布相同的度的已產生輸出節點，然後通過合併至少一個部分解碼節點來生成具有所述第一被選參考分布相同的度的已產生輸出節點。
2.根據權利要求1所述的方法，其特徵在於，在所述合併步驟中，通過所選試探法確定 一個度，以便能夠生成具有所述度的已產生輸出節點。
3.根據權利要求1和2中任一項所述的方法，其特徵在於，在已生成所述已產生輸出節 點後，將所述輸入節點的當前分布與第二被選參考分布進行比較，以確定 至少一個輸入節 點是否已被過多地用於生成已產生輸出節點，以及在肯定的情況下，如果所述輸入節點允 許在已產生輸出節點與連結到所述已產生輸出節點的輸入節點合併時使已產生輸出節點 的度保持不變，那麼用過少使用的輸入節點來代替所述過多地用於生成所述已產生輸出節 點的輸入節點的至少一個，以歸一化所述輸入節點的所述當前分布。
4.根據權利要求3所述的方法，其特徵在於，將所述已產生輸出節點與包括所述過多 使用的輸入節點、並具有等於2的度的輸出節點進行合併。
5.根據權利要求1至4中任一項所述的方法，其特徵在於，在所述合併步驟中，在已生 成所述準備發送的已產生輸出節點後，對所述已產生輸出節點的度的當前分布和所述輸入 節點的當前分布進行更新。
6.根據權利要求2所述的方法，其特徵在於，在所述合併步驟中，所述試探法在於檢 查要產生的節點的度是否低於或等於包括已解碼輸入節點和具有至少一個相鄰節點的輸 入節點在內的覆蓋的輸入節點的數目。
7.根據權利要求6所述的方法，其特徵在於，所述試探法還在於檢查條件^<f,k-n(k) 是否被驗證，其中，d是所確定的要產生的輸出節點的度，以及n(k)是度為k的部分解碼節 點的數目，k小於已知的d。
8.—種網絡重編碼設備(D)，用於對要發送到與網絡相連的至少一個通信設備(CE)的 已編碼符號進行重編碼，其特徵在於包括重編碼裝置(RM)，配置用於通過將所選擇的輸入 節點和/或具有已知值並被稱為部分解碼節點的輸出節點相合併來對由LT碼符號所定義 的輸出節點進行重編碼，以生成定義準備要發送的已產生輸出節點的新LT碼符號，所述LT 碼表示已編碼符號，並且分別表示對其值已被發現的已解碼符號進行定義的輸入節點之間 的X0R布爾操作的結果，所述輸出節點與所述輸入節點在Tanner圖中相連結；其特徵在於，所述重編碼裝置(RM)布置用於通過在所述部分解碼節點之間進行X0R布爾操作來合併所述部分解碼節點；以及，所述重編碼裝置(RM)布置用於通過在已產生輸出節點的度的當前分布的度之 中，確定與第一被選參考分布相同的度具有最大差的度，並且這使得能夠生成具有所述第 一被選參考分布相同的度的已產生輸出節點，然後通過合併至少一個部分解碼節點來生成 具有所述第一被選參考分布相同的度的已產生輸出節點。
9.根據權利要求8所述的網絡重編碼設備，其特徵在於，所述重編碼裝置(RM)布置用 於應用所選的試探法來確定一個度，以便能夠生成具有所述度的已產生輸出節點。
10.根據權利要求8和9中任一項所述的網絡重編碼設備，其特徵在於，所述重編碼 裝置(RM)布置用於在已生成所述已產生輸出節點後，將所述輸入節點的當前分布與第二 被選參考分布進行比較，以確定至少一個輸入節點是否已被過多地用於生成已產生輸出節 點，以及在肯定的情況下，如果所述輸入節點允許已產生輸出節點與連結到所述已產生輸 出節點的輸入節點時合併時使所述已產生輸出節點的度保持不變，那麼用過少使用的輸入 節點來代替所述過多地用於生成所述已產生輸出節點的輸入節點的至少一個，以歸一化所 述輸入節點的所述當前分布。
11.根據權利要求10所述的網絡重編碼設備，其特徵在於，所述重編碼裝置(RM)布置 用於將所述已產生輸出節點與包括所述過多使用的輸入節點、並具有等於2的度的輸出 節點進行合併。
12.根據權利要求8至11中任一項所述的網絡重編碼設備，其特徵在於，所述重編碼設 備(冊)布置用於在已生成所述準備發送的已產生輸出節點後，對所述已產生輸出節點的 度的當前分布和所述輸入節點的當前分布進行更新。
13.根據權利要求8至12中任一項所述的網絡重編碼設備，其特徵在於，所述重編碼裝 置(RM)布置用於應用試探法，所述試探法在於檢查要產生的節點的度是否低於或等於包 括已解碼輸入節點和具有至少一個相鄰節點的輸入節點在內的覆蓋的輸入節點的數目。
14.根據權利要求13所述的網絡重編碼設備，其特徵在於，所述重編碼裝置(RM)布置用於應用試探法，所述試探法在於檢查條件d^ilW^是否被驗證，其中，d是所確定的要產生的輸出節點的度，以及n(k)是度為k的部分解碼節點的數目，k小於已知的d。
全文摘要
本發明公開了一種網絡重編碼設備(D，)旨在對要發送到與網絡相連的至少一個通信設備(CE1)的已編碼符號進行重編碼。這種網絡重編碼設備(D)包括重編碼裝置(RM)，被布置用於通過將所選擇的輸入節點和/或具有已知值的輸出節點相結合來對由LT碼符號所定義的輸出節點進行重編碼，以生成定義準備要發送的已產生輸出節點的新LT碼符號，該LT碼符號表示已編碼符號，並且分別表示對其值已被發現的已解碼符號進行定義的輸入節點之間的XOR布爾操作的結果，所述輸出節點與所述輸入節點在Tanner圖中相連結。
文檔編號H04L1/00GK101860413SQ20101010502
公開日2010年10月13日 申請日期2010年1月27日 優先權日2009年1月27日
發明者尼克拉·勒斯庫阿內克, 瑪麗-呂克·坎貝爾 申請人:湯姆森許可貿易公司