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

局部修复码(Locally Repairable Codes)是一种能为分布式存储系统提供信息修复能力的新型纠删码。针对目前三元域上局部修复码的研究尚不充分的情况,给出了利用循环码构造局部修复码的一般方法。首先从循环码的码长出发,计算出对应的3-分圆陪集,然后通过分圆陪集的组合确定各循环码的定义集从而确定码的距离和局部度,进而构造了码长8≤n≤50范围内达到Cadambe-Mazumdar(C-M)界的三元局部修复码。特别是通过定义集设计对偶距离,并利用BCH界筛选分圆陪集,构造了3种具有小局部度的最优局部修复码。这些研究结果进一步完善了三元局部修复码的相关构造理论。     

短码长的五元最优局部修复码

在分布式存储系统中,应用局部修复码(LRCs),可以提高修复错误节点的效率。研究了码长不大于31的五元最优LRCs,给出了4类五元最优LRCs及其具体刻画。首先利用距离最优的线性码和Simplex码等特殊码,构造了性能较好的LRCs的校验矩阵。对已得到的LRCs,通过矩阵变换、矩阵拼接和删截的方法,给出了其他LRCs。所构造的五元LRCs的最小距离为2≤d≤8和d=10,参数均达到了Singleton界。这些结果对于其他五元最优LRCs和一般域上最优LRCs的构造具有借鉴意义。     

短码长二元循环码的局部修复度

局部修复码是一种局部纠删编码,近年来在分布式存储系统中得到了广泛的应用。码的局部修复度为r指的是,码字的任一位发生删除错误时至多需要该码字的其他r位进行恢复。研究了r≤3的二元循环局部修复码的存在性与构造。基于循环码定义集理论,采用局部修复码的对偶码描述,依据码的参数制约关系,进行局部修复码的构造及参数优化。证明了r=1的任意码长二元循环码的存在性,构造了r=1且参数达到Griesmer界的局部修复码;给出了r=2和r=3的部分码长二元循环码存在性的判据,基于7≤n≤99的二元循环码分别构造了r=2和r=3的、参数优良的短码长局部修复码。研究结果对进一步研究循环码的局部修复度与其他参数的关系、构造参数优良的一般码长局部修复码具有借鉴作用。     

低维四元局部修复码的构造

在分布式存储系统中,当节点发生故障时,局部修复码能够提高修复效率.四元距离最优码易于实现,当给定码长和维数时,四元距离最优码的纠错能力优于二元距离最优码,但目前利用四元距离最优码构造四元局部修复码的研究存在很多空白.设四元距离最优码的维数2≤k≤4,由给定维数的四元Simplex码与MacDonald码以及少量距离最优码的生成矩阵,利用扩展、删除与并置等组合方法,设法构造出任意码长n≥k+1且局部度较小的四元局部修复码.确定出达到Singleton-Like界或Cadambe-Mazumdar界的四元局部修复码.证明除55个四元局部修复码外,其余的四元局部修复码都是局部度最优的.     

2类最优局部修复码的构造

局部修复码可以提高分布式存储系统中失效节点的修复效率,是分布式存储编码领域的研究热点。文章研究最优局部修复码的构造,利用二元常重量码构造了两类矩阵,并以这两类矩阵作为校验矩阵,构造了局部性为r、最小距离分别为d=5和d=6的两类最优局部修复码。     

五维三元最优线性码的局部度

局部修复码(Locally Repairable Code)中每一码字的任意位发生错误可通过读取此码字的其它若干位予以修复。在应用了局部修复码的分布式存储系统中,任意节点发生损坏时均可通过读取较小数量的其它节点对其进行修复,给出了一些可以达到较小局部修复度的码的生成矩阵的构造方法。通过对相应最优码参数的分析,采用删截、扩展,并置等方法构造出了五维三元最优码的生成矩阵,分析了生成矩阵列向量之间的线性相关关系后,得到了许多具有较小局部度的五维三元最优码。     

基于自对偶码的S-链构造

研究具有某种最优性质的码的存在性、结构和构造是编码研究的中心问题,为构造量子纠错码开始研究具有特定对偶距离的二元自正交码。研究了码长n满足12≤n≤20的二元不可分解自对偶码B12、D14、E16、F16、H18、I18、J20、K20、L20、M20和S20的两类子码,即对偶距离最优或对偶距离拟最优的子码,以及相应的S-链的构造。依据不可分解自对偶码的生成矩阵,利用组合方法构造出对偶距离为2、3和4的对偶距离最优或拟最优的子码生成矩阵。在此基础上研究了这些子码构成的子码链,以及由它们的对偶构成的S-链。最后,利用得到的S-链构造出好的量子纠错码,这些量子码都是给定码长和维数时距离达到最大值的量子码。     

五元域上LCD码的构造

基于最优线性码与射影几何理论,针对不同码长最优码的距离特性,研究了低维五元最优LCD码的构造。首先利用删截等方法构造了较小码长的三维和四维最优线性码以及最优LCD码;其次,借助部分已知矩阵和删截等方法构造了较大码长的三维和四维最优线性码以及最优LCD码;最后,利用已知最优LCD码和特殊码长最优自正交码构造了任意大码长的最优LCD码,完全解决了三维和四维最优LCD码的构造问题。这些LCD码的构造方法对于五元高维最优LCD码以及一般域上最优LCD码的研究具有重要的理论指导意义。     

自正交码的组合构造与应用

量子纠错码是量子计算和量子通信可靠运行的保障,构造具有很好参数的量子纠错码是重要的研究问题之一.用二元线性码构造量子码的方法有CSS(Calderbank-Shor-Steane)方法和Steane方法,这两种方法都建立在如何构造给定对偶距离的自正交码上,研究了用组合方法构造二元自正交码问题.由已知对偶距离的二元自正交码链,用组合方法构造对偶距离为3、4、5和6的二元自正交码, 以及对偶距离为3、4、5和6的二元自正交码构成二元自正交码链的条件.在此基础上, 对每个满足47≤n≤70的 , 构造出参数为[n, n-s-t, 5][n, n-s, 3]和[n, n-u-v, 6][n, n-v, 4]的S-链.利用所得到的码链,由Steane构造法构造出距离为5和6的具有很好参数的量子纠错码,改进了前人得到的几个量子纠错码的参数.     

一类基于极图理论的局部修复编码的性质及构造

由于分布式存储系统大量使用廉价的磁盘构建,磁盘故障往往不可避免导致数据丢失.数据编码是一种防止数据丢失的必要容错机制.局部修复码与经典的最大距离可分(MDS)码相比,以一定的存储空间开销,能够有效提高数据修复的效率,降低网络带宽占用.为了降低该码的存储空间开销,本文研究以极图理论来描述该类编码.将存储节点与编码块抽象为二分图中的X、Y两类顶点,从而存储空间占用最小化等价于计算二分图中边数的极小值.这种求极值问题可以归结为Zarankiewicz问题.本文使用极值二分图对局部修复码进行建模与分析,并给出了相应的构造算法.     

关于码的拟复合的组合性质

引入码的拟复合的概念,并把码的复合的一系列性质推广到拟复合的情况,得到一些新的结果.特别关于拟复合码的完全性的结果,为码的完全化提供了一个新的工具.     

在微机上实现汉明码纠错的方法

本文讨论了纠错中的线性分组码以及它的生成矩阵、校验矩阵和伴随式,进而在微机上实现(7,4)码的编码和解码,并给出了流程框图。     

同步码的完全化构造方法

完全码体现为编码资源的充分利用,同时它又是一种代数结构的极大元·依据同步码的度进一步研究了同步码和前缀同步码的若干组合特性,从而给出了它们的完全化·对于同步码,首先确定了一个度为1的字,证明了以该字起首并以该字结尾的字的全体是一个子自由幺半群,基于该子自由幺半群的基,构造了同步码的完全化·至于前缀同步码,找出了一个具有某种特性的无框字,全体以该字结尾而不以码字起首的字的前缀根连同给定的码便是它的完全化·     

n次甚稀疏前缀码的完全化

主要依据前缀码的典型分解性质以及同步码的完全化,给出次为n的甚稀疏前缀码的完全化构造方法,从而解决一类特殊前缀码的完全化问题.     

用四元循环码构造的线性量子码

用模奇数n的4-分圆陪集和生成多项式刻划四元循环码,得到一般四元循环码的对偶码为自正交码的充要性判别准则,将前人关于自正交四元单根循环码和四元BCH码的对偶码为自正交判别准则推广到任意四元循环码,包括四元单根循环码和重根循环码.利用单根循环码与重根循环码关系,确定出所有能由短码长的四元循环码构造的线性量子码。     

内缀码的一个推广

考虑了内缀码在双缀码中的一个推广,即强双缀码,讨论了这类码及其子类的一些性质。特别地,证明了强双缀码的子集也是强双缀码。     

Hamming码和延长Hamming码的周期分布

Hamming码是一类特殊的线性码．该文对Hamming码和延长Hamming码的周期分布作进一步的分析，首次利用延长Hamming码是第1阶R—M码的对偶码，给出了延长Hamming码的周期分布的表达式．     

循环码谱码的一些性质

讨论了循环码的谱码的最小距离及重量分布,并且证明了当n≠1时,码长为n的循环码的谱码一定不是循环码。     

n次甚稀疏码的一个组合特性

讨论了n次甚稀疏码的组合特性,并给出了判断一个甚稀疏码次为n的充要条件.     

认证码的平衡化方法

引入一种全新的编码算法(称其为平衡化方法),证明了任意一个认证码(或系统认证码)都可以通过平衡化方法转化为一种新的认证码,即平衡认证码(或平衡系统认证码), 并依此得到了一般认证码在编码规则概率空间服从均匀分布时最大伪造概率的新下界.