Луизова Л.А. Теория информации. Кодирование
Подождите немного. Документ загружается.
ПетрГУ
Кафедра информационно-измерительных систем и
физической электроники.
Луизова Л.А.
Теория информации
Петрозаводск
2009
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
2
Луизова Л.А. Теория информации
Конспект лекций. – Петрозаводск, ПетрГУ, 2009г.
Кафедра информационно-измерительных систем и
физической электроники.
Конспект лекций по теории информации
Лекции записали и набрали студенты: Забровский Анатолий, Пискунов Андрей и
Минькович Даниил . После некоторых исправлений, дополнений и сокращений они
помещены на сайт в помощь другим студентам Буду благодарна за все замечания и
дополнения. Л.А.Луизова
Содержание
Неравенство Рао - Крамера 3
Понятие информации по Шенону 5
Получение информации о системе A в опыте B 6
Информационные характеристики источников информации и каналов связи 9
Информационные характеристики канала передачи данных 11
Кодирование информации 13
Эффективное кодирование 13
1. Код Шеннона – Фано 13
2. Код Хафмана 14
Теоремы Шеннона о передаче информации 15
Помехоустойчивые коды 15
Код Хэмминга 16
Циклические коды 17
Адаптивное кодирование 19
Кодирование с целью скрытия информации 19
Непрерывный код 19
Блочная кодировка 19
Код с симметричным ключом 19
Код с несимметричным ключом 19
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
3
Неравенство Рао - Крамера
Пусть из результатов эксперимента необходимо найти некоторый параметр.
x – результат;
α - параметр
Неравенство Рао – Крамера отвечает на вопрос:
Какова предельная точность оценки параметра?
Полное описание эксперимента P(x, α )-это вероятность получить данный результат x
эксперимента при конкретном значении искомого параметра α.
Пример: Студент предлагает измерять высоту небоскреба H
0
, карабкаясь по стене и
последовательно прикладывая к ней барометр, длина которого L.
Предполагается , что L ~ N (L
0
, σ
2
), n- число раз , которое барометр уложится на высоте.
Тогда n*L- результат измерения, H
0
- искомый параметр.
P(n*L, H
0
)=
*
n2
1
22
δπ
22
2
)
0
(
n2
δ
HnL
e
−−
Второй предлагаемый способ: бросить барометр с крыши и засечь время между моментом
броска и звуком удара. Цена деления секундомера - 1 с.
Если пренебречь другими источниками погрешности,
1) P(t, H
0
)=1, при
5.0)
V
2
(-t
00
≤+
H
g
H
,
2) P(t, H
0
)=0 при
5.0)
V
2
(-t
00
>+
H
g
H
(g - ускорение свободного падения, V- скорость звука).
Выражения 1) и 2) это примеры полного описания эксперимента при различных
физических принципах измерения и различных типах погрешностей.
Доказательство неравенства Рао-Крамера
Пусть
α
~
- оценка искомого параметра . Матожидание оценки M
α
α
=
~
, находим его ,
используя известную функцию P(x,α)
α=
dxxP
αα
~
*),(
∫
+∞
∞−
1=
dxx
∫
+∞
∞−
),(P
α
( по определению) В дальнейшем опускаем пределы интегрирования, они
везде -бесконечности.
1=
dx
xP
α
α
α
~
*
),(
∫
∂
∂
0=
dx
xP
∫
∂
∂
α
α
),(
( Функцию под интегралом можно умножить и поделить на Р , от этого
ничего не изменится , но выражения преобразуются.
0*P*
Pln
=
∂
∂
∫
dx
α
1=
∫
∂
−
∂
α
α
α
α
)
~
)(,(xP
=
dxx
P
),(P*)
~
(*
ln
ααα
α
−
∂
∂
∫
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
4
Обозначим:
X
P
=
∂
∂
α
ln
,
)
~
(
α
α
−
=z
),Xcov(1)X( zzM
=
=
1DzDXr
Xz
=
, т.к. |r|≤1,
DX*Dz≥, и т.к.
α
α
α
~
)
~
( DD
=
−
, получаем:
∂
∂
≥
α
α
α
),(ln
1
~
xP
M
D
– Неравенство Рао-Крамера.
→≥
αα
α
g
D
1
~
g
α α
- это количество информации по Фишеру.
Путем непосредственных вычислений можно показать , что эту величину можно
преобразовать и к другому виду
2
2
2
),(ln),(ln
g
α
α
α
α
αα
∂
∂
−=
∂
∂
=
xP
M
xP
M
Если величина α однократно измерена прибором, погрешность которого распределена
нормально со средним 0 и дисперсией δ
2
и получен отсчет х, то
2
2
2
)(
*
2
1
),(
δ
α
πσ
α
−−
=
x
exP
2
1
δ
αα
=g
.
Если имеем два независимых измерения, то:
1
x
~ );,(
2
1
δα
N
2
x
~ );,(
2
2
δα
N
21
21
2
)(
2
)(
2
1
*
2
2
2
2
2
1
2
xxeP
xx
∆∆=⇒
−
−
−−
δπδ
δ
α
δ
α
2
2
2
11
1
δδ
αα
+=g
т. е. информация в независимых экспериментах складывается.
Если в эксперименте определяется несколько величин α ( и соответственно результатов х
должно быть не меньше), то такому эксперименту соответствует таблица величин
ij
m
xxP
M
αα
ααα
∂∂
∂
−=
)...,,,(ln
G
,2121
2
ji,
G
ij
-элементы информационной матрицы Фишера.
Если задача решается методом наименьших квадратов ,то
G
ij
=(A
T
WA)
ij
,
где А- матрица планирования, W- обратная ковариационная матрица
погрешностей эксперимента. Если эксперименты независимы и оценка дисперсии одного
отсчета S
2
y
,
то матрица G - диагональна
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
5
2
ii
y
1
)(G
S
AA
ii
T
=
Неравенство Рао-Крамера становися равенством , т.е. решение методом наименьших
квадратов даёт наименьшую погрешность в оценке результата измерений.
Понятие информации по Шенону
Рассмотрим некоторую систему: если эта система может находится
в состояниях: А
1
А
2
А
3
……………… А
m
с вероятностями: р
1
р
2
р
3
………………. р
m
,
то мы можем сказать что эта система обладает энтропией
i
m
i
i
ppH
2
1
log
∑
=
−=
Если же состояние этой системы определено, то можно сказать о том, что мы получили
количество информации, равное энтропии системы
Единицей информации может служить один бит – информация о системе из двух
равновероятных состояний:
- ½ ln ½ - ½ ln ½ = 1
Если система находится в одном из N равновероятных состояний, то количество
информации равно:
N
NN
H
N
i
22
1
log
1
log
1
==
∑
=
Информация в независимых экспериментах складывается:
А
1
А
2
…………… А
m
B
1
B
2
……………. B
n
P
1
P
2
…………… P
m
P
'
1
P
'
2
…………… P
'
n
jjiij
ij
ijij
ij
i
ppppppppppH
′′
+
′
=
′
=⇒
∑
∑
∑
222
loglog)*(log
Пусть имеем K независимых систем. Каждая система имеет m состояний. При каком
числе m энтропия будет максимальной , если Km=a ( постоянно)
m
m
a
mKHKH
221
loglog* ===
=
2ln
ln
log
2
x
x
0ln
dm
dH
;
ln2
1
ln
22
=+−==
m
a
m
m
a
m
m
a
H
,
lnm=1, т.е. наивыгоднейшее m= e=2.7. Технически удобно m=2, однако известны и
"троичные" машины , элементы которых имеют по 3 устойчивых состояния.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
6
Можно также показать, что система , имеющая N состояний обладает максимальной
энтропией если её состояния равновероятны.
Получение информации о системе A в опыте B
∑
=
⋅−=−=
n
j
jj
BAHBpAHBAHAHBAI
1
)/()()()/()()/(
,
где
j
B
один из n исходов опыта
B
.
)/( BAH
- называется средней условной энтропией системы А при условии В.
Рассмотрим систему, состоящую из A : A
1
…A
m
и B: B
1
…B
n
, причем все A
i
, i=1..m, не
совместны друг с другом и B
j
, j=1..n, не совместны друг с другом, но A
i
и B
j
, для любого
i и j, связаны между собой.
Система может находится в любом из состояний
ji
BA
.
Из курса «Теория вероятности» известно, что
)(
)(
)/(
Bp
ABp
BAp =
(*)
и
)(
)(
)/(
Ap
ABp
ABp =
.
Отсюда непосредственно следует, что
)()/()()/( ApABpBpBAp
⋅
=
⋅
.
Рассмотрим энтропию такой системы:
)(log)()(
2
,
,
ji
nm
ji
ji
BApBApABH
∑
−=
. (**)
Из (*) и (**) получим, что
)/A()B(
)/(log)()/()(log)()/(
)]()/([log)()/()(
2
,
,
2
,
,
2
,
,
ВHH
BApBpBApBpBpBAp
BpBApBpBApABH
ji
nm
ji
jjij
nm
ji
jji
jji
nm
ji
jji
+=
=
⋅+⋅−=
=⋅⋅−=
∑∑
∑
Таким образом
)B/A(H(B))A/B()()( HHAHABH +=+=
,
т.к. А и В можно поменять местами.
Отсюда, в частности следует , что
)A/B(H(B))/A()()/(I HBHAHBA −=−=
Выведем формулу для количества информации, которую мы можем получить о системе A
из опыта B.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
7
∑∑
∑∑
∑∑
⋅
⋅=
⋅
⋅⋅=
=⋅⋅+⋅⋅=
=⋅⋅+⋅−=
=−=
ji
ij
ji
ji
ji
ij
ji
jij
ji
j
ji
jij
ji
ijji
ji
jijij
ji
ii
ApBp
BAp
BAp
ApBp
BAp
BApBp
Bp
BAp
BApBpApBpBAp
BApBApBpApAp
BAHAHBAI
,
2
,
2
,
2
,
2
,
2
,
2
)()(
)(
log)(
)()(
)(
log)/()(
)(
)(
log)/()()(log)()/(
)/(log)/()()(log)(
)/()()/(
Отсюда вытекает очень важное свойство, а именно:
∑
⋅
⋅==
ji
ij
ji
ji
ApBp
BAp
BApABIBAI
,
2
)()(
)(
log)()/()/(
Пример:
По конвейеру идут детали A
1
-хорошие и A
2
– бракованные: вероятность встретить
хорошую деталь p(A
1
)=0.8 и бракованную – p(A
2
)=0.2.
На конвейере установлен робот, который проверяет качество деталей: он может не
забраковать (событие B
1
) или забраковать (событие B
2
) деталь.
Вероятность не забраковать хорошую деталь p(B
1
/A
1
)=0.9, забраковать хорошую -
p(B
2
/A
1
)=0.1 и забраковать бракованную - p(B
2
/A
2
)=1.
Из рисунка теперь видно, что
P(A
1
B
1
)=0.72
P(A
1
B
2
)=0.08
P(A
2
B
1
)=0
P(A
2
B
2
)=0.2
P(A
1
)=0.8
P(B
1
)=0.72
P(A
2
)= 0.2
P(B
2
)=0.28
50.0)/(
28.02.0
2.0
log2.00
28.08.0
08.0
log08.0
72.08.0
72.0
log72.0)/(
222
≈
⋅
⋅++
⋅
⋅+
⋅
⋅=
BAI
BAI
Рассмотрим теперь случайную величину
x
с непрерывной плотностью вероятности
)(xp
.
Разобьем ось X на отрезки
i
x
∆
, таким образом вероятность попадания
x
в интервал
i
x
∆
будет xxpxP
ii
∆⋅= )()( .
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
8
[ ]
xxxpxxpxp
xxpxxpxPxPH
ii
iiii
∆⋅∆⋅−∆⋅⋅−=
=∆⋅⋅∆⋅−=−=
∑∑
∑
∑
)(log)()(log)(
))((log)()(log)(
22
22
Если
0
x
→
∆
,
то
QdxxpxpH +⋅−=
∫
∞
∞−
)(log)(
2
,
где
∫
∞
∞−
⋅−= dxxpxph )(log)(
2
- дифференциальная энтропия.
Рассмотрим равномерное распределение.
Энтропия при равномерном распределении:
∫
−=
−
⋅
−
−=
b
a
abdx
abab
x )(log
1
log
1
)(h
22
Из всех распределений с фиксированными концами равномерное имеет наибольшую
энтропию.
Рассмотрим теперь нормальное распределение.
Пусть ),(~
2
σ
aNx , тогда энтропия
)e2(log
2
1
2
elog
2log
dx
2
)ax(
e
2
1
elogdxe
2
1
2log
dxe
2
1
loge
2
1
)x(h
2
2
2
2
2
2
2
2
2
2
)ax(
2
2
2
2
2
)ax(
2
2
2
2
2
2
)ax(
2
2
2
2
)ax(
σ⋅⋅π⋅⋅=+σ⋅π⋅=
=
σ⋅
−
⋅⋅
σ⋅π⋅
⋅+⋅
σ⋅π⋅
⋅σ⋅π⋅=
=
⋅
σπ⋅
⋅⋅
σπ⋅
−=
σ⋅
−
−
σ⋅
−
−
σ⋅
−
−
σ⋅
−
−
∞
∞−
∫∫
∫
Примечание:
xlnelogxlog
22
⋅
=
Из всех распределений с фиксированной дисперсией нормальное распределение имеет
наибольшую энтропию.
Пример 1:
Во сколько раз мощность равномерно распределенного сигнала (с параметром
a
) должна
быть больше нормально распределенного (c параметрами
b
и
2
N
σ
, чтобы они имели
одинаковую энтропию?
Пусть
0
Mu
=
, тогда
2
Du
P
σ
=
≈
, где
P
- средняя мощность сигнала.
Для нормального распределения:
2
NN
P σ=
.
Для равномерного :
3
a
P
2
2
00
=σ=
.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
9
)P12(log
2
1
)a4(log
2
1
)a2(logH
)Pe2(log
2
1
H
02
2
220
N2N
⋅⋅=⋅⋅=⋅=
⋅⋅π⋅⋅=
Отсюда видно, что
6
e
P
P
P12Pe2
N
0
0N
⋅
π
=⇒⋅=⋅⋅π⋅
Пример 2:
x -истинное значение сигнала.
),x(N~z
2
z
σ
- измеряемое значение сигнала.
δ
+
=
x
z
, где
),0(N~
2
δ
σ≈δ
.
)z(H)e2(log
2
1
)z(h
dx)e2(log
2
1
)x(p)z(h)x/z(h)z(h)z/x(I
2
2
2
2
εδ
δ
=σ⋅⋅π⋅⋅−=
=σ⋅⋅π⋅⋅⋅−=−=
∫
Величина
)z(H
ε
называется «эпсилон энтропия».
Пример 3:
),a(N~x
2
x
σ
-истинное значение сигнала.
),a(N~z
2
z
σ
- измеряемое значение сигнала.
22
x
2
z δ
σ+σ=σ
- при условии, что
x
и
z
независимы.
)1(log
2
1
log
2
1
)e2(log
2
1
)e2(log
2
1
)z/x(I
2
2
x
2
2
22
x
2
2
2
2
z2
δδ
δ
δ
σ
σ
+=
σ
σ+σ
=σ⋅⋅π⋅−σ⋅⋅π⋅=
Поскольку
2
Du
P
σ
=
≈
,
то
)1(log
2
1
.
2
шум
пол
P
P
I +=
.
( информация , содержащаяся в одном отсчете сигнала , среднее значение которого
равно 0, если Р
пол
- мощность полезного сигнала, Р
шум
- мощность шума).
Информационные характеристики источников информации и
каналов связи
Последовательность знаков можно рассматривать как сообщение.
Если у нас источник вырабатывает определённый набор знаков, то это источник
дискретных сообщений.
При этом, если появление каждого знака независимо от того что было до него, то это
источник с независимыми знаками.
Если вероятность появления любого знака не зависит от времени, то источник носит
название стационарного.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
10
Эргодическим источником называется источник, у которого результат оценки
вероятности по одному сообщению и по ансамблю дают один и тот же результат.
В дальнейшем мы будем рассматривать стационарный эргодический источник с
независимыми знаками.
Энтропия одного знака.
Пусть источник вырабатывает дискретные знаки (алфавит):
L: z
1
, z
2
, z
3
, z
4
,.................z
L
p
1,
p
2,
p
3,
p
4,...........................
p
L
Следовательно выражение для энтропии одного знака запишется так:
(
)
;plogpzH
i2
L
1i
i
∑
=
−=
Если бы все знаки встречались бы с равной вероятностью, то Llog
2max
=H
(
)
max
max
H
zHH
k
−
=
- коэффициент избыточности.
Информационной характеристикой источника является его производительность:
τ
z)(H
I =
- количество информации, которое источник может выдать за единицу
времени.
τ
- среднее время на выработку одного знака, т. к. на каждый знак может тратиться
различное время.
Возьмём большое количество знаков (последовательность):
Рассмотрим, какое число последовательностей длины N можно составить из L знаков.
M – число последовательностей: M = L
N
.
Типичная последовательность – последовательность, в которой различные знаки
встречаются с частотой, близкой к их вероятности.
Например: Сколько раз встретится знак z
i
?
Необходимо вспомнить закон больших чисел:
;1→<−
ε
i
i
p
N
m
P
где N – длина последовательности;
m
i
– число, показывающее, сколько раз знак z
i
встретится в
последовательности.
m
i
~ Np
i
(очень длинная последовательность)
Знаки независимы , для независимых событий A , B, C :
P(ABC) = P(A) * P(B) * P(C)
P(ABCA) = P(A)
2
* P(B) * P(C) , поэтому вероятность P
0
– типичной последовательности,
P
0
= p
1
NP1
* p
2
NP2
* ....
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.