Hamming Code   해밍 코드, 해밍 부호

1. 해밍 부호 (Hamming Code)

  ㅇ 데이타 전송시 1 비트의 에러를 정정할 수 있는 오류정정부호의 일종

  ㅇ (n,k) 선형블록부호 및 순회부호의 특성을 갖음

  ※ 미국의 Bell 연구소의 Hamming에 의해 고안된 간단한 블록부호 (1950년)
     - 사용 例) 플래시 메모리 등


2. (7,4) 해밍부호 例

  ㅇ 부호화 (1 비트 오류정정을 위한 3개의 패리티비트 첨가)

     - 부호표 
       

     - 패리티검사비트 생성규칙 (짝수 패리티 비트)
       
        . 여기서, 는 Modulo-2 덧셈 연산 (0+0=0, 0+1=1, 1+0=1, 1+1=0)

     - 부호어 생성을 위한 행렬표현  ☞ 생성행렬 참조
        

  ㅇ 복호화 (Syndrome Decoding - 오염된 부호의 오류정정) 

     - 신드롬표
       

     - 신드롬 생성규칙
       

     - 신드롬 생성 행렬표현
       


3. (7,4) 해밍부호 특징

  ㅇ 유효 부호어 개수 : 16개
     - 2k = 24 = 16개

  ㅇ 닫힘 성질 
     - 두 부호어의 합이 다시 또다른 부호어가 됨

  ㅇ 최소 해밍거리 (dmin) : 3
     - 임의의 두 부호어 쌍 간에 항상 3 비트 만 상이함

  ㅇ 신드롬 수 : 8개
     - 1개 : 오류 없음 
     - 7개 : 1 비트 오류 징후 (Error Pattern) 

  ㅇ 오류검출능력 : td ≥ dmin - 1 = 3 - 1 = 2
     - dmin - 1 보다 작거나 같은 모든 오류 패턴을 검출할 수 있음
        . 최대 2 비트 오류 검출 가능

  ㅇ 오류정정능력 : tc ≥ (dmin - 1)/2 ≥ (3-1)/2 = 1
     - 잉여 패리티검사비트가 (n-k)인 3개 비트가 추가되므로, 
       dmin의 상한이 3 이 되면서 오류정정능력 비트수는 1 비트가 됨
        . 각 부호의 해밍거리가 3 이상의 부호어로하는 부호계에서, 
        . 각 부호어의 거리가 3 이상이므로 하나의 부호어가 1 비트 잘못된 부호는,
        . 다른 부호어와 명확하게 구별할 수 있으므로,
        . 원리적으로 최대 1 비트 오류 정정 가능

  ㅇ 패리티 비트를 필요한 수 만큼 정해진 위치에 두어서,
     - 에러가 발생했을 때 에러 발생 비트를 알아내어 정정이 가능하도록 함.


4. 해밍조건
        
  ㅇ   2 p  >=  m + p + 1
     -  m : 정보 비트 수, p : 최소잉여 비트 수
     - 결국, 패리티 비트 수 p 는 위 관계식에 의해 결정