Введение

Пределы скорости передачи данных

В теории информации теорема кодирования с помехами (иногда теорема Шеннона или предел Шеннона) устанавливает, что для любой заданной степени зашумлённости канала связи возможно (в теории) передавать дискретные данные (цифровую информацию) практически без ошибок со скоростью, не превышающей вычислимый максимум. Этот результат был представлен Клодом Шенноном в 1948 году и частично основывался на более ранних работах и идеях Гарри Найквиста и Ральфа Хартли. Предел Шеннона или пропускная способность канала Шеннона относится к максимальной скорости передачи данных без ошибок, которую теоретически можно обеспечить при передаче по каналу, подверженному случайным ошибкам, при заданном уровне шума. Впервые она была описана Шенноном в 1948 году и вскоре после этого опубликована в книге Шеннона и Уоррена Уивера под названием «Математическая теория связи» (1949). Это заложило основу современной дисциплины – теории информации.

Обзор

Сформулированная Клодом Шенноном в 1948 году, теорема описывает максимальную достижимую эффективность методов коррекции ошибок в зависимости от уровня помех и искажений данных. Теорема Шеннона имеет широкое применение как в области связи, так и в области хранения данных. Эта теорема имеет основополагающее значение для современной теории информации. Шеннон представил лишь набросок доказательства. Первое строгое доказательство для дискретного случая приведено в теореме Шеннона, которая утверждает, что для шумного канала с пропускной способностью C и передаваемой информацией со скоростью R существуют коды, позволяющие сделать вероятность ошибки на приемнике сколь угодно малой. Это означает, что теоретически возможно передавать информацию почти без ошибок при любой скорости, меньшей предельной скорости C.

Обратное утверждение также важно. Если , то достижение сколь угодно малой вероятности ошибки невозможно. Все коды будут иметь вероятность ошибки, превышающую определенный положительный минимальный уровень, который возрастает с увеличением скорости передачи. Следовательно, надежная передача информации по каналу со скоростями, превышающими пропускную способность канала, не гарантируется. Теорема не рассматривает редкий случай, когда скорость передачи равна пропускной способности канала. Пропускную способность канала можно рассчитать на основе физических характеристик канала; для канала с ограниченной полосой пропускания и гауссовским шумом – с использованием теоремы Шеннона – Хартли. Простые схемы, такие как "отправка сообщения 3 раза и выбор наиболее часто встречающегося варианта из 3 копий", являются неэффективными методами коррекции ошибок, не способными асимптотически гарантировать передачу блока данных без ошибок. Более совершенные методы, такие как коды Рида — Соломона и, в последнее время, коды с низкой плотностью четности (LDPC) и турбокоды, значительно ближе к достижению теоретического предела Шеннона, но требуют высокой вычислительной сложности. Благодаря использованию этих высокоэффективных кодов и вычислительной мощности современных цифровых сигнальных процессоров, сейчас возможно достигать значений, очень близких к пределу Шеннона. Фактически, было показано, что коды LDPC могут достигать предела Шеннона с точностью до 0,0045 дБ (для бинарных аддитивных каналов с белым гауссовским шумом (AWGN) и очень большой длины блоков).

Конспект доказательства

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

Конспект доказательства

Доказательство проводится почти так же, как и для теоремы о кодировании каналов. Достижимость следует из случайного кодирования, при котором каждый символ выбирается случайным образом из распределения, достигающего пропускной способности для данного канала. Аргументы о типичности используют определение типичных множеств для нестационарных источников, как это определено в статье об асимптотическом свойстве равнораспределённости. Техническая сложность, связанная с нижним пределом, проявляется, когда последовательность не сходится.