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