[재귀 알고리즘] 그레이 코드(Gray Code)

 

[재귀 알고리즘] 그레이 코드(Gray Code) 

 

본 포스팅은 도서 "문제로 풀어보는 알고리즘"(황인욱, 김용혁 지음)을 공부한 내용을 정리하기 위한 글임을 밝힙니다.

 

 

 

그레이 코드(Gray Code)란?

 

그레이 코드는 연속된 수를 한 비트만 다르게 인코딩하는 방법이다.

연속적으로 변하는 양을 나타낼 때, 변화폭이 작아 오류를 줄일 수 있어 데이터 전송에서 많이 쓰인다.

이 글에서는 그레이 코드를 어떻게 생성할 수 있는지 생각해보자.

 

 

예시

 

0에서 7까지를 3비트 이진 코드와 그레이 코드로 나타내면 다음과 같다.

 

 

 

 

	이진 코드	그레이 코드
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비트 그레이 코드를 만드는 방법을 보면 몇 비트에서든 그레이 코드를 만들 수 있다는 사실을 알 수 있을 것이다.

먼저 2비트 그레이 코드를 쓰고(00, 01, 11, 10), 그 밑에 다시 2비트 그레이 코드를 역순으로(10, 11, 01, 00) 적는다.

 

그 다음 앞쪽 4개 코드의 앞에는 0을, 뒤쪽 4개 코드의 앞에는 1을 붙이면 3비트 그레이 코드가 만들어진다.

 

이렇게 n비트 그레이 코드를 이용하여 n+1비트 그레이 코드를 만들 수 있다.

정리하자면, n비트 그레이 코드를 적고 앞에 0을 붙인 것과 n비트 그레이 코드를 역순으로 적고 앞에 1을 붙인 것을 이으면 n+1비트 그레이 코드가 된다.

 

 

 

 

그레이 코드 출력 프로그램(C언어)

 

 

#include <stdio.h>

#define MAXN 20		// maximum for bits

/**
 *	A function to print out the gray-bits
 */
void print_code(int code[], int len) {
	for(int i = 0; i < len; i++) {
		printf("%d", code[i]);
	}
	printf("\n");
}

/**
 * A function that print out gray codes using recursive calls
 * @param code gray code data
 * @param n size of code
 * @param index current index
 * @param reverse reverse or not
 */
void print_gray(int code[], int n, int index, int reverse) {
	if(index == n) {
		print_code(code, n);
		return;
	}

	code[index] = reverse;
	print_gray(code, n, index + 1, 0);
	code[index] = 1 - reverse;
	print_gray(code, n, index + 1, 1);
}

int main(int argc, char** argv) {
	int code[MAXN], n;

	scanf("%d", &n);
	print_gray(code, n, 0, 0);
	return 0;
}

 

출력 결과