基于有限域结构的LRC码的存在性讨论

耿召民，胡万宝，钱 隆

（安庆师范大学 数理学院，安徽 安庆 246133）

大型云存储和分布式文件系统，如亚马逊弹性块存储（EBS）和谷歌文件系统（GoogleFS），由于其规模巨大，经常发生磁盘故障。为保护数据完整性，将编码理论用于对磁盘故障导致的丢失数据进行恢复。最简单的解决方案是跨越不同磁盘来直接复制数据包。然而，这种方案需要大量存储空间和较高运行速度，成本高昂。也有其他方案，例如将(n,k) 最大值的擦除码、最大距离可分离（MDS）码用作存储码。这些代码将k个信息符号编码为n个符号并将它们存储在n个磁盘上。与复制相比，这个方案有较大改进，冗余度有所提高。然而对于MDS代码而言，即便只有一个磁盘出现故障，系统也需要访问k个幸存磁盘以恢复丢失的符号，这使得修复过程成本高昂。

近年来，TAMO[1]和VLADUT[2]等提出一种有效改进修复的方法，它赋予码的局部性，此属性通过仅访问r来恢复故障符号远小于k个其他符号。具有局部性的擦除码也称为局部修复码（LRC），但其只用来擦除一次。在过去几年中，局部性的概念在多个方面得到了推广。例如，具有（r，δ）的LRC-位置允许通过读取r个其他符号来恢复集所遭受擦除的δ-1个符号，类似CAI[3]等的保证不相交的多个可修复集合的局部性研究。构造LRC码常用的数学工具为基于有限域结构[2,4-9]或代数函数域（代数曲线）的自同构群[2-3,7,10]。

本文讨论了用代数组合等方法来构造LRC码，其可以部分解决上述工具不能解决的问题，其中正文出现的符号Fq表示含q个元素的有限域。

1 局部恢复码

本文给出LRC码的正式定义如下。

定 义1[1]设C为Fq上的(n,k)线性码，若对于i∈{1,2,3,…,n}，存 在r个元素 的子集Ii⊆{1,2,3,…,n}{i}和一个函数φi→Fq，对于每个码字x∈C，都有xi=φi(xi1,xi2,xi3,…,xir)，其中i1,i2,i3,…,ir是Ii中的r个元素，则称C是(n,k,r)局部恢复码，简称(n,k,r)LRC 码。对于给定的坐标i∈{1,2,3,…,n}，集合Ii称作i的恢复集。

定理1[1]设C为Fq上(n,k,r)LRC码，则C的信息率满足

而C的最小距离满足

若（2）式等号成立，则称C为距离最优的(n,k,r)LRC码。

通常基于有限域来构造LRC码的方法有3种，首先介绍G-多项式，其是构造LRC码的关键。

定义2设A⊆Fq，A是元素个数为n的集合，r+1 能整除n，若一个多项式g(x)∈Fq[x]满足下列条件：（1）deg(g(x))=r+1，（2）存在关于集合[A]的划分，|Ai|=r+1，i=1,2,3,…,，使得g(x)在每个Ai上均为常数，即对∀α、β∈Ai有g(α)=g(β)，则称g(x)是关于划分A的G-多项式。

接下来介绍基于有限域结构构造G-多项式的常用方法。

构造1利用Fq的乘法子群进行构造。

构造2利用Fq(q=ps)的加法子群进行构造。

构造3利用Fq(q=ps)子域上的向量空间方法进行构造。

注在构造3中，由于H在Fpl的乘法运算下封闭，所以H可视为Fpl上的向量空间。

2 基于有限域结构的LRC码存在性讨论

上述三种构造方法可归纳为：假设在Fp的域扩张上构造一个G-多项式，其在元素个数为mpt的坐标数组的不相交子集上为常数，其中m与p互素，则，

（1）若t=0，可以使用满足pl≡1(modm)的某些扩域的乘法子群，如构造1；（2）若t＞0且m=1，可以使用加法子群，如构造2；（3）若t,m＞1且t为l的倍数，其中l为pl≡1(modm)的最小整数，则这种构造是通过结合域的加法和乘法结构来完成的，即向量空间法，如构造3。

具体说明如下：

（1）当t=0 时，m|H|=r+1=mpt=m，由pl≡1(modm)可得m|(pl-1)，即子群属于，故可以使用某些扩域Fpl的乘法子群；（2）当t＞0，m=1时，由m|H|=r+1=mpt可得H为的加法子群，其阶为pt，故可以使用构造2 的加法子群；（3）当t,m＞1且l|t时，有m|H|=mpt，而l为pl≡1(modm)的最小整数，其保证了H在Fpl的乘法运算下封闭。

在上述基于有限域结构的G-多项式3种构造方法中，并不能构造出任意想要的局部参数为r的LRC码。例如，当p=2 时，使用上述方法无法在域F2的任意扩张上构造局部参数为r=5 的码，因为r+1=5+1=6=3×2，所以m=3。又有l=2 为使得2l≡1(mod3)成立的最小整数，但t=1，2|/（lt不为l的倍数），则发现不满足上述构造方法的条件，也就是说无法使用上述方法在域F2的任意扩张上构造局部参数为r=5的码。

下面我们将讨论对于任意素数p，r的取值满足某些条件时，无法采用上述三种方法来构造出G-多项式，从而得不到想要的LRC码情况。

引理1对于给定素数p，当r满足时，（其中m＞1）上述三种方法不能构造出特征为p的有限域上局部参数为r的G-多项式。

证明因为r+1=mp，所以t=1。又因为p≡1(modm)且(m,p)=1，所以l≠1。从而可得l|/t，即不满足上述三种构造的条件，从而无法用上述方法构造G-多项式。

例1任意给定素数p，当r=p2+p-1时，由引理1可知，用上述三种方法无法构造出G-多项式。

在下文中，考虑使用代数组合等方法来讨论局部参数为r的LRC码存在条件。

3 具有局部参数r的LRC码存在的充分条件

对于给定的参数r，虽然无法用基于有限域的上述三种方法构造G-多项式，但仍可以通过其他方法构造。下面用组合代数的方法先得出G-多项式存在的充分条件，进而给出LRC码存在的条件。

定理2（充分条件）在有限域Fq上，对于正整数r，当qr时，G-多项式存在。

下面构造出一类LRC码，由引理1可知，这类码是不能用前面三种方法来构造。

4 结束语

本文主要通过代数组合等方法，对有限域上G-多项式的存在性进行了讨论，并介绍了对于任意的素数p，在有限域Fq上局部参数为r=p2+p-1的LRC码存在性。以后在本文基础上，可以考虑解决利用代数函数域或代数曲线上自同构群解决所不能解决的问题。