Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
СИБИРСКАЯ АЭРОКОСМИЧЕСКАЯ АКАДЕМИЯ
ИМЕНИ АКАДЕМИКА М. Ф. РЕШЕТНЕВА
Теория информации
Для студентов специальности «Автоматизированные системы обработки информации и управления»
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ РАБОТАМ
Лабораторная работа №3
«Определение избыточности сообщений.
Оптимальное неравномерное кодирование»
Определить коэффициент статистического сжатия.
Коэффициент относительной эффективности
Если энтропия источника сообщений не равна максимальной энтропии для алфавита с данным количеством качественных признаков (имеются в виду качественные признаки алфавита, при помощи которых составляются сообщения), то это прежде всего означает, что сообщения данного источника могли бы нести большее количество информации. Абсолютная недогруженность на символ сообщений такого источника
Для определения количества «лишней» информации, которая заложена в структуре алфавита либо в природе кода, вводится понятие избыточности. Избыточность, с которой мы имеем дело в теории информации, не зависит от содержания сообщения и обычно заранее известна из статистических данных. Информационная избыточность показывает относительную недогруженность на символ алфавита и является безразмерной величиной:
Н и Нmax берутся относительно одного и того же алфавита.
Кроме общего понятия избыточности существуют частные виды избыточности.
Избыточность, обусловленная неравновероятным распределением символов в сообщении.
Избыточность, вызванная статистической связью между символами сообщения,
Полная информационная избыточность
При построении оптимальных кодов наибольшее распространение нашли методики Шеннона—Фано и Хаффмена
Согласно методике Шеннона — Фано построение оптимального кода ансамбля из сообщений сводится к следующему:
1-й шаг. Множество из сообщений располагается в порядке убывания вероятностей.
2-й шаг. Первоначальный ансамбль кодируемых сигналов разбивается на две группы таким образом, чтобы суммарные веро ятности сообщений обеих групп были по возможности равны. Если равной вероятности в подгруппах нельзя достичь, то их делят так, чтобы в верхней части (верхней подгруппе) оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части (в нижней подгруппе).
3-й шаг. Первой группе присваивается символ 0, второй группе— символ 1.
4-й шаг. Каждую из образованных подгрупп делят на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны.
5-й шаг. Первым группам каждой из подгрупп вновь присваивается 0, а вторым—1. Таким образом, мы получаем вторые цифры кода. Затем каждая из четырех групп вновь делится на равные (с точки зрения суммарной вероятности) части до тех пор, пока в каждой из подгрупп не останется по одной букве.
Код Хаффмана
Согласно методике Хаффмана, для построения оптимального кода N символы первичного алфавита выписываются в порядке убывания вероятностей. Последние n0 символов, где 2 < n0 < т объединяют в некоторый новый символ с вероятностью, равной сумме вероятностей объединенных символов Последние символы с учетом образованного символа вновь объединяют, получают новый, вспомогательный символ, опять выписывают символы в порядке убывания вероятностей с учетом вспомогательного символа и т. д. до тех пор, пока сумма вероятностей т оставшихся символов не даст в сумме вероятность, равную 1.
На практике обычно, не производят многократного выписывания вероятностей' символов с учетом вероятности вспомогательного символа, а обходятся элементарными геометрическими построениями, суть которых сводится к тому, что символы кодируемого алфавита попарно объединяются в новые символы, начиная с символов, имеющих наименьшую вероятность. Затем с учетом вновь образованных символов, которым присваивается значение суммарной вероятности двух предыдущих, строят кодовое дерево, в вершине которого стоит символ с вероятностью 1. При этом отпадает необходимость в упорядочивании символов кодируемого алфавита в порядке убывания вероятностей