Некоторые определения
- Двоичный канал
Канал связи, имеющий двоичные алфавиты сообщений и сигналов
- Двоичный симметричный канал (ДСК, X-канал)
Канал связи, имеющий двоичные алфавиты сообщений и сигналов, и симметричные вероятности неверной передачи данных \(p\) (обычно полагается \(p\ll 1\))
- Двоичный асимметричный канал (Z-канал)
Двоичный канал связи, имеющий вероятность \(P(R=1|M=0) = 0\)
- Двоичный стирающий канал (двоичный канал со стиранием, Σ-канал)
Двоичный канал связи, имеющий вероятность \(p\) получения третьего сигнала на выходе для каждого из сообщений.
- Двоичный источник
- Источник сигналов, имеющий двоичный алфавит
- Двоичный источник без памяти (ДИБП)
- Двоичный источник, отдельные сообщения которого независимы, т.е. \(P(m_1 m_2 \ldots m_n) = \prod_{i=1}^n P(m_i).\)
Пример 1
Рассмотрим двоичный канал связи вида
Пусть априорные вероятности \(P(m_i)\) равны \(P(a) = 0.6\), \(P(b) = 0.4\).
Каков оптимальный приёмник?
Какова вероятность ошибки передачи?
Оптимальный приёмник имеет функцию отображения \(\hat m(r_j) = m_j\) для сигналов, имеющих наибольшую апостериорную вероятность \(P(m_i|r_j)\).
Нам дана канальная матрица \(P(r_i|m_j)\). Вычислим апостериорные вероятности исходя из канальной матрицы по теореме Байеса:
\(P(m_i|r_j) = \frac{P(r_j|m_i) P(m_i)}{P(r_j)},\) где по определению условной вероятности, если \(m_i\) независимы (они независимы по данным априорным вероятностям) \(P(r_j) = \sum_i P(r_j|m_i) P(m_i).\)
Тогда
\(P(0) = P(0 | a) P(a) + P(0 | b) P(b),\) \(P(1) = P(1 | a) P(a) + P(1 | b) P(b),\) \(P(0) = 0.2\cdot 0.6 + 0.7 \cdot 0.4 = 0.4,\) \(P(1) = 0.8\cdot 0.6 + 0.3 \cdot 0.4 = 0.6.\)
\(P(a|0) = \frac{P(0|a) P(a)}{P(0)},\) \(P(a|1) = \frac{P(1|a) P(a)}{P(1)},\) \(P(b|0) = \frac{P(0|b) P(b)}{P(0)},\) \(P(b|1) = \frac{P(1|b) P(b)}{P(1)}.\)
\(P(a|0) = \frac{0.2\cdot 0.6}{0.4} = 0.3,\) \(P(b|0) = \frac{0.7\cdot 0.4}{0.4} = 0.7,\) \(P(a|1) = \frac{0.8\cdot 0.6}{0.6} = 0.8,\) \(P(b|1) = \frac{0.3\cdot 0.4}{0.6} = 0.2.\)
Проверка: \(\sum_i P(m_i | r_j) = 1,\) \(\sum_i P(m_i | 0) = 0.3+0.7=1,\) \(\sum_i P(m_i | 1) = 0.8+0.2=1.\)
Тогда оптимальный приёмник будет иметь функцию \(\hat m\) вида \(\hat m(0) = b,\) \(\hat m(1) = a.\)
Вообще говоря, для получения того же результата достаточно было бы рассчитать совместные вероятности \(P(m_i r_j)\) и выбрать для \(\hat m(r_j)\) результаты с наибольшими совместными вероятностями \(\underset{m_j}\max\, P(m_i r_j)\) (этот достаточно очевидный факт строго обосновывается в лекции 3):
\(P(a, 0) = P(0|a) P(a) = 0.2\cdot 0.6 = 0.12,\) \(P(a, 1) = P(1|a) P(a) = 0.8\cdot 0.6 = 0.48,\) \(P(b, 0) = P(0|b) P(b) = 0.7\cdot 0.4 = 0.28,\) \(P(b, 1) = P(1|b) P(b) = 0.3\cdot 0.4 = 0.12.\)
(проверка: \(\sum_{ij} P(m_i r_j) = 1\))
Тогда, вероятность ошибки есть суммарная вероятность того, что функция приёмника \(\hat m\) делает неправильный выбор, то есть:
\(P(err) = P(a,0)+P(b,1) = 0.24\)
Упражнение 1.1
Рассмотрим двоичный канал связи вида
Пусть априорные вероятности \(P(m_i)\) равны \(P(a) = 0.5\), \(P(b) = 0.5\).
Каков оптимальный приёмник?
Какова вероятность ошибки передачи?
Упражнение 1.2
Рассмотрим двоичный симметричный канал связи вида
Пусть априорные вероятности \(P(m_i)\) равны \(P(a) = 0.8\), \(P(b) = 0.2\).
Каков оптимальный приёмник?
Какова вероятность ошибки передачи?
Упражнение 1.3
Рассмотрим двоичный Z-канал связи вида
Пусть априорные вероятности \(P(m_i)\) равны \(P(a) = 0.8\), \(P(b) = 0.2\).
Каков оптимальный приёмник?
Какова вероятность ошибки передачи?
Упражнение 1.4
Рассмотрим канал связи, имеющий алфавит сообщений \(\{a, b, c\}\), и алфавит сигналов \(\{1,2,3\}\). Априорные вероятности приведены в табл.:
| m | P(m) |
|---|---|
| a | 0.3 |
| b | 0.5 |
| c | 0.2 |
Канальная матрица \(P(r_j|m_i)\) имеет вид:
| 1 | 2 | 3 | |
|---|---|---|---|
| a | 0.6 | 0.3 | 0.1 |
| b | 0.1 | 0.5 | 0.4 |
| c | 0.1 | 0.1 | 0.8 |
Каков оптимальный приёмник?
Какова вероятность ошибки передачи?
Упражнение 1.5
Рассмотрим двоичный канал связи, имеющий алфавит сообщений \(\{0, 1\}\), и алфавит сигналов \(\{a,b,c\}\). Априорные вероятности приведены в табл.:
| m | P(m) |
|---|---|
| 0 | 0.7 |
| 1 | 0.3 |
Канальная матрица \(P(r_j|m_i)\) имеет вид:
| a | b | c | |
|---|---|---|---|
| 0 | 0.7 | 0.2 | 0.1 |
| 1 | 0.3 | 0.2 | 0.5 |
Каков оптимальный приёмник?
Какова вероятность ошибки передачи?
Пусть априорные вероятности неизвестны. Как ошибка передачи зависит от априорных вероятностей?
Указание: возможны восемь вариантов функции приёмника \(\hat m\). Для каждой из них можно найти функцию зависимости вероятности ошибки от априорной вероятности \(P(0)\). Например, рассмотрим ф-ю приёмника \(\hat m(a) = 0,\) \(\hat m(b) = 0,\) \(\hat m(c) = 1.\)
Вероятность ошибки тогда \(P(err) = 1 - (P(a, 0) + P(b, 0) + P(c,1))\). \(P(a, 0) = P(a|0)P(0),\) \(P(b, 0) = P(b|0)P(0),\) \(P(c, 1) = P(c|1)(1-P(0)).\) Тогда зависимость функции вероятности ошибки от \(P(0)\) имеет вид: \(f(x) = 1 - (0.7 x + 0.2 x + 0.5(1-x))\) \(= 0.5 - 0.4 x\).
Упражнение 1.6
Какова вероятность ошибки передачи в общем виде для
- Двоичного симметричного канала?
- Z-канала?
- Σ-канала?
Пример 2
Пусть имеется ДИБП с алфавитом \(\{0, 1\}\), \(P(0) = p\).
Какова энтропия этого источника?
Поскольку \(P(0)+P(1) = 1\), то \(P(1) = 1 - p\). Далее, по формуле Шеннона, \(H(p) = - p \log_2(p) - (1-p) \log_2(1-p).\)
Функция \(H(p)\) называется двоичной энтропией и часто обозначается \(H_2(p)\)
Упражнение 2.1
При каком значении аргумента достигается максимум двоичной энтропии?
Указание: экстремум достигается при равенстве производной нулю.
Упражнение 2.2
Для двоичного источника с алфавитом \(U = \{0, 1\}\), рассмотреть все двухсимвольные последовательности этого источника как новый источник с алфавитом \(U_2 = \{00, 01, 10, 11\}\).
Какова энтропия этого нового источника?
Как она связана с энтропией исходного источника?
Решение
Пусть вероятность \(P(0) = p\). Тогда, \(P(00) = p^2,\) \(P(01) = p(1-p),\) \(P(10) = (1-p)p,\) \(P(11) = (1-p)^2.\)
Энтропия по формуле Шеннона \(H(U_2) = - P(00) \log_2 P(00) - \ldots - P(11) \log_2 P(11).\)
\(\begin{align} H(U_2) & = - p^2 \log_2 p^2 - 2 p(1-p)\log_2(p(1-p)) - (1-p)^2 \log_2 (1-p)^2 \\& = - 2(p^2 + p(1-p))\log_2 p - 2 (p(1-p) + (1-p)^2) \log_2(1-p) \\& = - 2p\log_2 p - 2 (1 - p) \log_2(1-p) \\& = 2 H_2(p).\end{align}\)
Пример 3
Определить количество информации, содержащееся в случайном изображении размером 800х600 двухцветных (белый и чёрный) независимых пикселей. Цвета каждого пикселя равновероятны.
Поскольку цвета каждого пикселя равновероятны, а пиксели независимы, количество собственной информации каждого пикселя равно \(I_{px} = -\log_2 \frac{1}{2} = 1.\)
Поскольку для независимых событий информация аддитивна, то всего имеем \(I_\Sigma = 800\cdot 600 \cdot I_{px}\) = 480000 бит = 480 килобит = 60 килобайт информации.
Упражнение 3.1
Определить количество информации, содержащееся в случайном изображении размером 800х600 независимых пикселей, допускающих каждый 16 оттенков серого. Цвета каждого пикселя равновероятны.
Упражнение 3.2
Экран радара делится на 10x10 = 100 квадрантов. Изображение появляется в виде точки на экране. Полагая, что все положения равновероятны, определить количество информации в сообщениях:
- Объект находится в 46-м квадранте
- Объект находится в 5-й строке
Пример 4
Пусть имеется ДКБП, имеющий входной алфавит \(\{a, b\}\) и выходной алфавит \(\{0, 1\}\). Известны совместные вероятности \(P(m_i r_j)\)
| 0 | 1 | |
|---|---|---|
| a | 0.1 | 0.3 |
| b | 0.4 | 0.2 |
Определите количество взаимной информации для всех пар сообщений и сигналов
Взаимная информация двух событий \(I(x; y) = \log \frac{P(xy)}{P(x)P(y)},\) \(I(x; y) = \log P(xy) - (\log P(x) + \log P(y))),\) \(I(x; y) = I((x,y)) - I(x) - I(y),\) где \(I((x,y))\) – информация, получаемая при одновременных событиях \(x\), \(y\).
Информация совместных событий: \(I((a,0))=-\log_2 0.1 \approx 3.32,\) \(I((a,1))=-\log_2 0.3 \approx 1.74,\) \(I((b,0))=-\log_2 0.4 \approx 1.32,\) \(I((b,1))=-\log_2 0.2 \approx 2.32.\)
Информация сообщений и сигналов: \(I(a) = -\log_2(P(a,0)+P(a,1)) = -\log_2 0.4 \approx 1.32,\) \(I(b) = -\log_2 0.6 \approx 0.74,\) \(I(0) = I(1) = -\log_2 0.5 = 1.\)
Взаимная информация: \(I(a; 0)\approx 3.32 - 1.32 - 0.5 = 1.5,\) \(I(a; 1)\approx 1.74 - 1.32 - 0.5 = -0.08,\) \(I(b; 0)\approx 1.32 - 0.74 - 0.5 = 0.08,\) \(I(b; 1)\approx 2.32 - 0.74 - 0.5 = 1.08.\)
Упражнение 4.1
Пусть имеется ДКБП, имеющий входной алфавит \(\{a, b\}\) и выходной алфавит \(\{0, 1, 2\}\). Известны совместные вероятности \(P(m_i r_j)\)
| 0 | 1 | 2 | |
|---|---|---|---|
| a | 1/4 | 1/16 | 1/8 |
| b | 1/8 | 3/16 | 1/4 |
Определите количество взаимной информации для всех пар сообщений и сигналов
Пример 5
\(P(xy)=\)
| y₁ | y₂ | y₃ | |
|---|---|---|---|
| x₁ | 0.4 | 0.1 | |
| x₂ | 0.2 | 0.1 | |
| x₃ | 0.2 |
Определите \(H(X)\), \(H(Y)\), \(H(Y|X)\), \(H(X|Y)\), \(H(XY)\), \(I(X;Y)\)
Найдём собственные вероятности для \(x_i\), \(y_i\):
| y₁ | y₂ | y₃ | P(x) | |
|---|---|---|---|---|
| x₁ | 0.4 | 0.1 | 0.5 | |
| x₂ | 0.2 | 0.1 | 0.3 | |
| x₃ | 0.2 | 0.2 | ||
| P(y) | 0.4 | 0.3 | 0.3 |
Тогда:
\(H(X) = - 0.5\log_2 0.5 - 0.3 \log_2 0.3 - 0.2\log_2 0.2,\) \(H(Y) = - 0.4\log_2 0.4 - 0.3 \log_2 0.3 - 0.3\log_2 0.3.\)
\(\begin{align} H(XY) = & -0.4\log_2 0.4 - 0.1\log_2 0.1 \\& - 0.2\log_2 0.2 - 0.1 \log_2 0.1 \\& - 0.2\log_2 0.2 \end{align}\)
\(H(X) \approx 1.48,\) \(H(Y) \approx 1.57,\) \(H(XY) \approx 2.12.\)
\(H(X|Y) = H(XY) - H(Y) \approx 2.12-1.57 = 0.55,\) \(H(Y|X) = H(XY) - H(X) \approx 2.12-1.48 = 0.64.\)
Проверка (правило Байеса): \(H(X|Y) = H(Y|X) + H(X) - H(Y),\) \(H(X|Y) \approx 0.64 + 1.48 - 1.57 = 0.55.\)
\(I(X;Y) = H(X)+H(Y)-H(XY) = 1.48+1.57 - 2.12 = 0.93.\)
Отметим, что в идеальном канале \(I(X;Y) = H(X) \approx 1.48.\)
Упражнение 5.1
| y₁ | y₂ | y₃ | |
|---|---|---|---|
| x₁ | 0.3 | 0.1 | |
| x₂ | 0.25 | ||
| x₃ | 0.25 | 0.1 |
Определите \(H(X)\), \(H(Y)\), \(H(Y|X)\), \(H(X|Y)\), \(H(XY)\), \(I(X;Y)\)
Упражнение 5.2
| y₁ | y₂ | y₃ | |
|---|---|---|---|
| x₁ | 0.2 | ||
| x₂ | 0.4 | 0.25 | 0.15 |
Определите \(H(X)\), \(H(Y)\), \(H(Y|X)\), \(H(X|Y)\), \(H(XY)\), \(I(X;Y)\)
Пример 6
Пусть имеется ДCК с вероятностью перекрёстного сигнала \(p\).
Какова пропускная способность канала?
Каков оптимальный источник?
Пропускная способность канала определяется как \(C = \underset{\mathcal P(m)}\max\, I(M;R),\) где \(\mathcal P(m)\) – множество всех возможных распределений вероятностей источника.
Здесь \(I(M;R)\) – взаимная информация ансамблей \(I(M;R) = H(M) + H(R) - H(MR)\).
Ввиду того, что источник двоичный, \(P(b) = 1-P(a)\). Пусть \(P(a)=x\).
Тогда, \(P(m_1 r_1) = P(r_1|m_1)P(m_1) = (1-p) x,\) \(P(m_1 r_2) = P(r_2|m_1)P(m_1) = p x,\) \(P(m_2 r_1) = P(r_1|m_2)P(m_2) = p (1-x),\) \(P(m_2 r_2) = P(r_2|m_2)P(m_2) = (1-p) (1-x).\)
\(P(r_1) = P(m_1 r_1)+P(m_2 r_1) = (1-p) x + p (1-x),\) \(P(r_2) = P(m_1 r_2)+P(m_2 r_2) = p x + (1-p) (1-x).\)
\(I(M R) = -\sum_{m\in M, r\in R} P(mr) \log_2 \frac{P(r|m)}{P(r)},\)
\(\begin{align} -I(MR) & = (1-p) x \log_2\frac{1-p}{(1-p) x + p (1-x)} \\& + p x \log_2\frac{p}{p x + (1-p) (1-x)} \\& + p (1-x) \log_2\frac{p}{(1-p) x + p (1-x)} \\& + (1-p)(1-x) \log_2\frac{1-p}{p x + (1-p) (1-x)} \end{align}\)
Производная \(I(x)' = (1-2p)\log_2\frac{(1-p) x + p (1-x)}{p x + (1-p) (1-x)},\) \({p x + (1-p) (1-x)} = {(1-p) x + p (1-x)}.\)
Относительно p: \(\frac{p}{1-p} (2x - 1) = 2x - 1,\) \(\frac{p}{1-p} = 1,\) \(p = \frac{1}{2}.\)
Относительно x: \((2p - 1) \frac{x}{1-x} = 2p - 1,\) \(\frac{x}{1-x} = 1,\) \(x = \frac{1}{2}.\)
Таким образом, оптимальный источник – такой, сообщения которого равновероятны.
Пропускная способность \(C = \left.I(MR)\right|_{x=0.5}\) \(= 1 + (1-p)\log_2{(1-p)} + p \log_2{p}\) \(= 1 - H_2(p).\)
Упражнение 6.1
Для Z-канала,
Какова пропускная способность канала?
Каков оптимальный источник?
Упражнение 6.2
Для Σ-канала,
Какова пропускная способность канала?
Каков оптимальный источник?