Автор работы: Пользователь скрыл имя, 09 Декабря 2011 в 08:53, курсовая работа
Работа подавляющего числа современных систем связи основана на передаче сообщений в цифровом виде. Сбой при приеме любого элемента цифровых данных способен вызвать значительное искажение всего сообщения в целом, что, в свою очередь, может привести к полной потере информации, содержащейся в нем. В современных информационных системах важнейшей задачей является обеспечение информационной безопасности, связанной с методами криптографии и кодирования, теоретические основы которой заложил Шеннон в своих трудах.
Введение 3
1. Теоретические основы задачи кодирования……………………………………………...6
1.1. Постановка задачи кодирования………….……………………………..….……………6
1.2. Первая теорема Шеннона…………………………………………………………….....10
1.3. Вторая теорема Шеннона……………………………………………………………….13
1.4. Помехоустойчивые коды…..........………………………………………….......…….…14
2. Алфавитное кодирование......................................................................................................17
2.1. Основные определения.....................................................................................................17
2.2. Проблема распознавания взаимной однозначности алфавитного кодирования.......18
2.3. Алгоритм построения префиксного кода по набору длин элементарных кодов........22
2.4. Алгоритмы экономного алфавитного кодирования......................................................23
2.4.1. Алгоритм Хаффмана...............................................................................................24
2.4.2. Алгоритм Фано........................................................................................................26
2.4.3. Алгоритм Шеннона.................................................................................................27
2.4.4. Энтропия и ее связь со стоимостью оптимального алфавитного
кодирования..................................................................................................................................28
2.4.5. Возможности сжатия при алфавитном кодировании, учитывающем
синтаксис языка сообщений........................................................................................................31
Заключение..................................................................................................................................34
Список литературы 35
f1
: B∗ → {0, 1}∗
Алгоритм
Хаффмана
раз.
Пример 2.13. Пусть
Рассмотрим схему кодирования
Схема f1 задает взаимно-однозначное кодирование языка L1, так как фрагмент abc может быть закодирован одним символом 0, для взаимной однозначности кодирования достаточно каким-то образом кодировать число вхождений фрагмента abc в слово языка.
Пример 2.14. Пусть (Здесь a+ означает произвольную непустую последовательность букв a).
Буквы b и c контекстно-различимы, их можно кодировать одинаково. Поэтому следующая схема кодирования f2 задает взаимно-однозначное кодирование языка L2:
Пусть L неприводимый язык и F(L) – множество всех взаимно-однозначных кодирований языка L, задаваемых схемами алфавитного кодирования.
Пусть на множестве букв алфавита B языка L задано распределение вероятностей P. Обозначим через C *(L,P) стоимость оптимального алфавитного кодирования, учитывающего синтаксис языка L, и через C *(B*,P) стоимость кодирования по алгоритму Хаффмана (обозначавшуюся ранее как C *(P) ). Для a ∈ L через C *(L,a) обозначим , где f * - оптимальное алфавитное кодирование, учитывающее синтаксис языка L, и через C*(B*,a) - длину кода слова a ∈ L , построенного по алгоритму Хаффмана.
В качестве меры эффективности кодирования, учитывающего синтаксис языка L, рассмотрим коэффициент сжатия
Теорема
2.10. Пусть L – неприводимый
язык. Тогда
Из теоремы следует, что неприводимый язык может быть сжат с помощью
алфавитного кодирования не более чем в два раза.
Теорема 2.11. Для почти всех неприводимых языков
Z(L)
=1.
Заключение
В ходе курсовой работы была рассмотрена задача кодирования, которая включает в себя:
1.Обеспечение
экономичности передачи
2. Обеспечение надежности (помехоустойчивости) передачи информации.
3.Согласование скорости передачи информации с пропускной способностью канала.
В работе были изложены результаты, относящиеся к одному из направлений теории кодирования, в котором изучаются вопросы сжатия информации – экономное кодирование, на примере алфавитного кодирования, которое является простейшим видом автоматного кодирования.
Вопросы сжатия информации играют важную роль в информатике. Это связано с развитием вычислительной техники и средств связи и, как следствие, с необходимостью хранения и передачи больших объемов информации.
Также был рассмотрен вопрос об условиях взаимной однозначности кодирования слов некоторого алфавита при помощи замены каждой буквы некоторым словом того же или какого-либо другого алфавита. Доказано, что в общем случае задача сводится к аналогичной задаче для случая кодирования той же системой слов конечного множества слов этого алфавита. Установлено необходимое и достаточное условие взаимной однозначности, а, следовательно, и возможности обращения оператора, осуществляющего кодирование.
На основании приведенных примеров можно сделать вывод, что почти все неприводимые языки несжимаемы с помощью алфавитного кодирования.
При рассмотрении алфавитного кодирования, учитывающего синтаксические свойства
языка, возникают две задачи:
1. Проблема распознавания взаимной однозначности алфавитного кодирования.
2. Задача оптимального кодирования.
Проблема распознавания взаимной однозначности алфавитного кодирования для языков, описываемых источниками с конечным числом состояний, решена Ал.А.Марковым (1961 г.)
Задача
оптимального алфавитного кодирования
для конечных источников сложная
– она остается открытой. Задача решена
для отдельных подклассов источников.