Geum.ru

Пояснительная записка к курсовому проекту на тему «Кодирование информации методом Шеннона-Фано» по дисциплине

Вид материалаПояснительная записка

Содержание


Ахметова Г.С.
Пиявский С.А.
Их использование
5. Тест для контроля усвоения учебного материала
Подобный материал:
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО «Самарский государственный архитектурно-строительный университет»

Факультет информационных систем и технологий

Кафедра прикладной математики и вычислительной техники


Пояснительная записка

к КУРСОВОМУ ПРОЕКТУ на тему

«Кодирование информации методом Шеннона-Фано»

по дисциплине

СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

В ОБРАЗОВАНИИ


СТУДЕНТА ГИП-104 Ахметовой Г.С.






Подпись, дата
Расшифровка подписи







ВЫПОЛНИЛ:



^ Ахметова Г.С.







студент



/ /







Модуль сдан в библиотеку кафедры ПМ и ВТ












Модуль размещен на портале ФИСТ












ПРОВЕРИЛ:



^ Пиявский С.А.







ОЦЕНКА



/ /



Самара2007г


Оглавление


Введение.....................................................................................................................

Текст изучаемого раздела........................................................................................

Конспект лекции для автора курсового проекта как для преподавателя.............

Презентация для лекции...........................................................................................

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

Тест для контроля усвоения учебного материала..................................................

Заключение.................................................................................................................

Этапы выполнения курсового проекта....................................................................

Библиографический список......................................................................................


Введение

Войти в 21век образованным человеком можно, только хорошо владея информационными технологиями. Информатика, как никакая другая область знаний, характеризуется чрезвычайно высокой степенью динамики изменений.

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

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

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

^

Их использование:

  • оживляет материал и позволяет студенту «общаться» с ним
  • даёт больше интерактивности и стимулирует активное обучение
  • наглядно демонстрирует некоторые идеи, которые трудно объяснить на лекциях или просто в тексте
  • позволяет заглянуть внутрь изучаемых процессов посредством различных симуляций
  • развивает навыки самостоятельного обучения и самоконтроля
  • позволяет студентам попробовать невозможные, опасные или дорогие сценарии и ситуации, такие как параллельные миры, радиационное оборудование и проч.



1.Текст изучаемого раздела

Кодирование Шеннона-Фано является одним из самых первых алгоритмов сжатия, который впервые сформулировали американские учёные ссылка скрыта (Shannon) и Фано (Fano). 

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

Цель сжатия - уменьшение количества бит, необходимых для хранения или передачи заданной информации, что дает возможность передавать сообщения намного быстрее и оперативно хранить ( означает, что операция извлечения данной информации с устройства ее хранения будет проходить быстрее, что возможно, если скорость распаковки данных выше скорости считывания данных с носителя информации). Сжатие позволяет, например, записать больше информации на дискету, "увеличить" размер жесткого диска, ускорить работу с модемом и т.д. При работе с компьютерами широко используются программы-архиваторы данных формата ZIP, GZ, ARJ и других. Методы сжатия информации были разработаны как математическая теория, которая долгое время (до первой половины 80-х годов), мало использовалась в компьютерах на практике.

Главная идея этого метода - заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами. Таким образом, алгоритм основывается на кодах переменной длины.

В частности, в интересующем нас здесь случае идеального канала без помех такой источник должен просто обладать максимальной энтропией или нулевой избыточностью, т.е. выдавать независимые равновероятные сообщения. В то же время своей постановки задачи мы пожелали иметь возможность передавать сообщения от произвольного источника с любыми статистическими свойствами, т.е. имеющего ненулевую избыточность. Таким образом функции кодера являются согласованием в статическом смысле сообщений источника со входом канала. Задача этого согласования в конечном итоге сводится к устранению избыточности сообщений. Кодер осуществляет кодирование сообщений, т.е. каждому дискретному сообщению по определенному правилу ставят в соответствие последовательность символов из алфавита объемом М. При этом по отношению к входу каналом выдаваемые кодером символы сами являются дискретными элементами сообщений, статические свойства которых должны отличаться от статических свойств сообщений исходного источника. Возможность построения кодера полностью устраняющего избыточность произвольного исходного источника сообщений и определяет возможность решения поставленной задачи без ошибочной передачи информации со скоростью, равной пропускной способности канала. При полном ее решении оказывается справедливым равенство
H1(U)=uC*H(U)=uK*logM=C

откуда имеем h=uK/uC=H(U)/logM
где H(U) - энтропия источника передаваемых сообщений, uK и u C - средние количества символов соответственно сообщения и кода передаваемых в единицу времени.
h = uK/ uC - среднее количество символов кода приходящиеся на одно сообщение.

Энтропия источника- наименьшее количество двоичных символов на сообщение.

Кодирование позволяющее устранять избыточность источников сообщений называется эффективным или статистическим. Коды, получаемые в результате такого кодирования, называются эффективными или статистическими. Рассмотрим основные идеи, которые могут быть положены в основу эффективного кодирования. Как отмечалось в пункте 1.4. избыточность дискретных источников обуславливается двумя причинами:

1) памятью источника;

2) неравномерностью сообщений.

Универсальным способом уменьшения избыточности обусловленной памятью источника является укрупнение элементарных сообщений. При этом кодирование осуществляется длинными блоками. Вероятностные связи между блоками меньше чем между отдельными элементами сообщений и чем длиннее блоки, тем меньше зависит между ними. Смысл укрупнения поясним на примере буквенного текста: если вероятностные связи между буквами в любом языке относительно сильны, то между словами они значительно меньше, еще меньше между фразами, еще меньше между абзацами. Поэтому, применяя кодирование слов, фраз, абзацев мы можем достаточно полно устранить избыточность обусловленную вероятностными связями. Однако при этом возрастает задержка передачи сообщений, так как сначала нужно дождаться формирования всего длинного блока сообщений и лишь затем его закодировать и передавать. Уменьшение избыточности обусловленной неравномерностью сообщений может быть достигнута применением неравномерных кодов. Основная идея построения таких кодов состоит в том, что наиболее вероятным сообщениям ставятся в соответствие наиболее короткие блоки кодовых символов (кодовые комбинации), а наименее вероятным более длинные. В силу неравномерности таких кодов и случайного характера сообщения U передача без потерь информации с постоянной скоростью следования кодовых символов uK может быть обеспечено лишь при наличии буферного накопителя с большой памятью, и, следовательно, при допустимости больших задержек.

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


где m - избыточность источника. Анализ выражения (2.5) показывает, что при любой не нулевой избыточности источника m число сообщений высоко вероятного подмножества составляет сколь угодно малую часть от всех возможных сообщений если длина сообщения К достаточно велика (сколь угодно малую вероятность имеет большая часть достаточно длинных сообщений). Это большинство и позволяет добиться близкого к минимуму числа h кодовых символов на элемент сообщения, применен следующий способ кодирования. Высоко вероятной группе сообщений поставим в однозначное соответствие различные короткие (их мало) кодовые комбинации равномерного кода длинны n1, оставив одну для использования в качестве разделительного сигнала.


На конкретном примере рассмотрим алгоритм вычисления кода Шеннона-Фано:

Закодируем сообщение:

«РоссийскаяСистемаВысшегоТехническогоОбразования»


1. Составим алфавит кода и для каждого символа этого алфавита и определим вес [количество повторений символа в сообщении].


Р-2,О-5,С-7,И-4,Й-1,К-2,А-4,Я-2,Т-2,Е-4,М-1,В-2,Ы-1,Ш-1,Г-2,

Х-1,Н-2,Ч-1,Б-1,З-1


2. Ранжируем алфавит по убыванию веса символа.


С-7, О-5, И-4, А-4, Е-4, Р-2, К-2, Я-2, Т-2, В-2, Г-2, Н-2, Й-1, М-1,

Ы-1,Ш-1, Х-1, Ч-1,Б-1,З-1

3. Далее, создается таблица символов, делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в '0', второй в '1




СИМВОЛ
НЕНАРМИРОВАННЫЙ КОД

С[7]
0
0
0
*
*
*
000

О[5]
0
0
1
*
*
*
001

И[4]
0
1
0
*
*
*
010

А[4]
0
1
1
0
*
*
0110

Е[4]
0
1
1
1
*
*
0111

Р[2]
1
0
0
0
*
*
1000

К[2]
1
0
0
1
*
*
1001

Я[2]
1
0
1
0
*
*
1010

Т[2]
1
0
1
1
0
*
10110

В[2]
1
0
1
1
1
*
10111

Г[2]
1
1
0
0
*
*
1100

Н[2]
1
1
0
1
0
*
11010

Й[1]
1
1
0
1
1
0
110110

М[1]
1
1
0
1
1
1
110111

Ы[1]
1
1
1
0
0
*
11100

Ш[1]
1
1
1
0
1
0
111010

Х[1]
1
1
1
0
1
1
111011

Ч[1]
1
1
1
1
0
*
11110

Б[1]
1
1
1
1
1
0
111110

З[1]
1
1
1
1
1
1
111111



4.Получаем код к каждой букве:

С
000
Р
1000
Г
1100
Ш
111010

О
001
К
1001
Н
11010
Х
111011

И
010
Я
1010
Й
110110
Ч
11110

А
0110
Т
10110
М
110111
Б
111110

Е
0111
В
10111
Ы
11100
З
111111

5. В результате получается новое сообщение:

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



0000010100110011110001001101010110101111100110101101101101111110011101011101111110111110111111


2. Конспект лекции для автора курсового проекта как для преподавателя

Главная идея этого метода - заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами. Таким образом, алгоритм основывается на кодах переменной длины.

Алгоритм:

Сообщение-

«РоссийскаяСистемаВысшегоТехническогоОбразования»


1.


Р-2,О-5,С-7,И-4,Й-1,К-2,А-4,Я-2,Т-2,Е-4,М-1,В-2,Ы-1,Ш-1,Г-2,

Х-1,Н-2,Ч-1,Б-1,З-1


2.


С-7, О-5, И-4, А-4, Е-4, Р-2, К-2, Я-2, Т-2, В-2, Г-2, Н-2, Й-1, М-1,

Ы-1,Ш-1, Х-1, Ч-1,Б-1,З-1


3. Таблица


1
С
7
7
0
0
0









2
О
5
12
1









3
И
4
16
1
0









4
А
4
20
1
0






5
Е
4
24
1






6
Р
2
26
1
0
0
0






7
К
2
28
1
0



8
Я
2
30
1



9
Т
2
32
1
0






10
В
2
34
1
0



11
Г
2
36
1



12
Н
2
38
1
0
0






13
И
1
39
1
0



14
М
1
40
1
0

15
Ы
1
41
1

16
Ш
1
42
1
0
0



17
Х
1
43
1



18
Ч
1
44
1
0



19
Б
1
45
1
0

20
З
1
46
1



4.Получаем код к каждой букве:

С
000
Р
1000
Г
1100
Ш
111010

О
001
К
1001
Н
11010
Х
111011

И
010
Я
1010
Й
110110
Ч
11110

А
0110
Т
10110
М
110111
Б
111110

Е
0111
В
10111
Ы
11100
З
111111

5. В результате получается новое сообщение:


0000010100110011110001001101010110101111100110101101101101111110011101011101111110111110111111


3. Презентация для лекции

































4. Сценарий контролирующей программы по методу Шеннона-Фано:


Шаг 1: вводится сообщения для кодирования

Шаг 2: выводится список всех символов, встречающихся в сообщении.

Шаг 3: выводится вероятность появления каждого символа в списке.

Шаг 4: выводится энтропия символов

Шаг 5: выводится избыточность символов

Шаг 6: делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в '0', второй в '1

Шаг 7: определяется конечный код каждой буквы.


^ 5. Тест для контроля усвоения учебного материала


Заключение


Этапы выполнения курсового проекта


Библиографический список



1
Пиявский С.А. Системы поддержки принятия решений в образовании: Учебное пособие / С.А. Пиявский, СГАСУ. – Самара, 2005 – 216 с.

2
Информационные системы и технологии в образовании: Методические указания к курсовому проектированию «Разработка электронного обучающего модуля» / составитель С.А. Пиявский; Самарск. гос. арх.-строит. ун-т. - Самара, 2007. - 19 с.

3
«Шеннона-Фано» электронный ресурс T.ru [25.09.2007]