그레이 코드¶
그레이 코드는 연속한 두 값이 단 하나의 비트만 다른 이진 기수법입니다.
수 $n$을 그레이 코드로 나타낸 것을 $G(n)$으로 표기합니다. 3비트 수에 대한 그레이 코드의 수열은 000, 001, 011, 010, 110, 111, 101, 100이므로 $G(4) = (110)_2 = 6$입니다. 예를 들어 $G(3) = (010)_2$와 $G(4) = (110)_2$는 정확히 한 비트, 즉 가장 왼쪽 비트만 다릅니다. 마찬가지로 $G(4) = 110$과 $G(5) = (111)_2$는 정확히 한 비트, 즉 가장 오른쪽 비트만 다릅니다. 이는 연속한 모든 수에 대해 성립합니다.
이 코드는 1953년에 Frank Gray가 고안했습니다.
그레이 코드 구하기¶
수 $n$의 비트와 수 $G(n)$의 비트를 살펴봅시다. $G(n)$의 $i$번째 비트는 $n$의 $i$번째 비트가 1이고 $i + 1$번째 비트가 0이거나, 그 반대인 경우($i$번째 비트가 0이고 $i + 1$번째 비트가 1인 경우)에만 1이 된다는 점에 주목하십시오. 따라서 $G(n) = n \oplus (n >> 1)$입니다:
int g (int n) {
return n ^ (n >> 1);
}
역 그레이 코드 구하기¶
그레이 코드 $g$가 주어졌을 때 원래의 수 $n$을 복원합니다.
최상위 비트부터 최하위 비트 쪽으로 이동하겠습니다(최하위 비트의 인덱스는 1이고 최상위 비트의 인덱스는 $k$입니다). 수 $n$의 비트 $n_i$와 수 $g$의 비트 $g_i$ 사이의 관계는 다음과 같습니다:
이를 코드로 작성하는 가장 쉬운 방법은 다음과 같습니다:
int rev_g (int g) {
int n = 0;
for (; g; g >>= 1)
n ^= g;
return n;
}
실제 응용¶
그레이 코드에는 몇 가지 유용한 응용이 있으며, 때로는 꽤 뜻밖의 응용도 있습니다:
-
$n$비트 그레이 코드는 각 비트가 하나의 차원에 대응하는 초입방체 위에서 해밀턴 사이클을 이룹니다.
-
그레이 코드는 디지털-아날로그 신호 변환에서 오류를 최소화하는 데 사용됩니다(예를 들어 센서에서).
-
그레이 코드는 하노이의 탑 문제를 푸는 데 사용할 수 있습니다. 원판의 개수를 $n$이라고 합시다. 모두 0으로 이루어진 길이 $n$의 그레이 코드($G(0)$)에서 시작하여 연속한 그레이 코드 사이를 이동합니다($G(i)$에서 $G(i+1)$로). 현재 그레이 코드의 $i$번째 비트가 $i$번째 원판을 나타낸다고 합시다(최하위 비트는 가장 작은 원판에, 최상위 비트는 가장 큰 원판에 대응합니다). 각 단계에서 정확히 한 비트만 바뀌므로, $i$번째 비트가 바뀌는 것을 $i$번째 원판을 옮기는 것으로 볼 수 있습니다. 각 단계에서(시작 위치와 끝 위치 제외) 가장 작은 원판을 제외한 각 원판에는 이동 방법이 정확히 하나뿐이라는 점에 주목하십시오. 가장 작은 원판에는 항상 두 가지 이동 방법이 있지만, 항상 답으로 이어지는 전략이 있습니다: $n$이 홀수이면 가장 작은 원판의 이동 순서는 $f \to t \to r \to f \to t \to r \to ...$와 같으며, 여기서 $f$는 처음 기둥, $t$는 목표 기둥, $r$은 나머지 기둥이고, $n$이 짝수이면 $f \to r \to t \to f \to r \to t \to ...$입니다.
-
그레이 코드는 유전 알고리즘 이론에서도 사용됩니다.