그레이 코드 (Gray Code)

보통 이진수는 7 → 8 처럼 값이 조금만 올라도 0111 → 1000 으로 네 비트가 한꺼번에 뒤집힌다. 그레이 코드는 순서를 재배열해서 이웃한 값끼리 항상 딱 1비트만 다르게 만든 코드다. 로터리 엔코더, 카노 맵, ADC, 유전 알고리즘에서 쓰인다.

1. 이진 코드 vs 그레이 코드 — 비트가 몇 개나 바뀌나

0부터 15까지 셀 때, 한 칸 올라갈 때마다 바뀐 비트를 빨갛게 표시했다. 이진 코드의 "비트 변화 합계"와 그레이 코드의 합계를 비교해 보자.

2. 이진수 ↔ 그레이 코드 변환

변환은 XOR 한 방이면 된다. 이진수를 오른쪽으로 1칸 민 것과 원래 값을 XOR 한다:

거꾸로 그레이 → 이진은 앞 비트부터 누적 XOR:

3. 로터리 엔코더 — 그레이 코드가 오류를 막는 이유

회전하는 원판에 동심원 트랙을 파고, 각 각도마다 광센서 3개가 트랙의 검정/흰색을 읽어 3비트 값을 만든다. 원판을 드래그해서 돌려 보자. 이진 원판은 경계에서 센서 정렬이 조금만 어긋나도 순간적으로 튀는 값을 뱉는다. 그레이 원판은 어떤 경계에서도 1비트만 바뀌므로 최악이라도 인접한 두 값 중 하나로만 읽힌다.

4. 어떻게 만들까 — "반사 이진 코드" (reflected binary code)

그레이 코드의 정식 명칭은 반사 이진 코드다. n비트 코드에서 (n+1)비트 코드를 만드는 규칙:

1. 기존 n비트 목록을 그대로 쓰고, 각 줄 앞에 0 을 붙인다.
2. 기존 목록을 위아래로 뒤집어(거울) 복사하고, 각 줄 앞에 1 을 붙인다.
3. 두 목록을 이어 붙이면 (n+1)비트 그레이 코드가 된다.

거울로 뒤집었기 때문에 이어 붙이는 경계에서도 (접두 비트를 뺀) 나머지가 똑같아 1비트만 바뀐다. 목록의 처음과 끝도 1비트만 다르다(순환 코드).

5. 코드

# 정수 → 그레이 코드 정수
def to_gray(n):
    return n ^ (n >> 1)

# 그레이 코드 정수 → 원래 정수 (앞에서부터 누적 XOR)
def from_gray(g):
    b = g
    while g > 0:
        g >>= 1
        b ^= g
    return b

# n비트 그레이 코드 순서 전체 (반사 구성)
def gray_sequence(bits):
    seq = ["0", "1"]
    for _ in range(bits - 1):
        seq = ["0" + x for x in seq] + ["1" + x for x in reversed(seq)]
    return seq

print([to_gray(i) for i in range(8)])   # [0, 1, 3, 2, 6, 7, 5, 4]