使用進化策略演算法及標的編程對短長度盧比抹除更正碼作多目標性能制定之研究

Multi-objective Performance Customization for Short-Length Luby Transform Erasure Correcting Codes using Evolution Strategies and Goal Programming

何納己(Hornansky,Martin)

指導教授 ： 邵家健 ； 王忠炫

國立交通大學/電機學院/電機資訊國際學位學程/博士(2017年)

摘要

短長度Luby變換（SLLT）碼是第一個可實際實現湧泉碼並且隨機確保保護碼，可以提供可靠的數據流服務用於向具有不同損失率的多個端點。 然而，由於不同的應用可能對它們的解碼性能施加不同的需求集合的事實，因此期望相對於這些依賴於應用的需求以及關於受保護的源數據的特性來定制它們。 此外，由於沒有可行的分析方法能夠在它們的塊長度短而大於幾百個符號時推導出這些代碼的解碼性能，所以估計它們的解碼性能的唯一可行的方法是執行大量的Monte - 基於數值模擬。
在本論文中，我們提出一種系統方法來定制這些代碼的解碼性能，使得受保護的位元流可以在寬的頻道損失率範圍內具有最佳的回放品質。 我們的方法從基於三個參數的新的統計解碼性能模型的建議開始：解碼開銷，符號解碼失敗率和符號解碼失敗率的尾部概率。 後演示如何使用他提出了性能模型以指定對解碼性能施加的任何性能目標，我們將SLLT代碼定制制定為多目標優化問題，並且出示如何使用Tchebyccheff目標編程方法將其轉換為單目標的方式。因此，我們展示如何選擇一個合適的優化方法，能夠進行最優解的搜索，在本文的最後部分，我們提供一套規則如何適應所選的方法，以提供魯棒和有效的收斂行為。通過兩個真實世界的SLLT代碼設計場景，即通過以下設計來演示所提出的用於產生具有相對於任何一組性能目標調諧的解碼性能的SLLT代碼的方法的能力和實用性：（1）SLLT後代碼提供對H.264 AVC位元流的擦除保護的短長度猛禽編碼，以及（2）支持H.264 SVC播放質量的適度降級的無比率UEP編碼的SLLT後編碼。
所獲得的結果表明，當使用針對目標程序的提議的統計性能模型來設置解碼性能目標時，所選擇的優化方法能夠有效地收斂到非常好的解決方案。 此外，我們的兩個現實世界設計場景的結果表明，所提出的方法能夠產生具有定制解碼性能的SLLT代碼，使得回放圖片能夠獲得比PSNR值顯著更高的PSNR值（在解碼處理的不同階段） 的在傳統優化代碼保護下恢復的圖像。

關鍵字

Rateless coding ； Luby transform codes ； Performance tuning ； Stochastic optimization ； Evolutionary computation ； Goal programming

並列摘要

Short-length Luby Transform (SLLT) codes, the first practical implementation of the digital fountain codes, are powerful randomized erasure protection codes that can be used to provide reliable data streaming services to multiple endpoints possessing different loss rates. However, due to the fact that different applications may impose on their decoding performance different sets of requirements, it is desirable to customize them with respect to these application-dependent requirements as well as with respect to the characteristics of protected source data. Moreover, since there is no feasible analytical method capable to deduce the decoding performance of these codes when their block length is short while greater than a few hundreds of symbols, the only feasible way to estimate their decoding performance is to execute a large number of Monte-Carlos based numerical simulations.
In this thesis, we present a structured approach capable to customize the decoding performance of the LT codes so that the protected video bitstreams may have the best playback quality over a wide range of channel loss rates. Our thesis begins with the proposal of a new statistical decoding performance model based on three parameters: decoding overhead, symbol decoding failure rate and tail probability of symbol decoding failure rate. After demonstrating how to use the proposed performance model in order to specify any performance objective imposed on the decoding performance, we formulate the SLLT code customization as a multi-objective optimization problem and show a way how to convert it into a single-objective one using the Tchebyccheff goal programming approach. Consequently, we show how to choose a suitable optimization method capable to conduct the search for optimal solution and in the final part of this thesis we provide a set of rules how to adapt the chosen method in order to deliver robust and efficient convergence behavior. The capability and practicability of proposed approach to produce SLLT codes with the decoding performance tuned with respect to any set of performance objectives is demonstrated through two real-world SLLT code design scenarios, namely, through the design of: (1) SLLT post-code of a short-length raptor code that provides erasure protection to H.264 AVC bitstreams, and (2) SLLT post-code of a rateless UEP code that supports graceful degradation of H.264 SVC playback quality.
Obtained empirical results confirm our expectations that chosen optimization method is able to efficiently converge to a set of very good solutions when searching for SLLT codes with decoding performance objectives set using proposed statistical performance model in terms of a goal program. Moreover, the results of our two real-world design scenarios demonstrate that proposed approach is capable of producing SLLT codes with customized decoding performance that enable the playback pictures to attain significantly higher PSNR values (at different stages of the decoding process) than the PSNR values of the pictures recovered under the protection of conventionally optimized codes.

並列關鍵字

無編碼 ； 盧比抹除更正碼 ； 性能調優 ； 隨機優化 ； 進化計算 ； 目標編程

參考文獻

[1] D. Vukobratovic, V. Stankovic, D. Sejdinovic, L. Stankovic, and Z. Xiong, “Scalable Video Multicast Using Expanding Window Fountain Codes,” IEEE Trans. Multimed., vol. 11, no. 6, pp. 1094–1104, Oct. 2009.

[2] H. Zhu and Z. Xie, “Advanced LT codes in satellite data broadcasting system,” 2008 11th IEEE Singapore Int. Conf. Commun. Syst., pp. 1431–1435, Nov. 2008.

[3] A. Oka and L. Lampe, “Data Extraction from Wireless Sensor Networks Using Distributed Fountain Codes,” IEEE Trans. Commun., vol. 57, no. 9, pp. 2607–2618, 2009.

[4] W. Yao, L. Chen, H. Li, and H. Xu, “Research on Fountain Codes in Deep Space Communication,” 2008 Congr. Image Signal Process., pp. 219–224, 2008.

[5] J. Jiao, Q. Zhang, and H. Li, “Design of Concatenated Fountain Code in Deep Space Communication,” no. 60672089, 2009.