Теорема Шеннона об источнике шифрования - Доказательство теоремы об источнике шифрования для кодов символов

Интернет магазин китайских планшетных компьютеров

Компьютеры - Теорема Шеннона об источнике шифрования - Доказательство теоремы об источнике шифрования для кодов символов

22 января 2011

Оглавление:
1. Теорема Шеннона об источнике шифрования
2. Доказательство теоремы об источнике шифрования
3. Доказательство теоремы об источнике шифрования для кодов символов

Пусть s_i длина слова для каждого возможного x_i. Определим $q_i = a^{-s_i}/C$ , где С выбирается таким образом, что: $\sum q_i = 1$ .

Тогда

$\begin{matrix} H &=& - \sum_{i=1}^n p_i \log_2 p_i \\ && \\ &\leq& - \sum_{i=1}^n p_i \log_2 q_i \\ && \\ &=& - \sum_{i=1}^n p_i \log_2 a^{-s_i} + \sum_{i=1}^n p_i \log_2 C \\ && \\ &=& - \sum_{i=1}^n p_i \log_2 a^{-s_i} + \log_2 C \\ && \\ &\leq& - \sum_{i=1}^n - s_i p_i \log_2 a \\ && \\ &\leq& \mathbb{E}S \log_2 a \\ \end{matrix}$

где вторая строка является неравенством Гиббса, а пятая строка является неравенством Крафта $C = \sum_{i=1}^n a^{-s_i} \leq 1$ $\log C \leq 0$ .

для второго неравенства мы можем установить

$s_i = \lceil - \log_a p_i \rceil$

и так

$- \log_a p_i \leq s_i < -\log_a p_i + 1$

а затем

$a^{-s_i} \leq p_i$

$\sum a^{-s_i} \leq \sum p_i = 1$

таким образом минимальное S удовлетворяет

$\begin{matrix} \mathbb{E}S & = & \sum p_i s_i \\ && \\ & < & \sum p_i \left \\ && \\ & = & \sum - p_i \frac{\log_2 p_i}{\log_2 a} +1 \\ && \\ & = & \frac{H}{\log_2 a} +1 \\ \end{matrix}$

<<< Сжатие с использованием вейвлет

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие