Методические указания

1 2 3 4 5 6 7

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ ЛНР

«ЛУГАНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

Имени ВЛАДИМИРА ДАЛЯ»

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к лабораторным работам №1 – №6 по дисциплине

"Теория кодирования информации"

для студентов направления подготовки/специальности:

"09.03.04 – Программная инженерия"

Авторы: ст. преп. Кийко А.В., асс. Кийко С.А.

Луганск 2017

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

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

1. Теоретические сведения

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

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

Пример. Порядок двоичного числа 000001101 равен 4, а мантисса – 1101.

1.1. Коды класса Fixed + Variable

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

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

Таблица 1

Код класса Fixed + Variable

число	двоичное представление	кодовое слово	длина кодового слова
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 ..

1.2. Коды класса Variable + Variable

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

Таблица 2

Код класса Variable + Variable

число	двоичное представление	кодовое слово	длина кодового слова
0 1	00000000000 00000000001	1 0 1	1 2
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	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 является омега-код Элиаса (ω-код Элиаса).В нем первое значение (кодовое слово для единицы) задается отдельно. Другие кодовые слова состоят из последовательности групп длиной , начинающихся с единицы. Конец всей последовательности задается нулевым битом. Длина первой группы составляет 2 бита, длина каждой следующей группы равна двоичному значению битов предыдущей группы плюс 1. Значение битов последней группы является итоговым значением всей последовательности групп, т.е. первые групп служат лишь для указания длины последней группы.

Таблица 4

Омега-код Элиаса

число	кодовое слово	длина кодового слова
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

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

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

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

2. Диапазон значений входных элементов не ограничен или неизвестен. Например, при кодировании 32-битовых чисел реально большинство чисел маленькие, но могут быть и большие.

3. При использовании в составе других схем кодирования, например, кодировании длин серий.

1.3. Кодирование длин серий

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

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

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 бит.

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