Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ»
Кафедра МСИБ
Методическая разработка к лабораторной работе № 60
СОПРЯЖЕНИЕ ИСТОЧНИКА ИЗБЫТОЧНЫХ
ДИСКРЕТНЫХ СООБЩЕНИЙ С ДИСКРЕТНЫМ
КАНАЛОМ (ЭФФЕКТИВНОЕ КОДИРОВАНИЕ)
Составитель: к.т.н., доц. Крыжановский А.В.
Редактор: к.т.н., доц. Казаченко Ю.М.
Рецензент: к.т.н., доц. Соколов В.Ф.
САМАРА
2011
Цель работы
Изучить особенности и методы построения эффективных кодов и расчет их характеристик с использованием ПЭВМ.
Рекомендуемые источники
Подготовка к работе
Контрольные вопросы
Содержание работы
Содержание отчета
Отчет должен содержать:
Методические указания к выполнению работы
Лабораторная работа выполняется на ПЭВМ в диалоговом режиме. После ввода программы в память ЭВМ все необходимые указания, вопросы и пояснения выводятся на дисплей.
Перед выполнением лабораторной работы на экране дисплея выводится ее название и текст «Нажмите пробел». После этого нужно ввести номер варианта, который совпадает с номером бригады. После ввода числа здесь и в дальнейшем, если не оговорено особо, нужно нажать клавишу «Enter». После этого ЭВМ задает контрольные вопросы и принимает решение о допуске к работе. Для допуска к работе допускается совершить не более трех ошибок. В случае возникновения конфликта между ЭВМ и студентом он может быть разрешен преподавателем.
В соответствии с выбранным вариантом ЭВМ устанавливает значения вероятностей букв первичного алфавита, сведенные в таблицу. Необходимо произвести кодирование и заполнить таблицу. Перед заполнением таблицы следует убедиться, что сумма вероятностей букв первичного алфавита равна 1.
Во избежание чрезмерного количества ошибок и, как следствие, конфликтов с ЭВМ, предлагается вначале заполнить таблицу без привлечения ЭВМ по методике, изложенной на с. 5-6 настоящей методической разработки (Табл. 1). Затем правильность заполнения таблицы проверяется на ЭВМ, при этом следует пользоваться клавишами «1», «0», «-», клавишу «Enter» в данном случае нажимать не следует.
Как и в предыдущем пункте ЭВМ устанавливает значения вероятностей букв первичного алфавита. Рекомендуется предварительно заполнить предлагаемую таблицу вручную по методике, изложенной на с. 5-6 настоящей методической разработки (Табл. 2). Правильность заполнения таблицы проверяется на ЭВМ, при этом после ввода каждого численного значения следует нажимать клавишу «Enter».
По заполненной таблице строится кодовое дерево (Табл. 3).
Требуется рассчитать на микрокалькуляторе численные значения следующих характеристик эффективного кода: средней длины кодовой комбинации – формула (1), энтропии источника дискретных сообщений – формула (3), коэффициента статистического сжатия – формула (7), коэффициента относительной эффективности – формула (8).
Рассчитанные значения введите в ЭМВ, после ввода числового значения нажимайте клавишу «Enter», и сравните свои значения с рассчитанными на ЭВМ. При большом расхождении сравниваемых значений выдается сообщение об ошибке.
Общие сведения
В технике передачи дискретных сообщений приходится решать задачу сопряжения (согласования) источников дискретных сообщений с каналом. Решение этой задачи связано с поиском путей передачи информации со скоростью, возможно более близкой к предельной.
Для большинства источников дискретных сообщений, характеризующихся информационной избыточностью, максимальная скорость передачи может быть достигнута в результате устранения избыточности в передаваемом сообщении. Процедуры, направленные на устранение избыточности источника дискретных сообщений, передаваемых по каналу без помех, называются эффективным кодированием.
Пусть имеется сообщение, записанное с помощью букв некоторого первичного алфавита , содержащего букв. Требуется закодировать это сообщение, т.е. указать правило сопоставления каждой букве первичного алфавита последовательности из символов «0» и «1», образующих вторичный алфавит.
При передаче дискретных сообщений по каналам связи буквы алфавита обычно отображаются кодовыми комбинациями постоянной длины (равномерное кодирование). Длина кодовой комбинации выбирается из условия . Применение эффективного кодирования позволяет уменьшить среднее число двоичных символов на букву сообщения
(1)
где – длина кодовой комбинации, отображающей -ю букву,
– вероятность появления -й буквы.
Уменьшение средней длины кодовой комбинации, отображающей букву сообщения, позволяет увеличить скорость передачи.
Эффективное кодирование базируется на теореме Шеннона для каналов без шума. Согласно этой теореме (основной теореме кодирования), сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов, приходящихся на букву, будет сколь угодно близко к энтропии источников этих сообщений , но не менее этой величины, т.е.
(2)
Под энтропией дискретного источника понимается среднее количество информации, приходящееся на одну букву сообщения:
(3)
Для построения эффективных кодов наибольшее распространение нашли методики Шеннона-Фано и Хаффмена.
Метод Шеннона-Фано.
Эти процедуры повторяются до тех пор, пока в каждой группе останется по одной букве.
Построение кода Шеннона-Фано для ансамбля из 8 букв приведено в Табл. 1 на с. 6.
При равномерном кодировании 8-ми букв кодовые комбинации содержат по три двоичных разряда. При использовании кода Шеннона-Фано средняя длина кодовой комбинации составляет:
Это меньше, чем при равномерном кодировании и не очень далеко от энтропии
Метод Хаффмена.
Второй и третий этапы повторяются до тех пор, пока суммарная вероятность не будет равна единице.
Построение кода Хаффмена для ансамбля из 8 букв приведено в Табл. 2.
Таблица 1
|
Буквы |
Деление букв на группы |
Код Шеннона-Фано |
|
|
0,20 |
11 |
||
|
0,20 |
101 |
||
|
0,15 |
100 |
||
|
0,13 |
011 |
||
|
0,12 |
010 |
||
|
0,10 |
001 |
||
|
0,07 |
0001 |
||
|
0,03 |
0000 |
Кодовое дерево строится следующим образом (Табл. 3). Сначала находятся буквы с наименьшими вероятностями 0,07 () и 0,03 (), а затем от них проводятся линии к точке, изображающей «укрупненный» символ с суммарной вероятностью 0,10. На рисунке эта процедура обозначена цифрой I. Затем берутся две наименьшие вероятности со значением 0,10 и получают новый «укрупненный» символ с вероятностью 0,20 (процедура II). Теперь наименьшие вероятности имеют символы (0,13) и (0,12). Соединяя их линиями формируют новый символ с суммарной вероятностью 0,25 (процедура III).
Эти процедуры повторяются до тех пор, пока линии от основных и «укрупненных» символов не соединятся в точке с суммарной вероятностью, равной 1. Верхнюю линию обозначают цифрой «1», а нижнюю «0». Любая кодова комбинация представляет собой последовательность «1» и «0», которые встречаются на пути от вершины дерева с вероятностью 1 к точке, изображающей нужную букву.
Сравнение рассмотренных методик построения эффективных кодов позволяет сделать вывод, что методика Хаффмена более удобна для практического использования. В общем случае код Хаффмена экономичнее кода Шеннона-Фано.
Нетрудно заметить, что сокращение средней длины кодовой комбинации эффективного кода по сравнению с равномерными кодами достигается благодаря присвоению более вероятным буквам коротких кодовых комбинаций, а менее вероятным буквам – более длинных кодовых комбинаций. Таким образом, эффективность рассматриваемых кодов связана с различием в числе символов кодовых комбинаций. Это приводит к определенным трудностям при декодировании. Конечно, для различия кодовых комбинаций можно ставить разделительный символ, но при этом существенно снижается эффект, который достигается использованием неравномерных кодов, так как средняя длина кодовой комбинации, по существу, увеличивается на одни символ. Более разумным является обеспечение однозначного декодирования без введения разделительных символов. Для этого эффективный код строят так, чтобы ни одна комбинация кода не совпадала с первыми символами более длинной кодовой комбинации. Коды, удовлетворяющие этому условию, называются префиксными.
Коды, представляющие первичные алфавиты с неравновероятными символами, имеющие минимальную среднюю длину кодового слова, называются оптимальными неравномерными кодами (ОНК).
Максимально эффективными будут те ОНК, у которых энтропия дискретного источника H(A) численно равна среднему числу двоичных символов на букву :
(4)
или с учетом (1) и (3)
(5)
Очевидно, что это равенство будет иметь место только тогда, когда
(6)
Величина точно равна H(A), если вероятности представляют собой целочисленные отрицательные степени двойки. Если это не выполняется, то и согласно основной теореме кодирования Шеннона для каналов без шумов средняя длина кодовой комбинации приближается к энтропии источника сообщений по мере укрупнения кодируемых блоков.
Для оценки эффективности ОНК предназначены следующие характеристики.
1. Коэффициент статического сжатия.
(7)
Он характеризует уменьшение количества двоичных символов на букву алфавита при применении ОНК по сравнению с применением методов нестатистического кодирования.
2. Коэффициент относительной эффективности.
(8)
Этот коэффициент показывает, насколько устраняется статистическая избыточность передаваемого сообщения.
Методы устранения избыточности позволяют эффективно использовать пропускную способность канала связи. Они полезны также в тех случаях, когда требуется хранить большой объем информации в различных запоминающих устройствах. Экономия в пропускной способности канала или в объеме запоминающего устройства приводит к снижению стоимости, сокращению размеров и веса аппаратуры. Рассмотренные методы кодирования получили применение при передаче факсимильных сообщений.