그레이 코드(Gray Code)는 인접한 코드 간에 1비트만 차이가 나도록 구성된 이진 코드 시스템으로, 회전 인코더나 오류 보정 등에서 널리 사용됩니다. 이 글에서는 파이썬을 이용해 그레이 코드 문자열을 일반 이진수 문자열로 변환하는 알고리즘을 구현하고 설명합니다.
구현 예제
핵심 로직은 가장 상위 비트(MSB)는 그대로 유지하고, 이후 비트부터는 이전 이진수 비트와 현재 그레이 코드 비트를 XOR(배타적 논리합) 연산하여 구하는 것입니다. 아래 코드는 문자열 연산으로 이를 구현한 예시입니다.
def flip_bit(bit):
"""비트 반전: '0' -> '1', '1' -> '0'"""
return '1' if bit == '0' else '0'
def gray_to_binary(gray_str):
"""그레이 코드 문자열을 이진수 문자열로 변환"""
if not gray_str:
return ""
binary = gray_str[0] # MSB는 동일
for i in range(1, len(gray_str)):
# 현재 그레이 비트가 '0'이면 이전 이진 비트 유지, '1'이면 반전
if gray_str[i] == '0':
binary += binary[i - 1]
else:
binary += flip_bit(binary[i - 1])
return binary
# 테스트 실행
gray_code = "01101001"
print(f"그레이 코드: {gray_code}")
print(f"변환된 이진수: {gray_to_binary(gray_code)}")실행 결과
그레이 코드: 01101001
변환된 이진수: 01001110코드 동작 원리 상세 분석
- flip_bit 함수: 인자로 받은 비트 문자열('0' 또는 '1')을 반전시켜 반환하는 헬퍼(helper) 함수입니다.
- gray_to_binary 함수: 변환의 진입점입니다.
- 입력된 그레이 코드의 첫 번째 비트(최상위 비트)는 이진수의 첫 번째 비트와 동일하므로 그대로 복사합니다.
- 두 번째 비트부터 루프를 돌며 다음 규칙을 적용합니다:
Binary[i] = Binary[i-1] XOR Gray[i]원리에 따라, 그레이 코드 현재 비트가'0'이면 이전 이진 비트를 그대로 가져오고,'1'이면 이전 이진 비트를 반전(flip_bit)시킵니다.
- 시간 복잡도: O(n) - 입력된 문자열의 길이 n에 비례하여 한 번만 순회하므로 효율적입니다.
참고: 비트 연산자를 활용한 대안 구현
문자열 처리 대신 정수형 비트 연산을 사용하면 더 간결하고 빠르게 구현할 수 있습니다.
def gray_to_binary_int(n):
"""정수형 그레이 코드를 정수형 이진수로 변환"""
mask = n
while mask != 0:
mask >>= 1
n ^= mask
return n
# 사용 예
gray_val = 0b01101001 # 105
bin_val = gray_to_binary_int(gray_val)
print(f"이진수: {bin(bin_val)}") # 0b1001110 (앞의 0은 생략됨)이 방식은 n ^= (n >> 1) 과정을 반복하며 상위 비트부터 하위 비트까지 누적 XOR을 수행하는 원리입니다. 실제 애플리케이션에서는 이 정수 연산 방식을 권장합니다.