Момент очередного отсчета определяется выполнением равенства 4 страница

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

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

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

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

Для достижения определенных целей в указанный дискретный канал могут быть введены кодирующие и декодирующие устройства. При этом получаем дискретный канал связи, на вход которого поступают сообщения z, а выходом являются сообщения w, направляемые адресату. Отметим, что непрерывные сообщения z(t) путем дискретизации и квантования всегда можно преобразовать в дискретные и, таким образом, перейти от непрерывного канала к дискретному.

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

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

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

§ 4.2. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ ИСТОЧНИКА ДИСКРЕТНЫХ СООБЩЕНИЙ

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

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

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

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

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

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

Цепь Маркова порядка n характеризует последовательность событий, вероятности которых зависят от того, какие n событий предшествовали данному. Эти n конкретных событий определяют состояние источника, в котором он находится при выдаче очередного знака. При объеме алфавита знаков l число R различных состояний источника не превышает . Обозначим эти состояния через , а вероятности выбора в состоянии знака — через . При определении вероятности естественно предположить, что к моменту выдачи источником очередного знака известны все знаки, созданные им ранее, а следовательно, и то, в каком состоянии находится источник.

Если источник находится в состоянии , его частная энтропия H() определяется соотношением

Усредняя случайную величину H() по всем возможным состояниям q = , получаем энтропию источника сообщений:

где p() — вероятность того, что источник сообщений находится в состоянии .

Величина H(Z) характеризует неопределенность, приходящуюся в среднем на один знак, выдаваемый источником сообщений.

Определим энтропию источника сообщений для нескольких частных случаев.

Если статистические связи между знаками полностью отсутствуют, то после выбора источником знака , его состояние не меняется (R = 1). Следовательно, p()= 1, и для энтропии источника сообщений справедливо выражение:

Когда корреляционные связи наблюдаются только между двумя знаками (простая цепь Маркова), максимальное число различных состояний источника равно объему алфавита. Следовательно, R= l и = , где q = . При этом выражение (4.2) принимает вид

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

Тогда

Подставляя эти значения в (4.2), находим

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

Пример 4.1. Определить, является ли эргодическим стационарный дискретный источник сообщений, алфавит которого состоит из четырех знаков и , причем безусловные вероятности выбора знаков одинаковы [], a условные вероятности заданы табл 4.1.

Таблица 4.1.

Анализ табл. 4.1 показывает, что источник имеет два режима работы. С вероятностью, равной ¾, первым будет выбран один из знаков или и источник начнет формировать последовательность с равновероятным появлением знаков. Если же первым будет выбран знак (вероятность такого случая равна ), то генерируется последовательность, содержащая только знаки .

Усреднение по ансамблю предполагает наличие множества однотипных источников, примерно три четверти из которых будет работать в первом режиме, а остальные — во втором. При этом в соответствии с (4.3) энтропия источника

Среднее по последовательности (времени) вычисляется с использованием конкретной последовательности и поэтому зависит от режима функционирования источника. В первом режиме неопределенность, приходящаяся на один знак достаточно длинной последовательности (энтропия последовательности), равна 1,586 дв. ед., а во втором — нулю.

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

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

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

Пусть, например, эргодический источник без памяти последовательно выдает знаки в соответствии с вероятностями 0,1; 0,3; 0,6. Тогда в образованной им достаточно длинной последовательности знаков мы ожидаем встретить в среднем на один знак три знака и шесть знаков . Однако при ограниченном числе знаков в последовательности существуют вероятности того, что она будет содержать;

только знаки (либо , либо );

только знаки и один знак или ;

только знаки и один знак или ;

только знаки и один знак или ;

только знаки и два знака или и т. д.

С увеличением числа знаков вероятности появления таких последовательностей уменьшаются.

Фундаментальные свойства длинных последовательностей знаков, создаваемых эргодическим источником сообщений, отражает следующая теорема: как бы ни малы были два числа δ>0 и μ>0 при достаточно большом Ν, все последовательности могут быть разбиты на две группы.

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

Вторая группа включает типичные последовательности, которые при достаточно большом N отличаются тем, что вероятности их появления практически одинаковы, причем вероятность ρ любой такой последовательности удовлетворяет неравенству

где Η(Ζ) — энтропия источника сообщений.

Соотношение (4.5) называют также свойством асимптотической равномерности длинных последовательностей. Рассмотрим его подробнее.

Поскольку при N→ ∞ источник сообщений с вероятностью, сколь угодно близкой к единице, выдает только типичные последовательности, принимаемое во внимание число последовательностей равно 1/р. Неопределенность создания каждой такой последовательности с учетом их равновероятности составляет log(l/p). Тогда величина log(l/p)/N представляет собой неопределенность, приходящуюся в среднем на один знак. Конечно, эта величина практически не должна отличаться от энтропии источника, что и констатируется соотношением (4.5).

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

Тогда вероятность ρ реализации любой типичной последовательности близка к величине

Логарифмируя правую и левую части выражения (4.6), получаем

откуда (при очень больших Ν)

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

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

При объеме алфавита источника l и количестве знаков в последовательности N число всех возможных последовательностей

Принимая во внимание соотношение (4.5), число типичных последовательностей nможно записать в виде

Тогда

Так как

то

и неравенство усиливается с увеличением N.

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

Пример 4.2. Оценить, какую долю общего числа возможных последовательностей следует учитывать в практических расчетах, если эргодический источник характеризуется параметрами l = 16, Η(Ζ) = 3,5 дв.ед, а N = 50.

В соответствии с (4.7) и (4.8) имеем

откуда

Следовательно, к типичным последовательностям относится только одна тридцатимиллионная доля всех возможных реализаций!

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

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

где (Z) — максимально возможная энтропия, равная log l; H(Ζ) — энтропия источника.

Если избыточность источника равна нулю, то формируемые им сообщения оптимальны в смысле наибольшего количества переносимой информации. Для передачи определенного количества информации I при отсутствии помех в этом случае необходимо k=I/[(Z)] знаков.

Поскольку энтропия сообщений, формируемых реальным источником, обладающим избыточностью, меньше максимальной, то для передачи того же количества информации I знаков требуется больше, а именно: = I/H(Z)
> k. Поэтому говорят также об избыточности знаков в сообщении или просто об избыточности сообщения, характеризуя ее тем же параметром D:

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

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

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

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

Максимальная энтропия текста на русском языке (с учетом пренебрежения при передаче различиями в буквах е и ё, ъ и ь) установлена ранее (см. пример 3.3) и равна 5 дв. ед. Там же определена энтропия с учетом неравномерного распределения вероятностей появления отдельных букв (4,42 дв. ед.). Имея сведения о переходных вероятностях и исходя из предположения, что текст представляет собой простую цепь Маркова, можно установить, что энтропия уменьшается до 3,52 дв. ед. Учет всех ограничений в языке, включая связи между словами, позволяет оценить минимальную величину энтропии значением 1,5 дв. ед. Таким образом, избыточность русского языка составляет

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

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

Длительность выдачи знаков источником в каждом из состояний в общем случае может быть различной. Обозначим длительность выдачи знака , формируемого источником в состоянии S, через τ. Тогда средняя длительность выдачи источником одного знака

Производительность источника Ī(z) теперь можно выразить формулой

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

Если длительность выдачи знака не зависит от состояния источника, для всех знаков одинакова и равна τ, то τ= τ. Выражение для Ī(Z) принимает вид

Наибольшая производительность источника в этом случае достигается при максимальной энтропии.

§ 4.3 ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ ДИСКРЕТНЫХ КАНАЛОВ СВЯЗИ

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

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

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

Термины «элементарный сигнал» и «символ», так же как «сложный сигнал» и «последовательность символов», в дальнейшем будут использоваться как синонимы.

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

В каждом состоянии канал характеризуется матрицей условных вероятностей ρ() того, что переданный символ u_i будет воспринят на выходе как символ ν_j. Значения вероятностей в реальных каналах зависят от многих различных факторов: свойств сигналов, являющихся физическими носителями символов (энергия, вид модуляции и т.д.), характера и интенсивности воздействующих на канал помех, способа определения сигнала на приемной стороне.

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

Канал называется с «памятью» (с последействием), если переходные вероятности в данном состоянии канала зависят от его предыдущих состояний. Если переходные вероятности постоянны, т.е. канал имеет только одно состояние, он называется стационарным каналом без памяти. Под k-ичным каналом подразумевается канал связи, у которого число различных символов на входе и выходе одинаково и равно k.

Дата добавления: 2014-10-23