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

耿召民，胡萬(wàn)寶，錢 隆

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

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

近年來，TAMO[1]和VLADUT[2]等提出一種有效改進(jìn)修復(fù)的方法，它賦予碼的局部性，此屬性通過僅訪問r來恢復(fù)故障符號(hào)遠(yuǎn)小于k個(gè)其他符號(hào)。具有局部性的擦除碼也稱為局部修復(fù)碼（LRC），但其只用來擦除一次。在過去幾年中，局部性的概念在多個(gè)方面得到了推廣。例如，具有（r，δ）的LRC-位置允許通過讀取r個(gè)其他符號(hào)來恢復(fù)集所遭受擦除的δ-1個(gè)符號(hào)，類似CAI[3]等的保證不相交的多個(gè)可修復(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)的符號(hào)Fq表示含q個(gè)元素的有限域。

1 局部恢復(fù)碼

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

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

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

而C的最小距離滿足

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

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

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

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

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

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

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

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

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

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

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

在上述基于有限域結(jié)構(gòu)的G-多項(xiàng)式3種構(gòu)造方法中，并不能構(gòu)造出任意想要的局部參數(shù)為r的LRC碼。例如，當(dāng)p=2 時(shí)，使用上述方法無(wú)法在域F2的任意擴(kuò)張上構(gòu)造局部參數(shù)為r=5 的碼，因?yàn)閞+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)造方法的條件，也就是說無(wú)法使用上述方法在域F2的任意擴(kuò)張上構(gòu)造局部參數(shù)為r=5的碼。

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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