1

そのため、この夏のプロジェクトでハミングコードを使用したメッセージ送信のエラーを修正したいのですが、実際にどのように機能するのか理解できません。私はオンラインで多くの記事を読みましたが、アルゴリズムを本当に理解していません。誰かがそれを簡単な言葉で説明できますか？

ありがとう。

4

3 に答える 3

9

それはすべてハミング距離についてです。

2つの2進数値の間のハミング距離は、それらが異なるビット数です。したがって、Aを送信しても、Bを受信した場合、送信で切り替えられたはずのビット数は、AとBの間のハミング距離になります。

ハミングコードは、各コードワードのビットが何らかの方法で別々に送信される場合に役立ちます。シリアルかパラレルかは関係ありませんが、たとえば、数ビットを表すアナログ値に結合されたり、エンコード後に圧縮/暗号化されたりすることはありません。

したがって、各ビットは独立して（一定の確率でランダムに）受信されるか、反転されます。送信がかなり信頼できると仮定すると、ほとんどのビットは正しく受信されます。したがって、少数のビットでエラーが発生する可能性が高く、多数のビットで同時にエラーが発生する可能性は低くなります。

したがって、ハミングコードは通常、1ビットエラーを修正したり、2ビットエラーを検出したりすることを目的としています（2つの主要なタイプの詳細については、ウィキペディアの記事を参照してください）。より大きなエラーを修正/検出するコードを作成することはできますが、AFAIKはあまり使用されていません。

このコードは、「ハミングスペース」のコードポイントを均等に配置することで機能します。これは、数学的には、ハミング距離をメトリックとして、関連するワードサイズのすべての値で構成される距離スペースです。各コードポイントが無効な値の小さな「バッファゾーン」に囲まれていると想像してください。コードポイントではない値を受信した場合は、有効なコードポイントのみが送信されるため、エラーが発生している必要があります。

バッファゾーンの値を受信した場合、1ビットエラーが発生したと仮定すると、送信された値は受信した値から1の距離にある必要があります。ただし、コードポイントが分散しているため、閉じるコードポイントは1つだけです。したがって、1ビットエラーは、他のコードポイントが受け取った値を生成するために必要となるより大きなエラーよりも可能性が高いという理由で、そのコードポイントに「修正」されます。確率の観点から、近くのコードポイントを送信した条件付き確率は、私が行った値を受け取った場合、他のコードポイントを送信した条件付き確率よりも大きくなります。ですから、送信の信頼性と各ワードのビット数に基づいて一定の自信を持って、近くのものを送信したと思います。

2つのコードポイントから等距離にある無効な値を受け取った場合、一方が他方よりも真の値である可能性が高いとは言えません。そのため、エラーを検出しましたが、修正できません。

明らかに、3ビットエラーはSECDEDハミングコードでは修正されません。受信した値は、他のコードポイントよりも実際に送信した値から離れているため、誤って間違った値に「修正」しました。したがって、それらを気にしないほど信頼性の高い伝送が必要であるか、またはより高レベルのエラー検出（たとえば、メッセージ全体に対するCRC）も必要です。

于 2009-04-16T19:23:05.540 に答える
2

具体的にはウィキペディアから、アルゴリズムは次のとおりです。

  1. 1から始まるビットに番号を付けます：ビット1、2、3、4、5など。
  2. ビット番号を2進数で書き込みます。1、10、11、100、101など。
  3. 2の累乗であるすべてのビット位置（それらの位置のバイナリ形式で1ビットのみを持つ）はパリティビットです。
  4. 他のすべてのビット位置は、それらの位置のバイナリ形式で2つ以上の1ビットを持ち、データビットです。
  5. 各データビットは、そのビット位置のバイナリ形式によって決定されるように、2つ以上のパリティビットの一意のセットに含まれます。
    1. パリティビット1は、最下位ビットが設定されているすべてのビット位置をカバーします。ビット1（パリティビット自体）、3、5、7、9などです。
    2. パリティビット2は、2番目に最下位ビットが設定されているすべてのビット位置をカバーします。ビット2（パリティビット自体）、3、6、7、10、11などです。
    3. パリティビット4は、3番目に最下位ビットが設定されているすべてのビット位置（ビット4〜7、12〜15、20〜23など）をカバーします。
    4. パリティビット8は、4番目に最下位ビットが設定されているすべてのビット位置（ビット8〜15、24〜31、40〜47など）をカバーします。
    5. 一般に、各パリティビットは、パリティ位置とビット位置の2進数のANDがゼロ以外のすべてのビットをカバーします。
于 2009-04-16T19:07:35.140 に答える
0

ウィキペディアの記事はそれを非常にうまく説明しています。

アルゴリズムの特定の側面を理解していない場合は、誰かが問題の特定の部分に対処できるように、質問を言い換える（または詳細にする）必要があります。

于 2009-04-16T18:26:48.530 に答える