グレイコード→次のグレイコード的なカウンタ
[twitter:@iorivur] さんがつぶやいた、グレイコードを直接出すカウンタは…できました。けど複雑な上に実質加算器なので、個人的にはこれはあまり好きになれません。
グレイコードとは
グレイコードとは、1 ステップ進めると 1 ビットだけ変化するという性質を持つ n ビットの数値符号です。ここでは、3 ビットのグレイコードを見てみましょう。
| v | b2 | b1 | b0 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 1 |
| 3 | 0 | 1 | 0 |
| 4 | 1 | 1 | 0 |
| 5 | 1 | 1 | 1 |
| 6 | 1 | 0 | 1 |
| 7 | 1 | 0 | 0 |
C 言語では、次の関数でグレイコードに変換できます。
int graycode(int v) { return v ^ (v >> 1); }
「上位のビットに」依存するグレイコード
上の関数は、通常の数値からグレイコードを生成します。では、グレイコードから次のグレイコードを生成できるのか? というのが [twitter:@iorivur] さんの疑問だったみたいです。でまぁ…卑怯ですが、できました。
- 各ビットは、「自ビットより上位ビットすべての偶数パリティ」=P、「自ビット」=Bin、「キャリー」=Cin を受け取る
- 各ビットはキャリーが 1 のときにしか更新されない
- 最下位ビットのキャリーは、通常の加算器と異なり常に 1 (最下位ビットから更新が始まる)
- 各ビットは出力の自ビット=Bout、キャリー=Cout を出力し、Cout はすぐ上のビットの Cin になる
このとき…
| Cin | P | Bin | Bout | Cout |
| 0 | X | X | Bin | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 |
もっと省略すると、
| Cin | P | Bin | Bout | Cout |
| 0 | X | X | Bin | 0 |
| 1 | X | X | ~P | P^Bin |
ただしこれは最上位ビットを除く話です。最上位ビットの場合には、0→1 のとき上記ルールが適用できますが、1→0 のときルールが適用できません。そのため、Cin=1, Bin=1 で、かつ下位ビットすべてが 0 ならば、Bout は 0 にする必要があります。
ビット毎に計算して正しいことを確かめてみてください。
各ビット毎のパリティをあらかじめ求めておく必要はあるものの、これで一応はグレイコード→次のグレイコードが一意に算出できます。だけどこれって加算器を変形しただけだから、実質バイナリ (数値) 変換してるのと変わらないのよね…。
