請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50665
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 闕志達(Tzi-Dar Chiueh) | |
dc.contributor.author | Bei-Sheng Su | en |
dc.contributor.author | 蘇倍陞 | zh_TW |
dc.date.accessioned | 2021-06-15T12:51:30Z | - |
dc.date.available | 2023-08-18 | |
dc.date.copyright | 2020-08-24 | |
dc.date.issued | 2020 | |
dc.date.submitted | 2020-08-18 | |
dc.identifier.citation | [1] Ericsson, “Mobile data traffic growth outlook,” ericsson.com, para. 4. Nov. 2019. [Online]. Available: https://www.ericsson.com/en/mobility-report/reports/november-2019/mobile-data-traffic-outlook. [Accessed June. 16, 2020]. [2] ITU-R M.2083-0 IMT Vision – Framework and overall objectives of the future development of IMT for 2020 and beyond. [3] TS38.212V.15.1.1.[Online].Available:https://www.3gpp.org/ftp/Specs/archive/38 series/38.212/[Accessed June. 16, 2020]. [4] ETSI, “Why do we need 5G,” etsi.org, para. 3. [Online]. Available: https://www.etsi.org/technologies-clusters/technologies/5g. [Accessed June. 16, 2020]. [5] S. Yen, S. Hung, C. Chen, H. Chang, S. Jou and C. Lee, 'A 5.79-Gb/s Energy-Efficient Multirate LDPC Codec Chip for IEEE 802.15.3c Applications,' IEEE Journal of Solid-State Circuits, vol. 47, no. 9, pp. 2246-2257, Sept. 2012. [6] Y. Sun and J. R. Cavallaro, 'VLSI Architecture for Layered Decoding of QC-LDPC Codes With High Circulant Weight,' IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 21, no. 10, pp. 1960-1964, Oct. 2013. [7] C. Roth, P. Meinerzhagen, C. Studer and A. Burg, 'A 15.8 pJ/bit/iter quasi-cyclic LDPC decoder for IEEE 802.11n in 90 nm CMOS,' in Proc. of 2010 IEEE Asian Solid-State Circuits Conference, Beijing, 2010, pp. 1-4. [8] X. Peng, Z. Chen, X. Zhao, D. Zhou and S. Goto, 'A 115mW 1Gbps QC-LDPC decoder ASIC for WiMAX in 65nm CMOS,' in Proc. of IEEE Asian Solid-State Circuits Conference 2011, Jeju, 2011, pp. 317-320. [9] N. Yang et al., 'Reconfigurable Decoder for LDPC and Polar Codes,' in Proc. of 2018 IEEE International Symposium on Circuits and Systems (ISCAS), Florence, 2018, pp. 1-5,. [10] W. Qiao, D. Liu and S. Liu, 'QFEC ASIP: A Flexible Quad-Mode FEC ASIP for Polar, LDPC, Turbo, and Convolutional Code Decoding,' IEEE Access, vol. 6, pp. 72189-72200, 2018. [11] Z. Babar et al., 'Polar Codes and Their Quantum-Domain Counterparts,' IEEE Communications Surveys Tutorials, vol. 22, no. 1, pp. 123-155, First quarter 2020. [12] Z. B. Kaykac Egilmez, L. Xiang, R. G. Maunder and L. Hanzo, 'The Development, Operation and Performance of the 5G Polar Codes,' IEEE Communications Surveys Tutorials, vol. 22, no. 1, pp. 96-122, First quarter 2020. [13] J. H. Bae, A. Abotabl, H. P. Lin, K. B. Song, and J. Lee, 'An overview of channel coding for 5G NR cellular communications,' APSIPA Trans.Signal Inf. Process., vol. 8, no. 1, pp. 1–14, Jan. 2019. [14] R. Gallager, 'Low-density parity-check codes,' IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21-28, January 1962. [15] D. J. C. MacKay and R. M. Neal, 'Near Shannon limit performance of low density parity check codes,' Electronics Letters, vol. 33, no. 6, pp. 457-458, 13 March 1997. [16] Seho Myung, Kyeongcheol Yang and Jaeyoel Kim, 'Quasi-cyclic LDPC codes for fast encoding,' IEEE Transactions on Information Theory, vol. 51, no. 8, pp. 2894-2901, Aug. 2005. [17] Thien Truong Nguyen Ly, 'Efficient Hardware Implementations of LDPC Decoders, through Exploiting Impreciseness in Message-Passing Decoding Algorithms. Networking and Internet Architecture, ' Ph.D. dissertation, University’s de Cergy Pontoise, France, 2017. [18] D. Hui, S. Sandberg, Y. Blankenship, M. Andersson and L. Grosjean, 'Channel Coding in 5G New Radio: A Tutorial Overview and Performance Comparison with 4G LTE,' IEEE Vehicular Technology Magazine, vol. 13, no. 4, pp. 60-69, Dec. 2018. [19] H. Li, B. Bai, X. Mu, J. Zhang and H. Xu, 'Algebra-Assisted Construction of Quasi-Cyclic LDPC Codes for 5G New Radio,' IEEE Access, vol. 6, pp. 50229-50244, 2018. [20] T. K. Moon, Error Correction Coding, Mathematical Methods, and Algorithms. New York: Wiley Interscience.,2005. [21] M. M. Mansour, 'A Turbo-Decoding Message-Passing Algorithm for Sparse Parity-Check Matrix Codes,' IEEE Transactions on Signal Processing, vol. 54, no. 11, pp. 4376-4392, Nov. 2006. [22] E. Arikan, '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. [23] S. Zhao, P. Shi, and B. Wang, “Designs of Bhattacharya parameter in the construction of polar codes,” in Proc. of Wireless Communications, Networking and Mobile Computing (WiCOM), 7th international conference on, Wuhan, September 2011, pp. 1–4. [24] P. Trifonov, 'Efficient Design and Decoding of Polar Codes,' IEEE Transactions on Communications, vol. 60, no. 11, pp. 3221-3227, November 2012. [25] G. He et al., 'Beta-Expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes,' in Proc. of GLOBECOM 2017 - 2017 IEEE Global Communications Conference, Singapore, 2017, pp. 1-6. [26] I. Tal and A. Vardy, 'List Decoding of Polar Codes,' IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213-2226, May 2015. [27] K. Niu and K. Chen, 'CRC-Aided Decoding of Polar Codes,' IEEE Communications Letters, vol. 16, no. 10, pp. 1668-1671, October 2012. [28] E. Arikan, “Polar codes: A pipelined implementation,” in Proc. of 4th Int. Symp. on Broad. Commun. ISBC 2010, pp. 11-14, July 2010. [29] A. Elkelesh, M. Ebada, S. Cammerer and S. t. Brink, 'Decoder-Tailored Polar Code Design Using the Genetic Algorithm,' IEEE Transactions on Communications, vol. 67, no. 7, pp. 4521-4534, July 2019. [30] 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. [31] Youn Sung Park, Yaoyu Tao, Shuanghong Sun and Zhengya Zhang, 'A 4.68Gb/s belief propagation polar decoder with bit-splitting register file,' in Proc. of 2014 Symposium on VLSI Circuits Digest of Technical Papers, Honolulu, HI, 2014, pp. 1-2 [32] B. Yuan and K. K. Parhi, 'Early Stopping Criteria for Energy-Efficient Low-Latency Belief-Propagation Polar Code Decoders,' IEEE Transactions on Signal Processing, vol. 62, no. 24, pp. 6496-6506, Dec.15, 2014. [33] C. Wey, M. Shieh and S. Lin, 'Algorithms of Finding the First Two Minimum Values and Their Hardware Implementation,' IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 55, no. 11, pp. 3430-3437, Dec. 2008. [34] C. Cheng, J. Yang, H. Lee, C. Yang and Y. Ueng, 'A Fully Parallel LDPC Decoder Architecture Using Probabilistic Min-Sum Algorithm for High-Throughput Applications,' IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, no. 9, pp. 2738-2746, Sept. 2014. [35] M. Weiner, M. Blagojevic, S. Skotnikov, A. Burg, P. Flatresse and B. Nikolic, '27.7 A scalable 1.5-to-6Gb/s 6.2-to-38.1mW LDPC decoder for 60GHz wireless networks in 28nm UTBB FDSOI,' in Proc. of 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), San Francisco, CA, 2014, pp. 464-465. [36] M. Li et al., 'An energy efficient 18Gbps LDPC decoding processor for 802.11ad in 28nm CMOS,' in Proc. of 2015 IEEE Asian Solid-State Circuits Conference (A-SSCC), Xiamen, 2015, pp. 1-5. [37] R. Ghanaatian et al., 'A 588-Gb/s LDPC Decoder Based on Finite-Alphabet Message Passing,' IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 26, no. 2, pp. 329-340, Feb. 2018. [38] A. Balatsoukas-Stimming, M. B. Parizi and A. Burg, 'LLR-Based Successive Cancellation List Decoding of Polar Codes,' IEEE Transactions on Signal Processing, vol. 63, no. 19, pp. 5165-5179, Oct.1, 2015. [39] P. Giard et al., 'PolarBear: A 28-nm FD-SOI ASIC for Decoding of Polar Codes,' IEEE Journal on Emerging and Selected Topics in Circuits and Systems, vol. 7, no. 4, pp. 616-629, Dec. 2017. [40] X. Liu et al., 'A 5.16Gbps decoder ASIC for Polar Code in 16nm FinFET,' in Proc. of 2018 15th International Symposium on Wireless Communication Systems (ISWCS), Lisbon, 2018, pp. 1-5. [41] S. M. Abbas, Y. Fan, J. Chen and C. Tsui, 'High-Throughput and Energy-Efficient Belief Propagation Polar Code Decoder,' IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 25, no. 3, pp. 1098-1111, March 2017. [42] V. Bioglio, C. Condo, and I. Land, 'Design of polar codes in 5G new radio,' arXiv:1804.04389, Apr 2018. [43] H. M. Ji and E. Killian, 'Fast parallel CRC algorithm and implementation on a configurable processor,' in Proc. of 2002 IEEE International Conference on Communications. Conference Proceedings. ICC 2002 (Cat. No.02CH37333), New York, NY, USA, 2002, pp. 1813-1817 vol.3. [44] 'Clock Gating Integrated Cell,'Aug.2012.[Online]. Available: http://vlsi-soc.blogspot.com/2012/08/clock-gating-integrated-cell.html. [Accessed July.28, 2020]. [45] Gonc ̧alves, J.F., Mendes, J.J.M., Resende, M.G.C., ' A hybrid genetic algorithm for the job shop scheduling problem.,' European Journal of Operational Research 167, pp. 77–95. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50665 | - |
dc.description.abstract | 隨著人們對於超高可靠度與低延遲的需求日益提升,前向錯誤更正碼(FEC)已是現代通訊不可或缺的技術之一,其中極化碼與低密度奇偶校驗碼因為解碼的表現可以非常接近香農極限,已被5G系統中的增強型行動寬頻通訊(eMBB)所採納使用,分別拿來保護控制訊號與數據訊號。然而,這兩種錯誤更正碼皆可利用信度傳播(Belief Propagation)的方式進行解碼,其為一種可全平行化的演算法,可以有效應用於低延遲與高吞吐量的通訊系統中。本論文主要研究基於信度傳播的解碼器設計,一共有兩大主軸,一是改善極化碼於傳統信度傳播下解碼表現不佳的問題,二是設計一共用的電路架構使得兩種碼能夠在不同的時間上於同一套硬體資源上進行解碼,進而降低傳統上需要兩套單模式解碼器所需的面積。
在本論文的第二章中,介紹了兩種錯誤更正碼的基礎理論、編碼與解碼的方法與於5G系統下的使用方式,並去比較不同解碼方法的性能表現,包含塊錯誤率(BLER)、平均所需迭代數、運算延遲與運算複雜度,來決定第四章中的硬體架構需要採取何種方案。 在第三章中,我們運用另一種最佳化的演算法---遺傳算法套用基於信度傳播的極化碼解碼過程中,使得迭代過程更具有方向性,更容易找到傳統方法所無法成功解碼的結果,而一共有兩種施行方法,分別為修改左訊息法與修改右訊息法,經模擬顯示其解碼性能可以與CA-SCL (L=8)相當,並且仍保有天生平行的優勢。於本章的末節,亦會探討不同解碼方法的複雜度,及參數的選擇方式。 在第四章與第五章中,我們利用兩種碼都能透過信度傳播解碼的特性,設計出一套通用的硬體架構並實作成晶片,使其可以在不同時間下支援兩種模式。除了共用架構,我們亦針對各別模式進行優化,包含低複雜度及多模式的處理單元設計、儲存方式的優化、低功耗的設計與特殊的排程等。比起兩個單一模式的解碼器,共用的架構可以省去約35%的面積使用,並且其餘相關的硬體指標並不會與其他文獻單一模式的解碼器相差太多,顯示我們設計的共用架構並不會付出太多額外的成本。 | zh_TW |
dc.description.abstract | With the increasing demand for ultra-high reliability and low latency, forward error correction codes (FEC) has become one of the indispensable technologies in modern communication systems. Among them, polar codes and low-density parity-check (LDPC) codes are appealing since their performance is very close to the Shannon limit. Given this, they have been adopted in Enhanced Mobile Broadband Communication (eMBB), one of the 5G use cases, to protect control and data channels, respectively. However, both error correction codes can be decoded by Belief Propagation (BP), a fully parallelizable algorithm that can be effectively applied to low-latency and high-throughput decoding. This thesis focuses on the design of a dual-mode BP based decoder. Toward this end, there are two main issues. One is to improve the inferior decoding performance of polar codes using conventional belief propagation. The other is to design a unified hardware architecture so that the two codes can be decoded on the same hardware, replacing two single-mode decoders and thus reducing the die area and associated cost.
In Chapter 2, the basic principles of two error correction codes, the encoding and decoding methods and the usage in 5G system are introduced. Moreover, the performance of different decoding methods is compared, including block error rate and average iteration number, latency, and complexity. In Chapter 3, we adopt the genetic algorithm to improve the decoding process of polar codes based on belief propagation, making the iterative process more effective in finding the optimal solution that conventional methods cannot. We propose two implementation methods, namely the modified left message method and the modified right message method. Simulation results show that the decoding performance of the proposed methods can be comparable to CA-SCL (L=8), while still maintaining the inherent parallel characteristic. At the end of this chapter, we also discuss the complexity of different decoding methods and the parameter setting. In Chapters 4 and 5, we take advantage of the fact that both codes can be decoded by belief propagation and design a unified hardware architecture. In addition to sharing processing elements and memory, we also optimize several aspects of the decoder, including low-complexity and multi-mode processing unit design, storage optimization, low-power design, and special scheduling. Compared with the single-mode decoder, the unified architecture can save about 35% die area, and other hardware figure of merits (FOM) are similar to other single-mode decoder implementations, indicating the proposed architecture is quite area efficient. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T12:51:30Z (GMT). No. of bitstreams: 1 U0001-1108202004432900.pdf: 10434477 bytes, checksum: a1605dbc53c058d0ac9d31ebbb978b16 (MD5) Previous issue date: 2020 | en |
dc.description.tableofcontents | 致謝 i 摘要 iii Abstract v 目錄 vii 圖目錄 xi 表目錄 xvii 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機與目標 3 1.3 研究現況 5 1.4 論文組織與貢獻 6 第二章 適用於5G-NR之錯誤更正碼介紹 7 2.1 低密度奇偶校驗碼 (LDPC Codes) 7 2.1.1簡介 7 2.1.2編碼方法(Encoding) 11 2.1.3解碼方法(Decoding) 19 2.1.3.1 Sum-Product (SP) 20 2.1.3.2 Min-Sum based algorithms 27 2.1.3.3 Layered Decoding 28 2.1.4演算法之性能比較 31 2.2 極化碼 (Polar Codes) 33 2.2.1簡介 33 2.2.2通道極化(Channel Polarization) 34 2.2.3編碼方法(Encoding) 38 2.2.4解碼方法(Decoding) 40 2.2.4.1 連續消除法(Successive Cancelation)[22] 40 2.2.4.2 列表連續消除法(Successive Cancelation List)[26] 45 2.2.4.3 循環冗餘校驗輔助列表連續消除法(CRC-aided SCL) 48 2.2.4.4 信度傳播(Belief Propagation)[28] 48 2.2.5演算法之性能比較 53 2.3 第二章總結 57 第三章 基於遺傳算法之信度傳播極化碼解碼器設計 59 3.1 遺傳演算法介紹 59 3.1.1 簡介 59 3.1.2 相關名詞解釋 60 3.1.3 流程 62 3.2 本論文提出的解碼器設計 62 3.2.1 修改右訊息法 63 3.2.2 修改左訊息法 68 3.2.3 演算法之模擬與參數選擇 73 3.2.4 不同碼長與碼率下的解碼表現 77 3.2.5 複雜度分析 81 3.3 第三章總結 88 第四章 基於信度傳播之通用解碼器設計與硬體實現 89 4.1 硬體架構 89 4.2 操作流程 92 4.3 各模式的資料流 93 4.3.1 Polar Codes模式 93 4.3.2 LDPC Codes模式 98 4.4 各電路單元介紹 101 4.4.1可共用的運算單元 102 4.4.1.1 共用概念 102 4.4.1.2 具有雙模的極化運算單元(BCU) 106 4.4.1.3 具有雙模的變數點運算單元(VNU) 107 4.4.1.4 低複雜度且可管線化的查核點運算單元(CNU) 108 4.4.4.5 提前中止單元 112 4.4.2 可共用的記憶體系統 116 4.4.2.1 記憶體配置 116 4.4.2.2 儲存方式的優化 118 4.4.3 其餘不可共用的電路單元 122 4.4.3.1 重新排序單元 122 4.4.3.2 解壓縮單元 125 4.4.4 控制訊號生成單元 126 4.5 電路特點與比較 128 4.6 第四章總結 136 第五章 晶片實現 139 5.1 晶片設計流程 139 5.2 驗證流程 140 5.3 定點數模擬 141 5.4 系統規格 142 5.5 晶片佈局圖 144 5.6 晶片量測考量 146 5.7 晶片性能比較 148 5.7.1比較指標說明 148 5.7.2晶片性能 149 5.7.3綜合比較 151 5.8 第五章總結 155 第六章 結論與展望 157 附錄 159 A.1 Base graph 1 (46x68) [3] 159 A.2 Base graph 2 (42x52) [3] 160 B.1 Polar sequence [3] 161 B.2 CRC polynomial [3] 162 參考文獻 163 | |
dc.language.iso | zh-TW | |
dc.title | 在5G網路下針對低密度奇偶校驗碼與極化碼之通用信度傳播解碼器設計與晶片實現 | zh_TW |
dc.title | Design and Chip Implementation of Unified Belief Propagation Based Decoder for LDPC and Polar Codes in 5G Networks | en |
dc.type | Thesis | |
dc.date.schoolyear | 108-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 蘇炫榮(Hsuan-Jung Su),吳安宇(An-Yeu Wu),趙啟超(Chi-Chao Chao) | |
dc.subject.keyword | 前向錯誤更正碼,低密度奇偶校驗碼,極化碼,信度傳播,遺傳演算法, | zh_TW |
dc.subject.keyword | forward error correction codes (FEC),low-density parity-check (LDPC) code,polar code,belief propagation (BP),genetic algorithm, | en |
dc.relation.page | 168 | |
dc.identifier.doi | 10.6342/NTU202002890 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2020-08-19 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1108202004432900.pdf 目前未授權公開取用 | 10.19 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。