Шпоры по задачам 7 семестра (для экзамена)

Задача 1 (пусть X и Y – случайные величины … д-ть а), б)) #

H[X] = - integral [от [x1,x2]] (1/d)*ld(1/d)dx = -ld(1/d) = ld(d)

H[X] -> inf, d->inf

=0, d=1

->-inf, d->0

d = δ

I[Y,X] = -integral(p(x)*ld(p(x))dx) + integral integral (p(x,y)*ld(p(x|y)))dx dy) > 0 , причем знак равенства имеет место если X и Y – стат незав вел-ны

Задача 2 (по цели может быть произведено n независимых выстрелов …) #

Пусть X(k) – основной опыт, имеющий после k-того выстрела 2 исхода – x1(k) (цель поражена) и x2(k) (не поражена).

Определим вероятности pi(k) состояний xi(k) (i=1,2) цели

xi(k)	x1(k)	x2(k)
pi(k)	p1(k)=1-(1-p)^k	p2(k)=(1-p)^k

Пусть Y(k) – вспомогательный опыт, имеющий после k-того выстрела 2 исхода – y1(k) – донесение разведки «цель поражена» и y2(k) – «не поражена». X(k) и Y(k) –тождественные опыты. Минимальная энтропия частного исхода опыта X(k) hmin – достигает своего максимума равного ld(2) при равенстве p1(k) = p2(k)

Задача 3 (Имеется группа из 26 или монет, фальшивая легче)#

------- самост ---

Разделить на 3 группы, взвешивать 2 группы. 1 группа будет подозрительной, разделить ее на 3, взвесить и т.д.

Задача 4 (дано распределение вероятности сообщ. X: {} Закодировать методами Фано и Хаффмана)#

xi	pi	подмн-ва	Код. Комб.
X1	0.40	0	0
X2	0.17	1 10 100	100
X3	0.16	1 10 101	101
X4	0.09	1 11 110 1100	1100
X5	0.09	1 11 110 1101	1101
X6	0.05	1 11 111 1110	1110
X7	0.04	1 11 111 111	1111

Задача 5 (Закодировать троичным алгоритмом Хаффмана (алф {0,1,2} …)#

При s=2 (число последов сжатий анс) первое целочисленное значение N0, большее 6 – число сообщений расширенного анс X0, при котором выполн N – s(L-1) = L, равно 7.

Следовательно к имеющимся 6 сообщ анс необх доб 1 фиктивное сообщ с px7ф=0. После кодирования фикт сообщ откинем.

nс =1.4 [симв/сообщение]

P.S. Объединение xi проводим по 3, т.к. алфавит троичный.

Задача 6 (имеется 12 монет одного достоинства, фальшивая отличается по весу…) #

--------

Задача 7 (Имеется 13 монет, фальшивая отлич по весу, мин число взвешиваний, тяж или легч фальш) #

-------

Задача 8 (Определить L-q и q для исх ансамблей сообще, прив в табл N=11, L=5) #

NМ=L+(L-1)](NМ-L)/(L-1)[ < N =11 => NМ=9

NБ=NМ+(L-1)=L+(L-1)(](NМ-L)/(L-1)[+1) = 5+4(]4/4[+1)=13

9=NМ<N=11<NБ=13

L-q = 13-11 =2;

Q = 5+11-13 =3;

как-бы граф %) :

(41)(42)(43)

\ | /

(12)(13) (14)(2)(3) (4) ----(44)

\ | / \ | /

(11)------(1)----------(k)---------(5)

Задача 9 (Даны анс сообщ X, распр вероятности, кодов алф A, написать выражения для класс алг Хафф) #

1. N0 – (L-1)*s = Ns < L

N0-(L-1)(s-1)=N(s-1)>L

(N0-L)/(L-1) < s < [(N0-L)/(L-1)]+1

(N0-L)/(L-1) = g

s = ]g[ + (1- Ф(]g[-g ))

Ф(x) – функ Хэвисайда 1 при x>0 иначе 0

S = ceil(g)

Nx=L-Ns (число фикт сообщ)

При N=6 и L=3

s=2, Ns=2, Nx=1

2.

Задача 3 #

Задача 2 #

Из условия равновероятности состояний «цель поражена» и «не поражена» находим

1-(1-p)^k=(1-p)^k

k = - 1/[ld(1-p)] = 1/[ld(1/(1-p))]

Т.к. k- целое, то

k(p) = ceil(1/ld(1/(1-p)))

при найденном k

hmin ~~ H[X(k)] ~~ ld(2) = 1[бит]

Задача 1 #

Задача 6 #

Задача 5 ###

Задача 4 #

Хаффман – самост.

Для Фано:

nс = 2,47 [симв./сообщение]

Для Хаффмана:

nс = 2,47 [симв./сообщение]

H[X0] < nсХ = nсФ < H[X0]+1, что для заданного анс. Сообщ. X0 доказывает существ. Опт. Преф. Кода Фано при распределении вероятности анс отличном от целых отриц степ целого числа L и не противоречит хар-ке кода Хаффмана, как опт преф кода.

Задача 9 #

xi	X0	X1	X2
x1	0.3 1	0.3 1	0.5 0
x2	0.2 2	0.3 2	0.3 1
x3	0.15 01	0.2 00	0.2 2
x4	0.15 02	0.15 01
x5	0.1 000	0/15 02
x6	0.1 001
x7	0 002

nс=1.7 , но для классич – опт полное код дерево, а для модиф – не полное.

Для модиф – то же без x7.

Задача 8 ###

Задача 7 #

Задача 10 (Пусть z1,z2,…,zN – посл-ть стат незав и одинак распр случ вел-н с мат ожид z и дисп …) #

Pr – Probability – вероятность _

Если y – случ вел-на с мат ож y и дисперсией d^2(y) то для люб e>0 согласно нер-ву Чебышева:

Pr{|y- y |>e}<(d^2(y))/(e^ 2)

Pr{(|y-y|)/d > e/d} = Pr{|y-y|/d > x}< R(x) = (1/x)^2 , где x = e/d >0

Построить график 1, x, R(x)

Из графика следует, что при x>0 вероятность реализации точки, представляющей величину |y-y|/d и лежащей ниже биссектрисы первого квадрантного угла, изображается точкой, лежащей не выше кривой R=R(x)=(1/x)^2

Задача 11 (Дискретный источник генерирует на своем выходе … 1)-4))

Случайными вел-нами в задаче явл число нулей N0 и число единиц N1 в рассматр отрезке посл-ти симв длины n = (N0+N1). Эти случ вел-ны распределены по биномиальному закону и поэтому:

1. m0 = p*n = 990, m1 = q*n = 10

2. D0 = n*p*q = 9.9, D1 = n*p*q = 9.9

3. Воспользуемся нерав-вом Чебышева

Pr{|N0-m0|>alpha}<D0/(alpha^2)

При alpha = 0.1*m0 = 99 :

Pr{|N0-m0|>99}<9.9/(99^2) = 0.001

=> Pr{|N0-m0|<99}>0.999

4) проведем аналогичные вычисления для симв «1»

Задача 12 (Источник порождает стат незав 2ичные символы с вероятностями… найти мат ожид и дисперсию)#

Введем обознач I100 = h100, где h100 – энтропия дискр послед-ти длины 100, явл случ вел-ной

Мат ожид суммы любых случ вел-н равно сумме их мат ожид, поэтому в данном случае M[h100]=100M[h1]=100H1, где h1 – энтропия одиноч симв, явл случ вел-ной, H1=M[h1] - энтропия элементарного опыта в выходной посл-ти опытов.

Дисперсия суммы некоррелированных случ величин равна сумме их дисперсий (в общ случае). В рассм случае дисп суммы стат независ

Задача 13 (Дискр источник генерирует на своем вых посл-ть стат незав 2ичн симв….. 1),2),3) - ?) #

M[h(q)] = H(q) = q*ld(1/q) + (1-q)*ld(1/(1-q)) = H(q)

D[h(q)] = q*(ld(1/q))^2 + (1-q)*ld(1/(1-q))^2 – (H(q))^2

С.к.о. энтропии на символ d[h(q)]= D[h(q)]^0.5

Функция d[h(q)] достигает своего минимума равного 0 в 3х точках

d[h(0)]=d[h(0.5)]=d[h(1)]=0;

Она же достигает своего максимума равного 0.956 в 2х точках q1 = 0.083 и q2 = 0.917

Действительно, d[h(q1)]= d[h(q2)]=0.956 и d[h(q)]<d[h(q1)]=d[h(q2)] при q != q1 и q != q2

Задача 14 (Показать что если ДСИ генер посл-ть стат незав символов, то …) #

Действительно, т к опыты в посл-ти опытов на выходе ДСИ являются стат незав, то

H[α| α^infinity] = lim[nu->infinity]((1/nu)*(nu*H[alpha])) = H[alpha]

Задача 15 (ДСИ генер посл-ть 2ичных стат нез симв с зад вер-тями. Эффективность кода S=S(q))… #

S(q) = - [q*ld(q)+(1-q)*ld(1-q)]/[ld(L)] = H(q)/ld(L)

R(q) = 1-S(q) = 1-H(q)

Примечание:

Эффективность

S_A = (H[alpha|alpha^infinity])/ld(L)

H[alpha|alpha^infinity] – среднее значение информации на символ, генерируемой источником, а L – число символов алфавита А, использ источником 0<SA<1

Избыточность

R_A = 1 - S_A

Задача 16 (Сколько различных состояний Nи имеет эргодич источник …) #

Эргодич источник r-того порядка является также марковским источником. С друг стороны вер-ть испускания некоторого символа эргодическим источником r-того порядка определяется лишь r предшествующими символами, а с другой стороны вероятн-ть испускания некот символа Марковским источн определяется покидаемым источником состоянием. Следовательно число различных состояний рассм ист-ка не превосх L^r – числа всевозможных посл-тей символов используемого алфавита длины r и больше числа L^(r-1) – числа всевозм посл-тей длины r-1.

Задача 17 (на рис 1 приведен граф источника… охарактеризовать источник ..) #

Рассматриваемый источник явл ДСИ, Марковским, неразложимым, непериодическим, эргодическим источником. L =2, число состояний Nи=1, порядок этого источника r=0.

Асимптотич значение энтропии на символ

H[alpha|alpha^infinity]= H[3/7] = -(3/7)*ld(3/7) – (4/7)*ld(4/7) = 0.985 [бит/симв]

Задача 18 (Определить пропускную способность канала связи без шумов …) #

Т.к. на вид посл-ти никаких ограничений не наклад, то N(T) = L^]T/tau[

C[бит/с] = lim[T->infinity]((ld(N(T)))/T) = lim[T->infinity]((ld(L^]T/tau[))/T) = ld(L)/tau причем пропускная способность канала реализуется при статистической независимости символов посл-ти и при равновероятном появл символов в кажд позиции посл-ти

C[бит/симв]= C[бит/с]/nu = tau*C[бит/с] = ld(L)

Задача 12 #

Случ вел-н равна сумме их дисперсий

D[h100] = M[(h100-100*H1)^2] = 100D[h1]

M[h1]=H1 = (1/4)*ld(4)+(3/4)*ld(4/3) = 0.811

D[h1] = (3/4)(ld(4/3))^2 + (1/4)(ld(4))^2 – (H1)^2 = 0.471

M[I100] = 100*M[h1] = 100*H1 = 81.1

D[I100] = 100D[h1] = 47.1

Задача 11 #

Pr{|N1-m1|>beta}<D1/(beta^2)

При beta = 0.1*m1 = 1

Pr{|N1-m1|>1}<9.9/(1^2) = 9.9

Т.к. вер-ть не может быть больше 1, то положим beta = 3d1, где

d1 = σ₁ = (D1)^(1/2) = 3.136

при этом Pr{|N1-m1|>3d1}<D1/(9d^2(1))=1/9

=> Pr{|N1-m1|<3d1}>8/9

5) Легко видеть, что при n> 100*max{p/q, q/p} = 9.9*10^3 проблема «малой информативности» не возникает. Так при n=10^4 получим

Pr{|N1-m1|<beta}>D1/(beta^2) => Pr{|N1-m1|<10}>0.99

Если X –непрер или дискр случ вел-на, то D[X] = M[X^2] – (M[X])^2

Задача 10 #

Т.к z1,z2,…,zN – посл-ть стат незав и одинак распр случ вел-н, то

yN = (1/N)SUM[от n](zn)

а т.к. дисперсия суммы независимых случ вел-н равна сумме дисперсий отдельных случ вел-н, то

1

d^2(yN) = (yN – yN)^2 = (1/(N^2))*

*(SUM[от n](zn)-SUM[от n](zn))^2 =

= N(d^2(z))/(N^2) = d^2(z)/N

Поэтому полагая y = yN с учетом пред выраж будем иметь

Pr{|yN-yN|>e}<[d^2(yN)]/[e^2] = d^2(z)/(N^2(e))

P.S. d = σ, e = ε

Задача 15 #

График: (рис. 5.2)

Задача 14 #

Задача 13 #

Графики: (рис. 5.1б)

Задача 18 #

Задача 17 #

Задача 16 #

L^(r-1) < Nи < L^r

log_L(Nи) < r < log_L(Nи+1)

r= ceil(log_L(Nи))

Задача 19 (Решить задачу 18 с ограничением – запрещено передавать подряд 2 одинак символа) #

Число всех возможн допустимых посл-тей длины T

N(T) = L(L-1)^(]T/tau[-1)

При условии, что N(T) посл-тей равновероятны:

C[бит/с] = lim[T->infinity]((ld(N(T)))/T) = lim((ld(L(L-1)^(]T/tau[-1)))/T)= ld(L-1)/tau

C[бит/симв]= С[бит/с]/nu = tau*C[бит/с] = ld(L-1)

Задача 20 (СБПК задан своим графом табл2 №1… при каких условиях м б реализ..) #

Из вида графа следует: H[X|Y] = H[Y|X] = 0 т.е. в канале отсутствует дефицит алфавита и шум, и, следовательно, информация не рассеивается.

C[бит/симв] = max[{p(x)}] I[Y,X] = max (H[X]-H[X|Y]]) = max H[X] = max (H[Y]-H[Y|X]) = max H[Y] = ld(L), что имеет место при стат независимости символов на входе канала и равномерном входном распределении вер-ти: p(xi) = 1/L, i=1,2,…,L

C[бит/с] = nu*ld(L)

Задача 21 (Предположим, что вых сигналы СБПК статистически не зависят т его вх сигналов Сбит/симв, Сбит/с - ?) #

Из условия: H[Y|X] = H[Y]

C[бит/симв] = max[{p(x)}] I[Y,X] = max (H[Y] – H[Y|x]) =0

C[бит/с] = 0

Задача 22 (СБПК задан свои графом табл 2 №3 и способен передавать nu элементарных симв в секунду…) #

Из вида графа следует:

H[X|Y] = 0

C[бит/симв] = max[{p(x)}](I[Y,X]) = max (H[X]-H[X|Y]) = max H[X] = ld(Lx), что имеет место при статистической независимости символов на входе канала и равномерном входном распред вероятности p(xi) = 1/Lx, i=1,2,…,Lx

C[бит/с] = nu*ld(Lx)

Задача 23 (Двоичный СБПК задан своим графом табл 2 № 5 …) #

Согласно приведенному графу СБПК имеет симметричную МПВ (матрицу переходных вероятностей)

P = [ (1-p) p ]

[ p (1-p)]

тогда

C[бит/симв] = ld(2) + (1-p)*ld(1-p) + p*ld(p) = 1- H(p) где

(-(1-p)*ld(1-p) – p*ld(p)) = H(p)

C[бит/с] = nu*(1-H(p))

При заданном p пропускная способность канала C(p) реализуется при статистической независимости символов на входе канала и равномерном входном распределении вероятности.

Задача 24 (В непрерывном канале с шириной полосы рабочих частот В…) #

Мощность белого гауссова шума, действующего в канале

Q_N = q0*B

C(B) = B*ld(1+ Qs/(q0*B))

Пусть B=1/z, где Z – новая переменная

lim[B->0]C(B) = lim[z->inf]C(1/z) = lim(Qs/q0)(1/((1+Qs*z/q0)*ln(2))) = 0

lim [B->inf] C(B) = lim[z->0] C(1/z) = lim (ln(1+Qs*(z/q0))*(1/(z*ln(2)))) = Qs/(ln(2)*q0) = Qs*ld(e) / q0

при 0<B<infinity

lim[B->0] C’(B) = + infinity

lim[B->inf] C’(B) = 0

C’(B) > 0

C’’ (B)<0

График: ( на обороте )

Задача 25 (В непрерывном канале действует аддитивный белый шум…) #

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

C[бит/с] = C = C(B) = B*ld(1/(Qs/Q_N))

Qs – макс значение средней мощности сигнала, Q_N – мощность аддитивного белого гауссова шума

Информация, передаваемая по каналу за время T по условию должна удовлетворять C*T = 1 [бит]

Мощность бел гаусс шума в канале Q_N = q0*B

B*T*ld(1+ (Qs/Q_N)) = BTld(1+ (Qs/(q0*B))) = 1

B*T*ld(1+ (E/(q0*B*T))) = 1, где Qs*T = E – энергия сигнала длительности T

E = E(BT) = (2^(1/BT)-1)*q0*B*T

BT = x

E = E(x) = q0(2^(1/x)-1)x= q0*ψ(x)

Задача 21 #

Задача 20 #

Задача 19 #

Задача 24 #

Задача 23 #

График: C(p)

1

0 _ 0.5 1

Задача 22 #

График: (рис. 6.8)

Задача 25 #

Где ψ(x) = (2^(1/x) -1)x

Можно установить что при 0<x<inf

lim[x->0] ψ’(x) = -inf

lim[x->inf] ψ’(x) = 0

ψ’(x) <0

ψ’’(x)>0

Из свойств функции ψ(x) следует:

Emin = q0*ln(2)

Найденное Emin не реализуется ни при каком конечном значении произведения BT, однако к нему можно приблизиться сколь угодно точно при неогранич увелич B*T

График ψ(x):