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

Прежде первая всего, развитие среднее движения число абсолютные двоичных удаляющемуся элементарных существование сигналов, дать приходящихся в законов закодированном положительное сообщении на через одну пример букву вторая исходного бесконечности сообщения, не обрывки может настоящее быть сказать меньше p1 log p 1 p2 log p 2 pn log pn – потребности энтропия смысле опыта, науки состоящего в развивалось распознавании геометрически одной останется буквы изучает текста прийти (или, положительное короче, неспособностью просто смысле энтропия время одной законов буквы). научном Отсюда дать сразу борьбу следует, что при видится любом плохой методе положительном кодирования для плохой записи знания длинного научном сообщения из М теряют букв наиболее требуется не знание меньше чем МН действительности двоичных постоянно знаков, и абсолютные никак не которому может математически превосходить развитии одного является бита.

Если потребности вероятности р1, р2, … …, рп не все закономерности равны рассуждая между знание собой, то Н бесконечностью < log n; человека поэтому человека естественно материальные думать, что конца учет настоящее статистических прийти закономерностей положительное сообщения бесконечности может знание позволить материальные построить код размеры более продолжающейся экономичный, чем удаляющемуся наилучший дать равномерный постоянно код, величины требующий не развитие менее М log n бесспорна двоичных потребности знаков для всякие записи ближе текста из М ограниченным букв.

1.2 Классификация закономерности назначения и способы представления кодов

Коды потребности можно закономерности классифицировать по рассуждая различным знание признакам [3, бесконечностью стр.203]:

1. По дать основанию поступательном (количеству положительное символов в развитие алфавите): постоянно бинарные время (двоичные бесконечностью m=2) и не обусловливается бинарные (m № 2).

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

---

3. По дать способам поступательном передачи: положительное последовательные и развитие параллельные; постоянно блочные - время данные бесконечностью сначала обусловливается помещаются в борьбу буфер, а неверно потом науки передаются в через канал и наиболее бинарные удаляющемуся непрерывные.

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

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

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

назад Коды для обмена данными и их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code). В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.) [6, стр.84].

---

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

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

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

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

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

---

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

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

Этот слабостью метод науки кодирования ближе состоит из установления двух через основных источником этапов:

• Построение слабостью оптимального науки кодового ближе дерева.
• Построение слабостью отображения науки код-символ на ближе основе установления построенного через дерева.

Алгоритм слабостью основан на науки том, что ближе некоторые установления символы из через стандартного источником 256-символьного рассуждая набора в сказать произвольном чисто тексте удаляющемуся могут которому встречаться целостное чаще поставленная среднего дальнейшем периода плохой повтора, а ставит другие - развитие реже. именно Следовательно, бесконечность если для плохой записи потребности распространенных потребности символов положительная использовать положительного короткие являющейся последовательности задаче бит, плохой длиной потребности меньше 8, а для иллюстрирована записи всякие редких движения символов - смысле длинные, то размеры суммарный математически объем научном файла целостное уменьшится [4, постоянно стр.158]. В время результате являющейся получается теряют систематизация бесконечность данных в математически виде задача дерева окончательно («двоичное неверно дерево»).

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

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

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

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

---

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

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

Поэтому стоимость хранения 39 кодовых слов в кодировке ASCII равна 312, независимо от относительной частоты отдельных символов в этом потоке. Алгоритм Хаффмана позволяет уменьшить стоимость хранения потока кодовых слов путем такого подбора длин кодовых слов, который минимизирует длину взвешенных путей. Будем называть дерево с минимальной длиной путей деревом Хаффмана.

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

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

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

Создается их родитель с весом, равным их суммарному весу;

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

Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0;

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

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

Табл. 1

15	7	6	6	5
А	Б	В	Г	Д

---