Лекция 1: «кодирование сигналов»

1.1 ОСНОВНЫЕ ПОНЯТИЯ

Кодирование – преобразование элементов дискретного сообщения в последовательности кодовых символов. Обратное преобразование – декодирование.

Устройства, осуществляющие эти операции автоматически, называются соответственно кодером и декодером. Кодек – устройство, объединяющее кодер и декодер.

Код – алгоритм (правило), по которому осуществляется кодирование.

Кодовая комбинация (слово) – последовательность кодовых символов, соответствующая одному элементу дискретного сообщения.

Кодовый алфавит – весь набор кодовых символов.

Основание кода m – число символов в кодовом алфавите. Если m=2 код называется двоичным, m>2 – многопозиционным (недвоичным).

Разряд – значащая позиция кодового слова.

Разрядность (значность) кода n – число символов в кодовой комбинации. Если n=const, то код называется равномерным, n≠const – неравномерным.

Кодеры и декодеры легче сделать для равномерных двоичных кодов.

1.2 СИСТЕМА ПЕРЕДАЧИ ДИСКРЕТНЫХ СООБЩЕНИЙ

Рисунок 1.1 – Структурная схема системы передачи дискретных сообщений.

Источник выдает дискретное сообщение. Для формирования дискретного сообщения из непрерывного используется дискретизация по времени и по уровню.

Кодирование источника (сжатие данных) применяется для снижения технических затрат на хранение и передачу информации.

Криптографическое кодирование (шифрование) применяется для предотвращения несанкционированного доступа к информации.

Кодирование канала (помехоустойчивое кодирование) применяется для повышения достоверности передачи информации по каналу с помехами.

1.3 СЖАТИЕ ДАННЫХ

Сжатие возможно, т.к. данные на выходе источника содержат избыточную и/или плохо различимую информацию.

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

Приемы, применяемые в алгоритмах сжатия с потерями:

- использование модели – подбор параметров модели и передача только одних параметров;

- предсказание – предсказание последующего элемента и передача величины ошибки;

- дифференциальное кодирование – передача изменений последующего элемента при сравнении с предыдущим.

Избыточная информация – информация, которая не добавляет знаний о предмете. Избыточность может быть уменьшена или устранена с помощью сжатия без потерь (эффективного кодирования). При этом энтропия данных остается неизменной. Сжатие без потерь применяется в системах передачи данных.

Приемы, применяемые в алгоритмах сжатия без потерь:

- кодирование длин последовательностей – передача числа повторяющихся элементов;

- кодирование словаря – использование ссылок на переданные ранее последовательности, а не их повторение;

- неравномерное кодирование – более вероятным символам присваиваются более короткие кодовые слова.

1.4 КОДИРОВАНИЕ СЛОВАРЯ

Позволяет уменьшить избыточность, вызванную зависимостью между символами. Идея кодирования словаря состоит в замене часто встречающихся последовательностей символов ссылками на образцы, хранящиеся в специально создаваемой таблице (словаре). Данный подход основан на алгоритме LZ, описанном в работах израильских исследователей Зива и Лемпеля.

1.5 НЕРАВНОМЕРНОЕ КОДИРОВАНИЕ

Позволяет уменьшить избыточность, вызванную неравной вероятностью символов. Идея неравномерного кодирования состоит в использовании коротких кодовых слов для часто встречающихся символов и длинных – для редко возникающих. Данный подход основан на алгоритмах Шеннона-Фано и Хаффмана.

Коды Шеннона-Фано и Хаффмана являются префиксными. Префиксный код – код, обладающий тем свойством, что никакое более короткое слово не является началом (префиксом) другого более длинного слова. Такой код всегда однозначно декодируем. Обратное неверно.

Код Шеннона-Фано строится следующим образом. Символы источника выписываются в порядке убывания вероятностей (частот) их появления. Затем эти символы разбиваются на две части, верхнюю и нижнюю, так, чтобы суммарные вероятности этих частей были по возможности одинаковыми. Для символов верхней части в качестве первого символа кодового слова используется 1, а нижней – 0. Затем каждая из этих частей делится еще раз пополам и записывается второй символ кодового слова. Процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному символу.

Пример1.1:

Таблица 1.1 – Построение кода Шеннона-Фано.

Символ	Вероятность	Этапы разбиения					Код
		1	2	3	4
а1 а2 а3 а4 а5	0,40 0,35 0,10 0,10 0,05	1				1 01 001 0001 0000
		0 0 0 0	1
			0 0 0	1
				0 0	1
					0

Алгоритм Шеннона-Фано не всегда приводит к построению однозначного кода с наименьшей средней длиной кодового слова. От отмеченных недостатков свободен алгоритм Хаффмана.

Код Хаффмана строится следующим образом. Символы источника располагают в порядке убывания вероятностей (частот) их появления. Два самых последних символа объединяют в один вспомогательный, которому приписывают суммарную вероятность. Полученные символы вновь располагают в порядке убывания вероятностей, а два последних объединяют. Процесс продолжается до тех пор, пока не останется единственный вспомогательный символ с вероятностью 1. Для нахождения кодовых комбинаций строится кодовое дерево. Из точки, соответствующей вероятности 1, направляются две ветви. Ветви с большей вероятностью присваивается символ 1, с меньшей – 0. Такое ветвление продолжается до достижения вероятности каждого символа. Двигаясь по кодовому дереву сверху вниз, записывают для каждого символа кодовую комбинацию.

Пример1.2:

Таблица 1.2 – Построение кода Хаффмана.

Символ	Вероятность	Объединение символов					Код
а1 а2 а3 а4 а5	0,40 0,35 0,10 0,10 0,05	0,40 0,35 0,15 0,10	0,40 0,35 0,25	0,60 0,40	1,00	0 11 100 1011 1010

Рисунок 1.2 – Кодовое дерево для кода Хаффмана.