ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
x y 44 Глава 2. Каналы связи Теорема 5. Пропускная способность двоичного симметричного канала связи равна C = F [1 + (1 − β) · lb(1 − β) + β · lbβ], где β – вероятность ошибочного приема, F = 1/τ - частота посылки импульсов, τ - длительность одного сигнала. Доказательство. Рассмотрим схему двоичного симметричного канала связи. Обозначим через x – случайную величину значений на входе, а y – случайную величину значений на выходе канала информации. x 0 1 0 1 y β β β β α α Допустим, что вероятность появления на входе канала значения 0 или 1 равны соответственно: p(x = 0) = p; p(x = 1) = 1 − p = p. Вследствие помех передаваемый сигнал проходит канал без искажения с вероятностью β и принимает противоположное значение с вероятностью β. Такое действие описывается канальной матрицей: p( y|x) = β β β β Вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов столбца даёт вероятность появления соответствующего символа на стороне приёмника p( y). Матрица совместного распределения вероятностей принимает вид p(x, y) = p · β p · β p · β p · β Складывая вероятности по строкам и столбцам, получим редуцированные (маргинальные) законы распределения p( x) и p(y): x y 0 1 p(x) 0 p · β p · β p 1 p · β p · β p p(y) p · β + p · β p · β + p · β P = 1 Средняя взаимная информация Средняя взаимная информация определяет скорость передачи информации и вычисляется по формуле I(x, y) = H(x) + H(y) − H(x, y), 2.1. Пропускная способность каналов связи 45 Здесь H(x) = − X x p(x) · lb p(x) = −p · lbp − p · lbp, H(y) = − X y p(y) · lb p(y) = −(p · β + p · β) · lb(p · β + p · β) −(p · β + p · β) · lb(p · β + p · β), H(x, y) = − X x X y p(x, y) · lb p(x, y) = −pβ · lbpβ − pβ · lbpβ − pβ · lbpβ − pβ · lbpβ . Тогда I(x; y) = H(x) + H(y) − H(x, y) = −p · lbα − p · lbp − (p · β + p · β) · lb(p · β + p · β) − (p · β + p · β) · lb(p · β + p · β) + pβ · lbpβ + pβ · lbpβ + pβ · lbpβ + pβ · lbpβ. Пропускная способность Пропускная способность канала связи C – максимальная скорость передачи информации, которая может быть достигнута выбором оптимального распределения вероятности p(x) символов сообщения: C = Max p(x) F · I(x; y). Исследуем функцию I(x|y) на экстремум d dp I(x; y) = −1 · lbp − 1 + 1 · lbp + 1 − (β − β) · lb(p · β + p · β) − (β − β) − (β − β) · lb(p · β + p · β) − (β − β) + β · lbpβ + β + β · lbpβ + β − β · lbpβ − β − β · lbpβ − β = lb p p + (β − β) · lb (p · β + p · β) (p · β + p · β) + lb p p = (β − β) · lb (p · β + p · β) (p · β + p · β) = 0. Отсюда следует, что (p · β + p · β) (p · β + p · β) = 1, или β − pβ + p − pβ pβ + 1 − p − β + pβ = 1 откуда 2β − 4pβ + 2p = 1 т.е. p ∗ = 1 2 46 Глава 2. Каналы связи Подставляя полученное значение p ∗ в выражение для I(x|y) получим I(x; y) = H(x) + H(y) − H(x, y) = − 1 2 · lb 1 2 − 1 2 · lb 1 2 − β 2 + β 2 · lb β 2 + β 2 − β 2 + β 2 · lb β 2 + β 2 + β 2 · lb β 2 + β 2 · lb β 2 + β 2 · lb β 2 + β 2 · lb β 2 = 1 + 1 + β · lb β 2 + β · lb β 2 = 2 + β · lbβ + β · lbβ − 1 = 1 + β · lbβ + β · lbβ. При отсутствии помех (β = 0) C = C m = F. Потери информации Потери информации со стороны источника H(y/x) = H(x, y) − H(x), Потери информации со стороны приемника H(x/y) = H(x, y) − H(y), Пример 2.1. По двоичному симметричному каналу связи с помехами передаются сигналы (x 1 , x 2 ) с априорными вероятностями p(x 1 ) = 3/4; p(x 2 ) = 1/4. Из-за наличия помех вероятность правильного приема каждого из сигналов (x 1 , x 2 ) уменьшается до α = 7/8. Найти: 1. скорость передачи информации I(x; y); 2. пропускную способность канала C = Max p(x) I(x; y). Решение. По условию p(x 1 ) = 3/4, p(x 2 ) = 1/4, α = 7/8, α = 1/8. Предварительно, вычислим вероятности p(y j ), p(x j , y j ), и p(x j /y j ). По формуле полной вероятности получим: p(x 1 , y 1 ) = p(x 1 )α = 3 4 · 7 8 = 21 32 ; p(x 1 , y 2 ) = p(x 1 )α = 3 4 · 1 8 = 3 32 ; 2.1. Пропускная способность каналов связи 47 p(x 2 , y 1 ) = p(x 2 )α = 1 4 · 1 8 = 1 32 ; p(x 2 , y 2 ) = p(x 2 )α = 1 4 · 7 8 = 7 32 Составим таблицу совместного распределения для передаваемых и получаемых сигналов x \ y 0 1 p(x) 0 21 32 3 32 24 32 = 3 4 1 1 32 7 32 8 32 = 1 4 p(y) 22 32 10 32 P p = 1 1. По формулам для среднего количества информации H(x) = − X i p(x i ) lbp(x i ) = − 3 4 lb 3 4 − 1 4 lb 1 4 = 0.811 bit H(y) = − X i p(y i ) lbp(y i ) = − 22 32 lb 22 32 − 10 32 lb 10 32 = 0.896 bit H(x, y) = − X X p(x, y) lbp(x, y) − 21 32 lb 21 32 − 3 32 lb 3 32 − 1 32 lb 1 32 − 7 32 lb 7 32 = 1.355 bit I(x, y) = H(x) + H(y) − H(x, y) = − X p(x) lbp(x) − X p(y) lbp(y) + X X p(x, y) lbp(x, y) = − 3 4 lb 3 4 − 1 4 lb 1 4 − 22 32 lb 22 32 − 10 32 lb 10 32 + 21 32 lb 21 32 + 3 32 lb 3 32 + 1 32 lb 1 32 + 7 32 lb 7 32 = 0.352 bit Для нахождения пропускной способности двоичного симметричного канала, нам необходимо найти такие значения p и q при которых скорость передачи по каналу (при заданных помехах) будет максимальна. Имеем x 0 1 0 1 y p q 7/8 7/8 1/8 1/8 Составим таблицу совместного распределения для передаваемых и получаемых сигналов x \ y 0 1 p(x) 0 p 7 8 p 1 8 p 1 q 1 8 q 7 8 q p(y) p 7 8 + q 1 8 p 1 8 + q 7 8 P p = 1 48 Глава 2. Каналы связи По формулам для среднего количества информации H(x) = − X i p(x i ) lbp(x i ) H(y) = − X i p(y i ) lbp(y i ) H(x, y) = − X X p(x, y) lbp(x, y) I(x, y) = H(x) + H(y) − H(x, y) = − X p(x) lbp(x) − X p(y) lbp(y) + X X p(x, y) lbp(x, y) = −p lb (p) − q lb (q) − p 7 8 + q 1 8 lb p 7 8 + q 1 8 − p 1 8 + q 7 8 lb p 1 8 + q 7 8 + p 7 8 lb p 7 8 + p 1 8 lb p 1 8 + q 1 8 lb q 1 8 + q 7 8 lb q 7 8 Теперь, учитывая что q = 1 − p, получим I(p) = −p lb (p) − q lb (q) − p 7 8 + (1 − p) 1 8 lb p 7 8 + (1 − p) 1 8 − p 1 8 + (1 − p) 7 8 lb p 1 8 + (1 − p) 7 8 + p 7 8 lb p 7 8 + p 1 8 lb p 1 8 + (1 − p) 1 8 lb (1 − p) 1 8 + (1 − p) 7 8 lb (1 − p) 7 8 Исследуем функцию I(p) на экстремум d dp I(p) = 3 4 lb 1 + 6p 7 − 6p , 3 4 lb 1 + 6p 7 − 6p = 0, 1 + 6p 7 − 6p = 1, 1+6p = 7 −6p, p ∗ = 1/2. Подставляя полученное значение p ∗ в формулу для I(p) получим выражение для пропускной способности двоичного симметричного канала при вероятности помехи α: C = max p(x) I(p) = 1 + α lbα + α lbα. Подставляя сюда α = 7/8 получим C = 1 + 7 8 lb 7 8 + 1 8 lb 1 8 = 0.456 bit. Это же значение легче получить графически. Для этого построим график функции I(p) в Mathcad (см. рисунок). Из графика видно что максимальное значение скорости передачи данных I max (p ∗ ) = 0.456 в нашем канале достигается при p ∗ = 1/2. N I(p) 0 p 1 0.456 p * 2.1. Пропускная способность каналов связи 49 Задача 2.1. По двоичному симметричному каналу связи с помехами передаются сигналы (x 1 , x 2 ) с априорными вероятностями p(x 1 ); p(x 2 ) = 1 −p(x 1 ). Из-за наличия помех вероятность правильного приема каждого из сигналов (x 1 , x 2 ) уменьшается до α. Найти: 1. скорость передачи информации I(x; y); 2. пропускную способность канала. N p α N p α N p α 1 0.1 0.91 11 0.15 0.80 21 0.23 0.70 2 0.2 0.92 12 0.25 0.81 22 0.33 0.71 3 0.3 0.93 13 0.35 0.82 23 0.43 0.72 4 0.4 0.94 14 0.45 0.83 24 0.53 0.73 5 0.5 0.95 15 0.55 0.84 25 0.63 0.74 6 0.6 0.96 16 0.65 0.85 26 0.73 0.75 7 0.7 0.97 17 0.75 0.86 27 0.83 0.76 8 0.8 0.98 18 0.85 0.87 28 0.93 0.77 9 0.9 0.99 19 0.95 0.88 29 0.03 0.78 10 0.95 0.90 20 0.05 0.89 30 0.93 0.79 Задача 2.2. По двоичному симметричному каналу связи с помехами передаются сигналы (x 1 , x 2 ) с априорными вероятностями p(x 1 ); p(x 2 ) = 1 −p(x 1 ). Из-за наличия помех вероятность правильного приема каждого из сигналов (x 1 , x 2 ) уменьшается до α. Найти: 1. среднее количество информации I(x; y); 2. пропускную способность канала. p 1 p 2 α y 1 y 2 z 1 z 2 1−α α 1−α α α 1−α 1−α N p α N p α N p α 1 0.1 0.91 11 0.15 0.80 21 0.23 0.70 2 0.2 0.92 12 0.25 0.81 22 0.33 0.71 3 0.3 0.93 13 0.35 0.82 23 0.43 0.72 4 0.4 0.94 14 0.45 0.83 24 0.53 0.73 5 0.5 0.95 15 0.55 0.84 25 0.63 0.74 6 0.6 0.96 16 0.65 0.85 26 0.73 0.75 7 0.7 0.97 17 0.75 0.86 27 0.83 0.76 8 0.8 0.98 18 0.85 0.87 28 0.93 0.77 9 0.9 0.99 19 0.95 0.88 29 0.03 0.78 10 0.95 0.90 20 0.05 0.89 30 0.93 0.79 50 Глава 2. Каналы связи Пример 2.2. По каналу связи с помехами передаются сигналы ( 0,1). Из-за наличия помех сигнал 0 искажается на 1 с вероятностью e=0.1 и на 2 с вероятностью 2e=0.2. Сигнал 1 искажается на 0 с вероятностью s=0.2 и на 2 с вероятностью 3s=0.6. Найти пропускную способность канала. Решение. По условию канал связи имеет вид показанный на рисунке. 0 1 2 0 1 p q e s 2e 3s x \ y 0 1 2 p( x) 0 p(1-3e) pe 2pe p 1 qs q(1-4s) 3qs q p( y) p(1-3e)+qe pe+ q(1-4s) 2pe+3qs P = 1 Подставляя конкретные значения (e;s)=(0.1;0.2) получим x \ y 0 1 2 p( x) 0 0.7p 0.1p 0.2p p 1 0.2q 0.2q 0.6q q p( y) 0.7p+0.2q 0.1p+0.2q 0.2p+0.6q P = 1 Тогда H x (p) = − (p lbp + q lbq = p lbp + (1 − p) lb(1 − p)) ; H y (p) = −(0.7p + 0.2q) lb(0.7p + 0.2q) + (0.1p + 0.2q) lb(0.1p + 0.2q) + (0.2p + 0.6q) lb(0.2p + 0.6q) = −(0.5p + 0.2) lb(0.5p + 0.2) + (−0.1p + 0.2) lb(−0.1p + 0.2) + ( −0.4p + 0.6) lb(−0.4p + 0.6) H xy (p) = −(0.7p) lb(0.7p) + (0.1p) lb(0.1p) + (0.2p) lb(0.2p) + (0.2q) lb(0.2q) + (0.2q) lb(0.2q) + (0.6q) lb(0.6q) H xy (p) = −(0.7p) lb(0.7p) + (0.1p) lb(0.1p) + (0.2p) lb(0.2p) + 0.2(1 − p) lb(0.2(1 − p)) + 0.2(1 − p) lb(0.2(1 − p)) + 0.6(1 − p) lb(0.6(1 − p)) 2.1. Пропускная способность каналов связи 51 Взаимная информация есть I(p) = H x (p) + H y (p) − H xy (p) Пропускная способность канала определяется таким значением p, для которого скорость передачи информации I(x, y) принимает максимальное значение C = max I(p) = I(p ∗ ). Решаем задачу на экстремум. В mathcad определим функцию G(p) := d dp I(p) simplif y → и найдем ее корень на промежутке [0;1] root(G(p), p, 0, 1) = 0.492. Можно решить задачу приближенно построив график функции I(p). Из графика видим, что p ∗ ≈ 0.492, тогда для пропускной способности канала связи получим С=I(0.492)=0.2867 bit. N I(p) 0 p 1 0.2867 0.492 52 Глава 2. Каналы связи Пример 2.3. По каналу связи с помехами передаются сигналы ( 0,1,2). Из-за наличия помех сигнал 0 искажается на 1 с вероятностью 0.1 и на 2 с вероятностью 0.3. Сигнал 1 искажается на 0 с вероятностью s=0.2 и на 2 с вероятностью s=0.1. Сигнал 2 не искажается с вероятностью s=0.4 и принимает другие значения с равной вероятностью. Найти пропускную способность канала. 0 1 2 0 1 p q r 0.2 0.1 2 0.3 0.6 0.4 0.1 Решение. По условию канал связи имеет вид показанный на рисунке или x \ y 0 1 2 p( x) 0 6 10 p 1 10 p 3 10 p p 1 2 10 q 7 10 q 1 10 q q 2 3 10 r 3 10 r 4 10 r r p( y) 6 10 p + 2 10 q + 3 10 r 1 10 p + 7 10 q + 10 10 r 3 10 p + 1 10 q + 4 10 r P = 1 Тогда H x (p, q, r) = −(p lbp + q lbq + r lbr) H y (p, q, r) = − 6p + 2q + 3r 10 lb 6p + 2q + 3r 10 − p + 7q + 10r 10 lb p + 7q + 10r 10 − 3p + q + 4r 10 lb 3p + q + 4r 10 H xy (p, q, r) = − 6p 10 lb 6p 10 − p 10 lb p 10 − 3p 10 lb 3p 10 − 2q 10 lb 2q 10 − 7q 10 lb 7q 10 − q 10 lb q 10 − 3r 10 lb 3r 10 − 3r 10 lb 3r 10 − 4r 10 lb 4r 10 C учетом p + q + r = 1 запишем выражение для взаимной информации (скорости передачи) I(p, q) = H x (p, q, 1 − p − q) + H y (p, q, 1 − p − q) − H xy (p, q, 1 − p − q) Пропускная способность канала определяется такими значениями p, q, для которых I(p, q) принимает максимальное значение. 2.1. Пропускная способность каналов связи 53 Решаем задачу на экстремум. В mathcad определим функции G1(p, q) := d dp I(p, q) simplif y → G2(p, q) := d dq I(p, q) simplif y → и найдем ее корень на промежутке [0;1]: x = 1 100 y = 1 100 Given G1(x, y) = 0 G2(x, y) = 0 xval yval := F ind(x, y) xval = 0.47 yval = 0.42 Подставляя экстремальные значения p ∗ = 0.47, q ∗ = 0.42 получим пропускную способность канала связи C = I(0.47, 0.42) = 0.227bit. N Задача 2.3. По каналу связи с помехами передаются сигналы ( 0,1,2) с вероятностями p = q = r = 1/3. Из-за наличия помех сигнал 0 принимается как 0 с вероятностью e 1 и как 2 с вероятностью e 2 . Сигнал 1 искажается на 0 с вероятностью s 1 и на 2 с вероятностью s 2 Сигнал 2 не искажается с вероятностью k 1 и принимает значение 0 вероятностью k 2 . Найти скорость передачи информации по каналу. 0 1 2 0 1 p q r 2 e 1 e 2 s 1 s 2 k 1 k 2 N e 1 e 2 s 1 s 2 k 1 k 2 N e 1 e 2 s 1 s 2 k 1 k 2 1 0.0 0.2 0.0 0.1 0.2 0.2 16 0.0 0.3 0.5 0.4 0.3 0.0 2 0.1 0.9 0.1 0.1 0.2 0.2 17 0.1 0.3 0.5 0.4 0.3 0.0 3 0.2 0.8 0.2 0.1 0.2 0.3 18 0.2 0.3 0.5 0.4 0.3 0.0 4 0.3 0.7 0.3 0.1 0.2 0.3 19 0.3 0.3 0.5 0.3 0.3 0.0 5 0.4 0.6 0.4 0.1 0.2 0.3 20 0.4 0.3 0.5 0.3 0.4 0.0 6 0.5 0.5 0.5 0.1 0.2 0.3 21 0.5 0.3 0.5 0.3 0.4 0.0 7 0.6 0.4 0.6 0.1 0.2 0.5 22 0.6 0.3 0.5 0.3 0.4 0.0 8 0.7 0.3 0.7 0.1 0.2 0.4 23 0.7 0.0 0.5 0.2 0.4 0.0 9 0.8 0.2 0.8 0.1 0.2 0.4 24 0.8 0.0 0.5 0.2 0.5 0.0 10 0.9 0.1 0.9 0.1 0.2 0.4 25 0.9 0.0 0.5 0.2 0.5 0.0 11 0.8 0.1 0.8 0.1 0.2 0.4 26 0.8 0.0 0.5 0.2 0.6 0.0 12 0.8 0.1 0.7 0.1 0.2 0.5 27 0.7 0.0 0.5 0.1 0.6 0.0 13 0.7 0.1 0.6 0.1 0.2 0.5 28 0.6 0.4 0.5 0.1 0.7 0.0 14 0.7 0.2 0.6 0.1 0.2 0.5 29 0.5 0.5 0.5 0.1 0.7 0.0 15 0.7 0.2 0.6 0.1 0.2 0.5 30 0.4 0.5 0.5 0.1 0.7 0.0 54 Глава 2. Каналы связи Пример 2.4. По 3-ичному симметричному каналу связи с помехами передаются сигналы ( 0,1,2). Из-за наличия помех сигнал 0 с вероятностью α/2 может восприниматься как 1 или 2 и безошибочно принимается с вероятностью 1 − α. Поскольку канал симметричный, аналогичным образом ведут себя и другие сигналы. Найти пропускную способность канала связи. 0 1 2 0 1 p q r 2 1−α α/2 α/2 Решение. Запишем канальную матрицу p(y |x) = 1 − α α/2 α/2 α/2 1 − α α/2 α/2 α/2 1 − α Тогда, матрица совместных вероятностей входного x и выходного y сигнала равна p(x, y) = p(1 − α) pα/2 pα/2 qα/2 q(1 − α) qα/2 rα/2 rα/2 r(1 − α) откуда пропускная способность C = lb3 + (1 − α) lb(1 − α) + α lb α 2 . N Аналогично, для k-ичного канала, с вероятностью ошибки α/(k − 1), получим C = lbk + (1 − α) lb(1 − α) + α lb α k − 1 Пример 2.5. По каналу связи с ретранслятором 0 1 2 0 1 p q r 2 передаются сигналы ( 0,1,2). Из-за наличия помех каждое значение сигнала не искажается с вероятностью α = 0.8 и принимает другие значения с равной вероятностью. Найти пропускную способность канала. |