15

データを送信するとき、ハミング コードを使用すると、ネットワーク上で破損したデータ (エラー修正コード) を再作成できるようです。

これはどのように機能し、制限がある場合はどのような制限がありますか?

(再送信とは対照的に) エラー訂正のためのより良い解決策はありますか? 再送信の方がよい状況はありますか?

4

6 に答える 6

39

それを少し説明してみましょう：

3ビットの数字があります。可能性は、各ビットが軸を表す立方体として表すことができます。8つの可能性は隅にあります。

000 --------001
 | \         | \
 | 100---------101
 |  |        |  |
 |  |        |  |
010-|-------011 |
   \|          \|
   110---------111

各欠陥（たとえば、101は100として読み取られます）により、立方体の線がシフトします。

データに2ビットを使用し、パリティチェックに3番目のビットを使用する場合（たとえば、偶数パリティ）。4つのデータポイントが失われます。ただし、1ビットの障害を検出できるという利点があります（これにより、偶数の1が奇数の1に変換されます）。奇数は*でマークされています。そして、それぞれの奇数の（間違って送信された）単語が偶数の（正しく送信された）単語によって追い詰められていることがわかります。したがって、100を受け取った場合、それが間違っていると確信できます。

ただし、（1ビットの障害がある場合）正しい表現は000、101、または110である可能性があります。したがって、何かが間違っていることは検出できますが、何が間違っているかは検出できません。

 000 -------*001
  | \         | \
  |*100---------101
  |  |        |  |
  |  |        |  |
*010-|-------011 |
    \|          \|
    110--------*111

これは、1ビットエラー検出コードと呼ばれます。

チェックに別のビットを使用して、データ用に1つ削除した場合。1つのデータビットと2つの「チェックビット」が残っています。この場合、000と111が有効なデータ表現であり、他の6つは有効ではないと仮定します。輸送中に1ビットが壊れた場合、興味深い状況になります。000を送信して010を受信すると、010には1つの有効なネイバー（000）と2つの無効なネイバー（110と011）があることがわかります。これで、000を送信するつもりであり、それを修正できることがわかりました。

 000 -------*001
  | \         | \
  |*100--------*101
  |  |        |  |
  |  |        |  |
*010-|------*011 |
    \|          \|
   *110---------111

これは、1ビットエラー訂正コードと呼ばれます。

1ビットのエラー訂正コードは2ビットのエラー検出コードでもあることに注意してください。

そしてそれをより一般的に言えば。

チェックビットがn個ある場合は、ビットエラー検出コードがあります。2nのチェックビットがある場合は、ビットエラー訂正コードがあります。

もちろん、「有効な」コードを注文して、互いに隣接しないようにする必要があります。

于 2008-12-23T11:28:25.610 に答える
13

これが本当に高レベルの概要です。

Suppose that every time I send a message, I send thrie copies of the text.
Suppose that every time I send z message, I send three copies of the teyt.
Suppose that every tyme I send a message, I send three copies if the tezt.

文字を比較し、各位置で単純多数決を取ることで、1 つの間違った文字を修正できます。ただし、このスキームのコスト (送信する必要があるデータの量) は高く、異なるコピーの対応する位置にある2 つのエラー (上記のサンプルの最後の単語のように) という可能性は低いが可能性のあるケースを検出しません。 ）。

ハミング コード (およびリードソロモンなどの他の種類のエラー修正コード) は、(単純な複製ではなく) 余分なデータを計算する数式に基づいています。追加されたビットは、受信側で計算が繰り返されるときにコピーのエラーが検出可能な変化のパターンを作成する方法で、データ ビットの組み合わせに依存します。

説明のために、単純な奇数パリティから始めましょう。1 ビットを追加して、メッセージ内のビットの総数が確実に奇数になるようにします。したがって、メッセージ10110110は101101100(5 つの 1、余分な 1 は不要) になり、メッセージ10010110は100101101(4 つの 1、余分な 1 が必要) になります。のメッセージを受け取り、1011011011 が 6 つ表示されている場合は、エラーがあることはわかりますが、どこにあるのかわかりません。考慮されるビットをコピーし、無視されたビットに「-」を使用することによって以下に示すように、それぞれがメッセージの一部のみに依存するパリティビットをさらに追加するとします。

10110110
1-1-0-1- => 0
-0-1-1-0 =>  1
10--01-- =>   1
--11--10 =>    0
1011---- =>     0
----0110 =>      1

したがって、完全なメッセージは10110110011001. ここで、伝送エラーによってメッセージの 3 番目のビットが変更され、 が読み取られるとします10010110011001。受信者がエラー チェック計算を再実行すると、一致しなくなります。

10010110
1-0-0-1- => 1*
-0-1-1-0 =>  1
10--01-- =>   1
--01--10 =>    1*
1001---- =>     1*
----0110 =>      1

一致しないチェック ビットは、まさに 3 番目のデータ ビットの影響を受けるビットです。これは、実際の堅牢なエラー修正スキームではありません。これは、冗長性の構築がエラーの正確な性質を特定するのにどのように役立つかを示すための単なるスケッチです。

于 2008-12-23T13:58:17.897 に答える
5

詳しい操作方法はこちら

エラー修正コードに関する一般的な情報は、こちらから入手できます。

于 2008-12-23T10:45:14.730 に答える
3

ハミング コードに関する情報は、こことここで入手できます。

適合性に関しては、これが理由を説明しています：

  1. ハミングのようなエラー訂正コードは、再送信を要求できないシンプレックス チャネルに適しています。

  2. エラー検出と再送信は、より効率的であるため、多くの場合好まれます。

比較のために、ビットあたりのエラー率が のチャネルを考えてみましょう。ブロックサイズを 1000 ビットとします。

(ハミング コードによって) 1 つのエラーを修正するには、ブロックごとに 10 のチェック ビットが必要です。1000 ブロックを送信するには、10,000 チェック ビット (オーバーヘッド) が必要です。1 つのエラーを検出するには、ブロックごとに 1 つのパリティ ビットで十分です。1000 ブロックを送信するには、(ビットあたりのエラー率により) 1 つの外部ブロックのみを再送信する必要があり、オーバーヘッドは 2001 (= 1000 + 1001) ビットだけになります。

于 2008-12-23T11:05:24.250 に答える
0

ハミングコードは、シリアル伝送で最大4ビットの損失を修正するための数学的トリックです。また、最新のメモリチップの「パリティビット」を優先して使用されます。

復元できるビット数には制限があり、4ビット以下です。4ビット以上失われた場合は、再送が必要です。

状況が異なれば、エラー訂正技術も異なります。これらのテクニックのいくつかは、ここの他の投稿にリストされています。

于 2008-12-23T11:22:32.703 に答える
0

@GameCat と 2 ビット エラー検出コードについて。

この場合、111 が 100 に変更されたとします。111 と 100 の間の距離は 2 ビットであり、000 と 100 の距離は 1 ビットであるため、2 ビットの誤りがあることがわかります。したがって、2 ビット エラーがあることがわかっている場合は、正しい値を確認できます。

于 2010-03-08T15:50:57.033 に答える