Что называется опытом в вероятностной теории к шеннона

Введение в теорию информации

Apr 25, 2020 · 9 min read

Индонезийские пещеры острова Борнео дают представление о самой примитивной зарегистрированной форме коммуникации. Около 40000 лет назад, ещё до развития письменного языка, физические иллюстрации на стенах пещеры были наиболее систематическим зарегистрированным способом общения. С течением времени методология записи эволюционировала от наскальных рисунков до сложных алфавитов, предлагая полноценное выражение с помощью сложной структуры называемой язык. В английском языке идеи, столь же чёткие, как “дерево”, и столь же неоднозначные, как “любовь”, выражаются с помощью 26 букв, не имея никакой внутренней ценности кроме той, которую в них вкладывает общество.

Информация в ко н тексте недавно развившейся области определяется как разрешение неопределённости (или неожиданности). Рассмотрим сообщение о существовании дерева. Например, на фиксированном изображении форма, цвет и даже относительный размер соседних деревьев прекрасно видны, но является ли эта информация предельно точной? Относительно. Несоответствие проявляется только при сравнении с дополнительной информацией, предоставленной письменным языком. С неограниченным запасом слов язык предлагает намного более глубокую описательную информацию, которую невозможно увидеть на изображении, например, где дерево было выращено, кем и в какой почве. Различные методы коммуникации подразумевают различия в сообщаемой неопределённости.

Отец теории информации, математик Массачусетского технологического института Клод Шеннон, блистательно представил логический математический способ измерения этого различия в зарегистрированных методах коммуникации: он определил её как энтропию. Энтропия дополняет математический набор инструментов для измерения взаимосвязи между принципами неупорядоченности и неопределённости. Высокий уровень энтропии указывает на высокий уровень неопределённости информации. Или, на практике, на более высокое число возможных выводов функции. Прежде чем перейти к современной формуле измерения информации, вернёмся назад в 1920–е, когда Ральф Хартли вывел первую формулу на основе работ Генри Найквиста.

Ранняя энтропия — мера неопределённости

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

На графике по оси y, H(x), отображается энтропия для символа с двумя возможностями (двоичная). Заметьте, что энтропия, или неопределённость, максимальна (равна 1) в середине графика. Объяснение интуитивно понятно: когда мы бросаем монетку, неопределённость исхода максимальна, когда монета находится в воздухе. Соответственно энтропия минимальна (равна 0) на противоположных концах оси x, когда мы точно знаем значение двоичного символа. Имея это в виду, можно смело утверждать, что подбрасывание монетки, вопросы типа “да/нет”, логические значения и двоичные числа (0 или 1) математически эквивалентны — на графике все они представлены в терминах теории информации.

Символ с двоичным свойством, называющийся “бит”, является базовой единицей энтропии, используемой во всей теории информации.

Хронологически термин “бит” не был общепринятым до довольно позднего времени, однако мы используем его сейчас для простоты понимания, поскольку приближаемся к современной теории информации. Забавный факт: слово “бит” образовано от слов binary digi t — двоичное число.

Резонно предположить, что предполагаемое сообщение с решением за один шаг (один бит, бросок монеты, ответ на вопрос типа “да/нет”, логическое значение неопределённости) имеет меньшее значение энтропии, чем решения в два или более шагов. Например, рассмотрим бросок монеты. При попытке определить, выпадет орёл или решка, для разгадки значения “выпал орёл?” достаточно одного бита. В любом случае мы уверены в том, что значение будет получено с первой попытки. Энтропия этой задачи равна единице, поскольку ответ определяется за один шаг:

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

Что, если отправить сообщение из трёх символов (все биты)?

Что, если отправить сообщение с единственным не двоичным символом?

Теперь, допустим, мы хотим отправить один символ, что означает, что символ может быть любой из двадцати шести букв (1/26). Каково будет значение энтропии на этот раз? То есть, на сколько вопросов типа “да/нет” мы должны ответить, чтобы определить, например, букву J?

Проще всего запрашивать в алфавитном порядке “является ли X предполагаемой буквой?”. Например, “нам нужна А буква? Как насчёт B? Или C?…”. С помощью этого метода для определения одного символа в среднем нам понадобится 13 вопросов типа “да/нет” (или 13 бит энтропии). Однако здесь есть большая оговорка: для измерения информации необходим наиболее эффективный способ присвоения значения символам. В отличие от индивидуального поиска по порядку, мы заимствуем концепцию алгоритма двоичного поиска. При повторном поиске буквы J спрашиваем, находится ли искомая буква в первой половине алфавита? Да. Далее делим оставшийся массив пополам и спрашиваем, попадает ли искомый символ в первые 6 букв (A-F)? Нет. И так далее, пока не найдём искомый символ — J. Заметьте, что подобный способ поиска значения гораздо более эффективен. В отличие от среднего значения из 13 вопросов “да/нет”, со вторым методом нам никогда не понадобится более 5 вопросов (иногда только 4).

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

Формула выше даёт приблизительное количество энтропии (4,7 бит), связанное с отправкой одного случайного символа алфавита. Как заключил Ральф Хартли в своей выдающейся статье “Передача информации”:

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

Его раннее определение информации немного отличалось в нотации. Он определил H (информацию) как H = n log (s), где H — это информация, n — количество символов (букв, чисел и т.д.), а s — количество различных символов, доступных при каждой выборке (по сути, длина области сообщений).

Всё ещё не совсем современная теория информации, но мы уже твёрдо установили следующее:

До этого момента мы предполагали, что каждое значение в наборе символов является случайным образом дискретным, однако на самом деле это целесообразное упрощение. Как мы знаем, реальность не так аккуратна, и значения символов не эквиваленты. Существуют органичные, измеримые модели нашего языка и других форм коммуникации. В качестве быстрого мысленного эксперимента вычислим количество букв “e” в предыдущем предложении. Является ли это распределение равномерным распределением 1/26?

Когда символы не случайны — цепи Маркова

Перенесёмся в 1948 год, когда отец современной теории информации, Клод Шеннон, в своей новаторской работе “Математическая теория связи” предположил, что существуют модели в коммуникации, которые можно использовать для вывода одного и того же сообщения или значения в несколько шагов, то есть битов.

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

Другими словами, предыдущее значение делает следующее менее неопределённым, то есть уменьшает энтропию. Наилучшим примером является предсказуемость появления буквы ‘U’ после ‘Q’ в английском письменном языке. Если за ‘Q’ следует ‘U’ в 90% случаях, потенциальный выход следующей буквы больше не находится в равновесии со всей системой, он смещается к значению ‘Q’ со скоростью 90%.

Это создаёт систему, в которой следующее значение зависит от предыдущего. Русский математик Андрей Марков вывел это в своём революционном доказательстве, которое назвали в его честь как “Цепь Маркова”. В нём он заявляет, что вероятность будущих значений, зависящая от предыдущих, фиксирована в их вероятности. Он доказал, что в течение непрерывного функционирования системы, результаты будут соответствовать их статистической вероятности.

С учётом зависимости “За ‘Q’ следует ‘U’ с вероятностью 9/10 ‘U’” (P(Xi)), энтропия, или неопределённость появления ‘U’ за ‘Q’, равна H(X) = 0.13 бит. Энтропия любого значения полностью случайного алфавита равна H(X) = 4.7 бит. С этим подходом энтропия уменьшается на поразительные 4.57 бита. Вместо деления алфавита пополам на первом этапе вопрос, разрешающий большинство информационных состояний, будет сформулирован как “Значение равно ‘U’?”. В 90% случаев это будет правдой, а энтропия будет только 1 бит, что позволяет убрать лишние вопросы и понизить общую энтропию системы. Благодаря компьютерному анализу миллионов текстов, были выведены стандартные распределения каждой буквы английского языка. Это стандартные вероятности, которые можно использовать для независимых событий. Принимая во внимание зависимые выходные значения (цепь Маркова), были установлены также частотные зависимости повторения букв.

Повторный вывод формулы информации/энтропии

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

Однако вышеприведённая формула предполагает равномерное распределение, что, как мы знаем благодаря цепи Маркова, не является истиной. Чтобы учесть это, в формулу нужно добавить умножение на частотную вероятность каждого значения символа x, ( p(x)):

Наконец, нужно заменить n внутри логарифма. Мы рассчитываем количество вопросов типа “да/нет”, необходимых для получения каждого отдельного символа, а не общего результата. Продолжая пример с алфавитом, мы знаем из цепи Маркова, что для угадывания символа e или z требуется неравное количество битов. Следовательно, для каждой суммы нам нужно число конкретных результатов, и мы знаем, что это не 26, а ( 1 / p(x)):

Формула, которую мы только что вывели — это формула, выведенная Клодом Шенноном и сделавшая его отцом теории информации. Он немного переставил символы выше. Вот это уравнение лежит в основе современной теории информации:

H(x) — это энтропия, мера неопределённости, связанная с установленной переменной X. P(x) — это вероятность вывода x в переменной X. И log(1/p(x)) по основанию 2 — это количество битов, необходимое для расшифровки вывода x переменной X. Ещё раз: базовая единица, которой равна H(x), определяется в битах.

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

Напомним, что мы рассчитали энтропию H(x) = 4.7 для единичного символа алфавита. Давайте сравним ее с H(x), вычисленной по обновлённой формуле:

Как видим из суммы справа внизу, это интуитивное значение проверяется итоговым значением энтропии H(x) = 4.18. Уже с этой формулой энтропии теория информации и её приложения развиваются всё быстрее с 1950-х.

Посмотрим на приложения

Изученные здесь концепции, построенные на математическом понятии, узнаваемы и мощны в цифровую эпоху. Вероятно одним из наиболее распространённых и влиятельных применений теории информации является сжатие информации без потерь. Эта форма сжатия используется в записях баз данных, текстовых файлах, изображениях и видеофайлах. В этой форме данные можно полностью восстановить до исходного состояния. Используя принципы энтропии Шеннона и цепи Маркова,можно получить безошибочную информацию. Эта способность к сжатию позволила массово производить устройства, способные хранить огромные объёмы данных. Особенно впечатляет это в музыкальных файлах. В ранние годы звукозапись опиралась на виниловые пластинки — несжатый формат информации. Запись на пластинке хранит альбом в несжатом состоянии без потерь. С современными технологиями музыкальные файлы сжимаются и содержат биты, относящиеся к высоте, громкости, резонансу и т.д. Другой убедительный пример — это увеличение возможностей аппаратного хранения.

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

Источник

Информационная теория

Обработка информации — важная техническая задача, чем, например, преобразование энергии из одной формы в другую. Важнейшим шагом в развитии теории информации стала работа Клода Шеннона (1948). Логарифмическое измерение количества данных было первоначальной теорией, и прикладными задачами по коммуникации в 1928 году. Наиболее известным является вероятностный подход к измерению информации, на основе которого представлен широкий раздел количественной теории.

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

Основная теорема Шеннона о кодировании

Важный практический вопрос при обработке информации — какова мощность системы передачи данных. Можно получить определённый ответ, используя уравнение Шеннона. Оно позволяет точно понять информационную пропускную способность любого сигнального канала. Формула Шеннона в информатике: I = — (p1log2 p1 + p2 log2 p2 +. + pN log2 pN)

Основная теория Шеннона о кодировании для дискретного канала с помехой, приведённая здесь без доказательства, аналогична теореме канала не имеющего помех: если источник данных с энтропией H (Z), а канал связи имеет ширину полосы C, то сообщения, сгенерированные источником, всегда могут быть закодированы так, чтобы их скорость передачи vz была произвольно близка к значению: vzm = C | H (Z).

Не существует метода кодирования, который бы позволял передавать со скоростью, превышающей vzm, и с произвольно низкой вероятностью ошибки. Другими словами, если поток информации: H ‘(Z) = vz * H (Z) C он не существует.

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

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

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

Это приводит к замечательному выводу:

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

Условие применения формулы Шеннона — избыточность, создаёт предсказуемые отношения между различными участками сигнального устройства. Хотя это снижает эффективность передачи информации в системе, но помогает отличать детали сигнала от случайного шума. Здесь обнаружена максимально возможная информационная пропускная способность системы. Поэтому нужно избегать избыточности и позволять сигналу иметь «непредсказуемые» качества, которые делают его статистически похожим на случайный шум.

Передача сигналов

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

Это означает:

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

Это означает, что в такой системе, большинство сообщений будет одинаковый уровень мощности. В идеале каждое ИС должно иметь одинаковый, максимально возможный уровень мощности. На самом деле можно повернуть этот аргумент с ног на голову и сказать, что «типичны» только сообщения со средними силами, подобными этому максимуму. Те, что обладают гораздо более низкими способностями, необычны — то есть редки.

Определённое уравнение

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

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

Стоит рассмотреть теперь разделение этого диапазона на полосы одинакового размера. (т. е. каждая из этих полос будет охватывать ИС.) Чтобы предоставить другую метку для каждой полосы, нужны символы или цифры. Поэтому всегда можно указать, какую полосу занимает уровень напряжения в любой момент с точки зрения B-разрядного двоичного числа. По сути, этот процесс является ещё одним способом описания того, что происходит, когда берут цифровые образцы с B-разрядным аналоговым преобразователем, работающим в общем диапазоне.

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

Уравнение Шеннона может использовать:

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

Хартли понимал информационное получение как подбор одного вида данных из набора равновероятного сообщения и определил объём, содержащейся ВС, как логарифм N. Выполняются примеры решения по формуле Хартли в информатике: N = mn.

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

В этом случае средний объём информации, переносимой одним символом, можно считать расчётным: J (Z; Y) = Хапр (Z) — Хапест (Z) = Хапр (Y). Поскольку функция H (Y) = H (Z) и H (Y / Z) = 0, а индекс max = Hmax (Y) — максимальная энтропия источника класса сигнала, возникающая в результате распределения символов Y: p (y1) = p (y2) = … = p (ym) = 1 / My, т. е. Hmax (Y) = logaMy.

Следовательно, главная дискретная ширина полосы таблицы без информации о помехах в единицу времени равна: Cy = Vy • max = Vy • Hmax (Y) = Vy • logaMy или записываться Ck = Vk • logaMy. Где буква Mk — должно быть максимально возможное количество уровней, разрешённых для передачи по этому каналу (конечно, может обозначаться Mk = My).

Согласно теореме, метод кодирования онлайн, который может использоваться и позволяет:

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

Источник

Инструменты сайта

Основное

Навигация

Информация

Действия

Содержание

Статус документа: черновик.

Теория информации по Шеннону

Энтропия

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

Пример. Предположим, что найденная Иваном-царевичем лягушка в течение минуты либо

После приведения этой формулировки, Шеннон пишет:

Происхождение слова «энтропия» ☞ ЗДЕСЬ.

Свойства энтропии

Проанализируем теперь формулу для энтропии.

Условная энтропия

Проиллюстрируем результат теоремы на примере, который подробно будем разбирать во всех последующих пунктах. Источник приведенных в нем данных ☞ ЗДЕСЬ.

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

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

Понятие об информации

Информационная избыточность

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

Частота встречаемости букв в обычном (неспециальном) тексте (без учета пробелов) [2]:

Пример [обезьяна за клавиатурой]. Известна теорема о бесконечных обезьянах: абстрактная обезьяна, ударяя случайным образом по клавишам печатной машинки 7) в течение неограниченно долгого времени, рано или поздно напечатает любой наперёд заданный текст (например «Войны и мира»). В указанной ссылке приводятся оценки времени наступления этого события. Следующие примеры 8) показывают, что может произойти, если обезьяна будет бить по клавиатуре специально сконструированной машинки, в которой клавиши соответствуют биграммам, триграммам и т.п. русского языка и при этом размеры клавиш пропорциональны частотам встречаемости в русском языке (а обезьяна будет чаще ударять по большим клавишам).

Приближения нулевого порядка (символы независимы и равновероятны):

ФЮНАЩРЪФЬНШЦЖЫКАПМЪНИФПЩМНЖЮЧГПМ ЮЮВСТШЖЕЩЭЮКЯПЛЧНЦШФОМЕЦЕЭДФБКТТР МЮЕТ

Приближение первого порядка (символы независимы, но с частотами, свойственными русскому языку):

ИВЯЫДТАОАДПИ САНЫАЦУЯСДУДЯЪЛЛЯ Л ПРЕЬЕ БАЕОВД ХНЕ АОЛЕТЛС И

Приближение второго порядка (частотность диграмм такая же как в русском языке):

ОТЕ ДОСТОРО ННЕДИЯРИТРКИЯ ПРНОПРОСЕБЫ НРЕТ ОСКАЛАСИВИ ОМ Р ВШЕРГУ П

Приближение третьего порядка (частотности триграмм такие же как в русском языке):

С ВОЗДРУНИТЕЛЫБКОТОРОЧЕНЯЛ МЕСЛОСТОЧЕМ МИ ДО

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

СВОБОДНОЙ ДУШЕ ПРОТЯНУЛ КАК ГОВОРИТ ВСПОМНИТЬ МИЛОСТЬ КОМНАТАМ РАССКАЗА ЖЕНЩИНЫ МНЕ ТУДА ПОНЮХАВШЕГО КОНЦУ ИСКУСНО КАЖДОМУ РЯСАХ К ДРУГ ПЕРЕРЕЗАЛО ВИДНО ВСЕМ НАЧИНАЕТЕ НАД ДВУХ ЭТО СВЕТА ХОДУНОМ ЗЕЛЕНАЯ МУХА ЗВУК ОН БЫ ШЕЮ УТЕР БЕЗДАРНЫХ

Приближение второго порядка на уровне слов. Переходные вероятности от слова к слову соответствуют русскому языку, но «более дальние» зависимости не учитываются:

ОБЩЕСТВО ИМЕЛО ВЫРАЖЕНИЕ МГНОВЕННОГО ОРУДИЯ К ДОСТИЖЕНИЮ ДОЛЖНОСТЕЙ ОДИН В РАСЧЕТЫ НА БЕЗНРАВСТВЕННОСТИ В ПОЭЗИИ РЕЗВИТЬСЯ ВСЕ ГРЫЗЕТ СВОИ БРАЗДЫ ПРАВЛЕНИЯ НАЧАЛА ЕГО ПОШЛОЙ

Результатом оказывается кодовая таблица

А теперь перейдем к фундаментальному результату теории кодирования, связав код Шеннона-Фано с понятием энтропии.

Пример. Обратимся к рассмотренному ☞ ЗДЕСЬ примеру сокращенного русского языка

Если же перейти к алфавиту, составленному из биграмм

Ои | то | ми | и_ | о_ | им | и_ | оо | ои | тм | и_ | о_ | о_ | о_ | оо | ии | им | то | ми | им | от | ои | м_ | …

Пропускная способность канала связи

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

Дополнительно вводятся ограничения на допустимые к передаче последовательности — например, запрет двух пробелов подряд между словами. ♦

Пример. Для рассмотренного выше «телеграфного» примера имеем разностное уравнение в виде

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

Статья не закончена!

Источники

[1]. Шеннон К. Математическая теория связи. (Shannon C.E. A Mathematical Theory of Communication. Bell System Technical Journal. — 1948. — Т. 27. — С. 379-423, 623–656.)

[2]. Яглом А.М., Яглом И.М. Вероятность и информация. М. Наука. 1973.

Источник