information-theory - エラー訂正コードの上限

Question

dビットパケットを送信し、エラー訂正コード（d> r）用にさらにrビットを追加したい
場合、最大でいくつのエラーを見つけて訂正できますか？

Answer 1

送信したい長さ d ビットの 2^d 種類の異なるパケットがあります。それらに r ビットを追加すると、長さが d+r のコードワードになるため、送信できるコードワードは 2^d になります。受信機は、2^(d+r) 個の異なる受信ワード (エラーの可能性があるコードワード) を取得できます。問題は、これらの 2^(d+r) 受信ワードを 2^d コードワードにどのようにマッピングするかということです。

これは、コードの最小距離に帰着します。つまり、コードワードの各ペアについて、それらが異なるビット数を見つけ、それらの値の最小値を取ります。

最小距離が 3 だったとします。単語を受信し、それがコードワードの 1 つではないことに気付きました。つまり、エラーがあります。したがって、より優れたデコード アルゴリズムがないため、最初のビットを反転して、それがコードワードかどうかを確認します。そうでない場合は、裏返して次のものを裏返します。最終的に、コードワードを取得します。すべてのコードワードは 3 つの位置で異なるため、このコードワードが受信したワードに「最も近い」ことがわかります。別のコードワードに到達するには、受信したワードの 2 ビットを反転する必要があるためです。一度に 1 ビットだけ反転してコードワードを取得できなかった場合、2 ビットを反転することで取得できるコードワードが複数あるため、エラーがどこにあるかを特定することはできませんが、少なくとも 2 つのビットがあることはわかっています。エラー。

これは、最小距離 md で md-1 エラーを検出し、floor((md-1)/2) エラーを修正できるという一般原則につながります。最小距離の計算は、コードとも呼ばれるコードワードの生成方法の詳細に依存します。d と (d+r) に基づいて md の上限を計算するために使用できるさまざまな境界があります。

ポールはハミングコードに言及しましたが、これは良い例です。ハミング限界を達成しています。(7,4) ハミング コードの場合、4 ビットのメッセージと 7 ビットのコードワードがあり、最小距離 3 を達成します。明らかに*、追加するビット数よりも大きな最小距離を得ることは決してありません。これがあなたにできる最善のことです。ただし、これに慣れすぎないでください。ハミング コードは、非自明な完全コードの数少ない例の 1 つであり、それらのほとんどの最小距離は、追加したビット数よりも小さくなります。

*それはあまり明白ではありませんが、重要なエラー修正コードについては正しいと確信しています。パリティ ビットを 1 つ追加すると、最小距離が 2 になり、エラーを検出できるようになります。{000,111} で構成されるコードでは、わずか 2 ビットを追加するだけで最小距離 3 が得られますが、それは些細なことです。

Answer 2

おそらく、これに関するウィキペディアのページを読む必要があります。

http://en.wikipedia.org/wiki/Error_detection_and_correction

特にハミングコードが必要なようです：

http://en.wikipedia.org/wiki/Hamming_code#General_algorithm

そのスキームを使用して、リンクされたテーブルからいくつかの例の値を検索できます。