@a4lg のそろそろ技術的日記

グレイコード→次のグレイコード的なカウンタ

math

@iorivur さんがつぶやいた、グレイコードを直接出すカウンタは…できました。けど複雑な上に実質加算器なので、個人的にはこれはあまり好きになれません。

グレイコードとは

グレイコードとは、1 ステップ進めると 1 ビットだけ変化するという性質を持つ n ビットの数値符号です。ここでは、3 ビットのグレイコードを見てみましょう。

C 言語では、次の関数でグレイコードに変換できます。

int graycode(int v)
{
    return v ^ (v >> 1);
}

「上位のビットに」依存するグレイコード

上の関数は、通常の数値からグレイコードを生成します。では、グレイコードから次のグレイコードを生成できるのか? というのが @iorivur さんの疑問だったみたいです。でまぁ…卑怯ですが、できました。

• 各ビットは、「自ビットより上位ビットすべての偶数パリティ」=P、「自ビット」=Bin、「キャリー」=Cin を受け取る
  • 偶数パリティは、データに含まれる 1 ビットの数が偶数なら 0、奇数なら 1 になるパリティ。ようは全ビットの XOR。
• 各ビットはキャリーが 1 のときにしか更新されない
• 最下位ビットのキャリーは、通常の加算器と異なり常に 1 (最下位ビットから更新が始まる)
• 各ビットは出力の自ビット=Bout、キャリー=Cout を出力し、Cout はすぐ上のビットの Cin になる

このとき…

もっと省略すると、

ただしこれは最上位ビットを除く話です。最上位ビットの場合には、0→1 のとき上記ルールが適用できますが、1→0 のときルールが適用できません。そのため、Cin=1, Bin=1 で、かつ下位ビットすべてが 0 ならば、Bout は 0 にする必要があります。

ビット毎に計算して正しいことを確かめてみてください。

各ビット毎のパリティをあらかじめ求めておく必要はあるものの、これで一応はグレイコード→次のグレイコードが一意に算出できます。だけどこれって加算器を変形しただけだから、実質バイナリ (数値) 変換してるのと変わらないのよね…。

Permalink | コメント(0) | トラックバック(0) | 21:00