Hamming Code   해밍 코드, 해밍 부호

(2023-08-24)

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)

     - 생성행렬  :  (부호어 생성을 위한 행렬표현)
       복호화 (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개 (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 는, 위 관계식에 의해 결정

선형 블록부호의 종류
   1. 반복 부호   2. 해밍 부호   3. 직각 부호   4. 쌍대 부호   5. LDPC  
에러 정정
   1. 에러정정   2. 해밍 코드   3. 길쌈 부호   4. RS 부호   5. FEC(전진에러수정)  


Copyrightⓒ written by 차재복 (Cha Jae Bok)       기술용어해설 소액 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"