耿召民，胡萬寶，錢 隆

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

大型云存儲和分布式文件系統(tǒng)，如亞馬遜彈性塊存儲（EBS）和谷歌文件系統(tǒng)（GoogleFS），由于其規(guī)模巨大，經(jīng)常發(fā)生磁盤故障。為保護數(shù)據(jù)完整性，將編碼理論用于對磁盤故障導(dǎo)致的丟失數(shù)據(jù)進行恢復(fù)。最簡單的解決方案是跨越不同磁盤來直接復(fù)制數(shù)據(jù)包。然而，這種方案需要大量存儲空間和較高運行速度，成本高昂。也有其他方案，例如將(n,k) 最大值的擦除碼、最大距離可分離（MDS）碼用作存儲碼。這些代碼將k個信息符號編碼為n個符號并將它們存儲在n個磁盤上。與復(fù)制相比，這個方案有較大改進，冗余度有所提高。然而對于MDS代碼而言，即便只有一個磁盤出現(xiàn)故障，系統(tǒng)也需要訪問k個幸存磁盤以恢復(fù)丟失的符號，這使得修復(fù)過程成本高昂。

近年來，TAMO[1]和VLADUT[2]等提出一種有效改進修復(fù)的方法，它賦予碼的局部性，此屬性通過僅訪問r來恢復(fù)故障符號遠小于k個其他符號。具有局部性的擦除碼也稱為局部修復(fù)碼（LRC），但其只用來擦除一次。在過去幾年中，局部性的概念在多個方面得到了推廣。例如，具有（r，δ）的LRC-位置允許通過讀取r個其他符號來恢復(fù)集所遭受擦除的δ-1個符號，類似CAI[3]等的保證不相交的多個可修復(fù)集合的局部性研究。構(gòu)造LRC碼常用的數(shù)學(xué)工具為基于有限域結(jié)構(gòu)[2,4-9]或代數(shù)函數(shù)域（代數(shù)曲線）的自同構(gòu)群[2-3,7,10]。

本文討論了用代數(shù)組合等方法來構(gòu)造LRC碼，其可以部分解決上述工具不能解決的問題，其中正文出現(xiàn)的符號Fq表示含q個元素的有限域。

1 局部恢復(fù)碼

本文給出LRC碼的正式定義如下。

定 義1[1]設(shè)C為Fq上的(n,k)線性碼，若對于i∈{1,2,3,…,n}，存 在r個元素 的子集Ii?{1,2,3,…,n}{i}和一個函數(shù)φi→Fq，對于每個碼字x∈C，都有xi=φi(xi1,xi2,xi3,…,xir)，其中i1,i2,i3,…,ir是Ii中的r個元素，則稱C是(n,k,r)局部恢復(fù)碼，簡稱(n,k,r)LRC 碼。對于給定的坐標(biāo)i∈{1,2,3,…,n}，集合Ii稱作i的恢復(fù)集。

定理1[1]設(shè)C為Fq上(n,k,r)LRC碼，則C的信息率滿足

而C的最小距離滿足

若（2）式等號成立，則稱C為距離最優(yōu)的(n,k,r)LRC碼。

通?；谟邢抻騺順?gòu)造LRC碼的方法有3種，首先介紹G-多項式，其是構(gòu)造LRC碼的關(guān)鍵。

定義2設(shè)A?Fq，A是元素個數(shù)為n的集合，r+1 能整除n，若一個多項式g(x)∈Fq[x]滿足下列條件：（1）deg(g(x))=r+1，（2）存在關(guān)于集合[A]的劃分，|Ai|=r+1，i=1,2,3,…,，使得g(x)在每個Ai上均為常數(shù)，即對?α、β∈Ai有g(shù)(α)=g(β)，則稱g(x)是關(guān)于劃分A的G-多項式。

接下來介紹基于有限域結(jié)構(gòu)構(gòu)造G-多項式的常用方法。

構(gòu)造1利用Fq的乘法子群進行構(gòu)造。

構(gòu)造2利用Fq(q=ps)的加法子群進行構(gòu)造。

構(gòu)造3利用Fq(q=ps)子域上的向量空間方法進行構(gòu)造。

注在構(gòu)造3中，由于H在Fpl的乘法運算下封閉，所以H可視為Fpl上的向量空間。

2 基于有限域結(jié)構(gòu)的LRC碼存在性討論

上述三種構(gòu)造方法可歸納為：假設(shè)在Fp的域擴張上構(gòu)造一個G-多項式，其在元素個數(shù)為mpt的坐標(biāo)數(shù)組的不相交子集上為常數(shù)，其中m與p互素，則，

（1）若t=0，可以使用滿足pl≡1(modm)的某些擴域的乘法子群，如構(gòu)造1；（2）若t＞0且m=1，可以使用加法子群，如構(gòu)造2；（3）若t,m＞1且t為l的倍數(shù)，其中l(wèi)為pl≡1(modm)的最小整數(shù)，則這種構(gòu)造是通過結(jié)合域的加法和乘法結(jié)構(gòu)來完成的，即向量空間法，如構(gòu)造3。

具體說明如下：

（1）當(dāng)t=0 時，m|H|=r+1=mpt=m，由pl≡1(modm)可得m|(pl-1)，即子群屬于，故可以使用某些擴域Fpl的乘法子群；（2）當(dāng)t＞0，m=1時，由m|H|=r+1=mpt可得H為的加法子群，其階為pt，故可以使用構(gòu)造2 的加法子群；（3）當(dāng)t,m＞1且l|t時，有m|H|=mpt，而l為pl≡1(modm)的最小整數(shù)，其保證了H在Fpl的乘法運算下封閉。

在上述基于有限域結(jié)構(gòu)的G-多項式3種構(gòu)造方法中，并不能構(gòu)造出任意想要的局部參數(shù)為r的LRC碼。例如，當(dāng)p=2 時，使用上述方法無法在域F2的任意擴張上構(gòu)造局部參數(shù)為r=5 的碼，因為r+1=5+1=6=3×2，所以m=3。又有l(wèi)=2 為使得2l≡1(mod3)成立的最小整數(shù)，但t=1，2|/（lt不為l的倍數(shù)），則發(fā)現(xiàn)不滿足上述構(gòu)造方法的條件，也就是說無法使用上述方法在域F2的任意擴張上構(gòu)造局部參數(shù)為r=5的碼。

下面我們將討論對于任意素數(shù)p，r的取值滿足某些條件時，無法采用上述三種方法來構(gòu)造出G-多項式，從而得不到想要的LRC碼情況。

引理1對于給定素數(shù)p，當(dāng)r滿足時，（其中m＞1）上述三種方法不能構(gòu)造出特征為p的有限域上局部參數(shù)為r的G-多項式。

證明因為r+1=mp，所以t=1。又因為p≡1(modm)且(m,p)=1，所以l≠1。從而可得l|/t，即不滿足上述三種構(gòu)造的條件，從而無法用上述方法構(gòu)造G-多項式。

例1任意給定素數(shù)p，當(dāng)r=p2+p-1時，由引理1可知，用上述三種方法無法構(gòu)造出G-多項式。

在下文中，考慮使用代數(shù)組合等方法來討論局部參數(shù)為r的LRC碼存在條件。

3 具有局部參數(shù)r的LRC碼存在的充分條件

對于給定的參數(shù)r，雖然無法用基于有限域的上述三種方法構(gòu)造G-多項式，但仍可以通過其他方法構(gòu)造。下面用組合代數(shù)的方法先得出G-多項式存在的充分條件，進而給出LRC碼存在的條件。

定理2（充分條件）在有限域Fq上，對于正整數(shù)r，當(dāng)qr時，G-多項式存在。

下面構(gòu)造出一類LRC碼，由引理1可知，這類碼是不能用前面三種方法來構(gòu)造。

4 結(jié)束語

本文主要通過代數(shù)組合等方法，對有限域上G-多項式的存在性進行了討論，并介紹了對于任意的素數(shù)p，在有限域Fq上局部參數(shù)為r=p2+p-1的LRC碼存在性。以后在本文基礎(chǔ)上，可以考慮解決利用代數(shù)函數(shù)域或代數(shù)曲線上自同構(gòu)群解決所不能解決的問題。