Файл: Методы кодирования данных (Сущность и общие особенности представления данных).pdf

Введение

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

- методы кодирования данных без потерь;

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

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

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

Методы оптимального кодирования данных применяются в тех случаях, когда символы алфавита встречаются в сообщениях с различной вероятностью. В этом случае применение оптимальных кодов позволяет минимизировать избыточность кода, а, следовательно, сократить время передачи сообщений. Код Шеннона-Фано и код Хаффмана относятся к множеству оптимальных кодов.

Алгоритм Шеннона-Фано ‒ один из первых алгоритмов кодирования, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод кодирования имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: символы, имеющие большую вероятность появления, кодируется кодом меньшей длины, символы с малой вероятностью появления ‒ кодом большей длины.

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

Исходя из факторов актуальности данного исследования, рационально сформулировать его объект, предмет и цель.

Объект исследования курсовой работы - кодирование данных.

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

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

Исходя из данной цели, требуется решить следующие задачи:

1. Дать определение представления данных

2. Провести анализ сущности кодирования данных

---

3. Исследовать основные методы кодирования данных

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

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

- теоретический анализ и синтез литературы по теме исследования,

- изучение и обобщение отечественной и зарубежной практики,

- сравнение,

- абстрагирование,

- конкретизация и идеализация,

- индукция и дедукция,

- аналогия,

- классификация,

- обработка и обобщение полученных данных.

1. Сущность и общие особенности представления данных

1.1 Определение представления данных

Информация может быть заключена множеством символов (букв, цифр, знаков препинания и т. д.). Последовательности символов представляют слова языка^[1].

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

Количество символов, которые можно задать последовательностью бит длины n, задается простой формулой . Таким образом, от нужного количества символов напрямую зависит количество используемой памяти.

При записи числа в прямом коде (англ. Signed magnitude representation) старший разряд является знаковым разрядом. Если его значение равно нулю, то представлено положительное число или положительный ноль, если единице, то представлено отрицательное число или отрицательный ноль. В остальных разрядах (которые называются цифровыми) записывается двоичное представление модуля числа. Например, число  в восьмибитном типе данных, использующем прямой код, будет выглядеть так: ^[2].

Таким способом в -битовом типе данных можно представить диапазон чисел .

Достоинства представления чисел с помощью прямого кода

---

1. Получить прямой код числа достаточно просто.
2. Из-за того, что  обозначает , коды положительных чисел относительно беззнакового кодирования остаются неизменными.
3. Количество положительных чисел равно количеству отрицательных.

Недостатки представления чисел с помощью прямого кода

1. Выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора (например, для вычитания невозможно использовать сумматор, необходима отдельная схема для этого).
2. Существуют два нуля:   и  , из-за чего усложняется арифметическое сравнение.

Из-за весьма существенных недостатков прямой код используется очень редко.

Код со сдвигом. Как видно, двоичное представление зациклено по модулю  ( нулей)

При использовании кода со сдвигом (англ. Offset binary) целочисленный отрезок от нуля до  ( — количество бит) сдвигается влево на , а затем получившиеся на этом отрезке числа последовательно кодируются в порядке возрастания кодами от  до . Например, число  в восьмибитном типе данных, использующем код со сдвигом, превратится в , то есть будет выглядеть так: .

По сути, при таком кодировании:

• к кодируемому числу прибавляют ;
• переводят получившееся число в двоичную систему исчисления.

Можно получить диапазон значений .

Достоинства представления чисел с помощью кода со сдвигом

1. Не требуется усложнение архитектуры процессора.
2. Нет проблемы двух нулей.

Недостатки представления чисел с помощью кода со сдвигом

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

---

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

Дополнительный код (дополнение до единицы)

Нумерация двоичных чисел в представлении c дополнением до единицы. В отличии от кода со сдвигом, нулю соответствуют коды и

В качестве альтернативы представления целых чисел может использоваться код с дополнением до единицы (англ. Ones' complement).

Алгоритм получения кода числа:

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

Пример: переведём число  в двоичный восьмибитный код. Прямой код модуля : , инвертируем и получаем . Для получения из дополнительного кода самого числа достаточно инвертировать все разряды кода.

Таким способом можно получить диапазон значений ^[3].

Достоинства представления чисел с помощью кода с дополнением до единицы

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

Недостатки представления чисел с помощью кода с дополнением до единицы

1. Выполнение арифметических операций с отрицательными числами требует усложнения архитектуры центрального процессора.
2. Существуют два нуля:  и .

В качестве примера переведём число  в дополнительный восьмибитный код. Прямой код модуля : , обратный — , прибавляем , получаем , приписываем  в качестве знакового разряда, в результате получаем .

---

Дополнительный код также удобно использовать для вычислений в длинной арифметике, особенно для операций сложения и вычитания. Это операции удобно выполнять с числами одинаковой длины, поэтому в старшие разряды меньшего числа нужно поместить нули (если число положительно) или единицы (если число отрицательно). Тогда числа будут выглядеть следующим образом: в старших разрядах бесконечное число нулей (единиц), а в младших разрядах уже встречаются и нули, и единицы, которые кодируют само число, а не знак^[4].

Удобство заключается в том, что нам не обязательно проделывать операции сложения с каждой парой бит, если мы знаем, что на этом отрезке в числах стоят либо единицы, либо нули. Таким образом, на этом отрезке в получившемся числе тоже будут либо только единицы, либо только нули. Операцию сложения можно выполнить только один раз для старших бит, таким образом мы узнаем знак получившегося числа. Вычитание тоже выполняется просто: инвертируем число, прибавляем один и получаем это число с минусом, затем просто делаем сложение. Однако умножение с числами, представленными дополнительным кодом, выполнять не всегда оптимально: алгоритм либо слишком медленный (наивный алгоритм работает за ), либо слишком сложный. Лучше для умножения использовать прямой код (бит под знак). Тогда можно числа перевести в десятичную систему счисления, выполнить быстрое преобразование Фурье за , затем перевести их обратно в двоичную. Обычно такой алгоритм работает быстрее, чем выполнение операции напрямую с двоичными числами. Для деления обычно тоже лучше использовать прямой код^[5].

1.2 Анализ сущности кодирования данных

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

С ростом производительности компьютеров стали появляться таблицы кодировок с большим количеством символов. Первой семибитной кодировкой стала ASCII7. В нее уже вошли прописные буквы английского алфавита, арабские цифры, знаки препинания. Затем на ее базе была разработана ASCII8, в которым уже стало возможным хранение 256 символов: 128 основных и еще столько же расширенных. Первая часть таблицы осталась без изменений, а вторая может иметь различные варианты (каждый имеет свой номер). Эта часть таблицы стала заполняться символами национальных алфавитов.

---