📂양자정보이론

정보이론에서 부호화, 복호화

양자정보이론

[ 펼치기 · 접기 ] 양자계산 논리게이트 비트 · 부울함수(AND · OR · NOT · XOR · NAND · NOR · CNOT · CCNOT · CSWAP) · 범용 게이트 · 복제 함수 · 사영 · 주입 양자게이트 큐비트 · 양자 얽힘 · 양자 회로 · 양자 게이트(파울리 게이트 · 위상 게이트 · 아다마르 게이트 · 양자 CNOT · 교환 게이트 · 양자 CSWAP · 양자 CSWAP) · 솔베이-키타예프 정리 · 복제 불가 정리 정보이론 고전정보이론 정보량 · 엔트로피(결합 엔트로피 · 조건부 엔트로피 · 상대적 엔트로피 · 상호 정보 ) · 부호화 · 복호화 양자정보이론 TBD · TBD · TBD 관련 분야 선형대수 · 양자역학

정의¹

알파벳들의 집합을 $\Sigma$라고 하자. 다음과 같이 정의되는 $f_{n}$을 압축률^{compression rate}이 $0 \lt \alpha \le 1$인 코딩 함수^{encoding scheme, 부호화}라고 한다.

$$ f_{n} : \Sigma^{n} \to \left\{ 0, 1 \right\}^{\lfloor \alpha n \rfloor} $$

아래와 같은 $g_{n}$을 압축률이 $\alpha$인 디코딩 함수^{decoding scheme, 복호화}라고 한다.

$$ g_{n} : \left\{ 0, 1 \right\}^{\lfloor \alpha n \rfloor} \to \Sigma^{n} $$

설명

쉽게 말해서 압축률이란 알파벳들을 2진수로 매핑할 때, $0$과 $1$의 개수를 알파벳의 개수로 나눈 것이다. 예를들어 $\text{LESSERAFIM} \mapsto 101_{(2)}$과 같은 매핑이라면 압축률은 다음과 같다.

$$ 0.3 = \dfrac{3}{10} = \dfrac{\left| \left\{ 1, 0, 1 \right\} \right|}{ \left| \left\{ L, E, S, S, E, R, A, F, I, M \right\} \right| } $$

데이터의 양이 많으면 이를 효율적으로 저장하고 전송하는데에 어려움이 있다. 그래서 정보이론에서는 메세지 $m \in \Sigma^{n}$이 얼마나 효율적으로 압축될 수 있는지에 관심을 갖는다. 효율적이라는 말은 압축 뿐 아니라 복원에도 포함된다. $m \mapsto 1$과 같이 매핑하면 엄청난 효율로 압축한 것이지만, 이 $1$을 원래의 메세지 $m$으로 복원하는 것은 불가능하다. 따라서 $m = g_{n}(f_{n}(m))$을 만족하는 $f_{n}, g_{n}$이 존재하도록하는 최소의 $\alpha$를 찾는 것이 곧 메세지를 효율적으로 압축하는 것이다. 이는 정보이론의 아버지 클로드 섀넌에 의해 수학적으로 정리되었다.

• 잡음이 없는 코딩 정리
• 잡음이 있는 채널 코딩 정리

본 글에서는 메세지의 효율적인 압축에 대해 좀 더 나이브하게 설명한다. $0$과 $1$로 이루어진 길이가 $n$인 메세지를 보내려는 상황을 생각하자. 메세지에서 $0$이 등장할 확률이 $p$라면 $1$이 나올 확률은 $1-p$이다.

큰 수의 법칙

$\left\{ X_{i} \right\}_{i=1}^{n}$을 서로 독립인 확률변수이라고 하자. $X_{i}$들의 평균이 $\mu$이면, 임의의 $\epsilon \gt 0$에 대해 다음이 성립한다.

$$ \lim\limits_{n \to \infty} P\left( \left| \dfrac{1}{n}\sum\limits_{i=1}^{n}X_{i} - \mu \right| \ge \epsilon \right) = 0 $$

큰 수의 법칙은 시행횟수 $n$이 충분히 크면, 표본평균 $\dfrac{1}{n}\sum\limits_{i=1}^{n}X_{i}$이 모평균 $\mu$에 충분히 가깝다는 것을 의미한다. 이에 따라서 $n$이 충분히 클 때 메세지에서 $0$의 개수는 $np$이고 $1$의 개수는 $n(1-p) = (n - np)$이다. 이러한 $0$과 $1$로 만들 수 있는 메세지의 경우의 수는 $n$개의 자리에서 $0$이 들어갈 자리 $np$개를 순서에 상관없이 뽑는 것이므로 다음과 같다.

$$ \dfrac{n!}{(np)! (n-np)!} $$

이 메세지들에 이진법으로 번호를 붙여 구분하려면 필요한 비트의 개수는 다음과 같다.

$$ \begin{equation} \log_{2}\dfrac{n!}{(np)! (n-np)!} \end{equation} $$

스털링 공식

$$ \log_{2} n! \approx n \log_{2} n - n \log_{2}e $$

$(1)$을 스털링 공식으로 근사하면 다음과 같다.

$$ \begin{align*} & \log_{2} n! - \log_{2}(np)! - \log_{2}(n-np)! \\ &\approx \left( n \log_{2} n - n \log_{2}e \right) - \left( np \log_{2} (np) - np \log_{2}e \right) \\ &\qquad - \left( (n-np) \log_{2} (n-np) - (n-np) \log_{2}e \right) \\ &= n \log_{2} n - {\color{red}\cancel{\color{black}n \log_{2}e}} - np \log_{2} (np) + {\color{green}\cancel{\color{black}np \log_{2}e}} \\ &\qquad - (n-np) \log_{2} (n-np) + ({\color{red}\cancel{\color{black}n}}-{\color{green}\cancel{\color{black}np}}) \log_{2}e \\ &= n \log_{2} n - np \log_{2} n - np \log_{2} p - n\log_{2} n(1-p) + np\log_{2} n(1-p) \\ &= n \log_{2} n - np \log_{2} n - np \log_{2} p \\ &\qquad - n\log_{2} n - n\log_{2}(1-p) + np\log_{2} n + np\log_{2} (1-p) \\ &= - np \log_{2} p - n\log_{2}(1-p) + np\log_{2} (1-p) \\ &= - np \log_{2} p - n(1-p)\log_{2}(1-p) \\ &= n\Big(- p \log_{2} p - (1-p)\log_{2}(1-p) \Big) \end{align*} $$

괄호 안의 식은 엔트로피이다. 따라서 다음을 얻는다.

$$ \log_{2}\dfrac{n!}{(np)! (n-np)!} \approx nH(p) $$

따라서 $n$이 충분히 클 때 $nH(p)$개의 비트로 코딩하는 것이 효율적이고, 효율적인 압축률은 $H(p) = \dfrac{nH(p)}{n}$이다. 이 결과는 확률변수 $X$의 엔트로피란 곧 $X$의 독립시행으로 만들어지는 메세지의 압축 효율이라는 것을 의미한다.

위의 내용을 일반적으로 얘기해보자. 어떤 알파벳 $x_{i}$가 등장할 확률을 $p(x_{i})$라고 하면 메세지에서 알파벳 $x_{i}$가 등장하는 횟수는 평균적으로 $np(x_{i})$이다. 알파벳을 $k \ge 2$개 써서 만든 길이가 $n$인 메세지의 수는 다음과 같다.

$$ \dfrac{n!}{\prod\limits_{1\le i \le k}(np(x_{i}))!} $$

이 메세지들에 이진법으로 번호를 붙이면,

$$ \begin{align*} &\log_{2} \dfrac{n!}{\prod\limits_{1\le i \le k}(np(x_{i}))!} \\ &= \log_{2}n! - \sum\limits_{1\le i \le k}\log_{2}(np(x_{i}))! \\ &\approx \left( n \log_{2} n - n \log_{2}e \right) - \sum\limits_{1\le i \le k}\Big( np(x_{i})\log_{2}(np(x_{i})) - np\log_{2}e \Big) \\ &= - n\sum\limits_{1\le i \le k} p(x_{i})\log_{2}p(x_{i}) \\ &= - nH \end{align*} $$