高 有,高晉如
(中國民航大學理學院,天津300300)
隨著人類對通信網(wǎng)絡(luò)需求的增加,通信領(lǐng)域的發(fā)展也越來越快,傳統(tǒng)的通信模式已無法滿足人們?nèi)找嬖鲩L的社會通信需求,因此新的理論和技術(shù)不斷產(chǎn)生。傳統(tǒng)的隨機線性網(wǎng)絡(luò)編碼是網(wǎng)絡(luò)中傳播信息的有力工具,但易受各種來源導(dǎo)致的錯誤影響,當利用接收到的分組隨機線性組合推導(dǎo)出所發(fā)送的消息時,即使一個錯誤分組中的單個錯誤也可能使整個傳輸變得無用。因此,隨機線性網(wǎng)絡(luò)編碼的差錯控制非常關(guān)鍵,近年來也受到越來越多的關(guān)注。子空間碼作為網(wǎng)絡(luò)編碼中的一個重要組成部分[1-2],具有一定的檢錯與糾錯能力,與傳統(tǒng)糾錯碼的區(qū)別是子空間碼將每個子空間看作一個碼字,定義一個子空間距離,子空間距離的大小可以用來衡量該子空間碼的檢錯與糾錯能力。
目前,國內(nèi)外學者對于子空間碼的研究已有很多優(yōu)秀成果。Koetter 等[3]提出了線性算子信道模型與Reed-Solomon-like 碼,并給出了關(guān)于子空間碼的第一組詳述結(jié)果,打開了研究子空間碼的大門;此外,他們計算得到了子空間碼的Sphere-Packing 界、Gilbert 界及常維碼的Singleton 界,這些性能界雖然比較寬泛但具有廣泛的適用性。Xia 等[4]研究并計算得到了常維碼的部分上下界,給出了目前為止一類最優(yōu)的上界,并證明了常維碼達到一類上界的充分必要條件,在此基礎(chǔ)之上發(fā)現(xiàn)了一類最優(yōu)常維碼。近幾年,關(guān)于常維碼的研究仍在繼續(xù),文獻[5-10]基于有限域上不同幾何空間(仿射空間、奇異線性空間、酉空間、辛空間)的子空間的幾何性質(zhì)構(gòu)造常維碼,研究解決了子空間碼的一些性能界。目前,國內(nèi)外并沒有基于偽辛空間的子空間構(gòu)造子空間碼及研究所構(gòu)造的子空間碼的碼字個數(shù)上下界的相關(guān)研究成果,因此,基于偽辛空間的(m,0,0,1)型子空間構(gòu)造子空間碼,并利用偽辛空間的相關(guān)幾何性質(zhì)研究并計算所構(gòu)造的子空間碼的球填充界、Singleton 界、Gilbert-Varshamov 界 和Wang-Xing-Safavi-Naini 界,對于網(wǎng)絡(luò)編碼中常維數(shù)子空間碼的理論研究具有一定的意義。
偽辛空間的基本概念及相關(guān)計數(shù)定理[11]如下。
設(shè)Fq是一個有限域,含有q 個元素,其中q 是一個素數(shù)的冪。設(shè)S 是Fq上n×n 的非奇異非交錯對稱矩陣,若Fq上n×n 的矩陣T 滿足TSTT=S,則稱T 關(guān)于S 是偽辛的。這些滿足條件的T 關(guān)于矩陣乘法構(gòu)成一個群,稱為Fq上關(guān)于S 的偽辛群,記作PSn(Fq,S)。
定理1設(shè)S 是Fq上n×n 的非奇異非交錯對稱矩陣,若n=2v+1 為奇數(shù),v∈N,則S 合同于S1=若n=2v+2 為偶數(shù),則S 合同于S2=
Fq上關(guān)于S1和S2偽辛群記作PS2v+1(Fq,S1)和PS2v+2(Fq,S2),簡記為PS2v+1(Fq)和PS2v+2(Fq),合記作PS2v+δ(Fq),其中δ=1,2。
定義1設(shè)P 是一個(m,2s + τ,s,ε)型子空間(τ =0,1,2;ε=0,1),滿足條件:①PSδPT合同于L(m,2s+τ,s);②ε=0 時,e2v+1?P;ε=1 時,e2v+1∈P(ei表示第i 個位置的單位向量)。
定理2偽辛空間中,(m,2s+τ,s,ε)型子空間存在的充要條件是
式中:當δ =1 時,n0=0;當δ =2 時,(τ,s)=(0,0)對應(yīng)n0= m,(τ,ε)=(0,1)對應(yīng)n0= 0,其他情況對應(yīng)n0=2(v+1)-m。
對于一個(m,2s+τ,s,ε)型子空間,其中含有(m1,2s1+ τ1,s1,ε1)型子空間的數(shù)目記作N(m1,2s1+ τ1,s1,ε1;m;2s+τ,s,ε;2v+δ)。
定理3在偽辛空間中,存在(m,2s+τ,s,ε)型子空間,則
式中n1=m1,m1,m-m1+2s1,2(m-m1+2s1)分別對應(yīng)(τ,τ1)=(0,0),(2,0),(2,1),(2,2)。
式中n2= 0,0,m - m1+ 2s1分別對應(yīng)(τ,τ1)=(0,0),(2,0),(2,2)。
取C?M(m,0,0,1;2n + 2),C 中共含有M 個(m,0,0,1)型子空間,將C 中任一子空間記作一個碼字,則碼字個數(shù)為M,取C 的任意兩個碼字U 和V,定義
從而定義集合C 的最小距離為
d(C)=min{d(U,V)|U≠V,U,V∈C}則稱C 是一個(2n+2,M,d,(m,0,0,1))q碼。記Aq(2n+2,d,(m,0,0,1))表示子空間碼C 所含有的最大碼字個數(shù)。由定義可知,d 是偶數(shù),所以只需考慮d=2α(α∈N)。
定義2以M(m,0,0,1;2n + 2)中的一個子空間V 為中心,以t 為半徑的球S(V,(m,0,0,1),t)定義為:M(m,0,0,1;2n+2)中與V 的距離滿足d(U,V)≤2t 的所有(m,0,0,1)型子空間的集合。
定理4S(V,(m,0,0,1),t)中所含有的(m,0,0,1)型子空間的個數(shù)與V 的選取無關(guān),且
式中:V∈M(m,0,0,1;2n + 2)是偽辛空間中一個固定的(m,0,0,1)型子空間;Nq(2n+2,(m,0,0,1),(m,0,0,1),(m - i,0,0,0))表示M(m,0,0,1;2n + 2)中滿足V∩W∈M(m-i,0,0,0;2n+2)的(m,0,0,1)型子空間W 的個數(shù);Nq(2n+2,(m,0,0,1),(m,0,0,1),(m-i,0,0,1))表示M(m,0,0,1;2n+2)中滿足V∩W∈M(m - i,0,0,1;2n + 2)的(m,0,0,1)型子空間W 的個數(shù)。
證明設(shè)V∈M(m,0,0,1;2n+2)是偽辛空間中的一個固定的(m,0,0,1)型子空間,Nq(2n+2,(m,0,0,1),(j,0,0,1),(s,0,0,1))表示M(j,0,0,1;2n+ 2)中滿足V∩W∈M(s,0,0,1;2n + 2)的(j,0,0,1)型子空間W 的個數(shù)。V∩W 為(s,0,0,1)型子空間有N(s,0,0,1;m,0,0,1;2n+2)=種可能,當(s,0,0,1)型子空間確定以后,該子空間可以擴充為一個(j,0,0,1)型子空間,一共有種擴充方法,所以
則
設(shè)V∈M(m,0,0,1;2n+2)是偽辛空間中一個固定的(m,0,0,1)型子空間,Nq(2n + 2,(m,0,0,1),(j,0,0,1),(s,0,0,0))表示M(j,0,0,1;2n + 2)中滿足V∩W∈M(s,0,0,0;2n+2)的(j,0,0,1)型子空間W的個數(shù)。V∩W 為(s,0,0,0)型子空間有N(s,0,0,0;m,0,0,1;2n+2)=種可能,當(s,0,0,0)型子空間確定以后,該子空間可以擴充為一個(j,0,0,1)型子空間,一共有種擴充方法,所以
則
由式(1)知,Nq(2n + 2,(m,0,0,1),(m,0,0,1),(m-i,0,0,0))與Nq(2n+ 2,(m,0,0,1),(m,0,0,1),(m-i,0,0,1))是滿足與確定的(m,0,0,1)型子空間V的距離為2i 的(m,0,0,1)型子空間的個數(shù),因此
顯然,S(V,(m,0,0,1),t)的數(shù)量與子空間V 的選擇無關(guān)。
定理5(球填充界)設(shè)t=[(α-1)/2],則
設(shè)C 是(m,0,0,1)型子空間的集合,V∈C,W′是偽辛空間的任一(2n+1)維子空間。定義
C′={V′|V′=Hm-1(V∩W′),V∈C},
式中Hm-1(V∩W′)表示若V∩W′是一個(m-1,0,0,1)型子空間,則用V∩W′替換V,否則用V 的一個(m-1,0,0,1)型子空間替換。
引理1設(shè)C?M(m,0,0,1;2n+2)是一個(2n+2,M,d,(m,0,0,1)q碼,其中d >2,則上面定義的C′是一個(2n+1,M,d′,(m- 1,0,0,1))q碼,其中d′≥d-2。
證明設(shè)U 和V 是子空間碼C 中的兩個不同碼字,根據(jù)C′定義對應(yīng)得到U′ = Hm-1(U∩W′),V′ =Hm-1(V∩W′)。顯然,U′?U,V′?V。
由于d(U,V)= 2m - 2dim(U ∩V)≥d,則2dim(U′∩V′)≤2dim(U∩V)≤2m-d。
又由式(1)得
d(U′,V′)=dim(U′)+dim(V′)-2dim(U′∩V′)=
2(m-1)-2dim(U′∩V′)≥
2(m-1)-(2m-d)=d-2
因為d >2,則d′=d(U′,V′)≥d-2 >0,即U′與V′是兩個不同的碼字,所以碼C 與碼C′具有相同的碼字個數(shù)。
定理6(Singleton 界)
定理7(Gilbert-Varshamov 界)
證明設(shè)C 是一個(2n+2,M,2α,(m,0,0,1))q碼,假設(shè)該碼的碼字個數(shù)達到了碼C 含有的最大碼字個數(shù),即M=Aq(2n+2,2α,(m,0,0,1))。則對任意V∈C,由于碼C 已經(jīng)達到了最大碼字個數(shù),則在M(m,0,0,1;2n+2)中,不存在(m,0,0,1)型子空間U,使得d(U,V)≥2α。否則將U 加到碼C 中,得到一個碼字個數(shù)為M+1 的碼,與碼C 已經(jīng)達到最大碼字個數(shù)矛盾。所以,對?V∈C,有M·|S(V,(m,0,0,1),α-1)|≥N(m,0,0,1;2n+2)。
因此,M≥N(m,0,0,1;2n+2)/|S(V,(m,0,0,1),α-1)|,其中
定理8(Wang-Xing-Safavi-Naini 界)
利用偽辛空間的(m,0,0,1)型子空間構(gòu)造子空間碼,計算了所構(gòu)造的子空間碼的球填充界、Sing-leton界、Gilbert-Varshamov 界及Wang-Xing-Safavi-Naini界,豐富了有限域上典型群的幾何學知識,對網(wǎng)絡(luò)編碼中子空間碼的理論研究有重大意義。