一類新的（k＋2，k）Hadamard MSR碼

張司娜， 唐小虎， 李 杰

（西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，四川成都610031）

一類新的（k＋2，k）Hadamard MSR碼

張司娜， 唐小虎， 李 杰

（西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，四川成都610031）

為降低分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)的存儲(chǔ)量，構(gòu)造了一類新（k＋2，k）Hadamard MSR碼．該碼的每個(gè)編碼矩陣皆對(duì)應(yīng)于2個(gè)值，供其對(duì)角元素選?。诰幋a矩陣中，這2個(gè)值循環(huán)出現(xiàn)，且不同的矩陣，循環(huán)出現(xiàn)的周期不同．基于這一特性構(gòu)造了節(jié)點(diǎn)的修復(fù)方案，將失效節(jié)點(diǎn)中的α個(gè)數(shù)據(jù)分成α／2組，每一組重建2個(gè)數(shù)據(jù)，其他k＋1個(gè)節(jié)點(diǎn)為每一組各提供1個(gè)數(shù)據(jù)．證明了若新碼編碼矩陣的對(duì)角元素可取的2個(gè)值不相等，則可最優(yōu)修復(fù)系統(tǒng)節(jié)點(diǎn)；若所有編碼矩陣對(duì)角元素可取的2個(gè)值的和為同一不為0的值，則可最優(yōu)修復(fù)第1個(gè)校驗(yàn)節(jié)點(diǎn)；若所有編碼矩陣對(duì)角元素可取的2個(gè)值的逆的和為1，則可最優(yōu)修復(fù)第2個(gè)校驗(yàn)節(jié)點(diǎn)．新碼的節(jié)點(diǎn)存儲(chǔ)量降低到了Hadamard MSR碼的理論界，可最優(yōu)修復(fù)任意系統(tǒng)節(jié)點(diǎn)和1個(gè)校驗(yàn)節(jié)點(diǎn)．

分布式；存儲(chǔ)；再生碼；MSR碼；高碼率；最優(yōu)；修復(fù)

分布式存儲(chǔ)系統(tǒng)利用大量節(jié)點(diǎn)提供海量數(shù)據(jù)的存儲(chǔ)服務(wù)，具有成本低、易擴(kuò)展等優(yōu)點(diǎn)，在云計(jì)算、云存儲(chǔ)等有著廣泛的應(yīng)用，如OceanStore［1］、Total Recall［2］、DHash＋＋［3］．

為了保證數(shù)據(jù)的可靠性和可用性，分布式存儲(chǔ)系統(tǒng)必須保持一定的數(shù)據(jù)冗余．糾刪碼就是一種重要的冗余存儲(chǔ)機(jī)制，其磁盤利用率高．現(xiàn)有采用糾刪碼方案的分布式存儲(chǔ)系統(tǒng)有Facebook的Hadoop、Google Colossus與Microsoft Azure［4］．

基于糾刪碼，將一個(gè)大小為M＝kα的文件編碼成同樣大小的n份（大小為α），任意k份都可恢復(fù)出原文件，即具有MDS（maximum distance separable）性質(zhì)．在糾刪碼中，節(jié)點(diǎn)中的數(shù)據(jù)被視為標(biāo)量，所以，當(dāng)一個(gè)節(jié)點(diǎn)失效，為修復(fù)其數(shù)據(jù)（大小為α），需要從其他k個(gè)節(jié)點(diǎn)下載其全部數(shù)據(jù)，換言之，為修復(fù)M／k個(gè)數(shù)據(jù)，糾刪碼需要下載M個(gè)數(shù)據(jù)．

近年來(lái)，文獻(xiàn)［5］提出了最小存儲(chǔ)再生（minimum storage regenerating，MSR）碼，該碼具有MDS性質(zhì)，磁盤利用率與糾刪碼相同．該碼將節(jié)點(diǎn)中的數(shù)據(jù)視為矢量，在修復(fù)失效節(jié)點(diǎn)的M／k個(gè)數(shù)據(jù)時(shí)，從其他d個(gè)（d≥k）可用節(jié)點(diǎn)下載其部分?jǐn)?shù)據(jù)［6］，下載的數(shù)據(jù)總量（稱為修復(fù)帶寬）為dM／k（d－k＋1）＜M．

（n＝k＋2，k）系統(tǒng)MSR碼具有以下優(yōu)勢(shì)：

（1）重建原文件時(shí)，若選取系統(tǒng)節(jié)點(diǎn)，無(wú)需計(jì)算；

（2）與其他MSR碼相比，存儲(chǔ)開銷最?。?-8］．

現(xiàn)有的（n＝k＋2，k）系統(tǒng)MSR碼見(jiàn)文獻(xiàn)［9-15］．其中，文獻(xiàn)［9］提出的Hadamard MSR碼的系統(tǒng)節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)中的同一層數(shù)據(jù)恰好組成一個(gè)標(biāo)量MDS碼．這一特性不僅使得Hadamard MSR碼可直接用于基于糾刪碼的分布式存儲(chǔ)系統(tǒng)，而且當(dāng)某一系統(tǒng)節(jié)點(diǎn)中的數(shù)據(jù)變更時(shí)，所有校驗(yàn)節(jié)點(diǎn)只需變更同層的數(shù)據(jù)，即具有最優(yōu)更新性質(zhì)．

文獻(xiàn)［16］證明了（k＋2，k）Hadamard MSR碼的節(jié)點(diǎn)存儲(chǔ)量α的下界為2k，然而，文獻(xiàn)［9］提出的Hadamard MSR碼的節(jié)點(diǎn)存儲(chǔ)量α＝2k＋1，是下界的2倍．

本文構(gòu)造了一個(gè)新的（k＋2，k）Hadamard MSR碼．新碼的節(jié)點(diǎn)存儲(chǔ)量α達(dá)到了理論界2k，具有最優(yōu)更新性質(zhì)，可最優(yōu)修復(fù)所有系統(tǒng)節(jié)點(diǎn)，雖然只能最優(yōu)修復(fù)一個(gè)校驗(yàn)節(jié)點(diǎn)，但對(duì)整個(gè)系統(tǒng)性能的影響較小，系統(tǒng)節(jié)點(diǎn)數(shù)遠(yuǎn)大于2，其失效概率遠(yuǎn)大于校驗(yàn)節(jié)點(diǎn)，而且與校驗(yàn)節(jié)點(diǎn)相比，系統(tǒng)節(jié)點(diǎn)的失效更嚴(yán)重，因?yàn)楹笳邔?dǎo)致原始數(shù)據(jù)的丟失，增大用戶訪問(wèn)信息的時(shí)恒．

1 （k＋2，k）Hadamard MSR碼的結(jié)構(gòu)與修復(fù)特性

在域Fq上，用（k＋2，k）系統(tǒng)MSR碼對(duì)一個(gè)大小為M＝kα的文件進(jìn)行編碼，生成k＋2份大小均為α的數(shù)據(jù)．其中，k份包含的是原始數(shù)據(jù)，另2份是原始數(shù)據(jù)的線性表達(dá)．這k＋2份數(shù)據(jù)分別存儲(chǔ)于k＋2個(gè)存儲(chǔ)節(jié)點(diǎn)．存儲(chǔ)原始數(shù)據(jù)的節(jié)點(diǎn)稱為系統(tǒng)節(jié)點(diǎn)，其他存儲(chǔ)節(jié)點(diǎn)稱為校驗(yàn)節(jié)點(diǎn)．若將節(jié)點(diǎn)i（1≤i≤k＋2）中的數(shù)據(jù)用一個(gè)α維列向量ci表示，

不失一般性，校驗(yàn)節(jié)點(diǎn)k＋1中的數(shù)據(jù)可表示為所有系統(tǒng)節(jié)點(diǎn)中的數(shù)據(jù)之和，即

校驗(yàn)節(jié)點(diǎn)k＋2中的數(shù)據(jù)可表示為所有系統(tǒng)節(jié)點(diǎn)中數(shù)據(jù)的線性組合，即

其中，Ai（1≤i≤k）是α×α的矩陣，稱為系統(tǒng)節(jié)點(diǎn)i的編碼矩陣．若該系統(tǒng)MSR碼選用（k＋2，k）Hadamard MSR碼，編碼矩陣A1，A2，…，Ak均為對(duì)角矩陣，其編碼矩陣Ai（1≤i≤k）可表示為

其中，ai，l∈Fq，1≤l≤α．（k＋2，k）Hadamard MSR碼的結(jié)構(gòu)如表1所示．

由表1可以看出，在（k＋2，k）Hadamard MSR碼中，校驗(yàn)節(jié)點(diǎn)中的數(shù)據(jù)僅與系統(tǒng)節(jié)點(diǎn)中同層的數(shù)據(jù)相關(guān)，而與其他層的數(shù)據(jù)無(wú)關(guān)．因而，在某一系統(tǒng)節(jié)點(diǎn)中的數(shù)據(jù)變更時(shí)，所有校驗(yàn)節(jié)點(diǎn)只需變更同層的數(shù)據(jù)，換言之，（k＋2，k）Hadamard MSR碼具有最優(yōu)更新性質(zhì)．由表1還可以看出，在每一層，（c1，l，…，ck，l，ck＋1，l，ck＋2，l）均是一個(gè)（k＋2，k）標(biāo)量MDS碼，1≤l≤α，所以，（k＋2，k）Hadamard MSR碼可看作α層標(biāo)量MDS碼的組合．顯然，若（k＋2，k）Hadamard MSR碼具有MDS性質(zhì)，需要編碼矩陣的對(duì)角元素滿足ai，l≠0與ai，l－aj，l≠0，其中，1≤i≠j≤k，1≤l≤α．

表1 （k＋2，k）Hadamard MSR碼的結(jié)構(gòu)Tab．1 Structure of（k＋2，k）Hadamard MSR code

在（k＋2，k）Hadamard MSR碼中，失效節(jié)點(diǎn)的最優(yōu)修復(fù)是分組進(jìn)行、同層相助的［17］．在另外k＋1個(gè)節(jié)點(diǎn)的幫助下，失效節(jié)點(diǎn)中數(shù)據(jù)（大小為α）的修復(fù)是分成α／2組并行進(jìn)行的，每一組負(fù)責(zé)重建2個(gè)數(shù)據(jù)，若失效節(jié)點(diǎn)的第l層與第s層（l≠s）的數(shù)據(jù)分為一組進(jìn)行修復(fù)，為重建這2個(gè)數(shù)據(jù)，每一個(gè)幫助節(jié)點(diǎn)提供的數(shù)據(jù)（大小為1）也是由各自的第l層與第s層數(shù)據(jù)生成的．

2 一類新的（k＋2，k）Hadamard MSR碼

文獻(xiàn)［9］提出的（k＋2，k）Hadamard MSR碼的節(jié)點(diǎn)存儲(chǔ)量α為2k＋1，是文獻(xiàn)［16］給出的理論界的2倍．為降低節(jié)點(diǎn)存儲(chǔ)量，本文對(duì)其進(jìn)行了改進(jìn)，構(gòu)造了一類新的（k＋2，k）Hadamard MSR碼．新碼的節(jié)點(diǎn)存儲(chǔ)量α為2k，降低到了理論界．

（k＋2，k）MSR碼由編碼矩陣A1，A2，…，Ak組成，而（k＋2，k）Hadamard MSR碼的編碼矩陣均為對(duì)角陣．

在新（k＋2，k）Hadamard MSR碼中，編碼矩陣Ai（1≤i≤k）主對(duì)角線上的元素ai，l（1≤l≤α＝2k＋1）取值為

即，編碼矩陣

為方便后續(xù)定理的證明，將新碼編碼矩陣對(duì)角元素的取值規(guī)律以引理的形式表示．

引理1 ai，l＝ai，l＋2i－1，aj，l與aj，l＋2i－1一個(gè)取μi，另一個(gè)取νi，其中，1≤i≠j≤k，l∈［2is＋1，2is＋2i－1］，0≤s≤2k－i－1．

證明 根據(jù)式（1），引理1等價(jià)于

當(dāng)i＜j時(shí)，不失一般性，令

則有

而

則有

引理2 ai，l與ai，2k－l＋1一個(gè)取μi，另一個(gè)取νi，其中，1≤i≤k，l∈［1，2k－1］．證明 不失一般性，令

則

根據(jù)式（1），ai，l與ai，2k－l＋1一個(gè)取μi，另一個(gè)取νi．

2．1 系統(tǒng)節(jié)點(diǎn)的最優(yōu)修復(fù)方案

在新（k＋2，k）Hadamard MSR碼中，系統(tǒng)節(jié)點(diǎn)i（1≤i≤k）的修復(fù)是將第l層（l∈［2is＋1，2is＋2i－1］，0≤s≤2k－i－1）與第l＋2i－1層分為一組，為修復(fù)該組數(shù)據(jù)，其他系統(tǒng)節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)提供的數(shù)據(jù)均是這2層的數(shù)據(jù)之和．

下面證明編碼矩陣的對(duì)角元素的取值μi與νi（1≤i≤k）滿足何種條件時(shí)，新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)系統(tǒng)節(jié)點(diǎn)．

定理1 若μi≠νi（1≤i≤k），新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)所有系統(tǒng)節(jié)點(diǎn)．

證明 系統(tǒng)節(jié)點(diǎn)i（1≤i≤k）中的數(shù)據(jù)為ci，1，ci，21，…，ci，2k，為重建ci，l與ci，l＋2i－1（l∈［2is＋1，2is＋2i－1］，0≤s≤2k－i－1），從其他系統(tǒng)節(jié)點(diǎn)下載

從校驗(yàn)節(jié)點(diǎn)k＋1下載ck＋1，l＋ck＋1，l＋2i－1，即為

從校驗(yàn)節(jié)點(diǎn)k＋2下載ck＋2，l＋ck＋2，l＋2i－1，即為

由引理1可知，aj，l＝aj，l＋2i－1，因而，式（3）與式（4）的最后一項(xiàng)都可由式（2）消去，而式（3）的第1項(xiàng)與式（4）的第1項(xiàng)組成關(guān)于ci，l與ci，l＋2i－1的方程組，只要ai，l≠aj，l＋2i－1，該方程組可解．

由引理1知，ai，l與aj，l＋2i－1一個(gè)取μi，另一個(gè)取νi，所以，只要μi≠νi，則可解出ci，l與ci，l＋2i－1．

因此，若μi≠νi（1≤i≤k），新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)所有系統(tǒng)節(jié)點(diǎn)．

2．2 校驗(yàn)節(jié)點(diǎn)的最優(yōu)修復(fù)

新（k＋2，k）Hadamard MSR碼無(wú)法保證2個(gè)校驗(yàn)節(jié)點(diǎn)均可最優(yōu)修復(fù)，只能選取一個(gè)進(jìn)行最優(yōu)修復(fù)．

若可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋1，其修復(fù)是將第l層（l∈［1，2k－1］）與第2k－l＋1層分為一組．為修復(fù)該組數(shù)據(jù)，系統(tǒng)節(jié)點(diǎn)提供的數(shù)據(jù)是這2層數(shù)據(jù)之和，而校驗(yàn)節(jié)點(diǎn)k＋2提供的則是這2層數(shù)據(jù)之差．

下面證明編碼矩陣對(duì)角元素的取值μi與νi（1≤i≤k）滿足何種條件時(shí)，新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋1．

定理2 若μ1＋ν1＝μ2＋ν2＝…＝μk＋νk≠0，新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋1．

證明 校驗(yàn)節(jié)點(diǎn)k＋1中的數(shù)據(jù)為ck＋1，1，ck＋1，21，…，ck＋1，2k，為重建ck＋1，l與ck＋1，2k－l＋1（l∈［1， 2k－1］），從k個(gè)系統(tǒng)節(jié)點(diǎn)下載

將式（5）的所有項(xiàng)相加，得

從校驗(yàn)節(jié)點(diǎn)k＋2下載ck＋2，l－ck＋2，2k－l＋1，即為

式（6）與式（7）組成關(guān)于ck＋1，l與ck＋1，2l－l＋1的方程組，若要方程組可解，需要a1，l＋a1，2k－l＋1≠0并且式（7）的最后一項(xiàng)可消去，即

由引理2可知，ai，l與ai，2k－l＋1一個(gè)取μi，另一個(gè)取νi，即

那么，只要

則可解出ck＋1，l與ck＋1，2l－l＋1．

因此，若

新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋1．

若新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋2，其分組與修復(fù)校驗(yàn)節(jié)點(diǎn)k＋1時(shí)相同，即第l層（l∈［1，2k－1］）與第2k－l＋1層分為一組．為修復(fù)該組數(shù)據(jù)，系統(tǒng)節(jié)點(diǎn)提供的數(shù)據(jù)是這2層的數(shù)據(jù)之和，而校驗(yàn)節(jié)點(diǎn)k＋1提供的則是這2層的數(shù)據(jù)之差．

下面證明編碼矩陣的對(duì)角元素的取值μi與νi（1≤i≤k）滿足何種條件時(shí)，新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋2．

定理3 若μ－1i＋ν－1i＝1（1≤i≤k），新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋2．

證明 校驗(yàn)節(jié)點(diǎn)k＋2中的數(shù)據(jù)為ck＋2，1，ck＋2，21，…，ck＋2，2k，為重建ck＋2，l與ck＋2，2k－l＋1（l∈［1，2k－1］），從k個(gè)系統(tǒng)節(jié)點(diǎn)下載

將式（8）的所有項(xiàng)相加，得

從校驗(yàn)節(jié)點(diǎn)k＋1下載ck＋1，l－ck＋1，2k－l＋1，即為

式（9）與式（10）組成關(guān)于ck＋2，l與ck＋2，2k－l＋1的方程組，若要方程組可解，式（10）的最后一項(xiàng)需消去，即需

由引理2可知，ai，l與ai，2k－l＋1一個(gè)取μi，另一個(gè)取νi，即

那么，只要

則可解出ck＋2，l與ck＋2，2k－l＋1．

因此，若

新（k＋2，k）Hadamard MSR碼可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋2．

2．3 新碼的M DS性質(zhì)

下面證明編碼矩陣的對(duì)角元素的取值μi與νi（1≤i≤k）滿足何種條件時(shí)，新（k＋2，k）Hadamard MSR碼滿足MDS性質(zhì)．

定理4 若μi≠0，νi≠0，μi≠νi，μi≠μj，νi≠νj（1≤i≠j≤k），新（k＋2，k）Hadamard MSR碼具有MDS性質(zhì)．

證明 若（k＋2，k）Hadamard MSR碼具有MDS性質(zhì)，需要編碼矩陣的對(duì)角元素滿足ai，l≠0與ai，l－aj，l≠0（1≤i≠j≤k，1≤l≤α）．由式（1）知，新碼的ai，l取值μi或νi，則ai，l－aj，l的取值有4種，分別為μi－μj，νi－νj，μi－μj，νi－νj那么，若要ai，l≠0與ai，l－aj，l≠0同時(shí)成立，則需μi≠0，νi≠0，μi≠νj，μi≠μj，νi≠νj．

因此，若μi≠0，νi≠0，μi≠νj，μi≠μj，νi≠νj（1≤i≠j≤k），新（k＋2，k）Hadamard MSR碼具有MDS性質(zhì)．

下面確定新（k＋2，k）Hadamard MSR碼需要多大的域．綜上所述，新碼若可最優(yōu)修復(fù)所有系統(tǒng)節(jié)點(diǎn)且具有MDS性質(zhì)，需要

即要求μi，νi（1≤i≤k）為2k個(gè)不相同的非零數(shù)．而

（可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋1的充分條件）與

（可最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋2的充分條件）均要求μi與νi（1≤i≤k）是k對(duì)和相同且和不為0的數(shù)．因此，新（k＋2，k）Hadamard MSR碼需要有限域Fq具有奇特征且q≥2k＋3．

在域Fq（q≥2k＋3）上，若新碼選擇最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋1，μi與νi（1≤i≤k）可取

若選擇最優(yōu)修復(fù)校驗(yàn)節(jié)點(diǎn)k＋2，μi與νi（1≤i≤k）可取

其中，1≤t≤q－2．

3 結(jié) 論

本文給出了一類新的（k＋2，k）Hadamard MSR碼，其節(jié)點(diǎn)存儲(chǔ)量達(dá)到了Hadamard MSR碼的理論界．給出了節(jié)點(diǎn)的分組修復(fù)方案，基于該修復(fù)方案，證明了新碼可最優(yōu)修復(fù)系統(tǒng)節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)的充分條件．

［1］ RHEA S，WELLS C，EATON P，et al．Maintenancefree global data storage［J］．IEEE Internet Computing，2001，5（5）：40-49．

［2］ BHAGWAN R，TATI K，CHENG Y C，et al．Total recall：System support for automated availability management［C］∥Symposium Networked Systems Design and Imp lementation．San Francisco：ACM，2004：25-25．

［3］ DABEK F，LIJinyang，SIT E，etal．Designing a DHT for low latency and high throughput［C］∥Symposium Networked Systems Design and Implementation（NSDI）．San Francisco：ACM，2004：85-98

［4］ HUANG Cheng，SIMITCI H，XU Yi，et al．Erasure coding in windows azure storage［C］∥Usenix annual Technical Conference．Boston：ACM，2012：15-26．

［5］ DIMAKISA G，GODFREY P B，WU Yunnan，et al．Network coding for distributed storage systems［J］．IEEE Transactions on Information Theory，2010，56（9）：4539-4551．

［6］ 范文禮，劉志剛．基于傳輸效率矩陣的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度排序方法［J］．西南交通大學(xué)學(xué)報(bào)，2014，49（2）：337-342．FAN Wenli，LIU Zhigang．Ranking method for node importance based on efficiency matrix［J］．Journal of Southwest Jiaotong University，2014，49（2）：337-342．

［7］ DIMAKISA G，RAMCHANDRAN K，WU Yunnan，et al．A survey on network codes for distributed storage［J］．Proceedings of the IEEE，2011，99（3）：476-489．［8］ 郝杰，逯彥博，劉鑫吉，等．分布式存儲(chǔ)中的再生碼綜述［J］．重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，25（1）：30-38．HAO Jie，LU Yanbo，LIU Xinji，et al．Survey for regenerating codes for distributed storage［J］．Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition，2013，25（1）：30-38．

［9］ PAPAILIOPOULOS D S，DIMAKIS A G，CADAMBE V R．Repair optimal erasure codes through hadamard designs［J］．IEEE Transactions on Information Theory，2013，59（5）：3021-3037．

［10］ TAMO I，WANG Zhiying，BRUCK J．Zigzag codes：MDS array codes with optimal rebuilding［J］．IEEE Transactions on Information Theory，2013，59（3）：1597-1616．

［11］ WANG Zhiying，TAMO I，BRUCK J．Long MDS codes for optimal repair bandwidth［C］∥Proceedings of IEEE International Symposium on Information Theory．Cambridge：IEEE，2012：1182-1186．

［12］ TAMO I，WANG Zhiying，BRUCK J．MDS array codes with optimal rebuilding［C］∥Proceedings of IEEE International Symposium on Information Theory．St．Petersburg：IEEE，2011：1240-1244．

［13］ CADAMBE V R，JAFAR S A，MALEKI H，et al．Asymptotic interference alignment for optimal repair of MDS codes in distributed storage［J］．IEEE Transactions on Information Theory，2013，59（5）：2974-2987．

［14］ CADAMBE V R，HUANG Cheng，LI Jin，et al．Polynomial length MDS codes with optimal repair in distributed storage［C］∥The 45th Asilomar Conference on Signals，Systems and Computers（ASILOMAR）．Pacific Grove：IEEE，2011：1850-1854．

［15］ CADAMBE V R，HUANG Cheng，LI Jin．Permutation code：Optimal exact-repair of a single failed node in MDS code based distributed storage systems［C］∥Proceedings of IEEE International Symposium on Information Theory Proceedings（ISIT）．St．Petersburg：IEEE，2011：1225-1229．

［16］ TAMO I，WANG Zhiying，BRUCK J．Access versus bandwidth in codes for storage［J］．IEEE Transactions on Information Theory，2014，60（4）：2028-2037．

［17］ TANG Xiaohu，YANG Bin，LI Jie．New repair strategy of hadamard minimum storage regenerating code for distributed storage system［J／OL］．（2013-12-18）［2014-12-10］．http：／／arxiv．org／pdf／1312．5173v1．pdf．

（中文編輯：唐 晴 英文編輯：周 堯）

A New（k＋2，k）Hadamard Minimum Storage Regenerating Code

ZHANG Sina， TANG Xiaohu， LI Jie
（School of Information Science and Technology，Southwest Jiaotong University，Chengdu 610031，China）

To reduce the storage capacity of nodes in distributed storage systems，a new（k＋2，k）Hadamard Minimum Storage Regenerating（MSR）code was constructed．Each coding matrix is related to two values，from which the diagonal elements of this coding matrix are selected．These two values appear in the coding matrix in a repeating pattern，but with different repeating cycles for different matrices．Based on the structure of the coding matrix，a repair strategy was constructed．The repair strategy divides symbols in the failed node intoα／2 groups with two symbols in each group，then the two symbols are recovered by downloading one symbol from each of the other k＋1 nodes．If the two values related to each coding matrix are unequal，the new Hadamard MSR code can optimally repair systematic nodes．If the sum of two values related to each coding matrix is nonzero and the k values are the same，the new Hadamard MSR code can optimally repair the first parity node．If the sum of the inverse of two values related to each coding matrix is one，the new Hadamard MSR code can optimally repair the second parity node．The new code reduces the storage capacity to the bond for Hadamard MSR code．Further，it can optimally repair all systematic nodes and one parity node．

distributed；storage；regenerating code；MSR code；high code-rate；optimal；repair

TN911．22

A

0258-2724（2016）01-0188-06 DO I：10．3969／j．issn．0258-2724．2016．01．026

2015-02-01

張司娜（1985—），女，博士研究生，研究方向?yàn)榉植际酱鎯?chǔ)編碼，E-mail：nsz1221＠163．com

唐小虎（1971—），男，教授，博士生導(dǎo)師，研究方向?yàn)樾畔踩c編碼，E-mail：xhtang_scce＠home．swjtu．edu．cn

張司娜，唐小虎，李杰．一類新的（k＋2，k）Hadamard MSR碼［J］．西南交通大學(xué)學(xué)報(bào)，2016，51（1）：188-192，200．