0 概述

编码理论是一个重要的数学分支, 在大数据和云存储系统的发展中, 分布式存储技术起到了重要作用, 因此, 应用于此的局部修复码^[1]被研究者提出。局部修复码是一类特殊的纠删码, 其码字的任一信息位发生错误都可通过访问其他固定数量的信息位进行恢复。如果分布式存储系统的某一节点发生损坏, 则该节点存储的信息可立即通过读取其他不超过r个相关节点予以修复, r即被称为码的局部修复度^[2]。在现有的分布式存储系统中, 评估一个编码方案性能主要可以从以下3个方面考量^[3-4]:首先是修复过程中传输的数据量, 称为修复带宽, 文献[5]对其进行研究并得到一个界, 将符合此界的码称作再生码; 其次是单个节点修复过程中存储系统读取的数据量, 称为磁盘读写量, 文献[6-7]对此进行了研究; 最后是修复任意节点错误所需要访问的其他节点数量, 称为码的局部修复度。本文主要通过代数方法, 由部分已知的最优码得到五元域上所有最优码, 并在此基础上分析得到五元域上局部修复度尽可能小的码。

1 预备知识

定义1  设F₅={0, 1, 2, 3, 4}, F₅ⁿ为F₅上n维向量空间, 若C为F₅的k维子空间, 则称C为5元码长为n的k维线性码^[8]。C中每一个向量称为C的一个码字。若C中所有非零码字的最小Hamming重量为d, 则称d为C的最小距离, 记为C=[n, k, d]₅。

定义2  对于任意线性码C=[n, k, d]_q, 以C的任意一组基为行向量构成的矩阵G, 称为C的生成矩阵^[8]。

定义3  在线性码C=[n, k, d]_q中, 若C的任意码字中每一位都与其他至多r位线性相关, 则称C为局部修复码, 其局部修复度为r^[8]。

文献[9]指出可以通过判断一个线性码生成矩阵中列向量之间的线性相关关系来得出这个码的局部修复度。

定义4  Cadamb-Mazumdar(C-M)界^[10]

一个局部修复度为r的[n, k, d]₅码满足以下关系:

$ k \leqslant \min\limits_{t \in \mathbb{Z}^{+}}\left\{t r+k_{\mathrm{opt}}^{q}(n-t(r+1), d)\right\} $

其中, k_opt^q(n, d)是给定码长n、域q和d时可能达到的最大维数。更一般地, 包含可用度t的界可参考。

引理1  设一个长度为n的线性码的生成矩阵G=(g₁g₂…g_n), 若对于∀i∈{1, 2, …, n}, 设集合A_i⊆{1, 2, …, n}\{i}, g_i可被至多r个g_j线性表示(j∈A_i), 则矩阵G生成码的局部修复度为r^[9]。

定义5

1) 下文讨论的均为五元线性码, 令1_n=(1, 1, …, 1)_1×n, 0_n=(0, 0, …, 0)_1×n, 用N(a, b)表示集合({a, a+1, a+2, …, b})。

2) 将矩阵看作其中所有列向量的集合, 若A为一个矩阵, α为A中一个列向量, 则可记作α∈A, 用(A\α)表示在A中删除α后剩余列向量构成的矩阵, 用mA表示m个矩阵A并置而成的新矩阵($m \in \mathbb{Z}^{+} $)。

设$ k \in \mathbb{Z}^{+}$, 则k维首一列向量的个数为n_k=$ \frac{5^{k}-1}{4}$, 显然有n_k+1=5n_k+1。

令$\boldsymbol{S}_{2}=\left(\begin{array}{l}{101111} \\ {011234}\end{array}\right) $, 用递归的方式可得出k维Simplex码的生成矩阵S_k以及k维MacDonald码的生成矩阵M_k:

$ {\mathit{\boldsymbol{S}}_k} = \left( {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{S}}_{k - 1}}}&{{\mathit{\boldsymbol{0}}}_{k - 1}^{\rm{T}}}&{{{\mathit{\boldsymbol{S}}}_{k - 1}}}&{{{\mathit{\boldsymbol{S}}}_{k - 1}}}&{{{\mathit{\boldsymbol{S}}}_{k - 1}}}&{{{\mathit{\boldsymbol{S}}}_{k - 1}}}\\ {{{\mathit{\boldsymbol{0}}}_{{n_{k - 1}}}}}&1&{{{\mathit{\boldsymbol{1}}}_{{n_{k - 1}}}}}&{2 \cdot {{\mathit{\boldsymbol{1}}}_{{n_{k - 1}}}}}&{3 \cdot {{\mathit{\boldsymbol{1}}}_{{n_{k - 1}}}}}&{4 \cdot {{\mathit{\boldsymbol{1}}}_{{n_{k - 1}}}}} \end{array}} \right)\\ \boldsymbol{M}_{k}=\left(\begin{array}{ccccc}{{\bf 0}_{k-1}^{\mathrm{T}}} & {\boldsymbol{S}_{k-1}} & {\boldsymbol{S}_{k-1}} & {\boldsymbol{S}_{k-1}} & {\boldsymbol{S}_{k-1}} \\ {1} & {{\bf 1}_{n_{k-1}}} & {2 \cdot {\bf 1}_{n_{k-1}}} & {3 \cdot {\bf 1}_{n_{k-1}}} & {4 \cdot {\bf 1}_{n_{k-1}}}\end{array}\right) $

显然S_k与M_k生成r=2的最优[n_k, k, 5^k-1]₅码和最优[5^k-1, k, 4·5^k-2]₅码^[8]。为确定某些特殊形式最优码的局部度, 给出如下引理:

引理2  设G_{k, n}生成局修复部度为r的最优[n, k, d]码。若[n+1, k, d]码为最优, 则存在局部修复度为r的[n+1, k, d]最优码^[11]。

引理3

1) 设G_{k, n1}生成局部修复度为r₁的最优[n₁, k, d₁]码, G_{k, n2}生成局部修复度为r₂的最优[n₂, k, d₂]码, 则G_{k, n1+n2}=(G_{k, n1}|G_{k, n2})生成一个[n₁+n₂, k, d₁+d₂]码, 其局部修复度r≤min(r₁, r₂)。

2) 设[n, k, d]码与[2n, k, 2d]码均为最优, 则存在局部修复度为1的[2n, k, 2d]最优码^[11]。

引理4  若三维最优码的生成矩阵含有矩阵$\boldsymbol{O}=\left(\begin{array}{c|c}{0} & {101111} \\ {0} & {011234} \\ {1} & {l \cdot {\bf 1}_{6}}\end{array}\right) $的所有向量(l=1, 2, 3, 4), 则此码的局部修复度为2。

引理5  若三维最优码生成矩阵中任一重量为3的向量与其相邻的某一向量的线性组合重量为1, 则此码的局部修复度为2。

关于三维、四维五元最优码的存在性问题, 文献[12-14]中已给出了构造方法并解决。但在五元最优码的研究中, 局部修复度并没有得到重视, 并且对于一般给定参数的[n, k, d]₅最优码, 达到此参数的最优码往往有许多个且它们具有不同的r值。如何构造r值尽可能小的[n, k, d]₅最优码, 目前研究较少, 经过对现有文献的查阅和分析可知, 其中给出的最优码的r值多不理想。为此, 本文将从构造特殊码长的、具有较小r值的特殊最优码着手, 采用删截、扩展、并置等组合方法, 由一个码导出尽可能多的最优码, 再根据周期规律和达到Griesmer界的码的情况, 得到所有三维、四维最优码, 其中特殊码长的最优生成矩阵参考magma数据库^[15]。

2 三维最优码的局部修复度分析

当k=3、n=4时, 显然存在局部修复度r=3的最优[4, 3, 2]码。因此, 下文将对三维第一周期内最优线性码按照码长为5≤n≤31、32≤n≤63、n≥93 3种情况进行讨论。为简化分析过程, 本文通过分析最优码生成矩阵列向量的线性相关性确定其r值。

2.1 5≤n≤62时的三维最优码及局部修复度

码长满足5≤n≤62时的三维最优码及局部修复度分析如下:

1) 当n=4, 5, 6, 8, 12, 38, 43, 44, 48, 49时, 其最优码生成矩阵由magma数据库^[15]给出, 由r≤k可知其局部修复度为3。

2) $ \boldsymbol{G}_{3, 7}=\left(\begin{array}{l}{1001011} \\ {0100132} \\ {0011123}\end{array}\right)$中的列向量β₁~β₅重量不超过2, $\beta_{6}+\beta_{7}=\left(\begin{array}{l}{2} \\ {0} \\ {0}\end{array}\right) $, 满足引理5, 所以, G_{3, 7}生成最优码局部修复度为2。同理n∈[9, 11], [13, 16]时, 其最优码生成矩阵由magma数据库^[15]给出, 因此G_{3, n}生成最优码的局部修复度为2。

3) 当n=50时, G_{3, 50}=(G_{3, 25}|G_{3, 25}), 显然其生成r=1的最优码。

4) 当n∈[17, 30]时, G_{3, n}可由S₃从最后删去第1列~第14列得到。因此, G_{3, n}生成最优码的局部修复度为2。

5) 当n∈[32, 37], [39, 42], [45, 47]或[51, 62]时, G_{3, n}=(G_{3, n-31}|S₃)生成的最优码的局部修复度为2。

2.2 63≤n≤93时的三维最优码及局部修复度

当n=62+i(i=8, 13, 14, 18, 19, 20)时, G_{3, n}=(G_{3, n-31}|S₃)生成的最优码局部修复度为2。

对于其余的n, 则G_{3, n}=(G_n-62|S₃|S₃), 显然G_{3, n}生成的最优码局部修复度为1。

2.3 n≥94时的三维最优码及局部修复度

若n=31t+j₁(0≤j₁≤30), 则t≥3。令G_{3, n}=(G_{3, 31+j}|G_{3, 62})。因为G_{3, 62}=(S₃|S₃)所生成的最优码局部修复为1, 所以G_{3, n}生成的最优码局部修复度为1。

定理1  当k=3且n=31u+w时, w∈[1, 31]。

1) 当u=0且n=4, 5, 6, 8, 12时, G_{3, n}生成最优码的局部修复度为3, 其余的最优码局部修复度为2。

2) 当u=1且n=38, 43, 44, 48, 49时, G_{3, n}生成最优码的局部修复度为3;当n=50时, G_{3, n}生成最优码的局部修复度为1, 其余的最优码局部修复度为2。

3) 当u=2且n=70, 75, 76, 80, 81, 82时, G_{3, n}生成最优码的局部修复度为2, 其余的最优码局部修复度为1。

4) 当u≥3时, G_{3, n}生成最优码的局部修复度为1。

3 四维最优码的局部修复度分析

为解决四维最优码的局部修复度确定问题, 本文利用有限几何理论先构造特定码长的四维最优码, 然后再按照码长157≤n≤624以及n≥625分情况讨论四维最优码的构造和局部修复度。

3.1 5≤n≤156时的四维最优码及局部修复度

码长满足5≤n≤156时的四维最优码及局部修复度分析如下:

1) 当n∈[115, 156]时, 分2种情况讨论:

(1) G_{4, 156}=S₄和G_{4, 125}=${\mathit{\boldsymbol{S}}_4}\backslash \left( {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{S}}_3}}\\ {{\mathit{\boldsymbol{0}}_{1 \times 6}}} \end{array}} \right) $生成的最优码的局部修复度为2, 可由G_{4, 156}和G_{4, 125}分别删去前1至10列得n∈[115, 124], [145, 155]的r=2的最优码。

(2) 构造:

$ \boldsymbol{G}_{4, 138}=\boldsymbol{S}_{4} \backslash\left(\begin{array}{cc}{\boldsymbol{S}_{2}} &{\boldsymbol{0}_{2 \times 6} }&\boldsymbol{S}_{2} \\ {\boldsymbol{0}_{2 \times 6}} & {\boldsymbol{S}_{2}}&\boldsymbol{S}_{2}\end{array}\right)\\ \boldsymbol{G}_{4, 132}=\boldsymbol{S}_{4} \backslash\left(\begin{array}{c}{\boldsymbol{S}_{2} \boldsymbol{0}_{2 \times 6} \boldsymbol{S}_{2} \boldsymbol{S}_{2}} \\ {{\bf 0}_{2 \times 6} \boldsymbol{S}_{2} \boldsymbol{S}_{2} 2 \boldsymbol{S}_{2}}\end{array}\right)\\ \boldsymbol{G}_{4, 144}=\boldsymbol{S}_{4} \backslash\left(\begin{array}{cc}{\boldsymbol{S}_{2}} &\boldsymbol{0}_{2 \times 6} \\ {{\bf 0}_{2 \times 6}} & {\boldsymbol{S}_{2}}\end{array}\right) $

可由G_{4, 144}, G_{4, 138}和G_{4, 132}分别删去前第1列~第5列得n∈[126, 131], [133, 137], [139, 143]时r=2的最优码。

2) 当n=114, 108, 102, 95, 89, 83, 75, 70, 64, 58, 52, 46, 42, 32, 27, 16, 12时, 本文通过magma数据库^[16]得到最优码生成矩阵G_{4, n}, 对其进行首一化以后删列向量得到本周期内其余矩阵。

记删截G_{4, n}的最后1至p列得到的矩阵为G_{4, m}(n-p≤m≤n-1), G_{4, m}生成的最优码的r不变。

(1) 当n=114, 108, 95, 89, 83, 75, 70, 64, 58, 52, 12时, 令p=5, 则G_{4, m}生成r=2的最优码。

(2) 当n=52, 12时, p=5, 则G_{4, m}生成r=3的最优码。

(3) 当n=39, 102时, p=6, 则G_{4, m}生成r=2的最优码。

(4) 当n=27时, p=10, 则G_{4, m}生成r=2的最优码。

(5) 当n=32时, p=4, 则G_{4, m}生成r=3的最优码。

(6) 当n=46时, p=3, 则G_{4, m}生成r=2的最优码。

(7) 当n=42时, p=2, 则G_{4, m}生成r=2的最优码。

(8) 当n=16时, p=3, 则G_{4, m}生成r=3的最优码。

3) 当n=5, 6, 77时, G_{4, 5}、G_{4, 6}、G_{4, 77}如下所示。

$ \boldsymbol{G}_{4, 5}=\left(\begin{array}{c}{10001} \\ {01001} \\ {00101} \\ {00011}\end{array}\right), \boldsymbol{G}_{4, 6}=\left(\begin{array}{c}{100011} \\ {010012} \\ {001021} \\ {000132}\end{array}\right) $

$ \boldsymbol{G}_{4, 77}=\left(\begin{array}{c} {10001100101110011100111111101110111101101110011011111111111111111111111111111}\\ {01002000010341111211002322413021400014114001114101443223144122431113441113222}\\ {00100411140000100023234200143322021342313321200340433431313214131111443241112}\\ {00010013001002421231430041010402314230030421441213131113324232442134431142414} \end{array}\right) $

其中:G_{4, 5}、G_{4, 6}生成的最优码局部修复度为4;G_{4, 77}生成的最优码的局部修复度为2。

3.2 157≤n≤624时的四维最优码及局部修复度

在3.1节的基础上, 下面分6种类型具体给出最优码的生成矩阵并分析其局部修复度。

1) 若n∈[159, 161], [166, 167], [178, 181]或[284, 311], 构造G_{4, n}=(G_{4, n-155}|G_{4, 155})。G_{4, 155}含有矩阵O, 根据引理4, G_{4, n}生成r=2的最优码。

2) 若n∈[171, 177], [221, 227], [316, 331], 构造G_{4, n}=(G_{4, n-150}|G_{4, 150})。显然G_{4, 150}生成最优码的r=2, G_{4, n-150}生成最优码且r=2, 因此G_{4, n}生成r=2的最优码。

3) 若n=220或属于以下任意一个区间:[162, 165], [183, 189], [190, 202], [203, 219], [245, 283], [312, 315], [345, 377], [407, 432], [496, 500], [515, 531], 构造G_{4, n}=(G_{4, n-125}|G_{4, 125})。同理可得G_{4, n}生成r=2的最优码。

4) 若n∈[378, 406], 构造G_{4, n}=(G_{4, n-250}|G_{4, 250})。由引理3可得G_{4, 250}=(G_{4, 125}|G_{4, 125})生成最优码且r=1, 因此, G_{4, n}生成r=1的最优码。

5) 若n∈[433, 468], [469, 495], [501, 514], [532, 624], 构造G_{4, n}=(G_{4, n-312}|A_{4, 312})。G_{4, 312}=(G_{4, 156}|G_{4, 156})生成最优码且r=1, 因此G_{4, n}生成r=1的最优码。

6) 若n∈[239, 243], G_{4, n}为G_{4, 244}分别删去第1列~第5列得到。G_{4, 244}生成最优码且r=2, 可得G_{4, n}生成r=2的最优码。

利用文献[12]和Griesme界可逐条验证上述G_{4, n}生成的最优线性码。

3.3 n≥625时的四维最优码及局部修复度

n≥625时的四维最优码及局部修复度分析如下:

1) 若625≤n≤780, 令n₁=n-312, 则313≤n₁≤468, 构造G_{4, n}=(G_{4, n-312}|G_{4, 312})。显然, G_{4, n}生成最优码的局部修复度为1。

2) 若n≥781, 令n=156×t+n₂, 0≤n₂≤155, 则t≥5。构造G_{4, n}=(G_{4, 468+n2}|G_{4, 312})。显然, G_{4, n}生成最优码的局部修复度为1。

定理2  当k=4时, n=156h+v, v∈[1, 156]。

1) 当h=0且n∈[5, 6]时, G_{4, n}生成最优码的局部修复度为3;当n∈[7, 12], [13, 16], [28, 32]或[47, 52]时, G_{4, n}生成最优码的局部修复度为3;其余的最优码局部修复度为2。

2) 当h∈[1, 3]且n∈[378, 406], [433, 468], [469, 495], [501, 514], [532, 624]时, G_{4, n}生成最优码的局部修复度为1。其余的最优码局部修复度为2。

3) 当h≥4时, G_{4, n}生成最优码的局部修复度为1。

4 三维、四维最优码的局部修复度最优性分析

上文构造了维数k=3、k=4的最优码, 且由定义4可以验证构造的这些码多数达到了C-M界。表 1列出了未达到C-M界[n, k]₅的码长n和维数k。

5 结束语

本文利用部分已知五元域上三维、四维最优码的生成矩阵, 通过删截、扩展和并置等方法, 得到五元域上所有最优[n, 3, d]₅和[n, 4, d]₅码, 并分析所得生成矩阵列向量之间的线性相关关系, 构造码长n≥3、局部修复度r≤4的[n, 3, d]₅码和[n, 4, d]₅码。下一步将在所得最优码的基础上, 分析其线性自对偶性质, 在得到参数较优的LCD码后, 研究基于纠缠辅助的量子纠错码。