改善短長度LT碼連線數機率分布之研究

Abstract

本論文提出非普適性(Nonuniveral) 及普適性(Universal) 兩類方法，改善短長度LT 碼的表現，並應用於多媒體通訊。基本概念在於增加單一連線字符(Degree One Symbol)的平均數量，避免置信傳播(Belief-Propagation，BP) 解碼過程過早中斷。我們首先介紹非普適性方法，包含奠基於索靈頓的連線數機率分佈以及有限隨機性編碼法。接著分析普適性方法，並將重點放在，如何根據解碼過程中，單一連線字符的平均數量來建立連線數機率分佈。 LT 碼已經被證明，在抹除通道(Erasure Channel) 上可達到通道容量，這一類型的通道編碼表現，主要取決於碼長以及連線數機率分佈的設計。目前最廣泛使用的健全索靈頓分佈(Robust Soliton Distribution，RSD)，是針對無限碼長作最佳化設計，並廣泛使用於通訊系統中。然而當碼長逐漸降低時，LT 碼結合健全索靈頓分佈的表現也隨之變差，因為單一連線字符的數量，變得更容易在解碼初期降到零，導致解碼過程經常過早中止。因此，健全索靈頓分佈不適合應用在多媒體通訊中，傳輸資料量小或分割後的檔案，例如音樂檔案、圖像群組（Group of Pictures，GOP）、等等。 在本論文所提出的Nonuniveral 方法中，我們提高單一連線字符在健全索靈頓分佈中的比例，避免解碼過程過早中止。而低連線字符的比例也被降低，使接收端收到冗餘字符的機率減少。我們還提出非重複性(Non-Repetitive，NR) 編碼方法，旨在減少重複的單一連線字符的產生。但是非重複性編碼方法限制了編碼的隨機性，LT 碼的表現因此跟通道狀況產生關聯性，所以此編碼方法為非普適性。此外，我們結合數個非重複性編碼器，來達到非均等抹除保護(Unequal Erasure Protection)，給予可適性視訊編碼(Scalable Video Coding) 中，不同重要性的層級相對應的保護。實驗結果顯示，跟過去的研究比較，我們所提出的非均等抹除保護方法，在峰值信噪比(Peak Signal-to-NoiseRatio，PSNR) 上有較好的表現。 在普適性方法中，我們用所提出的連線數機率分佈取代健全索靈頓分佈，同時保持隨機編碼過程不變，以維持LT 碼的表現與通道狀況相互獨立。在給定限制條件下，藉由最小化目標函數，可得到相對應的連線數機率分佈，使其單一連線字符的平均數量，近似於事先決定的曲線，並使用序列二次規劃法(Sequential Quadratic Programming)，尋找最小化問題的解。跟健全索靈頓分佈及過去的研究比較，我們所提出的連線數機率分佈，降低編解碼複雜度和完全解碼所需的字符平均數量。此外，我們在模擬中，使用基於802.11g WLAN 的用戶數據報協議（User Datagram Protocol，UDP）封包丟失紀錄。相對應的結果顯示，跟健全索靈頓分佈比較，我們所提出的連線數機率分佈達到更高的傳輸效率，並分別降低至少31.2% 和25.4% 的編碼和解碼複雜度。

This dissertation presents both nonuniversal and universal approaches that improve the performance of short-length Luby Transform (LT) codes with applications to multimedia communication. The key idea is to increase the expected output ripple size to prevent Belief-Propagation (BP) decoding process from terminating prematurely. The nonuniversal approach with Soliton-based distribution and randomness-limited encoding scheme is discussed first. Then the universal approach is investigated focusing on constructing degree distributions with respect to the output ripple size. LT codes have been proved to be capacity-achieving on erasure channels. The performance of these codes is dominated by the code length and the design of the degree distribution. The state of the art robust Soliton distribution (RSD) is designed for asymptotic optimality and widely used in communication systems. As the code length decreases, however, the performance of LT codes using RSD degrades. This is because the output ripple size becomes smaller and more likely to decrease to zero during early stage, leading to frequent premature decoding termination. As a result, RSD is unsuitable for multimedia communication, which typically involves transmission of small or segmented data, such as music files and Group of Pictures (GOP) in a coded video. In the nonuniversal approach, we increase the degree-1 proportion in RSD. The output ripple size becomes larger accordingly, and the problem of premature decoding termination is then relieved. The proportion of low degrees, except for degree-1, is also decreased to reduce the number of redundant output symbols. In addition, we introduce Non- Repetitive (NR) encoding scheme to avoid generating repeated degree-1 output symbols. NR encoding scheme limits the randomness of the encoding process so that its performance depends on the channel condition. Moreover, we integrate multiple NR encoders to achieve Unequal Erasure Protection (UEP) for Scalable Video Coding (SVC) layers with different importance. Experimental results show that our UEP scheme outperforms previous studies in terms of the Peak Signal-to-Noise Ratio (PSNR). In the universal approach, RSD is replaced by our proposed distributions. Meanwhile, we keep the encoding process intact to maintain the universality of LT codes. By minimizing objective functions under certain constraints, degree distributions can be constructed with their expected output ripple size approximating predetermined curves. Sequential Quadratic Programming (SQP) algorithm is employed to solve the minimization problem. Compared to RSD and previous works, our proposed ripple-based distribution (RBD) is able to reduce the average overhead needed to fully decode input symbols as well as the encoding and decoding complexity. Moreover, we record User Datagram Protocol (UDP) packet loss patterns over 802.11g WLAN and apply them to our simulations. The corresponding results show that the transmission efficiency can be improved by using RBD instead of RSD. Compared to RSD, RBD reduces the encoding and decoding complexity by at least 31.2% and 25.4%, respectively.