ランクエラー訂正コード

符号理論では、ランク符号（ガビドゥリン符号とも呼ばれる）は、ハミングではなくランクメトリック上の非バイナリ^[1] 線形 誤り訂正符号である。彼らは、複数のランダムランク誤りを検出して訂正できる符号を構築する体系的な方法について説明した。kシンボルワードを n シンボルワードに符号化して冗長性を追加することで、ランク符号はt =  ⌊ ( d  − 1) / 2 ⌋ までのランクの誤りを訂正できる。ここで、dは符号距離である。消失訂正符号としては、最大d − 1 個の既知の消失 を訂正できる。

ランク符号は、リード・ソロモン符号に似た有限体上の代数線形符号です。 ${\displaystyle GF(q^{N})}$

上のベクトルの階数は、 上の線形独立成分の最大数です。 上の 2 つのベクトル間の階数距離は、これらのベクトルの差の階数です。 ${\displaystyle GF(q^{N})}$${\displaystyle GF(q)}$${\displaystyle GF(q^{N})}$

ランクコードは、エラーベクトルのランクがt以下のすべてのエラーを修正します 。

を有限体上のn次元ベクトル空間とします。ここで は素数のべき乗で、 は正の整数です。 を体 上のベクトル空間としてのの基底とします。 ${\displaystyle X^{n}}$ ${\displaystyle GF\left({q^{N}}\right)}$${\displaystyle q}$${\displaystyle N}$${\displaystyle \left(u_{1},u_{2},\dots ,u_{N}\right)}$${\displaystyle u_{i}\in GF(q^{N})}$${\displaystyle GF\left({q^{N}}\right)}$${\displaystyle GF\left({q}\right)}$

すべての要素はとして表すことができます。したがって、上のすべてのベクトルは行列として表すことができます。 ${\displaystyle x_{i}\in GF\left({q^{N}}\right)}$${\displaystyle x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}}$${\displaystyle {\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)}$${\displaystyle GF\left({q^{N}}\right)}$

${\displaystyle {\vec {x}}=\left\|{\begin{array}{*{20}c}a_{1,1}&a_{1,2}&\ldots &a_{1,n}\\a_{2,1}&a_{2,2}&\ldots &a_{2,n}\\\ldots &\ldots &\ldots &\ldots \\a_{N,1}&a_{N,2}&\ldots &a_{N,n}\end{array}}\right\|}$

体上のベクトルの階数は、で表される体上の対応する行列の階数です 。 ${\displaystyle {\vec {x}}}$${\displaystyle GF\left({q^{N}}\right)}$${\displaystyle A\left({\vec {x}}\right)}$${\displaystyle GF\left({q}\right)}$${\displaystyle r\left({{\vec {x}};q}\right)}$

すべてのベクトルの集合は空間です。マップ) は 上のノルムとランク メトリックを定義します。 ${\displaystyle {\vec {x}}}$${\displaystyle X^{n}=A_{N}^{n}}$${\displaystyle {\vec {x}}\to r\left({\vec {x}};q\right)}$${\displaystyle X^{n}}$

${\displaystyle d\left({{\vec {x}};{\vec {y}}}\right)=r\left({{\vec {x}}-{\vec {y}};q}\right)}$

からのベクトルの集合は、コード距離 を持つコードと呼ばれます 。集合がのk次元部分空間も形成する場合、それは距離 を持つ線形 ( n , k )-コードと呼ばれます。このような線形ランク メトリック コードは、常に等式を伴うシングルトン境界を満たします。 ${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle X^{n}}$${\displaystyle d=\min d\left(x_{i},x_{j}\right)}$${\displaystyle X^{n}}$${\displaystyle d}$${\displaystyle d\leq n-k+1}$

ランクコードには、d  =  n  −  k + 1 の最大ランク距離(または MRD) コードであるいくつかの既知の構成があります 。構築が最も簡単なのは (一般化) Gabidulin コードとして知られており、最初に Delsarte (彼はこれをシングルトン システムと呼びました) によって発見され、後に Gabidulin ^[2] (および Kshevetskiy ^[3] )によって発見されました。

要素のフロベニウス乗を次のように 定義しましょう。${\displaystyle [i]}$${\displaystyle x\in GF(q^{N})}$

${\displaystyle x^{[i]}=x^{q^{i\mod N}}.\,}$

そして、上で線形独立なすべてのベクトル は、MRD ( n , k , d  =  n  −  k + 1) コードの生成行列を定義します 。 ${\displaystyle {\vec {g}}=(g_{1},g_{2},\dots ,g_{n}),~g_{i}\in GF(q^{N}),~n\leq N}$${\displaystyle GF(q)}$

${\displaystyle G=\left\|{\begin{array}{*{20}c}g_{1}&g_{2}&\dots &g_{n}\\g_{1}^{[m]}&g_{2}^{[m]}&\dots &g_{n}^{[m]}\\g_{1}^{[2m]}&g_{2}^{[2m]}&\dots &g_{n}^{[2m]}\\\dots &\dots &\dots &\dots \\g_{1}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\dots &g_{n}^{[(k-1)m]}\end{array}}\right\|,}$

どこ。 ${\displaystyle \gcd(m,N)=1}$

ランクコードに基づく公開鍵暗号システムにはいくつかの提案があるが、そのほとんどは安全ではないことが証明されている（例えば、Journal of Cryptology、2008年4月^[4]を参照）。

ランクコードは、ネットワークコーディングにおけるエラー訂正や消失訂正にも役立ちます。

• 線形コード
• リード・ソロモン誤り訂正
• ベルレカンプ・マッシーアルゴリズム
• ネットワークコーディング

• ガビドゥリン、エルンスト・M.（1985）「最大ランク距離を持つコードの理論」、情報伝達の問題、21（1）：1–12
• Kshevetskiy , Alexander; Gabidulin, Ernst M. (2005 年 9 月 4 ～ 9 日)。「ランクコードの新しい構築」。議事録。国際情報理論シンポジウム、2005 年。ISIT 2005。pp. 2105 ～ 2108。doi :10.1109/ISIT.2005.1523717。ISBN 978-0-7803-9151-2. S2CID  11679865。
• Gabidulin, Ernst M.; Pilipchuk, Nina I. (2003 年 6 月 29 日 – 7 月 4 日)。「ランク コードによる消失訂正の新しい方法」IEEE 国際情報理論シンポジウム、2003 年。議事録。p. 423。doi : 10.1109 / ISIT.2003.1228440。ISBN 978-0-7803-7728-8.S2CID 122552232  。

• ランクメトリックコーデックのMATLAB実装