Глава 3. Количественная оценка информации 4 страница

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

Избыточность. Следствием ограничений на выбор источником знаков является также недоиспользование их как переносчиков информации. Известная априорная информация о вероятностях выбора отдельных знаков и их сочетаний приводит к уменьшению средней неопределенности выбора источником знака, а следовательно, и переносимого им количества информации. При равновероятном и некоррелированном выборе ту же информационную нагрузку на знак можно обеспечить, используя алфавит меньшего объема. В связи с этим говорят об избыточности алфавита 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.

Стационарный дискретный двоичный канал без памяти однозначно определяется четырьмя условными вероятностями: р(0/0), р(1/0), р(0/1), р(1/1). Такую модель канала принято изображать в виде графа, представленного на рис. 4.2, где р(0/0) и р(1/1) — вероятности неискаженной передачи символов, а р(0/1) и р(1/0) — вероятности искажения (трансформация) символов 0 и 1 соответственно.

Если вероятности искажения символов можно принять равными, т. е. то такой канал называют двоичным симметричным каналом [при р(0/1) р(1/0) канал называется несимметричным ]. Символы на его выходе правильно принимают с вероятностью ρ и неправильно — с вероятностью 1—p = q. Математическая модель упрощается.

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

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

Следует отметить еще одну модель канала, которая в последнее время приобретает все большее значение. Это дискретный канал со стиранием. Для него характерно, что алфавит выходных символов отличается от алфавита входных символов. На входе, как и ранее, символы 0 и 1, а на выходе канала фиксируются состояния, при которых сигнал с равным основанием может быть отнесен как к единице, так и к нулю. На месте такого символа не ставится ни нуль, ни единица: состояние отмечается дополнительным символом стирания S. При декодировании значительно легче исправить такие символы, чем ошибочно определенные.

На рис. 4 3 приведены модели стирающего канала при отсутствии (рис. 4.3, а) и при наличии (рис. 4.3, 6) трансформации символов.

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

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

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

где — среднее значение длительности символа.

При одинаковой продолжительности τ всех передаваемых символов = τ.

Единицей измерения технической скорости служит бод — скорость, при которой за одну секунду передается один символ.

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

При известной скорости манипуляции V_T скорость передачи информации по каналу Ī(V,U) задается соотношением

где I(V,U) — среднее количество информации, переносимое одним символом.

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

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

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

Пропускная способность канала, как и скорость передачи информации по каналу, измеряется числом двоичных единиц информации в секунду (дв. ед./с).

Так как в отсутствие помех имеет место взаимно-однозначное соответствие между множеством символов {ν} на выходе канала и {u} на его входе, то I(V,U) = =I(U,V) = H(U). Максимум возможного количества информации на символ равен log m, где m — объем алфавита символов, откуда пропускная способность дискретного канала без помех

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

Расширение объема алфавита символов m приводит к повышению пропускной способности канала (рис. 4.4), однако возрастает и сложность технической реализации.

Пропускная способность дискретного канала с помехами. При наличии помех соответствие между множествами символов на входе и выходе канала связи перестает быть однозначным. Среднее количество информации I(V,U), передаваемое по каналу одним символом, определяется в этом случае соотношением

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

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

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

Если объем алфавита входных символов u равен m₁, а выходных символов υ — m₂, то

Подставив выражения (4.18) и (4.19) в (4.17) и проведя несложные преобразования, получим

Скорость передачи информации по каналу с помехами

Считая скорость манипуляции V_T предельно допустимой при заданных технических характеристиках канала, величину I(V,U) можно максимизировать, изменяя статистические свойства последовательностей символов на входе канала посредством преобразователя (кодера канала). Получаемое при этом предельное значение С_Д скорости передачи информации по каналу называют пропускной способностью дискретного канала связи с помехами:

где р{u} — множество возможных распределений вероятностей входных сигналов.

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

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

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

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

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

где — производительность источника сообщений; С_Д — пропускная способность канала связи.

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

Пример 4.4. Определить пропускную способность двоичного симметричного канала (ДСК) со скоростью манипуляции V_T в предположении независимости передаваемых символов.

Запишем соотношение (4.19) в следующем виде:

Воспользовавшись обозначениями на графе (рис. 4.5), можем записать

Так как

то

Величина H_U(V) не зависит от вероятностей входных символов, что является следствием симметрии канала.

Следовательно, пропускная способность

Максимум H(V) достигается при равенстве вероятностей появления символов, он равен 1. Отсюда

График зависимости пропускной способности ДСК от ρ показан на рис. 4.6. При увеличении вероятности трансформации символа с 0 до 1/2 С_Д(р) уменьшается от 1 до 0. Если ρ = 0, то шум в канале отсутствует и его пропускная способность равна 1. При р=1/2 канал бесполезен, так как значения символов на приемной стороне с равным успехом можно устанавливать по результатам подбрасывания монеты (герб—1, решетка — 0). Пропускная способность канала при этом равна нулю.

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

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

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

Под ε-производительностью источника непрерывных сообщений Η_ε(z) понимают минимальное количество информации, которое необходимо создать источнику в единицу времени, чтобы любую реализацию (t) можно было воспроизвести с заданной вероятностью ε.

Допустим, что (t) воспроизводится реализацией u_T(t). Наблюдаемые реализации следует рассматривать, как сигналы, обладающие ограниченным, хотя возможно и достаточно широким спектром F [28, 8].

При достаточно большой длительности Т как (t), так и u_T(t) могут быть представлены N-мерными (N = 2FT) векторами () и (), координатами которых являются отсчеты. Ансамбли сообщений { (t)} и воспроизводящих сигналов {u_T(t)} характеризуют при этом N-мерными случайными векторами Ζ и U, составляющими которых являются соответственно случайные величины Ζ₁, Z₂,.., Z_N и U₁, U₂,.., U_N. Статистическое описание каждого из ансамблей задается N-мерными плотностями распределения вероятностей ρ(Ζ) = ρ() и p(U) = p(). Связь между ансамблями отражают условные плотности распределений p_u(Z)= = ρ( / ) и p_z(U) = p( / ), а также совместная плотность распределения вероятностей p(Z,U) = p(; ).

Распространяя формулу (4.20) на N-мерные случайные векторы Ζ и U для количества информации одного из них относительно второго, получим

где интегралы являются N-мерными.

Используем, как и ранее, среднеквадратический критерий верности (Z,U), который в рассматриваемом случае имеет вид

где p(Z,U)ZU представляет собой квадрат расстояния l (Z,U) в N-мерном евклидовом пространстве.

Количество информации, приходящееся в среднем на один отсчет дискретизованных сигналов Z_T(t) и U_T(t), определяется выражением

Тогда в соответствии с определением для ε-пропорциональности источника непрерывных сообщений Н_ε(Z) запишем

при выполнении условия

Величина ν характеризует скорость формирования источником отсчетов (ν = =2F).

Пример 4.5. Определить ε-производительность источника, формирующего со скоростью ν₁ некоррелированные отсчеты стационарного нормального случайного сигнала с дисперсией σ².

Воспользовавшись полученным в (3.65) значением ε-энтропии для нормально распределенной случайной величины, найдем

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

Конечное подмножество воспроизводящих сигналов U_T(t) размещается в центрах непересекающихся правильных сферических N-угольников (ε-областей), на которое гиперсфера разбивается без промежутков. Размеры ε-областей определены заданной верностью воспроизведения сообщений. Если источником реализуется сообщение z*_T(t), конец вектора которого должен попасть в ε-область сигнала u*_T(t), то воспроизводится сигнал u*_T(t).

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