臺灣博碩士論文加值系統

網路編碼應用於無線網路的傳輸上，可以提高其傳輸效率，並且增加傳輸的可靠度。在無線網路的傳輸中，可利用網路編碼的方法，在中間的節點將封包編碼組合，然後廣播給鄰近的節點。透由這樣的方式，訊息的交換會更有效率。
基本上將網路編碼應用於無線傳輸，可以區分成兩種不同的方式。第一種是解碼前送的方法 (Decode-and-Forward, DF)，即節點先將所有接收的訊息解出，然後再編碼廣播出去。第二種是放大前送的方法 (Amplify-and-Forward, AF)，是應用多路存取通道 (multiple access channel) 的特性，直接接收在通道上干擾相加的合成訊號，不透過解碼，直接將訊號放大轉送給鄰近的節點，由鄰近的節點自行解碼。在高訊雜比的情況下，這樣可以達到更高的傳送效率。
在本論文中，我們結合了放大前送和錯誤更正碼的技術，利用錯誤更正碼的特性，降低封包錯誤的機率，以減少重傳次數，從而達到更好的傳輸效率。我們也針對錯誤檢測及錯誤更正做進一步討論，並將兩者合併設計。透由理論和數值的分析，我們驗證了合併設計的好處。我們也比較和分析在不同的訊雜比情況下，各種系統的性能表現，由分析的結果可以得到，我們所提出的方法，在中間區段的訊雜比情況下，可以得到更好的傳輸效率。

It is well known that network coding can be used in wireless transmission to increase the network throughput and robustness. The intermediate node receives messages from its neighbors and then encodes the messages before it broadcasts them to neighbors. By such a way, messages can be exchanged with more efficiency.
Basically, there are two kinds of methods to apply the network coding techniques. The first is called Decode-and-Forward (DF) method, in which the intermediate node decodes the received messages before its encoding process. The second is called Amplify-and-Forward (AF) method, in which the intermediate node doesn’t decode the received messages, in stead, it just amplifies and broadcasts the received summing wave signals. The neighbors should take the duty to decode the messages. In this case, the channel should be a multiple access channel.
In this thesis, we combine the AF method with error correction coding techniques. By using forward error correction code, the packet error rate is reduced, hence the average retransmission times per packet is also reduced and the whole system throughput is increased. We also discuss the issues of packet error detection. Then we propose a new method, which adopts the error correction code with detection and correction capabilities. Through the theoretical analysis and numerical results, it is seen that the proposed methods can further increase the network throughput. Compared with DF and AF methods, our proposed methods can get a higher network throughput at moderate signal-to-noise ratio (SNR).

摘要…………………………………………………………………i
Abstract……………………………………………………………iii
誌謝………………………………………………………………v
目錄………………………………………………………………vi
表目錄……………………………………………………………ix
圖目錄…………………………………………………………x
第一章 緒論………………………………………………………1
1.1 研究動機與目的………………………………………………1
1.2 研究範圍………………………………………………………2
1.3 論文章節概要…………………………………………………3
第二章 網路編碼…………………………………………………5
2.1 代數之簡介…………………………………………………5
2.1.1 群、環、場……………………………………………7
2.2 網路編碼之簡介……………………………………………10
2.3 網路編碼的定義……………………………………………11
2.4 線性網路編碼………………………………………………14
2.4.1 最大流量最小切面定理………………………16
2.5 線性網路編碼之定義與性質………………………………18
第三章 應用無線網路編碼的技術在放大前送之
雙向傳輸上………………24
3.1 簡介…………………………………………………………25
3.2 系統模組……………………………………………………28
3.2.1 DF BAT-relaying……………………………………28
3.2.2 AF BAT-relaying……………………………………29
3.3 BAT-relaying的協定………………………………………30
3.3.1 DF BAT-relaying的傳輸協定……………………32
3.3.2 AF BAT-relaying的傳輸協定……………………36
3.4 分析和數值模擬結果………………………………………37
第四章 利用錯誤更正碼做進一步改善的探討………………41
4.1 簡介…………………………………………………………41
4.2 錯誤更正碼之介紹…………………………………………42
4.2.1 線性區段碼…………………………………………43
4.2.2 錯誤檢測和錯誤更正能力…………………………45
4.3 減少錯誤率的設計方法……………………………………47
4.3.1 設計一僅具更正能力之線性區段碼 (方法1) ……47
4.3.2 設計同時具有更正和檢測能力之線性區段碼
(方法2) ………………49
4.4 方法1、方法2與原始方法的比較…………………………51
4.5 實驗數據比較………………………………………………54
第五章 結論與未來展望………………………………………65
參考資料…………………………………………………………66
作者簡介…………………………………………………………68








表目錄
表 2-1 質數場GF(5) 的運算……………………………………10
表 4-1 BCH碼…………………………………………………55
表 4-2 方法1中各項數據值……………………………………56
表 4-3 方法2中各項數據值……………………………………59


















圖目錄
圖 1.1(a) 解碼前送(decode-and-forward)之技術…………………3
圖 1.1(b) 放大前送(amplify-and-forward)之技術…………………3
圖 2.1 群、環、場三者之關係………………………………………6
圖 2.2 網路廣播傳輸訊號………………………………………14
圖 2.3 表示來源點S添加虛構通道為2的網路架構圖…………15
圖 2.4(a) G的網路型態和通道容量………………………………17
圖 2.4(b)~(e) 最小切面種類…………………………………………17
圖 2.5 線性網路編碼中區域和全域的核心編碼……………20
圖 2.6(a)~(e) 線性網路編碼之種類圖………………………………22
圖 3.1(a) 傳統傳輸方式……………………………………………27
圖 3.1(b) 解碼前送之技術…………………………………………27
圖 3.1(c) 放大前送之技術…………………………………………27
圖 3.2 DF BAT-relaying協定的馬可夫鏈……………………33
圖 3.3 解碼前送和放大前送的傳輸率比較圖…………………40
圖 4.1 簡易的編解碼系統………………………………………43
圖 4.2 簡易線性區段碼之架構…………………………………44
圖 4.3 系統編碼字的構造………………………………………44
圖 4.4 編碼前後的封包大小比較………………………………48
圖 4.5 方法1和方法2設計上的比較……………………………49
圖 4.6 包含CRC的封包大小在編碼前後之比較………………50
圖 4.7(a) 估算：不可檢測機率的上界………………………………51
圖 4.7(b) 細算：不可檢測的錯誤圖樣………………………………51
圖 4.8(a) 時，方法1的傳輸率 與 和 之比較……57
圖 4.8(b) 時，方法1的傳輸率 與 和 之比較………57
圖 4.8(c) 時，方法1的傳輸率 與 和 之比較………58
圖 4.8(d) 方法1的傳輸率 與 和 之比較…………………58
圖 4.9(a) 當 時，比較方法1與方法2的傳輸率……………60
圖 4.9(b) 當 時，比較方法1與方法2的傳輸率……………60
圖 4.9(c) 當 時，比較方法1與方法2的傳輸率……………61
圖 4.9(d) 比較方法1與方法2的傳輸率……………………………61
圖 4.10(a) 當 時，比較方法1、方法2和原始封包之傳輸率…62
圖 4.10(b) 當 時，比較方法1、方法2和原始封包之傳輸率…63
圖 4.10(c) 當 時，比較方法1、方法2和原始封包之傳輸率…63
圖 4.10(d) 比較方法1、方法2和原始封包三種之傳輸率…………64

[1] R.Ahlswede, N.Cai, S.-Y.R.Li, and R.W.Yeung,“ Network information flow, ” IEEE Transactions on Information Theory, vol.46, no.4, pp.1204-1216, July 2000.
[2] R.W.Yeung and Z.Zhangn,“ Distributed Source Coding for Statellite Communications, ” IEEE Transactions on Information Theory, IT-45, pp.1111-1120, 1999.
[3] Raymond.W.Yeung, S.-Y. R. Li, N.Cai and Z.Zhang,“ Network Coding Theory ”.
[4] Y.Wu, P.A.Chou, and S.-Y.Kung,“ Information exchange in wireless networks with network coding and physical-layer broadcast, ” in Proc. 39th Annual Conference on Information Sciences and Systems (CISS) 2005.
[5] P. Larsson, N.Johansson, and K.-E. Sunell,“ Coded bi-directional relaying, ” in Proc. 5th Scandinavian Workshop on Ad Hoc Networks (ADHOC’05) .
[6] P.Larsson, N.Johansson,“ Interference cancellation in wireless relaying networks, ” May 2003 patent WO 2004/102981.
[7] P.Popovski and H.Yomo,“ Bi-directional amplification of throughput in a wireless multihop network, ” in 63th IEEE Vehicular Technology Conference (VTC) 2006.
[8] Shu Lin, Daniel J.Costello,“ Error Control Code ”.
[9] Ren-Der Lin and Wen-Shyen Chen,“Fast Calculation Algorithm of the Undetected Errors Probability of CRC Code,” Proc. 5th International Conference on Advanced Information Networking and Applications (AINA) 2005.
[10] Jorge Castiñeira Moreira, Patrick Guy Farrell, “ Essentials of Error Control Coding ”.
[11] P.Gupta and P.R.Kumar,“ The capacity of wireless networks, ” IEEE Trams. Inform. Theory, vol.46, no.2, pp.388-404, 2000.
[12] Peter Popovski, Member, IEEE, and Hiroyuki Yomo, Member, IEEE,“ Wireless Network Coding by Amplify-and-Forward for Bi-Directional Traffic Flows, ”