Теорема о кодировании в зашумленном канале
-
Теорема Шеннона о кодировании в зашумленном канале
- Теорема устанавливает максимальную скорость передачи данных без ошибок через зашумленный канал.
- Теорема была сформулирована Клодом Шенноном в 1948 году.
- Теорема имеет широкое применение в связи и хранении данных.
-
Основные понятия
- Пропускная способность канала C может быть рассчитана исходя из физических свойств канала.
- Для канала с ограниченной полосой пропускания и гауссовым шумом используется теорема Шеннона–Хартли.
- Простые схемы исправления ошибок неэффективны и не гарантируют передачу данных без ошибок.
-
Математическое утверждение
- Сообщение W передается по зашумленному каналу с использованием функций кодирования и декодирования.
- Вероятность ошибки определяется как отношение числа ошибок к общему числу символов.
-
Схема доказательства
- Доказательство включает результат достижимости и обратный результат.
- Достижимость доказывает существование кода, удовлетворяющего требуемой низкой вероятности ошибки при любой скорости передачи данных ниже пропускной способности канала.
- Обратный результат показывает, что при скорости передачи данных выше пропускной способности канала вероятность ошибки не может быть сколь угодно малой.
-
Достижимость для дискретных каналов без памяти
- Используется аргумент случайного кодирования и свойство асимптотического равнораспределения.
- Кодовая книга создается случайным образом, что упрощает анализ и доказывает существование кода.
- Вероятность ошибки делится на две части: отсутствие совместно типичных кодовых слов и неправильная последовательность X.
-
Слабый конверс для дискретных каналов без памяти
- Используется неравенство Фано и неравенство для энтропии и взаимной информации.
- Вероятность ошибки отклоняется от 0 при R больше C.
-
Мощный конверс для дискретных каналов без памяти
- Сильная обратная теорема Вулфовица утверждает, что при R больше C вероятность ошибки не может быть сколь угодно малой.
-
Слабое и строгое обратные утверждения
- Слабое обратное утверждение утверждает, что вероятность ошибки ограничена от нуля при n стремящемся к бесконечности.
- Строгое обратное утверждение гласит, что ошибка равна 1 при n стремящемся к бесконечности.
-
Теорема о канальном кодировании для нестационарных каналов без памяти
- Канал не имеет памяти, но вероятности его перехода изменяются со временем.
- Пропускная способность канала определяется по формуле, где C — максимальное значение пропускной способности для каждого канала.
-
Краткое изложение доказательства
- Доказательство выполняется почти так же, как в случае теоремы о канальном кодировании.
- Достижимость вытекает из случайного кодирования, где каждый символ выбирается случайным образом.
- Аргументы типичности используют определение типичных наборов для нестационарных источников.
-
Технические аспекты ограничения информации
- Ограничение информации вступает в силу, когда сумма не сходится.
-
Связанные темы
- Свойство асимптотического равномерного распределения (AEP)
- Неравенство Фано
- Теория искажения скорости
- Теорема Шеннона о кодировании исходного кода
- Теорема Шеннона–Хартли
- Турбо-код
- Записи
- Рекомендации