1.6. ТЕОРЕМА ШЕННОНА О СУЩЕСТВОВАНИИ ХОРОШИХ КОДОВ
В последнем разделе мы убедились, что очень простой код 
уменьшает среднюю вероятность ошибки на символ от 0,01 до 0,00530 (ценой передачи 4 символов вместо передачи 2 символов сообщения) и что код 
который также имеет скорость 1/2, уменьшает это значение до 0,00072 (теперь вместо 3 информационных символов необходимо передать 6 символов).
В общем случае для фиксированной скорости 
хотелось бы знать, сколь малым мы можем сделать значение Рсимв с помощью 
-кода. Ответ дается замечательной теоремой Шеннона, которая утверждает, что 
следовательно, и Рсимв в силу упражнения 
может быть сделана сколь угодно малой при условии, что скорость 
меньше пропускной способности канала.
Рис. 1.9 Пропускная способность двоичного симметричного канала
Определение. Пропускная способность двоичного симметричного канала с вероятностью ошибки 
(см. рис. 1.1) равна (рис. 1.9):
Теорема 7. (Шеннон; доказательство опущено). Для любого 
если 
достаточно зелико, существует 
двоичный код со скоростью 
вероятность ошибки которого 
(Подобный же результат справедлив и для недвоичных кодов, но с другим определением пропускной способности.)
К сожалению, эта теорема была доказана пока только вероятностными методами и ничего не говорит о том, как построить эти коды.
На практике (как мы уже видели) трудно вычислить 
и Рсимв, поэтому в качестве более удобного критерия, насколько хорош код, используется минимальное расстояние кода 
Ибо зная 
мы знаем, что код может исправлять 
ошибок (теорема 2), и формула (1.26) является хорошим приближением для 
особенно если 
мало.
Таким образом, возможна такая формулировка основной проблемы теории кодирования: найти коды с большим 
(для эффективности) и с большим 
(чтобы исправлять много ошибок). Конечно, эти цели противоречивы. Верхнюю границу на мощность кода дает теорема 6; другие верхние границы будут даны в гл. 17 (см. рис. 17.7). С другой стороны, более слабой версией теоремы 7 является теорема 12 в конце этой главы, и она утверждает, что хорошие линейные коды существуют. В настоящее время, однако, мы не знаем, как найти такие коды.
Конечно, для практических целей хочется также иметь код, который можно легко кодировать и декодировать.
