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

ВВЕДЕНИЕ

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

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

Глава 1. Понятие кодирования

В начале 20 века появляются теории кодирования и информации. В 1948 г. статьи К. Шеннона положили начало для развития этих теорий, а также для дальнейших работ в этой области.

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

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

На рисунке 1 представлена основная модель, которую изучает теория информации – модель системы передачи сигналов:

ШУМ

Источник

Кодер

источника

Канал

Приемник

Кодер

канала

Декодер

канала

Декодер

источника

Рисунок 1 – Модель системы передачи сигналов

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

• алфавит источника – множество различных символов, порождаемых некоторым источником [2].
• размер алфавита источника – количество символов в множестве всех символов.

Как пример можно привести текст на русском языке. Текст порождается источником с алфавитом из 33 русских букв, знаков препинания, а так же пробелами.

Кодирование дискретного источника заключается в сопоставлении символов алфавита А источника символам некоторого другого алфавита В. Обычно символу исходного алфавита ставится в соответствие группа символов алфавита В, которая называется кодовым словом. Сразу возникают два определения:

• Кодовый алфавит – множество различных символов, используемых для записи кодовых слов [3].
• Код – совокупность всех кодовых слов, которые применяются для представления порождаемых источником символов.

Самым популярным примером является Азбука Морзе, где каждой букве языка соответствуют кодовые слова (последовательности) из «точек» и «тире».

В случае, когда размер кодового алфавита равен двойке, рассматривается двоичное кодирование. Конечная последовательность битов (0 или 1) называется кодовым словом, а количество битов в этой последовательности – длиной кодового слова.

Дано строгое определение кодирования. Пусть даны алфавит источника , кодовый алфавит . обозначено, как множество всевозможных последовательностей в алфавите А (В). Множество всех возможных сообщений в алфавите А приняло значение S. Тогда отображение , которое преобразует множество сообщений в кодовые слова в алфавите В, называется кодированием. Если , то – кодовое слово. Обратное отображение (если оно существует) называется декодированием.

Обычно задача кодирования сообщения имеет следующий вид. Требуется при заданных алфавитах А и В и множестве сообщений S найти такое кодирование F, которое обладает определенными свойствами и оптимально в некотором смысле. Свойства, которые требуются от кодирования, могут быть различными. Самый распространённые из них:

1. существование декодирования;
2. помехоустойчивость или исправление ошибок при кодировании;
3. обладает заданной трудоемкостью (время, объем памяти).

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

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

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

Метод сжатия данных делится на две группы:

• статические методы, предназначенные для кодирования конкретных источников информации с известной статистической структурой, порождающих определенное множество сообщений. Методы этой группы основывается на знании статистической структуры первоначальных данных. Наиболее распространенные примеры: арифметический код, код Фано, Хаффмана, Шеннона.
• адаптивные методы используются при неизвестной статистики источника информации, либо она изменяется с течением времени. В этой группе методов, во время кодирования очередного символа, применяется информация о ранее закодированной части сообщения, что способствует определению вероятности появления очередного символа. Во время кодирования адаптивные методы адаптируются на статистическую структуру кодируемых сообщений, точнее коды символов меняются в зависимости от накопленной статистики данных. Что позволяет адаптивным методам продуктивно и скоро кодировать сообщение за один сеанс. К этой группе относится множество различных методов сжатия данных. Самые известные – адаптивный код Хаффмана, код «стопка книг», интервальный и частотный коды

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

Если рассмотреть группу методов кодирования, при которых не учитывается вероятность появления символов источника и учесть, что каждый символ имеет номер, то алфавит представляет собой целые числа. Такие методы также называют представлением целых чисел, так как каждому целому числу из определенного диапазона ставится в соответствие свое кодовое слово [5].

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

Методы кодирования целы чисел обычно делят на две группы:

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

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

В рассматриваемой группе кодов под запись порядка числа отводится установленный объем бит, значение порядка зависит от числа бит, выделяемого под мантиссу. Для осуществления процесса кодирования целого числа нужно:

• определить порядок числа и количество бит мантиссы;
• иметь под рукой таблицу кодовых слов.

Лучше всего рассмотреть процесс построения кода на примере:

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

Таблица 1 – Код класса Fixed + Variable

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

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

Таблица 2 – Код класса Variable + Variable

Если в кодах исключить кодовое слово для нуля, то можно уменьшить длины кодовых слов на 1 бит, убрав первый ноль. Таким образом строится гамма-код Элиаса (γ-код Элиаса).

Таблица 3 – Гамма-код Элиаса

Еще одним примером кода класса Variable + Variable является омега-код Элиаса (ω-код Элиаса). В нем кодовое слово для единицы задается отдельно. Другие кодовые слова состоят из последовательности групп длиной L₁, L₂,…, L_m, начинающихся с единицы. Конец всей последовательности задается нулевым битом. Длина первой группы составляет 2 бита, длина каждой следующей группы равна двоичному значению битов предыдущей группы плюс 1. Значение битов последней группы является итоговым значением всей последовательности групп, т.е. первые m - 1 групп служат лишь для указания длины последней группы.

Таблица 4 – Омега-код Элиаса