エラーの検出と訂正

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
地球の大気によって引き起こされた伝送エラーをクリーンアップするために(左)、ゴダードの科学者は、CDやDVDで一般的に使用されているリードソロモンエラー訂正(右)を適用しました。典型的なエラーには、欠落したピクセル(白)と誤った信号(黒)が含まれます。白い縞模様は、送信が中断された短い期間を示します。

コンピュータサイエンスおよび電気通信のアプリケーションを使用する情報理論および符号理論ではエラー検出および訂正またはエラー制御は、信頼性の低い通信チャネルを介したデジタルデータの信頼性の高い配信可能にする技術です多くの通信チャネルはチャネルノイズの影響を受けやすいため、送信元から受信機への送信中にエラーが発生する可能性があります。エラー検出技術はそのようなエラーを検出することを可能にしますが、エラー訂正は多くの場合元のデータの再構築を可能にします。

定義

エラー検出は、送信機から受信機への送信中にノイズまたはその他の障害によって引き起こされたエラーの検出です。

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

歴史

古典古代では、ヘブライ語聖書の写字家は、スティッチの数(詩の行)に応じて彼らの仕事に対して報酬を支払われていました聖書の散文本はほとんどスティッチで書かれていなかったので、写字家は仕事の量を見積もるために文字を数えなければなりませんでした。[1]これはまた、後続のコピーの作成でテキストの送信の正確さを確保するのに役立ちました。[2] [3]西暦7世紀から10世紀の間に、ユダヤ人の書記のグループがこれを形式化して拡張し、数値マソラを作成しました。神聖なテキストの正確な複製を確実にするため。これには、行、セクション、本、および本のグループ内の単語数のカウントが含まれ、本の中間のステッチ、単語使用統計、および解説に注目しました。[1]基準は、トーラーの巻物の1文字でさえも許容できないと見なされるようになりました。[4]彼らの誤り訂正方法の有効性は、西暦前150年から75年にかけての1947年から1956年の死海文書の発見によって実証された何世紀にもわたるコピーの正確さによって検証されました。[5]

エラー訂正コードの最新の開発は、1947年にリチャードハミングの功績によるものです。 [6]ハミングのコードの説明はクロードシャノン通信の数学的理論[7]に掲載され、マルセルJEゴレイによってすぐに一般化されました[8]

はじめに

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

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

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

エラー訂正の種類

エラー訂正には主に3つのタイプがあります。[9]

自動再送要求(ARQ)

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

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

ARQプロトコルには、Stop-and-wait ARQGo-Back-N ARQ、およびSelective RepeatARQの3種類があります。

ARQは、インターネットの場合のように、通信チャネルの容量が変動するか不明な場合に適しています。ただし、ARQはバックチャネルの可用性を必要とし、再送信により遅延が増加する可能性があり、再送信用のバッファとタイマーのメンテナンスが必要です。これにより、ネットワークの輻輳が発生すると、サーバーとネットワーク全体の容量に負担がかかる可能性があります。[10]

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

前方誤り訂正

前方誤り訂正(FEC)は、エラー訂正コード(ECC)などの冗長データをメッセージに追加して、エラーが多数発生した場合でも(コードの能力まで)受信者がデータを回復できるようにするプロセスです。使用済み)は、送信プロセス中または保管中に導入されました。受信者は送信者にデータの再送を要求する必要がないため、前方誤り訂正にバックチャネルが不要であり、放送などの単方向通信に適しています。エラー訂正コードは、 CDなどのメディアでの信頼性の高いストレージだけでなく、下位層の通信でも頻繁に使用されます。DVDハードディスク、およびRAM

エラー訂正コードは通常、畳み込みコードブロックコードで区別されます。

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

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

ハイブリッドスキーム

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

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

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

エラー検出方式

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

さまざまなハッシュ関数の設計が存在します。ただし、特定の種類のエラーを検出するための単純さまたは適合性(たとえば、バーストエラーの検出における巡回冗長検査のパフォーマンス)のために、特に広く使用されているものもあります。

最小距離コーディング

最小距離コーディングに基づくランダムエラー訂正コードは、検出可能なエラーの数を厳密に保証できますが、原像攻撃から保護できない場合があります。

反復コード

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

繰り返しコードは非常に非効率的であり、各グループのまったく同じ場所でエラーが発生した場合、問題が発生する可能性があります(たとえば、前の例の「1010 1010 1010」は正しいものとして検出されます)。繰り返しコードの利点は、それらが非常に単純であり、実際に番号局の一部の送信で使用されることです。[11] [12]

パリティビット

パリティビットは、ソースビットのグループに追加されるビットであり、結果のセットビット(つまり、値が1のビット)の数が偶数または奇数になるようにします。これは非常に単純なスキームであり、出力内の単一またはその他の奇数(つまり、3、5など)のエラーを検出するために使用できます。反転したビットの数が偶数の場合、データに誤りがある場合でも、パリティビットは正しく表示されます。

送信される各「ワード」に追加されるパリティビットは横方向の冗長性チェックと呼ばれ、「ワード」のストリームの最後に追加されるパリティビットは縦方向の冗長性チェックと呼ばれます。たとえば、一連のmビットの「ワード」のそれぞれにパリティビットが追加され、そのワードに奇数または偶数の1があったかどうかを示す場合、単一のエラーが含まれるワードが検出されます。ただし、エラーが単語のどこにあるかはわかりません。さらに、nワードの各ストリームの後にパリティ合計が送信され、その各ビットが、最新のグループで送信されたそのビット位置に奇数または偶数の1があったかどうかを示す場合、エラーの正確な位置決定し、エラーを修正することができます。ただし、この方法は、n語のすべてのグループに1つ以下のエラーがある場合にのみ有効であることが保証されます。より多くのエラー訂正ビットを使用すると、より多くのエラーを検出でき、場合によっては訂正できます。

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

チェックサム

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

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

巡回冗長検査

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

CRCには、バーストエラーの検出に適した特性がありますCRCはハードウェアでの実装が特に簡単であるため、コンピュータネットワークやハードディスクドライブなどのストレージデバイスで一般的に使用されます

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

暗号化ハッシュ関数

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

エラー訂正コード

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

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

アプリケーション

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

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

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

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

信頼性と検査エンジニアリングも、エラー訂正コードの理論を利用しています。[13]

インターネット

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

深宇宙通信

エラー訂正コードの開発は、惑星間距離での信号電力の極端な希薄化と宇宙探査機での限られた電力利用可能性のために、深宇宙ミッションの歴史と密接に結びついていました。初期のミッションではデータがコード化されずに送信されていましたが、1968年以降、デジタルエラー訂正は(最適にデコードされていない)畳み込みコードリードマラーコードの形式で実装されました。[14]リード・マラー符号は、宇宙船が受けるノイズに非常に適しており(ベルカーブにほぼ一致、マリナー宇宙船に実装され、1969年から1977年のミッションで使用されました。

1977年に開始されたボイジャー1号ボイジャー2号のミッションは、木星土星からのカラーイメージングと科学情報を提供するように設計されました。[15]これによりコーディング要件が増加したため、宇宙船は、外側のゴレイ(24,12,8)コードと連結できる(最適にはビタビ復号された)畳み込みコードによってサポートされていました。Voyager 2クラフトは、リードソロモンコードの実装を追加でサポートしていました連結されたリード-ソロモン-ビタビ(RSV)コードは、非常に強力なエラー訂正を可能にし、天王星への宇宙船の延長された旅を可能にしましたネプチューン1989年にECCシステムがアップグレードされた後、両方の技術でV2RSVコーディングが使用されました。

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

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

衛星放送

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

データストレージ

エラー検出および訂正コードは、データストレージメディアの信頼性を向上させるためによく使用されます。[16] シングルビットエラーを検出できるパリティトラックは、1951年の最初の磁気テープデータストレージに存在しました。グループコード記録テープで使用される最適な長方形コードは、シングルビットエラーを検出するだけでなく修正します。一部のファイル形式、特にアーカイブ形式には、破損と切り捨てを検出するためのチェックサム(ほとんどの場合CRC32 )が含まれ、破損したデータの一部を回復するために冗長ファイルまたはパリティファイルを使用できます。リードソロモンコードコンパクトディスクで使用されます引っかき傷によって引き起こされたエラーを修正します。

最新のハードドライブは、リードソロモンコードを使用して、セクター読み取りのマイナーエラーを検出して修正し、障害のあるセクターから破損したデータを回復して、そのデータをスペアセクターに保存します。[17] RAIDシステムは、さまざまなエラー訂正技術を使用して、ハードドライブに完全な障害が発生したときにデータを回復します。ZFSBtrfsなどのファイルシステム、および一部のRAID実装は、データのスクラビングと再シルバー化をサポートします。これにより、不良ブロックを検出し、(うまくいけば)使用前に回復できます。[18]復元されたデータは、まったく同じ物理的な場所に書き換えたり、同じハードウェア上の別の場所にある予備のブロックに書き換えたり、交換用のハードウェアに書き換えたりすることができます。

エラー訂正メモリ

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

エラー訂正メモリコントローラーは、従来、ハミングコードを使用しますが、トリプルモジュラー冗長性を使用するものもありますインターリーブを使用すると、隣接するビットを異なる単語に関連付けることにより、単一の宇宙線の効果を複数の単語に物理的に隣接する複数のビットを混乱させる可能性があります。シングルイベントアップセット(SEU)が、アクセス間の特定のワードでエラーしきい値(たとえば、シングルエラー)を超えない限り、(たとえば、シングルビットエラー訂正コードによって)訂正できますエラーのないメモリシステムの錯覚が維持される可能性があります。[19]

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

も参照してください

参考文献

  1. ^ ab マソラ」。ジューイッシュエンサイクロペディア
  2. ^ プラティコ、ゲイリーD。; ペルト、マイルズV.ヴァン(2009)。聖書ヘブライ語文法の基礎:第2版ゾンダーヴァン。ISBN 978-0-310-55882-8
  3. ^ Mounce、William D.(2007)。私たちの残りのためのギリシャ語:聖書の言語を習得せずにギリシャ語のツールを使用するゾンダーヴァン。p。289. ISBN 978-0-310-28289-1
  4. ^ Mishneh Torah、Tefillin、Mezuzah、およびSefer Torah、1:2。英語訳の例: EliyahuTougerランバンのミシュネー・トーラーMoznaim PublishingCorporation
  5. ^ ブライアンM.フェイガン(1996年12月5日)。「死海文書」。考古学へのオックスフォードコンパニオンオックスフォード大学出版局ISBN 0195076184
  6. ^ Thompson、Thomas M.(1983)、エラー修正コードからスフィアパッキング、単純なグループまで、Carus Mathematical Monographs(#21)、The Mathematical Association of America、p。vii、ISBN 0-88385-023-0
  7. ^ Shannon、CE(1948)、 "A Mathematical Theory of Communication"、Bell System Technical Journal27(3):379–423、doi10.1002 / j.1538-7305.1948.tb01338.xhdl10338.dmlcz / 101429PMID 9230594 
  8. ^ Golay、Marcel JE(1949)、「デジタルコーディングに関する注記」、Proc.IRE(IEEE)37:657
  9. ^ グプタ、ビカス; ヴェルマ、チャンデルカント(2012年11月)。「エラー検出と訂正:はじめに」。コンピュータサイエンスとソフトウェア工学の先端研究の国際ジャーナル2(11)。S2CID17499858_ 
  10. ^ a b A. J. McAuley、バースト消去修正コードを使用した信頼性の高いブロードバンド通信、ACM SIGCOMM、1990。
  11. ^ フランクヴァンガーウェン。「数(および他の不思議な)ステーション」2012年3月12日取得
  12. ^ Gary Cutlack(2010年8月25日)。「不思議なロシアの「数字放送局」は20年後に放送を変更します」ギズモード2012年3月12日取得
  13. ^ ベンガルI .; Herer Y。; Raz T.(2003)。「検査エラー時の自己修正検査手順」(PDF)IIEトランザクション品質と信頼性に関するIIEトランザクション、34(6)、pp.529-540。2013-10-13にオリジナル(PDF)からアーカイブされました2014年1月10日取得
  14. ^ K. Andrews et al。、深宇宙アプリケーション用のターボおよびLDPCコードの開発、IEEEの議事録、Vol。95、No。11、2007年11月。
  15. ^ ハフマン、ウィリアム・ケアリー; Pless、Vera S.(2003)。エラー修正コードの基礎ケンブリッジ大学出版局ISBN 978-0-521-78280-7
  16. ^ Kurtas、Erozan M。; Vasic、Bane(2018-10-03)。データストレージシステムの高度なエラー制御技術CRCプレス。ISBN 978-1-4200-3649-7[永久リンク切れ]
  17. ^ スコットA.モールトン。「私のハードドライブが死んだ」2008-02-02にオリジナルからアーカイブされました。
  18. ^ Qiao、Zhi; フー、ソング; Chen、Hsing-Bung; Settlemyer、Bradley(2019)。「信頼性の高い高性能ストレージシステムの構築:経験的および分析的研究」。2019 IEEE International Conference on Cluster Computing(CLUSTER):1–10。土井10.1109 /CLUSTER.2019.8891006ISBN 978-1-7281-4734-5S2CID207951690 _
  19. ^ 「NanosatelliteのオンボードコンピュータでStrongArmSA-1110を使用する」清華宇宙センター、清華大学、北京。2011-10-02にオリジナルからアーカイブされました2009年2月16日取得
  20. ^ ジェフレイトン。「エラーの検出と訂正」LinuxMagazine2014年8月12日取得
  21. ^ 「EDACプロジェクト」bluesmoke.sourceforge.net 2014年8月12日取得
  22. ^ 「Documentation / edac.txt」Linuxカーネルのドキュメントkernel.org2014-06-16。2009年9月5日にオリジナルからアーカイブされました2014年8月12日取得

さらに読む

外部リンク