Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

10.5. Средний случайный код

Все, что было сделано до сих пор, представляется достаточно разумным, за исключением, возможно, случайного выбора кода (хотя можно надеяться, что перемешивание, описанное в разд. подготовило читателя к идее случайного выбора). Такой прием достаточно типичен при обычном исследовании задачи. Однако следующая идея Шеннона, состоящая в том, что нужно усреднить по всем возможным случайным кодам (а что еще остается делать?), не принадлежит к тем идеям, которые сразу приходят в голову. Конечно, после того, как идея предложена, следует ее испробовать.

Таким образом, необходимо провести усреднение по всем кодам. Средние значения по всем кодам будут обозначаться волнистой чертой сверху. Кодовые слова выбираются из урны одно за другим (или формируются символ за символом путем бросания монеты), и общее число слов равно [см. равенство (10.4.1)]. Всего имеется слов длины так что общее число различных кодов равно При случайном выборе все эти коды равновероятны, так что каждый из них появляется с вероятностью Усреднение, соответствующее этим вероятностям, дает среднюю вероятность ошибки, равную Константа 6 одинакова для Ьсех кодов и не зависит от всего кода. Поэтому после усреднения множеству всех кодов неравенство (10.4.6) имеет вид

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

последовательностей длины Пусть число последовательностей, лежащих в шаре Тогда

Поскольку канал является двоичным симметричным, то

Напомним, что [из (10.4.2)]

Используя биномиальное неравенство [см. (9.4.6)] с получаем

Поэтому из равенства (10.5.2) следует

Таким образом, из (10.5.1) получаем

Учитывая равенство (8.5.3), для двоичного симметричного канала имеем Из определения ясно, что Поэтому показатель степени в (10.5.4) можно записать:

Поскольку энтропия является выпуклой функцией для любого можно использовать оценку

где (поскольку

Поэтому и неравенство (10.5.4) имеет вид

Из равенства и получаем

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

то среднюю ошибку можно сделать сколь угодно малой, выбрав достаточно большое

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

удовлетворяющий этим требованиям. Следовательно, доказан результат Шеннона.

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

Почему же мы испытывали такие большие трудности при отыскании хороших кодов? Причина кроется в следующем: при доказательстве предполагалось, что длина блока достаточно велика. На самом деле она не «достаточно велика», а очень и очень велика!

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

<< Предыдущий параграф Следующий параграф >>
Оглавление