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 ) 이므로, 동시코드가 될 수 없음