Error Detecting Capability, Error Correcting Capability   오류 검출 능력, 오류 정정 능력

1. 해밍 최소거리, 해밍 구, 복호화 가능 구

  ㅇ 해밍 최소거리 (Hamming Minimum Distance)  :  dmin
     - 서로 다른 두 부호어 간의 해밍거리 중에서 가장 작은 거리

     * 오류를 검출하거나 정정할 수 있는 능력과 직접 관련되는 중요 파라미터 임

  ㅇ 해밍 구 (Hamming Sphere)  :  (해당 수신 부호어를 기준으로 한 최소 거리)
     - 수신 부호어로부터 발생가능 오류개수 t 보다 작은 해밍거리를 갖는 구(球)

  ㅇ 복호화 가능 구 (Decoding Sphere)  :  (복호 가능 영역)
     - 해밍 구들이 서로 겹치지 않게 전체 부호어 공간을 꽉 채우는 구
        . 반경 t인 오류정정능력 보다 작은 개수의 오류 발생시 원래 부호어로 복호 가능

      


2. 반경 t 인 해밍 구 내 가능한 부호어 수

  ㅇ q진 부호인 경우
      
[# \binom{n}{0}+\binom{n}{1}(q-1)+\binom{n}{2}(q-1)^2+\cdots+\binom{n}{t}(q-1)^t = \sum^{t}_{i=0} \binom{n}{i} (q-1)^i #]
     - 부호길이 n 에서, 두 부호어 간 거리 (차이)가 i 이라면, 
     - 매 거리 마다 선택 가능 자리 수는, {# \binom{n}{i} #}
     - 매 거리 마다 각 자리에, (q-1)i개 심볼들을 사용 가능
     - (q-1)은, 이미 고정 선택된 1개 심볼을 제외하고 나머지 심볼들에서 선택 가능한 수

  ㅇ 2진 부호 (q = 2)인 경우
      
[# \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{t} #]


3. `오류 검출 및 오류 정정 능력` => (해밍 최소거리는 비트 오류를 검출,정정하는 능력과 직결됨)

  ㅇ 오류 검출 능력 (td)  :  검출 가능 최대 오류의 수
     -   td ≤ dmin - 1  또는  dmin ≥ td + 1
        . dmin : 해밍 최소 거리

     * 즉, 오류 검출 능력은, td = dmin - 1 이고,
        . 오류 갯수가, (dmin-1) 보다 작아야 오류 검출이 가능함

  ㅇ 오류 정정 능력 (tc)  :  정정 가능 최대 오류의 수
     -   2 tc + 1 ≤ dmin ≤  2 tc + 2
          
[# t_{c} \leq \left \lfloor  \frac{d_{min} - 1}{2} \right \rfloor  #]
        . 여기서, {# \lfloor x \rfloor #}는, {#x#} 보다 크지 않은 최대 정수   ☞ 마루 함수 참조

     * 즉, 오류 정정 능력은, tc =  {#\left\lfloor \frac{d_{min} - 1}{2}\right\rfloor#} 이고,
        . 오류 갯수가, (dmin-1)/2 보다 작은 정수가 되어야 오류 정정이 가능함

  ㅇ 例) (7,4) 해밍 코드(선형블록부호)의 경우
     - 최소해밍거리 : dmin = 3 비트
     - 오류검출능력 : td ≤ dmin - 1 = 3 - 1 = 2 비트
     - 오류정정능력 : tc ≤ (dmin - 1)/2 ≥ (3-1)/2 = 1 비트


4. 오류 검출 및 정정 능력 간의 관계

  ㅇ  td > tc

  ㅇ  dmin ≥ tc + td + 1

  ㅇ 단, 동시에, 오류 검출, 오류 정정 능력 모두가 최대로 발휘 못함
     - 例) 최소거리 3 인 경우  :  2개 조합
        . (오류 검출 : 1 비트, 오류 정정 : 1 비트), (오류 검출 : 2 비트)
     - 例) 최소거리 4 인 경우  :  2개 조합
        . (오류 검출 : 2 비트, 오류 정정 : 1 비트), (오류 검출 : 3 비트)
     - 例) 최소거리 5 인 경우  :  2개 조합
        . (오류 검출 : 2 비트, 오류 정정 : 2 비트), (오류 검출 : 3 비트, 오류 정정 : 1 비트)


5. 오류 검출/정정 능력의 한계(Bound)

  ※ n,k,td,tc 간의 관계로써, 오류 정정 능력의 한계를 규정짓는 관계식
     - 주로, n와 k의 값을 어떻게 정해야 하는지에 대한 조건 관계식

  ㅇ 싱글톤 한계 (Singleton Bound)
     - (n,k) 선형 블록부호의 최소거리/최소무게의 하한값 
        .  dmin ≤ n - k + 1  또는  dmin -1 ≤ n - k
           .. (n - k) : 패리티비트

     - 한편, 최대 거리 부호 (Maximum Distance Code)는,
        . 최소 거리가 다음을 만족하는 부호를 지칭함
           ..  dmin = n - k + 1

  ㅇ 해밍 한계 (Hamming Bound) 
     - t error-correcting code에 대해,
        
[# \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{t} = \sum^{t}_{i=0} \frac{n!}{(n-i)!i!} = \sum^{t}_{i=0} \binom{n}{i} \leq 2^{n-k} #]
     - 여기서, (n,k) 부호일 경우에
        . 전체 n개 비트 중 i 비트 마다,                  ☞ 이항 계수, 경우의 수 계산 (요약) 참조
           .. {#\binom{n}{i}#}개의 n 차원 부호어(n-tuple Codeword)를 만들 수 있음
        . 오류정정 능력으로, t 비트까지 포함하려면,
           .. {#\sum^{t}_{i=0} \binom{n}{i}#}
        . 이 오류정정 능력을 갖춘 경우의 수가, 
           .. 2n-k개의 가능한 오류 패턴 보다 작아야 함               ☞ 표준 배열 참조

     - 例) t = 1 즉, 단일 오류정정 이려면,                                      ☞ 해밍 부호 참조
        . 
[# 2^{n-k} \geq \binom{n}{0} + \binom{n}{1} = 1 + n #]
        . 따라서, 패리티 검사 비트수 n - k 는, n - k > log2 n 을 만족해야 함

     - 한편, 완전 부호(Perfect Code)는,
        . 해밍 한계에 도달하는(만족하는) 부호를 지칭함