請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/79659完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 闕志達(Tzi-Dar Chiueh) | |
| dc.contributor.author | Yu-Wei Lin | en |
| dc.contributor.author | 林祐葳 | zh_TW |
| dc.date.accessioned | 2022-11-23T09:06:40Z | - |
| dc.date.available | 2021-09-17 | |
| dc.date.available | 2022-11-23T09:06:40Z | - |
| dc.date.copyright | 2021-09-17 | |
| dc.date.issued | 2021 | |
| dc.date.submitted | 2021-09-07 | |
| dc.identifier.citation | 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. 23, 2021]. ITU-R M.2083-0 IMT Vision – Framework and overall objectives of the future development of IMT for 2020 and beyond. TS38.212V.16.2.0.[Online].Available:https://www.3gpp.org/ftp/Specs/archive/38series/38.212/.[Accessed June. 23, 2021]. ETSI, “Why do we need 5G,” etsi.org, para. 3. [Online]. Available: https://www.etsi.org/technologies-clusters/technologies/5g. [Accessed June. 23, 2021]. “Technical Specification Group Radio Access Network,” 3GPP, 2018, TS38.212V.15.1.1. [Online]. Available:http://www.3gpp.org/ftp/Specs/archive/38 series/38.212/. 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. 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. 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. 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. I. Tal and A. Vardy, “List Decoding of Polar Codes,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213-2226, May 2015. K. Niu and K. Chen, “CRC-Aided Decoding of Polar Codes,” IEEE Communications Letters, vol. 16, no. 10, pp. 1668-1671, October 2012. E. Arikan, “Polar Codes: A Pipelined Implementation,” in Proc. of 4th Int. Symp. on Broad. Commun. ISBC 2010, pp. 11-14, July 2010. G. D. Forney, “Codes on Graphs: Normal Realizations.” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 520-548, Feb. 2001. 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. 2014. “Final report of 3GPP RAN1 ad-hoc NR1 meeting,” Tech. Rep., 3GPP, Spokane, WA, US, Jan. 2017. 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, Sep. 2011, pp. 1–4. P. Trifonov, “Efficient Design and Decoding of Polar Codes,” IEEE Transactions on Communications, vol. 60, no. 11, pp. 3221-3227, Nov. 2012. G. He, et al., “Beta-Expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes,” IEEE Global Communications Conference (GLOBECOM), Singapore, Dec. 2017, pp. 1-6. A. Elkelesh, M. Ebada, S. Cammerer, and S. T. Brink, “Belief Propagation Decoding of Polar Codes on Permuted Factor Graphs,” IEEE Wireless Commun. Netw. Conf. (WCNC), Apr. 2018, pp. 1–6. N. Doan, S. A. Hashemi, M. Mondelli and W. J. Gross, “On the Decoding of Polar Codes on Permuted Factor Graphs,” IEEE Global Communications Conference (GLOBECOM), Abu Dhabi, United Arab Emirates, Dec. 2018, pp. 1-6. A. Elkelesh, M. Ebada, S. Cammerer, and S.T.Brink, “Belief Propagation List Decoding of Polar Codes,” IEEE Commun. Lett., vol. 22, no. 8, pp. 1536-1539, Aug. 2018. M. Geiselhart, A. Elkelesh, M. Ebada, S. Cammerer and S. ten Brink, “CRC-Aided Belief Propagation List Decoding of Polar Codes,” IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, Jun. 2020, pp. 395-400. B. Li, B. Bai, M. Zhu and S. Zhou, “Improved Belief Propagation List Decoding for Polar Codes,” IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, 2020, pp. 1-6. Y. Yu, Z. Pan, N. Liu and X. You, “Belief Propagation Bit-Flip Decoder for Polar Codes,” IEEE Access, vol. 7, pp. 10937-10946, Jan. 2019. Y. Shen, W. Song, Y. Ren, H. Ji, X. You and C. Zhang, “Enhanced Belief Propagation Decoder for 5G Polar Codes With Bit-Flipping,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 67, no. 5, pp. 901-905, May 2020. J. Zhang and M. Wang, “Belief Propagation Decoder With Multiple Bit-Flipping Sets and Stopping Criteria for Polar Codes,” IEEE Access, vol. 8, pp. 83710-83717, Apr. 2020. Z. Zhang, K. Qin, L. Zhang and G. T. Chen, “Progressive Bit-Flipping Decoding of Polar Codes: A Critical-Set Based Tree Search Approach,” IEEE Access, vol. 6, pp. 57738-57750, Oct. 2018. 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. 2015. 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, Jul. 2019. Holland, John Henry. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992. J.F. Gonc ̧alves, J.J.M. Mendes, M.G.C. Resende, “A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem.” European Journal of Operational Research, vol. 167, no. 1, pp. 77–95, Nov. 2005. A. Eslami, and H. Pishro-Nik. “On Finite-length Performance of Polar Codes: Stopping Sets, Error Floor, and Concatenated Design.” IEEE Transactions on communications, vol. 61, no. 3, pp. 919-929, Mar. 2013. M. Rekha, “The Ascent of Gradient Descent,” Sep. 2019. [Online]. Available: https://blog.clairvoyantsoft.com/the-ascent-of-gradient-descent-23356390836f. [Accessed Jul. 3, 2021]. J. Jordan, “Setting the Learning Rate of your Neural Network,” Mar. 2018. [Online]. Available: https://www.jeremyjordan.me/nn-learning-rate/ [Accessed Jul. 3, 2021]. S. Sun, S. Cho and Z. Zhang, “Error Patterns in Belief Propagation Decoding of Polar Codes and their Mitigation Methods,” in 50th Asilomar Conference on Signals, Systems and Computers, Nov. 2016, pp. 1199-1203. C. Simsek and K. Turk, “Simplified Early Stopping Criterion for Belief-Propagation Polar Code Decoders,” IEEE Communications Letters, vol. 20, no. 8, pp. 1515-1518, Aug. 2016. Y. Yan, X. Zhang and B. Wu, “Simplified Early Stopping Criterion for Belief-Propagation Polar Code Decoder Based on Frozen Bits,” IEEE Access, vol. 7, pp. 134691-134696, Sep. 2019. Y. Wang, S. Zhang, C. Zhang, X. Chen and S. Xu, “A Low-Complexity Belief Propagation Based Decoding Scheme for Polar Codes - Decodability Detection and Early Stopping Prediction,” IEEE Access, vol. 7, pp. 159808-159820, Oct. 2019. C. Leroux, I. Tal, A. Vardy and W. J. Gross, “Hardware Architectures for Successive Cancellation Decoding of Polar Codes,” IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2011, pp. 1665-1668. Y. S. Park, Y. Tao, S. Sun and Z. 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. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/79659 | - |
| dc.description.abstract | 近年來隨著科技的進步與時代的演進，人們對於高可靠度和低延遲通訊的需求日益提升，前向錯誤更正碼(FEC)也因此成為現代通訊不可或缺的技術之一。極化碼是第一個經數學證明解碼的表現可以達到香農極限的錯誤更正碼，在5G系統中的增強型行動寬頻通訊(eMBB)被採納拿來保護控制訊號。目前公認解碼表現最好的演算法為利用循環冗餘校驗輔助的列表循序消除(CA-SCL)解碼器，然而，基於本身循序解碼的特性，具有高解碼延遲的問題，並且隨著傳輸的碼長越長越嚴重。極化碼還可以利用置信度傳播(Belief Propagation)的方式進行解碼，其為一種可全平行化的演算法，可以有效應用於低延遲與高吞吐量的通訊系統中。本論文主要研究基於置信度傳播的解碼器設計，一共有兩大研究方向，一是改善傳統置信度傳播解碼器的解碼表現，二是改善置信度傳播解碼器本身複雜度較大的問題。 在本論文中，我們使用另一種最佳化的演算法---基因演算法套用在置信度傳播的極化碼解碼過程中。借鑑於生物演化過程中的突變以及自然選擇，我們在傳統置信度傳播無法成功解碼時挑選更好的初始條件並執行位元翻轉，使置信度傳播能朝著正確的方向進行迭代，因此能找到傳統方法所無法成功解碼的結果，經模擬顯示其解碼性能可以與CA-SCL (L=8)相當，並且仍保有天生平行的優勢。 然而，由於置信度傳播平行化解碼的特性，與基於循序消除的解碼器相比有複雜度較高的問題。本論文借鑑於深度學習中調整梯度的想法，提出加速演算法，在傳統置信度傳播的迭代過程中加入了加速參數，改善傳統算法的收斂速度，並因此降低了平均迭代次數，也同時降低了複雜度及解碼延遲。另外，我們透過觀察置信度傳播迭代過程中，因子圖(factor graph)中對數似然比(Log Likehood Ratio，LLR)的變化，提出一新的指標，錯誤凍結位元數。透過這個指標，我們能掌握解碼的進度和狀況，當我們透過指標預判會發生解碼錯誤時，能在迭代初期的階段提前中止，避免置信度傳播消耗多餘的迭代次數卻無法得到正確的結果。 最後，我們挑選其他基於置信度傳播的相關研究進行比較，探討不同解碼方法的解碼表現、複雜度以及解碼延遲。 | zh_TW |
| dc.description.provenance | Made available in DSpace on 2022-11-23T09:06:40Z (GMT). No. of bitstreams: 1 U0001-0209202101090400.pdf: 9769935 bytes, checksum: a96ec76d7ea157caa95666d1de888dcc (MD5) Previous issue date: 2021 | en |
| dc.description.tableofcontents | 致謝 i 摘要 iii Abstract v 目錄 vii 圖目錄 xi 表目錄 xvi 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機 3 1.3 論文組織與貢獻 5 第二章 適用於5G-NR之極化碼介紹 7 2.1 極化碼 (Polar Codes) 7 2.1.1 簡介 7 2.1.2 通道極化 (Channel Polarization) 8 2.1.3 編碼方法 (Encoding) 9 2.1.4 解碼方法 (Decoding) 11 2.1.4.1 連續消除法(Successive Cancellation)[9] 12 2.1.4.2 列表連續消除法(Successive Cancellation List)[10] 13 2.1.4.3 循環冗餘校驗輔助列表連續消除法(CRC-aided SCL)[11] 14 2.1.4.4 置信度傳播(Belief Propagation)[12] 15 2.1.4.5 列表置信度傳播(Belief Propagation List) [19]-[23] 16 2.1.4.6 置信度傳播位元翻轉(Belief Propagation Bit-flip) [24]-[26] 17 2.1.5 演算法之性能比較 17 2.2 第二章總結 22 第三章 基於基因演算法之置信度傳播解碼器設計 24 3.1 基因演算法介紹 24 3.1.1 簡介 24 3.1.2 相關名詞解釋 25 3.1.3 流程 27 3.2 解碼器設計 28 3.2.1 基於基因演算法之置信度傳播 29 3.2.2 演算法之模擬與參數選擇 36 3.3 解碼流程改良與優化 40 3.3.1 刪除冗餘步驟 40 3.3.1.1 交配流程簡化 41 3.3.1.2 選擇流程簡化 43 3.3.2 優化突變模式 44 3.3.2.1 菁英選擇式突變法 45 3.3.2.2 使用翻轉集合輔助突變法 48 3.4 解碼性能模擬與複雜度分析 50 3.4.1 解碼性能 50 3.4.2 解碼延遲與複雜度分析 51 3.5 第三章總結 54 第四章 針對傳統置信度傳播提出加速演算法與提前中止機制之設計 56 4.1 加速演算法 56 4.1.1 動機與原理 57 4.1.2 解碼模擬與參數選擇 62 4.2 提前中止機制設計 71 4.2.1 置信度傳播解碼錯誤類型 71 4.2.2 解碼錯誤偵測 74 4.2.2.1 收斂型解碼錯誤 (Converged Decoding Error) 75 4.2.2.2 無法收斂型解碼錯誤 (Unconverged Decoding Error) 77 4.2.2.2.1 錯誤凍結位元數(Number of error frozen bit) 79 4.2.2.2.2 解碼錯誤偵測性能模擬 79 4.3 高效率之置信度傳播 86 4.3.1 解碼器設計 86 4.3.2 解碼性能模擬 88 4.4 第四章總結 89 第五章 高效率且基於基因演算法之置信度傳播解碼器參數分析與設計 91 5.1 高效率且基於基因演算法之置信度傳播 91 5.2 解碼器參數設計 94 5.2.1 加速常數選擇 94 5.2.2 適應度分數替換 96 5.2.3 基因演算法參數選擇 96 5.2.4 提前中止機制 98 5.3 解碼性能模擬 99 5.3.1 解碼性能分析 100 5.3.2 解碼延遲分析 101 5.3.3 解碼複雜度分析 103 5.4 第五章總結 105 第六章 結論與展望………………………………………………………………..106 附錄…………………………………………………………………………………108 7.1 A.1 CRC polynomial [3] 108 7.2 A.2 Polar sequence [3] 109 7.3 A.3 Interleaving pattern [3] 111 參考文獻……………………………………………………………………………112 | |
| dc.language.iso | zh-TW | |
| dc.title | 針對第五代行動通訊極化碼的高效率且基於基因演算法的置信度傳播解碼器之設計 | zh_TW |
| dc.title | Design of an Efficient Genetic-based Belief Propagation Decoder for 5G NR Polar Codes | en |
| dc.date.schoolyear | 109-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 蔡佩芸(Hsin-Tsai Liu),馬席彬(Chih-Yang Tseng),黃元豪 | |
| dc.subject.keyword | 前向錯誤更正碼,極化碼,置信度傳播,基因演算法,加速演算法,提前中止機制, | zh_TW |
| dc.subject.keyword | forward error correction codes,polar code,belief propagation,genetic algorithm,acceleration algorithm,early termination, | en |
| dc.relation.page | 116 | |
| dc.identifier.doi | 10.6342/NTU202102939 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2021-09-07 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-0209202101090400.pdf | 9.54 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。