2. Кодер источника сообщений, модулированные

сигналы, модели помех в каналах связи

(2010г.)

2.1. Кодирование (сжатие) сообщений в кодере источника

2.1.1 .Виды сообщений.

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

Возможные мгновенные значения реализаций непрерывных сообщений определяют диапазон значений

, D_dб=20 lg(х_max / х_min) (2.1)

Дискретными называются сообщения, образованные из отдельных элементов (символов, импульсов и т.д.), каждый из которых может принимать конечное число М различных значений. Число М определяет размер алфавита сообщения. Двоичный алфавит М=2 состоит из двух элементов 0 и 1.

Дискретный источник без памяти (ДИБП) - это модель дискретного источника сообщений, на выходе которого последовательность символов статистически независима.

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

Значение каждой дискретной или квантованной выборки источника с алфавитом М может быть представлено кодовым словом фиксированной длины в q-ичной системе счисления

,

где q - основание системы счисления (q ³ 2);

п - число разрядов в слове,

g_i - весовой коэффициент, принимающий целое значение в интервале 0£ g_i £ q-1.

При двоичной системе (q=2) значениями g_i являются 0 или 1 и на выходе кодера получим двоичные кодовые комбинации.

Пример: M=17, q=2. Необходимое число разрядов п = log₂M=4,…;

берут избыточное целое п = 5, тогда

M = 17 = γ₅·2⁴ +γ₄·2³+γ₃·2² +γ₂·2¹+γ₁·2⁰,

где γ₅ =γ₁ =1, а остальные 0.

Рассмотрим более эффективные со сжатием методы кодирования ДИБП.

2.1.2. Кодирование (сжатие) сообщений дибп

Методы сжатия сообщений базируются на положениях теории информации.

Основные определения и положения теории информации.

Количественно информация измеряется величиной

,

где Р(а_i) -вероятность выдачи источником сообщения а_i из ансамбля А, i=1,2… М; М -алфавит сообщений ансамбля А.

Чем меньше Р(а), тем больше i(a).

Полученную при этом единицу информации в сообщении, появившемся с вероятностью Р(а)=1/2, называют:

- двоичной единицей или бит при основании логарифма 2;

- нат при основании логарифма е, которая в log₂ е≈1,443 раза больше двоичной.

Качество источника сообщения определяется энтропией источника, которая равна математическому ожиданию количества информации по всему ансамблю сообщений А:

(2.2)

При этом должны учитываться все вероятностные связи между зависимыми сообщениями а_i ансамбля А.

Энтропия ДИБП с алфавитом М согласно (2.2) определена формулой:

(2.3)

,

которая для равновероятных а_i равна значению log₂ М.

С войства энтропии.

1.Энтропия неотрицательна, равна нулю для достоверного сообщения Р(а)=1.

2. Энтропия аддитивна, т.е. энтропия «укрупненного» из k исходных сообщений источника в k раз больше энтропии исходного источника.

3.Для ансамбля сообщений А с алфавитом М известно неравенство

. (2.4)

Равенство имеет место при равновероятных и независимых сообщениях, в частности, для двоичного ДИБП энтропия максимальна при равновероятных Р(а₁)= Р(а₂)=0,5 и равна Н(А)=log₂2=1 бит.

Чем больше энтропия источника, тем более неопределенным является ожидаемое сообщение. Поэтому энтропию часто называют мерой неопределенности сообщений.

Энтропия источника зависимых сообщений всегда меньше энтропии источника независимых сообщений при прочих равных условиях.

Поэтому источник сообщений с объемом алфавита М характеризуется избыточностью

, (2.5)

которая показывает, какая доля от максимально возможной при данном М не используется источником. Поэтому при кодировании источника надо стремиться к максимуму энтропии ансамбля кодовых слов a_k(t_i) на выходе кодера источника (см. рис.1.1), т.е. их независимости и равной вероятности.

Производительность (бит за секунду) источника с фиксированной скоростью передачи определяется выражением

Н'(А)=Н(А)/ Т_с=1/Т_б , (2.6)

где Т_с - время на передачу сообщения с энтропией Н(А).

В развитие свойства 2 энтропия укрупненного источника А^[k]равна

. (2.7)

При этом доказана асимптотическая равная вероятность типичных k-последовательностей укрупненного источника А^[k].

Поэтому объемом алфавита укрупненного источника согласно (2.4)

. (2.8)

а) Блоковое кодирование ДИБП двоичным словом фиксированной длины.

При алфавите М ДИБП число двоичных символов n кодового слова кодера источника на один символ источника требуется:

- при M=2ⁿ целой степени 2

,

- при М не целой степени 2

, (2.9)

т.е. как и в приведенном выше примере избыточно.

Величину n называют скоростью R кодирования, т.е. числом символов кодера на один символ источника сообщения.

Поскольку на основании (2.4)

.

Эффективность блокового кодирования определяется отношением

β_к=Н(А)/R ≤ 1 (2.10)

Если М целая степень 2 и символы источника равновероятны, то β_к=1 и кодирование эффективно. Если М не целая степень 2, а символы равновероятны и М мало, то эффективность кодирования согласно (2.9) существенно уменьшается.

Однако, если кодировать k символов источника за время kТ, то получим согласно (2.8) источник с укрупненным алфавитом М_у=M^k, которому должны сопоставить в кодере кодовые слова длиной

N ≥ log.₂М_{у .} Следовательно, согласно (2.9.) максимальное значение длины N двоичных кодовых слов кодера укрупненного источника:

.

В этом случае среднее число символов кодера на символ источника (скорость кодирования) уменьшается и равно

Т.о. эффективность кодирования (2.10) укрупненного источника растет по сравнению с посимвольным кодированием за счет уменьшения знаменателя и увеличения числителя (на основании асимптотической равной вероятности типичных k-последовательностей укрупненного источника). Такое кодирование называют бесшумным (однозначным), позволяющим избыточность (2.5) источника свести к нулю и повысить скорость передачи информации.

б) Кодирование (сжатие) ДИБП кодовым словом переменной

длины (энтропийное кодирование)

Если символы источника не равновероятны, то более эффективным посимвольным кодированием является так называемое энтропийное кодирование, при котором более вероятным символам источника соответствуют более короткие кодовые слова.

Однако, при таком кодировании возможны ситуации, когда более короткие кодовые слова могут совпадать с началом более длинных слов. Это может привести к неоднозначности при немедленном декодировании или необходимой задержке для однозначного декодирования. Эти недостатки отсутствуют в коде, удовлетворяющем условию префиксности:

-для данного слова С_k длины k с элементами (b_1,b_2… b_k ) не должно существовать других кодовых слов длины l<k с элементами (b_1,b₂ b_l) для 1≤l≤k-1.

Это условие реализует алгоритм кодирования Хаффмeна, основанный на знании априорных вероятностей символов и кодировании согласно двоичному кодовому дереву.

Алгоритм кодирования Хаффмана минимизирует среднее число бит кодера на символ источника

(2.11)

Алгоритм для М=7 представлен совместно с исходными данными на рис.2.1.

рис.2.1

Символы x_i источника упорядочены в порядке убывания вероятностей. Процесс кодирования начинается с двух наименее вероятных символов х₆ и х₇. Эти два символа объединяем в узел, причем верхнему ветвлению узла присваивается «0», а нижнему «1». Вероятности этих двух ветвей складываются и общему узлу присваивается суммарная вероятность, равная в данном случае 0,01. Теперь мы имеем исходные символы х_{1 ,} х₅ плюс новый символ, полученный объединением х₆ и х₇, обозначим его х^'₆. На следующем шаге снова объединяются два наименее вероятных символа из набора х₁ х_2, х^'₆ и т.д. Эта процедура продолжается, пока не будут исчерпаны все символы источника.

В результате получим кодовое дерево с ветвями, которое содержит кодовые слова, которые надо читать справа налево от правого узла дерева. Скорость кодирования равна бит/симв. при энтропии источника сообщения Н(х)=2,11 бит/симв.