소스 코딩

Source Coding

1. 소스 심볼은
   이진수
   로 인코딩 되어야 한다.
2. 평균 코드 길이는 최소화되어야 한다.
3. 중복 제거 $\rightarrow$ 비트율 감소

• 알파벳에 기반한 이산 무기억 소스 고려 : $S = \{s_0, s_1, \ldots, s_k\}$
• $s_i$의 확률: $p_{i}$
• $s_i$의 코드 길이: $l_i$
• 평균 코드 길이(심볼 당 평균 비트 수): $L = \sum_{k=0}^{K-1} p_k \cdot l_k$

• $L$의 최소한 가능한 값: $L_{min}$
• 소스의 코딩 효율성: $\eta=\frac{L_{min}}{L}$

• 데이터 압축
  1. 전송 전에 중복 정보 제거
  2. 손실 없는 데이터 압축
  3. 이산 무기억 소스(discrete memoryless source)의 출력을 나타내는 소스코드는 유일하게 복호화 가능

다른 코드의 접두어가 아닌

가변 길이 소스 코드

• 접두사 코드의 특성
  1. 접두사 코드는 유일하게 복호화 가능
  2. 접두사 코드의 역은 항상 참이 아님 → 모든 유일하게 복호화할 수 있는 코드가 접두사 코드인 것은 아님

• 확률들의 총합: $1 = \sum_{k=0}^{K-1} p_k = \sum_{k=0}^{K-1} 2^{-l_k}$
• 평균 코드 길이: $L = \sum_{k=0}^{K-1} p_k \cdot l_k = \sum_{k=0}^{K-1} 2^{-l_k} \cdot l_k$

1. 기호 확률을 감소하는 순서로 배열 후 트리의 리프 노드로 간주
2. 노드가 하나 이상 남을 때 까지 다음을 반복
   • 가장 낮은 확률을 가진 두 노드를 선택 후 가장 낮은 노드에는 0, 높은 노드에는 1을 할당(반대도 가능, but 일관적이어야 함)
   • 두 노드를 병합하여 하나의 노드 생성, 그 확률은 두 노드의 확률의 합이 됨
   • 1단계로 돌아가기
3. 각 기호에 대해, 리프 노드에서 트리의 루트까지의 경로를 따라 이진 코드 생성
   • 리프 노드의 비트는 부호어(codeword)의 마지막 비트가 된다.

• 분산은 부호어 길이의 변동성을 측정하는 것
  $\sigma^2 = \sum_{k=0}^{K-1} p_k (l_k - \overline{L})^2$
• 오류를 피하고자
  분산이 큰
  허프먼 트리를 선택
  → 분산이 높은 트리는 부호의 길이가 더 다양하므로 오류를 더 잘 처리할 수 있다.

• 분산이 높은 트리는 오류를 더 잘 처리할 수 있다.