정의
선형 부호(線型符號, 영어: linear code)는 컴퓨터 과학과 조합론에서 다루는 개념으로, 알파벳이 유한체(finite field)이며 부호화 함수가 유한체 위의 선형 변환인 블록 부호(block code)를 말한다. 즉, 선형 부호는 유한체 $\mathbb{F}_q$ 위의 $n$차원 벡터 공간 $\mathbb{F}_q^n$ 속의 $k$차원 부분 벡터 공간으로 정의된다. 이때 $q$는 소수의 거듭제곱이며, $n$은 부호의 길이, $k$는 차원을 나타낸다.
선형 부호는 보통 $[n, k, d]_q$ 형태로 표기하며, 여기서 $d$는 최소 거리(minimum distance)로, 0이 아닌 부호어(codeword)들 중 가장 작은 해밍 무게(Hamming weight)를 의미한다. $q=2$인 이진 부호의 경우 $q$는 생략되기도 한다.
주요 구성 요소
- 부호어(codeword): 선형 부호 $C$의 원소.
- 생성 행렬(generator matrix): $C$를 선형 생성하는 $k$개의 열벡터로 구성된 $n \times k$ 행렬. 보통 $G$로 표기한다.
- 패리티 확인 행렬(parity check matrix): $C = \ker H$를 만족하는 $(n-k) \times n$ 행렬. 보통 $H$로 표기하며, 수신된 데이터의 오류 검출 및 교정에 사용된다.
- 쌍대 선형 부호(dual linear code): $C$의 직교 여공간 $C^\perp$으로, $[n, n-k, d']_q$ 형태의 선형 부호이다.
성질
선형 부호의 핵심적인 성질은 그 속의 벡터들 사이의 해밍 거리가 클수록, 노이즈가 있는 통신 채널을 통해 전송된 데이터의 오류를 더 많이 교정할 수 있다는 점이다. 선형성을 활용하면 부호화와 복호화 과정을 행렬 연산으로 효율적으로 처리할 수 있으며, 신드롬 복호(syndrome decoding) 등의 기법을 통해 오류를 체계적으로 교정할 수 있다.
주요 예
- 자명한 선형 부호: $[n, k, 1]_q$ 형태로, 오류 교정 능력이 없어 실제 통신에는 사용되지 않는다.
- 해밍 부호(Hamming code): $[2^r - 1, 2^r - r - 1, 3]_2$ 형태의 이진 선형 부호로, 1개 이하의 오류를 교정하고 2개 이하의 오류를 발견할 수 있다. 1950년 리처드 해밍(Richard Hamming)이 발표하였다.
- 아다마르 부호(Hadamard code): $[2^r, r, 2^{r-1}]_2$ 형태의 선형 부호로, 아다마르 행렬을 이용하여 구성된다.
- 골레 부호(Golay code): 이진 골레 부호는 $[24, 12, 8]_2$, 삼진 골레 부호는 $[12, 6, 6]_3$ 형태이다. 마르셀 골레(Marcel Golay)가 도입하였다.
역사
선형 부호 이론은 1950년 리처드 해밍이 해밍 부호를 발표하면서 시작되었다. 해밍은 1940년대 벨 연구소에서 릴레이 회로와 천공 카드를 사용하는 컴퓨터로 작업하던 중, 입력 오류로 인해 프로그램이 중단되는 문제를 해결하기 위해 오류 정정 부호를 연구하였다. 이후 선형 부호 이론은 통신, 데이터 저장, 위성 통신, QR 코드 등 다양한 분야에서 핵심적인 역할을 하고 있다.
