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

а избыточность источника

,

где Hmax(X)=1.

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

б) Экстремальные свойства относительной энтропии

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

максимально.

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

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

Приведем несколько примеров.

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

.

Приведенные рассуждения не являются строгим доказательством последнего равенства. Строгое доказательство можно найти в литературе [8,10,11].

2. Если на случайную величину наложить следующие ограничения:

а) область возможных значений неограничена ;

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

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

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

.

 

Билет 10.
а) Сущность и методы эффективного кодирования

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

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

Билет 12.
а) Определение кол-ва информации по К. Шеннону
б) Префиксные коды. Неравенство Крафта

 

 

Билет 13.
а) Определение канала связи. Каналы с памятью и без памяти

Канал – совокупность технических средств между источником информации и потребителем информации.

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

Для общего описания канала связи и построения теории информации используется одна и та же модель. Канал называется дискретным (непрерывным), если множества 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 до n) так, что исправные будут помечаться 1, а не исправные 0, получим последовательность, которая будет описывать состояние системы. Всего таких состояний (последовательностей) будет 2ⁿ. Всё множество состояний S можно рассматривать как пространство элементарных событий , каждое из которых может наступить после эксплуатации системы в течение заданного времени с вероятностью, равной

, (1)

 

где p_j - вероятность отказа j -го блока; J - множество номеров исправных блоков, I – множество номеров не исправленных блоков. При этом предполагается, что отказ одного из блоков не влияет на вероятность отказа других блоков.

Возможна организация некоторой совокупности Z точек контроля, допустимое значение сигнала в каждой из которых обеспечивается определённым подмножеством блоков. В качестве исходной диагностической информации используется матрица проверок B_z, построенная на допустимом множестве точек контроля, где номер столбца совпадает с номером блока, а номер строки - с номером точки контроля. Проверка сигнала в каждой точке контроля позволяет судить о работоспособности всех блоков соответствующего подмножества, которое определяется совокупностью единиц в соответствующей строке матрицы проверок. Результат проверки принимается равным единице, если контролируемый сигнал вышел из допуска, и нулю в противном случае. Таким образом, при выходе из строя одного из блоков результат проверок совпадает с соответствующим столбцом матрицы. В случае выхода из строя нескольких блоков результаты проверок образуют вектор-столбец , равный логической поэлементной сумме соответствующих столбцов матрицы, где Y - множество всех возможных исходов диагностического эксперимента, под которым будем понимать измерение сигналов в точке контроля.

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

Разработку стратегии определения состояния системы будем вести с учётом следующих свойств этих подмножеств.

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

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

Свойство 3. Сумма всех состояний подмножества также принадлежит этому подмножеству.

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

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

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

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

 

Билет 14.
а) Определение скорости передачи информации и пропускной способности
б) Информационная мера глубины поиска дефекта