陳雯雯，胡萬寶，崔良武，胡 帥

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

分布式存儲系統(tǒng)是指運用一定的技術(shù)手段，將原始數(shù)據(jù)分別存儲在相互獨立的若干臺設(shè)備(節(jié)點)上，常采用不同程度的冗余校驗來提高系統(tǒng)的穩(wěn)定性，現(xiàn)已被廣泛應(yīng)用。在采用編碼技術(shù)的分布式存儲系統(tǒng)中，常需要進(jìn)行節(jié)點修復(fù)。節(jié)點修復(fù)問題[1]是指當(dāng)存儲了編碼數(shù)據(jù)的節(jié)點發(fā)生失效，為了維持系統(tǒng)的穩(wěn)定性，需要再生出失效的數(shù)據(jù)并將它存儲在新的節(jié)點上替代失效節(jié)點。文獻(xiàn)研究表明，如果系統(tǒng)僅有一個節(jié)點失效，采用糾刪碼技術(shù)恢復(fù)數(shù)據(jù)時，必須要先恢復(fù)出完整的原始數(shù)據(jù)，這樣勢必會增加修復(fù)帶寬，降低修復(fù)效率。為了減小修復(fù)帶寬，提高修復(fù)效率，人們對傳統(tǒng)糾刪碼進(jìn)行了一定的改造和優(yōu)化，定義了若干種再生碼[2]解決節(jié)點修復(fù)問題。本文提出一種利用再生碼解決節(jié)點修復(fù)問題的修復(fù)方案。下面先介紹一般代數(shù)幾何碼的修復(fù)算法。

1 代數(shù)幾何碼的修復(fù)算法

有限域Fp的特征可以為偶素數(shù)，也可以為奇素數(shù)。關(guān)于代數(shù)函數(shù)域和代數(shù)幾何碼的相關(guān)概念綜述可參考文獻(xiàn)[3-4]。下面先給出方案中需要用到的跡對偶基[5]和對偶碼[6]的定義。

定義1[5]設(shè)Fp是一個有限域，F(xiàn)q是Fp的域擴(kuò)張。選取Fq在Fp上的兩組基和，若當(dāng)1≤i,j≤t時，存在一個Fq到Fp上的跡映射Tr使得則稱這兩組基為跡對偶基。

定義2[6]設(shè)是一個一般線性碼，對于一個集合，若對任意的c=滿足稱W為C的對偶碼，通常記為C⊥。

1.1 一般線性碼的修復(fù)方案

設(shè)Fq在Fp上的擴(kuò)張次數(shù)為t，對于一般線性碼將中的每一個向量看成是由一個函數(shù)賦值生成的。例如，若賦值點集合對于任意c∈ C，存在一個函數(shù)f使得因此，C可視為由若干個不同的函數(shù)f生成的一個Fqn的子空間。也就是說，將函數(shù)f看作一條信息，每一個賦值點對應(yīng)一個存儲信息的節(jié)點，相對應(yīng)的向量c=是一個碼字，c中的每個分量是Fq中的一個符號。

線性碼的修復(fù)實際上是由一組t個函數(shù)決定的[8]，具體描述：假設(shè)一個碼字，若第i個節(jié)點失效，即數(shù)據(jù)丟失，修復(fù)則需要找到一組函數(shù)，這里( i, u)中的i是指第i個節(jié)點失效，在所做的單個節(jié)點失效問題中，是固定的且滿足：對于每并且使得，由(1)式可得

因為跡函數(shù)是線性映射，所以可得t個等式

為了恢復(fù)f(αi)，需要充分檢索的信息去計算(2)式。

1.2 RS碼的修復(fù)方案

RS碼是一種特殊的線性碼，生成它的一組函數(shù)f均為低次多項式，先給出RS碼的定義。

定義3[8]設(shè)Fq是一個有限域，F(xiàn)q[ ]x是Fq上的一個多項式環(huán)，A是一個賦值點集合A=一個Fq上的k維RS碼RS被定義為

對于一個RS(A ,k)碼來說，假設(shè)失效節(jié)點存儲的信息是，則需要找到一組函數(shù)h(i,u)使得其生成的對偶碼在Venkatesan等所研究的RS碼的精確修復(fù)方案中[8]，令函數(shù)其中Tr是F到F上的跡函數(shù)，α是在失效節(jié)點的賦值點，則qpi滿足和對于所有

1.3 代數(shù)幾何碼的修復(fù)方案

代數(shù)幾何碼是RS碼的一種自然推廣，所以代數(shù)幾何碼的修復(fù)算法和RS碼的修復(fù)算法類似。對于一個代數(shù)幾何碼，由RS碼的修復(fù)方案可知，在代數(shù)幾何碼修復(fù)方案中，假設(shè)所在節(jié)點發(fā)生失效，信息丟失，要想恢復(fù)的信息，關(guān)鍵是要找到一個函數(shù)h(i,u)使得滿足bi(i)=t和對于所有

設(shè)Fp是一個有限域，F(xiàn)q是Fp的一個域擴(kuò)張，且其擴(kuò)張次數(shù)為t，選定Fq在Fp上的一組基及對偶基由(1)式可知，對于一個代數(shù)幾何碼來說，失效節(jié)點信息為

引理1[7]設(shè)m，r，d都是正整數(shù)，且滿足假設(shè)對于某個固定的存在一個函數(shù)使得，則是一個帶寬b=的再生碼，其中

基于Fp的特征是任意值的前提，下面進(jìn)行帶寬的計算。設(shè)V是Fq上的子空間，其在Fp上的維數(shù)為l。定義一個p-加性多項是Fq到Fp上的Fp-線性映射，由有限域知識可知，顯然所以根據(jù)同態(tài)定理

定理1 設(shè)Fp是一個特征為任意素數(shù)的有限域，F(xiàn)q是Fp的一個域擴(kuò)張，且其擴(kuò)張次數(shù)為t，F(xiàn)是Fq上虧格為g的函數(shù)域，是F的n+1個不同的有理位若，則是一個帶寬為的再生碼。

2 由Hermitian碼得到的再生碼

下面將給出一個Hermitian碼的例子，并對比RS碼和Hermitian碼在同等碼長下的帶寬情況。

在代數(shù)幾何碼中，當(dāng)函數(shù)域F是一個有理函數(shù)域時，相對應(yīng)的代數(shù)幾何碼就是一個RS碼，且當(dāng)碼長n=q時，帶寬b=( )n-1 log p。

設(shè)q=r2，Hermitian碼是被定義Hermitian函數(shù)域上的一種碼。在Fq上的Hermitian函數(shù)域被定義為H=Fq(x ,y)，且H滿足yr+y=xr+1，H的虧格為有N=1+q3個有理位，其中P∞是x和y唯一的共同極點，其余r3個有理位恰好由滿足集合的r3對給出。對于設(shè)D是由Hermitian函數(shù)域H上除了P∞以外的所有有理位構(gòu)成的集合，則定義Cm:=CL( )mP∞,D ，稱碼。

定義有理位Pα,β是由滿足的有理點對應(yīng)給出的。設(shè)D是由Hermitian函數(shù)域H上除了P∞以外的所有有理位構(gòu)成的集合。對于每個α∈Fq，主除子和

綜上，兩個碼在相同碼長的情況下有著相同的碼率和修復(fù)帶寬，但是RS碼定義在F729上，即每個符號存儲量為log 729，而Hermitian碼定義在一個更小的域F81上，每個符號存儲量為log 81，也就是說Her-mitian碼在數(shù)據(jù)存儲上用更小的空間達(dá)到同RS碼同樣的效果。

3 結(jié)束語