加快收斂速度之無率碼產生矩陣及連線維度導向解碼排程之設計

Generator matrix design and degree-oriented scheduling for the fast convergence of rateless codes

詹志偉(Chan, chih wei)

指導教授 ： 翁詠祿

國立清華大學/電機資訊學院/電機工程學系/碩士(2012年)

摘要

在盧比變換碼(Luby transform Codes)的編碼過程中，所傳送的編碼位元是使用``隨機式''地連接任意個要傳遞的信息位元。近年來，在以追求得到最佳的的錯誤率效能之下，編碼位元的維度分佈已經被許多研究者做過各種研究、分析，經由數學推導已找出一個在適用於雜訊通道裡一個編碼位元維度分佈。但是在傳統的編碼器產生矩陣中，編碼位元以``任意地"連接信息位元並不能保證能夠讓解碼器有高效率的傳輸信息，反道是有可能地降低了疊代式解碼器的收斂速度。在此篇論文裡，提出了一個新的連線演算法，設計如何在連接傳遞信息位元時做特定的連線調整，以產生能夠更有效率地傳輸通道信息的產生矩陣，重要的是，以上提升整體解碼的收斂速度並不會犧牲錯誤率的表現。此篇論文在解碼端也提出了``連線維度導向解碼排程之設計''的演算法，亦可加快編碼器的收斂速度，並且可以降低疊代式解碼器的疊代次數。除此之外，將此篇論文所提出的新的產生矩陣，合併經由``連線維度導向解碼排程之設計''演算法設計過的解碼器，整體收斂效果更加明顯。此篇論文發現盧比變換碼的解碼收斂速度可以經由各種不同的解碼器被加快收斂，並且會介紹幾種收斂效果較明顯的演算法。最後，在迅龍碼(Raptor Codes)的表現當中，盧比變換碼外加了一個錯誤更正碼，整體錯誤率的提升以及收斂效果會更加明顯。

關鍵字

無率碼 ； 動態解碼排程

並列摘要

In the encoding of Luby transform (LT) codes, information bits (variable
nodes) are randomly connected to the check nodes. Although the check node
degrees have been optimized for error-rate performance, the arbitrary connec-
tions in the code graph cannot guarantee ecient propagation of the channel
information, and may slowdown the convergence speed of the iterative decod-
ing. This thesis proposed a design of generator matrix such that the channel
information can be eciently propagated through the arranged connections.
In addition, the convergence speed for rateless codes can also be accelerated
using a variety of dierent decoders. The proposed degree-oriented schedul-
ing belief propagation (DOS-BP) updates the decoding messages in the order
of check node degrees, and further reduces the required number of iterations.
The improvement in the convergence speed can be achieved without sacri-
cing the error-rate performance. In the case of Raptor codes, the BER
performance can even be improved.

參考文獻

[1] M. Luby, LT codes," in Proc. 43rd Annual IEEE Symp. on Foundations

[2] O. Etesami and A. Shokrollahi, Raptor codes on binary memoryless

symmetric channels," IEEE Trans. Inform. Theory, vol. 52, pp. 2033-

[3] R. Palanki and J. Yedidia, Rateless codes on noisy channels," in Proc.

tor codes over fading cannels," in Proc. of IEEE Global Commun. Conf.