Глава 10. Основная теорема Шеннона

10.1. Введение

В гл. 6 было введено понятие энтропии, а в разд. 6.8 показано, что существуют методы кодирования со скоростью, сколь угодно близкой к энтропии входа. В частности, было показано [см. (6.8.2)],

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

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

Далее рассматривался канал, и пропускная способность С канала определялась равенством (8.1.1). В настоящей главе доказывается фундаментальный результат того, что даже при наличии шума можно сколь угодно близко подойти к пропускной способности канала. Точнее, можно передавать сообщения по каналу со скоростью, сколь угодно близкой к пропускной способности, и с надежностью, сколь угодно близкой к 1.

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