선형 부호 문서 원본 보기

{{위키데이터 속성 추적}}
[[컴퓨터 과학]]과 [[조합론]]에서 '''선형 부호'''(線型符號, {{llang|en|linear code|리니어 코드}})는 알파벳이 [[유한체]]이며, 부호화 함수가 [[유한체]] 위의 [[선형 변환]]인 [[블록 부호]]이다. 그 속의 벡터들 사이의 [[해밍 거리]]가 큰 선형 부호를 사용하면, 노이즈가 있는 채널을 통해 전송된 데이터의 일부 오류를 교정할 수 있다.

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

'''길이 <math>n</math>의 <math>k</math>차원 <math>q</math>진 선형 부호'''(-<math>k</math>次元<math>q</math>進線型符號, {{llang|en|<math>k</math>-dimensional <math>q</math>-ary linear code with length <math>n</math>}})는 [[유한체]] <math>\mathbb F_q</math> 위의 <math>n</math>차원 [[벡터 공간]] <math>\mathbb F_q^n</math> 속의 <math>k</math>차원 <math>\mathbb F_q</math>-부분 벡터 공간
:<math>C\subseteq\mathbb F_q^n</math>
이다. 이는 [[블록 부호]]
:<math>C\colon\mathbb F_q^k\to\mathbb F_q^n</math>
으로 생각할 수 있다.

선형 부호 <math>C</math>의 원소는 '''부호어'''(符號語, {{llang|en|codeword}})라고 한다. <math>C</math> 위에 [[해밍 거리]]를 부여하면, 이는 [[거리 공간]]을 이룬다. 해밍 거리를 <math>\operatorname{d_H}(-,-)</math>로 표기하자.

선형 부호 <math>C</math>의 '''최소 거리'''(最小距離, {{llang|en|minimum distance}}) <math>d</math>는 그 부호어 가운데 0이 아닌 것의 최소 [[해밍 무게]]이다. 이는 <math>C</math>의 서로 다른 두 원소 사이의 거리의 최솟값과 같다.
:<math>d=\min_{c\in C}\operatorname{d_H}(c,0)=\min_{c,c'\in C,\;c\ne c'}\operatorname{d_H}(c,c')</math>

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

=== 생성 행렬과 패리티 확인 행렬 ===
<math>[n,k,d]_q</math>-선형 부호 <math>C\subseteq\mathbb F_q^n</math>의 '''생성 행렬'''(生成行列, {{llang|en|generator matrix}})은 <math>C</math>를 선형 생성하는 <math>k</math>개의 열벡터들로 구성된 <math>n\times k</math> 행렬이며, 흔히 <math>G</math>로 표기된다.

<math>[n,k,d]_q</math>-선형 부호 <math>C\subseteq\mathbb F_q^n</math>의 '''패리티 확인 행렬'''({{llang|en|parity check matrix}})은
:<math>C=\ker H</math>
가 되는 <math>n-k\times n</math> 행렬이다. 다시 말해, <math>H</math>의 열벡터들은 <math>C^\perp</math>를 선형 생성한다. 이는 흔히 <math>H</math>로 표기된다.

만약 <math>H</math>가
:<math>H=(B_{n-k\times k}|1_{n-k\times n-k})</math>
의 꼴이라면, <math>H</math>를 '''표준형 패리티 확인 행렬'''(標準型parity確認行列, {{llang|en|standard-form parity check matrix}})이라고 한다. 임의의 선형 부호에 대하여, 표준형 패리티 확인 행렬이 존재한다.

== 연산 ==
선형 부호
:<math>C\subseteq\mathbb F_q^n</math>
의 [[직교 여공간]]
:<math>C^\perp
=\{v\in \mathbb F_q^n\colon \langle u,v\rangle=0\qquad\forall u\in C\}
</math>
을 <math>C</math>의 '''쌍대 선형 부호'''(雙對線型符號, {{llang|en|dual linear code}})라고 한다. 만약 <math>C</math>가 <math>[n,k,d]_q</math>-선형 부호라면, <math>C^\perp</math>은 <math>[n,n-k,d']_q</math>-선형 부호이다. 일반적으로 <math>d'</math>은 <math>(n,k,d,q)</math>로부터 결정되지 않는다.
<div class="mw-collapsible mw-collapsed toccolours">
'''예:'''
<div class="mw-collapsible-content">
:<math>\operatorname{Span}_{\mathbb F_2}\{(1,0,0),(0,1,0)\}</math>
:<math>\operatorname{Span}_{\mathbb F_2}\{(1,0,0),(0,1,1)\}</math>
은 둘 다 [3,2,1]<sub>2</sub>-선형 부호이지만, 그 쌍대 선형 부호
:<math>(\operatorname{Span}_{\mathbb F_2}\{(1,0,0),(0,1,0)\})^\perp=\operatorname{Span}_{\mathbb F_2}\{(0,0,1)\}</math>
:<math>(\operatorname{Span}_{\mathbb F_2}\{(1,0,0),(0,1,1)\})^\perp=\operatorname{Span}_{\mathbb F_2}\{(0,1,1)\}</math>
는 각각 [3,1,1]<sub>2</sub>-선형 부호 및 [3,1,2]<sub>2</sub>-선형 부호이다.
</div></div>

== 예 ==
=== 자명한 부호 ===
임의의 [[소수 (수론)|소수]] 거듭제곱 <math>q</math> 및 두 양의 정수 <math>1\le k\le n</math>에 대하여, 자명한 선형 부호
:<math>C=\{
(a_1,a_2,\dotsc,a_k,0,0,\dotsc,0)\}\subseteq\mathbb F_q^n</math>
를 정의할 수 있다. 이는 <math>[n,k,1]_q</math>-선형 부호이다. 즉, 이 자명한 선형 부호는 각 부호어마다
* 0개의 오류를 교정할 수 있으며,
* 0개의 오류를 발견할 수 있다.
다시 말해, 이 자명한 부호는 실제 데이터의 송신에는 쓸모가 없다.

=== 해밍 부호 ===
{{본문|해밍 부호}}
임의의 2 이상의 정수 <math>r</math>에 대하여, <math>r</math>-'''[[이진 해밍 부호]]'''는 <math>[2^r-1,2^r-r-1,3]_2</math>-선형 부호이다. 예를 들어, <math>r=2</math>일 때 2-[[이진 해밍 부호]]는 [3,1,3]<sub>2</sub>-선형 부호이며, 3-[[이진 해밍 부호]]는 [7,4,3]<sub>2</sub>-선형 부호이다.

최소 [[해밍 무게]]가 3이므로, [[이진 해밍 부호]]는 각 부호어마다
* 1개 이하의 오류를 교정할 수 있으며,
* 2개 이하의 오류를 발견할 수 있다.

2-[[이진 해밍 부호]]는 최대 거리 분리 선형 부호이지만, <math>r\ge3</math>일 경우 <math>r</math>-[[이진 해밍 부호]]는 최대 거리 분리 선형 부호가 아니다.

=== 아다마르 부호 ===
정수 <math>r</math>에 대하여, '''아다마르 부호'''({{llang|en|Hadamard code}})는 <math>[2^r,r,2^{r-1}]_2</math>-선형 부호이다. 예를 들어, <math>r=1</math>일 때 1-아다마르 부호는 [2,1,1]<sub>2</sub>-선형 부호이며, 2-아다마르 부호는 [4,2,2]<sub>2</sub>-선형 부호이며, 3-아다마르 부호는 [8,2,4]<sub>2</sub>-선형 부호이다.

=== 골레 부호 ===
{{본문|이진 골레 부호}}
{{본문|삼진 골레 부호}}
'''[[이진 골레 부호]]'''는 [24,12,8]<sub>2</sub>-선형 부호이며, '''[[삼진 골레 부호]]'''는 [12,6,6]<sub>3</sub>-선형 부호이다. 이들은 [[마티외 군]]의 군론적 성질을 사용하여 구성된다.

=== 데이터 전송 ===
데이터
:<math> p=\begin{pmatrix}1\\0\\1\\1\end{pmatrix}</math>
를 <math>r=3</math> [[이진 해밍 부호]]로 전송한다고 하자. <math>r=3</math> 이진 해밍 부호의 생성 행렬과 표준형 패리티 확인 행렬은 각각 다음과 같다.
: <math>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}</math>
:<math>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}</math>

그렇다면, 다음과 같은 부호를 송신하게 된다.
: <math>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}</math>

==== 오류 없음의 확인 ====
반대로, 위 데이터
:<math>x=\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}</math>
를 수신하였다고 하자. 이 데이터가 오류 없이 수신되었음을 확인하려면, 패리티 확인 행렬을 사용하여 다음을 계산한다.
:<math>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}</math>
이 값이 0이므로 오류가 발생하지 않았음을 알 수 있다.

==== 오류의 교정 ====
전송 과정에서 다음과 같은 1비트 오류가 발생했다고 하자.
: <math>r=\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}</math>
그렇다면, 다음과 같이 오류를 발견할 수 있다.
: <math>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}</math>
이에 따라, 둘째 비트에서 오류가 발생하였음을 알 수 있다.

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

해밍은 이런 문제로 인해 여러 차례 고생을 한 후에, 이 문제를 근본적으로 해결하기 위해 노력했다. 그 후 몇 년 동안 오류를 수정하는 방법에 대해서 연구하면서 이와 관련된 여러가지의 효율적인 알고리즘을 만들어냈고 마침내 1950년에 [[해밍 부호]]를 발표했다.<ref>{{저널 인용|제목=Error detecting and error correcting codes|이름=Richard W.|성=Hamming|저자링크=리처드 해밍|doi=10.1002/j.1538-7305.1950.tb00463.x|날짜=1950-04|저널=Bell Labs Technical Journal|권=29|호=2|쪽=147–160|issn=1089-7089|언어=en}}</ref>

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

== 각주 ==
{{각주}}
* {{서적 인용 | 이름=Jack H. |성=van Lint | title=Introduction to coding theory | 판=2 | 출판사=Springer-Verlag | series=Graduate Texts in Mathematics | issn=0072-5285 | volume=86 | date=1992 | isbn= 978-3-540-64133-9 | doi= 10.1007/978-3-642-58575-3 |  언어=en }}
* {{서적 인용|제목=Elements of algebraic coding theory|이름=L. R.|성=Vermani|url=https://www.crcpress.com/Elements-of-Algebraic-Coding-Theory/Vermani/p/book/9780412573804|날짜=1996|총서=Chapman Hall/CRC Mathematics Series|출판사=Chapman & Hall Mathematics|isbn=978-041257380-4|언어=en}}

== 외부 링크 ==
* {{eom|title=Linear code}}
* {{매스월드|id=LinearCode|title=Linear code}}
* {{nlab|id=linear code|title=Linear code}}
* {{nlab|id=binary linear code|title=Binary linear code}}
* {{웹 인용|url=http://ctl.sangji.ac.kr/common/downLoad.action?siteId=com&fileSeq=12777316|제목=정보 및 부호이론|날짜=2015|출판사=상지대학교 컴퓨터정보공학부|저자=성현경|언어=ko}}

[[분류:부호 이론]]
[[분류:선형대수학]]
[[분류:유한체]]