Прикладная теория информации Учебное пособие

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ РЯЗАНСКАЯ ГОСУДАРСТВЕННАЯ РАДИОТЕХНИЧЕСКАЯ АКАДЕМИЯ

Г.И. НЕЧАЕВ

Прикладная теория информации

Учебное пособие

1-PII

PI

PII

1-PI

Рязань 2004

УДК 519.92 УДК 621.391.24

Прикладная теория информации: Учеб. пособие / Г.И. Нечаев; Рязан. гос. радиотехн. акад. Рязань, 2004. 24 с.

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

Предназначены студентам заочной формы обучения по специальности 071900 «Информационные системы и технологии» для изучения дисциплины «Прикладная теория информации».

Табл. 2 . Ил. 5 . Библиогр.: 3 назв.

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

Печатается по решению методического совета Рязанской государственной радиотехнической академии.

Рецензент: кафедра автоматизированных систем управления Рязанской государственной радиотехнической академии

Н е ч а е в Геннадий Иванович

Прикладная теория информации

Редактор И.П. Перехрест Корректор Е.В. Ипатова

Подписано в печать 24.06.04. Формат бумаги 60 х 84 1/16. Бумага газетная. Печать трафаретная. Усл. печ. л. 1,5.

Уч.-изд. л. 1,5. Тираж 100 экз. Заказ Рязанская государственная радиотехническая академия.

390005, Рязань, ул.Гагарина, 59/1. Редакционно-издательский центр РГРТА.

©Рязанская государственная радиотехническая академия, 2004

Введение

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

Источники сообщений и каналы связи отличаются большим разнообразием по своей структуре и физической природе. В информационных системах широко используются оптоволоконные, проводные электрические (кабель, «витая пара») и радиоканалы связи [1].

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

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

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

1. Пропускная способность дискретного (цифрового) канала

Структурная схема цифрового информационного канала показана на рис.1 [1,2].

Источник

помех

Рис.1. Структурная схема цифрового канала На вход такого канала обычно поступают дискретные соотношения х,

например, в виде текста. Последние с помощью кодирующего устройства преобразуются в кодированные сигналы у. Как известно, для кодирования используется некоторый алфавит элементарных сигналов (символов) – у1, у2,…, уm, а существо кодирования сводится к представлению отдельных сообщений хi или последовательностей сообщений некоторыми комбинациями символов используемого алфавита. Декодирующее устройство преобразует кодированные сигналы z в сообщения w в форме, наиболее приемлемой для получателя, которым может быть не только человек, но и различные технические устройства (принтер, монитор, ПЭВМ и др.). В современных информационно-вычислительных комплексах исходные сообщения х могут быть и в непрерывной форме, но с помощью кодирующих устройств последние преобразуют в кодированные сигналы.

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

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

При отсутствии шумов можно считать, что в информационном канале z = y, а w = x, следовательно, для сообщений zT = yT, wT = xT, передаваемых

за время Т, количество информации, поступающей к получателю от источника, составит

I(WT, XT) = I(XT, XT) = H(XT),

где Н(ХТ) - энтропия источника сообщений.

По аналогии для канала связи, представляющего часть

Если последовательность хТ состоит из m сообщений и средняя длительность сигнала, обеспечивающего передачу одного сообщения

составляет τс, то можно определить скорость передачи информации как

где Н(X) – энтропия источника n сообщений:

n

H ( X ) = −∑P( xi )log2 P( xi ) .

i=1

Вдальнейшем основание 2 логарифма для простоты будет опущено.

Очевидно, что скорость передачи информации I(W , X ) будет зависеть

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

Пропускная способность информационного канала C определяется максимальным значением скорости передачи:

Аналогично находится пропускная способность канала связи Cс, являющегося частью информационного канала:

Обычно Cс > C.

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

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

максимальная скорость передачи информации называется эффективным.

Дискретный канал, в котором передаваемые сообщения представлены двоичным кодом, называется двоичным каналом. Если код имеет m символов

(разрядов), то очевидно, что всего можно закодировать n = 2m сообщений, а длительность одного сообщения составит T = mτ, где τ - длительность

символа кода с учетом того, что все символы обычно имеют одинаковую длительность. Двоичные коды, состоящие из одинакового числа символов m, называются равномерными. Пропускная способность рассматриваемого канала с учетом формул (1.1), (1.2) и (1.3) составит

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

энтропии следует, что H(YT) будет максимальна, если сообщения равновероятны, это максимальное значение может быть определено мерой Хартли и будет равно logn = log2m = m [2].

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

Рассмотрим два простых примера.

Пример 1. Пусть источник сообщений вырабатывает четыре сообщения х1, х2, х3, х4, (n = 4). Все сообщения имеют одинаковые вероятности: P(xi) = 1/n = 0,25. Для их кодирования используется двоичный равномерный код, число символов в котором достаточно выбрать m = 2. Исходные сообщения х1, х2, х3, х4 в этом примере будут

представлены следующими кодами: 00, 01, 10, 11.

Скорость передачи информации будет определяться по формуле (1.2), в которой энтропия источника равновероятных сообщений будет максимальной:

а длительность каждого из четырех сообщений будет определяться

длительностями соответствующих кодовых комбинаций и составит τс = 2τ. Для примера 1 по формуле (1.2) находим

I = log 2 = 1 , дв.ед. .

2τ τ с

Таким образом, в этом примере, как и следовало ожидать, скорость передачи информации оказалась равной пропускной способности канала:

I = Cc = 1/τ.

Пример 2. Источник сообщений и способ их кодирования такие же, как и в примере 1, но вероятности сообщения при этом не одинаковы:

Р(х1) = 0,5; Р(х2) = 0,25; Р(х3) = Р(х4) = 0,125.

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

значение энтропии Н(х) для источника разновероятных сообщений х1, х2,

х3, х4 (n = 4):

4

H( X ) = −∑ P( xi log P( xi ) = −P( x1 ) log P( x1 ) − P( x2 ) log P( x2 ) −

i=1

−P( x3 ) log P( x3 ) − P( x4 ) log P( x4 ) = 0,5 log 2 + 0,25 log 4 +

Длительности всех сообщений остаются такими же, как и в примере 1: τс = 2τ. Скорость передачи информации составит

В этом примере скорость передачи информации оказалась меньше пропускной способности двоичного канала Cс(0,875/τ < 1/τ).

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

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

К эффективным относится, в частности, код Шеннона − Фано, пригодный для кодирования статистически независимых сообщений.

Рассмотрим построение кода Шеннона − Фано для источника сообщений х1, х2, х3, х4, приведенных в примере 2. Использование равномерного кода для этих сообщений, как отмечалось ранее, не позволяет обеспечить максимальную скорость передачи информации. Покажем, что с помощью кода Шеннона − Фано рассматриваемые сообщения можно передать с максимальной скоростью, равной пропускной способности двоичного канала. Кодирование сообщений в этом случае иллюстрируется таблицей 1, которая составлена следующим образом.

Записывают сообщения в порядке убывания их вероятностей. Проводят первое деление всех сообщений на две подгруппы I и II так,

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

при первом делении в подгруппу I входит сообщение х1, вероятность

которого равна 0,5, а в подгруппу II входят сообщения х2, х3, х4, сумма вероятностей которых (0,25+0,125+0,125) будет тоже составлять 0,5.

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

Номер подгруппы, в которую попадает данное сообщение при каждом делении, определяет символ на соответствующей позиции кода этого сообщения. В рассматриваемой таблице принадлежность к подгруппе I обозначается символом 0, а к подгруппе II – символом 1. Так, в частности,

первое деление дало на первой позиции кода для сообщения x1 символ 0, а для остальных сообщений – символ 1.

Как следует из таблицы 1, полученный код является неравномерным, т.е. сигналы разных сообщений имеют различное число символов, следовательно разную длительность. Для наглядности в таблице 2 для сообщений х1, х2, х3, х4 приведены неравномерный код Шеннона − Фано и равномерный, используемый ранее в примерах 1 и 2. Анализируя неравномерный код Шеннона − Фано, можно убедиться в том, что наиболее вероятному сообщению соответствует самая короткая кодовая комбинация, наименее вероятному – длинная. Этим можно объяснить увеличение скорости передачи информации при использовании данного кода.

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

Для вычисления скорости передачи информации при использовании кода Шеннона − Фано воспользуемся формулой (1.2), применительно к

Как отмечалось выше, код Шеннона − Фано является неравномерным.

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

длительности τi сообщения xi [по аналогии с энтропией Н(Х)]:

n

τc = ∑P( xi )τi . i =1

Для выбранного примера по таблице 1 (n = 4) находим τс = 1,75τ, что

позволяет считать кодовую комбинацию состоящей в среднем из m = 1,75 символов.

По формуле (1.2) для полученных значений Н(Х) и τс находим скорость передачи:

Таким образом, в данном примере код Шеннона − Фано позволил полностью согласовать статистические характеристики источника сообщений с каналом связи, поскольку скорость передачи информации

оказалась равной пропускной способности канала: I = Cc .

Равномерный код, как отмечалось в примере 2, не является эффективным. Это можно объяснить тем, что при использовании эффективного кода Шеннона − Фано сигнал каждого сообщения в среднем состоит из 1,75 символов, а при использовании равномерного кода – из 2-х (таблица 2). Из чего следует, что в единицу времени сообщений, представленных кодом Шеннона − Фано, будет передано больше, чем при использовании равномерного кода.

Необходимо заметить и то, что, действуя по правилу построения кода Шеннона − Фано для четырех равновероятных сообщений, рассмотренных в примере 1, получаем приведенный в таблице 2 равномерный код, который в данном случае является эффективным.

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

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

составит τc′ = 2,5τ , а скорость передачи информации

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

H (X ) = H (X ) /τc , вырабатываемой источником, равен Н(Х) = Сс - ξ, где

ξ - сколь угодно малая величина, то всегда можно найти такой способ кодирования, который обеспечивает передачу всех сообщений,

вырабатываемых источником, причем скорость передачи I = Сс - ξ . Обратное утверждение состоит в том, что невозможно обеспечить

передачу всех сообщений источника, у которого H ( X ) > Cc .

1.2.Пропускная способность дискретных каналов с шумами

Для дискретного канала с шумами (рис.1) количество информации, содержащейся в последовательности выходных сигналов zT о входных сигналах YT , cоставит [2]

где H(ZT|YT) и H(YT|ZT) – условные энтропии.