Оптимальный код. Код Хаффмена.

Пусть сообщения A ₁, A ₂,..., A_N имеют вероятности р ₁, p ₂, …, p_N (p ₁ ³ p ₂³ … p_N) и кодируются двоичными словами a _l, a ₂, …, a_N, имеющими длины l ₁, l ₂,..., l_N. Какими свойствами должен обладать двоичный код, если он оптимален.

1. В оптимальном коде менее вероятное сообщение не может кодироваться более коротким словом, т. е. если p_i < p_j, то l_i ³ l_j.

2. Если код оптимален, то всегда можно так перенумеровать сообщения и соответствующие им кодовые слова, что p ₁ ³ p ₂³ … p_N и при этом l ₁£ l ₂£... £ l_N (1)

Из неравенств (1) следует, что сообщение A_N кодируется словом a_N наибольшей длины l_N.

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

Рассмотрим новое множество сообщений A⁽¹⁾ = {A₁, А₂, …, A_N-2, А} с вероятностями р ₁, p ₂, …, p_N-2, p = p_{N- 1} + p_N. Оно получается из множества {A₁, А₂, …, A_N-2, А_N-1, A_N } объединением двух наименее вероятных сообщений A_N-1, A_N в одно сообщение А. Будем говорить, что A⁽¹⁾ получается сжатием из {A₁, _А2, …, A_N-2, А_N-1, A_N }

Пусть для A⁽¹⁾ построена некоторая система кодовых обозначений K⁽¹⁾ ={a₁, а₂,..., a_N-2, а}, иными словами, указано некоторое кодовое дерево с концевыми вершинами a₁, а₂,..., a_N-2, а. Этой системе можно сопоставить код K ={a₁, а₂,..., a_N-2, a_N-1, а_N} для исходного множества сообщений, в котором слова a_N-1 и а_N получаются из слова а добавлением соответственно 0 и 1. Процедуру перехода от K⁽¹⁾ к K назовем расщеплением.

Справедливо следующее утверждение, открывающее путь для построения оптимального кода:

Если код K⁽¹⁾ для множества сообщений A⁽¹⁾ является оптимальным, то оптимален также и код K для исходного множества сообщений.

Код Хаффмена:

Для построения оптимального кода можно использовать последовательные сжатия исходного множества сообщений.

 

Кодирование и декодирование при передаче информации по каналам связи с «шумом». Математическая модель системы связи. Вектор ошибок.

Коды с обнаружением ошибок и коды с исправлением ошибок.

Блочный двоичный (m, n)-код определяется двумя функциями: E: {0, 1} ^m ® {0, 1} ⁿ и D: {0, 1} ⁿ ® {0, 1} ^m, где m £ n и {0, 1} ⁿ — множество всех двоичных последовательностей длины n. Функция E определяет схему кодирования, а функция D — схему декодирования.

Здесь T —функция ошибок;

E и D выбираются таким образом, чтобы композиция D ° T ° E была функцией, с большой вероятностью близкой к тождественной.

Двоичный (m, n)-код содержит 2 ^m кодовых слов.

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

Расстояние Хемминга. Вес слова, вес поразрядной суммы.

На множестве двоичных слов длины m расстоянием d (a, b) между словами a и b называют число несовпадающих позиций этих слов.

Определенное таким образом понятие называется расстоянием Хемминга. Оно удовлетворяет следующим аксиомам расстояний:

1) d (a, b) ³ 0 и d (a, b) = 0 тогда и только тогда, когда a = b;

2) d (a, b) = d (b, a);

3) d (a, b) + d (b, c) ³ d (a, c) (неравенство треугольника).

Весом w (a) слова a называют число единиц среди его координат. Тогда расстояние между словами a и b есть вес их суммы a Å b: d (a, b) = w (a Å b), где Å — операция покоординатного сложения по модулю 2.

 

Теорема о наименьшем расстоянии между кодовыми словами, необходимом для обнаружения ошибок.

Для того, чтобы код позволял обнаруживать ошибки в k (или менее) позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было ³ k + 1.

 

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

Для того, чтобы код позволял исправлять все ошибки в k (или менее) позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было ³ 2k + 1.