Современные проблемы науки и образования. Логарифмическая мера информационной емкости

Аддитивная мера (мера Хартли) использует понятия глубины А и длины n числа.

Глубина числа - количество символов (элементов), принятых для представления информации. В каждый момент времени реализуется только один какой-либо символ.

Длина n числа - количество позиций, необходимых и достаточных для представления чисел заданной величины.

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

Если сообщение - число, понятие глубины числа будет трансформировано в понятие основания системы счисления. При заданных глубине и длине числа количество чисел, которое можно представить, N = А n . Очевидно, что N однозначно характеризует степень исходной неопределенности. Исходная неопределенность по Хартли определяется

H 1 = log a N . (4)

Неопределенность после получения сообщения, остаточная неопределенность,

H 2 = log a N* , (5)

где N* - число возможных значений принятого слова после получения сообщения.

Основание логарифма в (5) определяет только единицы измерения неопределенности. При a=2 это двоичная единица информации, называемая бит. При a = 10 десятичная (дит ), при a =e натуральная (нат ). Далее мы будем всегда пользоваться двоичной единицей.

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

Очевидно, что должно быть N* < N, а N* = 1 только в идеальном случае передачи сообщения без потери информации или, что то же самое, измерения некоторой физической величины без ошибок. Количество информации по Хартли оценивается как

I=H 1 – H 2 = log a N - loga N* n = log a N/ N* . (6)

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

I(q) =log 2 N=n log 2 А , бит . (7)

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

Логарифмическая мера для неопределенности и информации выбрана не случайно. Она оказывается удобной при описании сложных опытов. Допустим, что задача состоит в одновременном приеме информации от двух источников, не зависящих друг от друга. При этом N 1 и n 1 - число возможных сообщений до и после приема информации от первого источника, а - N 2 и n 2 от второго. Пусть H 11 и H 12 - исходная неопределенность знания первого и второго сообщения, соответственно, первого и второго источника. Естественно потребовать, чтобы общая неопределенность знания о двух сообщениях определялась суммой неопределенностей каждого, т.е. мера должна обладать свойством аддитивности

H = H 11 + H 12 .

Число возможных сочетаний двух независимых величин из множеств N 1 N 2 N = N 1 N 2 .

Тогда исходная неопределенность H =H 11 + H 12 , аналогично остаточная неопределенность H=H 21 +H 22 .

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

I(q 1 , q 2 , ...,q n)= I(q 1)+ I(q 2)+...+I(q k) , (8)

где I(q k) - количество информации от источника k .

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

Примечание. Для рассмотрения дальнейшего материала необходимо использовать понятие «вероятность события» . Под вероятностью события (см., например, Лютикас В.С. Факультативный курс по математике. Теория вероятностей. М.: Просвещение, 1990.) принимается постоянная величина, около которой группируются значения частоты появление некоторого события, например, передачи одного из символов алфавита. Если частота появления любого символа алфавита при передаче длинной последовательности символов одинакова, то говорят о равновероятных событиях, символах, сообщениях и т.п. Независимыми сообщения полагают, если вероятности их передачи не зависят от того, какие сообщения были переданы ранее.

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Об обосновании логарифмической меры информации

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

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

Важнейшим вопросом, на основе которого строится та или иная теория информации, является выбор меры информации.

Он во многом определяется теми объектами, на анализ которых направлена разрабатываемая теория.

В настоящее время в теории информации наибольшее распространение имеют меры Хартли и Шеннона, причем в ряде случаев меру Хартли представляют как частный случай меры Шеннона.

Однако уже по своему назначению мера Хартли имеет существенное отличие от меры Шеннона, так как первая направлена на исследование детерминированных (невероятностных) процессов конечной длины, а вторая - на анализ вероятностных процессов любой длительности, для анализа которых используются статистические методы .

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

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

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

Лежащая в основе структурной теории информации логарифмическая мера, где и - любые положительные числа конечной длины, не равные 0, а еще и не равное 1, предложенная Хартли в 1928 г., не была им логически обоснована, а вводилась на основе интуитивных соображений . Причем, что существенно, в таком виде она может принимать как положительные, при, так и отрицательные, при, значения.

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

Действительно, если каждый из двух источников и генерирует соответственно и сообщений, то их общее количество

Прологарифмировав выражение (1), получим равенство

которое доказывает свойство аддитивности меры информации Хартли.

Рассмотрим другое обоснование меры Хартли применительно к задачам поиска (непрерывного и дискретного).

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

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

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

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

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

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

Если за меру информации в данном случае взять, то она в точности совпадает с логарифмической мерой Хартли, взятой по основанию:

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

В общем случае при разбиении исходного множества, состоящего из объектов, на классов эквивалентности в каждом из них может содержаться объектов и соответственно вероятность нахождения искомого объекта в том или ином классе равна

При этом.

Формула Шеннона для энтропии, определяющая меру неопределенности нахождения искомого объекта в том или ином классе эквивалентности до тестирования, при первом разбиении

где утверждает, что величина энтропии достигает максимума для первого разбиения

при нахождении искомого объекта в классах эквивалентности с равными вероятностями

В данном случае.

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

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

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

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

На рис. 1 показано дерево с 3 равномерными разбиениями на 2 класса эквивалентности исходных объектов. В его вершинах проставляются содержащиеся в полученных классах эквивалентности количества объектов. В данном случае в каждой вершине генерируется максимальное количество информации

в сумме по всем разбиениям составляющее бита.

Рисунок 1 - Дерево равномерных разбиений с,

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

Другое дерево разбиений на рис. 2 для неравномерных разбиений объектов на 2 класса эквивалентности имеет среднее число разбиений по всем возможным путям разбиений

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

Это вызвано тем, что количество информации, вырабатываемое при каждом разбиении в соответствии с формулой Шеннона (6), меньше 1 бита, то есть время поиска искомого объекта не является минимальным.

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

Количество информации, необходимое для поиска одного целого искомого объекта не зависит от способа разбиения исходного множества объектов на классы эквивалентности и остается постоянным и равным.

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

Рисунок 2 - Дерево неравномерных разбиений при, и

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

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

Основное выражение для теории информации, предложенное Шенноном, имеет вид

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

искомого объекта и остаточной

где - остаточное число объектов, среди которых имеется искомый.

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

Последнее выражение представляет важное условие, которое сформулировано в как принцип унитарности.

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

Если же, то это говорит о том, что информация об объекте передана приемнику частично.

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

Это значит, что в рассматриваемом случае, когда, при тестировании вырабатывается дополнительная информация о деталях объекта, принадлежащих теперь уже новым, ранее неисследованным классам эквивалентности. Такая процедура детализации объекта может длиться неопределенно долго. Например, в дереве разбиений на рис. 1 после вершины (класса эквивалентности), содержащий после 3-го разбиения один объект, могут идти вершины, содержащие 0,5 объекта (4-е разбиение), затем 0,25 и т.д. Каждый раз величина информации об объекте при этом увеличивается на 1 бит и может достичь любой величины.

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

Все приведенные выше рассуждения относятся и к задачам поиска с числом объектов при условии, что в получаемых в процессе разбиений классах эквивалентности допускаются нецелые числа объектов.

Из неравенства следует, что

и соответственно

где - энтропия при;

Энтропия при.

Теорема 1. Если -е разбиение числа объектов, содержит классы эквивалентности с равным количеством объектов, то имеет место неравенство

Доказательство.

Из условия и соответственно следует, что.

Теорема доказана.

Следствие 1. Энтропия -го разбиения ограничена неравенством

Теорема 2. Если -е разбиение числа объектов при содержит классы эквивалентности с количеством объектов, то имеет место неравенство

Доказательство. Так как, то, где - количество объектов, размещенных по классам эквивалентности -го разбиения.

Из условия и соответственно непосредственно следует, что.

Теорема доказана.

Следствие 1 Остаточная энтропия ограничена неравенством

На рис. 3 в качестве примера к теоремам 1, 2 приведено дерево для трех разбиений с исходным количеством объектов. Из него видно, что классы второго разбиения содержат по 1,5 объекта, а классы третьего разбиения по 0,75 объекта, . По вертикальной оси координат на рисунке расположены номера исходных объектов, а по горизонтали величина получаемой после очередного разбиения 1, 2, 3 суммарной информации и значение остаточной информации. Величина вырабатываемой на каждом шаге информации остается при этом постоянной и максимальной:

Теорема 3.

Доказательство. Так как, то, где. Прологарифмировав последнее выражение, получим, что

Теорема доказана.

Рисунок 3 - Дерево разбиений при.

Теорема 4

Доказательство. Так как, то, где. Прологарифмировав последнее выражение, получим, что.

Теорема доказана.

Следствие 1

Так как при разбиениях числа в классах, получаемых при -м разбиении, содержится больше, а в классах -го разбиения меньше 1-го объекта, то это значит, что количество информации об объекте после -го разбиения

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

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

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

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

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

относительно.

Например, при значение надо выбрать примерно равным. Тогда.

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

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

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

Основание логарифма, при котором

где - целое число разбиений, которое можно найти из выражения

Соответственно

Из (25) следует, что

Например, для,

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

Определим отношение (25) как начальную плотность информации до первого разбиения:

Очевидно, что плотность информации изменяется при изменении от 1 до в пределах от 0 до 1.

Так для, начальная плотность информации

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

Так, для рассматриваемого выше примера после первого разбиения на два класса эквивалентности

а после второго

Из выражения (28) следует, что в случае после каждого разбиения плотность информации уменьшается и только при остается постоянной для всех разбиений и равной максимальной - 1.

Из (26) следует, что

и соответственно при

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

Следствие 1 теоремы 4 показывает, что количество информации, вырабатываемой на -м последнем разбиении

При этом в соответствии с (16) не равно 0.

Для получения полной информации об объекте достаточно, чтобы. Тогда выражение (31) примет вид

Так как из (17) следует, что

то достичь равенства (32) можно, исходя из выражения

которое при заданном выполняется при соответствующем распределении вероятностей.

Так, например, для

и соответственно

Для достижения последнего равенства следует, чтобы вероятности и равнялись соответственно 0,15; 0,85 или 0,85; 0,15.

Это значит, что полученное во 2-м разбиении число в размере объекта разбивается во время 3-го разбиения на две пропорциональные вероятностям и части (0,225 и 1,275), которые затем анализируются тестом на предмет отношения одной из них к искомой. Вероятность их нахождения равна или, или в зависимости от их величины.

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

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

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

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

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

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

Подобные документы

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

контрольная работа , добавлен 24.12.2012


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

курсовая работа , добавлен 22.03.2010


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

курсовая работа , добавлен 09.05.2013


Понятие энтропии. Энтропия как мера степени неопределенности. Понятие об информации. Измерение информации. Теорема Шеннона о кодировании при наличии помех. Пример использования энтропии в прогнозировании и ее значение для прогнозирования.

реферат , добавлен 14.12.2008


Разработка экономико-математической модели и решение задачи линейного программирования с использованием математических методов. Транспортная задача в матричной постановке и ее свойства. Построение исходного допустимого плана. Критерий оптимальности.

курсовая работа , добавлен 16.01.2011


Основы математического моделирования детерминированных и стохастических объектов. Идентификация объектов управления по переходной характеристике. Получение модели методом множественной линейной регрессии и проверка ее адекватности по критерию Фишера.

курсовая работа , добавлен 14.10.2014


Простейшие алгоритмы направленного случайного поиска. Алгоритм наилучшей пробы с направляющим гиперквадратом. Многоканальный статистический оптимизатор со случайным поиском. Метод статистического градиента. Локальный случайный поиск по наилучшей пробе.

курсовая работа , добавлен 08.02.2015


Понятия и определения теории генетических алгоритмов. Математический базис изобретательской физики. Генетический алгоритм изобретательской задачи. Описание операторов генетических алгоритмов. Система мысленного поиска и слежения в сознании изобретателя.

курсовая работа , добавлен 22.05.2012


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

контрольная работа , добавлен 18.05.2015


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

Существует несколько подходов к измерению информации.

Комбинаторная мера

Для лучшего понимания рассмотрим несколько простейших примеров.

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

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

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

Этот пример позволяет перейти к понятию комбинаторной меры информации и дать следующее определение:

Комбинаторная мера информации N - это способ измерения количества информации путем оценки количества возможных комбинаций информационных элементов.

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

Рассмотрим следующий пример.

Пример 2. Пусть задана одна из десятичных цифр, например, цифра 8 и одна из шестнадцатеричных – к примеру, цифра 6 (можно было взять любую другую шестнадцатеричную - 8, В, F и т. д.). Теперь, в соответствии с определением комбинаторной меры, определим количество информации, заключенное в каждой из этих цифр. Поскольку цифра 8 является десятичной, а значит, представляет один символ из десяти, то N 8 = 10 комбинаций. Аналогично, цифра 6 представляет один из шестнадцати символов, а поэтому N 6 = 16 комбинаций. Следовательно, что шестнадцатеричная цифра содержит больше информации, чем десятичная.

Из рассмотренного примера можно сделать вывод, что чем меньше цифр находится в основании системы счисления, тем меньше информации несет в себе один ее элемент.

Двоичная логарифмическая мера

Английский инженер Р. Хартли предложил измерять количество информации двоичной логарифмической мерой:

где N - количество различных комбинаций информационных элементов. Единицей измерения информации при таком измерении является бит.

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

Подсчет дает следующие результаты:

в примере с кубиком I = log 2 6 = 2,585 бит;

в примере с десятичной системой счисления I = log 2 10 = 3,322 бит;

в примере с шестнадцатеричной системой счисления I = log 2 16 = 4 бит;

в примере с двоичной системой счисления I = log 2 2 = 1 бит.

Последняя цифра говорит о том, что в каждой цифре двоичной системы счисления содержится один бит информации. Вообще, в технических системах двоичная система счисления применяется для кодировки двух возможных состояний, например 1 обозначает наличие электрического тока в сети, 0 - его отсутствие.

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

Равновероятные и взаимно независимые события в реальной жизни встречаются довольно редко. Если обратить внимание на разговорные языки, например русский, то можно сделать интересные выводы. Для упрощения теоретических исследований в информатике принято считать, что русский алфавит состоит из 32 символов (е и ё, а также ь и ъ между собой не различаются, но добавляется знак пробела между словами). Если считать, что каждая буква русского языка в сообщении появляется одинаково часто и после каждой буквы может стоять любой другой символ, то можно определить количество информации в каждом символе русского языка как:

I = log 2 32 = 5.

Однако, фактически все бывает не так. Во всех разговорных языках одни буквы встречаются чаще, другие - гораздо реже. Исследования говорят, что на 1000 букв приходится следующее число повторений:

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

Эта мера определяет полезность информации (ценность) для достижения пользователем поставленной цели.

В основе всей теории информации лежит открытие, сделанное Р. Хартли в 1928 году, и состоящее в том, что информация допускает количественную оценку.

Подход Хартли основан на фундаментальных теоретико-множественных, по существу комбинаторных основаниях, а также нескольких интуитивно ясных и вполне очевидных предположениях.

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

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

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

Чем больше элементов в множестве, тем больше неопределенность выбора, тем больше информации.

Количество этих чисел (элементов) в множестве равно: N=2i

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

Выбор одного числа дает нам следующее количество информации: i=Log 2 (N)

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

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

При увеличении длины числа в два раза количество информации в нем так же должно возрасти в два раза, не смотря на то, что количество чисел в множестве возрастает при этом по показательному закону (в квадрате, если числа двоичные), то есть если N2=(N1)2, то I2=2*I1,

F(N1*N1)=F(N1)+F(N1).

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

Log 2 (N2)=Log 2 (N1)2=2*Log 2 (N1)

Это второе требование называется требованием аддитивности.

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

Пример. Имеются 192 монеты. Известно, что одна из них фальшивая, например, более легкая по весу. Определим, сколько взвешиваний нужно произвести, чтобы выявить её. Если положить на весы разное количество монет, то получим три независимые возможности: а) левая чашка ниже; б) правая чашка ниже; в) чашки уравновешены. Таким образом, каждое взвешивание дает количество информации I=log23, следовательно, для определения фальшивой монеты нужно сделать не менее k взвешиваний, где наименьшее k удовлетворяет условию log23k log2192. Отсюда, k 5или, k=4 (или k=5 - если считать за одно взвешивание и последнее, очевидное для определения монеты). Итак, необходимо сделать не менее пять взвешиваний (достаточно 5).

6.1. Мера количества информации

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

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

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

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

Для исследования этих вопросов с общих позиций необходимо прежде всего установить универсальную количественную меру информации, не зависящую от конкретной физической природы передаваемых сообщений. Когда принимается сообщение о каком-либо событии, то наши знания о нем изменяются. Мы получаем при этом некоторую информацию об этом событии. Сообщение о хорошо известном нам событии, очевидно, никакой информации не несет. Напротив, сообщение о малоизвестном событии содержит много информации. Например, сообщение бюро погоды от 20 июня о том, что в Одессе «завтра выпадет снег» несет больше информации, чем сообщение «завтра ожидается ясная погода». Первое сообщение является неожиданным, оно несет сведения о редком, маловероятном явлении и поэтому содержит много информации. Второе сообщение является весьма вероятным, оно содержит мало нового и поэтому несет мало информации.

Таким образом, количество информации в сообщении о некотором событии существенно зависит от вероятности этого события.

Вероятностный подход и положен в основу определения меры количества информации. Для количественного определения информации, в принципе, можно использовать любую монотонно убывающую функцию вероятности F [ P (a )] где Р(а) - вероятность, сообщения а. Простейшей из них является функция F =1/Р(а) которая характеризует меру неожиданности (неопределенности) сообщения. Однако удобнее исчислять количество информации а логарифмических единицах, т. е. определять количество информации в отдельно взятом сообщении как

Так как 0< P (a ) l , то J (a ) - величина всегда положительная и конечная. При Р(а)=1 количество информации равно нулю, т. е., сообщение об известном событии никакой информации не несет. Логарифмическая мера обладает естественным в данном случае свойством аддитивности, согласно которому количество информации, содержащееся в нескольких независимых сообщениях, равна сумме количества информации в каждом из них. Действительно, так как совместная вероятность п независимых сообщений , то количество информации а этих сообщениях равно: , что соответствует интуитивным представлениям об увеличении информации при получении дополнительных сообщений. Основание логарифма k может быть любым. Чаще всего принимают k =2, и тогда количество информации выражается в двоичных единицах: дв. ед.

Двоичную единицу иногда называют бит. Слово бит произошло от сокращения выражения binary digit (двоичная цифра). В двоичных системах связи для передачи сообщения используется два символа, условно.обозначаемых 0 и 1. В таких системах при независимых и равновероятных символах, когда P (0) = P (1)=1/2 , каждый из них несет одну двоичную единицу информации:

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

(6.2)

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

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

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

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

К определению информации можно подойти и с другой стороны. Будем рассматривать в качестве сообщения не отдельную букву, а целое слово. Если все буквы равновероятны и следуют независимо, то все слова будут также равновероятны и , где N = m n - число возможных слов. Тогда можно записать

Для двоичного кода ансамбль элементарных сообщений состоит из двух элементов 0 и 1 (m =2). В этом случае сообщение из п элементов несет информацию,

В общем случае при передаче сообщений неопределенность снимается не полностью. Так, в канале с шумами возможны ошибки. По принятому сигналу v только с некоторой вероятностью можно судить о том, что было передано сообщение а. Поэтому после получения сообщения остается некоторая неопределенность, характеризуемая величиной апостериорной вероятности P (a / v ), а количество информации, содержащееся в сигнале v , определяется степенью уменьшения неопределенности при его приеме. Если Р(а) - априорная,вероятность, то количество информации в принятом сигнале v относительно переданного сообщения а, очевидно, будет равно:

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