Hamming Code   해밍 코드, 해밍 부호

(2021-10-13)

1. 해밍 부호 (Hamming Code)

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

  ㅇ (n,k) 선형블록부호순회부호의 특성을 갖음
     - 선형블록부호 : 블록부호선형성이 추가됨
     - 순회부호 : 블록부호선형성 및 순회성이 추가적으로 부과됨 
     - (n,k) = (2m - 1, 2m - 1 - m) (단, m은 임의 양의 정수)
        . m이 3일 때, (7,4) 해밍 코드가 됨
     - [참고] ☞ 생성행렬(부호어 생성), 패리티검사행렬(오류 검사), 신드롬(오류 증상) 등

  ※ 미국의 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 비트 만 상이함

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

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

  ㅇ 신드롬 수 : 8개
     - 1개 : 오류 없음 
     - 7개 : 각각이 1 비트 오류 징후 (Error Pattern)를 나타냄

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


4. 해밍 부호의 주요 파라미터  (m ≥ 3)패리티 검사 비트 수      :  m = n - k
  ㅇ 코드 길이                :  n = 2m - 1
  ㅇ 원 정보 비트 길이        :  k = 2m - m - 1
  ㅇ 오류 정정 능력           :  t = 1 (dmin = 3, t =  {#\left\lfloor \frac{d_{min} - 1}{2}\right\rfloor#} )

  ㅇ 패리티 검사 행렬의 크기              :  (n - k) x n = m x n
  ㅇ 패리티 검사 행렬체계적 부호 형식  :  
[# H = [ I_m \; Q ]#]
- {#I_m#} : m x m 단위 행렬 - {#Q#} : m x (2m - m - 1) 부분 행렬 5. 해밍 조건 ㅇ 2 n-k ≥ n + 1 ☞ 해밍 한계 (Hamming Bound) 참조 - k : 정보 비트 수, n-k : 최소 잉여 비트 수 - 결국, 최소 필요, 패리티 비트 수 n-k 는, 위 관계식에 의해 결정



Copyrightⓒ   차재복 (Cha Jae Bok)