1

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования Российской Федерации

Таганрогский государственный радиотехнический университет

Сборник примеров и задач

по теории информации

Руководство для практических занятий на базе Mathcad 6.0 Plus

С.В. Кавчук

Таганрог 2002

УДК

С.В. Кавчук. Сборник примеров и задач по теории информации. Руководство для практических занятий на базе Mathcad 6.0 Plus. Таганрог: Изд-во ТРТУ, 2002. 64 с.

Рассмотрены основные понятия и расчетные соотношения теории информации для практических занятий по темам: оценка энтропийных характеристик, оценка количества информации, оценка информационных характеристик систем и эффективное кодирование. Приводятся примеры решения типовых задач с использованием программного обеспечения Matchad 6.0 Plus. Дается набор типовых задач с ответами.

Руководство предназначено для улучшения качества изучения курса “Теоретические основы информационно-измерительной техники” и других дисциплин, содержащих разделы теории информации.

Табл. 1. Ил. 13. Библиогр.: 13 назв.

Рецензент С.В. Николаев, канд. техн. наук, доцент кафедры АСНИиЭ ТРТУ.

ОГЛАВЛЕНИЕ

1. ОЦЕНКА ЭНТРОПИЙНЫХ ХАРАКТЕРИСТИК

1.1 Основные сведения

1.1.1 Дискретные случайные величины

1.1.2 Непрерывные случайные величины

1.2 Типовые примеры

1.3 Типовые задачи

2. ОЦЕНКА КОЛИЧЕСТВА ИНФОРМАЦИИ

2.1 Основные сведения

2.2 Типовые примеры

2.3 Типовые задачи

3. ОЦЕНКА ИНФОРМАЦИОННЫХ ХАРАКТЕРИСТИК СИСТЕМ

3.1 Основные сведения

3.2 Типовые примеры

3.3 Типовые задачи

4. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ

4.1 Основные сведения

4.2 Типовые примеры

4.3 Типовые задачи

ЛИТЕРАТУРА

1.  ОЦЕНКА ЭНТРОПИЙНЫХ ХАРАКТЕРИСТИК

1.1 Основные сведения

1.1.1 Дискретные случайные величины

Вероятностная мера неопределенности Шеннона или энтропия дискретной случайной величины имеет вид

, (1.1)

где вероятность появления i-го значения x_i случайной величины X;

мера неопределенности i-го значения; знак минус понимается как наличие "беспорядка" для величины X.

Формулу (1.1) можно записать в компактном виде

H(X) = M[-log₂P(x)],

где log₂P(x) дискретная случайная величина, для которой i-е значение log₂P(x_i) имеет вероятность P(x_i).

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

Тогда

, (1.2)

где мера Хартли.

В этом случае статистическая мера Шеннона совпадает с комбинаторной мерой Хартли.

Энтропия системы дискретных случайных величин X и Y

, (1.3)

где вероятность совместного появления i-го и j-го значений случайных величин X и Y, или в форме математического ожидания

,

где log₂P(X,Y) случайная величина, принимающая значения согласно матрице совместного распределения, и для которой значение log₂P(x_i,y_j) имеет вероятность P(x_i,y_j).

Энтропия системы зависимых величин

или ,(1.4)

где H(X) безусловная энтропия величины Х;

H(Y) безусловная энтропия величины Y;

H(Y/X) условная энтропия величины Y относительно величины Х;

H(X/Y) условная энтропия величины X относительно Y.

Для независимых величин

 и .

Условная энтропия X относительно Y

,(1.5)

где P(x_i/y_j) вероятность значения x_i величины X при условии, что величина Y приняла значение y_j (условная вероятность).

Условная энтропия величины X относительно значения y_j величины Y

.(1.6)

Условная энтропия Y относительно X

.(1.7)

1.1.2 Непрерывные случайные величины

Энтропия непрерывной случайной величины

, (1.8)

где p(x) плотность вероятности случайной величины X; шаг ее квантования, определяющий точность перехода от непрерывной величины к дискретной.

При x=1 имеем дифференциальную или относительную энтропию

. (1.9)

Энтропия системы непрерывных случайных величин X и Y

, (1.10)

где p(x,y) совместная (безусловная) плотность вероятности двух случайных величин X и Y.

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

, (1.11)

Условная дифференциальная энтропия X относительно Y

, (1.12)

где p(x/y) условная плотность вероятности.

Условная дифференциальная энтропия величины X относительно значения y величины Y

.(1.13)

1.2 Типовые примеры

Пример 1.2.1

Имеются три дискретных источника информации X(x1,x2), Y(y1,y2,y3) и Z(z1,z2). Вероятности появления сообщений P(xi), P(yi) и P(zi) каждого источника заданы при , и (задание начальных значений индексов) векторами

, и .

Требуется определить, какой источник обладает большей неопределенностью.

Решение. Сначала определим единицы измерения количества энтропии:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

На основании (1.1) энтропии источников:

первого

и составит ;

второго

и составит ;

третьего

и составит

Таким образом, в случае равновероятных сообщений большей неопределенностью обладает троичный источник Y. При этом неопределенность может быть подсчитана так же как мера Хартли, равная logN, где N число равновероятных сообщений. Сравнение двоичных источников X и Z показывает, что большей неопределенностью обладает источник с равновероятными сообщениями.

Пример 1.2.2

Число символов алфавита источника ( или ). Вероятности появления символов источника , , и .

Между соседними символами имеются корреляционные связи, которые описываются при матрицей условных вероятностей P(xi/xj)= следующего вида

,

например

Требуется определить энтропию источника.

Решение. Сначала определим единицы измерения количества энтропии:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

Ввиду зависимости между символами неопределенность источника характеризуется условной энтропией H(X/X). С учетом корреляционной связи и соотношения

на основании (1.5) условная энтропия

,

Пример 1.2.3. Ансамбли событий X и Y объединены, причем вероятности совместных событий определяются матрицей P_XY совместных вероятностей P(X,Y) при :

;

Требуется определить:

а) энтропии ансамблей X и Y;

б) энтропию объединенного ансамбля;

в) условные энтропии ансамблей.

Решение. Предварительно определим единицы измерения количества энтропии:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

Найдем безусловные вероятности P(xi) и P(yj) при и :

; ;

; .

На основании (1.1) вычислим энтропии ансамблей:

; ;

; .

На основании (1.3) энтропия объединенного ансамбля

; .

Так как согласно (1.4), энтропия объединения

H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y),

то условные энтропии будут

; .

; .

Пример 1.2.4

По линии связи передаются непрерывные амплитудно-модулированные сигналы x(t), распределенные по нормальному закону с нулевым средним значением и среднеквадратичными отклонениями .

Определить энтропию сигнала при точности его измерения .

Решение. Предварительно определим единицы измерения количества энтропии:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

По условию задачи плотность вероятности сигнала

.

На основании (1.8) энтропия непрерывного сигнала

;

Итак, энтропия сигнала

;

Пример 1.2.5

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

; .

Максимальное значение воздействия составляет . Сигнал дискретизирован по времени с шагом и имеет длительность .Определить энтропию сигнала.

Решение. Предварительно определим единицы измерения количества информации:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

График плотности вероятности в виде ступенчатой функции, соответствующей шагу квантования, приведен на рис.1.2.1 при и .



Рис. 1.2.1

Определим вероятности появления уровней сигнала

;

по приближенной формуле

;

Согласно (1.1), энтропия или средняя неопределенность одного дискретного значения задающего воздействия

; .

Сигнал состоит из отсчетов задающего воздействия. На основании свойства аддитивности энтропии окончательно имеем энтропию сигнала в целом

; .

Пример 1.2.6

Случайная погрешность измерительной системы, состоящей из двух устройств, является суммой двух независимых случайных погрешностей ?1 и ?2 отдельных ее устройств. Погрешности имеют с параметрами и равномерные законы распределения (рис. 1.2.2 при , и ) с плотностями вероятности соответственно

и .

Рис. 1.2.2

Найти дифференциальную энтропию суммарной погрешности

Решение. Предварительно определим единицу измерения энтропии как . При этом один .

Из теории вероятностей известно, что плотность вероятности p(z) суммы двух независимых случайных величин Z=X+Y определяется как свертка плотностей распределения p1(x) и p2(y) слагаемых, т.е.

p(z)= =.

В этом случае закон распределения суммы p(z) называется композицией законов распределения слагаемых p1(x) и p2(y).

Таким образом, для решения задачи необходимо найти композицию двух равномерных законов распределения p1(?1) и p2(?2), т.е. свертку

.

Для ограниченных законов распределения при сдвиге плотности вероятности p2(?2) на величину произведение под знаком интеграла отлично от нуля, когда функции p1(?1) и p2(?2) перекрываются, т.е. накладываются друг на друга. В нашем случае возможны три ситуации.

1) Пусть и функция p2 полностью накладывается на p1 (рис.1.2.3).

Рис. 1.2.3

В этом случае интервал изменения суммарной погрешности будет

.

2) Пусть и функция p2 частично и справа накладывается на p1 (рис.1.2.4).

Рис. 1.2.4

Во втором случае интервал изменения суммарной погрешности будет

.

3) Пусть и функция p2 частично и слева накладывается на p1 (рис. 1.2.5).

Рис. 1.2.5

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

В результате интеграл свертки принимает вид

или после взятия интегралов

График плотности вероятности суммарной погрешности 2 как композиция законов распределения слагаемых 1 и 2 показан на рис. 1.2.6 при:

,

Рис. 1.2.6

Для определения на основании (1.8) и (1.9) дифференциальной энтропии суммарной погрешности нужно из-за кусочной непрерывности функции p вычислить три интеграла.

Первый интеграл

Второй интеграл

.

Третий интеграл

.

В конечном итоге дифференциальная энтропия суммарной погрешности при шаге квантования будет

или после преобразований в окончательной форме

; .

Пример 1.2.7

Случайный сигнал U(t) на выходе аналогового датчика ограничен по мощности при среднеквадратическом отклонении значением .

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

Решение. Средняя мощность стационарного случайного процесса определяет дисперсию случайной величины U в сечении процесса для момента времени t, т.е. . Таким образом, среди всех законов распределения p(u) непрерывной случайной величины U с одной и той же дисперсией D нужно найти закон распределения, максимизирующий, согласно (1.8), интеграл вида

Согласно теореме вариационного исчисления для нахождения функции y=y(x), дающей экстремум интеграла



при дополнительных условиях

(s=1,2,...,m),

необходимо решить (не дифференциальное) уравнение Эйлера

,

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

В данном примере нужно найти максимум интеграла

при дополнительных условиях

и ,

где m₁ - математическое ожидание.

Отсюда (пусть для начальной определенности , , , ) следует функционал

.

Следовательно, уравнение для определения p(x) будет иметь вид

или после дифференцирования

.

Решение уравнения в символическом виде будет

.

Таким образом, если положить , то плотность вероятности можно записать в виде

.

Из дополнительных условий находим два уравнения для определения постоянных i. Для первого условия имеем

.

Это дает первое уравнение

или .

Для второго условия

.

Отсюда имеем второе уравнение

.

Подставляя сюда величину c из первого уравнения и решая второе уравнение в символическом виде с помощью функции Find(x), получим

; .

Следовательно, постоянные будут

и .

В конечном итоге плотность вероятности, максимизирующая интеграл в формуле (1.8), принимает вид

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

1.3 Типовые задачи

Задача 1.3.1

Имеются три дискретных источника информации X(x1,x2,x3), Y(y1,y2) и Z(z1,z2). Вероятности появления их сообщений P(xi), P(yi) и P(zi) заданы при векторами

, и .

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

Ответ. Средняя неопределенность источников:

; ; .

Связь между энтропиями источников определяется выражением

.

Задача 1.3.2

Предварительно определим единицу измерения энтропии как . При этом один . Элементы алфавитов X и Y статистически связаны. Известно, что энтропии и . В каких пределах меняется условная энтропия H(Y/X) при изменении H(X/Y) в максимально возможных пределах.

Ответ. Условная энтропия H(Y/X) меняется в пределах от 4 до 12 бит.

Задача 1.3.3

Предварительно определим единицу измерения энтропии как . При этом один . Дискретный источник информации X имеет энтропию , а источник Y энтропию . Найти условную энтропию H(X/Y), если условная энтропия H(Y/X)=.

Ответ. Условная энтропия .

Задача 1.3.4

Дана при , и матрица совместных вероятностей

,

например элемент (2,2) матрицы

Определить энтропии H(X), H(Y), H(X/Y), H(Y/X), H(X/y1), H(Y/x2), H(X,Y).

Ответ

; ; ;

; ;

; .

Задача 1.3.5

Случайный сигнал имеет с параметрами , , плотность вероятности

,

и квантуется по уровню с шагом квантования (рис.1.3.1, где pkv(x) плотность вероятности квантованного сигнала).

Рис. 1.3.1

Найти энтропию квантованного сигнала, если условные вероятности уровней заданы при матрицей

,

Ответ. Для указанного на рис.1.2.2 способа квантования матрица безусловных вероятностей уровней будет

При этом энтропия квантованного сигнала .

Задача 1.3.6. Аналоговый сигнал U(t) на выходе датчика имеет постоянную составляющую и ограничен по мощности при параметре значением . Выходной сигнал носит случайный характер и распределен по нормальному закону распределения.

Определить дифференциальную энтропию выходного сигнала.

Ответ. При шаге квантования дифференциальная энтропия

и составляет .

Задача 1.3.7

Найти условные дифференциальные энтропии H_д(X/Y) и H_д(Y/X) для суммы нормальных и зависимых случайных величин X и Y, если их среднеквадратические отклонения , и коэффициент корреляции .

Ответ. При условные дифференциальные энтропии

, ;

, .

Задача 1.3.8

Аналоговый сигнал u(t) на выходе непрерывного источника ограничен по уровню значениями U1 и U2. Найти дифференциальный закон распределения, обеспечивающий максимальную относительную энтропию.

Ответ. Равномерное на интервале [U1, U2] распределение.

Задача 1.3.9

Аналоговый сигнал u(t) на выходе датчика принимает только положительные значения, т.е. его плотность вероятности p(u)=0 при u<0. Среднее значение сигнала неизменно (математическое ожидание ).

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

Ответ. Экспоненциальное распределение с плотностью вероятности

.

Задача 1.3.10

Определим единицу времени: одна миллисекунда как . Измерительное устройство вырабатывает временные интервалы, распределенные случайным образом с равной вероятностью в пределах от до . Как изменится энтропия случайной величины при изменении точности измерения . до 1 mks.

Ответ. Энтропия увеличится на величину .

Задача 1.3.11

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

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

Ответ. Энтропия сигнала

; .

Задача 1.3.12. Определить, при каком соотношении между шагами квантования н и р квантованные энтропии погрешностей X и Y, распределенных по нормальному и равномерному законам распределения, равны.

Ответ

,

где н и р среднеквадратические отклонения нормального и равномерного распределений.

Задача 1.3.13

Две независимых случайных погрешности ₁ и ₂ распределяются с равной вероятностью на интервале [-m, m], где .

Найти дифференциальную энтропию суммарной погрешности

Ответ. При шаге квантования дифференциальная энтропия

; .

Задача 1.3.14

Система измерения дальности имеет две независимых составляющих случайной погрешности измерения. Определим единицу длины один метр как . Первая случайная погрешность ?₁ имеет при параметре распределение Симпсона с плотностью вероятности

Вторая случайная погрешность ?₂ равномерно распределена на интервале [0, h/2] с плотностью вероятности

.

Найти неопределенность результата измерения в среднем на одно измерение.

Ответ. Плотность вероятности суммарной погрешности

Средняя неопределенность результата измерения определяется дифференциальной энтропией суммарной погрешности при шаге квантования

; .

Задача 1.3.15

Измерительное устройство имеет случайную погрешность измерения, распределенную при параметрах и по закону Коши с плотностью вероятности

.

Найти среднюю неопределенность результата измерения.

Ответ. При.шаге квантования дифференциальная энтропия

; .

Задача 1.3.16

Найти среднюю неопределенность результата измерения координаты точки (x,y), если случайная погрешность системы для определения координат имеет при среднеквадратических отклонениях , и коэффициенте корреляции нормальное распределение с плотностью вероятности

Ответ. Средняя неопределенность результата измерения определяется дифференциальной энтропией HдXY погрешности. При шагах квантования и дифференциальная энтропия погрешности

;

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

.

Задача 1.3.17. Измерительное устройство имеет случайную погрешность измерения, распределенную при параметрах и по экспоненциальному закону с плотностью вероятности

Найти среднюю неопределенность результата измерения.

Ответ. Средняя неопределенность результата измерения определяется дифференциальной энтропией погрешности Hд?, которая при.шаге квантования будет

; .

2. ОЦЕНКА КОЛИЧЕСТВА ИНФОРМАЦИИ

2.1 Основные сведения

В общем случае количество информации I, получаемое в результате эксперимента, определяется как мера уменьшения неопределенности, а именно

I=H-H₀, (2.1)

где H - неопределенность (энтропия) до проведения эксперимента; H₀ -неопределенность после проведения эксперимента (остаточная).

Для дискретных случайных величин различают 4 вида информации.

1. Полная информация I(X) о величине X при непосредственном ее наблюдении

I(X) = H(X) = M[-log₂P(X)] 0. (2.2)

Это средняя информация, получаемая от всех возможных значений X в расчете на одно значение.

2. Полное количество информации I(YX) о величине X, содержащееся в величине Y,

I(YX) = H(X)-H(X/Y); (2.3)

I(YX) = I(XY) = I(YX)0,

где I(YX) полная взаимная информация, содержащаяся в X и Y,

. (2.4)

3. Частная информация I(y_iX)0 о величине X, содержащаяся в значении y_i величины Y,

(2.5)

или, учитывая равенство

,

. (2.6)

4. Частная информация I(y_j x_i) о значении x_i величины X, содержащаяся в значении y_j величины Y,

,

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

_. (2.7)

Виды информации для непрерывных случайных величин:

частная взаимная информация двух значений x и y

;(2.8)

частная информация о величине X, содержащаяся в значении y величины Y,

; (2.9)

полная взаимная информация, содержащаяся в X и Y,

. (2.10)

2.1 Типовые примеры

Пример 2.2.1

По двоичному симметричному каналу связи с помехами передаются два сигнала x1 и x2 с априорными вероятностями P(x1)=3/4 и P(x2)=1/4. Из-за наличия помех вероятность правильного приема каждого из сигналов уменьшается до 7/8. Требуется определить:

1) полную информацию I(X) на выходе источника сигналов;

2) взаимную частную информацию I(y2,x2) двух случайных сигналов на выходе и входе канала связи относительно друг друга (т.е. количество информации о сигнале x2 источника в сообщении y2 приемника);

3) условную частную информацию I(x2/y2), содержащуюся в сообщении x2 источника при условии приема сообщения y2;

4) среднее количество информации I(y2,X) в принятом сообщении y2 относительно всех передаваемых сообщений X(x1,x2);

5) среднее количество взаимной информации I(Y,X) в сообщениях Y приемника о сообщениях X источника;

Решение. По условию:

а) безусловные вероятности P(xi)=Pxi сообщений x1 и x2:

; .

б) условные вероятности P(yj/xi)= приема сообщений y1, y2 при условии передачи сообщений x1, x2:

; ; ; .

Вычислим вероятности P(yj)=Pyj , P(xi, yj)=Pxyi,j и P(xi/yj)= при и , необходимые для расчета информационных характеристик:

; ;

задание начального значения индексов;

; .

Итак,

; ;

; .

Так как

или ,

то имеем следующие условные вероятности

, т.е.

; ; ;

Определим единицы измерения количества информации:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

В случае дискретного источника полное количество информации на его выходе в расчете на одно сообщение, согласно (2.2), совпадает с энтропией источника (1.1) и будет

; или .

Согласно (2.7), взаимная частная информация I(y2,x2) двух сигналов

или ;

; .

Условная частная информация I(x2/y2)

; .

Согласно (2.5), среднее количество информации I(yj,X) в принятом сообщении yj относительно всех передаваемых сообщений X

; ;

; .

Согласно (2.4), среднее количество взаимной информации I(Y,X) в сообщениях Y приемника относительно всех передаваемых сообщений X

; .

Рассмотрим второй способ определения I(Y,X). Найдем, согласно (1.5), условную энтропию источника при условии снятия неопределенности приемника

; .

Тогда на основании (2.3) с учетом I(X)=H(X) среднее количество взаимной информации I(Y,X) в расчете на одно сообщение

; .

Пример 2.2.2

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

Решение. Предварительно определим единицы измерения количества информации:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

На входе канала имеется шесть () комбинаций x1, x2, x3, x4, x5, x6. На выходе канала при правильной передаче им однозначно соответствуют также шесть () комбинаций y1x1, y2x2, y3x3, y4x4, y5x5, y6x6 . Передаваемая комбинация xi может под влиянием помех трансформироваться (перейти) в любую из комбинаций yj с вероятностью и принята правильно с вероятностью . Вероятность ошибки, например, комбинации x1

Pош(x1)= P(y2/x1)+P(y3/x1)+P(y4/x1)+P(y5/x1)+P(y6/x1)=p0=0.4,

где P(yj/xi), условная вероятность приема комбинации yj при условии передачи комбинации xi. Так как комбинация может перейти в любую другую с равной вероятностью, то

P(yj/xi)=p0 / (N-1)=0.08 , и P(yi/xi)=pп=0.6 при j=i .

Следовательно, данный канал передачи информации характеризуется канальной матрицей условных вероятностей P(yj/xi)=,

.

Количество информации в среднем на одну переданную комбинацию

I(X,Y)=H(Y)-H(Y/X),

где H(Y) энтропия принимаемой комбинации; H(Y/X) условная энтропия, т.е. энтропия принимаемой комбинации при условии, что известна передаваемая комбинация.

Так как комбинации передаются и принимаются с равной вероятностью, то вероятность передачи i-й и приема j-й комбинации

; ; ; .

Согласно (1.1), энтропия принимаемой комбинации

; .

Согласно (1.7) с учетом P(xi,yj)=P(xi)P(yj/xi) условная энтропия принимаемой комбинации при известной передаваемой

; .

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

; .

Пример 2.2.3

Радиостанция противника может работать на волне ?1 (событие A1) или на волне ?2 (событие A2), причем в импульсном режиме (событие B1) или непрерывном режиме (событие B2). Вероятности совместных событий имеют следующие значения:

; ; ; .

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

Решение. Предварительно определим единицы измерения количества информации:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

Вычислим безусловные вероятности P(Ai) и P(Bj) при , и :

; ;

; ;

Вычислим условные вероятности P(B/A):

; ;

Элементы матрицы:

; ;

; .

Согласно (2.3), количество информации о режиме работы станции, которое содержится в сообщении о длине ее волны,

I(A,B)=H(B)-H(B/A).

На основании (2.4) можно записать

; .

Пример 2.2.4. На вход регистрирующего устройства поступает случайный сигнал Y(t)= X(t)+?(t), где полезный сигнал X(t) и помеха ?(t) независимые случайные процессы с нулевым средним значением и среднеквадратичными отклонениями и .

Требуется определить:

а) количество информации I(y,x), которое содержится в зарегистрированной реализации y(t) сигнала Y(t) о реализации x(t) полезного сигнала X(t);

б) полную среднюю взаимную информацию I(Y,X), получаемую при регистрации процесса Y(t) о полезном процессе X(t).

Решение. Предварительно определим единицы измерения количества информации:

при натуральном логарифме (нит) ;

при двоичном логарифме (бит) .

По условию задачи:

1) плотность вероятности нормального полезного сигнала

;

2) плотность вероятности нормальной помехи

.

Сумма Y(t) двух нормальных процессов X(t) и ?(t) является также нормальным процессом. Так как X(t) и ?(t) независимы, то дисперсия суммарного случайного сигнала , а его среднеквадратичное отклонение . При этом закон распределения нормального случайного сигнала Y(t) будет

.

С другой стороны, композиция законов распределения суммы двух независимых величин определяется интегралом свертки их плотностей вероятности

, т.е.

;

результат интегрирования.

Совместная плотность вероятности независимых сигналов X(t) и ?(t)

, т.е.

.

Введем понятие условной плотности вероятности, например, p1(?/x) для случайной величины ? при заданной (известной) величине x

, где .

Для условной плотности вероятности должно выполняться условие нормировки

.

Рассмотрим условную плотность вероятности p2(y/x)=q2(y,x)/p1(x) для реализации y(t) при известной реализации x(t). В общем случае знание x(t) дает также некоторую информацию о реализации y(t). Условная плотность вероятности p2(y/x) содержит больше (по крайней мере, не меньше) сведений о y(t), чем безусловная плотность вероятности p3(y), так как

=

Насколько увеличивается информация о y(t) в результате того, что стала известной реализация x(t), зависит от конкретных условий. В нашем случае, когда y(t)=x(t)+(t), информация о y(t) вообще не прибавляется, какой бы ни оказалась реализация x(t). Другими словами, при известной величине "x" неопределенность (случайный характер) величины "y" полностью определяется случайной помехой. Это значит, что условная плотность вероятности p2(y/x) равна закону распределения помехи p2(?) при ?=y-x, т.е.

Из определения условной плотности вероятности следует совместная плотность вероятности сигналов Y(t) и X(t)

, т.е.

;

или после преобразований

.

Найдем на основании (2.8) или (2.7) при замене вероятностей P(yj/xi), P(yj) соответствующими плотностями вероятности p2(y/x), p3(y) количество информации I(y,x), которое содержится в зарегистрированной реализации y(t) сигнала Y(t) о реализации x(t) полезного сигнала X(t)

; .

После преобразований можно получить

.

Усреднение этого частного количества взаимной информации по множеству реализаций дает полную взаимную информацию I(Y,X)=M[I(y,x)], получаемую при регистрации процесса Y(t) о полезном процессе X(t). Здесь M знак математического ожидания.

Раскрывая знак математического ожидания, имеем

Интегрирование дает

;

.

Таким образом, полное количество информации в сигнале Y(t) о сигнале X(t) будет

и составляет .

Выполнив подстановку вместо , полученное выражение для I(Y,X) можно упростить

;

результат упрощения.

Следовательно, в окончательном виде полное количество информации будет

или .

информационный энтропийный программный кодирование

Пример 2.2.5

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

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

Решение. Предварительно определим единицы измерения количества энтропии и информации:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

По условию задачи плотность вероятности измеряемого напряжения

или в другой форме записи

.

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

Неопределенность величины напряжения до измерения определяется энтропией сигнала на входе вольтметра, а после измерения энтропией его погрешности (рис. 2.2.1) при

, .и ).

Рис. 2.2.1

На основании (1.8) энтропия H(U) непрерывного входного напряжения при шаге квантования

;

результат интегрирования.

Итак, энтропия сигнала

,

Полученное выражение для энтропии можно представить в другой форме

;

Так как

,

то в другой форме получим

.

Отсюда следует

, .

На основании (1.8) энтропия H(?) непрерывной величины погрешности при шаге квантования

.

В результате интегрирования получим

,

или после преобразований

, .

На основании (2.1) количество информации в среднем на одно измерение

;

или после преобразований

, .

2.3 Типовые задачи

Задача 2.3.1

В линию связи посылаются равновероятные и статистически независимые дискретные сигналы x1 и x2 (). Действие помех приводит к тому, что на выходе канала связи имеются сигналы z1, z2 и z3 () с матрицей условных вероятностей P(zi/xj)= при

, например,

Определить полную взаимную информацию I(X,Z)=IXZ.

Ответ. Матрица безусловных вероятностей выходного сигнала

Матрица совместных вероятностей входного и выходного сигналов

Полная взаимная информация .

Задача 2.3.2. Измеряемая величина X на интервале [] при с параметрами и

имеет усеченный нормальный закон распределения с плотностью вероятности (рис.2.3.1 при и )



Погрешность каждого результата измерения (например, ) при параметре имеет распределение Лапласа (двустороннее экспоненциальное) с плотностью вероятности (рис.2.3.1 при и )

Рис. 2.3.1

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

Ответ. Коэффициент

.

Количество информации

, .

Задача 2.3.4

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

Определить количество информации I(X,Y)=IXY о величине X, содержащееся в результатах измерения Y=X+Z.

Ответ. Количество получаемой информации о величине X при регистрации результата измерения Y=X+Z в среднем на одно измерение

;

Примечание. Среднее количество информации I(X,Y)=IXY определяется разностью энтропий результата измерения H(Y) и погрешности измерения H(Z) при условии нормального распределения величин Z и Y соответственно с дисперсиями и .

Задача 2.3.5

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

Определить среднее количество информации на один сигнал, передаваемое по каналу при наличии и отсутствии помех.

Ответ. Среднее в расчете на один сигнал количество информации, передаваемое по каналу при отсутствии помех,

; .

Среднее количество информации, передаваемое по каналу при наличии помех,

; .

Задача 2.3.6

Система передачи информации характеризуется при , и матрицей P(X,Y)=Pxy совместных вероятностей

.

Определить среднее количество взаимной информации I(X,Y)=IXY.

Ответ. Так как величины X и Y независимы, то взаимная информация I(X,Y)=0.

Задача 2.3.7

Измеряемая величина X имеет с параметрами и логарифмически нормальный закон распределения с плотностью вероятности (рис.2.3.2 при и )

.

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

.

Рис. 2.3.2

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

; .

Задача 2.3.8

Измеряемая величина напряжения U распределена с равной вероятностью в пределах от до ., т.е. имеет плотность вероятности (рис. 2.3.3 при и )

.

Измерительное устройство для каждого результата измерения (например, ) имеет случайную погрешность ??? распределенную при параметре по экспоненциальному закону с плотностью вероятности (рис.2.3.3 при и

)

.

Рис. 2.3.3

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

; .

Задача 2.3.9

Измеряемая величина X имеет с параметрами , , и логарифмически нормальный закон распределения с плотностью вероятности

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

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

; .

Задача 2.3.10

Радиолокационная станция РЛС противника может работать в метровом диапазоне d1 или в дециметровом диапазоне d2, а также в режиме обзора r1 или в режиме наведения r2. Совместные вероятности этих событий описываются при матрицей

.

Вычислить количество частной информации I(R,d_j)=, получаемой относительно режима R(r₁,r₂) работы РЛС, если система обнаружения сообщает диапазон d_j работы станции.

Ответ. Частная информация

;;.

Задача 2.3.11

Система передачи информации характеризуется при матрицей P(X,Y)=Pxy совместных вероятностей

Определить среднее количество взаимной информации I(X,Y)=IXY и количество частной информации I(X,yj)=, содержащейся в сообщении yj приемника об источнике X в целом.

Ответ. Количество полной и частной информации соответственно

 и

Задача 2.3.12

На координатной плоскости (X,Y) объект с равной вероятностью может находиться в любой точке (x,y) прямоугольной площади с центром в начале координат (рис.2.3.4, где p_xy(x,y) - плотность вероятности положения объекта). При этом координата X при параметре изменяется в пределах интервала [-hx,hx], а координата Y при параметре в пределах интервала [-hy,hy]. Система измерения координат независимо от их значений (например, и ) при среднеквадратических отклонениях , и коэффициенте корреляции имеет нормальное распределение погрешности ?(x,y) с плотностью вероятности (рис. 2.3.4)

.

Найти среднее количество информации, получаемое в результате измерений координат объекта.



Рис. 2.3.4

Ответ. Среднее количество информации при измерении координат объекта

;

3.  ОЦЕНКА ИНФОРМАЦИОННЫХ ХАРАКТЕРИСТИК СИСТЕМ

3.1 Основные сведения

Избыточность источника оценивается коэффициентом избыточности

. (3.1)

Производительность источника это количество информации в сообщении за одну секунду

, (3.2)

где средняя длительность одного сообщения; средняя скорость создания сообщения источником, .

Единица измерения производительности 1 бит/с.

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

, (3.3)

где средняя скорость передачи сообщения по каналу; средняя длительность сообщения в канале связи.

Важнейшая характеристика канала это пропускная способность. Она определяется как максимально возможная скорость передачи информации по каналу связи

[дв.ед./с] или [бит/c]. (3.4)

Пропускная способность дискретного канала без помех

[ бит/с].(3.5)

Пропускная способность двоичного симметричного канала связи c канальной матрицей

,

где p₀ вероятность ошибки, определяется выражением

.(3.6)

Согласно теореме Шеннона о кодировании для дискретного канала с помехами: если источник имеет энтропию H(X), а канал связи пропускную способность C, то сообщение источника всегда можно закодировать так, что скорость их передачи будет близка к величине

,(3.7)

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

Для непрерывного канала с помехами пропускная способность определяется выражением:

, (3.8)

Где;

энтропия помехи;

f_k граничная частота пропускания канала;

P_xk средняя мощность сигнала, допускаемая в канале;

средняя мощность помехи в канале;

отношение сигнал-помеха.

Максимальное количество информации, которое можно передать по каналу связи за время T_k,

. (3.9)

3.2 Типовые примеры

Пример 3.2.1

По двоичному симметричному каналу связи с помехами передаются два сигнала x1 и x2 с априорными вероятностями P(x1)=3/4 и P(x2)=1/4. Из-за наличия помех вероятность правильного приема каждого из сигналов уменьшается до 7/8. Длительность одного сигнала . Требуется определить:

1) производительность и избыточность источника;

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

Решение. Определим единицу измерения количества информации как или как и воспользуемся результатами решения примера 2.2.1, в котором получены:

условные вероятности P(y_j/x_i)= приема сообщений y₁, y₂ при условии передачи сообщений x₁, x₂

; ; ; .

количество информации на входе канала в расчете на одно сообщение или ;

среднее количество взаимной информации I(Y,X)=I_XY в расчете на одно сообщение

; .

Рассчитаем на их основе информационные характеристики источника и канала связи:

1) согласно (3.2), производительность источника

; .

2) согласно (3.1), избыточность источника при максимальном количестве его информации

;

3) согласно (3.3), скорость передачи информации

;

4) согласно (3.6), при вероятности ошибки или пропускная способность канала на сигнал

и составляет на один сигнал, а пропускная способность в единицу времени

;

Сравнение C и vIX показывает, что пропускная способность данного канала не обеспечивает передачи информации со сколь угодно малой вероятностью ошибки путем помехоустойчивого кодирования, поскольку vIX>C (согласно теореме Шеннона).

Пример 3.2.2

Число символов алфавита источника (или ). Вероятности появления символов источника , , и .

Между соседними символами имеются корреляционные связи, которые описываются при матрицей условных вероятностей

P(xi/xj)=:

,

например

Требуется определить избыточность источника R1 при статистической независимости символов и R2 при учете зависимости между символами.

Решение. Для оценки избыточности нужно найти безусловную энтропию H1(X) и условную энтропию H2(X/X) источника. Сначала определим единицы измерения количества энтропии:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

В случае не учета статистической связи на основании (1.1) для H1(X) имеем

;

С учетом корреляционной связи на основании (1.5) или (1.7)

; .

Максимально возможная энтропия источника с четырьмя символами определяется мерой Хартли

; .

Cледовательно,

;

;

Пример 3.2.3

По каналу связи передается ансамбль 3 сигналов xi, с длительностью и частотой следования . Источник сигналов имеет матрицу P(X)=Px безусловных вероятностей

;

Канал связи характеризуется при , , и матрицей условных вероятностей

P(yj/xi)=,

где yj, ансамбль сигналов на выходе канала (т.е. приемника),

;

Определить пропускную способность канала. Сравнить производительность источника и пропускную способность канала.

Решение. Предварительно определим единицы измерения количества энтропии:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

По условию задачи скорость vx создания сигналов и скорость vk их передачи по каналу равны, т.е. vx=vk. Эти скорости соответствуют частоте следования сигналов, т.е. и .

Согласно определению (3.5), пропускная способность

C = vkmax{I(Y,X)}=Fmax{I(Y,X)},

где максимум ищется по всем распределениям вероятностей P(X) и P(Y).

Найдем безусловные вероятности P(yi):

.

Следовательно,

;

;

.

Согласно (1.1), безусловная энтропия H(Y) выходного сигнала

;

На основании (1.7) с учетом P(xi,yj)=P(xi)P(yj/xi) условная энтропия H(Y/X) выходного сигнала Y относительно входного X

.

Раскрывая знак суммы при , имеем

.

Так как сумма вероятностей , то условная энтропия принимает вид

и не зависит от статистик входного и выходного сигналов. Она полностью определяется параметрами канальной матрицы.

Согласно (2.3), количество информации на выходе канала связи

I(X,Y)=H(Y)-H(Y/X)

будет максимально при максимуме энтропии приемника H(Y). Энтропия H(Y) максимальна в случае равной вероятности сигналов на выходе канала, т.е. когда при числе сигналов их вероятности ; ; ;

В этом случае энтропия выходных сигналов канала соответствует мере Хартли и равна lnN, т.е.

; .

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

I(X,Y)_max=H(Y)_max-H(Y/X), будет

.

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

и составляет .

Согласно (1.1), безусловная энтропия H(X) входного сигнала

; .

При этом, согласно (3.2) и (2.2), производительность vI(X) источника

и составляет .

Так как vI(X)>C, то канал связи нельзя использовать для передачи информации от данного источника.

Пример 3.2.4

Определить максимально возможную скорость передачи информации по радиотехническому каналу связи пункта управления с телеуправляемой ракетой, если полоса пропускания канала связи равна , а минимальное отношение сигнал/шум по мощности x = Px/P в процессе наведения ракеты на цель

Предварительно определим единицы измерения количества информации:

а) при натуральном логарифме (нит) ;

б) при двоичном логарифме (бит) .

На основании (3.8) пропускная способность данного непрерывного канала

и составляет .

3.3 Типовые задачи

Задача 3.3.1

Алфавит состоит из четырех букв x1, x2, x3 и x4. Вероятности появления символов P(xi) заданы вектор-столбцом

Между соседними символами имеются корреляционные связи, которые описываются при матрицей условных вероятностей

P(xi/xj)= следующего вида

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

Ответ. Избыточность источника при статистической независимости символов и при статистической зависимости символов .

Задача 3.3.2

Для передачи сообщений используется код, состоящий из трех символов, вероятности появления которых равны 0.8, 0.1 и 0.1. Корреляция между символами отсутствует. Определить избыточность кода.

Ответ. Избыточность кода R=0.42.

Задача 3.3.3

Измерительное устройство вырабатывает при среднеквадратическом отклонении и параметре случайный сигнал U(t) с нормальной плотностью вероятности и корреляционной функцией

.

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

Ответ. При шаге квантования избыточность сигнала

или

Задача 3.3.4

На вход канала связи поступает ансамбль сигналов {xi}, с длительностью и частотой следования . Сигнал x1 значительно отличается от других и всегда принимается правильно. Априорные вероятности P(xi) и вероятности переходов P(yj/xi), имеют при и параметрах ; и значения, указанные в соответствующих матрицах

;

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

Ответ. При введении коэффициента

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

;.

Производительность источника

; .

Задача 3.3.5

На вход канала связи поступает ансамбль сигналов {xi}, с длительностью и частотой следования . Априорные вероятности P(xi) и условные вероятности P(yj/xi), имеют при и вероятности ошибки значения, указанные в соответствующих матрицах

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

Ответ. Пропускная способность канала

;

Производительность источника

;

Задача 3.3.6

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



Ответ. Пропускная способность канала

;.

Задача 3.3.7

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

;.

Примечание. Изображение принимает вид белого шума, если все его элементы как в одном кадре, так и в различных кадрах независимы.

Задача 3.3.8

Определить пропускную способность симметричного канала с матрицей условных вероятностей

Ответ. Пропускная способность.

Задача 3.3.9

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

Ответ. При вероятности ошибки скорость передачи информации по каналу

;

.

Задача 3.3.10

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

Ответ. Время передачи сигнала

;

4. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ

4.1 Основные сведения

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

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

, (4.1)

где длительность двоичного символа; среднее число символов в сообщении; число кодовых символов для i-го сообщения x_i; p_i вероятность этого сообщения.

Источник будет согласован с двоичным каналом, когда . Отсюда следует

и . (4.2)

Код, обеспечивающий равенство (4.2), имеет наибольшую эффективность и соответственно наименьшую избыточность

(4.3)

Известны две методики построения эффективного кода: алгоритм Шеннона-Фано и алгоритм Хаффмена. Последний алгоритм обеспечивает однозначное построение кода.

Рассмотрим алгоритм Хаффмена. Составляется таблица. В таблице сообщения выписываются в основной столбец в порядке убывания их вероятностей. Два последних сообщения объединяются в одно вспомогательное. Ему приписывается суммарная вероятность. Вероятности снова располагаются в порядке их убывания в дополнительном столбце, где две последние объединяются. Процесс продолжается до получения вспомогательного столбца с вероятностью, равной единице.

Согласно этой таблице, строится кодовое дерево в виде графа. При движении из вершины дерева с P =1 ребрам графа присваиваются соответствующие вероятности и кодовые символы, например “1” при выходе из узла влево и “0”при выходе из узла вправо. Движение по кодовому дереву из вершины к сообщению, определяемому соответствующей вероятностью, дает кодовую комбинацию для сообщения.

4.2 Типовые примеры

Пример 4.2.1

Ансамбль сообщений xi , на выходе источника X имеет следующие вероятности их появлений, заданные при вектор-строкой , где, например, и

Произвести кодирование эффективным двоичным кодом по методу Шеннона-Хаффмена. Вычислить энтропию сообщений и среднюю длину nср кодового слова. Сравнить с минимально возможной длиной nср.min.

Решение. Предварительно определим единицы измерения количества энтропии и информации как и .

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

;

.

Две последних вероятности P1 объединяются в одну вспомогательную вероятность Ps1:

; ; ;

Вероятности снова располагаются в порядке их убывания в дополнительном столбце

;

Две последних вероятности P2 объединяются в одну вспомогательную вероятность Ps2:

; ; ;

Вероятности снова располагаются в порядке их убывания в дополнительном столбце

;

Две последних вероятности P3 объединяются в одну вспомогательную вероятность Ps3:

; ; ;

Вероятности снова располагаются в порядке их убывания в дополнительном столбце

;

Две последних вероятности P4 объединяются в одну вспомогательную вероятность Ps4:

; ; ;

Вероятности снова располагаются в порядке их убывания в дополнительном столбце

;

Две последних вероятности P5 объединяются в одну вспомогательную вероятность Ps5:

; ; ;

Вероятности снова располагаются в порядке их убывания в дополнительном столбце

...