一種適用於低密度奇偶校驗碼解碼之創新尋找近似最小值的方法及其在穿刺渦輪低密度奇偶校驗碼上之應用

Abstract

最小值-總和演算(Min-Sum Algorithm)因為其低複雜度且具有一定的位元錯誤率(bit error rate)效能，被廣泛應用在低密度奇偶校驗碼(low-density parity-check code, LDPC code)解碼演算法中。但其仍需要大量的比較運算來尋找最小的對數概似比值(Log-Likelihood Ratio)。為了更進一步降低解碼器的複雜度，我們提出了一種尋找近似最小值的方法，其中運用了一種新的資料表示方式轉換和後續的處理動作，藉此我們可以找到近似的最小值且不需要任何的比較運算，也因此可以大幅減少最小值-總和演算法的運算複雜度。雖然在某些情況下此方法找不出最小值，但當其運用於常態化最小值-總和演算法(normalized Min-Sum algorithm)中，模擬的結果顯示其位元錯誤率效能十分接近於原本未使用本方式的效能。

渦輪碼(turbo codes)與低密度奇偶校驗碼同為現今效能最佳的兩種通道編碼技術，使用低密度奇偶校驗碼作為區塊渦輪碼(block turbo code)中的組成碼，渦輪低密度奇偶校驗碼(Turbo-LDPC code)結合了渦輪碼與低密度奇偶校驗碼的優點，運用渦輪解碼的概念以及低密度奇偶校驗碼解碼演算法來完成解碼動作，解碼效能也因此顯著增加，同時其解碼器的主要部分與傳統的低密度奇偶校驗碼解碼器相同，為一種有效率的新式編解碼技術。但為了解決外部信(extrinsic information)傳播失真，需要使用外部信息常態化(extrinsic information normalization, EIN) 也因此提高了解碼複雜度。

本論文的第二部分提出了一種穿刺渦輪低密度奇偶校驗碼(punctured Turbo-LDPC code), 解由移除check on check奇偶校驗位元可有效減低原本的編碼及解碼複雜度，且具有較高的碼率(code rate)。在不使用外部訊息常態化的情況下，相較於原本的渦輪低密度奇偶校驗碼有較佳的錯誤位元率表現。

最後，為了進一步降低解碼複雜度，我們將所提出的尋找近似最小值方法應用到穿刺渦輪低密度奇偶校驗碼中。模擬結果顯示，在選擇合適的量化方式下，其高信噪比區域錯誤位元率效能十分接近於原本未採用近似最小值方法時的效能。結合所提出的這兩種方法，提供了我們一種強大且具一定複雜度的錯誤更正編解碼方案。

Min-sum (MS) algorithm is one of most popular LDPC decoding algorithms used in real applications due to its low complexity and reasonably well BER performance. Still, it requires a lot of comparison operations to find the minimum LLR value. To reduce the complexity further, the proposed approximate minimum values finding scheme adopts a novel data conversion scheme and a sequence of associated operations to find the minimum value without any comparison operation. As such, the computational complexity can be significantly reduced. Although the proposed method cannot find the exact minimum value in some cases, simulation result show that it is accurate enough to generate good BER performance which is very close to conventional normalized Min-Sum algorithm.

Turbo-LDPC code, which combines the merits of both the turbo code and LDPC code is an efficient coding scheme. It applies the LDPC codes to the block turbo coding scheme, that is, it decodes codewords with turbo decoding concept by using LDPC decoding algorithms. The decoding performance is significantly improved by utilizing turbo decoding process, while the major part of the decoder is basically the same as a conventional LDPC decoder. To reduce the problem of belief propagation distortion of extrinsic information after message interleaving, an extrinsic information normalization (EIN) process is required which causes high decoding complexity.

The second part of this work aims at inventing a new punctured Turbo-LDPC coding scheme which can achieve better decoding performance than the original Turbo-LDPC codes in the condition of without applying the EIN process. By removing the check on check bit of the original Turbo-LDPC codeword, both the encoding and decoding computational complexity can be reduced. By combining with the Normalized Min-Sum algorithm (NMSA), the proposed punctured Turbo-LDPC code also has much better decoding performance than combined block turbo code and BCH codes under the same decoding computational complexities without the aid of EIN process.

Finally, we apply the proposed approximate minimum finding scheme to the punctured Turbo-LDPC code for further reducing the decoding complexity. Simulation result shows that the BER performance is nearly the same in high SNR region if we use proper quantization scheme. This shows feasibility to build powerful and practical error correct coding scheme by combining this two proposed techniques.