[Data] Encoding

Encoding이란 말 그대로 정보를 특정 패턴과 mapping을 하는 과정이다. 이전 포스트에서도 이야기했다시피 정보는 거기에 포함된 불확실성을 줄이는데 의미가 있는 것이고, 이렇게 encoding과정을 거치게 되면 그런 목적을 어느정도 달성할 수 있다. 말이 조금 어려운 것일수도 있는데, 실제로 우리가 어떤 정보에 대한 규칙을 정의하고, 여기에 해당하는 정보가 들어왔을 때 그대로 해석하는 것으로 이해하면 좋을거 같다. 

 예를 들어서 사전에 A는 00, B는 01, C는 10, D는 11이라는 2bit information의 규칙이 정의되어 있다고 가정을 하자. 

만약 ABBA라는 정보를 얻고 싶으면 어떤 입력이 들어와야 할까? 당연히 00 01 01 00 이라는 8bit information으로 전달하면 어떨까? 만들기도 쉽고, 이런 비슷한 정보가 들어왔을 때도 해석(decoding)하기 쉽다. 이렇게 2bit이라는 고정값을 두고 변환하는 방식을 Fixed Length Encoding 이라고 한다. 장점이야 앞에서 말한것처럼 쉽다는 것인데, 문제는 쉬운만큼 유연성이 없다는 것이다. 만약 1이라는 정보를 전달하고 싶어하는데, 지금처럼 fixed length encoding 기법을 사용하게 되면 00000001이라는 정보를 보내야 한다. 1앞에 있는 7개의 0도 1이라는 정보를 전달하기 위해서 같이 포함되어야 한다는 것이다. 그냥 간단히 1만 딱 보내면 조금더 효율적으로 encoding할 수 있지 않을까 싶다.

 이런 개념이 적용된 것이 바로 Variable Length Encoding 기법이다. 이름에서 내포하고 있는 것처럼 전체 정보의 표현량 자체가 유동적으로 변할 수 있다는 것이다.

여기 나온것처럼 A, B, C, D값에 각각 다른 length의 data를 담고 있다고 정의할 때, ABBA를 전달하고자 하면 위에서 표현한 것처럼 01 1 1 01 이라고 해주면 된다. 그러면 앞에서 소개한 Fixed Length Encoding에 비해서 bit도 적게 보내면서 모든 정보량을 전달할 수 있게된다. 그런데 문제는 이렇게 length 라는 개념이 정보에 포함되게 되면, 애초에 우리의 목적이었던 불확실성을 줄이기는 커녕 오히려 늘어나게 될수도 있다는 것이다.

마지막의 예시를 보게되면 그런 불확실성이 어떤 것인지를 알 수 있다. 만약 0 1 1 0 이라는 입력을 받게 되면 우리는 이걸 어떻게 해석할 것인가? 사람에 따라서는 ABC, 혹은 ADA라고 해석할 수도 있을 것이다. 그러면 우리가 전달하고자 했던 ABBA에 대한 불확실성이 커지게 되는 것이다. 

 이걸 해결하기 위해서 기본적으로 Variable Length Encoding에 대한 규칙을 세울 때는 Binary Tree 의 원칙을 적용하도록 한다. 이 말은 즉, 같은 패턴이 나오지 않게끔 하나의 unique한 케이스로 구분하게 두자는 것이다. 이를테면 이런 것이다.

위와 같이 모든 경우에 대해서 overlap되는 구간이 없다. 그냥 보이는대로 이해하면 된다. 예를 들어 0이 딱 하나 나왔을 경우에도 B이고, 0이 연속으로 두번 나왔을 경우에도 다른 케이스에 이와 중복되는 케이스가 없기 때문에 그대로 BB라고 인지할 수 있다. 반면 1이 먼저 나온 케이스에 대해서는 그에 맞춰서 패턴을 찾아 해석하면 되겠다. 이렇게 하면 variable length encoding의 장점을 가지면서 불확실성을 해소하는데 어느정도 도움을 줄수 있지 않을까 싶다. 

 참고로 앞에서 나왔던 ABBA를 이런식으로 표현하게 되면.... 아마 쉽게 구하겠지만 11 0 0 11 이 되겠다.

출처 : MITx: 6.004.1x Computation Structures - Part 1: Digital Circuits