吳珊珊

（安慶師范大學數(shù)理學院，安徽安慶246133）

在大數(shù)據(jù)時代背景下，數(shù)據(jù)的傳輸呈指數(shù)型爆炸增長，若想有效地存儲數(shù)據(jù)，就得引入冗余和編碼技術。最簡單的冗余形式就是復制，但復制會帶來大量存儲空間的消耗[1]。糾刪碼是存儲系統(tǒng)容錯的主要方法[2]，但是其容錯能力和運算效率存在缺陷。擦除碼較復制而言，冗余和可利用性得到提高，只需較小的存儲開銷就能實現(xiàn)較高的數(shù)據(jù)可利用性，但其恢復丟失的冗余效率仍然較低。關于擦除碼，學者重點關注擦除碼的可恢復的局部性[3]，即發(fā)現(xiàn)碼的一種局部恢復性[4]，從而研究一類具有局部性的最大可恢復碼，并對局部可恢復碼（LRC）及其參數(shù)展開研究?？紤]長度為n、帶有k個信息符號的碼，若碼字的第i個符號丟失，可以通過訪問至多ri(ri?n)個其他符號來恢復，則稱該碼具有良好的局部性ri。

因為大部分的碼不具有良好的局部性，且可以直接使用的LRC碼的構造太少，所以，LRC碼成為研究熱點。2011年，Gopalan等通過深入地研究線性碼中冗余、擦除校正與符號局部性的關系，發(fā)現(xiàn)了碼的距離上界和具有局部性的碼符之間的關系，開創(chuàng)了碼符局部性的理論研究[3]。隨后Papailiopoulos證明了Gopalan等提出的局部性碼符之間的確存在一種關系，并且在(r+1)|n的條件下是可以實現(xiàn)的，進而給出了LRC碼的定義、構造、距離上界及速率上界等參數(shù)上界結論[4]。Gopalan等發(fā)現(xiàn)少有對碼的另一個參數(shù)字母表大小的研究，于是從碼字符號的局部性研究中發(fā)現(xiàn)了與字母大小相關的碼的最小距離上界[5]。2013年，Silberstein等在Gopalan和Papailiopoulos的結論上又提出了一種新的LRC碼族的構造[6]，他們不僅將Gopalan提出的數(shù)量LRC碼推廣到向量LRC碼，而且這個新的LRC碼族的構造與Papailiopoulos提出的構造相比具有全符號局部性，利用這種全符號局部性構造得到的碼可以更準確、更有效地恢復丟失的節(jié)點。2014年至2016年期間，Tamo和Barg等先后提出了LRC碼族的概念，構造了當r+1|n時達到界的最優(yōu)LRC碼[7]。

以上研究在有限域、代數(shù)曲線、代數(shù)曲面及一些著名函數(shù)域上構造LRC碼可以得到局部性更小的、速率更大的碼，實現(xiàn)較低的恢復成本，但是它們的構造復雜、譯碼困難，因此，本文在代數(shù)函數(shù)域上構造LRC碼，且這類LRC碼的恢復過程只需經過一次減法運算。

1 預備知識

我們對于LRC碼的構造完全基于代數(shù)函數(shù)域上，相關理論和符號來自于《代數(shù)函數(shù)域與碼》[8]?，F(xiàn)給出代數(shù)幾何碼的定義和3個命題，其中，代數(shù)幾何碼是構造LRC碼的基礎。

設C是有限域Fq上的碼，下面給出局部恢復碼的定義。

定義2[7]對任意的i∈[n]:={1,2,3,…,n}，存在子集Ai?[n]{i}， ||Ai≤r和函數(shù)φi，使得對每個碼字x=(x1,x2,x3,…,xn)∈C，都有xi=φi({xj,j∈Ai})，則稱碼C?Fnq是具有局部參數(shù)r的局部恢復碼。

若用(n,k,d,r)和[n,k,d,r]分別表示碼長為n、碼的個數(shù)為qk、碼的最小距離為d、局部參數(shù)為r的碼和線性碼，則LRC碼的參數(shù)具有以下重要性質。

定理1[4]設C是在Fq上的[n,k,d,r]LRC碼，則

當式（2）取等號時，C叫做距離最優(yōu)LRC碼。局部參數(shù)r滿足1≤r≤k，且當r=k時，

命題1[8]考慮函數(shù)域F K和多項式φ(T)=anTn+an-1Tn-1+an-2Tn-2+…+a0，其中ai∈F。假設存在位P∈PF，對于i=1,2,3,…,n-1，vP(an)=0，vP(ai)≥0，vP(a0)<0且gcd(n,vP(a0))=1，則φ(T)在F[T]上是不可約多項式。

命題3[8]設K=Fq2是勢為q2的有限域，H=Fq2(x,y)，其中q是一個素數(shù)的冪，x和y滿足xq+x=yq+1，則H被定義為在Fq2上的Hermite函數(shù)域，且H在K上有q3+1個次數(shù)為1的位，即對?β∈K，存在q個元素α∈K使得αq+α=βq+1。

2 在代數(shù)函數(shù)域上構造局部恢復碼

從而h至多有l(wèi)?deg E+(l-2)?deg(x)∞個零點。同樣可以證明，對任意的f∈V，f至多有l(wèi)?deg E+(l-2)?deg(x)∞個零點，因而每個碼字的重量

最后證明維數(shù)。

由于f∈V至多有l(wèi)?deg E+(l-2)?deg(x)∞個零點，l?deg E+(l-2)?deg(x)∞

又C是線性的，所以d≥n-l?deg E-(l-2)?deg(x)∞。

在Hermite函數(shù)域上構造具體的LRC碼之前，我們需要介紹兩個引理。

引理1若L(T):=Tn+a1T+a0∈Fq[T]是Fq上的三項式，x1,x2,x3,…,xn是其在Fq的擴域上的n個根，記其初等對稱多項式為

記對稱多項式Sk=x1k+x2k+x3k+…+xnk(0≤k≤n)，則對于1≤k≤n-2時，有Sk=0。

證明對于k≤n，由Newton公式[9]知，Sk和σk之間有以下關系：

由于L(T)=Tn+a1T+a0是三項式，利用根與系數(shù)的關系[10]有：

當1≤k≤n-2時，都有Sk=0。

最后一步等式是由Char Fq|l得到的。

類似地，將引理2運用到定理2，得到碼的局部恢復性定理。

設F=Fq(y)是有理函數(shù)域，F(xiàn)′=F(x)=Fq(y)(x)是F的單擴張，擴張次數(shù)[F′:F]=l且Char Fq|l，對于A(T)∈Fq[T]，a0,a1∈Fq，有xl+a1x+a0-A(y)=0。對于任意的j=1,2,3,…,s，βj∈Fq，Pβj是F′F中完全分裂的位，即對?i=1,2,3,…,l，Pαi,βj是Pβj的l個擴張。F的有理位構成集合S:={Pβ1,Pβ2,Pβ3,…,Pβs}，Aj:={Pαi,βj:1≤i≤l}，F(xiàn)′的有理位構成集合P:={Pαi,βj:1≤i≤l,1≤j≤s}，則|P|=ls。

設E∈Div(F)是F中使得supp(E)?S=?的除子，{f1,f2,f3,…,fm}是L(E)的一組基。設x∈F′使得{1,x,x2,…,xs-2}在F上線性無關且vPαi,βj(x)≥0，定義函數(shù)空間

記C:=Im(ev)是其映射的像，由代數(shù)幾何碼的定義知C是線性碼。

定理3上述構造的碼C是Fq上的[n,k,r]LRC碼，其參數(shù)為

證明由定理2知，C是Fq上的[n,k,d]碼，且各參數(shù)滿足式（11）。對?f1，f2∈V，λ,μ∈Fq，若

則λc1+μc2=((λf1+μf2)(Pα1,β1),(λf1+μf2)(Pα1,β2),(λf1+μf2)(Pα1,β3),…，(λf1+μf2)(Pαl,βs))∈C，因此C是Fq上的線性碼。

下面證明C是局部恢復碼。

對于碼字c中的每個坐標值ci都可以被其它l-1個坐標值來恢復，因而C是局部恢復碼，并且其恢復僅用一次減法即可得到。

與插值多項式解碼進行對比，不難發(fā)現(xiàn)利用插值多項式構造更為復雜。而經過改進得到的局部恢復性定理，只需使用一次線性運算就能進行解碼。

下面將上述定理應用于具體的Hermite函數(shù)域上。

并且這類LRC碼可以通過一次線性減法運算進行快速恢復。

下面結合上述定理和引理，對本例進行一些說明。

令φ(T):=Tq+T-yq+1∈F[T]，根據(jù)命題1，顯然φ(T)是x在F上的極小多項式：因為vP∞(y)=-1，vP∞(1)=0 ，vP∞(-yq+1)=vP∞(yq+1)=(q+1)?vP∞(y)=-(q+1)<0 ，φ(x)=xq+x-yq+1=0 且gcd(q,vQ(-yq+1))=gcd(q,(q+1))=1，所以φ(T)是x在F上的極小多項式且degφ(T)=[F′:F]=q。

對任意的β∈K，多項式φα(T):=Tq+T-βq+1恰有q個互不相同的根：因為φα′(T)=q?Tq-1+1=1，故gcd(degφα(T),degφ′α(T))=1，因此φα(T)無重根。再由命題3知，對任意的β∈K，都存在q個元素αi(i=1,2,3,…,q)∈K都有等式αiq+αi=βq+1成立，顯然是φα(T)=0的q個根，因此φα(T)有q個互異的根。對所有這樣的(αi,β)，都存在唯一的次數(shù)為1的位P′αi,β∈PH，即存在q個不同的具有性質P′αi,β|P′β的位P′αi,β∈PH，故可驗證P′βj(j=1,2,3,…,q2)∈H/K是完全分裂的。對任意的P′βj(j=1,2,3,…,q2)，將其q個擴張記為A′j:={ P′α1,βj,P′α2,βj,P′α3,βj,…,P′αq,βj}，將H中除Q∞以外的q3個有理位構成的集合記為P′:={P′αi,βj:1≤i≤q,1≤j≤q2}。因為E=q(q-1)Q∞，故L(E)=L(q(q-1)Q∞)，?(E)≥deg E+1-g=

所以有deg E=q(q-1)>2g-1=q(q-1)-1，從而

3 結束語

綜上所述，本文首先在代數(shù)函數(shù)域上構造了一類局部修復碼，然后給出它們的參數(shù)，接著證明丟失的碼字c=(c1,c2,c3,…,cn)坐標值ci滿足ci=-，其中l(wèi)是擴張次數(shù)，cik(k=1,2,3,…,l-1)是碼字c中的l-1個分量，故可利用三項式的一次線性減法運算去恢復其他丟失的位置。通過一個具體的例子，闡明了在具體的Hermite函數(shù)域上如何利用一個三項式上的代數(shù)函數(shù)域構造一類LRC碼及其快捷恢復。將本方法進一步推廣到Kummer擴張、Artin-Schreier擴張等代數(shù)函數(shù)域上，也一樣可以得到較好的結果。