🔢 mathematics

Optimal Non-Binary Single-Track Gray Code

이 논문은 소수 $p=3$ 및 $p=5$ 에 대하여 유한체 $\mathbb{F}_p$ 상의 $p^{p^t}$ 개의 코드워드를 갖는 길이 $p^t$ 의 최적 비이진 단일 트랙 그레이 코드(single-track Gray code)의 존재를 증명하는 동시에, 더 큰 소수 및 소수가 아닌 알파벳 크기에 대한 존재 조건을 제공한다.

원저자: Tuvi Etzion

게시일 2026-07-16

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Tuvi Etzion

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 자전거 바퀴나 거대한 산업용 팬처럼 회전하는 바퀴를 추적하려고 한다고 상상해 보십시오. 당신은 어느 순간에도 바퀴가 정확히 어디에 있는지 알고 싶습니다. 이를 위해 엔지니어들은 바퀴에 줄무늬를 그리고 센서로 이를 읽어냅니다. 만약 표준 숫자 체계를 사용한다면, 바퀴가 두 숫자 사이에 있을 때 센서들이 혼란을 겪을 수 있습니다. 왜냐하면 여러 개의 줄무늬가 동시에 변하면서 컴퓨터가 바퀴의 위치를 잘못 파악하는 '글리치(glitch)' 현상이 발생할 수 있기 때문입니다.

이를 해결하기 위해 수학자들은 **그레이 코드(Gray code)**라고 불리는 특별한 종류의 암호를 발명했습니다. 이것은 한 번에 단 하나의 요소만 변화시켜야 다음 숫자로 넘어갈 수 있는 일종의 비밀 언어와 같습니다. 마치 사다리를 오를 때 한 번에 두 칸을 뛰는 것이 아니라 반드시 한 칸씩만 올라가야 하는 것과 같습니다. 이는 센서가 약간 흔들리더라도, 아주 작은 무해한 오류만을 보게 될 뿐 결코 거대한 혼란을 일으키지 않도록 보장합니다.

이제, 당신은 매우 정밀한 바퀴를 만들고 싶지만, 모든 센서를 위한 별도의 트랙을 그릴 공간이 충분하지 않다고 상상해 보십시오. 당신은 이 모든 정보를 더 작은 패키지에 압축할 방법이 필요합니다. 여기서 **싱글 트랙 그레이 코드(Single-Track Gray Codes)**가 등장합니다. 여러 개의 트랙을 갖는 대신, 하나의 트랙을 복사하고 이동시키는 방식을 사용합니다. 이것은 마치 코드라는 긴 리본 하나를 바퀴에 감아놓은 것과 같으며, 센서는 서로 다른 시작점에서 이를 읽어냅니다. 마법 같은 점은, 이 단 하나의 리본이 서로 다른 각도에서 읽히더라도 여전히 "한 번에 하나만 변화시킨다"는 규칙을 따른다는 것입니다.

오랫동안 과학자들은 단순한 "예/아니오"(이진법) 시스템을 위한 이러한 코드를 만드는 법은 알고 있었지만, 모든 가능한 크기의 바퀴에 대해 작동하게 만드는 데에는 한계에 부딪혔습니다. 특히 바퀴가 어떤 위치도 놓치지 않고 모든 위치를 보여주어야 할 때 말입니다. 또한, 0, 1, 2, 3, 4와 같은 숫자를 사용하는 더 복잡한 시스템(비이진법 시스템)에서 이를 작동시키는 데에도 어려움을 겪었습니다.

이 논문은 그 벽을 허무는 것에 관한 것입니다. T. Etzion이 이끄는 저자들은 3이나 5와 같은 소수를 알파벳 크기로 사용하는 시스템을 위한 이 특별한 "싱글 트랙" 코드를 구축하는 방법을 알아냈습니다. 그들은 단순히 추측한 것이 아니라, 이 코드가 특정 크기(p가 3 또는 5이고 t가 2 이상의 임의의 정수인 $p^t$ 길이의 경우)의 바퀴에 대해 확실히 존재함을 증명하는 수학적 기계, 즉 재귀적 레시피를 만들어냈습니다.

다음은 몇 가지 유쾌한 비유를 사용하여 그들이 이 일을 해낸 과정에 대한 이야기입니다.

구성 요소: "자기 쌍대(Self-Dual)" 리본

코드를 만들기 위해 저자들은 특별한 종류의 재료가 필요했습니다. 숫자의 패턴이 그려진 긴 종이 띠를 상상해 보십시오. 이제, 모든 숫자에 1을 더하는(즉, 0은 1이 되고, 1은 2가 되며, 2는 다시 0으로 돌아가는) "마법의 거울"을 상상해 보십시오.

보통 원래의 띠와 거울에 비친 띠를 비교하면 완전히 다르게 보입니다. 하지만 저자들이 필요로 했던 것은, 거울 이미지를 적절한 양만큼 이동시켰을 때 원래의 띠와 정확히 일치하는 특별한 종류의 띠였습니다. 그들은 이를 **자기 쌍대 수열(Self-Dual Sequences, SDS)**이라고 부릅니다. 이는 특정한 종류의 마법 변환 하에서 완벽하게 대칭을 이루는 리본과 같습니다.

이 논문은 3 또는 5개의 기호를 사용하는 시스템을 위해 이러한 리본을 무한히 생성할 수 있음을 증证明합니다. 그들은 단계별 레시피를 통해 이를 수행했습니다. 작은 리본을 가져와서, 약간의 "풍미"(수학적 용어로 $Z$ 와 $Y$ )를 더하면, 짠—더 큰 완벽한 리본이 탄생합니다. 이는 마치 프랙탈과 같습니다. 작은 패턴을 가져와 규칙을 적용하면, 여전히 특수한 대칭성을 유지하면서 더 큰 패턴으로 성장하게 됩니다.

조립 라인: 리본을 엮는 작업

리본을 갖는 것은 전투의 절반일 뿐입니다. 당신은 이 리본들을 특정한 순서로 배열해야 합니다. 만약 그냥 무더기로 던져 놓는다면 센서들이 혼란을 겪을 것입니다.

저자들은 한 리본에서 다음 리본으로 넘어갈 때, 코드의 단 한 위치만 변하도록 이 리본들을 배치해야 했습니다. 이것이 가장 어려운 부분입니다. 마치 카드를 교체할 때마다 단 하나의 카드 값만 바꿀 수 있고, 결국 시작점으로 돌아오되 절대 중간에 갇히지 않도록 카드 덱을 배열하는 것과 같습니다.

3(삼진법 시스템)과 5(오진법 시스템)의 경우, 저자들은 이를 수행할 영리한 방법을 찾아냈습니다. 그들은 영리한 "병합(merging)" 기술을 사용했습니다. 리в본들의 여러 그룹이 있다고 상상해 보십시오. 어떤 그룹들은 매우 유사하며, 단 한 군데의 아주 작은 지점에서만 차이가 납니다. 저자들은 두 그룹을 가져와서 그들이 서로 다른 정확한 지점을 찾아내고, "한 번에 하나만 변화시킨다"는 규칙을 유지하면서 더 큰 그룹으로 엮어내는 방법을 보여주었습니다.

그들은 크기가 3과 5의 거듭제곱(예: $3^2, 3^3, 5^2$ 등)인 경우, 항상 이 리본들을 엮어 전주기(full-period) 코드를 형성할 수 있음을 증명했습니다. 이는 이 코드가 단 하나의 위치도 놓치지 않고 모든 가능한 위치( $m^{m^t}$ 개의 코드워드)를 나타낼 수 있음을 의미합니다.

그들이 하지 않은 것 (그리고 배제한 것)

이 논문이 말하고자 하는 바가 아닌 것을 아는 것도 중요합니다.

모든 숫자를 위한 마법 지팡이가 아닙니다: 저자들은 이진 시스템(0과 1만 사용하는 경우)의 경우, $n=2$ 인 경우를 제외하고는 어떤 크기에 대해서도 전주기 싱글 트랙 코드를 만들 수 없다고 명시적으로 밝히고 있습니다. 그들은 더 큰 이진 바퀴에 대해 이것이 불가능함을 증명했습니다.
아직 모든 소수를 위한 것은 아닙니다: 그들은 3과 5를 위한 것은 증명했지만, 7, 11, 13과 같은 더 큰 소수의 경우 아직 "씨앗"이 되는 리본을 찾지 못했다고 인정했습니다. 그들은 레시 recipe가 작동할 것이라고 추측하지만, 먼저 시작 패턴을 찾아야 합니다.
비소수 숫자를 위한 것은 아닙니다 (대부분): 그들은 크기 4에 대한 구체적인 예시를 보여주었지만, 그들의 주요하고 엄격한 증명은 소수를 대상으로 합니다.

결론

이 논문은 이러한 코드들이 존재할 수도 있다고 제안하는 데 그치지 않고, 3과 5에 기반한 무한한 크기의 가족에 대해 그 존재를 증명합니다. 그들은 수학적 "설계도"(재귀적 구성)와 "스타터 키트"(p=3 및 p=5를 위한 씨앗)를 제공했습니다.

호기심 많은 십 대나 고속 센서를 설계하는 엔지니어에게 이것은 매우 중요한 일입니다. 이는 완전히 새로운 클래스의 기계들을 위해, 우리가 더 작고, 더 정밀하며, 오류에 덜 취약한 인코더를 만들 수 있음을 의미합니다. 저자들은 문을 열어 보여주었습니다. 적절한 수학적 도구가 있다면, 이전에는 불가능하다고 생각되었던 방식으로 정보를 조직할 수 있다는 것을 말입니다. 그들은 단순히 건초더미에서 바늘을 찾은 것이 아니라, 그 건초더미가 3과 5로 만들어져 있는 한, 무한한 수의 건초더미에서 바늘을 찾을 수 있는 기계를 만든 것입니다.

기술 요약: 최적의 비이진 단일 트랙 그레이 코드(Single-Track Gray Code)

문제 정의
본 논문은 비이진 알파벳에 대한 단일 트랙 그레이 코드(STGC)의 구축 문제를 다룬다. 길이 $n$ 과 주기 $P$ 를 갖는 STGC는 $P$ 개의 서로 다른 단어들로 이루어진 순환 리스트이며, 인접한 단어들은 정확히 하나의 위치에서만 달라야 하고, 코드 배열의 $n$ 개 트랙(열)은 단일 트랙의 순환 이동(cyclic shift)이어야 한다. 이진 STGC의 경우, 완전 주기( $P=2^n$ )를 갖는 코드는 $n=2$ 인 경우에만 존재하며, $n > 2$ 일 때 최대 주기는 $2^n - 2^n$ 으로 제한된다는 것이 알려져 있다. 본 논문은 더 큰 알파벳을 사용하는 경우의 STGC 존재 여부를 조사한다. 구체적으로, $p$ 가 소수일 때 $n = p^t$ 및 $P = p^{p^t}$ 인 유한체 $\mathbb{F}_p$ 상의 완전 주기 코드를 나타내는 STGC의 구축을 목표로 한다.

방법론
저자들은 **비이진 자기 쌍대 수열(Non-Binary Self-Dual Sequences, SDSs)**에 기반한 재귀적 구축 전략을 사용한다. 방법론은 다음 단계로 진행된다:

이진 구축 방식의 일반화: 본 논문은 기존의 이진 STGC 구축 정리(자기 쌍대 수열을 포함하는 이전 연구의 정리 2)를 비이진 알파벳 $\mathbb{Z}_m$ 으로 확장하여 적용한다. 이 적응 과정(정리 4)은 $m^n$ 주기를 갖는 $r$ 개의 서로 다른 쌍생 불변(pairwise inequivalent) SDS들의 순서가 필요하며, 이때 연속된 수열들은 정확히 $m$ 개의 좌표에서 달라야 하고, 이동 연산자 $E$ 와 차이 집합(difference set)에 대한 특정 조건을 만족해야 한다.
SDSs의 재귀적 생성: SDS를 $\mathbb{Z}_p$ $Z_{p}$ ( $p$ $p$ 는 홀수 소수) 상에서 생성하기 위한 핵심 구성 요소는 재귀적 방법이다.
- 기초 사례(Base Case): 주어진 주기 $p^t$ 에 대해, SDS는 $[X, X+1, \dots, X+(p-1)]$ 의 형태를 갖는다.
- 재귀 단계(Recursive Step): 주기 $p^t$ 에서 주기 $p^{t+1}$ 인 SDS를 구축하기 위해, 저자들은 베이스 단어 $Z$ (0에서 시작)와 보조 단어 $Y_1, \dots, Y_{p-2}$ 를 사용하여 새로운 단어 $V$ 를 정의한다. 새로운 SDS는 $[V, V+1, \dots, V+(p-1)]$ 로 형성된다.
- 조합론적 계수(Combinatorial Counting): 본 논문은 $Z$ 와 $Y$ 벡터에 대한 선택지를 열거함으로써, 이 구축법이 필요한 정확한 수의 서로 다른 SDS( $p^{p^t - t - 1}$ )를 생성함을 증명한다.
배열 및 병합(Arrangement and Merging): 생성된 SDS들을 STGC 인접 조건(최종 코드에서 정확히 하나의 좌표에서 차이가 남)을 만족하도록 배열하는 것이 핵심적인 과제이다.
- 저자들은 연속된 SDS들이 서로 다른 위치를 나타내는 성질 (P1)과 (P2)를 정의한다.
- $p=3$ 인 경우에 대해 상세히 설명된 복잡한 병합 과정이 기술된다. 이는 SDS의 구성 요소들을 결합하는 과정을 포함한다. 여기에는 가중치(weight)에 따라 단어들을 분할하고, 결과적인 수열이 요구되는 차이 성질을 유지하도록 리스트 $A(Z, Y)$ 를 병합하는 과정이 포함된다.
- 병합 로직은 차이 위치의 집합 $D_{p^{t+1}}$ 이 모든 필요한 인덱스 $\{0, 1, \dots, p^t - 1\}$ 를 커버하도록 보장한다.

주요 기여 및 결과

존재성 증명: 본 논문은 특정 소수 $p=3$ 및 $p=5$ 에 대하여, 모든 $t \ge 2$ 에 대해 길이 $n = p^t$ 와 주기 $P = p^{p^t}$ 를 갖는 완전 주기 비이진 STGC의 존재성을 증명한다.
재귀적 프레임워크: 임의의 홀수 소수 $p$ 에 대한 일반적인 재귀적 구축 프레임워크를 제공한다. 이 구축은 "적절한 시드(appropriate seed)"—즉, 초기 배열 성질을 만족하는 주기 $p^2$ (또는 $p=3$ 의 경우 주기 27)의 모든 SDS의 특정 배열—의 존재를 전제로 한다.
특정 시드: 저자들은 $p=3$ (주기 27인 729개의 SDS)과 $p=5$ (부록 A와 B에 상세 기술됨)에 필요한 시드를 제공함으로써 이 두 경우에 대한 구축을 완료하였다.
비소수 알파벳: 본 논문은 주요 초점이 소수 체계에 맞춰져 있으나, 비소수 알파벳 크기에 대해서도 그러한 코드가 존재할 수 있다는 징후(예제 3에서 $m=4$ 의 경우 입증됨)를 언급한다.

의의 및 주장
본 논문은 최초이자 유일하게 알려진 두 개의 무한 가족(infinite families) 완전 주기 단일 트랙 그레이 코드(STGC)를 제시한다고 주장한다(for $p=3$ and $p=5$ ). 그 의의는 이진 코드에서 $n > 2$ 일 때 완전 주기 STGC가 존재하지 않는 한계를 극복했다는 점에 있다. 비이진 알파벳을 활용함으로써, 저자들은 길이 $n$ 의 모든 가능한 단어를 포함하는 코드( $P = p^{p^t}$ )를 달로 성취하였으며, 이는 단일 물리적 트랙을 통해 높은 해상도가 요구되는 양자화 및 코딩 응용 분야에 최적이다.

저자들은 $p > 5$ 인 소수에 대해서는 이론적으로는 유효하지만, 적절한 시드(주기 $p^2$ 인 SDS의 배열)의 발견이 필요하다고 겸허히 밝히고 있다. 이들은 더 큰 소수를 위한 시드 탐색과 "보완 순환 레지스터(complemented cycling register)"의 비이진 알파벳으로의 일반화가 향후 연구의 주요 방향임을 명시하였다. 본 논문은 모든 소수 또는 모든 비소수 크기에 대한 문제를 해결했다고 주장하는 것이 아니라, $p=3$ 과 $p=5$ 에 대한 존재성을 확립하고 다른 경우를 위한 경로를 제시하는 것을 목적으로 한다.

구성 요소: "자기 쌍대(Self-Dual)" 리본

조립 라인: 리본을 엮는 작업

그들이 하지 않은 것 (그리고 배제한 것)

결론

유사한 논문