해밍 부호

1. 개요

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

2. 정의

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

데이터에 오류 정정 비트를 포함시키고, 이 비트들을 특정 규칙에 따라 배열하면, 어떤 비트에서 오류가 발생했는지 식별하는 것이 가능하다. 예를 들어, 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\; \backslash in\; \backslash \{2,\; 3,\; 4,\; \backslash dots\backslash \}$)을 하나 선택한다. 그리고 체 $\backslash mathbb\{F\}\_2\; =\; \backslash \{0,\; 1\backslash \}$ 위에서 다음과 같은 $r\; \backslash 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\; =\; \backslash 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\; =\; \backslash ker\; H\; =\; \backslash \{\; \backslash mathbf\{x\}\; \backslash in\; \backslash mathbb\{F\}\_2^\{2^r-1\}\; \backslash mid\; H\backslash mathbf\{x\}^\backslash mathsf\{T\}\; =\; \backslash mathbf\{0\}\; \backslash \}$와 같이 나타낼 수 있다. 여기서 $\backslash mathbf\{x\}^\backslash mathsf\{T\}$는 벡터 $\backslash 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$이면 삼진법 해밍 부호가 된다.

이때 유한체 $\backslash mathbb\; F\_q$ (크기가 $q$인 유한체) 위의 $r$차원 벡터 공간 $\backslash mathbb\; F\_q^r$을 생각한다. 이 벡터 공간에서 영벡터($\backslash vec\; 0$)를 제외한 벡터들에 대해, 한 벡터가 다른 벡터의 0이 아닌 스칼라배와 같으면 같은 것으로 간주하는 관계를 정의한다 ($u\backslash sim\; v\backslash iff\backslash exists\backslash lambda\backslash in\backslash mathbb\; F\_q^\backslash times\backslash colon\; u=\backslash lambda\; v$). 이 관계에 따라 벡터들을 묶어 $r-1$차원 사영 공간 $\backslash mathbb\; P^\{r-1\}\_\{\backslash mathbb\; F\_q\}$을 구성할 수 있다. 이 사영 공간은 서로 다른 '방향'을 나타내는 점들의 집합으로 볼 수 있으며, 점의 개수는 다음과 같다.
:$\backslash frac$

해밍 부호의 부호화 및 복호화 과정은 주로 두 개의 행렬, 즉 생성 행렬(Generator matrix) $\backslash mathbf\{G\}$와 패리티 검사 행렬(Parity-check matrix) $\backslash mathbf\{H\}$를 사용하여 수행된다. 생성 행렬 $\backslash mathbf\{G\}$는 $k$ 비트의 원본 데이터를 $n$ 비트의 부호어로 변환하는 데 사용되고, 패리티 검사 행렬 $\backslash 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\; \backslash times\; n$ 크기의 생성 행렬(Generator matrix) $\backslash mathbf\{G\}$를 사용하여 이루어진다. 부호화는 $1\; \backslash times\; k$ 크기의 원본 데이터 행 벡터 $\backslash vec\{a\}$와 생성 행렬 $\backslash mathbf\{G\}$를 곱하여 $1\; \backslash times\; n$ 크기의 부호어 행 벡터 $\backslash vec\{x\}$를 얻는 과정이다.
:$\backslash vec\{x\}\; =\; \backslash vec\{a\}\; \backslash mathbf\{G\}$
이때 행렬 곱셈 과정에서의 모든 덧셈 연산은 모듈로 2 덧셈, 즉 배타적 논리합(XOR)으로 수행된다.

생성 행렬 $\backslash mathbf\{G\}$는 $m\; \backslash times\; n$ 크기의 패리티 검사 행렬(Parity-check matrix) $\backslash mathbf\{H\}$와 다음의 관계를 만족한다.
:$\backslash mathbf\{H\}\; \backslash mathbf\{G\}^\backslash text\{T\}\; =\; \backslash mathbf\{0\}$
여기서 $\backslash mathbf\{G\}^\backslash text\{T\}$는 $\backslash mathbf\{G\}$의 전치 행렬이고, $\backslash mathbf\{0\}$은 모든 원소가 0인 $m\; \backslash times\; k$ 크기의 영행렬이다.

계산의 편의성과 구현의 간결성을 위해 종종 조직 부호(Systematic code) 형태의 행렬이 사용된다. 조직 부호 형태에서 생성 행렬 $\backslash mathbf\{G\}$와 패리티 검사 행렬 $\backslash mathbf\{H\}$는 일반적으로 다음과 같은 구조를 가진다.
*
*

여기서 $\backslash mathbf\{I\}\_k$와 $\backslash mathbf\{I\}\_m$은 각각 $k\; \backslash times\; k$ 및 $m\; \backslash times\; m$ 크기의 단위 행렬이고, $\backslash mathbf\{P\}$는 $k\; \backslash times\; m$ 크기의 특정 행렬이다. 조직 부호 형태의 생성 행렬을 사용하면, 생성된 부호어 $\backslash vec\{x\}$ 안에 원본 데이터 비트 $\backslash vec\{a\}$가 그대로 포함되어 나타나는 장점이 있다.

예를 들어, 원본 소스에서 제시된 (7,4) 해밍 부호 (m=3, n=7, k=4)의 조직 부호 형태 생성 행렬 $\backslash mathbf\{G\}$와 패리티 검사 행렬 $\backslash mathbf\{H\}$는 다음과 같다.
:$\backslash mathbf\{G\}\; :=\; \backslash 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}
:$\backslash mathbf\{H\}\; :=\; \backslash 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}
(참고: 여기서 이고 이다. $\backslash mathbf\{H\}$는 형태는 아니지만, $\backslash mathbf\{H\}\; \backslash mathbf\{G\}^\backslash text\{T\}\; =\; \backslash mathbf\{0\}$ 관계를 만족하는 유효한 패리티 검사 행렬이다.)

이 생성 행렬 $\backslash mathbf\{G\}$를 사용하여 4비트 데이터 $\backslash vec\{a\}\; =\; [1,\; 0,\; 1,\; 1]$를 부호화하는 과정은 다음과 같다.
:$\backslash vec\{x\}\; =\; \backslash vec\{a\}\backslash 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}
:$=\; \backslash 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}
:
:
:

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

4.2. 복호화 및 오류 정정

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

수신된 부호어(데이터)를 Y라고 할 때, Y와 검사 행렬 H의 전치 행렬인 $H^T$를 곱한다. 이때 모든 계산 과정에서의 덧셈은 배타적 논리합(XOR) 연산을 사용한다.

$Y\; H^T$

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

오류 증후군 벡터는 검사 행렬 H의 특정 열과 일치하게 된다. 이 일치하는 열의 번호가 바로 오류가 발생한 비트의 위치이다. 예를 들어, (7,4) 해밍 부호에서 오류 증후군이 으로 계산되었다면, 이는 검사 행렬 H의 2번째 열인 $\backslash begin\{bmatrix\}\; 0\; \backslash \backslash \; 1\; \backslash \backslash \; 1\; \backslash end\{bmatrix\}$과 일치하므로, 수신된 부호어의 2번째 비트에 오류가 있음을 의미한다. 오류 위치를 찾으면 해당 비트의 값을 반전시켜(0은 1로, 1은 0으로) 오류를 정정한다.

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

예시

(7,4) 해밍 부호에서 특정 부호어가 전송되었으나, 오류가 발생하여 가 수신되었다고 가정해 보자. 이때 사용된 검사 행렬 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\; =\; \backslash 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}
계산된 오류 증후군 는 검사 행렬 H의 2번째 열 $\backslash begin\{bmatrix\}\; 0\; \backslash \backslash \; 1\; \backslash \backslash \; 1\; \backslash end\{bmatrix\}$과 일치한다. 따라서 수신된 부호어의 2번째 비트에 오류가 있음을 알 수 있다.
수신된 부호어 의 2번째 비트(1)를 반전시키면 이 되어 오류가 정정된 부호어를 얻는다.

오류가 정정된 부호어에서 원래의 데이터 비트들을 추출한다. 만약 조직 부호 형태로 부호화되었다면, 생성 행렬 G가 $G\; =\; [\; I\_k\; |\; A^T\; ]$ 형태(여기서 $I\_k$는 k x k 단위 행렬)를 가지므로, 정정된 부호어의 앞쪽 k개의 비트가 원래 데이터에 해당한다. 위의 예시 (7,4) 해밍 부호의 경우, 정정된 부호어 에서 앞의 4비트인 이 원래의 데이터가 된다.

5. 역사

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

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

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

5.1. 해밍 이전의 부호

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

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

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

=== 2-5 코드 ===
2-5 코드는 다섯 개의 비트 중 정확히 두 개의 비트만 1이고 나머지 세 개의 비트는 0으로 구성하는 부호화 방식이다. 이 방식으로는 $\backslash 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-해밍 부호는 유한체 $\backslash mathbb\; F\_3\; =\; \backslash \{0,\; 1,\; 2\backslash \}$ 상에서 정의되는 예시이다.

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

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

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

이 부호의 생성 행렬($G$)과 표준형 패리티 확인 행렬($H$)은 다음과 같다.
:$G=\backslash begin\{pmatrix\}$
1\\
1\\
1
\end{pmatrix}
:$H=\backslash begin\{pmatrix\}$
1&1&0\\
1&0&1
\end{pmatrix}

7.2. 이진 3-해밍 부호

2 이상의 정수 $r$에 대해 $[2^r-1,\; 2^r-1-r,\; 3]\_2$ 해밍 부호를 정의할 수 있다. 이 부호는 $\backslash mathbb\; F\_2$ 상의 이진 선형 부호이며, 패리티 확인 행렬 $H$는 $r\; \backslash 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\; =\; \backslash 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\; =\; \backslash 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\; \backslash cdot\; G^T\; =\; 0$을 만족한다.)

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

[8,4] 확장 해밍 부호의 생성 행렬 $G$와 패리티 확인 행렬 $H$의 한 예는 다음과 같다 (비표준형).
:$\backslash mathbf\{G\}\; :=\; \backslash 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-해밍 부호를 설명한다. 이 부호는 유한체 $\backslash mathbb\; F\_3\; =\; \backslash \{0,\; 1,\; 2\backslash \}$ 위에서 정의된다.

먼저 벡터 공간 $\backslash mathbb\; F\_3^2$를 고려한다. 여기서 영벡터 $\backslash vec\; 0\; =\; (0,0)$을 제외한 벡터들의 집합 $\backslash mathbb\; F\_3^2\backslash setminus\backslash \{\backslash vec\; 0\backslash \}$은 다음과 같다.
:$(0,1),\; (0,2),\; (1,0),\; (2,0),\; (1,1),\; (2,2),\; (1,2),\; (2,1)$

이 벡터들을 이용하여 사영 직선 $\backslash mathbb\; P^1\_\{\backslash mathbb\; F\_3\}$을 구성한다. 이는 $\backslash mathbb\; F\_3^2\backslash setminus\backslash \{\backslash vec\; 0\backslash \}$의 원소들 사이에 동치 관계 $u\; \backslash sim\; v\; \backslash iff\; \backslash exists\; \backslash lambda\; \backslash in\; \backslash mathbb\; F\_3^\backslash times\; :\; u\; =\; \backslash lambda\; v$ (여기서 $\backslash mathbb\; F\_3^\backslash times\; =\; \backslash \{1,\; 2\backslash \}$)를 정의하고, 이 관계에 따른 동치류들의 집합으로 정의된다. 동치류들은 다음과 같이 네 개가 존재한다.
* $\backslash \{(0,1),\; (0,2)\backslash \}$
* $\backslash \{(1,0),\; (2,0)\backslash \}$
* $\backslash \{(1,1),\; (2,2)\backslash \}$
* $\backslash \{(1,2),\; (2,1)\backslash \}$

각 동치류에서 대표 벡터를 하나씩 선택하여 열벡터로 사용하면 패리티 확인 행렬 $H$를 만들 수 있다. 예를 들어, 각 동치류에서 특정 대표원들을 선택하고 배열하면 다음과 같은 표준형 패리티 확인 행렬을 얻을 수 있다.
:$H=\backslash begin\{pmatrix\}$
1&1&1&0\\
1&2&0&1
\end{pmatrix}

이 행렬 $H$를 패리티 확인 행렬로 갖는 선형 부호 $C\; =\; \backslash ker\; H$가 삼진 2-해밍 부호이다. 이 부호의 표준형 생성 행렬 $G$는 다음과 같다.
:$G=\backslash begin\{pmatrix\}$
1&0\\
0&1\\
2&2\\
2&1
\end{pmatrix}

8. 일반 알고리즘

다음은 임의의 비트 수에 대한 단일 오류 정정(SEC) 코드를 생성하는 일반적인 알고리즘이다. 이 알고리즘의 핵심 아이디어는 오류 정정 비트(패리티 비트)를 특정 위치에 배치하고, 그 값을 조절하여 특정 규칙(모든 1 값을 가진 비트 위치들의 XOR 결과가 0이 되도록 함)을 만족시키는 것이다. 이를 통해 수신된 메시지에 오류가 있는지, 있다면 어느 비트에서 발생했는지 식별할 수 있다.

알고리즘은 다음 단계로 구성된다.

# 비트 위치 번호를 1부터 매긴다: 1, 2, 3, 4, 5, 6, 7, ...
# 각 비트 위치 번호를 이진수로 표현한다: 1, 10, 11, 100, 101, 110, 111, ...
# 비트 위치 번호가 2의 거듭제곱인 위치(이진수 표현에서 1이 하나만 있는 위치)는 패리티 비트가 된다: 위치 1(1), 2(10), 4(100), 8(1000), 16(10000), ...
# 나머지 위치(이진수 표현에서 1이 두 개 이상 있는 위치)는 데이터 비트가 된다: 위치 3(11), 5(101), 6(110), 7(111), 9(1001), ...
# 각 데이터 비트는 자신의 위치 번호(이진수)에 따라 2개 이상의 패리티 비트 그룹에 포함된다. 각 패리티 비트는 특정 위치의 비트들을 검사한다.
## 패리티 비트 1 (위치 1): 위치 번호의 이진수 표현에서 가장 오른쪽 비트(최하위 비트)가 1인 모든 비트 위치를 확인한다. (예: 1, 3, 5, 7, 9, 11, ...)
## 패리티 비트 2 (위치 2): 위치 번호의 이진수 표현에서 오른쪽에서 두 번째 비트가 1인 모든 비트 위치를 확인한다. (예: 2, 3, 6, 7, 10, 11, ...)
## 패리티 비트 4 (위치 4): 위치 번호의 이진수 표현에서 오른쪽에서 세 번째 비트가 1인 모든 비트 위치를 확인한다. (예: 4, 5, 6, 7, 12, 13, 14, 15, ...)
## 패리티 비트 8 (위치 8): 위치 번호의 이진수 표현에서 오른쪽에서 네 번째 비트가 1인 모든 비트 위치를 확인한다. (예: 8, 9, 10, 11, 12, 13, 14, 15, ...)
## 일반적으로, 특정 패리티 비트는 자신의 위치 번호와 다른 비트 위치 번호 간의 비트 AND 연산 결과가 0이 아닌 모든 비트 위치를 확인한다.

패리티 값은 해당 패리티 비트가 확인하는 모든 비트(패리티 비트 자신 포함)의 짝수 패리티 또는 홀수 패리티 규칙에 따라 결정된다. 짝수 패리티는 해당 그룹의 1의 개수가 짝수가 되도록 패리티 비트 값을 정하고, 홀수 패리티는 홀수가 되도록 정한다. 인코딩과 디코딩 과정에서 동일한 패리티 규칙(짝수 또는 홀수)을 일관되게 사용해야 한다.

예를 들어, 데이터 10011010을 해밍 코드로 인코딩한다고 가정해 보자. 패리티 비트 위치(_)를 포함하여 데이터 비트를 배치하면 `__1_001_1010` 형태가 된다. 각 패리티 비트의 값을 계산하여 채워 넣으면 최종 코드 워드가 생성된다.

이 규칙은 아래 표와 같이 시각적으로 나타낼 수 있다. 'p'는 패리티 비트, 'd'는 데이터 비트를 의미한다. 각 패리티 비트(p1, p2, p4, ...)가 어떤 비트 위치들을 확인하는지 보여준다.

오류를 검사할 때는 수신된 코드 워드에서 모든 패리티 비트의 규칙(짝수 또는 홀수 패리티)이 맞는지 확인한다. 모든 패리티 검사를 통과하면 오류가 없는 것으로 간주한다. 만약 하나 이상의 패리티 검사에서 오류가 발견되면, 오류를 나타내는 패리티 비트들의 위치 번호를 모두 더한다. 이 합계 값(오류 증후군)이 바로 오류가 발생한 비트의 위치를 나타낸다. 예를 들어, 위치 1, 2, 8의 패리티 비트가 오류를 나타낸다면, 1 + 2 + 8 = 11이므로 비트 11에 오류가 발생한 것이다. 만약 단 하나의 패리티 비트만 오류를 나타낸다면, 그 패리티 비트 자체에 오류가 있는 것이다. 이 방법으로 단일 비트 오류의 위치를 정확히 찾아 수정할 수 있다.

사용하는 패리티 비트의 수를 m개라고 할 때, 이 해밍 코드는 총 2^m-1 개의 비트를 포함할 수 있다. 이 중 m개는 패리티 비트이고, 나머지 2^m-m-1 개는 데이터 비트로 사용된다. m 값이 커짐에 따라 다양한 길이와 효율을 가진 해밍 코드를 만들 수 있다.

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

기존의 해밍 부호는 최소 해밍 거리가 3이므로, 단일 비트 오류는 감지하고 수정할 수 있다. 하지만 이중 비트 오류가 발생했을 경우, 이를 단일 비트 오류로 잘못 판단하여 잘못된 값으로 수정될 수 있다. 즉, 1비트 오류 수정 기능과 2비트 오류 검출 기능을 동시에 수행하기 어렵다.

이러한 단점을 보완하기 위해 해밍 부호에 전체 부호어에 대한 패리티 비트 하나를 추가하는 방식이 사용된다. 이렇게 만들어진 부호를 확장 해밍 부호(extended Hamming code^영어)라고 부른다. 확장 해밍 부호는 최소 해밍 거리가 4로 늘어나, 디코더가 단일 비트 오류와 이중 비트 오류를 명확히 구별할 수 있게 된다.

결과적으로 확장 해밍 부호는 단일 오류는 수정하고, 동시에 이중 오류는 감지(수정은 불가)하는 능력을 갖추게 된다. 이 특징을 SECDED(Single Error Correction, Double Error Detection^영어, 단일 오류 수정, 이중 오류 검출)라고 부른다. 디코더가 오류 수정을 시도하지 않을 경우, 3중 비트 오류까지도 확실하게 감지할 수 있다.

확장 해밍 부호는 1961년 IBM 7030 스트레치 컴퓨터의 메모리 시스템에 처음 도입된 이후 널리 사용되었다. 오늘날에도 ECC 메모리나 RAID 2, 자일링스(Xilinx)의 FPGA 등 일부 하드웨어 설계에서 활용되고 있다. 다만, 현대의 서버 컴퓨터들은 SECDED 수준의 보호 기능은 유지하면서도, 더 긴 부호어(128~256 비트 데이터)와 수정된 패리티 검사 방식 등 해밍 부호와는 다른 발전된 기술을 사용하는 경우가 많다.

확장 해밍 부호 생성은 기존 해밍 부호로 생성된 부호어의 모든 비트에 대한 배타적 논리합(XOR)을 계산하여, 그 결과인 패리티 비트를 부호어의 마지막에 덧붙이는 방식으로 이루어진다. 예를 들어, (7,4) 해밍 부호의 부호어 '1011100'에 대해 모든 비트의 XOR 합은 0이므로, 확장 해밍 부호어는 '10111000이 된다.

복호화 과정에서는 수정된 검사 행렬 H를 사용한다. (7,4) 해밍 부호를 확장한 경우의 검사 행렬은 다음과 같다.
:$H\; =$
\begin{bmatrix}
1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{bmatrix}
이 행렬은 기존 (7,4) 해밍 부호의 검사 행렬 오른쪽에 모든 성분이 0인 열 벡터 하나를 추가하고, 아래쪽에 모든 성분이 1인 행 벡터 하나를 추가하여 구성된다. 수신된 부호어 Y와 이 검사 행렬의 전치 행렬($H^T$)을 곱한 결과(신드롬)를 통해 오류를 판별한다. 1비트 오류가 발생하면 신드롬은 검사 행렬의 특정 열 벡터와 일치하게 된다(단, 마지막 패리티 비트 오류는 마지막 행만 1이 됨). 반면, 2비트 오류가 발생하면 신드롬은 검사 행렬의 어떤 열 벡터와도 일치하지 않으면서 마지막 행의 값이 1이 되는 특징을 보여 구별이 가능하다. 이를 통해 1비트 오류 수정과 2비트 오류 검출이 동시에 가능해진다.

10. [7,4] 해밍 부호

1950년 벨 연구소의 리처드 해밍이 고안한 [7,4] 해밍 부호는 4비트의 데이터를 7비트로 부호화하는 방식이다. 이 과정에서 3개의 패리티 비트가 추가된다. 이 부호는 오류 정정 부호 중 가장 오래된 것 중 하나로 알려져 있으며, 블록당 1비트의 오류를 정정할 수 있다.

[7,4] 해밍 부호는 단일 비트 오류를 감지하고 수정할 수 있다. 또한, 단일 비트 오류와 이중 비트 오류를 모두 감지하는 것도 가능하지만, 이 경우 수정은 할 수 없다. 여기에 전체 패리티 비트를 하나 더 추가하면 [8,4] 확장 해밍 부호가 되는데, 이는 단일 비트 오류를 감지하고 수정하며, 동시에 이중 비트 오류를 감지할 수 있다(수정은 불가).

해밍 부호는 리드-솔로몬 부호 등에 비해 처리 속도가 빠르다는 장점이 있지만, 오류 정정 능력은 상대적으로 높지 않다. 이러한 특징 때문에 오류 발생률이 낮으면서 빠른 속도가 요구되는 분야에 주로 사용된다. 대표적인 예로는 ECC 메모리나 RAID 2가 있으며, WinRAR의 복구 레코드에도 사용된 바 있다.

일반적으로 해밍 부호는 어떤 정수 $m$에 대해 다음과 같은 특성을 가진다.
* 부호 길이: $n\; =\; 2^m\; -\; 1$
* 정보 비트 수: $k\; =\; n\; -\; m$

[7,4] 해밍 부호는 $m=3$인 경우에 해당한다. 따라서 부호 길이는 $n\; =\; 2^3\; -\; 1\; =\; 7$이고, 정보 비트 수는 $k\; =\; 7\; -\; 3\; =\; 4$가 된다. 즉, 4비트의 원본 데이터를 7비트의 부호어로 변환하는 것이다.

[7,4] 해밍 부호의 생성과 오류 검출에는 [[검사 행렬]]($H$)과 [[생성 행렬]]($G$)이라는 두 개의 행렬이 사용된다. 이 행렬 계산에 사용되는 덧셈 연산은 모두 배타적 논리합(XOR)이다.

검사 행렬 (H)

검사 행렬 $H$는 $m\; \backslash times\; n$ 크기의 행렬이다. [7,4] 해밍 부호의 경우 $3\; \backslash times\; 7$ 행렬이 된다. 검사 행렬의 각 열 벡터는 모두 달라야 하며, 모든 성분이 0인 열 벡터는 존재하지 않는다. [7,4] 해밍 부호의 검사 행렬 $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}
이 행렬은 $H\; =\; [\; A\; |\; I\_m\; ]$ 형태로 표현될 수 있는데, 여기서 $A$는 특정 행렬이고 $I\_m$은 $m\; \backslash times\; m$ 단위 행렬이다. 이런 형태의 부호를 조직 부호라고 부른다. 조직 부호는 이론적으로 특별한 중요성은 없지만, 생성 행렬 계산을 용이하게 하고 부호화 장치 구현을 간소화하는 장점이 있어 자주 사용된다. 위의 예시 $H$도 조직 부호 형태이다.

생성 행렬 (G)

생성 행렬 $G$는 $k\; \backslash times\; n$ 크기의 행렬로, 다음 조건을 만족한다.
$HG^T\; =\; GH^T\; =\; 0$ (여기서, $G^T$는 $G$의 전치 행렬을 나타낸다.)
검사 행렬 $H$가 $H\; =\; [\; A\; |\; I\_m\; ]$ 형태의 조직 부호일 경우, 생성 행렬 $G$는 다음과 같은 형태를 가진다.
$G\; =\; [\; I\_k\; |\; A^T\; ]$ (여기서 $I\_k$는 $k\; \backslash times\; k$ 단위 행렬이다.)
위에서 예시로 든 검사 행렬 $H$에 대응하는 생성 행렬 $G$는 다음과 같다.
$G\; =$
\begin{bmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
\end{bmatrix}

11. [8,4] 해밍 부호

(내용 없음)