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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Реферат Коды без памяти - простейшие коды, на основе которых выполняется сжатие данных. Статистическое кодирование с использованием префиксных множеств. Статистический анализ кодируемых данных. Недостатки кодов Хаффмена. Блочные коды и коды с конечной памятью.

Информация:

Тип работы: Реферат. Предмет: Схемотехника. Добавлен: 11.02.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра РЭС
Реферат на тему:
«Коды без памяти. Коды Хаффмена. Коды с памятью»

МИНСК, 2009
Коды без памяти. Коды Хаффмена

Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.
Префиксным множеством двоичных последовательностей S называется конечное множество двоичных последовательностей, таких, что ни одна последовательность в этом множестве не является префиксом, или началом, никакой другой последовательности в S.
К примеру, множество двоичных слов S1 = {00, 01, 100, 110, 1010, 1011} является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных совместных комбинаций (wi wj) из S1, то видно, что wi никогда не явится префиксом (или началом) wj. С другой стороны, множество S2 = { 00, 001, 1110 } не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества - 001.
Таким образом, если необходимо закодировать некоторый вектор данных X = ( x1, x2,… xn ) с алфавитом данных A размера k, то кодирование кодом без памяти осуществляется следующим образом:
- составляют полный список символов a1, a2, aj ... ,ak алфавита A , в котором aj - j-й по частоте появления в X символ, то есть первым в списке будет стоять наиболее часто встречающийся в алфавите символ, вторым - реже встречающийся и т.д.;
- каждому символу aj назначают кодовое слово wj из префиксного множества двоичных последовательностей S;
- выход кодера получают объединением в одну последовательность всех полученных двоичных слов.
Формирование префиксных множеств и работа с ними - это отдельная серьезная тема из теории множеств, выходящая за рамки нашего курса, но несколько необходимых замечаний все-таки придется сделать.
Если S = { w1, w2, ... , wk } - префиксное множество, то можно определить некоторый вектор v(S) = ( L1, L2, ... , Lk ), состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей (Li - длина wi ).
Вектор (L1, L2, ... , Lk), состоящий из неуменьшающихся положительных целых чисел, называется вектором Крафта. Для него выполняется неравенство
. (1)
Это неравенство называется неравенством Крафта. Для него справедливо следующее утверждение: если S - какое-либо префиксное множество, то v(S) - вектор Крафта.
Иными словами, длины двоичных последовательностей в префиксном множестве удовлетворяют неравенству Крафта.
Если неравенство (1) переходит в строгое равенство, то такой код называется компактным и обладает наименьшей среди кодов с данным алфавитом длиной, то есть является оптимальным.
Ниже приведены примеры простейших префиксных множеств и соответствующие им векторы Крафта:
S1 = {0, 10, 11} и v(S1) = ( 1, 2, 2 );
S2 = {0, 10, 110, 111} и v(S2) = ( 1, 2, 3, 3 );
S3 = {0, 10, 110, 1110, 1111} и v(S3) = ( 1, 2, 3, 4, 4 );
S4 = {0, 10, 1100, 1101, 1110, 1111} и v(S4) = ( 1, 2, 4, 4, 4, 4 );
S5 = {0, 10, 1100, 1101, 1110, 11110, 11111} и v(S5) = ( 1, 2, 4, 4, 4, 5, 5 );
S6 = {0, 10, 1100, 1101, 1110, 11110, 111110, 111111}
и v(S6) = (1,2,4,4,4,5,6,6).
Допустим мы хотим разработать код без памяти для сжатия вектора данных X = ( x1, x2,… xn ) с алфавитом A размером в k символов. Введем в рассмотрение так называемый вектор частот F = ( F1, F2, ... , Fk ), где Fi - количество появлений i-го наиболее часто встречающегося символа из A в X. Закодируем X кодом без памяти, для которого вектор Крафта L = ( L1, L2, ... , Lk ).
Тогда длина двоичной кодовой последовательности B(X) на выходе кодера составит
L*F = L1*F1 + L2*F2 + ... + Lk*Fk . (2)
Лучшим кодом без памяти был бы код, для которого длина B(X) - минимальна. Для разработки такого кода нам нужно найти вектор Крафта L, для которого произведение L*F было бы минимальным.
Простой перебор возможных вариантов - вообще-то, не самый лучший способ найти такой вектор Крафта, особенно для большого k.
Алгоритм Хаффмена, названный в честь его изобретателя - Дэвида Хаффмена, - дает нам эффективный способ поиска оптимального вектора Крафта L для F, то есть такого L, для которого точечное произведение L*F - минимально. Код, полученный с использованием оптимального L для F, называют кодом Хаффмена.

Алгоритм Хаффмена


Алгоритм Хаффмена изящно реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом:
1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.
2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагаем равной сумме вероятностей составляющих его символов. В конце концов построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него.
3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис. 1).
Построим кодовое дерево для со и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.