Они объяснят ошибку

В теории информации показатель ошибки или канального кода исходного кода по длине блока кода — это скорость, с которой вероятность ошибки экспоненциально убывает с длиной блока кода. Формально он определяется как предельное отношение отрицательного логарифма вероятности ошибки к длине блока кода для больших длин блоков. Например, если вероятность ошибки $P_{\mathrm {error} }$ декодера падает как $e^{-n\alpha }$, где $n$ длина блока, показатель ошибки равен $\alpha$. В этом примере ${\frac {-\ln P_{\mathrm {error} }}{n}}$ подходы $\alpha$ для больших $n$. Многие теоремы теории информации носят асимптотический характер, например, теорема о канальном кодировании утверждает, что для любой скорости, меньшей, чем пропускная способность канала, вероятность ошибки канального кода может быть обращена к нулю по мере увеличения длины блока. уходит в бесконечность. В практических ситуациях существуют ограничения на задержку связи, и длина блока должна быть конечной. Поэтому важно изучить, как падает вероятность ошибки при стремлении длины блока к бесконечности.

Показатель ошибки при кодировании канала

Для не зависящих от времени DMC

Теорема канального кодирования утверждает, что для любого ε > 0 и для любой скорости, меньшей пропускной способности канала, существует схема кодирования и декодирования, которую можно использовать, чтобы гарантировать, что вероятность ошибки блока будет меньше ε > 0 для достаточно длинного сообщения. блок Х. ​Кроме того, для любой скорости, превышающей пропускную способность канала, вероятность ошибки блока в приемнике стремится к единице, поскольку длина блока стремится к бесконечности.

Предположим, что канальное кодирование настроено следующим образом: канал может передавать любое из $M=2^{nR}\;$ сообщения, передавая соответствующее кодовое слово (длиной n ). Каждый компонент в кодовой книге рисуется iid в соответствии с некоторым распределением вероятностей с массы вероятности Q. функцией В конце декодирования выполняется декодирование максимального правдоподобия.

Позволять $X_{i}^{n}$ быть $i$случайное кодовое слово в кодовой книге, где $i$ идет от $1$ к $M$. Предположим, выбрано первое сообщение, поэтому кодовое слово $X_{1}^{n}$ передается. При условии $y_{1}^{n}$ получено, вероятность того, что кодовое слово будет неправильно обнаружено как $X_{2}^{n}$ является:

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

Функция $1(p(y_{1}^{n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n}))$ имеет верхнюю границу

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

для $s>0\;$ Таким образом,

$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 сообщений, а записи в кодовой книге имеют идентификатор iid, вероятность того, что $X_{1}^{n}$ путается с любым другим сообщением $M$ раз больше приведенного выше выражения. Используя оценку объединения, вероятность спутать $X_{1}^{n}$ с любым сообщением ограничено:

$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 }$

для любого $0<\rho <1$. Усреднение по всем комбинациям $x_{1}^{n},y_{1}^{n}$:

$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=1-s\rho$ и объединив две суммы по $x_{1}^{n}$ в приведенной выше формуле:

$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 }.$

Использование независимого характера элементов кодового слова и дискретного характера канала без памяти:

$P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\prod _{i=1}^{n}\sum _{y_{i}}\left(\sum _{x_{i}}Q_{i}(x_{i})[p_{i}(y_{i}\mid x_{i})]^{\frac {1}{1+\rho }}\right)^{1+\rho }$

Используя тот факт, что каждый элемент кодового слова одинаково распределен и, следовательно, стационарен:

$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}.$

Замена М на 2 ^н и определение

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

вероятность ошибки становится

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

Вопрос и $\rho$ следует выбирать так, чтобы граница была максимально жесткой. Таким образом, показатель ошибки можно определить как

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

Экспонента ошибки в исходном коде

Для инвариантных во времени дискретных источников без памяти

Теорема исходного кодирования утверждает, что для любого $\varepsilon >0$ и любой источник идентификаторов дискретного времени, например $X$ и для любой скорости , меньшей энтропии источника, существует достаточно большое $n$ и кодер, который принимает $n$ iid повторение источника, $X^{1:n}$и сопоставляет его с $n.(H(X)+\varepsilon )$ двоичные биты такие, что исходные символы $X^{1:n}$ восстанавливаются из двоичных битов с вероятностью не менее $1-\varepsilon$.

Позволять $M=e^{nR}\,\!$ быть общим количеством возможных сообщений. Затем сопоставьте каждую из возможных выходных последовательностей источника с одним из сообщений случайным образом, используя равномерное распределение и независимо от всего остального. При появлении источника генерируется соответствующее сообщение $M=m\,$ затем передается по назначению. Сообщение декодируется в одну из возможных исходных строк. Чтобы минимизировать вероятность ошибки, декодер будет декодировать исходную последовательность. $X_{1}^{n}$ это максимизирует $P(X_{1}^{n}\mid A_{m})$, где $A_{m}\,$ обозначает событие, о котором сообщается $m$ было передано. Это правило эквивалентно поиску исходной последовательности $X_{1}^{n}$ среди набора исходных последовательностей, которые соответствуют сообщению $m$ это максимизирует $P(X_{1}^{n})$. Такое сокращение следует из того, что сообщения распределялись случайным образом и независимо от всего остального.

Таким образом, в качестве примера возникновения ошибки предположим, что исходная последовательность $X_{1}^{n}(1)$ было сопоставлено с сообщением $1$ как и исходная последовательность $X_{1}^{n}(2)$. Если $X_{1}^{n}(1)\,$ был сгенерирован в источнике, но $P(X_{1}^{n}(2))>P(X_{1}^{n}(1))$ тогда возникает ошибка.

Позволять $S_{i}\,$ обозначают событие, когда исходная последовательность $X_{1}^{n}(i)$ был сгенерирован в источнике, так что $P(S_{i})=P(X_{1}^{n}(i))\,.$ Тогда вероятность ошибки можно представить как $P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\,.$ Таким образом, внимание можно сосредоточить на нахождении верхней границы $P(E\mid S_{i})\,$.

Позволять $A_{i'}\,$ обозначают событие, когда исходная последовательность $X_{1}^{n}(i')$ было сопоставлено с тем же сообщением, что и исходная последовательность $X_{1}^{n}(i)$ и это $P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))$. Таким образом, позволив $X_{i,i'}\,$ обозначают событие, когда две исходные последовательности $i\,$ и $i'\,$ сопоставление с тем же сообщением, у нас есть это

$P(A_{i'})=P\left(X_{i,i'}\bigcap P(X_{1}^{n}(i')\right)\geq P(X_{1}^{n}(i)))\,$

и используя тот факт, что $P(X_{i,i'})={\frac {1}{M}}\,$ и независим от всего остального

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

Простую верхнюю оценку члена слева можно установить как

$\left[P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i)))\right]\leq \left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\,$

для некоторого произвольного действительного числа $s>0\,.$ Эту верхнюю оценку можно проверить, заметив, что $P(P(X_{1}^{n}(i'))>P(X_{1}^{n}(i)))\,$ либо равно $1\,$ или $0\,$ потому что вероятности данной входной последовательности полностью детерминированы. Таким образом, если $P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))\,,$ затем ${\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\geq 1\,$ так что неравенство в этом случае выполнено. Неравенство справедливо и в другом случае, поскольку

$\left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\geq 0\,$

для всех возможных исходных строк. Таким образом, объединив все и введя некоторые $\rho \in [0,1]\,$, возьми это

$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))}}\right)^{s}\right)^{\rho }\,.$

Где неравенства следуют из вариации Union Bound. Наконец, применив эту верхнюю оценку к суммированию для $P(E)\,$ есть это:

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

Где теперь можно взять сумму за все $i'\,$ потому что это только увеличит границу. В конечном итоге это дает

$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 }\,.$

Теперь для простоты позвольте $1-s\rho =s\,$ так что $s={\frac {1}{1+\rho }}\,.$ Подставив это новое значение $s\,$ в приведенную выше оценку вероятности ошибки и используя тот факт, что $i'\,$ — это всего лишь фиктивная переменная в сумме, что дает в качестве верхней границы вероятности ошибки следующее:

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

$M=e^{nR}\,\!$ и каждый из компонентов $X_{1}^{n}(i)\,$ независимы. Таким образом, упрощение приведенного выше уравнения дает

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

Член в показателе степени должен быть максимизирован за $\rho \,$ для достижения наивысшей верхней границы вероятности ошибки.

Сдача в аренду $E_{0}(\rho )=\ln \left(\sum _{x_{i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\,,$ увидите, что показатель ошибки для случая исходного кодирования:

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

См. также

• Исходное кодирование
• Кодирование канала

Ссылки

Р. Галлагер, Теория информации и надежная связь , Wiley, 1968 г.