消去コード

符号理論において、消失訂正符号は、ビット誤りではなくビット消失を前提とした前方誤り訂正(FEC) 符号であり、 k個のシンボルのメッセージをn 個のシンボルのより長いメッセージ (コードワード) に変換し、元のメッセージをn個のシンボルのサブセットから復元できるようにします。分数r  =  k / nは、コードレートと呼ばれます。分数k'/k ( k'は復元に必要なシンボル数) は、受信効率と呼ばれます。復元アルゴリズムでは、 n 個のシンボルのうちどのシンボルが失われたかがわかっているものと想定されます。

消失訂正符号は1960年にアーヴィング・リードとギュスターヴ・ソロモンによって発明されました。 ^[1]

消失訂正符号にはさまざまな方式がある。最も一般的な消失訂正符号は リード・ソロモン符号、 低密度パリティ検査符号（LDPC符号）、 ターボ符号である。^[1]

2023年現在、現代のデータストレージシステムは、3つのアプローチのいずれかを使用して、データ損失なしでいくつかのディスクの完全な障害に耐えるように設計できます。^{[2] [3] [4]}

• レプリケーション
• レイド
• 消失訂正符号

技術的には RAID は消去コードの一種とみなすことができますが、^[5] 「RAID」は一般に単一のホスト コンピューター (単一障害点) に接続されたアレイに適用されますが、「消去コーディング」は一般に複数のホストを意味し、^[3]安価なサーバーの冗長アレイ(RAIS) と呼ばれることもあります。消去コードにより、これらのホストのいずれかが停止しても操作を続行できます。^{[4] [6]}

ブロックレベルのRAIDシステムと比較すると、オブジェクトストレージ消去符号化には、より回復力のあるいくつかの重要な違いがあります。^{[7] [8] [9] [10] [11]}

最適な消失訂正符号には、 n 個のコードワードシンボルのうちの任意のk個が元のメッセージを復元するのに十分であるという特性があります(つまり、最適な受信効率を持ちます)。最適な消失訂正符号は、最大距離分離符号(MDS 符号) です。

パリティ チェックは、 n  =  k + 1の特殊なケースです。k個の値 のセットからチェックサムが計算され、k 個のソース値に追加されます。 ${\displaystyle \{v_{i}\}_{1\leq i\leq k}}$

${\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}$

k  + 1 個の値のセットは、チェックサムに関して一貫性があります。これらの値の 1 つが消去された場合、残りの変数を合計することで簡単に回復できます。 ${\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}$${\displaystyle v_{e}}$

${\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}$

RAID 5はパリティチェック消去コードの広く使われているアプリケーションです。^[1]

k = 2の単純なケースでは 、2 つの元のシンボル間の線に沿って異なる点をサンプリングすることで冗長シンボルを作成できます。これは、err-mail と呼ばれる単純な例で示されます。

アリスは自分の電話番号（555629）をerr-mailを使って ボブに送りたい。err-mailは電子メールと同じように機能するが、

1. 郵便物の約半分が紛失します。
2. 5 文字を超えるメッセージは無効です。
3. 非常に高価です（航空便と同様）。

アリスは、ボブに送信したメッセージを確認するように依頼する代わりに、次のスキームを考案します。

1. 彼女は自分の電話番号を 2 つの部分(a = 555、b = 629)に分割し、2 つのメッセージ (「A=555」と「B=629」) をボブに送信します。
2. 彼女は、かつ となるような線形関数（この場合は ）を構築します。${\displaystyle f(i)=a+(ba)(i-1)}$${\displaystyle f(i)=555+74(i-1)}$${\displaystyle f(1)=555}$${\displaystyle f(2)=629}$

1. 彼女は値f (3)、f (4)、f (5)を計算し、3つの冗長メッセージ「C=703」、「D=777」、「E=851」を送信します。

ボブは、 f ( k )の形式が であることを知っています。ここで、aとb は電話番号の 2 つの部分です。ここで、ボブが「D=777」と「E=851」を受信したとします。 ${\displaystyle f(i)=a+(ba)(i-1)}$

ボブは、受け取った値（f（4）とf （5））からaとbの値を計算することで、アリスの電話番号を再構築できます。ボブは任意の2つのerrメールを使用してこの手順を実行できるため、この例の消去コードのレートは40％です。

アリスは自分の電話番号を 1 つの err-mail だけでエンコードすることはできないことに注意してください。これは、電話番号が 6 文字で構成され、1 つの err-mail メッセージの最大長が 5 文字であるためです。アリスが自分の電話番号を分割して送信し、ボブに各部分の受信確認を求めると、少なくとも 4 つのメッセージを送信する必要があります (アリスから 2 つ、ボブから 2 つの確認)。したがって、この例の消去コードでは 5 つのメッセージが必要であり、非常に経済的です。

この例は少し不自然です。あらゆるデータ セットで機能する本当に汎用的な消去コードの場合、与えられたf ( i ) 以外のものが必要になります。

上記の線形構築は、多項式補間に一般化できます。さらに、点は有限体上で計算されるようになりました。

まず、少なくともnの位数を持つ有限体F を選択しますが、通常は 2 のべき乗です。送信者は、データ シンボルに 0 からk  − 1 までの番号を付けて送信します。次に、 p ( i ) がデータ シンボルiと等しくなるように、位数kの(ラグランジュ) 多項式p ( x )を作成します。次に、p ( k )、...、p ( n − 1 ) を送信します。受信側は、 k個のシンボルを正常に 受信した場合、多項式補間を使用して失われたパケットを回復することもできます。 Fの位数が 2 ^b未満の場合( b はシンボル内のビット数)、複数の多項式を使用できます。

送信者は、シンボルkからn  − 1 を「オンザフライ」で構築できます。つまり、シンボルの送信間でワークロードを均等に分散します。 受信側が計算を「オンザフライ」で実行したい場合は、シンボルi  <  kが正常に受信された場合はq ( i ) = p ( i ) 、シンボルi < kが受信されなかった場合はq ( i ) = 0となるような新しい多項式qを構築できます。ここで、r ( i ) = p ( i ) −  q ( i ) とします。まず、シンボルi < kが正常に受信された場合はr ( i ) = 0 であることがわかります。次に、シンボルi  ≥  kが正常に受信された場合は、r ( i ) =  p ( i ) −  q ( i ) を計算できます。したがって、 rを構築し、それを評価して失われたパケットを見つけるのに十分なデータ ポイントがあります。したがって、送信者と受信者の両方でO ( n ( n  −  k )) の操作と、オンザフライでの操作に必要なスペースは O ( n  −  k ) のみになります。

このプロセスはリード・ソロモン符号によって実装され、符号語はヴァンデルモンド行列を使用して有限体上に構築されます。

最も実用的な消去コードは体系的なコードであり、元のk個のシンボルのそれぞれが、エンコードされていないコピーとしてn個のメッセージシンボルの1つとして見つかります。^{[12] （}秘密分散を サポートする消去コードでは体系的なコードは使用されません）。

ほぼ最適な消去コードでは、メッセージを復元するために (1 + ε) k個のシンボルが必要です (ε>0)。 ε を減らすと、CPU 時間が犠牲になります。ほぼ最適な消去コードは、訂正能力と計算の複雑さをトレードオフします。実用的なアルゴリズムでは、線形時間複雑さでエンコードおよびデコードできます。

ファウンテン コード(レートレス消失コードとも呼ばれる) は、準最適消失コードとして注目すべき例です。このコードでは、 k個のシンボル メッセージを実質的に無限のエンコード形式に変換できます。つまり、任意の数の冗長シンボルを生成でき、これらはすべてエラー訂正に使用できます。受信機は、 k 個よりわずかに多いエンコード シンボルを受信すると、デコードを開始できます。

再生成コードは、既存のエンコードされたフラグメントから失われたエンコードされたフラグメントを再構築（修復とも呼ばれる）する問題に対処します。この問題は、エンコードされた冗長性を維持するための通信が問題となる分散ストレージシステムで発生します。^[12]

消失訂正符号は現在、信頼性の高いデータストレージの標準的な手法となっている。^{[13] [ 14] [15} ] 特に、リード・ソロモン消失訂正符号のさまざまな実装は、 Apache Hadoop、 Linuxに組み込まれたRAID-6、Microsoft Azure、Facebookコールドストレージ、Backblaze Vaultsで使用されている。^{[15] [12]}

ストレージ システムの障害から回復する従来の方法は、レプリケーションを使用することでした。ただし、レプリケーションでは、無駄なバイトという点でかなりのオーバーヘッドが発生します。そのため、データ センターで使用されるようなますます大規模なストレージ システムでは、消失訂正符号化ストレージが使用されています。ストレージ システムで使用される消失訂正符号化の最も一般的な形式は、リード ソロモン (RS) コードです。これは、パリティ ブロックと呼ばれる既知のデータの一部から失われたデータを再生成できるようにするために使用される高度な数学式です。( k、  m ) RS コードでは、「チャンク」と呼ばれるk 個のデータ ブロックのセットが( k  +  m ) 個のチャンクにエンコードされます。チャンクのセット全体で 1 つのストライプが構成されます。このコーディングは、( k  +  m ) 個のチャンクのうち少なくともk 個が使用可能である限り、データ全体を回復できるように行われます。つまり、( k、  m ) RS エンコード ストレージは最大m 個の障害に耐えることができます。

例: FacebookのHDFSで使用されているRS(10,4)コード^[16]では、10MBのユーザーデータが10個の1MBブロックに分割されます。次に、冗長性を提供するために4つの追加の1MBパリティブロックが作成されます。これにより、最大4つの同時障害に耐えることができます。ここでのストレージオーバーヘッドは14/10 = 1.4倍です。

完全に複製されたシステムの場合、最大 4 つの同時障害に耐えるために、10 MB のユーザー データを 4 回複製する必要があります。その場合のストレージ オーバーヘッドは 50/10 = 5 回になります。

これにより、完全なレプリケーションと比較して、消失訂正符号化ストレージのストレージ オーバーヘッドが低くなり、それが今日のストレージ システムの魅力となっていることがわかります。

当初、消失訂正符号は「コールド」（めったにアクセスされない）データを効率的に保存するコストを削減するために使用されていましたが、消失訂正符号は「ホット」（より頻繁にアクセスされる）データを提供するパフォーマンスを向上させるためにも使用できます。^[12]

RAID N+MはデータブロックをN+Mドライブに分割し、M台のドライブのいずれかが故障してもすべてのデータを回復することができます。^[1] 特に、RAID 7.3はトリプルパリティRAIDを指し、3台のドライブのいずれかが故障してもすべてのデータを回復することができます。^[17]

以下に、さまざまなコードの実装例をいくつか示します。

• 竜巻コード
• 低密度パリティ検査符号

• ファウンテンコード
• オンラインコード
• LTコード
• ラプターコード
• ネットワークコード
• 三角形のコード

• パリティ: RAIDストレージ システムで使用されます。
• パーアーカイブ
• Tahoe-LAFSにはzfecが含まれています
• リード・ソロモン符号
• 消失耐性体系的コード、冗長パケットの最大数でリード・ソロモンを上回るMDSコード、^{[誰によると? ]} 2ビットのRS(4,2)または3ビットのRS(9,2)を参照
• 再生コード^{[18] [19]}
• その他の最大距離分離可能なコード

• 前方誤り訂正コード。
• 秘密共有（元の秘密は暗号化され、復号クォーラムに達するまで隠蔽される点が異なります）
• スペルアルファベット
• バイナリ消去チャネル

• Jerasure は、SIMD 最適化を備えたリード・ソロモンおよびコーシー消失訂正符号技術を実装したフリー ソフトウェア ライブラリです。
• ルイージ・リッツォによるコンピュータ通信におけるソフトウェアFECでは、最適な消失訂正符号について説明しています。
• Feclib は、バンド行列を使用する Luigi Rizzo の成果に対するほぼ最適な拡張です。バンドの幅のサイズや有限体のサイズなど、多くのパラメータを設定できます。また、最新の CPU の大きなレジスタサイズをうまく活用しています。上記のほぼ最適なコードとの比較は不明です。
• コードの再生成と消去コードの再構築に関する、分散ストレージ向けコーディング wiki。
• ECIP (Erasure Code Internet Protocol) は 1996 年に開発され、インターネットで FEC (Forward Error Correction) が初めて使用されました。最初に商業的に使用されたのは、スリランカのアーサー・C・クラーク卿のライブ ビデオをインディアナ州の UIUC にストリーミング配信するためでした。