臺灣博碩士論文加值系統

隨著無線通訊系統的發展，提高資料傳輸速率和降低延遲時間是現今的重要議題。為了解決這些問題，最新的無線通信系統採用極化碼作為控制信號傳輸，而極化碼能有效的提高資料的傳輸速率，並同時減少傳輸的延遲時間。此外，極化碼可以通過兩種不同的演算法進行解碼，如可信度傳遞演算法(Belief Propagation, BP)和連續消除演算法(Successive Cancellation, SC)。並且為了減少可信度傳遞演算法疊代解碼與高延遲時間的問題，許多文獻提出了有效的停止策略來減少解碼時間與運算複雜度。最常被使用的停止技術稱為G矩陣提早停止。雖然G矩陣提早停止是一個非常有效能的早停止技術，但是在各個疊代中還是存在多餘的解碼週期是能被進一步減少。
本篇論文探討基於可信度傳遞演算法解碼器下，設計一套層停止技術，此技術不僅能有效的減少各個疊代中的階層運算，並且相較於可信度傳遞演算法，此技術也能維持不錯的位元錯誤率。再者，層停止技術是一以層運算偵測為基準之停止技術，而G矩陣早停止是一以疊代運算偵測為基準之技術。因此，本篇論文利用了這兩種停止機制的優點，透過層停止技術與G矩陣早停止技術的結合提出了一個新的解碼器(Stage Stopping + G-Matrix, SS+GM)，使解碼器能進一步的減少解碼延遲，同時降低其功率消耗。
透過模擬結果可以看到本論文提出的層停止技術與G矩陣的解碼器(SS+GM)可以有效的減少解碼週期，並且擁有69.43%的停止率。最後，本論文透過40nm CMOS製程實現，並且和傳統G矩陣的解碼器相比，本論文所提出的解碼器最高能減少6.05%的功率消號和17.76%的能量消耗，並且只需要增加2.09%的面積。此外，本論文也在硬體架構上進行了優化，因此晶片的操作頻率可操作在285.7 MHz，晶片面積為4.41 mm2，吞吐量為0.8 Gbps和功耗為545.8 mW，並且能有良好的系統效能與硬體使用效率。

With the growth of the wireless communication system, improving the data rate and lowering the latency is a critical issue nowadays. In order to overcome this issue, the latest wireless communication system has adopted polar codes as control signal transmission, which is a solution to support high data rates and low latency. In addition, polar code can be decoded by two different algorithms, Belief Propagation (BP) and Successive Cancellation (SC) algorithm. Unlikely to SC algorithm, BP is an iterative algorithm; therefore several efficient stopping strategies are used to reduce the decoding cycle and computational complexity. The most commonly used stopping strategy is called G-Matrix early termination. Although the G-Matrix early termination has a powerful stopping ability, it still exists a few redundant cycles between an iteration.
Based on the polar BP decoding, we proposed a novel decoding strategy that can significantly reduce the stage computation among iterations. Meanwhile, the proposed Stage Stopping strategy can also maintain the bit error rate (BER) performance compared with the scaled BP decoding. Although the proposed Stage Stopping strategy can efficiently reduce the stage computation, it can be improved by combining with the G-Matrix early termination. Therefore, we further proposed a Stage Stopping + G-Matrix early termination (SS+GM) decoding that stops the stage computation with the Stage Stopping unit and stops the decoding by the G-Matrix detection.
Through the simulation result, it shows the proposed SS+GM decoder reduces the decoding cycle with stopping rates at 69.43%. Using the TSMC 40nm CMOS technology, the proposed decoder can also reduce the power consumption up to 6.05% and energy consumption up to 17.76% with only 2.09% area overhead compared with the conventional decoder using the G-Matrix early termination. In addition, the operating frequency can be working on 285.7 MHz with a core area of 4.41 mm2. The throughput achieves 0.8 Gbps. Consequently, the proposed Stage Stopping (SS) decoder provides better system performance and hardware efficiency.

摘要 ii
Abstract iv
誌謝 vi
List of Contents vii
List of Figures ix
List of Tables xii
Chapter 1 1
1.1 Background 1
1.2 Related works 2
1.3 Motivation and Goal 3
1.4 Thesis Organization 5
Chapter 2 6
2.1 Polar Code Algorithm 6
2.1.1 Channel Polarization : Channel Combining 7
2.1.2 Channel Polarization : Channel Splitting 9
2.1.3 Channel Polarization : Rate of Polarization 9
2.2 Polar Encoder 10
2.3 Polar Decoder 12
2.4 Simulation & Analysis 16
Chapter 3 18
3.1 G-Matrix early termination 18
3.2 Proposed Stage Stopping Algorithm 21
3.2.1 Proposed Stage Stopping Strategy 21
3.2.2 Proposed Stage Stopping + G-Matrix Early Termination (SS+GM) 24
3.3 Simulation & Analysis 26
Chapter 4 40
4.1 Design Flow 40
4.2 Encoder 42
4.3 Overall Polar Code Decoder 43
4.3.1 Processing Element 46
4.3.2 Shifting and De-Shifting Network 49
4.3.3 External Memory 50
4.3.4 Stage Stopping Strategy 52
4.3.5 G-Matrix Early Termination 55
4.3.6 Fixed-Point Simulation 58
4.4 Chip Results 61
4.5 FPGA Implementation Results 62
4.6 ASIC Implementation Results 64
4.6.1 Area Analysis 64
4.6.2 Power Analysis 65
4.6.3 Decoder Implementation 67
4.7 Comparison 69
Chapter 5 73
References 75

[1]https://dahetalk.com/
[2]https://www.3gpp.org/
[3]E. Arıkan, “Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels,” IEEE Trans. Inform. Theory (TIT), vol. 55, pp. 3051–3073, July 2009.
[4]E. Arikan, “Polar codes: A pipelined implementation,” in Proc. 4th Int. Symp. Broad. Commun. (ISBC), Jul. 2010, pp. 11–14.
[5]C. Leroux, I. Tal, A. Vardy, and W. J Gross, “Hardware architectures for successive cancellation decoding of polar codes,” in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), pp. 1665–1668. , May 2011.
[6]I. Tal and A. Vardy. “List decoding of polar codes,” IEEE Transactions on Information Theory (ISIT), vol. 61, no. 5, pp. 2213-2226, 2015.
[7]O. Afisiadis, A. Balatsoukas-Stimming, and A. Burg, “A Low-Complexity Improved Successive Cancellation Decoder for Polar Codes,” In 2014 48th Asilomar Conference on Signals, Systems and Computers (ACSSC), pp. 2116-2120. , CA, USA, 2014.
[8]B. Yuan, & K. K. Parhi, “Early stopping criteria for energy-efficient low-latency belief-propagation polar code decoders,” IEEE transactions on signal processing (TSP), vol. 62, no. 24, pp. 6496-6506, Oct. 2014.
[9]B. Yuan and K. K. Parhi, “Architecture optimizations for BP polar decoders,” 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Vancouver, BC, Canada, May. 2013.
[10]A. Elkelesh, M. Ebada, S.Cammerer, and S. Ten Brink, “Belief propagation list decoding of polar codes,” IEEE Communications Letters 22 (LCOMM), no. 8, pp. 1536-1539, 2018.
[11]Y. Yu, Z. Pan, N. Liu, and X.You, “Belief Propagation Bit-Flip Decoder for Polar Codes,” IEEE Access, vol. 7, pp. 10937-10946, 2019.
[12]Y.-F. Shen, H. Ji, Y. Ren, C. Ji ,X.-H Y, and C. Zhang, “Improved Belief Propagation Polar Decoders With Bit-Flipping Algorithms,” IEEE Transactions on Communications (TCOMM), vol. 68, no. 11, Nov, 2020.
[13]W. Xu, Z. Wu, Y.-L. Ueng, Xi. You, and C. Zhang. “Improved polar decoder based on deep learning,” 2017 IEEE International workshop on signal processing systems (SiPS), pp. 1-6, 2017.
[14]C.-F. Teng, K.-S. Ho, C.-H. Wu, S.-S. Wong, and A.-Y. Wu, “Convolutional Neural Network-aided Bit-flipping for Belief Propagation Decoding of Polar Codes,” IEEE Transactions on Signal Processing (TSP), vol. 69, Nov 2019.
[15]A. Pamuk, “An FPGA implementation architecture for decoding of polar codes,” in Proc. 8th Int. Symp.Wireless Commun. Syst. (ICWCS), pp. 437–441, Nov. 2011.
[16]R. E. Blahut, Theory and Practice of Error-Control Codes. Reading, MA, USA: Addison-Wesley, 1983.
[17]C. H. Lin, T. H. Huang, C. C. Chen, and S. Y. Lin, “Efficient layer stopping technique for layered LDPC decoding.” Electronics Letters, vol 49, no. 16, pp. 994-996, Aug. 2013.
[18]Design Compiler, and IC Compiler – Synopsys. [Online]. Available: https://www.synopsys.com/
[19]Zynq UltraScale+ MPSoC ZCU104 Evaluation Kit FPGA device. [Online]. Available: https://www.xilinx.com/products/boards-and-kits/zcu104.html
[20]Xilinx SDx Design Simulation Platform. [Online]. Available: https://www.xilinx.com/products/design-tools/vivado.html
[21]S.Sun and Z. Zhang. “Architecture and optimization of high-throughput belief propagation decoding of polar codes,” IEEE International Symposium on Circuits and Systems (ISCAS), pp. 165-168. IEEE, 2016.
[22]Y.-F. Shen, W.-Q. Song, Y.-Q. Ren, H. Ji, X.-H. You, and C. Zhang, “Enhanced Belief Propagation Decoder for 5g Polar Codes with Bit-Flipping,” IEEE Transactions on Circuits and Systems II, vol. 67, no. 5, pp. 901-905, May 2020.
[23]Y. Sung Park, Y. Tao, S. Sun, and Z. Zhang, “A 4.68 Gb/s belief propagation polar decoder with bit-splitting register file,” in Proc. Symp. VLSI Circuits Dig. Tech. Papers (VLSIC), pp. 1–2, Jun. 2014.
[24]W.-H. Xu, X. Tan, Y. Be’ery. Y.-L. Ueng. Y.-M. Huang, X.-H You, C. Zhang, “Deep Learning-Aided Belief Propagation Decoder for Polar Codes,” IEEE Journal on Emerging and Selected Topics in Circuits and Systems (JETCAS), vol. 10, no. 2, June 2020.
[25]B. Yuan and K. K. Parhi, “Architectures for Polar BP Decoder Using Folding,” in Proc. IEEE Int. Symp. Circuits Sys (ISCAS)t., 2014.
[26]J. M. Rabaey, C. Anantha, and N. Borivoje, Digital integrated circuits: a design perspective. Prentice Hall, 2003.