Глава 9. Предварительные математические сведения

9.1 Введение

Некоторые считают, что теорема доказана, когда приведено логически правильное доказательство; другие считают, что теорема доказана только в том случае, когда студент видит, почему она обязана быть верной. Автор стремится придерживаться второй точки зрения. Поэтому сейчас сделаем отступление и докажем, а не просто сформулируем ряд результатов, необходимых для понимания доказательства основной теоремы Шеннона. Изложение будет достаточно подробным для того, чтобы читатель мог прочно усвоить соответствующие результаты, а не просто ознакомиться с ними. Поэтому в ряде случаев будут приведены сведения, не используемые в дальнейшем.

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

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

Нам нужно будет также оценить хвост биномиального

распределения, чтобы показать, что его вклад не очень велик. Поэтому потребуется знаменитая приближенная формула Стирлинга для Эта формула часто используется, но редко просто объясняется.