그레이 코드(Gray code)는 대칭이진부호(reflected binary code)라고도 불리는데, 다음 단계의 수로 넘어갈 때, 자릿수 하나가 1만큼만 바뀌는 특징을 갖고 있다.
예를 들어, 십진법에서의 그레이 코드를 생각해보면, 183과 193은 서로 바로 전 단계 혹은 다음 단계 수일 수 있다. 여기서 두 수는 중간 자릿수 하나만 1 차이가 난다.
오른쪽의 플립시계가 돌아가는 것을 생각해보자. 시계가 7시 59분을 가리키고 있다면, 그 다음 시간인 8시 00분을 가리키기 위해서는 3개의 분할플랩을 돌려야 한다. 여기서 그레이 코드가 사용된다면, 1개의 분할플랩을 한 번만 움직이면 될 것이다. 다행히 이 시계는 1분마다 플랩을 움직이면 되기 때문에 그레이 코드를 사용하지 않아도 문제가 되진 않는다.
그런데, 이 시계가 나노초 단위까지 나타낸다면, 바로 다음 단계의 수를 세기 위해, 여러 개의 플랩을 돌리는 것은 비효율적일 뿐만 아니라 에러가 일어날 확률도 높이게 될 것이다.
이진법에서 그레이 코드를 만드는 것은 꽤 쉽다. 0과 1의 아래에 대칭이 되도록 1과 0을 쓴 후, 그 앞에 각각 0과 1을 붙이자. 그렇게 2비트짜리 그레이 코드를 만들고, 여기서 3비트 짜리를 만들 때도, 역시 2비트 그레이 코드를 나열한 뒤 대칭시키고, 앞에 0과 1을 붙이면 된다.
출처
- Martin Gardner (1986). 〈The Binary Gray Code〉. 《Knotted Doughnuts and Other Mathematical Entertainments》. W.H. Freeman. ISBN 978-0-7167-1799-7.
- 위키피디아