Министерство информационных технологий и связи

Российской Федерации

Сибирский государственный университет

телекоммуникаций и информатики

Е. В. Курапова

Е. П. Мачикина

Основные методы кодирования данных Методические указания

Новосибирск 2010

УДК 681.3.06

Ктн е. В. Курапова, кф-мн е. П. Мачикина. Основные методы кодирования данных: Практикум. / СибГути. – Новосибирск, 2010. – 62 с.

Практикум предназначен для студентов технических специальностей, изучающих дисциплину «Структуры и алгоритмы обработки данных». Пособие содержит необходимые теоретические сведения об основных методах кодирования информации и варианты заданий для самостоятельного выполнения.

Рисунков 13, таблиц  8. Список лит. –6 назв.

Кафедра прикладной математики и кибернетики.

Рецензент: доцент Мамойленко С.Н.

Утверждено редакционно-издательским советом СибГУТИ в качестве практикума.

 Сибирский государственный университет

телекоммуникаций и информатики, 2010 г.

ОГЛАВЛЕНИЕ

1.ВВЕдение 4

2.Необходимые понятия и определения 5

3.Кодирование целых чисел 8

3.1Коды класса Fixed + Variable 8

3.2Коды класса Variable + Variable 9

3.3Кодирование длин серий 11

4.Некоторые теоремы ПОБУКВЕННОГО кодирования 12

5.оптимальное ПОБУКВЕННОЕ кодирование 16

5.1Основные понятия 16

5.2Оптимальный код Хаффмана 19

6.почти оптимальное кодирование 22

6.1Код Шеннона 22

6.2Код Фано 23

6.3Алфавитный код Гилберта – Мура 25

7.арифметический код 28

8.адаптивные методы кодирования 33

8.1Адаптивный код Хаффмана 34

8.2Код «Стопка книг» 37

8.3Интервальный код 39

8.4Частотный код 41

9.словарные коды класса Lz 44

9.1Кодирование с использованием скользящего окна 45

9.2Кодирование с использованием адаптивного словаря 46

Лабораторные работы 52

Лабораторная работа №1 53

Лабораторная работа №2 54

Лабораторная работа №3 54

Лабораторная работа №4 55

Лабораторная работа №5 56

Лабораторная работа №6 57

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА 58

Приложение А 59

1. ВВЕдение

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

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