ローカルで回復可能なコード

局所的に回復可能な符号は、DSパパイリオプロスとAGディマキス^[1]によって最初に導入された誤り訂正符号の一種であり、分散ストレージシステムやクラウドストレージシステムに関連する応用のため、情報理論で広く研究されてきました。^{[2] [3] [4] [5]}

LRCは、 と、 とは異なるコードワードの他の座標の集合を入力として受け取り、を出力する関数が存在する線形コードです。 ${\displaystyle [n,k,d,r]_{q}}$ ${\displaystyle [n,k,d]_{q}}$ ${\displaystyle f_{i}}$ ${\displaystyle i}$ ${\displaystyle r}$ ${\displaystyle c=(c_{1},\ldots ,c_{n})\in C}$ ${\displaystyle c_{i}}$ ${\displaystyle c_{i}}$

概要

クラウドコンピューティングおよびストレージサービスへの需要の急増に伴い、分散ストレージシステムやクラウドストレージシステムにおける消失訂正符号（または単に消失訂正符号）の人気が高まっています。この傾向は、情報理論や符号理論の分野の研究者に、ストレージシステムでの使用に特化した符号の新たな側面を研究するきっかけを与えています。

LRCは、コードワード内のすべてのシンボルを復元するために、他のシンボルの限られたセットのみにアクセスする必要があるコードであることはよく知られています。この考え方は、分散ストレージシステムやクラウドストレージシステムにとって非常に重要です。なぜなら、最も一般的なエラーケースは、ストレージノードの1つが故障した場合（消失）だからです。主な目的は、ノードを復元するために、最小限の追加ストレージノードから可能な限り多くのデータを復元することです。したがって、ローカル回復可能コードは、このようなシステムにとって非常に重要です。

上記の説明から、LRC の以下の定義が導き出されます。長さ の - 局所的回復可能コード (LRC)は、情報シンボルから - シンボルのコードワードを生成するコードであり、コードワードの任意のシンボルに対して、そのシンボルの値を回復できる他のシンボルが最大で 個存在します。消去されたシンボル以外のシンボルにアクセスすることでコードワード全体を見つけることができるため、局所性パラメータはを満たします。さらに、最小距離を持つ局所的回復可能コードは、消失を回復できます。 ${\displaystyle [n,k,r]}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle 1\leq r\leq k}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle d-1}$

意味

を線形符号とする 。について、座標における消失を回復するために見なければならない他の座標の最小数を で表す。この数は、符号の-番目の座標の局所性と呼ばれる。符号の局所性は次のように定義される。${\displaystyle C}$ ${\displaystyle [n,k,d]_{q}}$ ${\displaystyle i\in \{1,\ldots ,n\}}$ ${\displaystyle r_{i}}$ ${\displaystyle i}$ ${\displaystyle r_{i}}$ ${\displaystyle i}$

${\displaystyle r=\max\{r_{i}\mid i\in \{1,\ldots ,n\}\}.}$

局所的に回復可能なコード( LRC) は、局所性を持つ線形コードです。 ${\displaystyle [n,k,d,r]_{q}}$ ${\displaystyle [n,k,d]_{q}}$ ${\displaystyle C\in \mathbb {F} _{q}^{n}}$ ${\displaystyle r}$

を -局所的に回復可能な符号とする。このとき、消去された成分は線形的に回復できる。^[6]すなわち、任意の に対して、符号の線形方程式の空間にはの形式（ ）の要素が含まれる。 ${\displaystyle C}$ ${\displaystyle [n,k,d]_{q}}$ ${\displaystyle i\in \{1,\ldots ,n\}}$ ${\displaystyle x_{i}=f(x_{i_{1}},\ldots ,x_{i_{r}})}$ ${\displaystyle i_{j}\neq i}$

最適なローカル回復可能コード

定理^[7]とを、サイズ の互いに素な局所集合を持つ -局所的に回復可能なコードとする。すると、${\displaystyle n=(r+1)s}$ ${\displaystyle C}$ ${\displaystyle [n,k,d]_{q}}$ ${\displaystyle s}$ ${\displaystyle r+1}$

${\displaystyle d\leq n-k-\left\lceil {\frac {k}{r}}\right\rceil +2.}$

-LRCは、最小距離が次式を満たす場合に最適であると言われる。${\displaystyle [n,k,d,r]_{q}}$ ${\displaystyle C}$ ${\displaystyle C}$

${\displaystyle d=n-k-\left\lceil {\frac {k}{r}}\right\rceil +2.}$

タモ・バーグ符号

を多項式とし、を正の整数とする。このとき、が ( , )-良好であるとは、 ${\displaystyle f\in \mathbb {F} _{q}[x]}$ ${\displaystyle \ell }$ ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle \ell }$

•学位を取得している、${\displaystyle f}$ ${\displaystyle r+1}$

•の異なる部分集合 が存在し、${\displaystyle A_{1},\ldots ,A_{\ell }}$ ${\displaystyle \mathbb {F} _{q}}$

– 任意の に対して、あるに対して、すなわち はに対して定数であり、${\displaystyle i\in \{1,\ldots ,\ell \}}$ ${\displaystyle f(A_{i})=\{t_{i}\}}$ ${\displaystyle t_{i}\in \mathbb {F} _{q}}$ ${\displaystyle f}$ ${\displaystyle A_{i}}$

– 、${\displaystyle \#A_{i}=r+1}$

–任意の。${\displaystyle A_{i}\cap A_{j}=\varnothing }$ ${\displaystyle i\neq j}$

{ } は の分割被覆であると言う。^[8]${\displaystyle A_{1},\ldots ,A_{\ell }}$ ${\displaystyle f}$

タモ・バーグ構造

タモ・バーグ構成は優れた多項式を利用している。^[9]

•上の-善多項式が分割被覆とともに与えられていると仮定します。${\displaystyle (r,\ell )}$ ${\displaystyle f(x)}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle i\in \{1,\ldots ,\ell \}}$

• を正の整数とします。${\displaystyle s\leq \ell -1}$

• 次の多項式のベクトル空間を考えてみましょう${\displaystyle \mathbb {F} _{q}}$ $${\displaystyle V=\left\{\sum _{i=0}^{s}g_{i}(x)f(x)^{i}:\deg(g_{i}(x))\leq \deg(f(x))-2\right\}.}$$

• させて。${\textstyle T=\bigcup _{i=1}^{\ell }A_{i}}$

• コードは -最適局所カバー可能コードであり、 はセット内のすべての点における の評価を表します。${\displaystyle \{\operatorname {ev} _{T}(g):g\in V\}}$ ${\displaystyle ((r+1)\ell ,(s+1)r,d,r)}$ ${\displaystyle \operatorname {ev} _{T}}$ ${\displaystyle g}$ ${\displaystyle T}$

タモ・バーグ符号のパラメータ

•長さ。長さは評価点の数です。 については集合が互いに素なので、コード の長さは です。${\displaystyle A_{i}}$ ${\displaystyle i\in \{1,\ldots ,\ell \}}$ ${\displaystyle |T|=(r+1)\ell }$

•次元。コードの次元は です（≤の場合）。各 は最大で次であり、次元のベクトル空間をカバーします。また、 の構築により、異なるが存在します。${\displaystyle (s+1)r}$ ${\displaystyle s}$ ${\displaystyle \ell -1}$ ${\displaystyle g_{i}}$ ${\displaystyle \deg(f(x))-2}$ ${\displaystyle \deg(f(x))-1=r}$ ${\displaystyle V}$ ${\displaystyle s+1}$ ${\displaystyle g_{i}}$

•距離。距離は（ただし ）という事実によって与えられ、得られたコードは最大次数のリード・ソロモンコードであるため、最小距離はに等しくなります。${\displaystyle V\subseteq \mathbb {F} _{q}[x]_{\leq k}}$ ${\displaystyle k=r+1-2+s(r+1)}$ ${\displaystyle k}$ ${\displaystyle (r+1)\ell -((r+1)-2+s(r+1))}$

•局所性。単一の成分を消去した後、 における評価（ ）は不明ですが、他のすべての評価は既知であるため、消去された成分を一意に決定するために必要な評価は最大で回となり、 の局所性が得られます。${\displaystyle a_{i}\in A_{i}}$ ${\displaystyle |A_{i}|=r+1}$ ${\displaystyle a\in A_{i}}$ ${\displaystyle r}$ ${\displaystyle r}$

これを確認するには、に制限して は、の要素の形式（つまり、は で定数であり、の は の次数が であるという事実）により、最大次数の多項式で記述できます。一方、 、 、 の評価により、次数の多項式が一意に決定されます。したがって、 を構築し、 で評価してを復元できます。${\displaystyle g}$ ${\displaystyle A_{j}}$ ${\displaystyle h}$ ${\displaystyle \deg(f(x))-2=r+1-2=r-1}$ ${\displaystyle V}$ ${\displaystyle f}$ ${\displaystyle A_{j}}$ ${\displaystyle g_{i}}$ ${\displaystyle \deg(f(x))-2}$ ${\displaystyle |A_{j}\backslash \{a_{j}\}|=r}$ ${\displaystyle r}$ ${\displaystyle r-1}$ ${\displaystyle h}$ ${\displaystyle a_{j}}$ ${\displaystyle g(a_{j})}$

タモ・バーグ構成の例

を用いて-LRCを構築します。この多項式の次数は5で、（、、、、 、、、、、、、、）において定数であることに注意してください。したがって、定義により、は 上で -good 多項式です。次に、この多項式を用いて、上で次元と長さの符号を構築します。この符号の局所性は4であり、最大4台の他のサーバに含まれる情報を参照することで、単一のサーバ障害を回復できます。 ${\displaystyle x^{5}\in \mathbb {F} _{41}[x]}$ ${\displaystyle [15,8,6,4]}$ ${\displaystyle A_{i}}$ ${\displaystyle i\in \{1,\ldots ,8\}}$ ${\displaystyle A_{1}=\{1,10,16,18,37\}}$ ${\displaystyle A_{2}=2A_{1}}$ ${\displaystyle A_{3}=3A_{1}}$ ${\displaystyle A_{4}=4A_{1}}$ ${\displaystyle A_{5}=5A_{1}}$ ${\displaystyle A_{6}=6A_{1}}$ ${\displaystyle A_{7}=11A_{1}}$ ${\displaystyle A_{8}=15A_{1}}$ ${\displaystyle A_{1}^{5}=\{1\}}$ ${\displaystyle A_{2}^{5}=\{32\}}$ ${\displaystyle A_{3}^{5}=\{38\}}$ ${\displaystyle A_{4}^{5}=\{40\}}$ ${\displaystyle A_{5}^{5}=\{9\}}$ ${\displaystyle A_{6}^{5}=\{27\}}$ ${\displaystyle A_{7}^{5}=\{3\}}$ ${\displaystyle A_{8}^{5}=\{14\}}$ ${\displaystyle x^{5}}$ ${\displaystyle (4,8)}$ ${\displaystyle \mathbb {F} _{41}}$ ${\displaystyle k=8}$ ${\displaystyle n=15}$ ${\displaystyle \mathbb {F} _{41}}$

次に、符号化多項式を定義します。ここで です。つまり、 です。 ${\displaystyle f_{a}(x)=\sum _{i=0}^{r-1}f_{i}(x)x^{i}}$ ${\displaystyle f_{i}(x)=\sum _{i=0}^{{\frac {k}{r}}-1}a_{i,j}g(x)^{j}}$ ${\displaystyle f_{a}(x)=}$ ${\displaystyle a_{0,0}+}$ ${\displaystyle a_{0,1}x^{5}+}$ ${\displaystyle a_{1,0}x+}$ ${\displaystyle a_{1,1}x^{6}+}$ ${\displaystyle a_{2,0}x^{2}+}$ ${\displaystyle a_{2,1}x^{7}+}$ ${\displaystyle a_{3,0}x^{3}+}$ ${\displaystyle a_{3,1}x^{8}}$

したがって、得られた符号化多項式を、符号化するデータを行ベクトル として用いることで使用できる。ベクトルを生成行列に掛け合わせることで、長さ15のメッセージベクトルに符号化する。${\displaystyle a=}$ ${\displaystyle (a_{0,0},a_{0,1},a_{1,0},a_{1,1},a_{2,0},a_{2,1},a_{3,0},a_{3,1})}$ ${\displaystyle m}$ ${\displaystyle c}$ ${\displaystyle m}$

${\displaystyle G={\begin{pmatrix}1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\1&1&1&1&1&32&32&32&32&32&38&38&38&38&38\\1&10&16&18&37&2&20&32&33&36&3&7&13&29&30\\1&10&16&18&37&23&25&40&31&4&32&20&2&36&33\\1&18&10&37&16&4&31&40&23&25&9&8&5&21&39\\1&18&10&37&16&5&8&9&39&21&14&17&26&19&6\\1&16&37&10&18&8&5&9&21&39&27&15&24&35&22\\1&16&37&10&18&10&37&1&16&18&1&37&10&18&16\end{pmatrix}}.}$

たとえば、情報ベクトル のエンコードにより、コードワードが生成されます。 ${\displaystyle m=(1,1,1,1,1,1,1,1)}$ ${\displaystyle c=mG=(8,8,5,9,21,3,36,31,32,12,2,20,37,33,21)}$

最適なLRCを構築したことに注意してください。したがって、シングルトン境界を用いると、このコードの距離は となります。したがって、他の8つの要素を調べるだけで、コードワードから任意の6つの消失を復元できます。 ${\displaystyle d=n-k-\left\lceil {\frac {k}{r}}\right\rceil +2=15-8-2+2=7}$

ローカルで回復可能なコードと可用性

コードが全シンボル局所性と可用性を持つとは、各コードシンボルが他のシンボルの互いに素な修復集合（各集合のサイズは最大でシンボル）から復元できる場合である。このようなコードは-LRCと呼ばれる。^[10]${\displaystyle C}$ ${\displaystyle r}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle r}$ ${\displaystyle (r,t)_{a}}$

定理局所性と可用性を持つ-LRCの最小距離は上限を満たす${\displaystyle [n,k,d]_{q}}$ ${\displaystyle r}$ ${\displaystyle t}$

${\displaystyle d\leq n-\sum _{i=0}^{t}\left\lfloor {\frac {k-1}{r^{i}}}\right\rfloor .}$

コードが体系的で、局所性と可用性がその情報シンボルにのみ適用される場合、そのコードは情報の局所性と可用性を持ち、-LRCと呼ばれる。^[11]${\displaystyle r}$ ${\displaystyle t}$ ${\displaystyle (r,t)_{i}}$

定理^[12]線形-LRCの最小距離は 上限を満たす${\displaystyle d}$ ${\displaystyle [n,k,d]_{q}}$ ${\displaystyle (r,t)_{i}}$

${\displaystyle d\leq n-k-\left\lceil {\frac {t(k-1)+1}{t(r-1)+1}}\right\rceil +2.}$

参考文献

1. Papailiopoulos, Dimitris S.; Dimakis, Alexandros G. (2012)、「局所的に修復可能なコード」、2012 IEEE International Symposium on Information Theory Proceedings、ケンブリッジ、マサチューセッツ州、米国: IEEE、pp.  2771– 2775、arXiv : 1206.3804、doi :10.1109/ISIT.2012.6284027、ISBN 978-1-4673-2579-0
2. Barg, A.; Tamo, I.; Vlăduţ, S. (2015)、「代数曲線上の局所的に回復可能な符号」、2015 IEEE 国際情報理論シンポジウム、香港、中国: IEEE、pp.  1252– 1256、arXiv : 1603.08876、doi :10.1109/ISIT.2015.7282656、ISBN 978-1-4673-7704-1
3. Cadambe, VR; Mazumdar, A. (2015)、「局所的に回復可能なコードのサイズの境界」、IEEE Transactions on Information Theory、61 (11)、IEEE: 5787– 5794、doi :10.1109/TIT.2015.2477406
4. Dukes, A.; Ferraguti, A.; Micheli, G. (2022)、「次数5までの良好な多項式の最適選択」、Designs, Codes and Cryptography、90 (6)、IEEE: 1427– 1436、arXiv : 2104.01434、doi :10.1007/s10623-022-01046-y
5. Haymaker, K.; Malmskog, B.; Matthews, G. (2022)曲線のファイバー積から得られる可用性t≥2の局所的に回復可能なコード、doi : 10.3934/amc.2018020
6. Papailiopoulos, Dimitris S.; Dimakis, Alexandros G. (2012)、「局所的に修復可能なコード」、2012 IEEE International Symposium on Information Theory、ケンブリッジ、マサチューセッツ州、米国、pp.  2771– 2775、arXiv : 1206.3804、doi :10.1109/ISIT.2012.6284027、ISBN 978-1-4673-2579-0
7. Cadambe, V.; Mazumdar, A. (2013)、「局所的に回復可能な符号のサイズの上限」、2013 International Symposium on Network Coding、カルガリー、アルバータ州、カナダ、pp.  1– 5、arXiv : 1308.3200、doi :10.1109/NetCod.2013.6570829、ISBN 978-1-4799-0823-3
8. Micheli, G. (2020)、「最適な局所的に回復可能なコードの構築」、IEEE Transactions on Information Theory、66 : 167–175、arXiv : 1806.11492、doi :10.1109/TIT.2019.2939464
9. Tamo, I.; Barg, A. (2014)、「最適な局所的回復可能符号のファミリー」、2014 IEEE 国際情報理論シンポジウム、ホノルル、ハワイ、米国、pp.  686– 690、doi :10.1109/ISIT.2014.6874920、ISBN 978-1-4799-5186-4
10. Huang, P.; Yaakobi, E.; Uchikawa, H.; Siegel, PH (2015)、「線形局所修復可能コードと可用性」、2015 IEEE International Symposium on Information Theory、香港、中国、pp.  1871– 1875、doi :10.1109/ISIT.2015.7282780、ISBN 978-1-4673-7704-1
11. Tamo, I.; Barg, A. (2014)、「多重回復集合を持つ局所回復可能符号の境界」、2014 IEEE 国際情報理論シンポジウム、ホノルル、ハワイ、米国、pp.  691– 695、arXiv : 1402.0916、doi :10.1109/ISIT.2014.6874921、ISBN 978-1-4799-5186-4
12. Wang, A.; Zhang, Z. (2014)、「多重消去耐性を持つ修復局所性」、IEEE Transactions on Information Theory、60 (11): 6979– 6987、arXiv : 1306.4774、doi :10.1109/TIT.2014.2351404