- •Основы теории цифровой связи Часть 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.3.1. Понятие префиксного множества
Префиксным множеством S называется такое множество двоичных последовательностей, в котором ни одна последовательность не является префиксом или началом другой последовательности.
Например, множество двоичных слов S1 = {00, 01, 100, 110, 1010, 1011} является префиксным, поскольку если проверить любую совместную комбинацию (wi wj), то видно, что wi никогда не явится префиксом (началом) wj.
С другой стороны, множество S2 = { 00, 001, 1110 } не является префиксным, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества 001.
Для префиксных множеств вводится понятие вектора Крафта: если S = = { w1, w2, ... , wk } – префиксное множество, то вектор v(S) = ( L1, L2, ..., Lk ), состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей, называется вектором Крафта. Для него справедливо следующее условие, называемое неравенством Крафта:
.
(2.7)
Если неравенство (2.7) переходит в строгое равенство, то код называется компактным и обладает наименьшей среди кодов с данным алфавитом длиной, то есть является оптимальным.
Ниже приведены примеры простейших префиксных множеств и соответствующие им векторы Крафта:
S1 = {0, 10, 11} и v(S1) = ( 1, 2, 2 );
S2 = {0, 10, 110, 111} и v(S2) = ( 1, 2, 3, 3 );
S3 = {0, 10, 110, 1110, 1111} и v(S3) = ( 1, 2, 3, 4, 4 );
S4 = {0, 10, 1100, 1101, 1110, 1111} и v(S4) = ( 1, 2, 4, 4, 4, 4 );
S5 = {0, 10, 1100, 1101, 1110, 11110, 11111} и v(S5) = (1, 2, 4, 4, 4, 5, 5);
S6 = {0, 10, 1100, 1101, 1110, 11110, 111110, 111111}
и v(S6) = (1,2,4,4,4,5,6,6).
Формирование префиксных множеств и работа с ними – это отдельная тема из теории множеств, выходящая за рамки данного курса, однако один простейший пример будет рассмотрен.
2.3.2. Алгоритм кодирования Хаффмена
Алгоритм Хаффмена, названный в честь его изобретателя Дэвида Хаффмена, предлагает простой и эффективный способ кодирования, обеспечивающий получение оптимального вектора Крафта. Код, полученный с использованием этого алгоритма, называют кодом Хаффмена.
Предположим, нужно закодировать сообщение со следующим словарем символов:
A B C D E
10 5 8 13 10
Здесь под каждой буквой словаря указано, сколько раз эта буква встречалась в тексте сообщения.
Алгоритм Хаффмена работает следующим образом.
1. Выписываем в ряд все символы (буквы) алфавита в порядке возрастания или убывания вероятности их появления в тексте:
B C A E D
5 8 10 10 13
2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагаем равной сумме вероятностей составляющих его символов:
A E BC D
10 10 13 13
BC D AE
13 13 20
AE BCD
20 26
AEBCD
46
3. Строим кодовое дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него (рис. 2.5).
Рис. 2.5
4. Прослеживаем путь от корня к каждому листу (вершине) дерева, помечая направление к каждому узлу: направо 1, налево 0. Полученная последовательность дает кодовое слово, соответствующее каждому символу.
Ветеран энтропийного кодирования алгоритм Хаффмена и сегодня очень широко используется в системах сжатия. Так, данный алгоритм является частью стандарта сжатия изображений JPEG и используется в компьютерных архиваторах PKZIP, LHA и др.
Алгоритм кодирования по Хаффмену обладает тем важным свойством, что кодовые слова, полученные с его использованием обладают префиксным свойством, а их длина минимальна. Недостатком этого алгоритма является необходимость предварительного вычисления вероятностей символов источника, то есть его статистический анализ. Процедура кодирования при этом становится двухпроходной. Сначала данные просматриваются и подсчитываются вероятности всех символов в кодируемом сообщении, а затем производится собственно кодирование.
