[00105409]最优局部修复码构造与分析

该项目为北京市自然科学基金资助青年项目（资助编号：4184093）。

该项目主要研究近些年来信息论编码领域的热门研究方向局部修复码(Locally Repairable Code,LRC)。极小距离达到著名类 Singleton 界的局部修复码在设计构建高效可靠的分布式存储系统数据冗余方案时具有重要应用。利用基于校验矩阵框架的研究方法研究两类重要的局部修复码：即(n,k,r)-LRC 和(n,k,r,δ)-LRC. 经过两年期的研究，该项目在最优局部修复码的构造和性质分析（重量分布和广义 Hamming 重量）等方面取得主要研究成果如下：

1. 对于最优局部修复码，有限域越小，编译码运算速度越快，所得编码更加实用：从理论上确定了 3 元域上最优(n, k, r, δ)-LRC 的所有参数，证明 3 元域上最优(n, k, r, δ)-LRC只有如下 6 类可能的参数，同时我们针对每类参数均给出了最优构造，从而基本在理论上解决了达到类 Singleton 界的 3 元最优(n, k, r, δ)-LRC 的构造问题。

2. 有限域的大小 q 确定后，往往希望最优局部修复码的极小距离 d 越大越好或码长 n 越长越好：在给定有限域大小 q 的情况下，申请人从理论上给出并证明了如下 q 元最优(n, k, r)-LRC 极小距离上界： d≤{█(■(q& r ∤ (k-1)),@■(2q& r | (k-1). ))┤ 对于最优 q 元 (n, k, r, δ)-LRC，其极小距离满足如下上界： d≤{█(■(q& r ∤ (k-1)),@■(δq& r | (k-1). ))┤有限域大小 q 固定后，给出了 q 元最优(n, k, r)-LRC 和(n, k, r, δ)-LRC 的码长上界。

3. 完善和解决了 2 元域上最优(n, k, r)-LRC 的构造问题，证明了 2 元域上最优 (n, k, r)-LRC 只存在 5 类参数，并在线性码等价意义下，给出全部最优构造，从而在理论上彻底解决了 2 元域上达到类 Singleton 界的最优(n, k, r)-LRC 构造问题。

4. 给出最优(n, k, r)-LRC 关于广义 Hamming 重量的广义 Singleton 类型的上界，并给出了高阶最优(n, k, r)-LRC 的码长一般上界。

5. 局部修复码在实用时，需要局部性参数较小且极小距离不用很大，着重研究了一类 d=5, r=2 的 q 元最优(n, k, r)-LRC. 证明在维数 k 为偶数时，极小距离为 5 的 q 元最优(n, k,2)-LRC 最大码长为 q 1，而在维数 k 为奇数时，最大码长可以达到 q 4. 同时，完全确定了维数 k 为偶数的最优 q 元最优(n, k, 2)-LRC 的下重量分布。令 B(u,v)=q^(2u v-2)-∑

_((t_1,t_2)∈D(u,v))▒〖C(u,v;t_1,t_2)B(t_1,t_2)〗 则 k 为偶数的最优 q 元最优(n, k, 2)-LRC 中，重量为 w (5≤w≤n) 的码字个数为： A_w=∑_(3u 2v=w, u,v≥0)▒〖(■(l@u))(■ (l-u@v)) 3^v B(u,v) 。