四元域上最优局部可修复码的分类

A classification for optimal quaternary locally repairable codes

近年来,为了提高分布式存储系统的容错性和可靠性,编码学家们引入了几类新的编码方案,其中局部可修复码(locally repairable codes,LRC)起到了重要的作用.对于一个线性码,若它的一个码字符号能通过其他至多r个码字符号修复,则称其具有局部性参数r.码长为n、维数为k、局部性参数为r的LRC((n,k,r)-LRC),其极小距离d满足Singleton型界d≤n-k-[k/r]+2.自LRC被提出以来,有许多工作研究小域上达到Singleton型界的码类.本文从码的校验矩阵角度出发,利用组合设计和有限几何的工具,研究了达到Singleton型界的最优四元LRC.本文证明了在四元域上共有27类最优的LRC,并且给出了这些最优码的构造.不仅如此,利用有限几何工具,本文还引入了判断最优LRC存在的新方法.

In recent years,several new types of codes have been introduced to provide the fault-tolerance and guarantee the system reliability in distributed storage systems,among which locally repairable codes(LRCs)have played an important role.A linear code is said to have locality r if each of its code symbols can be repaired by accessing at most r other code symbols.For an LRC with length n,dimension k,and locality r,its minimum distance d has been proved to satisfy the Singleton-like bound d≤n-k-[k/r]+2.Since then,many studies have been done for constructing LRCs meeting the Singleton-like bound over small fields.In this paper,we study quaternary LRCs meeting the Singleton-like bound through a parity-check matrix approach,using tools from combinatorial designs and finite geometry.We prove that there are 27 different classes of parameters for optimal quaternary LRCs.Moreover,for each class,explicit constructions of corresponding optimal quaternary LRCs are presented.In addition,using tools from finite geometry,we also introduce a new method to determine the existence of the optimal LRCs.