高 有，馬 赫

（中國民航大學理學院，天津 300300）

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

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

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

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

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

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

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

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

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

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

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

其中，高斯系數[7]為

當μ1=0 時。

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

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

設碼C(1)（μ1，μ2，m，q）和C(2)（μ1，μ2，m，q）所對應校驗陣H(1)（μ1，μ2，m，q）和H(2)（μ1，μ2，m，q）的停止距離分別記為s（H）和s（HT）。根據文獻[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。

一個碼的停止集和停止距離是與校驗陣相關的，因此，停止距離不能超過一個碼的最小Hamming 距離[8]。上述的有限幾何LDPC 碼在一些特殊情況下，最小距離已知。如文獻[3]得出了點與線構造的LDPC 碼的最小距離，且在仿射空間中構造的碼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）關于校驗陣H(1)（μ，μ + 1，m，2）的停止距離s（H），首先給出如下引理。

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

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

2）向量組{e1+a1，e1+a2，…，e1+aM}中任意3 個向量線性無關。

對引理1 中的2）的證明如下：設向量組A={e1+a1，e1+a2，…，e1+aM}，假設A 中存在3 個向量線性相關，不妨設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構成的兩兩線性無關的非零向量，矛盾。故向量組A 中任意3 個向量線性無關。

根據引理1 可得到如下引理。

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

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

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

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

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

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

根據以上引理得出主要結果：

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

證明：當μ =0 或μ +1 =m 時，由文獻[6]可知結論成立；當0 ＜μ ＜μ+1 ＜m 時，根據文獻[6]及以上的計數定理有結論：s（H）≥N′（μ，μ + 1，m，2）+1=2m-μ。

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

下面在射影空間中進行討論：

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

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

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

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

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

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

3 結語

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