The equivalent condition for GRL codes to be MDS, AMDS or self-dual

기술 요약: GRL 코드가 비-GRS MDS, AMDS 또는 자기 쌍대(Self-Dual)가 되기 위한 동치 조건

문제 정의
최대 거리 분리(Maximum Distance Separable, MDS) 및 거의 최대 거리 분리(Almost MDS, AMDS) 코드와 자기 쌍대 코드는 중요한 대수적 성질을 지니며 통신 시스템, 데이터 저장, 양자 코딩 및 암호학 분야에서 널리 적용된다. 리드-솔로몬(Reed-Solomon, RS) 코드는 잘 알려진 MDS 코드의 한 종류이지만, 가용 가능한 코드 패밀리의 다양성을 확장하기 위해 RS 코드와 동등하지 않은(non-RS) 코드를 구축하는 것은 여전히 중요한 연구 분야이다. Roth와 Lempel [20], 그리고 이후 Wu 등 [21, 22]은 RS 코드의 생성 행렬에 두 개 또는 세 개의 추가 열을 증강함으로써 특정 클래스의 non-RS MDS 코드를 구축하였다. 본 논문은 이러한 일반화된 구축법을 더욱 확장하고, 이들 일반화된 코드(및 그 쌍생 코드)가 RS 코드와 동등하지 않으면서 MDS, AMDS 또는 자기 쌍대 성질을 갖게 되는 정확한 대수적 조건을 확립하는 문제를 다룬다.

방법론
저자들은 유한체 $F_q$ 상에서 정의된, $A_{l \times l} \in GL_l(F_q)$인 임의의 가역 행렬 $A_{l \times l}$을 사용하여 이전 모델들을 일반화한 일반화된 Roth-Lempel (GRL) 코드 $GRL_k(\alpha, v, A_{l \times l})$를 도입한다. 구체적으로, 본 논문은 $l=3$인 경우인 $GRL_k(\alpha, v, A_{3 \times 3})$에 집중한다.

본 논문의 방법론은 다음과 같은 기술적 접근 방식을 채택한다:

1. 생성 행렬 분석: 저자들은 표준 반데르몽드 유사 구조에 $A_{3 \times 3}$으로부터 유도된 세 개의 열이 증강된 형태인 $GRL_k(\alpha, v, A_{3 \times 3})$ 코드의 생성 행렬 $G_4$를 정의한다.
2. Non-RS 검증: 저자들은 RS 코드의 특성을 나타내는 보조정리 5(Lemma 5)를 활용하여 코드가 non-RS임을 증명하며, 증강된 열들의 특정 구조가 $k > 3$일 때 RS 동등성을 위한 필요 조건을 만족하지 못함을 입증한다.
3. MDS 및 AMDS 조건: 생성 행렬의 임의의 $k$개 열이 선형 독립일 필요충분조건이 MDS라는 보조정리 6(Lemma 6)을 사용하여, 생성 행렬으로 형성되는 모든 가능한 $k \times k$ 부분 행렬의 행렬식(determinant)을 분석한다. 이는 증강된 열($u_1, u_2, u_3$)이 부분 행렬에 포함되는 경우에 대한 광범위한 사례 분석을 포함한다.
4. 패리티 검사 행렬 구축: 자기 쌍대 분석을 위해, 저자들은 GRL 코드에 대한 명시적인 패리티 검사 행렬 $H_5$를 유도한다. 이들은 역차이(inverse differences)의 거듭제곱 합에 대한 성질을 다루는 보조정리 4(Lemma 4)를 활용하여 직교 조건 $G H^T = 0$을 검증한다.
5. 자기 쌍대 기준: 자기 쌍대 조건($C = C^\perp$)은 생성 행렬과 패리티 검사 행리가 동일한 공간을 생성해야 한다는 요구사항을 통해 확립되며, 이는 벡터 $v$와 행렬 $A_{3 \times 3}$에 대한 특정 제약 조건으로 이어진다.

주요 기여 및 결과

1. Non-RS 성질: 정리 7은 $A_{3 \times 3} \in GL_3(F_q)$인 경우, 매개변수의 선택과 관계없이 $k > 3$에 대해 $GRL_k(\alpha, v, A_{3 \times 3})$가 엄격한 non-GRS(Generalized Reed-Solomon)임을 확립한다.

2. Non-RS MDS를 위한 동치 조건: 정리 8은 $GRL_k(\alpha, v, A_{3 \times 3})$가 MDS가 되기 위한 필요충분조건을 제공한다. 이 조건들은 평가 점 $\alpha_i$들의 곱의 합과 $A_{3 \times 3}$의 성분들 사이의 부등식으로 표현된다. 구체적으로, 크기가 $k-1$ 또는 $k-2$인 임의의 부분 집합에 대해, 행렬 성분을 포함하는 특정 다항식 표현이 0이 되지 않아야 한다.

   • 따름정리 10과 예제 11은 특정 행렬 형태와 $F_{11}$ 상의 구체적인 예시를 통해 이러한 조건들을 설명하며, $[8, 4, 5]$ 코드를 도출한다.

3. AMDS 쌍생 코드를 위한 동치 조건: 정리 12는 쌍생 코드 $GRL_k^\perp(\alpha, v, A_{3 \times 3})$가 AMDS가 되는 조건을 결정한다. 이를 위해서는 생성 행렬의 임의의 $k-1$개 열은 선형 독립이어야 하며, 적어도 하나의 $k$개 열 집합은 종속이어야 한다. 정리는 $A_{3 \times 3}$의 성분들과 $\alpha_i$의 합을 포함하는 여섯 가지 특정 사례를 나열한다.

   • 따름정리 13과 예제 14는 $F_7$ 상의 구체적인 구현을 제공하며, $[8, 4, 4]$ 코드를 생성한다.

4. 패리티 검사 행렬 및 자기 쌍대성: 정리 16은 GRL 코드에 대한 패리티 검사 행렬 $H_5$를 구축한다. 이를 바탕으로, 정리 17은 코드가 non-RS 자기 쌍대가 되기 위한 동치 조건을 제공한다. 조건은 다음과 같다:

   • $n + 3 = 2k$ (차원 제약).
   • 벡터 $v$는 역차이 벡터 $u$에 비례해야 한다 (즉, $v_i = \lambda u_i$).
   • 행렬 $A_{3 \times 3}$은 $\alpha_i$와 $\alpha_i^2$의 합을 포함하는 특정 이차 관계식을 만족해야 한다.
   • 예제 18과 19는 각각 $F_{13}$과 $F_{19}$ 상에서의 자기 쌍대 코드 구축을 보여준다. 특히, 예제 19는 이전 문헌 [22]의 제약을 넘어 $q \equiv 3 \pmod 4$인 경우에도 자기 쌍대 GRL 코드를 구축할 수 있음을 강조한다.

의의
본 논문은 특정 증강 행렬을 일반적인 가역 행렬 $A_{3 \times 3}$으로 대체함으로써 [21]과 [22]의 결과를 일반화한다고 주장한다. 주요 의의는 이러한 일반화된 코드들이 최적의 거리 성질(MDS/AMDS) 또는 자기 쌍대성을 갖게 되는 시점을 결정하는 통합된 프레임워크를 제공한다는 점에 있다. 저자들은 자신들의 결과가 [21]의 정리들을 특수 사례로서 회복함을 명시적으로 밝히고 있다. 나아가, $q \equiv 3 \pmod 4$에 대한 자기 쌍대 코드의 구축(예제 19)은 기존 문헌의 제약을 넘어 이러한 코드의 적용 가능성을 확장한다. 결론적으로, 이러한 동치 조건들은 통신 및 암호학 응용 분야에 적합한 desirable한 성질을 가진 non-RS 코드를 체계적으로 구축할 수 있게 한다.