臺灣博碩士論文加值系統

近年來，無線廣播通訊系統在多媒體傳輸上開始扮演著重要的角色。廣播系統有著可將相同訊息內容同時傳送給大量用戶的特點，比起單播系統可節省更多頻寬。舉例來說，用於可攜式裝置的行動電視服務如電影、電視影集的下載就很適合由無線廣播通訊網路來傳送。使用湧泉碼(fountain code)來傳送訊息可以產生近乎無限長的編碼，並且不用考慮每一用戶接受端的通道狀況與接收順序，只要每一用戶接收端任意接收一定數量的編碼，就可以將原本的訊息正確解回。因此，將湧泉碼應用於廣播系統中尤其用在抹除通道(erasure channel)下是很有效率的。LT碼(LT code)是湧泉碼的一種，比起傳統的湧泉碼，它有著比較簡單的編碼與解碼之特性，適合用於抹除機率未知之抹除通道下可靠的廣播通訊系統。自動重傳要求排程(ARQ scheduling)通常使用於重傳時，可提高吞吐量(throughput)的效率與可靠度。在本文中，我們首先模擬了LT碼的效能表現，以及LT碼加入自動重傳要求方式的效能表現。我們提出了一個使用增量冗餘符元(Incremental redundancy symbols)的混合自動重傳要求排程(HARQ scheduling)機制，並搭配於LT碼，相結合以使用於抹除通道下的廣播通訊系統。由於在重傳中，增量冗餘符元使用的數量決定了吞吐量的效率，因此我們對於這些增量冗餘符元的使用做了一個適當的排程安排機制。從模擬結果可看出，比起先前的重傳方法，我們提出的排程機制可使增量冗餘符元的使用數量達到最小，因此提高了LT碼於廣播通訊系統下整體的效能。

In the recent years, wireless broadcast communication systems have become an important role for multimedia transmission. Broadcasting are more appropriate transport technologies to cope with high numbers of users consuming simultaneously the same service when compared to unicasting, as there is no limit to how many users can receive the content. For example, mobile TV services for portable devices, as video clips from movies to TV dramas are suitable for wireless broadcast communication networks. Fountain codes can generate a potentially limitless stream of encoded symbols. Regardless of the channel condition and the order of received output symbols, once receivers get enough encoded symbols, they can recover all the source symbols. Therefore, fountain codes are efficient for broadcast systems with the erasure channel particularly. LT codes are a class of fountain codes with the simple encoding and decoding algorithm which provide reliable broadcast communications over erasure channels with unknown erasure probability. The ARQ scheduling is often employed to improve more throughput efficiency and reliability for retransmission. In this thesis, we evaluate the performance of LT codes and those with ARQ schemes. We propose a scheme which uses LT codes and an efficient hybrid ARQ scheduling algorithm with incremental redundancy symbols for broadcast communications over erasure channels. Since the number of incremental redundancy symbols for retransmission determines the throughput efficiency, we make a proper scheduling arrangement on incremental redundancy symbols. Simulation results show that comparing to other known schemes, our proposed scheme is with the least number of incremental redundancy symbols than that of others and therefore achieves better performance.

1 Introduction 1
2 Preliminaries 3
2.1 Erasure channel 3
2.2 Fountain codes 4
2.2.1 Random Linear Fountain codes 5
2.2.2 LT codes 6
2.2.3 Raptor codes 7
3 Review of LT codes 9
3.1 LT codes 9
3.1.1 Encoder 9
3.1.2 Decoder 10
3.1.3 LT process 12
3.1.4 Degree distribution 14
3.2 LT codes and hybrid ARQ 18
4 Proposed LT-code based HARQ scheduling schemes on differ-
ent scenarios 19
4.1 Scenario 1 - Acknowledgement from users with ACK/NACK 20
4.2 Scenario 2 - Acknowledgement from users with the number of unrecovered symbols 21
4.3 Scenario 3 - Acknowledgement from users with the unrecovered symbols 21
5 Simulation results 27
5.1 Decoding failure probability 27
5.1.1 Performance of LT codes 28
5.1.2 Decoding failure probability on scenario 1 31
5.1.3 Decoding failure probability on scenario 2 40
5.1.4 Decoding failure probability on scenario 3 42
5.2 Throughput and Mean delay time 51
5.2.1 Throughput 51
5.2.2 Mean delay time 53
6 Conclusion 55

[1] Michael Luby, ”LT-codes,” in Proceedings of the 43rd Annual IEEE Symposium on the Foundations of Computer Science (STOC), pp. 271-280, 2002.
[2] D. J. C. Mackay, ”Fountain codes,” in IEE Proceedings-Communications, Volume 152, no. 6, December 2005.
[3] D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms. Cambridge University Press, second edition, December 2003.
[4] Amin Shokrollahi, ”Raptor codes,” in IEEE Transactions on Information Theory, vol. 52, pp. 2551-2567, June 2006.
[5] Pasquale Cataldi, Miquel Pedr`os Shatarski, Marco Grangetto, and Enrico Magli, ”Implementation and performance evaluation of LT and Raptor codes for multimedia applications,” in Proceedings of the 2006 International Conference on Intelligent Information Hiding and Multimedia Signal Processing, pp. 263-266, December 2006.
[6] Technical Specification Group Services and System Aspects; Multimedia Broadcast/Multicast Service; Protocols and Codecs, , 3GPP TS 26.346 V7.6.0, December 2007.
[7] Michael Luby, Tiago Gasiba, Thomas Stockhammer, and Mark Watson, ”Reliable Multimedia Download Delivery in Cellular Broadcast Networks,” in IEEE Transactions on Broadcasting, Vol. 53, No. 1, pp. 235-246, March 2007.
[8] Mohammad Nekoui, Nazy Ranjkesh, and Farshad Lahouti, "A Fountain Code Approach towards Priority Encoding Transmission,” Proceedings of 2006 IEEE Information Theory Workshop (ITW’06).
[9] Emina Soijanin, Nedeljko Varnica, and Philip Whiting, Punctured vs Rateless Codes for Hybrid ARQ,”in IEEE Information TheoryWorkshop, pp. 155-159, March 2006.
[10] George D. Papadopoulos, Georgios Koltsidas and Fotini-Niovi Pavlidou, ”Two Hybrid ARQ Algorithms for Reliable Multicast Communications in UMTS Networks,” in IEEE Communications Letters, vol. 10, no.4, April 2006.
[11] Chikara Sasaki, Teruyuki Hasegawa, Osamu Kobayashi, Shigehiro Ano and Toru Hasegawa, ”On Unicast based Recovery for Multicast Content Distribution considering XOR-FEC,” in 2005 Asia-Pacific Conference on
Communications, pp. 1043-1047, October 2005.