代數函數域上的局部恢復碼

顏好, 胡萬寶, 陳子星

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

1 引言

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

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

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

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

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

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

2 相關準備

2.1 代數函數域[11]

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

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

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

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

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

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

定義2.5設F′/K′是F/K的代數擴張, 對于一個位P ∈PF, 定義它關于F′/F的上范數為

2.2 廣義Hermite 函數域

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

其中p(y)∈Fqs[y], 設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個次數為1 的位, 其中一個是x的極點Q∞, 另外, 對于所有的α ∈Fqs, 有α1+q+α1+q2+···+αqs?2+qs?1=β ∈Fqs且存在qs?1個不同的元素λ ∈Fqs使得λqs?1+···+λq+λ=β, 因此對于這樣的(λ,β) 存在次數為1 的位Pλ,β ∈PF使得x(Pλ,β)=λ且y(Pλ,β)=β.

2.3 代數幾何碼

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

則關聯D和G的代數幾何碼定義為

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

命題2.3設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 在代數函數域上構造局部恢復碼

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

設F/Fq,E/Fq是滿常域為Fq的代數函數域,F為E的擴域且[F:E] =r+1,設S={P1,P2,··· ,Pm}是E中m個有理位的集合, 且每個Pi,i= 1,2,··· ,m在F/E中是完全分裂的, 即對于E中每個Pi都存在r+ 1 個次數為1 的擴張Pi1,Pi2,··· ,Pi(r+1), 設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）

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

定義映射

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

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

則其參數為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上線性無關, 若

由于1,x,··· ,xr?1在E上線性無關, 則

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

下證fj ∈L(D),fjxi至多有(r+1)deg(D)+(r ?1)deg(x)∞個零點, 設零點的個數為|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), 所以有

設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)∞.

下面給出修復方案:

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

其中0≤i ≤r ?1, 設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α}對應的符號通過插值得到, 一旦δ(x)確定, 則丟失的符號為δ(x)(Pα), 因此C(P,V) 是(n,k,r) LRC 碼, 其中參數為

下面將此構造方法應用于廣義Hermite 函數域去構造局部恢復碼.

4 廣義Hermite 函數域上的局部恢復碼

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

當s=2 時, 廣義Hermite 函數域就變成了Hermitian 函數域.

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

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

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

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

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

應用定理3.1 得到一類局部恢復碼, 其參數如下:

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

定理4.1 中最小距離的下界利用廣義Hermite 碼的一些性質在某些特殊的情況下可以得到改進. 事實上, 對于廣義Hermite 碼Cm, 選取適當的m使得V ?L(mQ∞),則C(P,V)?Cm, 由子碼的性質得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的大小.

當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 可以看出, 當q>2 時, (5) 式的最小距離的界被明顯地改進.

5 結束語

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