鄭尤良, 李瑞虎, 呂京杰, 張 茂

(空軍工程大學(xué)基礎(chǔ)部，西安，710051)

隨著大數(shù)據(jù)時代的到來，世界上的數(shù)據(jù)量急劇增長，對存儲系統(tǒng)的要求也逐步提高。分布式存儲系統(tǒng)由于采用了可擴(kuò)展結(jié)構(gòu)，提高了系統(tǒng)的可用性和存儲效率，因此得到了廣泛應(yīng)用。為了提高分布式存儲系統(tǒng)的容錯能力，2012年Gopalan提出了局部修復(fù)碼的概念[1]。局部修復(fù)碼是一類特殊的糾刪碼，其碼字的任一信息位發(fā)生錯誤時都可通過訪問其它不超過r個信息位進(jìn)行恢復(fù)，r被稱為碼的局部修復(fù)度(Locality)[2]。此后，Cadambe和Mazumdar提出了一個考慮域q大小的局部修復(fù)碼的參數(shù)上界，即C-M界[3]。設(shè)C=[n,k,d]q, 若其局部修復(fù)度為r, 則:

(1)

定義1[4]碼長為n的q元線性碼C叫作循環(huán)碼，是指若c=(c0,c1,…,cn-1)∈C，則c的循環(huán)移位(cn-1,c0,c1,…,cn-2)∈C。

引理1[5]令循環(huán)碼C=[n，k，d]，D為C的對偶碼。若D的最小距離為d⊥，則C的局部修復(fù)度r=d⊥-1。

循環(huán)碼由于其所具有的特殊結(jié)構(gòu)，能夠更好地設(shè)計(jì)和分析碼的局部度，因此近年來關(guān)于循環(huán)碼的局部度問題研究日益增多。Zeh等人在2015年利用循環(huán)碼生成了部分局部度r=2的碼[6]。Kim等人通過分析二、三元域上的循環(huán)碼，得到了一些距離大于4的局部修復(fù)碼[7]。文獻(xiàn)[8～9]中考慮通過常循環(huán)碼來構(gòu)造局部修復(fù)碼。饒?bào)A等給出了二元域上循環(huán)碼構(gòu)造具有2、3局部度的碼的構(gòu)造方法[10]。夏易沖與陳斌討論了局部度為1、k-1時碼的特征[11]。楊瑞磻分析了一些有關(guān)三元本原長度碼長的循環(huán)碼的局部度[12]。本文主要利用循環(huán)碼構(gòu)造了碼長8≤n≤50范圍內(nèi)達(dá)到C-M界的三元局部修復(fù)碼，并著重討論其中具有小局部度的碼。這些碼的研究對局部修復(fù)碼在分布式存儲系統(tǒng)上的應(yīng)用具有重要的促進(jìn)意義。

1 預(yù)備知識

令F3={0,1,2}，F(xiàn)3上的碼長為n, 維數(shù)為k,最小距離為d的線性碼C記作[n,k,d]，若碼的局部度為r，則記為[n,k,d;r]。

設(shè)Zn表示模n整數(shù)環(huán)，本文研究的循環(huán)碼的碼長滿足gcd(n，3)=1。令循環(huán)碼C=[n，k，d]，當(dāng)碼字寫成多項(xiàng)式形式時，取g(x)為xn-1在Fq[x]中的首一因式，則C為環(huán)Rn=Fq[x]/(xn-1)中由g(x)生成的理想，并稱g(x)為C的生成多項(xiàng)式，xn-1/g(x)為C的校驗(yàn)多項(xiàng)式[4]。

定義2[4]若x為整數(shù)且滿足0≤x≤n，x模n的3-分圓陪集Cx定義為:

Cx={x,3x,32x,…,3l-1x}(modn)

(2)

式中：l是滿足xql≡x(modn)的最小正整數(shù),集合Cx中的最小元素稱為代表元。

引理2[13](BCH界)令循環(huán)碼C=[n，k，d]，若C的定義集T中存在δ長度的連續(xù)元素，則碼的距離d≥δ+1。

2 三元循環(huán)最優(yōu)局部修復(fù)碼的構(gòu)造

為構(gòu)造達(dá)到界的最優(yōu)局部修復(fù)碼，首先需計(jì)算出相應(yīng)碼長的3-分圓陪集，通過分圓陪集的組合可以確定碼的定義集從而確定循環(huán)碼，最后通過分析該碼及其對偶碼，即可得到參數(shù)為[n,k,d;d⊥-1]以及[n,n-k,d⊥;d-1]的局部修復(fù)碼。

相對而言，局部度越小，碼的修復(fù)效率越高[15]，因此構(gòu)造小局部度的碼更有實(shí)用價(jià)值。根據(jù)引理1，為構(gòu)造局部度為r的碼，對偶距離d⊥=r+1，再參考BCH界，確定對偶碼的定義集TD中連續(xù)整數(shù)的個數(shù)范圍，即可有針對性地構(gòu)造局部修復(fù)碼。本文重點(diǎn)構(gòu)造了局部度為1、2、3的3類小局部度的碼，各對偶碼定義集中的連續(xù)整數(shù)個數(shù)應(yīng)不大于局部度r。

定理1對于三元循環(huán)碼C=[n，k，d]，若碼長n為偶數(shù)且滿足gcd(n，3)=1，則當(dāng)n≥8時存在以下2種局部度r=1的最優(yōu)局部修復(fù)碼:

3 三元循環(huán)最優(yōu)局部修復(fù)碼

本節(jié)主要構(gòu)造了碼長8≤n≤50范圍內(nèi)局部度r≤3的最優(yōu)局部修復(fù)碼，并通過對偶碼定義集給出了具體的構(gòu)造方法，同時也給出了其余達(dá)到C-M界的局部修復(fù)碼。以下各表中帶*號的碼為前人用其他方法構(gòu)造的局部修復(fù)碼，由于循環(huán)碼相較一般碼在應(yīng)用中更具優(yōu)勢，所以仍在此給出。參數(shù)為[16,3,10;1]、[8,3,5;2]、[13,4,7;2]、[26,4,17;2]、[13,6,6;3]、[40,6,24;3]的碼已于文獻(xiàn)[12]中得到。

3.1 r=1的最優(yōu)局部修復(fù)碼

當(dāng)對偶碼定義集中無連續(xù)整數(shù)時，可以構(gòu)造對偶距離d⊥=2的碼，在碼長8≤n≤50范圍內(nèi)共得到39個最優(yōu)局部修復(fù)碼，其中滿足定理1的碼長有15種，見表1。

表1 r=1的最優(yōu)局部修復(fù)碼

3.2 r=2的最優(yōu)局部修復(fù)碼

當(dāng)對偶碼定義集中的連續(xù)整數(shù)個數(shù)不大于2時，可以構(gòu)造對偶距離d⊥=3的碼，進(jìn)而構(gòu)造了5個r=2的最優(yōu)局部修復(fù)碼，見表2。

表2 r=2的最優(yōu)局部修復(fù)碼

3.3 r=3的最優(yōu)局部修復(fù)碼

當(dāng)對偶碼定義集中的連續(xù)整數(shù)個數(shù)不大于3時，可以構(gòu)造對偶距離d⊥=4的碼，進(jìn)而構(gòu)造了15個r=3的最優(yōu)局部修復(fù)碼，見表3。

表3 r=3的最優(yōu)局部修復(fù)碼

3.4 r≥4的最優(yōu)局部修復(fù)碼

除了r≤3的碼以外，還得到了以下30個最優(yōu)局部修復(fù)碼，見表4。

表4 r=4的最優(yōu)局部修復(fù)碼

本節(jié)所構(gòu)造的幾類碼均達(dá)到了目前最為關(guān)注的C-M界，其中局部度r≤3的碼具有較高的修復(fù)效率，可進(jìn)一步考慮其實(shí)用價(jià)值，局部度r≥4的碼則主要是對結(jié)果的完善。

4 結(jié)語

本文利用定義集合設(shè)計(jì)三元循環(huán)碼的對偶距離，構(gòu)造了碼長在8≤n≤50范圍內(nèi)達(dá)到C-M界的最優(yōu)局部修復(fù)碼，尤其是構(gòu)造了一批具有較大實(shí)用價(jià)值的小局部度的碼。本文的方法與結(jié)論為深入研究三元局部修復(fù)碼提供了依據(jù)，今后會進(jìn)一步研究如何基于擬循環(huán)碼來構(gòu)造局部修復(fù)碼。