그레이 부호

3. 그레이 코드의 원리 및 특징

벨 연구소의 연구원 프랭크 그레이(Frank Gray (연구원))는 1947년 특허 출원에서 "반사 이진 코드"라는 용어를 도입하면서 이 코드가 "아직 인정된 이름이 없다"고 언급했다. 그는 이 코드가 "일종의 반사 과정을 통해 기존 이진 코드로 구성될 수 있다"는 사실에서 이름을 따왔다.

그레이 코드의 표준 인코딩에서 최하위 비트는 2 on, 2 off의 반복 패턴을 따른다. 다음 숫자는 4 on, 4 off의 패턴을 따릅니다. ''i''번째 최하위 비트는 2^''i'' on, 2^''i'' off의 패턴을 따른다. 최상위 숫자는 예외인데, ''n''비트 그레이 코드의 경우 최상위 숫자는 2^''n''-1 on, 2^''n''-1 off의 패턴을 따르며, 이는 두 번째로 중요한 숫자와 동일한(순환) 값 시퀀스이지만 2^''n''-2 자리만큼 앞으로 이동한다. 4비트 버전은 아래 표와 같다.

십진수 15의 경우, 코드는 단 하나의 스위치 변경으로 십진수 0으로 롤오버된다. 이것을 코드의 ''순환'' 또는 ''인접성 속성''이라고 한다.

원칙적으로 주어진 단어 길이에 대해 둘 이상의 코드가 있을 수 있지만, 그레이 코드라는 용어는 음이 아닌 정수를 위한 특정 이진 코드, 즉 ''이진 반사 그레이 코드'' 또는 '''BRGC'''에 처음 적용되었다.

이진 반사 그레이 코드 (BRGC)는 다음과 같은 방법으로 만들 수 있다.

• ''n'' 비트의 이진 반사 그레이 코드 목록은 목록을 반사하고(즉, 항목을 역순으로 나열), 원래 목록의 항목에 이진 0을 접두사로 붙이고, 반사된 목록의 항목에 이진 1을 접두사로 붙인 다음 원래 목록을 반전된 목록과 연결하여 ''n'' − 1 비트의 목록에서 재귀적으로 생성할 수 있다. 예를 들어, ''n'' = 2 목록에서 ''n'' = 3 목록을 생성하는 과정은 다음과 같다.

1비트 그레이 코드는 ''G''₁ = (0,1)이다. 이는 길이가 0인 단일 항목으로 구성된 0비트 그레이 코드 ''G''₀ = (Λ)에서 위와 같이 재귀적으로 구축된 것으로 생각할 수 있다.

''G''_''n''에서 ''G''_''n''+1을 생성하는 이 반복적인 프로세스는 표준 반사 코드의 다음 속성을 갖는다.

• ''G''_''n''은 숫자 0, ..., 2^''n'' − 1의 순열이다. (각 숫자는 목록에 정확히 한 번 나타난다.)
• ''G''_''n''은 ''G''_''n''+1의 첫 번째 절반으로 포함된다.
• 코딩은 일단 이진수가 ''G''_''n''에 나타나면 모든 더 긴 목록에서 동일한 위치에 나타난다는 의미에서 '안정적'이다. 따라서 숫자의 '반사적인' 그레이 코드 값에 대해 이야기하는 것이 의미가 있다. ''G''(''m'') = 0부터 세는 ''m''번째 반사 그레이 코드이다.
• ''G''_''n''의 각 항목은 이전 항목과 단 하나의 비트만 다릅니다. (해밍 거리는 1입니다.)
• ''G''_''n''의 마지막 항목은 첫 번째 항목과 단 하나의 비트만 다릅니다. (코드는 순환적입니다.)

4. 그레이 코드와 이진 코드 간 변환

C^영어에서 다음 함수는 이진 숫자와 그에 해당하는 그레이 부호 간의 변환을 보여준다. 그레이 코드에서 이진 코드로 변환하는 것은 각 비트를 한 번에 처리해야 하는 것처럼 보일 수 있지만, 더 빠른 알고리즘이 존재한다.^[1]

• 이진수를 그레이 코드로 변환하는 함수는 다음과 같다.

• `^`는 배타적 논리합 연산자이고, `>>`는 오른쪽 시프트 연산자이다.

• 그레이 코드를 이진수로 변환하는 함수는 다음과 같다.

• 각 그레이 코드 비트는 모든 상위 비트와 배타적 OR 연산을 수행한다.

• 32비트 이하의 그레이 코드에 대해 더 효율적인 버전은 다음과 같다.

5. 그레이 코드의 응용

그레이 코드는 디지털 통신 및 위치 인코더 등 다양한 분야에 응용된다.

디지털 통신에서는 오류 정정을 위해 직교 진폭 변조(QAM)과 같은 디지털 변조 방식에서 신호 성상도 배열에 활용된다. 인접한 성상도 점으로 전달되는 비트 패턴이 단 1비트만 다르도록 배열하고, 전방 오류 정정과 결합하여 수신기가 성상도 점이 인접 점의 영역으로 벗어나게 하는 전송 오류를 수정할 수 있게 한다. 이를 통해 전송 시스템은 노이즈에 덜 민감해진다.

위치 인코더에서는 선형 및 회전형 위치 인코더(절대 인코더, 직각 위상 인코더)에 사용되어 이진 인코딩보다 안정적인 위치 정보를 제공한다. 예를 들어, 일부 회전형 인코더는 동심원(트랙)에 전도성 그레이 코드 패턴이 있는 디스크를 사용하고, 각 트랙에는 고정 금속 스프링 접점이 있어 전도성 코드 패턴에 전기적 접촉을 제공한다. 이러한 접점들은 함께 그레이 코드 형태의 출력 신호를 생성한다. 이를 통해 위치 측정 오류를 줄일 수 있다.

십진법에 특화된 글릭슨 코드, O'Brien 코드, 페더릭 코드, 톰킨스 코드 등도 있다.

5. 1. 대한민국에서의 활용

6. 특수 유형의 그레이 코드

• 균형 그레이 코드(Balanced Gray Code): 서로 다른 좌표 위치에서의 변화 횟수를 가능한 한 가깝게 만들어 균일성을 높인 코드이다. 모든 전이 횟수가 같으면 균일(uniformly balanced)하다고 하며, ''n''이 2의 거듭제곱인 경우에만 존재한다. ''n''이 2의 거듭제곱이 아닐 때는 두 전이 횟수의 차이가 최대 2인 ''잘 균형 잡힌(well-balanced)'' 이진 코드를 구성할 수 있다.

• 롱 런 그레이 코드(Long Run Gray Code): 동일한 위치에서 연속적인 숫자 변화 사이의 거리를 최대화한 코드이다. 즉, 가능한 한 오랫동안 비트가 변경되지 않고 유지되는 최소 런 길이를 유지한다.^[5]

• 단조 그레이 코드(Monotonic Gray Code): 상호 연결망 이론에서 유용하며, 특히 프로세서의 선형 배열에 대한 딜레이를 최소화하는 데 사용된다. 이진 문자열의 "가중치"(문자열 내 1의 개수)를 고려할 때, 엄격하게 증가하는 가중치를 가진 그레이 코드는 불가능하지만, 다음 가중치에 도달하기 전에 코드가 두 개의 인접한 가중치를 통과하도록 하여 근사할 수 있다.

• 베케트-그레이 코드(Beckett–Gray Code): 대칭성에 관심이 있었던 아일랜드 극작가 사무엘 베케트의 이름을 따서 명명되었다. 그의 희곡 "쿼드"에서 영감을 받았으며, 특정 제약 조건(FIFO 큐)을 만족하는 코드이다. ''n'' = 2, 5, 6, 7, 8인 경우에는 존재하고, ''n'' = 3 또는 4인 경우에는 존재하지 않는 것으로 알려져 있다.

• 2차원 그레이 코드(Two-dimensional Gray Code): 통신에서 직교 진폭 변조(QAM)의 성상도에서 인접한 점들 간의 비트 오류 수를 최소화하는 데 사용된다. 수평 및 수직 인접 성상도 점은 단일 비트만 다르도록 배열된다.

• Excess-Gray-Code: 특정 코드 값의 일부분(예: 4비트 그레이 코드의 마지막 3비트)을 추출하여 사용하는 코드이다. 원래 값이 증가할 때 추출된 비트에서 거꾸로 카운트하는 속성을 보인다.

7. 그레이 등거리(Gray Isometry)

다음 전단사 매핑 { 0 ↔ 00, 1 ↔ 01, 2 ↔ 11, 3 ↔ 10 }은 등거리 사상을 설정한다. 이는 해밍 거리로 주어진 메트릭을 가진 유한체 $\backslash mathbb\{Z\}\_2^2$ 위의 메트릭 공간과 리 거리로 주어진 메트릭을 가진 유한환 $\backslash mathbb\{Z\}\_4$ (일반적인 모듈러 산술) 위의 메트릭 공간 간의 등거리 사상이다. 이 매핑은 해밍 공간 $\backslash mathbb\{Z\}\_2^\{2m\}$과 $\backslash mathbb\{Z\}\_4^m$의 등거리 사상으로 적절하게 확장된다. 그 중요성은 $\backslash mathbb\{Z\}\_4$에서 환-선형 부호의 $\backslash mathbb\{Z\}\_2^2$에서의 그레이 맵 이미지로, 반드시 선형 부호일 필요는 없는 다양한 "좋은" 부호들 간의 대응을 설정하는 데 있다.

8. 관련 코드

그레이 코드와 유사한 여러 이진 코드들이 존재한다.

• Datex 코드 (지안니니 코드(1954)): O'Brien 코드 II의 변형을 사용한다.
• Varec에서 사용된 코드 (ca. 1954): O'Brien 코드 I의 변형과 12진법 및 16진법 그레이 코드 변형을 사용한다.
• Lucal 코드 (1959): 수정된 반사 이진 코드(MRB)라고도 불린다.
• 길햄 코드(1961/1962): Datex 코드 및 O'Brien 코드 II의 변형을 사용한다.
• Leslie 및 Russell 코드 (1964):
• Royal Radar Establishment 코드
• Hoklas 코드 (1988):

• Petherick 코드 (1953): 왕립 항공 연구소(RAE) 코드라고도 알려져 있다.
• O'Brien 코드 I 및 II (1955): O'Brien I형 코드는 1954년에 Varec에서 사용되었다. 나중에 Watts 코드 또는 Watts 반사 십진법(WRD) 코드로도 알려졌으며, 때로는 모호하게 반사 이진 수정 그레이 코드라고도 한다. O'Brien II형 코드는 이미 1954년에 Datex에서 사용되었다.
• Excess-3 그레이 코드 (1956): 그레이 excess-3 코드, 그레이 3-excess 코드, 반사 excess-3 코드, excess 그레이 코드, 그레이 excess 코드, 10-excess-3 그레이 코드 또는 Gray–Stibitz 코드라고도 불린다. ITT의 Frank P. Turvey Jr.가 설명했다.
• Tompkins 코드 I 및 II (1956):
• Glixon 코드 (1957): 때로는 모호하게 수정된 그레이 코드라고도 한다.

• 글릭슨 코드: 9에 해당하는 부호는 그레이 코드가 "1101"인 반면 Glixon code는 "1000"이다. 9와 0의 변화에서도 해밍 거리가 1이 된다.
• O'Brien 코드: Glixon 코드와 마찬가지로, 9와 0의 변화에서도 해밍 거리가 1이 된다. 0에 대해 "0000"을 대응시키지 않는 부호화 중 하나이다.
• 페더릭 코드: 최상위 비트를 반전시킴으로써, 9의 보수(''n''에 대해 9''-n'')가 되는 부호화 중 하나이다.
• 톰킨스 코드: Glixon 코드와 마찬가지로, 9와 0의 변화에서도 해밍 거리가 1이 된다. 0에 대해 "0000"을 대응시키지 않는 부호화 중 하나이다. 또한, 최하위 비트 이외의 모든 비트에서 1인 비율이 1/2이 된다 (최하위 비트는 6/10의 비율로 1이다).

참조

_[1] 웹사이트 Understanding Gray Code: A Reliable Encoding System https://graycode.ie/[...] 2023-06-30
_[2] 웹사이트 How to generate Gray Codes for non-power-of-2 sequences https://www.eetimes.[...] 2022-01-29
_[3] OEIS A290772
_[4] 간행물 Construction of Uniform Gray Codes
_[5] 간행물 A Survey of Combinatorial Gray Codes http://www4.ncsu.edu[...] Society for Industrial and Applied Mathematics 1997-01-01
_[6] 웹사이트 'single track gray code' sought for encoding 360 degrees with 9 sensors https://www.experts-[...] 2008-07-25
_[7] 웹사이트 9-Bit Absolute Singletrack Gray Code Rotary Encoder https://www.thingive[...]
_[8] 특허 Pulse code communication 1953-03-17
_[9] 특허 Encoding Circuit 1956-01-31
_[10] 특허 Direction-Sensitive Binary Code Position Control System 1958-02-11
_[11] 웹사이트 グレイコードと実数 立木秀樹 http://www.i.h.kyoto[...]
_[12] 서적 컴퓨터 구조 이한출판사
_[13] 웹사이트 The Aggregate Magic Algorithms: Gray Code Conversion http://aggregate.org[...]