- 學位論文
一種針對極化碼的改良式置信度傳播解碼演算法與其硬體架構
A modified belief propagation algorithm and hardware architecture for polar codes
摘要
消息理論是由Claude Shannon在1948年提出。並且提出了通道容量限制又稱薛農極限(Shannon Limit)。其內容指出任何錯誤更正碼的錯誤率都不能超過薛農極限。因此後續不斷有許多學者投入這方面的研究，希望可以找到一種錯誤更正碼可以達到薛農極限。在1962年Gallager提出了低密度奇偶查核碼(Low Density Parity Check)。在1990年Mackay研究提出低密度奇偶查核碼的錯誤率可以接近薛農極限。極化碼是 Erdal Arikan 在 2007 年提出，他透過數學的方式推導出極化碼在碼長(Code Length)趨近於無限大時其錯誤率可以達到薛農極限(shannon limit)，因此極化碼的出現讓許多學者為其感到震驚與興奮。現今極化碼解碼演算法大致可分成逐次消除(successive-cancellation)演算法與置信度傳播(belief propagation)演算法。逐次消除(successive-cancellation)演算法的優點是其硬體複雜度較低，但是其缺點是一旦碼長(code length)變長，其吞吐量(throughput)會嚴重的受到限制。因此提出了置信度傳播(belief propagation)演算法。置信度傳播(belief propagation)演算法可以透過迭代與平行處理的概念能有效的解決逐次消除演算法中吞吐量對於碼長的限制，但其錯誤率相較於現今的改良後的逐次消除(successive-cancellation)演算法低，且複雜度較高。有鑑於此本論文提出透過改良式的置信度傳播演算法，此方法可以有效提升原置信度傳播演算法的錯誤更能力，又能保有其吞吐量，本論文提出之方法在信噪比(signal to noise ratio) SNR=4.5 dB 時其錯誤率可以下降約 20 倍，且吞吐量的減少約只有原來的 3.32%，硬體面積增加約為原來的 4.8% 。
並列摘要
Polar codes were proposed by Erdal Arikan in 2007. He showed that the error correction capability can achieve the Shannon limit when the code length achieves to infinity. Today the polar decoding algorithm can be roughly divided into two classes, i.e., the successive cancellation algorithm and the belief propagation algorithm. Owing to the sequential of the successive cancellation algorithm its hardware complexity is low. When the code length becomes longer, the throughput becomes lower. In order to mitigate this problem, the belief propagation algorithm was proposed. The belief propagation algorithm can mitigate this problem by using the concept of iteration and parallel processing; However its error correction capability is slightly worse than the successive cancellation algorithm. In the thesis, we proposed a modify belief propagation algorithm by using the inversion function. Simulation results show that the throughput of the proposed algorithm loses $3.32\%$ and the hardware area increases $4.8\%$, but the frame error rate is $20$ times better than the original belief propagation algorithm when the signal to noise ratio is $4.5$ dB.