Формула шеннона в информационных потоках
По информатике
Количество информации
Введение
2. Неопределенность, количество информации и энтропия
3. Формула Шеннона
4. Формула Хартли
5. Количество информации, получаемой в процессе сообщения
Введение
По определению А.Д. Урсула - «информация есть отраженное разнообразие». Количество информации есть количественная мера разнообразия. Это может быть разнообразие совокупного содержимого памяти; разнообразие сигнала, воспринятого в процессе конкретного сообщения; разнообразие исходов конкретной ситуации; разнообразие элементов некоторой системы… - это оценка разнообразия в самом широком смысле слова.
Таким образом, информация, связанная с 10 полосами. Мы по-прежнему замечаем, что полученный результат говорит нам о том, что для передачи головы и кросс-последовательности, определяемой 10 бросками нашей монеты, требуется 10 бит. Является ли мера информации субъективной?
Любопытный читатель может тогда задаться вопросом, является ли подсчет информации, предоставленной формулой Шеннона, объективной или нет. Другими словами, информация является неотъемлемым и объективным свойством наблюдаемых событий или зависит от выбора субъективного наблюдателя? разные наблюдатели связывают один и тот же информационный контент с теми же событиями?
Любое сообщение между источником и приемником информации имеет некоторую продолжительность во времени, но количество информации воспринятой приемником в результате сообщения, характеризуется в итоге вовсе не длиной сообщения, а разнообразием сигнала порожденного в приемнике этим сообщением.
Память носителя информации имеет некоторую физическую ёмкость, в которой она способна накапливать образы, и количество накопленной в памяти информации, характеризуется в итоге именно разнообразием заполнения этой ёмкости. Для объектов неживой природы это разнообразие их истории, для живых организмов это разнообразие их опыта.
Не желая слишком углублять философские вопросы, связанные с этим вопросом, совершенно очевидно, что существует сильная субъективная составляющая приписывания вероятностей, связанных с возможными исходами события. Вспомните случай букмекера, который должен приписать шансы на результаты спортивного матча. Он будет полагаться на историческую серию и фактическую ситуацию в собственных чемпионатах команды по целому ряду других соображений, чтобы определить вероятности. Однако, даже если расчет основан на объективных данных, очевидно, что оценки вероятности связаны с «моделью», т.е. субъективным представлением события наблюдателем.
1.Бит
Разнообразие необходимо при передаче информации. Нельзя нарисовать белым по белому, одного состояния недостаточно. Если ячейка памяти способна находиться только в одном (исходном) состоянии и не способна изменять свое состояние под внешним воздействием, это значит, что она не способна воспринимать и запоминать информацию. Информационная емкость такой ячейки равна 0.
Чтобы быть еще яснее: вряд ли все букмекеры получат одинаковые шансы на одно и то же спортивное событие. Таким образом, мера информации тесно связана с «моделью», принятой наблюдателем. Поэтому формула Шеннона не обеспечивает объективную меру информации, а представляет собой уникальный математический метод, связывающий информацию с вероятностью.
Веб-сайт, созданный на основе шаблона, предлагаемого. Какова связь между физикой и энтропией? Углубленное изучение: физика, информационные технологии и информация: «Энтропия и компьютерная информация». Область применения: физика, информатика и теория сигналов.
Минимальное разнообразие обеспечивается наличием двух состояний. Если ячейка памяти способна, в зависимости от внешнего воздействия, принимать одно из двух состояний, которые условно обозначаются обычно как «0» и «1», она обладает минимальной информационной ёмкостью.
Информационная ёмкость одной ячейки памяти, способной находиться в двух различных состояниях, принята за единицу измерения количества информации - 1 бит.
Тематика: Информатика: цифровая и аналоговая информация, бит и двоичная система. Физика: понятие энтропии в термодинамике, порядке и беспорядке. Отправная точка для углубления: информация теперь является товаром, таким как нефть или металл, государственная служба, такая как вода и электричество. Хотя не все знают, что такое информационный век на самом деле, можно смотреть везде с мобильных телефонов на обмениваемые электронной почтой. Наше общество считается мрачной деревней, где почти каждый человек имеет доступ к большому количеству информации и обменивается ими с другими.
1 бит (bit - сокращение от англ. binary digit - двоичное число) - единица измерения информационной емкости и количества информации, а также и еще одной величины – информационной энтропии, с которой мы познакомимся позже. Бит, одна из самых безусловных единиц измерения. Если единицу измерения длины можно было положить произвольной: локоть, фут, метр, то единица измерения информации не могла быть по сути никакой другой.
За этим были огромные технологические разработки, которые позволили эту передачу информации. Но какова информация? Что мешает ее передаче? Ответ на многие из этих вопросов можно найти в открытиях и исследованиях Клода Шеннона. Биография Клода Шеннона.
Он учился в Университете Массачусетского технологического института, где он сотрудничал с дифференциальным анализатором Ванневара Буша, аналоговым компьютером. Многие считают, что его тезис является одним из самых важных и знаменитых тезисов века. В этой работе основное внимание уделяется проблеме восстановления с определенной степенью достоверности информации, передаваемой отправителем. В этой фундаментальной работе Шеннон использовал такие инструменты, как случайный анализ и большие отклонения, которые только что разрабатывались в те годы.
На физическом уровне бит является ячейкой памяти, которая в каждый момент времени находится в одном из двух состояний: «0» или «1».
Если каждая точка некоторого изображения может быть только либо черной, либо белой, такое изображение называют битовым, потому что каждая точка представляет собой ячейку памяти емкостью 1 бит. Лампочка, которая может либо «гореть», либо «не гореть» также символизирует бит. Классический пример, иллюстрирующий 1 бит информации – количество информации, получаемое в результате подбрасывания монеты – “орел” или “решка”.
Шеннон определил энтропию информации как меру избыточности, заложив основы теории информации. Его наиболее важным эссе является следующее, написанное Уорреном Уивером, «Теория математической коммуникации», короткое и неожиданно доступное для неспециалиста. Другая импортированная статья - «Теория коммуникации в криптографических системах», с которой Шеннон в основном основал математическую теорию криптографии. Он также сыграл важную роль в представлении типовой теоремы, которая изучала представление непрерывного сигнала через дискретный массив выборок через регулярные интервалы.
Количество информации равное 1 биту можно получить в ответе на вопрос типа «да»/ «нет». Если изначально вариантов ответов было больше двух, количество получаемой в конкретном ответе информации будет больше, чем 1 бит, если вариантов ответов меньше двух, т.е. один, то это не вопрос, а утверждение, следовательно, получения информации не требуется, раз неопределенности нет.
Шеннон был известен своим живым интеллектом и очень индивидуальностью; редко использовал заметки или эскизы, и он предпочел работать со своей головой. Из его научных интересов Шеннон был жонглером, певцом и шахматистом. Физическая энтропия: в термодинамике энтропия представляет собой функцию состояния, которая изучается по второму принципу термодинамики, является мерой расстройства физической системы. Согласно этому определению можно сказать, что когда система проходит один В одной из своих различных формулировок второй принцип термодинамики гласит, что в изолированной системе энтропия может только увеличиваться или на пределе оставаться постоянной для обратимых термодинамических преобразований.
Информационная ёмкость ячейки памяти, способной воспринимать информацию, не может быть меньше 1 бита, но количество получаемой информации может быть и меньше, чем 1 бит. Это происходит тогда, когда варианты ответов «да» и «нет» не равновероятны. Неравновероятность в свою очередь является следствием того, что некоторая предварительная (априорная) информация по этому вопросу уже имеется, полученная, допустим, на основании предыдущего жизненного опыта. Таким образом, во всех рассуждениях предыдущего абзаца следует учитывать одну очень важную оговорку: они справедливы только для равновероятного случая.
Статистическое определение энтропии энтропии также имеет определение ближе к «статистическому» подходу возможных конфигураций. Именно эти отношения, как мы увидим, аналогичны энтропии, введенной Шенноном. Информация и энтропия В теории информации - и в связи с теорией сигналов - энтропия измеряет количество неопределенности или информации, присутствующей в случайном сигнале. С другой точки зрения, энтропия - наименее сложная описательная сложность случайной величины. Исследование энтропии Клода Шеннона в этом контексте обусловлено.
В первой теореме Шеннона или теореме Шеннона об исходном кодировании он показал, что случайный источник информации не может быть представлен рядом битов, меньших его энтропии, то есть к его средней самоинформации. Этот результат требует статистического определения энтропии. Когда Шеннон позже вспомнил о найденном им результате. Моя самая большая проблема заключалась в том, как назвать это.
Количество информации мы будем обозначать символом I, вероятность обозначается символом P. Напомним, что суммарная вероятность полной группы событий равна 1.
2.Неопределенность, количество информации и энтропия
Основоположник теории информации Клод Шеннон определил информацию, как снятую неопределенность. Точнее сказать, получение информации - необходимое условие для снятия неопределенности. Неопределенность возникает в ситуации выбора. Задача, которая решается в ходе снятия неопределенности – уменьшение количества рассматриваемых вариантов (уменьшение разнообразия), и в итоге выбор одного соответствующего ситуации варианта из числа возможных. Снятие неопределенности дает возможность принимать обоснованные решения и действовать. В этом управляющая роль информации.
Когда он обсуждал это с Джоном Фон Нейманом, у него была «лучшая идея». Можно ли простым образом объяснить взаимосвязь между энтропией и информацией? Термодинамическая энтропия - это величина, которая определяется из второго принципа термодинамики. Он представляет собой величину, описывающую необратимость процессов и нерастворимую тепловую дисперсию других форм энергии, присутствующих в системе. Для Шеннона информация в смысле теории информации также является характерные для систем, особенно тех систем, которые используются для связи.
Ситуация максимальной неопределенности предполагает наличие нескольких равновероятных альтернатив (вариантов), т.е. ни один из вариантов не является более предпочтительным. Причем, чем больше равновероятных вариантов наблюдается, тем больше неопределенность, тем сложнее сделать однозначный выбор и тем больше информации требуется для этого получить. Для N вариантов эта ситуация описывается следующим распределением вероятностей: {1/N, 1/N, … 1/N}.
Информация сообщения никогда не может превышать значение, которое оно имело во время отправки сообщения, но оно может уменьшаться из-за различных процессов, которые приводят к частичной потере или ухудшению сообщения. Между двумя размерами может быть не очевидно, они выглядят как два размера, которые имеют противоположное поведение, но анализ этих двух размеров может быть более подробным. Если мы посмотрим на физическую систему с микроскопической точки зрения, мы можем описать ее с вероятностным распределением, которое обеспечивает для каждой микроскопической составляющей вероятность наблюдения ее с определенной скоростью в определенном положении.
Минимальная неопределенность равна 0, т.е. эта ситуация полной определенности, означающая что выбор сделан, и вся необходимая информация получена. Распределение вероятностей для ситуации полной определенности выглядит так: {1, 0, …0}.
Величина, характеризующая количество неопределенности в теории информации обозначается символом H и имеет название энтропия, точнее информационная энтропия.
Больцман установил, что существует математическая связь между этим распределением вероятности и энтропией, в частности, что энтропия системы пропорциональна среднему значению, принятому логарифмом этого сдвинутого распределения вероятности. Шеннон ввел аналогичную величину в исследование л информация. На самом элементарном уровне каждое сообщение может быть выражено как последовательность символов. В зависимости от сообщения каждый символ может быть предсказан или нет, с разной степенью достоверности от предыдущих символов.
Чем больше персонаж предсказуем, тем меньше он добавляет информацию в глобальное сообщение, то есть избыточное, может быть опущено, и обмен сообщениями будет в равной степени понятным. Ему нужно знать, что такое письмо, чтобы понять, как понимать сообщение. Однако есть несколько букв, которые могут быть исключены, в то время как другие могут появляться с разными вероятностями, также в зависимости от других слов, которые я, возможно, отправил раньше. Это рассуждение позволяет также назначать распределение вероятности сообщениям.
Энтропия (H) – мера неопределенности, выраженная в битах. Так же энтропию можно рассматривать как меру равномерности распределения случайной величины.
На рисунке 1. показано поведение энтропии для случая двух альтернатив, при изменении соотношения их вероятностей (p, (1-p)).Максимального значения энтропия достигает в данном случае тогда, когда обе вероятности равны между собой и равны Ѕ, нулевое значение энтропии соответствует случаям (p0=0, p1=1) и (p0=1, p1=0).
Каждый символ имеет вероятность ожидаемого в соответствии со следующими символами. Шеннон ввел величину, называемую информационной энтропией, которая связана с этой вероятностью точно так же, как термодинамическая энтропия связана с вероятностью состояния системы. Эта энтропия информации имеет разные свойства, подобные свойствам термодинамики, в том числе что со временем это не уменьшается, потому что со временем сообщение может стать менее явным из-за нарушений передачи. Расстройства передачи вводят символы, которые нельзя ожидать от предыдущих, поэтому они имеют распределение плоская вероятность, эффект через формулу Больцмана-Шеннона заключается в увеличении энтропии информации.
Количество информации I и энтропия H характеризуют одну и ту же ситуацию, но с качественно противоположенных сторон. I – это количество информации, которое требуется для снятия неопределенности H. По определению Леона Бриллюэна информация есть отрицательная энтропия (негэнтропия).
Когда неопределенность снята полностью, количество полученной информации I равно изначально существовавшей неопределенности H.
Информация играет роль доступной энергии, которая со временем уменьшается. Пример, объясняющий физическое и «компьютерное» отношение энтропии: рассмотрим физическую систему с точки зрения температуры, давления и объема и установим значение энтропии, в связи с чем можно определить степень порядка и, следовательно, количество наших информация. Предположим теперь, что мы понизим температуру, оставив остальные параметры неизменными: заметим, что ее энтропия уменьшается, а также увеличивается ее степень порядка, а вместе с ней и наш уровень информации.
При частичном снятии неопределенности, полученное количество информации и оставшаяся неснятой неопределенность составляют в сумме исходную неопределенность. Ht + It = H.
По этой причине, формулы, которые будут представлены ниже для расчета энтропии H являются и формулами для расчета количества информации I, т.е. когда речь идет о полном снятии неопределенности, H в них может заменяться на I.
3.Формула Шеннона
В общем случае, энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P: {p0, p1, …pN-1}, т.е. H=F(N, P). Расчет энтропии в этом случае производится по формуле Шеннона, предложенной им в 1948 году в статье "Математическая теория связи".
В частном случае, когда все варианты равновероятны, остается зависимость только от количества рассматриваемых вариантов, т.е. H=F(N). В этом случае формула Шеннона значительно упрощается и совпадает с формулой Хартли, которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, т.е. на 20 лет раньше.
Формула Шеннона имеет следующий вид:
(1)
Рис. 3. Нахождение логарифма b по основанию a - это нахождение степени, в которую нужно возвести a, чтобы получить b.
Напомним, что такое логарифм.
Логарифм по основанию 2 называется двоичным:
log2(8)=3 => 23=8
log2(10)=3,32 => 23,32=10
Логарифм по основанию 10 –называется десятичным:
log10(100)=2 => 102=100
Основные свойства логарифма:
log(1)=0, т.к. любое число в нулевой степени дает 1;
log(ab)=b*log(a);
log(a*b)=log(a)+log(b);
log(a/b)=log(a)-log(b);
log(1/b)=0-log(b)=-log(b).
Знак
минус в формуле
(1) не означает,
что энтропия
– отрицательная
величина. Объясняется
это тем, что
piЈ1
по определению,
а логарифм
числа меньшего
единицы - величина
отрицательная.
По свойству
логарифма
,
поэтому эту
формулу можно
записать и во
втором варианте,
без минуса
перед знаком
суммы.
Интерпретируется как частное количество информации, получаемое в случае реализации i-ого варианта. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины {I0, I1, … IN-1}.
Пример расчета энтропии по формуле Шеннона. Пусть в некотором учреждении состав работников распределяется так: ѕ - женщины, ј - мужчины. Тогда неопределенность, например, относительно того, кого вы встретите первым, зайдя в учреждение, будет рассчитана рядом действий, показанных в таблице 1.
Таблица 1.
| pi | 1/pi | Ii=log2(1/pi), бит | pi*log2(1/pi), бит | |
| Ж | 3/4 | 4/3 | log2(4/3)=0,42 | 3/4 * 0,42=0,31 |
| М | 1/4 | 4/1 | log2(4)=2 | 1/4 * 2=0,5 |
| е | 1 | H=0,81 бит |
Если же априори известно, что мужчин и женщин в учреждении поровну (два равновероятных варианта), то при расчете по той же формуле мы должны получить неопределенность в 1 бит. Проверка этого предположения проведена в таблице 2.
Таблица 2.
| pi | 1/pi | Ii=log2(1/pi), бит | pi*log2(1/pi), бит | |
| Ж | 1/2 | 2 | log2(2)=1 | 1/2 * 1=1/2 |
| М | 1/2 | 2 | log2(2)=1 | 1/2 * 1=1/2 |
| е | 1 | H=1 бит |
4.Формула Хартли
Формула Хартли – частный случай формулы Шеннона для равновероятных альтернатив.
Подставив в формулу (1) вместо pi его (в равновероятном случае не зависящее от i) значение , получим:
таким образом, формула Хартли выглядит очень просто:
(2)
Из нее явно следует, что чем больше количество альтернатив (N), тем больше неопределенность (H). Эти величины связаны в формуле (2) не линейно, а через двоичный логарифм. Логарифмирование по основанию 2 и приводит количество вариантов к единицам измерения информации – битам.
Энтропия будет являться целым числом лишь в том случае, если N является степенью числа 2, т.е. если N принадлежит ряду: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048…}
Рис. 3. Зависимось энтропии от количества равновероятных вариантов выбора (равнозначных альтернатив).
Для решения обратных задач, когда известна неопределенность (H) или полученное в результате ее снятия количество информации (I) и нужно определить какое количество равновероятных альтернатив соответствует возникновению этой неопределенности, используют обратную формулу Хартли, которая выводится в соответствии с определением логарифма и выглядит еще проще:
Например, если известно, что в результате определения того, что интересующий нас Коля Иванов живет на втором этаже, было получено 3 бита информации, то количество этажей в доме можно определить по формуле (3), как N=23=8 этажей.
Если же вопрос стоит так: “в доме 8 этажей, какое количество информации мы получили, узнав, что интересующий нас Коля Иванов живет на втором этаже?”, нужно воспользоваться формулой (2): I=log2(8)=3 бита.
5.Количество информации, получаемой в процессе сообщения
До сих пор были приведены формулы для расчета энтропии (неопределенности) H, указывая, что H в них можно заменять на I, потому что количество информации, получаемое при полном снятии неопределенности некоторой ситуации, количественно равно начальной энтропии этой ситуации.
Но неопределенность может быть снята только частично, поэтому количество информации I, получаемой из некоторого сообщения, вычисляется как уменьшение энтропии, произошедшее в результате получения данного сообщения.
(4)
Для равновероятного случая, используя для расчета энтропии формулу Хартли, получим:
(5)
Второе равенство выводится на основании свойств логарифма. Таким образом, в равновероятном случае I зависит от того, во сколько раз изменилось количество рассматриваемых вариантов выбора (рассматриваемое разнообразие).
=> . Т.е. количество полученной информации будет положительной величиной, если в результате получения сообщения количество рассматриваемых альтернатив уменьшилось, и отрицательной, если увеличилось.
Если количество рассматриваемых альтернатив в результате получения сообщения уменьшилось вдвое, т.е. , то I=log2(2)=1 бит. Другими словами, получение 1 бита информации исключает из рассмотрения половину равнозначных вариантов.
Рассмотрим в качестве примера опыт с колодой из 36 карт.
Рис. 4. Иллюстрация к опыту с колодой из 36-ти карт.
Пусть некто вынимает одну карту из колоды. Нас интересует, какую именно из 36 карт он вынул. Изначальная неопределенность, рассчитываемая по формуле (2), составляет H=log2(36)@5,17 бит. Вытянувший карту сообщает нам часть информации. Используя формулу (5), определим, какое количество информации мы получаем из этих сообщений:
Вариант A. “Это карта красной масти”.
I=log2(36/18)=log2(2)=1 бит (красных карт в колоде половина, неопределенность уменьшилась в 2 раза).
Вариант B. “Это карта пиковой масти”.
I=log2(36/9)=log2(4)=2 бита (пиковые карты составляют четверть колоды, неопределенность уменьшилась в 4 раза).
Вариант С. “Это одна из старших карт: валет, дама, король или туз”.
I=log2(36)–log2(16)=5,17-4=1,17 бита (неопределенность уменьшилась больше чем в два раза, поэтому полученное количество информации больше одного бита).
Вариант D. “Это одна карта из колоды".
I=log2(36/36)=log2(1)=0 бит (неопределенность не уменьшилась - сообщение не информативно).
Вариант D. “Это дама пик".
I=log2(36/1)=log2(36)=5,17 бит (неопределенность полностью снята).
Список использованной литературы
Зрение. schools.keldysh/school1413/bio/novok/zrenie.htm/.
Ильина О. В. Кодирование информации в курсе информатики средней школы. iro.yar:8101/resource/distant/informatics/s/ilina/Chapter3.htm/.
Основы теории передачи информации. Экспериментальное изучение количественных аспектов информации. Количество информации по Хартли и К. Шеннону. Частотные характеристики текстовых сообщений. Количество информации как мера снятой неопределенности.
Информология- общая теория информации. Возникновение информологии как науки можно отнести к концу 50-х годов нашего столетия, когда американским инженером Р. Хартли была сделана попытка ввести количественную меру информации, передаваемой по каналам связи.
Обеспечение достоверности передаваемой информации применением корректирующих кодов. Код Хэмминга - алгоритм обнаружения и исправления одиночной ошибки. Использование циклических кодов при последовательной передачей между ЭВМ и внешними устройствами.
Програма розрахунку інформаційних характеристик каналу зв"язку. Побудова коду для передачі повідомлень. Процедури кодування, декодування та оцінка ефективності кодів. Програма на алгоритмічній мові Паскаль. Канальна матриця, що визначає втрати інформації.
Особенности вычисления количества информации, получаемой при фазовом сдвиге сигнала, если известна его амплитуда. Расчет информационных характеристик источников дискретных сообщений и дискретного канала. Особенности применения дискретизации и квантования.
Общая схема действия каналов связи, их классификация и характеристика. Дискретный, бинарный канал связи и определение их пропускной способности, особенности действия с помехами и без них по теореме Шеннона. Пропускная способность непрерывного канала.
2.2.2. Информационный критерий оценки фонетической неопределенности. При распознавании устной речи необходимо стремиться к тому, чтобы все фонемы классифицировались правильно, поэтому нас интересует распознавание полной последовательности фонетических единиц, составляющих высказывание.
Объединение как совокупность нескольких ансамблей дискретных, случайных событий. Безусловная энтропия - среднее количество информации, приходящееся на один символ. Описание информационных свойств непрерывного источника. Понятие дифференциальной энтропии.
Понятие информации, виды информации. Методы получения, использования информации. Измерение сообщений и информации. Понятие о связи информации и самоорганизации.
Формула Хартли. Формула Шеннона. Теорема Шеннона-Хартли. Теорема Котельникова. ИКМ. Основной цифровой поток DS0
Формула Хартли
Формула Хартли определяет количество информации, содержащееся в сообщении длины n.
Имеется алфавит А, из букв которого составляется сообщение:
Количество возможных вариантов разных сообщений:
где N - возможное количество различных сообщений, шт; m - количество букв в алфавите, шт; n - количество букв в сообщении, шт.
Пример: Алфавит состоит из двух букв «B» и «X», длина сообщения 3 буквы - таким образом, m=2, n=3. При выбранных нами алфавите и длине сообщения можно составить разных сообщений «BBB», «BBX», «BXB», «BXX», «XBB», «XBX», «XXB», «XXX» - других вариантов нет.
Формула Хартли определяется:
где I - количество информации, бит.
При равновероятности символов формула Хартли переходит в собственную информацию .
Формула Хартли была предложена Ральфом Хартли в 1928 году как один из научных подходов к оценке сообщений.
Иллюстрация
Допустим, нам требуется что-либо найти или определить в той или иной системе. Есть такой способ поиска, как «деление пополам». Например, кто-то загадывает число от 1 до 100, а другой должен отгадать его, получая лишь ответы «да» или «нет». Задаётся вопрос: «число меньше N?». Любой из ответов «да» и «нет» сократит область поиска вдвое. Далее по той же схеме диапазон снова делится пополам. В конечном счёте загаданное число будет найдено.
Сколько вопросов надо задать, чтобы найти задуманное число от 1 до 100. Допустим загаданное число 27. Вариант диалога:
Больше 50? Нет.
Больше 25? Да.
Больше 38? Нет.
Меньше 32? Да.
Меньше 29? Да.
Больше 27? Нет.
Это число 26? Нет.
Если число не 26 и не больше 27, то это явно 27. Чтобы угадать методом «деления пополам» число от 1 до 100, нам потребовалось 7 вопросов.
Можно просто спрашивать: это число 1? Это число 2? И т. д. Но тогда вам потребуется намного больше вопросов. «Деление пополам» - самый оптимальный способ нахождения числа. Объём информации, заложенный в ответ «да»/«нет», равен одному биту (действительно, ведь бит имеет два состояния: 1 или 0). Итак, для угадывания числа от 1 до 100 нам потребовалось семь бит (семь ответов «да»/«нет»).
Такой формулой можно представить, сколько вопросов (бит информации) потребуется, чтобы определить одно из возможных значений. N - это количество значений, а k - количество бит. Например, в нашем примере 100 меньше, чем 27, однако больше, чем 26. Да, нам могло бы потребоваться и всего 6 вопросов, если бы загаданное число было 28.
Формула Хартли: .
Количество информации (k), необходимой для определения конкретного элемента, есть логарифм по основанию 2 общего количества элементов (N).
Формула Шеннона
Когда события не равновероятны, может использоваться формула Шеннона . , где
Информацио́нная энтропи́я - мера неопределённости или непредсказуемости информации , неопределённость появления какого-либо символа первичного алфавита . При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии -го порядка, см. ниже ) встречаются очень редко, то неопределённость уменьшается еще сильнее.
Для иллюстрации понятия информационной энтропии можно также прибегнуть к примеру из области термодинамической энтропии , получившему название демона Максвелла . Концепции информации и энтропии имеют глубокие связи друг с другом, но, несмотря на это, разработка теорий в статистической механике и теории информации заняла много лет, чтобы сделать их соответствующими друг другу.
Энтропия - это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения.
Формальные определения
Информационная двоичная энтропия для независимых случайных событий с возможными состояниями (от до , - функция вероятности) рассчитывается по формуле
Эта величина также называется средней энтропией сообщения . Величина называется частной энтропией , характеризующей только -e состояние.
Таким образом, энтропия события является суммой с противоположным знаком всех относительных частот появления события , умноженных на их же двоичные логарифмы . Это определение для дискретных случайных событий можно расширить для функции распределения вероятностей .
Определение по Шеннону
Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:
1. мера должна быть непрерывной; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
2. в случае, когда все варианты (буквы в приведённом примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать значение функции;
3. должна быть возможность сделать выбор (в нашем примере букв) в два шага, в которых значение функции конечного результата должно являться суммой функций промежуточных результатов.
Поэтому функция энтропии должна удовлетворять условиям
1. определена и непрерывна для всех , где для всех и . (Нетрудно видеть, что эта функция зависит только от распределения вероятностей, но не от алфавита.)
2. Для целых положительных , должно выполняться следующее неравенство:
3. Для целых положительных , где , должно выполняться равенство
Шеннон показал, что единственная функция, удовлетворяющая этим требованиям, имеет вид
где - константа (и в действительности нужна только для выбора единиц измерения).
Шеннон определил, что измерение энтропии (), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка - имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т. д. (см. цепи Маркова ).
Теорема Шеннона - Хартли
Теорема Шеннона - Хартли в теории информации - применение теоремы кодирования канала с шумом к архетипичному случаю непрерывного временно́го аналогового канала коммуникаций, искажённого гауссовским шумом . Теорема устанавливает шенноновскую ёмкость канала, верхнюю границу максимального количества безошибочных цифровых данных (то есть, информации), которое может быть передано по такой связи коммуникации с указанной полосой пропускания в присутствии шумового вмешательства, согласно предположению, что мощность сигнала ограничена, и гауссовский шум характеризуется известной мощностью или мощностью спектральной плотности. Закон назван в честь Клода Шеннона и Ральфа Хартли .
Рассматривая все возможные многоуровневые и многофазные методы шифрования, теорема Шеннона - Хартли утверждает, что пропускная способность канала , означающая теоретическую верхнюю границу скорости передачи данных, которые можно передать с данной средней мощностью сигнала через аналоговый канал связи, подверженный аддитивному белому гауссовскому шуму мощности равна:
где - пропускная способность канала, бит /с; - полоса пропускания канала, Гц ; - полная мощность сигнала над полосой пропускания, Вт или В ²; - полная шумовая мощность над полосой пропускания, Вт или В ²; - частное от деления отношения сигнала к его шуму (SNR) на гауссовский шум, выраженное как отношение мощностей.
В данной теореме определено, что достичь максимальной скорости (бит/с) можно путем увеличения полосы пропускания и мощности сигнала и, в то же время, уменьшения шума.
Теорема Шеннона - Хартли ограничивает информационную скорость (бит/с) для заданной полосы пропускания и отношения «сигнал/шум». Для увеличения скорости необходимо увеличить уровень полезного сигнала, по отношению к уровню шума.
Если бы существовала бесконечная полоса пропускания, бесшумовой аналоговый канал, то можно было бы передать неограниченное количество безошибочных данных по ней за единицу времени. Реальные каналы имеют ограниченные размеры и в них всегда присутствует шум.
Удивительно, но не только ограничения полосы пропускания влияют на количество передаваемой информации. Если мы комбинируем шум и ограничения полосы пропускания, мы действительно видим, что есть предел количества информации, которую можно было передать, даже используя многоуровневые методы кодирования. В канале, который рассматривает теорема Шеннона - Хартли, шум и сигнал дополняют друг друга. Таким образом, приёмник воспринимает сигнал, который равен сумме сигналов, кодирующего нужную информацию и непрерывную случайную, которая представляет шум.
Это дополнение создает неуверенность относительно ценности оригинального сигнала. Если приёмник обладает информацией о вероятности ненужного сигнала, который создает шум, то можно восстановить информацию в оригинальном виде, рассматривая все возможные влияния шумового процесса. В случае теоремы Шеннона - Хартли шум, как таковой, произведен гауссовским процессом с некоторыми отклонениями в канале передачи. Такой канал называют совокупным белым гауссовским шумовым каналом , так как гауссовский шум является частью полезного сигнала. «Белый» подразумевает равное количество шума во всех частотах в пределах полосы пропускания канала. Такой шум может возникнуть при воздействии случайных источников энергии, а также быть связан с ошибками, возникшими при кодировании. Зная о вероятности возникновения гауссовского шума, значительно упрощается определение полезного сигнала.
Сравнивая пропускную способность канала и формулу Хартли, мы можем найти эффективное число различимых уровней:
Взятие квадратного корня по сути возвращает отношение мощностей к отношению напряжений, таким образом число уровней приблизительно равно отношению среднеквадратичной амплитуды сигнала к шумовому стандартному отклонению. Это подобие в форме между пропускной способностью по Шеннону и формулой Хартли не стоит понимать буквально, что для безошибочной передачи достаточно уровней сигнала. Избыточное кодирование для устранения ошибок потребует большего числа уровней, но предельная скорость передачи данных, к которой можно приблизиться с кодированием, эквивалентна использованию того самого из формулы Хартли.
ИКМ
Передача квантованных значений сигнала с помощью коротких импульсов различной высоты называется амплитудно-импульсной модуляцией (АИМ). Под импульсно-кодовой модуляцией (ИКМ) понимается передача непрерывных функций при помощи двоичного кода.
При кодовой модуляции необходимо передать числа, выражающие величину квантованных отсчетов. Для этого можно воспользоваться двоичным кодом. Числа, подлежащие передаче, надо записать в двоичной системе счисления – это и даст необходимые кодовые комбинации. При помощи n - значных двоичных чисел можно представить чисел. Благодаря квантованию количество чисел, подлежащих передаче, сводится до конечной величины . Если принять шаг квантования за единицу, то будет означать наибольшее квантованное значение. Количество знаков в двоичной кодовой комбинации равно . Если n – не целое, то оно округляется до ближайшего целого числа. На рис. 3 показаны преобразования аналогового сигнала (а) в АИМ (б) и ИКМ (в) для n = 4.
Рис. 3
При выборе шага квантования (или числа ) следует учитывать два фактора. С одной стороны, увеличение числа ступеней квантования увеличивает точность передачи сигнала, с другой – требует удлинения кодовой комбинации (n ). Так для телефонной передачи установлено, что удовлетворительное качество передачи достигается при , т.е. при семизначном коде.
При анализе приема сигналов с импульсно-кодовой модуляцией обычно рассматривают не отношение средних мощностей сигнала и помехи, а отношение половины шага квантования (цена округления) к среднеквадратичному значению помехи . Квадрат отношения
заменяет отношение сигнал – шум.
Пусть число уровней квантования равно . Будем передавать каждое из значений n -значным кодовым числом, составленным из импульсов, квантованных на m уровней (АИМ). Общее число возможных комбинаций равно . Очевидно, что . Пусть шкала уровней симметрична относительно нуля, т. е. разрешенными являются уровни:
Если все уровни равновероятны, средняя мощность сигнала равна
Отсюда шаг квантования равен
откуда
Таким образом, при неизменных мощностях сигнала и помехи выгодно уменьшать основание кода. Наименьшее значение m равно 2 (двоичный код), что соответствует ИКМ. В этом случае т.е. введенная величина совпадает с обычным определением отношения сигнал – помеха.
В обычной АИМ >>1, и в этом случае
Следовательно, ИКМ дает выигрыш в отношении сигнал – помеха в раз.
Какой же ценой достигается этот выигрыш? Если при АИМ за каждый тактовый интервал (отсчет) передается один импульс, то при ИКМ за тот же интервал должны быть переданы n импульсов. При неизменной скважности каждый из этих n импульсов в n раз короче (см. рис. 3), а, следовательно, ширина спектра сигнала в n раз больше, чем ширина спектра сигнала АИМ. Таким образом, за увеличение отношения сигнал – помеха мы расплачиваемся расширением полосы.
Основной цифровой поток DS0
Digital Signal 0 (DS0 или DS-0 ) - основной североамериканский цифровой сигнальный стандарт (64 Кбит/сек кГц и использованием 8 бит импульсно-кодовой модуляции , в результате поток данных составляет 64 кбит/сек. Из-за фундаментальной роли для передачи одного телефонного звонка стандарт DS0 используется как основной в иерархии цифровой мультиплексной передачи в телекоммуникационных системах, используемых в Северной Америке.
С целью уменьшения количества проводов между двумя связанными друг с другом узлами используется мультиплексирование нескольких DS0 в линии с большей пропускной способностью. Линии, в которых мультиплексированы 24 сигнала DS0, получили название DS1, линии с 28 сигналами DS1 - DS3. Переданные по медным проводам DS1 и DS3 соответствуют стандартам T1 и T3 соответственно.
Помимо использования DS0 для голосовой связи, стандарт может поддерживать 20 каналов на 2.4 кбит/сек, 10 каналов на 4.8 кбит/сек, 5 каналов на 9.67 кбит/сек, один канал на 56 кбит/сек, или один канал для передачи данных на 64 кбит/сек.
E0, стандартизированный как ITU G.703 это европейский эквивалент североамериканского DS0 для передачи одного телефонного звонка.
-
17 апреля 2015Виджеты в Dashboard Как закрыть dashboard -
17 апреля 2015Не обнаружен ключ защиты программы 7 -
17 апреля 2015RLS – гибкая и тонкая настройка ограничений доступа к данным
