一些用於強化樹狀解碼的設計

Designs for Efficient Tree-Search Decoding Algorithms

陳家俊(Chia-Chun Chen)

指導教授 ： 林茂昭

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201903338

摘要

A* 解碼演算法是基於線性區段碼的樹狀結構所設計的軟式解碼演算法，可以非常有效率地針對短碼長的二位元線性區段碼進行解碼。通常會以平均搜索分支數衡量其時間複雜度。在本論文中，我們則使用存放新節點時所花費的平均比較數做為另一項度量 A* 解碼複雜度的方法。

本篇論文的研究方向分為二點。第一點，如何在不犧牲錯誤性能的情況下，降低 A* 解碼演算法所需要的儲存空間(通常稱其為堆疊)，此研究是基於運用最可靠線性獨立符元的統計特性，將最大儲存節點數降低，運用此方法亦可事先計算合適的儲存空間大小。此外，我們改良堆疊的運作模式，進一步降低整體堆疊的大小。第二點，降低 A* 解碼演算法的平均解碼時間。我們利用接收信號的統計特性將一部份的候選碼字排除。在本論文中，我們提出兩種檢查方法，使 A* 解碼演算法能以簡單的判斷方式將一部分的候選碼字排除，以降低 A* 解碼演算法的平均解碼時間。除此之外，我們提出一種判斷標準，讓 A* 解碼演算法能夠提早終止解碼過程，省下後續的解碼時間。

關鍵字

通道編碼 ； 線性區段碼 ； A Star 解碼演算法 ； 軟式短線性區段碼解碼演算法 ； 權重樹狀搜索解碼演算法

並列摘要

A* decoding algorithm is a soft-decision decoding algorithm designing based on the tree-structure of linear block codes. It can efficiently achieve maximum likelihood (ML) detection for short-length binary linear block codes if unlimited storage is assigned. In general, the average number of visited tree edges will be taken as the measurement of its time-complexity. The average number of comparisons while storing an explored binary sequence will be taken as the additional measurement of its time-complexity. In this thesis, the two investigated topics are covered. The first is to reduce the required size of storage. We apply the statistical property of the most reliable and linearly independent position (MRIP) symbols to make A* decoding algorithm use smaller storage without sacrificing error performance. The second is to reduce its time-complexity. Similarly, we exploit the statistical property of received symbols to design deleting mechanisms for eliminating a part of undesired codewords. Besides, we propose an early termination approach to cut down the executing time of A* decoding algorithm.

並列關鍵字

Channel Codes ； Linear Block Codes ； A Star Decoding Algorithm ； Soft-Decision Decoding Algorithm For Short Linear Block Codes ； Priority Tree-Search Decoding Algorithm

參考文獻

[1] C. E. Shannon, “A mathematical theory of communication,” Bell system technical journal, vol. 27, no. 3, pp. 379–423, 1948.

[2] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes.,” in Proceedings of ICC’93IEEE International Conference on Communications, vol. 2, pp. 1064–1070, IEEE, 1993.

[3] R. Gallager, “Low-density parity-check codes,” IRE Transactions on information theory, vol. 8, no. 1, pp. 21–28, 1962.

[4] D. Chase, “Class of algorithms for decoding block codes with channel measurement information,” IEEE Transactions on Information theory, vol. 18, no. 1, pp. 170–182, 1972.

[5] M. P. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,” IEEE Transactions on Information Theory, vol. 41, no. 5, pp. 1379–1396, 1995.