Предмет статистической теории информации.

Билеты по Теории Информации

Оглавление

Билет 1. 1

Билет 2. 3

Билет 3. 3

Билет 4. 3

Билет 5. 3

Билет 6. 12

Билет 7. 16

Билет 8. 16

Билет 9. 16

Билет 10. 18

Билет 11. 23

Билет 12. 25

Билет 13. 25

Билет 14. 28

 

Билет 1.

а) Предмет и модель статистической теории информации

б) Определение симметричного канала и вычисление его пропускной способности

 

а)Модель статистической теории информации.

 

Понятие информация тождественно понятию сведения и ассоциирует с наличием по крайней мере двух взаимодействующих систем А и В, одна из которых В является наблюдаемой системой (приемником), а вторая А — источником информации. Вне указанной схемы понятие информация теряет смысл.

Любая система описывается совокупностью физических величин, которые могут зависеть от параметров. Состояния системы — это значения физической величины или параметра, которые ее описывают. Если эти значения дискретны, то система называется дискретной, а если непрерывны, то система называется системой с непрерывным множеством состояний. Таким образом, в рамках прикладной теории информации, информация – это сведения о состоянии системы.

Система случайным образом с некоторой вероятностью может оказаться в том или другом состоянии (передатчик приходит в состояние, которое соответствует передаваемой букве). Следовательно, множество состояний системы можно рассматривать как множество случайных событий.

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

 

Предмет статистической теории информации.

Теорией информации называется наука, изучающая количественные закономерности, связанные с получением, передачей, обработкой и хранением информации.

б) Определение симметричного канала.

Пропускная способность канала – предельная скорость передачи информации, при которой может быть получена сколь угодно малая вероятность ошибки.

Канал называется симметричным, если он симметричен по входу и выходу. Для симметричного канала Н (У|Х)не зависит от распределения источника сообщений, поэтому пропускная способность

Канал называется симметричным по входу, если строки матрицы различаются только порядком расстановки некоторого множества чисел .

Для симметричных по входу каналов частная условная энтропия

Она не зависит от номера передаваемой буквы и может быть вычислена по любой строке матрицы. Поэтому условная энтропия

Канал называется симметричным по выходу, если столбцы матрицы различаются только порядком расстановки некоторого множества чисел .

Если распределение источника равномерное (), то распределение р (у_i)на выходе симметричного по выходу канала также будет равномерным. При этом энтропии H (X)и H (Y) достигают своего максимального значения( ).

Ценность информации

 

- Ценной информацией считается та информация, которая способ­ствует достижению поставленной цели.

 

Один из способов измерения ценности информации, сформулированный в рамках статистической теории информации, был предложен А.А.Харкевичем. Ценность информации может быть выражена через приращение вероятности достижения цели. Если значение априорной вероятности достижения цели обозначить через р₁, а апостериорной — через p₂, то ценность полученной информации можно определить как

log .

В системах передачи информации цель сводится к правильной передаче сообщений независимо от их конкретного содержания и формулируется относительно каждого символа множества X. Пусть целью является принятие решения в пользу x_i. Тогда относительно этой цели ценность сведений,содержащихся в принятом y_j равна log , где P(x_i) — априорная вероятность передачи х_i; p(x_i|y_j) — вероятность того, что было передано x_i после принятия y_j. При такой формулировке цели ценность информации совпадает с обычным количеством информации, которое определено выше.

Таким образом, количество информации, которое у_i несет об x_i, равно

.

Умножая числитель и знаменатель под логарифмом на р{у_j) и учитывая равенства

p(x_i|y_j)p(y_j)= p(x_i, y_j)= p(y_j |x_i)р(х_i),

получим

(3)

 

Отсюда следует, что y_j несет об такое же количество информации, какое х_i несет об y_j (свойство симметрии). Поэтому I(х_i, y_j) называется взаимным количеством информации между i-м символом множества X и j-м символом множества У. Взаимное количество информации I(х_i, y_j), может быть положительным , отрицательным и равным нулю . Отрицательная информация называется дезинформацией.

 

Свойства энтропии

Энтропия поскольку p_i удовлетворяет неравенству 0 1. Энтропия H(X)=0, когда система находится в одном из состояний с вероятностью, равной единице, и во всех остальных — с вероятностью, равной нулю. При этом имеется в виду, что p_ilog p_i=0.

При равномерном распределении (p_i= ) энтропия H(X)=logm_x

Докажем, что это максимальное значение энтропии. Используя равенство =1, можно выполнить следующие тождественные преобразования:

Н(Х)-logm_X=

Для оценки выражения log воспользуемся неравенством lnz z—1, положив z= .

 

 

 

Заменяя на , получим

где log e —модуль перехода. Отсюда

Пусть множество состоит из двух элементов, которые обозначим через единицу и ноль, причем единица появляется с вероятностью, равной р, а ноль — с вероятностью, равной q=1 — р. Тогда

.

Указанная зависимость изображена на рис. 1. Максимум достигается при p=q= 0,5.

Билет 6.
а) Энтропия и ее свойства
б) Дискретизация непрерывных сообщений. Теорема Котельникова. Пространство сигналов.

 

а)Энтропия и её свойства.

Энтропия равна количеству информации,

которое необходимо для определения состояния одного раз­ряда.

Величина является характеристикой источника сообщений и называется энтропией.

Из лабораторной 1:

Предельные возможности определяются энтропией. Если она

Энтропия:

p- вер-ть появления еденицы в массиве

Энтропия это количество информации которое приходится на один разряд.

Из лабораторной 2:

Проблема передачи непрер. сообщ-я закл. в получ. его копии на приемном пункте. Не сущ-ет способа, позвол-го получить точную копию перед-ого сообщ-я, поск. это требует бесконечной точности его воспроизв-я. Поэт. задают точность воспр-я перед-ого сообщ-я.

воспр-я перед-ого сообщ-я.

энтропия – это min кол-во инфы, кот. необх. передать по каналу, чт. восст. сообщение с заданной точностью

Свойства энтропии

Энтропия поскольку p_i удовлетворяет неравенству 0 1. Энтропия H(X)=0, когда система находится в одном из состояний с вероятностью, равной единице, и во всех остальных — с вероятностью, равной нулю. При этом имеется в виду, что p_ilog p_i=0.

При равномерном распределении (p_i= ) энтропия H(X) max и определяется как H(X)=logm_x

Докажем, что это максимальное значение энтропии. Используя равенство =1, можно выполнить следующие тождественные преобразования:

Н(Х)-logm_X=

Для оценки выражения log воспользуемся неравенством lnz z—1, положив z= .

 

 

 

 

Заменяя на , получим

где log e —модуль перехода. Отсюда

Пусть множество состоит из двух элементов, которые обозначим через единицу и ноль, причем единица появляется с вероятностью, равной р, а ноль — с вероятностью, равной q=1 — р. Тогда

.

Указанная зависимость изображена на рис. 1. Максимум достигается при p=q= 0,5.

 

 

б)Дискритизация непрерывных сообщений. Теорема Котельникова. Пространство сигналов.

Произвольную кусочно-непрерывную функцию , изображающую сообщение или сигнал, можно разложить в обобщенный ряд Фурье по полной системе ортонормированных функций:

,

если энергия функции конечна [9].

Бесконечная система действительных функций называется ортогональной на отрезке [ a, b ], если

при ,

а отдельная функция называется нормированной, если

.

При заданной системе функций и при фиксированном числе членов ряда n значения коэффициентов можно выбрать такими, при которых среднеквадратичная ошибка аппроксимации (аппроксимация - приближенное решение сложной функции с помощью более простых, что резко ускоряет и упрощает решение задач)

 

достигает минимума. Минимум среднеквадратичной ошибки достигается в том случае, когда коэффициенты ряда определяются по формуле

.

Ряд, с определяемыми таким образом коэффициентами, называется обобщенным рядом Фурье.

Ортогональная система называется полной, если путем увеличения количества членов в ряде среднеквадратичную ошибку можно сделать сколь угодно малой.

Таким образом, по счетному множеству коэффициентов можно с определенной точностью восстановить соответствующую функцию можно заменить передачей последовательности коэффициентов . Указанную последовательность можно интерпретировать как вектор в n - мерном Евклидовом пространстве с координатами , квадрат длины которого

.

Последнее равенство является обобщением теоремы Пифагора на случай n -мерного пространства. Путем непосредственных вычислений легко установить, что энергия сигнала

.

Таким образом, дискретизацией называется замена непрерывной функции последовательностью коэффициентов ... (вектором).

Выбор системы ортогональных функций определяется целью и физической сущностью решаемой задачи, а не чисто математическими умозаключениями.

С целью передачи сигнала по каналу связи широко применяется разложение функции в ряд Котельникова, которое позволяет существенно упростить определение коэффициентов .

Согласно теореме Котельникова произвольная функция с ограниченным спектром, может быть тождественно представлена счетным числом ее значений, взятых через интервал времени где F - верхняя граничная частота спектра сигнала. В этом случае функции

,

 

образующие систему ортогональных функций, отличаются друг от друга только сдвигом по оси времени t на величину кратную , при этом каждая из них достигает своего максимального значения в те моменты времени, когда значения всех остальных функций равны нулю. Коэффициенты разложения определяются по формуле

,

которую в результате тождественных преобразований можно привести к виду: , то есть коэффициент равен значению функции в момент, когда функция достигает своего максимального значения.

Если дискретизации подлежит нормальный (гауссов) случайный процесс, энергетический спектр которого имеет прямоугольную форму, то коэффициенты будут статистически независимыми случайными величинами, которые совпадают со значениями случайной функции , взятыми с шагом D t [9].

Таким образом, непрерывные сообщения можно передавать в цифровом виде, то есть в виде последовательности чисел, при этом каждое число приближенно выражает величину соответствующего коэффициента

 

Билет 7.
а) Взаимная информация и ее свойства
б) Адаптивная дискретизация непрерывных сообщений

1.Взаимная информация и её свойства.

Источник информации и приемник можно рассматривать как подсистемы одной сложной системы. Взаимную информацию между состояниями подсистем, можно записать в виде

. (4)

Поскольку сложная система случайным образом приходит в то или иное состояние, определяемое парой чисел (x_i,y_j), то I (xi,y_j) будет случайной величиной, которую можно усреднить по всему множеству состояний. В результате почленного усреднения (4) получим выражение для средней (полной) взаимной информации:

,

где I(y,x)=

 

С точки зрения информационного описания системы связи безразлично, какую из подсистем рассматривать в качестве передатчика, а какую в качестве приемника.

Поэтому энтропии Н (Х) и H (У) можно интерпретировать как информацию, которая поступает в канал связи, а условные энтропии H (X | Y), H (Y | X) как информацию, которая рассеивается в канале. В [1] доказано, что 1(Х, У)≥0.

При выполнении указанного неравенства из (5) следует, что

Условную энтропию можно представить в виде

где величина называется частной условной энтропией. Она характеризует неопределенность состояния системы А в случае, когда известно состояние y_j наблюдаемой системы В. Зафиксировав состояние y_j системы В, мы тем самым изменяем комплекс условий, при которых может реализоваться событие x_i. Это обнаруживается как изменение вероятности реализации события x_i (i = ) (имеет место статистическая зависимость). Если до изменения условий указанная вероятность была равна безусловной (полной) вероятности p (X_i), то после изменения условий она стала равной условной вероятности p (x_i | y_j). При отсутствии статистической зависимости H (X | y_j)= H (X), поскольку P (x_i | y_j)= p (x_i).

 

Таблица 1

X y	x1	x2	p (yj)
y1 y2	0.5 0.25	0.25	0.5 0.5
p (xi)	0.75	0.25

 

Таблица 2

X y	x1	x2
y1 y2	0.5	0.5

 

При наличии статистической зависимости энтропия H (X | y_j) может оказаться как меньше, так и больше Н (Х). Напомним, что для энтропии H (X | Y) всегда справедливо неравенство H (X | Y)≤ H (X).

В качестве примера вычислим энтропии Н (Х), H (X | Y), H (X | y_j) и взаимную информацию I (Х, У), когда системы А и В описываются двумерным распределением p (x_i, y_j), заданным в виде табл. 1.

Вычисленные значения условной вероятности записаны в табл.2.

Используя записанные в таблицах значения вероятностей, полу

чим

Отсюда

 

Билет.

Алгоритм Шеннона-Фано.

 

Пусть имеется множество сообщений .

1. Все сообщения располагаются в порядке убывания их вероятностей.

2. Упорядоченное множество сообщений делится на две части: верхнюю часть и нижнюю часть, причем так, чтобы разность между суммой вероятностей в верхней и нижней части была минимальной.

3. После этого сообщениям в верхней части ставится в соответствие 1, а в нижней – 0.

4. Далее аналогичные действия производятся с каждой из частей. Вновь полученные подмножества сообщений снова аналогичным образом делятся на две части и т.д., до получения по одному сообщению в каждом из подмножеств.

5. В результате каждому сообщению будет соответствовать своя последовательность из нулей и единиц, т.е. кодовое слово.

 

Пример:

Pi	X
0.5	x1
0.25	x2
0.125	x3
0.125	x4

 

 

Алгоритм Хаффмена.

 

1. Все сообщения располагаются в порядке убывания их вероятностей.

2. Два самых нижних сообщения объединяются в одно событие, вероятность которого равна сумме вероятностей, объединяемых событий, причем верхнему событию ставится в соответствие 1, а нижнему 0.

3. Получился новый массив сообщений с количеством состояний на единицу меньшим по сравнению с предыдущим массивом, если два последних события считать одним более крупным событием. Далее преобразуем этот массив в соответствии с пунктами 1 и 2. Полученный массив вновь подвергаем указанным преобразованиям и т.д. до тех пор, пока не будет исчерпан весь массив.

4. Геометрически результат можно представить в виде дерева, где кодовое слово, соответствующее выражается последовательностью дерева с соответствующим сообщением .

 

Пример:

 

x1=1, x2 = 01, x3 = 001, x4 = 000

 

 

б)Эпсилон-Энтропия. Производительность источника с непрерывным множеством состояний.

ЭПСИЛОН - ЭНТРОПИЯ

Проблема передачи непрерывного сообщения заключается в получении его копии на приемном пункте и, в сущности, сводится к процедуре воспроизведения сообщения на основе полученной информации. Очевидно, в данном случае не существует способа, позволяющего получить точную копию передаваемого сообщения, поскольку это требует бесконечной точности его воспроизведения, причем неограниченное увеличение точности требует неограниченного увеличения количества передаваемой информации. Например, нельзя получить два абсолютно совпадающих графика. Поэтому о передаче непрерывного сообщения имеет смысл говорить только в том случае, когда задана точность его воспроизведения.

Передача непрерывного сообщения сводится к передаче последовательности его значений взятых в дискретные моменты времени. Все возможные значения функции в некоторый момент времени образуют множество .

Пусть случайная величина имеет равномерное на отрезке распределение. Тогда распределение дискретной случайной величины также будет равномерным, если все интервалы на которые разбит отрезок , имеют одну и ту же длину. При таком разбиении энтропии достигает своего максимального значения, равного , где - число элементов в множестве .

Количество взаимной информации между множествами и , определяемое равенством

,

равно энтропии , поскольку неопределенность , с которой значение случайной величины определяет значение случайной величины , равна нулю. Поэтому для воспроизведения значения случайной величины с точностью требуется количество информации, равное .

Пронумеруем все элементы множества числами от 1 до и запишем их в - ичной системе счисления. Минимальное количество разрядов , некоторое при этом потребуется, удовлетворяет неравенству:

.

Если величина окажется целым числом, то количество информации, необходимое для воспроизведения значения случайной величины с заданной точностью, непосредственно равно в - ичных единицах количеству символов (разрядов), передаваемых по каналу связи. Повышение точности требуют уменьшения длины интервала , а, следовательно, и увеличения количества передаваемой информации.

Более универсальной мерой точности воспроизведения по сравнению с является среднеквадратичная ошибка

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

Таким образом, количество информации, которое требуется для воспроизведения значения случайной величины с заданной точностью (с заданной среднеквадратичной ошибкой), зависит от выбранной меры точности и от характера статистической зависимости между множествами и (от преобразования случайной величины в случайную величину ), в частности, от того, каким образом выбраны длины интервалов и их количество. Канал, устанавливающий связь между множествами и , описывается условной вероятностью и, в сущности, представляет собой устройство квантования.

Определим e - энтропию как минимальное по количество информации, необходимое для воспроизведения значения случайной величины с заданной точностью при заданном распределении источника:

Следует напомнить, что пропускная способность канала была определена как максимальное количество взаимной информации, но не по , а по распределению источника при заданной статистической связи между множествами и (при заданном распределении .

При квантовании непрерывной величины указанная e - энтропия равна энтропии . Поскольку , то передача информации в виде чисел, записанных в - ичной системе счисления и имеющих число разрядов, равное , не будет экономной. Поэтому целесообразно предварительно осуществить экономное кодирование сообщений, в роли которых должны выступать элементы множества .

Отметим, что e - энтропия также используется и в качестве количественной меры производительности источника непрерывных сообщений, при этом, очевидно, нельзя говорить о производительности источника не задав точность воспроизведения.

Таким образом, производительность источника можно определить как минимальное количество информации , необходимое в единицу времени для воспроизведения непрерывного сообщения c заданной точностью, где n - число отсчетов сообщения , передаваемых за единицу времени.

Кроме квантования существует много других способов преобразования непрерывной величины . В частности, множество может представлять собой результаты измерений величины . Пусть непрерывная величина с некоторой погрешностью h воспроизводит нормально распределенную случайную величину : . Тогда при заданной дисперсии погрешности (при заданной среднеквадратичной ошибке) e - энтропия нормальной величины равна [ 8 ]

,

где - дисперсия случайной величины .

 

Билет 11.
а) Предельные возможности эффективного кодирования
б) Пропускная способность гауссова

Билет

(сделала 2 варианта первого вопроса – по лекциям Ломакина и по методичке)

Билет 14.

1. Определение скорости передачи информации и пропускной способности канала.

Пропускная способность канала – предельная скорость передачи информации, при которой может быть получена сколь угодно малая вероятность ошибки.

Для общего описания канала связи и построения теории информации используется одна и та же модель. Канал называется дискретным (непрерывным), если множества X и У дискретны (непрерывны), и полунепрерывным, если одно из множеств дискретно, а другое непрерывно. Ниже рассматриваются только дискретные каналы.

Канал полностью описывается условными вероятностями того, что k -мпринятым символом будет j -й символ множества Y ().

Указанную вероятность можно рассматривать как функцию y_jk и , вид которой отражает состояние канала, в частности, характер взаимодействия помехи и сигнала. Если , (, ) то соответствующий канал называется каналом без памяти. Если вероятность не зависит от к (от времени), то соответствующий канал называется стационарным. Ограничимся рассмотрением только стационарных каналов без памяти.

Определим скорость передачи информации как предел: где средняя взаимная информация между переданным и принятым . В случае отсутствия помех Н (Х|Y)=0, следовательно, R = Н (Х). Этот предел в случае канала без памяти равен взаимной информации: R=I(X, Y)=Н(Х)-Н(Х|Y)=Н(Y)-Н(Y|Х).

Скорость передачи информации — скорость передачи данных, выраженная в количестве бит, символов или блоков, передаваемых за единицу времени.

Скорость передачи информации R полностью определяется вероятностями р (х_i)и р (y_j | x_i) (). Поэтому изменять величину R мы можем только за счет изменения вида распре­деления р (х_i), поскольку р (y_j | x_i)- характеристика неуправляемого канала. Определим пропускную способность канала С как максимальную по р (х_i)скорость передачи информации:

В случае отсутствия помех

Билеты по Теории Информации

Оглавление

Билет 1. 1

Билет 2. 3

Билет 3. 3

Билет 4. 3

Билет 5. 3

Билет 6. 12

Билет 7. 16

Билет 8. 16

Билет 9. 16

Билет 10. 18

Билет 11. 23

Билет 12. 25

Билет 13. 25

Билет 14. 28

 

Билет 1.

а) Предмет и модель статистической теории информации

б) Определение симметричного канала и вычисление его пропускной способности

 

а)Модель статистической теории информации.

 

Понятие информация тождественно понятию сведения и ассоциирует с наличием по крайней мере двух взаимодействующих систем А и В, одна из которых В является наблюдаемой системой (приемником), а вторая А — источником информации. Вне указанной схемы понятие информация теряет смысл.

Любая система описывается совокупностью физических величин, которые могут зависеть от параметров. Состояния системы — это значения физической величины или параметра, которые ее описывают. Если эти значения дискретны, то система называется дискретной, а если непрерывны, то система называется системой с непрерывным множеством состояний. Таким образом, в рамках прикладной теории информации, информация – это сведения о состоянии системы.

Система случайным образом с некоторой вероятностью может оказаться в том или другом состоянии (передатчик приходит в состояние, которое соответствует передаваемой букве). Следовательно, множество состояний системы можно рассматривать как множество случайных событий.

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

 

Предмет статистической теории информации.

Теорией информации называется наука, изучающая количественные закономерности, связанные с получением, передачей, обработкой и хранением информации.

б) Определение симметричного канала.

Пропускная способность канала – предельная скорость передачи информации, при которой может быть получена сколь угодно малая вероятность ошибки.