エラー検出と修正

コンピュータサイエンスや電気通信に応用される情報理論と符号理論において、誤り検出訂正( EDAC ) または誤り制御は、信頼性の低い通信チャネルを介してデジタルデータを確実に配信できるようにする技術です。多くの通信チャネルはチャネルノイズの影響を受けやすく、そのため、送信元から受信側への送信中に誤りが発生する可能性があります。誤り検出技術は、このような誤りを検出できるようにします。一方、誤り訂正は、多くの場合、元のデータを再構築できるようにします。

エラー検出とは、送信機から受信機への送信中にノイズやその他の障害によって発生したエラーを検出することです。

エラー訂正とは、エラーを検出し、エラーのない元のデータを再構築することです。

古代、ヘブライ語聖書の写字生はステッチ（詩の行）の数に応じて報酬を受け取っていた。聖書の散文書がステッチで書かれることはほとんどなかったため、写字生は作業量を見積もるために文字を数えなければならなかった。^[1]これはまた、その後の写本の作成によるテキストの伝達の正確性を確保するのに役立った。^{[2] [3]}西暦7世紀から10世紀の間に、ユダヤ人の写字生の一団がこれを形式化して拡張し、聖なるテキストの正確な複製を確実にするために数値マソラを作成した。これには、行、セクション、本、および本のグループの単語数を数え、本の真ん中のステッチ、単語使用統計、および解説が含まれていた。^[1]基準は、トーラの巻物で1文字でも逸脱することは受け入れられないと見なされるほどになった。^[4]彼らの誤り訂正法の有効性は、1947年から1956年にかけて紀元前150年から紀元後75年頃の死海文書が発見されたことで実証された、何世紀にもわたる写本の正確 さによって検証されました。^[5]

誤り訂正符号の現代的な開発は、1947年のリチャード・ハミングによるものとされています。 ^[6]ハミングの符号の説明は、クロード・シャノンの「通信の数学的理論」^[7]に掲載され、マルセル・J・E・ゴレイによってすぐに一般化されました。^[8]

すべてのエラー検出および訂正方式は、メッセージにいくらかの冗長性（つまり、いくらかの追加データ）を追加します。受信者はこれを使用して、配信されたメッセージの一貫性をチェックし、破損していると判断されたデータを復元できます。エラー検出および訂正方式は、体系的または非体系的のいずれかです。体系的方式では、送信者は元の（エラーのない）データを送信し、一定の数のチェック ビット（またはパリティ データ）を添付します。チェック ビットは、何らかのエンコード アルゴリズムによってデータ ビットから導出されます。エラー検出が必要な場合、受信者は受信したデータ ビットに同じアルゴリズムを適用し、その出力を受信したチェック ビットと比較します。値が一致しない場合は、送信中のある時点でエラーが発生しています。エラー訂正が必要な場合、受信者は受信したデータ ビットと受信したチェック ビットにデコード アルゴリズムを適用して、元のエラーのないデータを復元できます。非体系的コードを使用するシステムでは、元のメッセージは、同じ情報を持ち、元のメッセージと少なくとも同じビット数を持つエンコードされたメッセージに変換されます。

優れたエラー制御性能を得るには、通信チャネルの特性に基づいて方式を選択する必要があります。一般的なチャネル モデルには、エラーがランダムかつ一定の確率で発生するメモリレスモデルと、エラーが主にバーストで発生する動的モデルがあります。したがって、エラー検出および訂正コードは、ランダム エラー検出/訂正コードとバースト エラー検出/訂正コードに一般的に区別できます。一部のコードは、ランダム エラーとバースト エラーが混在する場合にも適しています。

チャネル特性が判定できない場合、または特性が大きく変動する場合は、エラー検出方式をエラーのあるデータの再送信システムと組み合わせることがあります。これは自動再送要求(ARQ) と呼ばれ、インターネットで最もよく使用されています。エラー制御の代替アプローチは、ARQ とエラー訂正コーディングを組み合わせたハイブリッド自動再送要求(HARQ) です。

エラー訂正には主に3つの種類がある: ^[9]

自動再送要求(ARQ) は、エラー検出コード、確認応答メッセージおよび/または否定応答メッセージ、およびタイムアウトを利用して信頼性の高いデータ送信を実現する、データ送信のエラー制御方法です。確認応答は、受信側がデータ フレームを正しく受信したことを示すために送信されるメッセージです。

通常、送信側は、タイムアウトが発生する前に（つまり、データ フレームの送信後、妥当な時間内に）確認応答を受信しない場合、フレームが正しく受信されるか、または所定の再送信回数を超えてエラーが続くまで、フレームを再送信します。

ARQ プロトコルには、Stop-and-wait ARQ、Go-Back-N ARQ、Selective Repeat ARQの 3 種類があります。

ARQは、インターネットのように通信チャネルの容量が変動したり不明な場合に適しています。しかし、ARQではバックチャネルの可用性が必要であり、再送による遅延が増加する可能性があり、再送用のバッファとタイマーの維持が必要になるため、ネットワークが混雑している場合はサーバーとネットワーク全体の容量に負担がかかる可能性があります。^[10]

たとえば、 ARQ は、ARQ-Eの形式で短波無線データリンクで使用されるか、またはARQ-Mとして多重化と組み合わせて使用​​されます。

前方誤り訂正（FEC）は、誤り訂正符号（ECC）などの冗長データをメッセージに追加するプロセスであり、送信プロセス中または保存時に多数のエラー（使用されている符号の能力まで）が導入された場合でも、受信者がメッセージを回復できるようにします。受信者は送信者にデータの再送信を要求する必要がないため、前方誤り訂正ではバックチャネルは必要ありません。誤り訂正符号は、携帯電話ネットワーク、高速光ファイバー通信、Wi-Fiなどの下位層通信、^{[11] [12]}や、フラッシュメモリ、ハードディスク、RAMなどのメディアへの信頼性の高い保存に使用されます。^[13]

誤り訂正符号は通常、畳み込み符号とブロック符号に区別されます。

• 畳み込み符号はビット単位で処理されます。特にハードウェアでの実装に適しており、ビタビデコーダーにより最適なデコードが可能になります。
• ブロック コードはブロックごとに処理されます。ブロック コードの初期の例としては、繰り返しコード、ハミング コード、多次元パリティ チェック コードなどがあります。その後、多くの効率的なコードが登場しましたが、リード ソロモン コードは現在広く使用されているため最も注目されています。ターボ コードと低密度パリティ チェック コード(LDPC) は比較的新しい構造ですが、ほぼ最適な効率を実現できます。

シャノンの定理は、前方誤り訂正における重要な定理であり、特定の誤り確率または信号対雑音比(SNR)を持つチャネル上で信頼性の高い通信が可能な最大情報レートを説明します。この厳密な上限は、チャネル容量で表現されます。より具体的には、この定理は、符号化長の増加に伴って離散メモリレス チャネルでの誤り確率を任意に小さくできるコードが存在することを示しています。ただし、符号化率はチャネル容量よりも小さいことが条件です。符号化率は、 k 個のソース シンボルとn 個の符号化シンボル の分数k/nとして定義されます。

実際に許可される最大コード レートは、使用されるエラー訂正コードによって異なり、これより低くなる場合があります。これは、シャノンの証明が存在論的な性質のものだけであり、最適で効率的なエンコードおよびデコード アルゴリズムを備えたコードの構築方法を示していなかったためです。

ハイブリッドARQはARQと前方誤り訂正を組み合わせたものである。基本的なアプローチは2つある: ^[10]

• メッセージは常に FEC パリティ データ (およびエラー検出冗長性) とともに送信されます。 受信側はパリティ情報を使用してメッセージをデコードし、パリティ データがデコードに十分でなかった (整合性チェックの失敗によって識別された) 場合にのみ、ARQ を使用して再送信を要求します。
• メッセージはパリティ データなしで送信されます (エラー検出情報のみ)。 受信機がエラーを検出すると、ARQ を使用して送信機から FEC 情報を要求し、それを使用して元のメッセージを再構築します。

後者のアプローチは、レートレス消去コードを使用する場合の消去チャネルでは特に魅力的です。

エラー検出は、適切なハッシュ関数(具体的には、チェックサム、巡回冗長検査、またはその他のアルゴリズム) を使用して実現されるのが最も一般的です。ハッシュ関数はメッセージに固定長のタグを追加します。これにより、受信者はタグを再計算し、提供されたタグと比較することで、配信されたメッセージを検証できます。

ハッシュ関数の設計にはさまざまな種類があります。しかし、単純であることや、特定の種類のエラーを検出するのに適していること（たとえば、巡回冗長検査のバーストエラー検出性能）により、特に広く使用されているものもあります。

最小距離符号化に基づくランダム誤り訂正符号は、検出可能な誤りの数を厳密に保証できますが、原像攻撃から保護できない可能性があります。

繰り返しコードとは、チャネル上でビットを繰り返すことでエラーのない通信を実現するコーディング方式です。送信されるデータ ストリームが与えられると、データはビットのブロックに分割されます。各ブロックは、事前に決められた回数だけ送信されます。たとえば、ビット パターン1011を送信するには、4 ビット ブロックを 3 回繰り返して、1011 1011 1011を生成します。この 12 ビット パターンが1010 1011 1011として受信された場合(最初のブロックが他の 2 つのブロックと異なる場合)、エラーが発生しています。

繰り返しコードは非常に非効率で、各グループでまったく同じ場所でエラーが発生した場合に問題が発生しやすくなります（たとえば、前の例の1010 1010 1010は正しいと検出されます）。繰り返しコードの利点は、非常に単純なことであり、実際にいくつかの数字放送局の送信で使用されています。^{[14] [15]}

パリティビットは、出力内のセット ビット (つまり、値が 1 のビット) の数が偶数か奇数かを確認するためにソース ビットのグループに追加されるビットです。これは、出力内の 1 個またはその他の奇数 (つまり、3 個、5 個など) のエラーを検出するために使用できる非常に単純な方式です。反転したビットの数が偶数の場合、データに誤りがあってもパリティ ビットは正しいように見えます。

送信される各ワードに追加されるパリティ ビットは横断的冗長検査と呼ばれ、ワードストリームの最後に追加されるパリティ ビットは縦方向冗長検査と呼ばれます。たとえば、一連の m ビットワードのそれぞれに、そのワードに 1 が奇数個あったか偶数個あったかを示すパリティ ビットが追加されている場合、1 つのエラーを含むワードは検出されます。ただし、ワードのどこにエラーがあるかはわかりません。さらに、n ワードの各ストリームの後にパリティ サムが送信され、その各ビットが最新のグループで送信されたビット位置に 1 が奇数個あったか偶数個あったかを示す場合、エラーの正確な位置を判定してエラーを訂正できます。ただし、この方法は、n ワードの各グループにエラーが 1 つしかない場合にのみ有効であることが保証されます。エラー訂正ビットを増やすと、より多くのエラーを検出し、場合によっては訂正できます。

他にもビットグループ化の手法はあります。

メッセージのチェックサムは、固定ワード長 (バイト値など) のメッセージ コード ワードのモジュラー算術合計です。合計は、意図しないすべてゼロのメッセージを検出するために、送信前に 1 の補数演算によって否定される場合があります。

チェックサム方式には、パリティ ビット、チェック ディジット、および水平冗長性チェックが含まれます。Damm アルゴリズム、Luhn アルゴリズム、Verhoeff アルゴリズムなどの一部のチェックサム方式は、識別番号を書き留めたり記憶したりする際に人間が一般的に導入するエラーを検出するために特別に設計されています。

巡回冗長検査(CRC) は、コンピュータ ネットワーク内のデジタル データへの偶発的な変更を検出するために設計された、安全でないハッシュ関数です。悪意を持って導入されたエラーの検出には適していません。CRC は、入力データを被除数として、有限体上の多項式長除算の除数として使用される生成多項式の指定が特徴です。剰余が結果になります。

CRC はバースト エラーの検出に適した特性を持っています。CRC はハードウェアに実装するのが特に簡単なので、コンピュータ ネットワークやハード ディスク ドライブなどのストレージ デバイスでよく使用されます。

パリティ ビットは、特殊なケースの 1 ビット CRC として考えることができます。

暗号ハッシュ関数の出力は、メッセージ ダイジェストとも呼ばれ、データの変更が偶発的なもの (たとえば、伝送エラーによるもの) であるか悪意を持って導入されたものであるかにかかわらず、データの整合性について強力な保証を提供できます。データへの変更は、ハッシュ値の不一致によって検出される可能性が高くなります。さらに、ハッシュ値が与えられている場合、同じハッシュ値を生成する入力データ (与えられたもの以外) を見つけることは通常不可能です。攻撃者がメッセージだけでなくハッシュ値も変更できる場合は、キー付きハッシュまたはメッセージ認証コード(MAC) を使用してセキュリティを強化できます。キーを知らなければ、攻撃者は変更されたメッセージの正しいキー付きハッシュ値を簡単にまたは便利に計算することはできません。

デジタル署名は、データの変更が偶発的なものか悪意によるものかを問わず、データの整合性について強力な保証を提供できます。デジタル署名は、Web を安全に閲覧するための HTTPS プロトコルの一部であることで最もよく知られています。

任意のエラー訂正コードをエラー検出に使用できます。最小ハミング距離dを持つコードは、コードワード内の最大d − 1 個のエラーを検出できます。検出するエラーの最小数を厳密に制限する必要がある場合は、最小距離ベースのエラー訂正コードをエラー検出に使用するのが適しています。

最小ハミング距離d = 2 のコードは、エラー訂正コードの退化したケースであり、単一のエラーを検出するために使用できます。パリティ ビットは、単一エラー検出コードの例です。

低遅延を必要とするアプリケーション (電話での会話など)では、自動再送要求(ARQ)を使用できません。転送エラー訂正(FEC) を使用する必要があります。ARQ システムがエラーを検出して再送信するまでに、再送信されたデータは到着が遅すぎて使用できなくなります。

送信機が情報を送信するとすぐにその情報を忘れてしまうアプリケーション (ほとんどのテレビ カメラなど) では ARQ を使用できません。エラーが発生すると元のデータが使用できなくなるため、FEC を使用する必要があります。

ARQ を使用するアプリケーションにはリターン チャネルが必要です。リターン チャネルを持たないアプリケーションは ARQ を使用できません。

極めて低いエラー率を必要とするアプリケーション (デジタル送金など) では、FEC では修正できないエラーが発生する可能性があるため、ARQ を使用する必要があります。

信頼性工学や検査工学でも誤り訂正符号の理論が活用されている。^[16]

一般的なTCP/IPスタックでは、エラー制御は複数のレベルで実行されます。

• 各イーサネット フレームはCRC-32エラー検出を使用します。エラーが検出されたフレームは、受信側のハードウェアによって破棄されます。
• IPv4ヘッダーには、ヘッダーの内容を保護するチェックサムが含まれています。チェックサムが正しくないパケットは、ネットワーク内または受信側でドロップされます。
• ネットワーク ルーティングの処理コストを最小限に抑えるため、また現在のリンク層テクノロジが十分なエラー検出を提供すると想定されているため、チェックサムはIPv6ヘッダーから省略されました(RFC 3819 も参照)。
• UDP には、 UDP および IP ヘッダーのペイロードとアドレス情報をカバーするオプションのチェックサムがあります。チェックサムが正しくないパケットは、ネットワーク スタックによって破棄されます。チェックサムは IPv4 ではオプションですが、IPv6 では必須です。省略すると、データリンク層が必要なレベルのエラー保護を提供するものとみなされます。
• TCP は、 TCP および IP ヘッダー内のペイロードとアドレス情報を保護するためのチェックサムを提供します。チェックサムが正しくないパケットはネットワーク スタックによって破棄され、最終的には ARQ を使用して、明示的に ( 3 ウェイ ハンドシェイクなどを通じて) またはタイムアウトにより暗黙的に再送信されます。

惑星間距離を越える信号電力の極度な低下と宇宙探査機に搭載できる電力の制限のため、誤り訂正符号の開発は深宇宙探査の歴史と密接に結びついていた。初期のミッションではデータは符号化されずに送信されていたが、1968年以降、デジタル誤り訂正は（最適ではない形で復号された）畳み込み符号とリード・ミュラー符号の形で実装された。^[17]リード・ミュラー符号は宇宙船が受けるノイズによく適しており（ベル曲線にほぼ一致）、マリナー宇宙船に実装され、1969年から1977年までのミッションで使用された。

1977年に開始されたボイジャー1号と2号のミッションは、木星と土星のカラー画像と科学情報を届けるように設計されました。^[18]これによりコーディング要件が増加したため、宇宙船は外側のゴレイ (24,12,8) コードと連結できる(最適にビタビ復号された) 畳み込みコードによってサポートされました。ボイジャー2号は、リード・ソロモンコードの実装もサポートしました。連結されたリード・ソロモン・ビタビ (RSV) コードにより、非常に強力なエラー訂正が可能になり、宇宙船の天王星と海王星への長期の旅が可能になりました。1989年のECCシステムのアップグレード後、両方の宇宙船はV2 RSVコーディングを使用しました。

宇宙データシステム諮問委員会は現在、ボイジャー 2 号の RSV コードと同等のパフォーマンスを持つエラー訂正コードの使用を最低限推奨しています。連結コードは宇宙ミッションではますます好まれなくなり、ターボ コードやLDPC コードなどのより強力なコードに置き換えられています。

実施される深宇宙および軌道ミッションの種類が多様であることから、万能のエラー修正システムを見つけることが継続的な問題となることが予想されます。地球に近いミッションの場合、通信チャネルのノイズの性質は、惑星間ミッションの宇宙船が経験するものとは異なります。さらに、宇宙船が地球から遠ざかるにつれて、ノイズ修正の問題はより困難になります。

衛星トランスポンダ帯域幅の需要は、テレビ（新しいチャンネルや高精細テレビを含む）や IP データを配信したいという要望に支えられて、増え続けています。トランスポンダの可用性と帯域幅の制約により、この成長は制限されています。トランスポンダの容量は、選択した変調方式と FEC によって消費される容量の割合 によって決まります。

エラー検出および訂正コードは、データ記憶媒体の信頼性を向上させるためによく使用されます。^[19] 1951 年に登場した最初の磁気テープ データ ストレージ には、1 ビット エラーを検出できるパリティ トラックが搭載されていました。グループコード化記録テープで使用される最適矩形コードは、1 ビット エラーの検出だけでなく、訂正も行います。一部のファイル形式、特にアーカイブ形式には、破損や切り捨てを検出するためのチェックサム (ほとんどの場合CRC32 ) が含まれており、冗長ファイルまたはパリティ ファイルを使用して破損したデータの一部を復元できます。リード ソロモン コードは、傷によるエラーを訂正するために コンパクト ディスクで使用されます。

現代のハードドライブは、リード・ソロモン符号を使用して、セクター読み取り時の軽微なエラーを検出して修正し、故障したセクターから破損したデータを回復してそのデータをスペアセクターに保存します。^[20] RAIDシステムは、ハードドライブが完全に故障したときにデータを回復するためにさまざまなエラー修正技術を使用します。 ZFSやBtrfsなどのファイルシステムや一部のRAID実装は、データスクラブと再シルバリングをサポートしており、これにより不良ブロックを検出して（うまくいけば）使用前に回復することができます。^[21]回復されたデータは、まったく同じ物理的な場所に書き直されることもあれば、同じハードウェア上の別の場所にあるスペアブロックに書き直されることもあります。また、交換用のハードウェアに書き直すこともできます。

ダイナミック ランダム アクセス メモリ(DRAM) は、エラー訂正コードを利用することで、ソフト エラーに対する強力な保護を提供できます。ECCまたはEDAC 保護メモリと呼ばれるこのようなエラー訂正メモリは、科学計算、金融、医療などのミッション クリティカルなアプリケーションや、宇宙での放射線増加による地球外アプリケーションに特に適しています。

エラー訂正メモリコントローラは伝統的にハミングコードを使用するが、三重モジュラー冗長性を使用するものもある。インターリーブにより、隣接するビットを異なるワードに関連付けることで、単一の宇宙線が物理的に隣接する複数のビットを混乱させる可能性の影響を複数のワードに分散させることができる。アクセス間の特定のワードでシングルイベント混乱（SEU）がエラーしきい値（たとえば、単一のエラー）を超えない限り、それは訂正可能であり（たとえば、シングルビットエラー訂正コードによって）、エラーのないメモリシステムという幻想は維持される可能性がある。^[22]

ECCメモリが動作するために必要な機能を提供するハードウェアに加えて、オペレーティングシステムには通常、ソフトエラーが透過的に回復されたときに通知を提供するために使用される関連レポート機能が含まれています。 1つの例は、LinuxカーネルのEDACサブシステム（以前はBluesmokeと呼ばれていました）です。これは、コンピュータシステム内のエラーチェック対応コンポーネントからデータを収集します。ECCメモリに関連するイベントを収集して報告するだけでなく、PCIバスで検出されたものを含むその他のチェックサムエラーもサポートしています。^{[23] [24] [25]}いくつかのシステム^{[指定]は、エラーが回復不能になる前に早期にエラーを捕捉して修正する}メモリスクラブもサポートしています。

• バーガーコード
• バースト誤り訂正符号
• ECCメモリ、コンピュータデータストレージの一種
• リンク適応
• アルゴリズムの一覧 § エラー検出と訂正
• ハッシュ関数のリスト

• Shu Lin、Daniel J. Costello, Jr. (1983)。 『エラー制御コーディング: 基礎と応用』Prentice Hall。ISBN 0-13-283796-X。
• SoftECC: ソフトウェアメモリ整合性チェックシステム
• HPC 向けの調整可能なソフトウェアベースの DRAM エラー検出および修正ライブラリ
• 大規模高性能コンピューティングにおけるサイレントデータ破損の検出と修正

• オンライン教科書「情報理論、推論、学習アルゴリズム」（David JC MacKay著）には、基本的なエラー訂正コード、エラー訂正の理論的限界、低密度パリティ検査コード、ターボ コード、ファウンテン コードなどの最新の最先端のエラー訂正コードに関する章が含まれています。
• ECC ページ - 一般的な ECC エンコードおよびデコード ルーチンの実装