基於演化計算之最佳短碼長LT碼效能與度數分布之研究

A Study of Performance and Degree Distribution of Optimal Short-Length LT codes with Aids of Evolution Strategies

刁培倫(Pei-lun Diao)

指導教授 ： 邵家健

國立交通大學/資訊學院/網路工程研究所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.01088

摘要

LT碼設計在長碼長的情況下已經相當良好的分析結果，但是短碼長LT碼設計卻一直沒有很好的分析方法。本研究提出一種以LT碼效能為目標的優化方法來設計短碼長LT碼。
本研究首先定義LT碼的效能參數: overhead, failure ratio 與 failure probability，並利用演化計算找尋效能參數達到最佳化的LT碼，進而研究不同的最佳化效能參數組合對於LT碼的行為以及階數分布(degree distribution)的影響。

關鍵字

無率碼 ； 演化計算

並列摘要

There are already very good analytical results for designing long-length LT codes. However, there is still a lack of analytical methods for short-length cases. In this thesis, we propose an optimization method for designing short-length LT codes by optimizing their performance.
First of all, we define the performance parameters of LT codes, that is, overhead, failure ratio and failure probability. After that, we use evolution strategies to find degree distributions that are optimal in terms of these three parameters. Finally, we report how optimized parameters affect the performance and degree distributions of optimized LT codes.

並列關鍵字

Rateless codes ； Evolution Strategy

參考文獻

[1] M.Luby, "LT Codes", The 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 271-280, Vancouver, BC, Canada, November 2002.

[5] Chih-Ming Chen, Ying-ping Chen, Tzu-Ching Shen and John K. Zao, “On the Optimization of Degree Distributions in LT Code with Covariance Matrix Adaptation Evolution Strategy”, IEEE Congress on Evolutionary Computation, pp.1-8, Barcelona, Spain, July 2010

[2] Amin Shokrollahi, “Raptor Codes”, IEEE Transactions on Information Theory, Volume 52, Issue 6, pp. 2551-2567, June 2006.

[3] Richard Karp, Michael Luby, Amin Shokrollahi, “Finite length analysis of LT codes”, International Symposium on Information Theory, p. 39, Berkeley, Chicago, USA, June 2004.

[4] Esa Hyyti, Tuomas Tirronen, Jorma Virtamo, “Optimizing the Degree Distribution of LT Codes with an Importance Sampling Approach”, 6th International Workshop on Rare Event Simulation, October 2006.