ハミング距離

カルノー図

カルノー図は論理式を簡略化するためなどに使用する図です。

$\begin{aligned} f&=\overline{A}\cdot\overline{B}\cdot C +\overline{A}\cdot B \cdot C+ A\cdot\overline{B}\cdot\overline{C}+A\cdot B \cdot\overline{C} \\\ &=\overline{A} \cdot C+ A \cdot \overline{C} \end{aligned}$

　
このような論理式の簡略化を図から容易に行うことができます。
が、ここでは論理式は扱いません。ハミング距離の理解のためだけにカルノー図を使います。

ハミング距離の説明でよく超立方体が使われていますが（ハミング距離 - Wikipediaでも4次元の超立方体が使われてますね）次数が上がると図が意味不明になるし、そもそもイメージしずらいのでここではカルノー図で押し通してみましょう。
では、8変数までのカルノー図の作り方のはじまりはじまり・・・

2ビットのカルノー図

縦方向に $b_{1}$ 、横方向に $b_{0}$ を割り当てて、各マスには $b_{1} b_{0}$ の3ビットの値が書き込まれており、3ビットが取り得る値の一覧表になっています。 3ビットが取り得る値は $2^{2}=4$ で4通りなので4種類の値となります。

	$0$	$1$
$0$	$00$	$01$
$1$	$10$	$11$

2ビットのカルノー図はこれで完成です。
　
「で、カルノー図って一体なんなんだよ！！」はい、そうでしたね。ではカルノー図が一体何なのかは3ビットのカルノー図で説明しましょう。

3ビットのカルノー図

縦方向に $b_{2}$ $b_{1}$ 、横方向に $b_{0}$ を割り当てて、各マスには $b_{2}$ $b_{1}$ $b_{0}$ の3ビットの値が書き込まれており、3ビットが取り得る値の一覧表になっています。 3ビットが取り得る値は $2^{3}=8$ で8通りなので8種類の値となります。

	$0$	$1$
$00$	$000$	$001$
$01$	$010$	$011$
$10$	$100$	$101$
$11$	$110$	$111$

この表、縦方向の $b_{2}$ $b_{1}$ は $00$ → $01$ → $10$ → $11$ という順番に割り振ってありますが最後の2つ黄色の塗りつぶしの部分の順番を入れ替えて $00$ → $01$ → $11$ → $10$ としてみます。このようにして作られた表には面白い性質があります。

	$0$	$1$
$00$	$000$	$001$
$01$	$010$	$011$
$11$	$110$	$111$
$10$	$100$	$101$

$000$ からスタート、一つ下に進むと $010$ になり $000$ と比べると $b_{1}$ だけが $0$ から $1$ に変化します。
$010$ から更に一つ下に進むと $110$ になり $010$ と比べると $b_{2}$ だけが $0$ から $1$ に変化します。
$110$ から更に一つ下に進むと $100$ になり $110$ と比べると $b_{1}$ だけが $1$ から $0$ に変化します。
更に一つ下に進めてみようかな、と思ったのですがもうこれ以上、下はないので先頭の行に戻ると $000$ になり $100$ と比べると $b_{2}$ だけが $1$ から $0$ に変化します。ここでは上下に移動しましたが、左右の移動も変化するビットは1ビットだけになっています。
最初の表では $010$ の下は $100$ ですから $b_{2}$ が $0$ から $1$ 、 $b_{1}$ が $1$ から $0$ に変化しているので2ビット変化していますね。

このように上下左右とは1ビットしか異ならないように値を並べた表を「カルノー図」と呼びます。

表のはじまで行ったとき反対側に移動するのが面倒なら表自体を上下左右に伸ばして更に続きがあるんだ、と考えると簡単です。下の表は中央、青塗りつぶしのまわりに同じ表をつなげてみました。

	$0$	$1$	$0$	$1$	$0$	$1$
$00$	$000$	$001$	$000$	$001$	$000$	$001$
$01$	$010$	$011$	$010$	$011$	$010$	$011$
$11$	$110$	$111$	$110$	$111$	$110$	$111$
$10$	$100$	$101$	$100$	$101$	$100$	$101$
$00$	$000$	$001$	$000$	$001$	$000$	$001$
$01$	$010$	$011$	$010$	$011$	$010$	$011$
$11$	$110$	$111$	$110$	$111$	$110$	$111$
$10$	$100$	$101$	$100$	$101$	$100$	$101$
$00$	$000$	$001$	$000$	$001$	$000$	$001$
$01$	$010$	$011$	$010$	$011$	$010$	$011$
$11$	$110$	$111$	$110$	$111$	$110$	$111$
$10$	$100$	$101$	$100$	$101$	$100$	$101$

2ビットでは隣との違いは必ず1ビットとなるのでマトリクスにすると自然とカルノー図になっているんですね。

4ビットのカルノー図

4ビットのカルノー図は横方向も2ビット割り当てます。
値の並びは縦方向と同じく隣同士が1ビット違いになるようにします。
上下左右に移動したとき変化するビットは1ビットのみになっていますね。

	$00$	$01$	$11$	$10$
$00$	$0000$	$0001$	$0011$	$0010$
$01$	$0100$	$0101$	$0111$	$0110$
$11$	$1100$	$1101$	$1111$	$1110$
$10$	$1000$	$1001$	$1011$	$1010$

5ビットのカルノー図

4ビットまでのカルノー図は上記のとおり容易に作成できますが、更にビット数を増やそうとするとちと面倒なことが起こります。縦方向は $000$ → $001$ → $011$ → $010$ → $110$ → $111$ → $101$ → $100$ と1ビットづつ変化するように配置して以下のような表ができます。なにか、上手いことできているように見えますが黄色のセルを見てください。
$01100$ と $11100$ なので1ビットしか変化していないのですが、隣同士ではないんです。 5ビットになると変化するビットは5個、移動方向も5個ないといけないのですが、移動方向は上下左右の4通りなのですからもう一つ、新しい移動方向を考える必要があるのです。黄色のセルはこの新しい移動方向で隣同士になる、ということになります。

	$00$	$01$	$11$	$10$
$000$	$00000$	$00001$	$00011$	$00010$
$001$	$00100$	$00101$	$00111$	$00110$
$011$	$01100$	$01101$	$01111$	$01110$
$010$	$01000$	$01001$	$01011$	$01010$
$110$	$11000$	$11001$	$11011$	$11010$
$111$	$11100$	$11101$	$11111$	$11110$
$101$	$10100$	$10101$	$10111$	$10110$
$100$	$10000$	$10001$	$10011$	$10010$

新しい移動方向は

2行目と7行目
3行目と6行目

になります。
でも、なんか分かりづらいですね・・・
ということで少し考え方を変えてみましょう。上下左右の移動は2次元平面での移動ですから移動方向を増やしたければ3次元にしてやればよいのでは？

ということで、3次元バージョンの5ビットカルノー図です。 5ビットでは4ビットのカルノー図を2階建にします。移動方向は上下左右に加えて1階、2階を行き来できます。
5ビットの $b_{4}$ $b_{3}$ $b_{2}$ $b_{1}$ $b_{0}$ の $b_{4}$ を1階、2階に割り当てて以下のようにしましょう。
1階 $b_{4}=0$

	$00$	$01$	$11$	$10$
$00$	$00000$	$00001$	$00011$	$00010$
$01$	$00100$	$00101$	$00111$	$00110$
$11$	$01100$	$01101$	$01111$	$01110$
$10$	$01000$	$01001$	$01011$	$01010$

2階 $b_{4}=1$

	$00$	$01$	$11$	$10$
$00$	$10000$	$10001$	$10011$	$10010$
$01$	$10100$	$10101$	$10111$	$10110$
$11$	$11100$	$11101$	$11111$	$11110$
$10$	$11000$	$11001$	$11011$	$11010$

先ほど、隣同士になっていなかった $01100$ と $11100$ も1階と2階で隣どうしになれました。これで5ビットすべて隣は1ビット違いとなりました。

6ビットのカルノー図

ここまでの流れを考えれば6ビットは簡単ですね。
そうです、4階建てにします。

1階 $b_{5}b_{4}=00$

	$00$	$01$	$11$	$10$
$00$	$000000$	$000001$	$000011$	$000010$
$01$	$000100$	$000101$	$000111$	$000110$
$11$	$001100$	$001101$	$001111$	$001110$
$10$	$001000$	$001001$	$001011$	$001010$

2階 $b_{5}b_{4}=01$

	$00$	$01$	$11$	$10$
$00$	$010000$	$010001$	$010011$	$010010$
$01$	$010100$	$010101$	$010111$	$010110$
$11$	$011100$	$011101$	$011111$	$011110$
$10$	$011000$	$011001$	$011011$	$011010$

3階 $b_{5}b_{4}=11$

	$00$	$01$	$11$	$10$
$00$	$110000$	$110001$	$110011$	$110010$
$01$	$110100$	$110101$	$110111$	$110110$
$11$	$111100$	$111101$	$111111$	$111110$
$10$	$111000$	$111001$	$111011$	$111010$

4階 $b_{5}b_{4}=10$

	$00$	$01$	$11$	$10$
$00$	$100000$	$100001$	$100011$	$100010$
$01$	$100100$	$100101$	$100111$	$100110$
$11$	$101100$	$101101$	$101111$	$101110$
$10$	$101000$	$101001$	$101011$	$101010$

7ビット、8ビットのカルノー図

最後、7ビットと8ビット。7ビットなら移動方向は7種類、8ビットなら移動方向は8種類必要になります。
上下左右に上の階、下の階と3次元の移動方向は使い果たしてしまいました。そこで建物を増築します。1号館、2号館と2棟構成にしたのが7ビット、1号館から4号館の4棟構成にしたのが8ビットのカルノー図になります。
移動方法は・・・、空間移動です。とある部屋から別の棟の同じ位置の部屋に移動することができます。
　
7ビットの棟構成
1号棟 $b_{6}=0$
2号棟 $b_{6}=1$
　
8ビットの棟構成
1号棟 $b_{7}b_{6}=00$
2号棟 $b_{7}b_{6}=01$
3号棟 $b_{7}b_{6}=11$
4号棟 $b_{7}b_{6}=10$
　
ここまでくると、論理式の簡略化としての用途には使いずらくなってきます。まぁ、頑張ればできますが普通は6ビットぐらいまででしょうか。
しかし、ここではハミング距離のイメージを掴むためにカルノー図を用いるので、このワンフロア16部屋、4階建て、4棟構成のカルノー図でも十分に使うことができます（たぶん・・・）

ハミング距離はどうしたんだよ・・・

はい、おまたせしました。
やっとここからがハミング距離の説明です！！

エラー検出・訂正で使用するハミング距離とは2つの値の異なるビットの数となります。
そしてカルノー図上では異なる部屋の間の距離となります。
この距離とは一般的な距離の測り方とは少し異なります。とある部屋から1ビットしか異ならない部屋への移動を1として最短で何部屋移動するか、が距離となります。 4ビットのカルノー図で考えてみましょう。

黄色の部屋 $0101$ と緑色の部屋 $0100$ のハミング距離は1
黄色の部屋 $0101$ と青色の部屋 $1111$ のハミング距離は2
緑色の部屋 $0100$ とオレンジ色の部屋 $0110$ のハミング距離は1

	$00$	$01$	$11$	$10$
$00$	$0000$	$0001$	$0011$	$0010$
$01$	$0100$	$0101$	$0111$	$0110$
$11$	$1100$	$1101$	$1111$	$1110$
$10$	$1000$	$1001$	$1011$	$1010$

1はすぐ隣なので $0101$ から左に行って $0100$ で1、2は $0101$ から右に行って $0111$ 、下に行けば $1111$ なので2、これはいいですね。
3は $0100$ から右に行って $0101$ 、更に右に行って $0111$ 、もひとつ右に行って $0110$ だから3じゃないの・・・？と思うかもしれませんがカルノー図は左端と右端は繋がっているので $0100$ から左に行って $0110$ だから1になります。この決まりは階の間の移動でも、棟間の移動でも同じです。

2階建ての5ビットカルノー図で試してみましょう。黄色の部屋 $00000$ から緑色の部屋 $11111$ までの距離は $00000$ から1階を右に行って $00001$ 、更に右に行って $00011$ 、下に行って $00111$ 、もひとつ下に行って $01111$ 、2階に上って $11111$ でハミング距離5となります。どのような経路を辿ってもこれより短い経路はありません。実際にカルノー図を辿ってみてくださいね。

1階 $b_{4}=0$

	$00$	$01$	$11$	$10$
$00$	$00000$	$00001$	$00011$	$00010$
$01$	$00100$	$00101$	$00111$	$00110$
$11$	$01100$	$01101$	$01111$	$01110$
$10$	$01000$	$01001$	$01011$	$01010$

2階 $b_{4}=1$

	$00$	$01$	$11$	$10$
$00$	$10000$	$10001$	$10011$	$10010$
$01$	$10100$	$10101$	$10111$	$10110$
$11$	$11100$	$11101$	$11111$	$11110$
$10$	$11000$	$11001$	$11011$	$11010$

　
5ビットで全ビットが0だったのが全ビット1になったのだから異なるビットは5個でハミング距離は5、と見ただけでわかりますがこの後カルノー図を使ってエラー検出できる、できない、エラー訂正できる、できない、エラー検出・訂正ができるなら何ビットまでできるのか、の考察を行うので頭の中でカルノー図とハミング距離をイメージできるようにしておきましょう。

余談と次回予告

マンハッタン距離

カルノー図上でのハミング距離を数学用語で言うと『マンハッタン距離』となります。
一般の距離は『ユークリッド距離』と言って2点間を直線でつないだときの直線の長さとなります。これに対して『マンハッタン距離』は各座標軸での距離の和となります。マンハッタンの碁盤の目のような道路を進んでいったときの距離って感じですかね。斜めにショートカットすれば近いんだけどもそれはできない、碁盤の目を右に左に行った時の距離ということです。
ただ、マンハッタンの道路の右端と左端は繋がっていませんがカルノー図の右端と左端、上端と下端は繋がっているので計算するときはこれを考慮に入れる必要がありますね。

グレイコード

3ビットのカルノー図を作る際に $00$ → $01$ → $11$ → $10$ という並びを使用しました。隣同士が1ビットしか変化しない並びです。
このようなコードをグレイコードと呼びます。5ビットのカルノー図を作る際に最初に考えた $000$ → $001$ → $011$ → $010$ → $110$ → $111$ → $101$ → $100$ という並びも隣同士は1ビットしか変化しないのでグレイコードですね。
ソフトウェアではあまりお目にかかりませんがハードウェアではよく使う手法となります。一度に複数のビットが変化すると回路を構成する部品の微妙な動作時間の違いから本来出力されるべきではないコードが一瞬みえてしまい、これが誤動作の引き金になったりします。ここでグレイコードを使うと変化するのは必ず1ビットですから部品の動作時間のバラツキに関わらず正しいコードしか出力されないことになります。
一見、複雑そうなコードの並びですが信頼性を上げる重要な手法なんですね。

超立方体

2次元の座標で正方形を考えます。頂点が4個あってそれぞれの頂点からは2本の同じ長さの辺が出ており頂点で直角に交わっています。
では3次元の座標で立方体を考えます。頂点が8個あってそれぞれの頂点からは3本の同じ長さの辺が出ており頂点で直角に交わっています。
では4次元の座標だったら？
2次元から3次元に拡張したとこと同じように3次元から4次元に拡張すると頂点が16個あってそれぞれの頂点からは4本の同じ長さの辺が出ており頂点で直角に交わっている、そんな形になりそうです。
でもこれ、3次元の座標では作ることはできないですよね。頂点から4本の辺が出ていてそれぞれが直角に交わっている、この時点で3次元では実現できません。この4次元、あるいはそれ以上の次元での立方体を超立方体といいます。
4次元なので2次元や3次元で作ることはできませんが、条件をゆるめれば図にすることはできます。たとえば頂点で各辺が直角に交わっている、各辺の長さは同じ、という条件を外して書いたのがハミング距離 - Wikipediaの図になります。実はカルノー図を7ビットに拡張するときにも4次元をどう扱うか、という問題に直面しています。この時は隣の棟に空間移動できる、というズルをして解決しましたね。

次回予告

さて、ハミング距離もわかってきたので次回はエラー検出・訂正とハミング距離について考えてみましょう。

Smile Engineering Blog

ジェイエスピーからTipsや技術特集、プロジェクト物語を発信します

The Continuing Story of Error Correction Code 3