선형대수학 과 컴퓨터 과학 에서 해밍 부호 (해밍符號, 영어 : 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} 이다.
이진 2-해밍 부호
편집
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}}} 이진 3-해밍 부호
편집
가장 흔히 사용되는 해밍 부호는 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}}} 삼진 2-해밍 부호
편집
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)
