利用分群演算法分析低密度奇偶檢查碼的結構

Abstract

低密度奇偶檢查碼 (Low-density parity check codes, LDPC codes) 可以透過奇偶檢驗矩陣 (parity-check matrix) 表示，奇偶檢驗矩陣能夠利用 Tanner graph 圖形化顯示，但是效能好的碼從 Tanner graph 觀察不具有特定的結構特性。 本文利用分群演算法分析低密度奇偶檢查碼的結構，利用馬可夫分群演算法 (Markov cluster algorithm) 與模組性分群演算法 (Modularity cluster algorithm) 將 LDPC codes 的 nodes 分類，找到容易形成陷阱集合 (trapping set) 的小 cluster；並且透過網路參數 (Network parameter) 找出與 LDPC codes 解碼過程相關的參數。

Low-density parity-check (LDPC) codes are defined by a sparse parity-check matrix and can described by tanner graph. But there is no structural property to confirm the performance. We use clustering algorithm to analyze the structure of LDPC codes. We use Markov Cluster Algorithm and Modularity cluster algorithm to group the node of LDPC codes. We find that the small clusters have higher probability to be the trapping set. Also, we find some network parameter can explain the decoding process of LDPC codes.