- •Введение
- •1. Энтропия источников сообщений
- •1.1. Дискретные ансамбли и источники
- •1.2. Количество информации в дискретном сообщении. Энтропия ансамбля
- •1.3. Условная информация. Условная энтропия. Совместная энтропия дискретного источника
- •1.4. Энтропия дискретного стационарного источника на сообщение
- •1.5. Избыточность источника дискретных сообщений
- •1.6. Эффективное кодирование. Кодирование источника равномерными кодами
- •1.7. Высоковероятные множества постоянного дискретного источника
- •1.8. Энтропия источника без памяти как скорость создания информации
- •1.9. Избыточность источника непрерывных сигналов. Количество информации в непрерывном канале
- •1.10. Скорость передачи информации и пропускная способность в непрерывном канале
- •2. Кодирование информации
- •2.1. Неравномерное кодирование с однозначным декодированием
- •2.2. Оптимальные неравномерные двоичные коды
- •2.3. Кодирование для исправления ошибок: Основные положения
- •2.4. Постановка задачи кодирования
- •2.5. Прямая теорема о кодировании в канале с шумами
- •2.6. Обратная теорема кодирования
- •2.7. Основная теорема Шеннона, ограничение возможностей использования оптимального кодирования на практике
- •3. Коды, исправляющие ошибки
- •3.1. Блоковые и сверточные коды
- •3.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность
- •3.3. Линейные блоковые коды
- •3.4. Порождающая и проверочная матрицы. Кодирование с помощью матриц g и н
- •3.5. Декодирование по стандартной таблице
- •3.6. Циклические коды
- •3.7. Кодирующие устройства циклических кодов
- •3.8. Декодирование циклических кодов по синдрому
- •3.9. Мажоритарное декодирование
- •4. Энтропия в контексте защиты информации от помех при передаче по каналу связи
- •4.1. Меры искажения. Постановка задачи защиты информации от помех при передаче по каналу связи
- •4.2. Свойства функции скорость-искажение
- •4.3. Простые примеры вычисления функции скорость-искажение
- •4.4. Функция скорость-искажение для гауссовских последовательностей
- •4.5. Эпсилон-производительность источника
- •4.6. Дифференциальная энтропия
- •4.7. Свойства дифференциальной энтропии
- •4.8. Эпсилон - энтропия источника сообщений
- •4.9. Обратная теорема кодирования для дискретного постоянного источника при заданном критерии качества
- •4.10. Прямая теорема кодирования с заданным критерием качества
- •4.11. Аксиоматическое введение в теорию энтропии вероятностных схем
- •4.12. Энтропия и условная энтропия объединенной вероятностной схемы и их свойства
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
2.2. Оптимальные неравномерные двоичные коды
Описывается метод построения оптимальных однозначно декодируемых двоичных кодов (с минимальной средней длиной кодовых слов) для дискретных ансамблей {А,р(а)}.
В простом частном случае вероятности сообщений ансамбля могут быть целыми отрицательными степенями числа 2: p(ai) = 2-di, i = 1 ,...,К. Доказано , что оптимальный двоичный однозначно декодируемый код в этом случае имеет среднюю длину кодовых словd(A) = Н(А). В таком коде сообщению аi сопоставляется слово длины di= - logр(аi).
Следующий метод построения такого кода известен как метод Шеннона-Фано:
Подразделить множество сообщений на два равновероятных подмножества, произвольным образом переименовать подмножества. Для всех сообщений из 1-го подмножества положить первый символ 0, для второго подмножества — 1.
Каждое из подмножеств рассматривать как некоторое новое множество сообщений. Выполнить наj-м шаге,j = 2,3,..., действия, указанные в п. 1, для определенияj-го символа кодовых слов. Считать, что действия над данным подмножеством закончены, если оно содержит одно сообщение.
Кодирование методом Шеннона-Фано ансамбля из 9 сообщений с вероятностями 0,25; 0,125; 0,0625; 0,0625; 0,0625; 0,0625; 0,125; 0,125; 0,125 показано в табл. 2, в которой сделаны четыре последовательных шага кодирования в соответствии с указанном выше алгоритмом.
На рис. 3 представлено соответствующее кодовое дерево.
В общем случае, когда сообщения имеют произвольные вероятности, рассматривается метод построения оптимального префиксного кода, называемый методом Хаффмена. Здесь предполагается, что сообщения в ансамбле упорядочены, так чтоp(a1) ≥ р(а2) ≥ ... ≥ р(ак). В обосновании метода лежат три леммы.
В оптимальном коде слово, соответствующее наименее вероятному сообщению, имеет наибольшую длину.
Таблица 2.2
Сообщения |
Вероятности |
1-й шаг |
2-й шаг |
3-й шаг |
4-й шаг |
Кодовые слова |
a1 |
0,25 |
I |
I |
|
|
00 |
a2 |
0,125 |
II |
I |
|
010 |
|
a3 |
0,0625 |
II |
I |
0110 |
||
a4 |
0,0625 |
II |
0111 |
|||
a5 |
0,0625 |
II |
I II |
I |
I |
1000 |
a6 |
0,0625 |
II |
1001 |
|||
a7 |
0,125 |
II |
|
101 |
||
a8 |
0,125 |
II |
I |
|
110 |
|
a9 |
0,125 |
II |
|
111 |
2. В оптимальном двоичном префиксном коде два наименее вероятных сообщения кодируются словами одинаковой длины, одно из которых оканчивается нулем, а другое единицей.
Далее рассматривается новый ансамбль , состоящий из К - 1 сообщений с вероятностями
Любой префиксный код для ансамбля можно превратить в префиксный код для ансамбля А приписыванием к кодовому слову, кодирующему сообщение символов 0, 1 для получения слов, кодирующих сообщения Следующая лемма обосновывает последовательную процедуру кодирования.
Рис. 2.2
3. Если оптимален однозначно декодируемый префиксный код для ансамбля , то оптимален полученный из него префиксный код для ансамбля А.
Таким образом, задача построения оптимального кода сводится к задаче построения оптимального кода для ансамбля, содержащего на одно сообщение меньше. В этом ансамбле снова можно выделить два наименее вероятных сообщения и, объединяя их, получить новый ансамбль, содержащий теперь уже на два сообщения меньше, чем исходный. В итоге мы приходим к ансамблю, содержащему всего два слова, кодируемых символами 0 и 1.
Рассмотрим на примере ансамбля из 9 сообщений с вероятностями 0,2; 0,15; 0,15; 0,12; 0,1; 0,1; 0,08; 0,06; 0,04 кодирование методом Хаффмена. В табл. 3 показаны семь последовательных шагов, на каждом из которых происходит образование нового ансамбля с помощью склеивания наименее вероятных сообщений предыдущего ансамбля.
Таблица 2.3
Сообщения |
Вероятности |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Кодовое слово |
|
a1 |
0,20 |
|
10 |
||||||||
a2 |
0,15 |
001 |
|||||||||
a3 |
0,15 |
010 |
|||||||||
a4 |
0,12 |
011 |
|||||||||
a5 |
0,10 |
110 |
|||||||||
a6 |
0,10 |
111 |
|||||||||
a7 |
0,08 |
0001 |
|||||||||
a8 |
0,06 0,04 |
00000 |
|||||||||
a9 |
00001 |
Рис. 2.3
Алгоритм кодирования отражает в таблице и кодовое дерево. На рис. 2.3 дается его более наглядное представление.
Средняя длина кодового слова . Однозначно декодируемого кода с меньшей длиной не существует. При оптимальном кодировании минимальная длина кодового слова неравномерного кода равна энтропии источника сообщений, в данном случае равной