오차 지수

이 글에는 여러 가지 문제가 있다. 이 문제를 개선하거나 대화 페이지에서 토의하십시오. (이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 기사는 대체로 또는 전적으로 단일 출처에 의존한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 추가 출처에 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. 출처 찾기: "오류 지수" – 뉴스 · 신문 · 책 · 학자 · JSTOR (1919년 8월) 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 제거하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2019년 8월) (이 템플릿 메시지를 제거하는 방법 및 시기 학습) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

정보 이론에서, 코드의 블록 길이에 대한 채널 코드 또는 소스 코드의 오류 지수는 코드의 블록 길이에 따라 오류 확률이 기하급수적으로 감소하는 비율이다. 형식적으로는 큰 블록 길이에 대한 코드 블록 길이에 대한 오류 확률의 음수 로그의 제한 비율로 정의된다. For example, if the probability of error ${\displaystyle P_{\mathrm {error} }}$ of a decoder drops as ${\displaystyle e^{-n\alpha }}$, where ${\displaystyle n}$ is the block length, the error exponent is ${\displaystyle \alpha }$. In this example, ${\d$$isplaystyle {\frac {-\ln P_{\mathrm {error}}{{n$$}}}}$은(는) $large{\displaystyle }$ n ${\displaystyle$ $\alpha$}에$$$$ 접근한다$.$ 예를 들어 채널 용량보다 작은 속도에 대해서는 채널 co의 오류 확률인 점증적 성격을 가진 정보가 많다.de는 블록 길이가 무한대로 될 때 0으로 만들 수 있다. 실제 상황에서는 통신 지연에 한계가 있으며 블록 길이는 제한적이어야 한다. 따라서 블록 길이가 무한대로 갈수록 오차의 확률은 어떻게 떨어지는지를 연구하는 것이 중요하다.

채널 코딩의 오류 지수

시간 내 DMC의 경우

채널 부호화 정리는 어떤 ε > 0에 대해서 그리고 채널 용량보다 작은 비율에 대해서, 충분히 긴 메시지 블록 X에 대해서 블록 오류의 확률을 > > 0보다 작게 하는 것을 보증하는 데 사용할 수 있는 인코딩 및 디코딩 체계가 있다고 기술하고 있다. 또한, 채널 용량보다 큰 비율의 경우, 수신기에서 블록 오차의 확률은 블록 길이가 무한대로 갈 때 1로 간다.

채널 코딩 설정을 다음과 같이 가정하면: 채널은 해당하는 코드 워드(길이 n)를 전송하여 $M{\displaystyle }$= ${\displaystyle {2n}^{}}$ ${\displaystyle R^{}}$ $displaystyle M=2^{nR}\}$개의 메시지를$$ 전송할 수 있다. 코드북의 각 구성요소는 확률질량함수 Q와 함께 확률분포에 따라 I.I.d.를 그린다. 디코딩 엔드에서 최대우도 디코딩이 수행된다.

$X{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ n ${\$을(를) 코드북에 $i$ {\$displaystyle$ $i$$}$의 임의 코드 워드로 두십시오$$$.$ 여기서 i ${\displaystyle$ $i$$}$은(는) $1{\displaystyle \mathrm{}}$ ${\displaystystyle$ 1$}$에서 M ${\displaystystym M}($으)로$$ 선택되었다고 가정하면 X $1n${n}{1}{1}{n}}}}}}{n$}}}}}$이 전송된다$$. $y{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$을(를) 수신한$$ 경우 코드 워드가 $X{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$로 잘못 탐지될 확률은 다음과 같다$$.

${\displaystyle P_{n}{mathrm {error} \1to 2}=\sum _{x_{2}^{n}^{n}1(p)(y_{1}^{n}\mid x_{2}^{n}})1(y_{1}^{n}}}}})p(y_{{{{n}}\mid x_{1}{1}^{{1}^{1}^{1}^{n}).}$

함수 (y )> ( y x )${\displaystyle 1(p(y_{1}^{n}{$n}\$mid x_{2$}^{n$})$ p$(y_{1}^{n})$는 상한이다.

${\displaystyle \left({\frac {p(y_{1}^{n}\mid x_{1}^{n}}}{p(y_{1}^{n})}{p(y_{1}^{n}}}}){s}}}{s}}}}}}}}}}}}}}}$

> 0 $[\$ 따라서

${\displaystyle P_{\mathrm {error} \ 1\to 2}\leq \sum _{x_{2}^{n}}Q(x_{2}^{n})\left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}.}$

총 M 메시지가 있고, 코드북의 항목이 i.i.d이므로 X ${\displaystyle {}_{}^{}}$ ${\$이(가) 다른 메시지와 혼동될$$ 확률은 위의 식에 $M{\displaystyle }$ ${\displaystyle M}$배이다$$. 조합 바운드를 사용하면 X ${\displaystyle {}_{}^{}}$ ${\$과(와) 메시지가$$ 혼동될 확률은 다음과 같다.

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\left(\sum _{x_{2}^{n}}Q(x_{2}^{n})\left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}\right)^{\rho }}$

< > ${\displaystyle 0<\rho <1$ $x{\displaystyle {}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ :

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\sum _{y_{1}^{n}}\left(\sum _{x_{1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{1-s\rho }\right)\left(\sum _{x_{2}^{n}}Q(x_{2}^{n})[p(y_{1}^{n}\mid x_{2}^{n})]^{s}\right)^{\rho }.}$

$s{\displaystyle }$= ${\displaystyle 1}$- ${\displaystyle s}$ ${\displaystyle \rho }$ ${\displaystyle s=1-s\rho }$을(를) 선택하고$$ 위의 공식에서$$ $x{\displaystyle {}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$에 대한 두 합을 결합하는 방법:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\sum _{y_{1}^{n}}\left(\sum _{x_{1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{\frac {1}{1+\rho }}\right)^{1+\rho }.}$

코드 워드 요소의 독립성 및 채널의 개별 메모리 없는 특성 사용:

${\displaystyle P_{\mathrm {error} \1\mathrm {any}\\\leq M^{\rho }\prod _{i=1}{n}\sum _{y_}\sum _{x_{i}}}}}}}}}}\preft.Q_{i}(x_{i})[p_{i}(y_{i}\mid x_{i}})^{\frac {1}{1+\rho }}}}^{1+\rho }}}}}}:{1+\rho }}}}}}}}}}}}}}}}$

코드 워드의 각 요소가 동일하게 분포되어 고정되어 있다는 사실을 사용하여 다음을 수행하십시오.

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{\frac {1}{1+\rho }}\right)^{1+\rho }\right)^{n}.}$

M을 2로^nR 교체하고 정의하는 중

${\displaystyle E_{o}(\rho ,Q)=-\ln \left(\sum _{y}\left)(\sum _{x}Q(x)[p(y\mid x)]^{1/(1+\rho )}\right)^{1+\rho }}}}$

오차가 발생할 확률은

${\displaystyle P_{\mathrm {error}}}\leq \exp(-n(E_{o})(\rho ,Q)-\rho R)).}$

Q 및 $\rho {\displaystyle }$ ${\displaystyle \rho }$을(를) 선택하여 바운드가 가장 티그되도록 해야 한다$$. 따라서 오차 지수를 다음과 같이 정의할 수 있다.

${\displaystyle E_{r}(R)=\max _{Q}\max _{\rho \in [0,1]}}E_{o}(\rho ,Q)-\rho R.\;}$

소스 코딩의 오류 지수

시간 불변 이산 메모리 소스의 경우

그 정보원 부호화 정리 김치는 어떤ε>X{X\displaystyle} 같은 0{\displaystyle \varepsilon>0}과 어떤discrete-time i.i.d. 소스와 속도를 원천의 엔트로피보다 적은 돈을 위해, 큰 충분한 n{n\displaystyle}과 n{n\displaystyle}i.i.d 인코더다. 월의 반복이다.esource, ${\displaystyle X^{1:n}}$, and maps it to ${\displaystyle n.(H(X)+\varepsilon )}$ binary bits such that the source symbols ${\displaystyle X^{1:n}}$ are recoverable from the binary bits with probability at least ${\displaystyle 1-\varepsilon }$.

$M{\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle R^{}}$ $displaystyle M=e^{nR}\,\!}$을(를) 가능한 총 메시지 수입니다$$. 다음, 각 가능한 소스 출력 시퀀스를 동일한 분포를 사용하여 다른 모든 것과 독립적으로 메시지 중 하나에 매핑하십시오. 소스가 생성되면 해당 메시지 $M{\displaystyle }$= ${\displaystyle m}$ ${\$이(가) 대상으로 전송된다$$. 메시지는 가능한 소스 문자열 중 하나로 디코딩된다. In order to minimize the probability of error the decoder will decode to the source sequence ${\displaystyle X_{1}^{n}}$ that maximizes ${\displaystyle P(X_{1}^{n}\mid A_{m})}$, where ${\displaystyle A_{m}\,}$ denotes the event that message ${\displaystyle m}$ was transmitted. 이 규칙은 $P{\displaystyle }$ (${\displaystyle }$X ${\displaystyle {}_{}^{}}$ )${\displaystyle P(X_{1}^{n})$를 최대화하는 메시지$$ $m{\displaystyle }$ ${\displaystyle m}$에 매핑되는 소스 시퀀스 집합 중에서$$ 소스 시퀀스 $X{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ m}을$($를) 찾는 것과 같다$.$ 이러한 감소는 메시지가 임의로 다른 모든 것들과 독립적으로 할당되었다는 사실에서 나타난다.

Thus, as an example of when an error occurs, supposed that the source sequence ${\displaystyle X_{1}^{n}(1)}$ was mapped to message ${\displaystyle 1}$ as was the source sequence ${\displaystyle X_{1}^{n}(2)}$. If ${\displaystyle X_{1}^{n}(1)\,}$ was generated at the source, 그러나 ( ( )> ( ( 1)) ${\displaystyle P(X_{1}^{n}(2))>P(X_{1}^{n}(1)}}$ 그러면 오류가 발생한다.

Let ${\displaystyle S_{i}\,}$ denote the event that the source sequence ${\displaystyle X_{1}^{n}(i)}$ was generated at the source, so that ${\displaystyle P(S_{i})=P(X_{1}^{n}(i))\,.}$ Then the probability of error can be broken down as ${\displaystyle P(E)=\sum _{i}P}$${\displaystyle P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\,.}$ Thus, attention can be focused on finding an upper bound to the ${\displaystyle P(E\mid S_{i})\,}$.

Let ${\displaystyle A_{i'}\,}$ denote the event that the source sequence ${\displaystyle X_{1}^{n}(i')}$ was mapped to the same message as the source sequence ${\displaystyle X_{1}^{n}(i)}$ and that ${\displaystyle P(X_{$$1}^{n}(i')\geq P(X_{1}^{n}(i)}}$. 따라서 $X{\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle {{}^{}}_{}}$ ${\displaystyle {{\prime }^{}}_{}}$ $displaystyle X_{i,i'}\}\}$이(가) 두 원본 $시퀀스{\displaystyle }$ i$\,}$과${\displaystyle (}$와) $display$ {\$displaystyle$ i'\,}이$$(가$)$ 동일한 메시지에 매핑되는 이벤트를 나타내도록$$ 하면 다음과 같은 결과를 얻을 수 있다.

${\displaystyle P(A_{i'}}=P\left(X_{i,i'}\빅캡 P(X_{1}^{n}(i')\geq P(X_{1}^{n})(i)\,}$

$그리고{\displaystyle }$ P${\displaystyle ({Xi}_{}}$, ${\displaystyle {{}^{}}_{}}$ ${\displaystyle {{\prime }^{}}_{}}$)${\displaystyle }$= ${\displaystyle \frac{\mathrm{1M}}{}}$ $displaystyle P(X_{i,i'}}={\frac {1}{M}\},$ 다른 모든 것과 독립되어$$ 있다는 사실을 사용하여

${\displaystyle P(A_{i'}}={\frac {1}{1}{M}P(P(X_{1}^{n})(i')\geq P(X_{1}^{n})(i)\,}$

왼쪽의 용어에 대한 단순한 상한을 다음과 같이 설정할 수 있다.

${\displaystyle \left[P(X_{1}^{n})(i')\geq P(X_{1}^{n})(오른쪽)\leq \{\frac(X_{1}^{1}^{n')}{P(X_{1}^{n){n}}}}}{{n}i}i)}}}}^{s}\,}$

어떤 임의의 실수 s>0. 예를 들면{\displaystyle s>, 0\,.}이 상한은 P(P(X1n(나는 ′))을 점에 주목함으로써&P(X1n(나는))){\displaystyle P(P(X_{1}^{n}(나는 '))>P(X_{1}^{n}(나는)))\와 같이,}중 하나는 1{1\\displaystyle,}또는 0{0\\displaystyle,}기 때문에 proba 확인할 수 있다.의 bilities 주어진 입력 순서는 완전히 결정론적이다. Thus, if ${\displaystyle P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))\,,}$ then ${\displaystyle {\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))$$}}\geq 1\,}$이(가) 불평등이 그 경우에 버틸 수 있도록$$. 불평등은 다른 사례에서도 마찬가지인데, 그 이유는

${\displaystyle \left({\frac {P(X_{1}^{n}(i')}{P(X_{1}^{n})(i))}{P(X_{1}^{n})(i)}}}\오른쪽)^{s}\geq 0\,}$

모든 가능한 소스 문자열에 대해. 따라서 모든 것을 합쳐서${\displaystyle }some{\displaystyle }$ [ 0${\displaystyle ,}$ ${\displaystyle 1]}$ ${\$을$($를) 도입하면 다음과 같은 결과를 얻을 수 있다.

${\displaystyle P(E\mid S_{i})\leq P(\bigcup _{i\neq i'}A_{i'})\leq \left(\sum _{i\neq i'}P(A_{i'})\right)^{\rho }\leq \left({\frac {1}{M}}\sum _{i\neq i'}\left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}}}^{s}\오른쪽)^{\rho }\,}$

유니온 바운드에 대한 변화로부터 불평등이 뒤따르는 곳. $마지막$으로 P${\displaystyle (E}$) ${\$의 합계에 이 상한을 적용하면 다음과 같은 결과가$$ 나온다.

${\displaystyle P(E)=\sum _{i}P(E\mid S_{i}P(S_{i})\leq \sum _{i}P(X_{1}^{n})(i)\좌({\frac {1}{M}\sum _{i'}\좌({\frac {P(X_{1}^{n})(i')}{P(X_{1}^{n})(i)}}{P(X_{1}^{n})(i)}}}}^{s}\오른쪽)^{\rho }\,}$

이제 합계가 모든 $displaystyle$ i$'\}$을(를) 인수할 수 있는 곳, 왜냐하면 그렇게 되면 한계만 증가할 것이기 때문이다$$. 궁극적으로 그것을 양보한다.

${\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\sum _{i}P(X_{1}^{n}(i))^{1-s\rho }\left(\sum _{i'}P(X_{1}^{n}(i'))^{s}\right)^{\rho }\,.}$

Now for simplicity let ${\displaystyle 1-s\rho =s\,}$ so that ${\displaystyle s={\frac {1}{1+\rho }}\,.}$ Substituting this new value of ${\displaystyle s\,}$ into the above bound on the probability of error and using the fact that ${\displaystyle i'\,}$ is just a dummy variable in 합계는 오차 확률에 대한 상한을 다음과 같이 나타낸다.

${\displaystyle P(E)\leq {1}{M^{\rho }}}\왼쪽(\sum _{i}P(X_{1}^{n})(i)^{\frac {1}{1+\rho }}\오른쪽)^{1+\rho }\,}$

${\displaystyle M}$= ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle R^{}}$ $displaystyle M=e^{$${\displaystyle \mathrm{nR}}$$}\,\!}$ 및$$ $X{\displaystyle {}_{}^{}}$ 1 n ( ${\displaystyle {}_{}^{}}$ )${\$의 각 구성요소는 독립적이다$$. 따라서, 위의 방정식을 단순화하면 산출된다.

${\displaystyle P(E)\leq \ex \-n\left[\rho R-\ln \left(\sum _{x_}P(x_{i})^{1}{1+\rho }}\right){1\frac{1}(1+\rho )\right]\right]\right)}$

오류 확률에서 가장 높은 상한을 달성하려면$$ 지수 내 용어를 $\rho {\displaystyle }$ ${\$에 대해 최대화해야 한다.

Letting ${\displaystyle E_{0}(\rho )=\ln \left(\sum _{x_{i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\,,}$ see that the error exponent for the source coding case is:

${\displaystyle E_{r}(R)=\max _{\rho \in [0,1]}\왼쪽[\rho R-E_{0}(\rho )\right].\,}$

참고 항목

• 소스 부호화
• 채널 코딩

참조

R. 갤러거, 정보 이론 및 신뢰할 수 있는 커뮤니케이션, Wiley 1968