關于修復代數幾何碼的一個注記

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

（安慶師范大學數學與計算科學學院，安徽安慶246133）

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

1 代數幾何碼的修復算法

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

定義1[5]設Fp是一個有限域，Fq是Fp的域擴張。選取Fq在Fp上的兩組基和，若當1≤i,j≤t時，存在一個Fq到Fp上的跡映射Tr使得則稱這兩組基為跡對偶基。

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

1.1 一般線性碼的修復方案

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

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

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

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

1.2 RS碼的修復方案

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

定義3[8]設Fq是一個有限域，Fq[ ]x是Fq上的一個多項式環，A是一個賦值點集合A=一個Fq上的k維RS碼RS被定義為

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

1.3 代數幾何碼的修復方案

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

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

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

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

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

2 由Hermitian碼得到的再生碼

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

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

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

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

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

3 結束語