[세종대학교] [ 전자정보통신공학과] [전정통] [정보이론] 과제05(크레프트 부등식)

목차

없음

본문내용

kraft inequality를 설명하기 앞서 prefix code를 먼저 이해하자.

Prefix code : 특정 비트표현이 다른 비트표현과 겹쳐지지 않는 코드
예를 들어 a : 110 / b: 11 / c : 1 로 설정했다고 하자.
다음과 같은 코드 내에서 컴퓨터가 11110 을 해독한다면 이러한 일련과정은 모호함을 발생시킬 것이다. b와 c가 a의 prefix 이며 , c가 b의 prefix 이기 때문에 이러한 문제점이 발생한다는 것을 깨달을 수 있다.
아이러니 하게도, 이런 preifx 가 발생하지 않게끔 잘 구현된 코드를 prefix code라고 합니다. 보통 이러한 문제를 피하기 위해 tree 형태로 데이터를 표현하고, tree의 leaf 노드를 이용하여 표현한다.
ex)
a:0 b:10 c:110 d:111
다음 자료들을 tree로 표현하면 depth가 2인 트리가 그려질 것이고 a, b, c, d들은 leaft 노드 부분이라는 것을 쉽게 알 수 있다.

참고자료

· 없음