русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Основные методы побуквенного кодирования. Код Хаффмана


Дата добавления: 2013-12-23; просмотров: 2033; Нарушение авторских прав


Кодеры, основанные на системе сжатия без потерь информации

В данном случае кодирующее устройство должно удовлетворять следующим условиям:

1. Обеспечивать безошибочную передачу информации, то есть взаимно однозначное соответствие между и (рисунок 11.2).

2. Обеспечивать кодирование наиболее экономным образом (с минимальной избыточностью).

Для выполнения первого требования:

а) необходимо, чтобы различным буквам алфавита соответствовали различные кодовые слова;

б) необходимо, чтобы была предусмотрена возможность разделения кодовых слов при их последовательной передаче. Для обеспечения этой возможности:

- используют специальные разделяющие символы;

- применяют кодовые слова одинаковой длины (равномерное кодирование);

- кодовая таблица составляется таким образом, чтобы никакое кодовое слово не являлось началом другого кодового слова.

Для выполнения второго требования необходимо добиваться при кодировании минимальной средней длины кодового слова:

. (11.3)

где – это длина -ого слова с учетом разделительной буквы (если она используется).

Теорема 1. Теорема Шеннона о кодировании в дискретных каналах без шума.При кодировании множества сигналов с энтропией при условии отсутствия шумов средняя длина кодового слова не может быть меньше, чем , где – размер алфавита кодера, 2 – основание алфавита кода.

Если вероятности сигналов не являются целочисленными отрицательными степенями (то есть все вероятности сообщений имеют вид: , где – целое положительное число), достижение указанной нижней границы невозможно, но при кодировании достаточно длинными блоками к ней можно сколь угодно приближаться.

Существует несколько способов, позволяющих получать коды с малой избыточностью; причем все они обладают следующими свойствами:



1. Более вероятным буквам источника ставятся в соответствие более короткие кодовые слова.

2. Никакое кодовое слово не является началом другого более длинного кодового слова.

3. Все буквы алфавита, используемые для передачи информации приблизительно равновероятны.

4. Символы в последовательности на выходе кодера практически независимы.

Простейшими кодами, с помощью которых можно выполнять сжатие информации, являются коды без памяти:

- код Хаффмана;

- код Шеннона;

- код Шеннона-Фано;

- код Гильбера-Мура.

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

Код Хаффмана – это двоичный префиксный код без памяти. Далее рассмотрим некоторые теоретические основы этого кода.

Префиксным множеством двоичных последовательностей S называется конечное множество двоичных последовательностей таких, что ни одна последовательность в этом множестве не является префиксом, или началом, другой последовательности в S.

Например, множество двоичных слов является префиксным множеством, а – не является т. к. здесь двоичных последовательность 00 является началом, другой последовательности 001 в S2.

Каждый префиксный код является дешифрируемым (обратное утверждение неверно).

Кодирование кодом без памяти осуществляется следующим образом:

1. Необходимо составить полный список символов алфавита входного сигнала; на j-ом месте стоит символ с вероятностью , то есть на первом месте стоит наиболее часто встречающийся символ.

2. Для любого назначить кодовое слово из префиксного множества двоичной последовательности S.

3. На выходе кодера объединить в одну последовательность все полученные двоичные слова.

Если – префиксное множество, то можно определить некоторый вектор , состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей ( является длиной ). Вектор состоит из неуменьшающихся положительных целых чисел и называется вектор Крафта. Для него выполняется неравенство Крафта:

  (11.4)

Длины двоичных последовательностей в префиксном множестве удовлетворяют данному соотношению. Если в (11.4) имеет место строгое равенство, то код называется оптимальным.



<== предыдущая лекция | следующая лекция ==>
Сжатие с потерями информации | Пример № 2.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.