透過您的圖書館登入
IP:52.205.159.48
  • 學位論文

針對第五代行動通訊極化碼的高效率且基於基因演算法的置信度傳播解碼器之設計

Design of an Efficient Genetic-based Belief Propagation Decoder for 5G NR Polar Codes

指導教授 : 闕志達

摘要


近年來隨著科技的進步與時代的演進,人們對於高可靠度和低延遲通訊的需求日益提升,前向錯誤更正碼(FEC)也因此成為現代通訊不可或缺的技術之一。極化碼是第一個經數學證明解碼的表現可以達到香農極限的錯誤更正碼,在5G系統中的增強型行動寬頻通訊(eMBB)被採納拿來保護控制訊號。目前公認解碼表現最好的演算法為利用循環冗餘校驗輔助的列表循序消除(CA-SCL)解碼器,然而,基於本身循序解碼的特性,具有高解碼延遲的問題,並且隨著傳輸的碼長越長越嚴重。極化碼還可以利用置信度傳播(Belief Propagation)的方式進行解碼,其為一種可全平行化的演算法,可以有效應用於低延遲與高吞吐量的通訊系統中。本論文主要研究基於置信度傳播的解碼器設計,一共有兩大研究方向,一是改善傳統置信度傳播解碼器的解碼表現,二是改善置信度傳播解碼器本身複雜度較大的問題。 在本論文中,我們使用另一種最佳化的演算法---基因演算法套用在置信度傳播的極化碼解碼過程中。借鑑於生物演化過程中的突變以及自然選擇,我們在傳統置信度傳播無法成功解碼時挑選更好的初始條件並執行位元翻轉,使置信度傳播能朝著正確的方向進行迭代,因此能找到傳統方法所無法成功解碼的結果,經模擬顯示其解碼性能可以與CA-SCL (L=8)相當,並且仍保有天生平行的優勢。 然而,由於置信度傳播平行化解碼的特性,與基於循序消除的解碼器相比有複雜度較高的問題。本論文借鑑於深度學習中調整梯度的想法,提出加速演算法,在傳統置信度傳播的迭代過程中加入了加速參數,改善傳統算法的收斂速度,並因此降低了平均迭代次數,也同時降低了複雜度及解碼延遲。另外,我們透過觀察置信度傳播迭代過程中,因子圖(factor graph)中對數似然比(Log Likehood Ratio,LLR)的變化,提出一新的指標,錯誤凍結位元數。透過這個指標,我們能掌握解碼的進度和狀況,當我們透過指標預判會發生解碼錯誤時,能在迭代初期的階段提前中止,避免置信度傳播消耗多餘的迭代次數卻無法得到正確的結果。 最後,我們挑選其他基於置信度傳播的相關研究進行比較,探討不同解碼方法的解碼表現、複雜度以及解碼延遲。

並列摘要


With the advancement of science and technology, people’s demand for ultra high-reliability and low-latency communications has increased. Forward error correction codes (FEC) have become one of the indispensable technologies for modern communication systems. Among them, polar codes are the first error correction codes that have been proven to achieve channel capacity. Given this, polar codes have been adopted in Enhanced Mobile Broadband Communication (eMBB), one of the 5G use cases, to protect control channels. At present, it is recognized that the best decoding algorithm is the cyclic redundancy check assisted successive cancellation list (CA-SCL) decoder. However, based on its intrinsic sequential decoding characteristics, it has high decoding latency, and with the transmission of the longer code length, the more serious it is. Polar codes can also be decoded by Belief Propagation (BP), which is a fully parallelizable algorithm that can be effectively applied to low-latency and high-throughput decoding. This thesis focuses on the design of 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, and the other is to improve the high-complexity issue of BP based decoder. In this thesis, we apply the genetic algorithm to improve the decoding process of belief propagation. When the codes cannot be decoded successfully, we select a better initial codeword and perform bit-flipping, making the iterative process more effective in finding the optimal solution that conventional methods cannot. Simulation results show that the decoding performance of the proposed method can be comparable to CA-SCL (L=8) while still maintaining the inherent parallel characteristic. However, due to the characteristics of the parallelized decoding of belief propagation, there is a problem of high complexity compared with decoders based on successive cancellation. We draw on the idea of adjusting gradients in deep learning and propose an acceleration algorithm. The acceleration scale is added to the iterative process of belief propagation to improve the convergence and reduce the average number of iterations. In addition, by observing the changes in Log-Likelihood Ratio (LLR) in the factor graph during iterations, we propose a new indicator, the number of error frozen bits. Through this indicator, we can grasp the progress and status of decoding. When we predict that decoding errors will occur through the indicator, we can terminate the decoding early, avoiding belief propagation consuming extra iterations but failing to produce the correct result. Finally, we select other BP-based decoding algorithms for comparison and discuss the decoding performance, complexity, and decoding latency.

參考文獻


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/.

延伸閱讀