Лекция № 1

Тема: Введение. Понятие информации. Информация и данные.

1. Понятие информации

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

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

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

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

Информация, как любой объект или явления, имеет три составляющие: сущность, определение и термин.

Рассмотрим гипотезу, основанную на разделении понятия «информация» на два: «данные» и «смысл», т.к. смысл в этой паре является главным, то смысл, назовем «информацией».

С точки зрения философии информация – наиболее общее понятие наряду с материей.  Можно сказать, что она отражает организацию материи.  При этом информация не только пассивно характеризует структуру материи, но и способна активно создавать и воспроизводить эту структуру. Например, любой созданный человеком объект первоначально существует в виде идеи (образа) в голове его творца, а свойства самого человека в значительной степени запрограммированы информацией, хранящейся в его геноме.

“Антиподом” информации, характеризующей стуктурированность материи является энтропия, которая отражает ее неупорядоченность (“хаоc”).

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

2  Информация в адаптивной системе

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

Система всегда существует в определенной среде. Чтобы решать свои задачи она должна иметь собственную модель среды и постоянно корректировать ее на основе получаемых сведений (адаптировать). В рамках такого подхода информация есть «представление субъекта об окружающей среде». Напротив,  энтропия – неопределенность в таком представлении. Появление новых сведений снимает часть неопределенности и энтропия (“незнание”) заменяется информацией (“знанием”).

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

Контрольные вопросы:

1. Что понимают под информацией?
2. Что такое «информация» с точки зрения философии?
3. Какое понятие является антиподом информации?
4. Дайте пояснение понятию «модель среды».
5. Для чего служат сигналы?

Лекция 2.

Информация в человеческом обществе. Классификация информации.

         Развитие материи в процессе движения направлено в сторону усложнения структуры материальных объектов. Одна из самых сложных структур — человеческий мозг. Пока это единственная известная нам структура, обладающая свойством, которое сам человек называет сознанием. Говоря об информации мы, как мыслящие существа, априорно подразумеваем, что информация, кроме её наличия в виде принимаемых нами сигналов, имеет ещё и какой-то смысл. Формируя в своем сознании модель окружающего мира как взаимосвязанную совокупность моделей его объектов и процессов, человек использует именно смысловые понятия, а не информацию. Смысл — сущность любого феномена, которая не совпадает с ним самим и связывает его с более широким контекстом реальности. Смысл — понятие, описывающее глобальное содержание некоторого высказывания (см. БСЭ. Смысл). Само слово прямо указывает, что смысловое содержание информации могут формировать только мыслящие приемники информации. В человеческом обществе решающее значение приобретает не сама информация, а её смысловое содержание.

Пример (продолжение). Испытав такое ощущение, человек присваивает объекту понятие — «помидор», а его состоянию понятие — «красный цвет». Кроме того, его сознание фиксирует связь: «помидор» — «красного цвета». Это и есть смысл принятого сигнала. (Продолжение примера: ниже в этой секции).

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

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

Пример (продолжение). Если слова «помидор» и «красный цвет» — смысл понятий, то где же тогда информация? Информация содержится в мозге в виде определенных состояний его нейронов. Она содержится также в напечатанном тексте, состоящем из этих слов, и при кодировании букв трехразрядным двоичным кодом её количество равно 120 бит. Если произнести слова вслух, информации будет значительно больше, но смысл останется тем же. Наибольшее количество информации несёт зрительный образ. Это отражается даже в народном фольклоре — «лучше один раз увидеть, чем сто раз услышать».

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

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

• Хранение информации
• Передача информации
• Обработка информации

Классификация информации.

1. Информация подразделяется по форме представления на 2 вида:

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

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

2. По области возникновения выделяют информацию:

- элементарную (механическую), которая отражает процессы, явления неодушевленной природы;

- биологическую, которая отражает процессы животного и растительного мира;

- социальную, которая отражает процессы человеческого общества.

3. По способу передачи и восприятия различают следующие виды информации:

- визуальную, передаваемую видимыми образами и символами;

- аудиальную, передаваемую звуками;

- тактильную, передаваемую ощущениями;

- органолептическую, передаваемую запахами и вкусами;

- машинную, выдаваемую и воспринимаемую средствами вычислительной техники.

4. Информацию, создаваемую и используемую человеком, по общественному назначению можно разбить на три вида:

- личную, предназначенную для конкретного человека;

- массовую, предназначенную для любого желающего ее пользоваться (общественно-политическая, научно-популярная и т.д.) ;

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

5. По способам кодирования выделяют следующие типы информации:

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

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

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

Свойства информации можно рассматривать в трех аспектах: техническом - это точность, надежность, скорость передачи сигналов и т.д.; семантическом - это передача смысла текста с помощью кодов и прагматическом - это насколько эффективно информация влияет на поведение объекта.

Лекция 3.

Практическое занятие 1. Способы хранения, обработки и передачи информации.

2.Информационные процессы. Хранение, передача и обработка 
информации.

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

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

Информационные процессы в обществе

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

Коммуникационные системы, обеспечивающие распространение информации с помощью радио, телевидения, кино, звукозаписи,видеозаписи и печатных изданий, называются средствами массовой информации (СМИ). С появлением компьютеров развитие информационных процессов приобретает небывалый размах. Новая среда предоставляет условия обмена информацией и хранение ее в виде, удобном для корректировки и видоизменения.

Информационные процессы в живой природе.

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

Животные используют еще один способ общения, который играет важную роль в их жизни. Все вы знаете, как радостно собаки встречают своих хозяев, весело махая хвостом. Тем самым они выражают свои чувства, передают информацию. Звонок в дверь означает для собаки сигнал: «Кто-то пришел». Запах вошедшего – новая информация: знакомый или чужой.

Получить полный текст. 

Информационные процессы в технике

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

В конце XX века были созданы роботы – автоматические механизмы, управляемые компьютерами. Их используют на предприятиях для выполнения монотонных или опасных операций. Они применяются для работ в космосе, где человек не может самостоятельно работать. Эти роботы получают информацию о состоянии космического корабля и устраняют неполадки.

Сбор информации

Приходится признать, что органы чувств – наш главный инструмент познания мира – не самые совершенные приспособления. Не случайно о грубых, приблизительных вычислениях говорят: «на глаз». Без специальных приборов человек не смог бы проникнуть в тайны живой клетки или отправить к Марсу и Венере космические зонды.

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

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

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

Хранение информации

Чтобы информация стала достоянием многих людей, необходимо хранить ее не только в памяти человека. Сегодня мы используем для хранения информации самые различные материалы: бумагу, фото - и кинопленку, магнитную аудио - и видеоленту, магнитные и оптические диски. Все это – носители информации.

!  Носитель информации – материальный объект, предназначенный для хранения и передачи информации.

Передача информации

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

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

В процессе передачи информация может утрачиваться, искажаться. Это происходит из-за различных помех как в канале связи, так и при кодировании декодировании информации. Вопросами, связанными с методами кодирования и декодирования, занимается наука – криптография

Обработка информации

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

!  Входная информация – информация, которую получает человек или устройство

!  Выходная информация – информация, которая получается после обработки человеком или устройством

Поиск информации

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

3.Управление как информационный процесс. Замкнутые и разомкнутые системы управления, назначение обратной связи.

В повседневной жизни мы всюду сталкиваемся с управлением: рабочий управляет станком, учитель – учениками, дирижер – оркестром, программист – работой компьютера и ходом выполнения программы

Главное, надо знать: зачем выполняется управление? Например, летчик, садясь за штурвал самолета, должен заранее знать, куда и зачем он летит. Все это означает, что для управления надо знать конкретную цель, ожидаемый результат.

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

Например,

для водителя автомобиля исходная информация – это:

-  профессиональные знания по управлению автомобилем и о правилах дорожного движения;

-  сведения о состоянии дороги и автомобиля перед поездкой;

-  маршрут поездки.

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

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

Получить полный текст. 

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

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

Рассмотрим пример. Процесс обучения в школе построен по замкнутой схеме управления. Ученики являются объектами управления. Учитель перед началом урока обладает определенной исходной информацией: знаниями по предмету, знаниями об учениках. Эти знания позволяют ему так построить урок, чтобы ученики поняли новый материал. Применяя различные методы ведения урока, учитель оказывает на учеников управляющее воздействие. В процессе опроса учеников, что равносильно обратной связи, учитель делает вывод о том, как усвоен материал, и решает, что ему дальше делать – либо провести дополнительное разъяснение, либо дать новый материал. Он должен постоянно отслеживать текущую информацию, чтобы видеть, как реагируют ученики (объект управления) на его воздействия.

Не всегда управление осуществляется по замкнутой схеме. Например, управление потоком автомобилей и пешеходов с помощью светофора является примером незамкнутой (разомкнутой) схемы управления. Светофор не может воспринять корректирующую информацию, он выступает в роли устройства, которое только выдает управляющее воздействие. Изменение цветов светофора – управляющие сигналы. Автомобили и пешеходы выступают в качестве объектов управления.

Такой процесс получил название незамкнутого (разомкнутого) процесса управления и в виде схемы представлен на рисунке 5.2. В отличие от схемы на рисунке 5.1 в этой схеме отсутствует обратная связь – данные о состоянии объекта управления.

В зависимости от степени участия человека в процессе управления системы управления делятся на три класса: автоматические, неавтоматические и автоматизированные.

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

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

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

Лекция 4.

Измерение количества информации. Передача информации.

В информатике используются различные подходы к измерению информации:

Содержательный подход к измерению информации. Сообщение – информативный поток, который в процессе передачи информации поступает к приемнику.  Сообщение несет информацию для человека, если содержащиеся в нем сведения являются для него новыми и понятными  Информация - знания человека ? сообщение должно быть информативно. Если сообщение не информативно, то количество информации с точки зрения человека = 0. (Пример: вузовский учебник по высшей математике содержит знания, но они не доступны 1-класснику)

Алфавитный подход к измерению информации не связывает кол-во информации с содержанием сообщения. Алфавитный подход - объективный подход к измерению информации. Он  удобен при использовании технических средств работы с информацией, т.к. не зависит от содержания сообщения. Кол-во информации зависит от объема текста и мощности алфавита. Ограничений на max мощность алфавита нет, но есть достаточный алфавит мощностью 256 символов. Этот алфавит используется для представления текстов в компьютере. Поскольку 256=28, то 1символ несет в тексте 8 бит информации.

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

Количество информации  - это мера уменьшения неопределенности.

1 БИТ – такое кол-во информации, которое содержит сообщение, уменьшающее неопределенность знаний в два раза.  БИТ- это аименьшая единица измерения информации

Единицы измерения информации: 1байт = 8 бит

1Кб (килобайт) = 210 байт = 1024 байт

1Мб (мегабайт) = 210 Кб = 1024 Кб

1Гб (гигабайт) = 210 Мб = 1024 Мб

Формула  Шеннона

I  - количество информации

     N – количество возможных событий

pi – вероятности отдельных событий

Задача1: Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика, если в непрозрачном мешочке находится 50 белых, 25красных, 25 синих шариков

1) всего шаров 50+25+25=100

2) вероятности шаров 50/100=1/2, 25/100=1/4, 25/100=1/4

3)I= -(1/2 log21/2 + 1/4 log21/4 + 1/4 log21/4) = -(1/2(0-1) +1/4(0-2) +1/4(0-2)) = 1,5 бит

Количество информации достигает max значения, если события равновероятны, поэтому количество информации можно расcчитать  по формуле

Задача2 : В корзине лежит 16 шаров разного цвета. Сколько информации несет сообщение, что достали белый шар?

т.к. N = 16 шаров,  то  I = log2 N = log2 16 = 4 бит.

Лекция 5.

Экспертные системы. Вероятностный подход к измерению информации.

Существует два подхода к измерению информации: содержательный (вероятностный) и объемный (алфавитный).

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

Пусть у нас имеется монета, которую мы бросаем. С равной вероятностью произойдет одно из двух возможных событий – монета окажется в одном из двух положений: «орел» или «решка». Можно говорить, что события равновероятны.

Перед броском существует неопределенность наших знаний (возможны два события), и, как упадет монета, предсказать невозможно. После броска наступает полная определенность, так как мы видим, что монета в данный момент находится в определенном положении (например, «орел»). Это сообщение приводит к уменьшению неопределенности наших знаний в два раза, так как до броска мы имели два вероятных события, а после броска – только одно, то есть в два раза меньше.

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

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

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

N = 2I

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

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

2 = 21

Бит – наименьшая единица измерения информации.

С помощью набора битов можно представить любой знак и любое число. Знаки представляются восьмиразрядными комбинациями битов – байтами.

1байт = 8 битов = 23 битов

Байт– это 8 битов, рассматриваемые как единое целое, основная единица компьютерных данных.

Рассмотрим, каково количество комбинаций битов в байте.

Если у нас две двоичные цифры (бита), то число возможных комбинаций из них:

22=4: 00, 01, 10, 11

Объемный (алфавитный) подход к измерению информации

Существует два подхода к измерению информации: содержательный (вероятностный) и объемный (алфавитный).

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

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

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

Например, системы счисления можно рассматривать как формальные языки, имеющие алфавит (цифры) и позволяющие не только именовать и записывать объекты (числа), но и выполнять над ними арифметические операции по строго определенным правилам.

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

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

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

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

Набор символов знаковой системы (алфавит) можно рассматривать как различные возможные состояния (события).

Тогда, если считать, что появление символов в сообщении равновероятно, по формуле

N = 2I

где N– это количество знаков в алфавите знаковой системы, можно рассчитать I – количество информации, которое несет каждый символ.

Информационная емкость знаков зависит от их количества в алфавите. Так, информационная емкость буквы в русском алфавите, если не использовать букву «ё», составляет:

32 = 2I ,т.е.I = 5 битов

В латинском алфавите 26 букв. Информационная емкость буквы латинского алфавита также 5 битов.

На основании алфавитного подхода можно подсчитать количество информации в сообщении Ic, для этого необходимо умножить количество информации, которое несет один символ I, на количество символов K в сообщении:

Ic = I ´ K

Например, в слове «информатика» 11 знаков (К=11), каждый знак в русском алфавите несет информацию 5 битов (I=5), тогда количество информации в слове «информатика» Iс=5х11=55 (битов).

С помощью формулы N = 2Iможно определить количество информации, которое несет знак в двоичной знаковой системе: N=2 Þ 2=2I Þ 21=2I Þ I=1 бит

Таким образом, в двоичной знаковой системе 1 знак несет 1 бит информации. При двоичном кодировании объем информации равен длине двоичного кода.

Интересно, что сама единица измерения количества информации бит (bit) получила свое название от английского словосочетания BInary digiТ, т.е. двоичная цифра.

Чем большее количество знаков содержит алфавит знаковой системы, тем большее количество информации несет один знак.

Экспертная система — это программа (на современном уровне развития человечества), которая заменяет эксперта в той или иной области.

Отсюда вытекает простой вывод — все, что мы изучаем в курсе "Основы проектирования систем с ИИ", конечной целью ставит разработку ЭС. В этой лекции мы остановимся только на некоторых особенностях их построения, которые не затрагиваются в остальных лекциях.

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

С ЭС связаны некоторые распространенные заблуждения.

Заблуждение первое: ЭС будут делать не более (а скорее даже менее) того, чем может эксперт, создавший данную систему. Для опровержения данного постулата можно построить самообучающуюся ЭС в области, в которой вообще нет экспертов, либо объединить в одной ЭС знания нескольких экспертов, и получить в результате систему, которая может то, чего ни один из ее создателей не может.

Заблуждение второе: ЭС никогда не заменит человека-эксперта. Уже заменяет, иначе зачем бы их создавали?

Экспертные системы, методика построения

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

Рис. 9.1. Методика (этапы) разработки ЭС

Лекция 6.

Практическое занятие 2. Поиск энтропии случайных величин.

Цель: закрепить теоретические знания и получить практические навыки при вычислении энтропии.

Теоретическая часть

Рассмотрим некоторую систему Х, которая может принимать конечное множество состояний х1, х2, ... хn. Вероятность возникновения каждого состояния р1, р2, ... рn.

Примером системы Х может быть алфавит, у которого под множеством состояний понимаются символы алфавита

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

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

(1)

Энтропия обладает рядом свойств:

1. Энтропия системы всегда больше нуля.

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

3. Энтропия принимает максимальное значение, когда все состояния равновероятны.

4. Энтропия обладает свойством аддитивности, когда несколько систем объединяются в одну, их энтропии складываются.

Рассмотрим простейший случай. Система имеет два состояния и эти состояния равновероятны.

По формуле (1) имеем:

Н(х)=-(0,5log2 0,5+0,5log20,5)=1 бит/символ

Логарифм в формуле может быть взят при любом основании а>1. Выбор основания равносилен выбору определенной единицы измерения энтропии. На практике удобнее всего пользоваться логарифмами при основании два и измерять энтропию в двоичных единицах или битах. Таким образом, это энтропия одного двоичного числа, если он с одинаковой вероятностью может быть нулем или единицей.

ЭНТРОПИЯ СЛОЖНОЙ СИСТЕМЫ

Под объединением двух систем X и Y с возможными состояниями x1, x2, …, xn, y1, y2, …, ym понимается сложная система (X, Y), состояние которой (xi,yj) представляют собой все возможные комбинации состояний xi,yj . При этом число возможных состояний системы (X, Y) равно n×m.

В качестве примера сложной системы может быть взят алфавит, имеющий двухбуквенные сочетания. Обозначим pij вероятность того, что система (X, Y) будет находиться в состоянии (xi,yj). Тогда вероятности pij можно представить в виде таблицы.

Энтропия сложной системы равняется сумме произведений вероятностей всех возможных ее состояний на их логарифмы с обратным знаком

.

Энтропию сложной системы, как и энтропию простой, тоже можно записать в форме математического ожидания

.

Если системы X и Y независимы одна от другой, то при объединении систем их энтропии складываются .

Это положение называется теоремой сложения энтропий.

УСЛОВНАЯ ЭНТРОПИЯ. ОБЪЕДИНЕНИЕ ЗАВИСИМЫХ СИСТЕМ

Пусть имеются две зависимые системы X и Y. Обозначим p(yj|xi) условную вероятность того, что система Y примет состояние yj при условии, что система X находится в состоянии xi.

Частная условная энтропия системы Y при условии, что система X находится в состоянии xi определяется следующим образом

. (2)

Для нахождения полной энтропии системы каждая частная энтропия умножается на вероятность соответствующего состояния рi и все произведения складываются

,

где рi – вероятность наступления события хi.

Или

(3)

После преобразований получаем

,

где рij=рip(yj|xi).

Выражению также можно придать форму математического ожидания

.

Таким образом, полная энтропия характеризует степень неопределенности системы Y, остающейся после того, как состояние системы X полностью определилось.

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

Если две системы X и Y объединяются в одну, то энтропия объединенной системы равна энтропии первой ее составной части плюс условная энтропия второй части относительно первой

.

В частном случае, когда системы X и Y независимы, H(X|Y) = H(Y), и мы получаем рассмотренную ранее теорему сложения энтропий

.

В другом крайнем частном случае, когда состояние одной из систем полностью определяет собой состояние другой (или, как говорят, системы эквивалентны), получаем:

.

Практическая часть

1. Рассчитать значение энтропии для несбалансированного 6-гранного игрального кубика, у которого распределение задается следующей таблицей:

Значение p6 рассчитать также.

2. Рассчитать значение энтропии для сбалансированного 6-гранного игрального кубика.

3. Определить в каком случае (сбалансированный или несбалансированный кубик) больше энтропия и во сколько раз.

4. (не обязательное, на дополнительную оценку) Определить максимальное значение энтропии системы, состоящей из 8 элементов. Каждый элемент может находиться в одном из четырех состояний.

Лекция 7.

Теорема отсчетов Котельникова и Найквиста – Шеннона.

Частота Найквиста — в цифровой обработке сигналов частота, равная половине частоты дискретизации. Названа в честь Гарри Найквиста. Из теоремы Котельникова следует, что при дискретизации сигнала полезную информацию будут нести только частоты ниже частоты Найквиста. Частоты выше частоты Найквиста являются зеркальным отображением нижних частот. Если спектр сигнала не имеет составляющих выше частоты Найквиста, то он может быть оцифрован и затем восстановлен без искажений.

К примеру, в аудио компакт-дисках используется частота дискретизации 44100 герц. Частота Найквиста для них — 22050 герц, она ограничивает верхнюю полосу частот, до которой звук может быть воспроизведён без искажений.

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

Теоре́ма Коте́льникова (в англоязычной литературе — теорема Найквиста — Шеннона или теорема отсчётов) гласит, что, если аналоговый сигнал имеет ограниченный спектр, то он может быть восстановлен однозначно и без потерь по своим дискретным отсчётам, взятым с частотой строго большей удвоенной максимальной частоты спектра :

где — -верхняя частота в спектре, или (формулируя по-другому) по отсчётам, взятым с периодом , чаще полупериода максимальной частоты спектра :

Пояснение

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

Разумеется, реальные сигналы (например, звук на цифровом носителе) не обладают такими свойствами, так как они конечны по времени и, обычно, имеют во временно́й характеристике разрывы. Соответственно, их спектр бесконечен. В таком случае полное восстановление сигнала невозможно и из теоремы Котельникова вытекают 2 следствия:

Любой аналоговый сигнал может быть восстановлен с какой угодно точностью по своим дискретным отсчётам, взятым с частотой , где — максимальная частота, которой ограничен спектр реального сигнала.

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

Говоря шире, теорема Котельникова утверждает, что непрерывный сигнал можно представить в виде интерполяционного ряда

где — функция sinc. Интервал дискретизации удовлетворяет ограничениям Мгновенные значения данного ряда есть дискретные отсчёты сигнала .

стория открытия

Хотя в западной литературе теорема часто называется теоремой Найквиста со ссылкой на работу 1928 года «Certain topics in telegraph transmission theory», в этой работе речь идёт лишь о требуемой полосе линии связи для передачи импульсного сигнала (частота следования должна быть меньше удвоеной полосы). Таким образом, в контексте теоремы отсчётов справедливо говорить лишь о частоте Найквиста. Примерно в это же время Карл Купфмюллер получил тот же результат.[1] О возможности полной реконструкции исходного сигнала по дискретным отсчётам в этих работах речь не идёт. Теорема была предложена и доказана В. А. Котельниковым в 1933 году в работе «О пропускной способности эфира и проволоки в электросвязи», в которой, в частности, была сформулирована одна из теорем следующим образом[2][3]: «Любую функцию f(t), состоящую из частот от 0 до fc, можно непрерывно передавать с любой точностью при помощи чисел, следующих друг за другом через секунд». Независимо от него эту теорему в 1949 (через 16 лет!) году доказал Клод Шеннон[4], поэтому в Западной литературе эту теорему часто называют теоремой Шеннона. В 1999 году Международный научный фонд Эдуарда Рейна (Германия) признал приоритет В. А. Котельникова, наградив его премией в номинации «за фундаментальные исследования» за впервые математически точно сформулированную и доказанную в аспекте коммуникационных технологий теорему отсчётов.[5] Исторические разыскания показывают, однако, что теорема отсчётов как в части утверждения возможности реконструкции аналогового сигнала по дискретным отсчётам, так и в части способа реконструкции, рассматривалась в математическом плане многими учеными и ранее. В частности, первая часть была сформулирована ещё в 1897 году Борелем.

Лекция 8.

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

Математические модели

Математическая модель — приближенное описание объекта моделирования, выраженное с помощью математической символики.

Математические модели появились вместе с математикой много веков назад. Огромный толчок развитию математического моделирования придало появление ЭВМ. Применение вычислительных машин позволило проанализировать и применить на практике многие математические модели, которые раньше не поддавались аналитическому исследованию. Реализованная на компьютере математическая модель называется компьютерной математической моделью, а проведение целенаправленных расчетов с помощью компьютерной моделиназывается вычислительным экспериментом.

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

1. модель нужна для того, чтобы понять, как устроен конкретный объект, какова его структура, основные свойства, законы развития и взаимодействия
   с окружающим миром (понимание);
2. модель нужна для того, чтобы научиться управлять объектом (или процессом)  и определить наилучшие способы управления при заданных целях и критериях (управление);
3. модель нужна для того, чтобы прогнозировать прямые и косвенные последствия реализации заданных способов и форм воздействия на объект (прогнозирование).

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

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

Выработка концепции управления объектом — другая возможная цель моделирования. Какой режим полета самолета выбрать для того, чтобы полет был безопасным и экономически наиболее выгодным? Как составить график выполнения сотен видов работ на строительстве большого объекта, чтобы оно закончилось в максимально короткий срок? Множество таких проблем систематически возникает перед экономистами, конструкторами, учеными.

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

Второй этап: определение входных и выходных параметров модели; разделение входных параметров по степени важности влияния их изменений на выходные. Такой процесс называется ранжированием, или разделением по рангам (см. "Формализация и моделирование").

Третий этап: построение математической модели. На этом этапе происходит переход от абстрактной формулировки модели к формулировке, имеющей конкретное математическое представление. Математическая модель — это уравнения, системы уравнений, системы неравенств, дифференциальные уравнения или системы таких уравнений и пр.

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

Пятый этап: разработка алгоритма, составление и отладка программы для ЭВМ — трудно формализуемый процесс. Из языков программирования многие профессионалы для математического моделирования предпочитают FORTRAN: как в силу традиций, так и в силу непревзойденной эффективности компиляторов (для расчетных работ) и наличия написанных на нем огромных, тщательно отлаженных и оптимизированных библиотек стандартных программ математических методов. В ходу и такие языки, как PASCAL, BASIC, С, — в зависимости от характера задачи и склонностей программиста.

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

Седьмой этап: собственно вычислительный эксперимент, в процессе которого выясняется, соответствует ли модель реальному объекту (процессу). Модель достаточно адекватна реальному процессу, если некоторые характеристики процесса, полученные на ЭВМ, совпадают с экспериментально полученными характеристиками с заданной степенью точности. В случае несоответствия модели реальному процессу возвращаемся к одному из предыдущих этапов.

Математическая модель системы передачи информации

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

Пусть подсистема A передает информацию подсистеме B. Объем информации, находящийся в распоряжении подсистем, можно разде- лить на: информацию, которая имеется только у подсистемы i (i 2 fA; Bg); обозначим запас такой информации Ki; информацию, переданную подсистеме B; обозначим количество этой информации ––JA; информацию, которая воспринята подсистемой B (обозначим количество такой информации I) –– эта информация является общей для подсистем A и B.

Результативность решения задач подсистемой A зависит от информации, имеющейся в ее распоряжении и переданной информации подсистеме B, однако, эта подсистема не может контролировать восприятие информации подсистемой B. Поэтому целесообразно использовать оценку результативности подсистемой A, так что PA = PA(KA; JA). Для подсистемы B зависимость результативности решения задач PB = PB(KB; I).

В замкнутой системе количества информации KA + JA, KB не изменяются во времени, поэтому по одному аргументу из уравнений состояния можно сократить. Таким образом, уравнения состояния подсистем A, B, можно записать как: (2) PA = PA(JA) PB = PB(I):

Введем также величину SA, представляющую собой потери информации, то есть часть информации, которая была передана подсистемой A, но не воспринята подсистемой B.Математическая модель передачи информации в АОС 3 Изменения величины Pi (i 2 fA; Bg) за счет обмена информацией представляют собой ценность информации: [3]: (3) vA = dPA dJA; vB = dPB dI :

Положительное значение vi i 2 fA; Bg соответствует положительной мотивации i-ой подсистемы к обмену информацией, в случае, когда vi < 0, i-ая подсистема препятствует передаче или приему информации. Поэтому интенсивность потока информации qA(vA; vB) можно представить в простейшем случае как:

(4) qA(vA; vB) = (vA + vB);

где –– размерный коэффициент пропорциональности.

Интенсивность потока информации qA определяет изменение запасов информации у подсистемы A:

(5) dJA dt = dKA dt = qA(vA; vB):

Интенсивность получения информации подсистемой B qB < qA(vA; vB), так как существует доля информации, не воспринимаемая получателем [4].

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

qA = 0 вся переданная информация может быть воспринята; в случае, когда qA! 1, доля воспринимаемой информации стремится к нулю:

(6) qB = p(qA)qA; limqA!0 p(qA) = 1; lim qA!1 p(qA) = 0:

Величина p(qA) может иметь вероятностный смысл, как вероятность того, что элементарное количество информации, отправленной подсистеме B, будет ею воспринято. Одной из возможных функций p(qA) является экспоненциальная: (7) p(qA) = e kqA:

В каждый момент времени значение p показывает эффективность процесса обмена, однако среднее значение p за все время процесса неинформативно. Для определения показателя эффективности информационного обмена запишем баланс для величины SA = JAI:

(8) dSA dt = (1 p(qA))qA = > 0:

Величина _ представляет собой скорость потерь информации за счет

необратимости связанной с восприятием информации. По аналогии

с термодинамическими и экономическими системами эту величину

можно назвать диссипацией информации.

Лекция 9.

Энтропия. Виды энтропии. Энтропийное кодирование.

Информация и энтропия

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

Энтропия

В 1946 г. американский ученый-статистик Джон Тьюки предложил название БИТ (BIT — аббревиатура от BInary digiT), одно из главных понятий XX века. Тьюки избрал бит для обозначения одного двоичного разряда, способного принимать значение 0 или 1. Шеннон использовал бит как единицу измерения информации. Мерой количества информации Шеннон предложил считать функцию, названную им энтропией.

Пусть сообщение — осмысленное предложение на русском языке. Шеннон заметил, что при передаче различных букв мы передаем разное количество информации. Если мы передаем часто встречающиеся буквы, то информация меньше; при передаче редких букв — больше. Это видно при кодировании букв алфавита азбукой Морзе. Наиболее частые буквы передаются коротко, а для редких используют более длинные цепочки. Так, буква «Е» кодируется одной точкой «.», а редкая «Ш» — четырьмя тире «––––» (это самая длинная последовательность на букву в азбуке Морзе).

Количество информации на букву связано с частотой употреблений этой буквы во всех сообщениях, формируемых на языке. Чем более редкую букву мы передаем, тем больше в ней информации.
Энтропия — мера непредсказуемости. Это понятие Шеннон взял из статистической термодинамики. Пусть вероятность i-того символа алфавита, состоящего из n символов (мера частоты, с которой встречается символ во всех сообщениях языка), равна pi. Тогда информация одного символа:

(здесь log — логарифм по основанию 2).
Шеннон пишет: «Величина H играет центральную роль в теории информации в качестве меры количества информации, возможности выбора и неопределенности». Количество информации, передаваемое в сообщении, тесно связано с мерой неопределенности, или непредсказуемости передаваемых символов.

Избыточность

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

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

Сенсация — это редкое событие, предсказуемость которого очень мала, и потому велика его информационная стоимость. Часто информацией называют новости — сообщения о только что произошедших событиях, о которых мы еще не знаем. Но если о случившемся нам расскажут во второй и третий раз, избыточность сообщения станет очень велика, его непредсказуемость упадет  до нуля, и мы просто не станем слушать, отмахиваясь от говорящего со словами: «Знаю, знаю». Поэтому-то средства массовой информации (СМИ) и стараются быть первыми. Вот это соответствие интуитивному чувству новизны, которое рождается неожиданным известием, и сыграло главную роль в том, что статья Шеннона, не рассчитанная на массового читателя, стала сенсацией, которую подхватила пресса и которую приняли как универсальный ключ к познанию природы ученые самых разных специальностей — от лингвистов и литературоведов до биологов.
Но понятие информации, по Шеннону, — это строгая математическая теория, и ее применение за пределами теории связи очень рискованно. Зато в самой теории связи она играет центральную роль. 

Энтропи́я (информационная) — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

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

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

Формальные определения 

Информационная энтропия для независимых случайных событий  с  возможными состояниями (от 1 до ) рассчитывается по формуле:

Эта величина также называется средней энтропией сообщения. Величина  называется частной энтропией, характеризующей только -e состояние.

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

Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

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

Шеннон показал, что единственная функция, удовлетворяющая этим требованиям, имеет вид:

где  — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что измерение энтропии (), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т. д. См.: Цепи Маркова.

В общем случае -арная энтропия (где  равно 2, 3, …) источника  с исходным алфавитом  и дискретным распределением вероятности  где  является вероятностью  () определяется формулой:

Определение энтропии Шеннона связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Лекция 10.

Интерполяционная формула Уиттекера-Шеннона, частота Найквиста.

Интерполяционная формула Уиттекера — Шеннона служит для восстановления непрерывного сигнала с ограниченным спектром из последовательности равноотстоящих отсчётов.

Интерполяционная формула, как её обычно называют, восходит к работе Эмиля Бореля, датированной 1898 годом, и к работе Эдмунда Уиттекера, датированной 1915 годом. Интерполяционная формула была процитирована из работы сына Эдмунда Уиттекера — Джона Макнейтена Уиттекера, датированной 1935 годом, в виде теоремы отсчётов Найквиста — Шеннона в 1949 году, автором редакции был Клод Шеннон, до Шеннона данную теорему сформулировал Котельников. Также интерполяционную формулу обычно называют интерполяционной формулой Шеннона, или интерполяционной формулой Уиттекера.

Теорема отсчётов гласит, что при некоторых ограничивающих условиях, функция  может быть восстановлена из её дискретизации, , согласно интерполяционной формуле Уиттекера — Шеннона:

где  — период дискретизации,  — частота дискретизации,  — нормализированная sinc-функция.

Граничные условия

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

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

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

где  — период дискретизации.

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

Интерполяция как сумма свёртки

Интерполяционная формула выведенная в теореме Котельникова указывает на то что, она также может быть выражена как свёртка «гребёнки» Дирака с sinc-функцией:

Это эквивалентно фильтрации «гребёнкой» Дирака с помощью идеального низкочастотного фильтра.

Сходимость

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

Неравенство Гёльдера считается выполненным, если последовательность  принадлежит к любому из -пространств, где , что эквивалентно условию:

Это условие достаточно, но не необходимо.

Случайные стационарные процессы

Если  — бесконечная последовательность отсчётов дискретной функции в широком смысле стационарного процесса, и она не является членом любого  или или -пространства, с вероятностью 1; то сумма этих отсчётов, возведённых в степень , не принимает конечного ожидаемого значения. Несмотря на то, что интерполяционная формула сходится с вероятностью 1. Сходимость легко может быть показана путём расчёта разницы в ограниченных условиях суммирования, и свидетельствует о том, что разницу можно сделать сколь угодно малой при выборе достаточного количества условий. Если этот процесс отличен от нуля, тогда пары условий должны быть учтены таким образом, чтобы показать, что ожидаемое значение из ограниченных выражений сходится к нулю.

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

Лекция 11.

Практическое занятие 3. Применение теоремы отсчетов.

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

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

Как же часто следует брать отсчеты, чтобы по ним можно было полностью восстановить сигнал?

Ответ на этот вопрос дает теорема, доказанная в 1933 г. Советским ученым академиком В.А.Котельнико-вым. и названная его именем.

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

Теорема Котельникова является основой для дискретизации непрерывных сигналов по времени, так как, во – первых, доказывает, что непрерывный сигнал можно заменить его дискретными значениями, во – вторых, дает правило вычисления шага дискретизации – . При таком шаге дискретизации ряд Котельникова дает точное временное представление сложного сигнала.

Физический смысл теоремы Котельникова.

Теорема Котельникова утверждает, что если требуется передать непрерывный сигнал с ограниченным спектром по каналу связи, то можно не передавать все его значения: достаточно лишь передать его мгновенные значения (отсчеты) через интервал . Поскольку сигнал полностью определяется этими значениями, то по ним он может быть восстановлен на приемном конце системы связи. Для этого достаточно соединить отсчеты плавной кривой. Это можно объяснить тем, что сигнал между отсчетами может изменяться только плавно, так как частоты выше дающие быстрые изменения, в сигнале отсутствуют. Ведь отсчеты берутся достаточно часто, и тем чаще, чем выше максимальная частота .

Практическое применение теоремы Котельникова.

Дискретизация сигнала осуществляется достаточно просто: периодически на короткое время через интервал ключом замыкается цепь от источника сигнала к нагрузке – получаем отсчеты . Далее эти отсчеты, пройдя через канал связи, поступают на вход идеального фильтра нижних частот (ФНЧ) с верхней частотой пропускания . На выходе фильтра получается исходный непрерывный сигнал .

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

На передающей стороне берутся отсчеты сигнала в моменты . Далее отсчеты любым способом передаются по каналу связи. Идеальный ФНЧ на приемном конце восстанавливает исходный сигнал .

Частота следования импульсов, называемая также частотой дискретизации, определяется по теореме Котельникова:

.

Например, частота дискретизации для речевого (телефонного) сигнала, имеющего максимальное значение спектра сигнала , будет равна . Согласно рекомендациям МККТТ и, соответственно, .

Теорема Котельникова в многоканальной электросвязи.

Возможность передачи вместо непрерывных сигналов последовательности импульсов (отсчетов) позволяет осуществить временное разделение каналов. Дело в том, что при импульсной передаче период следования импульсов обычно намного больше их длительности, то есть импульсы имеют большую скважность – при большой скважности между импульсами одного сигнала остается промежуток, на котором можно разместить импульсы от других сигналов. Этот способ и называется временным разделением. В настоящее время уже реализованы многоканальные системы передачи с временным разделением каналов на 12, 15, 30, 120, 480, 1920 речевых сигналов.

Лекция 12.

Закон аддитивности информации. Формула Шеннона.

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

Информация – это одно из фундаментальных понятий современной науки, наряду с понятиями материи и энергии. По-видимому, не только понятие. В начале прошлого века Эйнштейн показал, что материя и энергия – по сути одно и то же (знаменитая формула E=mc2E=mc2). Современные исследования в физике указывают на то, что подобная связь может быть и между информацией и энергией.

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

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

Информация по Шеннону

Информация – это снятая неопределенность.

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

Это определение, однако, не слишком удобно без некоторой количественной меры неопределенности.

Величина неопределенности

количество возможных равновероятных исходов события

Так, например, игральный кубик имеет неопределенность 6.

Такой подход к определению информации называется содержательным. Он интуитивно понятен, однако, не отвечает на вопрос “сколько информации получено”.

Количество информации по Колмогорову

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

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

В качестве основной единицы количества информации принято брать бит – от binary digit.

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

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

В вопросе хранения информации, основным показателем является не количество информации, а информационный объем

Информационный объем сообщения

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

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

Формула Хартли

Сколько же информации получается в результате броска кубика?

Рассмотрим сначала более простую задачу: сколько информации получается в результате броска монеты? Считаем, что возможны два варианта: “орел” и “решка”.

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

Рассмотрим теперь бросок двух монет (или два броска одной монеты). Каждый из бросков имеет два варианта исхода. Всего мы имеем четыре варианта исхода: орел-орел, орел-решка, решка-орел, решка-решка. После бросков, мы получаем один конкретный вариант, то есть, неопределенность уменьшается в 4 раза – или дважды уменьшается в 2 раза. Мы, таким образом, получаем 2 бита информации.

Для броска трех монет, имеем 8 вариантов исхода, и в результате получаем 3 бита информации.

Интуитивно ясно, что если имеется NN равновероятных исходов, то количество информации, которое мы получаем при реализации одного из них, составляет log2Nlog2⁡N. Докажем это более строго.

ΔΔ

для набора из NN различных символов можно составить NmNm различных комбинаций (“слов”) длины mm (это утверждение легко доказывается по индукции, и известно из комбинаторики).

Существует такое k∈Nk∈N – количество необходимых для кодирования этого слова двоичных знаков – что

2k

.

Логарифмируя неравенства, получаем:

k⁡N≤k+1

или

km

. Таким образом, среднее количество информации, приходящееся на один символ kmkmотличается от log2Nlog2⁡N не более, чем на 1m1m.

Тогда при оптимальном кодировании информации (которое при неограниченном mmдостижимо с произвольной точностью), на один символ приходится log2Nlog2⁡N бит информации (или, что то же, один символ кодируется в среднем log2Nlog2⁡N двоичными символами) Δ̸Δ̸

Выражение

H=log2N,H=log2⁡N,

где HH – количество информации в символе NN-значного алфавита, называется Формулой Хартли.

Возвращаясь к кубику, количество информации, полученное в результате броска кубика составляет log26≈2.585log2⁡6≈2.585.

Применения формулы Хартли

Формула Хартли находит много различных применений. Одно из наиболее интересных заключается в оценке классов сложности вычислительных задач. Рассмотрим на примере алгоритмов сортировки.

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

Массив длинны NN имеет N!N! различных перестановок (это утверждение легко доказывается по индукции, и известно из комбинаторики).

Операция сравнения двух элементов по сути несет один бит информации (либо первый больше второго, либо меньше или равен), а по формуле Хартли количество информации, соответствующее выбору одного из N!N! вариантов H=log2(N!)H=log2⁡(N!), то есть, потребуется по крайней мере log2(N!)log2⁡(N!) операций сравнения.

Для больших NN можно использовать формулу Стирлинга для оценки факториала:

N!=2πN−−−−√NNe−N.N!=2πNNNe−N.

Тогда

H≈log2(2πN−−−−√NNe−N)=log2(2πN−−−−√)+log2(NN)+log2(e−N)=12log2(2πN)+Nlog2(N)−Nlog2(e)=12log2(2π)+(N+12)log2(N)−Nlog2(e)H≈log2⁡(2πNNNe−N)=log2⁡(2πN)+log2⁡(NN)+log2⁡(e−N)=12log2⁡(2πN)+Nlog2⁡(N)−Nlog2⁡(e)=12log2⁡(2π)+(N+12)log2⁡(N)−Nlog2⁡(e)

Поскольку Nlog2NNlog2⁡N растет быстрее, чем NN, то по порядку роста можно ввести оценку

H=O(NlogN),H=O(Nlog⁡N),

что будет соответствовать классу сложности DTIME(NlogNNlog⁡N).

Таким образом, в частности, алгоритм сортировки слиянием по порядку роста близок к теоретически оптимальному.

Закон аддитивности информации

Еще одно занимательное следствие формулы Хартли – это аддитивность информации.

Рассмотрим некую пару (x1,x2)∈X(x1,x2)∈X, где x1∈X1x1∈X1 и x2∈X2x2∈X2. Очевидно, что X=X1×X2X=X1×X2– декатрово произведение, и, если X1X1 состоит из N1N1 элементов, а X2X2 – из N2N2 элементов, то XX состоит из N1N2N1N2 элементов.

По формуле Хартли, количество информации, соответствующее выбору (x1,x2)(x1,x2) из XX равно

H(x1,x2)=log2(N1N2)H(x1,x2)=log2⁡(N1N2)

По правилом арифметики с логарифмами,

H(x1,x2)=log2(N1N2)=log2N1+log2N2H(x1,x2)=log2⁡(N1N2)=log2⁡N1+log2⁡N2

Но log2N1log2⁡N1 в свою очередь равно количеству информации, соответствующему выбору x1x1 из X1X1, а log2N2log2⁡N2 – x2x2 из X2X2. И действительно, чтобы выбрать пару (x1,x2)(x1,x2), мы можем выбрать сначала x1x1, затем x2x2.

Таким образом, по формуле Хартли,

H(x1,x2)=H(x1)+H(x2),H(x1,x2)=H(x1)+H(x2),

то есть, информация аддитивна – если мы получаем H1H1 информации об одном предмете и H2H2 – о другом, то всего мы получаем H1+H2H1+H2 информации о двух предметах.

Закон аддитивности информации

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

Этот закон легко обобщается для набора NN элементов.

Формула Шеннона

До сих пор мы рассматривали случай, когда все варианты равновероятны. Предположим, что это не так.

Пусть у нас имеется сообщение (“слово”), состоящее из символов a,ba,b, причем известно, что в сообщении есть nn символов aa и mm символов bb. Сколько информации приходится в среднем на символ этого сообщения?

Рассмотрим новый алфавит a1,…,an,b1,…,bma1,…,an,b1,…,bm из n+mn+m символов и запишем с его помощью наше сообщение таким образом, чтобы символы не повторялись. В таком случае, вероятность обнаружить какой-либо символ одинакова, и мы можем применить формулу Хартли.

Среднее количество информации на символ в таком случае,

Hn+m=log2(n+m)Hn+m=log2⁡(n+m)

. Однако, в исходном алфавите, мы не различаем символы aiai. Если бы мы делали различие между ними, то выбор одного из nn вариантов соответствовал бы количеству информации Hai=log2nHai=log2⁡n. Аналогично, Hbi=log2mHbi=log2⁡m. Однако, поскольку мы не делаем различий, мы по сути теряем эту информацию для каждого символа.

Всего на сообщение теряется nlog2n+mlog2mnlog2⁡n+mlog2⁡m бит информации, а всего информации в сообщении (n+m)log2(n+m)(n+m)log2⁡(n+m).

Таким образом, всего в сообщении в исходном алфавите содержится

HΣ=(n+m)log2(n+m)−nlog2n−mlog2m=nlog2(n+m)+mlog2(n+m)−nlog2n−mlog2m=nlog2n+mn+mlog2n+mmHΣ=(n+m)log2⁡(n+m)−nlog2⁡n−mlog2⁡m=nlog2⁡(n+m)+mlog2⁡(n+m)−nlog2⁡n−mlog2⁡m=nlog2⁡n+mn+mlog2⁡n+mm

бит информации.

Тогда среднее количество информации на один символ сообщения

H=HΣn+mH=HΣn+m

H=nn+mlog2n+mn+mn+mlog2n+mmH=nn+mlog2⁡n+mn+mn+mlog2⁡n+mm

Но Pa=nn+mPa=nn+m – это вероятность обнаружить в сообщении символ aa, а Pb=mn+mPb=mn+m – символ bb. Тогда

H=Palog21Pa+Pblog21PbH=Palog2⁡1Pa+Pblog2⁡1Pb

Это частный случай формулы Шеннона – для двух-символьного алфавита.

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

Поскольку вероятность аддитивна, Pa+Pb=1Pa+Pb=1, Pb=1−PaPb=1−Pa, можем записать HH как функцию PaPa:

H(Pa)=Palog21Pa+(1−Pa)log211−PaH(Pa)=Palog2⁡1Pa+(1−Pa)log2⁡11−Pa

График этой функции показан на рисунке:

Можно так же рассчитать производную:

dH(Pa)dPa=log21−PaPadH(Pa)dPa=log2⁡1−PaPa

и найти нули:

log21−PaPa=0log2⁡1−PaPa=0

1−PaPa=11−PaPa=1

1−Pa=Pa1−Pa=Pa

Pa=12Pa=12

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

В других случаях, выбор из двух вариантов соответствует менее чем одному биту информации.

Формула Шеннона для двух-символьного алфавита легко обобщается на случай NN-символьного алфавита по индукции:

H=∑i=1NPilog21PiH=∑i=1NPilog2⁡1Pi

ΔΔ

Действительно, база индукции для случая N=2N=2 уже доказана. Предположив, что формула верна для алфавита N−1N−1 элементов, вычислим HH для NN элементов.

Для этого, отождествим последние два символа алфавита. Для отождествленного алфавита количество информации на символ

HN−1=∑i=1N−2Pilog21Pi+(PN−1+PN)log21PN−1+PNHN−1=∑i=1N−2Pilog2⁡1Pi+(PN−1+PN)log2⁡1PN−1+PN

Среди двух отождествленных символов, каждый из них появляется с относительной вероятностью, соответственно,

qN−1=PN−1PN−1+PN,qN−1=PN−1PN−1+PN,

qN=PNPN−1+PN.qN=PNPN−1+PN.

В силу отождествления, на каждый отождествленный символ теряется

qN−1log21qN−1+qNlog21qNqN−1log2⁡1qN−1+qNlog2⁡1qN

бит информации, а их доля среди всех символов составляет PN−1+PNPN−1+PN.

Тогда в результате отождествления, мы потеряли в среднем

PN−1log21qN−1+PNlog21qNPN−1log2⁡1qN−1+PNlog2⁡1qN

бит на символ. Прибавив это выражение к HN−1HN−1, получим:

∑i=1N−2Pilog21Pi+(PN−1+PN)log21PN−1+PN+PN−1log21qN−1+PNlog21qN∑i=1N−2Pilog2⁡1Pi+(PN−1+PN)log2⁡1PN−1+PN+PN−1log2⁡1qN−1+PNlog2⁡1qN

∑i=1N−2Pilog21Pi+PN−1log21qN−1(PN−1+PN)+PNlog21qN(PN−1+PN)∑i=1N−2Pilog2⁡1Pi+PN−1log2⁡1qN−1(PN−1+PN)+PNlog2⁡1qN(PN−1+PN)

∑i=1N−2Pilog21Pi+PN−1log21PN−1+PNlog21PN∑i=1N−2Pilog2⁡1Pi+PN−1log2⁡1PN−1+PNlog2⁡1PN

∑i=1NPilog21Pi.∑i=1NPilog2⁡1Pi.

Δ̸Δ̸

Связь формул Хартли и Шеннона

Формула Хартли представляет собой частный случай формулы Шеннона.

Действительно, в предположении, что имеется набор из NN элементов, и вероятность выбора каждого элемента одинакова, то Pi=Pj=PPi=Pj=P и ∑Ni=1Pi=1∑i=1NPi=1, следовательно, P=1NP=1N. Тогда по формуле Шеннона,

H=∑i=1NPlog21P=∑i=1N1Nlog2N=log2N.H=∑i=1NPlog2⁡1P=∑i=1N1Nlog2⁡N=log2⁡N.

Мы получили формулу Хартли.

Оптимальное кодирование информации

Для достижения соответствия информационного объема и количества информации, необходимо оптимальное кодирование информации.

Легко можно показать случаи не оптимального кодирования информации. Допустим, кодируется результат падения монеты: орел или решка. Мы уже знаем, что количество информации в данном случае равно одному биту. При этом, если закодировать эти значения, например, русскими словами в коде UTF-8, то в среднем на одно значение уйдет 9 бит.

Одним из достаточно эффективных и при этом универсальных алгоритмов является алгоритм кодирования Хаффмана.

Алгоритм Хаффмана

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

Для построения кода, всем символам алфавита присваиваются значения приоритетов, соответствующие частоте появления символа.

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

После этого, “левым” ветвям дерева (с более низким приоритетом) присваивается код “0”, а “правым” (с более высоким) – “1”. Кодом символа является последовательность кодов ветвей, приводящих к нему.

Например, нам нужно оптимально закодировать сообщение “шла Маша по шоссе”. Всего сообщение состоит из 17 символов. Символы алфавита и их приоритеты:

“Склеим” символы “п”, “е”:

Теперь “л” и “м”

Теперь “пе” и “лМ”:

Действуя далее аналогично:

Приоритет последнего оставшегося узла равен длине сообщения.

Изображение соответствующего дерева:

Таким образом, коды символов:

Средний информационный вес символа по формуле Шеннона:

H=4117log217+3217log2172+317log2173+417log2174H=4117log2⁡17+3217log2⁡172+317log2⁡173+417log2⁡174

H≈2.98H≈2.98

Средний информационный вес по расчету:

H=2⋅4+3⋅3+3⋅2⋅3+4⋅417=3H=2⋅4+3⋅3+3⋅2⋅3+4⋅417=3

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

117≈0.06117≈0.06

С ростом общего числа символов в сообщении это различие будет становиться все меньше.

Лекция 13.

Теория вероятности. Дисперсия случайной величины.

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

Если случайная величина ξ имеет математическое ожидание Mξ, то дисперсией случайной величины ξ выражается так:

Dξ = M(ξ - Mξ )2.

Из этого следует, что                                        Dξ = M(ξ - Mξ )2= Mξ 2 - M(ξ)2.

Эта универсальная формула отлично применима как для дискретных случайных величин, так и для непрерывных. Величина Mξ 2 больше для дискретных и непрерывных случайных величин соответственно вычисляется по формулам:

, .

Для вычисления степени разброса значений случайной величины зачастую используют среднеквадратичное отклонение , связанное с дисперсией соотношением .

Свойства дисперсии случайной величины.

• Дисперсия каждой случайной величины неотрицательна:

• Если дисперсия случайной величины конечна, то конечно и её математическое ожидание;
• Если случайная величина = константе, то её дисперсия = 0:

Верно и обратное утверждение: если , то  почти везде;

• Дисперсия суммы двух случайных величин равна:

,

•   — их ковариация;
• Для дисперсии произвольной линейной комбинации нескольких случайных величин соответствует следующая формула:

,

где 

• Например,  для любых независимых или некоррелированных случайных величин, потому что ковариации этих случайных величин равны нулю;

Пример. Как найти математическое ожидание и дисперсию.

Предположим, случайная величина X имеет стандартное непрерывное равномерное распределение на [0,1], т.е. её плотность вероятности задана следующим равенством:

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

и формула математического ожидания случайной величины выглядит так:

Следовательно, дисперсию случайной величины найдем по формуле:

.

Лекция 14.

Локальная теорема Муавра-Лапласа.

Рассмотрим последовательность из n независимых опытов, в каждом из которых событие A может произойти с вероятностью p, либо не произойти — с вероятностью q=1−p. Обозначим через P n (k) вероятность того, что событие A произойдет ровно k раз из n возможных.

В таком случае величину P n (k) можно найти по теореме Бернулли (см. урок «Схема Бернулли. Примеры решения задач»):

Эта теорема прекрасно работает, однако у нее есть недостаток. Если n будет достаточно большим, то найти значение P n (k) становится нереально из-за огромного объема вычислений. В этом случае работаетЛокальная теорема Муавра — Лапласа, которая позволяют найти приближенное значение вероятности:

Локальная теорема Муавра — Лапласа. Если в схеме Бернулли число n велико, а число p отлично от 0 и 1, тогда:

Функция φ(x) называется функцией Гаусса. Ее значения давно вычислены и занесены в таблицу, которой можно пользоваться даже на контрольных работах и экзаменах.

Функция Гаусса обладает двумя свойствами, которые следует учитывать при работе с таблицей значений:

1. φ(−x) = φ(x) — функция Гаусса — четная;
2. При больших значениях x имеем: φ(x) ≈ 0.

Локальная теорема Муавра — Лапласа дает отличное приближение формулы Бернулли, если число испытаний n достаточно велико. Разумеется, формулировка «число испытаний достаточно велико» весьма условна, и в разных источниках называются разные цифры. Например:

1. Часто встречается требование: n · p · q > 10. Пожалуй, это минимальная граница;
2. Другие предлагают работать по этой формуле только для n>100 иn · p · q > 20.

На мой взгляд, достаточно просто взглянуть на условие задачи. Если видно, что стандартная теорема Бернулли не работает из-за большого объема вычислений (например, никто не будет считать число 58! или 45!), смело применяйте Локальную теорему Муавра — Лапласа.

К тому же, чем ближе значения вероятностей q и p к 0,5, тем точнее формула. И, наоборот, при пограничных значениях (когда p близко к 0 или 1) Локальная теорема Муавра — Лапласа дает большую погрешность, значительно отличаясь от настоящей теоремы Бернулли.

Однако будьте внимательны! Многие репетиторы по высшей математикесами ошибаются в подобных расчетах. Дело в том, что в функцию Гаусса подставляется довольно сложное число, содержащее арифметический квадратный корень и дробь. Это число обязательно надо найти еще до подстановки в функцию. Рассмотрим все на конкретных задачах:

Задача. Вероятность рождения мальчика равна 0,512. Найдите вероятность того, что среди 100 новорожденных будет ровно 51 мальчик.

Итак, всего испытаний по схеме Бернулли n = 100. Кроме того, p = 0,512, q= 1 − p = 0,488.

Поскольку n = 100 — это достаточно большое число, будем работать по Локальной теореме Муавра — Лапласа. Заметим, что n · p · q = 100 · 0,512 · 0,488 ≈ 25 > 20. Имеем:

Поскольку мы округляли значение n · p · q до целого числа, ответ тоже можно округлить: 0,07972 ≈ 0,08. Учитывать остальные цифры просто нет смысла.

Задача. Телефонная станция обслуживает 200 абонентов. Для каждого абонента вероятность того, что в течение одного часа он позвонит на станцию, равна 0,02. Найти вероятность того, что в течение часа позвонят ровно 5 абонентов.

По схеме Бернулли, n = 200, p = 0,02, q = 1 − p = 0,98. Заметим, что n = 200 — это неслабое число, поэтому используем Локальную теорему Муавра — Лапласа. Для начала найдем n · p · q = 200 · 0,02 · 0,98 ≈ 4. Конечно, 4 — это слишком мало, поэтому результаты будут неточными. Тем не менее, имеем:

Округлим ответ до второго знака после запятой: 0,17605 ≈ 0,18. Учитывать больше знаков все равно не имеет смысла, поскольку мы округляли n · p ·q = 3,92 ≈ 4 (до точного квадрата).

Задача. Магазин получил 1000 бутылок водки. Вероятность того, что при перевозке бутылка разобьется, равна 0,003. Найти вероятность того, что магазин получит ровно две разбитых бутылки.

По схеме Бернулли имеем: n = 1000, p = 0,003, q = 0,997. Отсюда n · p · q= 2,991 ≈ 1,732 (подобрали ближайший точный квадрат). Поскольку числоn = 1000 достаточно велико, подставляем все числа в формулу Локальной теоремы Муавра — Лапласа:

Мы сознательно оставляем лишь один знак после запятой (на самом деле там получится 0,1949...), поскольку изначально использовали довольно грубые оценки. В частности: 2,991 ≈ 1,732. Тройка в числителе внутри функции Гаусса возникла из выражения n · p = 1000 · 0,003 = 3.

Лекция 15.

Практическое занятие 4. Расчет вероятностей.

Классическая формула вычисления               вероятности.

Основные определения и формулы:

Эксперимент, исход которого невозможно предсказать, называют случайным экспериментом (СЭ).

Событие, которое в данном СЭ может произойти, а может и не произойти, называют случайным событием.

Элементарными исходами называют события, удовлетворяющие требованиям:

1.     при всякой реализации СЭ происходит один и только один элементарный исход;

2.     всякое событие есть некоторая комбинация, некоторый набор элементарных исходов.

Множество всех возможных элементарных исходов полностью описывает СЭ. Такое множество принято называть пространством элементарных исходов (ПЭИ). Выбор ПЭИ для описания данного СЭ неоднозначен и зависит от решаемой задачи.

Если элементарные исходы СЭ обладают свойством равновозможности (в силу определенной “симметрии” условий), то вероятность Р(А) любого события А определяется формулой:

Р(А) = n(A) / n ,

где n – общее число равновозможных исходов,

 n(A) – число исходов, составляющих событие А, как говорят еще,  благоприятствующих событию А.

Слова “наудачу”, “наугад”, “случайным образом” как раз и гарантируют равновозможность элементарных исходов.

Решение типовых примеров

Пример 1. Из урны, содержащей 5 красных, 3 черных и 2 белых шара, наудачу извлекают 3 шара. Найти вероятности событий:

А – “все извлеченные шары красные”;

В – “ все извлеченные шары – одного цвета”;

С – “среди извлеченных ровно 2 черных”.

Решение :

Элементарным исходом данного СЭ является тройка (неупорядоченная !) шаров. Поэтому, общее число исходов есть число сочетаний: n == 120 (10 = 5 + 3 + 2).

Событие А состоит только из тех троек, которые извлекались из пяти красных шаров, т.е. n(A)== 10.

Событию В кроме 10 красных троек благоприятствуют еще и черные тройки, число которых равно= 1. Поэтому: n(B)=10+1=11.

Событию С благоприятствуют те тройки шаров, которые содержат 2 черных и один не черный. Каждый способ выбора двух черных шаров может комбинироваться с выбором одного не черного (из семи). Поэтому: n(C) = = 3 * 7 = 21.

Итак: Р(А) = 10/120;  Р(В) = 11/120;  Р(С) = 21/120.

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

D – “максимальный извлеченный номер равен 4”;

Е – “ максимальный извлеченный номер равен 3”.

Решение :

Для вычисления n(D) можно считать, что в урне есть один шар с номером 4, один шар с большим номером и 8 шаров (3к+3ч+2б) с меньшими номерами. Событию D благоприятствуют те тройки шаров, которые обязательно содержат шар с номером 4 и 2 шара с меньшими номерами. Поэтому: n(D) = 

P(D) = 28/120.

Для вычисления n(Е) считаем: в урне два шара с номером 3, два с большими номерами и шесть шаров с меньшими номерами (2к+2ч+2б). Событие Е состоит из троек двух типов:

1.   один шар с номером 3 и два с меньшими номерами;

2.   два шара с номером 3 и один с меньшим номером.

Поэтому: n(E)=

Р(Е) = 36/120.

Пример 3. Каждая из М различных частиц бросается наудачу в одну из N ячеек. Найти вероятности событий:

А – все частицы попали во вторую ячейку;

В – все частицы попали в одну ячейку;

С – каждая ячейка содержит не более одной частицы (M £ N);

D – все ячейки заняты (M=N+1);

Е – вторая ячейка содержит ровно к частиц.

Решение :

Для каждой частицы имеется N способов попасть в ту или иную ячейку. По основному принципу комбинаторики для М частиц имеем N*N*N*…*N (М-раз). Итак, общее число исходов в данном СЭ n = NM.

Для каждой частицы имеем одну возможность попасть во вторую ячейку, поэтому n(A) = 1*1*…*1= 1М = 1, и Р(А) = 1/ NM.

Попасть в одну ячейку (всем частицам) означает попасть всем в первую, или всем во вторую, или и т.д. всем в N-ю. Но каждый из этих N вариантов может осуществиться одним способом. Поэтому n(B)=1+1+…+1(N-раз)=N и Р(В)=N/NM.

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

 n (C) = N*(N-1)*…*(N+M-1) и Р(С) = 

В частном случае при M=N :  Р(С)=

Событие D означает, что одна из ячеек содержит две частицы, а каждая из (N-1) оставшихся ячеек содержит по одной частице. Чтобы найти n(D) рассуждаем так: выберем ячейку в которой будет две частицы, это можно сделать =N способами; затем выберем две частицы для этой ячейки, для этого существует  способов. После этого оставшиеся (N-1) частиц распределим по одной в оставшиеся (N-1) ячеек, для этого имеется (N-1)! способов.

Итак, n(D) = 

 .

Число n(E) можно подсчитать так: к частиц для второй ячейки можно  способами, оставшиеся (М – К) частиц распределяются произвольным образом по (N-1) ячейке (N-1)М-К способами. Поэтому :

Лекция 16.

Алгоритмы сжатия информации. Методы Лемпела-Зива.

Алгоритм LZW

Алгоритм Лемпеля — Зива — Велча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь.

Непосредственным предшественником LZW явился алгоритм LZ78, опубликованный Абрахамом Лемпелем(Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel-Ziv-Welch).

Описание

Процесс сжатия выглядит следующим образом. Последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова. 
Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от «0» до «255»). Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 256 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом. 
Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового. Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер. Следовательно, при дешифровании при получении нового кода генерируется новая строка, а при получении уже известного, строка ивлекается из словаря.

Псевдокод алгоритма

1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения.
2. Считать очередной символ K из кодируемого сообщения.
3. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, иначе:
4. Если фраза ω(K) уже есть в словаре, присвоить входной фразе значение ω(K) и перейти к Шагу 2, иначе выдать код ω, добавить ω(K) в словарь, присвоить входной фразе значение K и перейти к Шагу 2.
5. Конец

Пример

Просто по псевдокоду понять работу алгоритма не очень легко, поэтому рассмотрим Рассмотрим пример сжатия и декодирования изображения.
Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется 256 различных символов, поэтому, для того, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в исходном файле, а какие — нет), начальный размер кода будет равен 8 битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит. Чтобы инициализировать таблицу, мы установим соответствие кода 0 соответствующему символу с битовым кодом 00000000, тогда 1 соответствует символу с кодом 00000001, и т.д., до кода 255. На самом деле мы указали, что каждый код от 0 до 255 является корневым.
Больше в таблице не будет других кодов, обладающих этим свойством.
По мере роста словаря, размер групп должен расти, с тем, чтобы учесть новые элементы. 8-битные группы дают 256 возможных комбинации бит, поэтому, когда в словаре появится 256-е слово, алгоритм должен перейти к 9-битным группам. При появлении 512-ого слова произойдет переход к 10-битным группам, что дает возможность запоминать уже 1024 слова и т.д.
В нашем примере алгоритму заранее известно о том, что будет использоваться всего 5 различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть 3 ( 8 различных комбинаций ).

Кодирование

Пусть мы сжимаем последовательность «abacabadabacabae».

• Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “a” и проверим, есть ли строка “a” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “a” есть в таблице.
• Шаг 2: Далее мы читаем следующий символ «b» из входного потока и проверяем, есть ли строка “ab” в таблице. Такой строки в таблице пока нет.
• Добавляем в таблицу <5> “ab”. В поток: <0>;
• Шаг 3: “ba” — нет. В таблицу: <6> “ba”. В поток: <1>;
• Шаг 4: “ac” — нет. В таблицу: <7> “ac”. В поток: <0>;
• Шаг 5: “ca” — нет. В таблицу: <8> “ca”. В поток: <2>;
• Шаг 6: “ab” — есть в таблице; “aba” — нет. В таблицу: <9> “aba”. В поток: <5>;
• Шаг 7: “ad” — нет. В таблицу: <10> “ad”. В поток: <0>;
• Шаг 8: “da” — нет. В таблицу: <11> “da”. В поток: <3>;
• Шаг 9: “aba” — есть в таблице; “abac” — нет. В таблицу: <12> “abac”. В поток: <9>;
• Шаг 10: “ca” — есть в таблице; “cab” — нет. В таблицу: <13> “cab”. В поток: <8>;
• Шаг 11: “ba” — есть в таблице; “bae” — нет. В таблицу: <14> “bae”. В поток: <6>;
• Шаг 12: И, наконец последняя строка “e”, за ней идет конец сообщения, поэтому мы просто выводим в поток <4>.

 Итак, мы получаем закодированное сообщение «0 1 0 2 5 0 3 9 8 6 4», что на 11 бит короче.

Декодирование

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

Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например aaaaaa … или 30, 30, 30 … и т. п. Их непосредственное сжатие будет генерировать выходной код 0, 0, 5 и т.д. Спрашивается, можно ли в этом частном случае повысить степень сжатия?
Оказывается, это возможно, если оговорить некоторые действия:
Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.

• Итак, кодировщик заносит первую «а» в строку, ищет и находит «а» в словаре. Добавляет в строку следующую «а», находит, что «аа» нет в словаре. Тогда он добавляет запись <5>: «аа» в словарь и выводит метку <0> («а») в выходной поток.
• Далее строка инициализируется второй «а», то есть принимает вид «a?» вводится третья «а», строка вновь равна «аа», которая теперь имеется в словаре.
• Если появляется четвертая «а», то строка «aa?» равна «ааа», которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <5> («aa»).
• После этого строка инициализируется третьей «а», и т.д. и т.п. Дальнейший процесс вполне ясен.
• В результате на выходе получаем последовательность 0, 5, 6 …, которая короче прямого кодирования стандартным методом LZW.

Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <0>, которому соответствует символ «a». Затем читает код <5>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть «a». Поэтому он добавит в свою таблицу строку «aa» с кодом <5>, а в выходной поток поместит «aa». И так может быть раскодирована вся цепочка кодов.
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.

Достоинства и недостатки

+ Не требует вычисления вероятностей встречаемости символов или кодов.
+ Для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.
+ Данный тип компрессии не вносит искажений в исходный графический файл, и подходит для сжатия растровых данных любого типа.
- Алгоритм не проводит анализ входных данных поэтому не оптимален.

Применение

Опубликование алгоритма LZW произвело большое впечатление на всех специалистов по сжатию информации. За этим последовало большое количество программ и приложений с различными вариантами этого метода.
Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время испольуется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

Алгоритмы LZ77 и LZ78

LZ77 и LZ78 — алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы наиболее известны в семействе LZ*, которое включает в себя также LZW, LZSS, LZMA и другие алгоритмы. Оба алгоритма относятся к алгоритмам со словарным подходом. LZ77 использует, так называемое, «скользящее окно», что эквивалентно неявному использованию словарного подхода, впервые предложенного в LZ78.

Принцип работы LZ77

Основная идея алгоритма это замена повторного вхождения строки ссылкой на одну из предыдущих позиций вхождения. Для этого используют метод скользящего окна. Скользящее окно можно представить в виде динамической структуры данных, которая организована так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам скользящего окна, и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в скользящем окне. В стандартном алгоритме LZ77 совпадения строки кодируются парой:

• длина совпадения (match length)
• смещение (offset) или дистанция (distance)

Кодируемая пара трактуется именно как команда копирования символов из скользящего окна с определенной позиции, или дословно как: «Вернуться в словаре на значение смещения символов и скопировать значение длины символов, начиная с текущей позиции». Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары длина-смещение является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения. Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними. Это означает, что каждый символ можно однозначно определить переместившись назад в буфере, даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары длина-смещение.

Описание алгоритма

LZ77 использует скользящее по сообщению окно. Допустим, на текущей итерации окно зафиксировано. С правой стороны окна наращиваем подстроку, пока она есть в строке <скользящее окно + наращиваемая строка> и начинается в скользящем окне. Назовем наращиваемую строку буфером. После наращивания алгоритм выдает код состоящий из трех элементов:

• смещение в окне;
• длина буфера;
• последний символ буфера.

В конце итерации алгоритм сдвигает окно на длину равную длине буфера+1.

Пример kabababababz

 Описание алгоритма LZ78

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

Пример kabababababz

Лекция 17.

Сжатие информации, компрессия, англ. data compression — алгоритмическое преобразование данных (кодирование), при котором за счет уменьшения их избыточности уменьшается их обьём.

Принципы сжатия информации

В основе любого способа сжатия информации лежит модель источника информации, или, более конкретно, модель избыточности. Иными словами для сжатия информации используются некоторые сведения о том, какого рода информация сжимается — не обладая никакми сведениями об информации нельзя сделать ровным счётом никаких предположений, какое преобразование позволит уменьшить объём сообщения. Эта информация используется в процессе сжатия и разжатия. Модель избыточности может также строиться или параметризоваться на этапе сжатия. Методы, позволяющие на основе входных данных изменять модель избыточности информации, называются адаптивными. Неадаптивными являются обычно узкоспецифичные алгоритмы, применяемые для работы с хорошо определёнными и неизменными характеристиками. Подавляющая часть же достаточно универсальных алгоритмов являются в той или иной мере адаптивными.

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

• преобразование сжатия;
• преобразование расжатия.

Преобразование сжатия обеспечивает получение сжатого сообщения из исходного. Разжатие же обеспечивает получение исходного сообщения (или его приближения) из сжатого.

Все методы сжатия делятся на два основных класса

• без потерь,
• с потерями.

Кардинальное различие между ними в том, что сжатие без потерь обеспечивает возможность точного восстановления исходного сообщения. Сжатие с потерями же позволяет получить только некоторое приближение исходного сообщения, то есть отличающееся от исходного, но в пределах некоторых заранее определённых погрешностей. Эти погрешности должны определяться другой моделью — моделью приёмника, определяющей, какие данные и с какой точностью представленные важны для получателя, а какие допустимо выбросить.

Характеристики алгоритмов сжатия и применимость

Коэффициент сжатия

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

k = So/Sc,

где k — коэффициент сжатия, So — размер несжатых данных, а Sc — размер сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм лучше. Следует отметить:

• если k = 1, то алгоритм не производит сжатия, то есть получает выходное сообщение размером, равным входному;
• если k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Ситуация с k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Шаблон:Е:бит составляет ровно 2n. Тогда количество различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить.

Коэффициент сжатия может быть как постоянным коэффициентом (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, μ-закон, ADPCM), так и переменным. Во втором случае он может быть определён либо для какого либо конкретного сообщения, либо оценён по некоторым критериям:

• среднее (обычно по некоторому тестовому набора данных);
• максимальное (случай наилучшего сжатия);
• минимальное (случай наихудшего сжатия);

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

Допустимость потерь

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

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

Однако сжатие с потерями позволяет добиться гораздо больших коэффициентов сжатия за счёт отбрасывания незначащей информации, которая плохо сжимается. Так, например алгоритм сжатия звука без потерь FLAC, позволяет в большинстве случаев сжать звук в 1,5—2,5 раза, в то время как алгоритм с потерями Vorbis, в зависимости от установленного параметра качетсва может сжать до 15 раз с сохранением приемлемого качества звучания.

Системные требования алгоритмов

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых исполняются:

• оперативной памяти (под промежуточные данные);
• постоянной памяти (под код программы и константы);
• процессорного времени.

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

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

Алгоритм сжатия гораздо требовательнее к ресурсам, нежели алгоритм расжатия.

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

Алгоритмы сжатия и расжатия имеют примерно равные требования.

Наиболее приемлемый вариант для линии связи, когда сжатие и расжатие происходит однократно на двух её концах. Например, это могут быть телефония.

Алгоритм сжатия существенно менее требователен, чем алгоритм разжатия.

Довольно экзотический случай. Может применяться в случаях, когда передатчиком является ультрапортативное устройство, где объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков, или это могут быть данные распаковка которых требуется в очень малом проценте случаев, например запись камер видеонаблюдения.

Лекция 18.

Алгоритмы сжатия неизвестного формата.

Имеется два основных подхода к сжатию данных неизвестного формата:

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

Лекция 19.

Практическое занятие 5. Практическое применение алгоритмов сжатия.

Эффективность работы большинства цифровых видеосистем во многом определяется примененными в них алгоритмами сжатия видеосигнала.

Действительно, первоначальный объем пакета информации от одного кадра цветного видеосигнала стандартного разрешения составляет приблизительно 650 кбайт, и такой пакет "выбрасывается" каждой камерой в систему 25 раз в секунду. Это означает, что для 16 камер цифровой поток составляет 260 Мбайт/с и каждую минуту заполняется почти 16 гекабайт дискового пространства. Разумеется, подобная цифровая система малопригодна для реальной жизни.

Только внедрение прогрессивных технологий сжатия, то есть уменьшения объема пакета, позволило примирить мечту с действительностью. Если объем пакета от одного кадра после сжатия составит 3 килобайта (довольно типичная величина), то для рассмотренного выше примера получим цифровой поток в 1,2 Мбайт/с и каждую минуту будем заполнять 72 мегабайта памяти, что довольно просто обеспечивается на современном уровне развития цифровых технологий. Однако, несмотря на важность выбора типа применяемого сжатия, потребитель зачастую не представляет, что стоит за тем или иным названием конкретного алгоритма сжатия.

Алгоритмы сжатия видеосигнала

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

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

Проще всего это пояснить на примере разложения сигнала по гармоническим функциям – преобразования Фурье. Физику же такого сжатия проще всего объяснить, в свою очередь, на примере человеческого глаза. Принято считать, что человеческий глаз позволяет воспринимать 700 мегабайт видеоинформации в секунду. Однако наш мозг использует лишь 1/1000 долю этой информации, отдавая предпочтение той ее части, в которой происходят резкие изменения. Степень "быстроты" изменения, при котором информация воспринимается наиболее полно, зависит от важности происходящего события. Точно так же и при данном сжатии видеосигнал каждый кадр подвергается дискретному Фурье-преобразованию и производится удаление верхних частотных составляющих (в зависимости от выставленного в программе "уровня внимания" записываются все более или менее крупные изменения изображения). Чем выше частота обрезания, тем больше объем записываемой информации и соответственно меньше степень ее сжатия. Как показывает опыт, таким образом можно добиться фактора сжатия до 20 раз при вполне приемлемом качестве восстановленной картинки.

Однако у процесса разложения по гармоническим функциям есть большой недостаток, а именно: каждая из этих функций бесконечна и поэтому мы в любом случае должны "отрезать" длинные "хвосты" колебаний либо "тащить" их с собой, сводя на нет весь эффект сжатия. Поэтому разработчики попробовали подобрать и иной альтернативный набор базовых функций, локальных в своем размере. Как образно сказал один из пионеров данных разработок Robi Policar, эти функции должны позволять "увидеть и лес, и деревья", в то время как, продолжая его аналогию, методы сжатия, использующие Фурье-преобразование, вынуждают вас выбрать что-либо одно то есть "либо лес, либо деревья". Была разработана целая группа подобных базовых функций (их назвали по зрительной аналогии "маленькими волнами" – вейвлетами). Наиболее известные из них приведены на рис. 1.

Любой исходный пакет информации в этих алгоритмах раскладывается по подобным вейвлетам при помощи применения к ним операций сдвига – shifting и масштабирования (расширения/сжатия) – scaling. Еще раз подчеркнем, что принципиальным моментом этих алгоритмов является то, что используемые базовые функции локальны во времени (в этом и есть смысл их названия "маленькие волны"), то есть имеют конечную энергию в отличие от гармонических функций ("больших волн") Фурье-анализа. Это позволяет выполнять сжатие информации с фактором сжатия до 100 раз, при вполне приемлемом качестве восстановленной картинки.

В свою очередь "сторонники" гармонического разложения также не остановились на достигнутом. Имея на руках такие свойства Фурье-преобразования, как простота его реализации и общераспространенность получаемого графического формата, они ринулись в бой. Практически проиграв на поле статичных изображений, они "вспомнили", что видеосигнал – есть последовательность из различных кадров. Значит, если научиться выделять в этой последовательности отдельные области (названные "макроблоками"), изменение которых от кадра к кадру мало или легко прогнозируемо, можно в целом существенно увеличить фактор сжатия. Были разработаны довольно хитрые алгоритмы, базирующиеся, тем не менее, на основе столь любимого многими дискретного Фурье-преобразования. Основная их идея – прогноз движения устойчивых объектов изображения от кадра к кадру. Например, в первом кадре изображение делится на мини-блоки 8х8 точек и макроблоки 16х16 (возможны и другие размеры макро-блоков в разных случаях) и осуществляется их обычное Фурье-преобразование. В последующих кадрах ищется новое местоположение имевшихся ранее макроблоков и на основании сравнения выполняется предсказание будущего их местоположения. Правильность прогноза периодически проверяется. Таким образом, можно достигнуть фактора сжатия видеопотока того же порядка, что и при использовании вейвлетов, а также при сохранении всех преимуществ Фурье-преобразования.

Вы думаете, что сторонники вейвлетов "сдались" на поле динамичных видеопотоков? Ничего подобного. Несмотря на то, что осуществить сложную межкадровую обработку практически невозможно, они разработали, тем не менее, алгоритмы, реализующие в какой-то мере межкадровую обработку (хотя и в самом простом ее виде).

Таким образом, на настоящий момент вопрос о том, на ком "надета желтая майка лидера" остается открытым. Определяющим будет, как всегда, практический опыт.

Практическое применение алгоритмов сжатия

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

1. JPEG и M-JPEG
2. MPEG2
3. MPEG4
4. H.263 и его клоны
5. JPEG2000
6. Wavelet и его клоны

Искать физическую сущность в приведенных названиях абсолютно бесполезно (кроме Wavelet, использующего вейвлеты), ибо названия их в большинстве случаев происходят от названий групп специалистов, занимающихся разработкой тех или иных стандартов. Более того, во внешне похожих методах JPEG и JPEG2000 используются абсолютно разные механизмы, а внешне различные MPEG-2 и H.263 довольно похожи. Поскольку практически все существующие механизмы мы рассмотрели выше, представим суть всех практических методик в графическом виде на рис. 2.

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

Лекция 20.

Помехоустойчивое и адаптивное арифметическое кодирование.

Принципы сжатия данных

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

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

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

Необратимое сжатие имеет обычно гораздо более высокую степень сжатия, чем кодирование без потерь, но допускает некоторые отклонения декодированных данных от исходных. На практике существует широкий круг практических задач, в которых соблюдение требования точного восстановления исходной информации после декомпрессии не является обязательным. Это, в частности, относится к сжатию мультимедийной информации: звука, фото- или видеоизображений. Так, например, широко применяются форматы мультимедийной информации JPEG и MPEG, в которых используется необратимое сжатие. Необратимое сжатие обычно не используется совместно с криптографическим шифрованием, так как основным требованием к криптосистеме является идентичность расшифрованных данных исходным. Однако при использовании мультимедиа-технологий данные, представленные в цифровом виде, часто подвергаются необратимой компрессии перед подачей в криптографическую систему для шифрования. После передачи информации потребителю и расшифрования мультимедиа-файлы используются в сжатом виде (то есть не восстанавливаются).

Рассмотрим подробнее некоторые из наиболее распространённых способов обратимого сжатия данных.

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем – это кодирование серий последовательностей (RunLength Encoding – RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов на один кодирующийбайт-заполнитель и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других, – не кодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток вначале кодированных цепочек. Такими метками могут быть характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже – с малым числом повторяющихся байтов в сериях.

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

Одними из широко используемых на практике являются словарные методы, к основным представителям которых относятся алгоритмы семейства Зива и Лемпела. Их основная идея заключается в том, что фрагменты входного потока ("фразы") заменяются указателем на томесто, где они в тексте уже ранее появлялись. В литературе подобные алгоритмы обозначаются как алгоритмы LZ сжатия.

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

Другим подходом к сжатию информации является код Хаффмана, кодер и декодер которого имеют достаточно простую аппаратную реализацию. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды, тогда как реже встречающимся символам – более длинные. За счет этого достигается сокращение средней длины кодового слова и большая эффективность сжатия. Коды Хаффмана имеют уникальный префикс (начало кодового слова), что и позволяет однозначно их декодировать, несмотря на их переменную длину.

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

Пусть источник информации способен генерировать четыре различных символа S1…S4 с вероятностями возникновения p(S1)=0,2, p(S2)=0,15, p(S3)=0,55, p(S4)=0,1. Отсортируем символы по убыванию вероятности появления и представим в виде таблицы ( рис. 14.3, а).

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

Рис. 14.3. Первый этап кодирования Хаффмана

На втором этапе осуществляется построение кодового дерева по свернутой таблице ( рис. 14.4, а). Дерево строится, начиная с последнего столбца таблицы.

Рис. 14.4. Второй этап кодирования Хаффмана

Корень дерева образует единица, расположенная в последнем столбце. В рассматриваемом примере эта единица образуется из вероятностей 0,55 и 0,45, изображаемых в виде двух узлов дерева, связанных с корнем. Первый из них соответствует символу S3 и, таким образом, дальнейшее ветвление этого узла не происходит.

Второй узел, маркированный вероятностью 0,45, соединяется с двумя узлами третьего уровня, с вероятностями 0,25 и 0,2.Вероятность 0,2 соответствует символу S1, а вероятность 0,25, в свою очередь, образуется из вероятностей 0,15 появления символаS2 и 0,1 появления символа S4.

Ребра, соединяющие отдельные узлы кодового дерева, нумеруются цифрами 0 и 1 (например, левые ребра – 0, а правые – 1 ). На третьем, заключительном этапе, строится таблица, в которой сопоставляются символы источника и соответствующие им кодовые слова кода Хаффмана. Эти кодовые слова образуются в результате считывания цифр, которыми помечены ребра, образующие путь от корня дерева к соответствующему символу. Для рассматриваемого примера код Хаффмана примет вид, показанный в таблице справа ( рис. 14.4, б).

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

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

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

Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество сжатия. Однако кодирование Хаффмана имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит – {0, 1}. Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит.

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

Предполагаемая требуемая последовательность символов при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке.

Рассмотренные методы обеспечивают обратимое сжатие данных. На практике применяются как программные, так и аппаратные их реализации, позволяющие добиваться коэффициентов сжатия порядка 20-40% в зависимости от типа сжимаемой информации.

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

Ключевые термины

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

Код – совокупность знаков, а также система правил, позволяющая представлять информацию в виде набора таких знаков.

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

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

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

Расстояние по Хэммингу – число разрядов кодовых слов, в которых они различны.

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

Соседние кодовые слова – кодовые слова, отличающиеся значением только одного разряда.

Краткие итоги

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

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

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

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

Набор для практики

Вопросы для самопроверки

1. Какие виды преобразований информации используются для комплексной защиты информации?
2. Каковы основные принципы помехоустойчивого кодирования сообщений?
3. Каким образом используется синдром ошибки при кодировании сообщений кодом Хэмминга?
4. Приведите примеры кодов, обеспечивающих сжатие сообщений.
5. За счет чего достигается сжатие сообщений при кодировании методом Хаффмана?
6. Как формируется кодовое слова Хаффмана?
7. Для каких типов данных целесообразно использовать алгоритмы сжатия с потерями? С чем это связано?

Упражнения для самопроверки

1. Блоковый помехоустойчивый код имеет длину блока 8 бит. Его избыточность равна 25%. Чему равно число информационных разрядов в нем?
2. Пусть источник информации способен генерировать четыре различных символа S1…S4 с вероятностями возникновения p(S1)=0,1, p(S2)=0,3, p(S3)=0,5, p(S4)=0,1. По этим данным выполните синтез классического кода Хаффмана.

Лекция 21.

Виды цифрового кодирования.

Передача данных на физическом и канальном уровнях

  2.2.1 Аналоговая модуляция

  2.2.2 Цифровое кодирование

Передача данных на физическом и канальном уровнях

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

2.2.1 Аналоговая модуляция

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

Амплитудно-частотная характеристика канала тональной частоты

Этот канал передает частоты в диапазоне от 300 до 3400 Гц, таким образом, его полоса пропускания равна 3100 Гц. Хотя человеческий голос имеет более широкий спектр - примерно от 100 Гц до 10 кГц, - для приемлемого качества передачи речи диапазон в 3100 Гц является хорошим решением. Строгое ограничение полосы пропускания тонального канала связано с использованием аппаратуры уплотнения и коммутации каналов в телефонных сетях.

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

Методы аналоговой модуляции

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

Различные типы модуляции

• а) Потенциальное кодирование - представляется потенциалами высокого уровня для единицы и потенциалом нулевого уровня для нуля.
• б) Амплитудная модуляция - для логической единицы выбирается один уровень амплитуды синусоиды несущей частоты, а для логического нуля другой. Используется редко из-за низкой помехоустойчивости.
• в) Частотная модуляция - значения 0 и 1 исходных данных передаются синусоидами с различной частотой f1 и f2. Обычно применяется в низкоскоростных модемах, работающих на скорости 300 или 1200 бит/с.
• г) Фазовая модуляция - при данном способе значениям 0 и 1 соответствуют сигналы одинаковой частоты, но различной фазы, например 0 и 1800 или 0, 90, 180 и 2700.

2.2.2 Цифровое кодирование

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

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

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

Требования к методам цифрового кодирования

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

• имел при одной и той же битовой скорости наименьшую ширину спектра результирующего сигнала;
• обеспечивал синхронизацию между передатчиком и приемником;
• обладал способностью распознавать ошибки;
• обладал низкой стоимостью реализации.

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

Потенциальный код без возвращения к нулю

На рисунке ниже иллюстрируется метод потенциального кодирования, называемый также кодированием без возвращения к нулю (Non return to Zero, NRZ). При передаче последовательности единиц сигнал не возвращается к нулю в течении такта. Метод NRZ прост в реализации, обладает хорошей распознаваемостью ошибок, но обладает свойством синхронизации. Поэтому при высоких скоростях обмена данными и длинных последовательностей единиц или нулей небольшое рассогласование тактовых частот может привести к ошибке в целый такт и, соответственно, считыванию некорректного значения бита. В чистом виде код NRZ в сетях не используется.

Способы дискретного кодирования данных

Метод биполярного кодирования с альтернативной инверсией

Одной из модификаций метода NRZ является метод биполярного кодирования с альтернативной инверсией (Bipolar Alternate Mark Inversion, AMI) . В этом методе (см. рис. б) используются три уровня потенциала - отрицательный, нулевой и положительный. Для кодирования логического нуля используется нулевой потенциал, а логическая единица кодируется либо положительным потенциалом, либо отрицательным, при этом потенциал каждой новой единицы противоположен потенциалу предыдущей.

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

Потенциальный код с инверсией при единице

Существует код, похожий на AMI, но только с двумя уровнями сигнала. При передаче нуля он передает потенциал, который был установлен в предыдущем такте (то есть не меняет его), а при передаче единицы потенциал инвертируется на противоположный. Эот код называется потенциальным кодом с инверсией при единице (Non return to Zero with ones Inverted, NRZI). Он удобен в тех случаях, когда наличие третьего уровня сигнала весьма нежелательно, например в оптических кабелях, где устойчиво распознаются два состояния сигнала - свет и темнота.

Биполярный импульсный код

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

Манчестерский код

В локальных сетях до недавнего времени самым распространенным методом кодирования был так называемый манчестерский код (см. рис. выше г) ). Он применялся в технологиях Ethernet и Token Ring.

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

Потенциальный код 2B1Q

Выше ни рис. ( д ) показан потенциальный код с четырьмя уровнями сигнала для кодирования данных. Этот код 2B1Q название которого отражает его суть - каждые два бита (2B) передаются за один такт сигналом, имеющем четыре состояния (1Q). Паре бит 00 соответствует потенциал -2,5 В; паре бит 01 - потенциал -0,833 В; паре 11 - потенциал +0,833; паре 10 - потенциал +2,5 В. При этом способе кодирования требуются дополнительные меры по борьбе с длинными последовательностями одинаковых пар битов, так как при этом сигнал превращается в постоянную составляющую. При случайном чередовании битов спектр сигналов в два раза уже, чем у кода NRZ, так как при той же битовой скорости, длительность такта увеличивается в два раза. Таким образом, с помощью кода 2B1Q можно по одной и той же линии передавать данные в два раза быстрее, чем с помощью кода AMI или NRZI. Однако для его реализации мощность передатчика должно быть выше, чтобы четыре уровня четко различались приемником на фоне помех.

Лекция 22.

Кодирование Хаффмана.

Идея, положенная в основу кодировании Хаффмана, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Это нужно, так как мы хотим, чтобы, когда мы обработали весь ввод, самые частотные символы заняли меньше всего места (и меньше, чем они занимали в оригинале), а самые редкие — побольше (но так как они редкие, это не имеет значения). Для нашей программы я решил, что символ будет иметь длину 8 бит, то есть, будет соответствовать печатному знаку.

Мы могли бы с той же простотой взять символ длиной в 16 бит (то есть, состоящий из двух печатных знаков), равно как и 10 бит, 20 и так далее. Размер символа выбирается, исходя из строки ввода, которую мы ожидаем встретить. Например, если бы я собрался кодировать сырые видеофайлы, я бы приравнял размер символа к размеру пикселя. Помните, что при уменьшении или увеличении размера символа меняется и размер кода для каждого символа, потому что чем больше размер, тем больше символов можно закодировать этим размером кода. Комбинаций нулей и единичек, подходящих для восьми бит, меньше, чем для шестнадцати. Поэтому вы должны подобрать размер символа, исходя из того по какому принципу данные повторяются в вашей последовательности.

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

Предположим, у нас есть строка «beep boop beer!», для которой, в её текущем виде, на каждый знак тратится по одному байту. Это означает, что вся строка целиком занимает 15*8 = 120 бит памяти. После кодирования строка займёт 40 бит (на практике, в нашей программе мы выведем на консоль последовательность из 40 нулей и единиц, представляющих собой биты кодированного текста. Чтобы получить из них настоящую строку размером 40 бит, нужно применять битовую арифметику, поэтому мы сегодня не будем этого делать).

Чтобы лучше понять пример, мы для начала сделаем всё вручную. Строка «beep boop beer!» для этого очень хорошо подойдёт. Чтобы получить код для каждого символа на основе его частотности, нам надо построить бинарное дерево, такое, что каждый лист этого дерева будет содержать символ (печатный знак из строки). Дерево будет строиться от листьев к корню, в том смысле, что символы с меньшей частотой будут дальше от корня, чем символы с большей. Скоро вы увидите, для чего это нужно.

Чтобы построить дерево, мы воспользуемся слегка модифицированной очередью с приоритетами — первыми из неё будут извлекаться элементы с наименьшим приоритетом, а не наибольшим. Это нужно, чтобы строить дерево от листьев к корню.

Для начала посчитаем частоты всех символов:

После вычисления частот мы создадим узлы бинарного дерева для каждого знака и добавим их в очередь, используя частоту в качестве приоритета:


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

Повторим те же шаги и получим последовательно:





Ну и после того, как мы свяжем два последних элемента, получится итоговое дерево:


Теперь, чтобы получить код для каждого символа, надо просто пройтись по дереву, и для каждого перехода добавлять 0, если мы идём влево, и 1 — если направо:


Если мы так сделаем, то получим следующие коды для символов:

Чтобы расшифровать закодированную строку, нам надо, соответственно, просто идти по дереву, сворачивая в соответствующую каждому биту сторону до тех пор, пока мы не достигнем листа. Например, если есть строка «101 11 101 11» и наше дерево, то мы получим строку «pepe».

Важно иметь в виду, что каждый код не является префиксом для кода другого символа. В нашем примере, если 00 — это код для 'b', то 000 не может оказаться чьим-либо кодом, потому что иначе мы получим конфликт. Мы никогда не достигли бы этого символа в дереве, так как останавливались бы ещё на 'b'.

На практике, при реализации данного алгоритма сразу после построения дерева строится таблица Хаффмана. Данная таблица — это по сути связный список или массив, который содержит каждый символ и его код, потому что это делает кодирование более эффективным. Довольно затратно каждый раз искать символ и одновременно вычислять его код, так как мы не знаем, где он находится, и придётся обходить всё дерево целиком. Как правило, для кодирования используется таблица Хаффмана, а для декодирования — дерево Хаффмана.

Входная строка: «beep boop beer!»
Входная строка в бинарном виде: «0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 000»
Закодированная строка: «0011 1110 1011 0001 0010 1010 1100 1111 1000 1001»
Как вы можете заметить, между ASCII-версией строки и закодированной версией существует большая разница.

Приложенный исходный код работает по тому же принципу, что и описан выше. В коде можно найти больше деталей и комментариев.

Все исходники были откомпилированы и проверены с использованием стандарта C99. Удачного программирования!

Скачать исходный код

Чтобы прояснить ситуацию: данная статья только иллюстрирует работу алгоритма. Чтобы использовать это в реальной жизни, вам надо будет поместить созданное вами дерево Хаффмана в закодированную строку, а получатель должен будет знать, как его интерпретировать, чтобы раскодировать сообщение. Хорошим способом сделать это, является проход по дереву в любом порядке, который вам нравится (я предпочитаю обход в глубину) и конкатенировать 0 для каждого узла и 1 для листа с битами, представляющими оригинальный символ (в нашем случае, 8 бит, представляющие ASCII-код знака). Идеальным было бы добавить это представление в самое начало закодированной строки. Как только получатель построит дерево, он будет знать, как декодировать сообщение, чтобы прочесть оригинал.

Лекция 23.

Практическое занятие 6. Практическое применение алгоритмов кодирования.

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

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

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

ВВВЕДЕНИЕ.

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

Любой живой организм, в том числе человек, является носителем генетической информации, которая передается по наследству. Генетическая информация хранится во всех клетках организма в молекулах ДНК (дезоксирибонуклеиновой кислоты). Молекула ДНК человека включает в себя около трех миллиардов пар нуклеотидов, и в ней закодирована вся информация об организме человека: его внешность, здоровье или предрасположенность к болезням, способности и т.д.

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

Для любой операции над информацией (даже такой простой, как сохранение) она должна быть как-то представлена (записана, зафиксирована). Этот процесс имеет специальное название – кодирование информации.

ПРЕДСТАВЛЕНИЕ И КОДИРОВАНИЕ ИНФОРМАЦИИ.

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

Кодирование информации необычайно разнообразно. Указания водителю автомобиля кодируются в виде дорожных знаков. Музыкальное произведение кодируется с помощью знаков нотной грамоты, для записи шахматных партий и химических формул созданы специальные системы записи. Любой грамотный компьютерный пользователь знает о существовании кодировок символов. Географическая карта кодирует информацию о местности. Необходимость кодирования речевой информации возникла в связи с бурным развитием техники связи, особенно мобильной связи. Людьми были придуманы специальные коды: Азбука Брайля, азбука Морзе, флажковая азбука. Таких примеров можно приводить очень много.

Известно, что одну и ту же информацию мы можем выразить разными способами.

Например, каким образом вы можете сообщить об опасности?

• Если на вас напали, вы можете просто крикнуть: “Караул!!” (англичанин крикнет “Неlр me!”).
• Если прибор находится под высоким напряжением, то требуется оставить предупреждающий знак (рисунок).
• На оживленном перекрестке регулировщик помогает избежать аварии с помощью жестов.
• В театре пантомимы вся информация передается зрителю исключительно с помощью мимики и жестов.
• Если ваш корабль тонет, то вы передадите сигнал “SОS” (...– – –...).
• На флоте помимо азбуки Морзе используют также семафорную и флажковую сигнализацию.

Набор знаков, в котором определен их порядок, называется алфавитом.

Существует множество алфавитов.

• Алфавит кириллических букв (А, Б, В, Г, Д, Е, ...)
• Алфавит латинских букв (А, В, С, D, Е, F, ...)
• Алфавит десятичных цифр(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
• Алфавит знаков зодиака (^ , _ , ` , a , b , c , d , e , f , g , h , i ) и др.

Имеются, однако, наборы знаков, для которых нет какого-то общепринятого порядка:

• Набор знаков азбуки Брайля (для слепых);
• Набор китайских идеограмм;
• Набор знаков планет;
• Набор знаков генетического кода (А, Ц, Г, Т).

Особенно важное значение имеют наборы, состоящие всего из двух знаков:

• Пара знаков (+, – );
• Пара знаков “точка”, “тире” (., – )
• Пара цифр (0, 1).
• Пара ответов (да, нет).

Таким образом, кодирование информации – это процесс формирования определенного представления информации. Значимость кодирования возросла в последние десятилетия в связи с внедрением ЭВМ.

C появлением компьютеров возникла необходимость кодирования всех видов информации, с которыми имеет дело и отдельный человек, и человечество в целом. Пписьменность и арифметика – есть не что иное, как система кодирования речи и числовой информации. Информация никогда не появляется в чистом виде, она всегда как-то представлена, как-то закодирована.

Основными атрибутами кодирования являются:

• Код – это набор знаков, упорядоченных в соответствии с определенными правилами того или иного языка, для передачи информации.
• Знак – это метка, предмет, которым обозначается что-нибудь (буква, цифра, отверстие). Знак вместе с его значением называют символом. Существует множество классификаций знаков(Приложение 1).
• Язык – это сложная система символов, каждый из которых имеет определенное значение. Языковые символы, будучи общепринятыми и соответственно общепонятными в пределах данного сообщества, в процессе речи комбинируются друг с другом, порождая разнообразные по своему содержанию сообщения.

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

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

ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ КОДИРОВАНИЯ ИНФОРМАЦИИ.

Стенография – это скоростное письмо особыми знаками, настолько краткими, что ими можно записать живую речь. Стенография пришла к нам из древнейших времен. Еще в Древнем Египте скорописцы записывали речь фараонов. Широкое распространение стенография получила в Древней Греции. В 1883 г. в Акрополе была найдена мраморная плита, на которой были высечены стенографические знаки. По мнению ученых, эти записи были сделаны в 350 г. до н.э. Но общепризнанным днем рождения стенографии считается 5 декабря 63 года до н.э. Тогда в Древнем Риме возникла необходимость дословной записи устной речи. Автором древнеримской стенографии считается Тирон – секретарь знаменитого оратора Цицерона.

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

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

Телефонный план нумерации.

В России используется закрытая десятизначная нумерация. Это значит, что любой полный телефонный номер с кодом региона или мобильной сети должен иметь 10 цифр. Это называется Национальный телефонный номер. При звонке на телефон с отличным от “домашнего” кодом региона понадобится дополнительно набирать код выхода на междугороднюю связь (“8”).

Персональные данные.

В последнее время очень актуален вопрос о персональных данных. Персональные данные человека записаны в его паспорте.

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

Штрих-коды.

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

В настоящее время в России и за рубежом ведутся большие работы по созданию автоматизированных систем обработки данных с применением машиночитаемых документов (МЧД), одной из разновидностей которых являются документы со штриховыми кодами. К машиночитаемым относятся товаросопроводительные документы, ярлыки и упаковки товаров, чековые книжки и пластиковые карточки для оплаты услуг, магнитные носители. В связи с этим появились термины “электронные ведомости”, “электронные деньги” и т. д.

Наиболее перспективным и быстроразвивающимся направлением автоматизации процесса ввода информации в ЭВМ является применение штриховых кодов.

Штриховой код представляет собой чередование темных и светлых полос разной ширины. Структура штрихового кода представлена на слайде.

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

В настоящее время штриховые коды широко используются не только при производстве и в торговле товарами, но и во многих отраслях промышленного производства.

Товарный штриховой код присваивается продукции (товару) на этапе запуска его в производство. Штрих-коды получили широкое практическое применение почти во всех сферах деятельности человека (Приложение 3):

• Штриховое кодирование помогает в приготовлении медицинских препаратов;
• Превосходная сортировка;
• Штрих-коды наводят порядок на складе;
• Вы можете стать штрих-кодом!
• Штрих-коды охраняют детей;
• Общее наблюдение за частной жизнью;
• Штрих-коды контролируют гарантийное обслуживание;
• Штрих-коды в аэропорту избежать путаницы;
• Штрих-коды и скоропортящиеся продукты;
• Карты безопасности;
• Штрих-коды следят за заключенными;
• Газеты в будущем;
• Штрих-коды помогают найти выгодную цену;
• Штрих-коды как искусство;
• Штрих-коды не пропустят `зайцев`;
• Штрих-коды отлавливают прогульщиков;
• Процесс выписки рецептов;
• Штриховое кодирование и медицина;
• Штрих-коды и гонки Формулы 1;
• Мобильный телефон вместо билета на концерт;
• Штрих-код охраняет детей;
• Шифровка диагнозов заболеваний в листках нетрудоспособности?

Смайлики.

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

Смайликами (от smile – улыбка) в Интернете называют значки, составленные из знаков препинания, букв и цифр, обозначающие какие-то эмоции.

Смайлик – это лучший способ передать ваши чувства и эмоции при виртуальном общении! Маленькие забавные рожицы, которые вставляются в текст, избавляют от необходимости писать излияния о ваших переживаниях. Считается, что смайлик для Интернета – все равно, что для человечества колесо. Без него невозможно обойтись ни в одной форме виртуального общения. Он крайне прост в употреблении, информативен и при всей своей простоте дает широкий простор воображению. Неудивительно, что его переняли sms-коммуникация, реклама, дизайн, обычная почта, при обмене записками на уроках.

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

ЗАКЛЮЧЕНИЕ.

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

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

• Артур Конан Дойль “Пляшущие человечки”;
• Эдгар По “Золотой жук”;
• Жюль Верн “Путешествие к центру земли”;
• Валентин Каверин “Исполнение желаний”;
• Дэн Браун “Код да Винчи”;
• Дэвид Кан “Взломщики кодов”.

Лекция 24.

Методы криптографии и шифрования. Криптоанализ.

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

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

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

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

В условиях повсеместного использования информационных технологий возникают новые стеганографические приемы. Например, известен способ, при котором секретное сообщение прячется в файле графического изображения. При использовании этого способа младший значащий бит в описании каждого пикселя изображения заменяется битом сообщения. Разделив все исходное сообщение на биты и разместив эти биты по всему графическому файлу, мы пересылаем изображение с замаскированным сообщением получателю. Графическое изображение при этом меняется не слишком сильно, особенно если использовался режим с большим количеством цветов, например, с глубиной цвета 24 бита на пиксел. Это связано с тем, что человеческий глаз не может различать такое большое количество цветов. В результате в картинке размером всего 32 на 32 точки можно вместить тайное сообщение длиной 1024 бита или 128 байт.

Третий способ защиты информации – наиболее надежный и распространенный в наши дни – криптографический . Этот метод защиты информации предполагает преобразование информации для сокрытия ее смысла от противника. Криптография в переводе с греческого означает "тайнопись". В настоящее время криптография занимается поиском и исследованием математических методов преобразования информации.

Наряду с криптографией развивается и совершенствуется криптоанализ – наука о преодолении криптографической защиты информации. Криптоаналитики исследуют возможности расшифровывания информации без знания ключей. Успешно проведенный криптоанализпозволяет получить ключ шифрования, или открытый текст, или то и другое вместе. Иногда криптографию и криптоанализ объединяют в одну науку – криптологию (kryptos - тайный, logos - наука), занимающуюся вопросами обратимого преобразования информации с целью защиты от несанкционированного доступа, оценкой надежности систем шифрования и анализом стойкости шифров.

В настоящее время криптография прочно вошла в нашу жизнь. Перечислим лишь некоторые сферы применения криптографии в современном информатизированном обществе:

• шифрование данных при передаче по открытым каналам связи (например, при совершении покупки в Интернете сведения о сделке, такие как адрес, телефон, номер кредитной карты, обычно зашифровываются в целях безопасности);
• обслуживание банковских пластиковых карт;
• хранение и обработка паролей пользователей в сети;
• сдача бухгалтерских и иных отчетов через удаленные каналы связи;
• банковское обслуживание предприятий через локальную или глобальную сеть;
• безопасное от несанкционированного доступа хранение данных на жестком диске компьютера (в операционной системе Windows даже имеется специальный термин – шифрованная файловая система (EFS)).

До начала ХХ века криптографические методы применялись лишь для шифрования данных с целью защиты от несанкционированного доступа. В двадцатом веке в связи с развитием техники передачи информации на дальние расстояния интерес к криптографии значительно возрос. Благодаря созданию новых криптографических методов расширился и спектр задач криптографии. В настоящее время считается, что криптография предназначена решать следующие задачи:

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

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

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

Основные определения

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

Шифр – совокупность заранее оговоренных способов преобразования исходного секретного сообщения с целью его защиты.

Исходные сообщения обычно называют открытыми текстами. В иностранной литературе для открытого текста используют терминplaintext.

Символ - это любой знак, в том числе буква, цифра или знак препинания.

Алфавит - конечное множество используемых для кодирования информации символов. Например, русский алфавит содержит 33 буквы отА до Я . Однако этих тридцати трех знаков обычно бывает недостаточно для записи сообщений, поэтому их дополняют символом пробела, точкой, запятой и другими знаками. Алфавит арабских цифр – это символы 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 . Этот алфавитсодержит 10 знаков и с его помощью можно записать любое натуральное число. Любое сообщение может быть записано также с помощьюдвоичного алфавита , то есть с использованием только нулей и единиц.

Сообщение, полученное после преобразования с использованием любого шифра, называется шифрованным сообщением (закрытым текстом, криптограммой). В иностранной литературе для закрытого текста используют термин ciphertext.

Преобразование открытого текста в криптограмму называется зашифрованием. Обратное действие называется расшифрованием. В англоязычной литературе терминам "зашифрование/ расшифрование" соответствуют термины "enciphering/deciphering".

Ключ – информация, необходимая для шифрования и расшифрования сообщений.

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

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

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

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

Все методы преобразования информации с целью защиты от несанкционированного доступа делятся на две большие группы: методы шифрования с закрытым ключом и методы шифрования с открытым ключом . Шифрование с закрытым ключом (шифрование с секретным ключом или симметричное шифрование) используется человеком уже довольно долгое время. Для шифрования и расшифрования данных в этих методах используется один и тот же ключ, который обе стороны стараются хранить в секрете от противника. Системы шифрования с закрытым ключом подробно рассматриваются в лекциях 2-9. Шифрование с открытым ключом (асимметричное шифрование) стало использоваться для криптографического закрытия информации лишь во второй половине ХХ века. В эту группу относятся методы шифрования, в которых для шифрования и расшифрования данных используются два разных ключа. При этом один из ключей (открытый ключ) может передаваться по открытому (незащищенному) каналу связи. Алгоритмам преобразования информации с открытым ключом посвящены лекции 10-14 учебного пособия.

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

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

Требования к криптографическим системам защиты информации

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

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

Лекция 25.

Практическое занятие 7. Практическое применение криптографии.

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

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

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

В настоящее время выпускаются и комбинированные модули шифрования, так называемые программно-аппаратные средства. В этом случаекомпьютер дополняется своеобразным "криптографическим сопроцессором" – аппаратным вычислительным блоком, ориентированным на выполнение специфических криптографических операций. Меняя программное обеспечение для такого устройства, можно выбирать тот или иной метод шифрования. Такое программно-аппаратное средство объединяет в себе достоинства программных и аппаратных методов.

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

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

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

Голландский криптограф Огюст Керкхоффс сформулировал принцип, называемый в настоящее время принципом Керкхоффса – правило разработки криптографических систем, согласно которому в засекреченном виде держится ключ шифрования, а остальные параметры системы шифрования могут быть открыты без снижения стойкости алгоритма. Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей. Принцип Керкхоффса направлен на то, чтобы сделать безопасность алгоритмов и протоколов независимой от их секретности; открытость не должна влиять на безопасность. Большинство широко используемых систем шифрования, в соответствии с принципом Керкхоффса, используют известные, не составляющие секрета криптографические алгоритмы.

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

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