錯誤更正碼設計
錯誤更正碼（Error Correction Code）
錯誤更正碼（Error Correction Code）
在現代通訊系統中，為了讓硬體能夠達到高可靠及高效率的傳輸能力，錯誤更正碼在其中就扮演著相當重要的角色，主要目的是確保資料傳輸時的正確性。錯誤更正碼的原理是在原始資料中額外加入冗餘資料（Redundancy），利用這些額外的資料與原始資料的關係，來修正傳輸中資料遭受干擾所產生的錯誤。修正錯誤的能力與額外加上的冗餘資料多寡有關，一般而言，加入的冗餘資料越多，可修正的錯誤也越多。而早期錯誤更正碼的編碼方式比較簡單，例如：漢明碼、迴旋碼…等，隨著時代的推進，以及為了因應更多的需求，新的錯誤更正碼持續被提出，其中像是渦輪碼(Turbo Code)、低密度同位檢查碼（Low-Density Parity-Check，LDPC）及極化碼(Polar code)等，這些錯誤更正碼目前都被許多國家採用為先進數位通訊標準。近年來Polar code除了引起學術界的關注外，同時也廣受業界的青睞，其中像是中國在2016年積極地推廣Polar Code成為未來5G無線通訊的標準之一。
在現代通訊系統中，為了讓硬體能夠達到高可靠及高效率的傳輸能力，錯誤更正碼在其中就扮演著相當重要的角色，主要目的是確保資料傳輸時的正確性。錯誤更正碼的原理是在原始資料中額外加入冗餘資料（Redundancy），利用這些額外的資料與原始資料的關係，來修正傳輸中資料遭受干擾所產生的錯誤。修正錯誤的能力與額外加上的冗餘資料多寡有關，一般而言，加入的冗餘資料越多，可修正的錯誤也越多。而早期錯誤更正碼的編碼方式比較簡單，例如：漢明碼、迴旋碼…等，隨著時代的推進，以及為了因應更多的需求，新的錯誤更正碼持續被提出，其中像是渦輪碼(Turbo Code)、低密度同位檢查碼（Low-Density Parity-Check，LDPC）及極化碼(Polar code)等，這些錯誤更正碼目前都被許多國家採用為先進數位通訊標準。近年來Polar code除了引起學術界的關注外，同時也廣受業界的青睞，其中像是中國在2016年積極地推廣Polar Code成為未來5G無線通訊的標準之一。
(圖片來源: 科技新報)
(圖片來源: 科技新報)
極化碼（Polar Code）
極化碼（Polar Code）
極化碼是在2007年由E. Arikan所提出的一種通道編碼理論，該理論的編碼增益相當接近對稱二位元輸入離散無記憶通道（Symmetric Binary-input Discrete Memoryless Channel，B-DMC）的通道容量。極化碼的通道會隨著編碼位元數的提升而產生極化現象，而通道極化是指編碼位元數無限大時有部份通道容量接近1，其他通道容量接近0，因此可以在通道容量接近1的通道上傳送資料位元，通道容量接近0的通道上傳送冗餘位元。而極化碼具備較低的編解碼需求、線性複雜度以及優越的通道性能，使得它近年在通道編碼領域中備受矚目。
極化碼是在2007年由E. Arikan所提出的一種通道編碼理論，該理論的編碼增益相當接近對稱二位元輸入離散無記憶通道（Symmetric Binary-input Discrete Memoryless Channel，B-DMC）的通道容量。極化碼的通道會隨著編碼位元數的提升而產生極化現象，而通道極化是指編碼位元數無限大時有部份通道容量接近1，其他通道容量接近0，因此可以在通道容量接近1的通道上傳送資料位元，通道容量接近0的通道上傳送冗餘位元。而極化碼具備較低的編解碼需求、線性複雜度以及優越的通道性能，使得它近年在通道編碼領域中備受矚目。
◎ 編碼 (Encode)
◎ 編碼 (Encode)
極化碼的編碼主要是利用極化現象來建構編碼系統產生編碼規則，對屬於線性區塊碼（Linear Block Code）的極化碼來說，編碼結果可由原始資料與生成矩陣做矩陣乘法後得到。其中GN表示基礎矩陣做n次的克羅內克積（Kronecker Product）運算。
極化碼的編碼主要是利用極化現象來建構編碼系統產生編碼規則，對屬於線性區塊碼（Linear Block Code）的極化碼來說，編碼結果可由原始資料與生成矩陣做矩陣乘法後得到。其中GN表示基礎矩陣做n次的克羅內克積（Kronecker Product）運算。
(圖一) 碼長為8的編碼架構圖
(圖一) 碼長為8的編碼架構圖
◎ 解碼演算法 (Decode Algorithm)
◎ 解碼演算法 (Decode Algorithm)
極化碼有兩種解碼演算法：連續消除（Successive Cancellation，SC）演算法與置信傳遞（Belief Propagation，BP）演算法。其中連續消除演算法採用遞迴（Recursion）的概念進行解碼，其優點為複雜度低；而置信傳遞演算法則採用迭代（Iterative）的概念進行解碼，其優點為可明確知道解碼序列的正確性。以下將對連續消除演算法做解碼運算的說明，基於以下公式此演算法會連續性的去估計u0到uN-1這些所傳送的位元：
極化碼有兩種解碼演算法：連續消除（Successive Cancellation，SC）演算法與置信傳遞（Belief Propagation，BP）演算法。其中連續消除演算法採用遞迴（Recursion）的概念進行解碼，其優點為複雜度低；而置信傳遞演算法則採用迭代（Iterative）的概念進行解碼，其優點為可明確知道解碼序列的正確性。以下將對連續消除演算法做解碼運算的說明，基於以下公式此演算法會連續性的去估計u0到uN-1這些所傳送的位元：
下圖為連續消除演算法的解碼流程圖，它是利用兩種不同型態的處理節點，並且以序向的方式來進行節點更新，分別是以f節點與g節點來進行對數似然比（Log-Likelihood Ratio，LLR）資料的運算。
下圖為連續消除演算法的解碼流程圖，它是利用兩種不同型態的處理節點，並且以序向的方式來進行節點更新，分別是以f節點與g節點來進行對數似然比（Log-Likelihood Ratio，LLR）資料的運算。
(圖二) 連續消除解碼流程
(圖二) 連續消除解碼流程
下圖為置信傳遞演算法的解碼流程圖(俗稱Factor Graph)，它僅使用一種型態的處理節點，並且以平行的方式來進行節點更新，主要是以f節點來進行資料的運算。
下圖為置信傳遞演算法的解碼流程圖(俗稱Factor Graph)，它僅使用一種型態的處理節點，並且以平行的方式來進行節點更新，主要是以f節點來進行資料的運算。
(圖三) 置信傳遞解碼流程
(圖三) 置信傳遞解碼流程
◎ LLR資料位元數之效能模擬與分析
◎ LLR資料位元數之效能模擬與分析
Polar code的解碼流程圖可以被劃分成log2N個Stage，且經過每個Stage的節點運算後LLR資料可能超出前一級LLR資料位元數所能表示的範圍，特別是g節點的運算。在一般硬體設計上可能採用足夠的位元數來表示LLR資料，舉例來說，當碼長為1024時，解碼流程圖可以被劃分成10個Stage，若要完整表示10個Stage運算完的結果，需使用13個位元來表示一筆LLR資料。透過MATLAB模擬來比較一般浮點數的解碼運算以及被提出的固定位元數之飽和運算，所謂的飽和運算是指當運算結果超出位元數可表示的範圍，則使用最大值或最小值來做為最後的運算結果。
Polar code的解碼流程圖可以被劃分成log2N個Stage，且經過每個Stage的節點運算後LLR資料可能超出前一級LLR資料位元數所能表示的範圍，特別是g節點的運算。在一般硬體設計上可能採用足夠的位元數來表示LLR資料，舉例來說，當碼長為1024時，解碼流程圖可以被劃分成10個Stage，若要完整表示10個Stage運算完的結果，需使用13個位元來表示一筆LLR資料。透過MATLAB模擬來比較一般浮點數的解碼運算以及被提出的固定位元數之飽和運算，所謂的飽和運算是指當運算結果超出位元數可表示的範圍，則使用最大值或最小值來做為最後的運算結果。
(圖四) 一般浮點運算與飽和運算錯誤率比較
(圖四) 一般浮點運算與飽和運算錯誤率比較
◎ 硬體架構設計
◎ 硬體架構設計
此硬體架構提出具有低解碼週期、低成本與高吞吐量的解碼器架構，其設計重點在於使用四組記憶體模組作為資料的存取，接著再以處理單元陣列依序完成節點的運算，如圖所示為連續消除解碼器的半平行化架構設計。
此硬體架構提出具有低解碼週期、低成本與高吞吐量的解碼器架構，其設計重點在於使用四組記憶體模組作為資料的存取，接著再以處理單元陣列依序完成節點的運算，如圖所示為連續消除解碼器的半平行化架構設計。
(圖五) 連續消除解碼器的半平行化架構設計
(圖五) 連續消除解碼器的半平行化架構設計
◎ 實作結果
◎ 實作結果
(圖六) 完成APR流程之晶片布局圖
(圖六) 完成APR流程之晶片布局圖
(圖七) (1024, 512) SC Polar decoder experimental result
(圖七) (1024, 512) SC Polar decoder experimental result