Gray Code (Reflected Binary Gray Code)

GrayCode

과학자 프랭크 그레이. 자신의 이름을 따와 그레이코드를 1940년대에 고안하였다.

GrayCode는 이진(Binary) 숫자 체계의 순서에서 연속된 값이
하나의 비트(Binary Digit)만 다르게 구성하여 숫자를 표현한다.

• 그레이 부호이라고도 부르기도 한다.
• 그레이 코드는 다음 수로 이동할 때 1비트만을 바꾼다.

그레이 코드 생성

0과 1로 할당하여 비트로 나열한다.
원래의 2진법 숫자1은 (01)이며, 숫자3은 (11) 된다.
그레이코드에서는 숫자 1은 (01)이며, 숫자3은 (10)이 된다.

숫자 0~7 표에서 2진법과 그레이코드를 살펴보자.

그레이코드의 특징으로 한 비트만 변경되어 연속된 값을 표현한다.
반면 2진법에서는 비트 1,2,1,3개씩 이동해야 연속된 숫자를 표현해주고 있다.

다음으로 비트 길이에 따른 위치를 살펴보도록하자. 비트위치를 파악해야 알고리즘 변형 및 구현할 때 도움이 된다.

2비트에서 그레이코드를 나열해 변환된 비트를 찻게되면 첫째{둘째}첫째 이 된다.
둘째 기준으로 좌우가 거울처럼 반사(reflect)한 모양처럼 된다.

3비트인 경우 그림과 같이 될것이다. 첫째둘째첫째{셋째}첫째둘째첫째

4비트 표를 만들지 않았지만, 여러분이
첫째둘째첫째셋째첫째둘째첫째{넷째}첫째둘째첫째셋째첫째둘째첫째 으로 예상을 하였다면,
비트 길이에 따른 알고리즘 구현에는 어려움이 없을 것이다.

그레이코드 생성 알고리즘

스텝(1). 0과 1를 수직으로 입력한다.
스텝(2). 거울에 놓은것처럼 반사하여(reflect) 입력한다.(1과 0 입력)
스텝(3). 원래 입력된 숫자(0과 1) 앞에 0를 입력한다.
스텝(4). 반사된 숫자(1과 0) 앞에 1를 입력한다.
다음 자릿수도 과정을 반복하여 입력한다.

변환 공식 (이진수 => 그레이코드 변환)

변환 공식은 다음과 같다.

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

KaTex:

\(G {\gets} N {\oplus} \left( N \gg 1 \right) \)

변환공식을 XOR와 쉬프트연산자로 0부터 19까지의 그레이 코드를 출력할 수 있다.
웹 about:blank 개발자 콘솔화면에서 실행하면 결과를 살펴볼 수 있다.

for(let i = 0; i < 20; i++) {
    g = i ^ (i >> 1)
    console.log("Number:"+i+" GrayCode Bit:"+g.toString(2));
}

변환 공식 (그레이코드 => 이진수 변환)

변환 공식은 다음과 같다.

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

KaTex:

\( B \gets \oplus_{i=0}^{n-1} \left( G \gg i \right) \)

Gray Code 변환에 Magic 코드는 다음과 같이 활용될 수 있다.
c언어에서는 unsigned int로 반환해주도록 한다.

function WordToBin(gray) {
    bin = gray ^ (gray >> 1)
    bin = bin ^ (bin >> 2)
    bin = bin ^ (bin >> 4)
    bin = bin ^ (bin >> 8)
    bin = bin ^ (bin >> 16)
    return bin
}

for(let i = 0; i < 20; i++) {
    g = i ^ (i >> 1)
    console.log("Number:"+i+" Graycode Bit:"+g.toString(2)+" Binary Bit:"+WordToBin(g).toString(2));
}

참고서

1. 당신은 구글에서 일할 만큼 똑똑한가?
   윌리엄 파운드스톤 저
   유지연 역
   타임비즈 출판사
2. Gray Code Conversion
   http://aggregate.org/MAGIC/#Gray%20Code%20Conversion
3. Gray Code Wiki
   https://en.wikipedia.org/wiki/Gray_code