Лидовский. Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со
 Скачать 0.89 Mb.
|
|
В. В. Лидовский ТЕОРИЯ ИНФОРМАЦИИ В. В. ЛИДОВСКИЙ ТЕОРИЯ ИНФОРМАЦИИ Допущено учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению 654600 — Информатика и вычислительная техника, специальности 220200 Автоматизированные системы обработки информации и управления МОСКВА 2004 Лидовский В. В. Теория информации Учебное пособие. М Компания Спутник, 2004. — 111 с. — ISBN Электронная версия от В учебном пособии излагаются основные понятия и факты теории информации. Рассмотрены способы измерения, передачи и обработки информации. Значительное внимание уделено свойствам меры информации, характеристикам канала связи, помехозащитному, уплотняющему и криптографическому кодированию. Кроме того, рассмотрены вопросы формализации информации, в частности, в документах Internet. Изложение сопровождается большим количеством примеров и упражнений. Для студентов втузов соответствующих специальностей и всех интересующихся вопросами точной работы с информацией и методами построения кодов с полезными свойствами. Библиогр. 23 назв. Ил. РЕЦЕНЗЕНТЫ Кафедра Управления и моделирования систем Московской государственной академии приборостроения и информатики завкафедрой др. тех. наук С. Н. Музыкин), доцент Н. Я. Смирнов Для подготовки издания использовались системы plain TEX, AMS-Fonts, PICTEX и TreeTEX ББК Л 55 Введение Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со студентами-третьекурсниками в течении лет на кафедре Моделирование систем и информационные технологии” «МАТИ» — Российского государственного технологического университета им. К. Э. Циолковского. Настоящее пособие достаточно полно освещает основные положения теории информации в соответствии с Государственным образовательным стандартом РФ от 1995 г. по специальности Автоматизированные системы обработки информации и управления (220200). Содержание некоторых глав (2, 9, 33–36) пособия выходит за рамки стандарта для означенной специальности, но затронутые в них темы актуальны и органично вписываются в материал пособия. Содержание пособия во многом базируется на некоторых вводных понятиях курса Теория вероятностей дискретная случайная величина (д.с.в.), закон распределения вероятностей, математическое ожидание (мои т.п. Кроме того, от читателя требуется умение выполнять соответствующие операции с матрицами, многочленами и булевыми ве- личинами. В главах с 1 по 9 рассмотрены общие вопросы, определяющие практические подходы к использованию понятия информация, те. дано определение основных терминов, используемых при работе с информацией, очерчен круг вопросов, рассматриваемых в теории информации, приведены способы хранения, обработки, преобразования, передачи и измерения информации. В главах 10–18 рассматриваются способы сжатия информации. Рассмотрены как статистические методы (Шеннона-Фэно, Хаффмена, арифметический), таки словарные методы Лемпела-Зива. Для статистических методов приведены варианты адаптивных алгоритмов кодирования. Приводятся формулы для оценки предельной степени сжатия информации. Обзорно рассматриваются способы сжатия информации с потерями и типы файлов, содержащих сжатые данные. Глава 19 посвящена физическому уровню передачи информации по каналам связи. Рассматриваются методы расчета пропускной способности (емкости) канала, теорема Шеннона и обратная ей теорема, способы кодирования дискретной информации для передачи. Полное раскрытие названных тем требует привлечения мощного аппарата средств теории вероятностей и теории связи, выходящих за рамки соответствующих курсов студентов втузов, поэтому эти темы раскрыты лишь частично, в обзорном порядке. В главах 20–27 рассматриваются способы построения и использования избыточных кодов для защиты от помех. Приводятся фундаментальные характеристики таких кодов. Для понимания материала й главы необходимо знакомство с начальными элементами теории групп. Главы 28–32 посвящены вопросам теории защиты информации. Рассматриваются как классические криптографические системы, таки системы, построенные на идеях Диффи и Хеллмана. Кратко математический фундамент этих методов излагается в Приложении Д. В заключительных главах рассмотрены некоторые вопросы использования информации в Используемые обозначения, неопределенные явно в основном материале, приводятся в Приложении Е. Ссылки на литературу из Приложения Ж, содержащую обоснования приведенных фактов или дополнительные подробности, заключаются в квадратные скобки. Высокая требовательность студенческой аудитории является постоянным стимулом в поиске более простых, доходчивых и ясных способов изложения. Автор надеется, что это учебное пособие, формировавшееся в процессе живого общения со студентами, не получилось чрезмерно сложным. Автор считает необходимым выразить искреннюю благодарность всем тем, кто помог ему в создании этого пособия, в особенности, Пан- телееву ПА, Лидовской В. В. и Бурашникову С. Р. Предмет и основные разделы кибернетики Теория информации рассматривается как существенная часть ки- бернетики. Кибернетика — это наука об общих законах получения, хранения, передачи и переработки информации. Ее основной предмет исследования это так называемые кибернетические системы, рассматриваемые абстрактно, вне зависимости от их материальной природы. Примеры кибернетических систем автоматические регуляторы в технике, ЭВМ, мозг человека или животных, биологическая популяция, социум. Часто кибернетику связывают с методами искусственного интеллекта, т. кона разрабатывает общие принципы создания систем управления и систем для автоматизации умственного труда. Основными разделами (они фактически абсолютно самостоятельны и независимы) современной кибернетики считаются теория информации, теория алгоритмов, теория автоматов, исследование операций, теория оптимального управления и теория распознавания образов. Родоначальниками кибернетики (датой ее рождения считается год, год соответствующей публикации) считаются американские ученые Норберт Винер (Wiener, он — прежде всего) и Клод Шеннон (Shannon, он же основоположник теории информации Винер ввел основную категорию кибернетики — управление, показал существенные отличия этой категории от других, например, энергии, описал несколько задач, типичных для кибернетики, и привлек всеобщее внимание к особой роли вычислительных машин, считая их индикатором наступления новой НТР. Выделение категории управления позволило Винеру воспользоваться понятием информации, положив в основу кибернетики изучение законов передачи и преобразования ин- формации. Сущность принципа управления заключается в том, что движение и действие больших масс или передача и преобразование больших количеств энергии направляется и контролируется при помощи небольших количеств энергии, несущих информацию. Этот принцип управления лежит в основе организации и действия любых управляемых систем: автоматических устройств, живых организмов и т. п. Подобно тому, как введение понятия энергии позволило рассматривать все явления природы сединой точки зрения и отбросило целый ряд ложных теорий, таки введение понятия информации позволяет подойти сединой точки зрения к изучению самых различных процессов взаимодействия в природе. В СССР значительный вклад в развитие кибернетики внесли академики Берг АИ. и Глушков В. МВ нашей стране в е годы кибернетика была объявлена лженаукой и была практически запрещена, что не мешало, однако, развиваться всем ее важным разделам (в том числе и теории информации) вне связи с обобщающим словом кибернетика. Это было связано стем, что сама по себе кибернетика представляет собой род философии, в кое- чем конфликтной с тогдашней официальной доктриной (марксистско- ленинской диалектикой). Теория информации тесно связана с такими разделами математики как теория вероятностей и математическая статистика, а также прикладная алгебра, которые предоставляют для нее математический фундамент. С другой стороны теория информации исторически и практически представляет собой математический фундамент теории связи. Часто теорию информации вообще рассматривают как одну из ветвей теории вероятностей или как часть теории связи. Таким образом, предмет Теория информации весьма узок, т.к. зажат между чистой математикой и прикладными (техническими) аспектами теории связи. Теория информации представляет собой математическую теорию, посвященную измерению информации, ее потока, размеров канала связи и т. п, особенно применительно к радиотелеграфии, телевидению и к другим средствам связи. Первоначально теория была посвящена каналу связи, определяемому длиной волны и частотой, реализация которого была связана с колебаниями воздуха или электромагнитным излучением. Обычно соответствующий процесс был непрерывным, но мог быть и дискретным, когда информация кодировалась, а затем декодировалась. Кроме того, теория информации изучает методы построения кодов, обладающих полезными свойствами. Формальное представление знаний При формальном представлении знаний каждому описываемому объекту или понятию ставится в соответствие некоторый числовой код. Связи между кодируемыми сущностями также представляются кодами (адресами и указателями. Для такого перевода неформальных данных в формальный, цифровой вид должны использоваться специальные таблицы, сопоставляющие кодируемым сущностям их коды и называемые таблицами кодировки. Простейший пример такой таблицы — это (American Standard Code for Information Interchange), используемая повсеместно с вычислительной техникой. Она сопоставляет печатными управляющим символам (управляющими являются, например, символы, отмечающие конец строки или страницы) числа от 0 до Следующая программа на языке Паскаль выведет на экран все печатные символы этой таблицы и их коды i: byte; begin for i := 32 to 126 do write(i:6, chr(i):2); writeln На практике обычно используют не сам исходный ASCII, атак называемый расширенный ASCII (ASCII+), описывающий коды 256 символов (от 0 до 255). Первые 128 позиций расширенного ASCII совпадают со стандартом, а дополнительные 128 позиций определяются производителем оборудования или системного программного обеспечения. Кроме того, некоторым управляющим символам ASCII иногда назначают другое значение. Хотя таблицы кодировки используются для формализации информации, сами они имеют неформальную природу, являясь мостом между реальными и формальными данными. Например, коду 65 в ASCII соответствует заглавная латинская буква A, ноне конкретная, а любая. Этому коду будет соответствовать буква A, набранная жирным прямым шрифтом, и буква A, набранная нежирным с наклоном вправо на 9.5 ◦ шрифтом, и даже буква A готического шрифта. Задача сопоставления реальной букве ее кода в выбранной таблице кодировки очень сложна и частично решается программами распознания символов например Упражнение Каков код букв W ив. Виды информации Информация может быть двух видов дискретная (цифровая) и непрерывная (аналоговая. Дискретная информация характеризуется последовательными точными значениями некоторой величины, а непрерывная непрерывным процессом изменения некоторой величины. Непрерывную информацию может, например, выдавать датчик атмосферного давления или датчик скорости автомашины. Дискретную информацию можно получить от любого цифрового индикатора электронных часов, счетчика магнитофона и т.п. Дискретная информация удобнее для обработки человеком, ноне- прерывная информация часто встречается в практической работе, поэтому необходимо уметь переводить непрерывную информацию в дискретную (дискретизация) и наоборот. Модем (это слово происходит от слов модуляция и демодуляция) представляет собой устройство для такого перевода он переводит цифровые данные от компьютера в звук или электромагнитные колебания-копии звука и наоборот. При переводе непрерывной информации в дискретную важна так называемая частота дискретизации ν, определяющая период (T = 1/ν) между измерениями значений непрерывной величины (см. рис. Исходный сигнал t T • • • • • • • • • Дискретизированный сигнал Рис. Чем выше частота дискретизации, тем точнее происходит перевод непрерывной информации в дискретную. Нос ростом этой частоты растет и размер дискретных данных, получаемых при таком переводе, и, следовательно, сложность их обработки, передачи и хранения. Однако для повышения точности дискретизации необязательно безграничное увеличение ее частоты. Эту частоту разумно увеличивать только до предела, определяемого теоремой о выборках, называемой также теоремой Котельникова или законом Найквиста (Любая непрерывная величина описывается множеством наложенных друг на друга волновых процессов, называемых гармониками, определяемых функциями вида A sin(ωt + ϕ), где A — это амплитуда — частота, t — время и ϕ — фаза. Теорема о выборках утверждает, что для точной дискретизации ее частота должна быть не менее чем в два разы выше наибольшей частоты гармоники, входящей в дискретизируемую величину Примером использования этой теоремы являются лазерные ком- пакт-диски, звуковая информация на которых хранится в цифровой форме. Чем выше будет частота дискретизации, тем точнее будут воспроизводиться звуки и тем меньше их можно будет записать на один диск, но ухо обычного человека способно различать звуки с частотой до КГц, поэтому точно записывать звуки с большей частотой бессмысленно. Согласно теореме о выборках частоту дискретизации нужно выбрать не меньшей 40 КГц (в промышленном стандарте на компакт- диске используется частота 44.1 КГц). При преобразовании дискретной информации в непрерывную, определяющей является скорость этого преобразования чем она выше, стем более высокочастотными гармониками получится непрерывная величина. Но чем большие частоты встречаются в этой величине, тем сложнее с ней работать. Например, обычные телефонные линии предназначены для передачи звуков частотой до 3 КГц. Связь скорости передачи и наибольшей допустимой частоты подробнее будет рассмотрена далее. Устройства для преобразования непрерывной информации в дискретную обобщающе называются АЦП (аналого-цифровой преобразователь) или ADC (Analog to Digital Convertor, A/D), а устройства для преобразования дискретной информации в аналоговую — ЦАП (циф- ро-аналоговый преобразователь) или DAC (Digital to Analog Упражнение В цифровых магнитофонах DAT частота дискретизации — 48 КГц. Какова максимальная частота звуковых волн, которые можно точно воспроизводить на таких магнитофонах. Хранение, измерение, обработка и передача информации Для хранения информации используются специальные устройства памяти. Дискретную информацию хранить гораздо проще непрерывной, т. кона описывается последовательностью чисел. Если представить каждое число в двоичной системе счисления, то дискретная информация предстанет в виде последовательностей нулей и единиц. Присутствие или отсутствие какого-либо признака в некотором устройстве может описывать некоторую цифру в какой-нибудь из этих последовательностей. Например, позиция на дискете описывает место цифры, а полярность намагниченности — ее значение. Для записи дискретной информации можно использовать ряд переключателей, перфокарты, перфоленты, различные виды магнитных и лазерных дисков, электронные триггеры и т. п. Одна позиция для двоичной цифры в описании дискретной информации называется битом (bit, binary digit). Бит служит для измерения информации. Информация размером в один бит содержится в ответе на вопрос, требующий ответа да или нет. Непрерывную информацию тоже измеряют в битах. Бит — это очень маленькая единица, поэтому часто используется величина враз большая — байт (byte), состоящая из двух 4-битных полубайт или тетрад. Байт обычно обозначают заглавной буквой B или Б. Как и для прочих стандартных единиц измерения для бита и байта существуют производные от них единицы, образуемые при помощи приставок кило (K), мега (M), гига (G или Г, тера (T), пета (P или Пи других. Но для битов и байтов они означают не степени 10, а степени двойки кило — 2 10 = 1024 ≈ 10 3 , мега — 2 20 ≈ 10 6 , гига — 2 30 ≈ 10 9 , тера — 2 40 ≈ 10 12 , пета — 2 50 ≈ 10 15 . Например, 1 KB = 8 К = 1024 B = 8192 bit, 1 МБ = 1024 КБ = 1 048 576 Б = 8192 Кбит. Для обработки информации используют вычислительные машины, которые бывают двух видов ЦВМ (цифровая вычислительная машина для обработки дискретной информации, АВМ (аналоговая вычислительная машина) — для обработки непрерывной информации. ЦВМ универсальны, на них можно решать любые вычислительные задачи с любой точностью, нос ростом точности скорость их работы уменьшается. ЦВМ — это обычные компьютеры. Каждая АВМ предназначена только для узкого класса задач, например, интегрирования или дифференцирования. Если на вход такой АВМ подать сигнал, описываемый функцией f (t), тона ее выходе появится сигналили. АВМ работают очень быстро, но их точность ограничена и не может быть увеличена без аппаратных переделок. Программа для АВМ — это электрическая схема из заданного набора электронных компонент, которую нужно физически собрать. Бывают еще и гибридные вычислительные машины, сочетающие в себе элементы как ЦВМ, таки АВМ. На рис. 2 изображена схема передачи информации. Кодированием, например, является шифровка сообщения, декодированием его дешифровка. Процедуры кодирования и декодирования могут повторяться много раз. Ошибки при передаче информации происходят из-за шума в канале (атмосферные и технические помехи, а также при кодировании и декодировании. Теория информации изучает, в частности, способы минимизации количества таких ошибок. КОДИРОВАНИЕ КАНАЛ СВЯЗИ ДЕКОДИРОВАНИЕ ↓ ↓ ↓ ИСТОЧНИК−→ПЕРЕДАТЧИК−→ПРИЕМНИК−→ПОЛУЧАТЕЛЬ. Pис. Скорость передачи информации измеряется в количестве переданных за одну секунду бит или в бодах (baud): 1 бод = 1 бит/сек (Производные единицы для бода такие же как и для бита и байта, например Информацию можно передавать последовательно, те. бит забитом, и параллельно, те. группами фиксированного количества бит. Параллельный способ быстрее, но он часто технически сложнее и дороже особенно при передаче данных на большие расстояния. Параллельный способ передачи используют, как правило, только на расстоянии небо- лее 5 метров. Упражнение Сколько битв одном килобайте. Базовые понятия теории информации Информация — нематериальная сущность, при помощи которой с любой точностью можно описывать реальные (материальные, виртуальные (возможные) и понятийные сущности. Информация — противоположность неопределенности. Канал связи — это среда передачи информации, которая характеризуется в первую очередь максимально возможной для нее скоростью передачи данных (емкостью канала связи). Шум — это помехи в канале связи при передаче информации. Кодирование — преобразование дискретной информации одним из следующих способов шифрование, сжатие, защита от шума. Общая схема передачи информации изображена на рис. Емкость канала связи без шума можно приблизительно вычислить, зная максимальную частоту волновых процессов, допустимую в этом канале. Можно считать, что скорость передачи данных может быть не меньше, чем эта частота. Например, при предельной частоте, равной Гц, можно обеспечить скорость передачи данных не меньше Кбод. Примеры каналов связи и связанных сними предельных частот: телеграф — 140 Гц, телефон — до 3.1 КГц, короткие волны (10–100 м 3–30 МГц, УКВ (1–10 м) — 30–300 МГц, спутник (сантиметровые волны) — до 30 ГГц, оптический (инфракрасный диапазон) — 0.15– 400 ТГц, оптический (видимый свет) — 400–700 ТГц, оптический (ультрафиолетовый диапазон) — 0.7–1.75 ПГц. исходная информация шифрование −→ сжатие −→ шумозащитное кодирование ↓ шум−→ канал связи ↓ полученная информация дешифровка ←− распаковка декодирование шумозащитных кодов Рис. Типичные современные каналы телеграфный и телефонный. Перспективные, внедряемые ныне оптоволоконный (терабоды) и цифровой телефонный (ISDN, Integrated Services Digital Networks) — 57–128 Кбод. В реальных оптоволоконных системах скорость гораздо ниже теоретических пределов (редко превосходит 1–10 Гбод). Наиболее широко пока используются телефонные линии связи. Здесь достигнута скорость более 50 Кбод! 6. Способы измерения информации Понятие количества информации естественно возникает, например, в следующих типовых случаях. Равенство вещественных переменных a = b, заключает в себе информацию о том, что a равно b. Про равенство a 2 = можно сказать, что оно несет меньшую информацию, чем первое, т.к. из первого следует второе, ноне наоборот. Равенство a 3 = несет в себе информацию по объему такую же, как и первое. Пусть происходят некоторые измерения с некоторой погрешностью. Тогда чем больше будет проведено измерений, тем больше информации об измеряемой сущности будет получено. М.о. некоторой сл.в. содержит в себе информацию о самой сл.в. Для сл.в., распределенной по нормальному закону, с известной дисперсией знание м.о. дает полную информацию о сл.в.; 4. Рассмотрим схему передачи информации. Пусть передатчик описывается сл.в. X, тогда из-за помех в канале связи на приемник будет приходить сл.в. Y = X + Z, где Z — это сл.в., описывающая помехи. В этой схеме можно говорить о количестве информации, содержащейся в сл.в. Y , относительно X. Чем ниже уровень помех (дисперсия Z мала тем больше информации можно получить из Y . При отсутствии помех содержит в себе всю информацию об В 1865 г. немецкий физик Рудольф Клаузиус ввел в статистическую физику понятие энтропии или меры уравновешенности системы. В 1921 г. основатель большей части математической статистики, англичанин Роналд Фишер впервые ввел термин информация в математику, но полученные им формулы носят очень специальный харак- тер. В 1948 г. Клод Шеннон в своих работах по теории связи выписывает формулы для вычисления количества информация и энтропии. Термин энтропия используется Шенноном по совету патриарха компьютерной эры фон Неймана, отметившего, что полученные Шенноном для теории связи формулы для ее расчета совпали с соответствующими формулами статистической физики, а также то, что точно никто не знает что же такое энтропия. |