잡음 채널 부호화 정리

정보 이론에서 잡음 채널 부호화 정리(영어: Noisy-channel coding theorem, 때로는 섀넌 정리(Shannon's theorem) 또는 섀넌 한계(Shannon's limit))는 통신 채널의 잡음 오염도가 주어지면 계산 가능한 최대 속도까지 채널을 통해 이산 데이터(디지털 정보)를 거의 오류 없이 통신하는 것이 (이론적으로) 가능함을 확립한다. 이 결과는 1948년 클로드 섀넌이 발표했으며, 부분적으로는 해리 나이퀴스트와 랄프 하틀리의 초기 작업 및 아이디어에 기반을 두었다.

통신 채널의 섀넌 한계 또는 섀넌 용량은 특정 잡음 수준에서 링크가 무작위 데이터 전송 오류에 노출될 경우 이론적으로 채널을 통해 전송될 수 있는 오류 없는 데이터의 최대 속도를 의미한다. 이는 섀넌(1948)이 처음 설명했으며, 그 직후 섀넌과 워런 위버가 저술한 의사소통의 수학적 이론(1949년)이라는 책으로 출판되었다. 이는 현대 정보 이론의 학문 분야를 확립했다.

개요

1948년 클로드 섀넌이 발표한 이 정리는 잡음 간섭 및 데이터 손상 수준에 대한 오류 정정 방법의 최대 효율성을 설명한다. 섀넌의 정리는 통신 및 데이터 저장 모두에서 광범위한 응용 분야를 가지고 있다. 이 정리는 현대 정보 이론 분야에 근본적인 중요성을 지닌다. 섀넌은 증명의 개요만 제시했다. 이산 사례에 대한 첫 번째 엄격한 증명은 (Feinstein 1954)에 제시되어 있다.

섀넌 정리는 채널 용량 C를 가진 잡음 채널과 속도 R로 전송되는 정보가 주어졌을 때, 만약 $R<C$이면 수신기에서 오류 확률을 임의로 작게 만들 수 있는 부호가 존재한다고 명시한다. 이는 이론적으로, 정보는 제한 속도 C 미만의 어떤 속도로도 거의 오류 없이 전송될 수 있음을 의미한다.

그 역도 중요하다. 만약 $R>C$이면, 임의로 작은 오류 확률은 달성할 수 없다. 모든 부호는 특정 양의 최소 수준보다 큰 오류 확률을 가지며, 이 수준은 속도가 증가함에 따라 증가한다. 따라서 정보는 채널 용량을 초과하는 속도로 채널을 통해 안정적으로 전송될 수 있다고 보장할 수 없다. 이 정리는 속도와 용량이 동일한 드문 상황을 다루지 않는다.

채널 용량 $C$는 채널의 물리적 속성으로부터 계산될 수 있으며, 가우스 잡음이 있는 대역 제한 채널의 경우 섀넌-하틀리 정리를 사용한다.

"메시지를 3번 보내고 사본이 다를 경우 셋 중 둘이 일치하는 투표 방식을 사용하라"와 같은 간단한 방식은 비효율적인 오류 정정 방법이며, 데이터 블록이 오류 없이 통신될 수 있음을 점근적으로 보장할 수 없다. 리드-솔로몬 부호와 같은 고급 기술과 최근에는 저밀도 패리티 검사(LDPC) 부호 및 터보 부호가 이론적인 섀넌 한계에 훨씬 더 가까이 다가가지만, 높은 계산 복잡성을 대가로 한다. 이러한 고효율 부호와 오늘날의 디지털 신호 처리 장치의 계산 능력을 사용하면 이제 섀넌 한계에 매우 가깝게 도달하는 것이 가능하다. 실제로 LDPC 부호는 섀넌 한계의 0.0045dB 이내에 도달할 수 있음이 입증되었다(이진 가산 백색 가우스 잡음 (AWGN) 채널의 경우, 매우 긴 블록 길이).

수학적 진술

채널의 잡음(비트 플립 확률; x축)에 따라 페이로드에 사용할 수 있는 채널 용량의 비율(y축)을 보여주는 그래프

통신 시스템의 기본 수학적 모델은 다음과 같다.

${\xrightarrow[{\text{Message}}]{W}}{\begin{array}{|c| }\hline {\text{Encoder}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Encoded \atop sequence} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Channel}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Received \atop sequence} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Decoder}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Estimated \atop message} }]{\hat {W}}}$

메시지 W는 인코딩 및 디코딩 함수를 사용하여 잡음 채널을 통해 전송된다. 인코더는 W를 길이 n의 미리 정의된 채널 기호 시퀀스로 매핑한다. 가장 기본적인 모델에서 채널은 각 기호를 다른 기호와 독립적으로 왜곡한다. 채널의 출력(수신된 시퀀스)은 시퀀스를 메시지의 추정치로 매핑하는 디코더로 공급된다. 이 설정에서 오류 확률은 다음과 같이 정의된다.

$P_{e}={\text{Pr}}\left\{{\hat {W}}\neq W\right\}.$

정리(섀넌, 1948):

1. 모든 이산 무기억 채널에 대해, 상호정보 $I(X;Y)$로 정의되는 채널 용량 $C$는 다음과 같은 속성을 가진다.

$\ C=\sup _{p_{X}}I(X;Y)$

모든 $\epsilon >0$ 및 $R<C$에 대해, 충분히 큰 $N$에 대해, 길이 $N$의 코드와 속도 $\geq R$ 및 디코딩 알고리즘이 존재하여 최대 블록 오류 확률이 $\leq \epsilon$이다.

2. 비트 오류 확률 $p_{b}$가 허용되는 경우, 다음을 만족하는 속도 $R(p_{b})$까지 달성할 수 있다.

$R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.$

여기서 $H_{2}(p_{b})$는 이진 엔트로피 함수이다.

$H_{2}(p_{b})=-\left[p_{b}\log _{2}{p_{b}}+(1-p_{b})\log _{2}({1-p_{b}})\right]$

3. 모든 $p_{b}$에 대해 $R(p_{b})$보다 큰 속도는 달성할 수 없다.

(MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11)

증명 개요

정보 이론의 다른 여러 주요 결과와 마찬가지로 잡음 채널 코딩 정리의 증명에는 달성 가능성 결과와 일치하는 역 결과가 포함된다. 이 두 구성 요소는 이 경우 잡음 채널을 통해 통신할 수 있는 가능한 속도 집합을 제한하는 역할을 하며, 일치는 이러한 경계가 엄격한 경계임을 보여주는 역할을 한다.

다음 개요는 정보 이론 텍스트에서 연구할 수 있는 여러 가지 스타일 중 하나일 뿐이다.

이산 무기억 채널의 달성 가능성

달성 가능성에 대한 이 특정 증명은 점근 등분 분할 특성(AEP)을 사용하는 증명 스타일을 따른다. 다른 스타일은 오류 지수를 사용하는 정보 이론 텍스트에서 찾을 수 있다.

두 가지 유형의 증명 모두 채널에서 사용되는 코드북이 무작위로 구성되는 무작위 코딩 인수를 사용한다. 이는 분석을 더 간단하게 만드는 동시에 채널 용량 미만의 모든 데이터 속도에서 원하는 낮은 오류 확률을 만족하는 코드의 존재를 증명한다.

AEP 관련 인수에 의해, 채널, 길이 $n$의 소스 기호 문자열 $X_{1}^{n}$ 및 길이 $n$의 채널 출력 문자열 $Y_{1}^{n}$이 주어지면 다음과 같이 공동 전형 집합을 정의할 수 있다.

$A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}$

$2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}$

$2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}$

${2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}$

두 시퀀스 ${X_{1}^{n}}$과 $Y_{1}^{n}$이 위에서 정의된 공동 전형 집합에 속하면 공동 전형적이라고 말한다.

단계

1. 무작위 코딩 인수의 스타일로, 우리는 확률 분포 Q에서 길이 n의 코드워드 $2^{nR}$개를 무작위로 생성한다.
2. 이 코드는 송신자와 수신자에게 공개된다. 또한 사용되는 채널의 전이 행렬 $p(y|x)$를 알고 있다고 가정한다.
3. 메시지 W는 코드워드 집합에 대한 균일 분포에 따라 선택된다. 즉, $Pr(W=w)=2^{-nR},w=1,2,\dots ,2^{nR}$이다.
4. 메시지 W는 채널을 통해 전송된다.
5. 수신자는 $P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))$에 따라 시퀀스를 수신하고, Y와 공동 전형적인 코드워드가 정확히 1개 존재하면 소스 시퀀스로 디코딩한다. 공동 전형적인 코드워드가 없거나 1개 이상이면 오류가 선언된다. 디코딩된 코드워드가 원래 코드워드와 일치하지 않는 경우에도 오류가 발생한다. 이를 전형 집합 디코딩이라고 한다.

이 방식의 오류 확률은 두 부분으로 나뉜다.

1. 첫째, 수신된 Y 시퀀스에 대해 공동 전형적인 X 시퀀스가 발견되지 않는 경우 오류가 발생할 수 있다.
2. 둘째, 잘못된 X 시퀀스가 수신된 Y 시퀀스와 공동 전형적인 경우 오류가 발생할 수 있다.

• 코드 구성의 무작위성으로 인해 모든 코드에 대해 평균화된 평균 오류 확률은 전송된 인덱스에 의존하지 않는다고 가정할 수 있다. 따라서 일반성을 잃지 않고 W = 1이라고 가정할 수 있다.
• 공동 AEP에 따라, 공동 전형적인 X가 존재하지 않을 확률은 n이 커질수록 0에 수렴한다. 이 오류 확률을 $\varepsilon$로 제한할 수 있다.
• 또한 공동 AEP에 따라, 특정 $X_{1}^{n}(i)$와 W = 1에서 발생하는 $Y_{1}^{n}$이 공동 전형적일 확률은 $\leq 2^{-n(I(X;Y)-3\varepsilon )}$이다.

정의: $E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}$

는 메시지 1이 전송될 때 수신된 시퀀스와 메시지 i가 공동 전형적인 사건이다.

${\begin{aligned}P({\text{error}})&{}=P({\text{error}}|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})\\&{}\leq P(E_{1}^{c})+(2^{nR}-1)2^{-n(I(X;Y)-3\varepsilon )}\\&{}\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}.\end{aligned}}$

$n$이 무한대로 갈 때, 채널에 대해 $R<I(X;Y)$이면 오류 확률이 0으로 수렴함을 알 수 있다.

마지막으로, 평균 코드북이 "좋다"고 입증되었으므로, 평균보다 성능이 우수한 코드북이 존재하며, 따라서 잡음 채널을 통한 통신에서 임의로 낮은 오류 확률에 대한 우리의 요구를 충족시킨다.

이산 무기억 채널에 대한 약한 역

$2^{nR}$개의 코드워드를 가진 코드가 있다고 가정하자. W를 이 집합에서 균일하게 인덱스로 추출하자. $X^{n}$과 $Y^{n}$을 각각 전송된 코드워드와 수신된 코드워드라고 하자.

1. $nR=H(W)=H(W|Y^{n})+I(W;Y^{n})$ 엔트로피와 상호정보 관련 항등식 사용
2. $\leq H(W|Y^{n})+I(X^{n}(W);Y^{n})$ X가 W의 함수이므로
3. $\leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})$ 파노 부등식 사용
4. $\leq 1+P_{e}^{(n)}nR+nC$ 용량이 상호정보를 최대화한다는 사실에 의해.

이 단계들의 결과는 $P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}$이다. 블록 길이 $n$이 무한대로 갈 때, R이 C보다 크면 $P_{e}^{(n)}$은 0에서 벗어나 제한된다는 것을 얻는다. R이 C보다 작을 때만 임의로 낮은 오류율을 얻을 수 있다.

이산 무기억 채널에 대한 강한 역

1957년 울포비츠(Wolfowitz)가 증명한 강한 역 정리는 다음과 같이 명시한다.

$P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}$

어떤 유한 양의 상수 $A$에 대해. 약한 역 정리는 $n$이 무한대로 갈 때 오류 확률이 0에서 멀리 떨어진다는 것을 명시하지만, 강한 역 정리는 오류가 1로 수렴한다는 것을 명시한다. 따라서 $C$는 완벽하게 신뢰할 수 있는 통신과 완전히 신뢰할 수 없는 통신 사이의 날카로운 임계값이다.

비정상 무기억 채널에 대한 채널 코딩 정리

채널이 무기억이지만, 그 전이 확률이 송신자와 수신자 모두에게 알려진 방식으로 시간에 따라 변한다고 가정한다.

이때 채널 용량은 다음과 같이 주어진다.

$C=\lim \inf \max _{p^{(X_{1})},p^{(X_{2})},...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i}).$

최댓값은 각 채널에 대한 용량 달성 분포에서 얻어진다. 즉, $C=\lim \inf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}$ 여기서 $C_{i}$는 i번째 채널의 용량이다.

증명의 개요

증명은 채널 코딩 정리의 증명과 거의 동일하게 진행된다. 달성 가능성은 각 심볼이 해당 채널에 대한 용량 달성 분포에서 무작위로 선택되는 무작위 코딩에서 따른다. 전형성 주장은 점근 등분 분할 특성 문서에 정의된 비정상 소스에 대한 전형 집합의 정의를 사용한다.

${\frac {1}{n}}\sum _{i=1}^{n}C_{i}$가 수렴하지 않을 때 하극한의 기술적 측면이 작용한다.

같이 보기

• 점근 등분 분할 특성 (AEP)
• 파노 부등식
• 부호율-변형 이론
• 섀넌의 원천 코딩 정리
• 섀넌-하틀리 정리
• 터보 부호

각주

• Aazhang, B. (2004). “Shannon's Noisy Channel Coding Theorem” (PDF). 《Connections》. 
• Cover, T.M.; Thomas, J.A. (1991). 《Elements of Information Theory》. Wiley. ISBN 0-471-06259-6. 
• Fano, R.M. (1961). 《Transmission of information; a statistical theory of communications》. MIT Press. ISBN 0-262-06001-9. 
• Feinstein, Amiel (September 1954). 《A new basic theorem of information theory》. 《Transactions of the IRE Professional Group on Information Theory》 4. 2–22쪽. Bibcode:1955PhDT........12F. doi:10.1109/TIT.1954.1057459. hdl:1721.1/4798. 
• Lundheim, Lars (2002). 《On Shannon and Shannon's Formula》 (PDF). 《Telektronik》 98. 20–29쪽. 
• MacKay, David J.C. (2003). 《Information Theory, Inference, and Learning Algorithms》. Cambridge University Press. ISBN 0-521-64298-1.  [free online]
• Shannon, C. E. (1948). 《A Mathematical Theory of Communication》. 《Bell System Technical Journal》 27. 379–423쪽. doi:10.1002/j.1538-7305.1948.tb01338.x. 
• Shannon, C.E. (1998) [1948]. 《A Mathematical Theory of Communication》. University of Illinois Press. 
• Wolfowitz, J. (1957). 《The coding of messages subject to chance errors》. 《Illinois J. Math.》 1. 591–606쪽. doi:10.1215/ijm/1255380682.