книги / Теория информации

учетом их равновероятности составляет log(l/p). Тогда величина log(l/ р)/М представляет собой неопределенность, приходящуюся в среднем на один знак. Конечно, эта величина практически не должна отличать­ ся от энтропии источника, что и констатируется соотношением (6.11).

Ограничимся доказательством теоремы для простейшего случая эргодического источника без памяти. Оно непосредственно вытекает из закона больших чисел, в соответствии с которым в длинной после­ довательности из М элементов алфавита I (zp z2,...z,), имеющих вероят­ ности появления р рр2,...,рп содержится Мрхэлементов zp Мр2элемен­ тов z2 ит.д.

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

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

м

lo g Р = М ^ р , log р, ы\

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

log( 1/р)/М+Н(Х).

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

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

Общее число всевозможных последовательностей длины М, вы­

рабатываемых источником,

= пМ= 2 Aflogn^

N T _ 9 « | t f W - l o g / i |

N

откуда при М —►оо NJN —►0, так как Н(Х) - log п < 0. Однако хотя типичных последовательностей мало, но только они в основном выра­ батываются источником, как то следует из теоремы.

Пусть, например,

а = 2, п = 100, Н= 2,75, т = 8. Тоща N = Sm =2300,7У2 = 2100 2,75 = 2275.

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

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

Целесообразно отметить, что в простейшем случае отсутствия статистической зависимости между элементами процесса свойство Е является простым следствием закона больших чисел [7].

6.4. Кодирование дискретных источников

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

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

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

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

Далее сформулируем предельные возможности статистических кодов.

Рассмотрим вначале последовательность 2?я=(6(1),...,6(п)) следующих друг за другом п элементов дискретного источника {В,р(Ь)}. Каждый элемент выбирается из алфавита {Ы, ...,Ьк}, и, таким образом, имеются К* последовательностей различной длины и, которые могут появляться на выходе источника. Поставим задачу кодирования этих последова­ тельностей в слова кода с фиксированной длиной. Если кодовый алфа­ вит состоит из т символов и если длина каждого кодового слова равна /, то существуют т1различных кодовых слов. Следовательно, если нуж­ но сопоставить различные кодовые слова разным последовательнос­ тям источника (если необходимо взаимно однозначное отображение),

длиной при декодировании необходимо иметь по меньшей мере log К/ log М кодовых символов на одну букву источника.

Если мы хотим в целях эффективного кодирования использовать меньше, чем log К/ log М символов на одну букву источника, то, оче­ видно, нужно ослабить требование того, чтобы всегда была возмож­ ность полного однозначного соответствия.

В подтверждение сказанному рассмотрим пример [1]. Предполо­ жим, что на телеграфе введена автоматическая обработка телеграмм, записанных в алфавите объемом 64 буквы (количество букв, содержа­ щееся в двух регистрах телетайпа). Пусть эффективность обработки информации определяется количеством телеграмм, которые можно ввести в запоминающее устройство (ЗУ). Объем ЗУ равен У двоичным ячейкам. Необходимо закодировать телеграммы двоичным кодом.

Рассмотрим вначале побуквенное кодирование. В этом случае ис­ пользуется код, содержащий 26 = 64 кодовых слова, и каждой букве телеграммы сопоставляется некоторое кодовое слово. Пусть исполь­ зуется равномерный код со словами в 6 двоичных символов. При этом в ЗУ можно поместить N/6 букв. Если считать, что средняя длина теле­ граммы - 20 слов, а средняя длина слова 8 букв, то в ЗУ можно помес­ тить примерно N/960 телеграмм.

Второй способ кодирования состоит в том, что выделяется специ­ альный словарь, например, из 213 = 8192 слова (достаточно практичес­ ки для любой телеграммы). Каждое слово может быть закодировано с помощью двоичной последовательности длиной 13 символов. В этом случае в ЗУ можно записать N/260 телеграмм, т.е. в 3—4 раза больше, чем в первом случае. (При кодировании и декодировании можно счи­ тать слово, отсутствующее в словаре, «ошибкой».)

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

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

Постановка задачи равномерного кодирования источника. Пусть А = {о,,..., ат} - алфавит кода источника - некоторое множество, со­ стоящее из т элементов; а. - кодовые символы. Последовательность кодовых символов задает кодовое слово, любое семейство кодовых слов - это код над алфавитом А. (Примеры: множество букв русского алфавита, множество цифр и т.д.) Код называется равномерным, если все его слова имеют одинаковую длину /, называемую длиной (значностью) кода. В противном случае код называется неравномерным. Ко­ личество различных слов равномерного кода длины / не превосходит т1- числа различных /м-ичных последовательностей длины /.

Определение. Кодированием сообщений ансамбля В посредством кода А называется отображение множества сообщений В" в мно­ жество кодовых слов.

Предлагается следующий способ равномерного кодирования [1]: множество всех последовательностей сообщений источника длиной и делится на два подмножества, одно из которых создается всеми пос­ ледовательностями —блоками длины п, однозначно отображаемыми кодовыми словами. Это подмножество называется множеством одно­ значно кодируемых и декодируемых блоков. Остальные блоки образу­ ют второе подмножество, которому соответствует одно единственное

кодовое слово. Длина / всех кодовых слов одинакова; она определяется числом М кодовых слов: / - наименьшее целое, удовлетворяющее нет равенству т! > М. Процесс кодирования и декодирования заключается в разбиении последовательности сообщений на выходе источника на блоки длиной п и сопоставлении каждому блоку соответствующего кодового слова длины /. Ошибкой процедуры декодирования при этом является событие, состоящее в появлении неоднозначно кодируемого блока. Количество /и-ичных кодовых символов, приходящихся на одно сообщение, определяется соотношением Un > log Ml log т. Число log Min = R для заданных значений М и п называется скоростью равно­ мерного кодирования источника. Скорость- R измеряется в двоичных символах на сообщение. Таким образом, существо равномерного ко­ дирования заключается в выборе множества однозначно кодируемых «-последовательностей сообщений.

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

Величина Н может рассматриваться как скорость создания инфор­ мации, если может быть доказано следующее важное утверждение.

Для любого R > Н и произвольного положительного д найдется значение п и код со скоростью R, для которого вероятность ошибки не превосходит д. (Прямая теорема кодирования источника.)

6.5. Энтропия источника без памяти как скорость создания информации

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

4.Каковы причины наличия избыточности в сообщении?

5.Определите производительность источника дискретных сооб­ щений и укажите пути ее повышения.

6.Что понимают под e-производительностью источника непре­ рывных сообщений?

7.Как определить избыточность дискретного источника и чем она вызывается? Какой источник имеет нулевую избыточность?

8.Каковы вероятностные характеристики достаточно длинных типичных и нетипичных последовательностей символов дискретного источника?

7.ДИСКРЕТНЫЕ КАНАЛЫ БЕЗ ШУМОВ

7.1.Модель информационной системы передачи дискретных

сообщений в отсутствие шумов

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

В зависимости от конкретного набора блоков системы и соответс­ твенно формы и характеристик входных и выходных сигналов канала пе­ редачи возникает необходимость в введении специальной классификации каналов.

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

1.Канал называется дискретным по входу (по выходу), если множес­ тво входных (выходных) сигналов является счетным.

2.Канал называется непрерывным по входу (по выходу), если множес­ тво входных (выходных) сигналов является несчетным.

3.Канал называется дискретным по входу и непрерывным по выходу,

если множество входных сигналов конечно, а множество выходных сигна­ лов несчетно. Такие каналы называют еще полунепрерывными.

4.Канал носит название канала с дискретным временем, если сигна­ лы на его входе и выходе представляют собой конечные или бесконечные последовательности из элементов некоторых ансамблей.

4а. Дискретный по входу и выходу канал с дискретным временем на­ зывается дискретным каналом.

5.Канал называется каналам с непрерывным временем, если сигналы на его входе и выходе являются непрерывными функциями времени.

5а. Непрерывный по входу и выходу канал с непрерывным временем называют непрерывным каналом.

Канал считается заданным, если известны статистические данные о сообщениях на его входе и выходе и ограничения, накладываемые на

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

Будучи не полной, представленная классификация является доста­ точной для последующею изложения материала. В данном разделе рас­ сматриваются толыю дискретные каналы (к числу которых, в частности, относятся кодеры и декодеры).

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

Упрощенная блок-схема дискретного канала связи без шумов приве­ дена на рис. 7.1.

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

Рис. 7.1. Блок-схема дискретного канала связи без шумов

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

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

Кодированные сигналы передаются по каналу связи и на его прием­ ном конце восстанавливаются в точно такой же или в иной форме (z). Де­

кодирующее устройство преобразует кодированные сигналы (z) в сообще­ ния (w) в форме, наиболее удобной для данного получателя.

С информационной точки зрения физическая реализация (форма или вид модуляции) кодированных сигналов на передающей (у) и на приемной

(z) сторонах, а также выходных сигналов (>v) значения не имеет. Важным является лишь установление определенного соответствия между у и JC, между z и у и, наконец, между w и z.

Не нарушая общности рассуждений, при отсутствии шумов (помех) можно принять z = у. Способ кодирования должен быть таким, чтобы в случае отсутствия шумов на приемной стороне по полученным кодиро­ ванным сигналам можно было однозначно восстановить вид переданных сообщений, т. е. чтобы w - х. Это накладывает некоторые ограничения на допустимые комбинации символов кода. Так, например, если мы закоди­ руем символы х, —►1, х, —* 2 и х3 —* 01, то при получении сигнала 01 на приемной стороне мы не будем знать, что было передано: сообщение х3 или два сообщения х ^ . Следовательно, необходимо либо отказаться от такого способа кодирования, либо заранее условиться, что комбинацию хут, передавать нельзя (она запрещена). На возможную последователь­ ность символов кода могут накладываться и другие ограничения.

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

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

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

Обозначив через Хт последовательность сообщений, создаваемых источником за время Т, а через WTсоответствующую ей последователь­ ность принятых сообщений, определим количество информации I(Wp Хг), содержащееся в последовательности сообщений WTна выходе канала о последовательности Хтна его входе. /(ЖрА^) зависит от вероятностных характеристик источника сообщений и характеристик шумов, действую­ щих в линии связи, метода кодирования сообщений, а также промежутка времени Т.