こんにちは、ぽたです。今回は、ハミング符号のハミング距離と誤り訂正能力について書いていこうと思います。
ハミング符号とは
ハミング符号とは、データの誤りを検出、訂正することができる符号の一つです。
詳しいことは、
こちらに載せてありますので参考にしてください！
つまり、
で表され、検査行列や生成行列を利用することによって誤り訂正を行うことができるというものです。
ハミング距離とは
ハミング距離とは、同じ位置にある文字、数字の異なる個数です。２元符号のハミング符号でかんがえてみましょう。例として、
この二つの符号間距離を考えてみましょう。そうすると、１、２、３列目が違いますよね。つまりこの二つのハミング距離は３ということになります。簡単ですよね。
また符号語間距離とも呼ばれます。
最小ハミング距離
次に、例えば、符号語がたくさんあったとしましょう。上の7列のベクトルを考えたときに、符号語の種類というのは27個ありますよね。
そのように与えられた２元符号に関して、任意の２つの異なる符号語の間のハミング距離の最小値のことを
最小ハミング距離と呼びます。
２元符号が３本、a,b,cがあったとします。aとbのハミング距離が３、bとcのハミング距離が2、aとcのハミング距離が４だったとすると、最小ハミング距離というのは２となります。すべてにおいて比較すれば出てきます。
しかしこれでは大変ですよね・・・
次にそれを解決するために、ハミング重みのお話をします
ハミング重みとは
また、これからの話をするにあたって、ハミング重みのお話をしておきます。
ハミング重みは、ビット列の中に含まれる１の数です。単純に、
次のような符号語があった場合、ハミング重みは２になります。
またこれは、
この符号とハミング距離を考えるとハミング距離は２になります。このイメージを覚えておいてください。
最小ハミング重み
最小ハミング重みは皆さんが想像した通りです。
２元符号がたくさん与えられたとして、その中の符号語のハミング重みの最小値のことを
最小ハミング重みといいます。
つまりどういうことかというと、
１が一番少ない符号のハミング重みが最小ハミング重みということです。
最小ハミング距離と最小ハミング重み
まず、一番最初に結論を言いますと、
線形符号では、最小ハミング距離と最小ハミング重みが一致します。
証明として堅苦しく書くと読むのが大変だと思うので、簡単に説明しますと、
ハミング距離というのは、ハミング重みを用いてあらわすと、２つの符号を引き算したハミング重み、ということになります。
つまり、
このような二つの符号語があったとしましょう。この二つの符号を引き算すると、
となります。２進数の計算です。最後に出た符号語のハミング重みは４です。したがってハミング距離も４になります。
逆にハミング距離から求めても、４になりますよね。ハミング距離というのは、符号の異なる個数でしたので。
これが最小の場合でも成り立つため、線形符号において、最小ハミング距離と最小ハミング重みというのは一致します。
これを利用すると簡単にハミング距離が求められます。
(7 4)ハミング符号の最小ハミング距離
それでは、 (7 4)ハミング符号の最小ハミング距離について考えていきましょう。(7 4)ハミング符号は先ほど貼り付けておいたリンク
こちらの方に詳しく書いてありますが、少し抜粋して書いていきます。
このように検査行列が与えられている(7 4)ハミング符号について考えてみます。これは上の記事でも述べられている通り、簡単な形です。これを例にして考えてみましょう。
このハミング符号の生成行列を求めると、
となります。ここから最小ハミング距離を求めてみましょう。
上の式から、生成行列の行の最小ハミング距離というのが、符号の最小ハミング距離になることがわかります。それでは生成行列のハミング距離を考えてみましょう。
考え方として、左側４列と右側３列で考え、行、つまり横に見たベクトルのハミング距離を考えます。
左側４列側の行、は明らかにハミング距離が２です。１が１つで別の場所にあるからです。
側３列は、すべて違う形になっているため、ハミング距離が１以上あります。逆に１以上無かった場合検査行列が機能しなくなります。
以上のことから、(7 4)ハミング符号の最小ハミング距離というのは３になることがわかったと思います。
また、どの行を見てもハミング重みは３以上になっています。ハミング重みの点から見ても最小ハミング距離というのは３になることが感覚的に理解できるかと思います。
それでは最後に誤り訂正、誤り検出能力についてお話していきます。
誤り訂正能力、誤り検出能力について
最後にお話しするのが、ハミング符号の誤り提出能力、誤り検出能力についてです。
まずは分かりやすいように(7 4)ハミング符号について考えてみようと思います。 (7 4)ハミング符号の最小ハミング距離が３であるということは先ほどお話いたしました。これを利用して誤りが訂正できるのかどうか考えてみましょう。
最小ハミング距離が３ということを図に表してみると、
このAとDの位置にある、ということだと考えてみましょう（今回使うハミング符号はAとDで、Bと
Cは間にある符号）。このように考えると、ハミング距離というものを実際の距離とみて考えることができます。AとBのハミング距離は１ということです。
Aを送信して、１符号誤っていた場合、Bとして受け取られます。ハミング距離が１だからです。つまり、Dの位置からの距離は２になります。
もし、ハミング符号の誤り訂正能力が１だった場合、ハミング距離が１までの符号なら元の符号に復号できます。この場合、Bという符号というのはAからの距離が１なので、Aに復号することが可能です。また、Dからは距離が２なので、複合することができません。
もし、誤り訂正能力が２だったらどうなるでしょう。ハミング距離が２までの符号なら元の符号に復号できるということです。そうすると、Ｂにある符号というのが、ＡにもＤにも復号できるということがわかりますでしょうか。
したがって誤りを確実に訂正するためには、最小ハミング距離が３の場合、誤り訂正能力は１でなくてはいけません。
この関係を、最小ハミング距離と誤り訂正能力の式として普遍的にすると、
と表されます。今回は最小ハミング距離が３、誤り訂正能力が１なので式が成立していることがわかると思います。
また、誤りを訂正できなくても検出だけはできる場合があります。その場合というのは、
となります。
このように最小ハミング距離と誤り検出能力、誤り訂正能力というのは密接に関わっています。
最後に
いかかでしたでしょうか。ハミング符号のハミング距離、ハミング重みのイメージ、それに加えて誤り検出、訂正能力についてが大体わかるようになってくれたらうれしいです。
もしわからないこととかがありましたら、コメントいただけたら返させていただきたいと思います。
それではまた。ぽたでした。