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

(2022-06-28)

에러 정정 능력, 오류 제어 능력, Hamming Sphere, 해밍구, Decoding Sphere, 복호 영역, Maximum Distance Code, 최대 거리 부호, Hamming Bound, 해밍 한계, Singleton Bound, 싱글톤 한계


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진 부호인 경우
[# \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)는, . 해밍 한계에 도달하는(만족하는) 부호를 지칭함



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