Реферат: Коды без памяти. Коды Хаффмена. Коды с памятью - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Коды без памяти. Коды Хаффмена. Коды с памятью

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 26 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

БЕЛОРУССКИЙ ГОСУДАРСТВЕНН ЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ К афедра РЭС Р еферат на тему: «Коды без памяти. Коды Хаффмена. Ко ды с памятью» МИНСК, 2009 Коды без памяти. Коды Хаффмена Простейшими кодами, на основе которых может выполня ться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в к о дируемом векторе данных заменяется кодовым словом из префик сного множества двоичных последов а тельностей или слов. Префиксным множеством двоичных последовательностей S называе т ся конечн ое множество двоичных последовательностей, таких, что ни одна последова тельность в этом множестве не яв ляется префиксом, или началом, ник а кой другой последовательности в S . К примеру, множество двоичных слов S1 = 00, 01, 100, 110, 1010, 1011 является префиксным множест вом двоичных последовательностей, поскольку, если проверить любую из 30 в озможных совмес т ных комб инаций ( w i w j ) из S1, то видно, что w i никогда не явится префиксом (или н ачалом) w j . С другой стороны, множество S2 = 00, 001, 1110 не является префиксным мн о жеством двоичных последо вательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множ е ства - 001. Таким образом, если необходимо закодировать некотор ый вектор да н ных X = ( x 1 , x 2 ,… x n ) с алфавитом данных A размера k , то кодирование кодом без памяти осуществляется следующи м образом: - составляю т полный список символов a 1 , a 2 , a j ... ,a k алфавита A , в котором a j - j -й по частоте по явления в X символ, то есть первым в списке будет стоять наиболее часто встречающийся в алфавите символ, вт о рым – реже встр е чающийся и т.д. ; - каждому сим волу a j назначают кодовое слово w j из префиксного мн о жества двоичных последовательностей S ; - выход кодера получают объединением в одну последовательность всех по лученных двои ч ных слов. Формирование префиксных множеств и работа с ними – это отдельная сер ь езная тема из теории множест в, выходящая за рамки нашего курса, но нескол ь ко необходимых замечаний все-таки придется сделать. Если S = w 1 , w 2 , ... , w k - пр ефиксное множество, то можно определить н е который вектор v(S) = ( L 1 , L 2 , ... , L k ), состоящий из чисел, являющихся длинам и соответс т вующих префиксны х последовательностей ( L i - длина w i ). Вектор ( L 1 , L 2 , ... , L k ), состоящий из неуменьшающихся положите льных целых чисел, называется вектором Крафта. Для него выполняется нера венс т во . (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 ( S 6) = (1,2,4,4,4,5,6,6). Допустим мы х отим разработать код без памяти для сжатия вектора да н ных X = ( x 1 , x 2 ,… x n ) с алфавитом A разме ром в k символов. Введем в рассмотрение так называемый вектор частот F = ( F 1 , F 2 , ... , F k ), где F i - кол и чество появлений i -го наиболее часто встречающегося символа из A в X . Закодируем X ко дом без пам я ти, для которого вектор Крафта L = ( L 1 , L 2 , ... , L k ) . Тогда длина двоичной кодовой последовательности B(X) на выходе к о дера составит L*F = L 1 *F 1 + L 2 *F 2 + ... + L k * F k . (2) Лучшим кодом без памяти был бы код, для которого длина B(X) - м и нимальна . Для разработки такого кода нам нужно найти вектор Крафта L, для к о торого произведение L*F было бы минимальным. Простой перебор возможных вариантов - вообще-то, не самый лучший сп о соб найт и такой вектор Крафта, особенно для большого k . Алгоритм Хаффмена, названный в честь его изобретателя - Дэвида Хаффмена, - дает нам эффективный способ п о иска оптимального вектора Крафта L для F , то есть т акого L , для которого точечное произведение L*F – минимально. Код, полученный с и с пользовани ем оптимального L для F , называют кодом Хаффм е на. Алгоритм Хаффмена Алгоритм Хаффмена изящно реализует общую идею ст атистического к о диро вания с использованием префиксных множеств и работает следующим обр а зом: 1. Выписы ваем в ряд все символы алфавита в порядке возрастания или убывания в е роятности их появления в тексте. 2. Последовательно объединяем два символа с наименьшими вероятн о стями появления в новый составн ой символ, вероятность появления котор о го полагаем равной сумме вероятностей составляющих его символов. В ко н це к онцов построим дерево, каждый узел которого имеет суммарную вероятност ь всех у з лов, находящи хся ниже него. 3. Прослеживаем путь к каждому л исту дерева, помечая направление к каждому узлу (например, направо - 1, нале во - 0) . Полученная последов а тельность дает кодовое слово, соответствующее каждому симв олу (рис. 1). Построим кодовое дерево для сообщения со следующим алфав и том: A B C D E 10 5 8 13 10 B C A E D 5 8 10 10 13 A E BC D 10 10 13 13 BC D AE 13 13 20 AE BCD 20 26 AEBCD 46 Рис. 1 Недостатки метода Хаффмена Самой большой сложностью с кодами Хаффмена, как следует из пред ы дущего обсуждения, является необходимость иметь таблицы вероятностей для каж дого типа сжимаемых данных. Это не п ре д ставляет проблемы, если известно, что сжимается английский или русский текст; мы просто предоставляем кодеру и декодеру подход я щее для английско го или русского текста кодовое дерево. В общем же случае, когда вероятнос ть символов для вхо д ных данных неизвестна, статические коды Хаффмена работают неэффекти в но. Решением этой проблемы является статистический анализ кодируемых да н ных, выполняемый в ходе пе рвого прохода по данным, и составление на его о с нове кодового дерева. Собственно кодирование при эт ом выполняется вторым пр о ходом. Существует, правда, динамическая в ерсия сжатия Хаффмена, которая может строить дерево Хаффмена "на лету" во время чтения и активного сжатия. Де рево постоянно обновляется, чтобы отражать изменения вероятн о стей входных данных. Однако и она на практике обладает серьезными огр а ничениями и недостатками и, кроме того, обеспечивает меньш ую эффекти в ность сжатия. Еще один недостаток кодов Хаффмена - это то, что минимальная длина к о дового слова для н их не может быть меньше единицы, тогда как энтропия соо б щения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код Хаффмена становится существенно избыточн ым. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процед у ра ко дирования/декодирования и значительно расширяется кодовое дерево, кот орое нужно в конечном итоге сохранять вместе с к о дом. Наконец, код Хаффмена обеспечивает среднюю длину кода, совпада ю щую с энтропией, только в том слу чае, когда вероятности символов источника являются целыми отрицательн ыми степенями дво й ки: 1/2 = 0,5; 1/4 = 0,25; 1/8 = 0,125; 1/16 = 0,0625 и т.д. На практике же такая ситуация встр е чается очень редко или может быть со здана блокированием символов со всеми вытекающими отсюда последс т виями. Коды с памятью Обычно рассматривают два типа кодов с памятью: - блочные коды; - коды с конечной памятью. Блочный код делит вектор данных на блоки заданной д лины и затем каждый блок заменяют кодовым словом из префиксного множест ва двои ч ных слов. Полученн ую последовательность кодовых сло в объединяют в результирующую двоичную строку на выходе кодера. О блочно м коде говорят, что он - блочный код k -го порядка, если все блоки имеют длину, ра в ную k . В качестве примера сожмем вектор данных X = (0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1), используя блочный ко д второго порядка. Сначала раз о бьем вектор X на блоки длины 2: 01, 10, 10, 01, 11, 10, 01, 01. Будем рассматривать эти бло ки как элементы нового “гипералфа вита” 01, 10, 11 . Чтобы определить, какой код назначить какому их символов этог о нового алфавита, определим вектор частот появлений элементов дополни тельного алфавита в последовательности блоков. Получим вектор частот (4, 3, 1), то есть наиболее часто встречающийся блок 01 поя в ляется 4 раза, следующий по частоте в стречаемости блок 10 - три раз а и наим е нее часто встреча ющийся блок 11 - лишь один раз. Оптимальный вектор Крафта для вектора частот ( 4, 3, 1 ) - это вектор (1, 2, 2). Таким образом, кодер для оптимального блочного кода второго порядка применительно к заданному вектору данных X определяет ся та б л. 1. Таблица 1 Таблица кодера Блок Кодовое слово 01 0 10 10 11 11 Заменяя каждый блок присвоенным е му кодовым словом из таблицы кодера, получим последов а тельность кодовых слов: 0, 10, 10, 0, 11, 10, 0, 0. Объединяя эти кодовые слова вместе, имеем выходную последовател ь ность кодера: B(X) = ( 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0 ). Можно проверить, что энтропия H(X) исходного вектора X равна 0.9887 бит/букву, а сте пень сжатия, получаемая в результате использования блочного кода R(X) = 12/16 = 0.75 бит на выборку да нных, оказалась меньше нижней границы энтропии. Полученный результат, ка залось бы, противоречит теореме Ше н нона, утверждающей, что невозможно достичь средней длины кода, м еньшей энтропии источника. Однако на самом деле это не так. Если внимател ьно посмотреть на вектор данных X , то можно заметить закономерност ь: за символом 0 чаще следует 1, то есть у с ловная вероятность Р(1/0) существенно больше, чем просто Р(0). Следовательно, энтропию этого источник а нужно считать как энтропию сложного сообщения, а она, как и з вестно, всегда меньше, чем для источник а простых соо б щений. Код с конечной памятью при кодировани и вектора данных ( X 1 , X 2 , ..., X n ) использует кодовую книгу, состоящую из нескольких различных к о дов без памяти . Каждая выборка данных кодируется кодом без памяти из кодовой книги, определяемым значением не которого числа предыдущих в ы борок данных. В качестве примера кодирования кодом с памятью рассмотрим уже упоминав шийся ранее классический пример X = ABRACADABRA . В этой последов а тельности совершенно очевидна сильная статистическая завис имость между ее очередными символами, которая должна обязательно учиты ваться при выборе метода кодиров а ния. Кодер с памятью при кодировании текущего символа учитывает значение предшествующего ему символа . Т аким образом, кодовое слово для текущего символа A будет различным в сочетаниях RA, DA и CA (иными сл о вами, код обладает памятью в один си мвол источника) (табл. 2). Таблица 2 Код ер Символ, предыдущий симво л Кодовое сл о во ( A ,-) 1 (B,A) 0 (C,A) 10 (D,A) 11 (A,R) 1 (R,B) 1 (A,C) 1 ( A , B ) 1 Результат кодирования - вектор B(X) = (10111011111011) длиной в 11 бит и скоростью сжатия R = 13/11=1,18 бита на символ данных, тогда как при кодировании равномерным трехраз рядным кодом с R = 3 понадоб и лось бы 33 б и та. ЛИТЕРАТУРА 1. Лидовский В.И. Теория информации. - М., « Высшая школа», 2002г. – 120с. 2. Метрология и радиоизмерения в теле коммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Ф едоров и др. – М.: Высшая школа, 2001 г. – 383с. 3. Цапенк о М.П. Измерительные информационные системы. – М.: Энергоатом издат, 2005. - 440с. 4. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. – 368 с. 5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, и спр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Кто бы мог подумать, что по ночам можно не только носиться по комнатам и орать, но и спать?
© Малый Кыс
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по информатике и информационным технологиям "Коды без памяти. Коды Хаффмена. Коды с памятью", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru