基于有限域結構的LRC碼的存在性討論

耿召民，胡萬寶，錢 隆

（安慶師范大學 數理學院，安徽 安慶 246133）

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

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

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

1 局部恢復碼

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

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

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

而C的最小距離滿足

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

通?；谟邢抻騺順嬙霯RC碼的方法有3種，首先介紹G-多項式，其是構造LRC碼的關鍵。

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

接下來介紹基于有限域結構構造G-多項式的常用方法。

構造1利用Fq的乘法子群進行構造。

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

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

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

2 基于有限域結構的LRC碼存在性討論

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

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

具體說明如下：

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

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

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

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

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

例1任意給定素數p，當r=p2+p-1時，由引理1可知，用上述三種方法無法構造出G-多項式。

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

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

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

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

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

4 結束語

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