適用於碼率相容低密度奇偶檢查迴旋碼之動態排程

Dynamic Scheduling for Rate-Compatible LDPC Convolutional Codes

蘇詠翔(Yung-Hsiang Su)

指導教授 ： 翁詠祿

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

摘要

在本篇論文，我們於低密度奇偶檢查迴旋碼 (low-density parity-check convolutional codes, LDPC-CCs) 實現無靜態變量節點差值可信度傳遞 (silent variable nodes free residual belief propagation, SVNF-RBP) 動態排程。

相較於標準序列排程而言，動態排程 (Informed dynamic scheduling, IDS) 能夠藉由有效率更新資訊的方式，得到較快的收斂速度和較好的效能表現，這是我們為何選擇使用動態排程的主要原因。在所有動態排程當中我們選擇 SVNF-RBP 作為核心演算法，因為 SNVF-RBP 有一個演算法動作能夠依序指定變量節點，這個特性能夠使 SVNF-RBP 輕易與 LDPC-CCs 結合，且依舊保有平行式疊代解碼的功能。 SVNF-RBP 因為克服貪婪群組與靜態變量節點兩種現象，因此在錯誤率的效能表現與收斂速度皆優於傳統動態排程。此外我們改良 SVNF-RBP，使其能夠在不增加運算複雜度的情況下，提高訊息更新的質量。最終，藉由設計 IEEE 802.16m 穿刺格式，實現增量冗餘形式的混合式自動重送請求。

關鍵字

低密度奇偶檢查碼 ； 低密度奇偶檢查迴旋碼 ； 動態排程 ； 無靜態變量節點差值可信度傳遞

並列摘要

In this thesis, we applied dynamic scheduling of silent variable nodes free residual belief propagation (SVNF-RBP) to low-density parity-check convolutional codes (LDPC-CCs).

Informed dynamic scheduling (IDS) can get higher convergenence speed and better performance by updating message efficiently rather than standard sequential scheduling, this is the main reason why we use IDS. We choose SVNF-RBP to be core algorithm in all types of IDS, because SVNF-RBP has an algorithm behavior which can assign variable node sequentially, this character makes SVNF-RBP combined with LDPC-CCs easily, and makes iteration-parallel decoding of LDPC-CCs still function work. Because SVNF-RBP overcame two phenomenon of greedy group and silent variable nodes, so the performance and the convergenence speed of SVNF-RBP will be better than the performance and the convergenence speed of traditional IDS. Finally, we achieved incremental redundancy (IR) typed hybrid automatic repeat request (HARQ) by designing IEEE 802.16m puccturing pattern.

並列關鍵字

LDPC codes ； LDPC-CC ； dynamic scheduling ； SVNF-RBP ； IEEE 802.16m

參考文獻

[1] R. G. Gallager, “Low-Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. 8, no. 1, pp. 21-28, Jan. 1962.

[3] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electron. Lett., vol. 33, no. 6, pp. 457-458, Jun. 1997.

[4] D. J. C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399-431, Mar. 1999.

[6] A. Morello and V. Mignone, “DVB-S2: The Second Generation Standard for Satellite Broad-band Services,” Proceedings of the IEEE, vol. 94, no. 1, pp. 210-227, Jan. 2006.

[10] A. Jimenez-Felstrom and K. S. Zigangirov, “Time-Varying Periodic Convolutional Codes With Low-Density Parity-Check Matrix,” IEEE Trans. Inf. Theory, vol. 45, no. 9, pp. 2181-2191, Sep. 1999.