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

Макеты страниц

Теперь рассмотрим ансамбль случайных СКК, у которых ансамбль внутреннего кода X фиксирован, а символы каждого внешнего кода выбираются независимо с вероятностной мерой Одновременно рассмотрим ансамбль случайных СКК с линейными внешними кодами. Очевидно, что ансамбли CKKI и СККII в этих случаях совпадают.

Пусть последовательность слов передается каналу с гауссовским шумом (например, -мерному) с отношением сигнал-шум — принятое слово, искаженное шумами.

Будем исследовать алгоритмы как с мягким, так и жестким декодированием внешними кодами.

Проанализируем алгоритм СКК с независимым декодированием внешними кодами (см. разд. 5.1). Пусть соответственно вектор разбиения и скорость скорость внешнего кода; матрица переходных вероятностей эквивалентного дискретного (или плотностей вероятности в случае полунепрерывного) канала для внешнего кода при условии, что все коды до включительно декодированы правильно; пропускная способность соответствующего канала. Пусть также — экспонента вероятности ошибочного декодирования и функция, ей обратная.

Легко заметить, что при использовании алгоритма Чнмп вероятность ошибки ограничена сверху выражением где вероятность ошибочного декодирования внешнего кода при условии, что все внешние коды до включительно декодированы правильно. Положим Зафиксируем скорость передачи последнего внешнего кода определим и подсчитаем остальные Следовательно, можно определить и скорость Для каждого допустимого т. е. определенного при любом в качестве скорости будет выбираться ее максимальное значение среди всех возможных разбиений (при фиксированном ансамбле сигналов X). Тогда из алгоритма и приведенных рассуждений непосредственно вытекает [91] следующее утверждение.

Утверждение 6.4. При декодировании с помощью алгоритма принятой из канала связи СКК вероятность ошибки ограничена сверху выражением

применять к каждому независимую экспоненту вероятности ошибки. Однако попытаемся действовать по аналогии с алгоритмом

Рассмотрим сначала экспоненту случайного кодирования. Вероятность ошибки при условии передачи вектора со словами выражается по формуле

где вероятностная мера слов внешнего кода; условная вероятность получения вектора у с выхода канала при передаваемых векторах вероятность ошибки. При мягком декодировании сумма по у заменяется интегралом, а условная вероятность получения вектора у — плотностью вероятности. Здесь для простоты вместо векторов и при жестком декодировании употребляем обозначение у.

Переходим к следующей гртппе событий Событие состоит в том, что произошла ошибка декодирования в векторе причем векторы безошибочны, а векторы произвольны. Тогда, как легко убедиться,

Подставив (6.17) в (6.16) и проведя преобразования, получим

где

Теперь в соответствии с методом получения экспоненты случайного кодирования [24] получим

где — число слов в внешнем коде

Подставив (6.20) в (6.19) и проведя необходимые преобразования по аналогии с [24], получим

Используя тот факт, что передача осуществляется по каналу без памяти, получаем

где — общее число зон квантования на шаге декодирования (определяется как пересечение зон на всех предыдущих шагах); номер зоны квантования; номера символов соответствующих вложенных кодов.

Переходные вероятности в (6.22) можно получить по формулам, аналогичным (6.14):

где означает вероятность попадания сигнала подкода в -зону квантования.

Положим теперь, что избыточности внешних кодов СКК выбраны таким образом, что выполняется тождество Тогда вероятность ошибки декодирования

или же

где показатель случайного кодирования

матрица размера скорость внешнего кода.

Взяв производную (6.26) по 0 при можно определить максимальную скорость внешнего кода [1]:

Следует отметить, что, во-первых, где определяется по (6.15), а во-вторых, сумма всех дает максимальную скорость СКК при декодировании по максимуму правдоподобия. Величину для мягкого декодирования внешними кодами можно получить из (6.27), заменив суммирование по -мерным интегралом и вероятности соответствующими плотностями вероятностей.

По аналогии с [24] можно получить выражение экспоненты для ансамбля СКК с выбрасыванием.

Утверждение 6.5. При декодировании по алгоритму принятой из канала связи СКК вероятность ошибки ограничена сверху выражением

Рентах

где функция, связывающая при заданном величины следующим образом:

Кроме того,

показатель экспоненты случайного кодирования и экспоненты с выбрасыванием матрица размерности с элементами столбце и строке; определяется по (6.27).

Как и в утверждении 6.4, для асимптотики коэффициент в (6.29) несуществен, поэтому (6 29) является экспонентной вероятности ошибки СКК при декодировании по алгоритму максимума правдоподобия Все выводы о максимизации экспонент по при независимом декодировании распространяются в этом случае для

Асимптотическая сложность алгоритмов декодирования СКК по максимуму правдоподобия определена формулами Тогда справедливо следующее утверждение.

Утверждение 6.6. Сложность декодирования СКК с ансамблем сигналов X, раскладываемым на цепочку вложенных ансамблей

вектором разбиений внешними кодами при реализации экспоненты ошибки в соответствии с утверждениями 6.4 и 6.5 оценивается неравенством

где показатель экспоненты сложности декодирования. В случае независимого декодирования внешними кодами

а при декодировании по максимуму правдоподобия

Рассмотрим для примера двухмерные сигналы ФМ и КАМ. На рис. 6.3 и 6.4 показано разбиение на зоны сигналов при жестком декодировании внешними кодами. Штриховой линией показано разбиение вложенных ансамблей сигналов.

Для расчета показателей экспонент вероятности ошибки необходимо уметь определять вероятности или плотности вероятностей (см. (6.14) и Для этого надо уметь подсчитывать вероятности попадания сигнала в заданную область двухмерного пространства или плотность вероятности в заданной точке пространства. Величину в дискретном канале можно вычислить при помощи методики, изложенной в [4]. В случае симметричного канала (ФМ) достаточно определить как функцию от отношения сигнал-шум [91]. Тогда где

Рис. 6.3 Разбиение на зоны сигналов при жестком декодировании

(кликните для просмотра скана)

Для несимметричного канала необходим полный перебор. Величина определяется аналогично.

Пусть — проекции двухмерного сигнала проекции принятого двухмерного сигнала. Как для , так и для при мягком решении необходимо оценить условную плотность вероятности попадания на шаге сигнала с номером из подкода в точку пространства

Подставив (6 35) в (6.14) и (6 23), можно оценить соответствующие показатели экспоненты вероятности ошибки декодирования СКК.

На рис. 6.5 и 6.6 показаны зависимости максимально достижимых скоростей передачи от отношения сигнал-шум при ФМ и КАМ соответственно. Кривые на рисунке соответствуют: 1 — пропускной

Рис. 6.6 Максимально достижимые скорости передачи при КАМ

способности ГКБП; 2 — жесткому алгоритму ; 3 — жесткому алгоритму мягкому алгоритму ; 5 — мягкому алгоритму . Буква а обозначает вектор разбиений

Как и следовало ожидать, начиная с дает существенные преимущества по сравнению с ФМ, которые увеличиваются с ростом числа сигналов в ансамбле. Преимущества мягкого декодирования внешними кодами при умеренных исчезают при возрастании отношения сигнал-шум. И при жестком, и при мягком декодировании внешними кодами алгоритм обеспечивает существенные преимущества по сравнению с Тнип. Однако при

Рис. 6.7 Зависимость показателя экспоненты ошибочного декодирования СКК от скорости передачи при ФМ

Рис. 6.8 Зависимость показателя экспоненты ошибочного декодирования СКК от скорости передачи при КАМ

Оглавление

ПРЕДИСЛОВИЕ
Часть I. Передача дискретных сообщений в каналах без межсимвольной интерференции
Глава 1. МОДЕЛИ КАНАЛОВ БЕЗ МЕЖСИМВОЛЬНОЙ ИНТЕРФЕРЕНЦИИ
Глава 2. ВИДЫ СИГНАЛОВ ДЛЯ ПЕРЕДАЧИ ПО КАНАЛУ БЕЗ МЕЖСИМВОЛЬНОЙ ИНТЕРФЕРЕНЦИИ
2.2. СИГНАЛЫ РАЗМЕРНОСТИ ОДИН И ДВА
2.3. СИГНАЛЫ РАЗМЕРНОСТИ БОЛЬШЕ ДВУХ
2.4. ПОСТРОЕНИЕ ВЛОЖЕННЫХ АНСАМБЛЕЙ СИГНАЛОВ
2.5. ПОМЕХОУСТОЙЧИВОСТЬ АНСАМБЛЕЙ СИГНАЛОВ
Глава 3. ВИДЫ КОРРЕКТИРУЮЩИХ КОДОВ
3.2 ЛИНЕЙНЫЕ БЛОЧНЫЕ КОДЫ
3.3. АЛГОРИТМЫ ДЕКОДИРОВАНИЯ БЛОЧНЫХ КОДОВ
3.4. КАСКАДНЫЕ КОДЫ
3.5. ПОТЕНЦИАЛЬНЫЕ СВОЙСТВА КОРРЕКТИРУЮЩИХ КОДОВ
3.6. ОЦЕНКИ ПОМЕХОУСТОЙЧИВОСТИ
Глава 4. СИНТЕЗ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ
4.2. ФОРМАЛЬНОЕ ОПИСАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ
4.3. ПОСТРОЕНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ
Глава 5. ДЕКОДИРОВАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ
5.2. ДЕКОДИРОВАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ПО МАКСИМУМУ ПРАВДОПОДОБИЯ
5.3. ДЕКОДИРОВАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ПО ЕВКЛИДОВУ РАССТОЯНИЮ
5.4 ВЕРОЯТНОСТНОЕ МАЖОРИТАРНОЕ ДЕКОДИРОВАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ
Глава 6. АСИМПТОТИЧЕСКИЕ ХАРАКТЕРИСТИКИ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИИ
6.1. АСИМПТОТИЧЕСКИЕ ЗАВИСИМОСТИ СКОРОСТИ ПЕРЕДАЧИ ОТ КВАДРАТА ЕВКЛИДОВА РАССТОЯНИЯ
6.2. ЭКСПОНЕНТА ВЕРОЯТНОСТИ ОШИБКИ РАЗЛИЧНЫХ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ
Глава 7. ОЦЕНКИ ПОМЕХОУСТОЙЧИВОСТИ И ПЕРСПЕКТИВЫ РЕАЛИЗАЦИИ КОНКРЕТНЫХ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ
7.1. СИГНАЛЬНО-КОДОВЫЕ КОНСТРУКЦИИ С ДЕКОДИРОВАНИЕМ ПО МАКСИМУМУ ПРАВДОПОДОБИЯ
7.2. СИГНАЛЬНО-КОДОВЫЕ КОНСТРУКЦИИ С ДЕКОДИРОВАНИЕМ ПО ЕВКЛИДОВУ РАССТОЯНИЮ
7.3. СИГНАЛЬНО-КОДОВЫЕ КОНСТРУКЦИИ С МАЖОРИТАРНЫМ ДЕКОДИРОВАНИЕМ
7.4. ПЕРСПЕКТИВЫ РЕАЛИЗАЦИИ
Часть II. Передача дискретных сообщений в каналах с межсимвольной интерференцией и и постоянными параметрами
Глава 8. МОДЕЛЬ КАНАЛА С МЕЖСИМВОЛЬНОЙ ИНТЕРФЕРЕНЦИЕЙ
8.1. МОДЕЛЬ КАНАЛА НЕПРЕРЫВНОГО ВРЕМЕНИ
8.2. МОДЕЛЬ КАНАЛА ДИСКРЕТНОГО ВРЕМЕНИ
8.3 ГАУССОВСКИЙ КАНАЛ С МСИ
Глава 9. ПРИЕМ СИГНАЛОВ В КАНАЛАХ С МЕЖСИМВОЛЬНОЙ ИНТЕРФЕРЕНЦИЕЙ
9.2. ОПТИМАЛЬНЫЙ ПРИЕМ СИГНАЛОВ В КАНАЛАХ С МСИ
9.3. ЛИНЕЙНЫЙ МАТРИЧНЫЙ ПРИЕМНИК
Глава 10. ОПТИМИЗАЦИЯ СИГНАЛОВ ДЛЯ КАНАЛОВ С МСИ
10.2. ПРЕОБРАЗОВАНИЕ ГАУССОВСКОГО КАНАЛА С МСИ В СОВОКУПНОСТЬ НЕЗАВИСИМЫХ ГАУССОВСКИХ КАНАЛОВ БЕЗ ПАМЯТИ
10.3. ОБЩАЯ СТРУКТУРА СИГНАЛОВ ДЛЯ КАНАЛОВ С МСИ И ИХ ОПТИМАЛЬНЫЙ ПРИЕМ
10.4. СИГНАЛЫ ДЛЯ КАНАЛА С МСИ, ОСНОВАННЫЕ НА ИСПОЛЬЗОВАНИИ ПРЕДЫСКАЖЕНИЙ И ОДНОГО АЛФАВИТА КАМ
10.5. СИГНАЛЫ ДЛЯ КАНАЛА С МСИ, ОСНОВАННЫЕ НА ИСПОЛЬЗОВАНИИ ПРЕДЫСКАЖЕНИЙ И ПРОИЗВОЛЬНОГО ЧИСЛА АЛФАВИТОВ КАМ
10.6. РЕАЛИЗАЦИЯ СИГНАЛОВ ДЛЯ КАНАЛОВ С МСИ ПОСРЕДСТВОМ ЭФФЕКТИВНЫХ МЕТОДОВ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ
Глава 11. ПОТЕНЦИАЛЬНЫЕ ХАРАКТЕРИСТИКИ КАНАЛОВ С МСИ
11.1. ПРОБЛЕМА ПОВЫШЕНИЯ СКОРОСТИ В КАНАЛАХ С МСИ
11.2. АНАЛИЗ ПОТЕНЦИАЛЬНЫХ ХАРАКТЕРИСТИК КАНАЛА С МСИ
Глава 12. СИГНАЛЬНО-КОДОВЫЕ КОНСТРУКЦИИ ДЛЯ ГАУССОВСКИХ КАНАЛОВ С МСИ
12.1. СИНТЕЗ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ДЛЯ ГАУССОВСКИХ КАНАЛОВ С МСИ
12.2. АНАЛИЗ АСИМПТОТИЧЕСКИХ ХАРАКТЕРИСТИК СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ДЛЯ КАНАЛОВ С МСИ
12.3. АНАЛИЗ РЕАЛЬНЫХ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ДЛЯ КАНАЛОВ С МСИ
Часть III. Передача сообщений в каналах с переменными параметрами и множественным доступом
13.1. ПРОБЛЕМА ИДЕНТИФИКАЦИИ КАНАЛА. ТРЕБУЕМАЯ ТОЧНОСТЬ ОЦЕНИВАНИЯ ПАРАМЕТРОВ КАНАЛА
13.2. ОЦЕНИВАНИЕ ПАРАМЕТРОВ ЗАРАНЕЕ НЕИЗВЕСТНОГО, НО НЕИЗМЕННОГО ВО ВРЕМЕНИ КАНАЛА
13.3. МОДЕЛЬ КАНАЛА С МСИ И ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ
13.4. МЕТОДЫ ИДЕНТИФИКАЦИИ КАНАЛА С МСИ И ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ. АДАПТАЦИЯ ПРИЕМНИКА
13.5. СИГНАЛЫ И СИГНАЛЬНО-КОДОВЫЕ КОНСТРУКЦИИ ДЛЯ КАНАЛА С МСИ И ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ
Глава 14. СИНТЕЗ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ДЛЯ КАНАЛОВ С ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ И МНОЖЕСТВЕННЫМ ДОСТУПОМ
14.1. ПРОБЛЕМА ОРГАНИЗАЦИИ МНОЖЕСТВЕННОГО ДОСТУПА В КАНАЛЕ С ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ
14.2. МОДЕЛЬ СИСТЕМЫ С МНОЖЕСТВЕННЫМ ДОСТУПОМ И ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ
14.3. ПРЕДЕЛЬНЫЕ ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ СИСТЕМ С МНОЖЕСТВЕННЫМ ДОСТУПОМ И ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ
14.4. ПОМЕХОУСТОЙЧИВОСТЬ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ДЛЯ СИСТЕМ С МЕДЛЕННЫМИ РЭЛЕЕВСКИМИ ЗАМИРАНИЯМИ
14.5. СИНТЕЗ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ДЛЯ СИСТЕМ С КОДОВЫМ РАЗДЕЛЕНИЕМ И МНОГОФАЗНОЙ МОДУЛЯЦИЕЙ
14.6. СИНТЕЗ СИГНАЛЬНО-КОДОВЫХ конструкции ДЛЯ СИСТЕМ С КОДОВЫМ РАЗДЕЛЕНИЕМ И МНОГОЧАСТОТНОЙ МОДУЛЯЦИЕЙ
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Источник

В статистическая проверка гипотез, показатель ошибки процедуры проверки гипотез — это скорость, с которой вероятности Типа I и Типа II экспоненциально убывают с размером выборки, используемой в тесте. Например, если вероятность ошибки P error { displaystyle P _ { mathrm {error}}} ${ displaystyle P _ { mathrm {error}}}$ теста уменьшается как e — n β { displaystyle e ^ {- n beta}} ${ displaystyle е ^ {- п бета}}$ , где n { displaystyle n}— размер выборки, показатель степени ошибки — β { displaystyle beta} beta .

Формально показатель ошибки теста определяется как предельное значение отношения отрицательного логарифма вероятности ошибки к размеру выборки для больших размеров выборки: lim n → ∞ — ln ⁡ P error n { displaystyle lim _ {n to infty} { frac {- ln P _ { text {error}}} {n}}} ${ displaystyle lim _ {n to infty} { frac {- ln P_ { text {error}}} {n}}}$ . Показатели ошибки для различных проверок гипотез вычисляются с использованием теоремы Санова и других результатов теории больших отклонений.

Содержание

1 Показатели ошибки при проверке двоичных гипотез
- 1.1 Оптимальная экспонента ошибки для Неймана –Тестирование Пирсона
- 1.2 Оптимальная экспонента ошибки для средней вероятности ошибки при проверке байесовской гипотезы
2 Ссылки

Показатели ошибки при проверке двоичной гипотезы

Рассмотрим задачу проверки двоичной гипотезы, в которой наблюдения моделируются как независимые и одинаково распределенные случайные величины по каждой гипотезе. Пусть Y 1, Y 2,…, Y n { displaystyle Y_ {1}, Y_ {2}, ldots, Y_ {n}} ${ displaystyle Y_ {1}, Y_ {2}, ldots, Y_ {n}}$ обозначают наблюдения. Пусть f 0 { displaystyle f_ {0}} $f_ {0}$ обозначает функцию плотности вероятности каждого наблюдения Y i { displaystyle Y_ {i}} $Y_ {i}$ при нулевой гипотезе H 0 { displaystyle H_ {0}} $H_ {0}$ и пусть f 1 { displaystyle f_ {1}} ${ displaystyle f_ {1}}$ обозначает вероятность функция плотности каждого наблюдения Y i { displaystyle Y_ {i}} $Y_ {i}$ при альтернативной гипотезе H 1 { displaystyle H_ {1}} $H_ {1}$ .

В этом случае есть два возможных события ошибки. Ошибка типа 1, также называемая ложное срабатывание, возникает, когда нулевая гипотеза верна и ошибочно отклоняется. Ошибка типа 2, также называемая ложноотрицательной, возникает, когда альтернативная гипотеза верна, а нулевая гипотеза не отклоняется. Вероятность ошибки типа 1 обозначается P (ошибка ∣ H 0) { displaystyle P ( mathrm {error} mid H_ {0})} ${ displaystyle P ( mathrm {error} mid H_ {0})}$ , а вероятность ошибки типа 2 равна обозначается P (ошибка ∣ H 1) { displaystyle P ( mathrm {error} mid H_ {1})} ${ displaystyle P ( mathrm {error} mid H_ {1})}$ .

Оптимальный показатель степени ошибки для тестирования Неймана – Пирсона

В шкале Неймана– Версия Пирсона для проверки бинарных гипотез, интересует минимизация вероятности ошибки типа 2 P (error ∣ H 1) { displaystyle P ({ text {error}} mid H_ {1})} ${ displaystyle P ({ text {error}} mid H_ {1})}$ при условии, что вероятность ошибки типа 1 P (error ∣ H 0) { displaystyle P ({ text {error}} mid H_ {0})} ${ displaystyle P ( { text {error}} mid H_ {0})}$ меньше или равно заранее заданному уровню α { displaystyle alpha} alpha . В этой настройке оптимальной процедурой тестирования является тест отношения правдоподобия. Кроме того, оптимальный тест гарантирует, что вероятность ошибки 2-го типа экспоненциально убывает при размере выборки n { displaystyle n}в соответствии с lim n → ∞ — ln ⁡ P (error H 1) N = D (е 0 ∥ е 1) { displaystyle lim _ {n to infty} { frac {- ln P ( mathrm {error} mid H_ {1})} {n} } = D (f_ {0} parallel f_ {1})} ${ displaystyle lim _ {n to infty} { frac {- ln P ( mathrm {error} mid H_ {1})} {n }} = D (f_ {0} parallel f_ {1})}$ . Показатель ошибки D (f 0 ∥ f 1) { displaystyle D (f_ {0} parallel f_ {1})} ${ displaystyle D (f_ {0} parallel f_ {1})}$ — это расхождение Кульбака – Лейблера между вероятностные распределения наблюдений при двух гипотезах. Этот показатель также называют показателем леммы Чернова – Стейна.

Оптимальная экспонента для средней вероятности ошибки при проверке байесовской гипотезы

В байесовской версии проверки двоичной гипотезы каждый заинтересован в минимизации средней вероятности ошибки при обеих гипотезах, предполагая априорную вероятность появления каждой гипотезы. Пусть π 0 { displaystyle pi _ {0}} ${ displaystyle pi _ {0}}$ обозначает априорную вероятность гипотезы H 0 { displaystyle H_ {0}} $H_ {0}$ . В этом случае средняя вероятность ошибки определяется как P ave = π 0 P (error ∣ H 0) + (1 — π 0) P (error ∣ H 1) { displaystyle P _ { text {ave}} = pi _ {0} P ({ text {error}} mid H_ {0}) + (1- pi _ {0}) P ({ text {error}} mid H_ {1}) } ${ displaystyle P _ { text {ave}} = pi _ {0} P ({ text {error}} mid H_ {0}) + (1- pi _ {0}) P ({ text {error} } mid H_ {1})}$ . В этой настройке снова оптимальным является проверка отношения правдоподобия, и оптимальная ошибка уменьшается как lim n → ∞ — ln ⁡ P ave n = C (f 0, f 1) { displaystyle lim _ {n to infty } { frac {- ln P _ { text {ave}}} {n}} = C (f_ {0}, f_ {1})} ${ displaystyle lim _ {n to infty} { frac {- ln P _ { text {ave}}} { n}} = C (f_ {0}, f_ {1})}$ где C (f 0, f 1) { displaystyle C (f_ {0}, f_ {1})} ${ displaystyle C (f_ {0}, f_ {1})}$ представляет информацию Чернова между двумя распределениями, определенными как C (f 0, f 1) = min λ ∈ [0, 1] ∫ (f 0 (x)) λ (f 1 (x)) (1 — λ) dx. { displaystyle C (f_ {0}, f_ {1}) = min _ { lambda in [0,1]} int (f_ {0} (x)) ^ { lambda} (f_ {1 } (x)) ^ {(1- lambda)} , dx.} ${ displaystyle C (f_ {0}, f_ {1}) = min _ { lambda in [0, 1]} int (f_ {0} (x)) ^ { lambda} (f_ {1} (x)) ^ {(1- lambda)} , dx.}$

Ссылки

Источник

Пусть
имеется некоторый, канал связи, который
описывается условными переходными
вероятностями Р(у | х), х є Хⁿ,
y є Yⁿ,
где X и Y — его входной и выходной алфавиты,
а Xⁿ
и Yⁿ
означают всевозможные последовательности
длины n
из алфавитов X и Y соответственно.
Обозначим через р_од(V,S)
вероятность ошибочного декодирования
в таком канале при использовании
некоторого кода V, состоящего из М
комбинаций, и алгоритма декодирования
по максимуму правдоподобия, если
передаётся сообщение S, 1 ≤ S ≤ М. Достаточно
общая верхняя граница для р_од
( V,S) при наилучшем выборе кода V была
получена Р. Галлагером.

Существует
блоковый код V длины n,
состоящий из М комбинаций, для которого
при передаче произвольного сообщения
S, 1 ≤ S ≤ М,

где
P(у
| х) — переходная условная вероятность
для блоков длины n
в заданном канале связи; Q(x) — произвольное
вероятностное распределение на входных
блоках длины n.

Эту
границу можно представить в экспоненциальной
форме, заменив на среднюю по сообщениям
вероятность ошибки

при произвольном наборе вероятностей
этих сообщений.

Для
2СК без памяти с вероятностью ошибки
символа р получается решение в замкнутом
виде

при

Неравенство
(7.21) позволяет сделать важный вывод, что
при R < С (Е(R)
> 0) вероятность ошибки при выборе
наилучшего кода не только убывает к
нулю при n→∞,
но убывает и как экспонента от n.
Именно поэтому границы подобного типа
называются экспонентами
вероятностей ошибок.

Для
того, чтобы сравнивать коды различной
мощности, воспользуемся понятием
эквивалентной вероятности ошибки р_э.

3) Коды с гарантированным обнаружением и исправлением ошибок

Пусть
задан некоторый блоковый код длины n,
состоящий из М
комбинаций (блоков, слов, векторов)
X₁,
Х₂
,
•••, Х_M.

Будем
всюду считать, что входной X
и выходной Y
алфавиты канала совпадают. В общем
случае канал может иметь память и
задаваться вероятностями p(х|у)
переходов входных блоков х в выходные
у.

Определение
1.
Расстоянием
Хэмминга
ρ(х, х’) между двумя комбинациями х
є Хⁿ
и х’ є
Хⁿ
будем называть число позиций этих
комбинаций, в которых отдельные кодовые
символы х и х’ не совпадают. Очевидно,
что 1≤ ρ (х, х’) ≤ n
для любых х’ ≠ х, и что ρ (х, х) = 0 для
любых х є
Хⁿ.

Определение
2. Образцом ошибки е будем называть
двоичный блок длины n,
который
имеет единицы в тех позициях, в которых
символы переданного х и принятого у
блоков отличаются друг от друга, и нули
— в остальных позициях.

Определение
3. Весом Хэмминга |х| блока (вектора) х
называют число ненулевых символов этих
блоков.

Определение
4. Кратностью
образца ошибки е (или короче — кратностью
ошибки) будем называть его вес Хэмминга
|е|. (По существу это число ошибок, которое
произошло при передаче блока х).

4) Линейные двоичные коды для обнаружения и исправления ошибок. Важные подклассы линейных двоичных кодов.

Определение
1.
Линейным
блочным двоичным кодом длины п
называется любое множество двоичных
последовательностей длины п,
которое содержит чисто нулевую
последовательность, и для каждой пары
последовательностей, принадлежащих
этому множеству, их поразрядная сумма
по mod
2 также является элементом этого
множества.

Пример.
Множество последовательностей длины
5: 00000, 11101, 01010, 10111, образует линейный код,
что проверяется непосредственно.
Поразрядная сумма по mod2
2-й
и 3-ей комбинации даёт 4-ю комбинацию,
сумма 3 и 4 даёт 2-ю, а сумма 2 и 4 даёт 3-ю
комбинацию.

Линейный
код удовлетворяет определению линейного
подпространства V
для пространства V*
всех двоичных последовательностей
длины п.

Из
алгебры известно, что всякое k-мерное
линейное подпространство п-
мерного
пространства, состоящего из конечного
числа (2ⁿ)
элементов, содержит базис, т.е.
совокупность k
линейно
независимых элементов, из которых путём
поразрядного суммирования по mod
2 можно образовать любые элементы данного
подпространства, т.е. в данном случае
комбинации линейного кода.

Совокупность
элементов базиса, записанная в виде
линейно независимых строк, образует
k×n
двоичную матрицу G,
которая называется порождающей
матрицей
кода:

Множество
всех кодовых слов, порождённых G,
может быть представлено
как
x
= bG,

где
х — вектор-строка кодовой комбинации
размерности n;

b
—
вектор-строка информационных символов
длины k.

Здесь
выполняется умножение вектора на
матрицу, а все действия осуществлены
по mod
2. В качестве вектора b
можно использовать k
последовательных элементов сообщения,
выдаваемых двоичным источником.
Переход от избыточных кодов общего вида
к линейным кодам практически решает
проблему сложности кодирования.
Действительно, вместо запоминания
М=
2^kкомбинаций
длины п,
т.е. п2^k
бит в общем случае, нам достаточно
запомнить лишь порождающую матрицу,
состоящую из пк
=
n
log₂М
бит. Сама же процедура кодирования
потребует выполнения не более чем
2kn
элементарных операций.

Для
любого линейного кода, заданного
некоторой порождающей матрицей G,
очевидно также следующее свойство:
любые перестановки столбцов и элементарные
преобразования строк, заключающиеся в
их перестановках или в суммировании
друг с другом, не изменяют список весов
данного кода. При помощи таких
преобразований любая (k
х n)
двоичная матрица G
с линейно-независимыми строками может
быть приведена к каноническому
виду

где
{
p_ij
— некоторые двоичные элементы; I_k
— единичная k
х k
матрица (с единицами на главной
диагонали и нулями в других местах); Р
— матрица k
х (n-k),
состоящая из двоичных элементов; (A
| B)
означает последовательную запись
матриц А и В}.

Тогда
x=(b
| c), (7.49)

где
с = bР.

По
правилу матричного умножения получаем
для с = (c₁,
…, c_n_—_k)

c_j
= сумм(i
от
1 до
k)(b_i
p_ij
(mod 2)), i=1, 2, …, n-k.

Определение
2. Линейные коды, слова которых представимы
в виде x=b/c,
называются систематическими.
Всякий
линейный код эквивалентен
некоторому
систематическому в смысле сохранения
списка весов, а, следовательно, и
расстояний Хэмминга. Первые k
символов
кодовых слов, совпадающих с символами
источника, называются информационными,
а последние n-k
символов
— проверочными.

Скорость
кода R,
определённая ранее как log₂(М/n),
для-линейного
кода будет равна k/n,
т.е. для систематического — отношению
числа информационных символов k
к длине кодового блока n.
Систематические коды с длиной блока
n
и с числом информационных символов k
будем кратко называть (n,
k)-кодами.
Иногда такой код обозначают тремя
параметрами (n,
k,
d),
где d
—
минимальное кодовое расстояние.

В
линейной алгебре существует понятие
ортогонального
пространства
или нуль-пространства для заданного
линейного пространства V.
Это по определению такое множество
V*
векторов х*
длины
n,
для которых (х*,
х) =
0 при любом хє V,
где (, ) означает скалярное произведение
соответствующих векторов (В нашем случае
все операции производятся по mod2).

Доказывается,
что это множество всегда является
линейным пространством, причём если
код V
имеет размерность k,
то код V*
будет иметь размерность n-k,
т.е. содержать 2ⁿ^—^k
комбинаций. Код V*,
совпадающий с ортогональным пространством,
называется дуальным
к коду V.
Он, очевидно, также может быть задан
своей порождающей матрицей G*=H
размерностью (n-k)
х n.
Тогда комбинации исходного кода V
могут быть определены как решения
векторно-матричного уравнения

V
= {х
: хH^T=
0}, (7.51)

где
Т
означает символ транспонирования
матрицы Н,
т.е.
взаимную замену строк и столбцов. Матрица
Н, которая является порождающей для
кода V*,
называется
проверочной
матрицей для исходного кода V.
Матрица Н так же, как и G,
может быть представлена в канонической
форме, причём можно показать, что
Н=(
-P^T
| I_n_—_k).

Определение
3. Синдромом
по коду V для любого принятого на выходе
канала связи двоичного слова y
длины n
будем называть двоичный вектор-строку
длины n-k:
s = yH^T,

где
Н — проверочная матрица кода V.

Оптимальное
декодирование в 2СК без памяти можно
производить, отыскивая слово минимального
веса, синдром которого совпадает с
синдромом, полученным по принятому
слову. Такой алгоритм декодирования
называется синдромным.

Схемы
кодирования и вычисления синдрома для
произвольного линейного кода приведены
на рисунках:

Элемент
порождающей матрицы p_ij
определяет характер связи i-й
ячейки регистра с j-м
сумматором: если p_ij
=
1 — связь есть, если p_ij
= 0 — связь отсутствует. Кодирование
происходит следующим образом: вектор
b
записывается
в регистр, после чего с выходов сумматоров
считывается вектор с.
Для
кодирования систематического кода
необходимо лишь п-к
сумматоров, связи которых с регистром
задаются матрицей Р. При этом вектор х
образуется
из вектора b
и
выходов п-к
сумматоров (вектора с).

Элемент
проверочной матрицы h_ij
определяет
характер связи i-й

ячейки
регистра с j-м
сумматором: если h_ij
=1
— связь есть, если h_ij
=
0 — связь

отсутствует.
Для вычисления синдрома вектор у
записывается в регистр, после чего с
выходов сумматоров считывается s.

Важные подклассы
линейных двоичных кодов.

Коды
с общей проверкой на чётность.
Это
класс кодов с параметрами (n,
k)
= (k
+ 1, k),
k
=
1, 2, …, когда имеется лишь один проверочный
символ, который образуется как сумма
по mod
2 всех информационных символов. Очевидно,
что минимальное расстояние d
для данных кодов всегда равно 2 и поэтому
они могут гарантированно обнаруживать
лишь одну ошибку. Комбинации данного
кода имеют лишь чётные веса.

Коды
Хэмминга.
Данный
класс кодов имеет параметры (n,
k)
= (2^s
-1, 2^s
-1-s),
s
— целое. Он определяется проверочной
матрицей Н,
которая
должна содержать все 2^s
—
1 ненулевых двоичных векторов. Легко
видеть, что данный класс кодов имеет
при любых s
минимальное кодовое расстояние, равное
3. Это пример совершенного кода,
исправляющего все однократные ошибки
и ничего более. Коды Хэмминга могут
гарантированно обнаруживать ошибки
кратности 1 и 2.

Модифицированный
код Хемминга
(КХМ) способен обнаруживать двойные
ошибки, а так же ошибки нечётной
кратности, плюс к этому – исправлять
одиночные ошибки.

М-последовательности. Это
класс кодов с параметрами (п,
к)
=
(2^S
-1,
s),
s
— целое,
которые определяются как дуальные к
кодам Хэмминга той же самой длины. Данный
класс кодов может быть определён также
иначе, как совокупность выходных
последовательностей при различных
начальных заполнениях линейного регистра
длины s
со связями, выбранными так, чтобы период
выходной последовательности оказался
равным 2^S
—1.
Поэтому они получили название
последовательностей
максимальной длины
или М-последовательностей.
Все
комбинации данного кода, кроме нулевой,
имеют одинаковый вес 2^S^{— 1}
и, следовательно, для такого кода d
= 2^S^{— 1}.
Коды Хэмминга и М-
последовательности
являются крайними случаями кодов с
малой и большой величиной минимального
кодового расстояния. Они не всегда
удобны для практического использования,
поскольку исправление только однократных
ошибок обычно оказывается недостаточным
для обеспечения высокой верности
передачи, а высокая исправляющая
способность М-последовательностей
покупается за счёт их весьма низкой
кодовой скорости R.
Поэтому необходимо иметь класс кодов
с промежуточными значениями R.
Это может быть достигнуто при переходе
к определённым подклассам циклических
кодов.

Полиномиальные
коды. Циклические коды. Коды Боуза-Чоудхури-
Хоквингема (БЧХ).
Кодовые
слова двоичного линейного кода могут
быть представлены в виде полиномов

x(D)
= x₀+x_lD
+ x₂D²+…+x_n_–_lDⁿ^—^l
степени
п-1
от некоторой формальной переменной
D,
причём двоичные коэффициенты х_i
задают
символы кодового слова.

Полиномиальный
код определяется как множество
полиномов (кодовых слов) степени п
—1,
получаемых умножением информационного
полинома b(D)
степени k-1
на порождающий полином кода g(D)
степени
п-к:
x(D)
= b(D)g(D).

Уравнение
задаёт процедуру кодирования
полиномиального кода: сообщение
дискретного источника кодируется
примитивным кодом длины к,
символы
примитивного кода становятся коэффициентами
информационного полинома b(D)
= b₀+b₁D+…+b_k_—_lD
^k^{— 1},
последний умножается на порождающий
полином кода g(D)
= g_o
+g_lD+…+g_n_—_kDⁿ^—^k,
и после приведения подобных членов
определяются п
коэффициентов полинома x(D),
являющихся символами кодового слова.

Из
уравнения видно, что любой из полиномов
x(D),
соответствующих кодовым словам
полиномиального кода, должен делиться
без остатка на порождающий полином
g(D).
Остаток от деления полинома y(D),
соответствующего принятой из канала
комбинации, на порождающий полином кода
g(D)
называется синдромным
полиномом s(D).
Если синдромный полином равен нулю
(т.е. деление произошло без остатка), то
принятая комбинация является кодовым
словом. В противном случае принятая
комбинация не является кодовым
словом. Таким образом, для полиномиальных
кодов процедура обнаружения ошибок
(вычисление синдрома) состоит в делении
принятой комбинации на порождающий
многочлен.

На
практике находят применение циклические
коды, являющиеся частным случаем
полиномиальных кодов.

Определение
. Линейный двоичный (n,
k)-код
V
называется циклическим кодом, если в
результате циклического сдвига любой
из его комбинаций полученная комбинация
снова принадлежит коду, т.е. S_x
є
V,
если x
є
V.

Теорема.
Для
любого двоичного циклического (п, к)-кода
существует такой многочлен g(D)
степени
r
= n-k
с
двоичными коэффициентами, который делит
без остатка многочлен Dⁿ
+1,
и
при этом любое кодовое слово может быть
представлено как многочлен х(D)
степени n-1
следующего
вида:

x(D)
= g(D)b(D),

где
b(D)
— произвольный
многочлен с двоичными коэффициентами
степени не выше k-
1.

Многочлен
g(D),
о котором идёт речь в данной теореме,
называется порождающим
многочленом
циклического кода.

Циклические
коды значительно упрощают описание
линейного кода, поскольку для них
вместо задания k
х (n—k)
элементов двоичной матрицы Р в
представлении требуется задать (n—k+1)
двоичных коэффициентов многочлена
g(D).
Кроме
того, они упрощают процедуру кодирования
и декодирования для обнаружения
ошибок. Действительно, для осуществления
кодирования достаточно выполнить
перемножение полиномов, что реализуется
с помощью линейного регистра,
содержащего k
ячеек памяти и имеющего обратные
связи, соответствующие многочлену h(D).

Для
обнаружения ошибок достаточно разделить
многочлен, соответствующий принятому
слову y(D),
на порождающий многочлен g(D)
и
проверить, будет ли остаток от деления
равен нулю. Эта процедура также
осуществляется на линейных сдвиговых
регистрах с обратными связями. Однако
более важное преимущество циклических
кодов состоит в том, что они могут быть
сконструированы как коды с некоторым
гарантированным значением минимального
кодового расстояния. Для этого необходимо
определённым образом выбрать порождающий
многочлен кода g(D).
Циклические
коды, которые имеют порождающий многочлен,
заданный своими определёнными
корнями, называются кодами
Боуза-Чоудхури-Хоквингема (кратко
БЧХ-кодами). Однако корни этого многочлена
ищутся не среди вещественных или
комплексных чисел, а как элементы так
называемых конечных полей Галуа.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

From Wikipedia, the free encyclopedia

In information theory, the error exponent of a channel code or source code over the block length of the code is the rate at which the error probability decays exponentially with the block length of the code. Formally, it is defined as the limiting ratio of the negative logarithm of the error probability to the block length of the code for large block lengths. For example, if the probability of error ${displaystyle P_{mathrm {error} }}$ of a decoder drops as ${displaystyle e^{-nalpha }}$ , where is the block length, the error exponent is alpha . In this example, ${displaystyle {frac {-ln P_{mathrm {error} }}{n}}}$ approaches alpha for large . Many of the information-theoretic theorems are of asymptotic nature, for example, the channel coding theorem states that for any rate less than the channel capacity, the probability of the error of the channel code can be made to go to zero as the block length goes to infinity. In practical situations, there are limitations to the delay of the communication and the block length must be finite. Therefore, it is important to study how the probability of error drops as the block length go to infinity.

Error exponent in channel coding[edit]

For time-invariant DMC’s[edit]

The channel coding theorem states that for any ε > 0 and for any rate less than the channel capacity, there is an encoding and decoding scheme that can be used to ensure that the probability of block error is less than ε > 0 for sufficiently long message block X. Also, for any rate greater than the channel capacity, the probability of block error at the receiver goes to one as the block length goes to infinity.

Assuming a channel coding setup as follows: the channel can transmit any of $M=2^{{nR}};$ messages, by transmitting the corresponding codeword (which is of length n). Each component in the codebook is drawn i.i.d. according to some probability distribution with probability mass function Q. At the decoding end, maximum likelihood decoding is done.

Let ${displaystyle X_{i}^{n}}$ be the th random codeword in the codebook, where goes from to . Suppose the first message is selected, so codeword $X_{1}^{n}$ is transmitted. Given that $y_{1}^{n}$ is received, the probability that the codeword is incorrectly detected as ${displaystyle X_{2}^{n}}$ is:

${displaystyle P_{mathrm {error} 1to 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})).}$

The function ${displaystyle 1(p(y_{1}^{n}mid x_{2}^{n})>p(y_{1}^{n}mid x_{1}^{n}))}$ has upper bound

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

for s>0; Thus,

${displaystyle P_{mathrm {error} 1to 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}.}$

Since there are a total of M messages, and the entries in the codebook are i.i.d., the probability that $X_{1}^{n}$ is confused with any other message is times the above expression. Using the union bound, the probability of confusing $X_{1}^{n}$ with any message is bounded by:

${displaystyle P_{mathrm {error} 1to 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 }}$

for any . Averaging over all combinations of ${displaystyle x_{1}^{n},y_{1}^{n}}$ :

${displaystyle P_{mathrm {error} 1to 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-srho }right)left(sum _{x_{2}^{n}}Q(x_{2}^{n})[p(y_{1}^{n}mid x_{2}^{n})]^{s}right)^{rho }.}$

Choosing and combining the two sums over $x_{1}^{n}$ in the above formula:

${displaystyle P_{mathrm {error} 1to 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 }.}$

Using the independence nature of the elements of the codeword, and the discrete memoryless nature of the channel:

${displaystyle P_{mathrm {error} 1to 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 }}$

Using the fact that each element of codeword is identically distributed and thus stationary:

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

Replacing M by 2^nR and defining

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

probability of error becomes

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

Q and rho should be chosen so that the bound is tighest. Thus, the error exponent can be defined as

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

Error exponent in source coding[edit]

For time invariant discrete memoryless sources[edit]

The source coding theorem states that for any and any discrete-time i.i.d. source such as and for any rate less than the entropy of the source, there is large enough and an encoder that takes i.i.d. repetition of the source, $X^{{1:n}}$ , and maps it to binary bits such that the source symbols $X^{{1:n}}$ are recoverable from the binary bits with probability at least .

Let $M=e^{{nR}},!$ be the total number of possible messages. Next map each of the possible source output sequences to one of the messages randomly using a uniform distribution and independently from everything else. When a source is generated the corresponding message M=m, is then transmitted to the destination. The message gets decoded to one of the possible source strings. In order to minimize the probability of error the decoder will decode to the source sequence $X_{1}^{n}$ that maximizes ${displaystyle P(X_{1}^{n}mid A_{m})}$ , where $A_{m},$ denotes the event that message was transmitted. This rule is equivalent to finding the source sequence $X_{1}^{n}$ among the set of source sequences that map to message that maximizes $P(X_{1}^{n})$ . This reduction follows from the fact that the messages were assigned randomly and independently of everything else.

Thus, as an example of when an error occurs, supposed that the source sequence $X_{1}^{n}(1)$ was mapped to message as was the source sequence $X_{1}^{n}(2)$ . If $X_{1}^{n}(1),$ was generated at the source, but $P(X_{1}^{n}(2))>P(X_{1}^{n}(1))$ then an error occurs.

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

Let $A_{{i'}},$ denote the event that the source sequence $X_{1}^{n}(i')$ was mapped to the same message as the source sequence $X_{1}^{n}(i)$ and that $P(X_{1}^{n}(i'))geq P(X_{1}^{n}(i))$ . Thus, letting $X_{{i,i'}},$ denote the event that the two source sequences and i', map to the same message, we have that

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

and using the fact that $P(X_{{i,i'}})={frac {1}{M}},$ and is independent of everything else have that

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

A simple upper bound for the term on the left can be established as

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

for some arbitrary real number s>0,. This upper bound can be verified by noting that $P(P(X_{1}^{n}(i'))>P(X_{1}^{n}(i))),$ either equals or because the probabilities of a given input sequence are completely deterministic. Thus, if $P(X_{1}^{n}(i'))geq P(X_{1}^{n}(i)),,$ then ${frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}geq 1,$ so that the inequality holds in that case. The inequality holds in the other case as well because

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

for all possible source strings. Thus, combining everything and introducing some , have that

${displaystyle P(Emid S_{i})leq P(bigcup _{ineq i'}A_{i'})leq left(sum _{ineq i'}P(A_{i'})right)^{rho }leq left({frac {1}{M}}sum _{ineq i'}left({frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}right)^{s}right)^{rho },.}$

Where the inequalities follow from a variation on the Union Bound. Finally applying this upper bound to the summation for P(E), have that:

${displaystyle P(E)=sum _{i}P(Emid 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 },.}$

Where the sum can now be taken over all i', because that will only increase the bound. Ultimately yielding that

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

Now for simplicity let so that $s={frac {1}{1+rho }},.$ Substituting this new value of into the above bound on the probability of error and using the fact that i', is just a dummy variable in the sum gives the following as an upper bound on the probability of error:

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

and each of the components of $X_{1}^{n}(i),$

are independent. Thus, simplifying the above equation yields

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

The term in the exponent should be maximized over rho , in order to achieve the highest upper bound on the probability of error.

Letting $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:

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

References[edit]

R. Gallager, Information Theory and Reliable Communication, Wiley 1968