1

エラー検出について読んでいて、よくわからない文に出くわしました。ステートメントは、「kビット文字列の場合、2ビットエラーを検出するにはlg kパリティビットが必要です」と述べています。ここで、lgはベース2への対数です

なぜこれが本当なのかよくわかりませんでした.これを確認する正式な派生物はありますか.

本の名前は Gallahager の Data Networks です。

私はその本が言っていることを疑っていませんが、派生物を見るのに十分興味があります.

ありがとう、チャンダー

4

2 に答える 2

1

Cyclic Redundancy Checkのウィキペディアのページを見てください。厳密に言えば、パリティ ビットは 1 ビットのチェックなので、1 つ以上のパリティ ビットについて話すことは、おそらく同等の CRC の省略形です。記事「CRC の数学」では、導出について詳しく説明しています。

于 2010-09-22T09:25:58.647 に答える
0

用語

  • 「線形」コード (CRC、ハミング コードなど) の場合、各データ ビットは常に、パリティ ビットの一部 (すべてではない) の固定セットに影響します。たとえば、データのビット 7 (のみ) が転送中に反転され、パリティ ビット 2 と 4 が反転され、パリティ ビット 5 が反転されない場合、再計算されたパリティ ビットでは、受信時のパリティ ビットと比較して、反転します。データのビット 7 は、パリティ ビット 2 と 4 を反転させますが、ペイロード データ ビットの可能なフレームごとにパリティ ビット 5 を反転させません。
  • 特定のパリティ ビット (パリティ ビット 5 など) に影響を与えるペイロード内のすべてのビットと、そのパリティ ビット自体は、そのパリティ ビットによって「カバー」または「保護」されていると言われます。

  • 受信側がパリティ ビットを再計算し、再計算されたパリティ ビットと受信したパリティ ビットを比較すると、その差がシンドロームと呼ばれます。エラーがなかった場合、シンドロームはゼロです。

    In other words, syndrome = recalculated_parity XOR recieved_parity.

証拠

ペイロード データ ビットの 2^n ビット フレームで 2 ビット エラーを検出するには、n パリティ ビットが必要であるという証明:

フレーム全体でエラーが 1 つしかない場合、受信機がパリティ ビットを再計算するとき、次の 2 つのケースがあります。

  • エラーのあるビットをカバーしない再計算された各パリティ ビットは、対応する受信パリティ ビットと同じです。(シンドロームの対応するビットは「0」です)。
  • エラーのあるビットをカバーする再計算された各パリティ ビットは、対応する受信パリティ ビットとは異なり、エラーが検出されます。(シンドロームの対応するビットは「1」です)。

フレーム全体に正確に 2 つのエラーがある場合、結果として得られるシンドロームは、各エラーが単独で発生したシンドロームの XOR です。受信機がパリティ ビットを再計算する場合、次の 3 つのケースがあります。

  • (a) どちらの誤りビットもカバーしない再計算された各パリティ ビットは、対応する受信パリティ ビットと同じです。(シンドロームの対応するビットは「0」です)。
  • (b)両方のエラー ビットをカバーする再計算された各パリティ ビットは、対応する受信パリティ ビットと同じです。(各エラーはそのようなビットを 1 回フリップし、両方のフリップを組み合わせてそのビットを元の状態に戻すため、シンドローム内の対応するビットは「0」です)。
  • (c) 1 つのエラー ビットをカバーし、他のエラー ビットをカバーしない再計算された各パリティ ビットは、対応する受信パリティ ビットとは異なり、エラーが検出されます。(シンドロームの対応するビットは「1」です)。

仮に、反転すると何らかのシンドローム S が生成されるようなペイロード ビットが存在し、まったく同じシンドローム S を生成する他のペイロード ビットが存在する場合、これらのビットの両方にヒットする 2 ビット エラーは検出できません。言い換えれば、その 2 ビット エラーは のシンドロームを与えることになりS xor S == zeroます。つまり、各パリティはケース (a) またはケース (b) のいずれかであり、どちらもそのようなエラーを検出することはできません。それは悪いでしょう。

したがって、フレーム内のすべての 2 ビット エラーを検出するには、各シングル ビット エラーが異なるシンドロームを生成するようにエラー検出コードを設計する必要があります。つまり、フレーム内の 2 つのエラー ビットのすべての可能なケースに対して、タイプ (c) の少なくとも 1 つのパリティ ビットが存在する必要があります。

n パリティ ビットを使用すると、n シンドローム ビットが得られます。n シンドローム ビットでは、最大 2^n の異なるシンドロームが存在します。したがって、フレーム内の各ビット (それが唯一のエラーである場合) が異なるシンドロームを与えるようにするには、フレーム内に最大で 2^n ビットが必要です。

この質問をhttps://math.stackexchange.com/に投稿した場合、はるかに短く、よりエレガントな証明が得られるでしょう:-)。

于 2013-05-31T04:24:33.127 に答える