12.Кодирование сообщений в дискретном канале: кодирующее отображение, равномерный и неравномерный коды, декодирование.

K – это процесс преобразования одной формы представления информации в другую с целью обеспечения удобства её хранения и передачи. Кодирующим отображением Г называют отображение множества слов в некотором алфавите в множество слов в этом же или другом алфавите. Входное множество символов – входной алфавит, выходное множество выходным. Применение кодирующего отображения Г к слову, представленному во входном алфавите, называется кодированием, а само правило кодирования Г – кодом.

Пример: A={p,q,r,s}, B={a,b}. Г(qprrs)=abaabababb.

Слово, составленное из символов выходного алфавита, называется кодовой комбинацией. Коды, формирующие кодовые комбинации различной длины, называются неравномерными, а одинаковой – равномерными. Длина кодовых комбинаций равномерного кода называется значностью кода. Процесс обратный кодированию – декодирование(Г^-1). β=Гα, α= Г^-1β.Код д.б. обратимым.Это означает, что преобразование Г^-1 единственное, т.е. зная кодовую комбинацию β, можно однозначно восстановить исходн.сообщ.

Часто в сист-ах передачи инф-ции исп-ся в качестве входн. алфавита символы естеств. языка, ва в кач-ве выходного алф – 0 и 1.тогда н-р, для кодирования символов русск.алф-та, достаточно 5-значн кода.

13.Эффективное кодирование. Формула для построения кода, близкого к эффективному.

Одной из хар-к сообщ явл-ся избыточность. Рассм. такой пример: в русс. языке имеется 33 буквы алф. Ск-ко слов можно составить имея такой алф.? 1букв-33,2букв-33²,3букв-33³…В ест языке большая изб-ть позволяет повысить помехоуст-ть, однако это ока-ся невыгодным, и всегда треб-ся знать,какое min кол-во символов нужно использ-ть для передачи заданного кол-ва инф-ции. Задача кодирования без избыточности наз-ся эфф. код-ем.Очевидно, что для уменьш-ния изб-ти необх. выбирать наиболее короткие кодовые комб-ции, и чем выше вер-ть их появления, тем короче д.б. эта комб-ция.

Пусть кодирующее отображение X={x₁,x₂,…,x_r}, это B, а |m| мощность.

Кодирующее отображение В каждому x_i ставит в соответствие некоторую кодовую комбинацию длительностью n_i из алфавита В. Задача: Оценить минимальную среднюю длину кодовой комбинации кода Г. Зная эту величину и сравнивая ее со средней длиной кодового слова реального кода, можно определить, насколько реально код близок к оптимальному. Известна вероятность P(x_i), и энтропия равна H(x)= -∑[i=1, k] P(x_i)*log₂P(x_i), Средняя длина n_ср=∑_i=1^rP_i*n_i. Максимальная энтропия, которую может иметь сообщение из символов алфавита В: H_max=n_ср*log₂m, т.к. H_max≥H(x), то n_ср*log₂m ≥ -∑_i=1^r P(x_i)*log₂P(x_i). Рассмотрим частный случай, при котором избыточность = 0. (H(x)=H_max), k_i – коэффициент избыточности.

k_i=(H_max – H(x))/H_max), k_i=(n_ср - n_min). ∑_i=1^r n_i*P(x_i)*log₂ m =-∑[i=1, r] P(x_i) log₂ P(x_i), ∑_i=1^r(P(x_i)*(n_ilog₂m+log₂P(x_i))=0, n_i log₂ m + log₂ P(x_i)=0, n_i= -log₂(P(x_i))/log₂m (*). Из (*) следует, что длина i-ой кодовой комбинации ~ (-log) вероятности появления i-го сообщения. Левая часть – целое число, правая часть – чаще всего нецелое. Полученное условие для реал. построения эффективного кода не может быть использовано, т.к. все равенство не выполняется. Но можно потребовать, чтобы n_i лежало в некотором диапазоне полученного значения, в котором обязательно найдется одно целое.

- log₂P(x_i)/log₂m ≤ n_i ≤ (- log₂P(x_i)/log₂(m)) +1, умножим обе части на P(x_i) …. - ∑_i=1^rP(x_i)log₂ P(x_i)/log₂m ≤ ∑_i=1^rP(x_i)n_i ≤ (-∑_i=1^rP(x_i)*log₂P(x_i)/log₂ m)+ ∑_i=1^rP(x_i),

H(x)/log₂m≤nср≤(H(x)/log₂ m)+1 (**).

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