Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Реферат'
Сделки являются одной из основных категорий гражданского права. Они широко распространены и обслуживают все сферы имущественного оборота. Ежедневно с...полностью>>
'Документ'
У багатьох країнах світу професійна успішність вже давно є однією з найбільш значущих соціокультурних установок людини, універсальним мотивом професі...полностью>>
'Книга'
 В начале 20-го века Бог дал Сенеке Соди славное переживание пребывания сорока дней на небесах. Эта книга изменит вашу жизнь и даст вам надежду, помо...полностью>>
'Самостоятельная работа'
На современном этапе развития педагогической теории и практики большое значение приобретает поиск наиболее эффективных путей обучения, повышения каче...полностью>>

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

Главная > Пояснительная записка
Сохрани ссылку в одной из сетей:

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

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

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

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

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

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

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

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

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

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

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

Подпись, дата

Расшифровка подписи

ВЫПОЛНИЛ:

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

студент

/ /

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

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

ПРОВЕРИЛ:

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

ОЦЕНКА

/ /

Самара2007г

Оглавление

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

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

  • оживляет материал и позволяет студенту «общаться» с ним

  • даёт больше интерактивности и стимулирует активное обучение

  • наглядно демонстрирует некоторые идеи, которые трудно объяснить на лекциях или просто в тексте

  • позволяет заглянуть внутрь изучаемых процессов посредством различных симуляций

  • развивает навыки самостоятельного обучения и самоконтроля

  • позволяет студентам попробовать невозможные, опасные или дорогие сценарии и ситуации, такие как параллельные миры, радиационное оборудование и проч.

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

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

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

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

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

В частности, в интересующем нас здесь случае идеального канала без помех такой источник должен просто обладать максимальной энтропией или нулевой избыточностью, т.е. выдавать независимые равновероятные сообщения. В то же время своей постановки задачи мы пожелали иметь возможность передавать сообщения от произвольного источника с любыми статистическими свойствами, т.е. имеющего ненулевую избыточность. Таким образом функции кодера являются согласованием в статическом смысле сообщений источника со входом канала. Задача этого согласования в конечном итоге сводится к устранению избыточности сообщений. Кодер осуществляет кодирование сообщений, т.е. каждому дискретному сообщению по определенному правилу ставят в соответствие последовательность символов из алфавита объемом М. При этом по отношению к входу каналом выдаваемые кодером символы сами являются дискретными элементами сообщений, статические свойства которых должны отличаться от статических свойств сообщений исходного источника. Возможность построения кодера полностью устраняющего избыточность произвольного исходного источника сообщений и определяет возможность решения поставленной задачи без ошибочной передачи информации со скоростью, равной пропускной способности канала. При полном ее решении оказывается справедливым равенство
H2(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



Скачать документ

Похожие документы:

  1. Учебная программа для высших учебных заведений по специальности I 39 01 04 Радиоэлектронная защита информации Cогласована с Учебно-методическим управлением бгуир

    Программа
    Э.М. Карпушкин, доцент кафедры радиотехнических систем Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники»,
  2. И квантовые приборы

    Документ
    С.В. Дробот, заведующий кафедрой электроники Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники», кандидат технических наук;
  3. Введение в специальность (8)

    Программа
    В.А. Чердынцев, заведующий кафедрой радиотехнических устройств Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники»,
  4. Введение в специальность (7)

    Программа
    Р.Г. Ходасевич, доцент кафедры радиотехнических систем Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники»,
  5. Учебная программа для высших учебных заведений по специальности 1-98 01 02 Защита информации в телекоммуникациях Согласована с Учебно-методическим управлением бгуир

    Программа
    Л.М. Лыньков, заведующий кафедрой защиты информации Учреждения образования “Белорусский государственный университет информатики и радиоэлектроники”, доктор технических наук;

Другие похожие документы..