서문

컴퓨터 시스템과 네트워크에서 데이터 무결성은 매우 중요한 요소이다. 우리가 보내는 모든 데이터는 네트워크를 통해 전송되는 동안 다양한 요인으로 인해 손상될 가능성이 있다. 예를 들어, 전기적 간섭, 하드웨어 결함, 네트워크 오류 등이 데이터 전송에 영향을 미칠 수 있다. 그렇다면 이런 오류를 어떻게 막을 수 있을까? 오류 검출 및 교정 기법이 여기에 중요한 역할을 한다.

가장 기본적인 방법 중 하나인 패리티 비트(Parity Bit)는 간단하면서도 효율적으로 데이터 전송 중 발생한 오류를 감지할 수 있도록 도와준다. 더 나아가, 해밍 코드(Hamming Code)와 같은 보다 정교한 기법을 사용하면 단순히 오류를 감지하는 것을 넘어서, 발생한 오류를 교정하는 기능까지 구현할 수 있다. 이 글에서는 이러한 오류 검출과 교정 기법이 어떻게 작동하는지, 패리티 비트와 해밍 코드를 중심으로 구체적인 예제를 통해 알아볼 것이다.

1. 패리티 비트(Parity Bit)

패리티 비트는 데이터 전송 중 발생할 수 있는 단일 비트 오류를 검출하는 데 사용되는 가장 기본적인 방법이다. 패리티 비트는 전송되는 데이터에 추가되어, 데이터를 수신하는 쪽에서 전송 중 오류가 발생했는지 확인할 수 있도록 도와준다. 이 방식은 매우 간단하지만, 오류를 교정할 수는 없고, 단지 오류가 발생했음을 감지하는 역할만 수행한다.

1.1. 종류

• 짝수 패리티(Even Parity)
  • 데이터 비트 내의 1의 개수가 짝수가 되도록 패리티 비트를 설정한다.
  • e.g. 1011 → 11011
• 홀수 패리티(Odd Parity)
  • 데이터 비트 내의 1의 개수가 홀수가 되도록 패리티 비트를 설정한다.
  • e.g. 1011 → 01011

1.2. 특징

• 오류 검출만 할 뿐 어느 비트에서 오류가 발생했는지 알 수 없기 때문에 수정할 수도 없다.
• 2 bit 이상의 데이터가 손실되면 알아차릴 수 없다.

이때문에 더 높은 신뢰성과 복구 기능이 필요한 시스템에서는 패리티 비트보다 해밍 코드와 같은 방법을 선호한다.

2. 해밍 코드(Hamming Code)

해밍 코드는 데이터 전송 중 발생할 수 있는 단일 비트 오류를 검출하고 교정할 수 있는 방법이다. 해밍 코드는 여러 개의 패리티 비트를 추가하여, 데이터에 포함된 비트 중 어디에서 오류가 발생했는지를 정확히 파악할 수 있도록 설계되었다. 이를 통해 수신된 데이터에서 오류가 발생하더라도, 해당 비트 위치를 식별해 올바른 값으로 수정할 수 있다.

$2^p ≥ d + p + 1$ (p: 패리티 비트 수, d: 원본 데이터 비트 수)

2.1. 생성 예제: 원본 데이터 1001

1. 몇 개의 패리티 비트를 추가해야 할지 계산한다.

   • $2^1 < 1+4+1$ ❌
   • $2^2 < 2+4+1$ ❌
   • $2^3 = 3+4+1$ ⭕️ (채택)
   • $2^4 > 4+4+1$ 🔺

2. 패리티 비트 자리를 추가하여 새로운 데이터를 만든다.

   • 패리티 비트의 위치는 일반적으로 2의 거듭제곱 위치에 놓인다. ($2^0, 2^1, 2^2, ...$)

   _ _ 1 _ 0 0 1
   
   패리티 비트 자리: 1, 2, 4(2의 거듭 제곱)
   나머지 비트 자리: 3, 5, 6

3. 각 패리티 비트를 계산하여 해당 자리에 넣는다.

• P1: 3번, 5번, 7번 비트의 XOR 값 P1 = D3 ⊕ D5 ⊕ D7 = 1 ⊕ 0 ⊕ 1 = 0
• P2: 3번, 6번, 7번 비트의 XOR 값 P2 = D3 ⊕ D6 ⊕ D7 = 1 ⊕ 0 ⊕ 1 = 0
• P4: 5번, 6번, 7번 비트의 XOR 값 P4 = D5 ⊕ D6 ⊕ D7 = 0 ⊕ 0 ⊕ 1 = 1
  

P1 P2 D3 P4 D5 D6 D7
0  0  1  1  0  0  1

2.2. 오류 검출 예제

전송된 데이터 0011001에서 비트 6(데이터 비트 3)이 0이 아닌 1로 잘못 전송되었다고 하자. → 0011011

• P1(0): D3 ⊕ D5 ⊕ D7 = 1 ⊕ 0 ⊕ 1 = 0, 오류 없음.
• P2(0): D3 ⊕ D6 ⊕ D7 = 1 ⊕ 1 ⊕ 1 = 1, 오류 가능성 있음.
• P3(1): D5 ⊕ D6 ⊕ D7 = 0 ⊕ 1 ⊕ 1 = 0 , 오류 가능성 있음.
• P2와 P4에서 오류가 검출되었으므로, 오류 위치는 $2+4=6$, 즉 6번 비트에서 오류가 발생했음을 알 수 있다.

마치며

공부를 하면서 패리티 비트나 해밍 코드가 1비트 이상의 오류를 검출하지 못한다는 한계를 지니고 있는데, 이런 기술이 과연 현재에도 여전히 쓰이고 있을까 궁금했다.

현대에는 네트워크 환경이 워낙 안정적이기 때문에 단일 비트 오류를 검출하는 것만으로도 충분한 이점이 있다고 한다. 애초에 오류가 빈번하게 발생하지 않기 때문에, 복잡한 체크섬 방식을 사용하는 것보다 간단한 방식이 더 효율적일 수 있다.

해밍 코드의 경우에는 수신 측에서 처리할 일이 많고, 데이터 양도 늘어나기 때문에 현대 네트워크에서는 잘 사용되지 않는다고 한다. 스스로 정정하는 방식보다, 일단 오류를 검출하면 재전송하는 방식이 훨씬 더 효율적이기 때문이다. 그럼에도 불구하고, 해밍 코드는 여전히 네트워크 대역폭이 제한적이거나 안정적인 연결이 어려운 환경, 예를 들어 임베디드 시스템이나 위성 통신 같은 분야에서는 여전히 유용하게 쓰이고 있다.

Reference

• [컴퓨터구조] 패리티 비트와 해밍 코드