Перегудов Ф. И., Тарасенко Ф. П
 Скачать 4.17 Mb.
|
§ 5.8. ОБ ОСНОВНЫХ РЕЗУЛЬТАТАХ ТЕОРИИ ИНФОРМАЦИИТеория информации приводит к ряду новых понятий, описывающих информационные процессы, происходящие в любых системах, к введению новых количественных параметров, позволяющих проводить измерения и расчеты. Часть этих понятий и величин мы рассмотрели в предыдущих параграфах, некоторые другие опишем ниже. Однако главная ценность теории информации заключается в полученных ею новых результатах, в открытии ранее неизвестных свойств систем. Чтобы познакомиться с основными из этих результатов, введем еще несколько понятий и параметров информационных процессов и систем. ИЗБЫТОЧНОСТЬ Одной из важнейших характеристик сигнала является содержащееся в нем количество информации. Однако по ряду причин количество информации, которое несет сигнал, обычно меньше, чем то, которое он мог бы нести по своей физической природе; информационная нагрузка на каждый элемент сигнала меньше той, которую элемент способен нести. Для описания этого свойства сигналов введено понятие избыточности и определена ее количественная мера. Пусть сигнал длиной в n символов содержит количество информации I. Если это представление информации обладает избыточностью, то такое же количество информации I может быть представлено с помощью меньшего числа символов. Обозначим через n0 наименьшее число символов, необходимое для представления I без потерь. На каждый символ в первом случае приходится I1 = I/n бит информации, во втором I1max = I/n0 бит. Очевидно, nI1 = n0I1max = I. В качестве меры избыточности R принимается относительное удлинение сигнала, соответствующее данной избыточности:  . (1)В дискретном случае имеются две причины избыточности: неравновероятность символов и наличие статистической связи между символами. В непрерывном случае – это неэкстремальность распределений (т.е. отклонение от распределений, обладающих максимальной энтропией), что в широком смысле сводится к отклонениям от экстремальности распределения первого порядка и от минимальности связи во времени (от равномерности спектра при его ограниченности). Не следует думать, что избыточность – явление всегда отрицательное. При искажениях, выпадениях и вставках символов именно избыточность позволяет обнаружить и исправить ошибки. СКОРОСТЬ ПЕРЕДАЧИ И ПРОПУСКНАЯ СПОСОБНОСТЬ Следующим важнейшим понятием является скорость передачи информации. Так называется количество информации, передаваемое в единицу времени. Эта величина определяется по формуле R = Н(Х) – Н(Х | Y), (2) где указанные энтропии исчисляются на единицу времени*. В дискретном случае единицей времени удобно считать время передачи одного символа, тогда в формуле (2) фигурируют априорная и апостериорная энтропии на один символ. Для непрерывных каналов единицей времени может служить либо обычная единица (например, секунда), либо интервал между отсчетами (см. § 5.5); тогда в формулу (2) входят соответствующие дифференциальные энтропии. Для более наглядного представления о величине R укажем, что темп обычной речи соответствует скорости порядка 20 бит/с, муравьи обмениваются информацией путем касания усиками со скоростью около 1/10 бит/с. Скорость передачи информации по каналу связи зависит от многих факторов – от энергии сигнала, числа символов в алфавите избыточности, полосы частот, способа кодирования и декодирования. Если имеется возможность изменять некоторые из них, то, естественно, следует делать это так, чтобы максимально увеличить скорость. Оказывается, что обычно существует предел, выше которого увеличение скорости невозможно. Этот предел называется пропускной способностью канала:  , (3)где RА – скорость передачи информации при условиях А, {А} – множество вариантов условий, подлежащих перебору. Так как множество {А} можно определить по-разному, то имеет смысл говорить о нескольких типах пропускных способностей. Наиболее важным является случай, когда мощность сигнала (объем алфавита) фиксирована, а варьировать можно только способ кодирования. Именно таким образом пропускную способность определил К.Шэннон [9]. С другой стороны, В.И.Сифоров показал, что целесообразно рассмотреть предел, к которому стремится шэнноновская пропускная способность С при стремлении мощности полезного сигнала к бесконечности. Оказалось, что все каналы связи разбиваются на два класса: каналы первого рода (терминология Сифорова), для которых указанный предел бесконечен, и каналы второго рода, имеющие конечную пропускную способность даже при бесконечной мощности передатчика. Этот предел называют собственной пропускной способностью. При других требованиях, предъявляемых к множеству {А}, мы придем к тем или иным условным пропускным способностям. Для представления о порядках величин С приведем примеры. Прямыми измерениями установлено, что пропускные способности зрительного, слухового и тактильного каналов связи человека имеют порядок 50 бит/с (вопреки распространенному мнению о сильном отличии зрительного канала). Возможно, ограничивающим фактором являются не сами рецепторы, а нервные волокна, передающие возбуждения. Если включить в канал и “исполнительные” органы человека (например, предложить ему нажимать педаль или кнопку в темпе получения сигналов), то пропускная способность близка к 10 бит/с. Интересно отметить, что многие бытовые технические устройства слабо согласованы с органами чувств человека. Например, канал телевидения имеет пропускную способность в десятки миллионов бит/с. КОДИРОВАНИЕ В ОТСУТСТВИЕ ШУМОВ С помощью введенных понятий можно рассмотреть многие информационные процессы. Начнем с дискретных систем без шумов. Здесь главное внимание привлекает проблема эффективности: важно, чтобы данная информация заняла в запоминающем устройстве как можно меньше ячеек, при передаче желательно занимать канал связи на максимально короткий срок. В такой постановке задачи легко распознается проблема устранения всякой избыточности. Однако эта проблема не тривиальна. Пусть алфавит системы состоит из m символов. Средствами этого алфавита требуется представить любой из M возможных сигналов {uk},  , вероятности которых {р(uk)} заданы. Обычно М > m, поэтому каждый из сигналов, подлежащих передаче, невозможно обозначить только одним символом и приходится ставить им в соответствие некоторые последовательности символов; назовем их кодовыми словами. Так как возможна последовательная передача разных кодовых слов, то они не только должны различаться для разных uk, но и не должны быть продолжением других, более коротких. Пусть сигналу uk соответствует кодовое слово длиной lk символов. При стационарной передаче сигналов с вероятностями {р(uk)} средняя длина кодового слова равна  . Возникает вопрос о том, как выбирать L и {lk}. Он не имеет смысла, пока не задан критерий выбора этих величин. Определим этот критерий так: L и {lk} должны быть минимальными величинами, такими, при которых еще не происходит потери информации. Напомним, что в отсутствие шумов среднее количество информации на один элемент uk ансамбля {uk} равно энтропии этого ансамбля, т.е. Н(U) = =  , а индивидуальное количество информации в uk есть i(uk) = – logр(uk). С другой стороны, на один символ придется максимальное количество i информации, если символы равновероятны и независимы; при этом i = logm. Поскольку кодирование должно вестись без потерь информации, сразу получаем  , (4)  . (5)Так из общих соображений находим нижние границы для L и lk. В теории информации доказываются теоремы об условиях достижимости этих границ. Мы не будем приводить эти теоремы; укажем лишь, что речь идет не только о принципиальной возможности: разработаны процедуры построения кодов, обеспечивающих безызбыточное кодирование (либо в случае невозможности этого – сколь угодно близкое к нему). КОДИРОВАНИЕ ПРИ НАЛИЧИИ ШУМОВ Наиболее интересные и важные результаты были получены при рассмотрении передачи информации по каналам связи с шумами. В этом случае безызбыточное кодирование приведет к безвозвратным потерям информации: искаженный символ нельзя ни обнаружить, ни исправить. Для борьбы с влиянием помех необходимо ввести избыточность в сигнал. Основываясь на интуитивных соображениях (например, на опыте многократного повторения), легко прийти к выводу, что при неограниченном повышении требований к малости вероятности ошибки избыточность и при любом способе кодирования должна неограниченно возрастать, а скорость передачи – стремиться к нулю. Здесь мы имеем яркий пример того, как сильно интуиция может привести к заблуждению. Шэннон показал, что существуют такие способы введения избыточности, при которых обеспечиваются одновременно и сколь угодно малая вероятность ошибки, и конечная (отличная от нуля) скорость передачи информации, причем эта скорость может быть сколь угодно близкой к пропускной способности канала. Это замечательное открытие и привлекло столь большое внимание к теории информации. Воспроизведем упрощенное доказательство указанного утверждения. Рассмотрим схему передачи по каналу с шумом (рис. 5.5). Будем считать, что на вход кодера сигналы поступают закодированными безызбыточно. Кодер вносит в сигналы избыточность, увеличивая длительность кодовых слов. Число возможных последовательностей сразу резко увеличивается, но избыточность и состоит в том, что к отправке предназначаются не все из них, а лишь разрешенные (отмеченные на рис. 5.5 черными кружками). Согласно фундаментальному свойству энтропии (см. формулу (8) § 5.6), число всевозможных последовательностей* длины n равно 2nH(X), а число разрешенных* к отправке равно 2nH < 2nH(X) (считаем, что энтропия исчисляется в битах); Н – энтропия на символ во множестве разрешенных к отправке последовательностей (“энтропия источника”, или “скорость создания информации”), Н(Х) – энтропия на символ во множестве всевозможных последовательностей. В результате воздействия шумов какие-то из символов отправленной последовательности подменяются другими и на приемный конец поступает другая, отличная от отправленной, последовательность. Поскольку р(х | у) считается известным, каждой принятой последовательности соответствует 2nH(Х | Y) возможно отправленных*. Декодирование (т.е. принятие решения о том, какая последовательность была отправлена) можно выразить как разбиение всего множества Y принимаемых последовательностей на 2nH подмножеств, сопоставляемых с разрешенными к отправке: если, например, принят сигнал i-й группы, то считается, что был послан i-й разрешенный сигнал, который тут же выдается в “чистом” виде получателю.  5.5 ————— Схема передачи информации по каналу с шумами Итак, в построенной модели проблема выбора кода (способа передачи) состоит в размещении разрешенных последовательностей среди множества всевозможных на передающем конце и в разбиении этого множества из 2nH(Х) последовательностей на 2nH подмножеств на приемном конце. Идея Шэннона состоит не в том, чтобы указать некоторый регулярный способ кодирования со сколь угодно малой вероятностью ошибки, а в том, чтобы показать, что такой код вообще существует. Рассмотрим класс всевозможных кодов, которые получаются, если разрешенные последовательности размещать среди всевозможных случайным образом, а в качестве декодирующего подмножества брать 2nH(Х | Y) последовательностей высоковероятностной группы, соответствующей принятому сигналу. GAUSSIAN гауссов (канал) REDUNDANCY избыточность CODING кодирование CAPACITY пропускная способность (канала) RATE скорость (передачи) Для информационных процессов в отсутствие шумов главной проблемой является наиболее эффективное (безызбыточное) представление информации. Свойства таких оптимальных кодов легко определяются из эвристических соображений (хотя могут быть доказаны и строго), что иллюстрирует полезность введенных понятий (см. (5) и (6) ). Пожалуй, самым важным открытием в теории информации является установленная К. Шэнноном возможность практически безошибочной передачи информации по каналу с шумом со скоростью, близкой к пропускной способности. Вероятность ошибки при этом равна вероятности того, что среди 2nH(Х | Y) последовательностей окажется более одной разрешенной. Так как код получается в результате случайного (равновероятностного) выбора 2nH последовательностей среди 2nH(Х), то вероятность того, что данная последовательность окажется разрешенной, равна 2nH/2nH(Х) = 2n(H – H(Х)). Средняя вероятность того, что в декодирующем подмножестве из 2nH(Х | Y) последовательностей имеется только одна разрешенная, выразится соотношением  ; (6) это и есть вероятность безошибочного приема. Поскольку Н < С = Н(Х) – Н(Х | Y), имеем Н – Н(Х) = – Н(Х | Y) – , где > 0. Отсюда (пренебрегая единицей по сравнению с 2nH(Х | Y) находим  . (7) Логарифмируя и применяя правило Лопиталя, легко показать, что  , т.е. что при кодировании достаточно длинными блоками средняя вероятность ошибки может быть сделана сколь угодно малой. Доказательство завершается утверждением, что существуют коды с вероятностями ошибок меньше средней. ПРОПУСКНАЯ СПОСОБНОСТЬ ГАУССОВА КАНАЛА СВЯЗИ Перейдем теперь к знакомству с основными результатами для систем с непрерывными сигналами. Наиболее известным выводом теории является формула для пропускной способности гауссова канала связи, которую мы сейчас получим. Гауссовым каналом называется канал связи, для которого выполняются следующие условия: 10) сигналы и шумы в нем непрерывны; 20) канал занимает ограниченную полосу частот шириной F; 30) шум n(t) в канале распределен нормально (“гауссов шум”); 40) спектр мощности шума равномерен в полосе частот канала и равен N единиц мощности на единицу полосы частот; 50) средняя мощность полезного сигнала х(t) фиксирована и равна Р0; 60) сигнал и шум статистически независимы; 70) принимаемый сигнал y(t) есть сумма полезного сигнала и шума: y(t) = х(t) + n(t)(“шум аддитивен”). Эти предположения позволяют вычислить пропускную способность гауссова канала. Во-первых, ограниченность полосы частот позволяет применить теорему отсчетов (см. § 5.5) и вести рассуждения для каждого отсчета в отдельности. Далее, аддитивность шума и его независимость от Х позволяют представить количество информации в Y об Х в виде  , (8) где h(N) – дифференциальная энтропия шума. Следовательно, пропускная способность такова:  Согласно условиям 30 и 40, имеем  . (9) В силу условий 40 – 70 мощность принимаемого сигнала есть  . (10) Максимум h(Y) при условии (10) достигается в случае нормального распределения (см. упражнение 2б) к § 5.6), т.е.  (11)Так как шум имеет равномерный спектр (см. условие 40) и спектр смеси y(t) также равномерен (вследствие независимости отсчетов), то и полезный сигнал должен иметь равномерный спектр. Вводя спектральную плотность Р = Р0/F и вычитая равенство (9) из (11), получаем известную формулу Шэннона – Таллера  (12) Таким образом, мы не только определили пропускную способность, но и заодно показали, что она реализуется, если полезный сигнал закодировать так, чтобы его спектр был равномерным в представленной полосе частот, а распределение мгновенных значений – нормальным. Дальнейшие обобщения связаны с рассмотрением “небелых” сигналов и шумов (предполагается зависимость от частоты их спектральных мощностей Р( f ) и N( f )), а также с допущением случайности величины Р (например, в случае замираний радиосигналов). Решения возникающих при этом задач имеются в литературе по теории информации.
ЗАКЛЮЧЕНИЕОтметим, что наиболее важные результаты теории информации – теоремы о кодировании – являются теоремами о существовании и носят асимптотический характер, т.е. не являются конструктивными. Однако уже само знание потенциальных возможностей имеет огромное значение: сравнение характеристик реальных систем с теоретическими пределами позволяет судить о достигнутом уровне и о целесообразности дальнейших затрат на его повышение. Прикладные же вопросы рассматриваются в специальном разделе теории информации – теории кодирования, которая изучает способы построения конкретных кодов и их свойства, в частности точные или граничные зависимости вероятностей ошибок от параметров кода.  5.6 ————— Блок-схема системы передачи информации Для напоминания об основных понятиях теории информации приведем вариант блок-схемы системы передачи информации (рис. 5.6). На этом рисунке приведено большинство введенных в данной главе понятий и обозначений. Значение теории информации выходит далеко за рамки теории связи, так как именно ее появление привело к широкому обсуждению новых понятий, к более глубокому пониманию открытых ранее закономерностей природы (например, второго закона термодинамики) и в конечном счете к тому, что понятие информации вошло теперь в число философских категорий, расширив и углубив тем самым наше видение и понимание мира. Вместе с тем некоторые специалисты различных отраслей науки некритически распространяли методы и конкретные результаты теории информации на любые информационные процессы в реальном мире. Уже сам Шэннон заметил эту тенденцию и настоятельно предостерегал от того, чтобы ей безоглядно следовать [8]. Дело в том, что шэнноновское количество информации является характеристикой, лишь с одной стороны описывающей информационные отношения. Именно эта сторона – соответствие состояний – играет главную роль в технических устройствах. Однако в этом соответствии не проявляют себя (и, следовательно, могут не учитываться) такие свойства информации, как смысл, доброкачественность (степень истинности), ценность, полезность, временное старение, причинно-следственная направленность и т.д. – свойства, весьма существенные для информационных отношений с участием живых организмов, людей, коллективов. Исследование проблем использования информации ведется в различных направлениях, достигнуты и успехи (семиотика, теория полезности, теория решений и выбора и т.д.). С некоторыми из них мы познакомимся в других разделах книги. Необходимость расширения принципов и методов исследования информационных процессов вытекает не только из внутренней логики развития науки, стремящейся ко все большим обобщениям, снятию или ослаблению ограничений, предположений и т.п. К развитию новых подходов толкает сильное “внешнее” давление общественной практики: масштабы и значение информационных потоков в современном обществе так резко возросли в последние годы, что даже возникло образное выражение “информационный взрыв” [3] . Появилась новая отрасль – “индустрия обработки данных”, затраты на которую в промышленно развитых странах превосходят затраты на энергетику. Этой общественной потребности отвечает возникновение новой отрасли науки – информатики. Для системного анализа теория информации имеет двоякое значение. Во-первых, ее конкретные методы и результаты позволяют провести ряд количественных исследований информационных потоков в изучаемой или проектируемой системе (если в этом возникнет необходимость). Однако более важным является эвристическое значение основных понятий теории информации – неопределенности, энтропии, количества информации, избыточности, пропускной способности и пр. Их использование столь же важно для понимания системных процессов, как и использование понятий, связанных с временными, энергетическими процессами. Системный анализ неизбежно выходит на исследование ресурсов (наличных и необходимых), которые потребуются для решения анализируемой проблемы. Информационные ресурсы играют далеко не последнюю роль наряду с остальными ресурсами – материальными, энергетическими, временными, кадровыми. ЛИТЕРАТУРА
УПРАЖНЕНИЯ§ 5.1
§ 5.2
§ 5.3
§ 5.4
§ 5.5
§ 5.6
 С помощью этого метода найдите распределения, обладающие максимальной дифференциальной энтропией при заданных условиях: а)   Ответ: равномерное распределение, р(х) =1/(b – a). б)     Ответ: нормальное распределение,  в)    Ответ: экспоненциальное распределение,  Вычислите дифференциальные энтропии экстремальных распределений, полученных в предыдущем упражнении. § 5.7
Ответ:  § 5.8
Вопросы |
, называется изопериметрической задачей вариационного исчисления и сводится к решению уравнения Эйлера 
против альтернативы Н1: 
РОЛЬ ИЗМЕРЕНИЙ | Глава шестаЯ |