Коды без памяти. Коды Хаффмена. Коды с памятью - Коммуникации, связь, цифровые приборы и радиоэлектроника реферат

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
«Коды без памяти. Коды Хаффмена. Коды с памятью»
Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в к о дируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последов а тельностей или слов.
Префиксным множеством двоичных последовательностей 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 ), состоящий из неуменьшающихся положительных целых чисел, называется вектором Крафта. Для него выполняется неравенство
Это неравенство называется неравенством Крафта. Для него справедливо следующее утверждение: если 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}
Допустим мы хотим разработать код без памяти для сжатия вектора данных 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).
Построим кодовое дерево для сообщения со следующим алфавитом:
Самой большой сложностью с кодами Хаффмена, как следует из предыдущего обсуждения, является необходимость иметь таблицы вероятностей для каждого типа сжимаемых данных. Это не представляет проблемы, если известно, что сжимается английский или русский текст; мы просто предоставляем кодеру и декодеру подходящее для английского или русского текста кодовое дерево. В общем же случае, когда вероятность символов для входных данных неизвестна, статические коды Хаффмена работают неэффективно.
Решением этой проблемы является статистический анализ кодируемых данных, выполняемый в ходе первого прохода по данным, и составление на его основе кодового дерева. Собственно кодирование при этом выполняется вторым проходом.
Существует, правда, динамическая версия сжатия Хаффмена, которая может строить дерево Хаффмена "на лету" во время чтения и активного сжатия. Дерево постоянно обновляется, чтобы отражать изменения вероятностей входных данных. Однако и она на практике обладает серьезными ограничениями и недостатками и, кроме того, обеспечивает меньшую эффективность сжатия.
Еще один недостаток кодов Хаффмена - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 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.
Заменяя каждый блок присвоенным ему кодовым словом из таблицы кодера, получим последовательность кодовых слов:
Объединяя эти кодовые слова вместе, имеем выходную последовательность кодера:
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).
Результат кодирования - вектор B(X) = (10111011111011) длиной в 11 бит и скоростью сжатия R = 13/11=1,18 бита на символ данных, тогда как при кодировании равномерным трехразрядным кодом с R = 3 понадобилось бы 33 бита.
Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. - 120с.
Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. - М.: Высшая школа, 2001 г. - 383с.
Цапенко М.П. Измерительные информационные системы. - М.: Энергоатом издат, 2005. - 440с.
Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. -368 с.
Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. - М.: Издательский дом «Вильямс», 2003 г. - 1104 с.
Орбиты спутниковых ретрансляторов. Модуляция-демодуляция и помехоустойчивое кодирование. Коды Боуза-Чоудхури-Хоквингема. Наиболее широко известные сверточные коды. Протоколы множественного доступа. Проблема статистического мультиплексирования потоков. контрольная работа [1,8 M], добавлен 20.12.2012
Коды Хэмминга как линейные систематические коды, в которых проверочные разряды (избыточные символы) формируются линейным преобразованием (суммированием по модулю 2) информационных разрядов (символы сообщения), их использование. Расчет параметров кодов. лабораторная работа [1,6 M], добавлен 30.11.2013
Способы задания линейных кодов. Проверочная матрица в систематическом виде. Основные свойства линейных кодов. Стандартное расположение группового кода. Коды Хэмминга. Корректирующая способность кода Хэмминга. Процедура исправления одиночных ошибок. реферат [87,9 K], добавлен 11.02.2009
Помехоустойчивые коды и их классификация. Формирование каскадного кода. Линейные коды. Замкнутость кодового множества. Схемы кодирования, применяемые на практике. Основные классы кодов. Блоковый код мощности. Сферы декодирования. Неполный декодер. реферат [83,4 K], добавлен 11.02.2009
Кодирование сигнала и структурированные последовательности. Определение линейного группового кода с повторением; длина кодового слова, количество информационных символов. Определение минимального расстояния Хэмминга кода, порождаемого матрицей Адамара. контрольная работа [407,0 K], добавлен 12.11.2012
Длина циклического кода. Свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим. Декодирование циклических кодов. Синдромный многочлен, используемый при декодировании циклического кода. реферат [195,1 K], добавлен 11.02.2009
Сущность циклических кодов, их использование в ЭВМ при последовательной передаче данных. Сложение двоичных многочленов. Принцип построения и корректирующие возможности циклических кодов. Список образующих полиномов. Обнаружение и исправление пачек ошибок. доклад [51,6 K], добавлен 19.10.2014
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Коды без памяти. Коды Хаффмена. Коды с памятью реферат. Коммуникации, связь, цифровые приборы и радиоэлектроника.
Осень В Парке Сочинение Для 3 Класса
Силовые Качества Реферат
Реферат: Особенности отношения к браку у лиц 25-30 лет
Клише Для Заключения Декабрьского Сочинения
Реферат Про Малахит
Контрольная Работа На Тему Народное Драматическое Творчество
Управление Внешним Государственным Долгом Рф Реферат
Председатель Вак Владимир Филиппов Отказался Защищать Диссертацию
Деловая Активность Предприятия Курсовая Работа
Дипломная работа по теме Анализ оборотных средств ОАО 'ДЭП-12'
Структура Отчета По Учебной Практике
Отчет по практике по теме Деятельность банка ОАО 'Росгосстрах Банк'
Реферат: История происхождения рубля
Реферат по теме Статистика населения. Методы анализа динамики численности и структуры населения
Гидравлический расчет системы водяного охлаждения промышленных предприятий
Реферат: Религии Древнего Востока. Скачать бесплатно и без регистрации
Курсовая работа: Гражданство Российской Федерации
Реферат: Організаційно - правові аспекти іноземного інвестування в Україні
Контрольная Работа Пресмыкающиеся 7 Класс
Достопримечательности Жарминский Район Эссе
Учет начисления выработки и заработной платы - Бухгалтерский учет и аудит дипломная работа
Розголошення комерційної таємниці - Государство и право курсовая работа
Мировая химическая промышленность - География и экономическая география курсовая работа