2 Раздел:
Согласование дискретного источника с дискретным каналом
Параграф 2.1: Задача согласования дискретного источника с дискретным каналом без шума. Эффективное (статистическое) кодирование.
Предположим, что мы имеем дискретный канал, вероятность возникновения ошибки равна 0 (в идеале 0). Такой канал называют идеальным каналом без памяти (каналом без шума). В соответствии с 1.25, пропускная способность такого канала C = vk * log N. При наличии идеального канала естественно поставить вопрос о возможности передачи по нему без потерь от произвольного дискретного источника, характеризующегося некоторой производительностью H’ (U) со скоростью, равной пропускной способности канала. Схема построения такой системы передачи информации показано на рисунке 2.1:
Необходимость включения кодера и декодера в состав этой системы обусловлено следующими обстоятельствами:
Как показано в параграфе 1.6, для того, чтобы скорость передачи информации в канале была равна его пропускной способности, на вход канала должен действовать дискретный источник с определенными статическими свойствами, максимизирующие величину I (Z, Z). В частности, в интересующем нас случае идеальном канале без помех такой источник должен просто обладать максимальной энтропии или нулевой избыточностью, т.е. выдавать независимые равновероятные сообщения. В то же время в своей постановке задачи мы пожелали иметь возможность передавать с максимальной скоростью сообщения от произвольного источника с любыми статистическими свойствами, т.е. имеющего ненулевую избыточность. Т.о. функции кодера, осуществляющего согласование в статическом смысле сообщения источника со входного канала, является полным устранением избыточности сообщения. Кодер осуществляет кодирование сообщения, т.е. каждому дискретному сообщению по определенным правилам ставит в соответствие последовательность символов из алфавита объемом N. При этом по отношению ко входу канала, выдаваемые кодером символы сами являются дискретными элементарными сообщениями, статистические свойства которых должны отличаться от статистических свойств сообщений исходного источника. Возможность построения кодера, полностью устраняемого избыточность произвольного источника сообщений, и определяет возможность решения поставленной задачи без ошибочной передачи информации со скоростью, равной пропускной способности канала.
При полном ее решении оказывается справедливым равенство:
H’ (U) = Vc × H (U) = Vk × log M = C (2.1)
откуда имеем η = Vk / Vc = H(U) / log M (2.1а), где H(U) - энтропия источника передаваемых сообщений, Vk и Vc - средние количества символов соответственно сообщения и кода передаваемых в единицу времени. η = Vk / Vc - среднее количество символов кода приходящиеся на одно сообщение.
Степень приближения к точному выполнению равенств (2.1) и (2.1а) зависит от степени уменьшения избыточности источника сообщений.
Кодирование позволяющее устранять избыточность источников сообщений называется эффективным или статистическим. Коды, получаемые в результате такого кодирования, называются эффективными или статистическими. Рассмотрим основные идеи, которые могут быть положены в основу эффективного кодирования. Как отмечалось в пункте 1.4. избыточность дискретных источников обуславливается двумя причинами:
памятью источника;
неравномерностью сообщений.
Универсальным способом уменьшения избыточности обусловленной памятью источника является укрупнение элементарных сообщений. При этом кодирование осуществляется длинными блоками. Вероятностные связи между блоками меньше чем между отдельными элементами сообщений и чем длиннее блоки, тем меньше зависит между ними. Смысл укрупнения поясним на примере буквенного текста: если вероятностные связи между буквами в любом языке относительно сильны, то между словами они значительно меньше, еще меньше между фразами, еще меньше между абзацами. Поэтому, применяя кодирование слов, фраз, абзацев мы можем достаточно полно устранить избыточность обусловленную вероятностными связями. Однако при этом возрастает задержка передачи сообщений, так как сначала нужно дождаться формирования всего длинного блока сообщений и лишь затем его закодировать и передавать. Уменьшение избыточности обусловленной неравномерностью сообщений может быть достигнута применением неравномерных кодов. Основная идея построения таких кодов состоит в том, что наиболее вероятным сообщениям ставятся в соответствие наиболее короткие блоки кодовых символов (кодовые комбинации), а наименее вероятным более длинные. В силу неравномерности таких кодов и случайного характера сообщения U передача без потерь информации с постоянной скоростью следования кодовых символов uK может быть обеспечено лишь при наличии буферного накопителя с большой памятью, и, следовательно, при допустимости больших задержек.