秩距離廣義BCH碼的最小秩距離

潘　桔

(沈陽大學(xué) 師范學(xué)院, 遼寧 沈陽　110044)

秩距離廣義BCH碼的最小秩距離

潘桔

(沈陽大學(xué) 師范學(xué)院, 遼寧 沈陽110044)

摘要:證明秩距離廣義BCH碼的最小秩距離與其校驗(yàn)矩陣的任一k階子式構(gòu)成的行列式的非零性有關(guān),而與廣義連續(xù)根集無關(guān).

關(guān)鍵詞:線性化多項(xiàng)式; 秩距離; 廣義BCH碼; 校驗(yàn)矩陣

秩距離碼的概念和極大秩距離碼的理論是1985年由俄國學(xué)者Gabidulin首先提出的,由于用秩距離碼構(gòu)造的各種密碼體制和認(rèn)證系統(tǒng)要比Hamming距離度量碼的安全性更高,所以,近年來在通信與密碼學(xué)的研究領(lǐng)域中受到廣泛關(guān)注.2000年以來,我國學(xué)者杜偉章,王新梅等人以此理論為基礎(chǔ), 在文獻(xiàn)[1-3]中給出了一些秩距離縮短碼、秩距離碼的構(gòu)造方法,并且提出了一種新的碼字----秩距離BCH碼的概念,討論了其最小秩距離的問題.他們指出秩距離BCH碼的最小秩距離問題與其生成多項(xiàng)式的根集情況有關(guān):當(dāng)所給秩距離碼的生成多項(xiàng)式具有廣義連續(xù)根集時(shí),它的最小秩距離問題是可以解決的; 而當(dāng)其生成多項(xiàng)式根集為一般形式時(shí),其最小秩距離及構(gòu)造極大秩距離碼卻是懸而未決的問題.

1線性化多項(xiàng)式的概念和性質(zhì)

線性化多項(xiàng)式的概念及其相關(guān)理論是研究秩距離碼的重要工具,尤其是其根的存在性理論在求最小秩距離的研究中起著至關(guān)重要的作用.

乘法運(yùn)算為

定義2[5]6設(shè)L(x)和L1(x)是GF(qN)上的線性化多項(xiàng)式,如果存在GF(qN)上的線性化多項(xiàng)式L2(x)使得L(x)=L1(x)L2(x)成立,則稱L1(x)能夠符號(hào)整除L(x).

2秩距離的相關(guān)概念

定義3[5]7設(shè)GF(qN)中任一元素xi=ai1α1+ai2α2+…+aiNαN,i=1,2,…,n, 其中α1,α2,…,αN是GF(qN)在GF(q)上的一組基,則對x=(x1,x2,…,xn)T∈GF(qN)n有

稱矩陣A(x)的秩為x在GF(q)上的秩,記為r(x;q);并將GF(qN)n中任意兩個(gè)不同的元素x,y之間的秩距離定義為兩者的差在GF(q)上的秩, 即

定義4[6]設(shè)矩陣H中的元素屬于GF(qN),其在GF(q)上的極大線性無關(guān)列數(shù)稱為該矩陣在GF(q)上的秩,記為r(H;q);在GF(qN)上的極大線性無關(guān)列數(shù)稱為該矩陣在GF(qN)上的秩,記為r(H;qN),顯然有r(H;q)≥r(H;qN).

定義5[7]設(shè)C為一個(gè)線性碼,其秩距離定義為任意不同碼字間距離的最小值, 即

對于碼長為n,維數(shù)為k且秩距離為d的線性碼稱為秩距離(n,k,d)碼.

定理1對于任意線性碼C, 其秩距離是所有碼字中秩最小的碼字的秩, 即

證明由定義5及定義7知碼C的秩距離表示為

又因?yàn)镃是一個(gè)線性碼,所以有x-y=z∈C,那么碼C的秩距離即為

引理1對于任意線性(n,k,d)碼的秩距離d都有d≤n-k+1, 并且稱能夠達(dá)到這個(gè)最大值的碼為極大秩距離碼.

定理2設(shè)C是GF(qN)上的線性秩距離碼, 其校驗(yàn)矩陣為

則碼C的秩距離為d當(dāng)且僅當(dāng)校驗(yàn)矩陣H的任意d-1列向量在GF(q)上都線性無關(guān), 其中d≥2.

證明(必要性)設(shè)線性碼C的秩距離為d,假設(shè)校驗(yàn)矩陣H有d-1列向量在GF(q)上是線性相關(guān)的,則不妨設(shè)向量h1,h2,…,hd-1線性相關(guān),根據(jù)線性相關(guān)性概念在GF(q)中可以找到不全為0的常數(shù)a1,a2,…,ad-1使a1h1+a2h2+…+ad-1hd-1=0成立,寫成矩陣乘法形式則有

即c=(a1,a2,…,ad-1,0,…,0)是C的一個(gè)碼字,且r(c;q)≤d-1,與碼的秩距離為d矛盾.

(充分性)設(shè)校驗(yàn)矩陣H的任d-1列向量在GF(q)上都線性無關(guān),要證碼C的秩距離為d. 假設(shè)碼C的秩距離為d-1, 則可設(shè)C中存在秩為d-1的碼字c=(a1,a2,…,ad-1,0,…,0), 其中a1,a2,…,ad-1∈GF(q)且均不為零, 那么就有

即a1h1+a2h2+…+ad-1hd-1=0,這與H的任意d-1列向量在GF(q)上都是線性無關(guān)的是相矛盾的, 因此碼C的秩距離為d.

3秩距離廣義BCH碼及其秩距離

例如,令G(z)=α5z[2]+α4z[1]+z為定義在GF(23)上的一個(gè)線性化多項(xiàng)式,其中α是GF(23)中的本原元素,且滿足α3=α2+1.經(jīng)過驗(yàn)證可得α[3]=1,(α2)[3]=1,即α和α2是GF(23)中的3級元素,且G(z)的根是α和α2在GF(2)上各種線性組合,那么由G(z)生成的線性碼C就是廣義BCH碼.

定理3設(shè)G(z)是GF(qN)上的線性化多項(xiàng)式,若由G(z)可以生成一個(gè)秩距離廣義BCH碼C, 那么

(1) 碼C的校驗(yàn)矩陣為

其中β1,β2,…,βk∈GF(q), 且G(z)的根是βi,i=1,2,…,k在GF(q)中的各種線性組合.

(2) 當(dāng)校驗(yàn)矩陣H的任一k階子式構(gòu)成的行列式不為零時(shí), 碼C的最小秩距離為k+1,并且此時(shí)該碼為極大秩距離碼.

寫成矩陣形式為

所以由G(z)生成的秩距離廣義BCH碼C的校驗(yàn)矩陣為

(2) 若校驗(yàn)矩陣H的任一k階子式構(gòu)成的行列式均不等于零,則有H中的任意k列向量在GF(q)上都是線性無關(guān)的,由定理3的內(nèi)容可推知此碼的最小秩距離為k+1.另一方面,設(shè)該碼的維數(shù)為k′,則由線性碼校驗(yàn)矩陣的定義可以得到n-k′=k,而它的最小秩距離為d=k+1=n-k′+1,即該碼是極大秩距離碼.

4結(jié)論

本文提出了秩距離廣義BCH碼的概念,討論了其最小秩距離的問題,得到了秩距離廣義BCH碼的最小秩距離與其校驗(yàn)矩陣的任一k階子式構(gòu)成的行列式的非零性有關(guān),而與廣義連續(xù)根集無關(guān),從而部分解決了杜偉章,王新梅等人提出的當(dāng)其生成多項(xiàng)式的根集為一般情況時(shí)秩距離規(guī)律的問題.

參考文獻(xiàn):

[1] 杜偉章,王新梅. 關(guān)于秩距離BCH碼的校驗(yàn)矩陣及其秩距離[J]. 通信學(xué)報(bào), 2001,22(1):126-128.

(DUWZ,WANGXM.ParitycheckmatricesandrankdistanceofrankdistanceBCHcodes[J].JournalofChinaInstituteofCommunications, 2001,22(1):126-128.)

[2] 杜偉章,陳克非. 秩距離BCH碼的進(jìn)一步研究[J]. 通信學(xué)報(bào), 2002,23(11):92-95.

(DUWZ,CHENKF.FurtherresearchonrankdistanceBCHcodes[J].JournalofChinaInstituteofCommunications, 2002,23(11):92-95.)

[3] 杜偉章,陳克非. 秩距離縮短碼的構(gòu)造[J]. 計(jì)算機(jī)學(xué)報(bào), 2002,25(4):445-448.

(DUWZ,CHENKF.Theconstructionofrankdistanceabridgingcodes[J].ChineseJournalofComputers, 2002,25(4):445-448.)

[4] 馮克勤. 糾錯(cuò)碼的代數(shù)理論[M]. 北京:清華大學(xué)出版社, 2010.

(FENGKQ.Thealgebraictheoryoferrorcorrectioncode[M].Beijing:TsinghuaUniversityPress, 2010.)

[5] 潘桔,關(guān)紅鈞. q-循環(huán)碼的生成矩陣和校驗(yàn)矩陣[J]. 沈陽大學(xué)學(xué)報(bào), 2008,20(4):6-8.

(PANJ,GUANHJ.Generatormatrixandcheckmatrixofq-cycliccodes[J].JournalofShenyangUniversity, 2008,20(4):6-8.)

[6] 陳博聰. 有限域上常循環(huán)碼的研究[D]. 武漢:華中師范大學(xué), 2013.

(CHENBC.Aresearchonconstacycliccodesoverfinitefields[D].Wuhan:CentralChinaNormalUniversity, 2013.)

[7] 錢建發(fā),朱士信. 秩距離循環(huán)碼的研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2005,41(32):89-90.

【責(zé)任編輯: 胡天慧】

(QIANJF,ZHUSX.Thestudyofrankdistancecycliccodes[J].ComputerEngineeringandApplications, 2005,41(32):89-90.)

Minimum Rank Distance of Generalized Rank Distance BCH Code

PanJu

(Normal School, Shenyang University, Shenyang 110044, China)

Abstract:It proves that the minimum rank distance of a generalized rank distance BCH code is relative to any non zerok-th subdeterminant of its check matrix, and has nothing to do with the generalized continuous root set.

Key words:linearized polynomials; rank distance; generalized BCH codes; check matrix

中圖分類號(hào):TN 911

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):2095-5456(2015)06-0512-03

作者簡介:潘桔(1980-),女,遼寧營口人,沈陽大學(xué)講師,博士研究生.

基金項(xiàng)目:遼寧省教育廳一般項(xiàng)目(L2015364).

收稿日期:2015-06-26