臺灣博碩士論文加值系統

本論文將對以下幾個項目進行優化後，實作出具有達到通道容量（Channel capacity）能力與靈活實現各種碼率（Code rate）的高效能極碼（Polar code）解碼器。而所提出的連續消除（Successive cancellation）解碼器被歸類於半平行化（Semi-parallel）的架構體系中。首先，採用P節點和合併f節點與g節點的運算來減少解碼的週期數。接著，採用四組記憶體來儲存LLR（Log-Likelihood Ratio）資料，並且配合適當的資料擺放排程，每組記憶體只需要兩個存取埠就能完成LLR資料的存取。而本論文也提出一個簡易的位址產生器，其設計上包含計數器、堆疊、狀態機和一些組合邏輯閘。一般典型的處理單元在運算f節點與g節點時，需要類似加法器的電路讓資料在符號大小表示法與二補數表示法之間進行轉換，而本論文在處理單元設計上提出於LLR資料中額外分配一個輔助位元，此機制不僅能夠避免轉換電路所造成的硬體成本，也能夠降低運算時所花費的時間。最後，提出管線化部份和（Partial sum）產生器，其設計上可以產生多組部份和結果，提供給多組處理單元做運算，以達到平行運算的目的。本論文所提出碼長為1024的連續消除極碼解碼器在90奈米的合成下，工作頻率可以達到500 MHz以及具有285 Mbps的吞吐量（Throughput），而所耗費的邏輯閘數量為91K，與先前文獻中所提出的設計，硬體面積上節省57%。

This thesis proposes a high-efficient VLSI decoder architecture for polar code which is capable of achieving channel capacity and flexibly realizing various code rates. The proposed successive-cancellation (SC) Polar decoder can be categorized into the class of semi-parallel architecture. First, it has employed P-node and merged computation of f and g nodes to reduce the decoding latency. Next, a central four-bank memory organization has been proposed to store the intermediate log-likelihood (LLR) data. Based on the proposed load-balance data distribution scheme, each memory bank can be equipped by only two ports, but still supply enough data bandwidth demand. A compact address generator design consisting of a counter, a stack, a finite-state machine (FSM) and some combinational logic gates is also presented. The typical implementation of processing element (PE) to process merged computation of f and g nodes requires adder-like circuits to convert data between two’s complement and sign-magnitude formats. However, by allocating an additional auxiliary bit in representing LLR, the conversion circuit can be avoided which can lead to shorter critical path as well as reduced cost. Finally, a pipeline partial sum generator is proposed which can handle non-successive input, and provide multiple partial sums for multiple PE. A SC polar decoder of a block size of 1024 has been implemented with 90-nm CMOS technology. It can run at 500 MHz, and provide the decoding rate of 285 Mbps. The total gate count is about 91K which is more than 57% smaller than the past designs reported in the literatures.

論文審定書 i
論文公開授權書 ii
摘要 iii
Abstract iv
目錄 v
圖次 vii
表次 ix
第一章 概論 1
1.1 研究背景與動機 1
1.2 論文大綱 2
第二章 極碼介紹 3
2.1 極碼（Polar Code） 3
2.2 編碼方法 4
2.3 解碼演算法 6
2.3.1 連續消除（Successive Cancellation，SC）解碼演算法 6
2.3.2 似然比（Likelihood Ratio，LR）關係推導 6
2.3.3 解碼節點運算介紹 8
2.4 解碼週期之分析 10
2.4.1 一般處理單元設計之解碼週期分析 10
2.4.2 前瞻式處理單元設計之解碼週期分析 11
2.4.3 前瞻式處理單元與預先運算節點設計之解碼週期分析 11
2.5 極碼解碼器電路架構 13
2.5.1 樹狀（Tree-Based）連續消除解碼器 13
2.5.2 線狀（Line-Based）連續消除解碼器 13
2.5.3 半平行化（Semi-parallel）連續消除解碼器 15
2.6 LLR資料位元數模擬分析 15
第三章 極碼解碼器架構設計與實作 17
3.1 硬體架構與單元實作 17
3.1.1 LLR記憶體單元（LLR Memory Unit） 17
3.1.2 位址產生器（Address Generator） 23
3.1.3 處理單元（Processing Element，PE） 27
3.1.4 預先運算節點（Precomputing Node，P Node） 32
3.1.5 部份和產生器（Partial Sum Generator，PSG） 33
3.2 硬體驗證 35
3.3 軟體驗證 36
3.4 晶片佈局設計 37
第四章 硬體數據分析與效能比較 40
4.1 數據分析 40
4.2 硬體效能比較 41
4.3 晶片佈局效能比較 43
第五章 結論與未來展望 44
5.1 結論 44
5.2 未來展望 44
參考文獻 46
附錄一 LLR記憶體資料擺放範例 49
附錄二 位址產生器產生記憶體存取序列範例 56

[1] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes,” in 2008 IEEE International Symposium on Information Theory, Jul. 2008, pp. 1173–1177.
[2] S. B. Korada, E. S¸as¸o˘glu, and R. Urbanke, “Polar codes: Characterization of exponent, bounds, and constructions,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6253–6264, Dec. 2010.
[3] R. Mori and T. Tanaka, “Performance of polar codes with the construction using density evolution,” IEEE Communications Letters, vol. 13, no. 7, pp. 519–521, Jul. 2009.
[4] I. Tal and A. Vardy, “How to construct polar codes,” IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6562–6582, Oct. 2013.
[5] I. Tal and A. Vardy, “List decoding of polar codes,” in 2011 IEEE International Symposium on Information Theory Proceedings, Jul.-Aug. 2011, pp. 1–5.
[6] K. Niu and K. Chen, “Stack decoding of polar codes,” Electronics Letters, vol. 48, no. 12, pp. 695–697, Jun. 2012.
[7] E. Arikan, “Systematic polar coding,” IEEE Communications Letters, vol. 15, no. 8, pp. 860–862, Aug. 2011.
[8] H. Vangala, E. Viterbo, and Y. Hong, “Permuted Successive Cancellation Decoder for Polar Codes,” International Symposium on Information Theory and Its Applications, Oct. 2014, pp. 438-442.
[9] M. S. Oommen and S. Ravishankar, “FPGA implementation of an advanced encoding and decoding architecture of polar codes,” in 2015 International Conference on VLSI Systems, Architecture, Technology and Applications (VLSI-SATA), Jan. 2015, pp. 1–6.
[10] C. Zhang, J. Yang, X. You, and S. Xu, “Pipelined implementations of polar encoder and feed-back part for SC polar decoder,” in 2015 IEEE International Symposium on Circuits and Systems (ISCAS), May 2015, pp. 3032–3035.
[11] C. Leroux, A. J. Raymond, G. Sarkis, and W. J. Gross, “A semi-parallel successive-cancellation decoder for polar codes,” IEEE Transactions on Signal Processing, vol. 61, no. 2, pp. 289–299, Jan. 2013.
[12] C. Zhang and K. K. Parhi, “Low-latency sequential and overlapped architectures for successive cancellation polar decoder,” IEEE Transactions on Signal Processing, vol. 61, no. 10, pp. 2429–2441, May 2013.
[13] C. Zhang, B. Yuan, and K. K. Parhi, “Reduced-latency SC polar decoder architectures,” in 2012 IEEE International Conference on Communications (ICC), Jun. 2012, pp. 3471–3475.
[14] B. Yuan and K. K. Parhi, “Low-latency successive-cancellation polar decoder architectures using 2-bit decoding,” IEEE Transactions on Circuits and Systems I Regular Papers, vol. 61, no. 4, pp. 1241–1254, Apr. 2014.
[15] C. Leroux, I. Tal, A. Vardy, and W. J. Gross, “Hardware architectures for successive cancellation decoding of polar codes,” in 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), May 2011, pp. 1665 – 1668.
[16] A. J. Raymond and W. J. Gross, “A scalable successive-cancellation decoder for polar codes,” IEEE Transactions on Signal Processing, vol. 62, no. 20, pp. 5339–5347, Oct. 2014.
[17] Y. Z. Fan and C. Y. Tsui, “An efficient partial-sum network architecture for semi-parallel polar codes decoder implementation,” IEEE Transactions on Signal Processing, vol. 62, no. 12, pp. 3165–3179, Jun. 2014.
[18] H. Y. Hsu, A. Y. Wu, and J. C. Yeo, “Area-efficient VLSI design of Reed-Solomon decoder for 10GBase-LX4 optical communication systems,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 43, no. 4, pp. 1019–1027, Nov. 2006.
[19] A. Mishra, A. J. Raymond, L. G. Amaru, G. Sarkis, C. Leroux, P. Meinerzhagen, A. Burg, and W. J. Gross, “A successive cancellation decoder ASIC for a 1024-bit polar code in 180nm CMOS,” IEEE Asian Solid-State Circuits Conference, pp.205-208, November 2012