二元域上有限幾何LDPC碼的停止距離

高 有，馬 赫

（中國民航大學(xué)理學(xué)院，天津 300300）

LDPC[1]（low density parity check）碼因其接近香農(nóng)限的良好性能而受到廣泛關(guān)注。在研究和分析LDPC碼在二元擦除信道上的譯碼表現(xiàn)時(shí)，發(fā)現(xiàn)其主要取決于校驗(yàn)陣中一種特殊的組合結(jié)構(gòu)，即停止集[2]。

設(shè)一個(gè)線性碼C 具有校驗(yàn)陣H，停止集是校驗(yàn)陣H 中某些列的列標(biāo)集合，使得校驗(yàn)陣由這些列所構(gòu)成的子矩陣沒有Hamming 重量為1 的行，最小的非空停止集的大小為停止距離。最小Hamming 距離對于研究一個(gè)碼在二元對稱信道上的譯碼表現(xiàn)有很重要的作用。類似的，停止距離對于研究碼在二元擦除信道上進(jìn)行一些迭代譯碼的表現(xiàn)同樣重要。

構(gòu)造LDPC 碼的方式有很多，其中通過有限幾何來構(gòu)造LDPC 碼是一類重要的方法。Kou 等[3]利用有限幾何中仿射空間與射影空間這兩類空間中的點(diǎn)和線構(gòu)造了性能很好的LDPC 碼，并計(jì)算了碼的最小Hamming 距離等參數(shù)。一個(gè)線性碼的校驗(yàn)陣對應(yīng)一個(gè)Tanner 圖，圖中最小圈的長稱為圍長，圍長至少為6的正規(guī)LDPC 碼其譯碼表現(xiàn)會(huì)更好。Tang 等[4]進(jìn)一步基于有限幾何中的flat 構(gòu)造了碼，其適用于很多的譯碼方法，如大數(shù)邏輯譯碼法、和積算法、置信傳播法等，而這樣構(gòu)造的有限幾何LDPC 碼（FG-LDPC）通常會(huì)有很多長為4 的圈，其譯碼表現(xiàn)結(jié)果出乎意料。Kashyap 等[5]給出了基于組合設(shè)計(jì)所構(gòu)造碼的停止距離的下界，其結(jié)論可應(yīng)用于有限幾何構(gòu)造的碼。Xia等[6]進(jìn)一步研究了有限幾何LDPC 碼停止距離的下界。

對于已有的基于二元域上仿射空間與射影空間中的μ-flat 和（μ+1）-flat 所構(gòu)造的PDPC 碼可找到一個(gè)停止集，其大小達(dá)到了有限幾何LDPC 碼停止距離所滿足的下界，由此得出了這一類有限幾何LDPC 碼的停止距離。

1 停止距離及FG-LDPC 碼簡介

對于停止集及停止距離，下面給出具體的定義[6]。

定義1設(shè)C 是一個(gè)具有校驗(yàn)陣H 的[n，k]線性碼，H 的行不是線性無關(guān)的。一個(gè)停止集S 是關(guān)于H的列標(biāo){1，2，…，n}的子集，滿足由H 的這些列構(gòu)成的子矩陣沒有Hamming 重量為1 的行。

定義2最小的非空停止集的大小稱為停止距離，記為s（H）。為了方便計(jì)算，對于停止距離還有另一種定義方式：設(shè)C 是一個(gè)具有校驗(yàn)陣H 的[n，k]線性碼，停止距離s（H）是滿足如下條件的最大的正整數(shù)，從H 中選出任意不超過s（H）-1 列構(gòu)成的子矩陣至少有一行Hamming 重量為1。

仿射空間和射影空間[7]是有限幾何中重要的兩類，現(xiàn)對其簡單介紹：

Fq是一個(gè)含有q 個(gè)元素的有限域（q 是一個(gè)素?cái)?shù)的冪）。設(shè)AG（m，q）和PG（m，q）分別是Fq上的仿射空間和射影空間，統(tǒng)記為有限幾何FG（m，q），由flat 組成。對0≤μ≤m，一個(gè)AG（m，q）中的μ-flat 是向量空間中的μ 維子空間或其陪集，一個(gè)PG（m，q）中的μ-flat 是向量空間中的μ +1 維子空間。特別的0-flat 和1-flat 分別代表FG（m，q）中的點(diǎn)和線。

在仿射空間和射影空間中有如下的計(jì)數(shù)定理[8]：AG（m，q）和PG（m，q）中μ-flat 個(gè)數(shù)分別記為NAG（μ，m，q）和NPG（μ，m，q），對0≤μ1＜μ2≤m 設(shè)NAG（μ1，μ2，m，q）和NPG（μ1，μ2，m，q）分別為AG（m，q）和PG（m，q）中給定μ2-flat 中的μ1-flat 的個(gè)數(shù)，N′AG（μ1，μ2，m，q）和N′PG（μ1，μ2，m，q）分別為AG（m，q）和PG（m，q）中包含給定μ1-flat 的μ2-flat 的個(gè)數(shù)?，F(xiàn)簡記N（μ1，m，q），N（μ2，m，q）分別為有限幾何FG（m，q）中的μ1-flat 和μ2-flat 的個(gè)數(shù)，N（μ1，μ2，m，q）為給定μ2-flat 包含的μ1-flat 的個(gè)數(shù)，N′（μ1，μ2，m，q）為包含給定μ1-flat 的μ2-flat 的個(gè)數(shù)。根據(jù)flat 的可遷性有

其中，高斯系數(shù)[7]為

當(dāng)μ1=0 時(shí)。

有限幾何LDPC 碼的介紹如下：

對0≤μ1＜μ2≤m，設(shè)n=N（μ1，m，q），J=N（μ2，m，q）。對于一個(gè)二元J×n 矩陣H(1)（μ1，μ2，m，q）=（hji），其行對應(yīng)有限幾何FG（m，q）中的μ2-flat，列對應(yīng)μ1-flat。當(dāng)?shù)趈 個(gè)μ2-flat 包含第i 個(gè)μ1-flat 時(shí)hji=1，否則hji=0。設(shè)H(1)（μ1，μ2，m，q）的轉(zhuǎn)置為H(2)（μ1，μ2，m，q），則以H(1)（μ1，μ2，m，q）和H(2)（μ1，μ2，m，q）為校驗(yàn)陣的碼稱為有限幾何LDPC 碼，分別記為C(1)（μ1，μ2，m，q）和C(2)（μ1，μ2，m，q）。由有限幾何的性質(zhì)[7]，易發(fā)現(xiàn)只有當(dāng)μ2=μ1+1 時(shí)，校驗(yàn)陣H(1)（μ1，μ2，m，q）和H(2)（μ1，μ2，m，q）的圍長為6，其余情況均為4。

設(shè)碼C(1)（μ1，μ2，m，q）和C(2)（μ1，μ2，m，q）所對應(yīng)校驗(yàn)陣H(1)（μ1，μ2，m，q）和H(2)（μ1，μ2，m，q）的停止距離分別記為s（H）和s（HT）。根據(jù)文獻(xiàn)[6]可知：對C(1)（μ1，μ2，m，q），s（H）≥N′（μ2-1，μ2，m，q）+1；對C(2)（μ1，μ2，m，q），s（HT）≥N（μ1，μ1+1，m，q）+1。

一個(gè)碼的停止集和停止距離是與校驗(yàn)陣相關(guān)的，因此，停止距離不能超過一個(gè)碼的最小Hamming 距離[8]。上述的有限幾何LDPC 碼在一些特殊情況下，最小距離已知。如文獻(xiàn)[3]得出了點(diǎn)與線構(gòu)造的LDPC 碼的最小距離，且在仿射空間中構(gòu)造的碼C(1)（0，μ2，m，2）（其中μ2＞1）是μ2-1 階的Reed-Muller 碼[9]，而Reed-Muller 碼的最小距離也已知，同樣易得出上述情況下碼的停止距離。

2 碼C(1)（μ，μ+1，m，2）的停止距離

為得到有限幾何FG（m，2）上碼C(1)（μ，μ + 1，m，2）（其中0≤μ ＜μ + 1≤m）關(guān)于校驗(yàn)陣H(1)（μ，μ + 1，m，2）的停止距離s（H），首先給出如下引理。

引理1設(shè)e1，e2，…，em是二元域F2上向量空間的一組基（ei的第i 個(gè)位置為1，其余位置為0，i=1，2，…，m）則：

1）由eμ+1，eμ+2，…，em的線性組合構(gòu)成的兩兩線性無關(guān)的非零向量共有M=2m-μ-1 個(gè)，記為a1，a2，…，aM；

2）向量組{e1+a1，e1+a2，…，e1+aM}中任意3 個(gè)向量線性無關(guān)。

對引理1 中的2）的證明如下：設(shè)向量組A={e1+a1，e1+a2，…，e1+aM}，假設(shè)A 中存在3 個(gè)向量線性相關(guān)，不妨設(shè)e1+ai∈A（i=1，2，…，M）可由向量e1+aj，e1+ak∈A（1≤i≠j≠k≤M）線性表示，于是在二元域F2中必有

e1+ai=（e1+aj）+（e1+ak）=aj+ak而由引理1 中的1）可知a1，a2，…，aM，是由eμ+1，eμ+2，…，em構(gòu)成的兩兩線性無關(guān)的非零向量，矛盾。故向量組A 中任意3 個(gè)向量線性無關(guān)。

根據(jù)引理1 可得到如下引理。

引理2設(shè)e1，e2，…，em是向量空間中的一組F2的基，對0 ＜μ ＜μ + 1 ＜m，設(shè)如下矩陣表示

其中：M=2m-μ- 1；a1，a2，…，aM是由eμ+1，eμ+2，…，em的線性組合構(gòu)成的兩兩無關(guān)的非零向量，則V1，V2，…，VM中的任意兩個(gè)均包含在一個(gè)μ + 1 維子空間中，共有個(gè)不同的μ + 1 維子空間。

由維數(shù)公式可知：dim（Vi∪Vj）=dim（Vi）+dim（Vj）-dim（Vi∩Vj）=μ+1。

故V1，V2，…，VM中的任意兩個(gè)均包含在一個(gè)μ +1 維子空間中且最多有個(gè)。

對任意的Vi，Vj，Vk，Vl，不妨令i≠j，k，l 且k≠l，設(shè)包含Vi，Vj的μ+1 維子空間為U1，包含Vk，Vl的μ +1 維子空間為U2，可寫出具體的矩陣表示為

為證明U1，U2是不同的μ+1 維子空間，只需證e1+ai不能由U2線性表示，根據(jù)向量的形式及引理1 的結(jié)論，易看出e1+ai不能由U2線性表示，即U1，U2是不同的μ+1 維子空間。故這個(gè)μ+1 維子空間互不相同。

根據(jù)以上引理得出主要結(jié)果：

定理1對于有限幾何FG（m，2）上的碼C(1)（μ，μ +1，m，2）（0≤μ ＜μ + 1≤m）關(guān)于校驗(yàn)陣H(1)（μ，μ +1，m，2）的停止距離s（H）=2m-μ。

證明：當(dāng)μ =0 或μ +1 =m 時(shí)，由文獻(xiàn)[6]可知結(jié)論成立；當(dāng)0 ＜μ ＜μ+1 ＜m 時(shí)，根據(jù)文獻(xiàn)[6]及以上的計(jì)數(shù)定理有結(jié)論：s（H）≥N′（μ，μ + 1，m，2）+1=2m-μ。

故對于碼C(1)（μ，μ + 1，m，2）的校驗(yàn)陣H(1)（μ，μ +1，m，2）只需找到一個(gè)大小為2m-μ的停止集即可。

下面在射影空間中進(jìn)行討論：

包含V 的μ + 2 維子空間共有M=N′（μ + 1，μ +2，m，2）=2m-μ-1 個(gè)，于是可將包含V 的μ + 2 的維子空間表示為

其中，a1，a2，…，aM是由eμ+2，eμ+3，…，em+1，的線性組合構(gòu)成的兩兩無關(guān)的非零向量，顯然U1，U2，…，UM均包含V 且兩兩不相同。從每個(gè)U1，U2，…，UM中選出一個(gè)包含在其中的μ+1 維子空間，可表示為

由引理2 可知V1，V2，…，VM中的任意兩個(gè)均包含在一個(gè)μ + 2 維子空間中，共有個(gè)且互不相同，于是V1，V2，…，VM，V 中任意兩個(gè)均包含在一個(gè)μ + 2 維子空間中，且這些μ + 2 維子空間互不相同。而在射影空間PG（m，2）中，μ-flat 和（μ + 1）-flat 分別代表向量空間中的μ + 1 維子空間和μ + 2 維子空間。校驗(yàn)陣H(1)（μ，μ+1，m，2）的行和列分別對應(yīng)（μ+1）-flat和μ-flat，于是按照上面選取的子空間即μ-flat 可從H(1)（μ，μ + 1，m，2）中選出相應(yīng)的列構(gòu)成子矩陣，其沒有

中的μ 維子空間用Hamming 重為1 的行，即存在大小為2m-μ的停止集。

類似地，對于仿射空間AG（m，2）仍然可找到大小為2m-μ的停止集。

綜上所述，C(1)（μ，μ + 1，m，2）的停止距離s（H）=2m-μ。

3 結(jié)語

文獻(xiàn)[6]得到了有限幾何LDPC 碼的停止距離的下界，利用其已有結(jié)論，并通過對仿射空間與射影空間中一些flat 具體形式的刻畫，對應(yīng)到碼的校驗(yàn)陣中可找到一個(gè)大小達(dá)到停止距離下界的停止集，從而得出了某些特殊情況下二元域上有限幾何LDPC 碼的停止距離。