11u-1_Информация. Количество информации Передача данных Сжатие данных
 Скачать 7.7 Mb.
|
|
§ 1. Количество информации § 2. Передача данных § 3. Сжатие данных § 4. Информация и управление § 5. Информационное общество § 1. Количество информации Формула Хартли (1928)I – количество информации в битах N – количество вариантов Ральф Хартли Пример: В аэропорту стоит 10 самолетов, из них один летит в Санкт-Петербург. Оценить количество информации в сообщении «В Санкт-Петербург летит второй самолет»? бита Алфавитный подходM – мощность алфавита Информационный объём символа: сообщения длиной L: Пример: сообщение длиной 100 символов закодировано с помощью алфавита из 50 знаков. бита бита вверх до целого числа 6 битов 600 битов Количество различных сообщенийM – мощность алфавита L – длина сообщения N – количество различных сообщений алфавит: А, Б, В, Г А, Б, В, Г А, Б, В, Г для каждого варианта А, Б, В, Г всего: 4 всего: 44 = 42 = 16 Информация и вероятность
Доля символов в русских текстах: из 1000 символов около 175 пробелов вероятность p появления символа ВероятностьВероятность события – число от 0 до 1, показывающее, как часто случается это событие в большой серии одинаковых опытов. событие никогда не происходит (нет неопределенности) событие происходит в половине случаев (есть неопределенность) событие происходит всегда (нет неопределенности) x2 0 x2 < 0 ВероятностьN – количество испытаний m – сколько раз произошло событие ровно 2: чётное: меньше 3: 2 и 2: 2 чётных: оба меньше 3: Вероятность и информация…АААААААААААААААААА получили букву «А»: …BАААААААААААААААААА получили букву «В»: Чем более неожиданно событие, тем больше получено информации. В 10 опытах будет получено в 10 раз больше информации, чем в одном (аддитивность). Определили свойства количества информации! ! Вероятность и информацияпри K = 1 информация в битах Если событие имеет вероятность p, то количество информации в битах, полученное в сообщении об этом событии, равно Вероятность и информацияАддитивность: по 8 шариков разного цвета всего 88 = 64 варианта бита битов битов Аддитивность выполняется! ! Связь с формулой ХартлиN равновероятных событий совпадает с формулой Хартли Если вероятности разные: «Васе достался зелёный шарик». Формула ШеннонаКоличество полученной информации равно уменьшению неопределенности. I = H = Hнач – Hкон Как вычислить H? ? Неопределённость знаний об источнике данных (N событий, вероятности pi): Клод Шеннон информационная энтропия Формула Шеннона«Идёт ли сейчас снег?» (1 – да, 2 – нет) зимой: Как вычислить p2? ? Сумма вероятностей всех событий, составляющих полную систему, равна 1! ! бит летом: бит Когда неопределённость наибольшая?Система двух событий: Неопределенность максимальна, когда все события равновероятны. 0 1 0,5 1 0,5 H p1 совпадает с формулой Хартли! § 2. Передача данных Скорость передачи данныхСкорость передачи данных – это количество битов (байтов, Кбайт и т.д.), которое передается по каналу связи за единицу времени (например, за 1 с). Пропускная способность канала связи – это наибольшая возможная скорость передачи данных, которую принципиально невозможно превысить. От чего зависит? ? аппаратура, мощность помех Единицы измерения1 бит/с = 1 bps (bits per second) 1 кбит/с = 1000 бит/с 1 Мбит/с = 106 бит/с 1 Гбит/с = 109 бит/с Объём переданных данныхсредняя скорость передачи время v = 512000 бит/с, t = 1 мин I = v t = 512000 бит/с ·60 с = 30 720 000 битов = 3 840 000 байтов = 3750 Кбайт. : 8 : 1024 Обнаружение ошибокБит чётности: 00 01 10 11 000 011 101 110 теперь число единиц в каждом блоке чётное Если в принятом блоке нечётное число «1» – ошибка! принято: 010 110 000 111 000 Можно ли исправить? ? Для файлов – контрольные суммы (хэш): CRC = Cyclic Redundancy Code MD5, SHA-1 Верно ли переданы данные? ? 10010 Помехоустойчивые коды111 000 000 111 000 – утроение каждого бита принято: 010111000101000 исправлено: 000111000111000 10010 Обнаруживает 1 или 2 ошибки, исправляет 1 ошибку! ! Помехоустойчивый код – это код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня. Расстояние ХэммингаРасстояние Хэмминга – это количество позиций, в которых отличаются два закодированных сообщения одинаковой длины. d(001, 100) = 2 d(000, 111) = ? 3 Обнаруживает 1 или 2 ошибки, исправляет 1 ошибку! ! Исправление r ошибок: d 2r + 1 Передача 3-битных блоков
dmin= 3 r = 1 d(000000, x)= ?
Исправление ошибки принято: 101110 Недопустимый код! ! ближайший допустимый код: 101010 Помехоустойчивые коды Хэмминга
4 полезных бита, 3 контрольных избыточность 3/4 =75% 3 = 1 + 2 5 = 1 + 4 6 = 2 + 4 7 = 1 + 2 + 4 бит 1: (1 + 1 + 0) mod 2 = 0 бит 2: (1 + 0 + 0) mod 2 = 1 бит 4: (1 + 0 + 0) mod 2 = 1 dmin= 3 r = 1 Код Хэмминга: исправление ошибки
бит 1: (1 + 1 + 0) mod 2 = 0 бит 2: (1 + 1 + 0) mod 2 = 0 бит 4: (1 + 1 + 0) mod 2 = 0 Контрольные биты: Номер ошибочного бита: 2 + 4 = 6
Длинные коды ХэммингаКонтрольные биты: 1, 2, 4, 8, 16, … , 2k Исправляется только 1 ошибка в блоке! !
§ 3. Сжатие данных Что такое сжатие?Алфавит: A, B, C, Сообщение: АBА CАBАBА 80 битов в 8-битной кодировке! ! A 00 B 01 C 10 11 АBА CАBАBА 00 01 00 11 10 00 01 00 01 00 20 битов Как раскодировать? ? Словарь:
Коэффициент сжатияСообщение: 10240 символов Алфавит: A, B, C, Словарь: 5 байтов Длина кода: 10240×2 = 20480 битов = 2560 байтов Длина сжатого сообщения: 5 + 2560 = 2565 байтов Коэффициент сжатия – это отношение размеров исходного и сжатого файлов. Сжатие без потерьСжатие без потерь – это такое уменьшение объема закодированных данных, при котором можно восстановить их исходный вид из кода без искажений. За счёт чего сжимается сообщение? ? В данных должна быть избыточность! ! используются только 4 символа из 256 Алгоритм RLERLE (англ. Run Length Encoding, кодирование цепочек одинаковых символов)
100 100 200 байтов Файл qq.txt Файл qq.rle (сжатый)
4 байта В чем состоит избыточность? ? сжатие в 50 раз! Сжатие с потерями или без? ? Что в худшем случае? ? Алгоритм RLE
управляющие байты АААААААААААААААБВ Распаковка: 15 2 Применение: сжатие рисунков *.bmp (с палитрой) один из этапов сжатия рисунков *.jpg 8F C0 02 C1 C216 Неравномерные кодыИдея: кодировать часто встречающиеся символы более короткими кодовыми словами. Азбука Морзе: А И • • • – – – корень Н М Т Е Е • – Т И • – А • • Н – М • – – Проблема: разделить последовательность на кодовые слова! ! • • И ЕЕ Можно ли обойтись без разделителя? ? Префиксные кодыПрефиксный код – это код, в котором ни одно кодовое слово не является началом другого кодового слова (условие Фано). А И • • • – – – корень Н М Т Е Е • – Т И • – А • • Н – М • – – Это не префиксный код! ! Проблема: как построить префиксный код? ! не все символы в листьях! Код Шеннона-ФаноАлфавит: О, Е, Н, Т, Количество символов в сообщении: 140 О Н Е Т 68 68 64 60 На 2 группы с примерно равным числом символов: 140 E T H O 68 64 60 68 208 192 начинаются с 0 начинаются с 1 00 O 01 E 10 T Н 64 60 начинаются с 11 Т Н 110 111 в порядке невозрастания Код Шеннона-ФаноО Е Н Т 0 0 0 0 1 1 1 1 корень Это префиксный код (все символы в листьях дерева)! ! Декодирование: 1110111101001011001111 111 01 111 01 00 10 110 01 111 Т O Т O Е Н О Т Код Шеннона-Фаноучитывается частота символов не нужен символ-разделитель код префиксный – можно декодировать по мере поступления данных нужно заранее знать частоты символов код неоптимален при ошибке в передаче сложно восстановить «хвост» не учитывает повторяющиеся последовательности символов Алгоритм ХаффманаДэвид Хаффман 140 Е Т Н О 68 64 60 68 По увеличению частоты: 140 Е Т Н О 68 68 124 140 Е О 136 Т Н 124 Алгоритм Хаффмана140 Е О Т Н 260 Т Н Е О 0 1 0 1 1 1 0 0 0 Т 100 Н 101 Код Хаффмана: Е 110 О 111 Сравнение алгоритмовКоличество символов в сообщении: 140 О Н Е Т 68 68 64 60 Равномерное кодирование (8-битный код): (140 + 68 + 68 + 64 + 60) 8 = 3200 битов Равномерное кодирование (3-битный код): (140 + 68 + 68 + 64 + 60) 3 = 1200 битов + словарь! В чём избыточность? ? Сравнение алгоритмовКоличество символов в сообщении: 140 О Н Е Т 68 68 64 60 Код Шеннона-Фано: 00 О 01 Е 10 Н Т 110 111 (140 + 68 + 68) 2 + (64 + 60) 3 = 924 бита Код Хаффмана: 0 О 111 Е 110 Н Т 101 100 140 + (68 + 68 + 64 + 60) 3 = 920 бит Оптимален! ! Алгоритм Хаффманакод оптимальный среди алфавитных кодов нужно заранее знать частоты символов при ошибке в передаче сложно восстановить «хвост» не учитывает повторяющиеся последовательности символов Алгоритм LZW1977: А. Лемпел и Я. Зив, 1984: Т. Велч Идеи: кодировать не отдельные символы, а блоки последовательностям символов присваиваются числовые коды новая цепочка занесение в словарь с новым кодом словарь строится по мере получения данных не нужны частоты символов за один проход! Применение: сжатие рисунков *.gif, *.tif сжатие документов *.pdf Алгоритм LZWввод СТРОКА пока не конец данных ввод СИМВОЛ если Есть_в_словаре( СТРОКА + СИМВОЛ ) то СТРОКА:= СТРОКА + СИМВОЛ иначе вывод Код(СТРОКА) Добавить_в_словарь( СТРОКА + СИМВОЛ ) СТРОКА:= СИМВОЛ вывод Код(СТРОКА) да / нет получить из словаря Сжатие с потерямиСжатие с потерями – это такое уменьшение объема закодированных данных, при которых распакованный файл может отличаться от оригинала. Применение: сжатие рисунков *.jpg, *.jpeg сжатие звука *.mp3, *.aac, *.ogg, … сжатие видео *.mpg, *.wmv, *.mov, … Идея: «отбросить» часть данных, которые не влияют на восприятие информации человеком (доп. размытие фотографий, частоты выше 20 кГц, …) Снижение глубины цвета8 битов на пиксель (256 цветов) 4 бита на пиксель (16 цветов) 2 бита на пиксель (4 цвета) размер качество Сжатие JPEGRGB Y Cb Cr яркость «синева» «краснота» Y = 0,299R + 0,587G + 0,114B Cb = 128 – 0,1687R – 0,3313G + 0,5B Cr = 128 + 0,5R – 0,4187G – 0,0813B глаз чувствительнее к зелёному! Что для чёрно-белого (серого)? ? Cb = Cr = 128 Сжатие JPEGИдея: глаз наиболее чувствителен к яркости
12 чисел например: Cb = Cb1 + Cb2 +Cb3 + Cb4 4 Cr = Cr1 + Cr2 +Cr3 + Cr4 4 Y1, Y2, Y3, Y4, Cb, Cr 6 чисел + дискретное косинусное преобразование, алгоритмы RLE и Хаффмана потери! Сжатие JPEGкачество 100 (8400 байтов) качество 50 (3165 байтов) качество 0 (1757 байтов) качество 0 (фрагмент) 40 30 20 10 0 BMP BMP(RLE) GIF PNG JPEG(100) JPEG(50) JPEG(0) V, Кбайт Плавные переходы! ! Артефакты – заметные искажения из-за сжатия с потерями Сжатие рисунков с потерями и безБольшие области одного цвета! Чёткие границы! ! 120 100 80 40 0 BMP BMP(RLE) GIF PNG JPEG(100) JPEG(50) JPEG(0) 60 20 V, Кбайт Что особенного? ? с потерями! без потерь! Сжатие звука (MP3)MP3 = MPEG-1 Layer 3, кодирование восприятия Битрейт – это число бит, используемых для кодирования 1 секунды звука. MP3: от 8 до 320 кбит/c Без сжатия на CD (1 сек, 44 кГц, 16 бит, стерео): 288000 = 176 000 байт = 1 408000 бит = 1408 кбит Cжатие MP3 (256 кбит/с): Сжатие видеовидео = изображения + звук Кодек (кодировщик/декодировщик) – это программа для сжатия данных и восстановления сжатых данных. MJPEG, MPEG-4, DivX, Xvid, H.264, … Артефакты – заметные искажения из-за сжатия с потерями Сжатие: итогиСжатие уменьшает избыточность данных! ! Хорошо сжимаются: тексты (*.txt) документы (*.doc) несжатые рисунки (*.bmp) несжатый звук (*.wav) несжатое видео (*.avi) Плохо сжимаются: случайные данные сжатые данные в архивах (*.zip, *.rar, *.7z) сжатые рисунки (*.jpg, *.gif, *.png) сжатый звук (*.mp3, *.aac) сжатое видео (*.mpg, *.mp4, *.mov) Нужно ли стремиться к полному удалению избыточности? ? § 4. Информация и управление КибернетикаНорберт Винер Кибернетика – это наука, изучающая общие закономерности процессов управления и передачи информации в машинах, живых организмах и обществе. Идеи: управление в любых системах подчиняется одним и тем же законам управление связано с обменом информацией Что такое система?Система – это группа объектов и связей между ними, выделенных из среды и рассматриваемых как одно целое. Примеры:
А Б В Г среда Системный эффект: свойства системы нельзя свести к «сумме» свойств ее компонентов. самолёт летает! Что такое система?Свойства системы: компоненты + связи (алмаз, графит) Подсистема: компонент-система. Цель работы системы определяется надсистемой! ! А Б В Е Ж Г Д S S1 S2 Системный анализ: изучение сложных систем на основе теории управления и теории информации. подсистема элемент Надсистема: система более высокого уровня. Системы управлениярегулятор объект цель среда управление Разомкнутая система – регулятор не получает информации о состоянии объекта (программное управление). Примеры:
простота – не нужно датчиков нужна точная модель объекта нельзя учесть влияние среды Неизвестно, достигнута ли цель! ! Системы с обратной связьюЗамкнутая система – регулятор получает информации о состоянии объекта по каналу обратной связи. регулятор объект цель среда управление датчики обратная связь (ОС) сравнение с целью! усложнение системы (датчики) модель объекта может быть неточной можно учесть влияние среды Отрицательная ОС – регулятор уменьшает разницу между целью и состоянием объекта. Типы систем управленияАвтоматические – работают без участия человека. Автоматизированные – собирают и обрабатывают информацию, а решения принимает человек. Адаптивные – «подстраиваются» под изменение внешних условия или свойств объекта. Управление роботамисистема управления исполнительные механизмы (моторы) датчики датчики датчики Управление роботамимикроконтроллер микропроцессор оперативная память (ОЗУ) постоянная память (ПЗУ) каналы ввода-вывода цель север 0 ошибка управления: e = – 0 пропорциональный закон управления: u = – ke = – ke( – 0) команда для вращения (+ – по часовой стрелке) § 5. Информационное общество Что такое информационное общество?Прогресс в обработке информации: письменность (около 3000 лет до н.э., Египет) книгопечатание (X век – Китай, XV век – Европа) средства связи (телеграф, телефон, радио, телевидение; конец XIX – начало XX века); компьютеры (вторая половина XX века). Информационное общество – это такая ступень развития цивилизации, на которой главными продуктами производства становятся информация и знания. ИнформатизацияИнформатизация – переход к информационному обществу: внедрение информационных технологий во все сферы жизни развитие компьютерных сетей, сотовой связи и т.п. необходимость компьютерной грамотности для всех свобода доступа к информации; доступность образования, в том числе дистанционного (через Интернет) изменение структуры экономики изменение уклада жизни людей ИнформатизацияНегативные последствия: усиление влияния СМИ разрушается частная жизнь людей сложно выбрать качественные и достоверные данные личное общение людей заменяется общением в Интернете людям старшего поколения очень сложно приспособиться Информационные ресурсыРесурсы – условия, позволяющие после некоторой «обработки» получить желаемый результат. Информационные ресурсы – документы в библиотеках, архивах, банках данных, информационных системах. товар! Информационные услуги: поиск и подбор информации подбор персонала (кадровые агентства) обучение (учебные центры) рекламные агентства консультации, услуги по оптимизации бизнеса разработка программ и веб-сайтов Информационные технологииТехнология – это способ сделать «продукт» из исходных материалов (с гарантированным результатом!). Новые информационные технологии – это технологии, связанные с использованием компьютеров для хранения, защиты, обработки и передачи информации. подготовка документов в электронном виде поиск информации телекоммуникации (сети, Интернет, e-mail) автоматизированные системы управления (АСУ) системы автоматизированного проектирования (САПР) геоинформационные системы обучение (электронные учебники, компьютерные тренажеры, дистанционное обучение). менеджер администратор сервер, база данных производство (кухня) рабочие места официантов, барменов, кассиров Ресторан+ … технологическими процессами (АСУ ТП) рабочее место оператора блок сбора информации датчики блок управления блок сбора информации датчики блок управления GSM модем GSM модем локальная сеть САПРСАПР – системы автоматизированного проектирования Геоинформационные системы (ГИС)Измерение расстояния Проложить маршрут Панорамы улиц Дистанционное обучение
консультации по Интернету Интернет тьютор Дистанционное обучениеwww.intuit.ru www.edx.org www.udacity.com www.coursera.org Гарвардский университет Массачусетский технологический институт Стэнфорский университет Университет Виргиния 33 университета www.khanacademy.org Академия Хана Компьютерные тренажёрыГосударственные электронные услугиgosuslugi.ru – Портал государственных услуг РФ подать заявку на получение паспорта подать налоговую декларацию записаться на приём к врачу; зарегистрироваться как ИП или ООО зарегистрировать автомобиль оплатить штрафы … rosreestr.ru – регистрация сделок с недвижимостью www.nalog.ru – Федеральная налоговая служба www.pfrf.ru – Пенсионный фонд РФ rospotrebnadzor.ru – Роспотребнадзор Электронная цифровая подпись (ЭЦП) – это набор символов, который получен в результате шифрования сообщения с помощью личного секретного ключа отправителя. Применение: доказательство авторства невозможность отказа от авторства защита от изменений (проверка целостности) Lorem ipsum dolor sit amet, consectetur adipiscing elit. Curabitur ultrices vulputate hendrerit. Sed odio mauris, tempor quis euismod ac, rutrum at lacus. Sed augue justo, suscipit non interdum quis, tempor in sem. Integer a hendrerit ligula. Phasellus tortor lacus, porttitor in tincidunt quis, pellentesque id nunc. Curabitur turpis mauris, tempus accumsan suscipit vitae, iaculis id risus. Sed non ipsum magna. Suspendisse quis lacus sem, vel placerat neque. Nunc vitae enim elit. Proin suscipit fringilla cursus. Cras facilisis 10101001010101011 открытый ключ секретный ключ Lorem ipsum dolor sit amet, consectetur adipiscing elit. Curabitur ultrices vulputate hendrerit. Sed odio mauris, tempor quis euismod ac, rutrum at lacus. Sed augue justo, suscipit non interdum quis, tempor in sem. Integer a hendrerit ligula. Phasellus tortor lacus, porttitor in tincidunt quis, pellentesque id nunc. Curabitur turpis mauris, tempus accumsan suscipit vitae, iaculis id risus. Sed non ipsum magna. Suspendisse quis lacus sem, vel placerat neque. Nunc vitae enim elit. Proin suscipit fringilla cursus. Cras facilisis Aсимметричное шифрование 11110101101000001 Lorem ipsum dolor sit amet, consectetur adipiscing elit. Curabitur ultrices vulputate hendrerit. Sed odio mauris, tempor quis euismod ac, rutrum at lacus. Sed augue justo, suscipit non interdum quis, tempor in sem. Integer a hendrerit ligula. Phasellus tortor lacus, porttitor in tincidunt quis, pellentesque id nunc. Curabitur turpis mauris, tempus accumsan suscipit vitae, iaculis id risus. Sed non ipsum magna. Suspendisse quis lacus sem, vel placerat neque. Nunc vitae enim elit. Proin suscipit fringilla cursus. Cras facilisis ? совпадают? Удостоверяющий центр Информационная культураДля общества – способность общества
Для человека – умение
обрабатывать информацию использовать информацию для принятия решений Нормы права и морали действуют по-прежнему! ! Стандарты в сфере ИТСтандарт – это нормативный документ, в котором определены требования к некоторому объекту или процессу. использование технических терминов разъёмы величины напряжения и силы тока протоколы обмена данными (TCP/IP) языки программирования (С++) оформление документации ISO – Международная организация по стандартизации МЭК – Международная электротехническая комиссия IBM PC – открытая архитектура Конец фильмаПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru Источники иллюстрацийwww.newbeanbag.ru compression.ru maps.yandex.ru ixbt.com www.dinamika-avia.ru www.transas.ru crazypiter.ru www.fotosearch.com www.notebookcheck.net www.energy2.ru www.wlangdesign.com www.1himplast.ru www.applecad.com gprs-modem.ru en.wikipedia.org nivo.co.za иллюстрации художников издательства «Бином» авторские материалы |