해밍 부호

선형대수학과 컴퓨터 과학에서 해밍 부호(해밍符號, 영어: Hamming code 해밍 코드^[*])는 이진 선형 부호의 일종이다.^[1] 거리가 3이므로, 1개 이하의 오류를 교정할 수 있으며, 2개 이하의 오류의 존재를 발견할 수 있다.

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

다음 데이터가 주어졌다고 하자.

• 2 이상의 정수 ${\displaystyle r\in \{2,3,4,\dotsc \}}$

그렇다면, 다음과 같은, ${\displaystyle \mathbb {F} _{2}}$ 계수의 ${\displaystyle r\times 2^{r}-1}$ 행렬 ${\displaystyle H}$를 정의할 수 있다.

${\displaystyle H_{i,j}=j_{i}\qquad (1\leq i\leq 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\})}$

즉, ${\displaystyle H}$의 ${\displaystyle j}$번째 열의 성분들은 ${\displaystyle j}$의 이진법 표기의 성분들이다. 예를 들어, ${\displaystyle r=3}$일 때 ${\displaystyle H}$는 다음과 같은 3×7 행렬이다.

${\displaystyle 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}}}$

이제, ${\displaystyle H}$를 패리티 확인 행렬로 갖는 이진 선형 부호

${\displaystyle C=\ker H}$

를 ${\displaystyle r}$-이진 해밍 부호 또는 ${\displaystyle [2^{r}-1,2^{r}-1-r,3]_{2}}$-해밍 부호라고 한다.

보다 일반적으로, 다음이 주어졌다고 하자.

• 소수 거듭제곱 ${\displaystyle q\in \{2,3,4,5,7,8,9,11,\dotsc \}}$
• 2 이상의 정수 ${\displaystyle r\in \{2,3,4,\dotsc \}}$

그렇다면, 유한체 ${\displaystyle \mathbb {F} _{q}}$ 위의 ${\displaystyle r}$차원 벡터 공간 ${\displaystyle \mathbb {F} _{q}^{r}}$ 및 ${\displaystyle r-1}$차원 사영 공간

${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{r-1}={\frac {\mathbb {F} _{q}^{r}\setminus \{{\vec {0}}\}}{u\sim v\iff \exists \lambda \in \mathbb {F} _{q}^{\times }\colon u=\lambda v}}}$

을 구성할 수 있다. 다시 말해, 사영화 몫 함수

${\displaystyle \mathbb {F} _{q}^{r}\setminus \{{\vec {0}}\}\twoheadrightarrow \mathbb {P} _{\mathbb {F} _{q}}^{r-1}}$

는 집합 ${\displaystyle \mathbb {F} _{q}^{r}\setminus \{{\vec {0}}\}}$ 위에 동치 관계를 정의하며, 그 동치류의 수는 다음과 같다.

${\displaystyle {\frac {|\mathbb {F} _{q}^{r}\setminus \{{\vec {0}}\}|}{|\mathbb {F} _{q}^{\times }|}}={\frac {q^{r}-1}{q-1}}}$

이제, 각 동치류에서 임의의 대표원을 고를 수 있으며, 이 대표원들을 열벡터로 삼아 ${\displaystyle \mathbb {F} _{q}}$ 성분의 ${\displaystyle r\times (q^{r}-1)/(q-1)}$ 행렬

${\displaystyle H\in \operatorname {Mat} (r,(q^{r}-1)/(q-1);\mathbb {F} _{q})}$

을 구성할 수 있다. 이 행렬을 패리티 확인 행렬로 갖는 선형 부호

${\displaystyle C=\ker H\subseteq \mathbb {F} _{q}^{(q^{r}-1)/(q-1)}}$

를 ${\displaystyle q}$진 ${\displaystyle r}$-해밍 부호라고 한다.

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

해밍 부호의 거리는 3이다. 즉, 일반적으로, 소수 거듭제곱 ${\displaystyle q}$ 및 양의 정수 ${\displaystyle r}$가 주어졌을 때, ${\displaystyle q}$진 ${\displaystyle r}$-해밍 부호는 ${\displaystyle [(q^{r}-1)/(q-1),(q^{r}-1)/(q-1)-r,3]_{q}}$-선형 부호이다. 특히, 거리가 3이므로, 해밍 부호는 각 부호어마다

• 1개 이하의 오류를 교정할 수 있으며,
• 2개 이하의 오류의 존재를 발견할 수 있다. (다만, 2개의 오류가 발생한 것을 1개의 오류가 발생한 것과 구별할 수 있지는 않다. 즉, 2개의 오류가 발생하였을 때, 데이터가 잘못 복구될 수 있다.)

소수 거듭제곱 ${\displaystyle q}$에 대하여, ${\displaystyle q}$진 해밍 부호를 구성하려면 동치류의 대표원을 임의로 골라야 한다. 각 동치류의 크기는 ${\displaystyle q-1}$이므로, (행의 순열을 무시하면) ${\displaystyle q}$진 ${\displaystyle r}$-해밍 부호의 가능한 패리티 확인 행렬의 수는

${\displaystyle (q-1)^{(q^{r}-1)/(q-1)}}$

이다. 물론, 서로 다른 패리티 확인 행렬이 같은 선형 부호를 정의할 수 있다.

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

${\displaystyle [2^{r}-1,2^{r}-1-r,3]_{2}}$-해밍 부호는 같은 길이 및 거리의 선형 부호 가운데, 가장 효율적이다. 즉, 임의의 ${\displaystyle [2^{r}-1,k,3]_{2}}$-선형 부호에 대하여,

${\displaystyle k\leq 2^{r}-1-r}$

이다.

${\displaystyle r=2}$ 이진 해밍 부호는 삼중 반복 부호(三重反復符號, 영어: triple repetition code)와 같다. 즉, 이는 다음과 같다.

• 송신할 때, 같은 비트를 세 번 반복하여 보낸다.
• 수신할 때,
  • 만약 세 비트가 모두 같다면, 오류가 없음을 알 수 있다.
  • 만약 세 비트 가운데 하나가 다르다면, 이를 다른 두 비트와 같게 교정할 수 있다.

생성 행렬과 표준형 패리티 확인 행렬은 다음과 같다.

${\displaystyle G={\begin{pmatrix}1\\1\\1\end{pmatrix}}}$

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

가장 흔히 사용되는 해밍 부호는 ${\displaystyle r=3}$ 이진 해밍 부호이다. 이 경우, ${\displaystyle r=3}$ 이진 해밍 부호의 생성 행렬과 표준형 패리티 확인 행렬은 각각 다음과 같다.

${\displaystyle 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}}}$

${\displaystyle 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}}}$

${\displaystyle \mathbb {F} _{3}}$ 위의 사영 직선 ${\displaystyle \mathbb {P} _{\mathbb {F} _{3}}^{1}}$을 구성하는 ${\displaystyle \mathbb {F} _{3}^{2}\setminus \{{\vec {0}}\}}$의 동치류들은 다음과 같다.

${\displaystyle \{(0,1),(0,2)\}}$

${\displaystyle \{(1,0),(2,0)\}}$

${\displaystyle \{(1,1),(2,2)\}}$

${\displaystyle \{(1,2),(2,1)\}}$

이에 따라, 예를 들어 첫째 대표원들을 고르면, 삼진 2-해밍 부호의 표준형 패리티 확인 행렬은 다음과 같다.

${\displaystyle H={\begin{pmatrix}1&1&1&0\\1&2&0&1\end{pmatrix}}}$

그 표준형 생성 행렬은 다음과 같다.

${\displaystyle G={\begin{pmatrix}1&0\\0&1\\2&2\\2&1\end{pmatrix}}}$

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

해밍 부호, 특히 ${\displaystyle r=3}$ 이진 해밍 부호는 오늘날에도 널리 사용되고 있다.

• 부호 이론
• 해밍 거리
• 리드 솔로몬 부호

• Weisstein, Eric Wolfgang. “Hamming code”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• 이철희. “해밍코드(Hamming codes)”. 《수학노트》. 
• 차재복 (2013년 1월 7일). “해밍 코드, 해밍 부호”. 《정보통신기술용어해설》.