Construction of cyclic codes with large minimum distance from power functions over odd characteristic finite fields

기술 요약: 홀수 표수 유한체 상의 거듭제곱 함수를 이용한 큰 최소 거리를 갖는 순환 부호의 구성

문제 정의
부호의 차원이 코드 길이의 절반을 초과하고($k > v/2$), 최소 거리가 코드 길이의 제곱근보다 큰($d > \sqrt{v}$) 순환 부호는 통신 시스템, 양자 내성 암호, 레이더와 같이 높은 전송 효율과 강력한 오류 정정 능력이 요구되는 응용 분야에서 매우 바람직하다. 이진 필드(표수 2)에 대해서는 상당한 진전이 이루어졌으나, 홀수 표수의 유한체 상에서 알려진 차분 균일성(differential uniformity)을 갖는 거듭제곱 함수를 사용하여 비이진 순환 부호를 구성하는 것에 대해서는 상대적으로 관심이 적었다. 본 논문은 유리한 파라미터, 구체적으로 차원 $k > (q^m - 1)/2$ 및 최소 거리 $d > \sqrt{q^m - 1}$을 목표로 하는 무한 가족 $q$-진 순환 부호(여기서 $q$는 홀수 소수의 거듭제곱)를 구성하는 공백을 다룬다.

방법론
저자들은 순환 부호를 구성하기 위해 트레이스 시퀀스(trace sequence) 접근법을 사용한다. 방법론은 다음 단계들을 포함한다:

1. 시퀀스 정의: 주어진 유한체 $\mathbb{F}_{q^m}$와 원시 원 $\alpha$에 대하여, 트레이스 함수를 통해 시퀀스 $s_\infty = (s_t)_{t \ge 0}$를 다음과 같이 정의한다: $s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$, 여기서 $F(x)$는 $\mathbb{F}_{q^m}$ 상의 선택된 거듭제곱 함수이다.
2. 생성 다항식 결정: 순환 부호 $C_F$는 시퀀스 $s_\infty$의 최소 다항식 $M_s(x)$에 의해 생성된다. 부호의 차원은 시퀀스의 선형 스팬($L_s$)에 의해 결정되며, 이는 시퀀스의 트레이스 전개에서 0이 아닌 계수의 수와 일치한다.
3. 거듭제곱 함수 선택: 본 논문은 홀수 $q$에 대해 알려진 차분 균일성을 갖는 모노미얼 $F(x) = x^d$를 선택한다. 선택 기준은 $m$의 기우성(parity)과 지수 $d$의 특정 구조에 따라 달라진다.
4. 대수적 분석:
   • 선형 스팬: 저자들은 $q$-진 전개, 루카스 정리(Lucas' Theorem), 그리고 사이클로토믹 코셋(cyclotomic cosets)의 성질을 활용하여 트레이스 함수를 전개하고 0이 아닌 항들을 식별한다. 이를 통해 선형 스팬 $L_s$를 정확히 계산하고 생성 다항식 $M_s(x)$를 구성할 수 있다.
   • 최소 거리 하한: BCH 바운드와 하트만-첸(Hartmann-Tzeng) 바운드를 사용하여 최소 거리 $d$의 하한을 설정한다. 이는 정의 집합(생성 다항식의 근들) 내의 연속된 정수 또는 특정 집합을 식별하는 과정을 포함한다.
   • 정확한 거리: 특정 사례의 경우, 저자들은 특정 가중치를 갖는 명시적인 코드워드들을 구성하여 정확한 최소 거리를 결정하며, 이는 종종 구성된 코드를 알려진 프리미티브 BCH 코드와 연관시킨다.

주요 기여 및 결과
본 논문은 차원이 $v/2$를 초과하는 $v = q^m - 1$ 길이의 여러 무한 가족 $q$-진 순환 부호를 제시한다. 사용된 거듭제곱 함수에 따른 구체적인 구성과 결과는 다음과 같이 분류된다:

1. $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$이 홀수일 때)로부터의 3진 부호:

   • $\mathbb{F}_{3^m}$ 상에서 구성됨.
   • 선형 스팬은 $3m + N_3(m)$이며, 이에 따라 차원은 $3^m - 1 - 3m - N_3(m)$이 된다.
   • 최소 거리 $d$는 $3 \le d \le 8$을 만족한다.
   • 예시: $m=5$인 경우, 거의 최적인 $[242, 226, 5]$ 코드가 얻어진다.

2. $x^{p^{m/2} + 2}$ ($m$이 짝수, $p$가 홀수일 때)로부터의 $p$-진 부호:

   • $\mathbb{F}_{p^m}$ 상에서 구성됨.
   • 선형 스팬은 $p$와 $m$에 의존한다 (예: $p=3$일 때 $N_p(m) + 5m/2$).
   • 최소 거리 하한이 설정된다: $d \ge 3$ ($p=3$인 경우), $d \ge 5$ ($p \ge 5, p \nmid m$인 경우), $d \ge 4$ ($p \ge 5, p \mid m$인 경우).
   • 특정 사례에 대한 정확한 거리가 결정된다 (예: $p=5, p \nmid m$일 때 $d=5$).

3. $x^{(q^{(m+1)/2} - 1)/(q-1)}$ ($m$이 홀수일 때)로부터의 코드:

   • 이 구성은 지수가 기하급수의 합인 특정 사례를 다룬다.
   • 저자들은 $N_p(k)$ 항들의 합을 포함하는 선형 스팬의 일반식을 도출한다.
   • 의의: 이 구성은 $m$이 홀수일 때 $t = (m+1)/2$인 순환 부호의 차원과 생성 다항식에 관한 Ding [35]의 **열린 문제 5.31(Open Problem 5.31)**을 부분적으로 해결한다.
   • $q$와 $t$에 따라 2에서 $2^{t-2} + 2$ 사이의 $d$에 대한 하한이 제공된다.

4. $x^{(3^{(m+1)/2} + 1)/2}$ ($m$이 홀수일 때)로부터의 3진 부호:

   • $m$에 따라 PN(Perfect Nonlinear) 함수 또는 4-uniform 함수인 모노미얼을 활용한다.
   • 선형 스팬은 $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$으로 계산된다.
   • 특정 가분성 조건 하에서 $d \ge 8$인 최소 거리 하한이 설정된다.

5. $x^{p^h - 1}$ ($1 \le h \le \lceil m/2 \rceil$)로부터의 $p$-진 부호:

   • 이전의 이진 결과를 홀수 표수로 일반화한다.
   • 선형 스팬은 $p$-진 전개와 특정 집합 정의($\hat{\Gamma}(t)$)를 사용하여 도출된다.
   • 최소 거리 하한은 많은 경우 코드 길이의 제곱근보다 현저히 높음을 보인다 (예: $d \ge p^h + 2$).
   • $h \mid m$인 경우의 정확한 거리는 설계 거리 $p^h + 1$을 갖는 좁은 의미의 프리미티브 BCH 코드와 동일함을 보여준다.

6. $x^{2 \cdot p^{m/2} - 1}$ 및 $x^{p^{2h} - p^h + 1}$로부터의 코드:

   • 이 섹션들은 특정 지수를 사용하여 짝수 및 홀수 $m$을 처리한다.
   • 저자들은 선형 스팬과 최소 다항식에 대한 복잡한 식을 도출한다.
   • 정리 11과 정리 13은 이 가족들에 대한 최소 거리 하한이 종종 제곱근 경계($\sqrt{v}$)보다 훨씬 우수함을 입증한다.

의의 및 주장
본 논문은 Ding과 Zhou [14]의 이진 프레임워크를 비이진 설정으로 확장한다고 주장한다. 주요 의의는 다음과 같다:

• 파라미터 개선: 구성된 코드들은 차원 $k > (q^m - 1)/2$ 및 최소 거리 $d > \sqrt{q^m - 1}$을 달성하여 코드율과 오류 정정 능력 사이의 균형을 효과적으로 맞춘다.
• 열린 문제 해결: 본 연구는 $m$이 홀수일 때 $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$로 정의된 3진 순환 부호에 관한 Ding [35]의 열린 문제 5.31을 부분적으로 해결한다.
• 최적성: 구성된 여러 코드(및 그 쌍대 코드)는 알려진 최적 선형 코드 데이터베이스 [47]와 비교했을 때 최적 또는 거의 최적인 것으로 확인되었다.
• 이론적 발전: 본 논문은 홀수 표수 필드의 복잡성을 다루기 위해 사이클로토믹 코셋, $p$-진 전개, 루카스 정리를 활용하여 무한 가족 코드에 대한 선형 스팬과 생성 다항식의 명시적인 공식을 제공한다.

저자들은 이러한 구성들이 까다로운 응용 분야에 적합한 코드의 풍부한 원천을 제공한다고 결론지으며, 홀수 표수의 거듭제곱 함수에 대한 추가적인 탐구가 더 최적화된 가족을 낳을 수 있음을 시사한다. 또한, 이 코드들이 CSS 구성을 통해 양자 오류 정정 코드를 구축하는 데 사용될 가능성이 있음을 언급한다.