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

2020-09-07郑尤良李瑞虎吕京杰

空军工程大学学报 2020年4期

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

(空军工程大学基础部，西安，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]中得到。