Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 66
Текст из файла (страница 66)
Таким образом, вероятность выбора некоторого частного кода *,,х,...,хи в этом ансамбле равна м П(З(х!). Каждый код из ансамбля имеет свою вероятность ошибочного декодирования при ! ! декодировании по максимуму правдоподобия. Если рассчитать среднюю по всему ансамблю кодов вероятность ошибочного декодирования, то она даст верхнюю границу Р, для наилучшего кода (т.е. кода с минимальной величиной Р„,). Среднюю по ансамблю кодов величину р,„(Я) при передаче Х-го сообщения можно тогда определить следующим образом: Р, (Я) = ~~! ~~! (7(хг)Р(У1х) Р(одЬУ, хе, У), (7.12) м г где Р(од~К, х, у) — вероятность ошибочного декодирования при условии, что, во-первых, передается сообщение Х, во-вторых, что для передачи этого сообщения была случайно выбрана комбинация кода хг, в-третьих, что была принята последовательность у.
Суммирование в (7.12) производится по всем входным и выходным последовательностям длины л. При заданных Ю, хе, у определим событие А . для каждого Я'!!Ю как событие, состоящее в том, что выбирается такое кодовое слово х ., соответствующее сообщению Я', для кото- рого Р(у~х, ) гР(у~х,) . (7.1З) 264 Теорема 7.2. Существует блоковый код г' длины и, состоящий из М комбинаций, для которого при передаче произвольного сообщения Я, 1 < 5' < М, !+р р (У,Б)<(М вЂ” 1)'~~! "! фх),Р(у!х), 0<р<1, (7.8) ганг" з х" где Р(у1х) — переходная условная вероятность для блоков длины и в заданном канале связи Ях) — произвольное вероятностное распределение на входных бЛоках длины и. Для доказательства теоремы потребуется следующая простая лемма. Лемма.
Пусть Р(А!), ..., Р(Аи) — вероятности событий А!, ..., Алг. Тогда при любом р (О я р я 1) вероятность объединения событий имеет границу РОА ' ХР(А) (7.9) Доказательство леммы. Используя известную аддитивную границу (неравенство Буля) и тривиальную границу для вероятности любого события, получаем Если в (7.13) имеет место строгое неравенство, то декодер максимального правдоподобия примет решение о передаче сообщения Ю' ~ Я, т,е. сделает ошибку.
(При наличии равенства в (7.13) ошибка произойдет не обязательно.) Позтому, используя лемму, получаем р Р(,од~8,х, у)яР ( (Ау, я ~Р(Ау), Оя р К1. (7.14) Согласно определению события Ау, имеем Р[А,,) = ~(7(ху ) . зиу(у!*;)ру(уа,) Легко убедиться, что правую часть (7.15) можно ограничить сверху, дое слагаемое в нем на [Р(у!х,,)/Р(у!х,)] при любом р>0, распространяя х, . Это дает верхнюю границу для Р(Ау ) (') Еа(.') Видно, что Я' является "глухой" переменной суммирования в (7.16), ца фактически не зависит от Я'. Подставляя (7.16) в (7.14), получаем (7.15) если умножить кажсуммирование на все (7.16) и поэтому зта грани- Р Р(од!8, х, у) ь (М-!)~(7(х) г ~Ях Р(у!х,) (7.17) Далее, подставляя (7.17) в (7.12), будем иметь Д(ху)Р(у!ху) ~ Д(х)Р(у!х) 3~ 1 р,„(8) к(м-!)' у' у (7.18) Подставляя р= !/(!+р) в (7,18) и замечая, что ху является также "глухой" переменной суммирования, получаем утверждение теоремы в виде неравенства (7.8).
1+р р (8) < (8~- 1)Р~ ...~. ~...,'~" Пфх,)р~у,~ х,.) у< у„е л„гм 1+р =<и-1! П~[~а(*,)у(„~.,)"-' (М 1) ~ ~фх,)Р(у !х,) (7.19) где 1! и т — объемы алфавитов входа и выхода канала соответственно. Границу (7.19) можно представить в экспоненциальной форме, заменив р„(Б) на среднюю по сообщениям вероятность ошибки р„при произвольном наборе вероятностей этих сообщений: Используем неравенство (7.8) для оценки р.,(Я) в дискретных каналах без памяти, описываемых переходными вероятностями Р(у,!х,), где у еК, х, еХ. Определим в этом случае вероятность случайного выбора кодового слова х как (у(х) = Пфх,). ия Тогда (7.8) преобразуется к виду р,„< р(- (Е,(р,~) — рЕоЦ, и-1 Г )-1 где Ео(Р,О) =-1п~~,"~" фх,)р(у,~х,) ~, я, = —.
(7.20) где Е(Я =1 — 2 1ов (/р+,/1 — р) — А (7.22) при Я= ' <Я.=~-ь( ), аЫ=-(*1 |,*+)1-*)1~ь)1-*)) 1оКз ~1~ ~ГР и '" ~ ~р+ Д-р б ~-а Е(Я)=51оц,— +(1 — 5)1ок, при С>Я>Я,„, (7.23) где б удовлетворяет уравнению я=1-Ь(5), С=1-Ь(р), (7.24) Неравенство (7.21) позволяет сделать важный вывод, что при Я < С (Е(Я) > О) вероятность ошибки при выборе наилучшего кода не только убывает к нулю при и -+ о, но убывает и как экспонента от и.
Именно поэтому границы подобного типа называются экспонентами вероятностей ошибок. Это фактически доказывает прямую часть теоремы кодирования Шеннона. Для доказательства обратной части теоремы кодирования, очевидно, необходимо использовать нижнюю границу р,„для наилучшего кода. Этот вопрос не будем здесь обсуждать, поскольку нижняя граница не имеет большого прикладного значения.
Экспоненты вероятностей (7.20), (7.21) позволяют рассчитать энергетический выигрыш от применения кодирования (ЭВК) как функцию заданной верности р„скорости кода Я и- длины кодового блока п. Однако в отличие от асимптотического случая здесь возникает одна дополнительная сложность. Пусть, например, два кода с одинаковыми скоростями Я, длинами и = 10 и и = 10000 имеют одинаковые вероятности р . Можно ли считать, что в обоих случаях обеспечивается действительно одинаковая верность передачи сообщений? Интуиция подсказывает нам, что во втором случае надежность передачи будет, наверное, больше, чем в первом. Постараемся облечь теперь наши интуитивные ощущения в более строгую форму.
Пусть передается информация такого типа, что количество ошибок на сеансе связи, состоящем из М информационных бит, не играет существенной роли для оценивания качества передачи. Критерием верности тогда служит вероятность Д(Л)) абсолютно правильного приема всех элементов.
Очевидно, что при использовании двоичного кода 266 Чтобы найти наилучшую верхнюю границу, необходимо максимизировать Е,(р, ф по Д(х) и 0 < р < 1. Решение этой задачи для произвольных дискретных каналов представляет определенные трудности. Однако для 2СК без памяти с вероятностью ошибки символа р получается решение в замкнутом виде р„<2 ~~"), (7.21) (7.26) (7.28) длины п, состоящего из М комбинаций, эта вероятность в канале связи без па- мяти может быть рассчитана по формуле фФ) =(1 — р,„) (7.25) где А = У/1о8~М вЂ” число кодовых комбинаций на интервале анализа.
Теперь ясно, что если два кода имеют одинаковые скорости, но разные длины, то код с большей длиной блока будет иметь большее число кодовых комбинаций М и поэтому для него Д(М) оказывается больше при равных зна- чениях М и р„. (Для канала с памятью можно при р,„«1 использовать адди- тивную границу фй) <1- р,„, У 1082М '"' для которой сделанный выше вывод также оказывается справедливым.) Для того чтобы сравнивать коды различной мощности, воспользуемся по- нятием эквивалентной вероятности ошибки р,.
Напомним читателю (см. ~ 5.11), что р, — это такая вероятность ошибки символа в 2СК без памяти, с постоянными параметрами и при отсутствии кодирования, которая обеспечива- ет ту же вероятность правильного приема О(Л~) информационных символов, что и данный код в данном канале. Очевидно, что можно написать ( ) ( )~м™ (7.27) Преобразуя (7.27), получаем ! р — 1 (1 р ) О2 (Видно, что р, оказалось не зависящей от М.) Если р,„«1, то для р, справедливо следующее приближенное выражение: и (7.29) 1082 М Величину р„(соответственно р,) для наилучшего кода можно найти из (7.21).
Расчет энергетического выигрыша одной дискретной системы передачи над другой (ЗВС) можно в общем случае вычислить при р., =сова, по формуле (5.108), ЗВК для заданного кода можно находить при заданной вероятности р, = р, и по формуле (б.б1). Предположение о том, что получатель сообщений не является критичным к количеству ошибок, типично для передачи данных, но вряд ли оправдано для таких сообщений, как оцифрованная речь, печатный текст или факсимильные сообщения. Для этих источников более естественно оценивать качество переда- чи сообщений средним числом ошибочных бит или средним числом ошибоч- ных передач некоторых элементов сообщений.
Зкспоненты вероятностей ошибок являются значительным продвижением в теории кодирования по сравнению с теоремами кодирования, поскольку они определяют верхнюю границу для наилучшего кода как функцию длины кодо- вого блока. Однако это верно лишь для наилучшего кода, тогда как способ его построения является пока неизвестным. Можно, правда, попытаться действи- тельно случайно выбрать некоторый код и зафиксировать его для работы по данному каналу связи. (При неудачном выборе можно повторить эксперимент. 2б7 проверяя эффективность кода при помощи расчета реализуемой им частости ошибочного декодирования.) Однако, как будет показано в дальнейшем, сложность алгоритма декодирования для случайно выбранного кода также экспоненциально возрастает с ростом длины кодового блока и поэтому целесообразно указать некоторый регулярный выбор если не наилучшего кода, то по крайней мере кода, гарантирующего определенную величину ре в заданном канале связи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
