基于循环码的三元局部修复码构造

郑尤良, 李瑞虎, 吕京杰, 张 茂

(空军工程大学基础部，西安，710051)

随着大数据时代的到来，世界上的数据量急剧增长，对存储系统的要求也逐步提高。分布式存储系统由于采用了可扩展结构，提高了系统的可用性和存储效率，因此得到了广泛应用。为了提高分布式存储系统的容错能力，2012年Gopalan提出了局部修复码的概念[1]。局部修复码是一类特殊的纠删码，其码字的任一信息位发生错误时都可通过访问其它不超过r个信息位进行恢复，r被称为码的局部修复度(Locality)[2]。此后，Cadambe和Mazumdar提出了一个考虑域q大小的局部修复码的参数上界，即C-M界[3]。设C=[n,k,d]q, 若其局部修复度为r, 则:

(1)

定义1[4]码长为n的q元线性码C叫作循环码，是指若c=(c0,c1,…,cn-1)∈C，则c的循环移位(cn-1,c0,c1,…,cn-2)∈C。

引理1[5]令循环码C=[n，k，d]，D为C的对偶码。若D的最小距离为d⊥，则C的局部修复度r=d⊥-1。

循环码由于其所具有的特殊结构，能够更好地设计和分析码的局部度，因此近年来关于循环码的局部度问题研究日益增多。Zeh等人在2015年利用循环码生成了部分局部度r=2的码[6]。Kim等人通过分析二、三元域上的循环码，得到了一些距离大于4的局部修复码[7]。文献[8～9]中考虑通过常循环码来构造局部修复码。饶驿等给出了二元域上循环码构造具有2、3局部度的码的构造方法[10]。夏易冲与陈斌讨论了局部度为1、k-1时码的特征[11]。杨瑞磻分析了一些有关三元本原长度码长的循环码的局部度[12]。本文主要利用循环码构造了码长8≤n≤50范围内达到C-M界的三元局部修复码，并着重讨论其中具有小局部度的码。这些码的研究对局部修复码在分布式存储系统上的应用具有重要的促进意义。

1 预备知识

令F3={0,1,2}，F3上的码长为n, 维数为k,最小距离为d的线性码C记作[n,k,d]，若码的局部度为r，则记为[n,k,d;r]。

设Zn表示模n整数环，本文研究的循环码的码长满足gcd(n，3)=1。令循环码C=[n，k，d]，当码字写成多项式形式时，取g(x)为xn-1在Fq[x]中的首一因式，则C为环Rn=Fq[x]/(xn-1)中由g(x)生成的理想，并称g(x)为C的生成多项式，xn-1/g(x)为C的校验多项式[4]。

定义2[4]若x为整数且满足0≤x≤n，x模n的3-分圆陪集Cx定义为:

Cx={x,3x,32x,…,3l-1x}(modn)

(2)

式中：l是满足xql≡x(modn)的最小正整数,集合Cx中的最小元素称为代表元。

引理2[13](BCH界)令循环码C=[n，k，d]，若C的定义集T中存在δ长度的连续元素，则码的距离d≥δ+1。

2 三元循环最优局部修复码的构造

为构造达到界的最优局部修复码，首先需计算出相应码长的3-分圆陪集，通过分圆陪集的组合可以确定码的定义集从而确定循环码，最后通过分析该码及其对偶码，即可得到参数为[n,k,d;d⊥-1]以及[n,n-k,d⊥;d-1]的局部修复码。

相对而言，局部度越小，码的修复效率越高[15]，因此构造小局部度的码更有实用价值。根据引理1，为构造局部度为r的码，对偶距离d⊥=r+1，再参考BCH界，确定对偶码的定义集TD中连续整数的个数范围，即可有针对性地构造局部修复码。本文重点构造了局部度为1、2、3的3类小局部度的码，各对偶码定义集中的连续整数个数应不大于局部度r。

定理1对于三元循环码C=[n，k，d]，若码长n为偶数且满足gcd(n，3)=1，则当n≥8时存在以下2种局部度r=1的最优局部修复码:

3 三元循环最优局部修复码

本节主要构造了码长8≤n≤50范围内局部度r≤3的最优局部修复码，并通过对偶码定义集给出了具体的构造方法，同时也给出了其余达到C-M界的局部修复码。以下各表中带*号的码为前人用其他方法构造的局部修复码，由于循环码相较一般码在应用中更具优势，所以仍在此给出。参数为[16,3,10;1]、[8,3,5;2]、[13,4,7;2]、[26,4,17;2]、[13,6,6;3]、[40,6,24;3]的码已于文献[12]中得到。

3.1 r=1的最优局部修复码

当对偶码定义集中无连续整数时，可以构造对偶距离d⊥=2的码，在码长8≤n≤50范围内共得到39个最优局部修复码，其中满足定理1的码长有15种，见表1。

表1 r=1的最优局部修复码

3.2 r=2的最优局部修复码

当对偶码定义集中的连续整数个数不大于2时，可以构造对偶距离d⊥=3的码，进而构造了5个r=2的最优局部修复码，见表2。

表2 r=2的最优局部修复码

3.3 r=3的最优局部修复码

当对偶码定义集中的连续整数个数不大于3时，可以构造对偶距离d⊥=4的码，进而构造了15个r=3的最优局部修复码，见表3。

表3 r=3的最优局部修复码

3.4 r≥4的最优局部修复码

除了r≤3的码以外，还得到了以下30个最优局部修复码，见表4。

表4 r=4的最优局部修复码

本节所构造的几类码均达到了目前最为关注的C-M界，其中局部度r≤3的码具有较高的修复效率，可进一步考虑其实用价值，局部度r≥4的码则主要是对结果的完善。

4 结语

本文利用定义集合设计三元循环码的对偶距离，构造了码长在8≤n≤50范围内达到C-M界的最优局部修复码，尤其是构造了一批具有较大实用价值的小局部度的码。本文的方法与结论为深入研究三元局部修复码提供了依据，今后会进一步研究如何基于拟循环码来构造局部修复码。