위키득계정 ↗
기술

그레이 코드

그레이 코드기술
영어
Gray code
핵심 성질
이웃한 코드의 해밍 거리가 1
대표 방식
반사형 이진 그레이 코드
변환식
G(n)=n XOR (n>>1)
그레이 코드는 순서상 이웃한 코드가 한 비트만 다르도록 구성한 이진 코드다. 여러 비트가 동시에 바뀌는 전환을 피하도록 순서를 배치한다. 대표적인 반사형 이진 그레이 코드는 정수 n을 n XOR (n>>1)로 변환해 얻는다.

보통의 이진수와 차이

일반적인 이진수는 3에서 4로 증가할 때 011에서 100으로 바뀌어 세 비트가 모두 달라진다. 그레이 코드는 연속한 값의 표현이 한 비트만 바뀌도록 한다. 따라서 그레이 코드의 비트열을 그대로 보통의 이진수 자릿값으로 읽으면 원래 순서의 정수와 다를 수 있다.

작은 코드의 순서

2비트 반사형 그레이 코드는 00, 01, 11, 10의 순서로 나타낼 수 있다. 각 전환에서 바뀌는 자리는 하나이며 마지막 10에서 처음 00으로 돌아갈 때도 한 자리만 바뀐다. 11이 세 번째라고 해서 그것을 보통의 이진수 3과 같은 순서로 해석하는 것은 아니다.

반사해서 확장하기

기존 목록 앞에 0을 붙인 뒤, 기존 목록을 역순으로 읽으며 앞에 1을 붙여 이어 붙이면 한 비트 긴 목록을 만든다. 2비트 목록에서 이 과정을 반복하면 3비트 코드가 된다. 두 절반의 접합부에서는 접두 비트만 달라져 한 비트 전환이 유지된다.

변환과 해석

대표적인 반사형 코드에서는 원래 정수를 한 비트 오른쪽으로 이동한 값과 XOR하면 그레이 코드를 얻는다. 역변환은 위쪽 비트부터 누적 XOR하는 방식으로 가능하다. 한 비트만 바뀐다는 성질은 코드 순서에 대한 것이며, 잡음이나 잘못된 비트를 자동으로 수정해 준다는 뜻은 아니다.

관련 문서

이진법 / 비트 연산 / 해밍 거리 / 배타적 논리합 / 순열 / 알고리즘