해밍 부호

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

해밍 부호는 주어진 데이터에 오류를 검출하고 정정하기 위해 추가 비트를 사용하는 선형 부호이다. 1950년 리처드 해밍에 의해 개발되었으며, 데이터 비트와 오류 정정 비트로 구성된다. 해밍 부호는 오류 정정 능력을 갖춘 다양한 형태로 존재하며, 이진 해밍 부호, 삼진 해밍 부호, 확장 해밍 부호 등이 있다. 확장 해밍 부호는 추가 패리티 비트를 사용하여 오류 검출 능력을 향상시킨다. 해밍 부호는 컴퓨터 메모리 시스템 등에서 널리 사용되며, 오류 정정 및 데이터 무결성 확보에 기여한다.

더 읽어볼만한 페이지

1951년 컴퓨팅 - 테이프 드라이브
테이프 드라이브는 자기 테이프에 데이터를 읽고 쓰는 장치이며, 1951년 UNISERVO 출시 이후 기술 발전을 거쳐 현재는 높은 저장 용량과 데이터 안정성을 바탕으로 백업, 아카이브 등에 활용된다.
부호 이론 - 해밍 거리
해밍 거리는 길이가 같은 두 문자열에서 서로 다른 기호의 개수를 나타내는 거리 척도로, 아벨 군에서는 벡터의 해밍 무게를 영벡터와의 해밍 거리로 정의하며, 오류 검출, 수정 부호 이론, 정보 이론, 계통학 등에서 활용된다.
부호 이론 - 선형 부호
선형 부호는 유한체 위의 벡터 공간의 부분 공간으로, 데이터 전송 및 오류 정정을 위해 사용되며, 길이, 차원, 최소 거리에 따라 표기되고, 부호어, 생성 행렬, 패리티 검사 행렬 등의 개념을 갖는다.
오류 검출 정정 - 부호 이론
부호 이론은 정보를 효율적으로 표현하고 오류를 감지 및 수정하는 기술을 연구하며, 소스 부호화, 채널 부호화, 암호 부호화 등으로 발전하여 CD, 모뎀, 휴대폰 등 다양한 분야에 응용된다.
오류 검출 정정 - 비터비 알고리즘
비터비 알고리즘은 잡음이 있는 통신 링크 상에서 길쌈 부호 해독에 사용되며, 확률과 관련된 극대화 문제에 동적 계획법을 적용하는 표준 용어로, 상태 기계를 기반으로 은닉 마르코프 모델에서 가장 가능성 높은 상태 시퀀스를 찾는 데 활용되어 통신, 자연어 처리, 생물정보학 등 다양한 분야에 적용되고 개선 방법이 연구되고 있다.

해밍 부호
개요
이름	해밍 부호
영어 이름	Hamming code
종류	선형 블록 부호
창시자	리처드 W. 해밍
기술 정보
블록 길이	(여기서 )
부호율	}}
표기법	-부호
속성	완벽 부호

2. 정의

'''해밍 부호'''는 데이터 전송이나 저장 과정에서 발생하는 오류를 검출하고 정정하기 위해 설계된 선형 부호의 한 종류이다. 이는 원본 데이터에 추가적인 확인용 비트(패리티 비트)를 덧붙이는 방식으로 작동하며, 일반적으로 해밍 거리 3을 갖도록 설계되어 1비트의 오류를 수정하거나 2비트의 오류를 검출할 수 있다.^[1]

데이터에 오류 정정 비트를 포함시키고, 이 비트들을 특정 규칙에 따라 배열하면, 어떤 비트에서 오류가 발생했는지 식별하는 것이 가능하다. 예를 들어, 7비트 데이터가 있을 때, 3개의 오류 제어 비트를 추가하면 총 10비트가 되는데, 이 3개의 비트를 통해 7개의 데이터 비트 중 어느 위치에서 단일 비트 오류가 발생했는지 알아낼 수 있다.

1950년 벨 연구소의 리처드 해밍은 이러한 오류 정정 부호 시스템을 설명하기 위한 명명법을 개발했다. 이 표기법은 (n, k) 형식으로 나타내는데, 여기서 n은 부호화된 후의 총 비트 수이고, k는 원래 데이터 비트의 수이다. 예를 들어, 7비트 ASCII 데이터에 패리티 비트 1개를 추가하는 간단한 오류 검출 코드는 (8, 7) 코드로 표현된다. 코드 속도는 k/n으로 계산되며, 이는 전체 비트 중 실제 데이터가 차지하는 비율을 나타낸다.

해밍은 또한 두 개 이상의 비트에서 오류가 발생하는 문제에 주목하여 '거리'라는 개념을 도입했는데, 이는 현재 그의 이름을 따 해밍 거리라고 불린다. 해밍 거리는 두 부호어(code word) 사이에 서로 다른 비트의 개수를 의미한다. 예를 들어, 단순 패리티 검사는 해밍 거리가 2인데, 이는 1비트 오류는 감지할 수 있지만 수정할 수는 없고, 2비트 오류는 감지조차 못 할 수 있음을 의미한다. 반면, 해밍 거리가 3인 코드는 1비트 오류를 수정하거나, 2비트 오류를 감지할 수 있다. 일반적으로 거리가 ''k''인 코드는 최대 ''k'' − 1개의 오류를 감지할 수 있다.

해밍은 높은 코드 속도를 유지하면서 동시에 해밍 거리를 늘려 오류 정정 능력을 향상시키는 것을 목표로 연구했으며, 패리티 비트들을 서로 중첩시켜 데이터와 다른 패리티 비트들을 동시에 검사하는 혁신적인 방식을 고안했다.

해밍 부호는 알려진 오류 정정 부호 중 가장 오래된 것 중 하나로, 블록당 1비트의 오류를 정정할 수 있다. 리드-솔로몬 부호와 같은 더 강력한 부호들에 비해 정정 능력은 상대적으로 낮지만, 처리 속도가 빠르다는 장점이 있다. 이러한 특징으로 인해 오류 발생률이 비교적 낮으면서 빠른 처리가 요구되는 ECC 메모리나 RAID 2와 같은 시스템에 사용된다. 또한, WinRAR의 복구 레코드에도 사용되고 있다.

2. 1. 이진 해밍 부호

선형 부호의 일종인 해밍 부호 중, 0과 1만을 사용하는 이진 해밍 부호는 비교적 간단하게 정의할 수 있다.

먼저 2 이상의 정수

r

(

r \in \{2, 3, 4, \dots\}

)을 하나 선택한다. 그리고 체

\mathbb{F}_2 = \{0, 1\}

위에서 다음과 같은

r \times (2^r-1)

크기의 행렬

H

를 만든다. 행렬

H

의

j

번째 열 벡터는 1부터

2^r-1

까지의 정수

j

를 이진법으로 표현했을 때 각 자릿수를 위에서부터 순서대로 나열한 것이다.

예를 들어

r=3

일 경우,

2^3-1=7

이므로

H

는 3×7 행렬이 된다. 1부터 7까지의 수를 이진법으로 나타내면 각각 001, 010, 011, 100, 101, 110, 111이다. (계산을 위해 앞에 0을 붙여 세 자리로 맞춤) 이를 각 열에 세로로 배치하면 다음과 같은 행렬

H

를 얻는다.

:

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

를 패리티 확인 행렬로 사용하는 이진 선형 부호

C

를 '''

r

-이진 해밍 부호'''라고 한다. 이 부호

C

는 행렬

H

의 핵(kernel)으로 정의되며, 수식으로는

C = \ker H = \{ \mathbf{x} \in \mathbb{F}_2^{2^r-1} \mid H\mathbf{x}^\mathsf{T} = \mathbf{0} \}

와 같이 나타낼 수 있다. 여기서

\mathbf{x}^\mathsf{T}

는 벡터

\mathbf{x}

의 전치(transpose)를 의미한다.

r

-이진 해밍 부호는 파라미터

[n, k, d] = [2^r-1, 2^r-1-r, 3]

를 가지므로, '''

[2^r-1, 2^r-1-r, 3]_2

-해밍 부호'''라고도 부른다. 여기서

n

은 부호어의 길이,

k

는 정보 비트의 수,

d

는 최소 거리(해밍 거리)를 의미한다.

2. 2. 임의의 진법의 해밍 부호

해밍 부호는 흔히 이진법에서 사용되지만, 이를 일반화하여 임의의 진법에서도 정의할 수 있다.

보다 일반적으로, 소수의 거듭제곱인 수

q

(예: 2, 3, 4, 5, 7, 8, 9, 11 등)와 2 이상의 정수

r

이 주어졌다고 하자. 여기서

q

는 사용하는 진법의 크기를 나타낸다. 예를 들어

q=2

이면 이진법,

q=3

이면 삼진법 해밍 부호가 된다.

이때 유한체

\mathbb F_q

(크기가

q

인 유한체) 위의

r

차원 벡터 공간

\mathbb F_q^r

을 생각한다. 이 벡터 공간에서 영벡터(

\vec 0

)를 제외한 벡터들에 대해, 한 벡터가 다른 벡터의 0이 아닌 스칼라배와 같으면 같은 것으로 간주하는 관계를 정의한다 (

u\sim v\iff\exists\lambda\in\mathbb F_q^\times\colon u=\lambda v

). 이 관계에 따라 벡터들을 묶어

r-1

차원 사영 공간

\mathbb P^{r-1}_{\mathbb F_q}

을 구성할 수 있다. 이 사영 공간은 서로 다른 '방향'을 나타내는 점들의 집합으로 볼 수 있으며, 점의 개수는 다음과 같다.

:

\frac

= \frac{q^r-1}{q-1}

이제, 이 사영 공간의 각 점(각 묶음)에서 대표 벡터를 하나씩 선택하여, 이 벡터들을 열벡터로 하는 행렬

H

를 만든다. 이 행렬

H

는

\mathbb F_q

의 원소를 성분으로 가지며, 크기는

r \times \frac{q^r-1}{q-1}

이다.

:

H\in\operatorname{Mat}(r,(q^r-1)/(q-1);\mathbb F_q)

이 행렬

H

를 패리티 확인 행렬로 사용하는 선형 부호

C

를 정의한다. 이 부호

C

는

H

를 곱했을 때 영벡터가 되는 모든 벡터들의 집합, 즉

H

의 핵(kernel)으로 정의된다.

:

C=\ker H = \{ \mathbf{x} \in \mathbb F_q^{(q^r-1)/(q-1)} \mid H\mathbf{x} = \vec 0 \}

이렇게 정의된 선형 부호

C

를 $q$ 진 $r$ -해밍 부호라고 부른다. 이는 기존의 이진 해밍 부호를 임의의 진법

q

와 차원

r

에 대해 일반화한 것이다.

2. 3. 확장 해밍 부호

다른 모든 선형 부호와 마찬가지로, 해밍 부호에 모든 성분에 대응되는 패리티 성분을 하나 더 추가할 수 있다. 이는

[2^r,2^r-r-1,4]

-선형 부호이며, '''확장 해밍 부호'''(extended Hamming code^영어)라고 부른다.

단순한 해밍 부호는 오류 검출만 수행할 경우 2비트의 오류까지 검출할 수 있다. 예를 들어 (7,4) 해밍 부호에서 부호어 ''x''에 위치 ''i''와 ''j''에 2비트 오류(''e_i'', ''e_j'')가 포함된 수신어 ''Y''는 다음과 같다.

:

Y = x \cdot G \oplus e_i \oplus e_j

이 수신어에 검사 행렬 ''H''의 전치 행렬 ''H^T''를 곱하여 신드롬(syndrome)을 계산하면 다음과 같다.

:

S = Y \cdot H^T = (x \cdot G \oplus e_i \oplus e_j) \cdot H^T = (x \cdot G \cdot H^T) \oplus (e_i \cdot H^T) \oplus (e_j \cdot H^T)

이때

x \cdot G \cdot H^T = 0

이므로 (모든 유효한 부호어는 검사 행렬을 곱하면 0이 됨),

:

S = e_i \cdot H^T \oplus e_j \cdot H^T

가 된다. ''e_i'' ≠ ''e_j'' 이므로, 위 식의 결과는 검사 행렬의 임의의 두 열 벡터의 배타적 논리합이 된다. 검사 행렬의 정의에 따라 모든 열 벡터는 서로 다르고 영벡터가 아니므로, 두 개의 서로 다른 열 벡터의 배타적 논리합은 영벡터가 될 수 없다. 따라서 2비트 오류 시에도 신드롬은 영벡터가 되지 않아 오류 발생을 감지할 수 있다.

하지만, 계산된 신드롬 값이 검사 행렬의 특정 열 벡터와 일치할 수 있다. 이 경우, 수신기는 이를 1비트 오류로 오인하여 잘못된 위치의 비트를 수정하는 오정정(miscorrection)을 일으킬 수 있다. 즉, 단순 해밍 부호만으로는 1비트 오류 수정 기능과 2비트 오류 검출 기능을 동시에 안정적으로 구현하기 어렵다.

이러한 한계를 극복하기 위해 해밍 부호에 부호어 전체에 대한 패리티 비트를 추가하여, 1비트 오류 수정과 동시에 2비트 오류 검출이 가능하도록 개선한 것이 확장 해밍 부호이다. 이 기능을 SECDED (Single Error Correction, Double Error Detection)라고도 한다.

확장 해밍 부호의 생성은, 먼저 단순 해밍 부호로 부호어를 생성한 뒤, 생성된 부호어의 모든 비트에 대한 배타적 논리합(전체 패리티)을 계산하여 부호어의 마지막 비트로 추가하는 방식으로 이루어진다. 예를 들어, (7,4) 해밍 부호에서 정보 비트 1011에 대한 부호어가 1 0 1 1 '''1 0 0''' 이었다고 가정하자. 이 7개 비트(1 0 1 1 1 0 0)의 배타적 논리합은 0 (1⊕0⊕1⊕1⊕1⊕0⊕0 = 0)이다. 따라서 해당 확장 해밍 부호어는 마지막에 패리티 비트 0을 추가한 1 0 1 1 1 0 0 '''0'''이 된다.

복호화에는 다음과 같이 기존 검사 행렬을 확장한 행렬을 사용한다.

:

H_{ext} =\begin{bmatrix}1 & 0 & 1 & 1 & 1 & 0 & 0 & \mathbf{0} \\1 & 1 & 0 & 1 & 0 & 1 & 0 & \mathbf{0} \\0 & 1 & 1 & 1 & 0 & 0 & 1 & \mathbf{0} \\\mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} \\\end{bmatrix}

이 행렬은 기존 (7,4) 해밍 부호의 검사 행렬 오른쪽에 모든 성분이 0인 열 벡터를 추가하고, 아래쪽에 모든 성분이 1인 행 벡터(전체 패리티 검사를 위한 행)를 추가하여 구성된다.

수신된 부호어 ''Y''에 확장된 검사 행렬

H_{ext}

의 전치 행렬을 곱하여 신드롬 ''S''를 계산한다.

:

S = Y \cdot H_{ext}^T

계산된 신드롬 ''S''와 전체 패리티 검사 결과(신드롬 벡터의 마지막 비트)를 이용하여 오류를 판별하고 처리한다.

오류 없음: 신드롬 ''S''가 영벡터이다 ( $S = 0$ ). 수신된 부호어는 오류가 없는 것으로 판단한다.
1비트 오류: 신드롬 ''S''가 영벡터가 아니며, $H_{ext}$ 의 특정 열 벡터와 일치한다. 이 열 벡터의 위치가 오류가 발생한 비트의 위치를 나타낸다. 해당 비트를 반전시켜 오류를 수정한다. 이때 전체 패리티 검사 결과(신드롬의 마지막 비트)는 1이 된다.
2비트 오류: 신드롬 ''S''가 영벡터가 아니지만, $H_{ext}$ 의 어떤 열 벡터와도 일치하지 않는다. 이때 전체 패리티 검사 결과(신드롬의 마지막 비트)는 0이 된다. 이 경우, 오류를 수정할 수는 없지만 2비트 오류가 발생했음을 검출할 수 있다.

이처럼 확장 해밍 부호는 패리티 비트 하나를 추가함으로써 1비트 오류 수정 능력은 유지하면서 2비트 오류까지 검출할 수 있는 향상된 성능을 제공한다.

3. 성질

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

메시지에 더 많은 오류 정정 비트를 포함시키고, 이 비트들을 서로 다른 잘못된 비트가 서로 다른 오류 결과를 생성하도록 배열하면 잘못된 비트를 식별할 수 있다. 예를 들어, 7비트 메시지에는 7가지 가능한 단일 비트 오류가 있으므로, 3개의 오류 제어 비트를 사용하면 오류 발생 여부뿐만 아니라 어떤 비트에서 오류가 발생했는지도 지정할 수 있다.^[4]

해밍은 블록의 데이터 비트 수와 오류 정정 비트 수를 포함하는 명명법을 개발했다. 예를 들어, 패리티 비트는 모든 데이터 워드에 단일 비트를 추가하므로, 7비트 ASCII 워드의 경우 해밍은 이를 총 8비트 중 7비트가 데이터인 ''(8,7)'' 코드로 설명했다. 반복 코드는 같은 논리에 따라 ''(3,1)'' 코드가 된다. 코드 속도는 데이터 비트 수를 총 비트 수로 나눈 값으로, (3,1) 반복 코드의 경우 1/3이다.^[4]

해밍은 또한 두 개 이상의 비트가 뒤집히는 문제를 "거리"(현재는 그의 이름을 따 해밍 거리라고 함)로 설명했다. 패리티 비트는 거리가 2이므로 1비트 오류를 감지할 수 있지만 수정할 수는 없으며, 2비트 오류는 감지하지 못한다. (3,1) 반복 코드는 거리가 3이므로, 1비트 오류를 수정하거나 2비트 오류를 감지(수정 불가)할 수 있다. (4,1) 반복 코드(각 비트 4번 반복)는 거리가 4이므로, 3비트 오류까지 감지(수정 불가)할 수 있다. 일반적으로 거리가 ''k''인 코드는 ''k'' − 1개의 오류를 감지할 수 있다.^[4]

해밍은 코드 속도를 최대한 높이는 동시에 거리도 최대한 늘리는 문제에 관심을 가졌다. 1940년대 동안 그는 기존 코드보다 성능이 크게 향상된 여러 인코딩 방식을 개발했는데, 그의 모든 시스템의 핵심은 패리티 비트가 서로 중첩되어 데이터와 다른 패리티 비트를 함께 검사할 수 있도록 하는 것이었다.^[4]

3. 1. 가짓수

소수의 거듭제곱인

q

에 대해,

q

진 해밍 부호를 만들 때는 동치류의 대표원을 임의로 선택해야 한다. 각 동치류의 크기는

q-1

이므로, 행의 순열을 고려하지 않으면

q

진

r

-해밍 부호에서 가능한 패리티 확인 행렬의 수는 다음과 같다.

:

(q-1)^{(q^r-1)/(q-1)}

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

특히

q=2

인 경우, 즉 이진 해밍 부호의 경우, 각 동치류가 원소 하나만 가지는 한원소 집합이므로 대표원을 선택할 필요 없이 해밍 부호는 유일하게 결정된다. 하지만 예를 들어

q=3

인 삼진 해밍 부호의 경우,

2^{(3^r-1)/2}

개의 서로 다른

r

-해밍 부호가 존재할 수 있다.

3. 2. 최적성

[2^r-1, 2^r-1-r, 3]₂로 표현되는 해밍 부호는 주어진 길이와 최소 거리를 가지는 선형 부호 중에서 가장 효율적인 부호이다. 구체적으로, 길이가 2^r-1이고 최소 거리가 3인 임의의 이진 선형 부호 [2^r-1, k, 3]₂가 있다고 할 때, 이 부호의 차원 k는 해밍 부호의 차원인 2^r-1-r보다 클 수 없다. 즉, 다음 부등식이 항상 성립한다.

:k ≤ 2^r-1-r

이는 같은 길이와 오류 정정 능력(최소 거리)을 가지는 부호들 중에서 해밍 부호가 가장 많은 정보를 담을 수 있다는 것을 의미한다.

4. 기본 개념

오류 정정 부호의 일종인 '''해밍 부호'''는 데이터 전송이나 저장 과정에서 발생하는 오류를 검출하고 정정하기 위해 사용된다. 특히, 한 비트의 오류(단일 비트 오류)가 발생했을 경우, 그 위치를 찾아내어 수정할 수 있는 능력을 갖추고 있다.

해밍 부호는 1940년대 벨 연구소의 리처드 해밍이 개발했다. 당시 사용되던 천공 카드 판독기는 오류가 잦았는데, 기존의 오류 검출 부호인 패리티 비트는 오류 발생 여부만 알 수 있을 뿐, 어느 비트에서 오류가 발생했는지는 알 수 없어 오류 발생 시 전체 작업을 다시 해야 하는 불편함이 있었다. 해밍은 이러한 문제를 해결하기 위해 오류 위치까지 파악하여 자동으로 정정할 수 있는 부호를 연구했다.^[3]

해밍은 서로 다른 부호어(code word) 간의 차이를 나타내는 '''해밍 거리''' 개념을 중요하게 다루었다. 해밍 거리는 두 부호어에서 서로 다른 비트의 개수를 의미한다. 예를 들어, '101'과 '111'의 해밍 거리는 1이다(두 번째 비트만 다름). 해밍 거리가 클수록 더 많은 오류를 감지하거나 수정할 수 있다.

단순 패리티 비트는 해밍 거리가 2이다. 이는 1비트 오류는 감지할 수 있지만 수정은 불가능하며, 2비트 오류는 감지조차 할 수 없음을 의미한다.
각 비트를 세 번 반복하는 (3,1) 반복 부호(예: 0 → 000, 1 → 111)는 해밍 거리가 3이다. 이는 1비트 오류는 수정할 수 있고, 2비트 오류는 감지할 수 있음을 의미한다.

일반적으로 해밍 거리가 ''d''인 부호는 최대 ''d''-1개의 오류를 감지할 수 있으며, 최대

\lfloor (d-1)/2 \rfloor

개의 오류를 수정할 수 있다. 해밍 부호는 최소 해밍 거리가 3이 되도록 설계되어, 1비트 오류를 수정하고 2비트 오류를 감지할 수 있다.

해밍은 부호의 효율성을 나타내는 코드 속도(code rate)와 오류 정정 능력을 나타내는 해밍 거리를 동시에 개선하고자 했다. 그는 여러 개의 패리티 비트를 사용하여 데이터 비트뿐만 아니라 다른 패리티 비트까지 서로 교차하여 검사하는 방식을 고안했다. 이를 통해 적은 수의 추가 비트(패리티 비트)로도 효과적인 오류 검출 및 정정이 가능해졌다.

해밍 부호는 일반적으로 정수

m \ge 2

에 대해 패리티 비트 수(

m

), 총 비트 수(

n

), 데이터 비트 수(

k

), 최소 해밍 거리(

d=3

) 등의 파라미터로 정의된다. 이러한 파라미터를 갖는 해밍 부호를

(n, k)

해밍 부호 또는

[n, k, d]_2

해밍 부호 (여기서 2는 이진법을 의미)라고 표기한다. 예를 들어

m=3

이면

n=7, k=4

가 되어 (7,4) 해밍 부호가 된다. 이는 4비트의 원본 데이터에 3비트의 패리티 비트를 추가하여 7비트의 부호어를 만드는 방식이다. 다양한

m

값에 따른 해밍 부호의 파라미터는 다음과 같다.

패리티 비트 ( $m$ )	총 비트 ( $n=2^m-1$ )	데이터 비트 ( $k=2^m-m-1$ )	이름	비율 ( $k/n$ )
2	3	1	해밍(3,1) (반복 부호)	1/3 ≈ 0.333
3	7	4	해밍(7,4)	4/7 ≈ 0.571
4	15	11	해밍(15,11)	11/15 ≈ 0.733
5	31	26	해밍(31,26)	26/31 ≈ 0.839
6	63	57	해밍(63,57)	57/63 ≈ 0.905
7	127	120	해밍(127,120)	120/127 ≈ 0.945
...	...	...	...	...

해밍 부호의 부호화 및 복호화 과정은 주로 두 개의 행렬, 즉 생성 행렬(Generator matrix) $\mathbf{G}$ 와 패리티 검사 행렬(Parity-check matrix) $\mathbf{H}$ 를 사용하여 수행된다. 생성 행렬 $\mathbf{G}$ 는 $k$ 비트의 원본 데이터를 $n$ 비트의 부호어로 변환하는 데 사용되고, 패리티 검사 행렬 $\mathbf{H}$ 는 수신된 $n$ 비트 부호어의 오류 여부를 검사하고 오류 위치를 찾는 데 사용된다.

4. 1. 부호화

일반적으로 해밍 부호는 어떤 정수 m ≥ 2에 대해 다음과 같은 파라미터로 구성된다.

부호 길이: $n = 2^m - 1$
정보 비트 수: $k = n - m = 2^m - m - 1$
패리티 비트 수: $m = n - k$

여기서 정보 비트 수는 원래 데이터의 비트 수를 의미하고, 부호 길이는 패리티 비트가 추가되어 생성되는 최종 부호어의 비트 수를 의미한다. 예를 들어, m = 3인 경우 n = 7, k = 4가 되며, 이는 4비트의 원본 데이터를 7비트의 부호어로 변환하는 (7,4) 해밍 부호를 형성한다.

해밍 부호의 부호화 과정은 주로

k \times n

크기의 생성 행렬(Generator matrix)

\mathbf{G}

를 사용하여 이루어진다. 부호화는

1 \times k

크기의 원본 데이터 행 벡터

\vec{a}

와 생성 행렬

\mathbf{G}

를 곱하여

1 \times n

크기의 부호어 행 벡터

\vec{x}

를 얻는 과정이다.

:

\vec{x} = \vec{a} \mathbf{G}

이때 행렬 곱셈 과정에서의 모든 덧셈 연산은 모듈로 2 덧셈, 즉 배타적 논리합(XOR)으로 수행된다.

생성 행렬

\mathbf{G}

는

m \times n

크기의 패리티 검사 행렬(Parity-check matrix)

\mathbf{H}

와 다음의 관계를 만족한다.

:

\mathbf{H} \mathbf{G}^\text{T} = \mathbf{0}

여기서

\mathbf{G}^\text{T}

는

\mathbf{G}

의 전치 행렬이고,

\mathbf{0}

은 모든 원소가 0인

m \times k

크기의 영행렬이다.^[3]

계산의 편의성과 구현의 간결성을 위해 종종 '''조직 부호'''(Systematic code) 형태의 행렬이 사용된다. 조직 부호 형태에서 생성 행렬

\mathbf{G}

와 패리티 검사 행렬

\mathbf{H}

는 일반적으로 다음과 같은 구조를 가진다.

$\mathbf{G} = \begin{pmatrix} \mathbf{I}_k & \mathbf{P}^\text{T} \end{pmatrix}$
$\mathbf{H} = \begin{pmatrix} \mathbf{P} & \mathbf{I}_m \end{pmatrix}$

여기서

\mathbf{I}_k

와

\mathbf{I}_m

은 각각

k \times k

및

m \times m

크기의 단위 행렬이고,

\mathbf{P}

는

k \times m

크기의 특정 행렬이다. 조직 부호 형태의 생성 행렬을 사용하면, 생성된 부호어

\vec{x}

안에 원본 데이터 비트

\vec{a}

가 그대로 포함되어 나타나는 장점이 있다.

예를 들어, 원본 소스에서 제시된 (7,4) 해밍 부호 (m=3, n=7, k=4)의 조직 부호 형태 생성 행렬

\mathbf{G}

와 패리티 검사 행렬

\mathbf{H}

는 다음과 같다.

:

\mathbf{G} := \begin{pmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \\0 & 1 & 0 & 0 & 1 & 0 & 1 \\0 & 0 & 1 & 0 & 0 & 1 & 1 \\0 & 0 & 0 & 1 & 1 & 1 & 1\end{pmatrix}_{4,7}

:

\mathbf{H} := \begin{pmatrix}1 & 1 & 0 & 1 & 1 & 0 & 0 \\1 & 0 & 1 & 1 & 0 & 1 & 0 \\0 & 1 & 1 & 1 & 0 & 0 & 1\end{pmatrix}_{3,7}

(참고: 여기서

\mathbf{G} = \begin{pmatrix} \mathbf{I}_4 & \mathbf{P}^\text{T} \end{pmatrix}

이고

\mathbf{P}^\text{T} = \begin{pmatrix} 1&1&0 \\ 1&0&1 \\ 0&1&1 \\ 1&1&1 \end{pmatrix}

이다.

\mathbf{H}

는

\begin{pmatrix} \mathbf{A} & \mathbf{I}_3 \end{pmatrix}

형태는 아니지만,

\mathbf{H} \mathbf{G}^\text{T} = \mathbf{0}

관계를 만족하는 유효한 패리티 검사 행렬이다.)

이 생성 행렬

\mathbf{G}

를 사용하여 4비트 데이터

\vec{a} = [1, 0, 1, 1]

를 부호화하는 과정은 다음과 같다.

:

\vec{x} = \vec{a}\mathbf{G} =\begin{pmatrix} 1 & 0 & 1 & 1 \end{pmatrix}\begin{pmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \\0 & 1 & 0 & 0 & 1 & 0 & 1 \\0 & 0 & 1 & 0 & 0 & 1 & 1 \\0 & 0 & 0 & 1 & 1 & 1 & 1 \\\end{pmatrix}

:

= \begin{pmatrix}(1\cdot1 \oplus 0\cdot0 \oplus 1\cdot0 \oplus 1\cdot0) &(1\cdot0 \oplus 0\cdot1 \oplus 1\cdot0 \oplus 1\cdot0) &(1\cdot0 \oplus 0\cdot0 \oplus 1\cdot1 \oplus 1\cdot0) &(1\cdot0 \oplus 0\cdot0 \oplus 1\cdot0 \oplus 1\cdot1) &(1\cdot1 \oplus 0\cdot1 \oplus 1\cdot0 \oplus 1\cdot1) &(1\cdot1 \oplus 0\cdot0 \oplus 1\cdot1 \oplus 1\cdot1) &(1\cdot0 \oplus 0\cdot1 \oplus 1\cdot1 \oplus 1\cdot1)\end{pmatrix}

:

= \begin{pmatrix} (1\oplus 0\oplus 0\oplus 0) & (0\oplus 0\oplus 0\oplus 0) & (0\oplus 0\oplus 1\oplus 0) & (0\oplus 0\oplus 0\oplus 1) & (1\oplus 0\oplus 0\oplus 1) & (1\oplus 0\oplus 1\oplus 1) & (0\oplus 0\oplus 1\oplus 1) \end{pmatrix}

:

= \begin{pmatrix} 1 & 0 & 1 & 1 & (1\oplus 1) & (1\oplus 1\oplus 1) & (1\oplus 1) \end{pmatrix}

:

= \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 1 & 0 \end{pmatrix}

따라서 원본 데이터 1011은 (7,4) 해밍 부호로 부호화되어 1011010 이라는 7비트 부호어가 된다. 이 부호어는 전송 과정에서 발생할 수 있는 단일 비트 오류를 수신 측에서 검출하고 정정할 수 있게 한다.

4. 2. 복호화 및 오류 정정

수신된 부호어에 오류가 있는지 확인하고, 있다면 어느 비트에 오류가 발생했는지 찾아 수정하기 위해 검사 행렬 H를 사용한다.

수신된 부호어(데이터)를 Y라고 할 때, Y와 검사 행렬 H의 전치 행렬인

H^T

를 곱한다. 이때 모든 계산 과정에서의 덧셈은 배타적 논리합(XOR) 연산을 사용한다.

Y H^T

계산 결과가 영 벡터(모든 원소가 0인 벡터)이면 오류가 없는 것으로 판단한다. 만약 결과가 영 벡터가 아니면, 이 결과값을 '''오류 증후군'''(Syndrome)이라고 부르며, 이 값은 오류가 발생한 비트의 위치를 알려준다.

오류 증후군 벡터는 검사 행렬 H의 특정 열과 일치하게 된다. 이 일치하는 열의 번호가 바로 오류가 발생한 비트의 위치이다. 예를 들어, (7,4) 해밍 부호에서 오류 증후군이

\begin{bmatrix} 0 & 1 & 1 \end{bmatrix}

으로 계산되었다면, 이는 검사 행렬 H의 2번째 열인

\begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}

과 일치하므로, 수신된 부호어의 2번째 비트에 오류가 있음을 의미한다. 오류 위치를 찾으면 해당 비트의 값을 반전시켜(0은 1로, 1은 0으로) 오류를 정정한다.

만약 단 하나의 패리티 비트만 오류를 나타낸다면, 이는 해당 패리티 비트 자체에 오류가 발생했음을 의미한다.

'''예시'''

(7,4) 해밍 부호에서 특정 부호어가 전송되었으나, 오류가 발생하여

\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 & 0 \end{pmatrix}

가 수신되었다고 가정해 보자. 이때 사용된 검사 행렬 H는 다음과 같다.

H =\begin{bmatrix}1 & 0 & 1 & 1 & 1 & 0 & 0 \\1 & 1 & 0 & 1 & 0 & 1 & 0 \\0 & 1 & 1 & 1 & 0 & 0 & 1 \\\end{bmatrix}

수신된 데이터 Y와 H의 전치 행렬

H^T

의 곱(오류 증후군)을 계산하면 다음과 같다.

Y H^T = \begin{bmatrix}1 & 1 & 1 & 1 & 1 & 0 & 0 \\\end{bmatrix}\begin{bmatrix}1 & 1 & 0 \\0 & 1 & 1 \\1 & 0 & 1 \\1 & 1 & 1 \\1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \\\end{bmatrix} =\begin{bmatrix}(1\cdot1 \oplus 1\cdot0 \oplus 1\cdot1 \oplus 1\cdot1 \oplus 1\cdot1 \oplus 0\cdot0 \oplus 0\cdot0) & (1\cdot1 \oplus 1\cdot1 \oplus 1\cdot0 \oplus 1\cdot1 \oplus 1\cdot0 \oplus 0\cdot1 \oplus 0\cdot0) & (1\cdot0 \oplus 1\cdot1 \oplus 1\cdot1 \oplus 1\cdot1 \oplus 1\cdot0 \oplus 0\cdot0 \oplus 0\cdot1) \\\end{bmatrix} =\begin{bmatrix}(1 \oplus 0 \oplus 1 \oplus 1 \oplus 1 \oplus 0 \oplus 0) & (1 \oplus 1 \oplus 0 \oplus 1 \oplus 0 \oplus 0 \oplus 0) & (0 \oplus 1 \oplus 1 \oplus 1 \oplus 0 \oplus 0 \oplus 0) \\\end{bmatrix} =\begin{bmatrix}0 & 1 & 1 \\\end{bmatrix}

계산된 오류 증후군

\begin{bmatrix} 0 & 1 & 1 \end{bmatrix}

는 검사 행렬 H의 2번째 열

\begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}

과 일치한다. 따라서 수신된 부호어의 2번째 비트에 오류가 있음을 알 수 있다.

수신된 부호어

\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 & 0 \end{pmatrix}

의 2번째 비트(1)를 반전시키면

\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \end{pmatrix}

이 되어 오류가 정정된 부호어를 얻는다.

오류가 정정된 부호어에서 원래의 데이터 비트들을 추출한다. 만약 조직 부호 형태로 부호화되었다면, 생성 행렬 G가

G = [ I_k | A^T ]

형태(여기서

I_k

는 k x k 단위 행렬)를 가지므로, 정정된 부호어의 앞쪽 k개의 비트가 원래 데이터에 해당한다. 위의 예시 (7,4) 해밍 부호의 경우, 정정된 부호어

\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \end{pmatrix}

에서 앞의 4비트인

\begin{pmatrix} 1 & 0 & 1 & 1 \end{pmatrix}

이 원래의 데이터가 된다.

5. 역사

리처드 해밍은 1950년에 해밍 부호를 발표했다.^[5] 그는 1940년대 벨 연구소에서 전기 기계식 릴레이로 만들어진 초기 컴퓨터인 벨 모델 V(Bell Model V^영어)를 사용하여 작업하고 있었다. 이 컴퓨터는 입력 방식으로 천공 카드나 천공 종이 테이프를 사용했는데, 이 때문에 입력 데이터에 오류가 발생할 가능성이 늘 존재했다.

주중에는 컴퓨터 관리자가 상주하며 오류가 발생하면 경고등을 보고 직접 수정할 수 있었지만, 관리자가 없는 주말에는 오류가 발생하면 프로그램 실행이 중단되고 다음 작업으로 넘어가 버리는 일이 잦았다. 주말에도 연구 작업을 계속했던 해밍은 이러한 문제로 인해 작업 내용을 처음부터 다시 시작해야 하는 상황에 반복적으로 부딪히면서 큰 불편을 겪었다.

해밍은 "기계가 오류를 감지할 수 있다면, 왜 오류 위치를 찾아 스스로 수정할 수는 없는가?"^[2]라는 의문을 품고 근본적인 해결책을 찾기 위해 노력했다. 그는 몇 년 동안 오류 정정 부호 문제를 연구하며 점점 더 강력한 알고리즘들을 개발했고, 마침내 1950년에 현재 해밍 부호로 알려진 것을 발표했다. 이 연구는 선형 부호 이론의 시작으로 평가받으며, 해밍 부호는 현재 ECC 메모리와 같은 여러 분야에서 중요한 기술로 사용되고 있다.

5. 1. 해밍 이전의 부호

해밍 부호가 등장하기 전에도 여러 가지 간단한 오류 검출 부호가 사용되었지만, 동일한 오버헤드를 가지면서 해밍 부호만큼 효과적인 부호는 없었다.

=== 패리티 비트 ===

패리티는 데이터 비트들에 추가되는 단일 비트로, 데이터 내 1의 개수(값이 1인 비트의 수)가 짝수인지 홀수인지를 나타낸다. 만약 전송 과정에서 홀수 개의 비트가 바뀌면, 전체 비트열의 패리티가 변하게 되어 오류 발생을 감지할 수 있다. 하지만 바뀐 비트가 패리티 비트 자신일 수도 있다. 일반적으로 패리티 비트 값이 1이면 데이터에 홀수 개의 1이 있다는 뜻이고, 0이면 짝수 개의 1이 있다는 뜻이다. 만약 짝수 개의 비트가 변경되면 패리티 비트는 변하지 않아 오류를 감지할 수 없다.

또한, 패리티 방식은 오류를 감지하더라도 어느 비트에서 오류가 발생했는지는 알려주지 못한다. 따라서 오류가 감지되면 데이터를 폐기하고 처음부터 다시 전송해야 한다. 전송 환경이 좋지 않으면 성공적인 전송에 오랜 시간이 걸리거나 실패할 수도 있다. 패리티 검사는 성능이 뛰어나지는 않지만, 단 하나의 비트만 추가하므로 오버헤드가 가장 적다는 장점이 있다.

=== 2-5 코드 ===

2-5 코드는 다섯 개의 비트 중 정확히 두 개의 비트만 1이고 나머지 세 개의 비트는 0으로 구성하는 부호화 방식이다. 이 방식으로는

\binom{5}{2}=10

가지의 조합이 가능하여, 숫자 0부터 9까지를 표현하는 데 사용될 수 있다. 2-5 코드는 모든 단일 비트 오류와 모든 홀수 개 비트 오류를 감지할 수 있다. 또한, 두 개의 1 비트가 모두 0으로 바뀌는 것과 같은 일부 짝수 개 비트 오류도 감지할 수 있다. 하지만 이러한 오류들을 수정하는 기능은 없다.

=== 반복 코드 ===

당시에 사용된 또 다른 방식은 데이터 비트를 여러 번 반복하여 전송하는 반복 코드이다. 예를 들어, 전송하려는 데이터 비트가 '1'이라면, 3번 반복하는(삼중 모듈러 중복) 코드는 '111'을 전송한다. 만약 수신된 세 비트가 모두 같지 않다면 전송 중 오류가 발생한 것으로 간주한다. 채널 상태가 비교적 양호하다면, 대부분의 경우 세 비트 중 하나만 오류가 발생할 가능성이 높다. 따라서 '001', '010', '100'은 원래 비트가 '0'이었음을 의미하고, '110', '101', '011'은 원래 비트가 '1'이었음을 의미한다고 해석할 수 있다. 즉, 수신된 비트들 중 더 많이 나타나는 값('0' 또는 '1')을 원래 데이터 비트로 판단하는 것이다. 이처럼 오류가 발생해도 원래 메시지를 복원할 수 있는 코드를 오류 정정 부호라고 한다. 이 3중 반복 코드는 일종의 해밍 부호로 볼 수도 있는데, 패리티 비트가 2개(''m'' = 2)이고 데이터 비트가 1개(2² − 2 − 1 = 1)인 경우에 해당한다.

그러나 반복 코드가 모든 오류를 완벽하게 수정할 수 있는 것은 아니다. 예를 들어 채널에서 두 개의 비트가 바뀌어 수신기가 '001'을 받았다면, 시스템은 오류를 감지하지만 원래 비트가 '0'이라고 잘못 판단하게 된다. 비트 수를 4개로 늘리면 모든 2비트 오류를 감지할 수는 있지만 수정은 불가능하다. 5개로 늘리면 모든 2비트 오류를 감지하고 수정할 수 있지만, 모든 3비트 오류는 수정할 수 없다.

게다가 반복 횟수를 늘리는 것은 매우 비효율적이다. 비트를 3번 반복하는 것만으로도 전송 효율은 1/3로 줄어들며, 더 많은 오류를 감지하고 수정하기 위해 반복 횟수를 늘릴수록 효율성은 급격히 떨어진다.

6. 응용

1950년 벨 연구소의 리처드 해밍이 고안한 해밍 부호는 알려진 오류 정정 부호 중 가장 오래된 것 중 하나이다. 블록당 1 비트의 오류를 정정할 수 있으며, 리드-솔로몬 부호 등 다른 부호에 비해 비교적 빠른 속도로 처리할 수 있다는 장점이 있지만, 오류 정정 능력은 상대적으로 높지 않다. 이러한 특징 때문에 오류 발생률이 낮으면서도 빠른 처리 속도가 요구되는 분야에 주로 사용된다. 대표적인 예로는 ECC 메모리나 RAID 2가 있으며, 파일 압축 프로그램인 WinRAR의 복구 레코드에도 활용된다.

7. 예시

해밍 부호는 다양한 파라미터와 진법에 따라 여러 종류로 구현될 수 있다. 주요 예시는 다음과 같다.

'''이진 2-해밍 부호 (삼중 반복 부호)''': 가장 간단한 형태로, 비트 하나를 세 번 반복하여 전송하는 삼중 반복 부호와 동일하다. 이를 통해 1비트 오류를 검출하고 수정할 수 있다.
'''이진 3-해밍 부호''': 가장 널리 사용되는 [7,4,3] 해밍 부호가 여기에 속한다. 4비트 데이터에 3비트의 패리티 비트를 추가하여 7비트 부호어를 만들며, 최소 거리 3을 가져 1개의 오류를 수정할 수 있다. 전체 패리티 비트를 하나 더 추가하여 최소 거리를 4로 늘린 [8,4] 확장 해밍 부호로 만들 수도 있는데, 이는 1개 오류 수정 능력은 유지하면서 2개 오류 검출 능력을 추가로 갖는다.
'''삼진 2-해밍 부호''': 이진법뿐만 아니라 삼진법과 같은 다른 진법 위에서도 해밍 부호를 정의할 수 있다. 삼진 2-해밍 부호는 유한체 $\mathbb F_3 = \{0, 1, 2\}$ 상에서 정의되는 예시이다.

7. 1. 이진 2-해밍 부호 (삼중 반복 부호)

r=2

일 때의 이진 해밍 부호는 '''삼중 반복 부호'''(triple repetition code^영어)와 같다. 이 부호는 다음과 같은 방식으로 작동한다.

송신: 전송하려는 비트 하나를 세 번 반복하여 보낸다. 예를 들어 '0'을 보내려면 '000'을, '1'을 보내려면 '111'을 전송한다.
수신:
* 세 비트가 모두 같다면 (예: '000' 또는 '111'), 오류 없이 수신된 것으로 간주한다.
* 세 비트 중 하나만 다르다면 (예: '010', '110', '001' 등), 다른 두 비트와 같은 값으로 수정한다. 예를 들어 '010'을 수신했다면, '0'이 두 개이므로 원래 비트는 '0'이었을 것이라 판단하고 '000'으로 교정한다.

이 부호의 생성 행렬(

G

)과 표준형 패리티 확인 행렬(

H

)은 다음과 같다.

:

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

:

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

7. 2. 이진 3-해밍 부호

2 이상의 정수

r

에 대해

[2^r-1, 2^r-1-r, 3]_2

해밍 부호를 정의할 수 있다. 이 부호는

\mathbb F_2

상의 이진 선형 부호이며, 패리티 확인 행렬

H

는

r \times (2^r-1)

크기를 가진다. 행렬

H

의

j

번째 열은

j

를 이진법으로 나타낸 것이다.

가장 널리 사용되는 해밍 부호는

r=3

인 경우로, 이를 [7,4,3] 해밍 부호 또는 간단히 [7,4] 해밍 부호라고 부른다. 이 부호는 7비트 부호어(codeword)를 사용하여 4비트 데이터를 표현하며, 최소 거리 3을 가지므로 최대 1개의 오류를 검출하고 수정할 수 있다.

r=3

일 때, 패리티 확인 행렬

H

는 다음과 같다.

:

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}

[7,4] 해밍 부호의 표준형 패리티 확인 행렬

H

와 이에 대응하는 생성 행렬

G

는 각각 다음과 같다.

:

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}

:

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}

(생성 행렬

G

는

H \cdot G^T = 0

을 만족한다.)

추가 패리티 비트를 갖는 [7,4] 해밍 부호 예시. 이 다이어그램은 본문의 행렬 H와 직접 대응하지는 않음.

[7,4] 해밍 부호는 부호어 전체에 대한 추가 패리티 비트를 하나 더 포함하여 [8,4] 확장 해밍 부호로 확장될 수 있다. 이 추가된 패리티 비트는 보통 부호어의 모든 비트의 합(XOR 연산)이 0 (짝수 패리티)이 되도록 설정된다. 이 확장을 통해 최소 거리가 3에서 4로 증가하여, 1개의 오류를 수정하는 능력은 유지하면서 2개의 오류를 검출할 수 있게 된다.

[8,4] 확장 해밍 부호의 생성 행렬

G

와 패리티 확인 행렬

H

의 한 예는 다음과 같다 (비표준형).

:

\mathbf{G} := \begin{pmatrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\1 & 0 & 0 & 1 & 1 & 0 & 0 & 1\\0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\1 & 1 & 0 & 1 & 0 & 0 & 1 & 0\end{pmatrix}_{4,8}

그리고

:

\mathbf{H} :=\begin{pmatrix}1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\0 & 0 & 0 & 1 & 1 & 1 & 1 & 0\\1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{pmatrix}_{4,8}.

위 패리티 확인 행렬

H

는 표준형(systematic form)이 아니다. 기본 행 연산을 사용하여 다음과 같은 표준형 패리티 확인 행렬과 동등한 행렬을 얻을 수 있다.

:

\mathbf{H} =\left( \begin{array}{cccc|cccc}0 & 1 & 1 & 1  &  1 & 0 & 0 & 0 \\1 & 0 & 1 & 1  &  0 & 1 & 0 & 0 \\1 & 1 & 0 & 1  &  0 & 0 & 1 & 0 \\1 & 1 & 1 & 0  &  0 & 0 & 0 & 1 \end{array} \right)_{4,8}.

이 표준형 패리티 확인 행렬에 대응하는 생성 행렬

G

의 표준형은 다음과 같다.

:

\mathbf{G} =\left( \begin{array}{cccc|cccc}1 & 0 & 0 & 0  &  0 & 1 & 1 & 1 \\0 & 1 & 0 & 0  &  1 & 0 & 1 & 1 \\0 & 0 & 1 & 0  &  1 & 1 & 0 & 1 \\0 & 0 & 0 & 1  &  1 & 1 & 1 & 0 \end{array} \right)_{4,8}.

예를 들어, 데이터

1011

은 원본 소스에서 제시된 특정 비표준형 생성 행렬

G

를 사용하여

01100110

으로 부호화될 수 있다. 이 8비트 부호어는 4비트 데이터 정보, 3비트의 [7,4] 해밍 부호 패리티 비트, 그리고 1비트의 추가 전체 패리티 비트로 구성된다 (비트의 순서는 사용된 생성 행렬에 따라 달라짐). 추가된 전체 패리티 비트는 부호어의 총 비트 수가 짝수가 되도록 한다.

[8,4] 확장 해밍 부호를 해독하려면 먼저 전체 패리티 비트를 확인한다.

전체 패리티 비트가 올바른 경우: 오류가 없거나, 2개의 오류가 발생한 경우이다. 이후 [7,4] 해밍 부호의 오류 검사(신드롬 계산)를 수행한다.
신드롬이 0이면 오류가 없는 것으로 간주한다.
신드롬이 0이 아니면, 2개의 오류가 발생했음을 나타낸다 (오류 위치는 신드롬 값과 직접적으로 연관되지 않을 수 있음).
전체 패리티 비트가 틀린 경우: 1개의 오류가 발생한 경우이다. [7,4] 해밍 부호의 오류 검사(신드롬 계산)를 통해 오류가 발생한 비트의 위치를 찾는다.
신드롬이 가리키는 위치가 데이터 비트 또는 [7,4] 패리티 비트 중 하나이면 해당 비트를 수정한다.
신드롬이 0인데 전체 패리티 비트가 틀렸다면, 오류는 추가된 전체 패리티 비트 자체에 발생한 것이므로 해당 비트를 수정한다.

7. 3. 삼진 2-해밍 부호

해밍 부호는 이진법뿐만 아니라 다른 진법 위에서도 정의될 수 있다. 여기서는 삼진법 (

q=3

)을 사용하는 해밍 부호의 한 예시로,

r=2

인 경우, 즉 '''삼진 2-해밍 부호'''를 설명한다. 이 부호는 유한체

\mathbb F_3 = \{0, 1, 2\}

위에서 정의된다.

먼저 벡터 공간

\mathbb F_3^2

를 고려한다. 여기서 영벡터

\vec 0 = (0,0)

을 제외한 벡터들의 집합

\mathbb F_3^2\setminus\{\vec 0\}

은 다음과 같다.

:

(0,1), (0,2), (1,0), (2,0), (1,1), (2,2), (1,2), (2,1)

이 벡터들을 이용하여 사영 직선

\mathbb P^1_{\mathbb F_3}

을 구성한다. 이는

\mathbb F_3^2\setminus\{\vec 0\}

의 원소들 사이에 동치 관계

u \sim v \iff \exists \lambda \in \mathbb F_3^\times : u = \lambda v

(여기서

\mathbb F_3^\times = \{1, 2\}

)를 정의하고, 이 관계에 따른 동치류들의 집합으로 정의된다. 동치류들은 다음과 같이 네 개가 존재한다.

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

각 동치류에서 대표 벡터를 하나씩 선택하여 열벡터로 사용하면 패리티 확인 행렬

H

를 만들 수 있다. 예를 들어, 각 동치류에서 특정 대표원들을 선택하고 배열하면 다음과 같은 표준형 패리티 확인 행렬을 얻을 수 있다.

:

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

이 행렬

H

를 패리티 확인 행렬로 갖는 선형 부호

C = \ker H

가 삼진 2-해밍 부호이다. 이 부호의 표준형 생성 행렬

G

는 다음과 같다.

:

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

8. 일반 알고리즘

(3중 반복 코드)1/3 ≈ 0.333374해밍(7,4)4/7 ≈ 0.57141511해밍(15,11)11/15 ≈ 0.73353126해밍(31,26)26/31 ≈ 0.83966357해밍(63,57)57/63 ≈ 0.9057127120해밍(127,120)120/127 ≈ 0.9458255247해밍(255,247)247/255 ≈ 0.9699511502해밍(511,502)502/511 ≈ 0.982...............m2^m-12^m-m-1해밍(2^m-1, 2^m-m-1)(2^m - m - 1)/(2^m-1)

해밍 부호

1. 개요

더 읽어볼만한 페이지

2. 정의

2. 1. 이진 해밍 부호

2. 2. 임의의 진법의 해밍 부호

2. 3. 확장 해밍 부호

3. 성질

3. 1. 가짓수

3. 2. 최적성

4. 기본 개념

4. 1. 부호화

4. 2. 복호화 및 오류 정정

5. 역사

5. 1. 해밍 이전의 부호

6. 응용

7. 예시

7. 1. 이진 2-해밍 부호 (삼중 반복 부호)

7. 2. 이진 3-해밍 부호

7. 3. 삼진 2-해밍 부호

8. 일반 알고리즘

9. 추가 패리티를 사용한 해밍 부호 (SECDED)

10. [7,4] 해밍 부호

11. [8,4] 해밍 부호

참조