網路編碼迷蝴蝶
來自香江的一個小故事，戲劇性地在通訊界掀起一股全球熱潮。
撰文/ 李碩彥（Shuo-Yen Robert Li）
翻譯/ 涂可欣
通訊是個古老的行業。一封郵件常常要經過好幾個郵局中轉，每一個中轉站所做的事就是
「儲存轉發」（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點
，那麼就只能先轉發兩個信號其中一個，再轉發另一個。但是如此一來，就需要用兩倍的
時間來完成通訊，也就是說信號的「傳輸率」降低了一半。這更意味網路編碼比儲存轉發有
優越之處，雖然幾千年來用的都是後者。
本圖中的xy信號，既不是x也不是y，而是兩者間一種數學運算的結果。它雖然簡單，卻也
是一種「編碼」的形式。事實上，xy是所謂的「二進位和」（binary sum），它不僅代表一
種編碼形式，也是數學上的「線性」編碼形式。線性編碼的數學基礎非常深厚，所以比「非
線性」編碼容易實現，因此也比較實用。
當兩條或多條信號傳輸的路徑局部重疊時，用編碼來提高信號傳輸率的技術可稱為「共路
徑編碼」。幾十年來，這技術被零零星星地用在各種通信網路，其中也包括一些我早期的研
究。蝴蝶網是共路徑編碼之一例，有時多條路徑重疊的部份僅在由起點出發的第一步，另外
的圖就是一例，圖中x和y兩個信號都從A點向B、C、D三點傳遞。
日思夜夢究真理
回想起來，網路編碼的起源充滿了戲劇性。
1997年中，我開始沉浸於寫作一本名為《代數交換論及其寬頻應用》（Algebraic Switchi
ng Theory and Broadband Applications）的書。我在這領域15年的研究成果幾乎都沒有
寫成論文來發表，只想用兩、三年的時間彙集成一本書，難度可不低，因此需要長期閉關修
行。當時每個夜晚都會醒來數次，黑暗中寫下夢裡得到的關鍵字句或理念，翌日早晨再將橫
豎潦草的字跡整理出來。
那年夏季，我在香港中文大學的同事楊偉豪應德國俾勒菲特大學的阿斯威第之邀，出訪該
校，並結識了蔡寧。楊偉豪曾與美國南加州大學的張珍共同研究過衛星通訊網的信號編碼，
用到了56頁圖中的共路徑編碼技術。旅德期間，他與蔡寧一起研究共路徑編碼的信號傳輸率
。楊偉豪9月返回香港中文大學，並拿了另外的圖的例子給我看。
不久之後，楊偉豪與蔡寧合擬了一篇初稿，從「資訊理論」（information theory）的觀
點來闡明該圖的理論根基，並找我評論。當時我想專心寫書，所以只想快點應付過去。結果
我發現文中某一個定理是錯的，我用很抽象的話對楊偉豪解釋為什麼那是一個錯誤，雖然這
個解釋對我自己而言可能都太抽象了。
楊偉豪沒聽懂我的解釋，依然認定那個定理沒有錯，所以再三找我討論。他要我乾脆給出
一個反例來徹底推翻那個定理，或者明確指出其數學證明錯在哪裡。為了避免細讀那個證明
，我只好試著做前者。當時我拿起筆在白板上畫起來，福至心靈，畫出了恰好構成反例的「
蝴蝶網」。楊偉豪看了略有感觸，將蝴蝶網也畫在他自己辦公室的白板上，同時又做成「標
本」，掛上另一幅牆。
麻煩才剛開始。每日望著白板上的蝴蝶網，我深深相信，不論蝴蝶網背後的理論基礎是什
麼，它都會是解釋這理論的最好圖例。此外，我已對楊偉豪宣稱：蝴蝶網背後的基本原理一
定是很簡單的「線性代數」。於是我撇開寫書，日夜思索到了11月，寫出一份數學初稿，將
它交給楊偉豪。封面上有我的自白：「這項工作並沒有我頭一百回想像得那麼簡單。」
【更多網路編碼運作和好處應用~~請見科學人雜誌2007年7月號第65期】