49.Типы дискретных источников.

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

Вероятность совместного появления в любом сообщении символов и равна произведению вероятности появления каждого из этих символов.

Источник, символы которого не являются статистически независимыми, называется источником с памятью. Сообщение состоящее из N символов, называется N-кортежем. Статистическая зависимость символов выражается в том, что неопределенность в появлении N-го символа в N-кортежа уменьшается при увеличении количества символов, предшествующем N-му.

Наличие статистической зависимости между символами сообщения в источнике с памятью позволяет сделать вывод, что гораздо эффективнее кодировать группы символов нежели каждый символ по отдельности. Следовательно, символы исходного сообщения могут быть представлены в виде комбинации символов кода. Эти комбинации называются кодовыми словами. Таблица, устанавливающая соответствие между символами источника и кодовыми словами называется кодовым словарем.

50.Свойства кодов.

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

2. Единственность декодирования (однозначность дешифрования) – любая кодовая последовательность отображается в строку исходных символов единственным образом.

3. Свобода от префикса (Prefix-free) – любое кодовое слово не является префиксом некоторого другого кодового слова.

Свободный от префикса код называется мгновенно декодируемым или моментальным. Для моментальных кодов граница текущего кодового слова определяется последним символом этого слова, а не 1-ым символом следующего слова.

51. Показатели кодирования

Различают коды с фиксированной и переменной длиной. Код с фиксир. длиной легко дешифровать. Нужно просто подсчитать кол-во бит в дешифр. слове. С др.стороны обычно символы исходного алфавита имеют разные вероятности появления. В этом случае целесообразно применять коды с переменной длиной. В этом случае часто встречающиеся символы кодируются короткими словами, а редко встречающиеся – длинными. Существует теорема помехоустойчивого кодирования: если имеется источник без памяти с энтропией Н, то любой однозначно декодированный код с алфавитом размером М дает слова с размерностью, кот. не меньше чем L_min=Н/log₂М, где М – алфавит кода (длина), Н – энтропия ист-ка. Эта теорема дает возможность определить самый минимальный код, с помощью которого полностью описывается источник и не происходит искажение инф-ии. Если исп-ся двоич. код, то длина код. слова ограничена снизу значением энтропии. Если анализир-ся код с переменной длиной, то исп-ся показатель, наз. средней длиной кодовых слов : L_ср= Prob[X^*_m]l_m ,

где l_m – разрядность m-го кодового слова. Производительность декодера рассчитывается исходя из показателя L_ср, но некот. отд. слова могут иметь разрядность < или > L_ср. Эти несоответствия сглаживаются декодером с пом. буферизации.

Эффективность кода опр-ся : =(L_min/L_ср)*100

Избыточность кода : (L_cp - L_min)/L_cp.