摘要：首先利用有限幾何的特點構(gòu)造經(jīng)典低密度奇偶校驗(LDPC)矩陣，然后通過對校驗矩陣的行或列變換構(gòu)造其對偶碼，本文提出了一種以量子CSS碼為理論基礎(chǔ)的基于有限幾何的量子LDPC碼。并對其進(jìn)行了充分的理論推導(dǎo)，從而使用有限幾何構(gòu)造量子LDPC碼稱為一種可行的途徑。

關(guān)鍵詞：有限幾何；LDPC碼；量子CSS碼；對偶碼

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)09-11745-02

Construction Quantum CSS Codes Based on Finite Geometries

YUE Ke-feng，XUN Chun-ling

(Nanjing University of Posts Telecommunications，Nanjing 210003，China)

Abstract: Using the low density parity check matrices created by finite geometric approach with its dual codes， which are constructed by splitting the rows of the LDPC check matrices，a quantum LDPC codes construction method is proposed based on finite geometries in this paper. Finally， this method is proved by theory deduction adequately.

Key words: Finite Geometries; LDPC Codes; Quantum CSS Codes; Dual Codes

1 引言

與經(jīng)典信道一樣，由于環(huán)境的影響，量子通信中的信息傳輸和處理不可避免地會產(chǎn)生消相干(decoherence)，借鑒經(jīng)典糾錯方法，量子糾錯編碼（quantum error correcting codes）技術(shù)成為克服這一問題的有效手段之一[1]。自95年以來，量子糾錯碼已成為編碼界研究的方向，構(gòu)造量子糾錯編碼的方法之一是借鑒經(jīng)典糾錯編碼方法，目前很多經(jīng)典糾錯編碼方案已移植到量子領(lǐng)域中，因此作為經(jīng)典最好碼的LDPC碼的量子版本，量子LDPC碼已成為這一領(lǐng)域的研究熱點[2]。

低密度奇偶校驗(LDPC)碼又稱為Gallager碼，它是1962年Gallager提出的經(jīng)典好碼[3]，隨后的研究發(fā)現(xiàn)用迭代譯碼算法該碼具有非常接近香農(nóng)限的性能特性[4]。Gallager最初提出的隨機(jī)構(gòu)造的方法經(jīng)過后來的研究表明需要較長的編譯碼時間[4-5]。對此，文獻(xiàn)[5]中提出了基于有限幾何的方法構(gòu)造LDPC碼，實現(xiàn)了編碼時間與碼長成線性關(guān)系，并且基于有限幾何的LDPC碼的Tanner圖不含4環(huán)，可用多種譯碼方法進(jìn)行譯碼。本文是利用有限幾何的特點提出一種構(gòu)造量子LDPC碼的方法，并對其進(jìn)行了系統(tǒng)的理論分析。

2 基于有限幾何的量子LDPC碼的構(gòu)造

有限幾何包含歐氏幾何與投影幾何，歐氏幾何相對投影幾何要簡單。在組合數(shù)學(xué)中，已知在GF(2s)上有2ms個m重向量(p0，p1，…，pm-1)( pi∈GF(2s))組成一個m維歐氏幾何，記為EG(m，2s)。每一點m重向量看作歐氏幾何中的一個點，而全零向量(0，0，…，0)記為歐氏幾何的原點，在GF(2s)上這2ms個m重向量組成歐氏幾何中的所有點，而這些向量又構(gòu)成了GF(2s)的m維向量空間。因此，EG(m，2s)是由2ms個m重GF(2s)構(gòu)成的向量空間，于是EG(m，2s)中的點與GF(2ms)中的元素一一對應(yīng)。在歐氏幾何EG(m，2s)中每條線由2s個點組成，并且有 條這樣的線，另外每條線有2(m-1)s-1條與之平行，歐氏幾何中的每一個點都會有 (2ms-1)/(2s-1)條線經(jīng)過。在特殊情況下F可表示EG(m，2s)中的一條不經(jīng)過原點(a∞=0)的直線[5]，于是F可表示GF(2s)上的矢量：VF=(v0，v1，…，v2ms-2。如果分量vi的位置數(shù)ai在直線F上，則對應(yīng)的vi為1，否則為0。把EG(m，2s)中所有不經(jīng)過原點的向量VF對應(yīng)校驗矩陣的行向量，這樣得到的校驗矩陣具有循環(huán)的特性，并且所得的校驗矩陣還具有LDPC碼的性質(zhì)：(1)行重與列重都是2s；(2)任兩列或列同時為1的數(shù)目最多只有一個；(3)校驗矩陣的密度很小。投影幾何校驗矩陣的構(gòu)造與歐氏幾何類似，只是PG(m，2s)的LDPC矩陣的行重與列重是2s+1。量子CSS碼是從經(jīng)典糾錯碼獲得對應(yīng)的量子碼最有效的方法之一，該量子碼的實現(xiàn)是以經(jīng)典線性碼為基礎(chǔ)[2]。由于經(jīng)典LDPC碼是一種線性碼，因此可以結(jié)合CSS碼的構(gòu)造來實現(xiàn)量子LDPC碼的構(gòu)造。設(shè)C1和C2為[n，k1]和[n，k2]的經(jīng)典線性碼，使有C2#8834;C1，且C1和C2┴兩者可糾正t個錯誤。于是可定義糾t個量子比特的一個[n，k1-k2]量子CSS(C1，C2)碼。設(shè)x∈C1為C1中任意的一個碼字，于是量子態(tài)∣x+C2>可定義為：

量子CSS(C1，C2)碼就定義為由所有x∈C1的量子態(tài)∣x+C2>所張成的向量空間，C1中C2的陪集的數(shù)目為∣C1∣/∣C2∣，所以CSS(C1，C2)的維數(shù)為∣C1∣/∣C2∣=2k1-k2，因此CSS(C1，C2)是一個[n，k1-k2]量子碼。

利用基于有限幾何的LDPC碼具有循環(huán)或準(zhǔn)循環(huán)的特點，通過對循環(huán)多項式的處理可得到該碼的對偶碼，這是構(gòu)造量子LDPC碼的可行途徑[6-7]。結(jié)合有限幾何構(gòu)造的LDPC矩陣和CSS碼的定義，我們提出一種基于CSS碼的量子LDPC碼的構(gòu)造方法。具體步驟如下：

(1)利用上面構(gòu)造的LDPC碼的校驗矩陣H1，把H1矩陣中每行以q進(jìn)行分離，即把每行的1均勻的分布到q行中，并且其1的位置不發(fā)生變化，這樣分離后可得矩陣H'；

(2)矩陣H'的行向量之間通過線性變換簡化后可得矩陣H2，并且H2中的行向量可用其中的某一行向量S循環(huán)生成，而S可用多項式h(x)表示；

(3)由 g(x)=(xn+1)/(h(x))得到g(x)，其中n是校驗矩陣的列數(shù)。把g(x)作為生成矩陣可以得到一個碼字空間C2；

(4)以H為校驗矩陣可以得到其對偶碼C1，而C2#8834;C1，這樣就可以生成CSS碼。

3 構(gòu)造方法的理論分析

由上面的構(gòu)造過程可知，C1*H1T=0，C2*H2T=0。設(shè)矩陣H1與矩陣H2分別為：

\\ykf04.tif>(3)

其中bi=(b11，b12，…，b1n)；

設(shè)C1中的任一碼子C=(C1，C2，…，Cn))，則由C1*H1T=0得：

H2是經(jīng)過H'線性變化得到的，而H'又是對H1進(jìn)行分離而生成的，所以存在：

兩邊乘以碼子c后的

由此推得

進(jìn)而可得

所以碼空間C1、C2都在校驗矩陣H2的對偶空間中。又碼空間C2的維數(shù)小于碼空間C1的維數(shù)，故可得到構(gòu)造CSS碼的基本條件C2#8834;C1。具備了這樣的條件就可以構(gòu)造基于CSS碼的量子LDPC碼。

4 結(jié)束語

本文是在利用有限幾何構(gòu)造的稀疏校驗矩陣的基礎(chǔ)上，通過變換校驗矩陣并以量子CSS碼為理論依據(jù)獲得基于有限幾何的量子低密度奇偶校驗碼。由于本文的構(gòu)造方法利用有限幾何的特性，其所得的碼字具有循環(huán)或準(zhǔn)循環(huán)的特點，從而可以通過對多項式的處理得到該碼字的對偶碼，并且對該方法進(jìn)行了充分的理論推導(dǎo)，所以用該方法構(gòu)造量子LDPC碼是一種簡便可行的途徑。

參考文獻(xiàn)：

[1] 蔡樂才.量子糾錯碼的研究，四川理工學(xué)院學(xué)報，Vol.17，No.3，4，December，2004.

[2] 鄭大鐘，趙千川，譯.量子計算和量子信息(二).北京:清華大學(xué)出版社，pp.92-99，F(xiàn)ebruary，2005.

[3] R.Gallager， \"Low-Density Parity-Check Codes\"， IEEE Transactions on Information Theory， pp.21-28，January，1962.

[4] Y.Kou， S.Lin， and M.Fossorier，\"Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results\"， IEEE Transactions on Information Theory， Vol.47，No.7 November，2001.

[5] Y.Kou， \"Finite Geometry Low Density Parity Check Codes\"， Ph.D. dissertation， Dept. of Elec. And Computer Eng.， Univ. of California，2001.

[6] D.J.C.Mackay， G.Mitchison， and P.L.McFadden， \"Sparse-Graph Codes for Quantum Error-Correction\"， IEEE Transactions on Information Theory， vol.50， No.10， October，2004.

[7] M.S.Postol， \"A Proposed Quantum Low Density Parity Check Code\"， arXiv/quant-ph/0108131，Aug，2001.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文?！?/p>