代數(shù)函數(shù)域上的局部恢復(fù)碼

顏好, 胡萬寶, 陳子星

(安慶師范大學(xué)數(shù)學(xué)與計算科學(xué)學(xué)院, 安慶 246133)

1 引言

傳統(tǒng)的大型存儲體系依賴于通過塊復(fù)制來提供系統(tǒng)的可靠性, 復(fù)制的缺點是存儲開銷大. 擦除編碼技術(shù)以相當(dāng)小的存儲開銷實現(xiàn)了更高的數(shù)據(jù)可靠性, 局部恢復(fù)碼(LRC碼) 是擦除編碼的一種, 它極大地提高了分布式存儲系統(tǒng)的可靠性和有效性[1].

雖然現(xiàn)代存儲系統(tǒng)允許幾個符號丟失的情況出現(xiàn), 但到目前為止, 一個符號丟失的情況更常見, 因此系統(tǒng)應(yīng)重點設(shè)計一個符號丟失的精確恢復(fù). 在系統(tǒng)中一個符號丟失的精確恢復(fù)效率, 可以通過三個不同的指標(biāo)來量化, 每個指標(biāo)都與不同的存儲系統(tǒng)和應(yīng)用相關(guān), 已經(jīng)有許多論文在這三個指標(biāo)下考慮精確恢復(fù)問題, 即讀取位的數(shù)量[2]、恢復(fù)帶寬[3-6]、局部化參數(shù)r(參與恢復(fù)過程符號的個數(shù)), 關(guān)注的是局部化參數(shù)r[7-8]. 對于一個局部恢復(fù)碼, 如果一個符號丟失, 可以通過至多r個符號來恢復(fù). 局部恢復(fù)碼的精確定義如下[9]:

定義1.1設(shè)C是Fq上的[n,k]線性碼,如果對于每個i ∈{1,2,··· ,n},存在r個元素的子集Ii ?{1,2,··· ,n}{i}和一個函數(shù)φi:Frq →Fq使得對于每個碼字x ∈C有xi=φi(xj1,xj2,··· ,xjr), 其中j1

如果C是(n,k,r) LRC 碼, 則C的最小距離滿足

若(1) 式成立, 稱C是距離最優(yōu)的(n,k,r) LRC 碼. 當(dāng)r=k時, (1) 式是著名的singleton 界. 若等式成立, 即

則稱碼C是MDS 碼. 每個坐標(biāo)重復(fù)兩次得到的長度為2k的線性碼是局部化參數(shù)為1的LRC 碼. 另外, 整個碼字可以通過接收除丟失符號之外的k個符號來確定, 因此局部化參數(shù)1≤r ≤k[10]. 文獻(xiàn)[7] 構(gòu)造了一族最優(yōu)的(n,k,r) LRC 碼, 與傳統(tǒng)的MDS 碼一樣, 在這族LRC 碼中, 碼長受到了字符集大小的限制, 即要求n ≤q. 為了突破這一限制, 自然地, 可以想到利用代數(shù)曲線或者代數(shù)函數(shù)域來構(gòu)造局部恢復(fù)碼. 文獻(xiàn)[10] 利用了G-S 曲線和Hermite 曲線等有理光滑絕對不可約曲線構(gòu)造了LRC 碼. 因為代數(shù)曲線涉及代數(shù)幾何等復(fù)雜數(shù)學(xué)知識, 諸如曲線映射, 描述起來甚是繁雜. 而對于在有理光滑絕對不可約曲線上構(gòu)造的局部恢復(fù)碼, 都可以等價地利用單變量的代數(shù)函數(shù)域來構(gòu)造,使得描述更直接,碼長也可以突破字符集的大小的限制.因此,相比文獻(xiàn)[10]的方法,利用代數(shù)函數(shù)域構(gòu)造局部恢復(fù)碼更具實際意義. 接著, 將構(gòu)造方法應(yīng)用于廣義Hermite函數(shù)域, 得到了一類廣義Hermite 函數(shù)域上的局部恢復(fù)碼. 進一步地, 通過構(gòu)造子碼的方式明顯地改進了廣義Hermite 函數(shù)域上的局部恢復(fù)碼的最小距離的下界.

2 相關(guān)準(zhǔn)備

2.1 代數(shù)函數(shù)域[11]

定義2.1設(shè)x ∈F是K上的超越元, 一個擴域F ?K使得F是K(x) 的有限代數(shù)擴張, 則稱F/K是K上單變量的代數(shù)函數(shù)域.

設(shè)P是F/K的一個位(place),OP是它的賦值環(huán),由于P是OP的一個極大理想,因此OP/P是一個域, 記為FP, 又由于K ?OP且K ∩P={0}, 因此OP →OP/P誘導(dǎo)出了K到OP/P的一個嵌入. 設(shè)F/K是滿常域為K的代數(shù)函數(shù)域,PF是F中位的集合, 次數(shù)為1 的位稱為有理位,g(F) 表示F的虧格.

定義2.3設(shè)G是F的除子, 黎曼洛赫空間定義為

它是K上有限維的向量空間,它的維數(shù)為l(G)≥degG+1?g(F),當(dāng)degG>2g(F)?1時,l(G)=degG+1?g(F).

命題2.1設(shè)x ∈FK, 則deg(x)=0, deg(x)0=deg(x)∞=[F:K(x)].

定義2.4設(shè)F′/F是函數(shù)域的代數(shù)擴張且P ∈PF, 如果F中存在P的一個擴張P′∈PF′, 使得分歧指數(shù)e(P′|P)=[F′:F], 則稱P在F′/F是完全分歧的.

定義2.5設(shè)F′/K′是F/K的代數(shù)擴張, 對于一個位P ∈PF, 定義它關(guān)于F′/F的上范數(shù)為

2.2 廣義Hermite 函數(shù)域

命題2.2設(shè)代數(shù)函數(shù)域F=Fqs(x,y) 滿足

其中p(y)∈Fqs[y], 設(shè)E=Fqs(y), 則

(a) [F:E]=qs?1,Fqs是F的滿常域;

(b)x,y的公共極點是Q∞;

(c) (y)∞=qs?1Q∞, (x)∞=(qs?1+qs?2)Q∞;

(d)F中有N=1+q2s?1個次數(shù)為1 的位, 其中一個是x的極點Q∞, 另外, 對于所有的α ∈Fqs, 有α1+q+α1+q2+···+αqs?2+qs?1=β ∈Fqs且存在qs?1個不同的元素λ ∈Fqs使得λqs?1+···+λq+λ=β, 因此對于這樣的(λ,β) 存在次數(shù)為1 的位Pλ,β ∈PF使得x(Pλ,β)=λ且y(Pλ,β)=β.

2.3 代數(shù)幾何碼

定義2.6設(shè)F/Fq是虧格為g(F)的代數(shù)函數(shù)域,P1,P2,··· ,Pn是F/Fq中互不相同的有理位,D=P1+P2+···+Pn,G是F/Fq的一個除子使得supp(G)∩supp(D)=?,

則關(guān)聯(lián)D和G的代數(shù)幾何碼定義為

對于m ∈Z, 取G=mQ∞, 定義一點廣義Hermite 碼為Cm:=CL(D,mQ∞), 其中D是廣義Hermite 函數(shù)域F/Fqs上次數(shù)為1 的位(Q∞除外) 的和, 碼Cm稱為廣義Hermite 碼.

命題2.3設(shè)dm是碼Cm的最小距離, 則

(a) 若m=aqs?1,0≤a ≤qs, 則dm=n ?m;

(b) 若m=aqs?1+b(qs?1+qs?2),0≤a ≤qs ?qs?1?qs?2, 且0≤b ≤qs?1,則dm=n ?m;

(c) 若m=q2s?1?qs?1+b,0≤b ≤qs?1, 則dm=qs?1.

3 在代數(shù)函數(shù)域上構(gòu)造局部恢復(fù)碼

在文獻(xiàn)[10] 中利用有限域上的代數(shù)曲線構(gòu)造局部恢復(fù)碼要求K(X)=K(Y)(x) 滿足方程xr+1+brxr+···+b0=0, 其中bi ∈K(Y). 本節(jié)利用代數(shù)函數(shù)域構(gòu)造局部恢復(fù)碼不受這一條件的限制. 下面介紹代數(shù)函數(shù)域上局部恢復(fù)碼的構(gòu)造:

設(shè)F/Fq,E/Fq是滿常域為Fq的代數(shù)函數(shù)域,F為E的擴域且[F:E] =r+1,設(shè)S={P1,P2,··· ,Pm}是E中m個有理位的集合, 且每個Pi,i= 1,2,··· ,m在F/E中是完全分裂的, 即對于E中每個Pi都存在r+ 1 個次數(shù)為1 的擴張Pi1,Pi2,··· ,Pi(r+1), 設(shè)P={Pij,1≤i ≤m,1≤j ≤r+1}, 則|P| =m(r+1),P的劃分A={A1,A2,··· ,Am}, 其中Ai={Pi1,Pi2,··· ,Pi(r+1)},i=1,··· ,m.

1.女子貧民院-Chiu Chi Yuan（石碑胡同(Shih Pei）, Hsi Ssu Pai Lou）

設(shè)D是E中的除子使得supp(D)∩S=?,f1,f2,··· ,ft是L(D) 在Fq上的一組基, 設(shè)x ∈F使得1,x,··· ,xr?1在E上線性無關(guān),x(Pij) 對于每個Ai中的有理位是互不相同的, 其中i=1,··· ,m, 定義函數(shù)空間

定義映射

記這個映射的像為C(P,V).

定理3.1上述定義的碼C(P,V) 是Fq上的(n,k,r) LRC 碼, 若

則其參數(shù)為n=m(r+1),k=rt, d ≥n ?(r+1)deg(D)?(r ?1)deg(x)∞.

證明顯然碼長n=m(r+1), 下面證明fjxi,j= 1,··· ,t,i= 0,··· ,r ?1 在Fq上線性無關(guān), 若

由于1,x,··· ,xr?1在E上線性無關(guān), 則

又由于f1,··· ,ft在Fq上線性無關(guān), 則aij= 0, 從而fjxi在Fq上線性無關(guān), 所以dimFq(V)=rt.

下證fj ∈L(D),fjxi至多有(r+1)deg(D)+(r ?1)deg(x)∞個零點, 設(shè)零點的個數(shù)為|I|, 由于|I|≤deg(fjxi)0=deg(fjxi)F∞, 則

由于fj ∈L(D),則(fj)+D ≥0,即(fj)0?(fj)∞+D ≥0,又由于supp(D)∩S=?,則(fj)∞≤D, 從而deg(fj)∞≤deg(D), 所以有

設(shè)g1,g2∈V,g=a1g1+a2g2?=0,a1,a2∈Fq, 由于

則對于任意的Q ∈supp((r+1)D+(r ?1)(x)∞) 有

所以從而deg(a1g1+a2g2)≤deg((r+1)D+(r ?1)(x)∞), 即

所以fj ∈L(D),fjxi至多有(r+1)deg(D)+(r ?1)deg(x)∞個零點.

下證eVA:(Pij) 是單射, 考慮

由于f ∈V至多有(r+1)deg(D)+(r ?1)deg(x)∞個零點, 且

則f=0, 所以eVA是單射, 顯然也是滿射, 從而

由于C(P,V) 是線性碼, 則最小距離d ≥n ?(r+1)deg(D)?(r ?1)deg(x)∞.

下面給出修復(fù)方案:

假設(shè)Pα ∈Ai,i ∈{1,2,··· ,m}對應(yīng)的符號為Cα=f(Pα) 丟失, 令

其中0≤i ≤r ?1, 設(shè)f ∈L(D),Pi是E中的位,Pij,j=1,··· ,(r+1) 是Pi的擴張,且deg(Pij)=1, 聲明f(Pij)=f(Pi), 由f(Pi)∈Fq可知, 存在a ∈Fq使得

從而有f ?a ∈Pi ?Pij, 因此

即f(Pij)=f(Pi). 對于任意的Pβ ∈Ai有

由于deg(δ(x))≤r ?1, 且{x(Pβ)}Pβ∈Ai{Pα},i ∈{1,2,··· ,m}是互不相同的, 丟失的符號可以通過Ai中其余r個位置Pβ ∈Ai{Pα}對應(yīng)的符號通過插值得到, 一旦δ(x)確定, 則丟失的符號為δ(x)(Pα), 因此C(P,V) 是(n,k,r) LRC 碼, 其中參數(shù)為

下面將此構(gòu)造方法應(yīng)用于廣義Hermite 函數(shù)域去構(gòu)造局部恢復(fù)碼.

4 廣義Hermite 函數(shù)域上的局部恢復(fù)碼

考慮代數(shù)函數(shù)域F=Fqs(x,y) 滿足

當(dāng)s=2 時, 廣義Hermite 函數(shù)域就變成了Hermitian 函數(shù)域.

設(shè)E=Fqs(y), 則[F:E]=qs?1, 設(shè)qs?1=r+1,l=qs, 由命題2.2 知, 設(shè)由Fqs帶來的有理位的集合為S1={P1,P2,··· ,Pl}, 每個Pi,i= 1,2,··· ,l在F/E中是完全分裂的,Pi1,Pi2,··· ,Pi(r+1)是Pi上的有理位, 設(shè)F中有理位的集合為

則|P|=l(r+1),P的劃分為A={A1,A2,··· ,Al}, 其中

矛盾, 因此1,y,··· ,yt在Fqs上線性無關(guān). 又由于

則l(D)=deg(D)+1?g(E)=t+1, 從而1,y,··· ,yt是L(D) 在Fqs上的一組基. 由于[F:E]=qs?1, 則1,x,··· ,xr?1在E上線性無關(guān),x(Pij) 對于Ai,i=1,··· ,l中的有理位是互不相同的, 定義函數(shù)空間V=〈xiyj,i= 0,··· ,r ?1,j= 0,··· ,t〉, 定義映射:

記這個映射的像為C(P,V).

應(yīng)用定理3.1 得到一類局部恢復(fù)碼, 其參數(shù)如下:

定理4.1上述定義的碼C(P,V) 是Fqs上的(n,k,r) LRC 碼, 其中參數(shù)為

定理4.1 中最小距離的下界利用廣義Hermite 碼的一些性質(zhì)在某些特殊的情況下可以得到改進. 事實上, 對于廣義Hermite 碼Cm, 選取適當(dāng)?shù)膍使得V ?L(mQ∞),則C(P,V)?Cm, 由子碼的性質(zhì)得dLRC≥dm, 由于

則t ≤qs ?qs?1?qs?2+2, 下面就以t=qs ?qs?1?qs?2+2,q> 2 情況來探討碼C(P,V) 的最小距離的下界的改進思想.

定理4.2若t=qs ?qs?1?qs?2+2,q>2, 則定理4.1 最小距離的界為

較(5) 式的距離改進了(q ?2)qs?2.

證明取m=tqs?1+(qs?1?2)(qs?1+qs?2), 則C1(P1,V1)?Cm, 要證

只需證明xiyj ∈L(mQ∞), 其中i=0,··· ,r ?1,j=0,··· ,t. 由

可得, (xiyj)0?(xiyj)∞≥?mQ∞, 從而有(xiyj)≥?mQ∞, 即(xiyj)+mQ∞≥0, 因此xiyj ∈L(mQ∞).

下面計算cm的最小距離dm.

若t=qs ?qs?1?qs?2+2, 則

其中b=qs?1?2qs?2, 顯然0

則dLRC≥dm=qs?1.

下面比較n ?m與dm的大小.

當(dāng)t=qs ?qs?1?qs?2+2 時,n?m=n?qs?1t?(qs?1?2)(qs?1+qs?2)=2qs?2,而dm=qs?1, 因此較(5) 式的距離改進了qs?1?2qs?2=(q ?2)qs?2. 證畢.

注4.1從定理4.2 可以看出, 當(dāng)q>2 時, (5) 式的最小距離的界被明顯地改進.

5 結(jié)束語

本文利用代數(shù)函數(shù)域構(gòu)造出了局部恢復(fù)碼, 并在廣義Hermite 函數(shù)域上得到一類局部恢復(fù)碼, 又通過子碼的方式改進了廣義Hermite 函數(shù)域上的局部恢復(fù)碼的最小距離的下界. 本文針對的是一個符號丟失的精確恢復(fù), 后面, 將擴展本文的構(gòu)造方法至多個符號丟失的精確恢復(fù), 以及構(gòu)造代數(shù)函數(shù)域上具有多重恢復(fù)集的局部恢復(fù)碼. 廣義Hermite 曲線既是Kummer 曲線, 也是Artin-schreier 曲線, 因此更多的代數(shù)曲線可以得到更多的局部恢復(fù)碼.