Применение эффективного (статистического) кодирования для сжатия данных
Понятие и основная задача эффективного кодирования. Условия эффективного использования пропускной способности канала. Оценка эффективности применения оптимальных неравномерных кодов. Пример двоичного кодового дерева. Алгоритм кодирования Хаффмана.
| Рубрика | Коммуникации, связь, цифровые приборы и радиоэлектроника |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 30.03.2017 |
| Размер файла | 29,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
ПРИМЕНЕНИЕ ЭФФЕКТИВНОГО (СТАТИСТИЧЕСКОГО) КОДИРОВАНИЯ ДЛЯ СЖАТИЯ ДАННЫХ
Эффективное кодирование - это процедуры направленные на устранение избыточности.
Основная задача эффективного кодирования - обеспечить, в среднем, минимальное число двоичных элементов на передачу сообщения источника.
При кодировании сообщений данного источника двоичным, равномерным кодом, каждый двоичный элемент, будет переносить 1 бит информации.
Если при том же объеме алфавита сообщения не равновероятны, то на каждый двоичный элемент кодовой комбинации будет приходиться меньше чем 1 бит.
Появившаяся избыточность, определяется по следующей формуле:
кодирование канал двоичный код
(4.1)
Среднее количество информации, приходящееся на один двоичный элемент комбинации при кодировании равномерным кодом
(4.2)
При кодировании неравномерным кодом, для сообщения, содержащее большее количество информации, выбирают более длинную кодовую комбинацию, а для передачи сообщения с малым объемом информации используют короткие кодовые комбинации.
Для эффективного использования пропускной способности канала необходимо его согласование с источником информации на входе. Такое согласование возможно как для каналов связи без помех, так и для каналов с помехами на основании двух теорем, доказанных К.Шенноном.
1-ая теорема (для канала связи без помех):
Нельзя закодировать сообщение двоичным кодом так, что бы средняя длина кодового слова была численно меньше величины энтропии источника сообщений
2-ая теорема (для каналов связи с помехами):
Существует способ кодирования, при котором средняя длина кодового слова немногим отличается от энтропии источника
Эффективность применения оптимальных неравномерных кодов может быть оценена:
- Коэффициентом статистического сжатия, который характеризует уменьшение числа двоичных элементов на сообщение, при применении методов эффективного кодирования в сравнении с равномерным.
- Коэффициент относительной эффективности, позволяет сравнить эффективность применения различных методов эффективного кодирования.
В неравномерных кодах возникает проблема разделения кодовых комбинаций. Решение данной проблемы обеспечивается применением префиксных кодов.
Префиксным называют код, для которого никакое более короткое слово не является началом другого более длинного слова кода. Префиксные коды всегда однозначно декодируемы.
Кодовое дерево для множества кодовых слов графически можно получить, установив соответствие между сообщениями и концевыми узлами двоичного дерева. Пример двоичного кодового дерева изображен на рисунке 4.1.
Рисунок 4.1. Пример двоичного кодового дерева
Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между “0” и “1” в качестве первого символа кодового слова: левая ветвь соответствует “0”, а правая - “1”. Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых слов, левая означает “0”, а правая - “1” и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.
Любой код, кодовые слова которого соответствуют различным концевым вершинам некоторого двоичного кодового дерева, является префиксным, т. е. однозначно декодируемым.
Одним из серьёзных недостатков префиксных кодов является появление трека ошибок, т.е. одиночная ошибка в кодовой комбинации, при определенных обстоятельствах, способна привести к неправильному декодированию не только данной, но и нескольких последующих кодовых комбинаций.
Метод Хаффмена
Одним из часто используемых методов эффективного кодирования является так называемый код Хаффмана.
Алгоритм кодирования Хаффмана состоит в следующем:
1. Сообщения располагаются в столбец в порядке убывания вероятности их появления.
2. Два самых маловероятных сообщения объединяем в одно сообщение, которое имеет вероятность, равную сумме вероятностей сообщений.
3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.
4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно определить, приписывая правым ветвям объединения символ “1”, а левым - “0”. Впрочем, понятия “правые” и “левые” ветви в данном случае относительны.
На основании приведенного алгоритма можно построить кодовое дерево.
Арифметическое кодирование
Достоинства арифметического кодирования: способность кодирования символа с количеством бит сколь угодно близким к предельному; возможность адаптивного изменения модели; высокая скорость работы.
Алгоритм арифметического кодирования:
1. Разбиваем единичный отрезок на участки, соответствующие вероятностям сообщений алфавита.
2. Выбираем участок, соответствующий первому сообщению в кодируемом блоке. Разбиваем его пропорционально суммарным вероятностям
3. Находим нижнюю и верхнюю границы, ширину участка.
4. Выбираем участок, соответствующий второму сообщению в кодируемом блоке на участке соответствующему ранее взятому сообщению. Разбиваем его пропорционально суммарным вероятностям.
5. Повторяем 3 и 4 пункты.
6. Участок, соответствующий последнему сообщению в кодируемом блоке, делим пополам и получаем число-архив. Количество разрядов, необходимое для представления архива в двоичном виде определяется как log2 (1/3) +1.
Декодирование арифметического кода производится двумя способами:.
1. Масштабирование отрезков
2. Масштабирование архива
Размещено на Allbest.ru
...Подобные документы
Методы кодирования и декодирования циклических кодов, метод кодирования и декодирования сверточных кодов, формирование проверочных разрядов. Изучение обнаруживающей и исправляющей способности циклических кодов, исследование метода коммутации.
лабораторная работа [709,6 K], добавлен 26.08.2010Помехоустойчивые коды и их классификация. Формирование каскадного кода. Линейные коды. Замкнутость кодового множества. Схемы кодирования, применяемые на практике. Основные классы кодов. Блоковый код мощности. Сферы декодирования. Неполный декодер.
реферат [83,4 K], добавлен 11.02.2009Модель передачи данных с применением помехоустойчивого кодирования. Код с удвоением элементов, характеризующийся введением дополнительных символов для каждого информационной части комбинации. Принципы построения и режимы использования каскадных кодов.
дипломная работа [780,7 K], добавлен 25.10.2013Характеристика кодирования как средства защиты и повышения достоверности передачи информации по каналу связи. Частотный диапазон Bluetooth и способ кодирования пакета в цифровых системах связи. Классификация кодов, их параметры и оптимальные значения.
презентация [146,0 K], добавлен 22.10.2014Схема кодирования звуковой информации. Аналоговая и дискретная формы представления информации. Выделение количества уровней громкости в процессе кодирования звуковой информации. Качество двоичного кодирования звука. Расчет информационного объема.
презентация [613,8 K], добавлен 26.11.2012Разработка структурной схемы системы связи, предназначенной для передачи двоичных данных и аналоговых сигналов методом импульсно-кодовой модуляции. Принципы статического (эффективного) кодирования сообщений. Классификация помехоустойчивых кодов.
курсовая работа [882,7 K], добавлен 13.12.2011Типы линий связи и способы физического кодирования. Модель системы передачи информации. Помехи и искажения в каналах связи. Связь между скоростью передачи данных и шириной полосы. Расчет пропускной способности канала с помощью формул Шеннона и Найквиста.
курсовая работа [1,3 M], добавлен 15.11.2013Сущность и методы рационального кодирования. Особенности параметрической адаптивной процедуры. Основные принципы равномерного и неравномерного квантования мгновенных значений сигнала. Теория разностного кодирования. Система адаптации по шагу и усилению.
курсовая работа [1,1 M], добавлен 17.03.2011Применение кодирования с исправлением ошибок для восстановления данных, потерянных при их передаче и хранения. Использование кодов Рида-Соломона с недвоичными символами. Деление полиномов как важный момент при кодировании и декодировании кодов компьютера.
реферат [43,4 K], добавлен 25.02.2014Кодирование длин участков (или повторений) один из элементов известного алгоритма сжатия изображений JPEG. Широко используется для сжатия изображений и звуковых сигналов метод неразрушающего кодирования, им является метод дифференциального кодирования.
реферат [26,0 K], добавлен 11.02.2009Методы компрессии цифровых аудиоданных, кодирования речевых сообщений, алгоритмы кодирования изображений. Стандарты в области компьютерной видеоконференцсвязи. Сжатие с потерями и без потерь. Определение полосы частот для заданного качества сообщения.
презентация [876,4 K], добавлен 16.03.2014Назначение систем видеоконференций. Передача мультимедийных данных через сеть Internet в режиме реального времени. Выбор структуры и форматов данных в системе видеоконференций. Выбор метода кодирования и декодирования, описание стандарта кодирования.
курсовая работа [863,8 K], добавлен 17.10.2012Разработка цифрового устройства для двоично-десятичного кодирования цифр номера зачетной книжки студента. Таблица истинности для входных переменных. Генераторы и счетчик импульсов. Схема совпадения кодов, регистры памяти. Минимизация булева выражения.
реферат [3,3 M], добавлен 26.12.2013Словарные методы кодирования. Сущность их состоит в том, что фразы в сжимаемом тексте заменяются указателем на то место, где они в этом тексте уже pанее появлялись. Декодирование сжатого текста. Алгоритм Абрахама Лемпела и Якоба Зива - LZ77, LZ-сжатие.
реферат [30,5 K], добавлен 11.02.2009Цель и понятие кодирования сообщений. Засекречивание передаваемой информации. Помехоустойчивое кодирование. Экономное кодирование - сокращения объема информации и повышения скорости ее передачи или сокращения полосы частот, требуемых для передачи.
реферат [51,3 K], добавлен 11.02.2009Расчет аналитического выражения модулированных колебаний. Построение временных диаграмм, амплитудно-частотных и фазо-частотных спектров. Эффективность статистического двоичного кодирования. Структурная схема системы связи. Аналого-цифровое преобразование.
курсовая работа [1,1 M], добавлен 15.08.2012Преимущества радиоканальных охранных систем. Основные направления кодирования речи: кодирование формы (Waveform coding) и источника сигнала (Source coding). Структурная схема процесса обработки речи в стандарте GSM. Оценка качества кодирования речи.
реферат [46,8 K], добавлен 20.10.2011Особенности построения цифровой сети ОАО РЖД с использованием волоконно-оптических линий связи. Выбор технологии широкополосного доступа. Алгоритм линейного кодирования в системах ADSL. Расчет пропускной способности для проектируемой сети доступа.
дипломная работа [5,9 M], добавлен 30.08.2010Использование помехоустойчивого кодирования в системах передачи информации. Построение структурной схемы восьмиразрядного микроконтроллера M68HC11. Разработка алгоритма кодирования и декодирования информации. Подключение внешних портов ввода/вывода.
курсовая работа [1,7 M], добавлен 05.09.2014Понятие открытого акустического оформления головки и его особенности. Разработка и расчет акустического оформления головки динамической. Кодировка индивидуальной кодовой комбинации (ФИО) четырьмя способами и выбор оптимального метода кодирования звука.
курсовая работа [500,7 K], добавлен 04.03.2011
