39. Коды с минимальной избыточностью (коды Хаффмана), метод построения.

Пусть р₁, р₂,…, р_r– частоты (вероятности), с которыми буквы алфавитавстречаются в исходных сообщениях. Частоты неотрицательны и удовлетворяют равенству.

Определение. Избыточностью схемы алфавитного кодирования Σ с длинами кодовых словl₁,l₂,…,l_r при заданных частотах р₁, р₂,…, р_rназывается число.

Избыточность схемы согласно определению равна .

Пример 1. При заданных частотах р₁= 0.4, р₂= 0.25, р₃= 0.2, р₄= 0.15 сравнить избыточность двух схем Σ₁и Σ₂, где

Заметим, что Σ₁– равномерная схема, а Σ₂– префиксная, поэтому обе эти схемы однозначно декодируемы. В схеме Σ₁длины кодовых словl₁ =l₂ =l₃ =l₄= 2, следовательно, её избыточность равна.

В схеме Σ₂длины кодовых словl₁ = 1,l₂ = 2,l₃ =l₄= 3, поэтому её избыточность равна.

Пример 2. Для набора частот р₁ = 0.4, р₂ = 0.25, р₃ = 0.2, р₄ = 0.1, р₅ = 0.05 требуется построить суффиксный код Хафмана с исходным алфавитоми кодирующим алфавитом.

0.4	0.4	0.4	0.6
0.25	0.25	0.35	0.4
0.2	0.2	0.25
0.1	0.15
0.05

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

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

Около каждой концевой вершины дерева указана частота, а в скобках - соответствующее ей кодовое слово кода Хафмана. В итоге получаем префиксную схему Σ_пкода Хафмана

Однако по условию задачи требовалось построить суффиксную схему кодирования. Она легко получается «зеркальным отражением» префиксной схемы Σ_п.Следовательно, искомый суффиксный код Хафмана задается схемой Σ_с, где.

Избыточность построенного кода равна

40. Линейные коды, порождающая матрица, двойственный код.

Определение. Коды с кодирующим алфавитом В = {0,1} называются двоичными кодами.

Определение. Булева функция f (x₁,x₂,…,x_n) называется характеристической функцией двоичного кода, если она обращается в единицу на тех и только тех наборах, которые являются кодовыми словами этого кода.

Утверждение.Пусть− два кодовых слова двоичного кода Σ. Черезобозначается расстояние Хэмминга между двумя кодовыми словамии, которое вычисляется по формуле. Формула означает, что расстояние Хэмминга между двумя кодовыми словами равно числу позиций, в которых эти слова различаются.

Определение. Кодовым расстоянием двоичного кода называется минимальное расстояние Хэмминга между двумя его кодовыми словами. Кодовое расстояние схемы Σ – это минимальное число позиций, в которых могут отличаться два её кодовых слова. Геометрическая интерпретация кодового расстояния − это длина кратчайшей цепи, которая соединяет две вершины n-мерного единичного куба, отвечающие кодовым словам данной схемы.

Утверждение.Говорят, что кодовые словалинейно зависимы, если хотя бы одно из них является линейной комбинацией остальных слов из этого набора. Если же ни одно из них не является линейной комбинацией остальных слов, то они считаются линейно независимыми.

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

Из определения линейного кода можно получить следующие его свойства:

• Любой линейный код содержит нулевое кодовое слово, т.е. слово, состоящее только из нулей.

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

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

• Линейный код размерности rимеет мощность 2^r, т.е. содержит ровно 2^rкодовых слов.

• Кодовое расстояние линейного кода равно минимальному числу единиц в ненулевом кодовом слове этого кода.

Определение. Порождающей матрицей линейного кода размерности r с длинами кодовых слов, равными n, называется матрица размера r на n, в строках которой стоят базисные кодовые слова этого кода.

Определение. Кодовые слова иназываютсяортогональными, если. Каждое слово ортогонально нулевому слову. Кроме того, оно может быть ортогонально и самому себе. Например, слово (0101) ортогонально словам (0000), (0010), (1000), (1010), (0101), (0111), (1101) и (1111). Обратим внимание на то, что эти восемь слов образуют линейный код.

Определение. Двойственным кодом к линейному коду Σ называется двоичный код, каждое кодовое слово которого ортогонально любому кодовому слову кода Σ. Двойственный код обладает рядом свойств. Наиболее важное из них состоит в том, что двойственный код к линейному коду размерности r сам является линейным кодом размерности (n – r) , где n – длина кодового слова.