- •Лекции Методы повышения достоверности передачи и приема
- •2.Применение помехоустойчивых видов модуляции
- •3.Применение помехоустойчивого кодирования
- •3.5. Разделение линий связи
- •3.5.1. Постановка задачи
- •3.5.2. Частотное разделение
- •3.5.3. Временное разделение
- •3.5.4. Фазовое разделение
- •3.5.5. Разделение по форме
- •3.5.7 Кодовое разделение
- •3.5.8. Комбинированные методы разделения.
- •5. Применение каналов с обратной связью.
- •Оптические линии связи
- •Сжатие данных Основные понятия
- •Характеристики алгоритмов сжатия данных
- •Алгоритмы сжатия без потерь
- •Статистические алгоритмы сжатия
- •Алгоритм Хаффмена
- •Алгоритм арифметического кодирования
- •Алгоритмы сжатия, использующие исключение повторов
- •Алгоритмы kwe
- •Словарные и словарно-статистические алгоритмы сжатия
- •Алгоритмы сжатия с потерями
- •Алгоритмы сжатия растровых статических изображений
- •Источники, рекомендуемые для углубленного изучения
- •Циклические коды некоторые обозначения и определения
- •Арифметика по модулю два
- •Двоичные циклические коды
- •Кодирование
- •Декодирование
Алгоритм Хаффмена
На зачете про него не рассказывать, т.к. на него есть задача!
Алгоритм арифметического кодирования
Алгоритм арифметического кодирования также как и алгоритм сжатия Хаффмена использует для уменьшения объема исходных данных разность в частоте встречаемости символов. В результате сжатия этим алгоритмом редко встречающиеся символы кодируются более длинными кодами по сравнению с более короткими кодами для часто встречающихся символов. Однако. в отличие от алгоритма Хаффмена символы кодируются не обязательно целым числом битов, т.е. один бит сжатых данных может относиться к нескольким символам сжимаемых данных.
Для данных, в которых частоты встречаемости для разных символов не сильно отличаются, алгоритм арифметического кодирования дает результаты, сходные с результатами, получаемыми при сжатии алгоритмом Хаффмена. Но там, где частоты встречаемости разных символов при небольшом их числе резко отличаются, арифметическое кодирование дает лучший результат по сравнению с алгоритмом Хаффмена. В большинстве реальных случаев арифметическое кодирование дает несколько больший коэффициент сжатия [].
До недавнего времени распространение данного алгоритма сдерживалось наличием на него патентов. В настоящее время срок действия патентов закончился и его начинают использовать.
Алгоритмы сжатия, использующие исключение повторов
Алгоритмы сжатия, использующие исключение повторов (RLE = Run-Length Encoding) чрезвычайно просты и ориентированы на быстрое сжатие данных, содержащих много идущих подряд одинаковых символов.
В основу алгоритмов RLE положен принцип выявления групп подряд идущих одинаковых символов и замены их структурой, в которой указывается код символа и число повторов, т.е. группа идущих подряд одинаковых символов заменяется на пару кодов вида <код символа; число повторов>. Максимальное число одинаковых символов, которое можно закодировать одной такой парой, определяется длиной кода числа повторов.
Проблему при сжатии алгоритмами RLE представляют данные, содержащие незначительное количество повторяющихся символов. К одиночным символам также приходится добавлять счетчик повторов, что вместо сжатия дает увеличение объема данных. Поэтому в практических реализациях алгоритмы RLE несколько усложняются, чтобы уменьшить увеличение объема сжатых данных в случае не очень подходящих данных.
В качестве примера рассмотрим реализацию RLE а графическом формате PCX. Группа повторяющихся байтов заменяется на байт-счетчик и байт данных. В байте-счетчике старшие два бита содержат единицы, в младших шести битах хранится число повторов. Неповторяющиеся значения, меньшие 0C0h = 0C016 = 110000002, записываются в сжатые данные без изменений. Для неповторяющихся значений, больших 0C016 = 110000002, (т.е. с двумя единицами в старших разрядах) такой подход недопустим, так как при распаковке такой байт будет восприниматься как байт-счетчик повторов. Поэтому такие байты при записи в сжатый поток предваряются байтом-счетчиком с числом повторов, равным единице (11000001 = С116). Рассмотрим пример.
Исходные данные: 00;00;00; 00;01;00;FE;FF;FF;FF.
Сжатые данные: С4;00;01;00;С1;FE;C3;FF.
В приведенном примере из строки длиной 10 байтов получена упакованная строка длиной 8 байтов. Видно, что один байт FE кодируется двумя байтами С1;FE, поэтому некоторые данные при таком сжатии могут вырасти в объеме до двух раз. Например:
Исходные данные: CF;FF;CF;FF;CF;FF.
Сжатые данные: C1;CF;C1;FF; C1;CF;C1;FF;C1;CF;C1;FF.
Распаковка производится следующим образом. Из входного потока читается байт и проверяются его старшие два бита. Если они равны единице, то из этого байта выделяются шесть младших битов, которые используются как счетчик. Далее из входного потока считывается байт и его значение записывается в выходной поток столько раз, сколько указано счетчиком. Если же в старших битах не две единицы, то этот байт непосредственно копируется в выходной поток. Рассмотрим пример.
Сжатые данные: C5;10;C4;FF;00;01;C1;CF;C1;EF.
Распакованные данные: 10;10;10;10;10;FF;FF;FF;FF;00;01;FF;EF.
Наилучшими объектами для данных алгоритмов являются графические файлы, в которых большие одноцветные участки изображения кодируются последовательностью одинаковых байтов. Эти алгоритмы могут давать заметное сжатие на некоторых типах файлов баз данных, имеющих таблицы с фиксированной длиной полей. RLE используется как этап сжатия в алгоритмах сжатия изображений. Следует отметить, что алгоритмы сжатия, использующие исключение повторов, неэффективны для сжатия текстовых данных.