63567 (695380), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Энтропия источника в этом случае, естественно, будет меньшей и составит _{= 1.781.}

Среднее число символов на одно сообщение при использовании того же равномерного трехразрядного кода

Избыточность кода в этом случае будет

,

или довольно значительной величиной (в среднем 4 символа из 10 не несут никакой информации).

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

Такое кодирование называется статистическим.

Неравномерный код при статистическом кодировании выбирают так, чтобы более вероятные буквы передавались с помощью более коротких комбинаций кода, менее вероятные - с помощью более длинных. В результате уменьшается средняя длина кодовой группы в сравнении со случаем равномерного кодирования.

Один из способов такого кодирования предложен Хаффменом. Построение кодового дерева неравномерного кода Хаффмена для передачи одного из восьми сообщений _i с различными вероятностями иллюстрируется табл. 3.

Таблица 3

Среднее число символов для такого кода составит

а избыточность кода

т.е. на порядок меньше, чем при равномерном кодировании.

Другим простейшим способом статистического кодирования является кодирование по методу Шеннона-Фано. Кодирование в соответствии с этим алгоритмом производится так:

• сначала все буквы из алфавита сообщения записывают в порядке убывания их вероятностей;

• затем всю совокупность букв разбивают на две примерно равные по сумме вероятностей группы; одной из них (в группе может быть любое число символов, в том числе – один) присваивают символ “1”, другой - “0”;

• каждую из этих групп снова разбивают (если это возможно) на две части и каждой из частей присваивают “1” и “0” и т.д.

Процедура кодирования по методу Шеннона-Фано иллюстрируется табл. 4.

Таблица 4

Буква	Р(i )	I	II	III	IV	V	Kод	ni Pi
А	0.6	1					1	0.6
Б	0.2	0	1	1			011	0.6
В	0.1			0			010	0.3
Г	0.04		0	1			001	0.12
Д	0.025			0	1		0001	0.1
Е	0.015				0		00001	0.075
Ж	0.01					1	000001	0.06
З	0.01					0	000000	0.06

Для полученного таким образом кода среднее число двоичных символов, приходящихся на одну букву, равно

,

а избыточность кода составит

то есть также существенно меньшую величину, нежели для равномерного кода.

Обратим внимание на тот факт, что как для кода Хаффмена, так и для кода Шеннона-Фано среднее количество двоичных символов, приходящееся на символ источника, приближается к энтропии источника, но не равно ей. Данный результат представляет собой следствие теоремы кодирования без шума для источника (первой теоремы Шеннона), которая утверждает:

Любой источник можно закодировать двоичной последовательностью при среднем количестве двоичных символов на символ источника _i, сколь угодно близком к энтропии, и невозможно добиться средней длины кода, меньшей, чем энтропия H(λ).

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

ЛИТЕРАТУРА

1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.

2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для вузов. / В.И. Нефедов, В.И. Халкин, Е.В. Федоров и др. – М.: высшая школа, 2001 г. – 383с.

3. Цапенко М.П. измерительные информационные системы.– М.: Энергоатом издат, 2005. - 440с.

4. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.

5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.

Характеристики

Список файлов реферата