Constructions of Quaternary Optimal Locally Repairable Code with Short Length
-
摘要: 在分布式存储系统中,当节点发生故障时局部修复码(LRC)可以通过访问少量其他节点来恢复数据,然而LRC的局部度不尽相同,该文构造了短码长且局部度较小的四元LRC。当码长不超过20,最小距离大于2时,若四元距离最优线性码的生成阵维数不超过校验阵维数,可利用其生成阵给出LRC,否则利用其校验阵给出LRC。对已构造的LRC的生成阵或校验阵,利用删除、并置等方法得到新矩阵,从而构造出190个码长
n≤20 ,最小距离d≥2 的LRC。除12个LRC外,其他LRC是局部度最优的。Abstract: In distributed storage system, when a node fails, Locally Repairable Code (LRC) can access other nodes to recover data. However, the locality of LRC is not the same. Quaternary LRC with short code length and small locality is constructed. When code length is not more than 20 and minimum distance is greater than 2, if the dimension of generator matrix of a quaternary distance optimal linear code does not exceed the dimension of parity-check matrix, an LRC can be constructed from generator matrix, otherwise parity-check matrix can be used to construct an LRC. From generator matrices or parity-check matrices of LRCs constructed, other LRC are given by operations of deleting and juxtaposition. There are 190 LRC with code length n ≤ 20 and minimum distance d ≥ 2 to be constructed. Except for 12 LRC, other LRC are all locality optimal.-
Key words:
- Optimal code /
- Locally Repairable Code (LRC) /
- Generator matrix /
- Parity-check matrix
-
1. 引言
在分布式存储系统中,三重备份能够保证数据的可靠性,并且它是最简单的方法[1]。然而三重备份的存储效率低、存储代价过大,于是人们提出了存储负荷更低的纠删码方案[2,3]。传统纠删码能满足高效存储的需求,但是修复效率低,因此编码学者提出了局部修复码[3]。2012年,Gopalan等人[4]提出LRC的概念以及Singleton-Like (S-L)界,但是S-L界在小域[4,5]上是不紧的。为了更加精确地描述
q 元局部修复码4个参数之间的关系,Cadambe和Mazumdar[6]提出考虑域的大小的界,即Cadambe-Mazumdar (C-M)界。在工程应用中,小域上LRC的编、解码复杂度较低,更具有使用价值[7]。二元域上LRC取得一定进展,人们研究了达到S-L界[8,9]以及C-M界[10,11]的局部度最优LRC。文献[12,13]研究了三元距离较小或者维数较低的局部度最优LRC。在四元域上,人们得到一些局部度最优LRC:文献[14]构造了2类距离为3的四元LRC;文献[15]构造了距离为4的四元LRC;这3类LRC是局部度最优和拟最优的[14,15]。Barg等人[16]利用代数曲线和代数曲面构造了码长为18、维数为11、距离为3、局部度为2的四元LRC。文献[17]通过缩短
q 元汉明码与(q2+1)− cap构造了距离为3和4的LRC,从而可得到16个距离为3和12个距离为4的局部度最优四元LRC。Jin等人[18]利用有限域上的自同构群构造一般域上LRC,可得到码长不超过5的四元LRC。由以上结果可知,当码长不超过20时,文献[14,15,16]构造了特定距离的局部度最优或拟最优四元LRC,但只有1个码是距离最优码;文献[17]的2个四元LRC以及文献[18]的1个四元LRC都不是距离最优码。由文献[19]可知,当域的大小为2的幂次时,码的运行速度快,并且文献[20]给出了RS码校验关系的等价转换方式,避免了复杂的符号转化。依据文献[21-23],码长不超过20的距离最优四元码的参数完全确定。由文献[23]可知,对于给定的码长和维数,距离最优四元码往往有很多,但是它们的局部度也有差别,人们往往更关注局部度尽可能小的LRC。基于此本文研究四元LRC,由已有文献结果可知,目前四元LRC的研究并不充分,其结果较为零散,因此本文将研究码长不超过20的四元码,设法构造距离最优且局部度尽可能小的四元LRC,并利用S-L界或C-M界判断其局部度的最优性。
2. 预备知识
令
F4={0,1,ω,ω2} 为四元域,记ω=2 ,ω2=3 ,F4={0,1,2,3} 。Fn4 为F4 上的n 维向量空间,若一个非零向量的第1个非零分量是1,则称此向量为首一向量。称Fn4 的k 维子空间C 为四元线性码[n,k]4 ,并记为C=[n,k]4 ,n 称为C 的码长,C 中的向量称为码字。若
x=(x1,x2,⋯,xn) ,y=(y1,y2,⋯,yn)∈Fn4 ,x 的汉明重量为wt(x)=#{i|1≤i≤n,xi≠0} ,x 与y 的汉明距离为d(x,y)=wt(x−y) 。若C 中非零码字的最小汉明重量为d ,则记C=[n,k,d]4 ,若不存在[n,k,d+1]4 码,则称C=[n,k,d]4 为距离最优码。对于x,y∈Fn4 ,x 与y 的内积为(x,y)= ∑ni=1xi⋅yi 。称C⊥={x∈Fn4|(x,c)=0,∀c∈C} 为C 的对偶码,显然C⊥ 的维数为n−k 。由C 的一组基构成的k×n 矩阵Gk,n 称为C 的生成阵,C⊥ 的生成阵Hn−k,n=(h1T,h2T,⋯,hn−kT)T 称为C 的校验阵。C=[n,k,d]q 是码长为n 、维数为k 、最小距离为d 的q 元线性码,若码字c=(c1,c2,⋯,cn)∈C 的第i 个码元ci (1≤i≤n) 都能通过除第i 位以外的其他至多r 位恢复,则称C 的局部度为r ,并记C=[n,k,d;r]q 。线性码的局部度可以由生成阵和校验阵确定,具体如下:引理1[4] 设线性码
C=[n,k,d]q 的生成阵为Gk,n=(g1,g2,⋯,gn) ,gi 是k 维列向量,当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]d≤n−k+2−⌈k/r⌉ (1) 等式成立时,称码达到S-L界。特别地,当
k=r 时,S-L界退化为经典的Singleton界。k≤mint∈Z+{tr+kqopt(n−t(r+1),d)} (2) 其中,
kqopt(n,d) 是码长为n 、最小距离为d 的q 元码的最大维数。等式成立时称C 达到C-M界。若
C=[n,k,d;r]q 达到S-L界或C-M界,或者[n,k,d;r−1]q 的局部修复码不存在,则称C 是局部度最优的(r− 最优的)。约定:
[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) 的转置。[n]={1,2,⋯,n} ,并约定n≤20 ;In 为n 阶单位阵。记Gk,m 的l 个并置为Gk,lm=(Gk,m,Gk,m,⋯,Gk,m)=(lGk,m) 。3.
F4 上短码长LRC的构造码长
n≤20 的距离最优码共210个,其中[n,n,1] 码不具有局部修复功能,还余下190个距离最优码。对于n≥2 ,1n 生成[n,1,n;1] 码,其对偶码为[n,n−1,2;n−1] ,此两码达到S-L界。故以下仅需考虑[n,k,d] 和[n,n−k,d′] (k≥2 )形式的局部修复码构造,分7个小节展开讨论。由文献[22,23],分以下3步构造距离最优码的生成阵
Gk,n :步骤1 由文献[22,23]得到距离最优码的生成阵,利用四元域中的乘法运算将生成阵中的列向量化为首一列向量;
步骤2 将首一列向量按照列汉明重量由小到大的顺序排列;
步骤3 对排序后的生成阵做列置换,依次删除生成阵
Gk,n 的最后j (1≤j<n−k) 个列向量得到子矩阵Gk,n−j ,从而由已有LRC构造新LRC。3.1 参数为
[n,2,d] 和[n,n−2,d′] 的LRC构造
G2,5=(1011101123)=(g1,g2,⋯,g5) ,G2,i=(g1,g2,⋯,gi) 以及G2,2i=(G2,i|G2,i) ,2≤i≤5 。由
G2,i (3≤i≤5) 可得[3,2,2;2] ,[4,2,3;2] 和[5,2,4;2] 码;由G2,2i (3≤i≤5) 可得[6,2,4;1] ,[8,2,6;1] 和[10,2,8;1] 码。令G2,5+j=(G2,5|G2,j) (j= 2,4) ,可得[7,2,5;2] 和[9,2,7;2] 码。若n=5l 且l≥2 ,则G2,5l=(lG2,5) 生成[5l,2,4l;1] 码。若n=5l+i≥ 11 ,1≤i≤4 且l≥2 ,则G2,5l+i= (G2,5(l−1)|G2,5+i) 生成[5l+i,2,4l+i−1;1] 码。当2m≥6 时,构造校验阵H2,2m=(1m0m0m1m),H2,2m+1=(1m0m+10m1m+1) (3) 以
H2,2m 和H2,2m+1 为校验阵的码为\left[ n,n - 2, 2;\left\lceil {{{(n - 2)} / 2}} \right\rceil \right] (n=2m,2m+1≥6 )。以上构造的LRC都是距离最优码,其中r=1的LRC的局部度已达到最小;码长
3≤n≤10(n≠7,9) 的[n,2,d;r] 码和n≥6 的\left[ n, n - 2, 2;\left\lceil {{{(n - 2)} / 2}} \right\rceil \right] 达到S-L界;[7,2,5;2] 和[9,2,7;2] 达不到S-L界和C-M界,但不难验证[7,2,5;1] 和[9,2,7;1] 不存在,故这两个码仍是r− 最优的。3.2 参数为
[n,3,d] 和[n,n−3,d′] 的LRC记
G3,n=(I3|B3,n−3) ,构造如式(4)的4个矩阵:B3,2=(111232),B3,6=(111111031223203131),B3,13=(001111111111111002311122331212001231323),G3,21=(100|011|011|011|111111111010|101|102|103|111222333001|110|220|330|123123123)=(α1,α2,⋯,α21) (4) 以上
G3,n 分别生成[5,3,3;3] ,[9,3,6;2] ,[16,3,12;2] 和[21,3,16;2] 码。由G3,5 的子矩阵可得[4,3,2;3] ;G3,5 添加列向量(1,3,1)T 得到G3,6 ,G3,6 生成[6,3,4;3] 。类似地,由G3,9 的子矩阵可得[7,3,4;2] 和[8,3,5;2] 码;由G3,16 的子矩阵G3,n (n=16−j,1≤j≤5) 可得[16−j,3,12−j;2] 码。当17≤n=21−j≤21 时,由G3,21 的子矩阵G3,n 可得[21−j,3,16−j;2] 。特别地,当i=5,6 时,构造G3,2i=(G3,i|G3,i) ,G3,2i 生成[10,3,6;1] 和[12,3,8;1] 码。记G3,n=(α1,α2,⋯,αn) ,7≤n≤21 。当13≤n=21−j≤21 时,以G3,n 为校验阵的码为[n,n−3,3;15−j] [19]。当7≤n= 12−j≤12 时,以G3,n 为校验阵的码为\left[ 12 - j,9 - j, 3;6 - \left\lfloor {{{2j} / 3}} \right\rfloor \right] 。以上构造的LRC均为距离最优码,其中
4≤n≤10 的[n,3,d;r] 以及[n,n−3,3;6−⌊2j/3⌋] (7≤n=12−j≤12) 和[n,n−3,3;15−j] \left( 13 \le n = 21 - j \le 21 \right) 码达到S-L界;11≤n=16−j≤15 的[n,3,12−j;2] ,[16,3,12;2] 和[n,3,16−j;2] (17≤n= 21−j≤21) 码为达到C-M界的LRC。3.3 参数为
[n,4,d] 和[n,n−4,d′] 的LRC记
G4,n=(I4|B4,n−4) ,构造如式(5)的5个矩阵,G4,17 由文献[17]给出B4,2=(01011010),B4,6=(011111122133201313330132),B4,19=(0011101111111111101110011031113333011203030213122122330113020031012331132322),B4,13=(0111|0111|111111031|1022|121333202|2301|321131130|2310|22321),H4,21=(100|100|100|100|011|011|011010|010|010|010|101|102|103001|001|001|001|110|220|330000|111|222|333|000|000|000) (5) 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] 。当1≤i≤3 时,删除H4,21 的后i 列得到[20,16,3;9] ,[19,15,3;8] 和[18,14,3;7] 码。以上构造的LRC都是距离最优码,其中6≤n≤10 的[n,4,d;r] 码和9≤ n≤17 的[n,n−4,4;r] 码达到S-L界; 达到C-M界的LRC为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 参数为
[n,5,d] 和[n,n−5,d′] 的LRC记
G5,n=(I5|B5,n−5) ,构造以下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] 码。当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] 。以上构造的LRC都是距离最优码,其中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界。B5,2=(0101011010),B5,6=(011111103223321313133012310133),B5,9=(001111111010123312113122233103110322323003231),B5,12=(000111111111011003121122123231033132202122311332210200223133),B5,19=(10001011111111111111011011231123203203010301221332131201301201230312231023120132130303133111203),H3,6=(111111231213112233)=(1,1,1,1,⋯,1γ1,γ2,⋯,γ6),H5,3⋅i=(1i0i0i0i1i0i0i0i1iXiXiXi) (6) 3.5 参数为
[n,6,d] 和[n,n−6,d′] 的LRC记
G6,n=(I6|B6,n−6) ,构造以下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] 码。以上构造的LRC均为距离最优码,其中[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] 码达到C-M界;而[19,6,10;3] 和[20,6,11;3] 码达不到S-L界和C-M界。3.6 参数为
[n,7,d] 和[n,n−7,d′] 的LRC记
G7,n=(I7|B7,n−7) ,构造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] 码。以上构造的LRC都是距离最优码,其中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界。B6,6=(111111012312102331233021230213323211),B6,9=(111111111013011233311200122310213013300331112001231221),B6,12=(001111011111010112102312120010113333113001211013103200222331132233120323), B6,14=(000110111111110110010123123312122332123311203032303311110103031203131210332312302323),H6,14=(110000003030321000202000031110303000310001013200002003020011200300001200103100001202),H6,17=(10000013020120013013200002020030110012231000020003110002020100003123¯0130300030013030300103100220012020),H6,21=(100001013020120320121010000101302011032212001223310000200110221¯000100033221201133102000010130211213202200000001331303303113111);B7,9=(011111011101123101210110232223100111120103322301011132031023312),B7,11=(11001011111030121311120011111332303130212311101311001121231321313321203322313),B7,13=(0101101111111101201030133112001132002123021121332013030001232321133302000121230032332031103),H7,20=(10020103000001101001011000000230101020300012332000000002011000000002333200010201¯120030103001320000000101320031030020320000013311032220001000) (7) 3.7 参数为
[n,k≥8,d] 和[n,n−k,d′] 的LRC构造以下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] 码。以上构造的LRC均为距离最优码,其中[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界。H8,17=(100000001212320030100003033222000300010002220030331120002012300100021210003011000001201003002130010033¯0013101200012003000001210000232103),H8,21=(103320000010302000011012002032001000300011000010111110000001302000000000001111111101¯120201300200010030001103320000010302000012010101301000201002110001002110200101032030), H9,18=(100001000013231002013000003100100321000100001022331001000010000132211003000001103000111032000000133101310003¯001003300110031003001100003101300110000010110200012310),H9,21=(100000000122010220022010130000003002010333001023100300000031031000100122000302300012¯000010110000003103313000001001302010303012000000100130201030213000000012201202020022000000001220122202200),H10,20=(1000000300001310033101000020210100002021001003113003000000310001003131003000001300001003131003000013¯0000010020001022021100000011200212002100000000010113310030031303001001013000003001303300000010300101),H11,22=(100030203000100002001100100031000100000033130120002100100200000031010002303000000100302110020030000030100020331020310000300000200032¯00012020002300033020000000101000303023100020000000030310300013101000000010311002000012011000000000230331010001) (9) 四元距离最优LRC的构造结果:码长
n≤20 的距离最优码共210个,除[n,n,1] 码外的190个距离最优码具有局部修复功能,其中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− 最优的LRC;[7,2,5;2] 和[9,2,7;2] 达不到S-L界和C-M界,但它们仍是r− 最优的。经查阅已有文献,这些构造结果包含了文献[15]中参数为[7,4,3;3] 的四元LRC,以及文献[17]中的16个d=3 和12个d=4 的四元LRC,具体参数为[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) 。此外,还包含文献[18]中参数为[2,1,2;1] ,[4,1,4;1] ,[4,3,2;3] ,[3,2,2;2] ,[5,4,2;4] 的5个四元LRC。表 1d≥3 ,n≤20 时四元LRC的结果n/k 1 2 3 4 5 6 7 8 9 3 3(1) 4 4(1) 3(2) 5 5(1) 4(2) 3(3) 6 6(1) 4(1) 4(3) 7 7(1) 5(2) 4(2) 3(3) 8 8(1) 6(1) 5(2) 4(3) 3(4) 9 9(1) 7(2) 6(2) 5(3) 4(4) 3(4) 10 10(1) 8(1) 6(1) 6(3) 5(4) 4(5) 3(5) 11 11(1) 8(1) 7(2) 6(3) 6(4) 5(5) 4(6) 3(6) 12 12(1) 9(1) 8(1) 7(3) 6(3) 6(5) 4(3) 4(6) 3(6) 13 13(1) 10(1) 9(2) 8(3) 7(3) 6(4) 5(4) 4(4) 4(7) 14 14(1) 11(1) 10(2) 9(3) 8(3) 7(4) 6(4) 5(5) 4(4) 15 15(1) 12(1) 11(2) 10(3) 8(3) 8(4) 7(5) 6(5) 5(5) 16 16(1) 12(1) 12(2) 11(3) 9(3) 8(4) 8(5) 7(6) 6(5) 17 17(1) 13(1) 12(2) 12(3) 10(3) 9(4) 8(5) 8(6) 7(7) 18 18(1) 14(1) 13(2) 12(3) 10(2) 10(4) 9(5) 8(5) 8(7) 19 19(1) 15(1) 14(2) 12(2) 11(3) 10(3) 9(5) 8(5) 8(6) 20 20(1) 16(1) 15(2) 13(2) 12(3) 11(3) 10(5) 9(4) 8(5) n/k 10 11 12 13 14 15 16 17 13 3(7) 14 4(8) 3(8) 15 4(4) 4(9) 3(9) 16 5(6) 4(5) 4(10) 3(10) 17 6(6) 5(7) 4(5) 4(11) 3(11) 18 6(6) 6(6) 5(8) 4(5) 3(7) 3(12) 19 7(6) 6(7) 6(7) 5(9) 4(6) 3(8) 3(13) 20 8(7) 7(7) 6(7) 6(7) 5(10) 4(7) 3(9) 3(14) H12,23=(10320000200000200000213000000000110130030001330000030330000030020011200000120003000032000111010000020000020000332210120230000002000000023100000030200320000010112¯0013000000000201001311000010033000003301001010000030030000030012302100000000033021330001001010001000200300001030220), H12,27=(100000000000010312031033323010000000000320300332022221000000100000233002030112321001203002002022000200003212010100000300013130003003131102003320300000020020003331000130300001200000002222112103202100020000302000003113¯000001000000302213132020130000000001000200302122230233000000000100321301323300130000000000010002130132333013) (10) 4. 结束语
本文研究了四元域上局部度较小的短码长LRC的构造,通过分析四元距离最优码的码长和维数,首先利用其生成阵或校验阵构造少量参数优良的LRC,然后删除或并置已有矩阵得到新LRC的生成阵或校验阵,最后利用S-L界或C-M界判断LRC的局部度最优性。与文献[15,17,18]比较,本文构造的四元LRC都是距离最优码且其结果更具有一般性,这对研究四元域上其他LRC的构造有很好的借鉴意义。在未来的工作中,将进一步研究四元域上码长和维数均较大时最优LRC的新构造。
-
表 1
d≥3 ,n≤20 时四元LRC的结果n/k 1 2 3 4 5 6 7 8 9 3 3(1) 4 4(1) 3(2) 5 5(1) 4(2) 3(3) 6 6(1) 4(1) 4(3) 7 7(1) 5(2) 4(2) 3(3) 8 8(1) 6(1) 5(2) 4(3) 3(4) 9 9(1) 7(2) 6(2) 5(3) 4(4) 3(4) 10 10(1) 8(1) 6(1) 6(3) 5(4) 4(5) 3(5) 11 11(1) 8(1) 7(2) 6(3) 6(4) 5(5) 4(6) 3(6) 12 12(1) 9(1) 8(1) 7(3) 6(3) 6(5) 4(3) 4(6) 3(6) 13 13(1) 10(1) 9(2) 8(3) 7(3) 6(4) 5(4) 4(4) 4(7) 14 14(1) 11(1) 10(2) 9(3) 8(3) 7(4) 6(4) 5(5) 4(4) 15 15(1) 12(1) 11(2) 10(3) 8(3) 8(4) 7(5) 6(5) 5(5) 16 16(1) 12(1) 12(2) 11(3) 9(3) 8(4) 8(5) 7(6) 6(5) 17 17(1) 13(1) 12(2) 12(3) 10(3) 9(4) 8(5) 8(6) 7(7) 18 18(1) 14(1) 13(2) 12(3) 10(2) 10(4) 9(5) 8(5) 8(7) 19 19(1) 15(1) 14(2) 12(2) 11(3) 10(3) 9(5) 8(5) 8(6) 20 20(1) 16(1) 15(2) 13(2) 12(3) 11(3) 10(5) 9(4) 8(5) n/k 10 11 12 13 14 15 16 17 13 3(7) 14 4(8) 3(8) 15 4(4) 4(9) 3(9) 16 5(6) 4(5) 4(10) 3(10) 17 6(6) 5(7) 4(5) 4(11) 3(11) 18 6(6) 6(6) 5(8) 4(5) 3(7) 3(12) 19 7(6) 6(7) 6(7) 5(9) 4(6) 3(8) 3(13) 20 8(7) 7(7) 6(7) 6(7) 5(10) 4(7) 3(9) 3(14) -
[1] WEATHERSPOON H and KUBIATOWICZ J D. Erasure coding vs. replication: A quantitative comparison[C]. The 1st International Workshop on Peer-to-Peer Systems, Cambridge, UK, 2002: 328–337. doi: 10.1007/3-540-45748-8_31. [2] HUANG Cheng, SIMITCI H, XU Yikang, et al. Erasure coding in windows azure storage[C]. 2012 USENIX Annual Technical Conference, Boston, USA, 2012: 15–26. [3] BALAJI S B, KRISHNAN M N, VAJHA M, et al. Erasure coding for distributed storage: An overview[J]. Science China Information Sciences, 2018, 61(10): 100301. doi: 10.1007/s11432-018-9482-6 [4] GOPALAN P, HUANG Cheng, SIMITCI H, et al. On the locality of codeword symbols[J]. IEEE Transactions on Information Theory, 2012, 58(11): 6925–6934. doi: 10.1109/TIT.2012.2208937 [5] PAPAILIOPOULOS D S and DIMAKIS A G. Locally repairable codes[C]. 2012 IEEE International Symposium on Information Theory, Cambridge, USA, 2012: 2771–2775. doi: 10.1109/ISIT.2012.6284027. [6] CADAMBE V and MAZUMDAR A. An upper bound on the size of locally recoverable codes[C]. 2013 International Symposium on Network Coding, Calgary, Canada, 2013: 1–5. doi: 10.1109/NetCod.2013.6570829. [7] GOPARAJU S and CALDERBANK R. Binary cyclic codes that are locally repairable[C]. 2014 International Symposium on Information Theory, Honolulu, USA, 2014: 676–680. doi: 10.1109/ISIT.2014.6874918. [8] HAO Jie, XIA Shutao, and CHEN Bin. Some results on optimal locally repairable codes[C]. 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016: 440–444. doi: 10.1109/ISIT.2016.7541337. [9] HAO Jie and XIA Shutao. Bounds and constructions of locally repairable codes: Parity-check matrix approach[EB/OL]. https://arxiv.org/abs/1601.05595v1, 2019. [10] FU Qiang, LI Ruihu, GUO Luobin, et al. Locality of optimal binary codes[J]. Finite Fields and Their Applications, 2017, 48: 371–394. doi: 10.1016/j.ffa.2017.08.013 [11] 杨森, 李瑞虎, 付强, 等. 二元局部修复码的新构造[J]. 空军工程大学学报: 自然科学版, 2019, 20(6): 104–108.YANG Sen, LI Ruihu, FU Qiang, et al. The new Constructions of binary locally repairable codes[J]. Journal of Air Force Engineering University:Natural Science Edition, 2019, 20(6): 104–108. [12] HAO Jie, XIA Shutao, and CHEN Bin. On optimal ternary locally repairable codes[C]. 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017: 171–175. doi: 10.1109/ISIT.2017.8006512. [13] YANG Ruipan, LI Ruihu, GUO Luobin, et al. Locality of some optimal ternary linear codes[J]. Procedia Computer Science, 2017, 107: 164–169. doi: 10.1016/j.procs.2017.03.073 [14] WESTERBACK T, ERNVALL T, and HOLLANTI C. Almost affine locally repairable codes and matroid theory[C]. 2014 IEEE Information Theory Workshop, Hobart, Australia, 2014: 621–625. doi: 10.1109/ITW.2014.6970906. [15] ERNVALL T, WESTERBÄCK T, and HOLLANTI C. Constructions of optimal and almost optimal locally repairable codes[C]. The 4th International Conference on Wireless Communications, Vehicular Technology, Information Theory and Aerospace & Electronic Systems (VITAE), Aalborg, Denmark, 2014: 1–5. doi: 10.1109/VITAE.2014.6934442. [16] BARG A, HAYMAKER K, HOWE E W, et al. Locally Recoverable Codes from Algebraic Curves and Surfaces[M]. HOWE E W, LAUTER K E, and WALKER J L. Algebraic Geometry for Coding Theory and Cryptography. Cham: Springer, 2016, 95–127. doi: 10.1007/978-3-319-63931-4_4. [17] FU Qiang, LI Ruihu, GUO Luobin, et al. Singleton-type optimal LRCs with minimum distance 3 and 4 from projective code[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer, 2021, E104-A(1): 319–323. doi: 10.1587/transfun.2019eal2158 [18] JIN Lingfei, MA Liming, and XING Chaoping. Construction of optimal locally repairable codes via automorphism groups of rational function fields[J]. IEEE Transactions on Information Theory, 2020, 66(1): 210–221. doi: 10.1109/TIT.2019.2946637 [19] PLANK J, GREENAN K, and MILLER E. Screaming fast Galois field arithmetic using Intel SIMD instructions[C]. The 11th USENIX Conference on File and Storage Technologies, San Jose, USA, 2013: 299–306. [20] 吴昭军, 张立民, 钟兆根, 等. 一种软判决下的RS码识别算法[J]. 电子与信息学报, 2020, 42(9): 2150–2157. doi: 10.11999/JEIT190690WU Zhaojun, ZHANG Limin, ZHONG Zhaogen, et al. Blind recognition of RS codes based on soft decision[J]. Journal of Electronics &Information Technology, 2020, 42(9): 2150–2157. doi: 10.11999/JEIT190690 [21] FEULNER T. Classification and nonexistence results for linear codes with prescribed minimum distances[J]. Designs, Codes and Cryptography, 2014, 70(1): 127–138. doi: 10.1007/s10623-012-9700-8 [22] GRASSL M. Bounds on the minimum distance of linear codes[EB/OL]. http://www.codetables.de, 2020. [23] BOUYUKLIEV I, GRASSL M, and VARBANOV Z. New bounds forand classification of some optimal codes over[J]. Discrete Mathematics, 2004, 281(1/3): 43–66. doi: 10.1016/j.disc.2003.11.003 -
计量
- 文章访问数: 866
- HTML全文浏览量: 512
- PDF下载量: 60
- 被引次数: 0