 Популярные статьи | |
| Сейчас на сайте |  Гостей: 1
На сайте нет зарегистрированных пользователей
Пользователей: 9,955
новичок: Logyattella
|
|
| 2.6.3. Сжатие данных |
Наличие в сообщениях избыточности позволяет ставить вопрос о сжатии данных, т.е. о передаче того же количества информации с по-мощью последовательностей символов меньшей длины. Для этого ис-пользуются специальные алгоритмы сжатия, уменьшающие избыточ-ность. Эффект сжатия оценивается коэффициентом сжатия:
K=n/q ,
где n – число минимально необходимых символов для передачи сооб-щения (практически это число символов на выходе эталонного алго-ритма сжатия); q – число символов в сообщении, сжатом данным ал-горитмом. Так, при двоичном кодировании n равно энтропии источни-ка информации. Часто степень сжатия оценивают отношением длин кодов на входе и выходе алгоритма сжатия.
Наряду с методами сжатия, не уменьшающими количество ин-формации в сообщении, применяются методы сжатия, основанные на потере малосущественной информации.
Сжатие данных осуществляется либо на прикладном уровне с помощью программ сжатия, называемых архиваторами, либо с помо-щью устройств защиты от ошибок (УЗО) непосредственно в составе модемов.
Очевидный способ сжатия числовой информации, представлен-ной в коде ASCII, заключается в использовании сокращенного кода с четырьмя битами на символ вместо восьми, так как передается набор, включающий только 10 цифр, символы “точка”, “запятая” и “пробел”.
Среди простых алгоритмов сжатия наиболее известны алгоритмы RLE (Run Length Encoding). В них вместо передачи цепочки из одина-ковых символов передаются символ и значение длины цепочки. Метод эффективен при передаче растровых изображений, но мало-полезен при передаче текста.
К методам сжатия относятся также методы разностного кодиро-вания, поскольку разности амплитуд отсчетов представляются мень-шим числом разрядов, чем сами амплитуды. Разностное кодирование реализовано в методах дельта-модуляции и ее разновидностях.
Предсказывающие (предиктивные) методы основаны на экстра-поляции значений амплитуд отсчетов, и если выполнено условие
Ar-Ap>d,
то отсчет должен быть передан, иначе он является избыточным; здесь Ar и Ap – амплитуды реального и предсказанного отсчетов; d – допуск (допустимая погрешность представления амплитуд).
Иллюстрация предсказывающего метода с линейной экстраполя-цией представлена на рис. 2.8. Здесь точками показаны предсказывае-мые значения сигнала. Если точка выходит за пределы “коридора” (допуска d), показанного пунктирными линиями, то происходит пере-дача отсчета. На рис. 2.8 передаваемые отсчеты отмечены темны-ми кружками в моменты времени t1,t2,t4,t7. Если передачи отсчета нет, то на приемном конце принимается экстраполированное значение.
Методы MPEG (Moving Pictures Experts Group) используют пред-сказывающее кодирование изображений (для сжатия данных о движу-щихся объектах вместе со звуком). Так, если передавать только изме-нившиеся во времени пиксели изображения, то достигается сжатие в несколько десятков раз. Методы MPEG становятся мировыми стандар-тами для цифрового телевидения.
Для сжатия данных об изображениях можно использовать также методы типа JPEG (Joint Photographic Expert Group), основанные на потере малосущественной информации (не различимые для глаза от-тенки кодируются одинаково, коды могут стать короче). В этих мето-дах передаваемая последовательность пикселей делится на блоки, в каждом блоке производится преобразование Фурье, устраняются вы-сокие частоты, передаются коэффициенты разложения для оставшихся частот, по ним в приемнике изображение восстанавливается.
Другой принцип воплощен в фрактальном кодировании, при ко-тором изображение, представленное совокупностью линий, описыва-ется уравнениями этих линий.
Более универсален широко применяемый метод Хаффмена, от-носящийся к статистическим методам сжатия. Идея метода - часто по-вторяющиеся символы нужно кодировать более короткими цепочками битов, чем цепочки редких символов. Недостаток метода заключается в необходимости знать вероятности символов. Если заранее они не известны, то требуются два подхода: на одном в передатчике подсчи-тываются вероятности, на другом эти вероятности и сжатый поток символов передаются к приемнику. Однако двухпроходность не всегда возможна.
Этот недостаток устраняется в однопроходных алгоритмах адап-тивного сжатия, в которых схема кодирования есть схема приспособ-ления к текущим особенностям передаваемого потока символов. По-скольку схема кодирования известна как кодеру, так и декодеру, сжа-тое сообщение будет восстановлено на приемном конце.
Обобщением этого способа является алгоритм, основанный на словаре сжатия данных. В нем происходит выделение и запоминание в словаре повторяющихся цепочек символов, которые кодируются це-почками меньшей длины.
Интересен алгоритм "стопка книг", в котором код символа равен его порядковому номеру в списке. Появление символа в кодируемом потоке вызывает его перемещение в начало списка. Очевидно, что час-то встречающиеся символы будут тяготеть к малым номерам, а они кодируются более короткими цепочками 1 и 0.
Кроме упомянутых алгоритмов сжатия существует ряд других ал-горитмов, например LZ- алгоритмы (алгоритмы Лемпеля-Зива). В LZ-алгоритме используется следующая идея: если в тексте сообщения по-является последовательность из двух ранее уже встречавшихся симво-лов, то эта последовательность объявляется новым символом, для нее назначается код, который при определенных условиях может быть значительно короче исходной последовательности. В дальнейшем в сжатом сообщении вместо исходной последовательности записывается назначенный код. При декодировании повторяются аналогичные дей¬ствия, и поэтому становятся известными последовательности символов для каждого кода.
|
|
| Комментарии |
| Добавить комментарий |
|
Пожалуйста залогиньтесь для добавления комментария.
|
| Рейтинги |
|
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
|
|
| Гость |
Вы не зарегистрированны? Нажмите здесь для регистрации.
Забыли пароль? Запросите новый здесь.
|
| Мини-чат | Вам необходимо залогиниться.
Нет присланных сообщений.
|
|
