短碼長的五元最優(yōu)局部修復(fù)碼

張 茂, 李瑞虎, 宋 倩, 陳 剛

(1.空軍工程大學(xué)基礎(chǔ)部，西安，710051； 2.蘭州市27支局30信箱55號(hào)，蘭州，732750；3.75837部隊(duì)，廣州,510000)

在大數(shù)據(jù)和云存儲(chǔ)系統(tǒng)的發(fā)展中，分布式存儲(chǔ)系統(tǒng)技術(shù)起著重要的作用。在現(xiàn)代分布式存儲(chǔ)系統(tǒng)中，簡(jiǎn)單的數(shù)據(jù)備份是解決節(jié)點(diǎn)錯(cuò)誤所采用的最廣泛的方法，例如三重備份[1]。隨著數(shù)據(jù)量的急劇增加，備份這種方法的缺點(diǎn)被暴露了出來，糾刪碼出現(xiàn)在人們的視野中[2-3]。2012年，Gopalan等人提出了一種新的糾刪碼——局部修復(fù)碼(LRC)，它將數(shù)據(jù)修復(fù)轉(zhuǎn)換成了構(gòu)造滿足一定條件的經(jīng)典碼的問題[4]：一個(gè)局部度為r的[n,k,d]線性碼被記為[n,k,d;r]，其最小距離滿足界：

(1)

這個(gè)界被稱為Singleton形界，達(dá)到這個(gè)界的LRCs被稱為最優(yōu)LRCs。

關(guān)于最優(yōu)LRCs，前人已經(jīng)做了很多工作[5-19]。目前，在二元、三元域上最優(yōu)LRCs的研究已經(jīng)取得了一定進(jìn)展，但在其他域上還有廣闊的發(fā)展空間。二元最優(yōu)LRCs的最小距離不大于4[7]，三元最優(yōu)LRCs的最小距離為2，3，4，5和6[8]。2014年，文獻(xiàn)[6]給出了四元域上d=3,r=3,4的最優(yōu)LRCs。文獻(xiàn)[5]和[11]、[9]、[14]和[17]分別給出了n≤q時(shí)、r+1|n時(shí)和d≤5時(shí)最優(yōu)LRCs的構(gòu)造。利用二元恒重碼，文獻(xiàn)[19]構(gòu)造了4類距離為5和6的最優(yōu)LRCs。當(dāng)r≥d-2且r+1|n時(shí)，文獻(xiàn)[18]給出了4類距離不小于7的最優(yōu)LRCs。文獻(xiàn)[12]運(yùn)用群論構(gòu)造了大域上的最優(yōu)LRCs。關(guān)于最優(yōu)LRCs的碼長的界在文獻(xiàn)[10]和[16]中給出。存在一些研究一般域上最優(yōu)LRCs的論文結(jié)果涉及到五元域，具體的碼見表1。

表1 文獻(xiàn)涉及到五元最優(yōu)LRCs的結(jié)果

對(duì)于參數(shù)為[n,k,d]的q元線性碼，如果參數(shù)為[n,k,d+1]的碼不存在，則稱該q元碼為最優(yōu)的。文獻(xiàn)[20]中已經(jīng)討論了3維和4維最優(yōu)碼的局部度，其中得到的10個(gè)碼長不大于12的局部修復(fù)碼的參數(shù)達(dá)到了Singleton形界。由于小域上的LRCs具有編解碼復(fù)雜度低和易于實(shí)現(xiàn)等優(yōu)點(diǎn)，鑒于以上工作，繼續(xù)構(gòu)造了大量新的最優(yōu)LRCs。文章的主要結(jié)果如下：

1)當(dāng)n≤12,2≤k≤n-1,[n,k]≠[7,2],[9, 2]和[11,2]時(shí)，對(duì)于任意的距離最優(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 預(yù)備知識(shí)

首先，為了便于敘述作以下標(biāo)記：

記[n]={1,2,…,n}；1n和0n各自為長度為n的全1和全0的行向量；對(duì)于矩陣A，m個(gè)A的并置(A,A,…,A)記為mA。

記a=(a1,a2,…,an)，向量a的Hamming重量定義為向量a中非零分量ai(i∈[n])的個(gè)數(shù)。如果C中所有非零碼字的最小Hamming重量為d，則d稱為碼C的最小距離，記為C。

記線性碼C=[n,k,d]。對(duì)任意的c=(c1,c2,…,cn)∈C，若第i個(gè)碼元ci可以由其他個(gè)碼元修復(fù)，則稱ci的局部度為r。如果C中所有碼元的最大局部度為r，則稱碼C的局部度為r。

線性碼的局部度可以根據(jù)生成陣和校驗(yàn)陣通過如下方法來判斷：

引理1[4]記G=(g1,g2，…，gn)為碼C=[n,k,d]的一個(gè)生成陣。對(duì)于任意的rAi?[n]/{i}，如果存在最大為r的集合Ai?[n]/{i}，使得gi是gj(j∈Ai)的線性組合,則碼C的局部度為r。

我們運(yùn)用引理1～3來確定接下來構(gòu)造得到的碼的局部度，構(gòu)造所用到的最優(yōu)碼見文獻(xiàn)[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]和其對(duì)偶碼[6-i,4-i, 3;4-i],(0≤i≤3)；

2)[6-j,3,4-j;3]和其對(duì)偶碼[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個(gè)生成矩陣：

易證明G2×6生成[6,2,5;2]碼，G3×6生成[6,3, 4;3]碼。

1)當(dāng)0≤i≤3時(shí)，刪除G2×6矩陣的最后i列可得到G2×n=G2×(6-i),n=6-i(n≥3)。G2×n生成最優(yōu)LRCC2×n=[n,2,n-1;2]，其對(duì)偶碼為[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]，其對(duì)偶碼為[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é)將分別應(yīng)用生成矩陣和校驗(yàn)矩陣構(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ù)文獻(xiàn)[20]，G3×11和G4×12生成[11,3, 8;2]和[12,4,8;3]最優(yōu)LRCs，其中：

1)當(dāng)0≤i≤4時(shí)，刪除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)當(dāng)0≤j≤5時(shí)，刪除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個(gè)最優(yōu)LRCs的校驗(yàn)陣，矩陣中橫線上面的行代表局部度行。由這些矩陣可以得到其他最優(yōu)LRCs。

3.1 由k≥5的擬MDS碼構(gòu)造最優(yōu)LRCs

給出以下5個(gè)碼的校驗(yàn)陣：

H2×12=(I2,I2,…,I2)

易知H2×12,H3×31,H4×26,H5×12,H6×12對(duì)應(yīng)最優(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]的校驗(yàn)陣H4×(26-t)可通過刪除H4×26的最后t列(0≤t≤14)得到；繼續(xù)刪除H4×12的最后u列(1≤u≤3)，可得到H4×(12-u)，其對(duì)應(yīng)最優(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]的校驗(yàn)陣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個(gè)校驗(yàn)陣：

易知H7×12和H5×24對(duì)應(yīng)最優(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時(shí)d≤8。文中給出了大量五元最優(yōu)LRCs，然而，關(guān)于五元域上是否存在其他最優(yōu)LRCs，仍需要進(jìn)行進(jìn)一步研究。

猜你喜歡

碼長碼元對(duì)偶

構(gòu)造長度為4ps的量子重根循環(huán)碼

合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)(2023年10期)2023-10-31 13:47:36

基于信息矩陣估計(jì)的極化碼參數(shù)盲識(shí)別算法

系統(tǒng)工程與電子技術(shù)(2022年2期)2022-02-23 07:49:16

LFM-BPSK復(fù)合調(diào)制參數(shù)快速估計(jì)及碼元恢復(fù)

雷達(dá)與對(duì)抗(2020年2期)2020-12-25 02:09:26

環(huán)Fq[v]/上循環(huán)碼的跡碼與子環(huán)子碼

山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版)(2018年2期)2018-01-16 03:32:21

基于極大似然準(zhǔn)則的短猝發(fā)信號(hào)盲解調(diào)

無線電通信技術(shù)(2016年6期)2016-12-20 03:08:13

對(duì)偶平行體與對(duì)偶Steiner點(diǎn)

應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào)(2015年1期)2015-07-20 11:39:06

對(duì)偶均值積分的Marcus-Lopes不等式

數(shù)學(xué)年刊A輯(中文版)(2014年4期)2014-10-30 01:50:38

對(duì)偶Brunn-Minkowski不等式的逆

數(shù)學(xué)年刊A輯(中文版)(2014年6期)2014-10-30 01:41:24

碼長為2nps的重根自對(duì)偶負(fù)循環(huán)碼

山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版)(2013年5期)2013-12-18 06:58:42

一種碼元同步時(shí)鐘信號(hào)的提取方法及單片機(jī)實(shí)現(xiàn)

河北大學(xué)學(xué)報(bào)(自然科學(xué)版)(2013年4期)2013-10-28 07:05:39

空軍工程大學(xué)學(xué)報(bào)2020年3期

空軍工程大學(xué)學(xué)報(bào)的其它文章

濾波白噪聲法的單輪起落架滑跑模型

基于CR-WFRFT的物理層安全認(rèn)證方法

平臺(tái)動(dòng)態(tài)防御演化博弈模型和狀態(tài)遷移策略

基于核密度估計(jì)密度峰聚類的通信輻射源個(gè)體識(shí)別

基于置信規(guī)則庫的機(jī)載導(dǎo)彈故障診斷

永磁超環(huán)面電機(jī)模糊終端滑模的直接轉(zhuǎn)矩控制