原名：網路編碼迷蝴蝶
來自香江的一個小故事，戲劇性地在通訊界掀起一股全球熱潮。
撰文╱李碩彥
網路編碼迷蝴蝶
來自香江的一個小故事，戲劇性地在通訊界掀起一股全球熱潮。
撰文╱李碩彥（Shuo-Yen Robert Li）
網路編碼最簡單的概念來自「蝴蝶網」。每個箭頭表示傳送一個訊號，信號值是0或1。兩個信號x和y都要從A點傳到B點和C點。此時網路編碼可提升其傳輸效率
通訊是個古老的行業。一封郵件常常要經過好幾個郵局中轉，每一個中轉站所做的事就是「儲存轉發」（store-and-forward）。古今中外，資訊的傳遞方式都採用儲存轉發，也就是信號複製。萬里長城上的烽煙如是，今日的網際網路（Internet）亦然。
複製信號是最自然的通訊方式，但資訊量太大時容易產生網路塞車的麻煩。若以圖中的網路為例，假設每個箭頭表示傳送一個信號，信號值是0或1，由A點發出兩個信號x和y，都要送到B點和C點。困難出現在M點收到x和y之後，它只能轉發一個信號，若轉發x，則B點收不到y，若轉發y，則C點收不到x。這時「網路編碼」提供了一個解決辦法：讓M點送出一個代表x與y之異同的信號，當B點收到此信號與x，即可解出y；同樣地，C點也可解出x。
這張圖，就是表達網路編碼概念最著名的「蝴蝶網」。研究網路編碼的論文，到現在已經累積了數百篇，其中大半一開始都重述一遍蝴蝶網。有些人畫蝴蝶網的時候，會略去A點，那麼圖形就更像蝴蝶了。
網路烽煙今古似
事實上，如果蝴蝶網中的M點一定要用儲存轉發的方式，把x和y兩個信號都傳遞到B點和C點，那麼就只能先轉發兩個信號其中一個，再轉發另一個。但是如此一來，就需要用兩倍的時間來完成通訊，也就是說信號的「傳輸率」降低了一半。這更意味網路編碼比儲存轉發有優越之處，雖然幾千年來用的都是後者。
圖中的x⊕y信號，既不是x也不是y，而是兩者間一種數學運算的結果。它雖然簡單，卻也是一種「編碼」的形式。事實上，x⊕y是所謂的「二進位和」（binary sum），它不僅代表一種編碼形式，也是數學上的「線性」編碼形式。線性編碼的數學基礎非常深厚，所以比「非線性」編碼容易實現，因此也比較實用。
當兩條或多條信號傳輸的路徑局部重疊時，用編碼來提高信號傳輸率的技術可稱為「共路徑編碼」。幾十年來，這技術被零零星星地用在各種通信網路，其中也包括一些我早期的研究。蝴蝶網是共路徑編碼之一例，有時多條路徑重疊的部份僅在由起點出發的第一步。
回想起來，網路編碼的起源充滿了戲劇性。
1997年中，我開始沉浸於寫作一本名為《代數交換論及其寬頻應用》（Algebraic Switching Theory and Broadband Applications）的書。我在這領域15年的研究成果幾乎都沒有寫成論文來發表，只想用兩、三年的時間彙集成一本書，難度可不低，因此需要長期閉關修行。當時每個夜晚都會醒來數次，黑暗中寫下夢裡得到的關鍵字句或理念，翌日早晨再將橫豎潦草的字跡整理出來。
那年夏季，我在香港中文大學的同事楊偉豪應德國俾勒菲特大學的阿斯威第之邀，出訪該校，並結識了蔡寧。楊偉豪曾與美國南加州大學的張珍共同研究過衛星通訊網的信號編碼，用到了共路徑編碼技術。旅德期間，他與蔡寧一起研究共路徑編碼的信號傳輸率。楊偉豪 9月返回香港中文大學，並拿了例子給我看。
不久之後，楊偉豪與蔡寧合擬了一篇初稿，從「資訊理論」（information theory）的觀點來闡明該圖的理論根基，並找我評論。當時我想專心寫書，所以只想快點應付過去。結果我發現文中某一個定理是錯的，我用很抽象的話對楊偉豪解釋為什麼那是一個錯誤，雖然這個解釋對我自己而言可能都太抽象了。
楊偉豪沒聽懂我的解釋，依然認定那個定理沒有錯，所以再三找我討論。他要我乾脆給出一個反例來徹底推翻那個定理，或者明確指出其數學證明錯在哪裡。為了避免細讀那個證明，我只好試著做前者。當時我拿起筆在白板上畫起來，福至心靈，畫出了恰好構成反例的「蝴蝶網」。楊偉豪看了略有感觸，將蝴蝶網也畫在他自己辦公室的白板上，同時又做成「標本」，掛上另一幅牆。
麻煩才剛開始。每日望著白板上的蝴蝶網，我深深相信，不論蝴蝶網背後的理論基礎是什麼，它都會是解釋這理論的最好圖例。此外，我已對楊偉豪宣稱：蝴蝶網背後的基本原理一定是很簡單的「線性代數」。於是我撇開寫書，日夜思索到了11月，寫出一份數學初稿，將它交給楊偉豪。封面上有我的自白：「這項工作並沒有我頭一百回想像得那麼簡單。」
雁歸相見不相識
我以為終於得到了解放，於是很快又沉浸在代數交換論當中。緊接著，麻煩又來了。楊、蔡兩人的初稿是屬於資訊理論的風格，而我的初稿寫的是線性代數，兩種形式格格不入。舉一個例子，我一開始定義「編碼」就要求網路中每一個點都對應到某一個「向量空間」，這樣的定義，在做資訊理論的人眼裡可能是很荒誕的。由於缺乏足夠的時間和精神去將兩種風格融合在一起，我們只好將兩者的基本概念分別發表於1998年的會議論文集當中，這些論文都是以蝴蝶網為起點，不過會議的性質分別屬於數學、運籌學、資訊理論等不同領域。
資訊理論出發的版本在2000年7月發表於電機電子工程師協會（IEEE）的《資訊理論會報》（Transactions on Information Theory），成為「網路編碼」的第一篇正式文獻──雖然當時尚未出現這個名詞。從線性代數出發的版本最終寫成〈線性網路編碼〉一文，是這領域的第二篇正式文獻，但出版時間已經是2003年2月了。之所以拖得這麼久，有兩個原因：第一，投稿期刊的繁瑣工作，幾乎由楊偉豪一手打理，而他從2000年起也開始忙著寫書。第二，跨學科的新領域剛形成時，必須面對多方不認同的現實處境，〈線性網路編碼〉一文曾經因此為期刊所拒。該文後來獲IEEE資訊理論協會 2005年度論文獎，頒獎主席的賀詞正是「恭喜你們開創了新領域」。
這個新領域的影子，幾十年來其實一直隱藏於「共路徑編碼」的零星應用之中。2006年春天，我為了替國際光學工程學會（SPIE）撰寫時事報導，搜索了舊文獻，找到了三篇論文。它們都沒有點出共路徑編碼技術的一般性，而是各自將之用於磁碟陣列（RAID）、多通道網路接入和衛星通訊，其中竟有一篇是我的舊作。半年後，我與楊、蔡三人一同為IEEE資訊理論學會合寫時事短文時，又想起了自己兩篇更早的相關論文。2007年，我又憶起了我有1.5個美國專利也與共路徑編碼相關。如果說有許多其他人也用過共路徑編碼的技術，我也不會驚訝。只不過他們看到網路編碼時，能否聯想起以前的工作，就很難說了。
