3.8. Верхняя оценка скорости кодов с малой плотностью проверок на четность

Все полученные до сих пор результаты о вероятностях ошибки были оценками сверху. Мы показали, что коды с малой плотностью проверок на четность ведут себя в ДСК по крайней мере так же хорошо, как и оптимальный код с несколько большей скоростью. Однако нет прямого способа показать, что некоторые коды с малой плотностью проверок не ведут себя гораздо лучше, чем средний. Некоторым шагом в этом направлении является следующая теорема, показывающая, что нельзя эффективно использовать такие коды в ДСК, пропускная способность которого сколь угодно близка к скорости кода.

Теорема 3.3. Пусть код с проверками на четность длины со скоростью символами в каждом проверочном множестве используется в ДСК с вероятностью перехода и пусть кодовые слова равновероятны. Пусть

Тогда при. фиксированном и при

вероятность ошибки декодирования ограничена снизу величиной, не зависящей от и большей 0.

Пропускная способность ДСК в битах на символ равна Поскольку теорема утверждает, что для надежной передачи необходимо, чтобы скорость источника была существенно меньше пропускной способности канала. На рис. 3.5 для некоторых значений показано, насколько пропускная способность должна превышать скорость источника.

Доказательство. Пусть и есть переданное кодовое слово, принятая последовательность.

Тогда средняя взаимная информация в битах на символ равна

Если ненадежность информации на символ удовлетворяет неравенству

для некоторого не зависящего от то вероятность ошибки декодирования также оказывается величиной, большей некоторой положительной константы. Мы получим неравенство (3.73), оценивая остальные слагаемые в равенстве (3.72).

Поскольку в коде всего сообщений, то

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

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

Вероятность того, что проверочное соотношение удовлетворится, равна вероятности того, что в

проверочное множество вошло четное число ошибок; таким образом,

Для проверки равенства (3.76) нужно переписать правую часть в виде

и разложить ее по формуле бинома.

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

Подстановка выражений (3.74), (3.75) и (3.77) в равенство (3.72) дает следующее:

По предположению теоремы существует удовлетворяющее равенству

Подставляя равенство (3.79) в неравенство (3.78), получим неравенство (3.73), доказывающее теорему. Ч.Т.Д.