Hamming Code   해밍 코드, 해밍 부호

1. 해밍 부호 (Hamming Code)

  ㅇ 데이타 전송시 1 비트의 에러를 정정할 수 있는, 오류정정부호의 일종
     
  ㅇ 미국의 Bell 연구소의 Hamming에 의해 고안됨 (1950년)
     - 사용 例) 플래시 메모리 등

  ㅇ (n,k) 선형블록부호 및 순회부호 에 속함
     - 선형블록부호 : 블록부호에 선형성이 추가됨
     - 순회부호 : 블록부호에 선형성 및 순회성이 추가적으로 부과됨 


2. (7,4) 해밍 부호

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

     - 부호표  :  (메세지어, 부호어 간의 매핑 관계)
       

     - 패리티검사비트  :  (짝수 패리티 비트의 생성규칙)
       
        . 여기서, 는 Modulo-2 덧셈 연산 (0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0)
        . 4개의 정보 비트에다가 3개의 짝수 패리티 비트를 추가함

     - 생성행렬  :  (부호어 생성을 위한 행렬표현)
        

        . k개 행과 n개 열을 갖음 (k = 4, n = 7)
        . 생성 행렬은, 행렬 곱셈에 의해, 선형 블록부호를, 효율적으로 생성시킴

  ㅇ 복호화  :  (Syndrome Decoding - 오염된 부호의 오류정정) 
     * 특히, 신드롬 복호법(Syndrome Decoding)은 해밍 코드에 적합

     - 신드롬표  :  (매 신드롬이, 오류 검출(증상)에 따른, 각각의 오류 패턴에 대응됨)
       

     - 신드롬의 생성규칙
       

     - 신드롬의 생성 행렬 표현
       


3. (7,4) 해밍 부호의 특징  :  (n = 7, k = 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개 (2n-k = 27-4 = 23 = 8개)
     - 7개 : 각각이 1 비트 오류 징후 (Error Pattern)를 나타냄
     - 1개 : 오류 없음
 
     * 각 1개의 부호어 마다, 이것과 해밍거리가 1인 모든 가능한 7개의 여분어가 있게 됨
        . 例) (0000000) 주위에, 
              (1000000),(0100000),(0010000),(0001000),(0000100),(0000010),(0000001) 존재 가능
        . 따라서, 총 24 x 23 = 27개의 벡터들이 존재 가능

  ㅇ 완전 부호 임
     - 모든 수신 부호어에 대해, 복호 실패 없이, 반드시 복호 가능

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


4. 해밍 부호의 주요 파라미터  (m ≥ 3, 단, m은 임의 양의 정수)

  ㅇ (n,k) = (2m - 1, 2m - 1 - m)
     - 패리티 검사 비트 수      :  m = n - k
     - 코드 길이                :  n = 2m - 1
     - 원 정보 비트 길이        :  k = 2m - m - 1
     * 여기서, m이 3일 때, (7,4) 해밍 코드가 됨

  ㅇ 패리티 검사 행렬
     - 패리티 검사 행렬의 크기              :  (n - k) x n = m x n
     - 패리티 검사 행렬의 체계적 부호 형식  :  
[# H = [ Q \; I_m ]#]
        . {#I_m#}  :  m x m 단위 행렬
        . {#Q#}    :  m x (2m - m - 1) = (m x k) 부분 행렬

  ㅇ 오류 검출, 오류 정정 능력
     - 오류 검출 능력
        .  td ≤ dmin - 1 = 3 - 1 = 2 비트
     - 오류 정정 능력
        .  tc = 1 (dmin = 3, tc =  {#\left\lfloor \frac{d_{min} - 1}{2}\right\rfloor#} )


5. 해밍 조건 
        
  ㅇ   2 n-k  ≥  n + 1                              ☞ 해밍 한계 (Hamming Bound) 참조
     -  k : 정보 비트 수
     -  n-k : 최소 잉여 비트 수
     *  결국, 최소로 필요한, 패리티 비트 수 n-k 는, 위 관계식에 의해 결정