2025-11-19T11:49:14.147379

On codes induced from Hadamard matrices

Hurley

Unit derived schemes applied to Hadamard matrices are used to construct and analyse linear block and convolutional codes. Codes are constructed to prescribed types, lengths and rates and multiple series of self-dual, dual-containing, linear complementary dual and quantum error-correcting of both linear block {\em and} convolutional codes are derived.

academic

Hadamard 행렬로부터 유도된 부호에 관하여

기본 정보

논문 ID: 2410.24027
제목: Hadamard 행렬로부터 유도된 부호에 관하여
저자: Ted Hurley (Galway 대학교)
분류: cs.IT math.IT (정보 이론)
발표 시간: 2024년 10월 (v2: 2025년 11월 17일)
논문 링크: https://arxiv.org/abs/2410.24027

초록

본 논문은 단위 유도 방식(unit derived schemes)을 Hadamard 행렬에 적용하여 선형 블록 부호와 합성곱 부호를 구성하고 분석한다. 논문은 지정된 유형, 길이 및 부호율을 가진 부호를 구성하였으며, 자기 쌍대 부호, 쌍대 포함 부호, 선형 상보 쌍대 부호 및 양자 오류 정정 부호의 여러 계열을 유도하였다. 이는 선형 블록 부호와 합성곱 부호 두 가지 범주를 포함한다.

연구 배경 및 동기

연구 문제

합성곱 부호 구성의 대수적 방법 부재: McEliece 등이 지적한 바와 같이, 합성곱 부호는 일반적인 대수적 구성 및 설계 방법이 부족하여 그 규모와 가용성이 크게 제한된다.
특정 유형 부호의 체계적 구성: 특정 속성(자기 쌍대, 쌍대 포함, LCD 부호 등)을 만족하는 부호를 구성하고 길이, 거리 및 부호율을 제어할 필요가 있다.
양자 오류 정정 부호의 구성: 고전 부호 이론(예: CSS 방법)을 통해 양자 오류 정정 부호를 구성해야 한다.

연구의 중요성

이론적 의의: 부호 이론에 통일된 대수적 구성 프레임워크 제공
실제 응용:
- LCD 부호는 측면 채널 공격 및 결함 공격에 대한 저항에 사용 가능
- 자기 쌍대 부호와 쌍대 포함 부호는 양자 오류 정정 부호 구성에 사용 가능
- 합성곱 부호는 통신 시스템에 광범위하게 적용됨 (예: Viterbi 알고리즘 복호)

기존 방법의 한계

Walsh-Hadamard 부호는 우수한 거리 특성을 가지지만 부호율이 매우 낮음 (1/2^k)
Hadamard 행렬로부터 다양한 유형의 부호를 체계적으로 구성하는 일반적인 방법 부재
합성곱 부호의 구성은 오랫동안 컴퓨터 생성에 의존하며 대수 이론 지원 부족

연구 동기

본 논문은 저자가 27에서 제시한 단위 유도 방법을 확장하여 Hadamard 행렬에 적용함으로써 다음을 실현한다:

선형 블록 부호와 합성곱 부호의 동시 구성
지정된 유형, 길이 및 부호율로의 구성
계산 가능한 거리 경계 획득
단일 Hadamard 행렬로부터 여러 부호 생성

핵심 기여

이론적 프레임워크: Hadamard 행렬 기반의 단위 유도 부호 구성 이론 수립, 5개의 핵심 명제(Propositions 2.1-2.5) 증명
알고리즘 설계: 4개의 일반적 구성 알고리즘 제시:
- 알고리즘 1: 임의 부호율 r/n의 LCD 선형 블록 부호 구성
- 알고리즘 2: 길이 2n의 자기 쌍대 선형 블록 부호 구성
- 알고리즘 3: 길이 n의 자기 쌍대 합성곱 부호 구성
- 알고리즘 4: 부호율 r/n (r≥n/2)의 쌍대 포함 합성곱 부호 구성
다중 유형 부호의 통일 구성: 동일한 Hadamard 행렬로부터 LCD, 자기 쌍대, DC 및 양자 오류 정정 부호 구성 가능
거리 분석: 거리의 대수적 계산 방법 제공, 합성곱 부호 거리는 선형 블록 부호의 2배까지 도달 가능
구체적 응용: H(20), H(28) 등 여러 구체적 사례 제시, 다량의 새로운 부호 구성

방법론 상세 설명

작업 정의

입력: n×n Hadamard 행렬 H, HH^T = nI_n 만족, 원소는 ±1 출력:

선형 블록 부호: n,r,d_q 부호 (길이 n, 차원 r, 최소 거리 d, 체 GF(q))
합성곱 부호: (n,k,δ;μ,d_f)_q 부호 (길이 n, 계수 k, 차수 δ, 메모리 μ, 자유 거리 d_f)

제약 조건:

체의 특성 p는 p∤n을 만족 (대부분의 구성)
자기 쌍대 합성곱 부호의 경우 i=√(-1)이 체에 존재해야 함
행렬의 계수 조건

핵심 방법 구조

1. 선형 블록 부호 구성 (기본 방법)

Hadamard 행렬을 분할: H = (A/B), 여기서 A는 r×n 행렬

핵심 성질:

(A/B)(A^T  B^T) = nI_n

체 GF(p) (p∤n)에서 이는 다음과 같이 변환됨:

AA^T + BB^T = 0 (mod p)
즉, AB^T = 0

결과:

A는 n,r 부호 생성
B^T는 검사 행렬
B는 쌍대 부호 생성

2. LCD 부호 구성 (명제 2.1)

정리: H = (A/B)에 대해, p∤n이면 A는 LCD 부호를 생성함

증명 요점:

AB^T = 0 ⟹ B는 A의 쌍대 부호 생성
H는 가역 ⟹ A의 행은 B의 행의 비자명 조합이 될 수 없음
따라서 C∩C^⊥ = 0 (LCD 성질)

3. 자기 쌍대 선형 블록 부호 (명제 2.2)

구성: G = (I_n, αH), 여기서 α는 1+α²n=0을 만족

핵심 계산:

(I_n, αH)(I_n / αH^T) = I_n + α²nI_n = (1+α²n)I_n

1+α²n=0일 때:

(I_n / αH^T)는 계수가 n인 검사 행렬
K = (I_n, αH)는 쌍대 부호 생성
따라서 부호는 자기 쌍대임

구현 세부사항:

α는 GF(p) 또는 그 이차 확장 GF(p²)에 존재 가능
생성 행렬은 직접 체계적 형태로 제공됨

4. 자기 쌍대 합성곱 부호 (명제 2.3)

구성: H = (A/B), n=2m, A와 B는 각각 m×n

생성 행렬 정의:

G(z) = A + iBz, 여기서 i=√(-1)

자기 쌍대성 검증:

G(z)(iB^T + A^Tz) = (A+iBz)(iB^T+A^Tz)
                   = 0 + nI_m·z - nI_m·z + 0 = 0

따라서 H^T(z) = iB^T + A^Tz는 검사 행렬이고, H(z^(-1))z = A+iB는 쌍대 부호를 생성함

비재난성 검증:

(A+iBz)A^T = nI_m

따라서 G(z)는 우측 다항식 역을 가지며, 부호는 비재난성임

거리 계산:

d_f = d(A) + d(B)

5. 쌍대 포함 합성곱 부호 (명제 2.4)

구성: H = (A/B), A는 r×n, B는 (n-r)×n, r>n-r

정의:

B_1 = (0_{t×n} / B), 여기서 t=2r-n
G(z) = A + iB_1z

DC 성질 검증:

검사 행렬 구성: H^T(z) = iB^T + C_1z
쌍대 부호 생성기: C_1^T + iB
쌍대 부호가 원래 부호에 포함됨을 검증

기술적 혁신점

행렬 분할 전략: 동일한 Hadamard 행렬로부터 다양한 분할 방식을 통해 다양한 유형의 부호 획득
매개변수 제어: 행 수 r 선택을 통해 부호율 제어 (r/n)
체 확장 기법: √(-1)의 존재성을 이용한 합성곱 부호 구성
거리 계산 가능성: Hadamard 행렬의 직교성을 이용한 대수적 거리 계산
통일 프레임워크: 선형 블록 부호와 합성곱 부호의 구성 방법 통일

실험 설정

데이터 집합 (Hadamard 행렬)

본 논문은 다양한 크기의 Hadamard 행렬을 사용:

소규모: H(12), H(20), H(24), H(28)
중규모: H(36), H(40), H(72)
대규모: H(144)

행렬 유형:

Paley-Hadamard 행렬 (크기 12k에 사용)
비분해 가능 Hadamard 행렬 (성능이 더 우수하므로 우선 사용)

평가 지표

부호 길이 n: 부호의 길이
차원/계수 r 또는 k: 정보 비트 수량
부호율: r/n (선형 블록 부호) 또는 k/n (합성곱 부호)
최소 거리 d: 오류 정정 능력의 척도
메모리 μ: 합성곱 부호의 메모리 길이
자유 거리 d_f: 합성곱 부호의 거리 척도

계산 도구

GAP 컴퓨터 대수 시스템 및 그 패키지:
- Guava 패키지: 부호 이론 계산
- Gauss 패키지: 유한체 상의 행렬 연산
사용 목적: 부분 행렬 연산, 유한체 계산, 거리 검증

구현 세부사항

체 선택: 주로 GF(3), GF(5), GF(7) 및 그 확장 GF(3²), GF(5²) 사용
계수 계산: 모듈로 p 의미에서 행렬 계수 계산
거리 계산:
- 소규모 길이 (≤100): 컴퓨터 직접 계산
- 대규모 길이: 대수적 방법 사용 (명제 2.6, 보조정리 2.18)

실험 결과

주요 결과

1. H(20)으로부터 구성된 부호

유형	매개변수	체	설명
LCD	20,13,4₃, 20,7,6₃	GF(3)	선형 상보 쌍대 부호
자기 쌍대 합성곱	(20,10,10;1,12)₃₂	GF(3²)	거리 12
DC 합성곱	(20,13,7;1,8)₃₂	GF(3²)	쌍대 포함
양자 부호	길이 20, 거리 8, 부호율 6/20	GF(3²)	CSS 구성을 통해
자기 쌍대	20,10,8₅	GF(5)	선형 블록 부호
자기 쌍대 합성곱	(20,10,10;1,14)₇₂	GF(7²)	거리 14
자기 쌍대	40,20,12₃	GF(3)	체계적 형태

2. H(28)으로부터 구성된 부호

유형	매개변수	체
LCD	28,16,6₃, 28,12,9₅	GF(3), GF(5)
자기 쌍대 합성곱	(28,14,14;1,12)₃	GF(3)
DC 합성곱	(28,18,10;1,8)₃	GF(3)
양자 부호	길이 28, 거리 8, 부호율 8/28	GF(3)
자기 쌍대 합성곱	(28,14,14;1,16)₅	GF(5)
자기 쌍대	28,14,9₇	GF(7)

3. 3진 부호의 극값 성질

H(12k)의 Paley-Hadamard 행렬에 대해:

자기 쌍대 12k, 6k, d₃ 부호 구성
검증 결과: k=1,2,3,4,5 (즉, n=12,24,36,48,60)에 대해 구성된 부호는 최적 거리 달성
이론적 상한: d ≤ ⌊n/12⌋+3
n=72 이상에서는 극값 부호 존재하지 않음

주요 발견

1. 거리 성능

합성곱 부호 vs 선형 블록 부호:

예: H(12):
- 선형 블록 부호 A: 12,6,6
- 합성곱 부호 G(z)=A+iBz: 거리 d_f=12
- 합성곱 부호 거리는 선형 블록 부호의 2배

2. 부호율 유연성

임의 부호율 r/n (0<r<n)의 LCD 부호 구성 가능
자기 쌍대 부호: 부호율 고정 1/2
DC 합성곱 부호: 부호율 r/n, r≥n/2

3. 계수 성질 (보조정리 2.7)

p|n (p≠2)인 소수에 대해:

rank(H) ≤ n/2 in GF(p)

검증: Paley-Hadamard 행렬 H(12k)는 GF(3)에서 계수가 정확히 6k

구체적 사례 분석

원형 예제 2.9: H(12) 상세 분석

행렬 분해: H = (A/B), A와 B는 각각 6×12

응용 1: 자기 쌍대 선형 블록 부호 (GF(3))

GF(3)에서: AA^T = 0 (3|12이므로)
A는 12,6,6₃ 자기 쌍대 부호 생성
최적성: 이론적 최적 거리 달성
오류 정정 능력: 2개 오류 정정 가능

응용 2: LCD 부호 (GF(5))

A는 12,6,6₅ LCD 부호 생성
B는 쌍대 부호 생성, 역시 12,6,6₅

응용 3: 자기 쌍대 합성곱 부호 (GF(5))

G(z) = A + 2Bz (2=√(-1) in GF(5))
매개변수: (12,6,6;1,12)₅
거리: d_f = d(A) + d(B) = 6+6 = 12
비재난성: (A+2Bz)A^T = 6I₆ = I₆

응용 4: 길이 24 자기 쌍대 부호 (GF(5²))

α²=2 필요, x²-2는 GF(5)에서 기약
GF(5²)에서: (I₁₂, αH)는 24,12,8₅₂ 자기 쌍대 부호 생성

응용 5: 길이 24 자기 쌍대 부호 (GF(7))

α=2는 1+12α²=0을 GF(7)에서 만족
(I₁₂, 2H)는 24,12,8₇ 자기 쌍대 부호 생성

예제 2.10: 고메모리 합성곱 부호

H(12)로부터 메모리 3의 합성곱 부호 구성:

A = H[1..3][1..12]
B = H[4..6][1..12]
C = H[7..9][1..12]
D = H[10..12][1..12]
G(z) = A + Bz + Cz² + Dz³

매개변수: (12,3,9;3,24) 거리: 24 (모든 부분 행렬의 거리가 6이므로)

대규모 응용

예제 2.11: 대규모 길이 부호

H(72): 72,36,18₃ 자기 쌍대 부호
H(144): 144,72,d₃ 부호

예제 2.15: H(36)

36,18,12₃ 자기 쌍대 부호 (GF(3))
(36,18,18;1,d)₅ 자기 쌍대 합성곱 부호 (GF(5))
양자 오류 정정 부호: 길이 36, 거리 d

결론 및 논의

주요 결론

이론적 기여:
- Hadamard 행렬 기반 부호 구성의 완전한 이론 프레임워크 수립
- 5개의 핵심 명제 증명, 4개의 일반적 알고리즘 제시
- 선형 블록 부호와 합성곱 부호의 구성 방법 통일
구성 능력:
- 임의 부호율의 LCD 부호 구성 가능
- 자기 쌍대, DC, 양자 오류 정정 부호 구성 가능
- 단일 Hadamard 행렬로부터 다양한 유형의 부호 획득
성능 우위:
- 합성곱 부호 거리는 선형 블록 부호의 2배 달성 가능
- 3진 부호는 소규모 길이에서 극값 성질 달성
- 대규모 길이, 고부호율 실현 가능

한계

체의 제약:
- 대부분의 구성은 p∤n 요구
- 자기 쌍대 합성곱 부호는 √(-1) 존재 필요
- 일부 구성은 체 확장 필요
거리 계산:
- 대규모 길이의 경우 거리 정확 계산 어려움
- 대수적 방법 및 컴퓨터 검증에 의존
- 일부 경우 추정만 가능
Hadamard 행렬 의존성:
- Hadamard 행렬의 명시적 표현 사전 필요
- 비분해 가능 Hadamard 행렬이 성능 우수하나 구성 어려움
- Hadamard 추측 미해결로 가용 크기 제한
고메모리 합성곱 부호:
- 논문은 주로 메모리 1 경우에 집중
- 고메모리 경우는 후속 연구로 남겨짐 (예제 2.10만 제시)
실제 응용 검증:
- 실제 통신 시스템에서의 성능 테스트 부재
- 복호 복잡도 분석 불충분

향후 방향

이론 확장:
- 고메모리 합성곱 부호의 체계적 구성
- 기타 직교 행렬의 응용
- 비이진 체 상의 심화 연구
거리 개선:
- 더 정밀한 거리 경계
- Singleton 경계 달성 MDS 부호 구성
- 점근적 성질 분석
응용 확대:
- 실제 통신 시스템 구현
- 양자 컴퓨팅에서의 응용
- 암호학 응용
계산 최적화:
- 효율적 복호 알고리즘
- 병렬 구현
- 하드웨어 친화적 설계

심층 평가

장점

이론적 혁신성 강함:
- Hadamard 행렬을 최초로 체계적으로 다중 유형 부호 구성에 적용
- 합성곱 부호 대수 구성의 장기적 난제 해결
- 단위 유도 방법의 혁신적 응용
방법 통일성 우수:
- 선형 블록 부호와 합성곱 부호 통일 처리
- 다양한 유형 부호 (LCD, 자기 쌍대, DC) 통일 프레임워크
- 이론에서 알고리즘에서 응용까지의 완전한 연쇄
실용 가치 높음:
- 명확한 구성 알고리즘 제시
- 임의 부호율 및 길이 실현 가능
- GAP 시스템으로 용이한 구현
실험 충분:
- 다양한 크기의 Hadamard 행렬
- 다양한 유한체 (GF(3), GF(5), GF(7) 및 확장)
- 상세한 원형 예제 (예제 2.9)
작성 명확:
- 구조 계층 분명
- 정의, 명제, 알고리즘, 응용의 논리 명확
- 수학적 유도 엄밀

부족점

이론 완비성:
- p|n 경우의 처리 체계 부족
- 고메모리 합성곱 부호 이론 불완전
- 일부 명제의 증명 과도히 간략 (예: 명제 2.3의 거리 증명)
실험 한계:
- 기존 최적 부호와의 체계적 비교 부재
- 거리 계산 주로 컴퓨터 의존 (길이 ≤100)
- 복호 성능 실험 부재
응용 지도 부족:
- 적절한 Hadamard 행렬 선택 방법?
- 다양한 응용 시나리오에서의 매개변수 선택 전략?
- 복호 복잡도 분석 부재
재현성:
- 코드 또는 구체적 구현 미제공
- 일부 Hadamard 행렬의 구성 미설명
- GAP 구현 세부사항 부족
비교 분석:
- Walsh-Hadamard 부호와의 상세 비교 부족
- 기타 대수적 구성 방법과의 대비 부재
- 성능-복잡도 트레이드오프 분석 부족

영향력

학술 기여:
- 부호 이론에 새로운 구성 도구 제공
- Hadamard 행렬의 부호 응용 추진
- 후속 계열 연구 유발 가능성
실용 가치:
- 양자 오류 정정 부호 구성의 실제 응용 잠재력
- LCD 부호의 보안 분야 응용 가치
- 현대 통신의 대규모 길이 부호 구성 수요 충족
재현성:
- 이론 방법 명확하고 재현 가능
- GAP 시스템 지원 필요
- 구체적 구현에 일정 작업량 필요
한계:
- Hadamard 행렬 존재성에 의존
- 일부 구성은 체 확장 필요
- 실제 시스템 응용 추가 검증 필요

적용 시나리오

이론 연구:
- 부호 이론의 대수적 구성 방법 연구
- Hadamard 행렬의 응용 연구
- 양자 정보 이론
실제 응용:
- 양자 통신: 양자 오류 정정 부호 구성
- 보안 통신: LCD 부호로 측면 채널 공격 방어
- 데이터 저장: 고부호율 오류 정정 부호
- 무선 통신: 합성곱 부호 응용
교육 용도:
- 부호 이론 과정의 사례
- 부호에서의 대수적 방법 응용 예시
- Hadamard 행렬의 응용 교육
부적용 시나리오:
- 극도로 높은 부호율 (>0.9) 필요 응용
- 복호 복잡도에 극도로 민감한 경우
- 연판정 복호 필요 응용

참고문헌 (주요 문헌)

3 McEliece: 정보 및 부호 이론 고전 교과서, 합성곱 부호 대수 구성 부재 문제 지적
6 Horadam: Hadamard 행렬 및 그 응용의 권위 있는 전문서
13,14 Calderbank & Shor: CSS 양자 오류 정정 부호 구성의 개척적 연구
27 Hurley: 본 논문의 이론적 기초, 최종 선형 블록 및 합성곱 부호
31 Massey: LCD 부호의 개척적 연구
35,38 Rosenthal 등: MDS 합성곱 부호의 중요 연구

종합 평가: 이는 이론적 혁신성이 강하고 방법이 체계적으로 완전한 우수 논문이다. 저자는 Hadamard 행렬과 단위 유도 방법을 성공적으로 결합하여 다중 유형 부호 구성의 통일 프레임워크를 수립했으며, 특히 합성곱 부호 대수 구성의 난제를 해결했다. 논문의 주요 가치는 이론에서 알고리즘에서 응용까지의 완전한 방법론을 제공하는 데 있으며, 학술적 의의와 응용 잠재력이 상당하다. 주요 부족점은 고메모리 합성곱 부호 이론의 불완전성과 실제 응용 검증 부족이다. 후속 연구에서 실제 시스템 구현 및 성능 테스트를 강화할 것을 권장한다.