エラーの検出と訂正

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

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

定義

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

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

歴史

古典古代では、copyistsヘブライ語聖書は、数に応じて自分の仕事のために支払われたstichs(詩の行)。聖書の散文本はほとんどスティッチで書かれていなかったので、写字家は仕事の量を見積もるために文字を数えなければなりませんでした。[1]これはまた、後続のコピーの作成でテキストの送信の正確さを保証するのに役立ちました。[2] [3]西暦7世紀から10世紀の間に、ユダヤ人の書記のグループがこれを形式化して拡張し、数値マソラを作成しました。神聖なテキストの正確な複製を確実にするため。これには、行、セクション、本、および本のグループ内の単語数のカウント、本の中間のステッチ、単語使用統計、および解説が含まれていました。[1]基準は、トーラーの巻物の1文字でも逸脱が許容できないと見なされるようになりました。[4]は、それらのエラー訂正方法の有効性の発見によって実証世紀を通してコピーの精度によって確認した死海文書1947から1956で、c.150 BCE-75 CEからデート。[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 10101010」は正しいものとして検出されます)。反復コードの利点は、それらが非常に単純であり、実際に番号局の一部の送信で使用されることです。[11] [12]

パリティビット

A parity bit is a bit that is added to a group of source bits to ensure that the number of set bits (i.e., bits with value 1) in the outcome is even or odd. It is a very simple scheme that can be used to detect single or any other odd number (i.e., three, five, etc.) of errors in the output. An even number of flipped bits will make the parity bit appear correct even though the data is erroneous.

Parity bits added to each "word" sent are called transverse redundancy checks, while those added at the end of a stream of "words" are called longitudinal redundancy checksたとえば、一連のmビットの「ワード」のそれぞれにパリティビットが追加され、そのワードに奇数または偶数の1があったかどうかを示す場合、エラーが1つあるワードが検出されます。ただし、エラーが単語のどこにあるかはわかりません。さらに、nワードの各ストリームの後にパリティ合計が送信され、その各ビットが、最新のグループで送信されたそのビット位置に奇数または偶数の1があったかどうかを示す場合、エラーの正確な位置決定し、エラーを修正することができます。ただし、この方法は、n語のすべてのグループに1つ以下のエラーがある場合にのみ有効であることが保証されます。より多くのエラー訂正ビットを使用すると、より多くのエラーを検出でき、場合によっては訂正できます。

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

チェックサム

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

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

巡回冗長検査

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

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

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

暗号化ハッシュ関数

メッセージダイジェストとも呼ばれる暗号化ハッシュ関数の出力は、データの変更が偶発的(たとえば、送信エラーによる)であるか、悪意を持って導入されたかにかかわらず、データの整合性に関する強力な保証を提供できます。データへの変更は、ハッシュ値の不一致によって検出される可能性があります。さらに、あるハッシュ値が与えられると、同じハッシュ値を生成するいくつかの入力データ(与えられたもの以外)を見つけることは通常実行不可能です。攻撃者がメッセージだけでなくハッシュ値も変更できる場合は、キー付きハッシュまたはメッセージ認証コード (MAC) can be used for additional security. Without knowing the key, it is not possible for the attacker to easily or conveniently calculate the correct keyed hash value for a modified message.

Error correction code

Any error-correcting code can be used for error detection. A code with minimum Hamming distance, d, can detect up to d − 1 errors in a code word. Using minimum-distance-based error-correcting codes for error detection can be suitable if a strict limit on the minimum number of errors to be detected is desired.

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

アプリケーション

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

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

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

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

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

インターネット

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

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

深宇宙通信

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

The Voyager 1 and Voyager 2 missions, which started in 1977, were designed to deliver color imaging and scientific information from Jupiter and Saturn.[15] This resulted in increased coding requirements, and thus, the spacecraft were supported by (optimally Viterbi-decoded) convolutional codes that could be concatenated with an outer Golay (24,12,8) code. The Voyager 2 craft additionally supported an implementation of a Reed–Solomon code. The concatenated Reed–Solomon–Viterbi (RSV) code allowed for very powerful error correction, and enabled the spacecraft's extended journey to Uranus and Neptune. After ECC system upgrades in 1989, both crafts used V2 RSV coding.

The Consultative Committee for Space Data Systems currently recommends usage of error correction codes with performance similar to the Voyager 2 RSV code as a minimum. Concatenated codes are increasingly falling out of favor with space missions, and are replaced by more powerful codes such as Turbo codes or LDPC codes.

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

衛星放送

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

データストレージ

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

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

エラー訂正メモリ

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

Error-correcting memory controllers traditionally use Hamming codes, although some use triple modular redundancy. Interleaving allows distributing the effect of a single cosmic ray potentially upsetting multiple physically neighboring bits across multiple words by associating neighboring bits to different words. As long as a single-event upset (SEU) does not exceed the error threshold (e.g., a single error) in any particular word between accesses, it can be corrected (e.g., by a single-bit error-correcting code), and the illusion of an error-free memory system may be maintained.[19]

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

も参照してください

参考文献

  1. ^ B "Masorah"。ジューイッシュエンサイクロペディア
  2. ^ Pratico、Gary D。; ペルト、マイルズV.ヴァン(2009)。聖書ヘブライ語文法の基礎:第2版ゾンダーヴァン。ISBN 978-0-310-55882-8
  3. ^ Mounce、William D.(2007)。私たちの残りのためのギリシャ語:聖書の言語を習得せずにギリシャ語のツールを使用するゾンダーヴァン。NS。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. ^ シャノン、CE(1948)、「通信の数学的理論」、ベルシステムテクニカルジャーナル27(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)。S2CID 17499858 
  10. ^ a b A. J. McAuley、バースト消去修正コードを使用した信頼性の高いブロードバンド通信、ACM SIGCOMM、1990。
  11. ^ フランクヴァンガーウェン。「数(および他の不思議な)ステーション」取得した3月12日に2012
  12. ^ Gary Cutlack(2010年8月25日)。「謎のロシアの「ナンバーズステーション」が20年後に放送を変更」ギズモード取得した3月12日に2012
  13. ^ ベンガルI .; ヘラーY .; Raz T.(2003)「検査エラー時の自己修正検査手順」(PDF)IIEトランザクション品質と信頼性に関するIIEトランザクション、34(6)、pp.529-540。2013-10-13にオリジナル(PDF)からアーカイブされまし取得した2014年1月10日を
  14. ^ K. Andrews et al。、 The Development of Turbo and LDPC Codes for Deep-Space Applications、Proceedings of the 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-5S2CID  207951690
  19. ^ 「ナノサテライトのオンボードコンピューターでStrongArmSA-1110を使用する」清華宇宙センター、清華大学、北京。2011-10-02にオリジナルからアーカイブされまし2009年216日取得
  20. ^ ジェフレイトン。「エラーの検出と訂正」LinuxMagazine取得した2014年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日を

さらに読む

外部リンク