臺灣博碩士論文加值系統

極碼 (polar codes) 因其可被證明用於實現通道容量而被視為編碼理論的最新突破，在現有的解碼方案中，接續消去名單 (successive-cancellation list, SCL) 解碼是主要的作法，可用來得到最佳的糾錯能力。然而，傳統的SCL解碼器在硬體實現上需要較大面積且其吞吐量過低，而後續相關研究並沒有同時對這兩種指標進行優化。本論文基於對數似然比 (log-likelihood-ratio, LLR) 的SCL解碼演算法與符號判斷，提出一種高重複使用的LLR記憶體以及簡化的部分總和產生器 (partial-sum generator, PSG) 來減小面積。另一方面，我們採用比率-0碼和重複碼的新凍結位置樣式 (frozen-location patterns) 來減少近似最大似然 (approximate maximum likelihood, AML) 解碼的排序階層，並進一步修改比率-0碼和比率-1碼來減少解碼週期。實驗結果顯示，基於本論文所提出之演算法而開發出的SCL解碼器，於名單大小為2的條件下，其所實現之4位元 (1024,512) 極碼解碼器設計的硬體效率可至少優於現有相關解碼器的 1.22倍。

Polar codes are the latest breakthrough in coding theory, as they can provably achieve the channel capacity. Among existing decoding schemes, successive-cancellation list (SCL) decoding is recognized as the main approach that can be applied to achieve the best error-correction performance. However, hardware implementation of the conventional SCL decoder usually consumes a large area and can only achieve low throughput. Recent research works were mainly focused on either reducing the hardware requirement or improving the resulting throughput. According to the log-likelihood-ratio (LLR) based SCL decoding algorithm and the concept of symbol decision, this thesis presents a highly reusable LLR memory structure and simplifies the partial-sum generator to reduce the overall area requirement of polar decoders. In addition, new frozen-location patterns of rate-0 and repetition codes were employed to decrease the number of sorting stages for approximate maximum likelihood decoding, and modified rate-0 and rate-1 codes were used to further reduce the decoding cycles. Experimental results reveal that the SCL decoder designed using the proposed algorithm and optimization schemes for a 4-bit (1024, 512) polar code with a list size of 2 can achieve at least 1.22 times the hardware efficiency of related works.

摘 　 要 i
ABSTRACT ii
致謝 iv
Content v
List of Tables viii
List of Figures ix
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Thesis organization 2
Chapter 2 Background 3
2.1 Channel polarization 3
2.2 Construction of polar codes 4
2.2.1 Channel combining 4
2.2.2 Channel splitting 5
2.2.3 Recursive channel transformations 5
2.2.4 Bit-reversed indexing 6
2.3 Successive-cancellation decoding 7
2.4 Architecture of SC decoder 8
2.4.1 Fully-parallel architecture 8
2.4.2 Tree architecture 9
2.4.3 Line architecture 10
2.4.4 Semi-parallel architecture 11
2.5 Simplified SC decoder 12
2.5.1 Min-sum approximation 12
2.5.2 Merged processing element and symbol-decision 13
2.5.3 Rate-0 and rate-1 nodes 14
2.6 Successive-cancellation list decoding 15
2.7 Architecture of semi-parallel SCL decoder 16
2.7.1 Metric computation unit 17
2.7.2 Zero-forcing unit and Frozen-location patterns 18
2.7.3 Sorter 19
2.7.4 Approximate maximum likelihood decoding 19
2.8 Quantization 22
Chapter 3 Proposed LLR-based SCL Decoder 23
3.1 Proposed SCL decoding for (1024, 512) polar codes 23
3.1.1 Architecture of 4-bit LLR-based SCL decoder with L=2 23
3.1.2 SCL decoding algorithm 25
3.2 Processing element unit 27
3.2.1 The simplification of g function 27
3.2.2 Non-uniform quantizer for LLR memory bank 29
3.3 LLR memory bank and multiplexer 30
3.3.1 Additional processing element unit without multiplexer connection 31
3.3.2 An efficient method for LLR memory bank with high usage rate 31
3.4 Metric computation unit, Frozen-location patterns and Sorter 33
3.4.1 Simplification on sorting 34
3.4.2 Fast sorting with additional judgement on Frozen-location patterns 35
3.5 Partial sum generator 37
3.6 Candidate memory bank 39
3.7 Encoder with Rate-1 node implementation 39
Chapter 4 Experimental Results 42
4.1 Analysis and comparison of simulation results 42
4.1.1 Quantization of different bit size on channel LLRs 42
4.1.2 Non-Uniform Quantization of SCL decoder 44
4.2 Estimation of SCL decoder with L=2 and k=2 45
4.3 Analysis and comparison of hardware performance 46
Chapter 5 Conclusion and Future Work 49
5.1 Conclusion 49
5.2 Future work 50
References 51

[1]Erdal. Arıkan, Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels, IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, July 2009.
[2]Kai Niu, Kai Chen, Jiaru Lin and Q. T. Zhang, Polar codes: Primary concepts and practical decoding algorithms, IEEE Communications Magazine, vol. 52, no. 7, pp. 192 - 203, July 2014.
[3]Camille Leroux, Alexandre J. Raymond, Gabi Sarkis, and Warren J. Gross, A semi-parallel successive-cancellation decoder for polar codes, IEEE Transactions on Signal Processing, vol. 61, no. 2, pp. 289 - 299, January 2013.
[4] Erdal Arıkan, Systematic Polar Coding, IEEE Communications Letters, vol. 15, no. 8, pp. 860 - 862, August 2011.
[5]Gabi Sarkis, Ido Tal, Pascal Giard, Alexander Vardy, Claude Thibeault, and Warren J. Gross, Flexible and Low-Complexity Encoding and Decoding of Systematic Polar Codes, IEEE Transactions on Communications, vol. 64, no. 7, pp. 2732 - 2745, July 2016.
[6]Camille Leroux, Ido Tal, Alexander Vardy, and Warren J. Gross, HARDWARE ARCHITECTURES FOR SUCCESSIVE CANCELLATION DECODING OF POLAR CODES, in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1665-1668, May 2011.
[7]Chuan Zhang and Keshab K. Parhi, Low-Latency Sequential and Overlapped Architectures for Successive Cancellation Polar Decoder, IEEE Transactions on Signal Processing, vol. 6, no. 10, pp. 2429 - 2441, March 2013.
[8]Bo Yuan and Keshab 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, April 2014.
[9]A. Mishra, A. Raymond, L. 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(A-SSCC), November 2012.
[10]Amin Alamdar-Yazdi and Frank R. Kschischang, A Simplified Successive-Cancellation Decoder for Polar Codes, IEEE Communications Letters, vol. 15, no. 12, pp. 1378 - 1380, December 2011.
[11]K. Chen, K. Niu and J.R. Lin, List successive cancellation decoding of polar codes, Electronics Letters, vol. 48, no. 9, pp. 500 - 501, April 2012.
[12]I. Tal and A. Vardy, “ List decoding of polar codes, arXiv:1206.0050, May 2012.
[13]Bo Yuan and Keshab K. Parhi, Successive cancellation list polar decoder using log-likelihood ratios, 48th Asilomar Conference on Signals, Systems and Computers, November 2014.
[14]Bo Yuan and Keshab K. Parhi, Low-Latency Successive-Cancellation List Decoders for Polar Codes With Multibit Decision, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23, no. 10, pp. 2268 - 2280, October 2015.
[15]Bo Yuan and Keshab K. Parhi, LLR-Based Successive-Cancellation List Decoder for Polar Codes With Multibit Decision, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 64, no. 1, pp. 21 - 25, January 2017.
[16]Chenrong Xiong, Jun Lin and Zhiyuan Yan, Efficient approximate ML decoding units for polar list decoders, IEEE Workshop on Signal Processing Systems (SiPS), October 2015.
[17]Chenrong Xiong, Jun Lin and Zhiyuan Yan, Symbol-based successive cancellation list decoder for polar codes, IEEE Workshop on Signal Processing Systems (SiPS), October 2014.
[18]Chenrong Xiong, Jun Lin and Zhiyuan Yan, A Multimode Area-Efficient SCL Polar Decoder, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 24, no. 12, pp. 3499 - 3512, December 2016.
[19]Alexios Balatsoukas-Stimming, Alexandre J. Raymond, Warren J. Gross and Andreas Burg, Hardware Architecture for List Successive Cancellation Decoding of Polar Codes, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 61, no. 8, pp. 609 - 613, August 2014.
[20]Alexios Balatsoukas-Stimming, Mani Bastani Parizi and Andreas Burg, LLR-Based Successive Cancellation List Decoding of Polar Codes, IEEE Transactions on Signal Processing, vol. 63, no. 19, pp.5165 - 5179, October 2015.
[21]Daesun Oh and Keshab K. Parhi, Min-Sum Decoder Architectures With Reduced Word Length for LDPC Codes, IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 57, no. 1, pp. 105 - 115, January 2010.
[22]Alaa A. Hasan and Ian D. Marsland, Non-uniform quantizers with SC polar based channel-optimized decoders, 8th IEEE Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON), October 2017.
[23]Gabi Sarkis and Warren J. Gross, Increasing the Throughput of Polar Decoders, IEEE Communications Letters, vol. 17, no. 4, pp. 725 - 728, April 2013.
[24]Gabi Sarkis, Pascal Giard, Claude Thibeault and Warren J. Gross, Autogenerating software polar decoders, IEEE Global Conference on Signal and Information Processing (GlobalSIP), December 2014.
[25]Chuan Zhang and Keshab K. Parhi, Latency Analysis and Architecture Design of Simplified SC Polar Decoders, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 61, no. 2, pp. 115 - 119, February 2014.
[26]Gabi Sarkis, Pascal Giard, Alexander Vardy, Claude Thibeault and Warren J. Gross, Fast Polar Decoders: Algorithm and Implementation, IEEE Journal on Selected Areas in Communications, vol. 32, no. 5, pp. 946 - 957, May 2014.
[27]Chenrong Xiong, Jun Lin and Zhiyuan Yan, Error performance analysis of the symbol-decision SC polar decoder, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), March 2016.
[28]Ido Tal and Alexander Vardy, List Decoding of Polar Codes, IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213 - 2226, May 2015.
[29]Alexios Balatsoukas-Stimming, Mani Bastani Parizi and Andreas Burg, On metric sorting for successive cancellation list decoding of polar codes, IEEE International Symposium on Circuits and Systems (ISCAS), May 2015.
[30]Byeong Yong Kong, Hoyoung Yoo and In-Cheol Park, Efficient Sorting Architecture for Successive-Cancellation-List Decoding of Polar Codes, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 63, no. 7, pp. 673 - 677, July 2016.
[31]Valerio Bioglio, Frédéric Gabry, Loïg Godard and Ingmar Land, Two-Step Metric Sorting for Parallel Successive Cancellation List Decoding of Polar Codes, IEEE Communications Letters, vol. 21, no. 3, pp. 456 - 459, March 2017.
[32]Sha Shi, Bing Han, Jing-Liang Gao and Yun-Jiang Wang, Enhanced Successive Cancellation List Decoding of Polar Codes, IEEE Communications Letters, vol. 21, no. 6, pp. 1233 - 1236, June 2017.
[33]Huan Li, Enhanced Metric Sorting for Successive Cancellation List Decoding of Polar Codes, IEEE Communications Letters, vol. 22, no. 4, pp. 664 - 667, April 2018.
[34]Seyyed Ali Hashemi, Carlo Condo and Warren J. Gross, Fast and Flexible Successive-Cancellation List Decoders for Polar Codes, IEEE Transactions on Signal Processing, vol. 65, no. 21, pp. 1233 - 1236, November 2017.
[35]Seyyed Ali Hashemi, Carlo Condo and Warren J. Gross, Simplified Successive-Cancellation List Decoding of Polar Codes, IEEE International Symposium on Information Theory (ISIT), July 2016.
[36]Guillaume Berhault, Camille Leroux, Christophe Jego and Dominique Dallet, Partial sums generation architecture for successive cancellation decoding of polar codes, IEEE Workshop on Signal Processing Systems, October 2013.
[37]Bo Yuan, 2015, Algorithm and VLSI Architecture for Polar Codes Decoder, PhD dissertation, University of Minnesota, U.S.A.
[38]Mostafa El-Khamy, Hessam Mahdavifar, Gennady Feygin, Jungwon Lee and Inyup Kang, Relaxed Polar Codes, IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 1986 - 2000, January 2017.
[39]Zhengming Shi, Kai Niu, On uniform quantization for successive cancellation decoder of polar codes, 2014 IEEE 25th Annual International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC), September 2014.