局部修復碼綜述

邢朝平

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

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

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

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

1 基本概念

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

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

為C的對偶碼.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

所以

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

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

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

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

1）C是MDS碼；

2）H的任意n-k列線性無關；

3）G的任意k列線性無關；

4）C⊥是MDS碼；

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

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

回顧一類最常見的MDS碼——廣義Reed-Solomon碼.設α1，α2，…，αn是有限域Fq中n個不同的元素（從而n≤q），v1，v2，…，vn均為Fq中的非零元素，整數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-同構，可以把Fq N中的元素看做是中的列向量.因此，向量對應一個Fq上的N×n矩陣U（不妨設n≤N）.

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

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

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

達到Singleton界的秩度量碼被稱為最大秩距離碼（簡稱為MRD碼）.文獻［4］給出了MRD碼的判別準則.

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

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

定義1.5設Fq／Fp是有限域擴張，且

設｛ζ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，不妨設其中ai∈Fp，則對于任意的j∈［n］，由對偶基定義可知

因此α可表示為

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

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

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

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

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

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

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

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

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

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

2.1 局部修復碼及其Singleton-like界

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

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

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

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

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

類似于經典碼，局部修復碼的參數之間也彼此制約，文獻［7］中首次給出了局部修復碼的Singleton-like界.

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

當r＝k時，上面的Singleton-like界即為經典的Singleton界.若具有局部修復性r的q元［n，k，d］線性碼的參數達到Singleton-like界，即

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

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

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

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

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

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

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

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

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

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

利用上述引理，文獻［6］證明了如下結論.

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

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

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

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

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

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

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

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

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

本文僅針對第一種情形介紹文獻［11］的構造.設H是的乘法子群，且｜H｜＝r+1.令

并定義多項式集合

顯然，V是Fq-空間且

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

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

設碼字（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））恢復.不妨設

令

則有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））恢復.即表明C具有局部修復性r.利用同樣的方法，文獻［11］得到了具有如下參數的最優(yōu)局部修復碼.

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

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

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

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

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

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

類似文獻［11］的構造，利用橢圓函數域的自同構群的結構，文獻［13］給出了的最優(yōu)局部修復碼的構造.

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

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

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

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

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

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

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

定理2.8［14］設r、t為兩個正整數，則有

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

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

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

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

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

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

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

3 達到cut-set界的再生碼

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

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

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

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

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

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

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

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

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

證明因為碼字c的每個分量都可被其前r個分量恢復，所以碼字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碼當且僅當C是MDS碼.

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

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

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

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

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

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

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

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

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

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

比特來修復，其中

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

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

設（f（α1），f（α2），…，f（αn））∈GRSk（a，1），其中degf（x）≤k-1.假設要恢復f（αi）.設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｝.

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

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

從而有

上式表明，從已下載的數據可以計算出

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

由對偶基的定義可知

由

和

可得

即

因此

結論得證.

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

設正整數n、k滿足n＞k，取m＝π（n-k），其中π（n-k）表示小于或等于n-k的素數的個數.設素數冪p滿足p≥n-m，l1，…，lm是不超過n-k的素數全體.選取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é)點達到（9）式的cut-set界.

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

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

比特即可恢復第i個分量，其中

故結論得證.

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

設Fq是F的s次擴域，則有

并且有

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

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

需要注意的是，文獻［22］構造的再生碼所在的有限域的元素個數是

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

1）如何構造“小”域上達到cut-set界的MSR碼；

2）研究MSR碼的帶寬B和域的元素個數q之間的關系.

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

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

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

定義4.1設l是素數冪，正整數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局部修復碼（簡稱為MR（n，r，h，a）l-LRC碼）.

根據定義，可直接得到下面的結論.

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

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

定義4.2設l是素數冪，正整數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-線性無關.

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

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

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

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

文獻［26］等給出了一個下界.

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

4.2 構造最優(yōu)極大局部修復碼很多文獻給出了最優(yōu)極大局部修復碼的具體構造.當h≤1時，文獻

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

定理4.1［28］設是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.

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

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

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

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

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

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

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

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

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

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

令Ai＝（ai1，…，air），hij是H的第i塊的第j列，則

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

即可.

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

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

其中μlj∈Fq.設λij∈Fq使得

即

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

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

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

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