За любыми страшными и непонятными математическими формулами скрывается простой и понятный смысл. Главное, к чему надо прилагать усилия, это то, чтобы декодировать этот смысл из многоумных математических формул, которые подобны кодам шифрования, и выразить его обычным человеческим языком. К сожалению, зачастую такой поиск и тщательная выверенная формулировка такого смысла подменяются у нас свободной литературной интерпретацией, а до проверочных расчетов дело вообще не доходит.
Удивительно что на Хабре нет статьи посвященной анализу теоремы Шеннона-Хартли и тому, какой смысл она несет.
Статья подготовлена по материалам из книги Бернарда Скляра "Цифровая связь", 2003 г.
Содержание:
Задачи и проблемы построения эффективных-экономных систем связи
Что можно определить как математику компромиссов
Несерьезная интерпретация теоремы Шеннона-Хартли из учебных материалов отечественных ВУЗов.
Теорема Шеннона из проверенного источника
Энтропия как мера информативности
Отличие дискретизации по Найквисту от дискретизации по Шеннону
Пример со сдвигом за пределы или как и когда можно организовать надежный прием глубоко под шумом.
Задачи и проблемы построения эффективных-экономных систем связи
Задачи построения систем цифровой связи пытаются примирить между собой несколько противоположностей. Основной конфликт происходит из того факта, что передача большего объема информации ведет к необходимости увеличения мощности (энергии в единицу времени) на единицу этой информации. Энергия требуется чтобы преодолеть расстояние и связанные с этим потери энергии по пути, а также чтобы в точке приема сигнал-сообщение было различимо на фоне шума который неизбежно присутствует в нашем реальном-материальном мире.
Казалось бы, очевидно, что уровень интенсивности сигнала (в чем бы эта интенсивность ни выражалась: в вольтах, в единицах давления для звука, ...) должен быть выше чем уровень интенсивности шума в точке приема. Оказывается, можно математически доказать, что уровень интенсивности сигнала в точке приема может быть гораздо ниже, чем уровень шума, и при этом связь, то есть способность системы-канала связи обеспечить надежную (с каким угодно малым, то есть с заданным уровнем вероятности появления ошибок) передачу единиц информации и точное воспроизведение-детектирование их в приемнике можно поддерживать на заданном уровне надежности.
Довольно часто мы можем наблюдать очень эмоциональные дискуссии о том, чем отличаются данные от информации, например, и почему их надо обязательно различать, но с точки зрения передачи информации и/или данных такие дискуссии выглядят вроде бы неконструктивно так как уводят в сторону от того, что действительно важно при построении систем передачи того, что можно называть как информацией, так и данными, или сообщениями, или даже кодами или сигналами из определенного кодового/сигнального набора. Возможно, мне удалось внести ясность в этот вопрос, при анализе понятия энтропии введенной Шенноном далее.
В общем, можно отметить, что систему передачи информации не интересует наличие или отсутствие смысла в информации, которую эта система должна передать из пункта А в пункт Б. Система передачи информации проектируется и строится, чтобы информация не потерялась и не получила искажений при передаче, независимо от того какую смысловую или даже эмоциональную нагрузку содержит или не содержит в себе эта информация. Системы передачи информации тестируются с помощью информации (наборов сообщений), которые ни для кого не имеют смысла, но определяют граничные режимы функционирования таких систем чтобы доказать надежность функционирования в штатных режимах.
Что можно определить как математику компромиссов.
Любая система, которая работает и в которой присутствует случайный процесс, а шум — это как раз такой случайный процесс, такая система должна рассчитываться и проектироваться в терминах теории вероятности и, вообще говоря, всегда будет оставлять место случайности. Но, как известно, в основе всего нашего мироздания лежит принцип неопределенности Гейзенберга, но это не мешает, например, солнцу с завидной стабильностью тысячи лет подниматься на востоке утром и заходить на западе вечером. Оказывается, законы, которые управляют вероятностями, вполне себе стабильны при достаточном количестве однотипных случайных событий, которые можно еще и целенаправленно сгенерировать и соответствующим образом усреднить. Математика, которая позволяет построить план такой генерации событий, связанный с методами усреднения и использования уже стабильных результатов, полученных на фоне случайных процессов и/или событий, я и предлагаю называть математикой компромиссов. Название «Математика компромиссов» — это не просто красивое название для такого направления математики, это название акцентирует внимание на том, что такая математика направлена именно на поиск компроммисов обычно между тем, чтобы преодолеть случайности так называемым (1) методом грубой силы, когда мы просто значительно увеличиваем уровень детерменированных сигналов над фоном случайных сигналов, и (2) методом точнейшей организации системы таким образом, чтобы случайные воздействия минимально смешивались и/или влияли на полезные сигналы или чтобы последствия случайных событий компенсировались за счет правильно организованной статистики наложения полезных воздействий к нестабильной среде, через которую происходит передача информации.
Учебником такой математики компромиссов я бы выбрал работу широко известного в узких кругах разработчиков цифровых систем связи Бернарда Скляра «Цифровая Связь» доступную на нашем родном языке в хорошем переводе с родного автору американского (фактически английского). То есть в любом случае очень рекомендую эту книгу всем ценителям практической математики и практического-же применения теории информации, книга также является большим справочником по фундаментальным трудам в большинстве смежных научных областей.
Например глава в которой излагается теорема Шеннона-Хартли начинается с такого вступления:
Системные компромиссы – это неотъемлемая часть всех разработок систем связи. ... Существуют несколько сдерживающих факторов и теоретических ограничений, которые неизбежно влекут за собой компромиссы в любых системных требованиях.
К сожалению в нашей национальной высшей инженерной школе достаточно хорошо освещаются только содержание первых трех глав из этой книги, содержание остальных глав если и преподается в каком-то виде, то очень фрагментарно-спорадически без практического приложения, только как литературный пересказ и интерпретация исходных выверенных формулировок жестко связанных с соответствующими математическими формулами без каой либо системной связи с этими формулами. Тут я не претендую на какую-то свою достаточную осведомленность, конечно! Более того, я даже был бы рад узнать о каком-то примере который бы опроверг это мое мнение.
Несерьезная интерпретация теоремы Шеннона-Хартли из учебных материалов отечественных ВУЗов.
Как интерпретируется теорема Шеннона можно посмотреть например на таком примере взятом из учебного пособия одного из наших ВУЗов:
Теоретической основой построения эффективных кодов является 1-я теорема кодирования К. Шеннона, доказывающая, что для канала связи без помех всегда можно создать систему экономного кодирования дискретных сообщений, у которой среднее количество двоичных кодовых сигналов на один символ сообщения будет приближаться как угодно близко к энтропии источника сообщений.
Базой для помехоустойчивого кодирования является 2-я теорема кодирования К. Шеннона, в которой утверждается, что для канала связи с помехами всегда можно создать систему кодирования, при которой сообщения будут переданы со сколь угодно высокой степенью верности, если только производительность источника не превышает пропускной способности канала связи.
Такие формулировки явно претендуют на литературный талант наследников Пушкина и Толстого, но совершенно ничего не дают с точки зрения решения реальных инженерных задач и расчета технических параметров реальных связных систем.
Как видите у нас обычно преподают теоремы Шеннона как достаточно пространную интерпретацию без математических формул и без вывода фундаментальных констант, таких как значение отношения Eb / N0 = 0.693 или (-1.6) дБ называемое пределом Шеннона.
Как видите авторы такого пособия не беспокоятся о том что студенты могут спутать термин «энтропия» с одноименным термином который широко используется в статистической механике (в физике), и не приводят даже математической формулы для вычисления величины определенной под этим термином.
Что уж говорить о том факте, что никто не акцентирует внимание студентов, что сложность теории информации по Шеннону связана не столько со сложностью разработанного и применяемого мат-аппарата, а с тем что разные термины и значения параметров, ими обозначаемые, происходят из разных устройств, из которых состоит система связи, где как минимум надо различать параметры определенные для источника-передатчика информации и приемника-потребителя информации. Например, в пределе Шеннона фигурируют энергия на бит сигнала и мощности шума на входе приемника (а не на выходе передатчика). Внимание к подобным деталям поможет нам, например, понять, что в условиях, когда энергия на входе приемника связана с энергией излучения передатчика нелинейно, например обратным степенным законом, квадратичным или кубическим, то повышение этой энергии становится очень затратной инженерной задачей.
Теорема Шеннона из проверенного источника
Теорема Шеннона на самом деле правильно записывается вот так (скопировано из [1]):
То есть как компактная математическая формула примерно равная по сложности формуле гравитации в физике,например. Эта формула устанавливает связь и зависимость пропускной способности канала С (выраженной в битах в секунду если логарифм берется по основанию 2, а ширина полосы W выражена в герцах) от:
ширины полосы канала W;
средней мощности принятого сигнала S;
средней мощности гауссового шума N
для каналов с аддитивным белым гауссовым шумом.
Смысл формулы в том, что чтобы определить, сколько бит в секунду мы сможем обеспечить при наличии данного конкретного канала, нам надо измерить строго определенные в данной формуле характеристики этого канала именно в точке приема и, видимо, посмотреть закономерности, влияющие на управление этими характеристиками из точки передачи. Как видите задача становится не такой простой когда мы учитываем сложность системы связи, связанную с тем, что ее компоненты разнесены в пространстве.
Предел Шеннона является важным следствием из этой теоремы-формулы. Оказывается существует предельное значение отношения энергии полезного сигнала на количество бит передаваемой информации в секунду и мощности шума на герц полосы пропускания. Тут кстати неплохо вспомнить что герц это обратная величина к времени 1Гц=1 / сек, то есть фактически мощность шума на герц это, в то же время, мощность шума в единицу времени. Двойственность рассмотрения всех величин в теории информации во временной и в частотной области тоже создает определенные сложности в понимании этой теории и в адекватном применении на практике.
Простыми словами, предел Шеннона говорит о том, что если амплитуда сигнала меньше чем примерно 0.83 (догадайтесь, откуда взялся коэффициент, посчитаем ниже) от средней амплитуды шума, сигнальные сообщения будут приходить (восприниматься в приемнике) с ошибками, которые невозможно исправить, даже если сигналы, которые используются для передачи значений битов, будут очень длинными (то есть если вы передаете один бит за час или за сутки, за год), то есть никакое накопление сигнала и усреднение за время этого сигнала, какой бы он ни был продолжительный, не позволит нам избавиться от возможной ошибки при приеме даже одного бита в год (например).
Для тех, кто учился по программам, подобным той, из которой я скопировал «определения» «теорем Шеннона», придется пояснить что число 0.83 (примерно) — это тоже значение — предел Шеннона только пересчитанное для амплитуд сигнала (напряжений для электронных сигналов), потому что отношения мощностей можно выразить как квадрат отношения амплитуд, соответственно отношение амплитуд находится как корень квадратный из отношения мощностей: 0.83 = корень квадратный от(Eb / N0 = 0.693).
Но Шеннон также предложил дополнительную формулу, которая все-таки позволяет уходить ниже им же открытого предела.
Эта формула также расширяет понятие энтропии источника сообщений, изначально введенной чтобы оценить среднее количество информации, приходящееся на один выход источника.
Здесь требуется пояснение относительно словосочетания «один выход источника», взятого из переведенной версии книги Скляра. На самом деле более правильным было бы говорить "одиночный выход источника", имеется в виду один из множества генерируемых источником передаваемых сообщений-сигналов, с помощью которых кодируется значение передаваемых битов.
Здесь уместно будет вспомнить, что цифровая связь подразумевает передачу сигналов из строго определенного набора сигналов. Если у нас в наборе только два сигнала, то выходом источника на каждом такте работы системы связи будет один из этих двух сигналов, которые уносят значение очередного бита, выбранного в передатчике в канал связи и далее в приемник. Можно определить 4-ре сигнала, и тогда в эфир будет уходить один из четырех сигналов на каждом такте, который кодирует-переносит значение двух битов. Очевидно что выбор в пользу количества сигналов не кратного степени двойки будет неэффективным.
Энтропия как мера информативности
Но вернемся к понятию энтропии источника сообщений. Если одиночный выход источника данных определить как очередное поступившее событие со своим значением для передачи (часто упоминается как символ, но нам важно именно то, что это значение конечного двоичного числа как результат некоторого события). Так вот Шеннон обращает наше внимание на то, что последовательность таких значений из источника данных-информации будет иметь какой-то смысл как информация только если эти значения хоть как-то разрешают неопределенность в выборе следующего значения приемником, и информация – это на самом деле нечто большее чем просто набор каких-то значений. Информацию в этом случае можно определять как устранение неопределенности. Математически устранение неопределенности должно начинаться с определения этой неопределенности (как бы странно это ни звучало!) – это значение вероятностей появления нуля и единицы соответственно. Информация характеризуется тем, насколько непредсказуемым и неожиданным может быть следующее сгенерированное значение источником для того, кто ожидает результат этого события в точке приема. Талант ученого и инженера заключается в том чтобы что-то невнятное и обтекаемое обернуть и зафиксировать с помощью четких математических формулировок, в идеале в виде математической формулы. В книге Скляра энтропию источника сообщений называют средним количеством информации в одиночном выходе, я думаю, не будет ошибкой называть энтропию мерой информативности атомарной посылки от передатчика к приемнику.
Интересно, что введение понятия энтропия все же разрешает давнюю мечту сторонников разделения понятий "данные" и "информация", ведь если энтропия это мера информативности, то можно сказать что данные, которые обладают достаточной энтропией несут в себе информацию. Соответственно данные которым не присуща энтропия нельзя называть информацией.
Таким образом, Шеннон вводит энтропию или меру информативности значений в сообщениях из данного источника информации. Такая мера может быть отнесена к конкретному источнику или ко всем источникам которые генерируют определенный тип информации (например речь определенного языка), то есть к определенному типу данных.
Вот так вот выглядит формула:
Чтобы окончательно осознать значение термина "энтропия источника сообщений" я бы предложил внимательно проанализировать роль логарифма в этой формуле и просто посчитать: если вы попробуете просто посчитать, чему равна энтропия источника при разновероятных значениях бита, одно из которых ноль, другое единица вам станет все понятно! Иногда нужно просто посчитать по формуле, чтобы осознать, как хороша эта формула. Это то, что можно назвать математическим чудом убеждения.
Но формула 9.10, которая приведена чуть выше, намного сложнее, считать придется в два раза больше, а потом еще сопостовлять результаты расчетов. Но если вы сможете пройти это испытание ваша жизнь никогда больше не останется преждней! Вы доберетесь до истины!
А истина эта заключается в том что значения в источнике (передатчике) сигнала и в приемнике должны быть связаны если не детерменированно то с некоторой вероятностью, и тогда возможно чудо! Чудо заключается в том, что по неточным значениям в приемнике можно с какой угодно точностью-вероятностью судить о том, что было сгенерировано-переданно в передатчике-источнике сигнала и восстановить ряд значений, которые кодирует сигнал! Это конечно чудо инженерной мысли, далее, буквально спустя один короткий параграф, мы коротко посмотрим пример практического применения этого чуда.
Отличие дескритизации по Найквисту от дескритизации по Шеннону
Многие путают теорему Найквиста-Котельникова и теорему Шеннона-Хартли, или считают что это теоремы примерно об одном и том же, и поэтому полезно подсветить принципиальную разницу между этими теоремами.
Но сначала надо заметить что тут действительно есть причина спутать эти теоремы, так как обе эти теоремы – это теоремы о дискретизации сигналов по времени в некотором приближении. Принципиальная разница заключается в том что теорема Найквиста (если мы начали говорить о Шенноне, логично вспоминать в первую очередь про Найквиста, по моему) теорема Найквиста рассматривает дискретизацию любого аналогового сигнала. Теорема Шеннона вообще говоря рассматривает не дискретизацию какого-то сигнала, а формирование дискретного сигнала, который состоит из элементарных сигналов (аналоговых дискретов), которые формируют суммарный аналоговый сигнал пригодный (наиболее подходящий) для извлечения из него цифровой информации в приемнике.
То есть, если коротко, теоремы отличаются так же как дискретизация сигнала отличается от формирования (генерации) специального сигнала, несущего цифровую информацию, которая сама по себе дискретна по определению.
Пример со сдвигом за пределы, или как и когда можно организовать надежный прием глубоко под шумом.
Математика интересна тем, что позволяет нам выходить за пределы привычного восприятия мира.
Можно ли поверить, что возможно организовать уверенный прием данных с помощью сигнала, который по мощности в 10 (десять!) раз меньше, чем мощность аддитивного сопровождающего шума. То есть, глядя на смесь сигнал-шум на осциллографе мы фактически не сможем увидеть сигнал - только шум! Ведь сигнал в корень из 10-ти, в более чем в три раза меньше по амплитуде чем шум (это вам не 0.83! Это 0.333 – чуствуете разницу?). Поверить, конечно, нельзя, но можно рассчитать и реализовать систему, которая такой уверенный прием все-таки обеспечивает. Система связи с такими параметрами оказывается вполне работоспособной, и все это благодаря теореме Шеннона, точнее, благодаря системе понятий-методов измерения-организации систем связи определенных-введенных Шенноном!
В рамках главы, посвященной теореме Шеннона-Хартли, рассматривается практическая задача (из Примера 9.3. из книги Скляра).
Покажите каким образом коррекция неоднозначности по Шеннону может помочь разрешить противоречие для двоичной системы с модуляцией PSK (вы знаете что такое модуляция PSK? Нет? Читайте Бернарда Скляра сначала!), если энтропия источника равна 1 бит/символ. Пусть рабочая точка на графике зависимости вероятности появления битовой ошибки от Eb / N0 при когерентном детектировании M-арных сигналов для случая ортогональных сигналов соответствует Eb / N0 = 0.1 (-10 дБ).
Оказывается что вероятность битовой ошибки, равная PB = 0.33, при таком типе модуляции (PSK) и при таком малом отношении сигнал/шум Eb / N0 = 0.1 (-10 дБ) все еще не так высока как можно было бы вообразить. В этом смысле фазовая манипуляция очень эффективна с точки зрения устойчивости к помехам (читайте соответствующие параграфы книги Скляра).
Далее мы можем выяснить, что чтобы преодолеть неоднозначность, которую создает такая вероятность битовой ошибки PB = 0.33 нам нужно добавить на каждые 85 полноценных(с единичной энтропией) бит 915 избыточных бит, которые будут компенсировать вносимую шумовую энтропию канала, и связь будет работать даже при таком низком отношении сигнал/шум. Соотношением можно управлять, например можно иметь 8 информационных бит и 92 избыточных. Существует уже огромное количество систем связи, которые реализуют эти принципы и их можно проверить, измерить параметры и убедиться на практике, что вся эта теория прекрасно работает.
В общем, я как всегда не предлагаю верить мне на слово. Читайте первоисточники, делайте свои модельные расчеты, изучайте существующую матчасть.
Буду рад, если какие-то мои альтернативные формулировки помогут кому-то разобраться с этой сложной темой и сориентироваться в достаточно большом потоке не очень качественных материалов по этой теме.
Литература.
1. Скляр, Бернард. Цифровая связь. Теоретические основы и практическое применение. 2003.