선형대수학 과 컴퓨터 과학 에서 해밍 부호 (해밍符號, 영어 : Hamming code 해밍 코드[* ] )는 이진 선형 부호 의 일종이다.[ 1]
해밍 부호 는 임의의 (소수 거듭제곱) 진법에 대하여 정의되는, 거리 3의 선형 부호 이다. 이 가운데 이진 해밍 부호는 정의하기가 특별히 간단하다.
다음 데이터가 주어졌다고 하자.
2 이상의 정수
r
∈
{
2
,
3
,
4
,
…
}
{\displaystyle r\in \{2,3,4,\dotsc \}}
그렇다면, 다음과 같은,
F
2
{\displaystyle \mathbb {F} _{2}}
r
×
2
r
−
1
{\displaystyle r\times 2^{r}-1}
H
{\displaystyle H}
H
i
,
j
=
j
i
(
1
≤
i
≤
r
,
j
=
j
r
+
2
j
r
−
1
+
4
j
r
−
2
+
8
j
4
+
⋯
+
2
r
−
1
j
1
,
j
1
,
…
,
j
r
∈
{
0
,
1
}
)
{\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\})}
즉,
H
{\displaystyle H}
j
{\displaystyle j}
j
{\displaystyle j}
이진법 표기의 성분들이다. 예를 들어,
r
=
3
{\displaystyle r=3}
H
{\displaystyle H}
H
=
(
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
)
{\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}}}
이제,
H
{\displaystyle H}
패리티 확인 행렬 로 갖는 이진 선형 부호
C
=
ker
H
{\displaystyle C=\ker H}
를
r
{\displaystyle r}
이진 해밍 부호 또는
[
2
r
−
1
,
2
r
−
1
−
r
,
3
]
2
{\displaystyle [2^{r}-1,2^{r}-1-r,3]_{2}}
해밍 부호 라고 한다.
보다 일반적으로, 다음이 주어졌다고 하자.
소수 거듭제곱
q
∈
{
2
,
3
,
4
,
5
,
7
,
8
,
9
,
11
,
…
}
{\displaystyle q\in \{2,3,4,5,7,8,9,11,\dotsc \}}
2 이상의 정수
r
∈
{
2
,
3
,
4
,
…
}
{\displaystyle r\in \{2,3,4,\dotsc \}}
그렇다면, 유한체
F
q
{\displaystyle \mathbb {F} _{q}}
r
{\displaystyle r}
벡터 공간
F
q
r
{\displaystyle \mathbb {F} _{q}^{r}}
r
−
1
{\displaystyle r-1}
사영 공간
P
F
q
r
−
1
=
F
q
r
∖
{
0
→
}
u
∼
v
⟺
∃
λ
∈
F
q
×
:
u
=
λ
v
{\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}}}
을 구성할 수 있다. 다시 말해, 사영화 몫 함수
F
q
r
∖
{
0
→
}
↠
P
F
q
r
−
1
{\displaystyle \mathbb {F} _{q}^{r}\setminus \{{\vec {0}}\}\twoheadrightarrow \mathbb {P} _{\mathbb {F} _{q}}^{r-1}}
는 집합
F
q
r
∖
{
0
→
}
{\displaystyle \mathbb {F} _{q}^{r}\setminus \{{\vec {0}}\}}
동치 관계 를 정의하며, 그 동치류 의 수는 다음과 같다.
|
F
q
r
∖
{
0
→
}
|
|
F
q
×
|
=
q
r
−
1
q
−
1
{\displaystyle {\frac {|\mathbb {F} _{q}^{r}\setminus \{{\vec {0}}\}|}{|\mathbb {F} _{q}^{\times }|}}={\frac {q^{r}-1}{q-1}}}
이제, 각 동치류에서 임의의 대표원을 고를 수 있으며, 이 대표원들을 열벡터로 삼아
F
q
{\displaystyle \mathbb {F} _{q}}
r
×
(
q
r
−
1
)
/
(
q
−
1
)
{\displaystyle r\times (q^{r}-1)/(q-1)}
행렬
H
∈
Mat
(
r
,
(
q
r
−
1
)
/
(
q
−
1
)
;
F
q
)
{\displaystyle H\in \operatorname {Mat} (r,(q^{r}-1)/(q-1);\mathbb {F} _{q})}
을 구성할 수 있다. 이 행렬을 패리티 확인 행렬 로 갖는 선형 부호
C
=
ker
H
⊆
F
q
(
q
r
−
1
)
/
(
q
−
1
)
{\displaystyle C=\ker H\subseteq \mathbb {F} _{q}^{(q^{r}-1)/(q-1)}}
를
q
{\displaystyle q}
r
{\displaystyle r}
다른 모든 선형 부호 와 마찬가지로,
해밍 부호에 모든 성분에 대응되는 (즉 일반적인) 패리티 성분을 하나 더 추가할 수 있으며, 이는
[
2
r
,
2
r
−
r
−
1
,
4
]
{\displaystyle [2^{r},2^{r}-r-1,4]}
확장 해밍 부호 (擴張Hamming符號, 영어 : extended Hamming code )라고 한다.
해밍 부호의 거리는 3이다. 즉, 일반적으로, 소수 거듭제곱
q
{\displaystyle q}
r
{\displaystyle r}
q
{\displaystyle q}
r
{\displaystyle r}
[
(
q
r
−
1
)
/
(
q
−
1
)
,
(
q
r
−
1
)
/
(
q
−
1
)
−
r
,
3
]
q
{\displaystyle [(q^{r}-1)/(q-1),(q^{r}-1)/(q-1)-r,3]_{q}}
선형 부호 이다. 특히, 거리가 3이므로, 해밍 부호는 각 부호어마다
1개 이하의 오류를 교정할 수 있으며,
2개 이하의 오류의 존재를 발견할 수 있다. (다만, 2개의 오류가 발생한 것을 1개의 오류가 발생한 것과 구별할 수 있지는 않다. 즉, 2개의 오류가 발생하였을 때, 데이터가 잘못 복구될 수 있다.) 소수 거듭제곱
q
{\displaystyle q}
q
{\displaystyle q}
동치류 의 대표원을 임의로 골라야 한다. 각 동치류의 크기 는
q
−
1
{\displaystyle q-1}
순열 을 무시하면)
q
{\displaystyle q}
r
{\displaystyle r}
패리티 확인 행렬 의 수는
(
q
−
1
)
(
q
r
−
1
)
/
(
q
−
1
)
{\displaystyle (q-1)^{(q^{r}-1)/(q-1)}}
이다. 물론, 서로 다른 패리티 확인 행렬 이 같은 선형 부호 를 정의할 수 있다.
q
=
2
{\displaystyle q=2}
동치류 가 한원소 집합 이므로 해밍 부호는 유일하며, 대표원을 임의로 고를 필요가 없다. 그러나 예를 들어
q
=
3
{\displaystyle q=3}
2
(
3
r
−
1
)
/
2
{\displaystyle 2^{(3^{r}-1)/2}}
r
{\displaystyle r}
[
2
r
−
1
,
2
r
−
1
−
r
,
3
]
2
{\displaystyle [2^{r}-1,2^{r}-1-r,3]_{2}}
선형 부호 가운데, 가장 효율적이다. 즉, 임의의
[
2
r
−
1
,
k
,
3
]
2
{\displaystyle [2^{r}-1,k,3]_{2}}
선형 부호 에 대하여,
k
≤
2
r
−
1
−
r
{\displaystyle k\leq 2^{r}-1-r}
이다.
r
=
2
{\displaystyle r=2}
삼중 반복 부호 (三重反復符號, 영어 : triple repetition code )와 같다. 즉, 이는 다음과 같다.
송신할 때, 같은 비트를 세 번 반복하여 보낸다.
수신할 때,
만약 세 비트가 모두 같다면, 오류가 없음을 알 수 있다.
만약 세 비트 가운데 하나가 다르다면, 이를 다른 두 비트와 같게 교정할 수 있다. 생성 행렬과 표준형 패리티 확인 행렬 은 다음과 같다.
G
=
(
1
1
1
)
{\displaystyle G={\begin{pmatrix}1\\1\\1\end{pmatrix}}}
H
=
(
1
1
0
1
0
1
)
{\displaystyle H={\begin{pmatrix}1&1&0\\1&0&1\end{pmatrix}}}
가장 흔히 사용되는 해밍 부호는
r
=
3
{\displaystyle r=3}
r
=
3
{\displaystyle r=3}
패리티 확인 행렬 은 각각 다음과 같다.
G
=
(
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
)
{\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}}}
H
=
(
0
1
1
1
1
0
0
1
0
1
1
0
1
0
1
1
0
1
0
0
1
)
{\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}}}
F
3
{\displaystyle \mathbb {F} _{3}}
사영 직선
P
F
3
1
{\displaystyle \mathbb {P} _{\mathbb {F} _{3}}^{1}}
F
3
2
∖
{
0
→
}
{\displaystyle \mathbb {F} _{3}^{2}\setminus \{{\vec {0}}\}}
{
(
0
,
1
)
,
(
0
,
2
)
}
{\displaystyle \{(0,1),(0,2)\}}
{
(
1
,
0
)
,
(
2
,
0
)
}
{\displaystyle \{(1,0),(2,0)\}}
{
(
1
,
1
)
,
(
2
,
2
)
}
{\displaystyle \{(1,1),(2,2)\}}
{
(
1
,
2
)
,
(
2
,
1
)
}
{\displaystyle \{(1,2),(2,1)\}}
이에 따라, 예를 들어 첫째 대표원들을 고르면, 삼진 2-해밍 부호의 표준형 패리티 확인 행렬 은 다음과 같다.
H
=
(
1
1
1
0
1
2
0
1
)
{\displaystyle H={\begin{pmatrix}1&1&1&0\\1&2&0&1\end{pmatrix}}}
그 표준형 생성 행렬은 다음과 같다.
G
=
(
1
0
0
1
2
2
2
1
)
{\displaystyle G={\begin{pmatrix}1&0\\0&1\\2&2\\2&1\end{pmatrix}}}
리처드 해밍 이 1950년에 도입하였다.[ 2] 벨 연구소 에서 벨 모델 V(영어 : Bell Model V )라는 컴퓨터 를 이용해서 작업을 했다. 이 컴퓨터는 확실히 여러 면에서 오늘날의 컴퓨터와는 거리가 멀었다. 릴레이 회로로 만들어졌으며 입력도 천공 카드 를 이용했다. 천공 카드를 이용했으므로 컴퓨터에 입력되는 자료들은 필연적으로 언제나 오류의 가능성이 있었다. 주중에는 컴퓨터의 관리자가 있으면서 입력에 오류가 발생했다는 경고등이 켜지면 직접 수정할 수 있었으나, 관리자가 없는 주말에는 에러가 발생한 채 프로그램이 실행되지 않고 다음 작업으로 넘어가기 일쑤였다. 해밍은 이런 문제로 인해 여러 차례 고생을 한 후에, 이 문제를 근본적으로 해결하기 위해 노력했다. 그 후 몇 년 동안 오류를 수정하는 방법에 대해서 연구하면서 이와 관련된 여러가지의 효율적인 알고리즘을 만들어냈고 마침내 1950년에 해밍 부호를 발표했다. 이는 선형 부호 이론의 시초로 여겨진다.
해밍 부호, 특히
r
=
3
{\displaystyle r=3}
![{\displaystyle [2^{r}-1,2^{r}-1-r,3]_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6842203acc11dfb49b6be7ea2dc3786a7e0dd98)
![{\displaystyle [2^{r},2^{r}-r-1,4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edb41b57e016b4994c3f41ca9547d87152b2f511)
![{\displaystyle [(q^{r}-1)/(q-1),(q^{r}-1)/(q-1)-r,3]_{q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c7e1ccd6308411cacb370913792306737d8b396)
![{\displaystyle [2^{r}-1,k,3]_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d265475d9a02201c6738870919c0ae9ae0fe775)
