Показатель ошибки

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью , добавив ссылки на дополнительные источники . Найти источники:  «Показатель ошибки»  -  новости  · газеты  · книги  · ученый  · JSTOR ( август 2019 г. ) Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Август 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Для инвариантных во времени DMC [ править ]

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

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

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

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

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

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

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

${\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}$${\displaystyle x_{1}^{n},y_{1}^{n}}$

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

Выбор и объединение двух сумм в приведенной выше формуле:${\displaystyle s=1-s\rho }$${\displaystyle x_{1}^{n}}$

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

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

${\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 }\right),}$

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

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

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

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

Показатель ошибки в исходной кодировке [ править ]

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

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

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

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

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

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

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

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

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

Простая верхняя оценка члена слева может быть установлена ​​как

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

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

для всех возможных исходных строк. Таким образом, комбинируя все и вводя некоторые , получаем, что${\displaystyle \rho \in [0,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))}}\right)^{s}\right)^{\rho }\,.}$

Где неравенство вытекает из варианта ограничения Союза. Наконец, применив эту верхнюю границу к суммированию для :${\displaystyle P(E)\,}$

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

Где сумма теперь может быть взята за все, потому что это только увеличит границу. В конечном итоге давая это${\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 }\,.}$

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Р. Галлагер, Теория информации и надежная коммуникация , Wiley, 1968 г.