グレイコードとは
グレイコード（英: Gray code グレイ符号）、交番二進符号（こうばんにしんふごう、英：Reflected Binary Code）とは、数値の符号化法のひとつで、前後に隣接する符号間のハミング距離が必ず1であるという特性を持つ。デジタル回路や、具体例としてはアブソリュート・ロータリー・エンコーダーのセンサー出力等に使われる。
ハミング距離が1の進行ということですね。001 -> 010 -> 011 -> 100という通常の二進法だと、それぞれ2ビット、1ビット、3ビットの変化が現れてしまうけれども、001 -> 011 -> 010 -> 110という進行だと、常に1ビットの変化で次の数が表せるので利点があるということです。
ハノイの塔との関連がありますので有名かもしれません。むしろ説明にあるアブソリュート・ロータリー・エンコーダーってなんでしょうね…名前がかっこいいですね。
それではこのグレイコードをPHPを使って出力してみます。
グレイコードへの変換
なぜこれで計算できるのかいまいちピンとこないのですが、「自分自身と自分自身１ビット右にシフトしたものの排他的論理和」でその数のグレイコード求めることができます。PHPで書くとこんな感じです。
$i^($i>>1);
ジェネレータを使う
ジェネレータを使えば、シンプルな イテレータを簡単に実装できます。 Iterator インターフェイスを実装したクラスを用意する オーバーヘッドや複雑さを心配する必要はありません。
だそうなので、せっかくなのでPHPのジェネレータを使って実装します。ジェネレータはPHP5.5から取り入れられたので、5.5.0以上でないとできません。
実装
<?php
function graycodes($range) {
foreach($range as $i) {
// キーも一緒に返すことができます。
yield $i => decbin($i ^ ($i >> 1));
// 次回はここからスタートします。
}
}
// 0から15番目までのグレイコードを出力します。
foreach(graycodes(range(0, 15)) as $k => $v) {
echo sprintf("%2d : %04d\n",$k, $v);
}
実行結果
0 : 0000
1 : 0001
2 : 0011
3 : 0010
4 : 0110
5 : 0111
6 : 0101
7 : 0100
8 : 1100
9 : 1101
10 : 1111
11 : 1110
12 : 1010
13 : 1011
14 : 1001
15 : 1000
まとめ
PHP5.5からの機能であるジェネレータを使って、グレイコードを出力する簡単なコードを書きました。ジェネレータはファイルを1行ずつ読み込んで処理をする、といったことなどに有用ですが、まずは簡単なものを書いてみるといいかもしれません。