Тема реферату: "КОДИРОВАНИЕ"


1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ КОДИРОВАНИЯ


Оптимальным статистическим (экономным) кодированием называется кодирование, при котором обеспечивается распределение времени на передачу отдельных символов алфавита в зависимости от априорных вероятностей их появления:


; (1)


где Cп - пропускная способность канала; pi - априорная вероятность i –й кодовой комбинации; ti -длительность i-й кодовой комбинации.

Оптимальными неравномерными кодами (ОНК) - называются коды, в которых символы алфавита кодируются кодовыми словами минима-льной средней длины.

Принципы построения оптимальных кодов:

1. Каждая кодовая комбинация должна содержать максимальное количество информации, что обеспечивает максимальную скорость передачи данных.

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

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

Возможность однозначного декодирования неравномерного кода обеспечивается выполнением требования разделимости (префиксности) кодовых комбинаций.

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

Существует много методов оптимального, статистического кодирования. Наиболее часто используют оптимальное кодирование по методу Шеннона - Фано и Хаффмена.


2. КОД ШЕННОНА-ФАНО


Кодирование по методу Шеннона - Фано осуществляется следующим образом:

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

2. Дальнейшее построение кода производится методом последовательного деления пополам. Символы сообщения разбиваются на две группы с примерно равными вероятностями (т. к. при отсутствии статистической связи между символами скорость передачи максимальна при условии равной вероятности передачи символов). Если равной вероятности в подгруппах достичь нельзя, то желательно чтобы суммарная вероятность нижней подгруппы была больше верхней.

3. Всем символам верхней группы приписывается кодовый символ 1, а символам нижней - 0. Можно наоборот, т. к. для кодовой реализации безразлично 0 или 1, но с точки зрения мощности, лучше, если в кодовой комбинации меньше единиц.

4. Затем каждая подгруппа аналогичным образом разбивается на подгруппы по возможности с одинаковыми вероятностями. Разбиение осуществляется до тех пор, пока в каждой подгруппе останется по одному символу.

Пример построения кода приведен в таблице 1.


Таблица 1

ai

pi

Разбиение

Кодовая комбинация

Длина

a1

a2

a3

a4

1/2

1/4

1/8

1/8

}1

0 }1

0 }1

}0

1

01

001

000

 

2

3

3


Построенный код является префиксным.

Например: полученная кодовая последовательность 11100001 однозначно декодируется как:


1 1 1 000 1 01 => a1 a1 a1 a4 a1 a2 .

a1 a1 a1 a4 a1 a2


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

Средняя длина кодовой комбинации, при использовании двоичного кода в качестве вторичного, равна


, (2)


где li - длина i-й комбинации; N -основание первичного кода.

Эффективность ОНК максимальна при


; . (3)


Коэффициент относительной эффективности (коэффициент использования пропускной способности) равен


. (4)


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


. (5)


Для рассмотренного примера при длительности символа кодовой комбинации (0 или 1) равной  средняя длина и средняя длительность кодовой комбинации, соответственно равны:



Энтропия источника равна



При этом: Коэ = 1,75/1,75 = 1; Кcc = 2/1,75 = 1,14.

Скорость передачи информации


, (6)


т. е. коэффициент использования пропускной способности канала равен 1, а значит, имеет место идеальное использование канала (оптимальное статистическое кодирование).

Если подгруппы имеют не одинаковую суммарную вероятность, то коэффициент меньше 1. Для равномерного кода , при этом


.


Недостаток кода ОНК - низкая помехоустойчивость, т. к. потеря одного разряда может означать потерю символа.


3. КОД ХАФФМЕНА


Кодирование по методу Хаффмена осуществляется следующим об-разом:

1. Все подлежащие кодированию символы записываются в порядке убывания их априорных вероятностей. Если некоторые символы имеют одинаковые вероятности, то их располагают рядом в произвольном порядке.

2. Выбирают символы с минимальными вероятностями по 2 и одному приписывают 0, а другому 1.

3. Выбранные символы объединяют в промежуточные символы с суммарной вероятностью.

4. Снова находят пару символов с наименьшими вероятностями и поступают аналогично.

В таблице 2 приведен пример кодирования по методу Хаффмена для источника сообщений с заданными вероятностями символов алфавита:


x1 = 0,4; x2 = x5 = 0,2; x3 = 0,1; x4 = x6 = 0,05.


Таблица 2

Символ

pi

Граф кода Хаффмена

Код

x1


x2


x5


x 3


x 4


x 6

0,4


0,2


0,2


0,1


0,05


0,05

1

(1,0)

1 0

(0,6)

1 0

(0,4)

1 0

(0,2)

1 0

(0,1)

0

1


01


001


0001


00001


00000



Энтропия источника равна



Средняя длина кодовой комбинации данного кода



Длина кодовой комбинации примитивного кода определяется соотношением


(7)


Округляя до ближайшего целого в большую сторону, получим l = 3.

Эффективность ОНК максимальна, если .

Коэффициент относительной эффективности равен


.


Коэффициент статистического сжатия равен


.


Неравномерный код можно передавать блоками заданной длины, а на приемной стороне декодировать всю последовательность.

Пример 1. Построить оптимальные неравномерные коды (ОНК) по методу Шеннона-Фано и по методу Хаффмена для передачи сообщений, в которых вероятности символов первичного алфавита равны:


p(a1) =0,1; p(a2) =0,07; p(a3) =0,02; p(a4) =0,17;

p(a5) =0,42; p(a6) =0,09; p(a7) =0,08; p(a8) =0,05.


Оценить эффективность каждого кода, т. е. насколько они близки к оптимальным. Определить емкость (пропускную способность) канала связи для каждого кода, если скорость передачи двоичных символов (V = 1/) равна 1000 симв/с, т.е. время передачи одного символа вторичного алфавита (двоичного символа) равна  = 0,001с = 1мкс.

Решение: Построим код по методу Шеннона-Фано, используя сле-дующий алгоритм:

1. Символы сообщения располагаем в порядке убывания их априорных вероятностей.

2. Исходный ансамбль кодируемых символов разбиваем на две группы с примерно равными вероятностями (лучше, если суммарная вероятность верхней группы меньше).

3. Верхней группе присваиваем символ 1, а нижней 0.

4. Процесс деления повторяем до тех пор, пока в каждой подгруппе останется по одному символу.

Процесс построения кода приведем в таблице 3.


Таблица 3

ai

p(ai)

Разбиение

Код

li

pili


a5

a4

a1

a6

a7

a2

a8

a3

0,42

0,17

0,10

0,09

0,08

0,07

0,05

0,02

}0

1 0 }0

}1

1 0 }0

}1

1 }0

}0

}1

0

100

101

1100

1101

1110

11110

11111

1

3

3

4

4

4

5

5

0,42

0,51

0,3

0,36

0,32

0,28

0,25

0,1


Случайные файлы

Файл
10004-1.rtf
79229.rtf
2095.rtf
183579.rtf
141835.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.