CRCで初歩的なエラー補正を行うことは可能ですか？

Question

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

Answer 1

CRCで単一ビットエラー修正を行うことができます。 CRCの「レジスタ」があり、CRCアルゴリズムを一度に少し前後に実行する機能があると仮定して、着信データを無視します

int crc_forward(int old_value, int data_bit)
{
  if (old_value & 0x8000)
    return ((old_value ^ 0x8000) SHL 1) ^ 0x1021 ^ data_bit;
  else
    return (old_value SHL 1) ^ data_bit;
}

int crc_reverse(int old_value)
{
  if (old_value & 1)
    return (old_value SHR 1) ^ 0x8810;
  else
    return old_value SHR 1;
}

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

このアプローチは、NAND Flashなどのソフトウェアエラー修正に適している可能性があることに注意してください。ハードウェアエラー修正のために有用に使用するには、ECCを処理するまで読み取り操作を遅らせるか、「シンドローム」値とビット位置の表が必要になるまで読み取り操作を遅らせる必要があります。

Answer 2

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

1. エラーCRC = CRC_GOTTEN ^ CRC_EXPECTEDを計算します。
2. 可能なすべての1ビットメッセージ（つまり、すべて0S、A 1、およびすべての0S）（評価するメッセージ_Lengthケースがあります。これはバイトではないビットです）を調べ、エラービットはエラーCRCを生成するメッセージです。
3. 検出されたビットを反転させて、エラーを修正します。

エラーCRCに一致する1ビットが見つからない場合は、すべての2ビット、3ビットをHamming_distance-1まで見てください。これにより、速度が速くなり、Message_Lengthは2ビットで2倍になり、5ビットで5ビットまで3ビットまで立てられています。

Answer 3

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

これが基本的なアイデアです：

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

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