해밍 부호 문서 원본 보기

{{위키데이터 속성 추적}}
[[선형대수학]]과 [[컴퓨터 과학]]에서 '''해밍 부호'''(해밍符號, {{llang|en|Hamming code|해밍 코드}})는 [[이진 선형 부호]]의 일종이다.<ref>{{서적 인용|이름=David J. C.|성=MacKay|날짜=2003|제목=Information theory, inference and learning algorithms|출판사=Cambridge University Press|isbn=0-521-64298-1|url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html|언어=en}}
</ref> 거리가 3이므로, 1개 이하의 오류를 교정할 수 있으며, 2개 이하의 오류의 존재를 발견할 수 있다.

== 정의 ==
'''해밍 부호'''는 임의의 (소수 거듭제곱) 진법에 대하여 정의되는, 거리 3의 [[선형 부호]]이다. 이 가운데 이진 해밍 부호는 정의하기가 특별히 간단하다.

=== 이진 해밍 부호 ===
다음 데이터가 주어졌다고 하자.
* 2 이상의 정수 <math>r\in\{2,3,4,\dotsc\}</math>
그렇다면, 다음과 같은, <math>\mathbb F_2</math> 계수의 <math>r\times 2^r-1</math> 행렬 <math>H</math>를 정의할 수 있다.
:<math>H_{i,j}=j_i\qquad(1\le i\le r,\quad j= j_r+2j_{r-1}+4j_{r-2}+8j_4+\dotsb+2^{r-1}j_1,\quad j_1,\dotsc,j_r\in \{0,1\})</math>
즉, <math>H</math>의 <math>j</math>번째 열의 성분들은 <math>j</math>의 [[이진법]] 표기의 성분들이다. 예를 들어, <math>r=3</math>일 때 <math>H</math>는 다음과 같은 3×7 행렬이다.
:<math>H
=\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}</math>
이제, <math>H</math>를 [[패리티 확인 행렬]]로 갖는 [[이진 선형 부호]]
:<math>C=\ker H</math>
를 <math>r</math>-'''이진 해밍 부호''' 또는 <math>[2^r-1,2^r-1-r,3]_2</math>-'''해밍 부호'''라고 한다.

=== 임의의 진법의 해밍 부호 ===
보다 일반적으로, 다음이 주어졌다고 하자.
* [[소수 (수론)|소수]] 거듭제곱 <math>q\in\{2,3,4,5,7,8,9,11,\dotsc\}</math>
* 2 이상의 정수 <math>r\in\{2,3,4,\dotsc\}</math>
그렇다면, [[유한체]] <math>\mathbb F_q</math> 위의 <math>r</math>차원 [[벡터 공간]] <math>\mathbb F_q^r</math> 및 <math>r-1</math>차원 [[사영 공간]]
:<math>\mathbb P^{r-1}_{\mathbb F_q}=\frac{\mathbb F_q^r\setminus\{\vec 0\}}{u\sim v\iff\exists\lambda\in\mathbb F_q^\times\colon u=\lambda v}</math>
을 구성할 수 있다. 다시 말해, 사영화 몫 함수
:<math>\mathbb F_q^r\setminus\{\vec 0\}\twoheadrightarrow \mathbb P^{r-1}_{\mathbb F_q}</math>
는 집합 <math>\mathbb F_q^r\setminus\{\vec 0\}</math> 위에 [[동치 관계]]를 정의하며, 그 [[동치류]]의 수는 다음과 같다.
:<math>\frac{|\mathbb F_q^r\setminus\{\vec 0\}|}{|\mathbb F_q^\times|}
=
\frac{q^r-1}{q-1}
</math>
이제, 각 동치류에서 임의의 대표원을 고를 수 있으며, 이 대표원들을 열벡터로 삼아 <math>\mathbb F_q</math> 성분의 <math>r\times(q^r-1)/(q-1)</math> [[행렬]]
:<math>H\in\operatorname{Mat}(r,(q^r-1)/(q-1);\mathbb F_q)</math>
을 구성할 수 있다. 이 행렬을 [[패리티 확인 행렬]]로 갖는 [[선형 부호]]
:<math>C=\ker H\subseteq \mathbb F_q^{(q^r-1)/(q-1)}</math>
를 '''<math>q</math>진 <math>r</math>-해밍 부호'''라고 한다.

=== 확장 해밍 부호 ===
다른 모든 [[선형 부호]]와 마찬가지로,
해밍 부호에 모든 성분에 대응되는 (즉 일반적인) 패리티 성분을 하나 더 추가할 수 있으며, 이는 <math>[2^r,2^r-r-1,4]</math>-선형 부호이다. 이를 '''확장 해밍 부호'''(擴張Hamming符號, {{llang|en|extended Hamming code}})라고 한다.

== 성질 ==
해밍 부호의 거리는 3이다. 즉, 일반적으로, 소수 거듭제곱 <math>q</math> 및 양의 정수 <math>r</math>가 주어졌을 때, <math>q</math>진 <math>r</math>-해밍 부호는 <math>[(q^r-1)/(q-1),(q^r-1)/(q-1)-r,3]_q</math>-[[선형 부호]]이다. 특히, 거리가 3이므로, 해밍 부호는 각 부호어마다
* 1개 이하의 오류를 교정할 수 있으며,
* 2개 이하의 오류의 존재를 발견할 수 있다. (다만, 2개의 오류가 발생한 것을 1개의 오류가 발생한 것과 구별할 수 있지는 않다. 즉, 2개의 오류가 발생하였을 때, 데이터가 잘못 복구될 수 있다.)

=== 가짓수 ===
[[소수 (수론)|소수]] 거듭제곱 <math>q</math>에 대하여, <math>q</math>진 해밍 부호를 구성하려면 [[동치류]]의 대표원을 임의로 골라야 한다. 각 동치류의 [[집합의 크기|크기]]는 <math>q-1</math>이므로, (행의 [[순열]]을 무시하면) <math>q</math>진 <math>r</math>-해밍 부호의 가능한 [[패리티 확인 행렬]]의 수는
:<math>(q-1)^{(q^r-1)/(q-1)}</math>
이다. 물론, 서로 다른 [[패리티 확인 행렬]]이 같은 [[선형 부호]]를 정의할 수 있다.

<math>q=2</math>일 경우, 각 [[동치류]]가 [[한원소 집합]]이므로 해밍 부호는 유일하며, 대표원을 임의로 고를 필요가 없다. 그러나 예를 들어 <math>q=3</math>일 경우, <math>2^{(3^r-1)/2}</math>개의 서로 다른 3진 <math>r</math>-해밍 부호가 존재한다.

=== 최적성 ===
<math>[2^r-1,2^r-1-r,3]_2</math>-해밍 부호는 같은 길이 및 거리의 [[선형 부호]] 가운데, 가장 효율적이다. 즉, 임의의 <math>[2^r-1,k,3]_2</math>-[[선형 부호]]에 대하여,
:<math>k\le 2^r-1-r</math>
이다.

== 예 ==
=== 이진 2-해밍 부호 ===
<math>r=2</math> 이진 해밍 부호는 '''삼중 반복 부호'''(三重反復符號, {{llang|en|triple repetition code}})와 같다. 즉, 이는 다음과 같다.
* 송신할 때, 같은 비트를 세 번 반복하여 보낸다.
* 수신할 때,
** 만약 세 비트가 모두 같다면, 오류가 없음을 알 수 있다.
** 만약 세 비트 가운데 하나가 다르다면, 이를 다른 두 비트와 같게 교정할 수 있다.
생성 행렬과 표준형 [[패리티 확인 행렬]]은 다음과 같다.
:<math>G=\begin{pmatrix}
1\\
1\\
1
\end{pmatrix}</math>
:<math>H=\begin{pmatrix}
1&1&0\\
1&0&1
\end{pmatrix}</math>

=== 이진 3-해밍 부호 ===
가장 흔히 사용되는 해밍 부호는 <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>

=== 삼진 2-해밍 부호 ===
<math>\mathbb F_3</math> 위의 [[사영 직선]] <math>\mathbb P^1_{\mathbb F_3}</math>을 구성하는 <math>\mathbb F_3^2\setminus\{\vec0\}</math>의 동치류들은 다음과 같다.
:<math>\{(0,1), (0,2)\}</math>
:<math>\{(1,0), (2,0)\}</math>
:<math>\{(1,1), (2,2)\}</math>
:<math>\{(1,2), (2,1)\}</math>
이에 따라, 예를 들어 첫째 대표원들을 고르면, 삼진 2-해밍 부호의 표준형 [[패리티 확인 행렬]]은 다음과 같다.
:<math>H=\begin{pmatrix}
1&1&1&0\\
1&2&0&1
\end{pmatrix}</math>
그 표준형 생성 행렬은 다음과 같다.
:<math>G=\begin{pmatrix}
1&0\\
0&1\\
2&2\\
2&1
\end{pmatrix}</math>

== 역사 ==
[[리처드 해밍]]이 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>
1940년대 [[벨 연구소]]에서 벨 모델 V({{llang|en|Bell Model V}})라는 [[컴퓨터]]를 이용해서 작업을 했다. 이 컴퓨터는 확실히 여러 면에서 오늘날의 컴퓨터와는 거리가 멀었다. 릴레이 회로로 만들어졌으며 입력도 [[천공 카드]]를 이용했다. 천공 카드를 이용했으므로 컴퓨터에 입력되는 자료들은 필연적으로 언제나 오류의 가능성이 있었다. 주중에는 컴퓨터의 관리자가 있으면서 입력에 오류가 발생했다는 경고등이 켜지면 직접 수정할 수 있었으나, 관리자가 없는 주말에는 에러가 발생한 채 프로그램이 실행되지 않고 다음 작업으로 넘어가기 일쑤였다. 해밍은 이런 문제로 인해 여러 차례 고생을 한 후에, 이 문제를 근본적으로 해결하기 위해 노력했다. 그 후 몇 년 동안 오류를 수정하는 방법에 대해서 연구하면서 이와 관련된 여러가지의 효율적인 알고리즘을 만들어냈고 마침내 1950년에 해밍 부호를 발표했다. 이는 [[선형 부호]] 이론의 시초로 여겨진다.

해밍 부호, 특히 <math>r=3</math> 이진 해밍 부호는 오늘날에도 널리 사용되고 있다.

== 같이 보기 ==
* [[부호 이론]]
* [[해밍 거리]]
* [[리드 솔로몬 부호]]
== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=HammingCode|title=Hamming code}}
* {{수학노트|title=해밍코드(Hamming codes)}}
* {{웹 인용|url=http://www.ktword.co.kr/abbr_view.php?m_temp1=1212|제목=해밍 코드, 해밍 부호|웹사이트=정보통신기술용어해설|저자=차재복|날짜=2013-01-07|언어=ko}}

[[분류:미국의 발명품]]
[[분류:부호 이론]]
[[분류:오류 검출 정정]]
[[분류:컴퓨터 산술]]
[[분류:1951년 컴퓨팅]]