17

CRCを使用する意図はエラー検出を行うことであることは知っていますが、エラー検出に加えて基本的なエラー訂正を行うために使用できると誰かが言っているのを聞きました。私はこれが事実であるかどうか興味がありました、そしてもしそうなら、それはどれくらい強力ですか？つまり、通常、CRCはxビット検出を実行できると言いますが、CRCがxビット補正を実行できるかどうか知りたいです。もしそうなら、これはどのように機能しますか？ありがとう。

4

4 に答える 4

14

CRCを使用してシングルビットエラー訂正を行うことができます。1つにCRC「レジスタ」があり、着信データを無視して、CRCアルゴリズムを一度に少しずつ前後に実行する関数があると仮定します。

int crc_forward（int old_value、int data_bit）
{{
  if（old_value＆0x8000）
    return（（old_value ^ 0x8000）SHL 1）^ 0x1021 ^ data_bit;
  そうしないと
    return（old_value SHL 1）^ data_bit;
}

int crc_reverse（int old_value）
{{
  if（old_value＆1）
    return（old_value SHR 1）^ 0x8810;
  そうしないと
    old_valueSHR1を返します。
}

crcをある値に初期化し、各ビットに対してcrc_forwardを実行すると（MSBが最初）ゼロになるように計算されたパケットがあるとします。ゼロ以外のCRC値を取得した場合、計算されたCRC値が1になるまで、アルゴリズムを逆に（データビットを無視して）実行できます。これは、誤ったビットの場所です。

このアプローチは、NANDフラッシュなどのソフトウェアエラー訂正に適している場合があることに注意してください。ハードウェアエラー訂正にこれを有効に使用するには、ECCが処理されるまで読み取り操作を遅らせることができるか、そうでない場合は「シンドローム」値とビット位置のテーブルが必要になります。

于 2011-05-29T19:13:12.267 に答える
8

CRCを使用してマルチビットエラー訂正を行うことができます。ウィキペディアを見ると、koopmansの動作を参照して、CRCはhamming_distance-1エラーを検出できます。ハミング距離は、ペイロードの長さと使用中のCRC多項式によって異なります。したがって、たとえば、0xBA0DC66BのKoopmans多項式は、最大16360ビット長のメッセージで最大5ビットのエラーを検出できます。前の2つのメッセージで説明したアルゴリズムは、必要な数のビットまで拡張できますが、修正するビット数に応じて時間は指数関数的に増加します。

  1. エラーCRC=CRC_gotten^CRC_expectedを計算します。
  2. 考えられるすべての1ビットメッセージ（つまり、すべて0、1、およびすべて0）（評価するmessage_lengthの場合があります。これはBYTESではなくBITSであることに注意してください）を調べ、エラービットはエラーCRCを生成するメッセージです。
  3. 検出されたビットを反転してエラーを修正します。

エラーCRCに一致する1ビットが見つからない場合は、hamming_distance-1までのすべての2ビット、3ビットを調べてください。これは遅くなることに注意してください。message_lengthは2ビットの場合は二乗、3ビットの場合は3乗、5ビットの場合は5乗になります。

于 2015-01-09T17:12:24.617 に答える
5

私は最近、CRC16エラー検出とシングルビットエラー訂正に取り組みました。

基本的な考え方は次のとおりです。

  1. シングルビットエラーがあると仮定します。
  2. data + crcにエラーが含まれていない場合、CRCは0になり、そうでない場合はそうではありません。
  3. 送信されたCRCをCRCとして定義し、受信したCRCをCRCrとして定義します。
  4. 次に、エラービットはによって与えられCRCox = CRCs ^ CRCrます。
  5. 結果には、CRCエラーとデータエラーの両方が含まれます。
  6. CRCoxとビットエラーの関係を見てください。

これは明らかですか？これについての論文があります。もっと知りたい場合は、私に知らせてください。

于 2011-12-21T09:30:45.967 に答える
1

遅い答えですが、CRC32多項式

0x1f1922815 (= 0x787 * 0x557 * 0x465 * 0x3 * 0x3)

1024ビット（992ビットデータ、32ビットCRC）メッセージの最大7ビットエラーを検出し、最大3ビットエラーを修正できます。comb（1024,1）+ comb（1024,2）+ comb（1024,3）=178957824の修正可能なビットエラーパターンがあります。1431662592バイトテーブル（178957824 * 8 =〜1.4 GB）に十分なメモリがある場合、考えられるすべての1、2、および3ビットエラーCRCが生成され、そのテーブルに格納されます。各エントリは次のようになります。32ビットCRC 、2ビットエラーカウント、およびビットエラー位置用の3つの10ビットフィールド。

次に、テーブルがソートされ、CRCをチェックするときに、それが不良である場合、テーブルのバイナリ検索（最大28ループ）で、それが1、2、または3ビットエラーの場合であるかどうかを判断し、格納されているインデックスを使用して修正できます。テーブルで。

ただし、5ビット以上のエラーで誤訂正される可能性があります。ある5エラービットパターンが3エラービットパターンと同じCRCを生成する場合、間違った3ビットが変更され、有効なCRCを持っているように見える8ビットエラーが発生します。

サンプルコードへのリンク：

https://github.com/jeffareid/misc/blob/master/crccor3.c

于 2020-06-04T18:10:27.690 に答える