WikiSort.ru - Не сортированное

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

Формула Хартли определяет количество информации, содержащееся в сообщении длины n.

Имеется алфавит А, из букв которого составляется сообщение:

${\displaystyle |A|=m.}$

Количество возможных вариантов разных сообщений:

${\displaystyle N=m^{n},}$

где N — возможное количество различных сообщений, m — количество букв в алфавите, n — количество букв в сообщении.

Пример: Алфавит состоит из двух букв «B» и «X», длина сообщения 3 буквы — таким образом, m = 2, n = 3. При выбранных нами алфавите и длине сообщения можно составить ${\displaystyle N=m^{n}=2^{3}=8}$ разных сообщений: «BBB», «BBX», «BXB», «BXX», «XBB», «XBX», «XXB», «XXX» — других вариантов нет.

Формула Хартли определяется:

${\displaystyle I=\log _{2}N=n\log _{2}m,}$

где I — количество информации в битах.

При равновероятности символов ${\displaystyle p={\frac {1}{m}},m={\frac {1}{p}}}$ формула Хартли переходит в собственную информацию.

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

Иллюстрация

Допустим, нам требуется что-либо найти или определить в той или иной системе. Есть такой способ поиска, как «деление пополам». Например, кто-то загадывает число от 1 до 100, а другой должен отгадать его, получая лишь ответы «да» или «нет». Задаётся вопрос: «число меньше N?». Любой из ответов «да» и «нет» сократит область поиска вдвое. Далее по той же схеме диапазон снова делится пополам. В конечном счёте загаданное число будет найдено.

Сколько вопросов надо задать, чтобы найти задуманное число от 1 до 100. Допустим, загаданное число 27. Вариант диалога:

Больше 50? Нет.
Больше 25? Да.
Больше 38? Нет.
Меньше 32? Да.
Меньше 29? Да.
Меньше 27? Нет.
Это число 28? Нет.

Если число не 28 и не меньше 27, то это явно 27. Чтобы угадать методом «деления пополам» число от 1 до 100, нам потребовалось 7 вопросов.

Можно просто спрашивать: это число 1? Это число 2? И т. д. Но тогда вам потребуется намного больше вопросов. «Деление пополам» — оптимальный в данном случае способ нахождения числа. Объём информации, заложенный в ответ «да»/«нет», равен одному биту (действительно, ведь бит имеет два состояния: 1 или 0). Итак, для угадывания числа от 1 до 100 нам потребовалось семь битов (семь ответов «да»/«нет»).

${\displaystyle N=2^{k}}$

Такой формулой можно представить, сколько вопросов (битов информации) потребуется, чтобы определить одно из возможных значений. N — это количество значений, а k — количество битов. Например, в нашем примере 27 меньше, чем 28, однако больше, чем 26. Да, нам могло бы потребоваться и всего 6 вопросов, если бы загаданное число было 28.

Формула Хартли:

${\displaystyle k=\log _{2}N.}$

Количество информации (k), необходимой для определения конкретного элемента, есть логарифм по основанию 2 общего количества элементов (N).

Формула Шеннона

Когда события не равновероятны, может использоваться формула Шеннона:

${\displaystyle I=-\sum _{i}p_{i}\log _{2}p_{i},}$

где p_i вероятность i-го события.

См. также

• Собственная информация