рефераты конспекты курсовые дипломные лекции шпоры

Раздел Философия
/
Теорема кодирования источников. Неравенство Крафта. Префиксный код.

Реферат Курсовая Конспект

Выберите учебное заведение

Теорема кодирования источников. Неравенство Крафта. Префиксный код.

Теорема кодирования источников. Неравенство Крафта. Префиксный код. - раздел Философия, Дисциплина Теория информации Тема №4: Оптимальное эффективное кодирование источников Теорема Шеннона О Кодировании Источников Устанавливает Связь Между Средней Дл...

Теорема Шеннона о кодировании источников устанавливает связь между средней длинной кодового слова и энтропией источника:

Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H(X) существует D-ичный префиксный код, в котором средняя длинна кодового слова , удовлетворяет неравенству:

В префиксном коде никакое кодовое слово не является префиксом другого кодового слова. Это значит, что поток кодовых слов может использоваться без специального разделения этих слов. Например, если код 101 является кодом какой-то буквы, то в качестве кодов других букв нельзя использовать следующие комбинации: 1,10,10101, …и т.д.

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

Если средняя длина =min, то код является оптимальным.

Теорема кодирования источников доказывается с использованием неравенства Крафта:

Для существования однозначно декодируемого D-ичного кода, содержащего k кодовых слов с длинами n₁,n₂,…,n_k, необходимо и достаточно, чтобы выполнялось неравенство Крафта:

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Дисциплина Теория информации Тема №4: Оптимальное эффективное кодирование источников

Тамбовский государственный технический университет... Кафедра Информационные системы... Дисциплина Теория информации...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Теорема кодирования источников. Неравенство Крафта. Префиксный код.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Тамбов 2010
Тема №4: Оптимальное (эффективное) кодирование источников. 4.1. Понятие кодирования. Кодовое дерево. В процессе кодирования каждая буква и

Методы оптимального кодирования. Сжатие данных.
Процедуру оптимального кодирования часто называют сжатием данных. Таким образом задача сжатия данных есть минимизация технических затрат на хранение или передачу информации путем оптимальн

Метод кодирования Шеннона - Фано.
Буквы исходного алфавита записываются в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивается так, чтобы суммарные вероятности двух подмножеств были примерно равными

Метод кодирования Хаффмана.
Этот метод кодирования всегда дает оптимальный код, т.е. получаемая является минимальной. Буквы алфавит

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

Алгоритм универсального кодирования методом Лемпела-Зива.
Этот метод относится к классу универсальных потому, что он не требует априорных знаний о статистике символов. Такой метод носит менее математически обоснованный, но более практический характер.

Особенности программ-архиваторов.
Если коды алгоритмов типа LZ передать для кодирования адаптивному алгоритму Хаффмана или арифметическому, то полученный двухшаговый алгоритм даст результат сжатия, подобный случайным программам: GZ

Сжатие с потерями.
Сжатие с потерями используется в основном для трех видов данных: 1.Полноцветная графика. 2. Звук. 3. Видеоинформация. Сжатие с потерями обычно происходит в два э