Файл: Методы кодирования данных (Основные понятия.pdf

СОДЕРЖАНИЕ

Введение 3

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

2. Побуквенное кодирование 11

2.1. Основные понятия побуквенного кодирования 10

2.2. Метод оптимального побуквенного кодирования Д. Хаффмана 16

3. Другие методы кодирования данных 20

3.1. Арифметический код 20

3.2. Адаптивные методы кодирования: код Хаффмана,

код «Стопка книг» 24

3.3. Словарные коды класса Lz 28

Заключение 33

Список литературы 35

Введение

Теория кодирования и теория информации появились в начале 20-го века. Начало развитию этих теорий как академических дисциплин положило возникновение в 1948 г. заметок К. Шеннона, которые положили основу для последующих изучений в данной сфере.

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

Кодирование данных – метод представления данных в удобном для сохранения и передачи варианте. В связи с развитием информационных технологий кодирование считается главным вопросом при решении самых различных задач программирования, подобных равно как:

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

Изучением методов кодирования данных занимались такие ученые как: Е.В. Курапова [10], Е.Ф. Березкин [2], Д.В. Ломакин [11], Ю.М. Штарьков [16], В.В. Бахтизин [1] и др.

Все выше изложенное и определяет актуальность данной темы курсовой работы.

Цель курсовой работы: рассмотреть методы кодирования данных.

Объект исследования: методы кодирования.

Предмет исследования методы кодирования данных в технологиях программирования.

Для достижения цели были поставлены следующие задачи:

1. Раскрыть особенности кодирования целых чисел.
2. Рассмотреть особенности побуквенного кодирования.
3. Изучить другие методы кодирования данных.

Структура и объем курсовой работы: работа состоит из введения, трех глав, заключения, списка литературы. Полный объем курсовой работы составляет 36 страниц.

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

Рассмотрим семейство методов кодирования, не учитывающих вероятности возникновения символов источника. Так как все без исключения символы алфавита источника возможно пронумеровать, в таком случае станем считать, что алфавит источника складывается из целых чисел. Любому целому числу из конкретного спектра устанавливается в соответствие свое кодовое слово, по этой причине данную категорию методов также именуют представлением целых чисел (representation of integers) [10, с. 8].

---

Главная концепция кодирования основана на том, чтобы в отдельности кодировать порядок значения числа («экспоненту» ) и в отдельности – значащие цифры числа («мантиссу» ). Значащие цифры мантиссы начинаются со старшей отличной от нуля цифры, а порядок числа обусловливается местом старшей отличной от нуля цифры в двоичной записи числа. Равно как и при десятичной записи, порядок равен количеству чисел в записи числа в отсутствии предыдущих незначащих нулей [2, с. 143].

Выделяют 2 категории методов кодирования целых чисел. Условно их возможно разделить на:

• Fixed + Variable (фиксированная длина экспоненты + переменная длина мантиссы);
• Variable + Variable (переменная длина экспоненты + переменная длина мантиссы).

В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит понадобится под запись мантиссы. Для кодирования целого числа следует осуществить с числом 2 процедуры: установление порядка числа и акцентирование бит мантиссы (возможно сохранять в памяти отделанную таблицу кодовых слов). Проанализируем процедуру построения кода данного класса на примере [6, с. 211].

Приведем пример. Пускай R = 15 – число бит исходного числа. Отведем E = 4 бита под экспоненту (порядок), т.к. R≤24. При записи мантиссы возможно сберечь один бит: никак не записывать первую единицу, т.к. это постоянно будет только единица. Таким образом, число бит мантиссы меньше на один бит, нежели количество бит для порядка.

Таблица 1.1 Код класса Fixed + Variable [10, с. 9]

Число	Двоичное представление	Кодовое слово	Длина кодового слова
0 1	000000000000000 000000000000001	0000 0001	4 4
2 3	000000000000010 000000000000011	0010 0 0010 1	5 5
4 5 6 7	000000000000100 000000000000101 000000000000110 000000000000111	0011 00 0011 01 0011 10 0011 11	6 6 6 6
8 9 10 … 15	000000000001000 000000000001001 000000000001010 … 000000000001111	0100 000 0100 001 0100 010 … 0100 111	7 7 7 .. 7
16 17 …	000000000010000 000000000010001 …	0101 0000 0101 0001 …	8 8 ..

---

Рассмотрим коды класса Variable + Variable

В качестве кода числа принимается двоичная очередность, выстроенная последующим способом: ряд нулей (число нулей равно значению порядка числа), далее единица как критерий окончания экспоненты неустойчивой длины, далее мантисса неустойчивой длины (равно как в кодах Fixed + Variable) [4, с. 119].

Рассмотрим образец построения кода данного класса (см. таблицу 1.2).

Таблица 1.2 Код класса Variable + Variable [10, с. 9]

число	двоичное представление	кодовое слово	длина кодового слова
1	2	3	4
0 1	00000000000 00000000001	1 0 1	1 2

Продолжение таблицы 1.2

1	2	3	4
2 3	00000000010 00000000011	00 1 0 00 1 1	4 4
4 5 6 7	00000000100 00000000101 00000000110 00000000111	000 1 00 000 1 01 000 1 10 000 1 11	6 6 6 6
8 9 10 …	00000001000 00000001001 00000001010 …	0000 1 000 0000 1 001 0000 1 010 …	8 8 8

В случае если в осмотренном ранее коде устранить кодовое слово для нуля, то в таком случае, возможно, сократить длины кодовых слов на один бит, сняв первый нуль. Подобным способом создается гамма-код Элиаса (γ-код Элиаса) (см. таблицу 1.3).

Таблица 1.3 Гамма-код Элиаса [10, с. 10]

число	кодовое слово	длина кодового слова
1	1	1
2 3	01 0 01 1	3 3
4 5 6 7	00 1 00 00 1 01 00 1 10 00 1 11	5 5 5 5
8 9 10 …	000 1 000 000 1 001 000 1 010 …	7 7 7

Иным примером кода класса Variable + Variable считается омега-код Элиаса (ω-код Элиаса). В нем 1-ое значение (кодовое слово для единицы) задается в отдельности. Прочие кодовые слова имеют структуру из очередности групп длиной , начинающихся с единицы. Окончание всей очередности задается нулевым битом. Протяженность первой группы равна 2 бита, протяженность любой последующей группы равна двоичному значению битов предыдущей группы плюс единица. Значение битов заключительной группы является окончательным значением всей последовательности групп, т.е. первые групп предназначаются только с целью для указания длины последней группы [7, с. 241].

---

Таблица 1.4 Омега-код Элиаса [10, с. 10]

Число	Кодовое слово		Длина кодового слова
1 2 3	0 10 0 11 0		1 3 3
4 5 6 7	10 100 0 10 101 0 10 110 0 10 111 0	6 6 6 6
8 9 .. 15	11 1000 0 11 1001 0 … 11 1111 0	7 7 .. 7
16 17 .. 31	10 100 10000 0 10 100 10001 0 … 10 100 11111 0	11 11 .. 11
32	10 101 100000 0	12

При кодировании создается сперва заключительная группа, далее предпоследняя и т.д., до тех пор, пока процесс не будет окончен. При декодировании, напротив, сперва считывается 1-ая группа, по значению ее битов обусловливается протяженность последующей группы, или итоговое значение кода, в случае следующая группа – 0 [9, с. 73].

Рассмотренные типы кодов имеют все шансы быть эффективными в последующих вариантах:

1. Вероятности чисел спадают с увеличением значений элементов и их распределение близко к этому: , при каждом x, т.е. небольшие числа попадаются чаще, чем крупные.

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

3. При применении в составе иных методик кодирования, к примеру, кодировании длин серий [13, с. 114].

Рассмотрим кодирование длин серий

Способ кодировки данных, известный равно как метод кодировки длин серий и представленный П. Элиасом, при построении применяет коды целых чисел. Входной поток для кодирования рассматривается как равно как очередность из нулей и единиц. Концепция кодирования состоит в том, чтобы кодировать очередности схожих элементов (к примеру, нулей) равно как целые числа, указывающие число элементов в этой очередности. Очередность схожих элементов именуется серией, число элементов в ней – длиной серии [15, с. 56].

Рассмотрим пример. Входную последовательность (общая длина тридцать один бит) возможно разделить на серии, а затем закодировать их длины.

000000 1 00000 1 0000000 1 1 00000000 1

Применяем, к примеру, γ-код Элиаса. Так как в коде нет кодового слова для нуля, в таком случае станем кодировать длину серии +1, т.е. последовательность 7 6 8 1 9:

---

7 6 8 1 9  00111 00110 0001000 1 0001001

Длина полученной кодовой последовательности равна 25 бит [10, с. 11].

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

В заключение можно сделать вывод, что кодирование целых чисел осуществляется с использованием группы метод кодирования целых чисел Fixed + Variable и Variable + Variable.

В кодах класса Fixed + Variable под запись значения порядка числа дается определенное число бит, а значение порядка числа устанавливает, сколько бит необходимо под запись мантиссы. Для кодирования целого числа нужно проделать с числом две определенные операции: нахождение порядка числа и выделение бит мантиссы (есть возможность сохранять в памяти готовую таблицу кодовых слов).

В кодах класса Variable + Variable в качестве кода числа принимается двоичная очередность, выстроенная последующим способом: ряд нулей (число нулей точно равно значению порядка числа), далее единица как критерий завершения экспоненты неустойчивой длины, далее мантисса переменной длины (как это реализуется в кодах Fixed + Variable).

2. Побуквенное кодирование

2.1. Основные понятия побуквенного кодирования

При кодировании сообщений является то, что символы сообщения порождаются определенным источником информации. Источник является установленным целиком, в случае если предоставлено вероятностное представление процесса появления сообщений на выходе источника. Данное значит, то что в любой момент времени установлена возможность порождения источником любой очередности символов Р(x₁x₂x₃...x_L), L≥1. Такой источник именуется дискретным вероятностным источником [10, с. 16].

В случае если вероятностный источник с алфавитом А={a₁, a₂, ..., a_n} порождает знаки алфавита вне зависимости друг от друга, т.е. знание предыдущих символов не влияет на вероятность последующих, то такой источник именуется бернуллиевским. В таком случае для любой последовательности x₁x₂...x_L, L≥1, порождаемой источником, выполняется равенство:

P(x₁x₂...x_L ) = P(x₁)·P(x₂)·...·P(x_L), (2.1)

где P(x) – вероятность появления символа х,

Р(x₁x₂x₃...x_L) – вероятность появления последовательности x₁x₂x₃...x_L.

---