Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Эффективное кодирование
|
|
Для эффективного кодирования для канала без помех необходимо минимизировать среднее число символов, требующихся для выражения одного элемента сообщения. Это, при отсутствии шума, позволяет уменьшить время передачи или объем ЗУ.
Для случая отсутствия статистической взаимосвязи между элементами методы построения эффективных кодов были даны впервые американскими учеными Шенноном и Фано. Код, построенный по их методике, называется кодом Шеннона-Фано.
Код строят следующим образом: элементы сообщений выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковыми. Всем элементам верхней половины в качестве первого символа приписывают 1, а всем нижним-0. Каждую из полученных групп, в свою очередь, разбивают на две подгруппы с одинаковыми суммарными вероятностями и т.д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному элементу.
Проведем эффективное кодирование сообщения из восьми элементов, характеристики которого представлены в таблице 16.3.
Таблица 16.3. Кодирование по Шеннону-Фано
| элементы сообщения | вероятности | этапы разбиения | кодовые комбинации | ||||
| I | II | III | IV | V | |||
| X1 | 0, 22 | 1 1 | |||||
| X2 | 0, 20 | 1 0 | |||||
| X3 | 0, 16 | 0 1 1 | |||||
| X4 | 0, 16 | 0 1 0 | |||||
| X5 | 0, 10 | 0 0 1 | |||||
| X6 | 0, 10 | 0 0 0 1 | |||||
| X7 | 0, 04 | 0 0 0 0 1 | |||||
| X8 | 0, 02 | 0 0 0 0 0 |
Методика дает неоднозначное построение кода, ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппы.
При обычном (не учитывающем статистических характеристик) кодировании для представления каждого элемента требуется три двоичных символа.
С учетом статистических характеристик среднее число двоичных символов на элемент n
Алгоритм кодирования Шеннона-Фано имеет простую графическую иллюстрацию в виде кодового дерева (рис. 16.3)
Рис. 16.3. Кодовое дерево кода Шеннона-Фано
Методика, предложенная Хаффменом в 1952 г., гарантирует однозначное построение кода с наименьшим, для данного распреления вероятностей, средним числом символов на элемент сообщения.
Порядок построения кода Хаффмена следующий: элементы сообщения выписываются в столбец в порядке убывания вероятностей. Два последних элемента объединяют в один вспомогательный, которому приписывают суммарную вероятность. Вероятности элементов, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнитеьном столбце, а два последних объединяются. Процесс продолжается до тех пор, пока не получим единственный вспомогательный элемент с вероятностью, равной единице (табл.16.4).
Осуществим эффективное кодирование элементов сообщения, приведенного в таблице 16.4
Таблица 16.4. Кодирование по Хаффмену
| элементы | вероятности | вспомогательные столбцы | ||||||
 X1
| 0, 22 | 0, 22 | 0, 22 | 0, 26 | 0, 32 | 0, 42 | 0, 58 | 1, 0 |
 X2
| 0, 20 | 0, 20 | 0, 20 | 0, 22 | 0, 26 | 0, 32 | 0, 42 | |
| X3 | 0, 16 | 0, 16 | 0, 16 | 0, 20 | 0, 22 | 0, 26 | ||
 X4
| 0, 16 | 0, 16 | 0, 16 | 0, 16 | 0, 20 | |||
 X5
| 0, 10 | 0, 10 | 0, 16 | 0, 16 | ||||
 X6
| 0, 10 | 0, 10 | 0, 10 | |||||
 X7
| 0, 04 | 0, 06 | ||||||
| X8 | 0, 02 |
Для наглядности строим кодовое дерево (рис.16.4). Из точки, соответствующей вероятности 1, 0, направляем две ветви, причем ветви с большей вероятностью присваиваем символ 1, а с меньшей – 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до вероятности каждого элемента.
Рис. 16.4.Кодовое дерево кода Хаффмена
Теперь, двигаясь по кодовому дереву снизу вверх, можно записать для каждого элемента сообщения соответствующий код.
x1 x2 x3 x4 x5 x6 x7 x8
01 00 111 110 100 1011 10101 10100
Таким образом, эффект связан с различием в числе символов кодовых комбинаций. А это приводит к трудностям при декодировании. Эффективный код необходимо строить так, чтобы ни одна комбинация кода не совпадала с началом (префиксом) более длинной комбинации. Коды, удовлетворяющие этому условию, называют префиксными кодами.
Например, для комбинаций префиксного кода
x1 x2 x3 x4
00 01 101 100
последовательность комбинаций 1000001101101101100 декодируется однозначно
100 00 01 101 101 101 100
x4 x1 x2 x3 x3 x3 x4,
а для комбинаций непрефиксного кода
00 01 101 010
x1 x2 x3 x4
последовательность 000101010101 декодируется неоднозначно
00 01 01 01 010 101
x1 x2 x2 x2 x4 x3
00 010 101 010 101
x1 x4 x3 x4 x3
00 01 010 101 01 01
x1 x2 x4 x3 x2 x2
Лекция 17. Кодирование информации при передаче по дискретному каналу с помехами.
План:
1. Помехоустойчивое кодирование
2. Основные принципы помехоустойчивого кодирования
3. Связь корректирующей способности кода с кодовым расстоянием
4. Построение кодов с заданной исправляющей способностью
|
|