Вторая теорема Шеннона

Отношение пропускной способности канала связи к скорости неискаженной передачи символов алфавита передаваемого сообщения должно быть больше или равно энтропии передачи одного символа.[5]

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

Доказательство теоремы основывается на следующих рассуждениях. Первоначально последовательность X={x_i} кодируется символами из В так, что достигается максимальная пропускная способность (канал не имеет помех). Затем в последовательность из В длины n вводится r символов по каналу передается новая последовательность из n + r символов. Число возможных последовательностей длины n + r больше числа возможных последовательностей длины n. Множество всех последовательностей длины n + r может быть разбито на n подмножеств, каждому из которых сопоставлена одна из последовательностей длины n. При наличии помехи на последовательность из n + r выводит ее из соответствующего подмножества с вероятностью сколь угодно малой.[12]

Теорема позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность n + r, и тем самым восстановить исходную последовательность длины n.

Эта теорема не дает конкретного метода построения кода, но указывает на пределы достижимого в области помехоустойчивого кодирования, стимулирует поиск новых путей решения этой проблемы.