Kraft Inequality   크라프트 부등식

1. 크라프트 부등식 (Kraft Inequality)

  ㅇ 코드의 길이에 따라 동시코드의 존재 조건을 나타내는 부등식


2. 크라프트 부등식 표현

  ㅇ 
[# \sum^q_{i=1} r^{-l_i} \leq 1 #]
     -  r : 코드알파벳의 원소 수 (Radix)
     -  l : 각 심볼의 코드 길이,
     -  q : 심볼의 개수 (i = 1,...,q)

  ※ 크라프트 부등식은, 
     - 동시코드를 구성하려면,
        . 매 심볼 코드의 길이 l가, 모두 일률적으로 짧거나 길거나를 의미하지 않고, 
     - 각 심볼 코드들이 이 부등식을 만족하게되면,
        . 동시코드가 될 수 있다는 의미임


3. 크라프트 부등식  :  동시코드의 존재에 대한 필요충분조건

  ㅇ Kraft 정리는, 오직 코드의 길이에 대해서 만, 동시코드의 존재(성) 여부를 판정함
     - 즉, 어떤 코드가 동시 코드인가 아닌가에 대해서는 판단하지 않음

  ※ 例) 이진코드 각각의 코드 길이가 {1,2,2,3} 이면,
     - (1/21 + 1/22 + 1/22 + 1/23) = (1/2 + 1/4 + 1/4 + 1/8) = (0.5 + 0.25 + 0.25 + 0.125)
     - (  1.125  >  1 ) 이므로, 동시코드가 될 수 없음