Lossy coding과 Entropy,Distortion

1.Lossy coding 손실 부호화

Lossy coding 의 Transmission system(전송 시스템)에서는 decoding 된 출력 Y'이 Y와 같다고 가정한다.
만약 Y를 주어진 rate로 전송하고 싶을 때, 우리가 얻을 수 있는 best quality의 X'은 무엇일까?

Source coding and transmission

 

2.Distortion(왜곡)

Lossy coding(손실 부호화)는 Receiver 수신단에서 손실(Loss / Degradation)을 만들기에, 원래 신호와 수신된 신호의 차이를 계산하여 Distortion을 측정할 수 있다.

$X,\hat{X} \in R$일 때,

$d\left(x,\hat{x} \right)={\left(x-\hat{x} \right)}^2$ : Quadratic distortion

$d\left(x,\hat{x} \right)=|x-\hat{x} |$ : Absolute value distortion

$X,\hat{X} \in N\;\mathrm{or}\;\left\lbrace 0,1\right\rbrace$ 일 때,

$d_H \left(x,\hat{x} \right)=0\;\mathrm{if}\;x=\hat{x} \;,\mathrm{else}\;1$  

$D=E_x \left(d_H \left(x,\hat{x} \right)\right)$ : Hamming distortion

실제 일련의 Sequence가  $x_1 ,x_2 ,\ldotp \ldotp \ldotp \ldotp x_N$로 부호화 될 때, $\hat{x_1 } ,\hat{x_2 } ,\ldotp \ldotp \ldotp \ldotp \hat{x_N }$ 로 복호화 된다고 가정한다. 이 때 평균 제곱 오차를 계산 할 수 있다.

$\delta_d^2 =\frac{1}{N}\sum_{n=1}^N {\left(x_n -\hat{x_n } \right)}^2$ : Mean square error

${\;\delta }_x^2$는 신호 x의 variance(분산)값이다. 위에서 구한 평균 제곱 오차 값($\delta_d^2$)로 나눠주면 SNR (Signal to noise ration)값이 된다. Noise가 클 수록 SNR이 작아지기에 SNR값은 클 수록 좋다! log를 씌워주면 dB 스케일이된다.

$\mathrm{SNR}=\frac{{{\;\delta }_x^2 } }{\delta_d^2 }$

${\mathrm{SNR}}_{\mathrm{dB}} =10{\mathrm{log}}_{10} \frac{{{\;\;\delta }_x^2 } }{\delta_d^2 }$

마찬가지로 PSNR값도 계산할 수 있는데, PSNR은 Peak Signal to Noise ratio (dB)의 약자로 다음과 같이 계산한다. $x_{\mathrm{max}}^2$는 x값 중 가장 큰 값의 제곱이다.

${\mathrm{PSNR}}_{\mathrm{dB}} =10{\mathrm{log}}_{10} \frac{x_{\mathrm{max}}^2 }{\delta_d^2 }$

이렇게 SNR, PSNR 외에도 손실 부호화의 Quality를 측정할 수 있는 방법의 예로 SSIM(Image), VNAF(video)가 있다.

3. Lossy coding and Information theory 손실 부호와와 정보 이론

예제) 위의 1번 그림에서와 같이, Source $X$가 Symbol을 0부터 15까지 생성한다고 해보자. Source coder는 $X$로부터 3개의 Most significant bit(MSB)만 유지하여 $Y$를 얻는다. $Y$로부터 $\hat{X}$를 복호화 하기 위해서 Least significant bit(LSB)에 0을 더해준다고 할 때 아래와 같이 얻을 수 있다.

$X=\left\lbrace 0,1,2,3,4,5,6,7,8\ldotp \ldotp \ldotp ,15\right\rbrace$

$Y=\left\lbrace 0,1,2,3,4,5,6,7\right\rbrace$

$\hat{X} =\left\lbrace 0,2,4,6,8,10,12,14\right\rbrace$

간략히 설명하면 이진수로 나타냈을 때 $X$가 0000,0001,0010,0011,0100....1111 까지의 값을 가지고, 이렇게 MSB만 3 비트씩 취한다면 $Y$ = {000,001,010,011,100,101,110,111}를 얻게 된다. $Y$로부터  $\hat{X}$를 얻기 위해서는 오른쪽에 LSB로 0만 추가해주면 된다. $\hat{X}$={0000,0010,0110,1000,1010,1100,1110}가되고,0부터14사이의짝수값만갖는다.

Entropy 계산

X와 Y의 Entropy를 계산해보자. 이 때 쉬운 계산을 위해 X와 Y가 Uniform distribution이라고 가정한다. Uniform distiribution이란 각 Symbol이 모든 같은 확률을 균일하게 갖는 분포를 말한다.

$H\left(X\right)=-\sum_i \frac{1}{16}{\mathrm{log}}_2 \frac{1}{16}=4\mathrm{bits}/\mathrm{symbol}$

$H\left(Y\right)=-\sum_i \frac{1}{8}{\mathrm{log}}_2 \frac{1}{8}=3\mathrm{bits}/\mathrm{symbol}$

Conditional Entropy는 어떻게 계산할 까? 

$\left(X,Y\right)$ $~$ $p\left(x,y\right)$와 같은 확률 분포를 따를 때, 아래와 같이 정의된다.

Conditional entropy 정의

$H\left(X|\hat{X} \right)$를 계산하기 위해서는 먼저 조건부 확률 $P\left(x=i,\hat{x} =j\right)$를 알아야 한다.

$H\left(X|\hat{X} \right)=-\sum_i \sum_j P\left(x=i,\hat{x} =j\right){\mathrm{log}}_2 P_r \left(x=i|\hat{x} =j\right)$

$H\left(X|\hat{X} \right)=-\sum_i \sum_j P\left(x=i|\hat{x} =j\right){P\left(\hat{x} =j\right)\mathrm{log}}_2 P_r \left(x=i|\hat{x} =j\right)$

$P_r \left(\hat{x} =j\right)$는 어떻게 구할까? $P_r \left(\hat{x} =j\right)$는 부호화된 Y로부터 복호화 할 확률이다. 위에서 본 것 처럼 $\hat{X}$는 짝수 값(0,2,4,6...14)만 갖기에 홀수일 경우의 확률은 0이고, 짝수일 경우에는 1/8이다.

$P_r \left(\hat{x} =j\right)=0\;\mathrm{if}\;j\;\mathrm{is}\;\mathrm{odd}$

$P_r \left(\hat{x} =j\right)=\frac{1}{8}\;\mathrm{if}\;j\;\mathrm{is}\;\mathrm{even}\;\left\lbrace 0,2,4,6,8,\ldotp \ldotp 14\right\rbrace$

$P\left(x=i|\hat{x} =j\right)$값은 어떻게 계산할까? 복호화 된 값을 알 때, 원래의 x값의 확률이다. 
복호된 값은 Y로부터 무조건 0을 붙인 값이므로 원래의 송신한 x와 같은 확률을 1/2이다.

예를들어 j = 10 (복호화된 값  $\hat{X}$ 이라고 할 때 , $X$는 10이나 11의 값을 가진다. 

$X={1010}_2 \;\mathrm{or}\;{1011}_2$

Cross entropy의 공식에 맞게 계산을 하면 다음과 같다.

$P\left(x=i|\hat{x} =j\right)=\frac{1}{2}\;\mathrm{if}\;i=j\;\mathrm{or}\;i=j+1\;\mathrm{and}\;j\;\mathrm{even},\mathrm{else}\;0$

$H\left(X|\hat{X} \right)=\frac{1}{2}\times \frac{1}{8}\times 16=1\frac{\mathrm{bits}}{\mathrm{symbol}}$

이 뜻은, $\hat{X}$ 값을 알 때 본래의 original 값 X를 알 불확실성을 측정하면 1 bit라는 것! 바로 위의 예시의 복호된 값이 10일 때, 원래의 값이 10이나 11일 경우를 고려하면 마지막 1 bit(1010,1011)에 의해서만 값이 달라지기에 1bit가 불확실성(Entropy)의 값이 된다.

반대로, 원래 송신한 X의 값을 알 때 부호화된 값 $\hat{X}$를 알 conditional entropy: $H\left(\hat{X} |X\right)$는 어떨까?

$P\left(\hat{x} =j|x=i\right)=1\;\mathrm{if}\;i=j\;\mathrm{or}\;i=j+1\;\mathrm{and}\;j\;\mathrm{even},\mathrm{else}\;0$

계산하면 $H\left(\hat{X} |X\right)=0$의 결과를 갖는다.

계산한 Entropy값이 0이라는 것은 불확실성이 없다는 뜻이고, 이 뜻은 원래 송신한 X값을 알 때 부호화된 값 $\hat{X}$ 는 완전하게 결정된다는 것!

당연한 얘기다. 예를들어, 11을 보냈다고 할 때, 1011 에서 마지막 1을 없애고 0으로 바꾸면 1010 = 10이 된다. 

Mutual information 계산

정의) I(X;Y)는 Y를 알 때 X의 불확실성의 감소량이다.
정의) I(Y;X)는 X를 알 때 Y의 불확실성의 감소량이다.

아래의 Ven diagram과 같이 Entropy X와 Y의 교집합 부분이라고 할 수 있다.

$I\left(X;Y\right)=H\left(X\right)-H\left(X|Y\right)=H\left(Y\right)-H\left(Y|X\right)$

Mutual information은 몇가지 특성을 가지는데 바로 0보다 크거나 같은 값을 가진다는 점.

교환 법칙도 성립한다. 

자기 자신의 정보량은 자신의 Entropy값과 같다. 

$I\left(X;Y\right)\ge 0$

$I\left(X;Y\right)=I\left(Y;X\right)$

$I\left(X;X\right)=H\left(X\right)$

위의 예제에 대입해 Mutual information 값을 계산해보자. 

$H\left(X\right)=\;4\;\mathrm{bits}$

$H\left(Y\right)=3\;\mathrm{bits}$

$I\left(X;\hat{X} \right)=H\left(X\right)-H\left(X|\hat{X} \right)=4-1=3\mathrm{bits}$

$I\left(\hat{X} ;X\right)=H\left(\hat{X} \right)-H\left(\hat{X} |X\right)=3-0=3\mathrm{bits}$