Скорость передачи информации по дискретному каналу без помех

•Скорость передачи информации – это количество информации, передаваемое по каналу в единицу времени.

•Если тактовый генератор канала выдает V элементарных импульсов в единицу времени, а средняя длина кода одного символа первичного алфавита составляет K сигналов вторичного (бинарного) алфавита, то, очевидно, отношение V/K будет выражать число символов первичного алфавита, транслируемых по каналу за единицу времени.

•Если с каждым из символов первичного алфавита связано среднее количество информации Н (энтропия источника сообщений), то можно найти общее количество информации, передаваемой по каналу связи за единицу времени – эта величина называется скоростью передачи (будем обозначать ее J).

	•	H	, где Н – энтропия источника информации,
	J V H		определяемая известной
		0 K
	K		формулой (3M.8):
			H pi log2 pi
			i 1

•Размерностью скорости J, как и пропускной способности C, является бит/с. Каково соотношение этих характеристик? Выразим V из (4.2) и получим:

•J V H C H (4.4)

K K log2 m

•Согласно теории информации Шеннона при любом способе

кодирования длина кода подчинена соотношению K	H	.
	log2 m

•хотя может быть сколь угодно близкой к этому значению.

•Следовательно, всегда J ≤ C, т.е. скорость передачи информации по каналу связи не может превысить его пропускной способности.

•Пример 4.1. Первичный алфавит состоит из трех знаков с вероятностями

p1 = 0,2; p2 = 0,7; p3 = 0,1. Для передачи по каналу без помех используются равномерный двоичный код. Частота тактового генератора 500 Гц. Какова пропускная способность канала и скорость передачи?

•Решение. Поскольку код двоичный, m = 2; C =V = 500 бит/с.

•Энтропия источника: H = – 0,2·log20,2 – 0,7·log20,7 – 0,1·log20,1 = 1,16 бит

•Поскольку код равномерный K ≥ H/log22 = 2 (т.е. для кодирования каждого знака первичного алфавита используется 2 элементарных разряда).

•Следовательно, в силу (4.4), получаем:

	J	C H	500 1.16	290
		K log2 m
			2	(бит в секунду).

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

•Если приблизить длину кода К к значению реальной энтропии, можно увеличить скорость передачи информации.

Эффективное статистическое кодирование сообщений. Теорема Шеннона для каналов без помех

•Для дискретных каналов без помех К. Шенноном была доказана следующая теорема (первая теорема Шеннона):

•Если производительность источника R = C – ε, где ε – сколь угодно малая величина, то всегда существует способ кодирования, позволяющий передавать по каналу все сообщения источника. Передачу всех сообщений при R > C осуществить невозможно.

•Как бы ни была велика избыточность источника, все его сообщения могут быть переданы по каналу, если R < C.

•Для рационального использования пропускной способности канала необходимо применять соответствующие способы кодирования.

•Эффективным статистическим кодированием называется кодирование, при котором статистические характеристики источника информации согласуются с характеристиками канала связи.

•При эффективном кодировании фактическая скорость передачи информации приближается к пропускной способности канала.

•Рассмотрим основные принципы оптимального кодирования для двоичного канала без помех.

•Пусть источник оперирует алфавитом символов ai, i=1…M. Вероятность каждого символа P(ai). Кодер преобразует символ ai в двоичную последовательность длиной ni. Средняя длительность кодовой комбинации одного символа первичного алфавита вычисляется так:

•	, где τ0 – длительность одного элемента кода.
	M
•	0 niP(ai )	M	. (4.5)
	При этом средняя длина кода определяется как
	i 1
•	Соответственно тогда τ = K∙τ0.	K ni P(ai )
		i 1

•Величина V/K определена ранее как среднее число знаков первичного алфавита, транслируемых по каналу в единицу времени. Соответственно, величина K/V – это средняя длительность трансляции одного знака первичного алфавита, т.е. τ = K/V.

• Значит, в соответствии с формулой (4.4) скорость передачи в канале

JH

.

•Подставляя выражения для средней длительности и энтропии, получим:

	M
J	P(ai )logP(ai )
	i 1
	M
	0 ni P(ai ) .		(4.6)

i 1

•В выражении (4.6) значение числителя определяется исключительно

статистическими свойствами источника, а τ0 – свойствами канала связи.

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

• Для двоичного канала:	С	1
		0 .

•Чтобы J равнялось С надо чтобы ni = - log2P(ai).

•Применение неравномерного кодирования (например, кода

Шеннона-Фано) может приблизить длину кода ni к величине - log2P(ai).

•Алгоритм Шеннона — Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано (англ. Robert Fano). Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

•Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

•Основные этапы

1.Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.

2.Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу.

3.В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».

4.полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

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

•На шаге деления алфавита существует неоднозначность, так как разность суммарных

вероятностей p0 – p1 может быть одинакова для двух вариантов разделения (учитывая, что все символы первичного алфавита имеют вероятность больше нуля).

•Алгоритм вычисления кодов Шеннона — Фано

•Код Шеннона — Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0.

Пример кодового дерева

Исходные символы:

A (частота встречаемости 50) B (частота встречаемости 39) C (частота встречаемости 18) D (частота встречаемости 49) E (частота встречаемости 35) F (частота встречаемости 24)

Полученный код: A — 11, B — 101, C — 100, D — 00, E — 011, F — 010. Кодирование Шеннона — Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса.