Loading article…
情報理論および符号理論（コンピュータ科学および電気通信への応用を含む）において、誤り検出訂正（EDAC）または誤り制御は、信頼性の低い通信チャネルを介してデジタルデータを確実に伝送するための技術である。多くの通信チャネルはチャネルノイズの影響を受けるため、送信元から受信元への伝送中にエラーが発生する可能性がある。誤り検出技術はこのようなエラーを検出することを可能にし、誤り訂正は多くの場合、元のデータを復元することを可能にする。
エラー検出とは、送信機から受信機への伝送中にノイズやその他の障害によって発生するエラーを検出することである。
エラー訂正とは、エラーを検出し、元のエラーのないデータを再構築することである。
古代においては、ヘブライ語聖書の写字生は、スティッチ（詩行）の数に応じて報酬を受け取っていた。聖書の散文書はほとんどスティッチで書かれていなかったため、写字生は作業量を見積もるために文字数を数える必要があった。 [ 1 ]これはまた、後続の写本の作成によるテキストの伝達の正確性を確保するのにも役立った。[ 2 ] [ 3 ]西暦7世紀から10世紀にかけて、ユダヤ人の書記の一団がこれを形式化して拡張し、聖典の正確な複製を保証するために数値マソラを作成した。これには、行、セクション、書、書のグループ内の単語数のカウント、書の真ん中のスティッチの記録、単語の使用統計、および注釈が含まれていた。[ 1 ]基準は、トーラーの巻物でたった1文字のずれでも許容できないものとなった。[ 4 ]彼らの誤り訂正方法の有効性は、紀元前150年頃から紀元後75年頃までの死海文書が1947年から1956年に発見されたことで実証された、数世紀にわたる写本の正確さによって検証された。[ 5 ]
誤り訂正符号の現代的な発展は、 1947年のリチャード・ハミングによるものとされている。[ 6 ]ハミング符号の説明は、クロード・シャノンの『通信の数学的理論』[ 7 ]に掲載され、マルセル・J・E・ゴレイによってすぐに一般化された。[ 8 ]
すべての誤り検出訂正方式は、メッセージに冗長性（つまり、余分なデータ）を追加します。受信側はこの冗長性を使用して、送信されたメッセージの一貫性を確認し、破損していると判断されたデータを復元できます。誤り検出訂正方式は、系統的方式と非系統的方式のいずれかです。系統的方式では、送信側は元の（誤りのない）データを送信し、データビットから何らかの符号化アルゴリズムによって生成された固定数のチェックビット（またはパリティデータ）を付加します。誤り検出が必要な場合、受信側は受信したデータビットに同じアルゴリズムを適用し、その出力を受信したチェックビットと比較します。値が一致しない場合、送信中にエラーが発生したことになります。誤り訂正が必要な場合、受信側は受信したデータビットと受信したチェックビットに復号アルゴリズムを適用して、元の誤りのないデータを復元できます。非系統的コードを使用するシステムでは、元のメッセージは、同じ情報を持つ符号化メッセージに変換され、元のメッセージと同じビット数以上のビットを持ちます。
優れた誤り制御性能を実現するには、通信チャネルの特性に基づいて方式を選択する必要があります。一般的なチャネルモデルには、誤りが一定の確率でランダムに発生するメモリレスモデルと、誤りが主にバースト的に発生する動的モデルがあります。したがって、誤り検出/訂正符号は、一般的にランダム誤り検出/訂正とバースト誤り検出/訂正に分類できます。また、ランダム誤りとバースト誤りが混在する状況にも適した符号もあります。
チャネル特性が特定できない場合、または大きく変動する場合は、誤り検出方式と誤りデータの再送信システムを組み合わせることができます。これは自動再送要求（ARQ）と呼ばれ、インターネットで最もよく使用されています。誤り制御の別の方法として、 ARQと誤り訂正符号化を組み合わせたハイブリッド自動再送要求（HARQ）があります。
エラー訂正には大きく分けて3種類あります。[ 9 ]
自動再送要求（ARQ）は、データ伝送におけるエラー制御方式であり、エラー検出コード、確認応答メッセージおよび／または否定応答メッセージ、タイムアウトを利用して、信頼性の高いデータ伝送を実現します。確認応答とは、受信側がデータフレームを正しく受信したことを示すために送信するメッセージです。
通常、送信側がタイムアウトが発生する前（つまり、データフレームを送信してから妥当な時間内）に確認応答を受信しない場合、正しく受信されるか、または所定の再送信回数を超えてエラーが継続するまで、フレームを再送信します。
ARQプロトコルには、ストップアンドウェイトARQ、ゴーバックN ARQ、および選択的リピートARQの3種類があります。
ARQは、インターネットのように通信チャネルの容量が変動したり不明な場合に適しています。しかし、ARQはバックチャネルの可用性を必要とし、再送信によって遅延が増加する可能性があり、再送信のためのバッファとタイマーの維持を必要とするため、ネットワークが混雑している場合はサーバーとネットワーク全体の容量に負担がかかる可能性があります。[ 10 ]
例えば、ARQは短波無線データリンクにおいてARQ-Eの形で使用されたり、多重化と組み合わせてARQ-Mとして使用されたりします。
前方誤り訂正(FEC) は、メッセージに誤り訂正符号(ECC)などの冗長データを追加するプロセスであり、送信中または保存中に (使用する符号の能力まで) 多数の誤りが混入した場合でも、受信側でメッセージを復元できるようにします。受信側は送信側にデータの再送信を要求する必要がないため、前方誤り訂正ではバックチャネルは不要です。誤り訂正符号は、セルラーネットワーク、高速光ファイバー通信、Wi-Fiなどの下位層通信[ 11 ] [ 12 ]や、フラッシュメモリ、ハードディスク、RAMなどのメディアへの信頼性の高い保存に使用されています[ 13 ]。
誤り訂正符号は通常、畳み込み符号とブロック符号に分類される。
シャノンの定理は前方誤り訂正における重要な定理であり、特定の誤り確率または信号対雑音比（SNR）を持つチャネル上で信頼性の高い通信が可能な最大情報レートを記述する。この厳密な上限はチャネル容量で表される。より具体的には、この定理は、符号化長が増加するにつれて、離散的な無記憶チャネル上の誤り確率を任意に小さくできるような符号が存在することを示している。ただし、符号レートはチャネル容量よりも低い必要がある。符号レートは、 k個のソースシンボルとn個の符号化シンボルの比率k/nとして定義される。
実際に許容される最大符号化率は、使用する誤り訂正符号によって異なり、それよりも低くなる場合がある。これは、シャノンの証明が存在論的な性質のものであり、最適かつ効率的な符号化・復号アルゴリズムを備えた符号の構成方法を示していなかったためである。
ハイブリッドARQはARQと前方誤り訂正の組み合わせです。基本的なアプローチは2つあります。[ 10 ]
エラー検出は、一般的に適切なハッシュ関数（具体的には、チェックサム、巡回冗長検査、またはその他のアルゴリズム）を用いて実現されます。ハッシュ関数はメッセージに固定長のタグを追加し、受信者はそのタグを再計算して送信されたタグと比較することで、配信されたメッセージを検証できます。
ハッシュ関数の設計には非常に多くの種類が存在する。しかし、そのシンプルさや特定の種類のエラー検出への適性（例えば、巡回冗長検査によるバーストエラー検出性能）といった理由から、特に広く利用されているものもある。
最小距離符号化に基づくランダム誤り訂正符号は、検出可能な誤りの数について厳密な保証を提供できますが、原像攻撃から保護するとは限りません。
繰り返し符号は、ビットをチャネル全体に繰り返して送信することで、エラーのない通信を実現する符号化方式です。送信するデータストリームは、ビットのブロックに分割されます。各ブロックは、あらかじめ決められた回数だけ送信されます。たとえば、ビットパターン1011を送信するには、4 ビットのブロックを 3 回繰り返すことで、1011 1011 1011というパターンが生成されます。この 12 ビットのパターンが1010 1011 1011として受信された場合（最初のブロックが他の 2 つのブロックと異なる場合）、エラーが発生したことになります。
繰り返し符号は非常に非効率的で、各グループでまったく同じ場所でエラーが発生すると問題が発生する可能性があります (たとえば、前の例の1010 1010 1010は正しいと検出されます)。繰り返し符号の利点は、非常に単純であることであり、実際には、一部のナンバーズ ステーションの送信で使用されています。[ 14 ] [ 15 ]
パリティビットとは、ソースビット群に追加されるビットで、出力におけるセットビット（値が1のビット）の数が偶数か奇数かを保証するものです。これは非常にシンプルな方式で、出力における単一のエラー、あるいは奇数個（3個、5個など）のエラーを検出するために使用できます。偶数個のビットが反転すると、データにエラーがあってもパリティビットは正しく見えるようになります。
送信される各ワードに追加されるパリティビットは横断的冗長性チェックと呼ばれ、ワードストリームの末尾に追加されるパリティビットは縦方向冗長性チェックと呼ばれます。たとえば、mビットのワードの系列のそれぞれに、そのワードに奇数個または偶数個の1が含まれているかどうかを示すパリティビットが追加されている場合、1つのエラーを含むワードはすべて検出されます。ただし、エラーがワードのどこにあるのかはわかりません。さらに、n個のワードのストリームごとにパリティ和が送信され、その各ビットが、直前のグループで送信されたビット位置における1の数が奇数個または偶数個であるかどうかを示す場合、エラーの正確な位置を特定してエラーを訂正できます。ただし、この方法は、n個のワードのグループごとにエラーが1つ以下である場合にのみ有効であることが保証されます。エラー訂正ビットを増やすと、より多くのエラーを検出でき、場合によっては訂正することもできます。
他にもビットグループ化の手法は存在する。
メッセージのチェックサムとは、固定ワード長（例えばバイト値）のメッセージコードワードのモジュラ演算による算術和のことです。意図しない全ゼロメッセージを検出するために、送信前に1の補数演算によって和を反転させることがあります。
チェックサム方式には、パリティビット、チェックデジット、縦方向冗長性チェックなどがあります。Dammアルゴリズム、Luhnアルゴリズム、Verhoeffアルゴリズムなどの一部のチェックサム方式は、識別番号を書き留めたり記憶したりする際に人間が引き起こす一般的なエラーを検出するように特別に設計されています。
巡回冗長検査（CRC）は、コンピュータネットワークにおけるデジタルデータの偶発的な変更を検出するために設計された、セキュリティ保護機能を持たないハッシュ関数です。悪意を持って導入されたエラーの検出には適していません。CRCの特徴は、有限体上で多項式除算を行う際に除数として使用される生成多項式を指定することです。入力データは被除数として扱われ、余りが結果となります。
CRCは、バーストエラーの検出に適した特性を備えています。CRCはハードウェアでの実装が特に容易であるため、コンピュータネットワークやハードディスクドライブなどのストレージデバイスで広く使用されています。
パリティビットは、1ビットCRCの特殊なケースと見なすことができる。
暗号学的ハッシュ関数の出力（メッセージダイジェストとも呼ばれる）は、データの変更が偶発的なもの（例えば、送信エラーによるもの）であろうと、悪意を持って行われたものであろうと、データの完全性について強力な保証を提供します。データへのいかなる変更も、ハッシュ値の不一致によって検出される可能性が高いです。さらに、あるハッシュ値が与えられた場合、通常、同じハッシュ値を生成する入力データ（与えられたデータ以外）を見つけることは不可能です。攻撃者がメッセージだけでなくハッシュ値も変更できる場合、追加のセキュリティのために鍵付きハッシュまたはメッセージ認証コード（MAC）を使用できます。鍵を知らなければ、攻撃者は変更されたメッセージに対して正しい鍵付きハッシュ値を容易かつ便利に計算することはできません。
デジタル署名は、データの変更が偶発的なものか悪意によるものかにかかわらず、データの完全性について強力な保証を提供することができます。デジタル署名は、ウェブを安全に閲覧するためのHTTPSプロトコルの一部として最もよく知られています。
誤り訂正符号は、誤り検出に用いることができます。最小ハミング距離dを持つ符号は、符号語中のd -1個の誤りを検出できます。検出すべき誤りの最小数に厳密な制限を設けたい場合、最小距離に基づく誤り訂正符号を誤り検出に用いることが適切です。
ハミング距離dが最小値d =2の符号は、誤り訂正符号の特殊なケースであり、単一誤りの検出に使用できます。パリティビットは、単一誤り検出符号の一例です。
低遅延が求められるアプリケーション（電話会話など）は、自動再送要求（ARQ）を使用できません。前方誤り訂正（FEC）を使用する必要があります。ARQシステムがエラーを検出して再送信する頃には、再送信されたデータは使用できないほど遅れて到着してしまうからです。
送信機が送信後すぐに情報を破棄するアプリケーション（ほとんどのテレビカメラなど）では、ARQを使用できません。エラーが発生すると元のデータが利用できなくなるため、FECを使用する必要があります。
ARQを使用するアプリケーションはリターンチャネルを備えている必要があります。リターンチャネルを持たないアプリケーションはARQを使用できません。極めて低いエラー率が求められるアプリケーション（デジタル送金など）は、FECでは訂正不能なエラーが発生する可能性があるため、ARQを使用する必要があります。
信頼性および検査工学では、誤り訂正符号の理論[ 16 ]や自然言語[ 17 ]も利用されています。
一般的なTCP/IPスタックでは、エラー制御は複数のレベルで行われます。
誤り訂正符号の開発は、惑星間距離での信号電力の極端な希釈と宇宙探査機に搭載された限られた電力供給のため、深宇宙探査ミッションの歴史と密接に結びついていました。初期のミッションではデータを符号化せずに送信していましたが、1968年からは、（最適に復号されない）畳み込み符号とリード・ミュラー符号の形でデジタル誤り訂正が実装されました。[ 18 ]リード・ミュラー符号は、宇宙船が受けるノイズ（おおよそベルカーブに一致する）によく適しており、マリナー宇宙船に実装され、1969年から1977年までのミッションで使用されました。
1977年に開始されたボイジャー1号とボイジャー2号のミッションは、木星と土星からカラー画像と科学情報を送信するように設計されました。[ 19 ]これにより、コーディング要件が増加し、そのため、宇宙船は、外側のゴレイ(24,12,8)コードと連結できる畳み込みコード(最適にビタビ復号)によってサポートされました。ボイジャー2号はさらに、リード-ソロモンコードの実装をサポートしました。連結されたリード-ソロモン-ビタビ(RSV)コードは、非常に強力な誤り訂正を可能にし、宇宙船の天王星と海王星への長距離の旅を可能にしました。1989年のECCシステムのアップグレード後、両方の宇宙船はV2 RSVコーディングを使用しました。
宇宙データシステム諮問委員会は現在、最低でもボイジャー2号RSV符号と同等の性能を持つ誤り訂正符号の使用を推奨している。連結符号は宇宙ミッションにおいて次第に使われなくなりつつあり、ターボ符号やLDPC符号といったより高性能な符号に置き換えられつつある。
実施される深宇宙探査や軌道探査ミッションの種類が多岐にわたることから、万能な誤り訂正システムを見つけることは今後も継続的な課題となるだろう。地球近傍のミッションでは、通信チャネルにおけるノイズの性質が、惑星間探査ミッションの宇宙船が経験するノイズとは異なる。さらに、宇宙船が地球から遠ざかるにつれて、ノイズ補正の問題はより困難になる。
衛星トランスポンダの帯域幅に対する需要は、テレビ放送（新チャンネルや高精細テレビを含む）やIPデータの配信へのニーズの高まりを背景に、増加の一途を辿っています。しかし、トランスポンダの供給状況や帯域幅の制約が、この成長を抑制しています。トランスポンダの容量は、選択された変調方式とFEC（前方誤り訂正）によって消費される容量の割合によって決まります。
エラー検出訂正符号は、データ記憶媒体の信頼性を向上させるためによく使用されます。[ 20 ] 1951年の最初の磁気テープデータストレージ には、1ビットエラーを検出できるパリティトラックが搭載されていました。グループ符号化記録テープで使用される最適な矩形符号は、1ビットエラーを検出するだけでなく訂正も行います。一部のファイル形式、特にアーカイブ形式には、破損や切り捨てを検出するためのチェックサム（多くの場合CRC-32）が含まれており、冗長性ファイルやパリティファイルを使用して破損したデータの一部を復元できます。コンパクトディスクでは、傷によるエラーを訂正するためにリード・ソロモン符号が使用されます。
最新のハードドライブは、リード・ソロモン符号を使用して、セクター読み取りの軽微なエラーを検出して修正し、故障したセクターから破損したデータを回復して、そのデータを予備セクターに保存します。[ 21 ] RAIDシステムは、ハードドライブが完全に故障したときにデータを回復するために、さまざまなエラー訂正技術を使用します。ZFSやBtrfsなどのファイルシステム、および一部のRAID実装は、データスクラビングとリシルバーリングをサポートしており、不良ブロックが使用される前に検出され、（うまくいけば）回復されます。[ 22 ]回復されたデータは、まったく同じ物理的な場所に書き直されるか、同じハードウェア上の別の予備ブロックに書き直されるか、または交換用ハードウェアに書き直される可能性があります。
ダイナミックランダムアクセスメモリ（DRAM）は、誤り訂正符号を用いることで、ソフトエラーに対するより強力な保護機能を提供する。ECCまたはEDAC保護メモリとして知られるこのような誤り訂正メモリは、科学計算、金融、医療などのミッションクリティカルなアプリケーション、および宇宙空間における放射線量の増加に対応するため、地球外アプリケーションにおいて特に望ましい。
エラー訂正メモリコントローラは従来ハミング符号を使用していたが、一部は三重冗長性を使用していた。インターリーブにより、隣接するビットを異なるワードに関連付けることで、物理的に隣接する複数のビットに影響を与える可能性のある単一の宇宙線の影響を複数のワードに分散させることができる。アクセス間の特定のワードで単一イベントアップセット（SEU）がエラーしきい値（単一のエラーなど）を超えない限り、それを訂正することができ（例えば、単一ビットエラー訂正符号によって）、エラーのないメモリシステムの錯覚を維持できる。[ 23 ]
ECC メモリの動作に必要な機能を提供するハードウェアに加えて、オペレーティングシステムには通常、ソフト エラーが透過的に回復されたときに通知を提供するのに使用される関連するレポート機能が含まれています。 1 つの例として、Linux カーネルのEDACサブシステム (以前はBluesmokeとして知られていました) があり、これはコンピュータ システム内のエラー チェック対応コンポーネントからデータを収集します。ECC メモリに関連するイベントを収集して報告するだけでなく、PCI バスで検出されたものを含む他のチェック サム エラーもサポートしています。[ 24 ] [ 25 ] [ 26 ]一部のシステムでは、メモリ スクラビングもサポートしており、エラーが回復不能になる前に早期に検出して修正します。