[정보이론] Kraft inequality(크래프트 부등식) 과 데이터 비트 표현

들어가기 앞서

 

컴퓨터는 특정 데이터를 비트로 압축시켜 표현합니다.

이 예시로는 허프만 코드가 있는데 아래 포스팅을 참고해 주시면 좋을 것 같습니다.

https://programming119.tistory.com/75

[알고리즘] 허프만 코드와 그리디 알고리즘 / Huffman code and greedy algorithm

 

---

 

Prefix code

 

Prefix code 란 특정 비트표현이 다른 비트표현과 겹쳐지지 않는 코드 입니다.

예를들어 a : 110 / b: 11 / c : 1 로 설정했다고 하죠.

다음과 같은 코드 내에서 컴퓨터가 11110 을 해독한다면 이러한 일련과정은 모호함을 발생시킬 것입니다.  b와 c가 a의 prefix 이며 , c가 b의 prefix 이기 때문에 이러한 문제점이 발생한다는 것을 깨달으실 수 있죠?

 

아이러니 하게도, 이런 preifx 가 발생하지 않게끔 잘 구현된 코드를 prefix code라고 합니다. 

보통 이러한 문제를 피하기 위해 tree 형태로 데이터를 표현하고, tree의 leaf 노드를 이용하여 표현합니다. 허프만 코드 게시글을 예시라 생각하고 생각해보면 될 것 같습니다. 당연히 허프만 코드는 prefix code 에 속합니다.

 

 

prefix code 의 예시

 

a : 0

b : 10

c : 110

d : 111

 

한번 다음 자료들을 tree로 표현해 보세요!  depth 가 2인 트리가 그려질 것이고,

a,b,c,d 들은 트리의 leaft 노드 부분이라는 것을 알 수 있을 것입니다!

 

---

 

Kraft Inequality란?

 

그렇다면 Kraft Inequality 는 무엇일까요?

prefix code를 만족시키는 코드에 대하여 다음과 같은 수식이 성립한다는 것입니다.

n_i :  코드를 표현하는데에 드는 길이 수를 의미합니다. 트리로 치면 깊이를 의미하죠.

예를들어 a : 110 이라면 비트3개가 필요하기 때문에 n_i 는 3 입니다.

 

s : 표현하는 코드의 진수 수를 의미합니다. 보통 0과 1을 이용한 비트 표현방식이기에 s = 2 인 경우가 많겠죠?

 

r : 표현하는 모든 코드의 수 입니다. 앞선 prefix code의 예시로 치면 a(0), b(10), c(110), d(111) 로 4 입니다.

 

(* s의 -n_i 승 : 데이터 압축 전의 빈도수 비율 이라고 생각할 수 있습니다.)

 

 

---

 

 

Kraft Inequality 가 의미하는 바는?

 

s의 -n_i 승 : 데이터 압축 전의 빈도수 비율의 근사값 이라고 생각할 수 있다는 것을 이해해야 합니다.

 

데이터를 압축하는 과정을 다시 한번 떠올려봅시다.

a 가 빈도수가 전체의 1/2 이었으면 아마

a는 011010 이렇게 표현되지 않고 0 이나 1로 표현이 되었을 것입니다.

그렇다는 것은 트리의 depth 가 1인 뜻이죠. 이는 Kraft Inequality 의 n_i 부분을 의미합니다.

데이터를 표현할 진수의 수 의 -n_i 승 이 의미하시는 바를 아시겠나요?

( 상황에 따라 다를 수도 있긴 합니다.)

 

 

즉, 모든 데이터들을 코드화 하여 표현했을 때에 만약에 내가 Prefix code로 잘 구현한것이 확실하다?? 그렇다면 그 빈도수 비율의 합은 1보다 작거나 같다는 뜻입니다. (잘 생각해보면 당연히 그래야합니다. 우리가 표현할 자료들을 추합할 때 빈도수 확률은 항상 합이 1이죠.)

 

결론적으로

Uniquely decodable  (prefix code이다.) => Kraft Inequality 가 성립한다.

 

라는 결론을 얻을 수 있습니다.

 

 

---

 

 

마치며

 

이번 글에서는 preifx code 와 Kraft Inequality 의 관계, Kraft Inequality의 의의를 알아봤습니다. 

Kraft Inequality 가 성립함을 증명하는 과정을 추후에 포스팅해볼까 합니다.

 

학사과정의 대학교 전공수업을 토대로 작성한 글이라 오류가 있을 수 있는 점 염두해 두시기 바라며, 틀렸다고 생각되는 부분은 피드백 남겨주시기 바랍니다.  감사합니다!