선형 부호

컴퓨터 과학과 조합론에서 선형 부호(線型せんけい符號ふごう, 영어: linear code 리니어 코드^[*])는 알파벳이 유한체이며, 부호화 함수가 유한체 위의 선형 변환인 블록 부호이다. 그 속의 벡터들 사이의 해밍 거리가 큰 선형 부호를 사용하면, 노이즈가 있는 채널을 통해 전송된 데이터의 일부 오류를 교정할 수 있다.

정의

두 자연수 $n,k\in \mathbb {N}$ 및 소수의 (양의 정수 지수) 거듭제곱 $q\in \{2,3,4,5,7,8,9,11,\dotsc \}$ 가 주어졌다고 하자.

길이 $n$ 의 $k$ 차원 $q$ 진 선형 부호(- $k$ 次元じげん $q$ 進すすむ線型せんけい符號ふごう, 영어: $k$ -dimensional $q$ -ary linear code with length $n$ )는 유한체 $\mathbb {F} _{q}$ 위의 $n$ 차원 벡터 공간 $\mathbb {F} _{q}^{n}$ 속의 $k$ 차원 $\mathbb {F} _{q}$ -부분 벡터 공간

C\subseteq \mathbb {F} _{q}^{n}

이다. 이는 블록 부호

C\colon \mathbb {F} _{q}^{k}\to \mathbb {F} _{q}^{n}

으로 생각할 수 있다.

선형 부호 $C$ 의 원소는 부호어(符號ふごう語ご, 영어: codeword)라고 한다. $C$ 위에 해밍 거리를 부여하면, 이는 거리 공간을 이룬다. 해밍 거리를 $\operatorname {d_{H}} (-,-)$ 로 표기하자.

선형 부호 $C$ 의 최소 거리(最小さいしょう距離きょり, 영어: minimum distance) $d$ 는 그 부호어 가운데 0이 아닌 것의 최소 해밍 무게이다. 이는 $C$ 의 서로 다른 두 원소 사이의 거리의 최솟값과 같다.

구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle d=\min_{c\in C}\operatorname{d_H}(c,0)=\min_{c,c'\in C,\;c\ne c'}\operatorname{d_H}(c,c')}

흔히, 최소 거리 $d$ 의, 길이 $n$ 의. $k$ 차원 $q$ 진 선형 부호를 $[n,k,d]_{q}$ -선형 부호라고 표기한다. ( $q=2$ 인 경우 $q$ 가 흔히 생략된다.)

생성 행렬과 패리티 확인 행렬

$[n,k,d]_{q}$ -선형 부호 $C\subseteq \mathbb {F} _{q}^{n}$ 의 생성 행렬(生成せいせい行列ぎょうれつ, 영어: generator matrix)은 $C$ 를 선형 생성하는 $k$ 개의 열벡터들로 구성된 $n\times k$ 행렬이며, 흔히 $G$ 로 표기된다.

$[n,k,d]_{q}$ -선형 부호 $C\subseteq \mathbb {F} _{q}^{n}$ 의 패리티 확인 행렬(영어: parity check matrix)은

C=\ker H

가 되는 $n-k\times n$ 행렬이다. 다시 말해, $H$ 의 열벡터들은 $C^{\perp }$ 를 선형 생성한다. 이는 흔히 $H$ 로 표기된다.

만약 $H$ 가

H=(B_{n-k\times k}|1_{n-k\times n-k})

의 꼴이라면, $H$ 를 표준형 패리티 확인 행렬(標準ひょうじゅん型がたparity確認かくにん行列ぎょうれつ, 영어: standard-form parity check matrix)이라고 한다. 임의의 선형 부호에 대하여, 표준형 패리티 확인 행렬이 존재한다.

연산

선형 부호

C\subseteq \mathbb {F} _{q}^{n}

의 직교 여공간

C^{\perp }=\{v\in \mathbb {F} _{q}^{n}\colon \langle u,v\rangle =0\qquad \forall u\in C\}

을 $C$ 의 쌍대 선형 부호(雙對そうつい線型せんけい符號ふごう, 영어: dual linear code)라고 한다. 만약 $C$ 가 $[n,k,d]_{q}$ -선형 부호라면, $C^{\perp }$ 은 $[n,n-k,d']_{q}$ -선형 부호이다. 일반적으로 $d'$ 은 $(n,k,d,q)$ 로부터 결정되지 않는다.

예:

\operatorname {Span} _{\mathbb {F} _{2}}\{(1,0,0),(0,1,0)\}

\operatorname {Span} _{\mathbb {F} _{2}}\{(1,0,0),(0,1,1)\}

은 둘 다 [3,2,1]₂-선형 부호이지만, 그 쌍대 선형 부호

(\operatorname {Span} _{\mathbb {F} _{2}}\{(1,0,0),(0,1,0)\})^{\perp }=\operatorname {Span} _{\mathbb {F} _{2}}\{(0,0,1)\}

(\operatorname {Span} _{\mathbb {F} _{2}}\{(1,0,0),(0,1,1)\})^{\perp }=\operatorname {Span} _{\mathbb {F} _{2}}\{(0,1,1)\}

는 각각 [3,1,1]₂-선형 부호 및 [3,1,2]₂-선형 부호이다.

예

자명한 부호

임의의 소수 거듭제곱 $q$ 및 두 양의 정수 $1\leq k\leq n$ 에 대하여, 자명한 선형 부호

C=\{(a_{1},a_{2},\dotsc ,a_{k},0,0,\dotsc ,0)\}\subseteq \mathbb {F} _{q}^{n}

를 정의할 수 있다. 이는 $[n,k,1]_{q}$ -선형 부호이다. 즉, 이 자명한 선형 부호는 각 부호어마다

0개의 오류를 교정할 수 있으며,
0개의 오류를 발견할 수 있다.

다시 말해, 이 자명한 부호는 실제 데이터의 송신에는 쓸모가 없다.

해밍 부호

임의의 2 이상의 정수 $r$ 에 대하여, $r$ -이진 해밍 부호는 $[2^{r}-1,2^{r}-r-1,3]_{2}$ -선형 부호이다. 예를 들어, $r=2$ 일 때 2-이진 해밍 부호는 [3,1,3]₂-선형 부호이며, 3-이진 해밍 부호는 [7,4,3]₂-선형 부호이다.

최소 해밍 무게가 3이므로, 이진 해밍 부호는 각 부호어마다

1개 이하의 오류를 교정할 수 있으며,
2개 이하의 오류를 발견할 수 있다.

2-이진 해밍 부호는 최대 거리 분리 선형 부호이지만, $r\geq 3$ 일 경우 $r$ -이진 해밍 부호는 최대 거리 분리 선형 부호가 아니다.

아다마르 부호

정수 $r$ 에 대하여, 아다마르 부호(영어: Hadamard code)는 $[2^{r},r,2^{r-1}]_{2}$ -선형 부호이다. 예를 들어, $r=1$ 일 때 1-아다마르 부호는 [2,1,1]₂-선형 부호이며, 2-아다마르 부호는 [4,2,2]₂-선형 부호이며, 3-아다마르 부호는 [8,2,4]₂-선형 부호이다.

골레 부호

이진 골레 부호는 [24,12,8]₂-선형 부호이며, 삼진 골레 부호는 [12,6,6]₃-선형 부호이다. 이들은 마티외 군의 군론적 성질을 사용하여 구성된다.

데이터 전송

데이터

p={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}

를 $r=3$ 이진 해밍 부호로 전송한다고 하자. $r=3$ 이진 해밍 부호의 생성 행렬과 표준형 패리티 확인 행렬은 각각 다음과 같다.

G={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0&1&1&1\\1&0&1&1\\1&1&0&1\\\end{pmatrix}}

H={\begin{pmatrix}0&1&1&1&1&0&0\\1&0&1&1&0&1&0\\1&1&0&1&0&0&1\\\end{pmatrix}}

그렇다면, 다음과 같은 부호를 송신하게 된다.

x=Gp={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0&1&1&1\\1&0&1&1\\1&1&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\\0\\1\\0\end{pmatrix}}

오류 없음의 확인

반대로, 위 데이터

x={\begin{pmatrix}1\\0\\1\\1\\0\\1\\0\end{pmatrix}}

를 수신하였다고 하자. 이 데이터가 오류 없이 수신되었음을 확인하려면, 패리티 확인 행렬을 사용하여 다음을 계산한다.

Hx={\begin{pmatrix}0&1&1&1&1&0&0\\1&0&1&1&0&1&0\\1&1&0&1&0&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\\0\\1\\0\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}

이 값이 0이므로 오류가 발생하지 않았음을 알 수 있다.

오류의 교정

전송 과정에서 다음과 같은 1비트 오류가 발생했다고 하자.

r={\begin{pmatrix}1\\1\\1\\1\\0\\1\\0\end{pmatrix}}

그렇다면, 다음과 같이 오류를 발견할 수 있다.

Hr={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\1\\1\\1\\0\\1\\0\end{pmatrix}}={\begin{pmatrix}0\\1\\0\end{pmatrix}}

이에 따라, 둘째 비트에서 오류가 발생하였음을 알 수 있다.

역사

선형 부호 이론은 1950년에 해밍 부호의 발견으로부터 시작된다. 해밍은 1940년대 벨 연구소에서 벨 모델 V(영어: Bell Model V)라는 컴퓨터를 이용해서 작업을 했다. 이 컴퓨터는 확실히 여러 면에서 오늘날의 컴퓨터와는 거리가 멀었다. 릴레이 회로로 만들어졌으며 입력도 천공 카드를 이용했다. 천공 카드를 이용했으므로 컴퓨터에 입력되는 자료들은 필연적으로 언제나 오류의 가능성이 있었다. 주중에는 컴퓨터의 관리자가 있으면서 입력에 오류가 발생했다는 경고등이 켜지면 직접 수정할 수 있었으나, 관리자가 없는 주말에는 에러가 발생한 채 프로그램이 실행되지 않고 다음 작업으로 넘어가기 일쑤였다.

해밍은 이런 문제로 인해 여러 차례 고생을 한 후에, 이 문제를 근본적으로 해결하기 위해 노력했다. 그 후 몇 년 동안 오류를 수정하는 방법에 대해서 연구하면서 이와 관련된 여러가지의 효율적인 알고리즘을 만들어냈고 마침내 1950년에 해밍 부호를 발표했다.^[1]

이진 골레 부호는 마르셀 골레(프랑스어: Marcel Jules Édouard Golay)가 도입하였다. 아다마르 부호는 자크 아다마르의 이름을 땄으며, 그 구성에 아다마르 행렬이 등장하므로 이러한 이름이 붙었다.

각주

↑ Hamming, Richard W. (1950년 4월). “Error detecting and error correcting codes”. 《Bell Labs Technical Journal》 (영어) 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. ISSN 1089-7089.

van Lint, Jack H. (1992). 《Introduction to coding theory》. Graduate Texts in Mathematics (영어) 86 2판. Springer-Verlag. doi:10.1007/978-3-642-58575-3. ISBN 978-3-540-64133-9. ISSN 0072-5285.
Vermani, L. R. (1996). 《Elements of algebraic coding theory》. Chapman Hall/CRC Mathematics Series (영어). Chapman & Hall Mathematics. ISBN 978-041257380-4.

외부 링크

“Linear code”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Linear code”. 《Wolfram MathWorld》 (영어). Wolfram Research.
“Linear code”. 《nLab》 (영어).
“Binary linear code”. 《nLab》 (영어).
성현경 (2015). “정보 및 부호이론”. 상지대학교 컴퓨터정보공학부.

[1] Hamming, Richard W. (1950년 4월). “Error detecting and error correcting codes”. 《Bell Labs Technical Journal》 (영어) 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. ISSN 1089-7089.

[1]