功能性修复再生码循环修复的一些性质

在我的开源的编码库中有一些判断功能性修复再生码(Regenerating Codes with Uncoded Repair)循环修复的一些性质,这里mark 一下。

前提:所有性质的判断都是针对通过随机线性码实现再生码的生成矩阵(generator matrix,GM),矩阵GM 有αn 行和c 列,相应的每个存储节点i 对应着矩阵GM 中连续的α 行,所以将每个节点的子矩阵(sub-GM)记作GMi 。每失效并修复一个节点时,相应的sub-GM 失效,并通过从d 个剩余sub-GMs 中获取dβ 个向量,随机线性组合为新的sub-GM。

修复判断 ——— NK_property(MDS 性质)

NK_property 在一次修复后判断是否修复成功,如果该性质满足则n 个节点中任意k 个可以重建出原始的数据。方法是n 个子矩阵sub-GM 中所有的k 个是否列满秩,如果是,则性质满足。复杂度为$C_n^k$

修复一步预判 ——— RP_property

RP_property 是该生成矩阵能够修复下一轮任意节点失效的性质,所以也叫做修复性质。如果第r 轮修复该性质满足,那么第r+1 轮修复的NK_property 满足。方法是检查n 个子矩阵中所有d 个子矩阵,是否存在从每d 个子矩阵中各取β 个向量,使得这d·β 个向量和d 个子矩阵中任意k-1 个矩阵的并集都列满秩(当然这d·β 个向量和k 个矩阵会有k·β 个向量的交集)。如果第r 轮该性质满足,则第r+1 轮的修复一定满足NK_property。复杂度为$C_{n-1}^{d-1}\alpha^{d}C_{d}^{k}$

修复多步预判 ——— CL_property

CL_property 是该生成矩阵能够向前循环修复α 轮的性质。如果第r 轮修复该性质满足,则第r+i(i ≤ α) 轮修复满足NK_property 。方法是在n 个子矩阵sub-GM 中选择出所有α 个子矩阵,将α 个子矩阵排列,第一个子矩阵删除所有α 行向量,第二个子矩阵删除α-1 行向量,最后一个子矩阵删除1 个行向量,GM 中所有剩下的向量列满秩。复杂度为$C_{n}^{\alpha}A^{\alpha}_{\alpha}\sum_{i=1}^{\alpha} C_{\alpha}^{i}$

其他性质 ———DB_property 和 AnyCols

DB_property 指的是任意d 个子矩阵sub-GM 中所有d×β 个向量的集合(每个子矩阵β 个) 都是线性无关的。

AnyCols 指的是任意c 行向量都是满秩的(或者秩不小于rank 且 rank≤c)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据