有理函數(shù)域上的最優(yōu)局部恢復(fù)碼的構(gòu)造

陳子星

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

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

現(xiàn)代存儲(chǔ)系統(tǒng)為減少存儲(chǔ)開銷，將擦除編碼技術(shù)應(yīng)用到系統(tǒng)中[10]，比起傳統(tǒng)的通過復(fù)制提高可靠性的存儲(chǔ)系統(tǒng)，更為可靠有效。本文研究的LRC碼是擦除編碼的一種。

1 局部恢復(fù)碼的定義

就LRC而言，如果一個(gè)符號(hào)丟失，可以通過至多r個(gè)其他符號(hào)來恢復(fù)。LRC的定義如下：

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

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

(1)

C的最小距離滿足：

(2)

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

d(C)=n-k+1

則稱碼C是MDC碼。本文從代數(shù)曲線上的LRC的構(gòu)造中得到啟發(fā)，在代數(shù)函數(shù)域上構(gòu)造LRC，特別地，在有理函數(shù)域上，得到了距離最優(yōu)的LRC。

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

2.1 代數(shù)函數(shù)域的相關(guān)結(jié)論

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

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

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

引理2設(shè)一個(gè)函數(shù)域F/K和一個(gè)多項(xiàng)式φ(T)=anTn+an-1Tn-1+…+a1T+a0，其中ai∈F。假設(shè)存在一個(gè)位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 代數(shù)函數(shù)域上局部恢復(fù)碼的構(gòu)造

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

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

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

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 有理函數(shù)域上的最優(yōu)局部恢復(fù)碼

下面將運(yùn)用同樣的構(gòu)造方法來構(gòu)造有理函數(shù)域上的最優(yōu)LRC并修復(fù)。

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

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

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

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

因此對于任意β是f(x)=xr+1-α∈Fq[x]的根，則有βr+1=α=(δk1)r+1?(δ-k1β)r+1=1，因?yàn)?r+1)|(q-1)則δ-k1β∈Fq，又因?yàn)棣膋1∈Fq，則δk1·δ-k1β=β∈Fq，因t是素?cái)?shù)，故階為t的有t-1個(gè)，又因?yàn)楫?dāng)α=1時(shí)，xr+1=α∈Fq在Fq中有r+1個(gè)不同的根，設(shè)當(dāng)α1,α2∈Fq且α1≠α2時(shí)，有(xr+1-α1,xr+1-α2)=1。

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

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

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

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

設(shè)D是F上與S不相交的除子，deg(D)=l≥1，設(shè)f1,…,fm是L(D)上的一組基，因?yàn)閐eg(D)=l≥2g(F)-1=-1，所以

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

因此設(shè)x∈F′，使得1,x,…,xr-1在F上線性無關(guān)，則定義函數(shù)空間

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

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

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

應(yīng)用引理3，可以得到以下定理：

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

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

證明：根據(jù)引理3可以計(jì)算出n和k，以及d≥n-(r+1)l-(r-1)h，又因?yàn)樵谟欣砗瘮?shù)域中h=deg(x)=[Fq(x):Fq(x)]=1，因此

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

因?yàn)榇aC(D,V)的最小距離滿足

計(jì)算得

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上距離最優(yōu)的(n,k,r)LRC碼。

因此定義譯碼多項(xiàng)式為:

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

例1取q=13，r=3，則x,y都是F13上的超越元且滿足x4=y，則t=3，設(shè)F′=F13(x)，F(xiàn)=F13(y)，則F′/F13、F/F13均是F13上的有理函數(shù)域，[F′:F]=4。因?yàn)閨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}。設(shè)D=P，P是x的極點(diǎn)，degD=l=1，L(D)=〈1,x4〉，dim(L(D))=m=l+1=2，則函數(shù)空間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上距離最優(yōu)的(12,6,3)LRC碼。

4 結(jié) 語

本文在有理函數(shù)域上構(gòu)造了距離最優(yōu)的LRC，并且在F13上構(gòu)造了一個(gè)距離最優(yōu)的(12,6,3)LRC碼。本文是在針對一個(gè)符號(hào)丟失的情況下的恢復(fù)，后續(xù)可將此構(gòu)造方法擴(kuò)展至多個(gè)符號(hào)丟失的情況。

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