臺灣博碩士論文加值系統

許多通道編碼都被證明在碼長夠長的情況下它的錯誤率可以達到向農限制，然而在一些情況下我們只能使用短線性區段碼，另外，軟式解碼相較於硬式由於保存了較多的通道資訊，使得其在錯誤率上有較佳的表現，本篇論文所要探討的A*解碼演算法正是一個應用在短線性區段碼的樹狀結構軟式解碼演算法

然而，為了使得它達到最大似然性能(maximum likelihood performance)，其所需要耗費的解碼複雜度可能是相當龐大的，此外，儲存空間的大小也是個衡量演算法優劣的重要因素。在這篇論文中，我們將許多已知的方法進行適當地調整及整合並將他們應用於A*解碼演算法中，希望能降低錯誤率及其解碼複雜度，我們所應用到的方法包含ordered statistics、path constraint algorithms、adaptive path constraint algorithm、control band check、early stop algorithms、modified Fano metric以及Multi-basis algorithm。

It has been confirmed that the error performances of some channel codes can approach the Shannon limit. However, there are some cases only allowed using short linear block code. On the other hand, soft-decoding algorithm has a better error performance than the hard-decoding algorithm because it reserves more channel information. The decoding algorithm discussed in this thesis, A* decoding algorithm, is a general tree structure soft-decoding algorithm for short linear block code.

However, to achieve maximum likelihood (ML) performance, the decoding complexity may be very huge. In addition, the memory size needed for storage is also an important issue. In this thesis, we appropriately integrate and modify many known techniques for decoding short binary linear codes into A* decoding to achieve the goal of both low decoding complexity and low error rates. The techniques taken into consideration includes the ordered statistics, path constraint algorithms and adaptive path constraint algorithm, control band check, early stop algorithms, modified Fano metric, and Multi-basis algorithm.

口試委員會審定書i
致謝ii
中文摘要iv
Abstract v
Contents vii
List of Figures x
1 Introduction 1
2 Introduction of A* Decoding Algorithm 7
2.1 Preview of the System . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 System Model . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.2 Decision Criterion . . . . . . . . . . . . . . . . . . . . . 9
2.2 A* decoding algorithm . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Tree Structure for binary block code . . . . . . . . . . . . 11
2.2.2 Procedure of A* decoding algorithm . . . . . . . . . . . . 14
2.2.3 Suboptimal A* decoding algorithm . . . . . . . . . . . . 20
2.3 Complexity of A* decoding algorithm . . . . . . . . . . . . . . . 21
2.3.1 Average Number of Search Tree Edges . . . . . . . . . . 21
2.3.2 Average Number of Comparison . . . . . . . . . . . . . . 23
2.4 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Decoding Complexity Reduction for A* Decoding Algorithm 28
3.1 Ordered Statistical Decoding . . . . . . . . . . . . . . . . . . . . 29
3.2 Path Constraint Algorithm . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 Path Constraint i Algorithm . . . . . . . . . . . . . . . . 31
3.2.2 Path Constraint out i Algorithm . . . . . . . . . . . . . . 33
3.2.3 Multiple Stack Algorithm . . . . . . . . . . . . . . . . . 35
3.2.4 simulation result . . . . . . . . . . . . . . . . . . . . . . 37
3.3 Control Band Check . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 simulation result . . . . . . . . . . . . . . . . . . . . . . 43
3.4 Early Stop Criterion . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.1 Channel Observation-based Stopping Criterion . . . . . . 47
3.4.2 Sufficient Condition . . . . . . . . . . . . . . . . . . . . 49
3.4.3 simulation result . . . . . . . . . . . . . . . . . . . . . . 52
4 Further Complexity Reduction for A* Decoding Algorithm 61
4.1 Analysis of different codes . . . . . . . . . . . . . . . . . . . . . 62
4.2 Fano Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.1 Modified Fano Metric . . . . . . . . . . . . . . . . . . . 68
4.2.2 simulation result . . . . . . . . . . . . . . . . . . . . . . 69
4.3 Adaptive-i Algorithm . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.1 The progress of Adaptive-i Algorithm . . . . . . . . . . . 75
4.3.2 simulation result . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Multi-basis algorithm . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4.1 simulation result . . . . . . . . . . . . . . . . . . . . . . 86
5 Conclusion and Future Works 95
Bibliography 97

[1] H.-S. Shih, C.-S. Wang, C.-C. Chen, and M.-C. Lin.,“Tree-search decoding using reduced-size stacks,” 2018 International Symposium on Information Theory and Its Applications (ISITA), pages 511–515, 2018.
[2] C. Berrou, A. Glavieux, and P. Thitimajshima,“Near shannon limit errorcorrecting coding and decoding: Turbo-codes. 1.,”Proceedings of ICC ’93 - IEEE International Conference on Communications, volume 2, pages 1064–1070 vol.2, 1993.
[3] R. Gallager,“Low-density parity-check codes,”IRE Transactions on Information Theory, 8(1):21–28, 1962.
[4] E. Arikan,“Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,”IEEE Transactions on Information Theory, 55(7):3051–3073, 2009.
[5] Z. Tang, R. C. Cannizzaro, G. Leus, and P. Banelli, “Pilot-assisted timevarying channel estimation for ofdm systems,” IEEE Transactions on Signal Processing, vol. 55, no. 5, pp. 2226–2238, 2007.
[6] Yang-Seok Choi, P. J. Voltz, and F. A. Cassara, “On channel estimation and detection for multicarrier signals in fast and selective rayleigh fading channels,”IEEE Transactions on Communications, vol. 49, no. 8, pp. 1375–1387, 2001.
[7] M. Fossorier and S. Lin, “Soft decision decoding of linear block codes based on ordered statistics,” Proceedings of 1994 IEEE International Symposium on Information Theory, pages 395–, 1994.
[8] Y. Han, C. Hartmann, and C.-C. Chen, “Efficient priority-first search maximum-likelihood soft-decision decoding of linear block codes,”IEEE Transactions on Information Theory, 39(5):1514–1523, 1993.
[9] L. Ekroot and S. Dolinar, “A* decoding of block codes,” IEEE Transactions on Communications, 44(9):1052–1056, 1996.
[10] C.-C. Chen, “Designs for efficient tree-search decoding algorithms,” Master’s Thesis, National Taiwan University, 2019.
[11] C.-Y. Chen,“Some study on short linear block codes,” Master’s Thesis, National Taiwan University, 2020.
[12] M. Fossorier, T. Koumoto, T. Takata, T. Kasami, and S. Lin, “The least stringent sufficient condition on the optimality of a suboptimally decoded codeword using the most reliable basis,” Proceedings of IEEE International Symposium on Information Theory, pages 430, IEEE, 1997.
[13] Y. Wu, and C. N. Hadjicostis, “Soft-Decision Decoding of Linear Block Codes Using Preprocessing and Diversification,” IEEE Transactions on Information Theory, 53(1):378–393, 2007.
[14] ‘E. L. Blokh, V. V. Zyablov, “Coding of Generalized Concatenated Codes,” Probl. Peredachi Inf., 10:45–50, 1974.
[15] J. Morris, “Optimal Blocklengths for ARQ Error Control Schemes,” IEEE Transactions on Communications, 27(2):488–493, 1979.