해밍 부호

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

해밍 부호(해밍符號, Hamming code)는 오류 정정 부호의 일종으로 리처드 해밍이 제안했다. 보통 해밍 부호라고 할 때는 해밍 (7,4) 부호를 가리킨다. 해밍 부호는 1비트 오류만 일어날 때는 오류를 정정할 수 있고, 2비트까지의 오류를 검출할 수 있다.

역사[편집]

해밍은 1940년대 벨 연구소에서 Bell Model V라는 컴퓨터를 이용해서 작업을 했다. 이 컴퓨터는 확실히 여러 면에서 오늘날의 컴퓨터와는 거리가 멀었다. 릴레이 회로로 만들어졌으며 입력도 천공카드를 이용했다. 천공카드를 이용했으므로 컴퓨터에 입력되는 자료들은 필연적으로 언제나 오류의 가능성이 있었다. 주중에는 컴퓨터의 관리자(operator)가 있으면서 입력에 오류가 발생했다는 경고등이 켜지면 직접 수정할 수 있었으나, 관리자가 없는 주말에는 에러가 발생한 채 프로그램이 실행되지 않고 다음 작업으로 넘어가기 일쑤였다.

해밍은 이런 문제로 인해 여러 차례 고생을 한 후에, 이 문제를 근본적으로 해결하기 위해 노력했다. 그 후 몇 년 동안 오류를 수정하는 방법에 대해서 연구하면서 이와 관련된 여러가지의 효율적인 알고리즘을 만들어냈고 마침내 1950년에 해밍 부호를 발표했다. 해밍 부호는 오늘날에도 사용되고 있다.

이전의 부호[편집]

해밍 부호 이전에도 에러를 검출하는 알고리즘이 있었지만, 해밍 코드만큼 효율적인 것은 없었다. 해밍 부호를 설명하기 전에 간략하게 설명하도록 하겠다.

패리티 비트[편집]

패리티 비트 (parity bit)는 주어진 비트열에 1이 짝수번 나오는지 홀수번 나오는지 추가적인 정보를 입력하는 방식이다. 예를 들어, 어떤 비트열에 1이 홀수번 나오면 패리티 비트가 1이고 짝수면 0으로 정했다고 하자. '1101011'이라는 비트열에는 1이 5번 나오므로 패리티 비트가 1이 되어서 최종적으로 '11010111'이라고 쓰는 방식이다.

패리티 비트는 여러가지 단점이 있다.

  • 짝수 개의 오류가 발생하면 오류를 검출하지 못하는 경우가 생길 수 있다. 예를 들어서 '0000'을 보내려고 패리티 비트 '0'을 추가해서 '00000'을 전송했는데 오류가 발생해서 '01010'이 전송되었다고 하자. 받는 쪽에서는 1이 두번 나오므로 패리티 비트가 제대로 0으로 설정되었다고 생각할 것이고, 결과적으로 오류를 검출하지 못하게 된다.
  • 전송된 비트열에 오류가 발생했다는 것을 알았다 하더라도 오류가 발생하기 전의 제대로 된 내용을 알 수 없다. 예를 들어서 '001000'이라는 비트열을 받았다고 하자. 이 비트열에서 1이 한 번 나오기 때문에 전송중에 오류가 생겼다는 것을 알 수 있지만, 원래 비트열은 알 수가 없다. 따라서 결과적으로 데이터를 다시 전송해야 하는 문제가 있다.
  • 데이터의 전송 과정에서 오류가 발생하므로 패리티 비트 자체에도 오류가 생길 수 있다.

반복[편집]

다른 방법으로는 전송하고자 하는 메시지를 여러차례 반복하여 오류를 검출하여 수정하는 방법이 있다. 예를 들어 메시지를 3회 반복한다고 하면, 1을 전송하고자 할때는 '111'을 보내고 0을 보내고자 할때는 '000'을 보내는 방식이다. 만약 '000'을 전송했는데 오류가 발생하여 '001'이 전송되었으면, '000'이었을 것이라고 추측하여 '000'으로 고치는 방식이다.

물론, 이 방법에도 단점이 있다. 오류가 반드시 한번만 발생하는 것이 아니기 때문에 '001'이라는 메시지를 받았을 때, 이것이 '000'이 잘못 전송된 것인지 '111'이 잘못 전송된 것인지 알 수가 없다. 무엇보다도 1비트를 전송하기 위해서 3비트를 전송하여야 하므로 매우 비효율적이다.

해밍 부호[편집]

만약 메시지에 더 많은 오류 검출 비트가 포함되어 있고, 서로 다른 잘못된 비트가 각각 다른 오류를 내도록 비트들을 배치할 수 있다면 잘못된 비트를 확인해 낼 수 있다. 7비트 메시지의 경우 1비트 오류는 일곱 가지가 있으므로, 오류가 발생했다는 것뿐만 아니라 어느 비트가 잘못되었는지 확인하기 위해서는 적어도 오류 검출 비트가 세 개 이상 필요하다.

해밍은 당시 존재했던 부호화 방법들을 연구하여 그 특징을 일반화하였다. 처음에 그는 이러한 체계의 명명법을 개발했는데, 이 방법은 한 비트열에 몇 개의 데이터 비트와 오류 검출 비트가 있는지를 사용한다. 예를 들어 7비트 ASCII 문자에 패리티 비트를 사용할 경우, 한 비트열은 8비트이고 그 중 7비트가 실제 데이터이므로 (8,7) 부호라고 한다. 반복의 경우 같은 방법으로 (3,1) 부호라고 부를 수 있다. 정보 속도(Information rate)는 둘째 숫자를 첫째 숫자로 나눈 것으로, 반복의 경우 1/3이 된다.

또한 해밍은 둘 이상의 비트들이 바뀐 경우를 관찰했고, 이를 "거리"로 설명하였다. (지금은 이를 해밍 거리로 부른다) 패리티 비트는 두 개의 비트가 바뀌면 오류를 검출해 낼 수 없기 때문에 거리가 2이다. (3,1) 반복의 경우 비트열 전체의 세 개의 비트가 바뀌어야 오류를 검출해 낼 수 없으므로 거리가 3이다. 같은 방법으로 (4,1) 반복의 거리는 4이다.

해밍은 정보 속도를 최대한 늘리면서 동시에 부호의 거리를 최대한 늘이는 데 관심을 가졌고, 1940년대 동안 당시 존재하던 부호들보다 훨씬 발전한 부호화 방법을 여럿 개발했다. 그가 만든 모든 체계는 공통적으로 패리티 비트가 중첩된다는 특징을 갖고 있으며, 따라서 패리티 비트들은 데이터 비트들 뿐만 아니라 다른 패리티 비트를 검사하는 데도 사용할 수 있다.

일반화된 해밍 부호를 만드는 방법은 다음과 같다:

  1. 2의 거듭제곱번째 위치에 있는 비트들은 패리티 비트로 사용한다. (1, 2, 4, 8, 16, 32, 64, …번째 비트)
  2. 나머지 비트에는 부호화될 데이터가 들어 간다. (3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, …번째 비트)
  3. 각각의 패리티 비트는 위치에 따라서 다음과 같은 비트들을 검사한다:
    • 1번째 비트: 그 비트를 포함해서 다음 1비트를 검사하고, 다음 1비트를 건너 뛰고, 1비트를 검사하고, 1비트를 건너 뛰고, …
    • 2번째 비트: 그 비트를 포함해서 다음 2비트를 검사하고, 다음 2비트를 건너 뛰고, 2비트를 검사하고, 2비트를 건너 뛰고, …
    • 4번째 비트: 그 비트를 포함해서 다음 4비트를 검사하고, 다음 4비트를 건너 뛰고, 4비트를 검사하고, 4비트를 건너 뛰고, …
    • 8번째 비트: 그 비트를 포함해서 다음 8비트를 검사하고, 다음 8비트를 건너 뛰고, 8비트를 검사하고, 8비트를 건너 뛰고, …
    • n번째 비트(단, n은 2의 거듭제곱): 그 비트를 포함해서 다음 n비트를 검사하고, 다음 n비트를 건너 뛰고, n비트를 검사하고, n비트를 건너 뛰고, …

이것을 그림으로 표현하면 아래와 같다.

프레임있음

해밍 (7,4) 부호[편집]

흔히 '해밍 부호'라고 하면 해밍이 1950년에 소개했던 해밍 (7,4) 부호를 뜻한다. 4비트의 자료를 전송하기 위해서 3비트의 패러티 비트를 추가하기 때문에 이런 이름을 가진다. 이 부호는 모든 1비트 오류를 감지해서 바로 잡을 수 있고, 2비트 오류도 감지할 수 있기 때문에 연집 오류가 발생하지 않는 전송 환경에서는 효과적이다.

해밍 행렬[편집]

해밍 부호는 패리티의 개념을 확장한 해밍 행렬을 사용한다. 이 행렬에는 부호화에 사용하는 생성 행렬 G와 오류를 감지하고 바로 잡는 데 쓰는 확인 행렬 H가 포함되며, (7,4) 부호의 경우 이들은 다음과 같다.

\mathbf{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}
\mathbf{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의 첫 네 행은 4×4 항등 행렬 I4이고, 나머지 세 행은 자료 비트 네 개와 패리티 비트 세 개의 대응을 나타낸다. G의 열 벡터는 H커널기저들이다. 항등 행렬은 행렬 곱셈을 할 때 자료 비트를 그대로 유지하기 위해서 필요하다. 비슷하게 H의 마지막 세 열은 3×3 항등 행렬 I3이고, 앞의 네 열은 자료 비트와 패리티 비트와의 대응을 나타낸다.

이렇게 행렬을 도입할 경우 실제로 보내고자 하는 자료 비트는 열 벡터로 구성해야 한다. 예를 들어 "1011"에 대응하는 벡터 p는 다음과 같다.

\mathbf{p}=\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}

부호화 과정[편집]

앞의 벡터 p는 앞에 G를 곱한 뒤 2의 나머지를 취해서 해밍 부호 x로 변환할 수 있다.

\mathbf{G} \mathbf{p} = \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}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}=
\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}=\mathbf{x}

패리티 확인[편집]

전송 과정에서 오류가 발생하지 않았다면 받은 내용 r은 보낸 내용 x와 동일할 것이다. 받는 쪽에서는 r 앞에 H를 곱한 뒤 2의 나머지를 취해서 오류가 발생했는지 확인한다.

\mathbf{H}\mathbf{r} = \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}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}

곱셈의 결과가 영 벡터이므로 오류가 발생하지 않았다는 것을 알 수 있다. 왜냐하면 앞에서 G를 자료 벡터에 곱할 때 바뀐 기저는 H의 커널의 부공간 안에 있고, 전송이 정상적으로 이루어졌다면 rH의 커널에 남아 있게 되므로 곱한 결과는 영 벡터가 된다.

오류 정정[편집]

전송 과정에서 1비트 오류가 발생했다고 하자. 이를 수학적으로 다음과 같이 쓸 수 있다.

\mathbf{r} = \mathbf{x} + \mathbf{e}_i \quad \mathrm{(mod\ 2)}

여기서 ei는 영 벡터에서 i번째 칸에만 1이 채워진 i번째 단위 벡터이다. 따라서 rx에서 i번째 비트만 다른 벡터가 된다.

r 앞에 H를 곱하면 다음을 얻는다.

 \mathbf{Hr} = \mathbf{H}(\mathbf{x}+\mathbf{e}_i) = \mathbf{Hx} + \mathbf{He}_i

앞에서 Hx의 곱은 영 벡터이므로, 이를 정리하면:

 \mathbf{Hx} + \mathbf{He}_i = \mathbf{0} + \mathbf{He}_i = \mathbf{He}_i

여기서 Hi번째 단위 벡터를 곱한 결과는 Hi번째 열이 되므로, 이 결과를 가지고 어떤 비트에서 오류가 생긴 건지 확인할 수 있다. H는 이 결과가 오류가 발생한 비트 번호를 이진법으로 나타낸 것이 되도록 만들어져 있다. 예를 들어서 결과가 (1, 0, 1)일 경우 다섯 번째 비트에서 오류가 발생한 것이다.

앞의 x에서 두 번째 비트가 잘못되었다고 하자.

\mathbf{r} = \mathbf{x}+\mathbf{e}_2 = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} =  \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}

따라서,

\mathbf{Hr} = \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}\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}

이진법 010은 십진법으로 2이므로 두 번째 비트가 잘못되었음을 알 수 있다.

이 방법은 2비트 이상의 오류가 일어나지 않을 때만 오류를 고칠 수 있음을 어렵지 않게 보일 수 있다. 2비트 오류가 발생할 때도 H와의 곱이 영 벡터가 되기 때문에 오류를 감지할 수는 있지만, 1비트 오류와 2비트 오류를 구별할 수 없기 때문에 정정은 불가능하다.

확장된 해밍 부호[편집]

해밍 부호에 모든 비트에 대응되는 (즉 일반적인) 패리티 비트를 하나 더 추가할 수도 있다. 이렇게 하면 해밍 거리는 3에서 4로 늘어 나며, 따라서 3비트 오류를 추가적으로 잡아 낼 수 있다.[1] 또한 1비트 오류, 2비트 오류, 3비트 오류가 서로 구별되기 때문에 어떤 경우에도 1비트 오류를 항상 고칠 수 있다.

2비트 오류는 상황에 따라서 정정이 가능할 수도 있고 불가능할 수도 있다. 만약 전체적으로 패리티가 잘못되었고 해밍 부호 자체도 잘못되었다면 바로 잡을 수 있지만, 패리티는 정상인데 해밍 부호가 잘못되었다면 감지는 가능하나 바로 잡을 수는 없다.

같이 보기[편집]

참고 자료[편집]