Rate at which the error probability decays exponentially with increasing block length in code
В теории информации канального показатель ошибки кода или исходного кода по длине блока кода — это скорость, с которой вероятность ошибки экспоненциально убывает с длиной блока кода. Формально он определяется как предельное отношение отрицательного логарифма вероятности ошибки к длине блока кода для больших длин блоков. Например, если вероятность ошибки
декодера падает как
, где
длина блока, показатель ошибки равен
. В этом примере
подходы
для больших
. Многие теоремы теории информации носят асимптотический характер, например, теорема о канальном кодировании утверждает, что для любой скорости , меньшей, чем пропускная способность канала, вероятность ошибки канального кода может быть обращена к нулю по мере увеличения длины блока. уходит в бесконечность. В практических ситуациях существуют ограничения на задержку связи, и длина блока должна быть конечной. Поэтому важно изучить, как падает вероятность ошибки при стремлении длины блока к бесконечности.
Показатель ошибки при кодировании канала [ править ]
Для не зависящих от времени DMC [ править ]
Теорема канального кодирования утверждает, что для любого ε > 0 и для любой скорости , меньшей пропускной способности канала, существует схема кодирования и декодирования, которая может использоваться для обеспечения того, чтобы вероятность ошибки блока была меньше ε > 0 для достаточно длинного сообщения. блок Х. Кроме того, для любой скорости , превышающей пропускную способность канала, вероятность ошибки блока в приемнике стремится к единице, поскольку длина блока стремится к бесконечности.
Предположим, что канальное кодирование настроено следующим образом: канал может передавать любое из
сообщения, передавая соответствующее кодовое слово (длиной n ). Каждый компонент в кодовой книге рисуется iid в соответствии с некоторым распределением вероятностей с функцией массы Q. вероятности В конце декодирования выполняется декодирование максимального правдоподобия.
Позволять
быть
случайное кодовое слово в кодовой книге, где
идет от
к
. Предположим, выбрано первое сообщение, поэтому кодовое слово
передается. При условии
получено, вероятность того, что кодовое слово будет неправильно обнаружено как
является:
![{\ displaystyle 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})).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7efe3bfdf5ede5138cec7641a16090b8af73183e)
Функция
имеет верхнюю границу
![{\displaystyle \left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^ {n})}}\right)^{s}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08f9a7720b4eaffb4389c8f73d0c5529cfaa3b95)
для
Таким образом,
![{\ 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)^{ с}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/73a86c04e64db2a89fcb381c8f56712215df869d)
Поскольку всего имеется M сообщений, а записи в кодовой книге имеют идентификатор iid, вероятность того, что
путается с любым другим сообщением
раз больше приведенного выше выражения. Используя оценку объединения, вероятность спутать
с любым сообщением ограничено:
![{\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 }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/974bcebbb0c0037452bcd061889b6a902e4d3142)
для любого
. Усреднение по всем комбинациям
:
![{\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 }.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c80e6f8a936e63538f616d5203ef62494cb5c2f)
Выбор
и объединив две суммы по
в приведенной выше формуле:
![{\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 }.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47e585bc57bb56d410e23c12a6d2b04f75dc1415)
Использование независимого характера элементов кодового слова и дискретного характера канала без памяти:
![{\displaystyle 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+\ ро }}\right)^{1+\rho }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9d6a1c7968f08d5731ea2f63747a9ffdb07ac9e)
Используя тот факт, что каждый элемент кодового слова одинаково распределен и, следовательно, стационарен:
![{\ 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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b1c86e37afc9dc15e6007ba4c6257c2de860a66)
Замена М на 2 н и определение
![{\displaystyle E_{o}(\rho,Q)=-\ln \left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{ 1/(1+\rho )}\right)^{1+\rho }\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bd7c00e52e92af68e0f30d3ef6ea1e8363ddd3b)
вероятность ошибки становится
![{\displaystyle P_{\mathrm {error} }\leq \exp(-n(E_{o}(\rho,Q)-\rho R)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7624117f956c3d5ed2d3d0e635681c62b2d2646a)
Вопрос и
следует выбирать так, чтобы граница была максимально жесткой. Таким образом, показатель ошибки можно определить как
![{\displaystyle E_{r}(R)=\max _{Q}\max _{\rho \in [0,1]}E_{o}(\rho,Q)-\rho R.\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/748bec95dc126d3630cce2d744c88f1df2f64fe7)
Экспонента ошибки в исходном коде [ править ]
Для инвариантных во времени дискретных источников без памяти [ править ]
Теорема исходного кодирования утверждает, что для любого
и любой источник iid дискретного времени, такой как
и для любой скорости, меньшей энтропии источника, существует достаточно большое
и кодер, который принимает
iid повторение источника,
и сопоставляет его с
двоичные биты такие, что исходные символы
восстанавливаются из двоичных битов с вероятностью не менее
.
Позволять
быть общим количеством возможных сообщений. Затем сопоставьте каждую из возможных выходных последовательностей источника с одним из сообщений случайным образом, используя равномерное распределение и независимо от всего остального. При появлении источника генерируется соответствующее сообщение
затем передается по назначению. Сообщение декодируется в одну из возможных исходных строк. Чтобы минимизировать вероятность ошибки, декодер будет декодировать исходную последовательность.
это максимизирует
, где
обозначает событие, о котором сообщается
было передано. Это правило эквивалентно поиску исходной последовательности
среди набора исходных последовательностей, которые соответствуют сообщению
это максимизирует
. Такое сокращение следует из того, что сообщения распределялись случайным образом и независимо от всего остального.
Таким образом, в качестве примера возникновения ошибки предположим, что исходная последовательность
было сопоставлено с сообщением
как и исходная последовательность
. Если
был сгенерирован в источнике, но
тогда возникает ошибка.
Позволять
обозначают событие, когда исходная последовательность
был сгенерирован в источнике, так что
Тогда вероятность ошибки можно представить как
Таким образом, внимание можно сосредоточить на нахождении верхней границы
.
Позволять
обозначают событие, когда исходная последовательность
было сопоставлено с тем же сообщением, что и исходная последовательность
и это
. Таким образом, позволив
обозначают событие, когда две исходные последовательности
и
сопоставление с тем же сообщением, у нас есть это
![{\displaystyle P(A_{i'})=P\left(X_{i,i'}\bigcap P(X_{1}^{n}(i')\right)\geq P(X_{1} ^{n}(i)))\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cb2e0011339bcdc29f58431fdb7bb3d6625281f)
и используя тот факт, что
и независим от всего остального
![{\displaystyle P(A_{i'})={\frac {1}{M}}P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n }(я)))\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b76352e35c415de3cc0a119663c7e8e9f5313997)
Простую верхнюю оценку члена слева можно установить как
![{\displaystyle \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}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42d81f364b8577381d1d0c2720eb23b64e1f44b2)
для некоторого произвольного действительного числа
Эту верхнюю оценку можно проверить, заметив, что
либо равно
или
потому что вероятности данной входной последовательности полностью детерминированы. Таким образом, если
затем
так что неравенство в этом случае выполнено. Неравенство справедливо и в другом случае, поскольку
![{\displaystyle \left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s} \geq 0\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c612881f177f7b39f388295832d72e0b84eafdf3)
для всех возможных исходных строк. Таким образом, объединив все и введя некоторые
, возьми это
![{\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))}}\right)^{s}\right)^{\rho }\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93298ff421346c07d890c00b320b40fd43b223b0)
Где неравенства следуют из вариации Union Bound. Наконец, применив эту верхнюю оценку к суммированию для
есть это:
![{\displaystyle 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 }\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a69937e87108e9dc40c4314725883b622ea352a5)
Где теперь можно взять сумму за все
потому что это только увеличит границу. В конечном итоге это дает
![{\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\sum _{i}P(X_{1}^{n}(i))^{1-s\ ро }\left(\sum _{i'}P(X_{1}^{n}(i'))^{s}\right)^{\rho }\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffad5289477453d99e50624c4fea0da7f8173d21)
Теперь для простоты позвольте
так что
Подставив это новое значение
в приведенную выше оценку вероятности ошибки и используя тот факт, что
— это всего лишь фиктивная переменная в сумме, что дает в качестве верхней границы вероятности ошибки следующее:
![{\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\left(\sum _{i}P(X_{1}^{n}(i))^{\ frac {1}{1+\rho }}\right)^{1+\rho }\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b53460dc73fa9a5fc282ed440b1715f027c42e04)
и каждый из компонентов
независимы. Таким образом, упрощение приведенного выше уравнения дает
![{\displaystyle 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92fb3aa7f9ec867c0ae54cb611b5b54671029ff4)
Член в показателе степени должен быть максимизирован за
для достижения наивысшей верхней границы вероятности ошибки.
Сдача в аренду
увидите, что показатель ошибки для случая исходного кодирования:
![{\displaystyle E_{r}(R)=\max _{\rho \in [0,1]} \left[\rho R-E_{0}(\rho)\right].\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fec9cb0211c0e4bd31cb9c32342dc8dcec163caf)
Р. Галлагер, Теория информации и надежная связь , Wiley, 1968 г.