Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Конкурс'
Проблемы гражданского становления подрастающего поколения, воспитания гражданского самосознания и высокой духовности детей и молодежи становятся наиб...полностью>>
'Лекція'
Механіка — наука про найпростішу форму руху тіл (механічний рух, або переміщення). Рух у широкому філософському розумінні є зміна взагалі, будь-яка з...полностью>>
'Решение'
В соответствии с Федеральным законом от 06.10.2003 № 131-ФЗ «Об общих принципах организации местного самоуправления в Российской Федерации» и в целях...полностью>>
'Документ'
Не возникает никаких сомнений в том, что для каждого учителя важным является повышение эффективности обучения. И этот вопрос требует постоянного поис...полностью>>

Лекции по курсу «Теория Информации»

Главная > Лекции
Сохрани ссылку в одной из сетей:

35


Установочные лекции по курсу «Теория Информации»

ВВЕДЕНИЕ

Информация! Что может быть проще информации?

Вы приступаете к изучению курса «ТЕОРИЯ ИНФОРМАЦИИ», далее «ТИ». По завершению, вы будет знать об информации все, необходимое для успешной профессиональной деятельности, а именно:

  • что называют информацией;

  • как и в чем измеряют информацию;

  • что такое кодирование и задачи кодирования информации;

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

Но прежде всего, нам надо выяснить: ЧТО ТАКОЕ ИНФОРМАЦИЯ?

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

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

В различных науках под «информацией» понимают различные сущности. Например,

  • в философии — информация понимается как наши «знания» об окружающем мире, помогающие преобразовывать этот мир под свои нужды, чаще всего эти знания представляют собой различные тексты, см. рис. 1 и 2;

    Рис.1. 11000-томная «Юнлэ дадянь» — самая большая бумажная энциклопедия в истории.

    (/wiki/­%D0%A4%D0%B0%D0%B9%D0%BB:­Yongle_Dadian_Encyclopedia_1403.jpg)

    Рис.2. Лексикон Техникум Харриса, титульная страница второго издания, 1708 г. (http://pages.cpsc.ucalgary.ca/­~williams/Tomash%20catalog%20­web/Images%20web%20site/­Image%20files/H%20Images/­index_3.htm)

  • в вычислительной технике — информация понимается как последовательности битов/байтов в памяти компьютера или «данные», см. рис.3;

    1010101111010010101001010100000101010100010010101001010001001010…

    00000000 89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 |.PNG........IHDR|

    00000010 00 00 00 87 00 00 00 a0 08 03 00 00 00 11 90 8f |................|

    00000020 b6 00 00 00 04 67 41 4d 41 00 00 d6 d8 d4 4f 58 |.....gAMA.....OX|

    00000030 32 00 00 00 19 74 45 58 74 53 6f 66 74 77 61 72 |2....tEXtSoftwar|

    00000040 65 00 41 64 6f 62 65 20 49 6d 61 67 65 52 65 61 |e.Adobe ImageRea|

    00000050 64 79 71 c9 65 3c 00 00 03 00 50 4c 54 45 22 22 |dyq.e<....PLTE""|

    00000060 22 56 56 56 47 47 47 33 33 33 30 30 30 42 42 42 |"VVVGGG333000BBB|

    00000070 4b 4b 4b 40 40 40 15 15 15 4f 4f 4f 2c 2c 2c 3c |KKK@@@...OOO,,,<|

    00000080 3c 3c 3e 3e 3e 3a 39 39 04 04 04 1d 1d 1d 35 35 |<<>>>:99......55|

    00000090 35 51 50 50 37 37 37 11 11 11 25 25 25 0d 0d 0d |5QPP777...%%%...|

    000000a0 27 27 27 1a 1a 1a 38 38 38 2a 2a 2a 08 08 08 20 |'''...888***... |

    000000b0 20 20 17 17 17 2e 2e 2e 13 13 13 bb bb bb 88 88 | ..............|

    Рис.3. Двоичная последовательность и шестнадцатеричное представление по 16 октетов в строке, с печатными ASCII-символами (справа) начала PNG-файла.

  • в теории систем — информация понимается как передача вещества и энергии от одной части системы к другой или «связи», см. рис.4.

Рис.4. Перемещение вещества и энергии в системе автоперевозок. А может этот автопоезд везет книги, т.е. информацию?

Теория информации дает свое определение. Это определение охватывает нечто общее, что есть у всех понятий «информация». Давайте вместе разберемся, что же связывает эти понятия?

Для этого обратимся к истории.

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

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

Обратим внимание, что количество различных «значений» может сильно различаться от 2-х в двоичной последовательности, до ~40 000 иероглифов в китайском тексте и до бесконечного разнообразия значений напряжения в электрической розетке. Иными словами, общее — это то, что любая «информация» – есть функция времени. Далее мы будем называть это «сигнал».

ЧТО же мы (в теории информации) понимаем под этим словом? Давайте запомним, нам это пригодится в дальнейшем.

ИТАК: Сигнал — это любая функция, аргументом которой является время, а значением — величина, которую можно представить числом или символом.

Этот «сигнал» и есть носитель информации с точки зрения теории информации. Сама «информация» содержится в этом «сигнале» и задача теории информации определить: как измерять «информацию».

И ВОТ что важно: Главное, что следует понять — «информация» в «Теории информации» БЕССМЫСЛЕННА. Например, текст романа Л.Н.Толстого «Война и мир» и любое другое сочетание букв и символов, составляющих это произведение, с точки зрения теории информации несет АБСОЛЮТНО одинаковую информацию.

Для того, чтобы нам понять и разобраться в вопросе, КАК ИЗМЕРИТЬ ИНФОРМАЦИЮ, определим ПОНЯТИЕ ИНФОРМАЦИОННОГО КАНАЛА.

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

ЗАПОМНИМ: Основная операция над «сигналом», изучаемая в Теории информации — передача информации. В этом процессе важную роль играет понятие ИНФОРМАЦИОННОГО КАНАЛА.

ЗАПОМНИМ: Под информационным каналом понимается любое устройство, предназначенное для передачи сигнала в пространстве или времени (см. рис.5 и рис.6).

Рис.5. Передача сигнала во времени — библиотека (Региональная библиотека во французском Алансоне, построена в 1800 году http://www.lib.kture.kharkov.ua/­ru/elexH49/1.php).

Рис.5. Передача сигнала в пространстве — телеграф Морзе (Соединение двух станций посредством обыкновенного телеграфа Морзе /wikipedia/ru/2/26/).

В этом устройстве различают три части (см. рис.7):

  1. кодирующее устройство,

  2. линия связи,

  3. декодирующее устройство.

Источник сигнала

Кодирующее устройство

Линия связи

Декодирующее устройство

Получатель сигнала

Рис.7. Информационный канал.

ОПРЕДЕЛИМ ЭТИ ПОНЯТИЯ. ИТАК:

  • «Кодирующим устройство» — это нечто, преобразующее сигнал в форму, допускающую передачу по линии связи.

  • «Линия связи» — это нечто, способное воспроизвести переданный сигнал в другой точке пространства или времени.

  • «Декодирующее устройство» — это нечто, преобразующее сигнал в первоначальную форму, т.е. в тот вид, который был получен из источника сигнала.

Например, в информационном канале «телеграф Морзе», см. рис.6, кодирующим устройством является телеграфист, преобразующий текст телеграммы в импульсы тока разной длительности; линия связи — металлический провод, по которому протекают эти импульсы; декодирующее устройство — другой телеграфист, записывающий последовательность импульсов в виде текста.

ОБРАТИМ ВНИМАНИЕ: Источник сигнала и получатель сигнала находятся вне рассмотрения ТИ – т.е. природой сигнала, а равно и его «смыслом» теория информации не интересуется.

ЗАДАДИМ СЕБЕ ВОПРОС: ЧТО ЖЕ ПРОИСХОДИТ ПРИ ПЕРЕДАЧЕ ИНФОРМАЦИИ?

ОКАЗЫВАЕТСЯ, возникают три проблемы:

  • НЕОБХОДИМОСТЬ передать информацию, используя минимум ресурсов, или необходимость устранения избыточности;

  • НЕОБХОДИМОСТЬ устранения случайных искажений информации при передаче (помех);

  • НЕОБХОДИМОСТЬ устранения несанкционированного доступа к информации.

КАК ЖЕ РЕШАЮТСЯ ЭТИ ПРОБЛЕМЫ?

ОТВЕТ НАПРАШИВАТСЯ САМ СОБОЙ:

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

НО ЧТО ТАКОЕ КОДИРОВАНИЕ СИГНАЛА? ДАДИМ ОПРЕДЕЛЕНИЕ понятие кодирования и запомним. ЭТО ВАЖНО.

ИТАК:

Кодирование сигнала

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

Преобразование информации из одной формы в другую, допускающее восстановление ИСХОДНОЙ формы информации (сигнала) без искажений — называют обратимым кодированием.

Например, текст можно записать номерами символов, а номера символов — двоичными последовательностями, см. рис.8.

Мама мыла раму



Рис.8. Эквивалентные представления текста.
a — соответствие буква ↔ число по стандарту ASCII.
B — соответствие десятичное число ↔ двоичное число по стандарту «младший бит первый».

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

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

ЗАВЕРШАЯ НАШЕ ВСТУПЛЕНИЕ, подведем предварительные итоги.

ИТАК: В курсе Теория информации мы изучим следующие разделы

Перечень основных разделов

Во-первых, рассмотрим измерение информации и разберемся с понятием «мера Шенона»;

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

В-третьих, рассмотрим теорию борьбы с искажениями и вопросы исправления ошибок — помехозащищенное кодирование;

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

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

Лидовских В.В. Теория информации. Учебное пособие. 2004г.

Это пособие, а также другая литература и домашние задания доступны по адресу:

mp.ustu.ru\InformationTheory

Задать вопросы и получить консультации можно по электронной почте:

aleks@dpt.ustu.ru

либо по телефону

9122929147.

1. Виды информации и ИЗМЕРЕНИЕ ИНФОРМАЦИИ

    1. Определение информации

Информация — любая функция времени вида y = f(t), где t – физическое время или его аналог и y – любая величина или значение сигнала.

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

1.2. Виды информации и дискретизация

Информация — f(t) — может быть двух видов:

  • непрерывная, рис. 9.

  • дискретная, рис. 10.

Непрерывный сигнал

Рис. 9.

Дискретный сигнал

Рис. 10.

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

Дискретизация непрерывного сигнала

T – период дискретизации.

Рис. 11.

Непрерывная информация может быть представлен в дискретной форме (дискретизирована). Для этого достаточно замерить значения y = f(t) в моменты времени tiiT, где i - целое число, T – период дискретизации (рис. 11). Очевидно, что при слишком большом периоде дискретизации восстановить исходную непрерывную информацию невозможно. При уменьшении периода дискретизации до бесконечно малой величины получается практически точная копия непрерывной информации, но и количество «значений», которые надо хранить или передавать становится близким к бесконечности.

Основная теорема дискретизации: «Теорема Уиттакера — Найквиста — Котельникова — Шеннона» (или теорема Котельникова) гласит, что, если непрерывная функция f(t) имеет спектр разложения в ряд Фурье, ограниченный сверху частотой Fmax, то она может быть однозначно и без потерь восстановлена по своим дискретным отсчётам, взятым с периодом:

T  .

Теорема сформулирована Гарри Найквистом в 1928 году в работе «Certain topics in telegraph transmission theory» и независимо В.А. Котельниковым в 1933 году в работе «О пропускной способности эфира и проволоки в электросвязи» и является одной из основополагающих теорем в теории цифровой связи.

Теорема также утверждает, что непрерывный сигнал можно представить в виде следующего ряда:

.

Значения yi = f(iT) — значения дискретизированного сигнала.

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

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

Каждая ДСВ определяется множеством X её возможных значений x и вероятностью p(x) (или долей) каждого из значений x в ДСВ. Конкретная последовательность x1, x2… значений ДСВ называется сообщением.

1.3. Хранение и передача информации. Информационная емкость

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

Существует формальное математическое доказательство (см. Ноберт Винер [1]), что хранение чисел в двоичном представлении требует минимальных затрат энергии, т.е. наиболее «экономично».

Достаточно представить каждое число в двоичной форме и записать получившуюся цепочку нулей и единиц на носитель. Например, на перфоленту: «дырка» = 1, а «отсутствие дырки» = 0.

Абстрактный носитель, способный хранить 1 или 0, получил название «БИТ» (bit).

Поскольку придумать носитель, способный хранить меньшее чем один «БИТ» количество информации невозможно, то БИТ используется в качестве минимальной меры информационной емкости.

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

Понимание того, что информационная емкость и количество информации не одно и тоже — ключевой момент.

Одна и та же информация может быть передана/записана множеством способов. Например, уменьшив период T дискретизации f(t) в два раза мы получим в два раза больше чисел для предачи/записи, но восстановленная f(t) не будет отличаться от дискретизации с периодом 2T, пока 2T меньше максимально допустимого значения (см. п. 1.2).

Это противоречие с информацией, которая равна и одновременно не равна сама себе, разрешил Клод Шенон [2].

Количественной мерой информации следует считать МИНИМАЛЬНУЮ информационную емкость, которая необходима для передачи (хранения) информации без искажения в условиях отсутствия помех.

Определение количественного значения минимальной информационной емкости — сложная задача. Академик Колмогоров А.Н. [3] сформулировал три способа измерения количества информации:

  • алгоритмический,

  • комбинаторный,

  • вероятностный.

Алгоритмическая мера

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

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

Комбинаторная мера (мера Хартли)

Если ДСВ x способна равновероятно принимать значения из множества X, состоящего из N элементов, то необходимо как минимум H(X) = log2(N) двоичных разрядов (бит), чтобы записать номер любого из возможных значений ДСВ и, соответственно, необходимо Mlog2(N) бит, чтобы записать сообщение из M конкретных значений x. Значение I(X) = log2(N) можно понимать как МИНИМАЛЬНОЕ количество бит, необходимых для записи возможных значений величины x или как меру информации, содержащейся в любом из значений x, выраженной в единицах БИТ/СИМВОЛ.

Вероятностная мера (мера Шенона)

Основное отличие от комбинаторной меры информации — постулируется неравная вероятность различных значений ДСВ X. Что это означает? Это значит, что если мы достаточно долго будем записывать некую ДСВ X, то доли конкретных значений xi в общем числе значений будут неравны.

Пусть вероятность (доля) конкретного значения xi составляет p(xi). Количество бит, необходимое В СРЕДНЕМ для записи одного значения x, может быть вычислена по формуле:

. (1)

Или необходимо не менее бит, чтобы записать сообщение из M конкретных значений x ДСВ X.

Эта формула называется формулой Шенона.

1.5. Смысл меры Шенона

Формула Шенона (1) может быть интерпретирована так: число n РАЗЛИЧНЫХ сообщений из M символов, где вероятность отдельных символов x совпадает с p(x), есть .

В этом смысле I(x) — есть мера неопределенности (или энтропия) ДСВ X. Указывая конкретное значение x = a, мы уничтожаем эту неопределенность, сообщая таким образом информацию на один символ сообщения.

Для сообщения из M значений ДСВ X величина MI(X) равна МИНИМАЛЬНОМУ количеству бит, которое необходимо для записи этого сообщения без искажений.

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

2.1. Понятие кодирования

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

Кодирование производится с целями:

  1. обеспечить возможность передачи информации;

  2. увеличить скорость передачи информации;

  3. защитить информацию от искажений.

  4. защитить информацию от несанкционированного доступа;

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

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

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

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

2.2. Кодирование для физического канала

В курсе теории информации мы не будем подробно рассматривать этот тип кодирования. Ограничимся самыми общими замечениями.

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

Природа канала накладывает ограничения и на способ передачи этого сигнала. Так, например, при передаче электрических сигналов через проводник не используется кодировка типа: есть напряжение = 1, нет напряжения = 0. Это обусловлено техническими трудностями детектирования постоянного уровня напряжения, оказывается, что гораздо проще и надежнее детектируется изменение напряжения и, как следствие, большинство систем кодирования электрических импульсов кодирует 0 как отсутствие изменения напряжения, а 1 как изменение напряжения в проводнике. Сходные особенности характерны и для других видов каналов.

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

Например, тексты преобразуют в последовательности чисел, согласно некоей кодировочной таблицы (ASCII, UNICODE и т.п.).

Кодировочная таблица сопоставляет каждому символу целое число. Обычно, количество чисел и символов есть целая степень двойки, так ASCII имеет 28 = 256 различных символов, Unicode — 216 = 65536 символов. Кодировочные таблицы позволяют записать любую символьную информацию как последовательность целых чисел фиксированной битовой ширины (см. рис.8), т.е. перевести любую информацию в цифровую форму.



Скачать документ

Похожие документы:

  1. Лекции по курсу «Теория ценных бумаг» (4)

    Лекции
    «Теория ценных бумаг» читается в Санкт-Петербургском государственном университете экономики и финансов в шестом семестре студентам специальности «Финансы и кредит» после изучения предмета «Деньги.
  2. Лекции по курсу «Теория ценных бумаг» (2)

    Лекции
    Неужели Алан Гринспэн все-таки стал сторонником теории «мыльного пузыря», т. е. того мнения, что цены на американском рынке ценных бумаг неоправданно высоки? Председатель Федеральной резервной системы США всегда славился умением шифровать
  3. Лекции по курсу «Теория ценных бумаг» (6)

    Лекции
    Пекин. Во вторник в Китае открылась первая фондовая биржа, деятельность которой будет целиком посвящена удовлетворению потребностей в капитале начинающих компаний в области высоких технологий.
  4. Лекции по курсу «Теория ценных бумаг» (17)

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

    Лекции
    Хотелось бы, чтобы в этом вопросе сохранилась преемственность, чтобы пришел человек, который мог бы продолжить ту политику, которую проводила ФКЦБ при Дмитрии Васильеве.

Другие похожие документы..