Файл: Изучение основных методов кодирования данных..pdf

В зависимости от целей кодирования, различают следующие его виды:

- кодирование по образцу - используется всякий раз при вводе данных в компьютер для их внутреннего представления;

- криптографическое кодирование, или шифрование, – используется, когда нужно защитить данные от несанкционированного доступа;

- эффективное, или оптимальное, кодирование – используется для устранения избыточности данных, т.е. снижения их объема, например, в архиваторах;

- помехозащитное, или помехоустойчивое, кодирование – используется для обеспечения заданной достоверности в случае, когда на сигнал накладывается помеха, например, при передаче данных по каналам связи [4, c. 94].

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

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

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

3. Эффективное кодирование. Этот вид кодирования используется для уменьшения объемов информации на носителе - сигнале. Для кодирования символов исходного алфавита используют двоичные коды переменной длины: чем больше частота символа, тем короче его код [2, c. 117].

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

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

Глава 2 Обзор методов кодирования данных

2.1 Метод Шеннона-Фано

Метод Шеннона-Фано просит упорядочения начального множества знаков по не возрастанию их частот. Далее исполняются последующие шаги:

а) список символов разделяется на две части так, чтобы суммы частот двух частей (обозначим их Σ₁ и Σ₂) были точно или приблизительно равны. В том случае, когда четкого равенства добиться не получается, разность между суммами должна быть минимальной;

б) кодовым комбинациям первой части дописывается 1, кодовым комбинациям второй части дописывается 0;

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

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

д) разбирается остальной список: если он пуст – код выстроен, работа завершается. Если нет, – исполняется шаг а) [10, c. 64].

Рассмотрим метод Шеннона-Фано на примере. Даны символы a, b, c, d с частотами f_a = 0,5; f_b = 0,25; f_c = 0,125; f_d = 0,125. Построим эффективный код методом Шеннона-Фано. Объединим начальные данные в таблицу, упорядочив их по не возрастанию частот:

Первая линия деления протекает под символом a: отвечающие суммы Σ₁ и Σ₂ одинаковы между собой и равны 0,5. Тогда создаваемым кодовым композициям дописывается 1 для верхней (первой) части и 0 для нижней (второй) части. Так как это первый шаг формирования кода, двоичные цифры не дописываются, а только принимаются формировать код:

В силу того, что верхняя часть списка содержит только один элемент (символ а), работа с ней заканчивается, а эффективный код для этого символа считается сформированным (в таблице, приведенной выше, эта часть списка частот символов выделена заливкой). Второе деление выполняется под символом b: суммы частот Σ₁ и Σ₂ вновь равны между собой и равны 0,25. Тогда кодовой комбинации символов верхней части дописывается 1, а нижней части – 0. Таким образом, к полученным на первом шаге фрагментам кода, равным 0, добавляются новые символы:

Поскольку верхняя часть нового списка содержит только один символ (b), формирование кода для него закончено (соответствующая строка таблицы вновь выделена заливкой). Третье деление проходит между символами c и d: к кодовой комбинации символа c приписывается 1, коду символа d приписывается 0:

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

Таким образом, получили коды: а - 1, b - 01, c - 001, d - 000.

Определим эффективность построенного кода по формуле:

I_cp = 0,5*1 + 0,25*01 + 0,125*3 + 0,125*3 = 1,75.

Поскольку при кодировании четырех символов кодом постоянной длины требуется два двоичных разряда, сэкономлено 0,25 двоичного разряда в среднем на один символ.

2.2 Метод Хаффмена

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

1) объединение частот:

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

- оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;

- предыдущие шаги повторяются до тех пор, пока ни получится единица в результате суммирования и список ни уменьшится до одного символа;

2) построение кодового дерева:

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

- ребра дерева кодируются: каждое левое кодируется единицей, каждое правое – нулём;

3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» веса проходимых рёбер [10, c. 68].

Рассмотрим метод Хаффмена на примере. Даны символы a, b, c, d с частотами f_a = 0,5; f_b = 0,25; f_c = 0,125; f_d= 0,125. Построим эффективный код методом Хаффмена.

1) Объединение частот (результат объединения двух последних частот в списке выделен в правом соседнем столбце заливкой):

2) Построение кодового дерева:

3) Формирование кода: a - 1; b - 01; c - 001; d -000.

Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.

Повысить эффективность кодирования можно, строя код не для символа, а для блоков из n символов, причем частота блока рассчитывается как произведение частот символов, входящих в блок. Рассмотрим этот тезис на примере.

Даны символы a и b с частотами, соответственно, 0,9 и 0,1. Построим эффективный код методом Шеннона-Фано для блоков из двух символов (n = 2).

Сформируем список возможных блоков и их частот. При этом частоту блока будем рассчитывать, как произведение частот символов, входящих в блок. Построение кода сведём в таблицу:

Таким образом, получены коды: aa – 1; ab - 01; ba - 001; bb - 000.

Определим эффективность построенного кода. Для этого рассчитаем сначала показатель эффективности для блока символов:

I_ср^блока = 0,81⋅1 + 0,09⋅2 + 0,09⋅3 + 0,01⋅3 = 1,28.

Поскольку в блоке 2 символа (n=2), для одного символа

I_ср=I_ср^блока/2 = 1,28/2 = 0,64.

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

Таким образом, при блочном кодировании выигрыш составил 1 - 0,64 = 0,36 двоичных разрядов на один кодируемый символ в среднем.

Эффективность блочного кодирования тем выше, чем больше символов включается в блок.

Особенностью эффективных кодов является переменное число двоичных разрядов в получаемых кодовых комбинациях. Это затрудняет процесс декодирования [15, c. 109].

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