ハミング距離とは何ですか? CRC スキームのハミング距離はどのように決定すればよいですか?

Question

コンピュータ ネットワークの授業の勉強中に、教授はサンプル コード内の 2 つの有効なコード ワード間のハミング距離について話しました。ハミング距離について読んだことがありますが、2本の弦間の距離の差を伝えるという観点からは理にかなっています。例えば：

Code Word 1 = 10110 

送信者がコード ワード 1 を送信すると、エラーが発生し、受信者は 10100 を受信します。したがって、4 番目のビットが破損していることがわかります。次の理由により、ハミング距離は 1 になります。

Valid Code Word: 10110
Error Code Word: 10100
                 -----
XOR              00010

2 つの文字列の XOR の結果は 1 になり、ハミング距離は 1 になります。そこまでは理解しています。しかし、教授はこう尋ねます。

• 標準 CRC-16 ビット プロトコルのハミング距離はどれくらいですか?
• 標準 CRC-32 ビット プロトコルのハミング距離はどれくらいですか?

私は少し混乱しており、誰かが助けてくれないかと思っていました。ありがとう。

Answer 1

あなたはおそらく今ではそれを考え出したが、何彼が尋ねたことは、最も可能性の高いCRCコードを検出しないだろうとビットエラーの最小数でした。答えは幅、多項式とメッセージの長さに依存します。例えば、最もよく知られているCRC-32（0x1EDC6F41）多項式は6以上5275ビット（Castaglioni、ブラウアー、ヘルマンまでのメッセージのためのハミング距離を有する：24と32パリティビットと巡回冗長検査符号の最適化、IEEE 5275ビット以下の単一のメッセージで5反転ビットまで検出することが保証されている通信手段、容量41ない6、1993年6月）にトランザクション

ところで、コードワードはチェックサムが含まれているので、あなたの例が間違っています。