Covering Sequences and Covering-Sequences Codes

기술 요약: 커버링 시퀀스(Covering Sequences) 및 커버링-시퀀스 코드(Covering-Sequences Codes)

문제 정의
본 논문은 $(n, R)_q$-커버링 시퀀스(CS)와 $(n, m, R)_q$-커버링-시퀀스 코드(CSC)의 구축을 다룬다. $(n, R)_q$-커버링 시퀀스는 알파벳 $\Sigma_q$ 상의 길이 $\ell$인 순환 시퀀스로서, 그 연속적인 $n$-튜플들이 $(n, R)_q$-커버링 코드(모든 단어가 해밍 거리 $R$ 내에 있는 코드 집합)를 형성하는 것을 의미한다. 주요 목표는 이러한 시퀀스의 길이를 최소화하는 것이다.

또한 본 논문은 $(n, m, R)_q$-CSC를 소개하는데, 이는 집합적인 연속 $n$-튜플들이 $(n, R)_q$-커버링 코드를 형성하는 길이 $m$인 $M$개의 순환 시퀀스들의 집합으로 정의된다. 본 논문은 이러한 코드들이 짧은 커버링 시퀀스를 구축하기 위한 근본적인 빌딩 블록 역할을 한다고 상정한다. 이전 연구(특히 [3])가 작은 반경을 가진 이진 시퀀스($q=2$)에 초점을 맞추었다면, 본 연구는 이러한 개념을 비이진 알파벳($q > 2$)과 더 큰 반경으로 일반화하는 동시에, $m > n$인 CSC의 구조적 역할에 역점을 둔다.

방법론
핵심 방법론은 "Construction MC" (Merging Cycles, 사이클 병합)라고 불리는 구축법에 의존한다. 이 과정은 $(n, m, R)_q$-CSC로부터 추출된 코드워드 집합을 하나의 순환 커버링 시퀀스로 변환한다:

1. 확장(Extension): 각 길이 $m$의 코드워드 $c$는 끝에 처음 $n-1$개의 심볼을 추가함으로써 길이 $m+n-1$로 확장된다.
2. 병합(Merging): 확장된 코드워드들은 한 코드워드의 접미지(suffix)가 다음 코드워드의 접두사(prefix)와 겹치도록 정렬된다.
3. 연결(Concatenation): 겹치는 부분을 제거하고 남은 세그먼트들을 연결하여 하나의 순환 시퀀스 $S$를 형성한다.
   본 논문은 만약 원래의 코드워드 집합이 $(n, m, R)_q$-CSC를 형성한다면, 결과물인 시퀀스 $S$는 $(n, R)_q$-CS가 됨을 증명한다.

본 논문은 다음과 같은 특정 대수적 구조를 사용하여 이 구축법을 적용한다:

• 이진 케이스 ($q=2$): 길이 $n=2^r-1$ 및 반경 $R=1$에 대해 순환 해밍 코드 $H_2(r)$를 활용한다. 또한, 보수(completion)에 대해 불변인 시퀀스( $[X, \bar{X}]$ 로 표현됨)인 "자기 쌍대 시퀀스(self-dual sequences)" 집합을 사용하여 $n=2^r$에 대해 거의 완벽한 커버링 코드를 형성한다.
• 비이진 케이스 ($q > 2$): 유한체 $\mathbb{F}_q$로 접근 방식을 일반화한다. 표준 해밍 코드 $H_q(r)$는 항상 순환적이지 않으므로, 본 논문은 **콘스타이클릭 코드(constacyclic codes)**를 활용한다. 본 논문은 $H_q(r)$가 콘스타이클릭 코드로 표현될 수 있음을 보여주며, 이를 통해 Construction MC의 적용을 가능하게 한다.
• 인터리빙(Interleaving): 더 큰 반경($R > 1$)을 다루기 위해, 기존 순환 코드의 패리티 검사 행렬을 인터리빙할 것을 제안한다. 구체적으로, $R$개의 패리티 검사 행렬 $H$를 인터리빙하면 새로운 코드가 생성되며, 이 코드는 반경 $R \cdot r_{old}$를 가지며 길이는 그에 따라 스케일링된다. 이는 해밍 코드를 적용하여 반경 2 이상의 시퀀스를 구축하는 데 사용된다.

주요 기여 및 결과

1. 비이진 알파벳으로의 일반화: 본 논문은 커버링 시퀀스 이론을 이진에서 임의의 소수 거듭제곱 알파벳($q > 2$)으로 확장한다. 해밍 코드 $H_q(r)$가 병합 사이클 구축을 용이하게 하기 위해 콘스타이클릭 코드로 취급될 수 있음을 입증한다.
2. 최적성 계수(Optimality Factors):
   • $n=2^r$ 및 $R=1$인 이진 시퀀스의 경우, 자기 쌍대 시퀀스를 사용하면 최적 크기의 1.25 배 이내의 커버링 시퀀스를 얻을 수 있다.
   • $n = \frac{q^r-1}{q-1}$ 및 $R=1$인 $\mathbb{F}_q$ 상의 비이진 시퀀스의 경우, 구축된 시퀀스는 이론적 하한(구체로 구형 커버링 경계, sphere-covering bound)의 $\frac{q}{q-1}$ 배 이내에 있다.
   • 반경 $R=2$의 경우, 해밍 코드의 패리티 검사 행렬을 인터리빙하면 하한의 작은 상수 계수(예: 특정 파라미터에 따라 2 또는 4) 내의 결과를 얻는다.
3. 퇴화된 시퀀스(Degenerated Sequences)의 구조: 본 논문은 "퇴화된" 시퀀스(주기가 길이보다 작은 시퀀스)를 분석한다. 이진 해밍 코드의 경우, 길이가 $2^r-1$인 모든 퇴화된 단어가 코드워드임을 증명한다. 그러나 이러한 성질이 비이진 콘스타이클릭 표현으로 직관적으로 일반화되지는 않는다는 점을 언급하며, 비이진 케이스에서의 정확한 퇴화 궤도(degenerated orbits)의 개수를 남겨진 과제로 남겨두었다.
4. 새로운 코드 군(New Code Families): 특히 $m > n$인 경우(예: 자기 쌍대 시퀀스 또는 콘스타이클릭 표현 사용)의 특정 $(n, m, R)_q$-CSC 군을 구축하며, 이들이 커버링 시퀀스를 위한 효율적인 빌딩 블록임을 주장한다.

의의 및 주장
본 논문은 커버링-시퀀스 코드(CSC)가 "순환 커버링 코드와 커버링 시퀀스 사이의 연결 고리"이며, 특히 전체 코드워드 길이가 최적에 가까운 경우에 향후 연구의 주된 초점이 되어야 한다고 주장한다.

본 연구의 의의는 다음과 같다:

• $(n, R)_q$-CS 및 $(n, m, R)_q$-CSC에 대한 최초의 체계적인 기술을 제공한다.
• 대수적 코딩 이론(특히 해밍, 네가사이클릭(negacyclic), 콘스타이클릭 코드)이 비이진 알파벳에 대해서도 최적에 점근적으로 가까운 커버링 시퀀스를 구축하는 데 효과적으로 활용될 수 있음을 입증한다.
• 상대적으로 짧은 시퀀스 길이를 유지하면서 패리티 검사 행렬 인터리빙을 통해 커버링 반경을 높이는 방법을 도입한다.

저자들은 구축된 시퀀스들이 최적성에 대해 작은 상수 계수 내에 있지만, 특히 더 큰 반경에 대해서는 추가적인 개선이 가능하다고 겸허히 밝힌다. 이들은 정확한 순환 시퀀스(궤도)의 수를 계산하는 공식의 단순화와 비이진 콘스타이클릭 표현에서의 궤도 주기에 대한 더 완전한 분석을 포함한 몇 가지 미해결 과제를 제시하였다.