Construction of MRD Codes Based on Circular-Shift Operations

1. 연구 배경 및 문제 정의 (Problem)

• 기존 MRD 코드의 한계:
  • 현재 잘 알려진 MRD 코드 (Gabidulin 코드, Twisted Gabidulin 코드 등) 는 확장체 (extension field) $\mathbb{F}_{q^N}$의 산술 연산에 의존하여 구성됩니다.
  • 파라미터 $N$이 커질수록 $\mathbb{F}_{q^N}$에서의 연산 복잡도가 급격히 증가하여, 파라미터 선택의 유연성이 떨어지고 실제 구현이 어려워집니다.
  • 특히, $\mathbb{F}_{q^N}$의 기저 (basis) 를 선택하여 벡터를 행렬로 변환하는 과정이 비효율적일 수 있으며, 이는 실용성을 저해합니다.
• 목표:
  • 확장체 $\mathbb{F}_{q^N}$의 복잡한 산술 연산을 피하고, 기본 체 $\mathbb{F}_q$의 연산 (특히 XOR 연산) 만으로 효율적으로 인코딩할 수 있는 MRD 코드를 개발하는 것입니다.

2. 제안된 방법론 (Methodology)

논문은 원형 시프트 (circular-shift) 연산을 핵심 도구로 활용하여 새로운 MRD 코드 구성을 제시합니다.

• 기본 설정:

  • $q$를 소수, $L$을 $q$와 서로소인 양의 정수 ($\gcd(q, L)=1$) 로 둡니다.
  • $m_L$: $q$를 모듈로 $L$로 나눈 곱셈 차수 (multiplicative order, $q^{m_L} \equiv 1 \pmod L$).
  • $J$: $L$에 대한 오일러 피 함수 값 ($J = \phi(L)$).
  • 코드 파라미터: $(J \times n, q^{Jk}, d)$ 형태의 MRD 코드 ($n \le m_L \le J$).

• 코드 구성 (Definition 6):

  • 코드 $C$는 다음과 같은 행렬 연산으로 정의됩니다:
    $$C = \{ \Delta(m(I_k \otimes P)\Psi_{k \times n}(I_n \otimes Q)) : m \in \mathbb{F}_q^{Jk} \}$$
  • 주요 구성 요소:
    • $\Psi_{k \times n}$: $L \times L$ 크기의 순환 행렬 (circulant matrix) $C_L$을 블록으로 갖는 $k \times n$ 블록 행렬.
    • $P, Q$: $\mathbb{F}_q$ 위에서 정의된 행렬 (제안된 구성에서는 $P=GL, Q=HL$로 설정).
    • $\Delta$: $Jn$차원 행 벡터를$J \times n$ 행렬로 매핑하는 함수.
  • 핵심 특징: 모든 연산이 기본 체 $\mathbb{F}_q$에서 수행되며, 확장체 $\mathbb{F}_{q^J}$의 산술 연산이 필요 없습니다.

• 행렬 $P, Q$ 설계:

  • MRD 성질을 만족시키기 위해 Vandermonde 행렬과 원시 $L$차 단위근을 이용하여 $GL$과$HL$을 구성합니다.
  • 두 가지 구성 방식 ($C_1$과 $C_2$) 을 제시하며, $C_2$는 다항식 $\tau(x)$를 활용하여 인코딩 복잡도를 추가로 최적화할 수 있습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

3.1. Gabidulin 코드 및 Twisted Gabidulin 코드와의 관계 규명

논문은 제안된 코드를 $q$-선형화 다항식 ($q$-linearized polynomials) 을 통해 재해석하여 기존 코드들과의 관계를 명확히 했습니다.

• 경우 $J \neq m_L$:
  • 특정 파라미터 설정 하에서 제안된 MRD 코드는 **어떤 Gabidulin 코드나 Twisted Gabidulin 코드와도 동일하지 않음 (non-equivalent)**을 증명했습니다.
  • 이는 새로운 형태의 MRD 코드 계열을 발견했음을 의미합니다.
• 경우 $J = m_L$:
  • 제안된 코드가 **Gabidulin 코드와 동치 (equivalent)**임을 증명했습니다.
  • 의의: 기존 Gabidulin 코드는 $\mathbb{F}_{q^J}$ 연산을 필요로 하지만, 제안된 방법은 $\mathbb{F}_q$ 연산만으로 동일한 코드를 구성할 수 있는 새로운 접근법을 제공합니다.

3.2. 일반화된 Gabidulin 코드와의 동치성

• 특정 행렬 $P, Q$ 선택 하에서 제안된 코드는 여러 개의 $(m_L \times n, q^{m_L k}, d)$ Gabidulin 코드를 합산하고 연결 (concatenating) 하여 만든 일반화된 Gabidulin 코드와 동치임을 보였습니다.
• 이는 기존 문헌에서 탐구되지 않았던 새로운 코드 구조를 제시합니다.

3.3. 계산 복잡도 분석 (Computational Complexity)

$q=2$, $L$이 소수, $n \le m_L$인 경우 인코딩 복잡도를 분석했습니다.

• 제안된 코드 (Circular-shift-based MRD):
  • 복잡도: $O(nkL)$ XOR 연산.
  • 특징: 확장체 곱셈이 필요 없으며, 행렬 곱셈과 XOR 연산, 원형 시프트만으로 구성됩니다.
• 기존 Gabidulin 코드 (Customary Construction):
  • 복잡도: $O(nkL^2)$ XOR 연산.
  • 이유: $\mathbb{F}_{2^L}$에서의 곱셈이 $O(L^2)$의 XOR 연산을 필요로 하기 때문입니다.
• 결론: 제안된 방법은 기존 방법보다 선형 (linear) 에 가까운 복잡도를 가지며, $L$이 클수록 효율성 차이가 극대화됩니다.

4. 의의 및 결론 (Significance)

1. 효율적인 인코딩: 확장체 연산을 배제하고 기본 체의 XOR 연산과 시프트 연산만으로 MRD 코드를 구성하여, 암호학 및 분산 저장 시스템에서의 실시간 처리 속도를 획기적으로 개선할 수 있습니다.
2. 파라미터 유연성: 확장체의 크기에 제한받지 않고 $J$와 $k$를 자유롭게 선택할 수 있어 시스템 설계의 유연성이 높아졌습니다.
3. 이론적 통찰: Gabidulin 코드와 제안된 코드가 동치인 경우와 다른 경우를 명확히 구분하여, MRD 코드 공간의 구조에 대한 이해를 심화시켰습니다.
4. 실용성: $q=2$인 이진 환경에서 특히 유리하며, 네트워크 부호화 (Network Coding) 및 저장 시스템에 직접 적용 가능한 저복잡도 솔루션을 제공합니다.

요약하자면, 이 논문은 MRD 코드의 실용적 장벽인 높은 계산 복잡도를 해결하기 위해 원형 시프트 연산을 도입한 혁신적인 구성법을 제시하며, 기존 코드들과의 이론적 관계를 규명하고 인코딩 효율성을 $O(L^2)$에서 $O(L)$로 낮추는 성과를 거두었습니다.