邢朝平

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

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

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

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

1 基本概念

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

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

為C的對(duì)偶碼.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

所以

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

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

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

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

1）C是MDS碼；

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

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

4）C⊥是MDS碼；

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

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

回顧一類最常見(jiàn)的MDS碼——廣義Reed-Solomon碼.設(shè)α1，α2，…，αn是有限域Fq中n個(gè)不同的元素（從而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）的對(duì)偶碼也是廣義Reed-Solomon碼，并且有

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

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

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

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

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

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

下面介紹有限域上的對(duì)偶基.

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

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

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

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

因此α可表示為

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

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

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

證明（n，M）q碼C可糾正d-1個(gè)刪除錯(cuò)誤等價(jià)于：對(duì)于任意的元素個(gè)數(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.若對(duì)于任意的元素個(gè)數(shù)為d-1的集合I?［n］以及任意的u，v∈C有uˉI＝vˉI，則有d（u，v）≤｜I｜＝d-1，這表明u＝v.

另一方面，設(shè)對(duì)于任意的元素個(gè)數(shù)為d-1的集合I?［n］以及任意的u，v∈C，u＝v當(dāng)且僅當(dāng)uˉI＝vˉI.假設(shè)d（C）＜d，則存在兩個(gè)碼字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個(gè)刪除錯(cuò)誤當(dāng)且僅當(dāng)碼CR：＝｛cR：c∈C｝的最小距離至少是d-1.

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

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

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

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

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

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

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

引理2.1［6］設(shè)C是碼長(zhǎng)為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時(shí)，上面的Singleton-like界即為經(jīng)典的Singleton界.若具有局部修復(fù)性r的q元［n，k，d］線性碼的參數(shù)達(dá)到Singleton-like界，即

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

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

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

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

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

定理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）.

對(duì)于最小距離d和碼長(zhǎng)n成比例的情形，利用如下引理同樣可以得到碼長(zhǎng)的一個(gè)上界.

引理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成比例時(shí)，最優(yōu)局部修復(fù)碼碼長(zhǎng)的上界.

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

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

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

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

2）若W是Fq的加法子群，則對(duì)于任意的β∈Fq，多項(xiàng)式

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

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

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

并定義多項(xiàng)式集合

顯然，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，且對(duì)于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是素?cái)?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），則存在碼長(zhǎng)為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時(shí)，存在碼長(zhǎng)為n的具有局部修復(fù)性r的q元最優(yōu)局部修復(fù)碼.

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

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

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

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

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

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

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

1）若r+1≥5為一個(gè)素?cái)?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時(shí)，存在碼長(zhǎng)是q1+?量級(jí)的最優(yōu)局部修復(fù)碼，其中0＜?＜1.很自然的一個(gè)問(wèn)題就是如何精確構(gòu)造出這樣的局部修復(fù)碼.文獻(xiàn)［15］利用校驗(yàn)矩陣構(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ù)碼.

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

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

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

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

在分布式存儲(chǔ)系統(tǒng)中，當(dāng)某個(gè)存儲(chǔ)節(jié)點(diǎn)失效后，局部修復(fù)碼采用的方式是通過(guò)訪問(wèn)少數(shù)可用節(jié)點(diǎn)來(lái)恢復(fù)失效節(jié)點(diǎn).近年來(lái)出現(xiàn)的再生碼則關(guān)注于帶寬的消耗.再生碼引入網(wǎng)絡(luò)編碼的思想，在修復(fù)失效節(jié)點(diǎn)時(shí)，參與修復(fù)過(guò)程的節(jié)點(diǎn)可進(jìn)行計(jì)算，目的是將最終修復(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，對(duì)任意的i∈［n］和任意I?［n］＼｛i｝滿足｜I｜＝r，有ci可被cI恢復(fù)；

2）任選碼字c＝（c1，…，cn）∈C，對(duì)任意的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ù)碼不需要在每個(gè)節(jié)點(diǎn)計(jì)算，再生碼允許在每個(gè)節(jié)點(diǎn)處計(jì)算.

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

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

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

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

下面的引理說(shuō)明了MSR和MDS碼的等價(jià)性.

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

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

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

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

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

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

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

3.2 Reed-Solomon碼可達(dá)到cut-set界Reed-Solomon碼在編碼學(xué)中有著非常廣泛的應(yīng)用.再生碼概念提出后的一段時(shí)間里，人們普遍認(rèn)為Reed-Solomon碼可能不是很好的再生碼.而Guruswami等［21］給出了Reed-Solomon碼的一個(gè)線性的修復(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為其對(duì)偶基.設(shè)GRSk（a，1）為定義1.3中給出的q元Reed-Solomon碼.

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

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

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

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

設(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｝）.對(duì)于j∈S，考慮空間

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

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

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

從而有

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

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

由對(duì)偶基的定義可知

由

和

可得

即

因此

結(jié)論得證.

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

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

令

則有

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

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

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

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

考慮域擴(kuò)張F(tuán)q／Fi，可知是Fq的一組Fi-基.令，則有由定理3.1可知，只需下載

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

故結(jié)論得證.

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

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

并且有

令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)造的再生碼所在的有限域的元素個(gè)數(shù)是

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

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

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

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

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

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

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

滿足如下條件：

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

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

則稱以G為生成矩陣的l元［n，k］線性碼為最優(yōu)極大（n，r，h，a）l局部修復(fù)碼（簡(jiǎn)稱為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的任意一個(gè)含有Bi（1≤i≤m）中最多r-a列的k×k子矩陣S是可逆的.

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

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

滿足以下條件：

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

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

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

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

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

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

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

引理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時(shí)，文獻(xiàn)

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

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

其中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.

接下來(lái)介紹文獻(xiàn)［24］中從校驗(yàn)矩陣角度構(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維線性射影空間中點(diǎn).

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

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

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

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

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

對(duì)于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）成立，只需證明：對(duì)于所有可能的Ti和Si，

即可.

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

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

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

即

因此對(duì)于所有滿足1≤i≤m的i都有

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

設(shè)r，h≥2，整數(shù)a滿足a≤r.因?yàn)锳i是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碼，且域的元素個(gè)數(shù)是