- •Основы теории цифровой связи Часть 1 кодирование информации
- •1. Введение
- •1.1. Модель радиотехнической системы связи
- •Контрольные вопросы
- •1.2. Статистическая трактовка процесса передачи информации
- •Контрольные вопросы
- •1.3. Основные понятия и элементы математического аппарата теории связи
- •1.3.1. Сигналы и помехи
- •1.3.2. Разложение сигнала по системе ортогональных функций. Спектр сигнала
- •1.3.3. Cвойства преобразования Фурье
- •1.3.4. Корреляционная функция сигнала
- •1.3.5. Связь между корреляционной функцией и спектром сигнала
- •1.3.6. Случайные сигналы и их характеристики
- •Контрольные вопросы
- •1.4. Источники информации
- •1.5. Теорема дискретизации
- •1.6. Дискретизация изображений
- •Контрольные вопросы
- •1.7. Квантование. Ошибки квантования
- •Контрольные вопросы
- •1.8. Количество информации, содержащейся в сообщении
- •1.8.1. Энтропия сложных сообщений, избыточность источника
- •Контрольные вопросы и задачи
- •2. Основы экономного кодирования информации
- •2.1. Способы представления кодов
- •Контрольные вопросы и задачи
- •2.2. Типы систем сжатия
- •X Квантователь Xq Кодер без потерь информации b (Xq) Декодер X*
- •Методы кодирования без потерь
- •2.3.1. Понятие префиксного множества
- •2.3.2. Алгоритм кодирования Хаффмена
- •2.3.3. Алгоритм Шеннона–Фано
- •2.3.4. Блочные коды
- •2.3.5. Арифметическое кодирование
- •2.3.6. Словарное кодирование. Метод Зива–Лемпеля
- •2.3.7. Кодирование длин повторений (rle)
- •2.3.8. Дифференциальное кодирование
- •Контрольные вопросы и задачи
- •2.4. Методы сжатия с потерей информации
- •2.4.1. Функции “скорость–искажение” и “искажение–скорость”
- •2.5. Сжатие речевых сигналов
- •2.5.1. Кодирование формы сигнала, икм
- •2.5.2. Дифференциальная икм
- •2.5.3. Адаптивная дифференциальная икм (адикм)
- •2.5.4. Дельта-модуляция
- •2.5.5. Другие методы кодирования формы сигнала
- •2.5.6. Кодирование источника
- •2.5.7. Гибридные методы кодирования речи
- •2.5.8. Полноскоростной кодер rpe-ltp (стандарт gsm 06.10)
- •2.5.9. Кодер vselp (стандарт d-amps)
- •Контрольные вопросы и задачи
- •2.6. Кодирование изображений. Стандарт сжатия jpeg
- •Процедуру дкп можно записать в матричной форме:
- •2.6.1. Рекурсивный (вэйвлет) алгоритм
- •2.7. Сжатие подвижных изображений (видео)
- •3. Основы помехоустойчивого кодирования
- •3.1. Основные принципы. Типы кодов
- •3.2. Линейные блочные коды
- •3.2.1. Код с проверкой на четность
- •3.2.2. Итеративный код
- •3.2.3. Порождающая матрица линейного блочного кода
- •3.2.4. Проверочная матрица
- •3.2.5. Дуальные коды
- •3.2.6. Синдром и обнаружение ошибок
- •3.2.7. Синдромное декодирование линейных блочных кодов
- •3.2.8. Мажоритарное декодирование линейных блочных кодов
- •3.2.9. Декодирование методом максимального правдоподобия
- •Поскольку
- •Если принятый сигнал дискретизован и Si – I-й отсчет принятого сигнала.
- •3.2.10. Вес и расстояние Хемминга. Способность кодов обнаруживать и исправлять ошибки
- •Контрольные вопросы и задачи
- •3.3. Полиномиальные коды
- •3.3.1. Циклические коды
- •3.3.2. Кодирование с использованием циклических кодов
- •3.3.3. Вычисление синдрома и исправление ошибок в циклических кодах
- •3.3.4. Неалгебраические методы декодирования циклических кодов
- •3.4. Сверточные коды
- •3.4.1. Кодирование с использованием сверточных кодов
- •3.4.2. Синдромное декодирование сверточных кодов
- •3.4.3. Кодовое дерево и решетчатая диаграмма
- •3.4.4. Декодирование сверточных кодов. Алгоритм Витерби
- •3.4.5. Алгоритмы поиска по решетке
- •Контрольные вопросы и задачи
- •3.5. Применение корректирующего кодирования в системах связи
- •3.5.1. Каскадные коды
- •3.5.2. Кодирование с перемежением
- •Библиографический список
- •Часть 1 1
2.6.1. Рекурсивный (вэйвлет) алгоритм
Английское название рекурсивного сжатия — wavelet. На русский язык оно переводится как волновое сжатие и как сжатие с использованием всплесков. Этот вид архивации известен довольно давно и напрямую исходит из идеи использования когерентности областей. Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами, идеален для картинок типа рентгеновских снимков. Коэффициент сжатия задается и варьируется в пределах 5…100. При попытке задать больший коэффициент на резких границах, особенно проходящих по диагонали, проявляется “лестничный эффект” – ступеньки разной яркости размером в несколько пикселов.
Идея алгоритма заключается в том, что вместо кодирования собственно изображений сохраняется разница между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к нулю. Так, два числа a2i и a2i+1 всегда можно представить в виде b i 1 = (a2i + a2i+1)/2 и b i 2 = = (a2i – a2i+1)/2. Аналогично последовательность ai может быть попарно переведена в последовательность b i 1,2.
Рассмотрим пример. Пусть нужно сжать строку из восьми значений яркости пикселов (ai): (220, 211, 212, 218, 217, 214, 210, 202). Получим следующие последовательности b1i, и b2i: полусуммы – (215.5, 215, 215.5, 206) и полуразности – (4.5, – 3, 1.5, 4). Заметим, что значения b2i достаточно близки к 0. Повторим операцию, рассматривая b1i как ai. Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Из (215.5, 215, 215.5, 206) получим (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана, можно считать результатом кодирования. Заметим, что преобразование применялось к цепочке цифр только два раза. Реально же можно применять wavelet-преобразование 4 – 6 раз, что позволит достичь заметных коэффициентов сжатия.
Алгоритм для двумерных данных реализуется аналогично.
Если имеется квадрат из четырех точек с яркостями a2i ,2j , a2i+1 , a 2j, a2i ,2j+1 , и a2i+1 , a 2j+1 , то
(2.39)
Используя эти формулы для изображения 512 х 512 пикселов, получим после первого преобразования уже четыре матрицы размером 256 х 256 элементов (рис. 2.35, 2.36)
Исходное изображение |
B1 |
B2 |
B3 |
B4 |
Рис. 2.35 Рис. 2.36
В первой матрице, как легко догадаться, хранится уменьшенная по размеру копия изображения, во второй – усредненные разности пар значений пикселов по горизонтали, в третьей – усредненные разности пар значений пикселов по вертикали, в четвертой – усредненные разности значений пикселов по диагонали изображения.
По аналогии с двумерным случаем можно повторить преобразование и получить вместо первой матрицы четыре матрицы размером 128 х 128. Применять операцию к трем остальным (уже разностным) матрицам особого смысла нет, поскольку абсолютные значения разностей уже и так малы.
Повторив преобразование в третий раз, получим в итоге набор из четырех матриц 64 х 64, трех матриц 128 х 128 и трех – 256 х 256 и т.д. Дальнейшее сжатие происходит за счет того, что в разностных матрицах имеется большое количество нулевых или близких к нулю значений, которые после квантования эффективно сжимаются.
К преимуществам этого алгоритма можно отнести то, что он очень легко позволяет реализовать возможность постепенного “проявления” изображения при передаче изображений, например, по Интернету. Сначала появляется растянутая до исходного размера картинка, полученная из уменьшенной копии, а затем ее четкость постепенно возрастает по мере приема и добавления к ней результатов декодирования очередных блоков. В отличие от JPEG данный метод работает с блоками 2 х 2, 4 х 4, 8 х 8 и т.д. За счет того, что коэффициенты для этих блоков сохраняются независимо, легко избежать дробления изображения на “мозаичные” квадраты.
