有理函數域上的最優局部恢復碼的構造

陳子星

安慶師范大學數學與計算科學學院,安徽安慶，246133

現代存儲系統允許幾個符號丟失的情況出現，但到目前為止，單個符號丟失的情況更為常見，因此本文著重于一個符號丟失的恢復。在分布式存儲系統中，一個符號丟失的恢復效率可以通過三個不同的指標來量化，分別是局部化參數r[1-4]、讀取位的數量[5]、恢復帶寬[6-9]，本研究關注的是局部化參數r。關于局部恢復碼(LRC)的研究，文獻[1]構造了一族最優的(n,k,r)LRC碼，但碼長受到字符集的限制，即n≤q,為了突破這一限制，文獻[2]利用代數曲線來構造LRC，需要滿足方程xr+1+brxr+…+b0=0，其中bi∈K(Y)，K(X)=K(Y)(x)，但過程復雜，本文利用代數函數域特別是有理函數域來構造LRC。

現代存儲系統為減少存儲開銷，將擦除編碼技術應用到系統中[10]，比起傳統的通過復制提高可靠性的存儲系統，更為可靠有效。本文研究的LRC碼是擦除編碼的一種。

1 局部恢復碼的定義

就LRC而言，如果一個符號丟失，可以通過至多r個其他符號來恢復。LRC的定義如下：

定義1假設C是有限域Fq上的一個[n,k]線性碼，如果對于每個i∈[n]，其中[n]:={1,2,…,n}，存在一個子集Ai?[n]{i}，|Ai|≤r和一個函數φi使得對于每個碼字x∈C有xi=φi({xj,j∈Ai})，則稱C是具有局部參數r的局部恢復碼，簡稱(n,k,r)LRC碼。

如果C是(n,k,r)LRC碼,則C的信息率滿足：

(1)

C的最小距離滿足：

(2)

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

d(C)=n-k+1

則稱碼C是MDC碼。本文從代數曲線上的LRC的構造中得到啟發，在代數函數域上構造LRC，特別地，在有理函數域上，得到了距離最優的LRC。

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

2.1 代數函數域的相關結論

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

特別地，當K上的超越元x∈F時，若F=K(x)，則F/K被稱為有理函數域。

引理1(黎曼洛赫定理) 設w是F/K的標準除子，對任意除子A∈Div(F)，有維數公式l(A)=degA+1-g+l(w-A)，若degA≥2g-1，則l(A)=degA+1-g。

引理2設一個函數域F/K和一個多項式φ(T)=anTn+an-1Tn-1+…+a1T+a0，其中ai∈F。假設存在一個位P∈PF使得以下任意一條成立vP(an)=0，vP(ai)≥vP(a0)>0，其中i=1,…,n-1，且gcd(n,vP(a0))=1。

vP(an)=0，vP(ai)≥0，i=1,…,n-1，vP(a0)<0，且gcd(n,vP(a0))=1。

則φ(T)在F[T]上是不可約的。

2.2 代數函數域上局部恢復碼的構造

設F′/Fq、F/Fq均是滿常域為Fq的代數函數域，F′是F的擴域且[F′:F]=r+1。若H={P1,…,Ps}是F中s個有理位的集合，對任意Pi∈H，i=1,2,…,s，在F′上都存在r+1個擴張Pi1,Pi2,…,Pi(r+1)，即對?Pi∈H，在F′/F中是完全分裂的。

設P={Pij|1≤i≤s,1≤j≤r+1}，則|P|=s(r+1)，設A={A1,…,As}是P的劃分，其中Ai={Pi1,Pi2,…,Pi(r+1)}，i=1,…,s。

設D是F上的除子且與H不相交(即SUPP(D)∩H=φ)，deg(D)=l≥1，設L(D)=〈fj|j=1,…,m〉，dim(L(D))=m。設x∈F′使得1,x,…,xr-1在F上線性無關，則定義在F′上的函數空間：

V=

定義映射

evA:V→F(r+1) sq

f(f(Pij),i=1,…,s,j=1,…,r+1)

則該映射的像為C(D,V)。

n=s(r+1)，k=rm，d≥n-(r+1)l-(r-1)h,其中h=deg(x),n-(r+1)l-(r-1)h>0。

3 有理函數域上的最優局部恢復碼

下面將運用同樣的構造方法來構造有理函數域上的最優LRC并修復。

設x,y都是Fq上的超越元且滿足xr+1=y，其中(r+1)|(q-1)，設(q-1)=t(r+1)，設F′=Fq(x)，F=Fq(y)，則F′/Fq、F/Fq均是Fq上的有理函數域。設多項式φ(T)=Tr+1-y∈Fq(y)[T]，其中a0=-y，ai=1,…,r，ar+1=1，選取P0:=Py-0∈PFq(y)，因為vP0(1)=0，vP0(ai)=vP0(0)=≥vP0(-y)=1，因此gcd(r+1,vP0(-y))=1，所以根據引理2可知φ(T)在Fq(y)上是不可約的多項式，所以[F′:F]=r+1。

設S={P1,…,Ps}∈ΡF是F中s個有理位的集合，對任意Pi∈S，i=1,…,s，在F′上存在r+1個擴張Pi1,…,Pi(r+1)，即?Pi∈S在F′/F上是完全分裂的。

假設0≠α∈Fq，若y=α，因為xr+1=y，則有xr+1=α，斷言f(x)=xr+1-α無重根，且若αt=1，則一定存在r+1個β∈Fq使得βr+1=α。

α=δk1(r+1)=(δk1)(r+1)

因此對于任意β是f(x)=xr+1-α∈Fq[x]的根，則有βr+1=α=(δk1)r+1?(δ-k1β)r+1=1，因為(r+1)|(q-1)則δ-k1β∈Fq，又因為δk1∈Fq，則δk1·δ-k1β=β∈Fq，因t是素數，故階為t的有t-1個，又因為當α=1時，xr+1=α∈Fq在Fq中有r+1個不同的根，設當α1,α2∈Fq且α1≠α2時，有(xr+1-α1,xr+1-α2)=1。

設Pα={P1,…,Pt}，取S={P1,…,Ps}?{P1,…,Pt}，s=|s|≤t，設F中有理位的集合為

P={Pij,1≤i≤s,1≤j≤r+1}，

則|P|=s(r+1)，設P的劃分A={A1,…,As}，其中

Ai={Pi1,…,Pi(r+1)}，i=1,…,s,

設D是F上與S不相交的除子，deg(D)=l≥1，設f1,…,fm是L(D)上的一組基，因為deg(D)=l≥2g(F)-1=-1，所以

dim(L(D))=m=deg(D)+1-g(F)=l+1

因此設x∈F′，使得1,x,…,xr-1在F上線性無關，則定義函數空間

V=〈fjxi,i=0,…,r-1,j=1,…,m〉，

f(f(Pij),i=1,…,s,j=1,…r+1)，

記該映射的像為C(D,V)。

應用引理3，可以得到以下定理：

定理上述定義的碼C(D,V)是Fq上的一組(n,k,r)LRC碼，其參數為：

n=(r+1)s，k=rm=r(l+1)，d=n-l(r+1)-(r-1)。

證明：根據引理3可以計算出n和k，以及d≥n-(r+1)l-(r-1)h，又因為在有理函數域中h=deg(x)=[Fq(x):Fq(x)]=1，因此

d≥n-l(r+1)-(r-1)，

因為碼C(D,V)的最小距離滿足

計算得

d≤(r+1)s-(l+1)r-(l+1)+2

=(r+1)s-(l+1)(r+1)+2

=(r+1)(s-l-1)+2

=(r+1)s-(r+1)l-(r+1)+2

=n-l(r+1)-(r-1)

因此

d=n-l(r+1)-(r-1)

即

則碼C(D,V)是Fq上距離最優的(n,k,r)LRC碼。

因此定義譯碼多項式為:

其中,deg(δ(x))≤r-1，且{x(Pβ)}Pβ∈Ai{Pα}，i={1,…,m}是互不相同的，丟失的符號可以通過Ai剩余r個位置Pβ∈Ai{Pα}對應的符號通過插值得到，一旦δ(x)確定，則丟失的符號為δ(x)(Pβ)。

例1取q=13，r=3，則x,y都是F13上的超越元且滿足x4=y，則t=3，設F′=F13(x)，F=F13(y)，則F′/F13、F/F13均是F13上的有理函數域，[F′:F]=4。因為|S|≤t，所以可以取|S|=3，則S={P1,P3,P9}，P的劃分A={A1,A2,A3}，其中A1={P1,1,P1,5,P1,12,P1,8}，A2={P3,2,P3,10,P3,11,P3,3}，A3={P9,4,P9,7,P9,9,P9,6}。設D=P，P是x的極點，degD=l=1，L(D)=〈1,x4〉，dim(L(D))=m=l+1=2，則函數空間V=〈fjxi,i=0,1,2,j=1,2〉={1,x,x2,x4,x5,x6}，

f(f(Pij),i=1,2,3,j=1,2,3,4)，

映射的像為C(D,V)，其中n=s(r+1)=12，k=rm=6，d=n-l(r+1)-(r-1)=5，所以碼C是F13上距離最優的(12,6,3)LRC碼。

4 結 語

本文在有理函數域上構造了距離最優的LRC，并且在F13上構造了一個距離最優的(12,6,3)LRC碼。本文是在針對一個符號丟失的情況下的恢復，后續可將此構造方法擴展至多個符號丟失的情況。

最后，我要感謝我的導師胡萬寶教授對我論文的指導。