基于循環(huán)碼的三元局部修復(fù)碼構(gòu)造

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

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

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

(1)

定義1[4]碼長(zhǎng)為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的對(duì)偶碼。若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時(shí)碼的特征[11]。楊瑞磻分析了一些有關(guān)三元本原長(zhǎng)度碼長(zhǎng)的循環(huán)碼的局部度[12]。本文主要利用循環(huán)碼構(gòu)造了碼長(zhǎng)8≤n≤50范圍內(nèi)達(dá)到C-M界的三元局部修復(fù)碼，并著重討論其中具有小局部度的碼。這些碼的研究對(duì)局部修復(fù)碼在分布式存儲(chǔ)系統(tǒng)上的應(yīng)用具有重要的促進(jìn)意義。

1 預(yù)備知識(shí)

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

設(shè)Zn表示模n整數(shù)環(huán)，本文研究的循環(huán)碼的碼長(zhǎng)滿足gcd(n，3)=1。令循環(huán)碼C=[n，k，d]，當(dāng)碼字寫成多項(xiàng)式形式時(shí)，取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中存在δ長(zhǎng)度的連續(xù)元素，則碼的距離d≥δ+1。

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

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

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

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

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

本節(jié)主要構(gòu)造了碼長(zhǎng)8≤n≤50范圍內(nèi)局部度r≤3的最優(yōu)局部修復(fù)碼，并通過對(duì)偶碼定義集給出了具體的構(gòu)造方法，同時(shí)也給出了其余達(dá)到C-M界的局部修復(fù)碼。以下各表中帶*號(hào)的碼為前人用其他方法構(gòu)造的局部修復(fù)碼，由于循環(huán)碼相較一般碼在應(yīng)用中更具優(yōu)勢(shì)，所以仍在此給出。參數(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)對(duì)偶碼定義集中無(wú)連續(xù)整數(shù)時(shí)，可以構(gòu)造對(duì)偶距離d⊥=2的碼，在碼長(zhǎng)8≤n≤50范圍內(nèi)共得到39個(gè)最優(yōu)局部修復(fù)碼，其中滿足定理1的碼長(zhǎng)有15種，見表1。

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

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

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

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

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

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

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

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

除了r≤3的碼以外，還得到了以下30個(gè)最優(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的碼則主要是對(duì)結(jié)果的完善。

4 結(jié)語(yǔ)

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