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

5. В зависимости от цели и области применения условно можно выделить следующие типы кодов:

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

Коды для обмена данными и их передачи по каналам связи. Код ASCII (американский стандартный код для обмена информацией) широко использовался на ПК. ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку компьютеры работают с байтами, 8-й бит используется для синхронизации или проверки на четность или для расширения кода. Компьютеры IBM используют расширенный двоично-десятичный код обмена (EBCDIC) для обмена информацией. Коды телекоммуникаций CCITT (международный консультативный комитет по телефонии и телеграфии) и его модификации (MTK и др.) Широко используются в каналах связи.

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

Коды для специальных приложений - это коды, предназначенные для решения особых задач передачи и обработки данных. Примером таких кодов является циклический код Грея, который широко используется в АЦП угловых и линейных смещений. Коды Фибоначчи используются для создания высокоскоростных и бесшумных АЦП. [5, 2012 - 272с]

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

Матричное представление кодов. Используется для представления единообразных n-значных кодов. Для примитивного (полного и равномерного) кода матрица содержит n столбцов и 2n строк, т. Е. Код использует все комбинации. Для исправления ошибок (исправления, обнаружения и исправления ошибок) матрица содержит n - столбцов (n = k + m, где k - количество информационных битов, а m - количество контрольных битов) и 2k строк ( где 2k - количество разрешенных кодовых комбинаций). При больших значениях n и k матрица будет слишком громоздкой, а код написан в сокращенной форме. Матричное представление кодов используется, например, в линейных групповых кодах, кодах Хэмминга и т. Д. [6-2007 - 458с]

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

1.3 Метод кодирования Хаффмана

Д.А. предложил метод кодирования или сжатия информации на основе деревьев двоичного кодирования. Хаффман в 1952 году задолго до появления современного цифрового компьютера. Обладая высокой эффективностью, он и его многочисленные адаптивные версии являются основой многих методов, используемых в современных алгоритмах кодирования. Код Хаффмана редко используется один, часто работая в сочетании с другими алгоритмами кодирования. Метод Хаффмана является примером построения кодов переменной длины, имеющих минимальную среднюю длину. Этот метод производит идеальное сжатие, то есть сжимает данные до их энтропии, если вероятности символов в точности равны отрицательным степеням 2.

Этот метод кодирования состоит из двух основных этапов:

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

• Построение отображения кодового символа на основе построенного дерева.

Алгоритм основан на том факте, что некоторые символы из стандартного набора из 256 символов в произвольном тексте могут встречаться чаще, чем средний период повторения, а другие - реже. Поэтому, если вы используете короткие последовательности битов длиной менее 8 для записи общих символов и длинные для записи редких символов, общий размер файла будет уменьшаться. Результатом является систематизация данных в виде дерева («бинарное дерево»). [7- 2005. – с.116]

Пусть A={a1,a2,...,an} - алфавит из n различных символов, W={w1,w2,...,wn} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c1,c2,...,cn}, такой что:

- ci не является префиксом для cj, при i!=j; минимальна (|ci| длина кода ci) называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.

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

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

Пусть T - двоичное дерево, A = (0,1) - двоичный алфавит, и каждому ребру T-дерева присваивается одна из букв алфавита, так что все ребра, исходящие из одной вершины, помечаются разными буквами. Затем уникальное кодовое слово может быть назначено любому листу T-дерева, сформированному из букв, которые отмечают ребра, встречающиеся при переходе от корня к соответствующему листу. Особенностью описанного способа кодирования является то, что принятые коды являются префиксами.

Очевидно, что стоимость хранения информации, закодированной с использованием T-дерева, равна сумме длин путей от корня до каждого листа дерева, взвешенных по частоте соответствующего кодового слова или длине взвешенных путей. :, где - частота кодового слова длины во входном потоке. Рассмотрим, например, кодировку символов в стандарте ASCII. Здесь каждый символ является кодовым словом фиксированной (8-битной) длины, поэтому стоимость хранения определяется выражением, где W - количество кодовых слов во входном потоке.

Следовательно, стоимость хранения 39 кодовых слов в кодировке ASCII составляет 312, независимо от относительной частоты отдельных символов в этом потоке. Алгоритм Хаффмана снижает стоимость хранения потока кодовых слов, выбирая длины кодовых слов, которые минимизируют длину взвешенных путей. Мы будем называть дерево с минимальной длиной пути деревом Хаффмана. [8]

Классический алгоритм Хаффмана на входе получает таблицу частот появления символов в сообщении. Кроме того, на основе этой таблицы строится дерево кодирования Хаффмана (H-дерево).

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

2. Выбраны два свободных узла дерева с наименьшими весами;

Их родитель создан с весом, равным их общему весу;

Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка;

Одна дуга, которая покидает родителя, отображается на бит 1, другая на бит 0;

Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Это будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот. (см. приложение 1)

На первом шаге из листьев дерева выбираются два с наименьшими весами - Г и Д. Они присоединяются к новому узлу- родителю, вес которого устанавливается 5+6= 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д - ветви 1.

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

На следующем шаге «самой простой» парой являются узлы B / V и G / D.

Еще раз, для них создается родитель, теперь с весом 24. Узел B / V соответствует ветви 0 родителя, G / D соответствует ветви 1.

На последнем шаге в свободном списке осталось только 2 узла - это узел A и узел B (B / C) / (G / D). Еще раз создается родитель с весом 39, и прежние свободные узлы объединяются в его разные ветви.

Поскольку только один узел оставался свободным, алгоритм построения дерева кодирования Хаффмана завершен.

Каждый символ, включенный в сообщение, определяется как объединение нулей и связанных с краями дерева Хаффмана на пути от корня к соответствующему листу.

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

Самый частый символ сообщения A кодируется с наименьшим количеством битов, а самый редкий символ D - с наибольшим. Стоимость хранения закодированного потока, определяемая как сумма длин взвешенных путей, определяется выражением 15 * 1 + 7 * 3 + 6 * 3 + 6 * 3 + 5 * 3 = 87, что значительно меньше, чем стоимость хранения входного потока (312).

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

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

Классический алгоритм Хаффмана имеет один существенный недостаток. Чтобы восстановить содержимое сжатого сообщения, декодер должен знать таблицу частот, используемую кодером. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которую следует отправлять перед данными, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость полной статистики частоты перед началом самого кодирования требует двух проходов сообщения: один для построения модели сообщения (таблица частот и дерево Хаффмана), а другой для кодирования. [9]

2. Программная реализация алгоритма кодирования Хаффмана

2.1 Описание процесса реализации алгоритма кодирования Хаффмана

Программную реализацию алгоритма кодирования Хаффмана мы выполнили в объектно-ориентированной технологии программирования, среды разработки Borland Delphi 7.0. и на языка программирования Delphi.

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

• записываем подряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;

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

• Мы прослеживаем путь до каждого листа дерева, отмечая направление к каждому узлу (например, справа - 0, слева - 1).[11]

Чтобы определить, сколько повторяющихся символов в сообщении и каковы все сообщения, я рассмотрел введенные символы как одну строку «s», ввел дополнительную переменную для подстроки «st» и создал цикл, для которого вся проверенная строка является условием выхода. Используя стандартную функцию «pos», я нашел одну и ту же подстроку в строке, т.е. те же самые символы в строке s. Найдя те же символы, он удалил найденный и увеличил количество удаленных. Приращение - это число идентичных символов.

Но каждый проверенный символ нужно опять добавить в массив с его числовым вхождением. Для этого был использован тот же самый массив, но он увеличивался на то количество, которое было проверено «setlength(a,KolSim)». В «Memo1» вывел результат подсчета символов.

begin

Button2.Enabled:=true;

Button1.Enabled:=false;

Memo1.Clear;

Memo2.Clear;

s:=Edit1.text;

st:=s;

KolSim:=0;

while length(s)>0 do

begin

c:=s[1];

j:=0;

repeat

i:=pos(c,s);

if i>0 then

begin

inc(j);

delete(s,i,1);