現代通訊系統的歷史以令人震驚的洞察力閃現為標誌。
克勞德·E·夏農，數學家和工程師，大約 60 年前發起了一場這樣的革命，他為新的通訊數學理論奠定了基礎——現在被稱為資訊理論。他的工作的實際成果，涉及資料的壓縮和可靠傳輸，今天可以在網際網路、有線和無線電話系統以及儲存裝置（從硬碟驅動器到 CD、DVD 和快閃記憶體盤）中看到。
夏農處理的是專用於個人通話的電話線路上的通訊。如今，資訊越來越多地透過共享網路（如網際網路）傳輸，在共享網路中，多個使用者同時透過相同的媒介進行通訊——無論是電纜、光纖還是無線系統中的空氣。共享網路有可能提高通訊系統的實用性和效率，但它們也造成了對公共資源的競爭。許多人必須爭奪訪問許可權，例如，提供可下載歌曲的伺服器或無線熱點。
支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道： 訂閱。透過購買訂閱，您正在幫助確保有關塑造我們當今世界的發現和想法的具有影響力的故事的未來。
因此，挑戰在於找到使共享順利進行的方法；幼兒的父母會認識到這個問題。網路運營商經常試圖透過增加資源來解決這一挑戰，但這種策略通常是不夠的。例如，銅線、電纜或光纖現在可以為商業和住宅使用者提供高頻寬，但鋪設成本高昂，並且難以修改和擴充套件。超寬頻和多天線傳輸系統可以擴大無線網路服務的客戶數量，但可能仍然無法滿足不斷增長的需求。
因此，也需要提高效率的技術。在網際網路和其他共享網路上，資訊目前由路由器中繼——路由器是在信令路徑或鏈路相交的節點處執行的交換機。路由器將傳入的訊息分流到通往訊息最終目的地的鏈路。但是，如果想要效率，路由器是這些交叉點的最佳裝置嗎？交換甚至是執行的正確操作嗎？
直到七年前，很少有人想到會問這樣的問題。但隨後，德國比勒費爾德大學的魯道夫·阿爾斯韋德，以及當時都在香港中文大學的蔡寧、李碩彥和楊偉豪，發表了開創性的工作，引入了一種在共享網路上分發資訊的新方法。在這種稱為網路編碼的方法中，路由器被編碼器取代，編碼器傳輸關於訊息的證據，而不是傳送訊息本身。當接收器收集證據時，他們會從組裝的線索中推斷出原始資訊。
儘管這種方法聽起來可能違反直覺，但仍在研究中的網路編碼有可能極大地加速和提高各種通訊系統的可靠性，並很可能引發該領域的下一次革命。調查人員當然也在探索提高效率的其他途徑；但據我們所知，這些其他方法通常擴充套件了現有方法。
位元不是汽車
阿爾斯韋德和他的同事部分基於夏農提出的觀點構建了他們的提案，即傳輸關於資料的證據實際上可能比直接傳遞資料更有用。他們還意識到，一旦收集到足夠的線索，接收器就能夠推斷出原始資料，但接收器不需要獲得所有發出的證據。一種線索可以被另一種線索取代，重要的是接收到一些線索的組合，這些線索共同揭示原始訊息。（如果接收器事先被告知用於生成證據的規則，或者如果關於如何使用證據的說明包含在證據本身中，則接收器將能夠理解證據。）
網路編碼打破了經典觀點，即通訊通道類似於道路，而位元就像在這些道路上行駛的汽車。但是，對通訊的交通運輸模型的理解有助於理解新方案的工作原理以及它為何如此有前途。
夏農在數學上證明，每個通道都有一個容量——它在任何給定的時間範圍內可以中繼的資訊量——並且只要不超過通道的容量，通訊就可以可靠地進行。在交通運輸類比中，道路的容量是每秒可以安全處理的汽車數量。如果交通量保持在容量以下，則通常可以保證在一端進入道路的汽車在另一端出口時保持不變（除非發生罕見的事故）。工程師們基於交通運輸模型構建了越來越複雜的通訊系統。例如，夏農思考的電話系統為每次對話分配了一條不同的“道路”；透過傳統電話線的兩個呼叫永遠不會在同一時間和頻率共享一條線路。
計算機網路——尤其是網際網路——本質上是一個合併、分支和交叉道路的迷宮。從一臺計算機傳輸到另一臺計算機的資訊通常會經過多條道路才能到達目的地。來自單個訊息的位元被分組到資料包中（資訊高速公路上的拼車或公共汽車），每個資料包都標有其預定目的地。路由器位於道路的交叉口，檢查每個資料包的標頭，並將該資料包轉發到其目的地。
具有諷刺意味的是，推動當今複雜通訊系統發展的交通運輸模型現在卻阻礙了進步。畢竟，位元不是汽車。當兩輛車在同一座狹窄的橋樑上會合時，它們必須輪流透過瓶頸。但是，當兩個位元到達瓶頸時，可能會有更多選擇——這就是網路編碼的用武之地。
工作原理
框“基本思想”中描述的假設的六節點數字網路可以幫助澄清這些選項。回想一下，在計算機中，所有訊息都採用二進位制程式碼字串的形式。想象一下，此網路中的每個鏈路或道路每秒可以攜帶一位——無論是 0 還是 1——並且僅在相應箭頭指定的方向上攜帶。節點 A 的網路使用者 Amy 希望以每秒一位的速度向節點 D 的 Dana 傳送資訊。與此同時，節點 B 的 Ben 希望以完全相同的速度和速率向節點 C 的 Carl 傳送資訊。Amy 和 Ben 的需求能否同時得到滿足，而不會超過任何鏈路的容量？
在路由器系統中（框中最左側），前景似乎黯淡。從 Amy 到 Dana 以及從 Ben 到 Carl 的兩條路徑都需要穿過鏈路 5。此鏈路成為狹窄的單車道橋樑的等效物。鏈路 5 起始節點 E 處的路由器每秒總共接收兩個位元（來自鏈路 2 的一個位元和來自鏈路 3 的一個位元），但由於鏈路 5 的容量為 1，因此路由器每秒只能沿其傳送一個位元。在交通運輸模型中，此類瓶頸會導致噩夢般的交通擁堵，隨著時間的推移，越來越多的位元堆積起來，等待輪到它們。
但在新方法中（框的右側部分），普通的路由器將被編碼器取代，編碼器將比交通警察有更多選擇。編碼器可以傳送完全不同的資訊，而不是中繼瓶頸處收集的實際位元流。例如，它可以將任何給定秒內到達的 1 的數量相加，如果該總和為偶數，則傳送 0。如果總和為奇數，則裝置可以傳送 1。因此，如果鏈路 5 同時從鏈路 2 和 3 接收到 1 和 0，則它攜帶 1。如果從鏈路 2 和 3 接收到兩個 0 或兩個 1，則鏈路 5 攜帶 0。然後，結果由路由器 F 透過鏈路 6 和 7 分別傳送到 Carl 和 Dana。
這種方法用兩個位元的混合體替換節點 E 處的每對位元。這樣的位元流似乎很荒謬。我們提出的編碼器所做的相當於以一種模糊兩者的方式將一個電話交談與另一個電話交談結合起來。這種方法的明顯荒謬性正是它長期以來未被研究的原因。
但有時明顯的瘋狂是真正的創新。混合比特流可能無法完美地描述任何一種傳輸，但它可以提供關於兩者的證據。假設我們還透過鏈路 1 將 Amy 的訊息傳送給 Carl，並透過鏈路 4 將 Ben 的訊息傳送給 Dana。傳送這兩條訊息使用了路由系統無法有效利用網路資源（鏈路 1 和 4）來滿足 Amy 和 Ben 的需求。Carl 的節點接收到 Amy 的傳輸，並且對於每個時刻（來自鏈路 6），它都知道 Amy 和 Ben 發出的訊息對中 1 的數量是偶數還是奇數。如果 Carl 的節點被程式設計為也“知道”鏈路 5 起始處的編碼器使用的規則，或者如果它可以從證據本身推斷出規則，則收集的證據將使其能夠解密 Ben 傳送的訊息。Dana 的節點也將類似地解開 Amy 的訊息。
明顯的優勢
這種策略實現了交通運輸模型的侷限性所無法想象的兩個目標。首先，它使離開節點的位元能夠同時走兩條路徑，這是汽車無法做到的。其次，它允許到達瓶頸頭部的兩位元流合併成單位元流，而會聚到一條狹窄橋樑上的兩輛汽車不能成為一個實體；一輛汽車必須等待另一輛汽車透過才能繼續過橋。
我們的六節點模型（阿爾斯韋德及其同事在 2000 年首次給出的一個次要變體）所例證的資料處理方法有可能在不需要新增額外管道的情況下增加網路容量，因為它避免了交通堵塞。僅使用路由，我們的六節點網路可以維持平均每秒二分之一位元的併發傳輸。（由於兩個競爭傳輸將不得不共享鏈路 5，因此對於每個競爭需求，有效資料速率將為每兩秒一位，或每秒二分之一位元。）使用網路編碼，同一系統支援每秒一位的併發傳輸。因此，在這裡，網路編碼使容量翻倍。
有時，網路編碼可能會產生更大的容量增益，有時則不會。但這種方法永遠不會降低網路的容量，因為在最壞的情況下，它會精確地模仿路由器系統的操作。它還應該提高相對龐大網路中的可靠性和抗攻擊能力，因為證據的可互換性意味著一些證據資料包可能會丟失而不會造成問題。
來自多播網路的經驗
到目前為止，對實施網路編碼的大部分研究都集中在多播網路上——在多播網路中，所有接收器都需要獲得相同的資訊。網際網路影片遊戲依賴於多播系統，以便在每次有人移動時更新每個玩家。影片或現場體育賽事的網路廣播以及以電子方式釋出給大量客戶的新軟體也透過多播網路傳輸。如今，此類網路仍然使用路由器，而回歸交通運輸類比有助於解釋為什麼設計它們通常非常困難。
想象一下，全國的公路上擠滿了汽車。每個路由器都像一個警察，在單個十字路口指揮交通。駛入的汽車加入到達它們之前的車輛後面的佇列。警官依次讀取每輛汽車的目的地，並將其引導到行駛路線上。系統設計中的目標是讓每個路由器以不僅加快後續每輛汽車到達其預定目的地的速度，而且還允許全國交通運輸系統作為一個整體滿足儘可能多的駕駛員的方式指揮交通。
即使是擁有全國所有道路完整地圖的中央設計師也很難確定每個路由器要遵循的最佳策略。隨著網路隨時間變化，難度會增加：高峰時段、道路維修、事故和體育賽事意味著道路和對道路的需求不斷變化。
直覺可能會認為，設計一個依賴於網路編碼的系統應該更加困難，因為有更多選項需要考慮。節點可以轉發未更改的資料，從而模仿路由器。但它也可能在傳送之前混合兩個或多個傳入資料流，並且如何混合它們也可能需要考慮；此外，不同的節點可能使用不同的演算法。
幸運的是，這種邏輯是有缺陷的。有時新增更多選項實際上會簡化事情。如果沒有編碼，多播系統的架構師將需要列舉從發射器到每個接收器的儘可能多的路徑，然後確定網路可以同時支援多少條路徑。即使對於簡單的網路，查詢和測試所有路徑組合也將是一項令人眼花繚亂的任務。
相比之下，使用網路編碼的多播系統將非常容易設計。令人震驚的事實是，加法和乘法是編碼網路需要應用的唯一數學函式。此外，即使網路中每個編碼器中程式設計的功能或規則是獨立於訊息和其他編碼功能選擇的，並且在沒有任何網路佈局知識的情況下選擇的，整個系統也將以極高的機率以最佳效能執行。即使系統隨時間變化（移動或可重新配置網路中可能會發生這種情況），網路也將繼續以最佳方式執行，而無需重新設計。要了解原因，請參見“程式碼設計示例”。
未來的網路
因此，如果編碼器取代路由器，網路的執行方式將大不相同。我們的訊息遍歷網路的方式將會改變：它們不僅會與其他傳輸共享“道路”，而且可能會與來自各種其他來源的流量緊密糾纏在一起。有些人可能擔心這種糾纏會損害訊息的安全性。然而，更可能的是，遍歷網路的流量將變成區域性無法解密的代數流。網路上的使用者將在不知不覺中相互協作以實現共同利益，不僅允許更高的資料速率或更快的資料下載，而且在無線網路的情況下，還可以提高能源效率。（由於每次無線傳輸都會消耗能量，因此節點可以透過將打算傳送給多個鄰居的資訊混合在一起並僅傳送一次傳輸來減少消耗。）
透過改變網路的功能，網路編碼可能會以我們目前無法想象的方式影響社會。
此外，影片下載延遲和手機通話丟失的情況將大大減少。在網際網路上，路由器會發生故障或被關閉進行維護，並且資料包會一直被丟棄。這就是為什麼人們有時必須重新請求網頁以及為什麼站點有時載入緩慢的原因。可靠性將隨著網路編碼的提高而提高，因為它不需要每一條證據都透過。
網路管理員將在無需新增新通訊通道的情況下提供這些好處，因為現有通道將得到更好的利用。因此，網路編碼將補充其他通訊技術，使使用者能夠儘可能多地從中受益。
有時使用者會知道網路編碼正在執行，因為它可能會修改一些常用應用程式（例如點對點下載）的功能。今天，尋求下載檔案的使用者會在其機器上駐留該檔案的協作使用者中進行搜尋。在使用網路編碼的系統中，檔案將不再以整體或可識別的片段形式儲存。
但是使用者個人不必弄清楚如何找到獲得所需檔案所需的證據。從使用者的計算機或電話傳送到網路中的請求將導致該個人的計算機或本地伺服器在網路中搜尋與感興趣的檔案相關的證據片段。收集到的證據（包括與所需檔案相關的代數混合資訊片段）將有助於恢復該檔案。伺服器或個人計算機不是將拼圖拼在一起，其碎片是整體的可識別片段，而是求解代數方程組。並且，一直以來，大多數人都會對這些操作一無所知——就像我們大多數人都不瞭解我們手機中複雜的糾錯操作一樣。
軍方已經認識到網路編碼的穩健性，目前正在資助對其在移動自組織網路中的應用進行研究，移動自組織網路可以動態形成。此類網路在高度可變的環境中很有價值，例如在戰場上，可靠的通訊至關重要，並且建立和維護光纖電纜或蜂窩塔的基礎設施很困難。在自組織網路中，每個士兵的無線電都成為通訊系統中的一個節點，每個節點都尋找並建立與相鄰節點的連線；這些連線共同建立網路的鏈路。每個節點既可以傳送和接收訊息，也可以充當中間人來傳遞傳送給其他接收器的訊息。此技術將通訊能力擴充套件到遠遠超出單個節點的傳輸範圍。它還具有極大的靈活性，因為網路隨使用者移動，並根據需要不斷重新配置和重新建立連線。
透過改變網路的功能，網路編碼可能會以我們目前無法想象的方式影響社會。與此同時，我們這些研究它的人正在考慮實施的障礙。從我們的基於路由器的系統過渡到網路編碼系統實際上將是較小的障礙之一。這種轉換可以透過逐步更改而不是突然的徹底改革來處理；可以重新程式設計一些路由器，而未構建為執行編碼操作的其他路由器將被逐步替換。
更大的挑戰將是應對超越用編碼器替換路由器的問題。例如，當接收節點將收集足夠的證據以從混合物中恢復其所需內容時，混合資訊是一種好的策略。這種情況始終在多播網路中得到滿足，但在一般情況下可能並非如此。此外，在某些情況下，例如當傳輸多個多播時，混合資訊會使使用者難以或不可能提取正確的輸出。那麼，當多個連線共享同一網路時，節點如何決定哪些資訊可以混合以及哪些資訊不能混合？無線網路中的網路編碼在哪些方面必須不同於其在有線網路中的使用？網路編碼的安全優勢和含義是什麼？當一個人的資料必然與其他使用者的資料混合在一起時，人們將如何為通訊服務付費？在全球範圍內的合作中，我們和其他人正在思考如何解開這些結，同時我們也在努力增強通訊網路的能力，這些網路已成為如此多生活不可或缺的一部分。
更多探索
通訊的數學理論。 C. E. 夏農，載於貝爾系統技術雜誌，第 27 卷，第 379-423 頁和第 623-656 頁；1948 年 7 月和 10 月。可在 http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html 獲取
網路資訊流。 R. 阿爾斯韋德、N. 蔡、S.-Y. R. 李和 R. W. 楊，載於IEEE 資訊理論彙刊，第 46 卷，第 4 期，第 1204-1216 頁；2000 年 7 月。
線性網路編碼。 S.-Y. R. 李、R. W. 楊和 N. 蔡，載於IEEE 資訊理論彙刊，第 49 卷，第 2 期，第 371-381 頁；2003 年 2 月。
網路編碼的代數方法。 R. 科特和 M. 梅達德，載於IEEE/ACM 網路彙刊，第 11 卷，第 5 期，第 782-795 頁；2003 年 10 月。
多播網路程式碼構造的多項式時間演算法。 S. 賈吉、P. 桑德斯、P. A. 周、M. 埃夫羅斯、S. 埃格納、K. 賈恩和 L.M.G.M. 托爾胡伊岑，載於IEEE 資訊理論彙刊，第 51 卷，第 6 期，第 1973-1982 頁；2005 年 6 月。
多播的隨機線性網路編碼方法。 T. 何、M. 梅達德、R. 科特、D. R. 卡格爾、M. 埃夫羅斯、J. 石和 B. 梁，載於IEEE 資訊理論彙刊，第 52 卷，第 10 期，第 4413-4430 頁；2006 年 10 月。