短碼長四元最優(yōu)局部修復(fù)碼的構(gòu)造

李瑞虎 展秀珍 付 強 張 茂 鄭尤良

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

1 引言

在分布式存儲系統(tǒng)中，三重備份能夠保證數(shù)據(jù)的可靠性，并且它是最簡單的方法[1]。然而三重備份的存儲效率低、存儲代價過大，于是人們提出了存儲負(fù)荷更低的糾刪碼方案[2,3]。傳統(tǒng)糾刪碼能滿足高效存儲的需求，但是修復(fù)效率低，因此編碼學(xué)者提出了局部修復(fù)碼[3]。2012年，Gopalan等人[4]提出LRC的概念以及Singleton-Like (S-L)界，但是SL界在小域[4,5]上是不緊的。為了更加精確地描述q元局部修復(fù)碼4個參數(shù)之間的關(guān)系，Cadambe和Mazumdar[6]提出考慮域的大小的界，即Cadambe-Mazumdar (C-M)界。

在工程應(yīng)用中，小域上LRC的編、解碼復(fù)雜度較低，更具有使用價值[7]。二元域上LRC取得一定進展，人們研究了達到S-L界[8,9]以及C-M界[10,11]的局部度最優(yōu)LRC。文獻[12,13]研究了三元距離較小或者維數(shù)較低的局部度最優(yōu)LRC。在四元域上，人們得到一些局部度最優(yōu)LRC：文獻[14]構(gòu)造了2類距離為3的四元LRC；文獻[15]構(gòu)造了距離為4的四元LRC；這3類LRC是局部度最優(yōu)和擬最優(yōu)的[14,15]。Barg等人[16]利用代數(shù)曲線和代數(shù)曲面構(gòu)造了碼長為18、維數(shù)為11、距離為3、局部度為2的四元LRC。文獻[17]通過縮短q元漢明碼與(q2+1)?cap構(gòu)造了距離為3和4的LRC，從而可得到16個距離為3和12個距離為4的局部度最優(yōu)四元LRC。Jin等人[18]利用有限域上的自同構(gòu)群構(gòu)造一般域上LRC，可得到碼長不超過5的四元LRC。由以上結(jié)果可知，當(dāng)碼長不超過20時，文獻[14,15,16]構(gòu)造了特定距離的局部度最優(yōu)或擬最優(yōu)四元LRC，但只有1個碼是距離最優(yōu)碼；文獻[17]的2個四元LRC以及文獻[18]的1個四元LRC都不是距離最優(yōu)碼。

由文獻[19]可知，當(dāng)域的大小為2的冪次時，碼的運行速度快，并且文獻[20]給出了RS碼校驗關(guān)系的等價轉(zhuǎn)換方式，避免了復(fù)雜的符號轉(zhuǎn)化。依據(jù)文獻[21-23]，碼長不超過20的距離最優(yōu)四元碼的參數(shù)完全確定。由文獻[23]可知，對于給定的碼長和維數(shù)，距離最優(yōu)四元碼往往有很多，但是它們的局部度也有差別，人們往往更關(guān)注局部度盡可能小的LRC。基于此本文研究四元LRC，由已有文獻結(jié)果可知，目前四元LRC的研究并不充分，其結(jié)果較為零散，因此本文將研究碼長不超過20的四元碼，設(shè)法構(gòu)造距離最優(yōu)且局部度盡可能小的四元LRC，并利用S-L界或C-M界判斷其局部度的最優(yōu)性。

2 預(yù)備知識

令F4={0,1,ω,ω2}為四元域， 記ω=2，ω2=3，F(xiàn)4={0,1,2,3}。F4n為F4上的n維向量空間，若一個非零向量的第1個非零分量是1，則稱此向量為首一向量。稱F4n的k維子空間C為四元線性碼[n,k]4，并記為C=[n,k]4，n稱為C的碼長，C中的向量稱為碼字。

引理1[4]設(shè)線性碼C=[n,k,d]q的生成陣為Gk,n=(g1,g2,...,gn)，gi是k維列向量，當(dāng)i ∈[n]時，若存在大小不超過r的子集Ai ?[n]{i}使得gi被至多r個gj(j ∈Ai)線性表出，則C的局部度為r。

引理2[9]H=(HlT,Hn?k?lT)T為線性碼[n,k,d]q的校驗陣，Hl中的列均為非零列向量，Hl的行稱為H的局部度行。若Hl的行向量的漢明重量不超過r+1，則C的局部度為r。

下面介紹常用的S-L界和C-M界。

引理3[4,6]若C=[n,k,d;r]q存在，式(1)和式(2)成立時，分別稱為S-L界[4]與C-M界[6]

等式成立時，稱碼達到S-L界。特別地，當(dāng)k=r時，S-L界退化為經(jīng)典的Singleton界。

若C=[n,k,d;r]q達到S-L界或C-M界，或者[n,k,d;r ?1]q的局部修復(fù)碼不存在，則稱C是局部度最優(yōu)的(r?最優(yōu)的)。

約定：[n,k,d]4簡記為[n,k,d]；[n,k,d;r]4簡記為[n,k,d;r]。in=(i,i,...,i)(i=0,1,2,3)表示長度為n且分量為i的行向量，iTn=(i,i,...,i)T為in=(i,i,...,i)的轉(zhuǎn)置。[n]={1,2,...,n}，并約定n ≤20；In為n階單位陣。記Gk,m的l個并置為Gk,lm=(Gk,m,Gk,m,...,Gk,m)=(lGk,m)。

3 F4上短碼長LRC的構(gòu)造

碼長n ≤20的距離最優(yōu)碼共2 1 0 個，其中[n,n,1]碼不具有局部修復(fù)功能，還余下190個距離最優(yōu)碼。對于n ≥2，1n生成[n,1,n;1]碼，其對偶碼為[n,n ?1,2;n ?1]，此兩碼達到S-L界。故以下僅需考慮[n,k,d]和[n,n ?k,d′](k ≥2)形式的局部修復(fù)碼構(gòu)造，分7個小節(jié)展開討論。

由文獻[22,23]，分以下3步構(gòu)造距離最優(yōu)碼的生成陣Gk,n：

步驟1 由文獻[22,23]得到距離最優(yōu)碼的生成陣，利用四元域中的乘法運算將生成陣中的列向量化為首一列向量；

步驟2 將首一列向量按照列漢明重量由小到大的順序排列；

步驟3 對排序后的生成陣做列置換，依次刪除生成陣Gk,n的最后j(1≤j

3.1 參數(shù)為[n,2,d]和([n,n?2,d′]的)LRC

以上構(gòu)造的LRC都是距離最優(yōu)碼，其中r=1的LRC的局部度已達到最??；碼長3≤n ≤10(n ?=7,9)的[n,2,d;r]碼和n ≥6的[n,n ?2,2;「(n ?2)/2■]達到S-L界；[7,2,5;2]和[9,2,7;2]達不到S-L界和C-M界，但不難驗證[7,2,5;1]和[9,2,7;1]不存在，故這兩個碼仍是r?最優(yōu)的。

3.2 參數(shù)為[n,3,d]和[n,n ?3,d′]的LRC

3.3 參數(shù)為[n,4,d]和[n,n ?4,d′]的LRC

記G4,n=(I4|B4,n?4)，構(gòu)造如式(5)的5個矩陣，G4,17由文獻[17]給出

G4,6和G4,10分別生成[6,4,2;2]和[10,4,6;3]碼。刪除G4,10的后i(1≤i ≤3)列，可得[9,4,5;3]，[8,4,4;3]和[7,4,3;3]碼。G4,23生成[23,4,16;2]碼，刪除G4,23的后i(1≤i ≤4)列可得[22,4,15;2]，[21,4,14;2]，[20,4,13;2]和[19,4,12;2]碼。G4,17添加G4,17中的1列可得[18,4,12;3]，由文獻[17]刪除校驗陣G4,17的列可得到[n,n ?4,4;rn]，9≤n=17?j ≤17，其中n=9,10,...,16,17時局部度分別為rn=4,5,6,6,7,8,9,10,11。記G4,17=(β1,β2,...,β17)，令G4,n=(β1,β2,...,βn) ，(11≤n=17?j ≤17)，G4,n生成[n,4,12?j;3]碼。以H4,21為校驗陣的碼為[21,17,3;9]。當(dāng)1≤i ≤3時，刪除H4,21的后i列得到[20,16,3;9]，[19,15,3;8]和[18,14,3;7]碼。以上構(gòu)造的LRC都是距離最優(yōu)碼，其中6≤n ≤10的[n,4,d;r]碼和9≤n ≤17的[n,n ?4,4;r]碼達到S-L界; 達到C-M界的L R C 為11≤n ≤23(n ?=19)的[n,4,d;r]以及18≤n ≤21的[n,n ?4,3;r]；而[19,4,12;2]LRC達不到S-L界和C-M界。

3.4 參數(shù)為[n,5,d]和[n,n ?5,d′]的LRC

記G5,n=(I5|B5,n?5)，構(gòu)造以下7 個矩陣，Xi=(γ1,γ2,...,γi)(4≤i ≤6)：

由G5,n分 別 可 得[7,5,2;3]，[11,5,6;4]，[14,5,8;3]，[17,5,10;3]和[24,5,16;2]碼。由G5,11的子矩陣可得[10,5,5;4]，[9,5,4;4]，[8,5,3;4]碼；由G5,14的子矩陣可得[13,5,7;3]，[12,5,6;4]碼；由G5,17的子矩陣可得[16,5,9;3]，[15,5,8;3]碼。當(dāng)1≤i ≤6時，依次刪除G5,24的后i列分別可得[23,5,15;3]，[22,5,14;3]，[21,5,13;2]，[20,5,12;3]，[19,5,11;3]，[18,5,10;2]碼。以H5,3i(i=4,5,6)為校驗陣的碼為[12,7,4;3]，[15,10,4;4]和[18,13,4;5]。刪除H5,3i(i=5,6)的最后1 列可分別為[14,9,4;4]與[17,12,4;5]；刪除H5,15的第10和15列得到[13,8,4;4]碼，刪除H5,18的第12和18列可得[16,11,4;5]碼。H5,18依次添加列向量(1,1,1,2,3)T和(1,2,3,1,1)T得到H5,19與H5,20, 以H5,19為校驗陣的碼為[19,14,4;6]，以H5,20為校驗陣的碼為[20,15,4;7]。以上構(gòu)造的LRC都是距離最優(yōu)碼，其中7≤n ≤11的[n,5,d;r]和12≤n ≤20(n ?=13)的[n,n ?5,4;r]碼達到S-L界；12≤n ≤24(n ?=19,20)的[n,5,d;r]碼以及[13,8,4;4]碼達到C-M界；而[19,5,11;3]和[20,5,12;3]碼達不到S-L界和C-M界。

3.5 參數(shù)為[n,6,d]和[n,n ?6,d′]的LRC

記G6,n=(I6|B6,n?6)，構(gòu)造以下7個矩陣，橫線以上的行為校驗陣的局部度行。

由G6,12和G6,12的子矩陣可得[12,6,6;5]和[11,6,5;5]碼；由G6,15和G6,15的子矩陣可得[15,6,8;4]，[14,6,7;4]和[13,6,6;4]碼；由G6,18和G6,18的子矩陣可得[18,6,10;4]，[17,6,9;4]，[16,6,8;4]碼；由G6,20和G6,20的子矩陣可得[20,6,11;3]和[19,6,10;3]碼。以H6,14為校驗陣的碼為[14,8,5;5]，刪除H6,14的最后1列得到[13,7,5;4]碼；以H6,17為校驗陣的碼為[17,11,5;7]，依次刪除H6,17的后2列得到[16,10,5;6]和[15,9,5;5]碼；由H6,21可得[21,15,5;11]，刪除H6,21的后3列得到[20,14,5;10]，[19,13,5;9]，[18,12,5;8]碼。以上構(gòu)造的LRC均為距離最優(yōu)碼，其中[11,6,5;5]和[12,6,6;5]碼達到S-L界；13≤n ≤18的[n,6,d;4]及13≤n ≤21的[n,n ?6,5;r]碼達到CM界；而[19,6,10;3]和[20,6,11;3]碼達不到S-L界和C-M界。

3.6 參數(shù)為[n,7,d]和[n,n ?7,d′]的LRC

記G7,n=(I7|B7,n?7)，構(gòu)造4 個矩陣(見下頁)。矩陣G7,n分別生成[16,7,8;5]，[18,7,9;5]和[20,7,10;5]碼；刪除這3 者的最后1 列分別得到G7,n?1(n=16,18,20)及其生成的[15,7,7;5]，[17,7,8;5]和[19,7,9;5]碼。以H7,20為校驗陣得到[20,13,6;7]碼，依次刪除H7,20的后i(1≤i ≤6)列得到[19,12,6;7]，[18,11,6;6]，[17,10,6;6]，[16,9,6;5]，[15,8,6;5]，[14,7,6;4]碼。以上構(gòu)造的LRC都是距離最優(yōu)碼，其中15≤n ≤18的[n,7,d;r]和14≤n ≤20的[n,n ?7,6;r]碼達到C-M界；而[19,7,9;5]和[20,7,10;5]碼達不到S-L界和C-M界。

3.7 參數(shù)為[n,k ≥8,d]和[n,n ?k,d′]的LRC

構(gòu)造以下7個矩陣，如式(9)，以H8,17為生成陣的碼為[17,8,8;6], 其前16列生成[16,8,7;6]碼；以H8,17為校驗陣的碼為[17,9,7;7]。由校驗陣H8,21可得[21,13,6;8]碼，刪除H8,21的后s(1≤s ≤3)列可得到[20,12,6;7], [19,11,6;7]和[18,10,6;6]碼。由H9,18可得[18,9,8;7]碼，刪除H9,18的最后1 列可得[17,8,8;6]碼。由校驗陣H9,21可得[21,12,7;8]碼，刪除H9,21的后i(1≤i ≤2)列可得[21?i,12?i,7;8?i]碼。以H10,20為校驗陣的碼為[20,10,8;7]碼，刪除H10,20的后i(1≤i ≤2)列可得[20?i,10?i,8;7?i]碼。由校驗陣H11,22可得[22,11,8;7]碼，刪除H11,22的后s(1≤s ≤3)列可得[21,10,8;6]，[20,9,8;5]和[19,8,8;5]碼。以上構(gòu)造的LRC均為距離最優(yōu)碼，其中[n,n ?8,7;r](n=16,17), 19≤n ≤21的[n,n ?9,7;r], [n,n ?9,8;r] (n=17,18), 18≤n≤20的[n,n ?10,8;r]以及20≤n ≤23的[n,n ?12,9;r]達到C-M界；而[n,n ?8,6;r](18≤n ≤20), [19,8,8;5]和[20,9,8;5]達不到S-L界和C-M界。

四元距離最優(yōu)LRC的構(gòu)造結(jié)果：碼長n ≤20的距離最優(yōu)碼共210個，除[n,n,1]碼外的190個距離最優(yōu)碼具有局部修復(fù)功能，其中d=2的碼共34個且達到S-L界。表1給出剩下的156個LRC[n,k,d;r]，達到S-L界的67個LRC用藍色表示；達到C-M界的75個LRC用黑色表示；紅色表示12個達不到S-L界和C-M 界且非r?最優(yōu)的L R C；[7,2,5;2]和[9,2,7;2]達不到S-L界和C-M界，但它們?nèi)允莚?最優(yōu)的。經(jīng)查閱已有文獻，這些構(gòu)造結(jié)果包含了文獻[15]中參數(shù)為[7,4,3;3]的四元LRC，以及文獻[17]中的16個d=3和12個d=4的四元LRC，具體參數(shù)為[17?s,13?s,4;11?s](0≤s ≤5)，[12?j,8?j,4;6?3i ?t](j=4i+t,0≤t ≤3,0≤i ≤1)及[21?s,18?s,3;15?s](1≤s ≤9)和[12?j,9?j,3;6?2i?t](1≤j=3i+t ≤4,0≤t ≤2,0≤i ≤2)。此外，還包含文獻[1 8]中參數(shù)為[2,1,2;1]，[4,1,4;1]，[4,3,2;3]，[3,2,2;2]，[5,4,2;4]的5個四元LRC。

表1 d ≥3 , n ≤20時四元LRC的結(jié)果

4 結(jié)束語

本文研究了四元域上局部度較小的短碼長LRC的構(gòu)造，通過分析四元距離最優(yōu)碼的碼長和維數(shù)，首先利用其生成陣或校驗陣構(gòu)造少量參數(shù)優(yōu)良的LRC，然后刪除或并置已有矩陣得到新LRC的生成陣或校驗陣，最后利用S-L界或C-M界判斷LRC的局部度最優(yōu)性。與文獻[15,17,18]比較，本文構(gòu)造的四元LRC都是距離最優(yōu)碼且其結(jié)果更具有一般性，這對研究四元域上其他LRC的構(gòu)造有很好的借鑒意義。在未來的工作中，將進一步研究四元域上碼長和維數(shù)均較大時最優(yōu)LRC的新構(gòu)造。