그레이코드

반사 이진 코드(RBC)는 프랭크 그레이(Frank Gray)의 이름을 따서 반사 이진 코드(RB) 또는 그레이 코드라고도 하며, 두 개의 연속적인 값이 오직 하나의 비트(이진 숫자)에서만 서로 다른 이진 숫자 시스템의 순서입니다.

예를 들어, 십진수 값 "1"을 이진법으로 표현하면 일반적으로 "001"이고 "2"는 "010"입니다.회색 코드에서 이러한 값은 "001" 및 "011"로 표시됩니다.이렇게 하면 1에서 2로 값을 증가시키면 2비트가 아니라 1비트만 변경해야 합니다.

회색 코드는 전기 기계식 스위치의 거짓 출력을 방지하고 디지털 지상파 텔레비전 및 일부 케이블 TV 시스템과 같은 디지털 통신에서 오류 수정을 용이하게 하기 위해 널리 사용됩니다.이러한 장치에 그레이 코드를 사용하면 논리 연산을 단순화하고 ^[3]실제 오류를 줄이는 데 도움이 됩니다.

기능.

많은 장치가 스위치를 닫고 열어서 위치를 표시합니다.해당 장치가 자연 이진 코드를 사용하는 경우 위치 3과 4는 서로 옆에 있지만 이진 표현의 세 비트는 모두 다릅니다.

십진법	이진법
...	...
3	011
4	100
...	...

자연 이진 코드의 문제는 물리적 스위치가 이상적이지 않다는 것입니다. 물리적 스위치가 정확히 동기화되어 상태를 변경할 가능성은 매우 낮습니다.위에 표시된 두 상태 사이의 전환에서는 세 개의 스위치 모두 상태가 바뀝니다.모든 것이 바뀌는 짧은 시간 동안 스위치는 일부 가짜 위치를 읽습니다.키바운스가 없어도 전환은 011 — 001 — 101 — 100처럼 보일 수 있습니다.스위치가 001 위치에 있는 것처럼 보일 때 관찰자는 그것이 "진짜" 위치 1인지 아니면 다른 두 위치 사이의 전환 상태인지 알 수 없습니다.출력이 조합 로직을 통해 순차적 시스템에 입력되는 경우, 순차적 시스템은 잘못된 값을 저장할 수 있습니다.

이 문제는 한 번에 하나의 스위치만 변경하면 해결할 수 있으므로 위치의 모호성이 전혀 없으므로 연속되는 정수 집합 각각에 코드를 할당하거나 원형 목록의 각 멤버에게 두 개의 코드 단어가 동일하지 않고 각각의 두 개의 인접 코드 단어가 정확히 하나의 기호만큼 차이가 나는 기호 단어를 할당합니다.이러한 코드는 인접 코드 간의 해밍 거리가 1인 것을 ^{[4][5][6][7][8]}참조하여 단위 거리, 단일 거리, 단일 단계^{[9][10][7][8]}, 단위성 또는 동기성 ^[9]코드라고도 합니다.

발명.

원칙적으로 주어진 단어 길이에 대해 두 개 이상의 이러한 코드가 있을 수 있지만, 그레이 코드라는 용어는 음이 아닌 정수에 대한 특정 이진 코드, 이진 반사 그레이 코드 또는 BRGC에 처음 적용되었습니다.벨 연구소 연구원 조지 R. Stibitz는 ^[11][12][13]1943년에 부여된 1941년 특허 출원에서 그러한 코드를 설명했습니다.프랭크 그레이(Frank Gray)는 1947년 자신의 특허 출원에서 이진 코드를 반영한 용어를 소개하면서 코드가 "아직 인식되지 않은 이름"^[14]을 가지고 있다고 언급했습니다.그는 이 이름이 "일종의 반사 과정에 의해 기존의 이진 코드로부터 구축될 수 있다"는 사실에서 유래했습니다.

표준 부호화에서 최하위 비트는 2 on, 2 off (… 11001100 … )의 반복 패턴을 따르고 다음 자리는 4 on, 4 off의 패턴을 따르며 최하위 비트는 2 onⁱ 2 off의ⁱ 패턴을 따릅니다.n비트 회색 코드의 경우, 가장 의미 있는 숫자는 2^n-1 on 2 off^n-1 뒤를 따르며, 두 번째 의미 있는 숫자와 동일하지만 시퀀스의 다른 지점에서 시작합니다.이에 대한 4비트 버전은 다음과 같습니다.

십진법	이진법	회색	십진법 회색의
0	0000	0000	0
1	0001	0001	1
2	0010	0011	3
3	0011	0010	2
4	0100	0110	6
5	0101	0111	7
6	0110	0101	5
7	0111	0100	4
8	1000	1100	12
9	1001	1101	13
10	1010	1111	15
11	1011	1110	14
12	1100	1010	10
13	1101	1011	11
14	1110	1001	9
15	1111	1000	8

decimal 15의 경우 단 한 번의 스위치 변경만으로 decimal 0으로 롤오버됩니다.이를 ^[15]코드의 순환 속성 또는 인접 속성이라고 합니다.

현대 디지털 통신에서 회색 코드는 오류 수정에 중요한 역할을 합니다.예를 들어, QAM과 같은 디지털 변조 방식에서, 일반적으로 4비트 이상의 심볼로 데이터가 전송되는 경우, 신호의 콘스텔레이션 다이어그램은 인접한 콘스텔레이션 포인트들에 의해 전달되는 비트 패턴들이 단지 1비트 차이가 나도록 배열됩니다.이를 단일 비트 오류를 수정할 수 있는 순방향 오류 수정과 결합함으로써 수신기는 별자리 점이 인접한 점의 영역으로 이탈하게 하는 전송 오류를 수정할 수 있습니다.이로 인해 변속기 시스템은 소음에 덜 민감하게 됩니다.

스티비츠가 그레이 이전에 이 코드를^[11][12][13] 설명했음에도 불구하고, 반사된 이진 코드는 나중에 그레이를 사용한 다른 사람들에 의해 그레이의 이름을 따서 붙여졌습니다.1953년에 출원된 두 개의 다른 특허 출원은 "회색 코드"를 "반영된 이진 코드"^[16][17]의 대체 이름으로 사용합니다. 그 중 하나는 이름 ^[17]중 "최소 오류 코드"와 "순환 순열 코드"를 나열하기도 합니다.1954년 특허 출원은 "벨 전화 회색 코드"^[18]를 언급하고 있습니다.다른 이름으로는 순환 이진 코드,^[12] 순환 진행 코드,^[19][12] 순환 순열 ^[20]이진 코드, 순환 순열 이진 코드,^[21][22] 순환 순열 이진 코드 등이 있습니다.

그레이 코드는 19세기 전기 장치 발명가 엘리샤 ^{[13][23][24][25]}그레이에게 잘못 귀속되기도 합니다.

역사 및 실무적용

수학적 퍼즐

반사된 이진 코드는 공학자들에게 알려지기 전에 수학 퍼즐에 적용되었습니다.

이진 반사 회색 코드는 1872년 프랑스의 ^[26][13]루이 그로스에 의해 기술된 순차적인 기계적 퍼즐 메커니즘인 고전적인 중국 고리 퍼즐의 기본 계획을 나타냅니다.

1883년 ^{[27][28][29][30]}프랑스의 에두아르 루카스의 게임을 바탕으로 하노이의 탑 문제에 대한 해결책이 될 수 있습니다.이와 유사하게, 소위 부쿠레슈티의 타워와 클라겐푸르트의 타워라는 게임 구성은 3진 및 5진 그레이 코드를 생성합니다.^[31]

마틴 가드너(Martin Gardner)는 1972년 8월 사이언스 아메리칸(Scientific American)^[32]지에 실린 수학 게임 칼럼에서 그레이 코드에 대한 대중적인 설명을 썼습니다.

이 코드는 또한 하이퍼큐브에서 해밀턴 사이클을 형성하며, 각 비트는 하나의 차원으로 보여집니다.

전신부호

프랑스 기술자 에밀 보도(Emile Baudot)가 인쇄 전신 시스템에 6단위(6비트) 코드를 사용하는 것에서 5단위 코드로 바뀌었을 때, 1875년 또는^[33] 1876년에,^[34][35] 그는 반사된 이진 코드를 사용하여 인쇄 바퀴에 알파벳 문자를 주문하고, 오직 세 개의 비트만을 사용하는 코드를 모음에 할당했습니다.모음과 자음이 알파벳 ^[36][37][38]순서대로 정렬되고 다른 기호들이 적절히 배치된 5비트 문자 코드는 반영된 ^[13]이진 코드로 인식되었습니다.이 코드는 보도^[39] 코드(Baudot code)로 알려지게 되었고,^[40][41][38] 약간의 변화를 거쳐 1932년에 결국 국제 전신 알파벳 1번(ITA1, CCITT-1)으로 채택되었습니다.

비슷한 시기인 ^[43][13]1874년,^[42] 독일계 오스트리아인 오토 셰플러는 같은 목적으로 5비트 반사 이진 코드를 사용하여 비엔나에서 또 다른 인쇄 전신기를 시연했습니다.

아날로그-디지털 신호 변환

호환 가능한 컬러 텔레비전에 사용되게 된 시그널링 방법을 발명하여 유명해진 프랭크 그레이는 진공관 기반 장치를 사용하여 아날로그 신호를 반사된 이진 코드 그룹으로 변환하는 방법을 발명했습니다.1947년에 제출된 방법과 장치는 ^[14]1953년에 특허를 받았고 그레이라는 이름은 코드를 고수했습니다.그레이가 특허 받은 "PCM 튜브" 장치는 벨 연구소의 레이먼드 시어스(Raymond W. Sears)가 그레이와 윌리엄 M과 함께 만들었습니다.그레이가 반사된 바이너리 ^[44]코드 아이디어를 낸 구달입니다.

그레이는 아날로그 신호를 디지털로 변환할 때 오류를 최소화하기 위해 코드를 사용하는 데 가장 관심이 많았습니다. 그의 코드는 오늘날에도 이 목적으로 사용되고 있습니다.

포지션 인코더

그레이 코드는 가중 이진 인코딩에 우선하여 선형 및 회전 위치 인코더(절대 인코더 및 직교 인코더)에서 사용됩니다.이렇게 하면 위치의 이진 표현에서 여러 비트가 변경될 때 일부 비트가 다른 비트보다 먼저 변경되어 잘못된 읽기가 발생할 가능성이 없습니다.

예를 들어, 일부 회전식 인코더는 동심원 링(트랙)에 전기 전도성 회색 코드 패턴이 있는 디스크를 제공합니다.각 트랙에는 전도성 코드 패턴에 전기적 접촉을 제공하는 고정 금속 스프링 접점이 있습니다.이들 접점은 함께 회색 코드 형태의 출력 신호를 생성합니다.다른 인코더는 광학 또는 자기 센서를 기반으로 한 비접촉 메커니즘을 사용하여 그레이 코드 출력 신호를 생성합니다.

이동 인코더의 메커니즘이나 정밀도에 관계없이 코드가 읽히는 정확한 순간(샘플링)에 코드가 변경될 수 있기 때문에 특정 위치(코드 경계에서)에서 위치 측정 오류가 발생할 수 있습니다.이진 출력 코드는 모든 비트를 동시에 변경하는 것이 불가능하기 때문에 중대한 위치 측정 오류를 유발할 수 있습니다.위치가 샘플링되는 순간에 일부 비트가 변경되고 일부 비트가 변경되지 않은 경우 샘플링된 위치가 부정확하게 됩니다.절대 인코더의 경우 표시된 위치가 실제 위치에서 멀리 떨어져 있을 수 있으며 증분 인코더의 경우 위치 추적을 손상시킬 수 있습니다.

반대로 위치 인코더에서 사용하는 회색 코드는 연속적인 두 위치의 코드가 1비트씩만 다르므로 한 번에 한 비트만 변경할 수 있습니다.이 경우 최대 위치 오차가 작아져 실제 위치에 인접한 위치를 나타냅니다.

유전자 알고리즘

그레이 코드의 해밍 거리 특성으로 인해 유전자 ^[15]알고리즘에 사용되기도 합니다.코드의 돌연변이는 대부분 점진적인 변화를 허용하지만, 때로는 한 번의 비트 변경으로 인해 큰 도약을 초래하고 새로운 특성으로 이어질 수 있기 때문에 이 분야에서 매우 유용합니다.

부울 회로 최소화

회색 코드는 1953년부터^[45][46][47] 카노 지도의 축을 라벨링하는 데에도 사용되고 1958년부터 ^{[48][49][50][51]}헨들러 원 그래프에도 사용되며, 논리 회로 최소화를 위한 그래픽 방법입니다.

오류수정

현대 디지털 통신에서 회색 코드는 오류 수정에 중요한 역할을 합니다.예를 들어, QAM과 같은 디지털 변조 방식에서, 일반적으로 4비트 이상의 심볼로 데이터가 전송되는 경우, 신호의 콘스텔레이션 다이어그램은 인접한 콘스텔레이션 포인트들에 의해 전달되는 비트 패턴들이 단지 1비트 차이가 나도록 배열됩니다.이를 단일 비트 오류를 수정할 수 있는 순방향 오류 수정과 결합함으로써 수신기는 별자리 점이 인접한 점의 영역으로 이탈하게 하는 전송 오류를 수정할 수 있습니다.이로 인해 변속기 시스템은 소음에 덜 민감하게 됩니다.

클럭 도메인간 통신

디지털 로직 설계자는 서로 다른 클럭 주파수에서 동작하는 동기 로직 간에 멀티비트 카운트 정보를 전달하기 위해 그레이 코드를 광범위하게 사용합니다.이 논리는 서로 다른 "시계 영역"에서 작동하는 것으로 간주됩니다.이것은 다양한 클록킹 주파수로 작동하는 대형 칩 설계의 기본입니다.

최소의 노력으로 상태를 순환

시스템이 일부 컨트롤 집합의 모든 가능한 온오프 상태 조합을 순환해야 하고 컨트롤 변경 시 사소한 비용(예: 시간, 마모, 인적 작업)이 필요한 경우 그레이 코드는 각 상태 조합에 대해 설정 변경 횟수를 단 한 번의 변경으로 최소화합니다.예를 들면 수동으로 작동하는 밸브의 모든 설정 조합에 대해 배관 시스템을 테스트하는 것이 될 수 있습니다.

균형 잡힌 회색 코드를 ^[52]구성할 수 있으며, 매 비트 동일하게 자주 플립됩니다.비트 플립이 균등하게 분포되어 있으므로 다음과 같은 방법으로 최적입니다. 균형 잡힌 회색 코드는 각 자리에서 비트 플립의 최대 카운트를 최소화합니다.

그레이 코드 카운터 및 산술

조지 R. Stibitz는 ^[11][12][13]이미 1941년에 이진 펄스 카운팅 장치에 반사된 이진 코드를 사용했습니다.

그레이 코드 카운터의 일반적인 용도는 서로 다른 클럭 도메인에 존재하는 읽기 및 쓰기 포트가 있는 FIFO(first-in, first-out) 데이터 버퍼를 구축하는 것입니다.이러한 이중 포트 FIFO 내부의 입력 및 출력 카운터는 종종 그레이 코드를 사용하여 카운트가 클럭 도메인을 ^[53]넘을 때 잘못된 과도 상태가 캡처되는 것을 방지합니다.업데이트된 읽기 및 쓰기 포인터는 각 도메인에서 FIFO 빈 상태와 전체 상태를 추적할 수 있도록 변경될 때 클럭 도메인 간에 전달되어야 합니다.포인터의 각 비트는 이 클록 도메인 전송을 위해 비결정적으로 샘플링됩니다.따라서 각 비트에 대해 이전 값 또는 새 값이 전파됩니다.따라서 샘플링 포인트에서 멀티비트 포인터의 한 비트 이상이 변경되는 경우 "잘못된" 이진 값(새 값도 이전 값도 아님)이 전파될 수 있습니다.그레이 코드는 한 비트만 변경할 수 있다고 보장함으로써 가능한 샘플링 값이 새 또는 이전 멀티비트 값임을 보장합니다.일반적으로 회색 길이의 2중 전력 코드가 사용됩니다.

때때로 전자 시스템에서 디지털 버스는 한 번에 하나씩만 증가하거나 감소할 수 있는 양을 전달하는 데 사용됩니다. 예를 들어, 클록 도메인 사이 또는 디지털-아날로그 변환기로 전달되는 이벤트 카운터의 출력입니다.이러한 응용 프로그램에서 회색 코드의 장점은 코드의 비트를 나타내는 많은 와이어의 전파 지연 차이로 인해 수신된 값이 회색 코드 시퀀스를 벗어난 상태를 통과할 수 없다는 것입니다.이것은 기계적인 인코더의 구성에서 그레이 코드의 장점과 유사하지만, 이 경우 그레이 코드의 소스는 전자 카운터입니다.카운터 자체는 그레이 코드로 카운트해야 합니다. 또는 카운터가 바이너리로 실행되는 경우 카운터의 출력 값이 그레이 코드로 변환된 후 다시 잠가야 합니다. 왜냐하면 값이 바이너리에서 ^{[nb 1]}그레이 코드로 변환될 때,이진 데이터 비트가 이진-회색 변환 회로에 도달하는 시간의 차이는 코드가 순서를 완전히 벗어난 상태를 잠깐 통과할 수 있음을 의미할 수 있습니다.카운트 값을 그레이 코드로 변환하는 회로 뒤에 클록 레지스터를 추가하면 지연 시간의 클록 사이클이 발생할 수 있으므로 그레이 코드로 직접 카운트하는 ^[54]것이 유리할 수 있습니다.

그레이-코드 카운터에서 다음 카운트 값을 생성하려면 저장되는 현재 카운트 값을 증가시킬 몇 가지 조합 로직이 필요합니다.그레이 코드 번호를 증가시키는 한 가지 방법은 일반 이진 ^[55]코드로 변환하고 표준 이진 덧셈기로 하나를 추가한 다음 결과를 그레이 ^[56]코드로 다시 변환하는 것입니다.이진 리플 ^[57]카운터에서 마스터 슬레이브 플립 플롭의 첫 번째 래치에서 출력을 가져오는 것을 포함하여 회색 코드로 계산하는 다른 방법에 대해서는 Robert W. Doran의 보고서에서 설명합니다.

그레이 코드 주소 지정

프로그램 코드의 실행은 일반적으로 로컬 연속 주소의 명령 메모리 액세스 패턴을 야기하므로, 이진 주소 대신 그레이 코드 주소 지정을 사용하는 버스 인코딩은 주소 비트의 상태 변화의 수를 크게 줄일 수 있으므로 일부 저전력 ^[58][59]설계에서 CPU 전력 소모를 줄일 수 있습니다.

n비트 회색 코드 구성

n 비트에 대한 이진 반사 그레이 코드 리스트는 리스트를 반영함으로써 n - 1 비트에 대해 리스트로부터 재귀적으로 생성될 수 있습니다(즉, 엔트리를 역순으로 나열함), 원래 리스트의 엔트리를 이진 0으로, 반사 리스트의 엔트리를 이진 1로 앞에 붙입니다.원래 목록과 반대 ^[13]목록을 연결하는 겁니다예를 들어, n = 2 목록에서 n = 3 목록을 생성하는 경우:

1비트 회색 코드는 G = (0,1)입니다.이는 길이가 0인 단일 항목으로 구성된 0비트 그레이 코드 G = (Ω)에서 위와 같이 재귀적으로 구축된 것으로 생각할 수 있습니다.G에서_n G를 생성하는_n+1 이 반복 과정은 표준 반사 코드의 다음 속성을 명확하게 합니다.

• G는_n 숫자 0, ..., 2ⁿ - 1의 순열입니다. (각 숫자는 목록에 정확히 한 번 나타납니다.)
• G는 G의 전반부로_n+1 내장되어 있습니다_n.
• 따라서 이진수가 G에 나타나면 모든 긴 목록에서 동일한 위치에 나타난다는 점에서 코딩은 안정적입니다. 따라서 0부터 세는 숫자의 반사 그레이 코드 값 G(m) = m번째 반사 그레이 코드 값에 대해 이야기하는 것이 타당합니다.
• G의_n 각 항목은 이전 항목과 1비트씩만 다릅니다. (해밍 거리는 1입니다.)
• G의 마지막_n 항목은 첫 번째 항목과 한 비트만 다릅니다. (코드는 순환입니다.)

이러한 특성은 이진값을 해당 그레이 코드로 단순하고 빠르게 변환하는 방법을 제시합니다.입력 값의 다음으로 높은 비트가 1로 설정되면 각 비트가 반전됩니다.이것은 비트 시프트 및 배타적 연산이 가능한 경우 병렬로 수행할 수 있습니다. n번째 회색 코드는 n ⊕ ${\displaystyle n}$ ${\displaystyle \frac{2}{}}$ ⌋ {\$displaystyle$ n$\opplus \left\l$ floor {\$tfrac {n}{2}}\right\rfloor$ $\}$를 $계산$하여 얻습니다. 0비트 앞에 붙이면 코드 워드의 순서는 변경되지 않고 1비트 앞에 붙이면 코드 워드의 순서가 반대가 됩니다.코드워드의 $위치{\displaystyle }$ i$${\$displaystyle$ i$}$의 비트가 반전되면 ${\displaystyle {2i}^{}}${\$displaystyle$ 2$^{i}$ 코드워드의$$ $인접{\displaystyle {\mathrm{}}^{}}$ 블록 순서가 반대가 됩니다.예를 들어, 비트 0이 3비트 코드워드 시퀀스에서 반전되면, 두 개의 인접 코드워드의 순서가 반대가 됩니다.

000,001,010,011,100,101,110,111 → 001,000,011,010,101,100,111,110 (비트 0 반전)

비트 1이 반전되면 코드워드 2개의 블록이 순서를 바꿉니다.

000,001,010,011,100,101,110,111 → 010,011,000,001,110,111,100,101 (비트 1을 반전)

비트 2가 반전되면 코드워드 4개의 블록이 순서를 반대로 바꿉니다.

000,001,010,011,100,101,110,111 → 100,101,110,111,000,001,010,011 (비트 2 반전)

$따라서$ ${\displaystyle {bi}_{}}$ + ${\displaystyle 1}$= ${\displaystyle 0}$${\$$displaystyle$ $b_{i$$}$ = 0 {\$displaystyle$ $b_{i+1}$ wor {\$displaystyle$ i$+1}$ 의 $블록$ ${\displaystyle {순서}^{}}$를 bi ${\displaystyle {+}_{}}$ ${\displaystyle 1_{}}$$$display 0 {\displaystyle b_{i+1} tt ${\$mathtt {$0}$의 순서를 반대로 하면${\displaystyle {\mathrm{bi}}^{}}$ + 1 {\$displaystyle 2^{i$+1$}$ 의 코드워드 순서를 변경할 수 있습니다.ds $if$ ${\displaystyle {bi}_{}}$+ ${\displaystyle 1_{}}$ = ${\displaystyle 1}${\$displaystyle b_{i+1$} = {\$mathtt {1$입니다. 이제, 이것은 그레이 코드를 생성하는 반사 앤 반사 방법과 정확히 동일한 연산입니다.

역번역을 수행할 때도 비슷한 방법을 사용할 수 있지만, 각 비트의 계산은 다음 상위 비트의 계산값에 따라 달라지므로 병렬로 수행할 수 없습니다.${\displaystyle {gi}_{}}$ ${\displaystyle g_{i}$를 $i${\$displaystyle$ i$}$번째 그레이 부호화 비트(${\displaystyle g_{}}$ 0$${\$displaystyle g_{0}}$를 최상위 비트)라고 ${\displaystyle {가정}_{}}$하고$,$ $bi$ {\$displaystyle b_${$}$를 i {\$displaystyle$ i}번째 이진 ${\displaystyle {부호화}_{}}$ 비트$(b$ 0 {\$displaystyle$ b_${0}$를 최상위 비트)라고 $가정$하면, 역번역은 재귀적으로 주어질 수 있습니다: ${\displaystyle b_{}}$ 0 = ${\displaystyle {}_{}}$ ${\displaystyle 0_{}}${\$display$}$스타일 b_{0}=g_{0$ $bi$ $=$ ${\displaystyle {gi}_{}}$$⊕$ ${\displaystyle {\mathrm{bi}}_{}}$ -${\displaystyle {}_{}}$1 ${\displaystyle b_{i$}$=$$g_{i}\opplus b_{i-1$ 또는 그레이 코드를 이진수로 디코딩하는 것은 그레이 코드의 비트의 프리픽스 합으로 설명할 수 있으며, 프리픽스 합에서 각 개별 합 연산은 모듈로 2를 수행합니다.

이진 패턴 그레이 코드를 반복적으로 구성하려면 0단계에서 코드 ${\displaystyle {}_{}}$ = ${\displaystyle 0}$ ${\displaystyle \mathrm {code} _{0$}={\$mathtt {0$로 시작합니다.그리고 > 0{\$displaystyle$i >$0}$ 에서 i$${\$displaystyle$i}의 이진 표현에서 최하위 1의 비트 위치를 찾고 이전 $코드{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{코드}}_{}}$ ${\displaystyle {\mathrm{i}}_{}}$ - 1 ${\$의 해당 위치에서 비트를 플립하여 다음 $코드{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ i$${\$displaystyle \mathrm {code} _{i$를 가져옵니다.비트 위치 시작 0, 1, 0, 2, 0, 1, 0, 3, ...^{[nb 2]}이러한 값을 계산하기 위한 효율적인 알고리즘은 첫 번째 집합 찾기를 참조하십시오.

회색 코드로 변환 및 변환

C의 다음 함수는 이진수와 그와 관련된 그레이 코드 사이를 변환합니다.그레이-투-바이너리 변환은 각 비트를 한 번에 하나씩 처리해야 하는 것처럼 보일 수 있지만, 더 ^{[60][55][nb 1]}빠른 알고리즘이 존재합니다.

타이프 디프 무기명의 인트 뭉치다;  // 이 함수는 부호가 없는 이진수를 반영된 이진수 그레이 코드로 변환합니다. 뭉치다 이진 토회색(뭉치다 숫자를) {     돌아가다 숫자를 ^ (숫자를 >> 1); // >> 연산자가 오른쪽으로 이동합니다.연산자 ^은 배타적이거나 입니다. }  // 이 함수는 반사된 2진수 그레이 코드 번호를 2진수로 변환합니다. 뭉치다 회색과 이진 연결(뭉치다 숫자를) {     뭉치다 가면을 쓰다 = 숫자를;     하는 동안에 (가면을 쓰다) {           // 각 그레이 코드 비트는 더 중요한 모든 비트와 함께 배타적으로 표시됩니다.         가면을 쓰다 >>= 1;         숫자를   ^= 가면을 쓰다;     }     돌아가다 숫자를; }  // SWAR(SIMD in register) 기법을 사용하여 32비트 이하의 그레이 코드에 보다 효율적인 버전. // 병렬 접두사 XOR 기능을 구현합니다.할당 문은 순서에 상관없이 사용할 수 있습니다. // // 이 기능은 단계를 추가하여 긴 회색 코드에 맞게 조정할 수 있습니다.  뭉치다 회색과 이진 연결32(뭉치다 숫자를) {     숫자를 ^= 숫자를 >> 16;     숫자를 ^= 숫자를 >>  8;     숫자를 ^= 숫자를 >>  4;     숫자를 ^= 숫자를 >>  2;     숫자를 ^= 숫자를 >>  1;     돌아가다 숫자를; } // 4비트 한 번에 변형은 이진수 (abcd)2를 (abcd)2 ^ (00ab)2로 변경한 다음 (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2로 변경합니다. 

최신 프로세서에서는 CLMUL 명령 집합을 활용하여 디코딩 단계에서 ALU 명령의 수를 줄일 수 있습니다.MASK가 0자리 한 자리로 끝나는 상수 이진 문자열인 경우, 회색 인코딩이 x인 MASK의 운반 없는 곱셈은 항상 x 또는 해당 비트 단위의 음수를 제공합니다.

회색 코드의 특수한 유형

실제로 "회색 코드"는 거의 항상 이진 반사 회색 코드(BRGC)를 나타냅니다.하지만, 수학자들은 다른 종류의 회색 코드를 발견했습니다.BRGC와 마찬가지로 각 단어는 단어 목록으로 구성되며, 각 단어는 한 자리의 숫자로만 다음 단어와 다릅니다(각 단어는 다음 단어와 해밍 거리가 1입니다).

n비트에 길이가 2보다 작은ⁿ 회색 코드

길이가 짝수이면 길이가 2보다 작은ⁿ n비트의 이진 그레이 코드를 구성할 수 있습니다.균형 잡힌 회색 코드로 시작하여 시작과 끝 또는 ^[61]중간에 있는 값 쌍을 제거하는 것이 한 가지 가능성입니다.OEIS 시퀀스 A290772는 0을 포함하고 최소 비트 수를 사용하는 길이 2n의 가능한 그레이 시퀀스 수를 제공합니다.

n자리 그레이 코드

이진법으로 반사된 그레이 코드 이외에도 많은 특수한 형태의 그레이 코드가 있습니다.그러한 그레이 코드 유형 중 하나는 불리언 그레이 코드라고도 알려진 n-ary 그레이 코드입니다.이름에서 알 수 있듯이 이 유형의 그레이 코드는 인코딩에서 불리언이 아닌 값을 사용합니다.

예를 들어 3진(삼차) 회색 코드에서는 값 0,1,^[31]2를 사용합니다.(n, k)-회색 코드는 ^[63]k자리의 n자리 회색 코드입니다.(3, 2)-회색 코드의 요소 순서는 00,01,02,12,11,10,20,21,22입니다.(n, k)-회색 코드는 BRGC처럼 재귀적으로 구성될 수도 있고, 반복적으로 구성될 수도 있습니다.(N, k)-회색 코드를 반복적으로 생성하는 알고리즘이 (C에서) 제시됩니다.

// 입력: 기본값, 숫자, 값 // 출력 : 그레이 // 값을 주어진 기본값과 숫자를 가진 회색 코드로 변환합니다. // 값의 시퀀스를 반복하면 시퀀스가 발생합니다. // 한 번에 한 자리만 바뀌는 회색 코드. 공허한 그레이에게(무기명의 기초, 무기명의 숫자들, 무기명의 가치, 무기명의 회색의[숫자들]) {   무기명의 염기 N[숫자들]; // 일반적인 기본 N 숫자를 저장합니다. 항목당 한 자리 수  무기명의 i;  // 루프 변수    // 일반적인 baseN 번호를 baseN array에 넣습니다.10루용, 109  // [9,0,1]로 저장됩니다.  위해서 (i = 0; i < 숫자들; i++) {   염기 N[i] = 가치 % 기초;   가치    = 가치 / 기초;  }    // 일반적인 baseN 번호를 회색 코드 등가로 변환합니다.참고:  // 루프는 가장 중요한 숫자에서 시작해서 아래로 내려갑니다.  무기명의 교대의 = 0;  하는 동안에 (i--) {   // 회색 숫자가 높은 값의 합만큼 아래로 이동합니다.   // 숫자들   회색의[i] = (염기 N[i] + 교대의) % 기초;   교대의 = 교대의 + 기초 - 회색의[i]; // 시프트가 양수가 되도록 밑면에서 풉니다.  } } // 예시들 // 입력 : 값 = 1899, 기본 = 10, 숫자 = 4 // 출력: baseN[] = [9,9,8,1], gray[] = [0,1,7,1] // 입력: 값 = 1900, 기본 = 10, 숫자 = 4 // 출력: baseN[] = [0,0,9,1], gray[] = [0,1,8,1] 

(n,k)-회색 코드에 대한 다른 회색 코드 알고리즘이 있습니다.위 알고리즘에 의해 생성된 (n,k)-회색 코드는 항상 순환적이며,^[63] K가 홀수일 때 Guan에 의해 생성된 것과 같은 일부 알고리즘은 이 속성이 부족합니다.한편, 이 방법으로 한 번에 한 자리의 숫자만 변경되지만 래핑(n - 1에서 0으로 루프)하여 변경할 수 있습니다.Guan의 알고리즘에서 카운트는 교대로 상승과 하강을 반복하여 두 회색 코드 자리 사이의 숫자 차이가 항상 1이 되도록 합니다.

회색 코드는 고유하게 정의되지 않습니다. 이러한 코드의 열에 대한 순열도 회색 코드이기 때문입니다.위의 절차는 숫자의 유의도가 낮을수록 더 자주 바뀌는 코드를 생성하여 일반적인 카운팅 방법과 유사합니다.

각 증분이 최대 1자리 운반 작업으로 수행될 수 있기 때문에 각 증분에서 최대 2자리가 변경되는 변형 삼차수 시스템인 스큐 이진법도 참조하십시오.

균형 잡힌 회색 코드

이진법이 반영된 회색 코드는 많은 시나리오에서 유용하지만 "균일성"^[52]이 부족하기 때문에 특정한 경우에는 최적이 코드가 최적이 아닙니다.균형 잡힌 회색 코드에서는 서로 다른 좌표 위치의 변경 횟수가 최대한 가깝습니다.이것을 더 정확하게 하기 위해, G를 전이$$수열 (δ${\displaystyle {}_{}}$k )$${\$displaystyle$(\$delta _{$k$\})\}$을 가진 R진 완전 그레이 사이클이라 하자; G의 전이 수(스펙트럼)은 다음과 같이 정의된 정수의 집합입니다.

${\displaystyle \display_{k}= \{j\in \mathbb {Z} _{R^{n}}:\delta _{j}=k\} \,,,{\text{ for }} k\in \mathbb {Z} _{n}$

회색 코드는 전환 횟수가 모두 같으면 균일하거나 균일하게 균형을 이루는데, 이 경우 모든 k에 대해 λ k = ${\displaystyle \frac{R^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}${\$displaystyle \limate_{k$}={\$tfrac {R^{n}}}$가 있습니다.분명히 ${\displaystyle \mathrm{R}}$=$$2 {\$displaystyle$R$$= 2$\}$일 때, 그러한 코드는 n이 2의 거듭제곱일 경우에만 존재합니다.n이 2의 거듭제곱이 아닌 경우, 두 번의 전이 횟수 사이의 차이가 최대 $2인$ 균형이 잘 잡힌 이진 코드를 구성할 수 있습니다. 따라서 모든 전이 횟수가 2 ⌊ ${\displaystyle \frac{2^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$ 2 ${\displaystyle \frac{n}{}}$ ⌋ {\$displaystyle$ 2$\left\l$ floor ${2^{n}}$ ⌉ {\$tfrac$ {2n$}}$⌈ \$right\rfloor$} $또는$ ${\displaystyle \frac{2^{}}{}}$ n ${\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{n}{}}$ 2 n$$\ {\$displaystyle 2\left\lceil {2^{$n}$}{2n}}\right\rceil$^[52] 그레이 코드는 모든 전이 계수가 2의 인접 거듭제곱일 때 지수적으로 균형을 맞출 수 있으며, 그러한 코드는 2의 ^[65]거듭제곱일 때마다 존재합니다.

예를 들어 균형 잡힌 4비트 회색 코드는 16개의 전환이 있으며, 이는 4개의 위치(위치당 4개의 전환) 모두에 균등하게 분포될 수 있으므로 균일한 ^[52]균형을 유지할 수 있습니다.

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0

0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0

0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0

0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

반면 균형 잡힌 5비트 회색 코드는 총 32개의 전이를 가지며, 이는 위치 간에 균등하게 분포될 수 없습니다.이 예제에서는 4개의 위치에 각각 6개의 전환이 있고 1개의 위치에는 ^[52]8개의 전환이 있습니다.

1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0

1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1

1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1

1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1

이제 n개마다 n자리의 균형 그레이 코드를 생성할 수 있는 균형이 잘 잡힌 이진 그레이 코드의 구성과^[66][67] 구현을 보여드리겠습니다.주요 원리는 균형 속성이 유지되는 방식으로 n자리 그레이 코드 G가 주어진 (n + 2)자리 그레이 $코드{\displaystyle {}^{}}$ G$'$ {\$displaystyle$ G$'}$를 유도적으로 구성하는 것입니다.이를 위해 G = ${\displaystyle g_{}}$ 0${\displaystyle ,}$ ${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle {2^{}}_{}}$n - ${\displaystyle 1_{}}${\$displaystyle$ G=$g_{0},\ldots,g_{2^{n}-1}$의 파티션을 형식의 비어 있지 않은 블록의 짝수 L로 고려합니다.

${\displaystyle \left\{g_{0}\right\},\left\{g_{1},\ldots,g_{k_{2}}\right\},\left\{g_{k_{2}+1},\ldots,g_{k_{3}}\right\},\ldots,\left\{g_{L-2}+1},\ldots,g_{-2}\right\},\left\{g_{-1}\right\}}$

$여기$서 ${\displaystyle k_{}}$ 1 = ${\displaystyle 0}${\$displaystyle k_{1$}=$0$ $k{\displaystyle L_{}}$ - ${\displaystyle 1_{}}$ = - ${\displaystyle 2}${\$displaystyle k_{L-1$}=-$2$$\},$ k ${\displaystyle L_{}}$ ${\displaystyle \ge }$ ${\displaystyle 1}$(${\displaystyle mod}$ ${\displaystyle 2^{}}$n )$${\$displaystyle k_{L}\equiv -1{\pmod {2^{n}}}).$이 파티션은 (${\displaystyle n}$ ${\displaystyle +}$ ${\displaystyle 2}$)$${\$displaystyle(n+2)}$ $-{\displaystyle }$ 다음과$$ 같은 숫자의 회색 코드를 유도합니다.

${\displaystyle {\mathtt {00}}g_{0}}$

${\displaystyle {\mathtt {00}}g_{1},\ldots,{\mathtt {00}g_{2}},{\mathtt {01}g_{k_{2}},\ldots,{\mathtt {01}g_{1},{\mathtt {11}g_{1},\ldots,{\mathtt {11}g_{2},}$

${\displaystyle {\mathtt {11}}g_{k_{2}+1},\ldots,{\mathtt {11}}g_{k_{3}},{\mathtt {01}g_{k_{3}},\ldots,{\mathtt {01}g_{k_{2}+1},{\mathtt {00}g_{k_{2}+1},\ldots,{\mathtt {00}g_{k_{3}},\ldots,}$

${\displaystyle {\mathtt {00}}g_{-2},{\mathtt {00}g_{-1},{\mathtt {10}g_{-1},{\mathtt {10}g_{-2},\ldots,{\mathtt {10}g_{0},{\mathtt {11}g_{0},{\mathtt {11}g_{-1},{\mathtt {01}g_{-1},{\mathtt {01}g_{0}},{\mathtt {01}g_{0},{\mathtt {10}g_{-1}},{\mathtt {10}g_{0}},{\mathtt {10}g_{0},{\mathtt {10}g_{0},{\mathtt {$

전이 다중도를 정의하면

${\displaystyle m_{i}=\left \left\{j:\lot _{k_{j}}=i,1\leq j\leq L\right\}\right }$

파티션에서 연속된 블록 사이의 위치 i가 변경되는 횟수가 되고, 이 파티션에 의해 유도된 (n + 2) 자리 회색 코드의 경우 $전이$ 스펙트럼 λ $'$ {\$displaystyle \lambda '_{i$}}는

${\displaystyle \displaystyle \display'_{i}={\text{case}4\display_{i}-2m_{i},&{\text{if}}}0\leq i<n\L,&{\text{그렇지 않으면}}\end{case}}$

이 구성의 섬세한 부분은 균형 잡힌 n자리 회색 코드의 적절한 분할을 찾는 것입니다. 코드에 의해 유도된 코드가 균형을 유지하도록 하지만 이를 위해서는 전이 다중도만이 중요합니다. 두 개의 연속된 블록을 한 $자리{\displaystyle }$ i$${\$displaystyle$ i$}$ 전이$$ 위에서 결합하고 다른 $자리{\displaystyle }$ i ${\displaystyle$에서 다른 블록을 분할하는 것입니다.$$i$}$ 전환은 전환 스펙트럼$$${\displaystyle {\lambda }_{}^{}}$ i$'$ {\$displaystyle \lambda '_{i$과(와) 완전히 동일한 회색 코드를 생성하므로, 예를 들어 $i$ ${\displaystyle$ i$}$의 첫 $번째$ ${\displaystyle {mi}_{}}${\$displaystyle m_{i}$ 전환을 두 블록 사이에 있는 전환으로 지정할 수 $있습니다$.R ${\displaystyle \ge 0}$ (${\displaystyle mod\mathrm{}}$ 4${\displaystyle )}${\$displaystyle$ R$\equiv$ 0${\pmod {4}},$ R$$ ${\displaystyle \mathrm{n}}$ ${\displaystyle {}^{}}$0 (${\displaystyle mod}$ n${\displaystyle )}${\$displaystyle$ R$^{n}\equiv$ 0${\pmod {n$일 때 통일된 코드를 찾을 수 있으며, 이 구성은 R-ary 케이스로도 ^[66]확장할 수 있습니다.

장기 회색 코드

긴 실행(또는 최대 간격) 회색 코드는 동일한 위치에서 연속적인 숫자 변경 사이의 거리를 최대화합니다.즉, 모든 비트의 최소 런 길이는 ^[68]가능한 한 오랫동안 변하지 않습니다.

모노톤 그레이 코드

모노톤 코드는 상호 연결 네트워크 이론, 특히 프로세서의 선형 ^[69]배열에 대한 확장을 최소화하는 데 유용합니다.이진 문자열의 가중치를 문자열 내 1의 수로 정의하면 가중치가 엄격하게 증가하는 회색 코드를 가질 수 없음이 분명하지만 다음 가중치에 도달하기 전에 코드를 인접한 두 개의 가중치를 통해 이를 근사화할 수 있습니다.

모노톤 그레이 코드의 개념을 다음과 같이 공식화할 수 있습니다. $하이퍼큐브$ ${\displaystyle Q_{}}$ n = (${\displaystyle V_{}}$ n${\displaystyle {}_{}{En}_{}}$ )$${\$displaystyle$ Q_${n$}= ($V_{n$}},$E_{$n}}}의 파티션을 가중치가 같은 정점 수준으로 생각해 보십시오.

${\displaystyle V_{n}(i)=\{v\in V_{n}:v{\text{weight}}}i\}$

0 ${\displaystyle \le }$ ${\displaystyle i}$ ${\displaystyle \le }$ ${\displaystyle n}$ ${\displaystyle$ 0$\leq$i\$leq$ n$\}$일 경우.이 수준은 V${\displaystyle {}_{}n}$ (${\displaystyle }$i ) = ( ${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$i )$${\$displaystyle V_{n}(i)$ =\$textstyle${\$binom {n}{i$을(를) ${\displaystyle 만족}$합니다. ${\displaystyle Q_{}}$n (${\displaystyle i}$${\displaystyle )}$$${\$displaystyle$ Q_${n}(i)$을 ${\displaystyle V_{}{n}_{}}$ (${\displaystyle \mathrm{i}}$ ${\displaystyle +}$ 1${\displaystyle )}$ ${\displaystyle$ Q_${n}}$에서 유도된 Q ${\displaystyle n_{}}$ ${\$displaystyle Q_${n}(i)$ ∪ $V_{n}(i$+$1$ and ${\displaystyle E_{}}$n (${\displaystyle i)}$ ${\displaystyle E_{n}(i)$을 ${\displaystyle Q_{}}n$ (${\displaystyle i)}$ {\$displaystyle Q_{n}($i) 의 가장자리라고 $합니다$$.$$(i)$ 그러면 단조 그레이 코드는 ${\displaystyle {Qn}_{}}$ {\$displaystyle Q_{n}$의 해밀턴 $경로$로 경로에서 $δ$ 1$$$∈$ ${\displaystyle {}_{}}$ ($)$ {\$displaystyle$ _{$1}\in$ E_${n}(i)}$가 $δ$ 2 $∈$ E ($)$ ${\displaystyle$ \$delta$ _${2}\in$ E_${n}(j)$ 앞에 $올$ 때마다 $i$ ${\displaystyle \le }$ ${\displaystyle j}$ ${\displaystyle$i\$leq$j$\}$가 됩니다$.$

임의의 n에 대한 단조로운 n자리 그레이 코드의 우아한 구성은 $길이$ 2${\displaystyle (\genfrac{}{}{0ex}{}{\mathrm{nj}}{})}${\$displaystyle$ P_${n,j}}$의 하위 $경로$ ${\displaystyle {Pn,}_{}}$ ${\displaystyle j_{}}$ ${\$$displaystyle$ P_{n,j}}를 재귀적으로 구축하는 아이디어를 기반으로 합니다. ${\displaystyle {En}_{}}$${\displaystyle {}_{}j)}${\$displaystyle$ E_${n}(j$의 가장자리를 가지는 $En$(j) {\displaystyle 2\textstyle {\$binom {n}{j}}.$${\displaystyle {}_{}}$P ${\displaystyle 1_{}}$, 0${\displaystyle }$= ${\displaystyle (0,}$ 1$$) {\$displaystyle P_{1$,0}=({\$mathtt {0}},$ {\$mathtt {1}}$를 $정의$합니다.$)\},$ ${\displaystyle {pn,}_{}}$ ${\displaystyle j_{}}$$=$ j < {\$displaystyle$ j$<0}$ $또는$ ${\displaystyle j}$ $≥$ ${\displaystyle$j\$geqn$일 마다 ${\displaystyle P_{n,j$}$=$\$emptyset$}, 및

${\displaystyle P_{n+1,j}={\mathtt {1}}P_{n,j-1}^{\pi_{n}},{\mathtt {0}P_{n,j}}$

그렇지않으면.여기서, ${\displaystyle {①}_{}}$ n ${\$는 적합하게 정의된 치환이고, ${\displaystyle {②}^{}}$ ${\$ P$^{\pi}}$는 $좌표$가 ② ${\displaystyle \pi$에 의해 치환된 경로 P를 말합니다. 이 경로들은 두 개의 단조 n자리 그레이 $코드{\displaystyle {}_{}^{}}$ ${\displaystyle {Gn}_{}^{}}$(${\displaystyle {1)}_{}^{}}${\$displaystyle$ G_${n}^{(1)}$ 및$$ ${\displaystyle {Gn}_{}^{}}$(${\displaystyle {2)}_{}^{}}$ ${\$를 생성합니다.

${\displaystyle G_{n}^{(1)}=P_{n,0}P_{n,1}^{R}P_{n,2}P_{n,3}^{R}\cdots {\text{ and }}G_{n}^{(2)}=P_{n,0}^{R}P_{n,2}^{R}P_{n,3}\cdots }$

이러한 코드가 실제로 회색 코드인지 확인하는 π n$${\$displaystyle \pi$ _${n}}$의 선택은${\displaystyle {}_{}^{}}$π n = E - 1 ${\displaystyle {(}^{}}$π${\displaystyle {}^{}}$n - ${\displaystyle {}_{}^{}}$)$${\$displaystyle \pi$ _${n$}=$E^{-1}\left(\pi _{n-1}^{2}\right$입니다$.$${\displaystyle {Pn,}_{}}$ ${\displaystyle j_{}}$ ${\$의 처음 몇 개의 값이 아래 표에 나와 있습니다.

새비지의 하위 경로들..

${\displaystyle P_{n,j}}$	j = 0	j = 1	j = 2	j = 3
n = 1	0, 1
n = 2	00, 01	10, 11
n = 3	000, 001	100, 110, 010, 011	101, 111
n = 4	0000, 0001	1000, 1100, 0100, 0110, 0010, 0011	1010, 1011, 1001, 1101, 0101, 0111	1110, 1111

이러한 단조로운 회색 코드는 O(n) 시간 내에 각 후속 요소를 생성할 수 있도록 효율적으로 구현할 수 있습니다.알고리즘은 코루틴을 사용하여 가장 쉽게 설명됩니다.

모노톤 코드는 연결된 모든 정점-과도 그래프가 해밀턴 경로를 포함한다는 로바즈 추측과 흥미로운 연관성을 가지고 있습니다."중간 수준" 하위 $그래프{\displaystyle {}_{}}$ Q ${\displaystyle 2_{}}$n +${\displaystyle {}_{}{1}_{}}$ (${\displaystyle n}$ )$${\$displaystyle$ Q_${2n+1}(n)}$은(즉, 그 오토모피즘 그룹은 과도적이므로, 우리는 오토모피즘을 얻기 위해 좌표뿐만 아니라 이진 숫자들에 재라벨을 붙일 수 있으므로) 각 정점은 동일한 "로컬 환경"을 가지고 다른 정점들과 구별될 수 없습니다.) 그리고 문제이 하위 그래프에서 해밀턴 경로를 찾는 것은 "중간 수준 문제"라고 불리며, 이는 더 일반적인 추측에 대한 통찰력을 제공할 수 있습니다.질문은 n ${\displaystyle \le }$ ${\displaystyle 15}${\$displaystyle$ n$\leq$ 15$\}$에 $대해{\displaystyle }$ 긍정적으로 대답되었으며, 단조 코드에 대한 이전 구성은 길이가 최소 0.839N인 해밀턴 경로를 보장하며, 여기서 N은 중간 수준 하위 ^[70]그래프의 정점 수입니다.

베켓-회색 코드

그레이 코드의 또 다른 종류인 베켓-그레이 코드는 대칭성에 관심이 있었던 아일랜드 극작가 사무엘 베켓의 이름을 따서 지어졌습니다.그의 연극 "쿼드"는 4명의 배우가 등장하고 16개의 시대로 나뉩니다.4명의 배우 중 한 명이 무대에 오르거나 퇴장하는 것으로 매 회차가 끝납니다.연극은 빈 무대로 시작과 끝을 맺는데, 베케트는 배우들의 각 부분집합이 정확히 한 ^[71]번씩 무대에 등장하기를 원했습니다.분명히 현재 무대에 있는 배우들의 집합은 4비트 이진 그레이 코드로 표현될 수 있습니다.그러나 베케트는 대본에 추가적인 제한을 두었는데, 그는 가장 오랫동안 무대에 섰던 배우가 항상 퇴장할 수 있도록 배우들이 출입하기를 바랐습니다.그 후 배우들은 선입선출 대기열로 대표될 수 있고, 그래서 (무대에 있는 배우들 중) 대기열에 있는 배우가 항상 가장 ^[71]먼저 대기열에 있는 배우가 될 수 있습니다.베케트는 그의 플레이에 대한 베케트-그레이 코드를 찾을 수 없었고, 실제로 가능한 모든 시퀀스의 철저한 목록은 n = 4에 대해 그러한 코드가 존재하지 않음을 나타냅니다.이러한 코드는 n = 2, 5, 6, 7, 8에 대해 존재하며 n = 3 또는 4에는 존재하지 않는 것으로 오늘날 알려져 있습니다.8비트 베켓-그레이 코드의 예는 Donald Knuth의 Art of Computer Programming에서 ^[13]찾을 수 있습니다.Sawada와 Wong에 따르면 n = 6에 대한 탐색 공간은 15시간 안에 탐색할 수 있으며, n = 7의 경우에 대한 9,500개 이상의 해결책이 발견되었습니다.

스네이크 인 더 박스 코드

스네이크 인 더 박스 코드 또는 뱀은 n차원 하이퍼큐브 그래프에서 유도 경로의 노드 시퀀스이고, 코일 인 더 박스 ^[73]코드 또는 코일은 하이퍼큐브에서 유도 사이클의 노드 시퀀스입니다.회색 코드로 보는 이 시퀀스는 단일 비트 코딩 오류를 감지할 수 있는 특성을 가집니다.이 ^[5]유형의 코드는 1950년대 후반에 윌리엄 H. 코츠에 의해 처음 기술되었습니다; 그 이후로 주어진 하이퍼큐브 차원에서 가능한 가장 많은 코드워드를 갖는 코드를 찾는 많은 연구가 있었습니다.

단선 그레이 코드

또 다른 종류의 그레이 코드는 노먼 B가 개발한 싱글 트랙 그레이 코드(STGC)입니다.Hiltgen, Paterson, Brandestini가 "Single-track Gray codes"(1996)^[76][77]에서 속도를 내고 다듬었습니다^[74][75].STGC는 두 개의 연속 단어가 정확히 하나의 위치에서 서로 다른 길이 n의 P 고유 이진 인코딩의 순환 목록이며, 목록을 P × n 행렬로 검사할 때 각 열은 첫 번째 ^[78]열의 순환 이동입니다.

이 이름은 회전식 인코더와 함께 사용하는 데서 비롯되었으며, 접촉에 의해 다수의 트랙이 감지되어 각각의 출력이 0 또는 1이 됩니다.서로 다른 접점이 정확히 같은 시간에 전환되지 않아 발생하는 잡음을 줄이기 위해 접점에 의해 출력되는 데이터가 회색 코드가 되도록 트랙을 설정하는 것이 좋습니다.높은 각도 정확도를 얻으려면 많은 접점이 필요합니다. 최소 1° 정확도를 달성하려면 회전당 최소 360개의 서로 다른 위치가 필요하므로 최소 9비트의 데이터가 필요하므로 동일한 수의 접점이 필요합니다.

모든 접점이 동일한 각도 위치에 배치된 경우 최소 1° 정확도의 표준 BRGC를 얻으려면 9개의 트랙이 필요합니다.그러나 제조업체가 접점을 다른 각도 위치(중심 축에서 같은 거리)로 이동시킨 경우, 동일한 출력을 제공하기 위해 해당 "링 패턴"을 동일한 각도로 회전시켜야 합니다.가장 의미 있는 비트(그림 1의 안쪽 링)를 충분히 회전시키면 다음 링 아웃과 정확히 일치합니다.그러면 두 링이 동일하므로 내부 링을 잘라낼 수 있으며, 해당 링의 센서가 동일한 나머지 링으로 이동합니다(그러나 해당 링의 다른 센서와 각도에서 오프셋됨).하나의 링 위에 있는 두 개의 센서는 직교 인코더를 만듭니다.이를 통해 "1° 해상도" 각도 인코더의 트랙 수가 8개로 줄어듭니다.트랙 수를 더 줄이는 것은 BRGC로는 불가능합니다.

여러 해 동안 Torsten^[79] Sillke와 다른 수학자들은 하나의 트랙에서 연속적인 위치가 2-센서, 1-트랙 직교 인코더를 제외하고는 하나의 센서에서만 차이가 나는 위치를 인코딩하는 것은 불가능하다고 믿었습니다.따라서 8개 트랙이 너무 큰 응용 프로그램의 경우, 사람들은 단일 트랙 증분 인코더(4차 인코더) 또는 2트랙 "4차 인코더 + 기준 노치" 인코더를 사용했습니다.

노먼 B.그러나 Speedding은 1994년에 특허를 등록했는데,^[74] 그것이 가능하다는 것을 보여주는 몇 가지 예들이 있습니다.하나의 트랙에서 n개의 센서로 2개의 위치를 구분할ⁿ 수는 없지만, 그에 가까운 개수를 구분할 수는 있습니다.에치온과 패터슨은 n 자체가 2의 거듭제곱일 때 n개의 센서가 최대ⁿ 2 - 2n 위치를 구별할 수 있고 프라임의 한계는 2 - 2 ^[80]위치라고ⁿ 추측합니다.저자들은 계속해서 자신들이 최적이라고 생각하는 길이 9의 504 위치 단일 트랙 코드를 생성했습니다.이 숫자는 2 = 256보다 크기 때문에, 어떤 코드에 의해서도 8개 이상의 센서가 필요하지만, BRGC는 9개의 센서로 512개의 위치를 구별할 수 있습니다.

P = 30 및 n = 5에 대한 STGC가 여기서 재현됩니다.

30개 위치에 대한 단일 트랙 회색 코드

각	코드		각	코드		각	코드		각	코드		각	코드
0°	10000		72°	01000		144°	00100		216°	00010		288°	00001
12°	10100		84°	01010		156°	00101		228°	10010		300°	01001
24°	11100		96°	01110		168°	00111		240°	10011		312°	11001
36°	11110		108°	01111		180°	10111		252°	11011		324°	11101
48°	11010		120°	01101		192°	10110		264°	01011		336°	10101
60°	11000		132°	01100		204°	00110		276°	00011		348°	10001

각 열은 첫 번째 열의 순환 이동이며, 임의의 행에서 다음 행으로 한 비트만 ^[81]변경됩니다.단일 트랙 특성(코드 체인과 같은)은 하나의 트랙만 필요하므로 이러한 휠의 제작에 유용합니다(BRGC와 비교). 따라서 비용과 크기를 줄일 수 있습니다.회색 코드 특성은 한 번에 하나의 센서만 변경되므로(De Bruijn 시퀀스라고도 불리는 체인 코드와 비교하여) 유용합니다. 따라서 두 이산 상태 간의 전환 중 불확실성은 장치가 ^[82]해결할 수 있는 각도 측정 단위의 플러스 또는 마이너스만 됩니다.

이 30도 예제가 추가된 이후로 더 높은 각도 분해능을 가진 예제에 많은 관심이 있었습니다.2008년, 게리 윌리엄스는 이전 ^[83]연구를 바탕으로^[80] 1도 해상도를 제공하는 9비트 싱글 트랙 그레이 코드를 발견했습니다.이 회색 코드는 실제 장치를 디자인하기 위해 사용되었으며, 이 장치는 Thingiverse 사이트에 게시되었습니다.이 장치는^[84] 에첸셉(플로리안 바우어)이 2022년 9월 설계했습니다.

P = 360 및 n = 9에 대한 STGC가 여기서 재현됩니다.

360 위치에 대한 단일 트랙 회색 코드

각	코드		각	코드		각	코드		각	코드		각	코드		각	코드		각	코드		각	코드		각	코드
0°	100000001		1°	110000001		2°	111000001		3°	111000011		4°	111000111		5°	111001111		6°	111011111		7°	111011011		8°	101011011
9°	101011111		10°	101011101		11°	101010101		12°	101010111		13°	101110111		14°	001110111		15°	001010111		16°	001011111		17°	001011011
18°	001011001		19°	001111001		20°	001111101		21°	000111101		22°	000110101		23°	000100101		24°	000101101		25°	000101001		26°	000111001
27°	000110001		28°	000010001		29°	000011001		30°	000001001		31°	100001001		32°	100001101		33°	100000101		34°	110000101		35°	010000101
36°	010000111		37°	010000011		38°	010000001		39°	000000001		40°	000000011		41°	100000011		42°	110000011		43°	110000111		44°	110001111
45°	110011111		46°	110111111		47°	110110111		48°	010110111		49°	010111111		50°	010111011		51°	010101011		52°	010101111		53°	011101111
54°	011101110		55°	010101110		56°	010111110		57°	010110110		58°	010110010		59°	011110010		60°	011111010		61°	001111010		62°	001101010
63°	001001010		64°	001011010		65°	001010010		66°	001110010		67°	001100010		68°	000100010		69°	000110010		70°	000010010		71°	000010011
72°	000011011		73°	000001011		74°	100001011		75°	100001010		76°	100001110		77°	100000110		78°	100000010		79°	000000010		80°	000000110
81°	000000111		82°	100000111		83°	100001111		84°	100011111		85°	100111111		86°	101111111		87°	101101111		88°	101101110		89°	101111110
90°	101110110		91°	101010110		92°	101011110		93°	111011110		94°	111011100		95°	101011100		96°	101111100		97°	101101100		98°	101100100
99°	111100100		100°	111110100		101°	011110100		102°	011010100		103°	010010100		104°	010110100		105°	010100100		106°	011100100		107°	011000100
99°	111100100		100°	111110100		101°	011110100		102°	011010100		103°	010010100		104°	010110100		105°	010100100		106°	011100100		107°	011000100
108°	001000100		109°	001100100		110°	000100100		111°	000100110		112°	000110110		113°	000010110		114°	000010111		115°	000010101		116°	000011101
117°	000001101		118°	000000101		119°	000000100		120°	000001100		121°	000001110		122°	000001111		123°	000011111		124°	000111111		125°	001111111
126°	011111111		127°	011011111		128°	011011101		129°	011111101		130°	011101101		131°	010101101		132°	010111101		133°	110111101		134°	110111001
135°	010111001		136°	011111001		137°	011011001		138°	011001001		139°	111001001		140°	111101001		141°	111101000		142°	110101000		143°	100101000
144°	101101000		145°	101001000		146°	111001000		147°	110001000		148°	010001000		149°	011001000		150°	001001000		151°	001001100		152°	001101100
153°	000101100		154°	000101110		155°	000101010		156°	000111010		157°	000011010		158°	000001010		159°	000001000		160°	000011000		161°	000011100
162°	000011110		163°	000111110		164°	001111110		165°	011111110		166°	111111110		167°	110111110		168°	110111010		169°	111111010		170°	111011010
171°	101011010		172°	101111010		173°	101111011		174°	101110011		175°	101110010		176°	111110010		177°	110110010		178°	110010010		179°	110010011
180°	111010011		181°	111010001		182°	101010001		183°	001010001		184°	011010001		185°	010010001		186°	110010001		187°	100010001		188°	100010000
189°	110010000		190°	010010000		191°	010011000		192°	011011000		193°	001011000		194°	001011100		195°	001010100		196°	001110100		197°	000110100
198°	000010100		199°	000010000		200°	000110000		201°	000111000		202°	000111100		203°	001111100		204°	011111100		205°	111111100		206°	111111101
207°	101111101		208°	101110101		209°	111110101		210°	110110101		211°	010110101		212°	011110101		213°	011110111		214°	011100111		215°	011100101
216°	111100101		217°	101100101		218°	100100101		219°	100100111		220°	110100111		221°	110100011		222°	010100011		223°	010100010		224°	110100010
225°	100100010		226°	100100011		227°	000100011		228°	000100001		229°	100100001		230°	100100000		231°	100110000		232°	110110000		233°	010110000
234°	010111000		235°	010101000		236°	011101000		237°	001101000		238°	000101000		239°	000100000		240°	001100000		241°	001110000		242°	001111000
243°	011111000		244°	111111000		245°	111111001		246°	111111011		247°	011111011		248°	011101011		249°	111101011		250°	101101011		251°	101101010
252°	111101010		253°	111101110		254°	111001110		255°	111001010		256°	111001011		257°	011001011		258°	001001011		259°	001001111		260°	101001111
261°	101000111		262°	101000110		263°	101000100		264°	101000101		265°	001000101		266°	001000111		267°	001000110		268°	001000010		269°	001000011
270°	001000001		271°	001100001		272°	101100001		273°	101100000		274°	101110000		275°	101010000		276°	111010000		277°	011010000		278°	001010000
279°	001000000		280°	011000000		281°	011100000		282°	011110000		283°	111110000		284°	111110001		285°	111110011		286°	111110111		287°	111110110
288°	111010110		289°	111010111		290°	011010111		291°	011010101		292°	111010101		293°	111011101		294°	110011101		295°	110010101		296°	110010111
297°	110010110		298°	010010110		299°	010011110		300°	010011111		301°	010001111		302°	010001101		303°	010001001		304°	010001011		305°	010001010
306°	010001110		307°	010001100		308°	010000100		309°	010000110		310°	010000010		311°	011000010		312°	011000011		313°	011000001		314°	011100001
315°	010100001		316°	110100001		317°	110100000		318°	010100000		319°	010000000		320°	110000000		321°	111000000		322°	111100000		323°	111100001
324°	111100011		325°	111100111		326°	111101111		327°	111101101		328°	110101101		329°	110101111		330°	110101110		331°	110101010		332°	110101011
333°	110111011		334°	100111011		335°	100101011		336°	100101111		337°	100101101		338°	100101100		339°	100111100		340°	100111110		341°	100011110
342°	100011010		343°	100010010		344°	100010110		345°	100010100		346°	100011100		347°	100011000		348°	100001000		349°	100001100		350°	100000100
351°	110000100		352°	110000110		353°	110000010		354°	111000010		355°	101000010		356°	101000011		357°	101000001		358°	101000000		359°	100000000

센서 9개가 40°로 분리된 단일 트랙 그레이 코드에 대한 20개 트랙의 시작 및 종료 각도

시작 각도	종료 각도	길이
3	4	2
23	28	6
31	37	7
44	48	5
56	60	5
64	71	8
74	76	3
88	91	4
94	96	3
99	104	6
110	115	6
131	134	4
138	154	23
173	181	9
186	187	2
220	238	19
242	246	5
273	279	7
286	289	4
307	360	54

2차원 그레이 코드

2차원 회색 코드는 통신에 사용되어 별자리의 QAM(quadrature amplitude modulation) 인접 지점에서 비트 오류의 수를 최소화합니다.일반적인 인코딩에서 수평 및 수직 인접 성상도 점은 단일 비트로 다르고 대각선 인접점은 ^[85]2비트로 다릅니다.

2차원 회색 코드는 또한 위치 식별 체계에서 사용되는데, 여기서 코드는 지구 표면의 메르카토르 투영과 같은 영역 지도에 적용되고 만하임 메트릭과 같은 적절한 순환 2차원 거리 함수는 두 인코딩된 위치 사이의 거리를 계산하는 데 사용됩니다.따라서 해밍 거리의 특성과 메르카토르 투영의 ^[86]순환적 연속을 결합합니다.

초과-회색

해당 값에서 특정 코드 값의 하위 섹션(예: 4비트 그레이 코드의 마지막 3비트)을 추출하면 결과 코드는 "과잉 그레이 코드"가 됩니다.이 코드는 원래 값이 더 증가할 경우 추출된 비트에서 역으로 카운트하는 속성을 보여줍니다.그 이유는 그레이 인코딩된 값이 "가장 높은" 값을 초과하여 증가할 때 고전적인 이진 인코딩에서 알려진 오버플로 동작을 보여주지 않기 때문입니다.

예:가장 높은 3비트 회색 코드인 7은 (0)100으로 인코딩됩니다.1을 더하면 숫자 8이 되며 회색으로 1100으로 인코딩됩니다.원래 4비트 코드를 더 늘리면 마지막 3비트는 오버플로우되지 않고 거꾸로 계산됩니다.

따라서 그레이 인코딩된 여러 값을 직렬 방식으로 출력하는 센서를 사용할 경우 센서가 하나의 단일 그레이 코드로 인코딩된 여러 값을 생성하는지 아니면 별도의 그레이 코드로 생성하는지에 주의해야 합니다. 그렇지 않으면 "오버플로우"가 예상될 때 값이 거꾸로 카운트되는 것처럼 보일 수 있기 때문입니다.

회색 등각법

사영 매핑 {0 ↔ 00, 1 ↔ 01, 2 ↔ 11,3 ↔ 10 }은(는) 해밍 거리가 주는 메트릭과 Lee 거리가 주는 메트릭이 있는 $유한장$ ${\displaystyle {}_{}}$ ${\$$displaystyle \mathbb {Z}$ _${2$$}^{2$$}}($일반적인 모듈러 산술)에 대한 메트릭 사이의 등각을 설정합니다$.$매핑은 해밍 $공간{\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 2 ${\displaystyle m_{}^{}}${\$displaystyle \mathbb {Z$$}$ _${$$2}^{$${\displaystyle {}_{}^{}}$$}$$$및 $Z4$ m ${\displaystyle \mathbb$ {$Z} _{$4}^{m$\}\}$의 등각으로 적합하게 확장됩니다. 이것의 중요성은 링-l의 ${\displaystyle {\mathrm{}}_{}^{}}$ {\$displaystyle \mathbb {Z}$ _${2}}$에서 그레이-맵 이미지로서 다양한 "좋은" 코드와 선형 코드 사이의 대응을 설정하는 데 있습니다$.$${\displaystyle {\mathrm{}}_{}}${\$displaystyle \mathbb {Z}$ _${4$^[87][88]의 near 코드입니다.

관련코드

이 섹션에는 인용 횟수가 지나치게 많을 수 있습니다.자세한 내용은 다음과 같습니다.참조가 너무 많으면 텍스트를 읽기 어렵습니다. 불필요하거나 평판이 좋지 않은 출처에 대한 참조를 제거하거나 가능한 경우 인용을 병합하거나 필요한 경우 내용을 삭제하도록 플래그를 지정하는 것을 고려하십시오. (2021년 3월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)