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

Сравнение способов кодирования

На рисунке 1 показаны диаграммы сигналов, формируемых при записи на жесткий диск ASCII-кода символа “X” для трех различных способов кодирования [9, c.19].

В верхней строке каждой из этих диаграмм показаны отдельные биты данных (01011000) в битовых ячейках, границами которых являются синхронизирующие сигналы, обозначенные точками. Под этой строкой изображен сам сигнал, представляющий собой чередование положительных и отрицательных значений напряжения, причем в моменты смены полярности напряжения происходит запись зоны смены знака. В нижней строке показаны ячейки перехода, причем T обозначает ячейку, содержащую зону смены знака, а N — ячейку, в которой зоны смены знака нет [10, c.56].

Разобраться в FM-кодировании очень просто. В каждой битовой ячейке содержится две ячейки перехода: одна для синхронизирующего сигнала, другая для самих данных. Все ячейки перехода, в которых записаны сигналы синхронизации, содержат зоны смены знака. В то же время ячейки перехода, в которых записаны данные, содержат зону смены знака только в том случае, если значение бита равно логической единице. При нулевом значении бита зона смены знака не формируется. Поскольку в примере значение первого бита — 0, он будет записан в виде комбинации TN. Значение следующего бита равно 1, и ему соответствует комбинация TT. Третий бит тоже нулевой (TN) и т.д. С помощью приведенной выше диаграммы FM-кодирования легко проследить всю кодирующую комбинацию для рассматриваемого примера байта данных. При таком способе записи зоны смены знака могут следовать непосредственно одна за другой; в терминах RLL-кодирования это означает, что минимальный “пробег” равен нулю. С другой стороны, максимально возможное количество пропущенных подряд зон смены знака не может превышать единицы; вот почему FM-кодирование можно обозначить как RLL 0,1 [20, c.89].

При MFM-кодировании в ячейках также записывается синхросигнал и биты данных. Но, как видно из схемы, ячейки для записи синхросигнала содержат зону смены знака только в том случае, если значения и текущего и предыдущего битов равны нулю. Первый бит слева — нулевой, значение же предыдущего бита в данном случае неизвестно, поэтому предположим, что он тоже равен нулю. При этом последовательность зон смены знака будет выглядеть как TN. Значение следующего бита равно единице, которой всегда соответствует комбинация NT. Следующему нулевому биту предшествует единичный, поэтому ему соответствует последовательность NN. Аналогичным образом можно проследить процесс формирования сигнала записи до конца байта. Легко заметить, что минимальное и максимальное число ячеек перехода между любыми двумя зонами смены знака равно 1 и 3 соответственно [16, c.88]. Следовательно, MFM-кодирование в терминах RLL может быть названо методом RLL 1,3.

Рисунок 1 - Сигналы, формируемые во время записи ASCII-кода символа “X” при способах кодирования FM, MFM и RLL 2,7

Поскольку в данном случае используется только половина зон смены знака (по сравнению с FM-кодированием), частоту синхронизирующего сигнала можно удвоить, сохранив при этом то же расстояние между зонами смены знака, которое использовалось при методе FM. Это означает, что плотность записываемых данных остается такой же, как при FM-кодировании, но данных кодируется вдвое больше [3, c.56].

Сложнее реализован метод RLL 2,7, поскольку в нем кодируются не отдельные биты, а их группы. Первая группа слева, совпадающая с одной из приведенных в табл. 2 комбинаций, состоит из трех битов: 010. Она преобразуется в такую последовательность зон смены знака: TNNTNN. Следующим двум битам (11) соответствует комбинация TNNN, а последним трем (000) — NNNTNN. Как видите, в данном примере для корректного завершения записи дополнительные биты не потребовались [13, c.19].

В этом примере минимальное и максимальное число пустых ячеек перехода между двумя зонами смены знака равно 2 и 6 соответственно, хотя в другом примере максимальное количество пустых ячеек перехода может равняться 7. Именно поэтому такой способ кодирования называется RLL 2,7. Поскольку в данном случае записывается еще меньше зон смены знака, чем при MFM-кодировании, частоту сигнала синхронизации можно увеличить в 3 раза по сравнению с методом FM и в 1,5 раза по сравнению с методом MFM. Это позволяет на таком же пространстве диска записать больше данных. Но необходимо отметить, что минимальное и максимальное физическое расстояние на поверхности диска между любыми двумя зонами смены знака одинаково для всех трех упомянутых методов кодирования [5, c.76].

Декодеры PRML (Partial-Response, Maximum-Likelihood)

В последнее время в накопителях вместо традиционных усилителей считывания с пиковыми детекторами стала использоваться так называемая технология PRML (Partial-Response, Maximum-Likelihood — частичное определение, максимальное правдоподобие). Это позволяет повысить плотность расположения зон смены знака на диске в среднем на 40% и на столько же увеличить емкость носителя [4, c.11].

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

В настоящее время в самых новых накопителях на жестких дисках с успехом используется описанная схема PRML.

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

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

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

• построение оптимального кодового дерева;
• построение отображения код-символ на основе построенного дерева [13, c.88].

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

Пусть A={a₁,a₂,...,a_n} - алфавит из n различных символов, W={w₁,w₂,...,w_n} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c₁,c₂,...,c_n}, такой что c_i не является префиксом для c_j, при i!=j; минимальная (|c_i| длина кода c_i) называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана [20, c.91].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 3

Исходная таблица частот

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д.

Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д - ветви 1.

На последнем шаге в списке свободных осталось только 2 узла - это узел А и узел Б (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39, и бывшие свободные узлы присоединяются к разным его ветвям.

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

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

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

Таблица 4

Коды Хаффмана

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

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

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

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