그레이 코드

  • 그레이 부호라고도 부른다.
  • 그레이 코드의 종류는 다양하지만 이 글에서는 반사된 이진 그레이 코드(reflected binary Gray code)를 다룬다.
  • 그레이 코드는 연속된 수를 한 비트만 다르게 인코딩한다.
    • 쉽게 말해, 다음 수로 넘어갈 때 언제나 1개 비트만 바뀐다.

일반적인 2진법과 비교해보자.

숫자 2진법 그레이 코드
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 111
6 110 101
7 111 100
  • 3 에서 4 가 될 때,
    • 2진법은 자리올림이 일어나며 011이 100 이 된다.
    • 그레이 코드는 언제나 1개 비트만 바뀌므로 010이 110이 된다.

생성 알고리즘

(1)  (2)  (3)   (4)
0    0    00    00
1    1    01    01
     1     1    11
     0     0    10
  1. 0과 1을 수직으로 쓴다.
  2. 아래쪽에 거울을 놓은 것처럼 반사하여(reflect), 1과 0을 반대 순서로 쓴다.
  3. 이제 원래 있었던 처음 두 숫자의 왼쪽에 0을 쓴다.
  4. 반대 순서로 쓴 1, 0의 왼쪽에 1을 쓴다.
  5. 다음 자릿수도 위의 과정을 반복하면 만들 수 있다.
(4)  (5)  (6)   (7)
00   00   000   000
01   01   001   001
11   11   011   011
10   10   010   010
     10    10   110
     11    11   111
     01    01   101
     00    00   100

한편, 다음의 방법으로 1부터 19까지의 그레이 코드를 출력할 수 있다.

for i := 0; i < 20; i++ {
    g := i ^ (i >> 1)
    fmt.Printf("%d : %b\n", i, g)
}

변환 공식

4비트 이진수 와 그레이 코드 가 있다고 하자.

변환 공식은 다음과 같다.

이진수를 그레이 코드로 변환

  • 첫 번째 비트 :
  • 두 번째 비트 :
  • 세 번째 비트 :
  • 네 번째 비트 :

만약 이진수 1010을 그레이 코드로 변환한다면 다음과 같을 것이다.

a b c d
1 0 1 0
  • 첫 번째 비트 :
  • 두 번째 비트 :
  • 세 번째 비트 :
  • 네 번째 비트 :

따라서 이진수 1010은 그레이 코드로는 1111이 된다.

  • 이진수 1010 : 십진수로 10.
  • 그레이 코드 1111 : 십진수로 10.

한편, 위의 공식을 잘 살펴보면 오른쪽으로 비트 쉬프트 한 다음, 본래 값과 논리합을 하면 끝난다는 것을 알 수 있다.

go 로 짜면 이런 함수가 나올 것이다.

func toGrayCode(bin int) int {
    return bin ^ (bin >> 1)
}

정리하자면 다음과 같다.

  • 참고
    • : 배타적 논리합(XOR).
    • : 오른쪽 자리이동. 반대편에 0 채움.
    • : 왼쪽 자리이동. 반대편에 0을 채운다.
    • : 오른쪽 자리이동. 부호 채움.
    • : 순환식 오른쪽 자리이동.
    • : 순환식 왼쪽 자리이동.

그레이 코드를 이진수로 변환

  • 첫 번째 비트 :
  • 두 번째 비트 :
  • 세 번째 비트 :
  • 네 번째 비트 :

만약 그레이 코드 1010을 이진수로 변환한다면 다음과 같을 것이다.

e f g h
1 0 1 0
  • 첫 번째 비트 :
  • 두 번째 비트 :
  • 세 번째 비트 :
  • 네 번째 비트 :

따라서 그레이 코드 1010은 이진수로는 1100이 된다.

  • 이진수 1100 : 십진수로 12.
  • 그레이 코드 1010 : 십진수로 12.

한편, 위의 공식을 잘 살펴보면 왼쪽부터의 논리합 누적 값을 계산하면 된다는 것을 알 수 있다.

go 로 짜면 다음과 같은 함수가 나올 것이다.

import "math"

func toBin(gray int) int {
    bitLength := 1 + int(math.Log2(float64(gray)))

    for i := 0; i < bitLength; i++ {
        gray ^= (gray >> uint(i))
    }
    return gray
}

정리하자면 다음과 같다.

그런데 이 공식은 워드의 패리티 계산 방법과 똑같다.

따라서 위의 toBin함수는 다음과 같이 최적화할 수 있다.

func toBin(gray int) int {
    bin := gray ^ (gray >> 1)
    bin = bin ^ (bin >> 2)
    bin = bin ^ (bin >> 4)
    bin = bin ^ (bin >> 8)
    bin = bin ^ (bin >> 16)
    return bin
}

하노이의 탑

그레이 코드는 하노이의 탑 문제의 솔루션이 될 수 있다.

다음은 3개의 비트를 사용한 그레이 코드의 목록을, 3개의 원판이 있는 하노이의 탑 문제의 솔루션으로 해석한 것이다.

GrayCode 하노이의 탑 문제의 솔루션으로 해석
000 시작.
001 1번 원판을 옮긴다.
011 2번 원판을 옮긴다.
010 1번 원판을 2번 원판 위로 옮긴다.
110 3번 원판을 옮긴다.
111 1번 원판을 옮긴다.
101 2번 원판을 3번 원판 위로 옮긴다.
100 1번 원판을 2번 원판 위로 옮긴다.
  • 가장 오른쪽 비트의 변화는 1번 원판의 이동이다.
  • 오른쪽에서 두 번째 비트의 변화는 2번 원판의 이동이다.
  • 오른쪽에서 세 번째 비트의 변화는 3번 원판의 이동이다.

참고문헌

  • 해커의 기쁨. 비트와 바이트 그리고 알고리즘 (2판) / 헨리 워렌 지음 / 류광 옮김 / 제이펍 / 2013년 07월 22일 출간
  • 당신은 구글에서 일할 만큼 똑똑한가? / 윌리엄 파운드스톤 저 / 유지연 역 / 타임비즈 / 2012년 07월

Links