ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
1 2 r · 1 · 1 2 0 r p( y) pα 2 + p · 1−α 4 + q+r 2 pα(1 − α) + p 1−α 4 + q+r1 2 p · 1−α 2 P = 1 Тогда H x (p, q, r) = −(p lbp + q lbq + r lbr) H y (p, q, r) = − pα 2 + p · 1 − α 4 + q + r 2 lb pα 2 + p · 1 − α 4 + q + r 2 − pα(1 − α) + p 1 − α 4 + q + r 2 lb pα(1 − α) + p 1 − α 4 + q + r 2 − p · 1 − α 2 lb p · 1 − α 2 H xy (p, q, r) = − pα 2 + p · 1 − α 4 lb pα 2 + p · 1 − α 4 − q 2 lb q 2 − r 2 lb r 2 − pα(1 − α) + p 1 − α 4 lb pα(1 − α) + p 1 − α 4 − q 2 lb q 2 − r 2 lb r 2 − p · 1 − α 2 lb p · 1 − α 2 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) принимает максимальное значение. Решаем задачу на экстремум. В 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) 56 Глава 2. Каналы связи xval = 0.47, yval = 0.42 Подставляя экстремальные значения p ∗ = 0.45, q ∗ = 0.001 получим пропускную способность канала связи C = I(0.45, 0.001) = 0.0072bit. N Пример 2.6. По известной канальной матрице p( y|x) = 1 0 0 0 0.8 0.2 0 0.3 0.7 определить скорость передачи и потери информации в канале с помехами, если входные символы сообщения появляются с вероятностями p( x) = (1/2, 1/3, 1/6). Решение. Матрицу совместных вероятностей получим по формуле p( x,y) = p(y|x) × p(x) = 1 0 0 0 0.8 0.2 0 0.3 0.7 × 1/2 1/3 1/6 = 1 · 1/2 0 · 1/2 0 · 1/2 0 · 1/3 0.8 · 1/3 0.2 · 1/3 0 · 1/6 0.3 · 1/6 0.7 · 1/6 = 1/2 0 0 0 8/30 2/30 0 3/60 7/60 Складывая элементы полученной матрицы, получим редуцированные законы распределения: по строкам - для входного сигнала p( x) = (1/2, 1/3, 1/6). по столбцам - для выходного сигнала p( y) = (1/2, 19/60, 11/60). Вычисляем энтропию H(x) = X p(x) lbp(x) = − 1 2 lb 1 2 + 1 3 lb 1 3 + 1 6 lb 1 6 = 1.459 H(y) = X p(y) lbp(y) = − 1 2 lb 1 2 + 19 60 lb 19 60 + 11 60 lb 11 60 = 1.474 H(xy) = X p(xy) lbp(xy) = − 1 2 lb 1 2 + 8 30 lb 8 30 + 2 30 lb 2 30 + 3 60 lb 3 60 + 7 60 lb 7 60 = 1.847 2.1. Пропускная способность каналов связи 57 Потери информации со стороны источника H(y/x) = H(x, y) − H(x) = 1.847 − 1.459 = 0.388. Потери информации со стороны приемника H(x/y) = H(x, y) − H(y) = 1.847 − 1.474 = 0.373. Скорость передачи информации I(x, y) = H(x) + H(y) − H(x, y) = 1.459 + 1.474 − 1.847 = 1.086. N Задача 2.4. По каналу связи с ретранслятором передаются сигналы (0,1,2). Из- за наличия помех каждое значение сигнала не искажается с вероятностью α = 1 N и принимает другие значения с равной вероятностью. Найти пропускную способность канала. Пример 2.7. Имеется источник информации с энтропией в единицу времени H=100 (бит) и два канала связи; каждый из них может передавать в единицу времени F=70 бит (0 или 1): в результате помехи каждое значение бита заменяется противоположным с вероятностью . Требуется выяснить: достаточна ли пропускная способность этих каналов для передачи информации, поставляемой источником? Решение. При отсутствии помех два канала с частотой генерации сигналов F=70 бит/сек. смогут обеспечить пропускную способность 2F=140 бит/сек., т.е. больше скорости источника H=100 бит/сек При наличии помех пропускная способность двоичного симметричного канала уменьшается и определяется по формуле C = F · [1 + p lbp + (1 − p) lb(1 − p)] . Тогда p lb p = 0.1 · lb(0.1) = −0.332, (1 − p) lb(1 − p) = 0.9 lb(0.9) = −0.137 C = F · (1 − 0.332 − 0.137] = 37.17 bit/s. Максимальное количество информации, передаваемое по одному каналу в единицу времени C=37.17 бит/сек. Это означает, что два канала смогут обеспечить скорость 2С=74.34 бит/сек., т.е. меньше чем H=100 бит/сек., Поэтому при данном уровне помех двух каналов недостаточно для обеспечения передачи всей информации от источника. Задача 2.5. Имеется источник информации с энтропией в единицу времени H бит и K каналов связи; каждый из которых может передавать в единицу времени F бит. В результате помехи каждое значение бита заменяется противоположным с вероятностью P. Требуется выяснить: достаточна ли пропускная способность этих каналов для передачи информации, поставляемой источником? 58 Глава 2. Каналы связи N H K F P N H K F P 1 290 4 80 0.021 16 160 4 50 0.036 2 280 5 60 0.022 17 170 3 60 0.037 3 289 3 100 0.023 18 180 4 70 0.038 4 270 4 80 0.024 19 190 3 80 0.039 5 270 4 70 0.025 20 130 7 20 0.040 6 270 4 100 0.026 21 110 6 20 0.041 7 280 3 110 0.027 22 120 4 35 0.042 8 288 6 55 0.028 23 130 3 45 0.043 9 289 6 50 0.029 24 140 4 35 0.044 10 278 4 70 0.030 25 150 3 60 0.045 11 210 3 75 0.031 26 160 4 40 0.046 12 220 4 80 0.032 27 170 3 60 0.047 13 230 3 80 0.033 28 180 4 50 0.048 14 240 4 65 0.034 29 190 3 70 0.049 15 250 3 65 0.035 30 140 4 30 0.050 2.2 Теоремы Котельникова и Шеннона Непрерывный сигнал характерен тем, что он задается для любых моментов времени на некотором отрезке длительности Т. В противном случае сигнал не будет непрерывным. Однако применение всех видов импульсной модуляции принципиально связано с необходимостью дискретизации (квантования) сигнала по времени. При этом естественно поставить вопрос – какие условия необходимо соблюдать, чтобы обеспечить передачу непрерывного сигнала с надлежащей точностью при наличии его квантования по времени. Ответ на поставленный вопрос не является единственным – возможны различные решения. Рассмотрим квантование непрерывного сигнала по времени в смысле Котельникова. Основным условием при этом является ограниченность спектра сигнала. Итак, пусть сигнал, представляющий собой непрерывную функцию времени х(t), имеет ограниченный спектр. Теорему Котельникова можно формулировать следующим образом. Всякий непрерывный сигнал, со спектром, ограниченным ω c , полностью определяется своими дискретными значениями в моменты отсчета, отстоящие друг от друга во времени на интервалы ∆t = 1/2ω c x(t) = +∞ X k=−∞ x(k∆t) sin ω c (t − k∆t) ω c (t − k∆t) Базисную функцию sinc(y) = sin(y)/y, называют функцией отсчетов, а x(k∆t) - отсчетами. Таким образом, если известны значения функции x(t) в точках отсчета, то она может быть полностью восстановлена для всех t посредством суммирования типовых функций отсчетов с соответствующими коэффициентами. 2.2. Теоремы Котельникова и Шеннона 59 Однако при практическом применении теоремы Котельникова возникают два принципиальных затруднения, не позволяющие использовать ее строго для интересующих нас сигналов. Во-первых, всякий реальный сигнал имеет конечную длительность, т. е. бесконечно широкоий спектр, что противоречит основному условию теоремы Котельникова. Во-вторых, для восстановления сигнала x(t) на приемном конце связи по его значениям в моменты отсчета необходимо в приемнике генерировать функции отсчетов, а так как последние имеют бесконечную протяженность во времени для отрицательных значений t, соответствующие фильтры физически неосуществимы. Таким образом, сигнал при приеме может быть восстановлен только приближенно. Однако отмеченные особенности теоремы Котельникова существенно затрудняют ее использование лишь в том случае, когда не делается никаких ограничений в точности воспроизведения передаваемого сигнала. На практике же никогда не требуется идеально точного воспроизведения, более того, такая постановка задачи противоречила бы реальным условиям работы систем связи и управления. Поэтому приближенный характер представления сигнала вполне возможен, если степень приближения не превосходит некоторых допустимых значений. На практике используют 2 следствия теоремы Котельникова: F Любой аналоговый сигнал может быть восстановлен с какой угодно точностью по своим дискретным отсчётам, взятым с частотой ω > 2ω c , где ω c — максимальная частота, которой ограничен спектр реального сигнала. F Если максимальная частота в сигнале превышает половину частоты дискретизации, то способа восстановить сигнал из дискретного в аналоговый без искажений не существует. Частота дискретизации (или частота семплирования, англ. sample rate) — частота взятия отсчетов непрерывного во времени сигнала при его дискретизации (в частности, аналого-цифровым преобразователем). Измеряется в Герцах. Частота Найквиста — в цифровой обработке сигналов частота, равная половине частоты дискретизации. Названа в честь Гарри Найквиста. Из теоремы Котельникова следует, что при дискретизации аналогового сигнала потерь информации не будет только в том случае, если спектр (спектральная плотность) сигнала равен нулю выше частоты Найквиста. Поэтому частоту дискретизации выбирают с запасом, к примеру, в аудио компакт- дисках используется частота дискретизации 44100 Герц, в то время как высшей частотой в спектре звуковых сигналов считается частота 20000 Гц. Используемые частоты дискретизации звука: 8 000 Гц — телефон, достаточно для речи; 11 025 Гц; 16 000 Гц; 22 050 Гц — радио; 32 000 Гц; 44 100 Гц — используется в Audio CD; 48 000 Гц — DVD, DAT. 96 000 Гц — DVD-Audio (MLP 5.1) 192 000 Гц — DVD-Audio (MLP 2.0) 2 822 400 Гц — SACD Super audio CD 5.1 — максимальная на 2008 г. 60 Глава 2. Каналы связи Клод Шеннон определил зависимость пропускной способности канала , обладающего определенной полосой пропускания F , от отношения сигнала S к шуму N C = F · lb 1 + S N Пример 2.8. Для стандартного телефонного канала F = 3 kHz и S/N = 31 db получим C = F · lb 1 + S N = 3000 · lb (1 + 31) ' 15 kb/s. N Однако к данной формуле надо относится осторожно, поскольку из нее следует, что при нулевом уровне шума можно получить бесконечно большую скорость передачи информации. Согласно теореме Найквиста максимальная скорость передачи данных C по каналу без шума определяется формулой: C = 2F · lb(n), где n - число дискретных уровней сигнала. Данная формула согласуется с теоремой Котельникова. При полосе сигнала F частота стробирования должна быть больше 2F , чтобы принимающая сторона могла корректно восстановить форму исходного сигнала. Пример 2.9. Для стандартного телефоного канала без шума с F = 3kHz при n = 2 получим C = 2F · lb(n) = 2 · 3000 · lb(2) ' 6 kb/s, а при n = 256: C = 2 · 3000 · lb(256) = 6000 · 8 ' 48 kb/s. N Задача 2.6. Пользуясь формулой Найквиста определить количество допустимых уровней сигнала n в телефонном канале связи с пропускной способностью C kb/s. N C N C N C N C N C N C N C N C N C N C 1 8 4 12 7 15 10 18 13 21 16 24 19 27 22 30 25 33 28 36 2 6 5 13 8 16 11 19 14 22 17 25 20 28 23 31 26 34 29 37 3 8 6 14 9 17 12 20 15 23 18 26 21 29 24 32 27 35 30 38 2.3. Теория массового обслуживания 61 2.3 Теория массового обслуживания 2.3.1 Цепи Маркова Неограниченная последовательность опытов с единственно возможными и попарно несовместными исходами (s 1 , s 2 , ..., s n ) называется цепью Маркова, если вероятность любого из этих исходов в очередном опыте однозначно определяется результатом непосредственно предшествующего опыта. Совокупность несовместных исходов s = (s 1 , s 2 , ..., s n ) называется вектором состояния системы, компоненты которого образует полную группу событий: s 1 + s 2 + ... + s n = 1. Обозначения: p (0) j - вероятность j-го исхода в первом опыте (j = 1, 2, ..., m); (p (0) 1 + p (0) 2 + ... + p (0) m = 1); p n ji - вероятность j-го исхода в n-м опыте при условии, что в (n−1) -м опыте наступил i-й исход, (n = 2, 3, ...; i, j = 1, 2, ..., m; p (n) 1i +p (n) 2i +...+p (n) mi = 1). Введенными вероятностями полностью описывается цепь Маркова. Цепь Маркова называется однородной, если вероятность p (n) ij от n не зависят, в этом случае они обозначаются без верхнего индекса: p ij . Числа p ij называются вероятностями переходов, а P = (p ij ) = p 11 p 12 ... p 1m p 21 p 22 ... p 2m p m1 p m2 ... p mm - матрицей перехода. По матрице перехода можно построить граф состояний, если в качестве узлов взять состояния s = (s 1 , s 2 , ..., s n ) системы, а стрелками – возможные переходы из одного состояния в другое состояние. Например, для матрицы перехода P = p 11 p 12 p 13 0 0 p 21 0 0 0 0 p 31 0 0 0 0 0 0 p 43 0 0 0 0 p 53 0 p 55 граф состояния имеет вид 62 Глава 2. Каналы связи Обозначим: p ij (n) – вероятность того, что через n шагов произойдет переход от s j к s i (i, j = 1, 2, ..., m), P (n) – матрицу переходов за n шагов, т.е. матрицу, состоящую из p ij (n). Если в начальный момент система находилась в состоянии s 0 = (s 1 , s 2 , ..., s n ), то на следующем шаге она перейдет в состояние s 1 = P s 0 На втором шаге состояние системы есть: s 2 = P s 1 = P P s 0 = P 2 s 0 Очевидно, что через n шагов состояние системы s n будет выражаться через исходное состояние системы s 0 формулой s n = P n s 0 Т.о. справедлива формула P (n) = P n Теорема Маркова (о предельных вероятностях): если существует такое натуральное число n 0 , что все элементы матрицы P (n 0 ) = P n 0 строго положительны, то для каждого (j = 1, 2, ..., m) существует предельная вероятность lim n→∞ P (n) = P ∗ Предельные вероятности (если они существуют) можно найти из уравнений: P s = s, или p ij s j = δ ij s j , (p ij − δ ij ) s j = 0. Перепишем задачу в матричном виде (P − I)s = 0: p 11 − 1 p 12 p 1n p 21 p 22 − 1 ... p 2n p n1 p n2 ... p nn − 1 s 1 s 2 s n = 0. Таким образом, вместе с условием нормировки на компоненты вектора состояния, задача на отыскание предельного состояния сводится к решению системы уравнений: (p 11 − 1)s 1 + p 12 s 2 + ... + p 1n s n = 0 p 21 s 1 + (p 22 − 1)s 2 + ... + p 21 s n = 0 p n1 s 1 + p n2 s 2 + ... + (p nn − 1)s n = 0 s 1 + s 2 + ... + s n = 1 2.3. Теория массового обслуживания 63 Поскольку данная система переопределена (в ней содержится лишнее уравнение), то из него можно вычеркнуть одно уравнение. Нежелательно вычеркивать последнее уравнение нормировки вектора состояния. Пример 2.10. Пусть (A 1 , A 2 , A 3 ) – точки числовой оси с целочисленными координатами (x = 1, x = 2, x = 3). Представим себе частицу, которая движется по этим точкам следующим образом: если в какой-то момент времени t = n (n = 0, 1, 2, 3, ...) частица находится во внутренней точке A 2 , то в следующий момент t = n + 1 она переходит в A 1 с вероятностью q или в A 3 – с вероятностью p = 1 − q; если частица оказалась в левой граничной точке A 1 , то в следующий момент времени с вероятностью q она там остается или с вероятностью p возвращается в A 2 ; если же частица оказалась в правой граничной точке A 3 , то в следующий момент времени она там остается с вероятностью или возвращается в A 2 с вероятностью q. а) Найдите матрицу переходов и постройте ее граф состояний. б) Найдите матрицу переходов за 2 шага. в) Проверьте существование предельных состояний. г) Если существуют предельные состояния, то найдите их. Решение. а) Изобразим граф состояний. 1 2 3 p 11 p 12 p 21 p 32 p 23 p 33 Напомним, что начальному состоянию перехода соответствует второй индекс k, а конечному первый индекс i матрицы p ik . Находим вероятности переходов p ik за один шаг: p 11 = q, p 21 = p, p 12 = q, p 32 = p, p 23 = q, p 33 = p. В результате матрица переходов имеет вид: P = q q 0 p 0 q 0 p p В качестве проверки, заметим, что сумма элементов по столбцам матрицы равна 1, согласно условию нормировки для вектора состояния. б) Для нахождения P (2) вычисляем P 2 : P (2) = P 2 = q q 0 p 0 q 0 p p · q q 0 p 0 q 0 p p = q q 2 q 2 pq 2pq pq p 2 p 2 p |