邢朝平

（上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海200030）

隨著計算機技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展，數(shù)據(jù)正以爆炸式的速度增長，對存儲系統(tǒng)提出了巨大的挑戰(zhàn).分布式存儲系統(tǒng)因其海量存儲能力、高擴展性和低成本等特性受到廣泛開發(fā)和使用.面臨海量數(shù)據(jù)存儲的大背景，當(dāng)前大型分布式存儲系統(tǒng)的存儲規(guī)模越來越大，存儲設(shè)備的質(zhì)量往往得不到保障，導(dǎo)致存儲系統(tǒng)中的節(jié)點出現(xiàn)故障.如何有效保障數(shù)據(jù)可靠性也成為當(dāng)前分布式存儲系統(tǒng)重點關(guān)注的問題之一.為了保障數(shù)據(jù)的可靠性，傳統(tǒng)的方法是使用備份的方法.但是隨著數(shù)據(jù)爆炸式增長，存儲成本越來越為大型分布式存儲系統(tǒng)所關(guān)注.備份的方法需要占用大量的存儲空間.相較于備份這種容錯技術(shù)，基于糾刪碼的容錯存儲技術(shù)能夠在保證一定的可靠性的前提下，降低冗余存儲開銷，因而在實際存儲系統(tǒng)中被廣泛的部署.國際上很多數(shù)據(jù)存儲的大公司，例如谷歌、微軟、Dropbox、Windows Azure、HDFS、Amazon等已經(jīng)相繼采用糾刪碼技術(shù)來保證存儲系統(tǒng)中數(shù)據(jù)的可靠性.糾刪碼起源于通信傳輸領(lǐng)域，原先主要是用于解決數(shù)據(jù)傳輸中的糾錯問題，后來逐漸應(yīng)用到存儲系統(tǒng)中的數(shù)據(jù)檢錯和糾錯問題中，以提高存儲系統(tǒng)的可靠性.目前，根據(jù)存儲系統(tǒng)應(yīng)用的特點和需求，人們對糾刪碼進(jìn)行了一系列的推廣并且針對具體的存儲模型提出了各種各樣的解決方案.

良好的容錯技術(shù)通常要求存儲系統(tǒng)具有低的冗余開銷、低修復(fù)帶寬以及高的錯誤容忍度.如何在這三者之間達(dá)到最優(yōu)的權(quán)衡是該領(lǐng)域的關(guān)鍵研究方向.傳統(tǒng)的糾刪碼的思想是當(dāng)出現(xiàn)錯誤的時候，利用碼的全局糾錯能力把整個碼字都恢復(fù)出來.然而已有統(tǒng)計數(shù)據(jù)表明在存儲系統(tǒng)中，很大的可能都是一個節(jié)點或者少數(shù)幾個節(jié)點失效，因而大多數(shù)研究主要針對如何以較低的修復(fù)帶寬來修復(fù)一個或兩個失效的節(jié)點.為了降低修復(fù)帶寬，人們提出了局部修復(fù)碼的概念，即通過訪問少數(shù)可用節(jié)點就可恢復(fù)失效的節(jié)點，從而達(dá)到比較少的計算量及帶寬.如今局部修復(fù)碼在分布式存儲中已被廣泛應(yīng)用，尤其是在大數(shù)據(jù)的可靠性及云存儲方面起著重要作用.

本文介紹國際上目前比較熱門的三類局部修復(fù)碼，即經(jīng)典的局部修復(fù)碼、再生碼和極大局部修復(fù)碼.重點是介紹這三類碼的最優(yōu)性質(zhì).第一節(jié)介紹基本概念及必要的基礎(chǔ)知識.第二節(jié)綜述最優(yōu)局部修復(fù)碼及構(gòu)造.第三節(jié)綜述達(dá)到cut-set界的再生碼及構(gòu)造.最后一節(jié)綜述最優(yōu)極大局部修復(fù)碼及構(gòu)造.

1 基本概念

本節(jié)將介紹一些基本概念及必要的基礎(chǔ)知識，包括線性碼、廣義Reed-Solomon碼以及局部譯碼等相關(guān)結(jié)論.這些基礎(chǔ)知識為后面的研究提供了理論依據(jù).下面首先介紹碼的一些相關(guān)結(jié)論，讀者可參考文獻(xiàn)［1-2］.設(shè)q為一個素數(shù)冪，F(xiàn)q表示含有q個元素的有限域表示Fq上的n維向量空間，即

1.1 碼的相關(guān)結(jié)論的每個非空子集C稱為一個碼長為n的q元碼，C中向量叫做碼字，｜C｜稱為碼字個數(shù)，k＝logq｜C｜稱為信息位數(shù).若碼長為n的q元碼C的碼字個數(shù)｜C｜＝M，則稱C為（n，M）q碼.若恰為Fq-線性子空間，則稱C為q元線性碼.此時碼的信息位數(shù)k恰為子空間C的維數(shù).碼長為n，信息位數(shù)為k的q元線性碼可以表示成［n，k］q.以線性碼C的一組基為行向量構(gòu)成的矩陣G稱為C的生成矩陣，以G的解空間的一組基為行向量構(gòu)成的矩陣H稱為C的校驗矩陣.記

為C的對偶碼.

除了碼長和碼字個數(shù)（或信息位數(shù)）之外，碼還有一個非常重要的參數(shù)——最小距離.在介紹最小距離之前，先簡單回顧一下Hamming距離.設(shè)向量

記［n］＝｛1，2，…，n｝，向量u的支撐集定義為

向量u的漢明重量wtH（u）定義為

兩個向量u、v的Hamming距離dH（u，v）定義為

由此可以給出碼的最小距離的定義（在本文余下部分，若無混淆的話將省略下標(biāo)H）.

定義1.1設(shè)是一個q元碼.C的最小距離d（C）定義為

特別地，線性碼C的最小距離為

碼長為n，信息位數(shù)為k，最小距離為d的q元線性碼可以表示成［n，k，d］q.碼的各個參數(shù)之間彼此制約，比如常用的Singleton界.

引理1.1［2］（Singleton界）q元［n，k，d］線性碼C的參數(shù)滿足

若q元［n，k，d］線性碼C的參數(shù)滿足n+1＝k+d，則稱碼C為極大距離可分碼，簡稱為MDS碼.

為了更好地描述MDS碼，接下來引入信息集的概念.

定義1.2設(shè)C為q元（n，qk）碼.若I?［n］滿足｜I｜＝k且

其中cI是c在I上的投影，則稱I為C的一個信息集.

MDS碼是一類非常重要的碼，糾錯能力強，在局部修復(fù)碼中有著非常廣泛的應(yīng)用.下面給出MDS碼的信息集的性質(zhì).

引理1.2q元（n，qk）碼C是MDS碼當(dāng)且僅當(dāng)每個元素個數(shù)為k的子集I?［n］都是C的一個信息集.

證明一方面，設(shè)（n，qk）q碼C是MDS碼，I?［n］是任一元素個數(shù)為k的集合.考慮映射

由C為MDS碼可知映射π是單射，所以

由定義可知，I?［n］是C的一個信息集.

另一方面，設(shè)集合［n］的每個元素個數(shù)為k的子集I都是C的一個信息集.反證，假設(shè)C不是MDS碼，則有d≤n-k.從而存在兩個碼字u，v∈C使得d（u，v）＝d，即

所以

不妨設(shè)I是的一個子集，且｜I｜＝k，則I是C的一個信息集.根據(jù)定義有

（1）與（2）式矛盾，假設(shè)不成立，因此C是MDS碼.

下面的引理總結(jié)了MDS碼的若干等價刻畫.

引理1.3［3］設(shè)［n，k］q線性碼C的生成矩陣和校驗矩陣分別是G和H，則下面的結(jié)論是等價的：

1）C是MDS碼；

2）H的任意n-k列線性無關(guān)；

3）G的任意k列線性無關(guān)；

4）C⊥是MDS碼；

5）任意一個元素個數(shù)為k的集合I?［n］都是C的一個信息集；

6）任意一個元素個數(shù)為n-k的集合I?［n］都是C⊥的一個信息集.

回顧一類最常見的MDS碼——廣義Reed-Solomon碼.設(shè)α1，α2，…，αn是有限域Fq中n個不同的元素（從而n≤q），v1，v2，…，vn均為Fq中的非零元素，整數(shù)k滿足1＜k＜n.記a＝（α1，α2，…，αn）和v＝（v1，v2，…，vn）.

定義1.3廣義Reed-Solomon碼被定義為GRSk（a，v）＝｛（v1f（α1），v2f（α2），…，vnf（αn））：

f（x）∈Fq［x］；degf（x）＜k｝.

引理1.4［1］GRSk（a，v）是［n，k，n-k+1］q線性碼，因此GRSk（a，v）是MDS碼.

引理1.5［2］GRSk（a，v）的對偶碼也是廣義Reed-Solomon碼，并且有

1.2 MRD碼和對偶基通過向量空間的Fq-同構(gòu)，可以把Fq N中的元素看做是中的列向量.因此，向量對應(yīng)一個Fq上的N×n矩陣U（不妨設(shè)n≤N）.

定義1.4兩個向量之間的秩距離dR（u1，u2）定義為rank（U1-U2），其中U1，U2∈FqN×n分別對應(yīng)u1，u2.的每一個子集C稱為一個秩度量碼.秩度量碼C的最小秩距離dR（C）定義為

若C是的一個Fq N-子空間，則稱C為線性秩度量碼.類似于經(jīng)典碼的Singleton界，秩度量碼的參數(shù)滿足如下結(jié)論.

引理1.6［4］（秩度量碼的Singleton界） 維數(shù)為k，最小秩距離為d的Fq N-線性秩度量碼C?的參數(shù)滿足

達(dá)到Singleton界的秩度量碼被稱為最大秩距離碼（簡稱為MRD碼）.文獻(xiàn)［4］給出了MRD碼的判別準(zhǔn)則.

引理1.7［4］設(shè)是維數(shù)為k的Fq N-線性秩度量碼，其生成矩陣為則C是MRD碼當(dāng)且僅當(dāng)對于每個中任意秩為k的矩陣M，矩陣GMT是可逆的.

下面介紹有限域上的對偶基.

定義1.5設(shè)Fq／Fp是有限域擴張，且

設(shè)｛ζ1，ζ2，…，ζt｝是Fq的一組Fp-基，若Fq上另一組Fp-基｛θ1，θ2，…，θt｝滿足

其中Tr是Fq到Fp的跡映射，則稱｛θ1，θ2，…，θt｝為｛ζ1，ζ2，…，ζt｝的對偶基.

已知對于Fq的任意一組Fp-基，其對偶基總是存在的［5］.可以利用對偶基和跡映射將擴域上元素表示出來.若固定Fq的一組Fp-基｛ζ1，ζ2，…，ζt｝及其對偶基｛θ1，θ2，…，θt｝，對于任意的α∈Fq，不妨設(shè)其中ai∈Fp，則對于任意的j∈［n］，由對偶基定義可知

因此α可表示為

1.3 糾刪碼和局部譯碼在分布式網(wǎng)絡(luò)存儲系統(tǒng)中需要考慮的是如何修復(fù)某個（些）故障的節(jié)點.這種類型的錯誤稱為刪除錯誤，即錯誤的位置是已知的.本文研究的是在網(wǎng)絡(luò)存儲中對刪除錯誤使用局部譯碼來恢復(fù)網(wǎng)絡(luò)中的某個故障節(jié)點，即用網(wǎng)絡(luò)中的部分而不是全部節(jié)點去修復(fù).對存儲系統(tǒng)中使用的刪除編碼通常要滿足以下要求：1）局部性低，用盡可能少的節(jié)點去修復(fù)；2）帶寬低，修復(fù)需下載的數(shù)據(jù)量盡可能?。?）節(jié)點計算少；4）硬件實現(xiàn)容易；5）有高效的譯碼算法等.

事實上，碼的最小距離和可糾正刪除錯誤個數(shù)之間有密切的關(guān)系.

引理1.8q元（n，M）碼C可糾正d-1個刪除錯誤當(dāng)且僅當(dāng)d（C）≥d.

證明（n，M）q碼C可糾正d-1個刪除錯誤等價于：對于任意的元素個數(shù)為d-1的集合I?［n］以及任意的u，v∈C，u＝v當(dāng)且僅當(dāng)uˉI＝vˉI，其中ˉI＝［n］＼I.

一方面，設(shè)d（C）≥d.若對于任意的元素個數(shù)為d-1的集合I?［n］以及任意的u，v∈C有uˉI＝vˉI，則有d（u，v）≤｜I｜＝d-1，這表明u＝v.

另一方面，設(shè)對于任意的元素個數(shù)為d-1的集合I?［n］以及任意的u，v∈C，u＝v當(dāng)且僅當(dāng)uˉI＝vˉI.假設(shè)d（C）＜d，則存在兩個碼字u≠v使得d（u，v）≤d-1.設(shè)J是u-v的支撐集，則｜J｜≤d-1.選擇I?［n］滿足｜I｜＝d-1，且J?I，則有uˉI＝vˉI，進(jìn)而u＝v，與u≠v矛盾.

利用上面的引理可以直接得到如下結(jié)論.

引理1.9q元（n，M）碼C在集合R?［n］中可局部糾正d-1個刪除錯誤當(dāng)且僅當(dāng)碼CR：＝｛cR：c∈C｝的最小距離至少是d-1.

2 最優(yōu)局部修復(fù)碼

局部修復(fù)碼是近幾年來一個非常熱門的研究方向，主要研究在分布式數(shù)據(jù)存儲系統(tǒng)中通過局部修復(fù)提高存儲節(jié)點修復(fù)效率的編碼理論和方法.本節(jié)將介紹最優(yōu)局部修復(fù)碼的相關(guān)進(jìn)展.

2.1 局部修復(fù)碼及其Singleton-like界

定義2.1設(shè)C為碼長是n的q元碼，若對任意的i∈［n］，存在元素個數(shù)為r的子集Ri?［n］＼｛i｝使得對于任意的c＝（c1，…，cn）∈C，ci可被｛cj｝j∈R i恢復(fù)，則稱C為具有局部修復(fù)性r的局部修復(fù)碼，集合Ri稱為i的恢復(fù)集.

注具有局部修復(fù)性r的局部修復(fù)碼也可有如下的等價刻畫：對于任意的i∈［n］，存在元素個數(shù)為r的子集Ri?［n］＼｛i｝使得對于任意的u，v∈C，有

當(dāng)且僅當(dāng)uR i＝vR i.也就是說局部修復(fù)碼中可以通過下載局部r個位置的信息來修復(fù)單個刪除錯誤.

下面的引理給出如何從對偶碼的角度刻畫線性碼的恢復(fù)集.

引理2.1［6］設(shè)C是碼長為n的q元線性碼.集合R?［n］＼｛i｝是i的恢復(fù)集當(dāng)且僅當(dāng)存在c∈C⊥使得i∈supp（c）?R∪｛i｝.

類似于經(jīng)典碼，局部修復(fù)碼的參數(shù)之間也彼此制約，文獻(xiàn)［7］中首次給出了局部修復(fù)碼的Singleton-like界.

引理2.2（Singleton-like界） 若q元［n，k，d］線性碼C具有局部修復(fù)性r，則有

當(dāng)r＝k時，上面的Singleton-like界即為經(jīng)典的Singleton界.若具有局部修復(fù)性r的q元［n，k，d］線性碼的參數(shù)達(dá)到Singleton-like界，即

則稱C為最優(yōu)局部修復(fù)碼.特別地，當(dāng)（r+1）｜n時，可以給出Singleton-like界的另一種形式，這種形式便于后面通過校驗陣刻畫最優(yōu)局部修復(fù)碼.

引理2.3［6］設(shè)整數(shù)n、k、d、r滿足（r+1）｜n且則

更進(jìn)一步，還可以得到最優(yōu)局部修復(fù)碼的恢復(fù)集剛好是［n］的一個劃分.

引理2.4［6］設(shè)C是參數(shù)為［n，k，d］q具有局部修復(fù)性r的最優(yōu)局部修復(fù)碼.若（r+1）｜n且滿足

2.2 最優(yōu)局部修復(fù)碼碼長的兩個上界經(jīng)典的MDS猜想告訴我們，不存在碼長超過q+1的非平凡（最小距離d＞2）的q元MDS碼，其中當(dāng)q為偶數(shù)且k＝3時，不存在碼長超過q+2的q元MDS碼.MDS猜想目前只有q為素數(shù)的情況被Ball［8］證明.由最優(yōu)局部修復(fù)碼和MDS碼之間的類比，一個很自然的問題就是當(dāng)固定字母集大小q后，q元最優(yōu)局部修復(fù)碼的最大碼長n能否超過q+1.令人驚訝的是，當(dāng)d＝3，4時，文獻(xiàn)［9］中利用循環(huán)碼構(gòu)作的最優(yōu)局部修復(fù)碼，其碼長可以任意大.當(dāng)d≥5時，最優(yōu)局部修復(fù)碼的最大碼長和MDS碼一樣是被q的函數(shù)限制的，但可以超過q+1.下面介紹文獻(xiàn)［6］中給出的最優(yōu)局部修復(fù)碼的兩個上界.

定理2.1［6］設(shè)C是參數(shù)為［n，k，d］q具有局部修復(fù)性r的最優(yōu)局部修復(fù)碼，設(shè)（r+1）｜n且參數(shù)滿足（7）式，若d≥5且d≡a（mod 4），1≤a≤4，則有

特別地，有n＝O（dq3+4／（d-4））.更進(jìn)一步，當(dāng)n＝5，6，分別有n＝O（q2），O（q3）.

對于最小距離d和碼長n成比例的情形，利用如下引理同樣可以得到碼長的一個上界.

引理2.5［10］設(shè)C是參數(shù)為［n，k，d］q具有局部修復(fù)性r的最優(yōu)局部修復(fù)碼，則有

其中kq（m，d）＝max｛k：存在［m，k，d］q線性碼｝.

利用上述引理，文獻(xiàn)［6］證明了如下結(jié)論.

引理2.6［6］設(shè)C是q元具有局部修復(fù)性r的最優(yōu)局部修復(fù)碼，則C的最小距離滿足

由上述引理直接可以得到當(dāng)d和n成比例時，最優(yōu)局部修復(fù)碼碼長的上界.

定理2.2［6］若d＝O（n），且r是常數(shù)，則q元具有局部恢復(fù)性r的最優(yōu)局部修復(fù)碼的碼長n滿足n＝O（q）.

2.3 利用多項式構(gòu)造最優(yōu)局部修復(fù)碼局部修復(fù)碼研究中的一個熱點問題是如何具體構(gòu)造出達(dá)到Singleton-like界的最優(yōu)局部恢復(fù)碼.一個突破性工作是2014年Tamo等［11］利用特殊多項式插值，構(gòu)造了碼長n≤q的q元最優(yōu)局部修復(fù)碼.下面介紹一下文獻(xiàn)［11］的工作.他們首先刻畫了一類在陪集上取值固定的“好的”多項式.

引理2.7［11］記為有限域Fq中非零元構(gòu)成的集合，則有

1）若H是的乘法子群，則對于任意的β∈多項式在陪集βH上是常值函數(shù)，即對于任意的β1，β2∈βH，g（β1）＝g（β2）.

2）若W是Fq的加法子群，則對于任意的β∈Fq，多項式

在陪集β+W上是常值函數(shù)，即對于任意的β1，β2∈β+W，g（β1）＝g（β2）.

3）設(shè)Fl是Fq的子域，W是Fq的Fl-子空間，H是的乘法子群.則對于任意的β∈Fq，多項式

本文僅針對第一種情形介紹文獻(xiàn)［11］的構(gòu)造.設(shè)H是的乘法子群，且｜H｜＝r+1.令

并定義多項式集合

顯然，V是Fq-空間且

易知C是［m（r+1），（t+1）r，d］q線性碼，其中

即C的參數(shù)達(dá)到（5）式.因此要證明C是具有局部修復(fù)性r的最優(yōu)局部修復(fù)碼只需證明C具有局部修復(fù)性r.

設(shè)碼字（f（β1α1），…，f（β1αr+1），…，f（βmα1），…，f（βmαr+1））∈C，其中f（x）∈V.不失一般性，只需證明f（β1αr+1）能被（f（β1α1），…，f（β1αr））恢復(fù).不妨設(shè)

令

則有deg（h（x））≤r-1，且對于1≤m≤r+1，有

由deg（h（x））≤r-1知，h（x）可完全由h（α1），…，h（αr）決定.因此h（αr+1）可由h（α1），…，h（αr）決定，即f（β1αr+1）能被（f（β1α1），…，f（β1αr））恢復(fù).即表明C具有局部修復(fù)性r.利用同樣的方法，文獻(xiàn)［11］得到了具有如下參數(shù)的最優(yōu)局部修復(fù)碼.

定理2.3［11］若滿足以下條件之一，則存在參數(shù)為［n，k，d］q，具有局部修復(fù)性r的最優(yōu)局部修復(fù)碼.

1）n｜（q-1），（r+1）｜n，存在整數(shù)t≥0使得k＝（t+1）r且n＞t（r+1）+r-1.

2）n｜q，（r+1）｜n，存在整數(shù)t≥0使得k＝（t+1）r且n＞t（r+1）+r-1.

3）設(shè)l是素數(shù)冪，存在整數(shù)s≥1，使得q＝ls，r+1＝luh，（r+1）｜n，n≤q，其中h｜（l-1），整數(shù)u滿足1≤u≤d.

類似文獻(xiàn)［11］的構(gòu)造，利用有理函數(shù)域的自同構(gòu)群的結(jié)構(gòu)，文獻(xiàn)［12］給出了n≤q+1的最優(yōu)局部修復(fù)碼的構(gòu)造.

定理2.4［12］設(shè)（r+1）｜n，若n｜（q-1）或n｜（q+1），則存在碼長為n的具有局部修復(fù)性r的q元最優(yōu)局部修復(fù)碼.

類似文獻(xiàn)［11］的構(gòu)造，利用橢圓函數(shù)域的自同構(gòu)群的結(jié)構(gòu)，文獻(xiàn)［13］給出了的最優(yōu)局部修復(fù)碼的構(gòu)造.

定理2.5［13］設(shè)當(dāng)r＝2，3，5，7，11和23時，存在碼長為n的具有局部修復(fù)性r的q元最優(yōu)局部修復(fù)碼.

2.4 通過校驗陣刻畫最優(yōu)局部修復(fù)碼由引理2.1、2.3和2.4可知，若（r+1）｜n，則參數(shù)為［n，k，d］q具有局部修復(fù)性r的最優(yōu)局部修復(fù)碼的校驗矩陣H有如下形式：且滿足H的任意d-1列線性無關(guān)，其中1（0）是長為r+1的全1（0）向量，ai是長為n的向量（1≤i≤h），這里本小節(jié)將回顧利用校驗陣刻畫最優(yōu)局部修復(fù)碼的部分工作.文獻(xiàn)［6］利用校驗陣給出了當(dāng)最小距離d＝2，3，4時，任意碼長的最優(yōu)局部修復(fù)碼的構(gòu)造.在此之前，文獻(xiàn)［9］利用循環(huán)碼得到了類似的結(jié)論.

定理2.6［6］設(shè)d-2≤r，（r+1）｜n.若q≥r+1時，則當(dāng)最小距離d＝2，3，4時，存在任意碼長的最優(yōu)局部修復(fù)碼.

證明這里僅證明d＝4的情形.對任意n滿足（r+1）｜n，令取

定理2.1證明了當(dāng)最小距離d≥5時，q元最優(yōu)局部修復(fù)碼碼長的上界為O（dq3）.文獻(xiàn)［6］利用校驗陣給出了最優(yōu)局部修復(fù)碼的最大碼長的一個下界.

定理2.7［6］設(shè)d≤r+2，（r+1）｜n，則存在碼長為的最優(yōu)局部修復(fù)碼.特別地，若r＞3和（r+1）｜n，則存在碼長為n＝Ω（q2），最小距離為5的最優(yōu)局部修復(fù)碼.

這個證明是非構(gòu)造性的.特別地，當(dāng)最小距離d＝5時，由定理2.7知最優(yōu)局部修復(fù)碼的最大碼長的下界是Ω（q2），而由定理2.1可知此時最大碼長的上界同樣是O（q2）.也就是說當(dāng)最小距離d＝5時，最優(yōu)局部修復(fù)碼的最大碼長的量級為Θ（q2），文獻(xiàn)［14］利用常重碼的相關(guān)結(jié)論，通過檢驗陣刻畫給出了一類碼長為Θ（q2）的最小距離為5的最優(yōu)局部修復(fù)碼的精確刻畫.同時文獻(xiàn)［14］利用常重碼和Moore矩陣還給出了一類偶特征上最小距離為6的最優(yōu)局部修復(fù)碼的構(gòu)造.

定理2.8［14］設(shè)r、t為兩個正整數(shù)，則有

1）若r+1≥5為一個素數(shù)冪，則可具體構(gòu)造出一簇q元具有局部修復(fù)性r參數(shù)為［n，k，5］的最優(yōu)局部修復(fù)碼，其中

2）設(shè)r+1≥8為2的冪次，則可具體構(gòu)造出一簇q元具有局部修復(fù)性r參數(shù)為［n，k，6］的最優(yōu)局部修復(fù)碼，其中

從定理2.7中可以看出，當(dāng)d＞6時，存在碼長是q1+?量級的最優(yōu)局部修復(fù)碼，其中0＜?＜1.很自然的一個問題就是如何精確構(gòu)造出這樣的局部修復(fù)碼.文獻(xiàn)［15］利用校驗矩陣構(gòu)造了q元域上具有局部化參數(shù)r＝d-1的參數(shù)為［r+1r（q-1），q-r，d］最優(yōu)局部修復(fù)碼.

定理2.9［15］設(shè)r｜（q-1）且d＝r+1，則存在局部度為r的參數(shù)為最優(yōu)局部修復(fù)碼.

最后給出兩個最優(yōu)局部修復(fù)碼中尚未解決的問題：

1）當(dāng)d≥6時，給出碼長為n＝Ω（q1+ε）的最優(yōu)局部修復(fù)碼的構(gòu)造，其中ε＞0為常數(shù).

2）當(dāng)d＝Ω（n）時，給出碼長為n＝Ω（（1+ε）n）的最優(yōu)局部修復(fù)碼的構(gòu)造，或證明其存在性，其中ε＞0為常數(shù).

3 達(dá)到cut-set界的再生碼

在分布式存儲系統(tǒng)中，當(dāng)某個存儲節(jié)點失效后，局部修復(fù)碼采用的方式是通過訪問少數(shù)可用節(jié)點來恢復(fù)失效節(jié)點.近年來出現(xiàn)的再生碼則關(guān)注于帶寬的消耗.再生碼引入網(wǎng)絡(luò)編碼的思想，在修復(fù)失效節(jié)點時，參與修復(fù)過程的節(jié)點可進(jìn)行計算，目的是將最終修復(fù)帶寬消耗降低.本節(jié)將介紹達(dá)到cut-set界的再生碼的相關(guān)研究進(jìn)展.

3.1 再生碼的定義及cut-set界再生碼的定義最早由Dimakis等［16］提出.

定義3.1設(shè)n、k、d、r、B為正數(shù)，若C?Fnq滿足C＝qk且有：

1）任選碼字c＝（c1，…，cn）∈C，對任意的i∈［n］和任意I?［n］＼｛i｝滿足｜I｜＝r，有ci可被cI恢復(fù)；

2）任選碼字c＝（c1，…，cn）∈C，對任意的i∈［n］和任意I?［n］＼｛i｝滿足｜I｜＝d，從｛cj｝j∈I中最多下載B比特可將ci恢復(fù).

則稱C是局部度為r，帶寬為B的q元（n，k，d）-再生碼.

注由定義可以看出局部度為r，帶寬為B的q元（n，k，d）-再生碼是具有局部性r的q元（n，qk）-局部修復(fù)碼.不同于局部修復(fù)碼不需要在每個節(jié)點計算，再生碼允許在每個節(jié)點處計算.

從再生碼的思想可以看出，希望使每個結(jié)點存儲的數(shù)據(jù)logq和下載帶寬B盡可能地小.而每個結(jié)點存儲的數(shù)據(jù)量有如下的下界.

引理3.1設(shè)C是局部度為r，帶寬為B的q元（n，k，d）-再生碼.則

證明因為碼字c的每個分量都可被其前r個分量恢復(fù)，所以碼字c完全被其前r個分量決定，它表明｜C｜≤qr，因此

定義3.2若局部度為r，帶寬為B的q元（n，k，d）-再生碼C滿足即r＝k，則稱C為最小存儲再生碼（簡稱為MSR碼）.

下面的引理說明了MSR和MDS碼的等價性.

引理3.2局部度為r，帶寬為B的q元（n，k，d）-再生碼C是MSR碼當(dāng)且僅當(dāng)C是MDS碼.

證明一方面，設(shè)C是局部度為r＝k，帶寬為B的q元（n，k，d）-再生碼，則每個碼字都可被任意k個分量恢復(fù)，這表明任意元素個數(shù)為k的集合I?［n］都是一個信息集，由引理1.3可知C是MDS碼.另一方面，設(shè)C是MDS碼.由引理1.3可知任意元素個數(shù)為k的集合I?［n］都是一個信息集，因此碼字的每個分量都可被其它任意的k個分量恢復(fù)，即局部度為r＝k.因此C是MSR碼.

由于局部度為r，帶寬為B的q元（n，k，d）-MSR碼滿足r＝k，因此接下來就直接說帶寬為B的q元（n，k，d）-MSR碼.針對MSR碼，希望帶寬B盡可能地小.文獻(xiàn)［16］給出了帶寬B的cut-set下界.

引理3.3［16］（cut-set界） 設(shè)C是帶寬為B的q元（n，k，d）-MSR碼，則

當(dāng)logq相對于n-k充分大時，（8）式的等號可以達(dá)到.而當(dāng)logq相對于n-k比較小時，（8）式的等式無法達(dá)到.常用更平凡的界替代它：

特別當(dāng)d＝n-1時，（8）式化為

引理3.4［16］設(shè)C是q元（n，qk）MDS碼，對于每個碼字c＝（c1，…，cn）∈C，對任意i∈［n］，從任意di個位置中下載Bi比特可將ci恢復(fù)，則有

研究達(dá)到cut-set界的MSR碼是再生碼研究中所關(guān)心的問題.如文獻(xiàn)［17］研究了碼率≤1／2的情形，文獻(xiàn)［18-20］研究了碼率＞1／2的情形.

3.2 Reed-Solomon碼可達(dá)到cut-set界Reed-Solomon碼在編碼學(xué)中有著非常廣泛的應(yīng)用.再生碼概念提出后的一段時間里，人們普遍認(rèn)為Reed-Solomon碼可能不是很好的再生碼.而Guruswami等［21］給出了Reed-Solomon碼的一個線性的修復(fù)算法，證明了在某些參數(shù)的情況下Reed-Solomon碼可達(dá)到cut-set界.在文獻(xiàn)［21］工作的基礎(chǔ)上，Tamo等［22］利用Reed-Solomon碼具體構(gòu)造出達(dá)到cutset界的再生碼.本小節(jié)介紹他們的工作.

3.2.1Reed-Solomon碼的修復(fù)算法 首先介紹Guruswami等［21］的工作.設(shè)q＝pt，ζ1，…，ζt是Fq的一組Fp-基，θ1，…，θt為其對偶基.設(shè)GRSk（a，1）為定義1.3中給出的q元Reed-Solomon碼.

定理3.1［21］設(shè)正整數(shù)k、l、d滿足k+l≤d，給定i∈［n］，若對于每個u∈［t］，總存在次數(shù)不超過l的多項式hu（x）使得hu（αi）＝ζu，則對任意i∈［n］，GRSk（a，1）中第i個分量可通過下載

比特來修復(fù)，其中

bj＝dimF pSpanF p｛hu（αj）：u＝1，2，…，t｝.（10）

證明為了文章的可讀性，這里簡單介紹下文獻(xiàn)［21］的證明.設(shè)GRSn-k（a，w）是GRSk（a，1）的對偶碼，其中

設(shè)（f（α1），f（α2），…，f（αn））∈GRSk（a，1），其中degf（x）≤k-1.假設(shè)要恢復(fù)f（αi）.設(shè)S?［n］＼｛i｝且｜S｜＝d.令

則有degg（x）＝n-d-1≤n-（l+k）-1，g（αi）≠0且g（αm）＝0，m∈［n］＼（S∪｛i｝）.對于j∈S，考慮空間

Hj＝SpanF p｛hu（αj）：u＝1，2，…，t｝.

設(shè)Jj?［t］且｜Jj｜＝bj使得｛hs（αj）：s∈Jj｝是Hj的一組Fp-基.從存儲f（αj）的節(jié)點下載

由Hj的定義可知，對于任意的u滿足1≤u≤t，存在Fp中一組數(shù)｛λs｝s∈J j使得

從而有

上式表明，從已下載的數(shù)據(jù)可以計算出

其中1≤u≤t，j∈S.

由對偶基的定義可知

由

和

可得

即

因此

結(jié)論得證.

3.2.2達(dá)到cut-set界的Reed-Solomon碼的構(gòu)造 現(xiàn)在介紹Tamo等［22］構(gòu)造的達(dá)到cut-set界的再生碼.首先介紹部分節(jié)點達(dá)到cut-set界的結(jié)論.

設(shè)正整數(shù)n、k滿足n＞k，取m＝π（n-k），其中π（n-k）表示小于或等于n-k的素數(shù)的個數(shù).設(shè)素數(shù)冪p滿足p≥n-m，l1，…，lm是不超過n-k的素數(shù)全體.選取m個不同的元素α1，…，αm∈ˉFp使得

令

則有

從Fp中選擇n-m個不同的元素αm+1，…，αn.令

可得q元Reed-solomon碼GRSk（a，1）.

定理3.2［22］Reed-Solomon碼GRSk（a，1）的前m個節(jié)點達(dá)到（9）式的cut-set界.

證明簡略敘述下證明過程.只需證明，對于1≤i≤m，從任意的di＝li+k-1個點下載比特即可修復(fù)第i個分量.

考慮域擴張Fq／Fi，可知是Fq的一組Fi-基.令，則有由定理3.1可知，只需下載

比特即可恢復(fù)第i個分量，其中

故結(jié)論得證.

利用類似的方法，Tamo等［22］構(gòu)造了全部節(jié)點都達(dá)到cut-set界的再生碼.設(shè)正整數(shù)n、d、k滿足n＞d＞k，設(shè)p是一個素數(shù)，取s＝d-k+1.由Dirichlet定理可知，存在無窮多個素數(shù)l滿足l≡1（mods）.選取n個不同素數(shù)l1，l2，…，ln，使得li≡1（mods）.選取αi∈ˉFp使得［Fp（αi）：Fp］＝li.定義

設(shè)Fq是F的s次擴域，則有

并且有

令a＝（α1，…，αn），考慮q元Reed-Solomon碼GRSk（a，1）.

定理3.3［22］上述GRSk（a，1）是帶寬為B的q元（n，k，d）-MSR碼，其中從而達(dá)到cut-set界.

需要注意的是，文獻(xiàn)［22］構(gòu)造的再生碼所在的有限域的元素個數(shù)是

這個域太大了！最后提出再生碼方向兩個尚未解決的問題：

1）如何構(gòu)造“小”域上達(dá)到cut-set界的MSR碼；

2）研究MSR碼的帶寬B和域的元素個數(shù)q之間的關(guān)系.

4 最優(yōu)極大局部修復(fù)碼

近年來，在線存儲的數(shù)據(jù)量激增，這導(dǎo)致局部修復(fù)碼已成為大型分布式存儲系統(tǒng)的首選方案.現(xiàn)在考慮一個新的模型，除了考慮單個或少數(shù)節(jié)點發(fā)生故障情況下的局部修復(fù)問題，同時還考慮了對最壞情況下更多刪除的容錯能力［23］.最優(yōu)極大局部修復(fù)碼提供了這種局部和整體容錯的最佳組合.本節(jié)介紹最優(yōu)極大局部修復(fù)碼的代數(shù)刻畫和構(gòu)造的相關(guān)工作.

4.1 最優(yōu)極大局部修復(fù)碼的生成陣和校驗陣考慮一個分布式存儲系統(tǒng)，若該系統(tǒng)由m個不同的元素個數(shù)均為r的組所構(gòu)成，每組內(nèi)可局部地糾正任意a個刪除錯誤，除此之外整個系統(tǒng)還可額外糾正任意h個刪除錯誤.可以糾正這種分布式存儲系統(tǒng)的錯誤的最優(yōu)碼稱為最優(yōu)極大局部修復(fù)碼，下面給出最優(yōu)極大局部修復(fù)碼的生成陣和校驗陣的刻畫.

定義4.1設(shè)l是素數(shù)冪，正整數(shù)a、m、r、h滿足ma+h＜mr.令n＝mr和k＝n-ma-h.若矩陣

滿足如下條件：

2）對于1≤i≤m，Bi可生成［r，r-a，a+1］lMDS碼.

3）從每個Bi中刪掉a列后，G余下的矩陣生成［n-ma，k，h+1］lMDS碼.

則稱以G為生成矩陣的l元［n，k］線性碼為最優(yōu)極大（n，r，h，a）l局部修復(fù)碼（簡稱為MR（n，r，h，a）l-LRC碼）.

根據(jù)定義，可直接得到下面的結(jié)論.

引理4.1［24］矩陣G＝（B1｜B2｜…｜Bm）∈是MR（n，r，h，a）l-LRC碼的生成矩陣當(dāng)且僅當(dāng)G的任意一個含有Bi（1≤i≤m）中最多r-a列的k×k子矩陣S是可逆的.

類似地，也可利用校驗矩陣給出MR（n，r，h，a）l-LRC碼的等價定義.

定義4.2設(shè)l是素數(shù)冪，正整數(shù)a、m、r、h滿足ma+h＜mr.令n＝mr和k＝n-ma-h.若矩陣

滿足以下條件：

2）對于1≤i≤m，Ai可生成［r，a，r-a+1］lMDS碼.

3）從每組中任意選擇a列后，再任意選擇h列，這am+h列Fl-線性無關(guān).

則稱以H為校驗矩陣的l元［n，k］線性碼為MR（n，r，h，a）l-LRC碼.

事實上，校驗矩陣中的子矩陣Ai是生成矩陣G中子矩陣Bi生成的線性碼的校驗矩陣.從定義可以看出，最優(yōu)極大局部修復(fù)碼的每個部分都是MDS碼.類似MDS猜想關(guān)于MDS碼碼長和有限域元素個數(shù)之間的關(guān)系，很自然地一個問題是：存在l元MR（n，r，h，a）-LRC碼的有限域的元素個數(shù)l最小是多少？文獻(xiàn)［25］討論了隨機碼的情形.

引理4.2［25］設(shè)l是素數(shù)冪，正整數(shù)a、m、r、h滿足

令n＝mr和k＝n-ma-h.若Fl上的隨機矩陣G∈以很高概率生成一個MR（n，r，h，a）l-LRC碼，則有

文獻(xiàn)［26］等給出了一個下界.

引理4.3［26］設(shè)h、a是常數(shù).若2≤h≤n／r，則MR（n，r，h，a）l-LRC碼必定滿足

4.2 構(gòu)造最優(yōu)極大局部修復(fù)碼很多文獻(xiàn)給出了最優(yōu)極大局部修復(fù)碼的具體構(gòu)造.當(dāng)h≤1時，文獻(xiàn)

［27］構(gòu)造的最優(yōu)極大局部修復(fù)碼的有限域元素個數(shù)為O（r）.當(dāng)h＝2，3時，文獻(xiàn)［26］構(gòu)造的最優(yōu)極大局部修復(fù)碼的有限域元素個數(shù)分別為O（n）、O（n3）.文獻(xiàn)［28］利用最大秩距離碼的判別準(zhǔn)則，從生成陣的角度構(gòu)造了一類最優(yōu)極大局部修復(fù)碼，其有限域元素個數(shù)為等［24］從校驗矩陣的角度構(gòu)造了一類最優(yōu)極大局部修復(fù)碼，其有限域元素個數(shù)為介紹一下文獻(xiàn)［28］和［24］的結(jié)果.

定理4.1［28］設(shè)是MRD碼C的生成陣，令對角塊矩陣

其中Mi是q元［r，r-a］-MDS碼的生成矩陣，1≤i≤m，則G＝?GM是MR（n，r，h，a）l-LRC碼的生成矩陣，其中n＝mr，h＝n-ma-k和l＝qN.

接下來介紹文獻(xiàn)［24］中從校驗矩陣角度構(gòu)造最優(yōu)極大局部修復(fù)碼的結(jié)果.

定義4.3設(shè)l是q的冪次，α1，…，αh∈Fl，h階Moore矩陣M定義為

Moore矩陣M的行列式det（M）滿足

其中（c1，…，ch）跑遍中全部h-1維線性射影空間中點.

由定義可知，det（M）≠0當(dāng)且僅當(dāng)α1，…，αh是Fq-線性無關(guān)的.接下來利用Moore矩陣來構(gòu)造最優(yōu)極大局部修復(fù)碼的校驗矩陣.設(shè)s、m是正整數(shù)，記

設(shè)α11，…，α1s，…，αm1，…，αms是Fl的一組Fq-基.若存在q元［r，r-s，h+a+1］線性碼，則對于每個1≤i≤m，存在集合使得βi1，…，βir中任意h+a個元素是Fq-線性無關(guān)的.定義Fl上矩陣

利用最優(yōu)極大局部修復(fù)碼的校驗矩陣的定義和Moore矩陣的性質(zhì)，可以得到如下結(jié)論.

定理4.2［24］設(shè)是q元［r，a］MDS碼的生成矩陣（1≤i≤m），Di是（14）式定義的矩陣.則以（13）式中的H為校驗矩陣的線性碼C是MR（n，r，h，a）l-LRC碼，且有限域的元素個數(shù)是

證明因為Ai是［r，a］l-MDS碼的生成矩陣（1≤i≤m），所以只需證明定義4.2中的條件3）成立即可.

對于i＝1，2，…，m，設(shè)Ti是｛（i，1），（i，2），…，（i，r）｝的子集且｜Ti｜＝a，令Si是｛（i，1），（i，2），…，（i，r）｝＼Ti的子集且

令A(yù)i＝（ai1，…，air），hij是H的第i塊的第j列，則

為了證明定義4.2中的條件3）成立，只需證明：對于所有可能的Ti和Si，

即可.

因此det（（hij）1≤i≤n，j∈T i∪S i）≠0當(dāng)且僅當(dāng)矩陣

可逆.注意到（15）式給出的矩陣是Moore矩陣，且第一行是

其中μlj∈Fq.設(shè)λij∈Fq使得

即

因此對于所有滿足1≤i≤m的i都有

因為｛βij｝j∈T i∪S i是Fq-線性無關(guān)的，所以λij＝0，j∈Si.因此（16）式中的h個元素Fq-線性無關(guān).故（15）式給出的Moore矩陣可逆，結(jié)論得證.

設(shè)r，h≥2，整數(shù)a滿足a≤r.因為Ai是q元［r，a］-MDS碼的生成矩陣，所以必有r≤q+1.設(shè)q＝2「log2r?，則存在q元［r，a］-MDS碼和q元［r，r-s，h+a+1］-MDS碼，其中s＝h+a.由定理4.2即可得到如下結(jié)論.

定理4.3［24］若r≥h+a+1，則存在MR（n，r，h，a）l-LRC碼，且域的元素個數(shù)是