정의
선형 부호(Linear code)란, 유한체 GF(q) 위의 n 차원 벡터 공간 V = GF(q)ⁿ에서 k 차원 부분공간 C ⊆ V 로 정의되는 오류 정정 부호이다. 즉, 모든 코드워드가 선형 결합에 대해 닫혀 있는 부호 집합으로, 일반적으로 (n, k, d) 부호라 표기한다. 여기서 n은 코드워드의 길이, k는 정보 심볼의 개수, d는 최소 해밍 거리이다.
개요
선형 부호는 통신 및 저장 시스템에서 전송 중 발생할 수 있는 오류를 검출하고 교정하기 위해 사용된다.
- 파라미터: (n, k, d) 형태로 나타내며, 전송 효율은 k/n, 오류 교정 능력은 ⌊(d‑1)/2⌋ 로 평가된다.
- 표현 방법: 생성 행렬 G (k × n)와 검증 행렬 H (n‑k × n)를 이용해 코드워드를 생성하거나 오류를 검출한다.
- 대표적인 예: 해밍 부호(Hamming code), 리드-솔로몬 부호(Reed–Solomon code), BCH 부호, Golay 부호 등이 있다.
어원/유래
‘선형(linear)’은 선형 대수학에서 벡터 공간의 부분공간이라는 의미를, ‘부호(code)’는 통신 이론에서 정보의 인코딩 방식을 의미한다. 영어 “linear code”를 직역한 용어이며, 20세기 중반 Claude Shannon과 Richard Hamming이 오류 정정 이론을 체계화하면서 학계에 도입되었다.
특징
- 선형성: 두 코드워드의 합(또는 스칼라 배)도 여전히 코드워드가 된다.
- 생성 행렬 G: k개의 독립적인 정보 심볼을 n개의 코드 심볼로 변환하는 매핑을 제공한다.
- 검증 행렬 H: 코드워드가 C에 속하는지를 검증하며, 수신된 워드와의 시그마( syndrome) 계산을 통해 오류 위치를 파악한다.
- 효율적인 디코딩: 시그마 기반 디코딩, 소프트 디시전 디코딩, 베이스스트리트 디코딩 등 다양한 알고리즘이 존재한다.
- 구조적 설계: 사이클릭 부호, 순환 부호 등 특정 대수적 구조를 갖는 경우 구현 및 해석이 용이하다.
관련 항목
- 오류 정정 부호
- 해밍 부호
- 리드-솔로몬 부호
- BCH 부호
- 생성 행렬, 검증 행렬
- 시그마(syndrome) 디코딩
- 유한체(GF(q))
- 통신 이론, 디지털 신호 처리