Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике § 3.8. Неравенство ФайнстейнаВ этом параграфе будет рассмотрено одно из важнейших теоретико-информационных неравенств, с помощью которого могут быть доказаны прямые теоремы кодирования для различных каналов связи, а именно неравенство Файнстейна. Рассмотрим дискретный канал, задаваемый переходными вероятностями
где
Теорема 3.8.1 (неравенство Файнстейна). Пусть вероятность
где
и
Доказательство. Для доказательства существования кода, указанного в теореме, мы будем пользоваться методом, который называется методом максимальных кодов. В соответствии с этим методом, содержание которого будет изложено ниже, мы покажем, что для всякого фиксированного
Рис. 3.8.1. К доказательству теоремы 3.8.1. Очевидно, что это неравенство эквивалентно неравенству (3.8.3) и, следовательно, доказательство существования кода, скорость которого удовлетворяет неравенству (3.8.5), эквивалентно доказательству утверждения теоремы. Далее мы будем предполагать, что Зафиксируем некоторое
Тогда множество
Пусть
где Предположим, что можно выбрать
где а — произвольное заданное число из интервала Покажем, что
Тогда должно выполняться следующее неравенство:
С другой стороны, из формулы (3.8.7) следует, что
Так как
то
что противоречит исходному предположению о том, что Как было сказано,
В противном случае выбор кодовых слов можно было бы продолжить, положив Так как для произвольных событий
Это неравенство имеет место для всех последовательностей
Из соотношений (3.8.11) и (3.8.12) следует, что
Используя это и предыдущее неравенство, можно получить, что
Теперь, чтобы завершить доказательство теоремы, необходимо связать левую часть этого неравенства с числом
Оценим вероятность
и, следовательно,
Суммируя обе части последнего неравенстга по всем
где последнее неравенство — следствие того, что
Учитывая неравенства (3.8.15), (3,8.16), (3.8.19), а также что Вернемся теперь к формулировке теоремы и обсудим возможности ее применения. В теореме утверждается существование кода, слова которого принадлежат множеству Предположим, что
где С — информационная емкость дискретного по времени канала, определяемая соотношением
и верхняя грань разыскивается по всем
Предположим, что при каждом взаимной информации
и
Для моделей каналов связи, представляющих интерес, верхняя грань в (3.8.21) достигается при Ниже мы применим неравенство Файнстейна и указанное выше рассуждение для доказательства прямых теорем кодирования для некоторых каналов. Мы покажем, что в рассматриваемых каналах существуют коды с произвольно малой вероятностью ошибки при условии, что скорость кода не превосходит информационную емкость канала. Фактически вместе с обратной теоремой кодирования это является доказательством того, что информационная емкость и пропускная способность, определенная ранее в § 3,2, совпадают.
|
1 |
Оглавление
|