Создатели электронного учебника
Информация о дисциплине
Программа дисциплины

2. СОГЛАСОВАНИЕ ДИСКРЕТНОГО ИСТОЧНИКА С ДИСКРЕТНЫМ КАНАЛОМ



2.1. Задача согласования дискретного источника с дискретным каналом без шума. Эффективное или статистическое кодирование

Предположим, что мы имеем дискретный канал вероятность возникновения ошибки, в котором близка к нулю (в идеале = 0). Такой канал называют идеальным каналом или каналом без шума. В соответствии с (1.25а) пропускная способность канала определяется . При наличии идеального канала естественно поставить вопрос о возможности передаче по нему без потерь информации от произвольного дискретного источника U характеризуемого производительностью H'(U) со скоростью равной пропускной способности канала. Схема построения такой системы передачи информации должна выглядеть, так как на рисунке 2.1. Необходимость включения устройства кодер, а так же декодера, выполняющего обратные ему операции. Состав этой системы обусловлен следующими обстоятельствами. Как говорилось в пункте 1.6. для того чтобы скорость передачи информации в канале была равна его пропускной способности, на входе канала должен действовать дискретный источник с определенными статистическими свойствами, максимизирующими величину I(Z,Z*). В частности, в интересующем нас здесь случае идеального канала без помех такой источник должен просто обладать максимальной энтропией или нулевой избыточностью, т.е. выдавать независимые равновероятные сообщения. В то же время своей постановки задачи мы пожелали иметь возможность передавать сообщения от произвольного источника с любыми статистическими свойствами, т.е. имеющего ненулевую избыточность. Таким образом функции кодера являются согласованием в статическом смысле сообщений источника со входом канала. Задача этого согласования в конечном итоге сводится к устранению избыточности сообщений. Кодер осуществляет кодирование сообщений, т.е. каждому дискретному сообщению по определенному правилу ставят в соответствие последовательность символов из алфавита объемом М. При этом по отношению к входу каналом выдаваемые кодером символы сами являются дискретными элементами сообщений, статические свойства которых должны отличаться от статических свойств сообщений исходного источника. Возможность построения кодера полностью устраняющего избыточность произвольного исходного источника сообщений и определяет возможность решения поставленной задачи без ошибочной передачи информации со скоростью, равной пропускной способности канала. При полном ее решении оказывается справедливым равенство
Hў(U) = uC ЧH(U) = uK Чlog M = C (2.1),
откуда имеем h = uK / uC = H(U) / log M (2.1а),
где H(U) - энтропия источника передаваемых сообщений, uK и u C - средние количества символов соответственно сообщения и кода передаваемых в единицу времени.
h = uK/ uC - среднее количество символов кода приходящиеся на одно сообщение.
Степень приближения к точному выполнению равенств (2.1) и (2.1а) зависит от степени уменьшения избыточности источника сообщений.
Кодирование позволяющее устранять избыточность источников сообщений называется эффективным или статистическим. Коды, получаемые в результате такого кодирования, называются эффективными или статистическими. Рассмотрим основные идеи, которые могут быть положены в основу эффективного кодирования. Как отмечалось в пункте 1.4. избыточность дискретных источников обуславливается двумя причинами:

1) памятью источника;

2) неравномерностью сообщений.

Универсальным способом уменьшения избыточности обусловленной памятью источника является укрупнение элементарных сообщений. При этом кодирование осуществляется длинными блоками. Вероятностные связи между блоками меньше чем между отдельными элементами сообщений и чем длиннее блоки, тем меньше зависит между ними. Смысл укрупнения поясним на примере буквенного текста: если вероятностные связи между буквами в любом языке относительно сильны, то между словами они значительно меньше, еще меньше между фразами, еще меньше между абзацами. Поэтому, применяя кодирование слов, фраз, абзацев мы можем достаточно полно устранить избыточность обусловленную вероятностными связями. Однако при этом возрастает задержка передачи сообщений, так как сначала нужно дождаться формирования всего длинного блока сообщений и лишь затем его закодировать и передавать. Уменьшение избыточности обусловленной неравномерностью сообщений может быть достигнута применением неравномерных кодов. Основная идея построения таких кодов состоит в том, что наиболее вероятным сообщениям ставятся в соответствие наиболее короткие блоки кодовых символов (кодовые комбинации), а наименее вероятным более длинные. В силу неравномерности таких кодов и случайного характера сообщения U передача без потерь информации с постоянной скоростью следования кодовых символов uK может быть обеспечено лишь при наличии буферного накопителя с большой памятью, и, следовательно, при допустимости больших задержек.

2.2. Теорема Шеннона для канала без шума

Предельные возможности статистического кодирования раскрывается в теореме Шеннона для канала без шума, которая является одним из основных положений теории передачи информации. Эта теорема может быть сформулирована следующим образом (обозначения те же, что и в пункте 2.1). Пусть источник сообщений имеет производительность H ў(U) = u CЧH(U), а канал имеет пропускную способность C = uK Чlog M. Тогда можно закодировать сообщения на выходе источника таким образом, чтобы получить среднее число кодовых символов приходящихся на элемент сообщения h = uK /uC = (H(U)/ log M)+e (2.2), где e - сколь угодно мало (прямая теорема).
Получить меньшее значение h невозможно (обратная теорема). Обратная часть теоремы утверждающая, что невозможно получить значение h = uK / uC < H(U)/ log M (2.3), может быть доказана если учесть, что неравенство (2.3) эквивалентно неравенству u CЧ H(U) > u KЧ log M, Hў (U) > C. Последнее неравенство не может быть выполнено т.к. рассматриваемое кодирование должно быть обратимым преобразованием (т.е. без потерь информации). Энтропия в секунду на входе канала или производительность кодера не может превышать пропускную способность канала (см. пункт 1.6).
Докажем прямую теорему двумя различными способами при этом источник сообщений будем полагать источником без памяти, имея в виду, что к нему со сколь угодно высокой степенью точности может быть сведен любой источник, если блоки элементов сообщения достаточно большой длинны К1 рассматривать, как элементарные сообщения Ui с объемом алфавита N u. Первый способ доказательства состоит в рассмотрении множества сообщений из К символов создаваемых источником. Каждую из таких последовательностей содержащую К элементарных сообщений Ui выбираемых из алфавита объемом Nu будем считать сообщением a =(Uk-1Uk-2 ?U1U0). Вероятность этих сообщений для источников без памяти P(a) = P(Uk-1)Ч P(Uk-2) ЧЧ Ч P(U0). При этом количество L отличных друг от друга сообщений a будет равно L=Nuk. При достаточно большой длине сообщения К все множество L возможных сообщений может быть разбито на 2 подмножества. Одно из них (назовем его высоко вероятным или типичным) содержит К1 наиболее вероятных сообщений, сумма вероятностей которых 1-d близка к единице, второе содержит остальные К2=L-K1 сообщений (мало вероятных или нетипичных), суммарная вероятность которых d близка к нулю (см. задача 1.10 пункт 2). Увеличивая К можно сделать d сколь угодно малым. Сказанное следует из закона теории вероятностей, согласно которому при достаточно большом числе испытаний количество каждого из возможных исходов близко к своему математическому ожиданию (закон больших чисел). В данном случае числом испытаний является число К элементов сообщений, исходом являются значения элементов ui и математическое ожидание количества исходов Ui равно K Ч P(Ui) (см. задачу 1.10 пункт 1). Поэтому достаточно длинное сообщение содержит близкое к KЧ P(0) число элементов 0, KЧ P(1) число элементов 1, ?, к KЧ P(Nu-1) число элементов Nu-1. Такие сообщения и составляют высоко вероятное подмножество. Вероятность того, что сообщения содержат другие числа элементов при К R ? ничтожно мала. Поскольку при отсутствии памяти у источника вероятность того или иного сочетания различных элементов сообщения зависит только от их количества, то все сообщения принадлежащие к высоко вероятному подмножеству т.е. содержащие примерно одно и тоже количество разных элементов и отличающихся только расположением этих элементов в последовательности, имеют одну и туже вероятность близкую к P(0)KЧ P(0) Ч P(1)KЧ P(1) ЧЧ Ч P(Nu-1)K Ч P(Nu-1)=P. Прологарифмируем полученное равенство
. В силу равновероятности число сообщений в высоко вероятном подмножестве К1>1/P, учитывая полученное выражение для логарифма P, К1 можно выразить через энтропию источника.
P=2-KЧ H(U), K1=1/P=2KЧ H(U) (2.4)
Поскольку L=NuK=2KЧ log(Nu)
(2.5),
где m - избыточность источника. Анализ выражения (2.5) показывает, что при любой не нулевой избыточности источника m число сообщений высоко вероятного подмножества составляет сколь угодно малую часть от всех возможных сообщений если длина сообщения К достаточно велика (сколь угодно малую вероятность имеет большая часть достаточно длинных сообщений). Это большинство и позволяет добиться близкого к минимуму числа h кодовых символов на элемент сообщения, применен следующий способ кодирования. Высоко вероятной группе сообщений поставим в однозначное соответствие различные короткие (их мало) кодовые комбинации равномерного кода длинны n1, оставив одну для использования в качестве разделительного сигнала. Для остальных К2=L-K1 >L сообщений, составляющих мало вероятное подмножество. Используем более длинные кодовые комбинации, содержащие n2 символов, начинающихся с упомянутой выше разделительной комбинации длинны n1 (для того, чтобы при декодировании можно разграничить принимаемые сообщения). Длины кодов n1 и n2 определим из условия (2.6), где S - число различных кодовых комбинаций равномерного кода, m - объем алфавита кодовых символов, n - число символов (длинна кодовой комбинации).
Полагая в (2.6) S=K1+1+l, n=n1, где l - число дополняющее К1+1 до можно записать , где . Увеличивая, число К можно сколь угодно уменьшить число q по сравнению с тем числом, с которым оно суммируется (при КR ? и К1R ?). Рассуждая, аналогично получим выражение для n2 с учетом разделительной комбинации.
,
, (про y и g можно сказать тоже самое, что про l и q).
Поскольку средняя длинна кодовой комбинации при этом равна , то среднее число кодовых символов приходящихся на один элемент сообщения равно , где . Где x становится сколь угодно малым при больших К. Это и доказывает прямую теорему.
В приведенном доказательстве мы полагали, что множество мало вероятных последовательностей кодируется длинными кодовыми комбинациями (длину n2+n1), делает возможным их однозначное декодирование. Однако в принципе всем сообщениям этой группы можно поставить в соответствие одну и туже разделительную комбинацию длиной n1 , и, определив по ней принадлежность принятого сообщения к мало вероятной группе отбрасывать их как ошибочные. Поскольку с ростом К вероятность нетипичных сообщений становится сколь угодно малой, сколь угодно малой будет вероятность ошибки. Данное замечание не меняет существа приведенного доказательства, но позволяет назвать рассмотренный в нем вариант кодирования равномерным кодированием.

2.3. Второй способ доказательства прямой теоремы Шеннона для канала без шума. Метод Фано. Оптимальные коды

Второй способ доказательства прямой теоремы предполагает другой способ эффективного кодирования, который заключается в следующем: по-прежнему рассматриваем сообщение ai представляющее собой последовательность элементарных сообщений uj длинной К. Расположим все сообщения a i в порядке убывания их вероятностей, пусть эти вероятности будут P1і P2 і ј і PL, где L=Nuk число сообщений ai. Пусть , т.е. Qs накопленная вероятность до Ps-1 включительно. Закодируем сначала все сообщения в двоичную систему. Двоичный код для сообщения as получиться путем записи дробной части разложения Qs, как двоичного числа (при S=1, Qs=0). Разложение производиться до ms позиции, где ms целое число, удовлетворяющее соотношению
(2.7).
Пример: Пусть мы имеем 4 сообщения
a1 a2 a3 a4
P(a1) = 1/2 P(a2) = 1/4 P(a3) = 1/8 P(a4) = 1/8
Q1 = 0 Q2 = 1/2 Q3 = 3/4 Q4 = 7/8
m1 = 1 m2 = 2 m3 = 3 m4 = 4
код 0 код 10 код 110 код 111
Коды показанные в последней строчке таблицы - это коды Шэннона дробной части.
Таким образом высоко вероятные сообщения представляются короткими кодами, а маловероятные длинными (это видно из (2.7)). Из этих неравенств вытекает следующая система неравенств (2.8). Оно показывает, что при выборе ms в соответствии с системой неравенств (2.7) вероятность сообщения с номером s Ps не меньше веса последнего младшего разряда двоичного разложения Qs. Вследствие этого код для Q s будет отличаться от всех последующих кодов одной и более из своих ms позиций, т.к. все остающиеся Qi, по крайней мере, на величину больше и поэтому их двоичное разложение отличается от кода для Qs, ходя бы в младшем разряде. Это говорит об однозначности предложенного способа кодирования. Среднее количество символов кода приходящихся на одно сообщение a можно определить, как (2.9), а среднее количество символов кода, приходящихся на одно элементарное сообщение Uk . Умножая все части системы неравенств (2.7) на и усредняя их по ансамблю сообщений ai приходим к неравенствам (2.10), но , где Нa - энтропия источника укрупненных сообщений a представляющих собой объединение К элементных независимых сообщений Ui (рассматриваем источник без памяти). Поэтому вследствие свойства адетивности энтропии Ha = KЧ H(U). В свою очередь . Таким образом неравенство (2.10) можно записать в виде (2.11). Неравенство (2.11) показывает, что с неограниченным ростом значение К, среднее количество h символов кода приходиться на одно элементарное сообщение источника, сколь угодно близко приближается к значению энтропии этого источника. Поскольку мы рассматривали двоичный код с объемом алфавита равного 2 и log2M=log22=1 выполнение неравенства (2.11) эквивалентно выполнению условия (2.2), это и доказывает прямую теорему. Полученный результат позволяет дать следующее толкование энтропии: энтропия источника есть наименьшее количество двоичных символов на сообщение, на выходе наилучшего кодера для этого источника при условии, что сообщения могут быть восстановлены по выходу кодера сколь угодно точно. Два рассмотренных варианта доказательства прямой теоремы иллюстрируют два возможных подхода к построению эффективных кодов, основанных на использовании равномерного и неравномерного кодирования. При неравномерном кодировании обеспечивается однозначное декодирование всех сообщений.
Второй способ доказательства мы рассмотрели в той же трактовке, в которой он был дан Шенноном, а именно на основе построения двоичного эффективного кода возможен более общий подход, базируется на построении неравномерного статистического кода с произвольным основанием М непосредственно приводящей к результату (2.2). Такой вариант доказательства дан в книге Колесник-Бондарев.
Предложенный Шенноном метод эффективного кодирования практически совпадает с методом предложенным другим американским ученым Фано по которому сообщение длинны К, записанное в порядке не возрастания вероятностей разделяется на две части так, чтобы суммарные вероятности сообщений в каждой части были по возможности равны. Сообщениям первой части приписывается в качестве первого символа 0, сообщениям второй части 1. Затем каждая из этих частей (если она содержит более одного сообщения) опять делится на две примерно равные части и в качестве второго символа для первой из них берется 0, а для второй 1. Этот процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному сообщению. Существуют и другие методы эффективного кодирования. Кодирование по методу Шеннона-Фано так же как и другими методами может применятся не только к последовательностям из К элементных сообщений, но и непосредственно к источникам не равновероятных элементарных сообщений. При этом уменьшается выигрыш в эффективности. В том случае, когда левая часть системы неравенств (2.11) обращается в равенство, имеем hmin=H(U) (2.12). Код, обладающий hmin называется оптимальным для того, чтобы сообщение источника можно было закодировать двоичным оптимальным кодом необходимо и достаточно, чтобы все вероятности источника сообщения представляли собой числа равные целой отрицательной степени числа 2, т.е. Pi= , где аi - целое. Действительно как видно из неравенства (2.8) в таком случае вероятности Ps при выбранном нами способе определении длины кодового слова ms определятся, как . При этом среднее число символов кода приходящихся на одно сообщение в соответствии с (2.9) равно . В свою очередь энтропия источника сообщений Нa равна . Таким образом получили, что hс = h с mina откуда после деления обеих частей последнего равенства на К можно придти к выражению (2.12). Рассуждая аналогичным образом можно показать, что и в случае кодирования сообщений источника неравномерным кодом с произвольным основанием М оптимальный код может быть получен при условии равенства вероятности всех сообщений целым отрицательным степеням числа М, т.е. при , где аi - целое и при этом . Если распределение вероятностей кодированного источника не обладает указанным свойством, эффективный код не будет оптимальным и соответствующая ему h > h min. Величина Y = hmin/ h (2.12а), характеризующая степень близости неравномерного статистического кода к оптимальному называется эффективностью кода. Таким образом нижний предел в условии теоремы, может быть, достигнут лишь при определенном распределении вероятности источника сообщений. Однако приближение к нему может быть сколь угодно близким при увеличении длинны К последовательности кодируемых сообщений. При этом рост эффективности системы передачи информации сопровождается увеличением задержки сообщений.
И так из рассмотренной теоремы вытекает, что для любого источника дискретных сообщений (т.е. характеризуется любым многомерным распределением вероятностей) скорость передачи информации по идеальному каналу может быть сделана сколь угодно близкой к пропускной способности канала при отсутствии потерь информации. При этом приближение тем больше, чем больше длина сообщения К, что указывает на возможность обмена задержки на скорость передачи информации.

2.4. Задача согласования дискретного источника с дискретным каналом с шумом.

Рассмотрим теперь ситуацию, когда в процессе передачи сигнал искажается шумом , т.е. некоторым случайным процессом. Предположим, что в соответствии с обозначениями (рисунок 2.1), что Z - ансамбль сигналов на входе дискретного канала, а Z* - ансамбль сигналов на его выходе. Наличие в канале шума приводит к тому, что по сигналу Z* нельзя однозначно определить сигнал Z. С точки зрения теории информации этот эффект характеризуется наличием потерь информации или ненадежностью канала H(Z/Z*)>0 и описывается соотношением I(Z,Z*)=H(Z)-H(Z/Z*), где I(Z,Z*) - информация переданная по каналу, H(Z)-энтропия или собственная информация ансамбля сигналов на входе канала. Переходя к информационным характеристикам, отнесенным к единице времени последнее выражение можно переписать в виде Iў(Z,Z*)=H ў(Z)-H(Z/Z* ) (2.13), где Iў (Z,Z*)-скорость передачи информации по каналу, Hў (Z)-производительность ансамбля на входе канала, H ў(Z/Z* )-потери информации в единицу времени. При этом пропускная способность канала С хоть и уменьшается по сравнению со случаем канала без шума см.(1.25б), но в общем случае принимает конечное значение (за исключением не принимаемого здесь во внимание экстремального случая обрыва канала). Положим далее, что имеется некоторый дискретный источник с производительностью Hў(U) < C сообщения которого необходимо передать по каналу. Для решения этой задачи по-прежнему воспользуемся системой передачи изображенной на рисунке 2.1. Функции выполняемые кодером и декодером в этом случае будут ясны из дальнейших рассуждений.
Поскольку Hў(U) < C возможна передача информации I(Z,Z*) по каналу со скоростью Iў (Z,Z*)=Hў (U) (2.14), т.к. по определению С- максимально возможная скорость передачи информации по каналу. Приравнивая правые части неравенств (2.13-14), приходим к соотношению Hў (Z)-Hў(Z/Z*)=H ў(U). Из которого следует, что Hў(Z)=H ў(U)+Hў (Z/Z*)> Hў(U). Последнее неравенство означает, что производительность ансамбля сигналов Z (назовем его кодом) на входе канала должна быть выше производительности источника сообщений U, и следовательно Z , кроме информации об U должен содержать дополнительную собственную информацию. При этом если бы удалось ввести дополнительную информацию таким образом, чтобы при прохождении сигнала Z по каналу с шумом вследствие ненадежности канала терялась бы именно она, а не полезная информация о сообщении U, то оказалось бы возможным обеспечить безошибочную передачу сообщений U по каналу с шумом с конечной скоростью H ў(U)< C. Таким образом задачей кодера в данной ситуации является согласование источника с каналом, заключается во внесении в сообщение источника избыточности , обладающей описанной выше свойством. Однако не тривиальным является вопрос, а возможно ли в принципе построение такого кодера ? Идея борьбы с мешающим влиянием шума за счет введения избыточности, при кодировании дискретных сообщений, существовала и до появления Теории Информации и трактовалась следующим образом: предполагалось сообщение двоичного источника U1 =0 и U2 =1 передавать по симметричному двоичному каналу (см. п1.6) с вероятностями ошибок Р< 0,5 двумя кодовыми комбинациями, содержащими соответственно n единиц или n нулей. ; . Если в месте приема регистрировать 1 или 0 по большинству принятых знаков в комбинации т.е. принимать так называемое мажоритарное декодирование , то ясно, что ошибка произойдет при условии, если в кодовой комбинации не верно будет принято n/2 или более символов. Согласно закону больших чисел вероятность уклонения числа ошибок m в кодовой комбинации длины n от их математического ожидания nЧp (см. задачу 1.11) стремится к 0 при n® ?, т.е.
e ® 0.
Поскольку nЧp < 0,5n при n®? вход обеспечит безошибочный прием. Однако передачу одного символа необходимо будет осуществлять бесконечно долго, т.е. скорость передачи информации по каналу будет стремится к 0. Таким образом на основании приведенных ранее рассуждений полагалось, что без ошибочная передача информации в канале с шумом возможна лишь в пределе при нулевой скорости передачи. Поэтому положительные решения сформулированного выше вопроса позволяют существенно изменить представление о потенциальных возможностях систем передачи дискретной информации и имеет принципиальное значение в развитии теории и практики связи. Ответ на данный вопрос содержится в теореме Шеннона для дискретного канала с шумом.

2.5. Теорема Шеннона для дискретного канала с шумом

Данная теорема является фундаментальным положением Теории Информации и называется так же основной теоремой кодирования Шеннона. Она может быть сформулирована следующим образом: если производительность источника сообщений Hў (U) меньше пропускной способности канала С т.е. Hў(U)< C то существует такая система кодирования которая обеспечивает возможность передачи сообщений источника со сколь угодно малой вероятностью ошибки (или со сколь угодно малой ненадежностью).
Если Hў(U) > C, то можно закодировать сообщение таким образом, что ненадежность в единицу времени будет меньше чем Hў(U)-C+ e, где e ®0 (прямая теорема).
Не существует способа кодирования обеспечивающего ненадежность в единицу времени меньшую, чем Hў(U)-C (обратная теорема).
В такой формулировке эта теорема была дана самим Шенноном. В литературе часто вторая часть прямой теоремы и обратная теорема объединяются в виде обратной теоремы сформулированной так: если Hў(U) > C, то такого способа кодирования не существует. Для доказательства первой части прямой теоремы воспользуемся результатами рассмотрения (см. п.2.2) множества длинных последовательностей элементарных дискретных сообщений источника, распадающегося как показано в п.2.2 на подмножества высоко вероятных или типичных и мало вероятных или нетипичных последовательностей. Пусть при некотором ансамбле входных сигналов дискретного канала Z обеспечивается пропускная способность канала C=Iў(Z,Z*)=H(Z)-H ў(Z/Z*) (2.16).
В соответствии с равенством (2.4) число типичных последовательностей входных сигналов канала достаточно большой длительности Т (содержащих большое число символов К) равно K1(Z)=2KЧ H(Z) (2.17)
Поскольку Hў(Z)=u kЧ H(Z), где uk - количество символов кода Z переданных в единицу времени Т=К/uk, то , поэтому равенство (2.17) можно записать в виде (2.18).
Передаче подлежат сообщения выдаваемые дискретным источником U с производительностью меньше Hў(U)< C= Hў(Z)- Hў (Z/Z*), откуда следует Hў(U)+Hў (Z/Z*)< Hў(Z) (2.19). Поскольку Hў(Z/Z*) >0 из (2.19) вытекает, что Hў(U)< Hў(Z) (2.20). При этом число типичных последовательностей источника достаточно большой длительности Т, аналогично (2.18) можно определить так (2.21). В следствии условия (2.20) число типичных последовательностей канала значительно превосходит типичное число последовательностей источника
(2.22).
Осуществим кодирование типичных последовательностей источника. В процессе кодирования каждой типичной последовательности источника поставим в соответствие одну из типичных последовательностей канальных сигналов. Нетипичные последовательности сообщений длительности Т (если источник все же выдаст одну из них) передавать не будет, соглашаясь с тем, что каждая такая последовательность будет принята ошибочно. Выполним указанное кодирование всеми возможными способами и усредним вероятность ошибок по всему этому большому (в следствии (2.22)) классу возможных систем кодирования. Это равносильно вычислению вероятности ошибок при случайном связывании типичных последовательностей источника сообщений и канальных сигналов. Очевидно, что число возможных кодов М равно числу размещений из K1(Z) числу элементов по K1(U) . Для того, чтобы оценить среднюю вероятность ошибки отметим следующее. Пройдя через канал каждая из типичных последовательностей канала может в следствии воздействия помех преобразоваться в такое количество типичных последовательностей выхода (образованием маловероятных нетипичных последовательностей выхода будем пренебрегать). В свою очередь в следствии ненадежности канала H(Z/Z*) каждая типичная выходная последовательность может быть обусловлена одной из (2.23) типичных входных канальных последовательностей. Данная ситуация иллюстрируется на рисунке 2.2. Предположим, что наблюдается некоторая входная последовательность Z* которая могла быть образована K1(Z/Z*) типичными входными последовательностями канала. Если среди этой совокупности входных последовательностей канала содержится только одна из числа использованных при кодированных источника сообщений, то очевидно она и передавалась, и следовательно соответствующая ей последовательность сообщений может быть принята верно. Ошибочный прием типичной последовательности передаваемых сообщений неизбежен лишь тогда, когда среди количества K1(Z/Z*) последовательностей сигналов имеются две или более использованные при кодировании. Средняя вероятность правильного приема типичной последовательности равна вероятности того, что среди количества K1(Z/Z*) входных последовательностей канала K1(Z/Z*)-1 не использовано при кодировании, а одна использована. Вероятность того, что какая-то одна типичная последовательность канальных сигналов использована при кодировании, в силу равно вероятности выбора равна (2.24), а вероятность того, что она не использована, определяется как , поскольку вероятность того, что один из канальных сигналов выбран, при кодировании равна единице. Следовательно средняя вероятность того, что при кодировании не использована K1(Z/Z*)-1 входных последовательностей . Полагая K1(Z/Z*) > > 1 (что справедливо при большом Т) можно записать (2.25). Разлагая (2.25) в бином Ньютона и с учетом условия (2.24), ограничиваясь двумя первыми членами разложения, можно записать (2.26). Средняя вероятность ошибочного приема типичной последовательности при достаточно больших Т или с учетом (2.21, 2.17, 2.23, 2.16). (2.27). Результирующая средней вероятности ошибки с учетом возможности появления и нетипичных последовательностей с суммарной вероятностью d она равна (2.28). Поскольку по условию теоремы (2.15) C-Hў(U) > 0, то как следует из (2.27 и 2.28) с ростом Т , так как при этом стремятся к нулю как (см.2.27) так и d (см. п.2.2). Следовательно, при любом заданном e > 0 можно выбрать столь большое Т, что будем иметь , но если среднее некоторого множества чисел не больше чем e, то в этом множестве должно существовать по крайней мере одно число меньше e. Поэтому среди всех возможных М кодов обеспечивающих среднее значение обязательно существует хотя бы один у которого вероятность ошибки не превышает . Таким образом первая часть теоремы Шеннона доказана.
Вторую часть прямой теоремы легко доказать исходя из того, что можно просто передавать С бит в секунду от источника сообщений совсем пренебрегая остатком создаваемой информации. В приемнике это не учитываемая часть создаст ненадежность в секунду времени Hў(U)-C, а передаваемая часть в соответствии с доказанным выше добавит e.
Доказательство обратной теоремы произведем методом от противного. Рассмотрим сначала ее формулировки предложенные Шенноном. Предположим, что производительность источника сообщений равна Hў(U)=C+а, где а> 0 . По условию теоремы минимально достижимое в этом случае значение ненадежности . Мы же будем считать, что существует способ кодирования, обеспечивающий значение , где e > 0. Однако при этом оказывается реализованной скорость передачи информации , это противоречит определению пропускной способности как максимальной скорости передачи информации по каналу, что и доказывает теорему.
Рассмотрим вторую формулировку обратной теоремы. Положим, что источник сообщений имеет производительность Hў (U)=C+e > C, где e > 0. И с помощью некоторого способа кодирования достигается ненадежность равная Hў (U/U*)=e /2. Опять же это эквивалентно реализации скорости передачи информации превышающей пропускную способность, что невозможно. Это противоречие доказывает теорему.
Физический смысл эффекта повышения вероятности при увеличении длительности кодируемых сообщений вытекающего из доказательства прямой теоремы заключается в том, что с ростом Т увеличивается степень усреднения шума действующего в канале и, следовательно, уменьшается степень его мешающего воздействия. Кодирование сообщений длительности Т способом предполагаемым при доказательстве теоремы Шеннона может начаться лишь тогда, когда сообщение целиком поступило на кодирующее устройство. Декодирование же может начаться, когда вся принятая последовательность поступила на декодирующее устройство. Поэтому задержка сообщений во времени между пунктами связи tзад=2T+t0, где t0 - время затрачиваемое на кодирование. Декодирование и прохождение по каналу. При большом Т можно принять, что tзад=2Т. Из (2.27) следует важный результат: верность связи тем выше (меньше вероятность ошибки), чем длиннее блок кодированной последовательности (т.е. тем больше разность С-Hў(U) определяющей запас пропускной способности канала). Итак, следует принципиальная возможность обмена между вероятностью, задержкой и скоростью передачи информации. На практике сложность кодирования и декодирования существенно возрастают с ростом Т поэтому в современных условиях чаще предпочитают иметь умеренное значение Т и добиваться увеличения вероятности за счет менее полного использования пропускной способности канала.

2.6. Методика построения помехоустойчивых кодов. Информационный предел избыточности

Кодирование с помощью которого можно устранять ошибки обусловленные наличием шума в канале называется помехоустойчивым. Коды способные исправлять и обнаруживать ошибки называется помехоустойчивым кодом. К сожалению основная теорема кодирования Шеннона не конструктивна, она не указывает способ построения конкретного оптимального помехоустойчивого кода, обеспечивающего предельное согласование сигнала с каналом, существование которого доказывает. Вместе с тем обосновав принципиальную возможность построения помехоустойчивых кодов, обеспечивающих идеальную передачу. Теория Шеннона мобилизовала усилия ученых на разработку конкретных кодов. В результате в настоящее время теория помехоустойчивого кодирования превратилась в самостоятельную науку в развитии которой достигнуты большие успехи.
Рассмотрим основополагающие принципы заложенные в основу построения помехоустойчивых кодов. Как следует из доказательства основной теоремы Шеннона неприменимым свойством помехоустойчивых кодов является наличие избыточности. При этом необходима не просто любая избыточность, а специфическая, определяемая свойствами канала и правилом построения кода. И позволяющая с минимальными затратами повысить вероятность передачи. В ситуации когда источник сообщений обладает собственной существенной избыточностью, которая в принципе тоже в определенной степени повышает достоверность передачи информации, но не так эффектно как это возможно. Поступают следующим образом: сначала с помощью эффективного кодирования до минимума уменьшают избыточность источника сообщений, а затем в процессе помехоустойчивого кодирования вносят в передаваемый сигнал избыточность, позволяющую простыми средствами поднять верность. Таким образом эффективное кодирование может сочетаться с помехоустойчивым.
Помехоустойчивые коды можно подразделить на два больших класса блочные и непрерывные. В случае блочных кодов, при кодировании, каждому дискретному сообщению ставится в соответствие отдельный блок кодовых символов называемого кодовой комбинацией. Непрерывные коды образуют последовательность символов неразделяемых на кодовые комбинации.
Рассмотрим принцип построения помехоустойчивых блочных кодов. Избыточность обуславливающая корректирующие свойства равномерного блочного кода обычно вводится за счет выполнения неравенства mn >M (2.29), где m-основание кода т.е. объем алфавита используемых кодовых символов, n-длина или количество разрядов кодовой комбинации, М-количество сообщений подлежащих кодированию. Выполнение этого неравенства означает, что для передачи знаков сообщения используют лишь часть М возможных кодовых комбинаций. Используемые кодовые комбинации называют разрешенными. Неиспользуемые mn -M комбинации являются запрещенными. На вход канала подаются только разрешенные комбинации. Если вследствие помех один или несколько символов приняты ошибочно, то на выходе канала появляется запрещенная комбинация, что и говорит о наличии ошибки. Для того, чтобы обеспечить выполнение (2.29) необходимо выбирать n > K , где К-минимальное целое, удовлетворяющее неравенству mKM (2.30). Число К обычно называют количеством информационных разрядов кодовой комбинации, поскольку именно столько разрядов должна содержать комбинация кода с основанием m, чтобы число разных кодовых комбинаций было не меньше числа сообщений М подлежащих передаче. R=n-K разрядов кодовой комбинации необходимых для передачи полезной информации называются проверочными. Количество их и определяет избыточность помехоустойчивого кода. При использовании помехоустойчивого кода возможно декодирование с обнаружением и исправлением ошибок. В первом случае на основе анализа принятой комбинации выясняется, является ли она разрешенной или запрещенной. После этого запрещенная комбинация либо отбрасывается, либо уточняется путем посылки запроса на повторение переданной информации. Во втором случае при приеме запрещенной комбинации определенным способом выявляются и исправляются содержащиеся в ней ошибки. Максимальные числа ошибок в кодовой комбинации q и S которые могут быть обнаружены (q) или исправлены (S) с помощью данного кода называются соответственно обнаруживающей или исправляющей способностью кода. В значении q и S определяются величиной dmin минимальным кодовым расстоянием между ближайшими разрешенными комбинациями. Под кодовым расстоянием понимают количество неодинаковых разрядов в кодовых комбинациях. Величина dmin в помехоустойчивом коде зависит от соотношения n и К т.е. от числа r проверочных разрядов кода.
Рассмотрим информационный (т.е. базирующий на идеях Теории Информации) подход позволяющий оценить необходимую минимальную избыточность, выраженную в количестве проверочных разрядов rmin блочного помехоустойчивого кода длиной n с заданной исправляющей способностью S. Пусть имеется код с основанием m и с исправляющей способностью S. И используется декодирование с исправлением ошибок. На приеме при использовании такого кода возможно две ситуации: правильный прием сообщения и неправильный. Осуществление с вероятностью PH. Неправильный прием может произойти в том случае, когда из-за превышения числом ошибок пришедшей из канала кодовой комбинации значение S она может превратиться в одну из других разрешенных кодовых комбинаций. В свою очередь правильный прием осуществляется либо в том случае, когда в принимаемой комбинации отсутствуют ошибки (обозначим вероятность такого сообщения Р0), либо Nправ в случаях когда в принятой комбинации присутствуют ошибки которые могут быть исправлены рассмотренным кодом. Вероятности таких случаев обозначим через Pj j=1 ё Nправ. Для решения поставленной задачи определим минимальное количество информации, которой может быть описана совокупность событий, включающая появление одной из конкретных ошибок и отсутствие ошибок или появление некорректных ошибок. Зная эту величину и максимальное количество информации которое может содержать один проверочный символ кода можно определить минимальное число проверочных символов.
Количество информации необходимо для описания указанных событий (2.31) (в случае отсутствия ошибки учтем включением нуля в предел суммирования). Максимальное количество информации которое может содержать символ кода с основанием m в соответствии с (1.6) равно log2m. Следовательно число проверочных разрядов в комбинации кода не может быть меньше, чем (2.32). Определенную таким образом величину rmin называют информационным пределом избыточности. Найдем значение rmin для двоичного канала с независимыми ошибками. В таком канале появление предыдущей ошибки не влечет за собой появление последующей. В этой ситуации число R(i) ошибок кратности i в кодовой комбинации длиной n равно числу сочетаний .
(2.33).
Поскольку ошибки независимы вероятность P(i) возникновения в кодовой комбинации ошибки кратности i равна P(i)=PiЧ(1-P)n-i (2.34), где Р-вероятность ошибки в канале. Учитывая, что в данном случае Nпр=S выражение (2.31) можно записать в виде . Вторым слагаемым можно пренебречь поскольку, описываемая им функция не используется в процессе исправления ошибок. Поэтому с учетом (2.23 и 2.24) имеем (2.35). Рассмотрим частный случай когда возникновение конкретной ошибки любой кратности и отсутствие ошибок имеют равную вероятность, т.е. PiЧ(1-P)n-i=P1 при любом i. Величину Р1 определим из условия нормировки (2.36), отражающего тот факт, что вероятность появления ошибки какой-либо кратности, включения и нулевую равна единице. Из (2.36) имеем следовательно (2.37). Поскольку под двоичной, то есть m=2 c учетом (2.37 и 2.38) имеем . Найденное таким образом значение rmin совпадает с оценками полученными другим методами в частности с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Полученные при этом результаты так же хорошо согласовывается с выводами полученными другими методами. Найденное таким образом значение rmin совпадает с оценками, полученными другими методами, в частности, с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Получаемые при этом результаты также хорошо согласуются с выводами, полученными другими методами.


Создатели электронного учебника
Информация о дисциплине
Программа дисциплины