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

Раздел Философия
/
Метод кодирования Шеннона - Фано.

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

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

Метод кодирования Шеннона - Фано.

Метод кодирования Шеннона - Фано. - раздел Философия, Дисциплина Теория информации Тема №4: Оптимальное эффективное кодирование источников Буквы Исходного Алфавита Записываются В Порядке Убывающей Вероятности. Упоряд...

Буквы исходного алфавита записываются в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивается так, чтобы суммарные вероятности двух подмножеств были примерно равными. Всем буквам верхней половины в качестве первого символа кода присваивают 1, а буквам нижней половины – 0. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия примерного равенства вероятностей и с тем же условием присвоения кодовых элементов в качестве второго символа. Такое разбиение продолжается до тех пор, пока в подмножестве не останется только по одной букве кодового алфавита.

Пример: Провести эффективное кодирование ансамбля из восьми букв (знаков).

Буква x_i	Вероятности p_i	Кодовая последовательность	Длина кодового слова n_i	p_in_i	-p_ilog₂p_i
Номер разбиения

x₁	0,25					0,5	0,50
x₂	0,25					0,5	0,50
x₃	0,15					0,45	0,41
x₄	0,15						0,41
x₅	0,05					0,2	0,22
x₆	0,05					0,2	0,22
x₇	0,05					0,2	0,22
x₈	0,05					0,2	0,22

== (0,25*2+0,25*2+0,15*3+0,15*3+0,05*4+0,05*4+0,05*4+0,15*4)=2,7 бит

= - (2*0,25*log₂ 0,25 + 2*0,15*log₂ 0,15 + 4*0,05*log₂0,05) = 2,7 бит

= 1

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

Развернуть

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

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

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

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

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

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Метод кодирования Шеннона - Фано.

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

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

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

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

Теорема кодирования источников. Неравенство Крафта. Префиксный код.
Теорема Шеннона о кодировании источников устанавливает связь между средней длинной кодового слова и энтропией источника: Для любого дискретного источника без памяти X с конечным алфавитом

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

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

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

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

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

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