[Signal] Run-length Encoding

요새 재미있게 듣고 있는 강의중 하나가 통신 강의다. 이전에 HKUST에서 강의하던 주제가 최근에 개정되면서 다시 열렸기에 열심히 듣고 있는 중이다.

이 강의의 묘미중 하나는 Matlab이 웹페이지에 내장되어 있어서 이걸 가지고 실제로 코드도 돌려보고 과제를 풀기도 한다는 것이다. 마침 encoding과 관련한 과제 주제가 있어서 한번 소개해보고자 한다. 

 데이터가 주고 받는 통신에서 크게 고려해야 될 이슈중 하나는 바로 데이터의 사이즈가 되겠다. 아무래도 통신을 통해서 주고 받을 데이터가 커버리게 되면, 완전한 데이터를 받는데 소비되는 시간도 늘어나기도 하고, 이에 대한 전력 소모도 늘어나기 마련이다. 이 때문에 어떻게 하면 효율적으로 데이터를 전달하냐를 고민하게 된다. 되도록이면 적은 시간에 정해진 량의 데이터를 보내고, 최대한 손실이 없이 전달하는게 통신에서 추구하는 Goal이 되겠다. 그런데 결국 적은 시간에 정해진 량을 보내기 위해서는 그만큼 데이터의 크기를 줄여야되고, 이렇게 하려면 뭔가 압축하고 풀어야하는 개념이 들어가야 한다. 이 개념이 encoding/decoding이고, 이런 걸 수행하는 과정 자체를 source coding이라고 한다. 이 포스트에서 소개하려는 Run Length Encoding도 이 Source Coding의 기법 중 하나다. 

 앞에서 언급한 것처럼 어떤 이미지나 정보가 상대방에게 전송되기 위해서는 그 데이터 자체가 아닌 0과 1로 구성된 형태로 전달이 된다. 예를 들어서 이미지의 하나의 픽셀도 그 내부를 들여다보면 R,G,B값이 다 포함되어 있고, 이 값이 모두 0과 1의 binary 형태로 전달되게 된다. 이때 0과 1로 변환되고 난 결과물을 raw data라고 한다. 그런데 이런 경우를 가정해보자

[00000000000000000000000000000000000000000000000000]

 데이터가 0으로만 구성되어 있다고 가정할 때, 이 데이터를 정말 raw data 그대로 보내는 것이 효율적일까?(사실 0이 몇개인지도 모르겠다. 그냥 40개라고 치자) 만약 이걸 받아들이는 수신기의 성능이 1bit/s라고 치면 이 데이터 모두를 받아들이기 위해서 40초라는 시간이 필요하게 되는데, 이렇게 되면 위와 같은 이미지로 변환되는데, 정말 오랜 시간이 걸리게 된다. 만약 이런식의 표현 방법은 어떨까?

[0 40]

  위와 같은 notation을 정의하고 수신부에서 40개의 0을 재생산해주는 과정을 거치게 되면, 수신기도 2초만 켜져있으면 되고 그만큼 데이터도 빨리 전달이 될 것이다. 이렇게 데이터를 있는 그대로 표현하는 게 아닌 bit의 갯수로 전달하는 방식을 Run Length Encoding이라고 한다. 

강의에서 나왔던 예제는 이런거였다. 가령 우리가 전달해야 될 데이터가 Raw Data라면 그걸 바로 보내는 것이 아니라, 8 bit Run Length Code로 바꿔서 전달하게 되면 394bit의 raw data를 단지 56bit으로 바꿀 수 있게 된다. 여기서 유념해야 될것은 한번에 몇 bit씩 전달하냐에 따라서 그 값에 overflow되는 값의 표현 방식이 바뀌게 된다는 것이다. 위의 예처럼 8bit으로 전달하는 경우는 최대 표현값이 2^8 - 1 = 255 이고 이외의 값은 오른쪽의 예처럼 extended시키는 개념으로 표현하게 된다. 

 물론 Run Length Encoding만 가지고 만족할만한 결과를 얻을 수 있겠지만, 아닌 경우도 존재한다. 오히려 raw data보다 더 크기가 커질 수도 있는데, 이렇게 변환한 코드를 이전 포스트에서 다룬 주제중 하나인 Huffman coding 기법을 활용하면 효율적으로 데이터를 압축할 수 있다. 지금 위의 예시도 보면 0의 빈도가 상대적으로 많다. 이를 4bit으로도 줄일 수 있을 거 같은데... 사실 무작정 줄이기만 해서 될게 아니라 어떤 notation으로 정의가 되어야 한다. 이를 위해서는 huffman dictionary라는게 필요한데, 간단하게 설명하자면 위의 결과로 나온 Run Length Code 각각을 특정 symbol로 변환해서 전달하자는 개념이다. 이렇게 symbol로 정의하다보면 어떤 symbol은 많이 나오고 어떤 symbol은 적게 나온다는 것을 알 수 있을텐데, 이 분포도를 토대로 huffman coding을 적용하면 "정말로" 효과적인 Source coding이 된다.

 내가 언급한 모든 개념을 적용한게 과제로 딱 나와서 matlab으로 개념을 적용해보았다.

이게 original image였고, 이걸 run length encoding을 거친후 그 결과물과 각 symbol에 대한 분포도를 그려보았다.

우선 encoding이 잘되어서 오른쪽 사진과 같이 원본과 동일한 이미지가 출력되었다. 여기에서 각 symbol에 대한 확률을 토대로 huffman tree를 작성해보았다.

딱 요기까지 하면 raw_data이에 비해서 크기가 약 53%정도로 줄어든 결과를 얻을 수 있었다. 대충 이런식으로 써먹으면 통신에 있어서도 이점을 누릴 수 있고... 아무튼 계산이 좀 복잡하긴한데(matlab에는 huffmandict라는 함수도 있어서 이런 과정을 자동으로 해준다..) 한번쯤 해보면 아 이런식으로 source coding이 이뤄지는구나 라는 걸 이해할 수 있게 된다. 시간되는 사람은 인터넷에도 이런식의 예제들이 많이 있으니까 한번 해볼 것을 권한다.