具分式校驗矩陣之低密度校驗迴旋碼及其相關解碼演算法

A Study on LDPC-CC with Rational Parity-Check Metrices and Related Decoding Algorithms

賴志傑(Chih-Chieh Lai)

指導教授 ： 王忠炫

國立交通大學/電機學院/電信工程系所/碩士(2009年)

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

摘要

低密度校驗碼(LDPC)是近幾年來最為人所熟知的靠近通道容量的編碼。低密度校驗螺旋碼(LDPC-CC)則為結合低密度校驗碼與螺旋碼的特性，具有低密度的非零位置在校驗矩陣中，同時尤於螺旋碼的結構而能被編碼成任意的長度，卻只需要一個解碼器即可進行解碼的動作。除此之外，解碼器在經過一開始的延遲時間後就能連續地輸出解碼後的資料。由於以上的特色，使得在可能更改資料框架的大小以及即時作業的系統中，低密度校驗迴旋碼比起低密度校驗方塊碼來得更合適。因此本碩士論文即從兩方面討論低密度校驗迴旋碼的解碼特。一為提供一新觀點來針對具分式校驗矩陣之低密度校驗迴旋碼做解碼的動作，二為提出針對低密度校驗迴旋碼之位翻轉解碼演算法的改善。
目前，具有良好更正能力的低密度校驗迴旋碼多為利用代數結構所建造出來的，而常被廣泛使用的則是利用半循環式低密度校驗碼來建構出低密度校驗迴旋碼。但是其對校驗矩陣的限制是每個元素必須是零或單項式或是二項式。若有一元素為三次多項式，則代表該碼Tanner
graph的最短周長小於等於六。這代表著在利用疊代信息傳遞解碼演算法進行解碼時容易造成信息相關性過大而使得編碼增益大幅降低。在本篇論文中，我們用新的觀點來針對具分式校驗矩陣之低密度校驗迴旋碼做解碼的動作，經由改良過的Tanner graph建造過程，我們避免了最短周長為四的情況。在模擬結果中，更表述了我們的方法能使得以往認為較差編碼增益的低密度校驗迴旋碼具有良好的編碼增益。於此同時，我們產生與具有良好編碼增益的低密度校驗迴旋碼之校驗矩陣的等價分式校驗矩陣，再經由我們所提出的方法進行解碼，所得的編碼增益媲美與原先的解碼結果。
另一方面，我們亦針對低密度校驗迴旋碼提出改善之位翻轉解碼演算法。在前人的研究中，針對低密度校驗迴旋碼之解碼器裡的每一個處理器提出了翻轉閾值的設定。此設定的模擬結果比Gallager提出的位翻轉解碼演算法有較佳的增益。但是事先設定閾值讓處理器不能對解碼過程的真實情況做出對應的改變。因此我們提出了動態提高閾值的解碼演算法，每個處理器只有在必要時候才會提高閾值以做為因應。模擬結果更告訴了我們所提出的改善方法能更有效率的偵錯，並獲得更佳的編碼增益。

關鍵字

低密度 ； 迴旋碼 ； 分式 ； 解碼 ； 演算法

並列摘要

Low-density parity-check convolutional codes (LDPC-CC) are convolutional codes with low-density of ones in the scalar form of parity-check matrices. They have good features that do not exist in LDPC block codes such as they can be encoded with arbitrary length by simple shift registers, and can be decode by only one decoder. On the other hand, a decoder for LDPC block code can only decode codewords with xed length. Besides, the decoder pops out the decoded outputs continuously, and makes LDPC-CC more adequate to real time operating systems than LDPC block codes. In this thesis, we discuss the decoding algorithms for LDPC-CC in two perspectives. First, we propose a new perspective for
decoding LDPC-CC with rational parity-check matrices. Second, we present an improved bit-fipping decoding algorithm for LDPC-CC. Recently, good performance LDPC-CC are constructed from quasi-cyclic LDPC (QCLDPC) codes. There are zeros, monomial or binomial in the parity-check matrices of those LDPC-CC. In this thesis, we discuss the possibility that LDPC-CC with rational paritycheck matrices can still have good bit error rate (BER) performance. We propose a new perspective of constructing Tanner graph to represent the rational in parity-check matrix. There are no cycles of length 4, and the iterative message passing algorithm can be free from high dependence in the examples. The simulation results show that the BER performance is
better than that of previous perspective for decoding LDPC-CC with rational parity-check matrices about 1 dB improvement and 1 dB away from maximum likelihood (ML) decoding results in the cases of LDPC-CC with small memory. In the cases of LDPC-CC with large memory, our simulation results show about 0.7 dB improvement. We also generate rational parity-check matrices equivalent to the monomial parity-check matrices constructed from QC-LDPC. The simulation results show that there are no dierence between two BER peformance.
In addition to the decoding for LDPC-CC with rational parity-check matrices, we also discuss the hard decision decoding for LDPC-CC. In many applications such as the communication in flash memory, the power consumption and the volume of the system are the most important concern, and a simplied decoding algorithm for LDPC codes is needed. Bit-flipping algorithms are good choices because they provide decoded results very quickly by utilizing hard decisions of received sequence. There is much research on modied bit-flipping algorithms for dierent type of LDPC block codes but few discussion about LDPC-CC. Unluckily,
the bit-flipping algorithm for LDPC block codes are not well suitable for decoding LDPC-CC due to the nature of the decoders for LDPC-CC. Therefore, we propose a modified bit-
ipping algorithm for decoding LDPC-CC in this thesis. The simulation results show that the BER performance is better than previous work about 2 dB improvement in many cases.

並列關鍵字

LDPC ； convolutional ； rational ； decoding

參考文獻

[1] R. G. Gallager, Low-Density Parity-Check Codes," IRE Trans. on Inform. Theory,vol. 8, pp. 21-28, Jan. 1962.

[2] Marc P. C. Fossorier, Quasi-Cyclic Low-Density Parity-Check Codes From Circulant

[3] R. Smarandache and P. O. Vontobel, On Regular Quasi-Cyclic LDPC Codes from

[4] S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications,

[6] A. Sridharan, Design and Analysis of LDPC Convolutional Codes," Ph.D. Dissertation,