Лекции по теории информации. Фурсов teoria_informacii. Лекции по теории информации под редакцией Н. А. Кузнецова
 Скачать 1.32 Mb.
|
|
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА» В.А. Фурсов ЛЕКЦИИ ПО ТЕОРИИ ИНФОРМАЦИИ Под редакцией Н.А. Кузнецова Допущено учебно-методическим советом по прикладной математике и информа- тике УМО по классическому университетскому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности и направлению «Прикладная математика и информатика» и по направлению «Инфор- мационные технологии» САМАРА Издательство СГАУ 2006 2 УДК 519.72 ББК 32.811 Рецензенты: д-р ф.-м. наук. В.М. Чернов, д-р техн. наук О.В. Горячкин. Фурсов В.А. Лекции по теории информации: Учеб. пособие под редакцией Н.А. Кузнецова – Самара: Изд-во Самар. гос. аэрокосм. ун-та, 2006. – 148 с.: ил. ISBN 5-7883-0458-X В учебном пособии рассматриваются модели сигналов, основы теории ин- формации и кодирования, а также некоторые вопросы приема и обработка ин- формации. Книга составлена как сборник лекций, каждая из которых посвяще- на одной теме. Дается краткое конспективное изложение основных вопросов. Лекции занимают промежуточное положение между справочниками и солид- ными изданиями и адресованы студентам, обучающимся по учебным планам бакалавров и специалистов. Утверждено Редакционно-издательским советом Самарского государственного аэрокосмического университета в качестве учебного пособия. УДК 519.72 ББК 32.811 ISBN 5-7883-0458-X В.А. Фурсов, 2006 Самарский государственный аэрокосмический университет, 2006 3 ПРЕДИСЛОВИЕ Идея подготовки настоящего пособия возникла в связи с переходом к под- готовке прикладных математиков по двухступенчатой схеме. В учебных планах подготовки бакалавров по направлению 510200 предусматривается лекционный курс теории информации и кодирования объемом около 35 часов. В рамках ука- занного сравнительного небольшого объема необходимо было сохранить доста- точно полную и глубокую подготовку, которая традиционно обеспечивалась учебным планом подготовки по специальности 010200. В 1977 году в Куйбышевском авиационном институте (ныне Самарский государственный аэрокосмический университет) вышло в свет учебное пособие [11] (автор В.А. Сойфер). В нем рассматриваются вопросы теории информации и кодирования, которые составляют основу курса. Наряду с этим в учебные программы входят также разделы, посвященные рассмотрению моделей сигна- лов, а также вопросам их обнаружения и восстановления параметров. Это на- шло отражение в изданиях других авторов [3], [7]. Вместе с тем, в указанных книгах либо недостаточно внимания уделено фундаментальным теоремам тео- рии информации [7], либо имеет место перегруженность техническими вопро- сами реализации методов [3], что не является задачей подготовки специалистов и бакалавров по прикладной математике. В связи с этим, потребовалось пересмотреть структуризацию материала с целью придания курсу большей компактности. При отборе материала авторы стремились дать основные теоретические сведения, на которых базируется ряд последующих специальных дисциплин. В частности, включены вопросы поме- хоустойчивого кодирования с использованием линейных последовательных машин, задачи обнаружения и оценивания. Вместе с тем, от многих, излагае- мых, например, в [3] вопросов, связанных со схемными решениями, пришлось отказаться. 4 Книга составлена как сборник лекций, каждая из которых посвящена од- ной теме, что по замыслу авторов должно облегчить самостоятельную работу над курсом. В учебном пособии дается краткое конспективное изложение ос- новных вопросов. Вместе с тем, авторы стремились к тому, чтобы в пособии нашли отражение ключевые вопросы математического описания сигналов, тео- рии информации и кодирования. По замыслу лекции должны занять промежу- точное положение между справочниками и солидными изданиями. Авторы выражают признательность заведующему кафедрой технической кибернетики СГАУ, члену-корреспонденту РАН Сойферу В.А., внимательно прочитавшему рукопись и высказавшему ряд полезных советов по содержанию учебного пособия, а также Гаврилову А.В., и Козину Н.Е., выполнившим набор текста рукописи книги. Учебное пособие подготовлено при финансовой поддержке Министерства образования и науки РФ, Администрации Самарской области и Американского фонда гражданских исследований и развития (CRDF). 5 ВВЕДЕНИЕ Понятие информации. Предмет и задачи курса Термин «Информация» относится к числу наиболее часто употребляе- мых. Он широко используется в лингвистике, психологии, биологии и других науках. Однако в разных областях знаний в него вкладывают разный смысл. Разнообразие информационных процессов и широкий интерес к ним в разных областях знаний породили много толкований определений понятия “информа- ция”, а также определений количества информации. Условно все подходы к определению количества информации [6] можно разделить на пять видов: 1) энтропийный; 2) алгоритмический; 3) комбинаторный; 4) семантический; 5) прагматический. Первые три вида дают количественное определение сложности описы- ваемого объекта или явления. Четвертый – описывает содержательность и но- визну передаваемого сообщения для получателя (пользователя) сообщения. На- конец, пятый вид обращает внимание на полезность полученного сообщения для пользователя. Термин «информация» происходит от латинского слова «informatio», что означает «разъяснения», и, по сути, предполагает наличие некоторого диалога между отправителями и получателями информации. Следовательно, информа- ционное взаимодействие можно представить пятикомпонентной (пятимерной векторной) величиной, состоящей из компонент: 6 1) физической; 2) сигнальной; 3) лингвистической; 4) семантической; 5) прагматической. Заметим, что приведенное разбиение информационного взаимодействия на пять компонентов носит условный характер и возможно частичное пересе- чение в этом разбиении. Так, отдельные составляющие передаваемого сообще- ния можно отнести к физической или сигнальной, сигнальной или лингвисти- ческой компонентам. Например, рассмотрим процесс передачи информации на примере устной речи. Процесс этот многокомпонентный (векторный). Первая компонента – фи- зическая, т.е. для успешного осуществления процесса передачи информации необходимо наличие источника акустического сигнала (голосовых связок чело- века), среды для распространения акустических колебаний и приемника коле- баний (уха). Вторая компонента – сигнальная: амплитудно и частотно модули- рованные акустические колебания. Третья компонента – синтаксическая; необ- ходимо, чтобы собеседники знали хотя бы один общий язык. Четвертая компо- нента – семантическая, т.е. в передаваемом сообщении должно присутствовать содержательное описание объекта или явления, неизвестное получателю ин- формации. Наконец, пятая компонента – прагматическая: необходимо наличие желания (мотивации) передавать и принимать сообщение. На сложный, многокомпонентный характер информации указывал еще А. Н. Колмогоров [5]: «Подчеркну и качественно новое и неожиданное, что со- держится . . . в теории информации. По первоначальному замыслу «информа- ция» не есть скалярная величина. Различные виды информации могут быть чрезвычайно разнообразны . . . было совершенно неясно, можно ли качественно различные информации . . . считать эквивалентными». Один из центральных вопросов, по которому существуют разные точки зрения, состоит в следующем: информация это свойство объекта или результат 7 взаимодействия. Мы будем придерживаться точки зрения А.Н. Колмогорова: информация существует независимо от того, воспринимается она или нет, но проявляется только при взаимодействии. Информация – это характеристика внутренней организованности материальной системы по множеству состояний, которые она может принимать. Приведем пример. По срезу дерева, опытный специалист может дать за- ключение относительно его возраста, эволюции климатических условий, в ко- торых развивалось дерево, и др., однако получить эту информацию он сможет лишь в результате анализа конкретного среза дерева. Другими словами, инфор- мация объективно существует независимо от нашего сознания, но выявляется при взаимодействии с конкретным объектом. Факт объективного существования информации независимо от нашего сознания для некоторых исследователей послужил поводом для пропаганды весьма неординарной точки зрения, что информация является третьей (наряду с материей и энергией) субстанцией материального мира. Эта точка зрения наи- более уязвима, поскольку для информации пока не сформулированы фундамен- тальные законы сохранения и перехода в эквивалентных количествах в мате- рию и/или энергию. Например, при сжигании дерева информация о нем, если она не была установлена и сохранена ранее, безвозвратно теряется. Тем не ме- нее, следует подчеркнуть, что информация всегда проявляется в материально- энергетической форме в виде сигналов, хотя это не материя и не энергия, кото- рые переходят друг в друга. Информация может исчезать и появляться. В настоящем пособии термин «Информация» понимается в узком смысле, принятом при описании так называемых информационных систем [3,4,7], [11]. К ним относятся телекоммуникационные и вычислительные сети, автоматизи- рованные системы управления и контроля и т.п. В данном случае понятие ко- личества информации, определяется как частота употребления знаков. Количе- ство информации в указанном смысле не отражает ни семантики, ни прагмати- ческой ценности информации. 8 Информационные системы – это класс технических систем, предназначен- ных для хранения, передачи и преобразования информации. Соответственно информация – это сведения, являющиеся объектом хранения, передачи и пре- образования, а теория информации – раздел кибернетики, занимающийся мате- матическим описанием методов передачи, хранения, извлечения (обработки) и классификации информации. Заметим, что сама информация, как правило, ис- пользуется для осуществления каких-либо управляющих воздействий. Таким образом, предметом нашего рассмотрения является теория инфор- мации в классическом смысле – решение теоретических вопросов, касающихся повышения эффективности и функционирования информационных систем, в частности, систем связи. Она включает в себя: 1) анализ сигналов, как средства передачи информации; 2) анализ информационных характеристик источников сообщения и каналов связи; 3) теорию кодирования; 4) методы приема и обработки информации. Каждый из указанных разделов может быть (и, как правило, является) предметом самостоятельного глубокого изучения в соответствующих дисцип- линах различных специальностей информационного направления. В настоящем курсе мы стремились акцентировать внимание на наиболее общих фундамен- тальных законах, имеющих существенное значение для восприятия указанных разделов как единого целого. На наш взгляд, таким общим фундаментом явля- ются теоремы К. Шеннона о кодировании и информационная теория оценива- ния, большой вклад в развитие которой внес Я.З. Цыпкин. 9 Лекция 1 Модели детерминированных сигналов 1.1 Понятие модели сигнала Для перенесения информации в пространстве и времени она представляет- ся в форме сообщений. Сообщение, вне зависимости от его содержания, всегда отображается в виде сигнала. Построение сигнала по определенным правилам, обеспечивающим соответствие между сообщением и сигналом, называют коди- рованием. Кодирование в широком смысле – преобразование сообщения в сигнал. Кодирование в узком смысле – представление исходных знаков, называемых символами, в другом алфавите с меньшим числом знаков. Оно осуществляется с целью повышения надежности и преобразования сигналов к виду, удобному для передачи по каналам связи. Сигналы могут быть непрерывными и дискретными как по времени, так и по множеству значений, т.е. возможен один из четырех типов сигнала: 1) непрерывный (по множеству значений и времени); 2) непрерывный по множеству значений, дискретный по времени; 3) дискретный по множеству значений, непрерывный по времени; 4) дискретный (по множеству значений и времени). Иногда в теории связи рассматривают также сигналы непрерывные по времени и значениям, но дискретные по параметру. Носителем сигнала всегда является объект или процесс, однако математи- ческая модель сигнала абстрагируется от его физической природы и описывает лишь существенные с точки зрения изучаемого явления черты. Модель сигнала может даже противоречить физическим свойствам реальных объектов. Напри- мер, математическая модель сигнала в виде суммы бесконечного числа гармо- нических функций не может быть реализована на практике, однако эта абстрак- ция позволяет выявить важные закономерности. 10 В реальных информационных системах осуществляется передача только той информации, которая не известна получателю. Поэтому можно предсказать лишь вероятность каждого сообщения, а аналитической моделью сигнала, стро- го говоря, может быть только случайный процесс. Тем не менее, основой для изучения случайных сигналов является анализ детерминированных сигналов, рассматриваемых как элементы множества (ансамбля) реализаций. В настоя- щем разделе изучаются модели детерминированных сигналов. 1.2 Обобщенное спектральное представление детерминированных сигналов Для анализа прохождения сложного сигнала u t через линейную систему его обычно представляют в виде 1 2 1 , , n k k k u t c t t t t , (1.1) где k t – так называемые базисные функции, а k c – безразмерные коэффици- енты. Если базисные функции заданы, u t полностью определяется коэффи- циентами k c , которые называют дискретным спектром сигнала. За пределами интервала 1 2 , t t сигнал (1.1) считается условно продолжающимся. При рас- смотрении ряда задач такое допущение может оказаться неприемлемым. Для представления сигналов конечной длительности используют интеграл: , u t S t d , (1.2) где S – спектральная плотность, описывающая непрерывный спектр, а ,t – базисная функция, зависящая от параметра Совокупность методов, в которых используется представление сигнала в виде (1.1) и/или (1.2) называют обобщенной спектральной теорией сигналов. При этом рассматриваются частные случаи, различающиеся видом используе- мых базисных функций. Основное требование, обычно предъявляемое к базис- ным функциям, – простота вычисления коэффициентов k c . Этому требованию 11 отвечают так называемые ортогональные на отрезке 1 2 , t t базисные функции, удовлетворяющие условию 2 1 при при 0, , , t k j t j k t t dt j k (1.3) Если умножить все j t , 1, j n на 1 , то при j k 2 1 1 t k j t t t dt (1.4) Такую систему функций называют ортонормированной. Предположим, что базисные функции удовлетворяют условию (1.4). Ум- ножим обе части (1.1) на j t и проинтегрируем на интервале 1 2 , t t : 2 2 2 1 1 1 1 1 t t t n n j k k j k k j k k t t t u t t dt c t t dt c t t dt В силу (1.3) все интегралы в правой части последнего равенства при j k рав- ны нулю. Поэтому с учетом (1.4) имеем 2 1 t k k t c u t t dt (1.5) Из последнего равенства видно, что коэффициенты k c , n k , 1 могут вы- числяться независимо друг от друга, а сложность их вычисления определяется лишь видом аналитического выражения базисной функции. Указанное, связан- ное с условиями (1.3), (1.4), свойство является причиной широкого использова- ния ортогональных функций при изучении свойств сигналов. В частности, при- меняются следующие системы ортогональных функций: система тригономет- рических функций; система функций Хаара, полиномы Лежандра, полиномы Лаггерра, полиномы Чебышева, полиномы Эрмита и др. 1.3 Временная форма представления сигналов Произвольную функцию (непрерывный сигнал) u t можно представить в виде совокупности примыкающих друг к другу импульсов бесконечно малой 12 длительности с амплитудой, равной значению сигнала в текущий момент вре- мени: u t u t d , (1.6) где t – дельта-функция: при при , , 1 0 t t t d t Нетрудно заметить, что представление (1.6) является частным случаем обоб- щенного спектрального представления (1.2) с базисной функцией t С помощью дельта-функции можно построить дискретную так называе- мую решетчатую функцию: g k u t u t t k t (1.7) Функция g u t равна u k t в точках t k t , где t - период следования им- пульсов, и нулю в остальных точках. Пределы суммирования в (1.7) также как в (1.1) могут быть установлены конечными, исходя из условий физической реа- лизуемости. |