close

Вход

Забыли?

вход по аккаунту

?

4 5 lab rabota

код для вставкиСкачать
эМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ"
КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ
РУКОВОДИТЕЛЬ
Старший преподавательМ.В. Соколовская должность, уч. степень, званиеподпись, датаинициалы, фамилия
ЛАБОРАТОРНАЯ РАБОТА
КОДИРОВАНИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ ИНФОРМАЦИИ Вариант 8.
по дисциплине: ИНФОРМАТИКАЛАБОРАТОРНУЮ РАБОТУ ВЫПОЛНИЛ(А)
СТУДЕНТ(КА) ГР.6332КХипели В.А.подпись, датаинициалы, фамилия
Санкт-Петербург 2013
Цель работы: Освоить метод построения кодов дискретного источника информации используя конструктивный метод, предложенный К.Шенноном и Н.Фано. На примере показать однозначность раскодирования имеющегося сообщения; освоить метод построения кодов дискретного источника информации используя методику Д.Хаффмана. На примере показать однозначность раскодирования имеющегося сообщения.
Метод Шеннона-Фано.
При кодировании дискретных источников информации зачастую приходится решать задачу уменьшения избыточности, а именно уменьшения количества символов, используемых для передачи сообщения по каналу связи. Это позволяет повысить скорость передачи за счет уменьшения количества передаваемой информации, а в системах хранения уменьшение избыточности дает возможность снизить требования к информационной емкости используемой памяти.
Для передачи и хранения информации обычно используется двоичное кодирование. Если алфавит A состоит из N символов, то для их двоичного кодирования требуется слово разрядностью n, которое можно определить, как:n = log2 N , где значение округляется до верхнего целого числа.
Это справедливо и при использовании стандартных кодовых таблиц, например, ASCII, KOI-8 и т.п., которые обеспечивают кодирование до 256 символов. Если в используемом алфавите символов меньше, чем используется в стандартной кодовой таблице, возможно использование некой другой таблицы кодирования, если необходимо передать или хранить сообщение, состоящее из символов кириллицы, цифр и семи символов-разделителей {".", ",", ":", ";", ")", "пробел", "?"} (всего 50 символов), можно воспользоваться следующими способами кодирования: Кодировать каждый символ в соответствии со стандартной кодовой таблицей, например, KOI-8R. По данной таблице n1 = 8;
Составить и использовать отдельную кодовую таблицу. Это может быть усеченный вариант стандартной таблицы, не учитывающей возможность кодирования символов, которые входят в передаваемое сообщение. Тогда необходимый размер кодового слова n2 =log2 N =  log2 50 =6, где значение нужно округлить таким же образом, как и при определении формулы разрядности.
Эффективное кодирование базируется на основной теореме Шеннона для каналов без шума, в ней доказывается, что сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов на букву будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины.
Код же строится следующим образом: буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей. Затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним - 0. Каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Таким образом, рассмотренный алгоритм Шеннона-Фано не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.
Энтропия набора символов может определяется как:
Смысл энтропии в данном случае, как следует из теоремы Шеннона, - наименьшее возможное среднее количество двоичных разрядов, необходимых для кодирования символов алфавита размера восемь с известными вероятностями появления символов в сообщении.
Можно вычислить среднее количество двоичных разрядов, используемых при кодировании символов по алгоритму Шеннона-Фано по следующей формуле:
где: A - размер (объем) алфавита, используемого для передачи сообщения,
n(ai) - число двоичных разрядов в кодовой комбинации, соответствующей символу ai. У меня оно равно 4,647563.
Пример декодирования сообщения:
Пусть передано сообщение: КОМБИНАЦИЯ
При кодировании, используя исходную таблицу, получим:
010101101001110010011011100110100010001011001101
Теперь декодируем это сообщение:
ШагКомбинацияКол-во символовБуква10104П, к, л, д201012П,к3010101К41102О, е511011О60017700113М, я, у8001111М900171000104Ы, з, б, ц11001002Б, ц120010011Б131012И, а1410111И151002Н, т1610011Н171012И, а1810101А1900172000104Ы, з, б, ц21001002Б, ц220010001Ц231012И, а2410111И2500172600113М, я, у27001102Я, у290011011Я
Методика Д.Хаффмана.
Основные положения:
От недостатка неоднозначного кодирования, рассмотренного в предыдущей лабораторной работе алгоритма свободна методика Д.Хаффмана, гарантирующая однозначное построение кода с наименьшим для данного распределения вероятностей средним числом двоичных разрядов на символ.
Для двоичного кода алгоритм Хаффмана сводится к следующему:
Шаг 1. Символы алфавита, составляющего сообщение, нужно выписать в основной столбец по порядку убывания вероятностей. Два последних символа объединить в один вспомогательный, которому следует приписать суммарную вероятность. Сим
волыВероятности р(а1)Вспомогательные вычисленияШаг1Шаг2Шаг
3Шаг
4Шаг
5Шаг
6Шаг7а10,220,220,220,260,320,420,581,0а20,200,200,200,220,260,320,42а30,160,160,160,200,220,26а40,160,160,160,160,20а50,100,100,160,16а60,100,100,10а70,040,06а80.02
Таблица 1.
Шаг 2. Вероятности символов, не участвовавших в объединении, и полученная суммарная вероятность снова расположить в порядке убывания вероятностей в дополнительном столбце, а две последних объединить. Процесс продолжать до тех пор, пока не получится единственный вспомогательный символ с вероятностью, равной единице. Эти два шага алгоритма иллюстрирует Таблица1 для уже рассмотренного случая кодирования восьми символов.
Шаг 3. Строится кодовое дерево и, в соответствии с ним, формируются кодовые слова, соответствующие кодируемым символам.
Для составления кодовой комбинации, соответствующей данному сообщению, необходимо проследить путь перехода сообщений по строкам и столбцам таблицы. Для наглядности строится кодовое дерево (рис.1). Из точки, соответствующей вероятности 1, направляются две ветви. Ветви с большей вероятностью присваивается символ 1, а с меньшей - символ 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до каждого символа. Рис.1 Кодовое дерево.
Таким образом, символам источника сопоставляются концевые вершины дерева. Кодовые слова, соответствующие символам, определяются путями из начального узла дерева к концевым. Каждому ответвлению влево соответствует символ 1 в результирующем коде, а вправо - символ 0.
Поскольку только концевым вершинам кодового дерева сопоставляются кодовые слова, то ни одно кодовое слово не будет началом другого. Тем самым гарантируется возможность разбиения последовательности кодовых слов на отдельные кодовые слова.
Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию (см.табл.2):
a1a2a3a4a5a6a7a8010011111010010111010110100Таблица 2.
Вывод: Я освоила метод построения кодов дискретного источника информации, используя конструктивный метод, предложенный К. Шенноном и Н.Фано, также я ознакомилась с методами кодирования Шеннона-Фано и получила практические знания касательно этой темы. А также на примере показала однозначность раскодирования имеющегося сообщения. 1
Документ
Категория
Рефераты
Просмотров
273
Размер файла
49 Кб
Теги
lab, rabota
1/--страниц
Пожаловаться на содержимое документа