Тема: Эффективное кодирование.

План лекции.

1. Эффективное кодирование равновероятных символов сообщений.

2. Эффективное кодирование неравновероятных символов сообщений.

Эффективное кодирование равновероятных символов сообщений

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

В случае, если все символы алфавита кодируемого сообщения независимы и их появление равновероятно, построение оптимального эффективного кода не представляет трудностей. Действительно, пусть Н(х)– энтропия исходного сообщения. Будем считать, что символы сообщения (х_i)равновероятны и объем алфавита исходного источника сообщений равен m. Следовательно, вероятность появления любого i-го символа данного сообщения (P(х_i)) будет одинакова, т.е.

, i = 1,.., m ,

а энтропия сообщения равна (Н(х)):

Если для кодирования используется числовой код по основанию k (объем алфавита элементов кодовых символов равен k), то энтропия элементов кодовых символов (Н₁), при условии, что элементы символов кода появляются равновероятно и взаимнонезависимо, определится из соотношения:

H₁ = log₂ k .

Тогда длина эффективного равномерного кода, т.е. число элементов в кодовом символе (l_эфф.), может быть найдена из соотношения:

, (10.1)

где m = kⁿ.

Эффективное кодирование неравновероятных символов сообщений

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

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

, (10.2)

где P(x_i)– вероятность появления i-го символа алфавита исходного кодируемого сообщения;

m – объем алфавита;

W_i – стоимость передачи i-го символа алфавита, которая пропорциональна длине кодового слова.

Эффективный код должен минимизировать функцию Q. Если передача всех элементов символов кода имеет одинаковую стоимость, то стоимость кодового символа будет пропорциональна длине соответствующего кодового символа. Следовательно, в общем случае (при неравновероятных символах исходного сообщения) код должен быть неравномерным, поэтому построение эффективного кода должно основываться на следующих принципах:

1. Длина кодового символа (n_i)должна быть обратно пропорциональна вероятности появления соответствующего символа исходного кодируемого сообщения (x_i);

2. Начало более длинного кодового символа не должно совпадать с началом более короткого (для возможности разделения кодовых символов без применения разделительных знаков);

3. В длинной последовательности элементы символов кода должны быть независимы и равновероятны.

Теоретическое обоснование возможности эффективного кодирования передаваемых по каналу сообщений обеспечивает теорема, доказанная К. Шенноном и которая носит название первая теорема Шеннона или основная теорема Шеннона о кодировании для каналов без помех. Эта теорема гласит, что если источник сообщений имеет энтропию Н [бит/символ], а канал обладает пропускной способностью С [бит/сек] (пропускная способность характеризует максимально возможное значение скорости передачи информации), то всегда можно найти способ кодирования, который обеспечит передачу символов сообщения по каналу со средней скоростью

, [символ/сек],

где ε – сколь угодно малая величина.

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

[символ/сек].

Эта теорема часто приводится в иной формулировке: сообщения источника сообщений с энтропией Н всегда можно закодировать последовательностями элементов кодовых символов с объемом алфавита k так, что среднее число элементов символов кода на один символ кодируемого сообщения (l _ср. ) будет сколь угодно близко к величине , но не менее ее.

Эта теорема показывает возможность эффективного наилучшего кодирования, при котором обеспечивается равновероятное и независимое поступление элементов символов кода, а следовательно, и максимальное количество переносимой каждым из них информации, равное log₂k (бит/элемент). К сожалению, теорема не указывает конкретного способа эффективного кодирования, она лишь говорит о том, что при выборе каждого элемента кодового символа необходимо, чтобы он нес максимальное количество информации, а, следовательно, все элементы символов кода должны появляться с равными вероятностями и взаимнонезависимо.

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

Лекция 6.

Дата добавления: 2018-05-12; просмотров: 728; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!