기원

그런 문제는 정보시대가 시작될 때부터 있었다. 프랭크 그레이(Frank Gray)는, 벨연구소가 디지털로 가는 거대한 흐름의 원동력이었던 시기에 소속 과학자로 있었다. 그레이는 컬러텔레비전을 가능케 한 다수의 원리를 개발했다. 그의 이름은 1940년대 중반에 고안된 그레이 코드(Gray code)로 가장 유명하다.

초기 텔레비전은 순전히 아날로그 방식이었다. 수평으로 주사(走査 scanning)하는 전자 빔이 계속해서 변하는 전압으로 생기는 자기장에 의해 위나 아래로 굴절되었다. 그레이는 아날로그 전압을 디지털 숫자로 전환하길 원했다. 즉 일련의 코딩된 펄스(coded pulses)로 말이다. 당시의 엔지니어들은 이진수들을 나타내는 구멍들이 뚫린, 회로패턴이 인쇄된 유리판인 마스크(mask)를 통해 전자빔을 쏜다는, 어딘가 스팀펑크적인 생각을 갖고 있었다. 여러 각도의 편향에 대응하는 이 마스크의 여러 다른 부분들은 서로 다른 패턴의 구멍들을 갖고 있었다. 빔이 정확한 전압을 이진수로 써나가도록 되어 있었다. 수많은 빛나는 아이디어들이 그랬듯이 이 역시 성공하지 못했다. 전자빔은 엉망진창이었다. 천지사방으로 날뛰는 고양이에게 물총을 쏘는 거나 같았다.

진짜 문제는, 빔이 한 가지 전압 숫자(voltage number)에서 다른 전압 숫자로 이동할 때 이상한 판독을 한다는 데 있었다. 제대로 작동하게 하기 위해 그레이는 딱 한 자리만이 각 숫자에서 다른 숫자로 바뀌는 숫자 코드가 필요했다. 그런 시스템을 현재 그레이 코드라 부른다. 10을 포함해서 어떤 기수(基數)를 가지고도 그레이 코드를 얻을 수 있다. 그러나 가장 유명한 예는 2진 그레이 코드다. 이런 모습이다.

(중략)

그레이 코드의 숫자들은 2든 뭐든 그것의 값을 나타내지 않는다. 그저 하나의 코드일 뿐이다. 예를 들어 코드 111은 5를 의미할 뿐이다. 거기서 그 이상의 다른 의미를 읽어내려고 해서는 안 된다. 그레이 코드가 존재하는 유일한 이유는 각 숫자가, 그 앞 숫자에서 딱 한 자리만 바꾸면 생성될 수 있다는 데 있다. 즉 5(111)에서 6을 얻으려면 가운데 있는 숫자를 바꿔서 101로 만들기만 하면 된다.

그레이는 코드를 생성하는 간단한 방법을 제공했다. 0과 1로 시작한다. 이들은 보통의 숫자인 0과 1에 할당된다. 속임수 같은 건 없다. 그런 후에 0, 1 수열을 1, 0으로 역전시킨다. 그런 후에 원래의 수열에 붙인다. 그러면 0, 1, 1, 0이 된다.

원래의 수열과 역전된 수열을 구별하기 위해 각 코드의 왼편에 별도로 숫자를 덧붙여야 한다. 원래의 수열에는 0을 붙이고 반전시킨 수열에는 1을 붙인다. 그러면 00, 01, 11, 10이 된다.

이 숫자들이 그레이 코드의 첫 네 숫자들이다.

– 당신은 구글에서 일할 만큼 똑똑한가? Answers. 336쪽.

그레이 코드

  • 그레이 부호라고도 부른다.
  • 그레이 코드의 종류는 다양하지만 이 글에서는 반사된 이진 그레이 코드(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비트 이진수 \(abcd\) 와 그레이 코드 \(efgh\) 가 있다고 하자.

변환 공식은 다음과 같다.

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

  • 첫 번째 비트 : \(e = a\)
  • 두 번째 비트 : \(f = a \oplus b\)
  • 세 번째 비트 : \(g = b \oplus c\)
  • 네 번째 비트 : \(h = c \oplus d\)

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

a b c d
1 0 1 0
  • 첫 번째 비트 : \(1\)
  • 두 번째 비트 : \(1 \oplus 0 = 1\)
  • 세 번째 비트 : \(0 \oplus 1 = 1\)
  • 네 번째 비트 : \(1 \oplus 0 = 1\)

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

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

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

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

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

정리하자면 다음과 같다.

\[G \leftarrow B \oplus ( B \overset{u}{\gg} 1 )\]
  • 참고
    • \(\oplus\) : 배타적 논리합(XOR).
    • \(x \overset{u}{\gg} y\) : 오른쪽 자리이동. 반대편에 0 채움.
    • \(x \ll y\) : 왼쪽 자리이동. 반대편에 0을 채운다.
    • \(x \overset{s}{\gg} y\) : 오른쪽 자리이동. 부호 채움.
    • \(x \overset{rot}{\gg} y\) : 순환식 오른쪽 자리이동.
    • \(x \overset{rot}{\ll} y\) : 순환식 왼쪽 자리이동.

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

  • 첫 번째 비트 : \(a = e\)
  • 두 번째 비트 : \(b = e \oplus f\)
  • 세 번째 비트 : \(c = e \oplus f \oplus g\)
  • 네 번째 비트 : \(d = e \oplus f \oplus g \oplus h\)

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

e f g h
1 0 1 0
  • 첫 번째 비트 : \(1\)
  • 두 번째 비트 : \(1 \oplus 0 = 1\)
  • 세 번째 비트 : \(1 \oplus 0 \oplus 1 = 0\)
  • 네 번째 비트 : \(1 \oplus 0 \oplus 1 \oplus 0 = 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
}

정리하자면 다음과 같다.

\[B \leftarrow \overset{n - 1}{\underset{i = 0}{\oplus}} G \overset{u}\gg i\]

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

따라서 위의 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쇄 발행 2012년 05월 10일 / 원제 : Are You Smart Enough to Work at Google?
  • 해커의 기쁨. 비트와 바이트 그리고 알고리즘 (2판) / 헨리 워렌 지음 / 류광 옮김 / 제이펍 / 2013년 07월 22일 출간