Основы информатики и вычислительной техники: Учебно-практическое пособие, страница 30

Предположим, что имеется источник с N возможными состояниями и энтропией Н(x). Требуется определить одно из состояний системы.

Для этого используется принцип последовательного образования равновероятных групп.

Вначале все состояния источника разделяют на две группы Х₁ и Х₂ (табл. 1.7), где Р - вероятность первой группы состояний. Когда состояния равновероятные, ответ дает максимальную информацию, равную 1 биту.

	P	1-P

                   Табл. 1.7

Полученный ответ не снимает полностью неопределенность, он только указывает группу, в которой находится состояние источника. Далее выбранную группу снова разделяют на две равновероятные группы. Ответ («Да» или «Нет») в свою очередь дает информацию равную одному биту. Таким образом, после двух ответов получено два бита информации. Для полного устранения неопределенности надо получит количество информации, равное энтропии источника Н [бит].

Следовательно, энтропия определяет минимальное количество вопросов, с помощью которых можно полностью определить состояние системы. Вопросы должны быть поставлены так, чтобы ответы были равновероятны.

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

Пример 1. Имеется 9 шаров, один тяжелее. Есть чашечные весы Определить минимальное число взвешиваний.

Одно взвешивание (один вопрос) дает три равновероятных ответа: «слева», «справа», «не на весах».

,

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

Пример 2. Имеется система трех последовательно соединенных элементов (рис. 1.14)

                   Р₁=1/2        Р₂=1/4                  Р₃=1/4

                                      рис. 1.14

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

В соответствии с (1.65)

Следовательно, минимальное число проверок равно 1,5. Разбиваем элементы на 2 группы с равными вероятностями Р=1/2. В первую группу входят первый элемент, во вторую – второй и третий элементы.

При первой проверке проверяем первый элемент: если он неисправен (ответ «да»), то проверка закончена, если он исправен (ответ «нет»), то проверка продолжается во второй группе. При второй проверке проверяется второй элемент: если он неисправен (ответ «да»), то проверка закончена, если он исправен (ответ «нет») – то неисправен третий элемент. Среднее количество проверок (с Р=1/2 неисправен первый элемент – одна проверка; с Р=1/2 – неисправны второй и третий элементы – две проверки):

 проверки.

Вопросы для самопроверки

1.  Какие проблемы рассматривает «теория информации»?

2.  В чем отличие сигналов детерминированных от случайных?

3.  В чем отличие стационарных случайных сигналов от нестационарных?