부호율-변형 이론

3. 수학적 모델링

가우시안이고 독립 항등 분포(i.i.d)인 신호 $x$에 대한 부호율-변형 함수는 다음과 같이 주어진다.^[2]

:$R(D)\; =\; \backslash left\backslash \{\; \backslash begin\{matrix\}$

\frac{1}{2}\log_2(\sigma_x^2/D ), & \mbox{if } D \le \sigma_x^2 \\ \\

0, & \mbox{if } D > \sigma_x^2

\end{matrix} \right.



여기서 $\backslash sigma\_x^2$은 신호 $x$의 분산(크기)이다. 이 식은 왜곡(D)이 신호의 분산보다 커질 수 없으며, 왜곡을 줄이려면 비트율(R)을 늘려야 함을 의미한다. distortion의 양은 원신호의 전력보다 커질 수 가 없다는 것이 한 가지이다. 그리고 distortion을 줄이기 위해서는 계속 bit수를 늘려야 함을 의미한다. 최대 distortion은 신호의 전력만큼이면 SDR로 나타내면 0dB이다. 여기서 3dB를 올려갈 때마다 1bit씩 추가로 늘어나야 한다. Distortion에 의한 SDR은 15dB까지 올리려고 하면 최소 5bits가 필요하다는 의미이다. 신호 대 왜곡 비(SDR)를 3dB 높일 때마다 1bit씩 추가해야 한다.^[2]

주의해야 할 점은 SDR에 있어서 필요한 rate는 원 신호의 전력의 절대적인 값과는 상관없다는 점이다. 통신 시스템의 성능이 신호대 오류의 전력비율로 결정되는 만큼 rate와 SDR과의 상관관계는 신호의 절대전력이 아니라 상대전력비로 결정이 된다.

3. 1. 가우시안 신호

3. 2. 베르누이 신호

4. 왜곡 함수 (Distortion Function)

왜곡 함수는 원본 기호 $x$를 근사 기호 $\backslash hat\{x\}$로 표현하는 비용을 측정한다. 대표적인 왜곡 함수로는 해밍 왜곡과 제곱 오차 왜곡이 있다.
해밍 왜곡 (Hamming Distortion)원본 기호와 복원된 기호가 같으면 왜곡이 없고, 다르면 왜곡이 1이다.

:$d(x,\backslash hat\{x\})\; =\; \backslash begin\{cases\}$

0 & \text{if } x = \hat{x} \\

1 & \text{if } x \neq \hat{x}

\end{cases}


제곱 오차 왜곡 (Squared-Error Distortion)원본 신호와 복원된 신호 간 차이의 제곱으로 왜곡을 측정한다.

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

4. 1. 해밍 왜곡 (Hamming Distortion)

4. 2. 제곱 오차 왜곡 (Squared-Error Distortion)

5. 율-왜곡 함수 (Rate-Distortion Function)

율-왜곡 함수는 주어진 왜곡 수준(D)에서 달성 가능한 최소 비트율(R)을 나타내는 함수이다. 율-왜곡 함수는 다음 최소화 문제의 해로 찾아진다.

:$\backslash inf\_\{Q\_\{Y\backslash mid\; X\}(y\backslash mid\; x)\}\; I\_Q(Y;X)\; \backslash text\{\; subject\; to\; \}\; D\_Q\; \backslash le\; D^*.$

여기서 $Q\_\{Y\backslash mid\; X\}(y\backslash mid\; x)$는 검정 채널(test channel)이라고도 불리며, 주어진 입력(원 신호) $X$에 대한 통신 채널 출력(압축된 신호) $Y$의 조건부 확률 밀도 함수(PDF)이다. $I\_Q(Y;X)$는 $Y$와 $X$ 사이의 상호 정보량으로, 다음과 같이 정의된다.

:$I(Y;X)\; =\; H(Y)\; -\; H(Y\backslash mid\; X)\; \backslash ,$

여기서 $H(Y)$와 $H(Y\backslash mid\; X)$는 각각 출력 신호 ''Y''의 엔트로피와 입력 신호가 주어졌을 때 출력 신호의 조건부 엔트로피이다.

상호 정보량은 수신자가 송신자의 신호에 대해 갖는 '사전' 불확실성(''H''(''Y''))에서 송신자의 신호에 대한 정보를 받은 후 남은 불확실성($H(Y\backslash mid\; X)$)을 뺀 값으로 이해할 수 있다.

율-왜곡 함수를 계산하려면 입력 $X$의 확률적 설명($P\_X\; (x)$)이 필요하며, 주어진 왜곡 $D^\{*\}$에 대해 율을 최소화하는 조건부 PDF $Q\_\{Y\backslash mid\; X\}(y\backslash mid\; x)$를 찾아야 한다.

이 최적화 문제에 대한 해석적 표현은 일반적으로 구하기 어렵지만, 섀넌 하한 (SLB)을 포함하여 율-왜곡 함수에 대한 상한 및 하한이 존재한다. 제곱 오차와 무기억 소스의 경우, 유한한 미분 엔트로피를 가진 임의의 소스에 대해 다음과 같은 섀넌 하한을 갖는다.

:$R(D)\; \backslash ge\; h(X)\; -\; h(D)\; \backslash ,$

여기서 ''h''(''D'')는 분산 D를 갖는 가우스 확률 변수의 미분 엔트로피이다.

블라후트-아리모토 알고리즘은 임의의 유한 입력/출력 알파벳 소스의 율-왜곡 함수를 수치적으로 구하는 반복 기법이다.

메모리가 있는 정상 소스를 사용할 때는 율 왜곡 함수의 정의를 수정해야 하며, 증가하는 길이의 시퀀스에 대한 극한의 의미로 이해해야 한다.

가우시안이고 i.i.d인 신호 $x$에 대한 부호율-변형 함수는 다음과 같이 주어진다.

:$R(D)\; =\; \backslash left\backslash \{\; \backslash begin\{matrix\}$

\frac{1}{2}\log_2(\sigma_x^2/D ), & \mbox{if } D \le \sigma_x^2 \\ \\

0, & \mbox{if } D > \sigma_x^2

\end{matrix} \right.



여기서 $\backslash sigma\_x^2$은 신호 $x$의 크기이다. 이 수식의 의미는 distortion의 양은 원신호의 전력보다 커질 수 없고, distortion을 줄이기 위해서는 계속 bit수를 늘려야 함을 의미한다.

6. 섀넌 하한 (Shannon Lower Bound)

7. 블라후트-아리모토 알고리즘 (Blahut-Arimoto Algorithm)

8. 채널 용량과의 관계

사용자가 왜곡 ''D''를 초과하지 않는 상태로 소스에 대한 정보를 전송하려 한다고 가정할 때, 부호율-왜곡 이론에 따르면 소스에서 사용자에게 최소 $R(D)$ 비트/심볼의 정보가 도달해야 한다.^[4] 소스 엔트로피가 ''H'' 비트/심볼이고, 채널 용량이 ''C'' (여기서 )인 경우, 섀넌의 채널 부호화 정리에 따르면, 주어진 채널을 통해 이 정보를 전송할 때 $H-C$ 비트/심볼이 손실된다.^[4] 사용자가 최대 왜곡 ''D''로 재구성할 수 있기를 바란다면, 전송 중에 손실된 정보가 $H-R(D)$ 비트/심볼의 최대 허용 손실을 초과하지 않도록 요구해야 한다.^[4] 즉, 채널 용량은 최소한 $R(D)$ 이상이어야 한다.^[4]

9. 응용

참조

_[1] 학회 Rethinking Lossy Compression: The Rate-Distortion-Perception Tradeoff http://proceedings.m[...] PMLR 2019
_[2] 서적
_[3] 서적 Elements of Information Theory Wiley
_[4] 서적 Rate Distortion Theory: A Mathematical Basis for Data Compression https://archive.org/[...] Prentice Hall