グレイコードをPythonで実装する｜"1ビットずつ"変化させる賢い数え方

普通の2進数は、3（011）から4（100）へ増えるとき3ビットが同時に変わります。この「同時変化」がデジタル回路では誤りの元。それを避けるのが グレイコード——隣り合う値が必ず1ビットだけ違う数え方です。Pythonで実装して使いどころを理解します。

なぜ1ビットずつが嬉しいのか

複数ビットが同時に変わると、物理的にはわずかなタイミングのズレで一瞬おかしな値（グリッチ）が出ます。位置センサー（ロータリーエンコーダ）などでこれが起きると、瞬間的に大きく誤った値を読んでしまう。グレイコードなら常に1ビットしか変わらないので、この誤りが原理的に起きません。

準備

Python標準機能だけ。

① 2進数 ⇄ グレイコード変換

変換はビット演算だけ。驚くほど簡単です。

def binary_to_gray(n):
    return n ^ (n >> 1)              # これだけ！

def gray_to_binary(g):
    b = g
    while g > 0:
        g >>= 1
        b ^= g
    return b

for n in range(8):
    g = binary_to_gray(n)
    print(f"{n}: 2進 {n:03b} → グレイ {g:03b}")

出力:

0: 2進 000 → グレイ 000
1: 2進 001 → グレイ 001
2: 2進 010 → グレイ 011
3: 2進 011 → グレイ 010
4: 2進 100 → グレイ 110
...

② 隣同士が1ビットだけ違うことを検証

def bit_diff(a, b):
    return bin(a ^ b).count("1")    # 異なるビット数

prev = binary_to_gray(0)
all_one = True
for n in range(1, 16):
    g = binary_to_gray(n)
    if bit_diff(prev, g) != 1:
        all_one = False
    prev = g
print("常に1ビットだけ変化？:", all_one)   # True

True。隣り合う値が必ず1ビットだけ違うことが確認できました。3→4のような「3ビット同時変化」が、グレイコードでは起きません。

③ 逆変換が正しいことも確認

ok = all(gray_to_binary(binary_to_gray(n)) == n for n in range(256))
print("往復変換OK:", ok)   # True

まとめ

• グレイコードは隣り合う値が必ず1ビットだけ違う数え方
• 変換は n ^ (n >> 1) だけ。逆変換も簡単
• 複数ビット同時変化によるグリッチ（誤読）を防げる
• エンコーダやスイッチで活躍。演算時は2進数に戻す

もう少し詳しく（背景と理論）

グレイコードは、隣り合う数どうしが必ず1ビットだけ異なるように並べた2進符号で、Bell 研の Frank Gray が1953年の特許で広めました¹。通常の2進では、例えば 3→4（011→100）で3ビットが同時に変化し、各ビットの切り替わりが少しずれると途中に誤った値（グリッチ）が一瞬現れます。グレイコードなら1ビットしか変わらないので、この過渡的な誤読が原理的に起きません²。だからロータリーエンコーダや位置センサ、そして異なるクロック領域をまたぐ非同期FIFOのポインタなどで重宝されます³。カルノー図の軸がグレイコード順に並ぶのも、隣接マスが1ビット差で論理簡単化に都合が良いためです。

次の一歩 🌸

数の基礎は2進数と2の補数、論理簡約はブール代数をPythonで、状態遷移は有限状態機械へどうぞ。

Footnotes

1. Frank Gray (Bell Labs, 特許1953) にちなむ反射2進符号。隣接コード間のハミング距離が常に1になるよう構成される。 ↩

2. 複数ビット同時変化は各ビットのタイミング差でグリッチ（過渡的な誤値）を生む。1ビットずつ変わるグレイコードはこれを回避する。 ↩

3. 非同期FIFOでは読み書きポインタをグレイコード化してクロック領域をまたぐ。1ビット差なので同期化時の誤読を防げる。エンコーダの角度検出にも使う。 ↩