Файл: прикладная теория информации.pdf

47 6. Из каких следующих значений длин кодовых слов можно построить од- нозначно декодируемый код:
– ????
1
=2, ????
2
= 2, ????
3
=2, ????
4
= 3, ????
5
= 3;
– ????
1
=1, ????
2
= 2, ????
3
=3, ????
4
= 3, ????
5
= 8;
– ????
1
=1, ????
2
= 2, ????
3
=3, ????
4
= 4, ????
5
= 4.

48
4. ТЕОРЕМА ШЕННОНА О КОДИРОВАНИИ ДЛЯ КАНАЛА БЕЗ ШУМА
(первая теорема Шеннона)
Если в канале передачи информации вероятность
???? → 0 (ошибки маловеро- ятны), основное требование к информационной системе – это представление символов источника в максимально компактной форме. Первая теорема Шен- нона определяет минимально достижимую длину кодового слова на символ ис- точника. Учитывая статистические свойства источника, можно более эффек- тивно передавать (обрабатывать) информацию. Если высоковероятным симво- лам поставить в соответствие более короткие длины кодовых слов, а маловеро- ятным символам – слова большей длины, в этом случае достигается увеличение скорости передачи информации. Количество передаваемой информации за еди- ницу времени также увеличится.
4.1. Энтропия блокового источника
Пусть имеется источник блоковых символов ????
????
. Эти блоки имеют длину
????. Первая теорема Шеннона утверждает, что если ???? → ∞, можно произвести ко- дирование блоковых символов источника ????
????
кодом, у которого средняя длина кодового слова будет приближаться к энтропии ???? источника ????.
Если рассматривать блоки символов длиной ???? как новые независимые со- бытия с энтропией ????
′
= ???????? (см. п. 2.7.1, свойство 4 энтропии блокового источ- ника), то в соответствии с выражением (3.5) можно записать
????
′
≤ ???? ≤ ????
′
+ 1, (4.1) где ???? – средняя длина слова источника ????
????
Это же значение ???? определяет среднюю длину кодового слова последова- тельности ???? символов источника ????.
Перепишем (4.1) как
???????? ≤ ???? ≤ ???????? + 1, где ???? – энтропия источника одиночных символов.
Полученное выражение преобразуем к виду
???? ≤
????
????
≤ ???? +
1
????
, (4.2) где
????
????
– средняя длина слова на один символ источника
???? (на одно событие).
Таким образом, расширяя источник одиночных символов, т. е. увеличивая значение ???? – длину блока, при ???? → ∞ можно закодировать символы блокового

49 источника кодовыми словами со средней длиной на символ источника ????, при- ближающейся к значению энтропии источника ????.
4.2. Первая теорема Шеннона
Кодируя блоковые последовательности источника без памяти ???? =
= {????
1
, ????
2
, … , ????
????
} с энтропией ????, можно построить q-ичный префиксный код, в котором средняя длина кодового слова удовлетворяет выражению lim
????→∞
????
????
????
= ????, где ????
????
– средняя длина кодовых слов префиксного кода.
Замечание. Составляющая
????
????
????
= ???? +
1
????
выражения (4.2) определяет макси- мальное значение средней длины кодового слова префиксного кода.
Вывод. Эффективное кодирование информации требует использования ис- точника с n-кратным расширением источника ????.
Пример 4 .1 . Вычислим энтропию двоичного источника с символами ал- фавита ???? = {????, ????} c вероятностью ????
1
=
7 8
, ????
2
=
1 8
Решение. Применяя формулу Шеннона (2.17), получаем
???? = −????
1
log
2
????
1
− ????
2
log
2
????
2
= −
7 8
log
2 7
8
−
1 8
log
2 1
8
=
=
7 8
∙ 0,1926 +
1 8
∙ 3 = 0,54 бит/символ.
Источник дает менее 1 бита информации на символ. Символы источника кодируются словами ???? → 0, ???? → 1. Длина кодовых слов равна ????
1
= ????
2
= 1.
Cредняя длина слова кода равна
???? = ∑ ????
????
2
????=1
????
????
=
7 8
∙ 1 +
1 8
∙ 1 = 1.
Пример 4.2 . Для увеличения количества передаваемой информации, ис- пользуем расширение источника одиночных символов примера 4.1. Построим блоковый источник ????
2
= {(????????), (????????), (????????), (????????)} = {????
1
, ????
2
, ????
3
, ????
4
, }.
Решение. Вероятности появления символов с 2-кратным расширением ис- точника одиночных символов равны:

50
????
1
= ????(????
1
) = ????
1
????
1
=
49 64
,
????
2
= ????(????
2
) = ????
1
????
2
=
7 64
,
????
3
= ????(????
3
) = ????
2
????
1
=
7 64
,
????
4
= ????(????
4
) = ????
2
????
2
=
1 64
Для кодирования блокового источника применим префиксный код:
(????????) → 0,
(????????) → 10,
(????????) → 110,
(
????????) → 111.
Средняя длина ????
????
этого кода равна:
????
????
= ∑ ????
????
4
????=1
????
????
=
49 64
∙ 1 +
7 64
∙ 2 +
7 64
∙ 3 +
1 64
∙ 3 =
87 64
Средняя длина слова на один символ источника равна:
????
????
????
=
87 64 2
=
87 128
= 0,68.
Как видно, средняя длина кода источника ???? = {????, ????} уменьшилась c
???? = 1 до
????
????
????
= 0,68 > ???? = 0,54.
Энтропия блокового источника равна
????
′
= ∑
−????(????
????
)
4
????=1
log
2
????(????
????
) = (−
49 64
log
2 49 64
) + (−
7 64
log
2 7
64
) + (−
7 64
log
2 7
64
) +
+ (−
1 64
log
2 1
64
) = 1,08 бит/символ (????
′
).
Заметим, энтропия блокового источника в ???? раз больше энтропии соответ- ствующего источника одиночных символов:
????
′
= ???? ???? = 2 ∙ 0,54 = 1,08 бит/символ (????
′
).

51
Пример 4 .3 . Источник формирует символы ???? = {????
1
, ????
2
} = {????, ????} c веро- ятностями {????
1
=
1 3
, ????
2
=
2 3
}. Размерность алфавита ???? = 2. Энтропия источника равна
???? = ∑
−????
????
2
????=1
log
2
????
????
=
1 3
∙ 1,585 +
2 3
∙ 0,585 = 0,918 бит/символ.
Символы источника кодируются словами ???? → 0, ???? → 1. Длина кодовых слов равна ????
1
= ????
2
= 1.
Пример 4 .4 . Для увеличения количества передаваемой информации, ис- пользуем источник одиночных символов примера 4.3. Построим блоковый ис- точник ????
2
= {(????????), (????????), (????????), (????????)} = {????
1
, ????
2
, ????
3
, ????
4
}. Выход этого источника принимает одно из состояний множества ???? = {????
1
, ????
2
, ????
3
, ????
4
}.
Решение
1. Вычислим вероятности появления символов множества ???? = {????
1
, ????
2
, ????
3
????
4
} как независимых событий источника ???? = {????
1
, ????
2
} c вероятностями символов
????
1
= ???? → ????
1
=
1 3
и
????
2
= ???? → ????
2
=
2 3
:
????(????
1
) = ????
1
∙ ????
1
=
1 9
, ????(????
2
) = ????
1
∙ ????
2
=
2 9
,
????(????
3
) = ????
2
∙ ????
1
=
2 9
, ????(????
4
) = ????
2
∙ ????
2
=
4 9
Для кодирования блокового источника применим следующий равномер- ный блоковый код:
(????????) → 00,
(????????) → 10,
(????????) → 01,
(
????????) → 11.
2. Средняя длина
????
????
этого кода равна:
????
????
= ∑ ????(????
????
)
????
????=1
????
????
=
1 9
∙ 2 +
2 9
∙ 2 +
2 9
∙ 2 +
4 9
∙ 2 = 2.
3. Средняя длина на один символ источника равна:
????
????
????
=
2 2
= 1.
Как видно, средняя длина кода источника ???? = {????, ????} не уменьшилась, т. к. в этом примере использовалось равномерное кодирование источника:

52
????
????
????
= 1 > ???? = 0,918.
4. Энтропия блокового источника равна
????′ = ∑
−????(????
????
)
4
????=1
log
2
????(????
????
) =
1 9
∙ 0,585 +
2 9
∙ 2,1699 +
2 9
∙ 2,1699 +
+
4 9
∙ 1,1699 = 1,83 бит/символ (????
′
).
Энтропия блокового источника в два раза больше энтропии соответствую- щего источника одиночных символов:
????
′
= ???? ???? = 2 ∙ 0,918 = 1,83.
Следует отметить, что применение рассмотренного метода эффективного представления информации приводит к увеличению сложности технической ре- ализации кодирования, увеличению сложности декодирования, увеличенияю времени на процесс декодирования.
4.3. Cжатие данных
В настоящее время большая часть передаваемых, хранимых, распределяе- мых, преобразуемых данных соответствует звуковой, графической или видеоин- формации. В этом случае реализация современных инфокоммуникационных си- стем неизбежно усложняется. Увеличиваются технические затраты на хранение данных, предъявляются более высокие требования по экономии канального ча- стотного и энергетического ресурсов. Эффективное кодирование или по другому сжатие данных позволяет уменьшить объем данных, используемых для пред- ставления информации. Даже при постоянном росте емкости хранения данных и пропускной способности каналов сжатие остается необходимым и существен- ным компонентом информационных технологий. Различают два основных ме- тода кодирования данных используемых для сжатия: кодирование с потерями и кодирование без потерь.
Идея этих двух методов сжатия основывается на возможности устранения или уменьшения избыточности передаваемых (хранимых) данных. Сигнал, несу- щий информацию, можно сжать путем удаления из него имеющейся избыточно- сти.
Различают два вида избыточности:
1. Видео/аудио (субъективная) избыточность, которую можно устранить с некоторой потерей информации, сравнительно мало влияющей на качество вос- производимого изображения или звука.
Например, в аналоговых телевизионных системах, передача видеоинфор- мации осуществляется в полосе 6 МГц. Хотя видеоспектр имеет значительно

53 большее значение, часть спектральных составляющих отбрасывается. В этом случае исходная видеоинформация не может быть полностью восстановлена.
Примером сжатия с потерями, когда отбрасывается несущественная ин- формация, может служить система цифрового покомпонентного телевидения
(Digital Video Broadcasting, DVB).
Формирование цифровых сигналов изображения включает в себя три этапа:
– дискретизацию;
– квантование;
– кодирование квантованных отсчетов.
При дискретизации телевизионного сигнала с частотой Найквиста - Ко- тельникова частота дискретизации ????
????
должна не менее чем вдвое превышать мак- симальное значение спектра видеосигнала. В соответствии с Рекомендацией
МСЭ (Международный союз электросвязи, ITU (
International Telecommunication
Union)) частота дискретизации ????
????
выбрана равной 13,5 МГц.
В покомпонентном телевидении в качестве исходных сигналов формиру- ются разделенные сигналы яркости ???? и цветоразностные сигналы ????
????
= ???? − ???? и
????
????
= ???? − ????.
В соответствии с Рекомендацией МСЭ форматы представления покомпо- нентного цифрового сигнала, которые различаются между собой структурой расположения отсчетов яркости ???? и цветоразностных сигналы ????
????
= ???? − ???? и
????
????
= ???? − ????. Например, в формате 4:2:2 плотность отсчетов для цветоразностных сигналов ????
????
и
????
????
в горизонтальном направлении в 2 раза меньше по сравнению с сигналом ????. В формате 4:2:2 в активной части строки содержится 720 отсчетов яркостного сигнала и по 360 отсчетов каждого цветоразностного сигналов.
При 8-битном кодировании каждого отсчета изображения ширина полосы частот цифрового полного телевизионного сигнала составляет величину
???? = ????
????
????
???? + ????
????
????
???? + ????
????
????
???? = 13,5 ∙ 8 + 6,75 ∙ 8 + 6,75 ∙ 8 = 216 МГц, где ????
????
????
– частота дискретизации яркостного канала (????
????
????
= 13,5 МГц), ????
????
????
= ????
????
????
– частоты дискретизации цветоразностных сигналов (????
????
????
= ????
????
????
= 6,75 МГц).
Скорость передачи информации достигает значения ???? = 216 Mбит/с . В этом случае за одну секунду передаются данные объемом 216 Mбит.
Телевидение высокой четкости для формата HDTV (High Definition Telev- ision) имеет примерно удвоенную разрешающую способность по горизонтали и как минимум удвоенную разрешающую способность по вертикали и соответ- ствующее увеличение объема цифрового информационного потока до значения
≈ 576 Mбит. Стандартный телевизионный канальный частотный ресурс нахо- дится в диапазоне 48–862 Мгц. Очевидно, без эффективного сжатия невозможно реализовать технологию многоканальной передачи информации в формате
HDTV. В этой технологии сжатие (кодирование) видеосигнала реализуется на основе стандарта MPEG (Motion Pictures Experts Group). Стандарт разработан

54
Экспертной группой по вопросам движущихся изображений. Кодирование осно- вано на удалении, не воспринимаемых органами зрения отдельных спектральных составляющих видеосигнала.
2. Статистическая избыточность, связанная с корреляцией и предсказуемо- стью обрабатываемых данных. Такая избыточность может быть полностью устранена без потери информации и исходные данные могут быть полностью восстановлены. Технология сжатия осуществляется за счет применения эффек- тивного кодирования данных источников. В этом случае под избыточностью по- нимают частое повторение символов информационного сообщения, повторяе- мость слов и предложений сообщений. Примером такого алгоритма является ко- дирование источника с помощью кода Хаффмена.
Эффективность сжатия оценивается коэффициентом
???? =
????−????
????
, (4.3) где ???? – затраты на передачу (хранение) данных без сжатия; ???? − затраты на пе- редачу (хранение) данных со сжатием.
Например, передача (хранение) яркостей всех 64 пикселей фрагмента изоб- ражения размером 8 × 8 реализуется посредством использования
???? = 2 6
∙ 2 3
= 2 9
= 512 бит.
Здесь значение яркости каждого пикселя кодируется двоичным кодом дли- ной 8 бит. Пусть с использованием метода сжатия по стандарту MPEG-2 полу- чено ???? = 128 бит. Тогда эффективность сжатия будет равна
???? =
512−128 512
= 0,75, что соответствует 75 %.
Преобразуем формулу (4.3) следующим образом:
???????? = ???? − ????,
???? = ???????? + ????,
????
????
=
???????? + ????
????
В этом случае отношение вида
????
????
характеризует выигрыш в записи данных.
Для рассматриваемого примера выигрыш равен
????
????
=
???????? + ????
????
=
0,75 ∙ 512 + 128 128
= 4.

55
Пример 4. 5. Оценить эффективность сжатия стереофонического аудио усовершенствованной системы кодирования звука MPEG-2 AAC (Advanced Au- dio Coding; стандарт разработан в 1998 г. в Институте интегральных схем Фра- унгофера – IIS-A, Германия) со скоростью 112 Кбит/с. В качестве сравнения рас- смотрим кодирование по стандарту стереофонического аудио компакт дисков
(CD-Audio), где сжатия практически нет. Стандартная частота дискретизации
????
????
непрерывного аудио сигнала для CD ????
????
= 44,1 КГц. Длина кодовых слов ???? = 16.
Решение. Скорость передачи стереоданных аудио CD определяется как
???? = 2 ∙ ????
????
∙ ???? = 2 ∙ 44,1 ∙ 16 = 1411,2 Кбит/с.
Эффективность сжатия
???? =
1411,2 − 112 1411,2
≅ 0,92.
Выигрыш в записи данных
????
????
=
1411,2 112
= 12,6.
Замечание. Сравнительно высокая степень сжатия методом кодирования
AAC отражается на качественных характеристиках воспроизводимого аудиосиг- нала.
Одним из первых методов сжатия без потерь является метод Шеннон –
Фано.

56 источника может находиться в диапазоне
???? ≤ ???? ≤ ???? + 1 и определяется величиной энтропии источника.
Таким образом, кодирование будет тем эффективнее, чем ближе средняя длина кодового слова приближается к энтропии и чем меньше значение энтро- пии. Метод эффективного кодирования источника информации, основанный на понятии энтропии, называется энтропийным. Один из основных методов такого кодирования известен как кодирование Хаффмена (D. А. Huffman, амер. уче- ный). В 1952 г. Д. А. Хаффмен показал, что разработанный им алгоритм эффек- тивного кодирования позволяет строить класс оптимальных префиксных кодов без запятой, т. е. неравномерных кодов. Эти коды позволяют кодировать сим- волы источника с минимальной избыточностью. Кодирование Хаффмена фор- мирует оптимальный код для дискретных источников без памяти. Средняя длина
???? кодового слова кода Хаффмена приближается к энтропии источника ????. В настоящее время коды Хаффмена используются при цифровой обработке изоб- ражений и звуков. Они составляют основную часть стандартов сжатия изобра- жений и звука MPEG, H. 264, JPEG (Joint Photographic Experts Group, JPEG разра- ботан Объединенной группой экспертов по обработке фотографических изобра- жений).
4.4.1. Алгоритм Хаффмена
Алгоритм включает в себя выполнение ряда итерационных действий:
1. Упорядочение. Необходимо расставить символы источника в порядке уменьшения их вероятностей.
2. Редукция. Необходимо объединить два символа с наименьшими вероят- ностями в один символ.
3. Переупорядочение. Необходимо расставить символы в порядке умень- шения их вероятностей.
4. Продолжить процессы 2 и 3 до тех пор, пока все символы не будут объ- единены. В случае, когда несколько символов имеют одинаковые вероятности, объединяются те из них, которые имели до этого меньшее число объединений.
5. Кодирование. Необходимо начать процесс кодирования с последнего объединения. Приписать первой компоненте составного символа значение 0, а второй компоненте значение 1. Продолжать этот процесс до тех пор, пока все символы не будут закодированы.
Пример 4 .6 . Источник формирует следующие символы ???? =
= {????
1
, ????
2
, … , ????
6
} = {????, ????, ????, ????, ????, !}. Вероятности символов задаются множе- ством: {????
1
= 0,05, ????
2
= 0,15, ????
3
= 0,05, ????
4
= 0,4, ????
5
= 0,2, ????
6
= 0,15}. Постро- ить код Хаффмена.
Решение. Алгоритм реализуется по схеме, приведенной на рис. 4.1.