三角形结合方案的最优局部修复码构造

图1 矩阵构造示意图

Fig.1 Diagram of matrix construction

可进一步构造行重为m、列重为p的正则矩阵.矩阵Φ_m_,_p中的块最终均能用Φ_l_,2(2<l≤m)、 ${Φ^{T}}_{v, 2}$ (2<v≤p)、单位矩阵及零矩阵表示.例如,由Φ_3,2、 ${Φ^{T}}_{3,2}$ 、单位矩阵及零矩阵可表示出Φ_{3, 3},即

Φ_{3, 3}= $[\begin{array}{l} Φ_{3,2} & 0 \\ I & {Φ^{T}}_{3,2} \end{array}]$

其中:Φ_3,2即为由三角形结合方案构造得到的行重为3、列重为2的关联矩阵.

构造2 由校验矩阵

H₂= $[\begin{array}{l} Φ_{m, p - 1} & 0 \\ I & {Φ^{T}}_{p, m - 1} \end{array}| I]$

定义的码C₄是信息符号,可以实现任意局部性r>2和任意可用性t>2的(n=(m+1)(m+2)… (m+p)/p!, k=m(m+1)…(m+p-1)/p!, r=m, t=p)_iBLRCs.

证明首先计算矩阵Φ_m_,_p的大小.由构造1可知Φ_m_,2的行数为m+1,列数为m(m+1)/2.由于矩阵 ${Φ^{T}}_{3, m - 1}$ 与Φ_m_{-1, 3}的行数及列数相同,当p=3时,为了计算方便,使用如下矩阵计算Φ_m_,3的行数和列数:

$[\begin{array}{l} Φ_{m, 2} & 0 \\ I & Φ_{m - 1,3} \end{array}]$ = $[\begin{array}{l} Φ_{m, 2} & 0 \\ I & |\bar{\begin{array}{l} Φ_{m - 1,2} & 0 \\ I & |\bar{\begin{array}{l} \frac{}{⋱} \\ |\bar{\begin{array}{l} Φ_{4,2} & 0 \\ I & |\bar{\begin{array}{l} Φ_{3,2} & 0 \\ I & Φ_{2,3} \end{array}} \end{array}} \end{array}} \end{array}} \end{array}]$

根据矩阵形式,Φ_m_,3的行数可表示为

m+1+ $\frac{m (m + 1)}{2}$ = $\frac{(m + 1) (m + 2)}{2}$

Φ_m_,3的列数可表示为

$\frac{(m + 1) m}{2}$ + $\frac{m (m - 1)}{2}$ +…+ $\frac{4 \times 3}{2}$ +4= $\frac{m (m + 1) (m + 2)}{2 \times 3}$

Φ_m_,4的行数可表示为

$\frac{(m + 1) (m + 2)}{2}$ + $\frac{m (m + 1) (m + 2)}{6}$ = $\frac{(m + 1) (m + 2) (m + 3)}{2 \times 3}$

Φ_m_,4的列数可表示为

$\frac{(m + 2) (m + 1) m}{6}$ + $\frac{(m + 1) m (m - 1)}{6}$ +…+ $\frac{5 \times 4 \times 3}{6}$ +5= $\frac{m (m + 1) (m + 2) (m + 3)}{2 \times 3 \times 4}$

当p>2时,假设Φ_m_,_p的行数为(m+1)(m+2)…(m+p-1)/(p-1)!,Φ_m_,_p的列数为m(m+1)…(m+p-1)/p!.由于矩阵 ${Φ^{T}}_{p + 1, m - 1}$ 与Φ_m_-1,_p₊₁的行数及列数相同,为了计算方便,使用如下矩阵计算Φ_m_,_p₊₁的行数和列数:

$[\begin{array}{l} Φ_{m, p} & 0 \\ I & Φ_{m - 1, p + 1} \end{array}]$ = $[\begin{array}{l} Φ_{m, p} & 0 \\ I & |\bar{\begin{array}{l} Φ_{m - 1, p} & 0 \\ I & |\bar{\begin{array}{l} \frac{}{⋱} \\ |\bar{\begin{array}{l} Φ_{4, p} & 0 \\ I & |\bar{\begin{array}{l} Φ_{3, p} & 0 \\ I & Φ_{2, p + 1} \end{array}} \end{array}} \end{array}} \end{array}} \end{array}]$

矩阵Φ_m_,_p₊₁的行数为

$\frac{(m + 1) (m + 2) \dots (m + p - 1)}{(p - 1)!}$ + $\frac{m (m + 1) \dots (m + p - 1)}{p!}$ = $\frac{(m + 1) (m + 2) \dots (m + p)}{p!}$

矩阵Φ_m_,_p₊₁的列数为

$\frac{m (m + 1) \dots (m + p - 1)}{p!}$ +

$\frac{(m - 1) m \dots (m + p - 2)}{p!}$ +…+

$\frac{3 \times 4 \dots (p + 2)}{p!}$ +p+2=

$\frac{m (m + 1) \dots (m + p)}{(p + 1)!}$

假设成立.

因此,当p>2时,Φ_m_,_p的行数为(m+1)(m+2)…(m+p-1)/(p-1)!,Φ_m_,_p的列数为m(m+1)…(m+p-1)/p!.则由校验矩阵H₂=[Φ_m_,_p|I]定义的码长

n=(m+1)(m+2)…(m+p)/p!

维度

k=m(m+1)…(m+p-1)/p!

当需要构造给定局部性r及可用性t的BLRCs时,可以基于三角形结合方案构造所需的列重为2的关联矩阵,由这些关联矩阵构造得到校验矩阵H₂=[Φ_r_,_t|I]进而构造BLRCs.

例2 以r=3, t=5为例构造BLRCs,由上述构造方法可知:

Φ_3,5= $[\begin{array}{l} Φ_{3, 4} & 0 \\ I & {Φ^{T}}_{5,2} \end{array}]$ = $[\begin{array}{l} \underline{\begin{array}{l} Φ_{3, 3} & 0 \\ I & {Φ^{T}}_{4,2} \end{array}}| & 0 \\ I & {Φ^{T}}_{5,2} \end{array}]$ =

$[\begin{array}{l} \underline{\begin{array}{l} \underline{\begin{array}{l} Φ_{3,2} & 0 \\ I & {Φ^{T}}_{3,2} \end{array}}| & 0 \\ I & {Φ^{T}}_{4,2} \end{array}}| & 0 \\ I & {Φ^{T}}_{5,2} \end{array}]$

其中,基于三角形结合方案构造关联矩阵的方法,矩阵Φ_3,2可以表示为

Φ_3,2= $[\begin{array}{l} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{array}]$

矩阵Φ_4,2、Φ_5,2也同样可以表示出来.可以看出,矩阵Φ_3,5中的块最终能用Φ_3,2、 $Φ_{3,2}^{T}$ 、 $Φ_{4,2}^{T}$ 、 $Φ_{5,2}^{T}$ 、单位矩阵及零矩阵表示.由校验矩阵H₂=[Φ_3,5|I]定义的码是信息符号可以实现局部性和可用性的(n=56, k=21, r=3, t=5)_i BLRCs.

3 性能分析

3.1 最小距离

定理6 由构造1中校验矩阵H₁构造得到的(n, k, r, 2)_aBLRCs的最小距离为d=3.

证明通过观察构造1中校验矩阵H₁可知,由于关联矩阵M的列重为2,且关联矩阵M的右边是一个单位矩阵,所以校验矩阵H₁中存在线性相关的3列.因此,构造得到的LRCs的最小距离d≤3.另一方面,从校验矩阵中任取两列,若两列都来自关联矩阵M或两列都来自单位矩阵I₍_m₊₁₎,显然它们线性无关;若一列来自关联矩阵M,另一列来自单位矩阵I₍_m₊₁₎,由于列重不同,它们必然线性无关.因此,构造得到的BLRCs的最小距离d≥3.综上可知,构造1构造的BLRCs的最小距离为d=3.

定理7 由构造2中校验矩阵H₂构造得到的信息符号可以实现任意局部性r>2和任意可用性t>2的(n, k, r, t)_iBLRCs是最小距离最优的BLRCs,且码的最小距离d=t+1.

证明由构造2中的校验矩阵H₂可知,矩阵Φ_m_,_p的列重为p,且矩阵Φ_m_,_p的右边是一个单位矩阵,可知从矩阵Φ_m_,_p中任选一列是单位阵中p列的线性组合,即校验矩阵H₂中存在线性相关的p+1列.因此,由校验矩阵H₂构造得到的BLRCs的最小距离d≤p+1.另一方面,根据矩阵Φ_m_,_p的形式可知,矩阵Φ_m_,_p的行重为m,列重为p,每列“1”元素所在p行中任意两行的支撑集只在该元素处相交,因此每个信息符号的修复局部性为m且具有p个不相交的修复集.根据定理1,最小距离应满足d≥p+1.综上所述,可知由校验矩阵H₂构造所得的BLRCs的最小距离d=p+1.

又因为由校验矩阵H₂构造的BLRCs的参数满足

n=(m+1)(m+2)…(m+p)/p!
k=m(m+1)…(m+p-1)/p!
r=m, t=p

将这些参数代入式(3),可得:

$\begin{array}{l} d \leqslant n-k-\left\lceil\frac{k t}{r}\right\rceil+t+1= \\ \frac{(m+1)(m+2) \cdots(m+p)}{p!}- \\ \frac{m(m+1) \cdots(m+p-1)}{p!}- \\ \left\lceil\frac{m(m+1) \cdots(m+p-1)}{p!} \frac{p}{m}\right\rceil+p+1=p+1 \end{array}$

因为p=t,所以构造出的BLRCs的最小距离d=t+1,且达到了式(3)中的最小距离边界,即该码是最小距离最优的BLRCs,证毕.

3.2 构造参数分析

由表1可知,当可用性t=2时,有

$\frac{r}{r + 2}$ > ${(\frac{r}{r + 1})}^{2}$

表1 构造1参数比较分析

Tab.1 Comparative analysis of parameters of Construction 1

构造方式	构造参数	最小距离	相对距离
构造1构造的BLRCs	n= $\frac{(r + 1) (r + 2)}{2}$ , k= $\frac{r (r + 1)}{2}$ , r,t=2	d_min=3	$\frac{6}{(r + 1) (r + 2)}$
基于近正则图构造的BLRCs^[18]	$n=k+\left\lceil\frac{2 k}{r}\right\rceil,\left\lceil\frac{2 k}{r}\right\rceil \geqslant r+2, t=2$	d_min=3	$\frac{3}{k + \frac{2 k}{r}}$
基于单位矩阵变换构造的BLRCs^[21]	n=r²+2r, k=r², r,t=2	d_min=3	$\frac{3}{r (r + 2)}$
基于直积码构造的BLRCs^[12](t=2)	n=(r+1)², k=r², r,t=2	d_min=4	$\frac{4}{{(r + 1)}^{2}}$

新窗口打开| 下载CSV

即由构造1构造的BLRCs的码率高于基于直积码构造的BLRCs的码率.虽然基于直积码构造的BLRCs 的最小距离大于构造1构造的BLRCs最小距离,但当局部性r>1时,由于

$\frac{6}{(r + 1) (r + 2)}$ > $\frac{4}{{(r + 1)}^{2}}$

即构造1构造的BLRCs的相对距离大于基于直积码构造的BLRCs的相对距离.当r|2k且2k=r(r+2)时,基于近正则图构造的BLRCs的相对距离

$\frac{6}{{(r + 2)}^{2}}$ < $\frac{6}{(r + 1) (r + 2)}$

即基于近正则图构造的BLRCs的相对距离小于构造1构造的BLRCs.构造1构造的BLRCs与基于单位矩阵变换构造的BLRCs能够达到相同的最小距离和码率,但是当局部性r取相同值并且r>1时,可知其相对距离

$\frac{6}{(r + 1) (r + 2)}$ > $\frac{3}{r (r + 2)}$

即构造1构造的BLRCs的相对距离大于基于单位矩阵变换构造的BLRCs.

图2给出了构造1构造的BLRCs、基于近正则图、基于直积码构造的BLRCs的码率R随局部性r变化曲线以及Prakash等^[18]提出的码率上界曲线.可以看出,当可用性t=2时,随着局部性r的增大,码率同时呈增大的趋势;当局部性r取相同值时,构造1构造的BLRCs的码率高于基于直积码构造的BLRCs;当局部性r取奇数时,构造1构造的BLRCs 的码率高于基于近正则图构造的BLRCs.此外,构造1构造的BLRCs的码率R=r/(r+2),达到了Prakash等^[18]提出的码率上界.

图2

图2 可用性t=2时码率随局部性的变化

Fig.2 Code rate versus locality at availabity t=2

由于推论1仅能构造局部性r=2的BLRCs,将其与基于单纯形码构造的BLRCs以及基于直积码构造的BLRCs进行比较.由表2可知,当基于直积码构造的BLRCs的局部性取为(2,t)且t>1时,有

$\frac{2}{2 + t}$ > ${(\frac{2}{3})}^{t}$

表2 推论1参数比较分析

Tab.2 Comparative analysis of parameters of Corollary 1

构造方式	构造参数	最小距离	相对距离
推论1构造的BLRCs	n= $\frac{(t + 1) (t + 2)}{2}$ , k=t+1, r=2,t	d_min=t+1	$\frac{2}{t + 2}$
基于单纯形码构造的BLRCs^[22]	n=2^m-1, k=m, r=2, t=2^m^-1-1	d_min=t+1	$\frac{t + 1}{2 t + 1}$
基于直积码构造的BLRCs^[12] (r = 2)	n=3^t, k=2^t, r=2,t	d_min=2^t	${(\frac{2}{3})}^{t}$

新窗口打开| 下载CSV

即由推论1得到的BLRCs的码率高于基于直积码构造的BLRCs.此外,由推论1得到的BLRCs的相对距离也大于基于直积码构造的BLRCs.基于单纯形码仅能构造可用性t=2^m^-1-1的BLRCs,限制了可用性的参数选择,而基于推论1可以构造具有任意可用性的BLRCs.

图3给出了局部性r=2时,3种码的码率R随可用性t变化曲线以及Tamo等^[12]提出的码率上界曲线.可以看出,当局部性r一定,随着可用性t的增大,码率同时呈减小的趋势;当可用性t取相同值时,推论1构造的BLRCs的码率高于基于直积码构造的BLRCs.虽然基于单纯形码构造的BLRCs的码率高于推论1构造的BLRCs,但是其可用性t具有较大的参数限制,推论1构造的BLRCs的参数选择更加灵活.

图3

图3 局部性r=2时,码率随可用性的变化

Fig.3 Code rate versus availability at locality r=2

由构造2可以构造任意局部性r>2和可用性t>2的BLRCs,将其与基于迹函数构造的BLRCs、基于超图构造的BLRCs、基于阵列LDPC码构造的BLRCs以及基于直积码构造的BLRCs进行比较.由表3可知,将码的局部性都取为(r,t),当t>2时,可知

${(1 + \frac{1}{r})}^{t}$ >1+ $\frac{t}{r}$

表3 构造2构造参数比较分析

Tab.3 Comparative analysis of parameters of Construction 2

构造方式	n	k	r	t	R
构造2构造的BLRCs	$\frac{(r + 1) (r + 2) \dots (r + t)}{t!}$	$\frac{r (r + 1) \dots (r + t - 1)}{t!}$	r>2	t>2	$\frac{r}{r + t}$
基于迹函数构造的BLRCs^[13]	2^m-1	2^m^-1-1	m-1	m	$\frac{2^{r} - 1}{2^{r + 1} - 1}$
基于超图构造的BLRCs^[16]	v+ $\frac{1}{r}$ vt	v	v≥t(r-1)+1, r\|vt		$\frac{r}{r + t}$
基于阵列LDPC码构造的BLRCs^[14]	r²+rt+1	r²	r(奇素数)	t(偶数)	$\frac{r^{2}}{r^{2} + r t + 1}$
基于直积码构造的BLRCs^[12]	(r+1)^t	r^t	r	t	${(\frac{r}{r + 1})}^{t}$

新窗口打开| 下载CSV

因此基于直积码构造的BLRCs的码率

${(\frac{r}{r + 1})}^{t}$ = $\frac{1}{{(\frac{r + 1}{r})}^{t}}$ < $\frac{1}{1 + \frac{t}{r}}$ = $\frac{r}{r + t}$

经分析可知,构造2构造的BLRCs的码率总高于基于直积码构造的BLRCs.由于

$\frac{r}{r + t}$ > $\frac{r^{2}}{r^{2} + r t + 1}$

即构造2构造的BLRCs的码率总高于基于阵列LDPC码构造的BLRCs.基于迹函数构造出的BLRCs 需要满足可用性t=r+1,只能构造特定参数的BLRCs,具有较大的参数限制,并且仅能构造码率 $\frac{2^{r} - 1}{2^{r + 1} - 1}$ < $\frac{1}{2}$ 的BLRCs.基于超图构造的BLRCs与构造2构造的BLRCs码率相同,但是超图存在的必要条件是超图的顶点数v≥t(r-1)+1并且r|vt,基于超图构造出的BLRCs具有极大的参数限制,主要针对特定参数的系统.

图4所示为当局部性r=11时,构造2构造的BLRCs 和几种典型BLRCs的码率随可用性的变化曲线,以及Tamo等^[12]提出的码率上界曲线.当局部性r一定,随着可用性t的增加,码率降低.当可用性t取相同值时,构造2构造的BLRCs的码率尽管没有达到Tamo等^[12]提出的码率上界,但高于基于直积码构造的BLRCs的码率.此外,当局部性 r=11时,基于阵列LDPC码仅能构造可用性t取偶数的BLRCs,具有一定的参数限制.基于迹函数构造的BLRCs的码率略高于构造2构造的 BLRCs,但是当局部性r=11时,基于迹函数仅能构造可用性 t=12的BLRCs,参数选择不够灵活.

图4

图4 局部性r=11时码率随可用性的变化

Fig.4 Code rate versus availability at locality r=11

当可用性t=4时,码率随局部性的变化曲线以及Tamo等^[12]提出的码率上界曲线如图5所示.随着局部性r的增大,码率同时呈增大的趋势;当局部性r取相同值时,构造2构造的BLRCs的码率仍高于基于直积码构造的BLRCs.此外,基于迹函数构造的BLRCs的码率高于构造2构造的BLRCs,但是当可用性t=4时,基于迹函数仅能构造局部性 r=3的BLRCs,基于阵列LDPC码仅能构造局部性r取奇素数的BLRCs,具有一定的参数限制且码率略低于构造2构造的BLRCs.

图5

图5 可用性t=4时码率随局部性的变化

Fig.5 Code rate versus locality at availabity t=4

4 结语

局部修复码能够有效实现分布式存储系统对海量数据的高可靠、高效率存储.提出基于三角形结合方案及其扩展的BLRCs构造方法,可以得到具有任意(r,t)局部性BLRCs.运用三角形结合方案的结合关系,基于校验矩阵构造可用性t=2的BLRCs,进一步基于生成矩阵构造局部性r=2的BLRCs;为了使BLRCs的参数选择更加灵活,对基于三角形结合方案构造的BLRCs进行扩展,进一步构造能够实现任意局部性r>2和任意可用性t>2的BLRCs.构造的具有(r,2)局部性的BLRCs达到了最优码率界;构造的具有任意局部性r>2和可用性 t>2的BLRCs达到了最优最小距离界.分析表明,与基于近正则图构造的BLRCs以及基于直积码构造的BLRCs等相比,本文构造的BLRCs在码率上表现更优且参数选择更灵活.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

FANG

W J

, CHEN

, XIA

S T

, et al.

Singleton-optimal LRCs and perfect LRCs via cyclic codes

[C]// 2021 IEEE International Symposium on Information Theory. Melbourne, Australia: IEEE, 2021: 3261-3266.

[2]

YAVARI

, ESMAEILI

Locally repairable codes: Joint sequential-parallel repair for multiple node failures

[J]. IEEE Transactions on Information Theory, 2020, 66(1): 222-232.

[3]

PAPAILIOPOULOS

D S

, DIMAKIS

A G

Locally repairable codes

[J]. IEEE Transactions on Information Theory, 2014, 60(10): 5843-5855.

[4]

WANG

A Y

, ZHANG

Z F

, LIN

D D

Bounds for binary linear locally repairable codes via a sphere-packing approach

[J]. IEEE Transactions on Information Theory, 2019, 65(7): 4167-4179.

[5]

GOPALAN

, HUANG

, SIMITCI

, et al.

On the locality of codeword symbols

[J]. IEEE Transactions on Information Theory, 2012, 58(11): 6925-6934.

[6]

LUO

, XING

C P

, YUAN

Optimal locally repairable codes of distance 3 and 4 via cyclic codes

[J]. IEEE Transactions on Information Theory, 2019, 65(2): 1048-1053.

[7]

JIN

L F

Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes

[J]. IEEE Transactions on Information Theory, 2019, 65(8): 4658-4663.

[8]

HAO

, XIA

S T

, SHUM

K W

, et al.

Bounds and constructions of locally repairable codes: Parity-check matrix approach

[J]. IEEE Transactions on Information Theory, 2020, 66(12): 7465-7474.

[9]

, GUO

L B

, LI

R H

, et al.

On the locality of some optimal ternary codes with dimension 6

[C]// 2020 13th International Symposium on Computational Intelligence and Design. Hangzhou, China: IEEE, 2020: 155-158.

[10]

CAI

, CHENG

M Q

, FAN

C L

, et al.

Optimal locally repairable systematic codes based on packings

[J]. IEEE Transactions on Communications, 2019, 67(1): 39-49.

[11]

RAWAT

A S

, PAPAILIOPOULOS

D S

, DIMAKIS

A G

, et al.

Locality and availability in distributed storage

[J]. IEEE Transactions on Information Theory, 2016, 62(8): 4481-4493.

[本文引用: 3]

[12]

TAMO

, BARG

Bounds on locally recoverable codes with multiple recovering sets

[C]// 2014 IEEE International Symposium on Information Theory. Honolulu, USA: IEEE, 2014: 691-695.

[本文引用: 9]

[13]

WANG

A Y

, ZHANG

Z F

, LIN

D D

Two classes of (r, t)-locally repairable codes

[C]// 2016 IEEE International Symposium on Information Theory. Barcelona, Spain:IEEE, 2016: 445-449.

[本文引用: 3]

[14]

HAO

, XIA

S T

, CHEN

On the single-parity locally repairable codes with availability

[C]// 2016 IEEE/CIC International Conference on Communications in China. Chengdu, China: IEEE, 2016: 1-4.

[15]

BALAJI

S B

, KUMAR

P V

Bounds on the rate and minimum distance of codes with availability

[C]// 2017 IEEE International Symposium on Information Theory. Aachen, Germany: IEEE, 2017: 3155-3159.

[本文引用: 4]

[16]

KIM

J H

, SONG

H Y

Hypergraph-based binary locally repairable codes with availability

[J]. IEEE Communications Letters, 2017, 21(11): 2332-2335.

[17]

TAN

, ZHOU

Z C

, SIDORENKO

, et al.

Two classes of optimal LRCs with information (r, t)-locality

[J]. Designs, Codes and Cryptography, 2020, 88(9): 1741-1757.

[18]

PRAKASH

, LALITHA

, BALAJI

S B

, et al.

Codes with locality for two erasures

[J]. IEEE Transactions on Information Theory, 2019, 65(12): 7771-7789.

[本文引用: 4]

[19]

BALAJI

S B

, PRASANTH

K P

, KUMAR

P V

Binary codes with locality for multiple erasures having short block length

[C]// 2016 IEEE International Symposium on Information Theory. Barcelona, Spain:IEEE, 2016: 655-659.

[本文引用: 3]

[20]

BAILEY

Association schemes: Designed experiments, algebra, and combinatorics[M]. Cambridge: Cambridge University Press, 2004.

[21]

WANG

, SHEN

K Q

, LIU

X Y

, et al.

Construction of binary locally repairable codes with optimal distance and code rate

[J]. IEEE Communications Letters, 2021, 25(7): 2109-2113.

[22]

WANG

A Y

, ZHANG

Z F

, LIU

M L

Achieving arbitrary locality and availability in binary codes

[C]// 2015 IEEE International Symposium on Information Theory. Hong Kong, China: IEEE, 2015: 1866-1870.