[發明專利]用于對已編碼符號進行重編碼的網絡重編碼方法和設備

有效

• 申請號: 201010105023.0
• 申請日: 2010-01-27
• 公開（公告）號: CN101860413A
• 公開（公告）日: 2010-10-13
• 發明（設計）人: 尼克拉·勒斯庫阿內克;瑪麗-呂克·坎貝爾
• 申請（專利權）人: 湯姆森許可貿易公司
• 主分類號: H04L1/00
• 分類號: H04L1/00
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 王波波

技術領域

本發明涉及符號數據處理，以及更具體地，涉及對接收到的已編碼符號進行解碼，并對要發送到與網絡相連的通信設備的符號數據進行編碼。

這里，“符號”指的是數據塊或數據分組。

背景技術

如本領域技術人員所知，數據在通信設備之間進行傳輸期間可能發生丟失或損壞。在這種情況下，接收機可以要求發送方再次發送丟失或損壞的數據，或者可以在一開始就發送兩份數據。另一種解決方案是通過碼，并且更具體地通過容錯碼，來對要發送的數據進行編碼。在這種情況下，不必等到已接收到內容的每一個數據便能夠對其解碼，這是因為只需要這些內容的(足夠的)一部分來重建發送方所發送的所有數據。

在編碼方法之中，被稱為“網絡編碼”的方法提供了若干優勢。這種編碼方法是由Rudolf?Ahlswede等人在“Network?informationflow”，IEEE?Transactions?On?Information?Theory?2000中提出的。例如，這種編碼方法可用在無線和/或互聯網網絡中。網絡編碼允許網絡的內部(或中間)路由器在接收到數據a和b時發送c＝f(a，b)類型的數據組合，而不是僅轉發接收到的數據a或b。因此，網絡編碼使得可以在網絡上達到最大流量，而路由則不夠強大以至于無法在一些網絡中達到最大流量。然而，這要求路由器能夠在發送接收到的數據之前，對接收到的數據進行計算，以對其進行編碼，以及最終的接收機能夠對其接收到的已編碼數據進行解碼。

由于已經證明了計算可以達到最大流量的函數f()的集合是NP-Hard的，已經提出了一些概率統計方案。

例如，T.HO等人已經在“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?relaychannel”Proc.IEEE?International?Symposium?on?Information?Theory，ISIT?2007，24?June?2007，pages?666-670中提出了另一種方案。

發明內容

因此，本發明的目的是提出一種使用被稱為Luby?Transform碼(或LT碼)的無比率碼的網絡重編碼方法和設備，LT碼的結構允許使用低復雜度的編碼器和解碼器。