정의 그레이 코드란 인접한 두 수의 코드가 정확히 한 비트만 다른, 음이 아닌 정수의 번호 매기기 체계를 말합니다.
예를 들어, 3비트 길이의 수에 대해서는 다음과 같은 그레이 코드 수열을 얻습니다: 000, 001, 011, 010, 110, 111, 101, 100. 예를 들어, G(4)=6입니다.
이 코드는 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 사이에 다음과 같은 관계를 얻습니다:
n_k = g_k, n_{k-1} = g_{k-1} \oplus n_k = g_k \oplus g_{k-1}[…] n_{k-2} = g_{k-2} \oplus n_{k-1} = g_k \oplus g_{[…] n_{k-3} = g_{k-3} \oplus n_{k-2} = g_k \oplus g_{[…] \ldots
프로그램 코드로는 다음과 같이 작성하는 것이 가장 간단합니다:
int rev_g (int g) { int n = 0; for (; g; g»=1) n ^= g; return n; } 응용 그레이 코드는 여러 분야에서 다양하게 응용되며, 때로는 꽤 뜻밖의 곳에서 쓰이기도 합니다:
n비트 그레이 코드는 n차원 큐브 위의 해밀턴 순환에 대응합니다. 공학에서 그레이 코드는 아날로그 신호를 디지털 신호로 변환할 때(예를 들어 센서에서) 오류를 최소화하는 데 사용됩니다. 실제로 그레이 코드는 바로 이 응용과 관련하여 발견되었습니다. 그레이 코드는 하노이의 탑 문제를 푸는 데 사용됩니다. n을 원판의 개수라고 합시다. 모두 0으로 이루어진 길이 n의 그레이 코드(즉, G(0))에서 시작하여 그레이 코드를 따라 이동합시다(G(i)에서 G(i+1)로 넘어갑니다). 현재 그레이 코드의 각 i번째 비트에 i번째 원판을 대응시킵시다(이때 가장 낮은 비트에는 크기가 가장 작은 원판이, 가장 높은 비트에는 가장 큰 원판이 대응합니다). 각 단계에서 정확히 하나의 비트만 바뀌므로, 비트 i의 변화를 i번째 원판의 이동으로 이해할 수 있습니다. 가장 작은 원판을 제외한 모든 원판에 대해서는 각 단계에서 가능한 이동이 정확히 하나뿐이라는 점에 주목하십시오(시작 위치와 최종 위치는 예외입니다). 가장 작은 원판에 대해서는 항상 두 가지 이동이 가능하지만, 항상 답으로 이어지는 이동 선택 전략이 있습니다. n이 홀수이면 가장 작은 원판의 이동 순서는 f \rightarrow t \rightarrow r \rightarrow f \rightarrow t \rightarrow r \rightarrow \ldots의 형태이고(여기서 f는 시작 기둥, t는 최종 기둥, r은 나머지 기둥입니다), n이 짝수이면 f \rightarrow r \rightarrow t \rightarrow f \rightarrow r \rightarrow t \rightarrow \ldots의 형태입니다.
그레이 코드는 유전 알고리즘 이론에서도 활용됩니다.