Методы сжатия данных.

Вопрос 1. Количество информации и энтропия

Лекция №8. Сжатие данных

Вопросы

1. Может ли непрерывная на сегменте функция не принимать нулевого значения ни в одной точке сегмента? Ответ объяснить.

2. Может ли непрерывная на интервале функция не принимать нулевого значения ни в одной точке сегмента? Ответ объяснить.

3. Пусть функция определена и непрерывна на , а на концах сегмента принимает значения одного знака. Вытекает ли из этого, что функция не принимает нулевого значения ни в одной точке сегмента? Ответ объяснить.

4. Пусть функция определена и непрерывна на , а на концах сегмента принимает значения разных знаков. Вытекает ли из этого, что функция принимает нулевое значение в какой-то точке сегмента? Ответ объяснить.

5. Доказать первую теорему Больцано-Коши.

6. Доказать, не решая уравнение непосредственно, что уравнение обязательно будет иметь корень на сегменте .

7. Пусть функция определена и непрерывна на , а на концах сегмента принимает значения разных знаков. Сколько корней может иметь уравнение ? Ответ объяснить.

8. Пусть функция определена на , а множество ее значений – это . Что можно сказать о непрерывности на ? Почему?

9. Доказать вторую теорему Больцано-Коши.

10. Доказать следствие из второй теоремы Больцано-Коши.

Вопросы:

1. Количество информации и энтропия. Методы сжатия данных.

В 1950 году Клод Шеннон заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных. Шеннон установил также, что количество бит в физическом представлении данных превышает значение, определяемое их энтропией. Для эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее, используются различные алгоритмы сжатия данных.

Сжатие данных применяется для сокращения времени их передачи. Так как на сжатие данных передающая сторона тратит дополнительное время, к которому нужно еще прибавить аналогичные затраты времени на декомпрессию этих данных принимающей стороной, то выгоды от сокращения времени на пере­дачу сжатых данных обычно бывают заметны только для низкоскоростных кана­лов. Этот порог скорости для современной аппаратуры составляет около 64 Кбит/с. Многие программные и аппаратные средства сети способны выполнять динамичес­кое сжатие данных в отличие от статического, когда данные предварительно сжимаютмя (например, с помощью популярных архиваторов), а уже затем отсылаются в сеть.

На практике может использоваться ряд алгоритмов сжатия, каждый из которых применим к определенному типу данных. Некоторые модемы (называемые интеллектуальными) предлагают адаптивное сжатие, при котором в зависимости от передаваемых данных выбирается определенный алгоритм сжатия.

Обычно применяются следующие алгоритмы сжатия данных.

Десятичная упаковка. Когда данные состоят только из чисел, значительную экономию можно получить путем уменьшения количества используемых на циф­ру бит с 7 до 4, используя простое двоичное кодирование десятичных цифр вместо кода ASCII. Просмотр таблицы ASCII показывает, что старшие три бита всех кодов десятичных цифр содержат комбинацию 011. Если все данные в кадре ин­формации состоят из десятичных цифр, то, поместив в заголовок кадра соответ­ствующий управляющий символ, можно существенно сократить длину кадра.

Относительное кодирование. Альтернативой десятичной упаковке при переда­че числовых данных с небольшими отклонениями между последовательными цифрами является передача только этих отклонений вместе с известным опор­ным значением. Такой метод используется, в частности, в методе цифрового кодирования голоса ADPCM, передающем в каждом такте только разницу между соседними замерами голоса.

Символьное подавление. Часто передаваемые данные содержат большое количество повторяющихся байт. Например, при передаче черно-белого изображения черные поверхности будут порождать большое количество нулевых значений, а макси­мально освещенные участки изображения — большое количество байт, состоящих из всех единиц. Передатчик сканирует последовательность передаваемых байт и, если обнаруживает последовательность из трех или более одинаковых байт, заменяет ее специальной трехбайтовой последовательностью, в которой указывает значение байта, количество его повторений, а также отмечает начало этой последовательно­сти специальным управляющим символом.

Коды переменной длины. В этом методе кодирования используется тот факт, что не все символы в передаваемом кадре встречаются с одинаковой частотой. Поэтому во многих схемах кодирования коды часто встречающихся символов заменяют кодами меньшей длины, а редко встречающихся — кодами большей длины. Такое кодирование называется также статистическим кодированием. Из-за того, что символы имеют различную длину, для передачи кадра возможна только бит-ориентированная передача. При статистическом кодировании коды выбираются таким образом, чтобы при анализе последовательности бит можно было бы однозначно определить соответствие определенной порции бит тому или иному символу или же запрещенной комбина­ции бит. Если данная последовательность бит представляет собой запрещенную комбинацию, то необходимо к ней добавить еще один бит и повторить анализ. Например, если при неравномерном кодировании для наиболее часто встречающе­гося символа «Р» выбран код 1, состоящий из одного бита, то значение 0 однобит­ного кода будет запрещенным. Иначе можно будет закодировать только два символа. Для другого часто встречающегося символа «О» можно использовать код 01, а код 00 оставить как запрещенный. Тогда для символа «А» можно выбрать код 001, для символа «П» — код 0001 и т. п.

Неравномерное кодирование наиболее эффективно, когда неравномер­ность распределения частот передаваемых символов достаточно велика, как при передаче длинных текстовых строк. Напротив, при передаче двоичных данных, например кодов программ, оно малоэффективно, так как 8-битовые коды при этом распределены почти равномерно.

Одним из наиболее распространенных алгоритмов, на основе которых строятся неравномерные коды, является алгоритм Хафмана, позволяющий строить коды автоматически, на основании известных частот символов. Существуют адаптивные модификации метода Хафмана, которые позволяют строить дерево кодов «на ходу», по мере поступления данных от источника.

Многие модели коммуникационного оборудования, такие как модемы, мосты, коммутаторы и маршрутизаторы, поддерживают протоколы динамического сжатия, позволяющие сократить объем передаваемой информации в 4, а иногда и 8 раз. В таких случаях говорят, что протокол обеспечивает коэффициент сжатия 1:4 или 1:8. Существуют стандартные протоколы сжатия, например V.42bis также большое количество нестандартных, фирменных протоколов. Реальный коэффициент сжатия зависит от типа передаваемых данных, так, графические и текстовые данные обычно сжимаются хорошо, а коды программ — хуже.