2

8 ビット以下の追加データを使用して、33 バイト メッセージの最初の 32 バイトで発生する可能性のあるビット フリップを 1 つ検出するためのエラー検出スキームを提案していただけますか?

ピアソンハッシュは解決策になるでしょうか?

4

3 に答える 3

7

メッセージ内の単一のビットフリップを検出するには、メッセージの長さに関係なく、追加のビットが1つだけ必要です。メッセージ内のすべてのビットをXORして、最後にタックします。いずれかのビットが反転すると、最後のパリティビットが一致しなくなります。

どのビットが反転したかを検出するように求めている場合、それは実行できません。単純な引数はそれを示しています。余分な8ビットは最大256クラスの32バイトメッセージを表すことができますが、ゼロメッセージと256メッセージはビットごとに1つずつ、すべて異なるクラスに属している必要があります。したがって、明確に分類する必要のあるメッセージは257個あり、クラスは256個だけです。

于 2011-08-26T01:37:29.047 に答える
5

任意の長さのメッセージで 1 つの余分なビットで 1 つのビット フリップを検出できます (@Daniel Wagner が述べているように)。パリティビットは、簡単に言えば、1ビットの総数が奇数か偶数かを示すことができます。明らかに、間違っているビットの数が偶数の場合、パリティ ビットは失敗するため、2 ビット エラーを検出することはできません。

ここで、32 バイト (256 ビット) をわずか 8 ビットでエラー訂正できない理由を理解しやすくするために、(ECC メモリで使用されるような)ハミング コードについてお読みください。このようなスキームは、ビットの総数のサブセットのパリティのみをエンコードする特別なエラー訂正パリティ ビット (以降、「EC パリティ」と呼ばれます) を使用します。合計ビットごとに、 EC ビット2^m - 1を使用する必要があります。mこれらは、「x ビットがオン、x ビットがオフ」というパターンに従って、考えられるそれぞれの異なるマスクを表します。ここxで、 は 2 のべき乗です。したがって、一度にビット数が多いほど、得られるデータ/パリティ ビットの比率が高くなります。たとえば、合計 7 ビットでは、3 EC ビットを失った後に 4 データ ビットしかエンコードできませんが、合計 31 ビットでは、5 EC ビットを失った後に 26 データ ビットをエンコードできます。

さて、これを本当に理解するには、おそらく例を挙げるでしょう。次の一連のマスクを検討してください。最初の 2 行は、ビット番号 (MSB とラベル付けした「最上位バイト」) を示すトップダウンで読み取られます。

  MSB                                LSB
   |                                  |
   v                                  v
   33222222 22221111 11111100 0000000|0
   10987654 32109876 54321098 7654321|0
   -------- -------- -------- -------|-
1: 10101010 10101010 10101010 1010101|0
2: 11001100 11001100 11001100 1100110|0
3: 11110000 11110000 11110000 1111000|0
4: 11111111 00000000 11111111 0000000|0
5: 11111111 11111111 00000000 0000000|0

最初に注目すべきことは、0 から 31 のバイナリ値が各列で右から左に表されていることです (行 1 から 5 のビットを読み取ります)。これは、各縦列が互いに異なることを意味します (重要な部分)。特定の理由から、ビット番号 0 と 1 の間に垂直の余分な線を入れました。列 0 にはビットが設定されていないため、役に立ちません。

エラー訂正を実行するには、受信したデータ ビットを各 EC ビットの事前定義されたマスクに対してビットごとに AND し、結果のパリティを EC ビットと比較します。計算されたパリティが一致しないことが判明した場合は、それらのビットのみが設定されている列を見つけます。たとえば、受信したデータ値から計算したときにエラー訂正ビット 1、4、および 5 が間違っている場合、これらのマスクのみに 1 を含む列 #25 は間違ったビットである必要があり、反転することで訂正できます。 . エラー訂正ビットが 1 つだけ間違っている場合、エラーはそのエラー訂正ビットにあります。これが機能する理由を理解するのに役立つアナロジーを次に示します。

32 個の同一のボックスがあり、そのうちの 1 つにビー玉が入っています。あなたの仕事は、古いスタイルのはかり (異なる物体の重さを比較するための 2 つのバランスのとれた台を備えた種類のもの) だけを使用してビー玉の位置を特定することであり、5 回の計量試行のみが許可されます。解決策はかなり簡単です。スケールの両側に 16 個のボックスを配置し、重い側がビー玉がどちら側にあるかを示します。軽い側の 16 個の箱を捨て、重い方を維持したまま 8 個と 8 個の箱の重さを量り、次に 4 個と 4 個、次に 2 個と 2 個の重さを量り、最後に最後の 2 個の箱の重さを 1 対 1 で比較してビー玉の位置を特定します。ボックスには大理石が入っています。32、16、8、4、2 箱の 5 回の計量でタスクを完了しました。

同様に、ビット パターンはボックスを 5 つの異なるグループに分割しました。さかのぼって、5 番目の EC ビットは、エラーが左側にあるか右側にあるかを決定します。ビット #25 のシナリオでは、これは間違っているため、エラー ビットがグループの左側 (ビット 16 ～ 31) にあることがわかります。EC ビット #4 の次のマスク (まだ後退) では、ビット 16 から 31 のみを考慮し、「重い」側が再び左側であることがわかり、ビット 24 から 31 を絞り込みました。決定木を下にたどり、可能な列の数を毎回半分に減らして、EC ビット 1 に到達するまでに、可能なビットは 1 つしか残っていません。つまり、「箱の中の大理石」です。

注: この類推は役に立ちますが、完全ではありません。1 ビットはビー玉で表されません。エラー ビットの位置はビー玉で表されます。

ここで、これらのマスクをいじり、どのように配置するかを考えてみると、問題があることがわかります。31 ビットすべてをデータ ビットにしようとすると、EC 用にさらに 5 ビットが必要になります。しかし、EC ビット自体が間違っているかどうかをどのように判断するのでしょうか? EC ビットが 1 つ間違っているだけで、一部のデータ ビットを修正する必要があると誤って伝えられ、そのデータ ビットを誤って反転させてしまいます。EC ビットは、どうにかして自分自身をエンコードする必要があります。解決策は、1 ビットのみが設定されている上記のビット パターンの列に、データ内のパリティ ビットを配置することです。このように、データビットが間違っていると2つがトリガーされますこれにより、EC ビットが 1 つだけ間違っていても、データ ビットが間違っていることを示すのではなく、それ自体が間違っていることがわかります。1 ビット条件を満たす列は 1、2、4、8、および 16 です。データ ビットは、位置 2 から始まるこれらの間でインターリーブされます。 -- EC ビットはまったく設定されません)。

最後に、全体的なパリティにもう 1 ビットを追加すると、2 ビット エラーを検出し、1 ビット エラーを確実に訂正できるようになります。これは、EC ビットとそれを比較できるためです。 、2 ビット間違っていることがわかっており、修正を実行できません。破棄されたビット #0 をパリティ ビットとして使用できます。実際、現在、次のパターンをエンコードしています。

0: 11111111 11111111 11111111 11111111

これにより、最終的に合計 6 個のエラー チェックおよび訂正 (ECC) ビットが得られます。異なるマスクを無期限に使用するスキームを拡張すると、次のようになります。

32 bits - 6 ECC bits = 26 data
64 bits - 7 ECC bits = 57 data
128 bits - 8 ECC bits = 120 data
256 bits - 9 ECC bits = 247 data
512 bits - 10 ECC bits = 502 data

ここで、1 ビット エラーのみが発生することが確実な場合は、#0 パリティ ビットを省略することができるため、次のようになります。

31 bits - 5 ECC bits = 26 data
63 bits - 6 ECC bits = 57 data
127 bits - 7 ECC bits = 120 data
255 bits - 8 ECC bits = 247 data
511 bits - 9 ECC bits = 502 data

これ以上データ ビットを取得しないため、これは変更されません。おっとっと！あなたが要求した 32 バイト (256 ビット) は、最悪でも 1 ビットのエラーしか発生しないことがわかっていても、1 バイトでエラー訂正することはできず、ECC ビットが正しいことがわかっています(それらを移動できるデータ領域の外に置き、それらすべてをデータに使用します)。256 データ ビットを取得するには、次の範囲の 512 ビットまでスライドして、246 データ ビットを除外する必要があります。つまり、ECC ビットが 1 つ、データ ビットが 1 つ増えます (255 個しかないため、Daniel が言ったこととまったく同じです)。

要約:: 最初の 32 バイトで反転したビットを検出するには、33 バイト + 1 ビットが必要です。

注: 64 バイトを送信する場合は、わずか 10 ビットでエラーを修正できるため、32:1 の比率を下回っています。しかし、実際のアプリケーションでは、ECC の「フレーム サイズ」はいくつかの理由で無期限に増加し続けることはできません。全体的な非効率性 (ECC RAM を考えてください)。2) フレームが大きくなればなるほど、より多くのエラーが発生する可能性が高くなるため、ビットを正確に修正できる可能性はますます低くなり、2 つのエラーはエラー修正能力を無効にし、3 つ以上のエラーはエラーを無効にする可能性があります。・探知能力。3) エラーが検出されると、フレーム サイズが大きいほど、再送信する必要がある破損部分のサイズが大きくなります。

于 2012-12-27T07:41:01.723 に答える
1

ビットではなくバイト全体を使用する必要があり、エラーの検出のみが必要な場合、標準的な解決策は巡回冗長検査 (CRC)を使用することです。いくつかのよく知られた 8 ビット CRC から選択できます。

CRC の一般的な高速実装では、256 エントリのテーブルを使用して、一度に 1 バイトのメッセージを処理します。8 ビット CRC の場合、これはピアソンのアルゴリズムの特殊なケースです。

于 2011-08-26T07:11:09.557 に答える