Основные теоремы

Некоторые результаты теории вероятностей

Среднее

для действительной случайной переменной \(x\) из ансамбля \(X\), среднее значение определяется как \(\overline x = \sum_x P(x) x\)

Дисперсия

для действительной случайной переменной \(x\) из ансамбля \(X\), дисперсия определяется как \(\sigma_x^2 = \sum_x P(x) (x-\overline x)^2\)

Первое Неравенство Чебышева

Пусть \(t\) неотрицательная действительная случайная переменная, а \(\alpha\) – положительное действительное число. Тогда, \[P(t\ge \alpha) \le \frac{\overline t}{\alpha}\]

Доказательство: \(P(t\ge\alpha)=\sum_{t\ge\alpha}P(t)\). Умножая каждый член правой части на \(\frac{t}{\alpha}\ge 1\): \(P(t\ge\alpha)\le\sum_{t\ge\alpha}P(t)\frac{t}{\alpha}\). Добавляя недостающие (заведомо положительные) члены в сумму: \(P(t\ge\alpha)\le \frac{1}{\alpha}\sum_{t}P(t)t = \frac{\overline t}{\alpha}\)

Второе Неравенство Чебышева

Пусть \(x\) неотрицательная действительная случайная переменная, а \(\alpha\) – положительное действительное число. Тогда, \[P((x - \overline x)^2 \ge \alpha) \le \frac{\sigma_x^2}{\alpha}\]

Доказательство: Из первого неравенства Чебышева, пусть \(t=(x-\overline x)^2\): \(P((x-\overline x)^2\ge\alpha) \le \frac{\overline{(x - \overline x)^2}}{\alpha} =\frac{\sum_x P(x)(x-\overline x)^2}{\alpha} = \frac{\sigma_x^2}{\alpha}\)

Слабый закон больших чисел (закон Хинчина)

Пусть \(x\) есть среднее от \(N\) независимых случайных переменных \(h_i\) (\(i\in\{1,\ldots,N\}\)), имеющих одинаковые средние \(\overline h\) и одинаковые дисперсии \(\sigma_h^2\): \(x=\frac{1}{N}\sum_i h_i\). Тогда, \[P((x-\overline h)^2 \ge \alpha)\le \frac{\sigma_h^2}{\alpha N}\]

Доказательство: Применяя 2 неравенство Чебышева к \(x\), \[P((x-\overline x)^2 \ge \alpha) \le \frac{\sigma_x^2}{\alpha},\] но из линейности математического ожидания, \(\overline x = \frac{1}{N}\sum_i \overline h = \overline h,\) а \(\sigma_x^2 = \frac{1}{N^2}\sum_i \sigma_h^2 = \frac{\sigma_h^2}{N}\) в силу независимости \(h_i\).

Выражаясь неформально, слабый закон больших чисел говорит нам, что среднее \(N\) опытов вероятно произвольно близко к статистическому среднему, для достаточно больших \(N\).

Теорема о кодировании источника

Теорема Шеннона о кодировании источника определяет пределы возможного сжатия данных при передаче, и определяет энтропию Шеннона для источника как оперативную характеристику.

Пропускная способность канала

Пропускная способность \(C\) дискретного канала определяется как \[C = \lim_{T\to\infty}\frac{\log N(T)}{T},\] где \(N(T)\) – число допустимых сигналов продолжительности \(T\).

Теорема (оригинальная формулировка)

Пусть источник имеет энтропию \(H\) (бит на символ), а канал обладает пропускной способностью \(C\) (бит в секунду). Тогда возможно подобрать схему кодирования, такую, что средняя скорость передачи будет составлять \(\frac{C}{H}-\epsilon\) символов в секунду, где \(\epsilon\) произвольно мало. Невозможна передача со средней скоростью выше, чем \(\frac{C}{H}\).

Альтернативная формулировка

Пусть \(X\) – ансамбль с энтропией \(H(X)\). Тогда, для любого данного \(\epsilon>0\), \(\exists\, N_0 \in \mathbb N: \forall N > N_0,\) \[\left|\frac{1}{N}H(X^N)-H(X)\right|<\epsilon,\] где \(X^N\) – последовательность \(N\) значений из ансамбля \(X\).

Доказательство

Рассмотрим случайную переменную \(\frac{1}{N}\log_2\frac{1}{P(\mathbf x)}\), где \(\mathbf x \in X^N\).

Определим множество “типичных” значений из \(X^N\) как \[T_{N\beta} = \left\{\mathbf x \in X^N : \left|\frac{1}{N}\log_2\frac{1}{P(\mathbf x)} - H(X)\right| < \beta \right\},\] т.е. таких “слов” (последовательностей символов) длины \(N\) из \(X^N\), среднее информационное содержание которых отличается от \(H(X)\) не более, чем на \(\beta\).

Для \(\mathbf x \in T_{N\beta}\), \[2^{-N(H(X)+\beta)} < P(\mathbf x) < 2^{-N(H(X)-\beta)}.\]

По закону больших чисел, \[P(\mathbf x\notin T_{N\beta}) \le \frac{\sigma^2}{\beta^2 N}\]

Покажем, что \[\frac{1}{N}H(X^N) < H(X)+\epsilon\]

Сумма вероятностей элементов, входящих в \(T_{N\beta}\) не выше 1. Тогда \[|T_{N\beta}| 2^{-N(H(X)+\beta)} < 1,\] \[|T_{N\beta}| < 2^{N(H(X)+\beta)}.\]

Тогда для кодирования любого \(\mathbf x \in T_{N\beta}\) нам достаточно \[log_2|T_{N\beta}| < N(H(X)+\beta)\] бит.

Пусть теперь мы кодируем символы из \(T_{N\beta}\) последовательностями длины \(\log_2|T_{N\beta}|+1\) бит, и первый бит всех кодов для \(\mathbf x \in T_{N\beta}\) равен \(0\). Тогда мы можем закодировать все последовательности из \(U_{N\beta} = X^N - T_{N\beta}\) кодами, первый бит которых равен \(1\), а число бит в коде не больше \(\log_2|U_{N\beta}|+1\). Тогда средний информационный объём последовательности, кодирующей \(\mathbf x \in X^N\)

\[\begin{align}H(X^N) & < P(\mathbf x \in T_{N\beta})(1+log_2|T_{N\beta}|) + P(\mathbf x \notin T_{N\beta})(1+\log_2|U_{N\beta}|) \\ & < 1 + N(H(X)+\beta)+\frac{\sigma^2}{\beta^2 N}(1+\log_2|U_{N\beta}|) \\ & < 1 + N(H(X)+\beta)+\frac{\sigma^2}{\beta^2 N}(1+\log_2|X|^N) \\ & = N(H(X)+\beta+\frac{1}{N}+\frac{\sigma^2}{\beta^2 N}\log_2|X|+\frac{\sigma^2}{\beta^2 N^2}) \end{align}\]

Выбрав \(\beta = N^{-1/4}\) \[\frac{1}{N} H(X^N) < H(X)+\frac{1}{N^{1/4}}+\frac{1}{N}+\frac{\sigma^2}{N^{1/2} }\log_2|X|+\frac{\sigma^2}{N^{3/2}}\]

Для любого наперёд заданного сколь угодно малого \(\epsilon > 0\), можно выбрать такое \(N_0\), что для любых \(N>N_0\), \[\frac{1}{N^{1/4}}+\frac{1}{N}+\frac{\sigma^2}{N^{1/2} }\log_2|X|+\frac{\sigma^2}{N^{3/2}} < \epsilon,\] и \[\frac{1}{N} H(X^N) < H(x) + \epsilon.\]

Покажем теперь, что \[\frac{1}{N}H(X^N) > H(X)-\epsilon\]

Предположим, что это не так. Тогда, существует некоторое подмножество \(S \subset X^N\), такое, что \(|S| \le 2^{N(H(X)-\epsilon)}\) и при этом \(P(\mathbf x \notin S) \to 0\) при \(N\to\infty\).

\[P(\mathbf x \in S) = P(\mathbf x \in S \cap T_{N\beta}) + P(\mathbf x \in S \cap (X^N - T_{N\beta})).\]

Положим \(\beta = \epsilon/2\). Первый член достигает максимального значения, если \(S \cap T_{N\beta}\) содержит \(2^{N(H(X)-2\beta)}\) элементов, каждый с максимальной вероятностью \(2^{-N(H(X)-\beta)}\). Максимальное значение второго члена \(P(\mathbf x \notin T_{N\beta})\). Тогда \[P(\mathbf x \in S) \le 2^{N(H(X)-2\beta)} 2^{-N(H(X)-\beta)} + \frac{\sigma^2}{\beta^2 N}.\] \[P(\mathbf x \in S) \le 2^{-N\beta} + \frac{\sigma^2}{\beta^2 N}.\]

\[P(\mathbf x \notin S) \ge 1 - 2^{-N\beta} - \frac{\sigma^2}{\beta^2 N}.\]

Таким образом, для любых подмножеств размерности меньше, чем \(2^{N(H(X)-\epsilon)}\), при \(N\to\infty,\) \(P(\mathbf x \notin S) \to 1\).

Теорема Шеннона для канала с шумами

Пропускная способность канала с шумом

Пропускная способность \(C\) дискретного канала с шумом определяется как \[C = \max_{\mathcal{P}_M} I(M R),\] где \(M\) – случайная дискретная переменная источника, \(R\) – случайная дискретная переменная приёмника, \(I(M R) = H(M)-H(M|R)\) – взаимная информация, \(\mathcal{P}_M\) – множество вероятностей \(\{P(m): m \in M\}\) каждого значения источника.

Иными словами, пропускная способность \(C\) – это теоретически максимально возможное количество взаимной информации между приёмником и источником, т.е. количество информации, переданной через канал, для некого “оптимального” источника.

Теорема (оригинальная формулировка)

Пусть дискретный канал имеет пропускную способность \(C\) и дискретный источник с энтропией \(H=H(M)\). Если \(H\le C\), то существует схема кодирования, такая, что сигнал источника может быть передан через канал с произвольно малой частотой ошибок (произвольно малой \(H(M|R)\)). Если \(H > C\), то \(H(M|R) = H - C + \epsilon\), где \(\epsilon\) произвольно мало. Не существует метода кодирования, такого, чтобы \(H(M|R) < H-C\).

Некоторые определения

\((N, K)\) блочный код

Множество \(2^K\) кодовых слов длины \(N\), кодирующих некий источник с алфавитом мощности \(2^K\).

Плотность кодирования \((N, K)\) блочного кода

\(ρ = K/N\).

Декодер \((N, K)\)-блочного кода

Отображение множества всех последовательностей длины \(N\) сигналов на выходе из канала на множество \(2^K+1\) меток кодовых слов, где “лишняя” метка означает неудачу.

Вероятность ошибки блочного кода

\[p_B = \sum_{m\in M}P(m)P(r\neq m|m),\] где \(M\) множество сообщений на входе канала, \(R\) множество сигналов на выходе канала, \(r \in R\)

Максимальная вероятность ошибки блочного кода

\[p_{BM} = \max_{m\in M}{P(r\neq m|m)}\]

Оптимальный декодер

декодер, минимизирующий вероятность ошибки блочного кода.

Вероятность битовой ошибки

Пусть номер кодового слова \(s\) в \((N, K)\)-блочном коде представлен двоичным числом \(\vect{s}\) длиной \(K\) бит. Вероятность битовой ошибки \(p_b\) составляет среднюю вероятность того, что один бит в представлении \(\vect{s}\) изменился после передачи соответствующего кода через канал.

Доказательство

Используем альтернативную формулировку теоремы.

Теорема (альтернативная формулировка)

1. Для любого дискретного канала без памяти с пропускной способностью \(C\), \(\forall \epsilon > 0, \forall ρ < C\), \(\exists N > 0,\) такое, что для кода длины \(N\), плотности кодирования \(\ge ρ < C\) и данного алгоритма декодирования, максимальная вероятность ошибки блочного кода \(\le \epsilon.\)
2. Если вероятность битовой ошибки \(p_b\) приемлема, то достижима плотность кодирования до \[ρ(p_b) = \frac{C}{1-H_2(p_b)},\] где \(H_2(p_b) = - p_b \log_2 p_b - (1-p_b) \log_2 (1-p_b)\) – формула энтропии Шеннона для двоичного алфавита.
3. Плотность кодирования выше \(ρ(p_b)\) недостижима.

Совместно-типичные последовательности

Пара случайных последовательностей \(\vect{x}\), \(\vect{y}\), элементы которых принадлежат ансамблям, соответственно, \(X\) и \(Y\), называются совместно-типичными (с точностью \(\beta\)), если:

• \(\vect{x}\) типичный относительно \(P(\vect{x})\), т.е. \[\left|-\frac{1}{N}\log P(\vect{x}) - H(X)\right| < \beta\]
• \(\vect{y}\) типичный относительно \(P(\vect{y})\), т.е. \[\left|-\frac{1}{N}\log P(\vect{y}) - H(Y)\right|< \beta\]
• \(\vect{x}\), \(\vect{y}\) типичны относительно \(P(\vect{x},\vect{y})\), т.е. \[\left|-\frac{1}{N}\log P(\vect{x},\vect{y}) - H(XY)\right|< \beta\]

Достижимость кодирования с произвольно малой вероятностью ошибки

Рассмотрим следующую систему кодирования-декодирования с плотностью \(ρ'\):

1. Пусть \(K = N ρ'\), тогда случайным образом составим блочный код \((N, Nρ')\), в соответствии с \[P(\vect x) = \prod_{n=1}^N P(x_n),\] где \(\vect x\) – кодовые слова. Обозначим этот код \(\mathcal{C}\).
2. Код известен отправителю и получателю.
3. Сообщение \(s\) выбирается из множества \(\{1, 2, \ldots, 2^{Nρ'}\},\) после чего посылается код \(\vect x^{(s)}\). Получаемый (кодированный) сигнал \(\vect y\) имеет вероятность \[P(\vect y | \vect x^{(s)}) = \prod_{n=1}^N P(y_n|x_n^{(s)})\]
4. \(\vect y\) декодируется как \(\hat s\), если \((\vect x^{(\hat s)}, \vect y)\) взаимно типичные, и \(\nexists s': (\vect x^{(s')}, \vect y)\) взаимно типичные. В противном случае, сообщить об ошибке, \(\hat s = 0\).
5. Ошибка декодирования соответствует ситуации \(\hat s \neq s\).

Мы можем выделить следующие вероятности ошибки декодирования:

1. Средняя вероятность ошибки для конкретного кода \(\mathcal C\): \[p_B(\mathcal C) \equiv 2^{-N\rho'}\sum_s P(\hat s \neq s | s, \mathcal C).\]
2. Средняя вероятность ошибки по всем (случайно составленным) кодам: \[\langle p_B \rangle = \sum_\mathcal{C} p_B(\mathcal C) P(\mathcal C)\]
3. Максимальная условная вероятность ошибки: \[p_{BM}(\mathcal C) = \max_s P(\hat s \ne s|s,\mathcal C).\]

Обозначим множество взаимно-типичных \(\vect x, \vect y\) (с точностью \(\beta\)) как \(J_{N\beta}\).

Оценим среднюю вероятность ошибки. Существует два потенциальных источника ошибки:

1. \((\vect x^{(s)},\vect y) \notin J_{N\beta}\)
2. \(\exists s' \neq s, \vect x^{(s')} \in \mathcal C: (\vect x^{(s')},\vect y) \in J_{N\beta}\)

В силу симметрии построения кодов, \(\langle p_B\rangle\) не зависит от конкретного \(s\), поэтому без ограничения общности можем рассмотреть \(s=1\): \[\angle{p_B} = \sum_{\mathcal C} P(\mathcal C) P(\hat s \ne 1|s = 1,\mathcal C)\]

По закону больших чисел, \[P\left[\left(-\frac{1}{N}\log P(\vect{x}) - H(X)\right)^2 \ge \beta^2\right] \le \frac{\sigma_X^2}{\beta^2 N},\] \[P\left[\left(-\frac{1}{N}\log P(\vect{y}) - H(Y)\right)^2 \ge \beta^2\right] \le \frac{\sigma_Y^2}{\beta^2 N},\] \[P\left[\left(-\frac{1}{N}\log P(\vect{x}\vect{y}) - H(XY)\right)^2 \ge \beta^2\right] \le \frac{\sigma_{XY}^2}{\beta^2 N}.\]

Тогда вероятность, что \(\vect x, \vect y\) не взаимно типичны \[p_{NJT} \le \frac{\sigma_X^2+\sigma_Y^2+\sigma_{XY}^2}{\beta^2N} = \delta.\] Тогда вероятность ошибки из-за (a) не превшывает \(\delta\).

Сумма вероятностей \(P(\vect x \vect y)\) для \((\vect x, \vect y) \in J_{N\beta}\) не выше 1, а сами вероятности по построению удовлетворяют условию \[2^{-N(H(XY) + \beta)} < P(\vect{x}\vect{y}) < 2^{-N(H(XY) - \beta)}.\] Тогда \[|J_{N\beta}| 2^{-N(H(XY) + \beta)} \le 1,\] \[|J_{N\beta}| \le 2^{N(H(XY) + \beta)}.\]

Для двух независимых \(\vect x' \in X^N\) и \(\vect y' \in Y^N\), вероятность того, что они совместно типичны \[\begin{align} P((\vect x', \vect y') \in J_{N\beta}) & = \sum_{(\vect x, \vect y) \in J_{N\beta}} P(\vect x)P(\vect y) \\& \le |J_{N\beta}|2^{-N(H(X)-\beta)}2^{-N(H(Y)-\beta)} \\& \le 2^{N(H(XY) + \beta)}2^{-N(H(X)-\beta)}2^{-N(H(Y)-\beta)} \\& = 2^{N(H(XY)-H(X)-H(Y)+3\beta)} \\& = 2^{-N(I(XY)-3\beta)} \end{align}\]

Всего имеем \(2^{N\rho'}\) возможных значений \(x'\neq x^{(1)}\). Тогда вероятность ошибки из-за (b) не превышает \[2^{Nρ'}2^{-N(I(XY)-3\beta)} = 2^{-N(I(XY)-ρ'-3\beta)}.\]

Тогда средняя вероятность ошибки \[\langle p_B\rangle \le \delta + 2^{-N(I(XY)-ρ'-3\beta)},\] причём равенство достигается только если (a) и (b) никогда не происходят одновременно.

Тогда, если \(ρ' < I(XY)-3 \beta\), \((I(XY)-ρ'-3\beta) > 0\) и можно выбрать достаточно большой \(N\), такой, что \(\langle p_B \rangle < 2\delta\) (т.к. \(\delta \sim \frac{1}{N}\), а экспонента убывает быстрее гиперболы)

Пусть теперь источник – оптимальный источник для данного канала, тогда \(I(XY)=C\), и тогда \(ρ' < C-3 \beta\). Поскольку средняя вероятность ошибки по всем случайно составленным кодам \(<2\delta\), то существует хотя бы один код \(\mathcal C\), такой, что средняя вероятность ошибки по всем сигналам у этого кода \(p_B(\mathcal C) < 2\delta\).

Составим на основе этого кода новый код, в котором исключим половину кодовых слов, имеющих наиболее высокие вероятности ошибки. Вероятность ошибки у каждого из оставшихся кодовых слов менее \(4 \delta\). Таким образом, мы получили новый код с плотностью \(\rho'' = \rho'-\frac{1}{N}\) и получили максимальную вероятность ошибки \(p_{BM} < 4 \delta\). Положим \(ρ' = (ρ+C)/2\), \(\delta = \epsilon/4\), \(\beta < (C-ρ')/3\) и получим формулировку первой части теоремы.

Ошибка при передаче сверх пропускной способности

Из первой части теоремы, мы по сути знаем, что любой канал с шумом можно превратить в практически бесшумный с меньшей плотностью кодирования (т.е. в итоге меньшей пропускной способностью). Теперь, зададимся вопросом, с какой скоростью мы можем передавать данные через идеальный (бесшумный) канал, если допустима ошибка передачи?

Рассмотрим канал без шума с пропускной способностью \(C\). Теперь представим, что мы передаём (ну или по крайней мере пытаемся передать) количество информации \(H>C\). Простая стратегия заключается в том, чтобы передавать только количество информации, равное \(C\), и отбрасывать остальное. Приёмник тогда должен угадать \(H-C\) бит сообщения. Потери информации в канале очевидно \(H(M|R) = H-C\) (при \(N\to\infty\)). Доля сообщения, которое приёмник должен угадать \(\frac{H-C}{H} = 1-\frac{C}{H}\), тогда вероятность битовой ошибки \[p_b = \frac{1}{2}(1-\frac{C}{H}).\]

Можно получить несколько лучший результат (в смысле уменьшения \(p_b\)), если распределить вероятность битовой ошибки равномерно по всем битам.

Неравенство Фано

Пусть \(X\), \(Y\) – случайные переменные, а \(p_e\) – вероятность ошибки “угадывания” \(X\) по \(Y\) (при известных вероятностях \(P(X|Y)\)). Тогда, \[H_2(p_e)+p_e\log(N-1) \ge H(X|Y),\] где \(N\) – размерность алфавита \(X\).

\(Δ:\)

Пусть \(E\) – двоичная случайная переменная, возвращающая 1, если возникла ошибка “угадывания”, 0 в противном случае. Заметим, что \(P(E=1) = p_e\), и \(H(E) = H_2(p_e).\)

По правилу цепочки, \[\begin{align} H(EXY) & = H(E|XY) + H(XY) \\& = H(E|XY) + H(X|Y) + H(Y) \end{align}\] с другой стороны, \[\begin{align} H(EXY) & = H(X|EY)+H(EY) \\& = H(X|EY) + H(E|Y) + H(Y) \end{align}\]

Тогда, \[H(E|XY) + H(X|Y) = H(X|EY) + H(E|Y)\]

\(H(E|XY) = 0\), поскольку \(E\) однозначно определена, если определены \(X\) и \(Y\). \(H(E|Y) \le H(E)\), поскольку условие не увеличивает энтропию. Наконец, \[\begin{align}H(X|EY) & = P(E=0)H(X|Y, E=0) \\& + P(E=1)H(X|Y,E=1) \\& \le p_e \log(N-1),\end{align}\] где неравенство следует из \(H(X|Y, E=0) = 0\) и \(H(X|Y,E=1) \le \log(N-1)\). \(N-1\), поскольку при \(E=1\), \(X\) точно не “правильный”, т.е. одно значение исключается.

Собирая вместе, получаем: \[\begin{align} H(X|Y) & = H(X|EY) + H(E|Y) \\& \le p_e \log(N-1) + H(E) \end{align}\]

Для двоичного алфавита, \(N=2\) и \[H(X|Y) \le H(E) = H_2(p_e)\]

Неравенство Йенсена (дискретный случай)

Пусть \(f(x)\) выпуклая вниз на некотором отрезке \(\mathcal X\), и пусть числа \(q_i\) (\(i=1,\ldots, n\)) представляют веса (\(q_i > 0\), \(\sum_i q_i = 1\)). Тогда \(\forall x_i \in \mathcal X\) \[f(\sum_i q_i x_i) \le \sum_i q_i f(x_i).\]

Для выпуклой вверх функции неравенство обращается.

\(Δ\): Для \(n=2\) прямо следует из определения выпуклой функции. Далее индукция по n.

Пусть \(R^N\) – кодовое слово на выходе из канала, использующее \((N, K)\)-блочный код, имеющий вероятность битовой ошибки \(p_b\), \(S\) – отправленное сообщение, \(M^N\) – кодовое слово на входе в канал.

\[\begin{align} H(M^N R^N S) & = H(M^{N-1} R^{N-1} S) \\& + H(M_N|M^{N-1} R^{N-1} S) & (= 0) \\& + H(R_N|M^{N-1} R^{N-1} S) & (= H(R^N|M^N)) \\& = H(M^{N-1} R^{N-1} S) + H(R_N|M_N) \\& = \ldots \\& = H(S) + \sum_{i=1}^N H(R_i|M_i) \end{align}\]

Первое равенство следует из того, что один символ кодового на входе в канал точно известен, если известны остальные символы кодового слова и исходное сообщение.

С другой стороны, \[\begin{align} H(M^N R^N S) & = H(R^N S) \\& + H(M_N|R^N S) & (= 0) \\& = H(R^N S) \end{align}\]

Тогда взаимная информация между исходным сообщением и кодовым словом на выходе из канала:

\[\begin{align} I(S R^N) & = H(S)+H(R^N)-H(R^N S) \\& = H(R^N)-\sum_{i=1}^N H(R_i|M_i) \\& \le \sum_{i=1}^N (H(R_i) - H(R_i|M_i)) \\& = \sum_{i=1}^N I(R_i M_i) \\& \le C N = C \frac{K}{ρ} \end{align}\]

Тогда: \[\begin{align} H_2(p_b) & = H_2(\frac{\sum_{i=1}^K P(\text{ошибка в }i\text{-том бите})}{K}) \\& \ge \frac{\sum_{i=1}^K H_2(P(\text{ошибка в }i\text{-том бите}))}{K} & \text{н-во Й.} \\& \ge \frac{\sum_{i=1}^K H(i\text{-й бит сообщения}|R^N)}{K} & \text{н-во Ф.} \\& \ge \frac{H(S|R^N)}{K} & \text{св-во }H \\& = \frac{H(S) - I(S R^N)}{K} & \text{опр. }I \\& \ge \frac{K - K\frac{C}{ρ}}{K} & \text{при } P(s_i)=P(s_j) \\& = 1 - \frac{C}{ρ} \end{align}\]

\[\begin{align} ρ \le \frac{C}{1 - H_2(p_b)} \end{align}\]

Теорема Шеннона-Хартли

Определяет пропускную способность канала с аддитивным гауссовским шумом.

\[C = B \log_2(1+\frac{S}{N}),\]

где C – пропускная способность канала, бит/с, \(B\) – полоса пропускания (частотная ширина канала), Гц, \(S\) – средняя мощность сигнала над полосой пропускания, Вт, \(N\) – средняя мощность шума над полосой пропускания, Вт.

Аксиоматическое определение энтропии

Не всегда энтропия вводится как у Шеннона. Её так же можно непосредственно ввести аксиоматически. Понятно, что любые полезные системы аксиом будут эквивалентны друг другу. Рассмотрим две системы аксиом.

Аксиомы Хинчина

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

1. \(H(p_1,\ldots,p_n)\) – непрерывная относительно аргументов функция в области определения \(0\le p_i \le 1\), \(\sum_i p_i = 1\)
2. \(H(p_1, \ldots, p_n)\) не меняется от перестановок аргументов.
3. \(H(p_1, \ldots, p_n, 0) = H(p_1,\ldots,p_n)\)
4. \(H(XY)=H(X)+H(Y|X)\), где \(H(Y|X) = \sum_{x\in X} P(x) H(\frac{P(x_i y_1)}{P(x_i)},\ldots,\frac{P(x_i y_m)}{P(x_i)}).\)
5. \(H(p_1, \ldots, p_n)\leq H(\frac{1}{n},\ldots,\frac{1}{n})\)

Этот набор аксиом однозначно приводит к энтропии Шеннона. Аксиома 4 кажется несколько неестественной: действительно, в аксиомах, определяющих энтропию, появляется условная энтропия. Более естественно могла бы выглядеть аксиома такого вида:

4. Энтропия двух независимых систем аддитивна, \(H(XY) = H(X)+H(Y)\).

Однако оказывается, что такая модифицированная 4-ая аксиома приводит к более общей функции энтропии, чем энтропия Шеннона, известной как энтропия Реньи или α-энтропия: \[H_\alpha(X)={\frac{1}{1-\alpha}}\log \sum _{x\in X} (P_{i}(x))^{\alpha},\] которая эквивалентна энтропии Шеннона только в пределе \(\alpha\to 1\): \[\begin{align} \lim_{\alpha\to 1} \frac{\log \sum_{x\in X} (P_{i}(x))^{\alpha}}{1-\alpha} & = - \lim_{\alpha\to 1} \frac{\sum_{x\in X}(P_{i}(x))^{\alpha} \log (P_{i}(x))}{\sum_{x\in X}(P_{i}(x))^{\alpha}} \\ & = - \sum_{x\in X} P_{i}(x) \log (P_{i}(x)) \end{align}\]

Аксиомы Фаддеева

Эквивалентная системе Хинчина аксиоматика.

1. \(H(p, 1-p)\) непрерывна при \(p\in[0,1]\) и положительна хотя бы в одной точке.
2. \(H(p_1, \ldots, p_n)\) не меняется от перестановок аргументов
3. При \(n\ge 2\), \(H(p_1,\ldots, p_{n-1}; q_1, q_2) = H(p_1, \ldots, p_n) + p_n H\left(\frac{q_1}{p_n}, \frac{q_2}{p_n}\right)\), где \(p_n=q_1+q_2\).

Отличия от аксиом Хинчина в том, что аксиома 5 заменяется на требование положительности \(H\) хотя бы в одной точке, а аксиомы Хинчина 3, 4 заменяются одной аксиомой Фаддеева 3.

Аксиома Фаддеева 3 оказывается более естественной, если интерпретировать энтропию как меру неопределённости. Тогда неопределённость, возникающая от деления события с вероятностью \(p_n\) на два события с условными вероятностями \(\frac{q_1}{p_n}\), \(\frac{q_2}{p_n}\), должна возникать только если собственно происходит событие с вероятностью \(p_n\) – чему, собственно, и соответствует член \(p_n H\left(\frac{q_1}{p_n}, \frac{q_2}{p_n}\right)\).