Коды Шеннона-Фано, Хафмана, Лемпела-Зива.

Методы сжатия делятся на статистические и словарные. Словарные методы заключаются в том, чтобы в случае встречи подстроки, которая уже была найдена раньше, кодировать ссылку, которая занимает меньше места, чем сама подстрока. Классическим словарным методом является метод Лемпела-Зива (LZ). Все используемые на сегодняшний день словарные методы являются лишь модификациями LZ.
Статистическое кодирование заключается в том, чтобы кодировать каждый символ, но использовать коды переменной длины. Примером таких методов служит метод Хаффмана (Huffman). Обычно словарные и статистические методы комбинируются, поскольку у каждого свои преимущества.

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

Кодирование Шеннона-Фано - алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия.

Данный метод выделяется своей простотой. Берутся исходные сообщения m(i) и их вероятности появления P(m(i)). Этот список делится на две группы с примерно равной интегральной вероятностью. Каждому сообщению из группы 1 присваивается 0 в качестве первой цифры кода. Сообщениям из второй группы ставятся в соответствие коды, начинающиеся с 1. Каждая из этих групп делится на две аналогичным образом и добавляется еще одна цифра кода. Процесс продолжается до тех пор, пока не будут получены группы, содержащие лишь одно сообщение. Каждому сообщению в результате будет присвоен код x c длиной –lg(P(x)). Это справедливо, если возможно деление на подгруппы с совершенно равной суммарной вероятностью. Если же это невозможно, некоторые коды будут иметь длину –lg(P(x))+1. На шаге делеения алфавита существует неоднозначность, так как разность суммарных вероятностей p ₀ − p ₁ может быть одинакова для двух вариантов разделения (учитывая, что все символы первичного алфавита имеют вероятность, большую нуля). Алгоритм Шеннона-Фано не гарантирует оптимального кодирования.

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

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

В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m₂ с более чем двумя символами.

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

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

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

 

Алгоритм

 

1. Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).

2. Символы первичного алфавита m₁ выписывают в порядке убывания вероятностей.

3.Последние n₀ символов объединяют в новый символ, вероятность которого равна суммарной вероятности этих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующее место (по вероятности). n₀ вычисляется из системы:
,
где a — целое число, m₁ и m₂ — мощность первичного и вторичного алфавита соответственно.

4. Последние m₂ символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.

5. Предыдущий шаг повторяют до тех пор, пока сумма всех m₂ символов не станет равной 1.

Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m₂ потомков — символы из предыдущего шага и т.д.

Каждые m₂ элементов, стоящих на одном уровне, нумеруются от 0 до m₂-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ, стоящий в листе и производится возврат в корень.

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

Алгори́тм Ле́мпеля — Зи́ва -это универсальный алгоритм сжатия данных без потерь. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.

Схема сжатия без потерь Лемпела-Зива позволяет работать с данными любого типа, обеспечивая достаточно быстрое сжатие и распаковку данных. На основе входного потока данных алгоритм формирует словарь данных (его также называют переводной таблицей или таблицей строк). Образцы новых данных сравниваются с записями словаря. Если они там не представлены, то создается новая кодовая фраза. Если строка повторно встречается во входном потоке, то в выходной поток записывается ссылка на соответствующую строку словаря, которая имеет меньшую величину, чем исходный фрагмент данных. Таким образом реализуется сжатие информации.

Декодирование LZW-данных производится в обратном порядке. Декомпрессор читает код из потока данных и, если этого кода еще нет в словаре, добавляет его туда. Затем этот код переводится в строку, которую он представляет, и заносится в выходной поток несжатых данных.

/** Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками. По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.

Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. **/

 

 

5 .Коды Хэмминга, свойство оптимальности

Коды Хэмминга

Помехоустойчивый код - двоичный код, позволяющий обнаруживать и корректировать ошибки при передаче данных. Код Хэмминга обнаруживает ошибки в двух битах и позволяет корректировать один бит. Контрольные разряды занимают позиции с номерами i = 2^j, j=0,1,2,.... Значения контрольных разрядов равно сумме разрядов, номера которых больше номера контрольного разряда и таких, что двоичное представление номера содержит единицу в разряде j начиная с младших разрядов.

B2 = B3 + B6 + B7 + B10 + B11 (если длина исходного слова 7 бит)

Если слово полученное после подстановки контрольных разрядов передано правильно, то выражение полученное в результате сложения контрольных разрядов и суммы, вычисленной по вышеуказнному правилу, будет равно 0.

S2= B2 + B3 + B6 + B7 + B10 + B11 (если длина исходного слова 7 бит)

Если какой-то разряд исказился, некоторые значения выражений будут равны 1. Пусть исказился Bi, тогда первое значение (S1) станет равно 1, если двоичное представление i содержит 1 в младшем разряде. Второе значение (S2), если во втором и т.д. Величина..,S3,S2,S1 - номер искажённого разряда.

entity Hamming is
port(Ic: in std_ulogic_vector(6 downto 0);
Id: in std_ulogic_vector(10 downto 0);
Oc: in std_ulogic_vector(10 downto 0);
Od: in std_ulogic_vector(6 downto 0);
end Hammaing;

Ic - вход для кодирования
Id - вход для декодирования
Oc - закодированное слово Ic
Od - декодированное слово Id