On the equivalence between additive and linear codes

1. 문제 제기 (Problem Statement)

• 배경: 가법 코드는 선형 코드보다 우수한 성능을 가질 수 있어 양자 오류 정정 코드 구성 등에 주목받고 있습니다. 특히 4 진 (Quaternary) 가법 코드 중 선형 코드보다 더 좋은 최소 거리 (Minimum Distance) 를 가지는 예시들이 최근 발견되었습니다.
• 핵심 문제: 새로운 가법 코드가 구성되었을 때, 이것이 **진정한 의미의 '엄격한 가법 코드 (Strictly Additive Code)'**인지, 아니면 단순히 선형 코드와 동등한 (Equivalent) 코드인지 구분하는 것이 근본적인 난제였습니다.
• 기존 방법의 한계: 기존 연구들은 주로 기하학적 기법 (예: 의사-호 (pseudo-arcs), Desarguesian 스프레드 등) 을 사용하여 동등성을 판별했으나, 이는 모든 가법 코드에 적용하기 어렵거나 계산적으로 복잡했습니다.
• 목표: 생성 행렬 (Generator Matrix) 만을 사용하여 어떤 가법 코드가 선형 코드와 동등한지 여부를 결정하는 **대수적 (Algebraic) 인 결정적 테스트 (Deterministic Test)**를 개발하는 것입니다.

2. 방법론 (Methodology)

저자들은 유한체 $\mathbb{F}_{q^2}$ 위의 가법 코드를 $\mathbb{F}_q$ 위의 선형 공간으로 변환하는 사상 $\phi$를 기반으로 대수적 프레임워크를 구축했습니다.

• 대수적 프레임워크:

  • $\mathbb{F}_{q^2}$의 원소를 $\mathbb{F}_q$의 기저 $\{1, \omega\}$에 대해 표현하여, 가법 코드 $C$를 $\mathbb{F}_q^{2n}$의 부분공간으로 매핑합니다.
  • 코드가 $\mathbb{F}_{q^2}$-선형 코드가 되기 위한 필요충분 조건을 도출하기 위해, $\mathbb{F}_{q^2}$의 곱셈 연산을 행렬로 표현하는 **정규 표현 (Regular Representation)**을 활용합니다.
  • $\omega$의 최소 다항식에 해당하는 $2 \times 2$ 동반 행렬 $M_\omega$를 정의하고, 이를 통해 $\mathbb{F}_{q^2}$-선형성 조건을 행렬 방정식으로 변환합니다.

• 동등성 판별 알고리즘 (Algorithm 1):

  1. 행렬 분할 및 랭크 확인: 생성 행렬 $G$를 $n$개의 $k \times 2$ 블록 ($G_i$) 으로 분할합니다.
     • 만약 어떤 $G_i$가 영행렬이면 좌표를 제거 (puncture) 합니다.
     • 만약 어떤 $G_i$의 랭크가 1 이라면, 해당 코드는 선형 코드와 동등하지 않음을 즉시 판별합니다 (Theorem 3.2).
  2. 선형 시스템 구성: 코드가 선형 코드와 동등하기 위해서는 특정 조건을 만족하는 행렬 $R$과 블록 대각 행렬 $A$가 존재해야 합니다. 이를 만족하는 $R$의 공간 (Null Space) 을 찾기 위해 크로네커 곱 (Kronecker product) 을 사용하여 대규모 선형 동차 시스템 $S\mathbf{x} = 0$을 구성합니다.
  3. 영수 (Nullity) 테스트:
     • 시스템 행렬 $S$의 영수 (Nullity, 즉 영공간 차원) 가 홀수이면, 해당 코드는 선형 코드와 동등하지 않음을 증명합니다 (Theorem 3.3). 이는 $\mathbb{F}_{q^2}$-선형 코드의 경우 해당 공간의 차원이 반드시 짝수여야 하기 때문입니다.
     • 영수가 짝수인 경우, 영공간의 기저를 탐색하여 실제 $\mathbb{F}_{q^2}$-선형 변환 행렬 $R$이 존재하는지 확인합니다.

3. 주요 기여 (Key Contributions)

1. 대수적 동등성 판별 기준 정립: 기하학적 방법이 아닌, 오직 생성 행렬의 대수적 성질만을 기반으로 한 결정적 테스트를 최초로 제안했습니다.
2. 필요충분 조건 및 필요 조건 도출:
   • Theorem 3.1: 가법 코드가 선형 코드와 동등할 필요충분 조건을 행렬 방정식 $RG = G(AM_\omega A^{-1})$ 형태로 제시했습니다.
   • Theorem 3.2: 생성 행렬의 블록 랭크가 1 인 경우 선형 코드와 동등하지 않음을 보였습니다.
   • Theorem 3.3: 시스템 행렬 $S$의 영수가 홀수이면 코드가 엄격한 가법 코드임을 증명했습니다.
3. 계산적 검증 도구 개발: MAGMA 컴퓨터 대수 시스템을 활용하여 위 알고리즘을 구현하고, 기존 문헌의 코드들을 대량으로 검증할 수 있는 프레임워크를 제공했습니다.

4. 연구 결과 (Results)

저자들은 제안된 알고리즘을 적용하여 두 가지 주요 문헌 [14] 과 [18] 의 4 진 가법 코드를 검증했습니다.

• 엄격한 가법 코드 확인 (Strictly Additive Codes):

  • 문헌 [14] 의 코드: Table II 에 나열된 여러 4 진 가법 코드 (예: $[47, 35, 7]_2^2$, $[63, 5, 45]_2^2$ 등) 에 대해 $S$의 영수가 모두 **1 (홀수)**임을 확인하여, 이들이 선형 코드와 동등하지 않은 엄격한 가법 코드임을 증명했습니다.
  • 문헌 [18] 의 코드: Plotkin 합 구성을 통해 얻어진 10 개의 4 진 ACD (Additive Complementary Dual) 코드 중 5 개는 랭크 조건으로, 나머지 5 개는 영수 계산을 통해 선형 코드와 동등하지 않음을 확인했습니다.

• 선형 코드와의 동등성 발견 및 성능 향상:

  • 문헌 [14] 의 ACD 코드: Table IV 의 1 번 항목인 $[22, 10, 9]_2^2$ ACD 코드를 분석한 결과, $S$의 영수 차원이 2 (짝수) 이었고, 구체적인 변환 행렬을 찾아 이 코드가 $\mathbb{F}_4$ 위의 선형 Hermitian LCD 코드와 동등함을 증명했습니다.
  • 의의: 이 발견은 기존에 알려진 선형 Hermitian LCD 코드의 최소 거리 한계를 개선하는 결과를 도출했습니다 (참고문헌 [2, Table 6] 의 해당 항목 개선).

5. 의의 및 결론 (Significance)

• 이론적 기여: 가법 코드와 선형 코드의 관계를 규명하는 데 있어 기하학적 접근의 한계를 넘어, 순수 대수적 방법론을 정립함으로써 코드 분류의 엄밀성을 높였습니다.
• 실용적 기여:
  • 새로운 가법 코드가 구성되었을 때, 그것이 기존 선형 코드의 단순한 변형인지, 아니면 새로운 성능을 가진 엄격한 가법 코드인지를 빠르고 정확하게 판별할 수 있는 도구를 제공합니다.
  • 기존에 '엄격한 가법 코드'로 오인되었거나 불확실했던 코드들 중 일부가 사실은 선형 코드와 동등하여, 선형 코드의 성능 한계를 개선하는 새로운 사례를 발견했습니다.
• 향후 연구: 이 방법론은 $q$가 홀수인 경우를 포함한 더 일반적인 유한체 $\mathbb{F}_{q^h}$로 확장 가능하며, 양자 코드 및 다른 오류 정정 코드 설계에 중요한 기준을 제시합니다.

요약하자면, 이 논문은 행렬의 영수 (Nullity) 분석을 통해 가법 코드의 선형성 동등성을 판별하는 강력한 알고리즘을 제시하고, 이를 통해 기존 문헌의 코드들을 재평가하여 엄격한 가법 코드를 확인함과 동시에 새로운 선형 코드 기록을 갱신하는 성과를 거두었습니다.