Кількість інформації згідно Р. Хартлі

Объединенная вероятностная схема

Імовірнісна схема

Вступ

Література.

Час – 2 год.

Навчальні питання

Лекція 3. Кількість інформації та ентропія

Задачі

Контрольні питання

Висновки

1. Які існують типи шифрів підстановки?

2. Які існують типи шифрів перестановки?

3. Наведіть приклад шифру Цезаря і його криптоаналіз.

4. Наведіть приклад шифру простої заміни.

5. Як можна здійснити криптоаналіз шифру простої заміни?

6. Наведіть приклад шифру Віженера.

7. У чому суть методу підрахунку числа збігів криптоаналізу шифру Віженера?

8. У чому суть методу Казіски криптоаналізу шифру Віженера?

9. Наведіть приклад шифру Вернама.

10. Наведіть приклад шифру Плейфера.

11. Наведіть приклад шифру перестановки.

Задача 1. Следующая криптограмма о президенте Кеннеди (Kennedy) получена с помощью простой замены. Определите открытый текст.

Задача 2. Дешифруйте следующий шифртекст, полученный при использований шифра Плэйфэра с ключом (как в разд. 2.3.2).

Задача 3. Зашифруйте следующий текст, с помощью шифра Виженера с ключом.

Задача 4. Рассмотрим криптограмму, полученную с помощью шифра Цезаря. Напишите программу в пакете "Mathematica" для поиска всех подстрок длины 5 в шифртексте, которые могли бы быть получены из слова. Проверьте эту программу на тексте из табл. 2.1. (См. также входную строку в примере 2.2).

1.... Імовірнісна схема. 1

2.... Кількість інформації згідно Р. Хартлі 3

3.... Кількість інформації за К. Шеноном.. 5

4.... Аксіоми Хінчина і Фадєєва. 7

1. Духин, Александр Александрович. Теория информации: Учебное пособие / А.А.Духин. - М.: Гелиос АРВ, 2007.

2. Стариченко Б. Е. Теоретические основы информатики: Учебное пособие для вузов. - 2-е изд. перераб. и доп. - М.: Горячая линия - Телеком, 2003.

3. Дмитриев В.И. Прикладная теория информации. Учебник для студентов ВУЗов по специальности «Автоматизированные системы обработки информации и управления». – М.: Высшая школа, 1989 – 320 с.

Исходным понятием в теории информации является понятие вероятностной схемы. Пусть - вероятностное пространство [1], где

W ‑ произвольное множество, элементы которого называются элементарными событиями, исходами или точками;

M – некоторая зафиксированная система подмножеств M Ì W ‑ случайных событий, удовлетворяющая свойствам σ (сигма)-алгебры:

· Пустое множество Æ должно быть событием, то есть принадлежать M. Это событие, которое существует в любом вероятностном пространстве, называется невозможным, поскольку оно никогда не происходит.

· Все множество W также должно быть событием: W Î M. Это событие называется достоверным, так как происходит при любой реализации случайного опыта.

· Совокупность событий M должна образовывать алгебру, то есть быть замкнутой относительно основных теоретико-множественных операций, выполняемых над конечным числом событий. Если A Î M и B Î M, тогда должно быть AÈB Î M, AÇB Î M, `A=W ‑A Î M. Операции над событиями имеют очевидный содержательный смысл.

· В дополнение к указанным свойствам, система M должна быть замкнута относительно операций над событиями, выполняемых в счетном числе (свойство s-алгебры). Если, тогда должно быть и.

Р ‑ это числовая функция, которая определена на M и ставит в соответствие каждому событию B Î M число P(B), которое называется вероятностью события B. Эта функция должна быть конечной сигма-аддитивной мерой, равной 1 на всем пространстве, то есть обладать свойствами:

§ 0≤P(B)≤1 для любого B Î M;

§ P(Æ) = 0, P(W)= 1;

§ Если A Î M и B Î M — события, причем AÇB =Æ, тогда P(AÈB)=P(A)+P(B) (свойство аддитивности).

§ Если, причем если B_iÇB_j=Æ для любых i¹j, тогда должно быть (свойство сигма-аддитивности).

Пусть ‑ полная группа попарно несовместимых исходов события A.

Определение 1.1. Параназывается вероятностной схемой события.

Говорят, что вероятностная схема А дискретна, если число событий не более чем счётно. В этом случае будем записывать в виде:

(1)

где а_k - исход вероятностной схемы, p_k - вероятность исхода,

,.

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

Пусть существует вероятностная схема события A

,,,

и вероятностная схема события B

,,,

тогда можно задать объединенную вероятностную схему некоторого события С, которое будет имеет вид:

,

дополнительно заметим, что

Важной характеристикой схемы является энтропия ‑ средняя мера неравновероятности исходов схемы. Энтропия и близкое понятие количество информации по-разному определялись рядом авторов. Приведём некоторые из этих определений.

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

Согласно Р. Хартли [2] количество информации, содержащееся в сообщении, должно удовлетворять двум требованиям:

a) Пусть сообщение Т₁ записанное в алфавите A₁, | A₁|=m₁ имеет длину n₁, а сообщение Т₂, записанное в алфавите А₂, | A₂|=m₂, имеет длину n₂. Тогда если выполнено, то сообщения Т₁ и Т₂ несут одинаковое количество информации.

b) Количество информации, содержащееся в сообщении, пропорционально его длине.

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

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

Чем больше (или меньше вероятность сообщения), тем большая степень неопределенности характеризует этот выбор и тем более информативным можно считать сообщение.

Очевидно, что количество информации, содержащейся в элементарном сообщении, является некоторой функцией от вероятности передачи этого сообщения:

. (1)

Определим вид этой функции Для этого потребуем, чтобы мера количества информации удовлетворяла двум интуитивным свойствам:

1. Если выбор сообщения заранее предопределен (‑ неопределенности нет), то количество информации в этом сообщении равно нулю:.

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

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

. (2)

Тогда, в соответствии с требованием (2), должно выполняться условие

. (3)

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

.

Эта логарифмическая функция характеризует количество информации. Указанная мера была предложена американским ученым Р.Хартли в 1928 г.

Иногда формулу Хартли для двоичных логарифмов и равновероятном появлении сообщений записывают так:

,

т. к. каждое из событий имеет равновероятный исход, то.

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

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

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

,,,

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

1. Информация одиночного события a_i Î A, происходящего с вероятностью p_i имеет положительное значение:

2. Имеет место для случая объединенной вероятностной схемы, например для A и B, тогда совместная информация двух независимых событий a_i и b_{j ,} которые обладают совместной плотностью вероятности, будет иметь вид:

3. Информация ‑ это есть непрерывная функция от вероятности.

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

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

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

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

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

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

H = log₂ m.

Тогда единицу количества информации на один элемент сообщения называют двоичной единицей или битом. При этом единица неопределенности (двоичная единица или бит) представляет собой неопределенность выбора из двух равновероятных событий (bit — сокращение от англ. binary digit — двоичная единица)

Так как из log₂ m = 1 следует m = 2, то ясно, что 1 бит - это количество информации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1.

Двоичное сообщение длины n содержит n бит информации.

Единица количества информации, равная 8 битам, называется байтом.

Если основание логарифма выбрать равным десяти, то энтропия выражается в десятичных единицах на элемент сообщения - дитах, причем 1 дит = log₁₀2 бит = 3,32 бит.

Если основание логарифма выбрать равным e, то энтропия выражается в натуральных единицах – натах.

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

Решение. В рассматриваемом случае длина сообщения, соответствующая одной строке, равна числу случайных по амплитуде импульсов в ней: n = 600.

Количество элементов сообщения (знаков) в одной строке равно числу значений, которое может принять амплитуда импульсов в строке,: m = 8.

Количество информации в одной строке: I = n log m = 600 log 8, а количество информации в кадре: I ¢ = 625 I = 625 600 log 8 = 1,125 × 10⁶ бит.

Дата добавления: 2013-12-12