資訊科技

網路編碼迷蝴蝶

來自香江的一個小故事,戲劇性地在通訊界掀起一股全球熱潮。

撰文/李碩彥(Shuo-Yen Robert Li)

資訊科技

網路編碼迷蝴蝶

來自香江的一個小故事,戲劇性地在通訊界掀起一股全球熱潮。

撰文/李碩彥(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點,那麼圖形就更像蝴蝶了。

網路編碼最簡單的概念來自「蝴蝶網」。每個箭頭表示傳送一個訊號,信號值是0或1。兩個信號x和y都要從A點傳到B點和C點。此時網路編碼可提升其傳輸效率



網路烽煙今古似

事實上,如果蝴蝶網中的M點一定要用儲存轉發的方式,把x和y兩個信號都傳遞到B點和C點,那麼就只能先轉發兩個信號其中一個,再轉發另一個。但是如此一來,就需要用兩倍的時間來完成通訊,也就是說信號的「傳輸率」降低了一半。這更意味網路編碼比儲存轉發有優越之處,雖然幾千年來用的都是後者。

圖中的x⊕y信號,既不是x也不是y,而是兩者間一種數學運算的結果。它雖然簡單,卻也是一種「編碼」的形式。事實上,x⊕y是所謂的「二進位和」(binary sum),它不僅代表一種編碼形式,也是數學上的「線性」編碼形式。線性編碼的數學基礎非常深厚,所以比「非線性」編碼容易實現,因此也比較實用。

當兩條或多條信號傳輸的路徑局部重疊時,用編碼來提高信號傳輸率的技術可稱為「共路徑編碼」。幾十年來,這技術被零零星星地用在各種通信網路,其中也包括一些我早期的研究。蝴蝶網是共路徑編碼之一例,有時多條路徑重疊的部份僅在由起點出發的第一步。



更多相關文章

2017年8月186期科學養腦 失智展曙光 雜誌訂閱

本期最新文章