線性分組碼的構造及其解碼算法

《線性分組碼的構造及其解碼算法》是依託揚州大學，由唐元生擔任項目負責人的面上項目。

基本介紹

• 中文名：線性分組碼的構造及其解碼算法
• 項目類別：面上項目
• 項目負責人：唐元生
• 依託單位：揚州大學

項目摘要

本項目主要研究具有高糾錯性能的線性分組碼的構造及其高效快速解碼算法的設計問題。利用代數、圖論以及組合數學等工具，提出具有較大圍長的LDPC碼的新的構造方法。根據平衡環的拓撲結構，通過確定包含平衡環的最小關聯矩陣，給出確定全部較短的平衡環的簡單方法。利用低階置換矩陣進行多次擴張，消除LDPC碼中的短環從而提高其圍長。針對一類在不降低糾錯性能的前提下可以大大降低解碼算法的計算複雜度的整數規劃問題，通過規劃問題的分裂，研究在參考向量的個數等於4，5，6時的快速求解問題。給出參考向量的選擇標準，進而套用於一些廣泛使用的解碼算法，降低其計算複雜度。針對Chase-型解碼算法，設計算法來計算或估計達到指定誤碼率所需搜尋中心的最小數目，並對達到限界距離解碼所需搜尋中心的最小數目進行估計，進而提出設計對碼長和信噪比都具備較大適用範圍的好的解碼算法。

結題摘要

本項目研究計畫已順利完成，具體如下： ① 我們通過對因子圖中平衡環的拓撲結構的研究，對平衡環進行了分類。通過確定包含平衡環的最小關聯矩陣，得到了一個計算和發現全部較短的平衡環的算法。提出了採用多次低階擴張的辦法消除這些較短的平衡環的一個有效算法。 ② 針對一類可用來對解碼算法設定加速條件的整數規劃問題（IPP），我們首先通過將其分裂成一些子規劃問題來簡化。當參考向量的個數為4時，可以把原IPP分裂成至多12個自變數個數減半的子規劃問題。當參考向量的個數為5時，原IPP可分裂成至多81個自變數個數減半的子規劃問題。關於這些子規劃問題的求解，我們將各子規劃問題的定義域適當劃分成一些小區，然後在各小區中適當選取一個種子，採用逐步修改種子的生長方向的辦法來找到各小區裡的最優解。 ③ 關於Chase型解碼算法，我們給出了達到限界距離解碼的一些條件。當搜尋中心的非零分量全部集中在不可靠的位置時，我們通過確定未搜尋區域內的最小向量，給出達到限界距離解碼的搜尋中心的最小數目的上界和下界，得到了目前最好的結果。