短碼長的五元最優(yōu)局部修復碼
2020-07-13 09:03:02李瑞虎
空軍工程大學學報 2020年3期
張 茂, 李瑞虎, 宋 倩, 陳 剛
(1.空軍工程大學基礎部，西安，710051； 2.蘭州市27支局30信箱55號，蘭州，732750；3.75837部隊，廣州,510000)
在大數(shù)據(jù)和云存儲系統(tǒng)的發(fā)展中，分布式存儲系統(tǒng)技術(shù)起著重要的作用。在現(xiàn)代分布式存儲系統(tǒng)中，簡單的數(shù)據(jù)備份是解決節(jié)點錯誤所采用的最廣泛的方法，例如三重備份[1]。隨著數(shù)據(jù)量的急劇增加，備份這種方法的缺點被暴露了出來，糾刪碼出現(xiàn)在人們的視野中[2-3]。2012年，Gopalan等人提出了一種新的糾刪碼——局部修復碼(LRC)，它將數(shù)據(jù)修復轉(zhuǎn)換成了構(gòu)造滿足一定條件的經(jīng)典碼的問題[4]：一個局部度為r的[n,k,d]線性碼被記為[n,k,d;r]，其最小距離滿足界：
(1)
這個界被稱為Singleton形界，達到這個界的LRCs被稱為最優(yōu)LRCs。
關(guān)于最優(yōu)LRCs，前人已經(jīng)做了很多工作[5-19]。目前，在二元、三元域上最優(yōu)LRCs的研究已經(jīng)取得了一定進展，但在其他域上還有廣闊的發(fā)展空間。二元最優(yōu)LRCs的最小距離不大于4[7]，三元最優(yōu)LRCs的最小距離為2，3，4，5和6[8]。2014年，文獻[6]給出了四元域上d=3,r=3,4的最優(yōu)LRCs。文獻[5]和[11]、[9]、[14]和[17]分別給出了n≤q時、r+1|n時和d≤5時最優(yōu)LRCs的構(gòu)造。利用二元恒重碼，文獻[19]構(gòu)造了4類距離為5和6的最優(yōu)LRCs。當r≥d-2且r+1|n時，文獻[18]給出了4類距離不小于7的最優(yōu)LRCs。文獻[12]運用群論構(gòu)造了大域上的最優(yōu)LRCs。關(guān)于最優(yōu)LRCs的碼長的界在文獻[10]和[16]中給出。存在一些研究一般域上最優(yōu)LRCs的論文結(jié)果涉及到五元域，具體的碼見表1。
表1 文獻涉及到五元最優(yōu)LRCs的結(jié)果
對于參數(shù)為[n,k,d]的q元線性碼，如果參數(shù)為[n,k,d+1]的碼不存在，則稱該q元碼為最優(yōu)的。文獻[20]中已經(jīng)討論了3維和4維最優(yōu)碼的局部度，其中得到的10個碼長不大于12的局部修復碼的參數(shù)達到了Singleton形界。由于小域上的LRCs具有編解碼復雜度低和易于實現(xiàn)等優(yōu)點，鑒于以上工作，繼續(xù)構(gòu)造了大量新的最優(yōu)LRCs。文章的主要結(jié)果如下：
1)當n≤12,2≤k≤n-1,[n,k]≠[7,2],[9, 2]和[11,2]時，對于任意的距離最優(yōu)的線性碼[n,k,d]均可構(gòu)造為最優(yōu)[n,k,d;r]LRCs；
4)存在以下局部度為1的最優(yōu)LRCs：[6,2,4;1],[10,3,6;1],[8,3,4;1],[6,3,2;1],[8,4,2;1],[10,4,4;1],[12,4,6;1],[10,5,2;1],[12,5,4；1]。
以上所有的最優(yōu)LRCs均由最優(yōu)碼構(gòu)造。其中1)～3)中的LRCs是距離最優(yōu)的，4)中的LRCs不是距離最優(yōu)的。
1 預備知識
首先，為了便于敘述作以下標記：
記[n]={1,2,…,n}；1n和0n各自為長度為n的全1和全0的行向量；對于矩陣A，m個A的并置(A,A,…,A)記為mA。
記a=(a1,a2,…,an)，向量a的Hamming重量定義為向量a中非零分量ai(i∈[n])的個數(shù)。如果C中所有非零碼字的最小Hamming重量為d，則d稱為碼C的最小距離，記為C。
記線性碼C=[n,k,d]。對任意的c=(c1,c2,…,cn)∈C，若第i個碼元ci可以由其他個碼元修復，則稱ci的局部度為r。如果C中所有碼元的最大局部度為r，則稱碼C的局部度為r。
線性碼的局部度可以根據(jù)生成陣和校驗陣通過如下方法來判斷：
引理1[4]記G=(g1,g2，…，gn)為碼C=[n,k,d]的一個生成陣。對于任意的rAi?[n]/{i}，如果存在最大為r的集合Ai?[n]/{i}，使得gi是gj(j∈Ai)的線性組合,則碼C的局部度為r。
我們運用引理1～3來確定接下來構(gòu)造得到的碼的局部度，構(gòu)造所用到的最優(yōu)碼見文獻[22]。
2 由k≤4的距離最優(yōu)的線性碼構(gòu)造LRCs
顯然由1n=(1,1,…,1)可得到平凡碼[n,1,n;1]和[n,n-1,2;n-1]。本節(jié)將由生成陣構(gòu)造k≤4的最優(yōu)LRCs。
2.1 由MDS碼構(gòu)造最優(yōu)LRCs
定理1存在以下最優(yōu)LRCs：
1)[6-i,2,5-i;2]和其對偶碼[6-i,4-i, 3;4-i],(0≤i≤3)；
2)[6-j,3,4-j;3]和其對偶碼[6-j,3-j,4;3-j],(0≤j≤2)；
3)[2s,2,2s-2;1],[2s,3,2s-4;1],(3≤s≤ 6);[12-2u,4,6-2u;1],(0≤u≤2)和[12-2v, 5,4-2v;1],(0≤v≤1)。
證明構(gòu)造如下2個生成矩陣：
易證明G2×6生成[6,2,5;2]碼，G3×6生成[6,3, 4;3]碼。
1)當0≤i≤3時，刪除G2×6矩陣的最后i列可得到G2×n=G2×(6-i),n=6-i(n≥3)。G2×n生成最優(yōu)LRCC2×n=[n,2,n-1;2]，其對偶碼為[n,n- 2,3;n-2]。由此可得到最優(yōu)LRCs[6,2,5;2],[5,2, 4;2],[4,2,3;2],[3,2,2;2],[6,4,3;4],[5,3,3;3],[4,2,3;2]和[3,1,3;1]。
2)刪除G3×6矩陣的最后j列(0≤j≤2)可得到矩陣G3×n=G3×(6-j)(n=6-j)。G3×n生成最優(yōu)LRCC3×n=[n,3,n-2;3]，其對偶碼為[n,n-3, 4;n-3]。由此得到最優(yōu)LRCs[6,3,4;3],[5,3,3;3], [4,3,2;3],[6,3,4;3],[5,2,4;2]和[4,1,4;1]。
3)令G2×2m=(G2×m,G2×m),G3×2m=(G3×m,G3×m),(3≤m≤6)，可得到最優(yōu)LRCs[2m,2,2m-2;1]和[2m,3,2m-4;1]。同樣，可構(gòu)造最優(yōu)LRCs [2m,4,2m-6;1],(4≤m≤6)和[2m,5,2m-8;1] (5≤m≤6)。由此可得到最優(yōu)LRCs[12,2,10;1], [10,2,8;1],[8,2,6;1],[6,2,4;1],[12,3,8;1],[10,3,6;1],[8,3,4;1],[6,3,2;1],[8,4,2;1],[10,4,4;1],[12,4,6;1],[10,5,2;1]和[12,5,4;1]。其中[12,2,10;1], [10,2,8;1],[8,2,6;1]和[12,3,8;1]是距離最優(yōu)的。
2.2 由擬MDS碼構(gòu)造最優(yōu)LRCs
本節(jié)將分別應用生成矩陣和校驗矩陣構(gòu)造3≤k≤4的最優(yōu)LRCs。
定理2存在最優(yōu)LRCs[n,3,n-3;2],(7≤n≤ 11)和[n,4,n-4;3],(7≤n≤12)。
證明根據(jù)文獻[20]，G3×11和G4×12生成[11,3, 8;2]和[12,4,8;3]最優(yōu)LRCs，其中：
1)當0≤i≤4時，刪除G3×11的最后i列可得到以下最優(yōu)碼的生成陣：[11,3,8;2],[10,3,7;2], [9,3,6;2],[8,3,5;2]和[7,3,4;2]。
2)當0≤j≤5時，刪除G4×12的最后j列可得到以下最優(yōu)碼的生成陣：[12,4,8;3],[11,4,7;3], [10,4,6;3],[9,4,5;3],[8,4,4;3]和[7,4,3;3]。
3 由k≥5的距離最優(yōu)的線性碼構(gòu)造LRCs
給出了7個最優(yōu)LRCs的校驗陣，矩陣中橫線上面的行代表局部度行。由這些矩陣可以得到其他最優(yōu)LRCs。
3.1 由k≥5的擬MDS碼構(gòu)造最優(yōu)LRCs
給出以下5個碼的校驗陣：
H2×12=(I2,I2,…,I2)
易知H2×12,H3×31,H4×26,H5×12,H6×12對應最優(yōu)LRCs[12,10,2;5]，[31,28,3;24]，[26,22,4;19]，[12,7,5;5]和[12,6,6;5]。
定理3存在以下最優(yōu)LRCs：
3)[26-t,22-t,4;19-t],(0≤t≤14),[11 -u,7-u,4;5-u],(0≤u≤2)；
(4)[12-v,7-v,5;5-v],(0≤v≤2)；
(5)[12,6,6;5]和[11,5,6;4]。
證明：
3)最優(yōu)LRC[26-t,22-t,4;19-t]的校驗陣H4×(26-t)可通過刪除H4×26的最后t列(0≤t≤14)得到；繼續(xù)刪除H4×12的最后u列(1≤u≤3)，可得到H4×(12-u)，其對應最優(yōu)LRCs[11,7,4;5],[10, 6,4;4]和[9,5,4;3]。
4)最優(yōu)LRCs[11,6,5;4]和[10,5,5;4]的校驗陣H5×(12-v)可通過刪除H5×12的最后v列(1≤v≤ 2)得到；
5)刪除H6×12的最后一列可得到H6×11和最優(yōu)LRC[11,5,6;4]。
3.2 k≥5且k+d
證明 給出如下2個校驗陣：
易知H7×12和H5×24對應最優(yōu)LRCs[12,5,6;2]和[24,19,4;9]。
刪除H5×24的最后i列(1≤i≤10)可得到參數(shù)為[23,18,4;9],[22,17,4;8],[21,16,4;7],[20,15, 4;7],[19,14,4;6],[18,13,4;5],[17,12,4;5],[16,11,4;5],[15,10,4;4]和[14,9,4;4]的LRCs。其中除了[23,18,4;9]外，其余均為最優(yōu)的。
綜上所述，定理1～4給出了前言部分的所有結(jié)果。
4 結(jié)語
本文研究了五元域上最優(yōu)LRCs的構(gòu)造，并給出了4類最優(yōu)LRCs。除了參數(shù)為[12,2,10;1]的最優(yōu)LRC，其他最優(yōu)LRCs均滿足最小距離d=3,4或n≤12時d≤8。文中給出了大量五元最優(yōu)LRCs，然而，關(guān)于五元域上是否存在其他最優(yōu)LRCs，仍需要進行進一步研究。
證明 給出如下2個校驗陣：
易知H7×12和H5×24對應最優(yōu)LRCs[12,5,6;2]和[24,19,4;9]。
刪除H5×24的最后i列(1≤i≤10)可得到參數(shù)為[23,18,4;9],[22,17,4;8],[21,16,4;7],[20,15, 4;7],[19,14,4;6],[18,13,4;5],[17,12,4;5],[16,11,4;5],[15,10,4;4]和[14,9,4;4]的LRCs。其中除了[23,18,4;9]外，其余均為最優(yōu)的。
綜上所述，定理1～4給出了前言部分的所有結(jié)果。
4 結(jié)語
本文研究了五元域上最優(yōu)LRCs的構(gòu)造，并給出了4類最優(yōu)LRCs。除了參數(shù)為[12,2,10;1]的最優(yōu)LRC，其他最優(yōu)LRCs均滿足最小距離d=3,4或n≤12時d≤8。文中給出了大量五元最優(yōu)LRCs，然而，關(guān)于五元域上是否存在其他最優(yōu)LRCs，仍需要進行進一步研究。
