Полная версия

Главная arrow Информатика arrow Архитектура ЭВМ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Цифровое представление изображений

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

Горизонтальное разрешение

<-?

-?

'г

У

і і

CD

О

X

с; ь;

Q.

(D

СО

Рис. 1.19. Дискретизация области изображения

  • <1) X X 0) 3
  • О)

о.

со

О.

Число пикселей называется разрешением. Часто встречаются значения 640 х 480, 800 х 600, 1024 х 768, 1280 х 1024. Каждый пиксель нумеруется, начиная с нуля слева направо и сверху вниз.

Для представления цвета используются цветовые модели. Цветовая модель — это правило, по которому может быть вычислен цвет. Самая простая цветовая модель — битовая. В ней для описания цвета каждого пикселя (черного или белого) применяется всего 1 бит. Для представления цветных изображений используются более сложные модели. Известно, что любой цвет может быть представлен как сумма трех основных цветов: красного, зеленого и синего. Если интенсивность каждого цвета представить числом, то любой цвет будет выражаться через набор из трех чисел. Таким образом определяется наиболее известная цветовая ЛСВ-модель. На каждое число отводится 1 байт. Так можно представить 224 цвета, т. е. примерно 16,7 млн цветов. Белый цвет в этой модели представляется как (1, 1, 1), черный — (О, 0, 0), красный (1,0, 0), синий (0, 0, 1). Желтый цвет — комбинация красного и зеленого и потому представляется как (1, 1,0).

Пр и мер 1.7. Пусть имеется изображение вида (рис. 1.20).

  • -?
  • 5 пикселей

А

' '

0)

о

с=

0)

с;

0)

о

у

с

  • 00
  • ?-?
  • 16 пикселей

Рис. 1.20. Исходное черно-белое изображение

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

0000000000000000 0000000000000000 0000111110000000 0000100010000000 0000100010000000 0000111110000000 0000000000000000 0000000000000000

В шестнадцатеричном коде этот двоичный набор будет выглядеть так:

00 00 00 00 ОБ 80 08 80 08 80 ОБ 80 00 00 00 00

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

рр РТ РР РР РР РР РР РР РР РР РР РР РР Р0 00 1Т РР РР РР Р1 РР 1Р РР РР РР Р1 РР 1Р РР РР РР Р0 00 1Р РР РР

РР РР РР РР РР РР РР РР РР РР РР РР

Для хранения такого изображения потребуется 48 байт.

Цифровое представление звука

Звук можно описать в виде совокупности синусоидальных волн определенных частоты и амплитуды. Частота волны определяет высоту звукового тона, амплитуда — громкость звука. Частота измеряется в герцах (Гц). Диапазон слышимости для человека составляет от 20 до 17 000 Гц (или 17 кГц).

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

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

Пр и мер 1.8. Возможности наиболее распространенной современной аппаратуры предусматривают работу с частотой выборки до 44,1 кГц, что позволяет правильно описывать звук частотой до 22,05 кГц. Точность выборки имеет всего два значения: 8 и 16 бит, т. е. для представления амплитуды 8-битного звука используется 28 = 256 уровней амплитуды.

Сжатие данных

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

Пр и мер 1.9. Рассмотрим принцип сжатия простейшего универсального ЯЕЕ-метода. Для этого воспользуемся представлением изображения, полученного в примере 1.7.

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

С4 00 0Е 80 08 80 08 80 0Е 80 С4 00

Здесь символ С используется как признак последовательности одинаковых символов, т. е. С4 означает, что далее идет последовательность из четырех символов. Размер хранимого изображения уменьшился с 16 до 12 байт. Коэффициент сжатия равен 1,33. Эффективность сжатия будет зависеть от размера и содержания изображения. Если то же самое изображение преобразовать в цветовую RGB-модель, то в сжатой форме оно получит вид:

CD FF F0 00 IF СЗ FF FI FF IF СЗ FF FI FF IF СЗ FF F0 00 IF СЕ FF

При этом вместо 48 байт сжатое изображение занимает 22 байта, а коэффициент сжатия равен 2,18.

Алгоритмы сжатия широко применяются для более компактного хранения изображений. Для этого было разработано большое число графических форматов растровых изображений. Наиболее популярными являются графические форматы: BMP (Bit МаР), PCX (PCExchange), GIF (Graphics Interchange Format), TIFF (Tagged Image File Format), JPEG (Joint Photographic Experts Group), которые, по существу, различаются между собой используемыми методами сжатия. Форматы BMP и PCX используют RLE-алгоритм, форматы GIF и TIFF — LZW-алгоритм, JPEG применяет алгоритм сжатия.

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

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

С точки зрения теории информации все то, что делает язык красочным, гибким, богатым оттенками, многоплановым, многозначным — избыточность. Как избыточно с таких позиций письмо Татьяны к Онегину! Сколько в нем информационных излишеств для краткого и понятного сообщения «Я вас люблю!»

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

Уместно вспомнить рассказ о шляпочнике, пригласившем своих друзей для обсуждения проекта вывески. Предполагалось нарисовать на вывеске шляпу и написать: «Джон Томпсон, шляпочник, делает и продает шляпы за наличные деньги». Один из друзей заметил, что слова «за наличные деньги» являются излишними — такое напоминание будет оскорбительным для покупателя. Другой нашел также лишним слово «продает», так как само собой понятно, что шляпочник продает шляпы, а не раздает их даром. Третьему показалось, что слова «шляпочник» и «делает шляпы» представляют собой ненужную тавтологию. Четвертый предложил выкинуть и слово «шляпочник» — нарисованная шляпа ясно говорит, кто такой Джон Томпсон. Наконец, пятый уверял, что для покупателя совершенно безразлично, будет ли шляпочник называться Джоном Томпсоном или иначе, и предложил обойтись без этого указания. Таким образом, в конце концов на вывеске не осталось ничего, кроме рисунка шляпы.

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

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

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

В персональных компьютерах имеются две основные возможности сохранения данных:

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

Для резервирования и архивации данных применяется сжатие данных, которое представляет собой уменьшение размеров файла без значительных информационных потерь. Технология сжатия данных используется при работе с файлами больших размеров, поскольку программы-упаковщики позволяют уменьшить объем исходного документа в 2—10 раз. Коэффициент сжатия, или степень компрессии, представляет собой отношение размеров исходных и сжатых данных. Степень сжатия данных зависит от типа файлов. Например, текстовые файлы сжимаются в 2—3 раза. Файлы для черно-белых изображений формата РСХ и ВМР могут быть сжаты в 5—10 раз. Выполняемые файлы ЕХЕ сжимаются очень плохо. Упакованные графические файлы не сжимаются.

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

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

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

  • • имя файла;
  • • сведения о местонахождении файла на диске;
  • • дата и время последней модификации файла;
  • • размер файла на диске и в архиве;
  • • коэффициент сжатия.

Наиболее распространенные архиваторы АЯЭ, VinZIP, VinRaR, VinARJ, ЬНА, РКРАК, РАК имеют приблизительно одинаковые возможности. Утилита YinARJ имеет больше команд, чем архиваторы Ут21Р-семейства. Архиватор VinRaR имеет наименьшее число функциональных элементов и возможностей управления по сравнению с VinZIP и VinARJ. Вместе с тем архиватор YinRaR, выполняя работу медленно, превышает в три-четыре раза степень сжатия Ут71Р-упаковщика, который считается одним из самых быстродействующих.

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

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

Имена архивных файлов программ ARJ и ’Ут71Р имеют следующие расширения: Мр — для архивных файлов программ YinZIP, .«/у — для архивных файлов программ ARJ.

Мера уменьшения неопределенности знания

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

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

В окружающем мире существует множество явлений, которые каждый раз происходят несколько по-иному, приводят к неожиданному результату. Эти явления называют случайными. Случай играет не последнюю роль в жизни человека. Не зря издавна существует понятие «Его Величество Случай».

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

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

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

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

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

Пример 1.10. На примере игры «Угадай число» рассмотрим уменьшение неопределенности. Первый участник загадывает целое число (например, 30) из заданного интервала (например, от 1 до 32), цель второго — «угадать» число первого участника. Для второго игрока начальная неопределенность знания составляет 32 возможных события. Чтобы найти число, необходимо получить определенное количество информации. Первый участник может отвечать только «да» или «нет». Второй должен выбрать следующую стратегию: последовательно, на каждом шаге уменьшать неопределенность знания в два раза. Для этого он должен делить числовой интервал пополам, задавая вопросы (табл. 1.7).

Таблица 1.7. Рабочая таблица

Вопрос второго участника

Ответ первого участника

Количество возможных событий (неопределенность знания), 32

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

Число больше 16?

Да

16

1

Число больше 24?

Да

8

1

Число больше 28?

Да

4

1

Число больше 30?

Нет

2

1

Это число 30?

Да

1

1

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

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

Если / — количество информации; к — количество возможных событий; р1 вероятности отдельных событий, то количество информации для событий с различными вероятностями можно определить по формуле

к

  • 1о§2 А>
  • 1=1

где / принимает значения от 1 до к.

Как частный случай формулы Шеннона можно рассматривать формулу Хартли:

/= 1о^Х= о%20/р) = -1о&2Р или К =2',

где каждое из К событий имеет равновероятный исход р = 1 /К.

Формулу Хартли применяют для случая, когда все состояния, в которых может находиться объект, равновероятны.

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

Пусть вероятность отдельных событий будет такова:

Л = 1/2; />2=1/4; />з=1/8; />4= 1/8.

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

1=-(/2оё2/2+ 1 /41о§21 /4 + 1/810^1/8+ 1/81ое21/8) =

= 1/2 + 2/4 + 3/8 + 3/8 =14/8=1,75 бит.

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

Сообщение содержит по формуле Хартли / = 1о§216 = 4 бита информации.

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

Таблица 1.8. Рабочая таблица

Вопрос второго игрока

Ответ первого игрока

Количество

возможных событий, 32

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

Задумана карта красной масти?

Нет

16

1

Задумана карта крестовой масти?

Да

8

1

Задумана карта-картинка?

Да

4

1

Задумана дама или туз крестовой масти?

Нет

2

1

Задуман валет крестовой масти?

Нет

1

1

Ответ. Был задуман король крестовой масти.

Пример 1.14. При угадывании целого числа в диапазоне от 1 до К было получено 7 бит информации. Чему равно К?

По формуле Хартли /= о%2К или К =2'. К= 27= 27 = 128.

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

Решение. Пусть объект А работает почти без перерыва, т. е. вероятность того, что он включен, очень велика (например, р_А_вкл = 0,99 и р А выкл = 0,01, а объект Б работает иначе и для него р_Б_вкл = р_Б_выкл = 0,5). Тогда, если диспетчер получает сообщение том, что объект А включен, он получает очень мало информации. С объектом Б дела обстоят иначе.

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

Объект А: /=-(0,99-1ое2(0,99) +0,01 • к^2(0,01)) = 0,0808.

Объект Б: / = -(0,50 • ^2(0,50) + 0,50 • ^2(0,50)) = 1.

Итак, каждое сообщение объекта Б несет 1 бит информации.

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

/= ^2(8) = 3 бита.

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

Какое количество информации содержит один символ в слове или тексте?

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

1= ^2(64) = 6 бит.

Из двух символов данного алфавита может быть образовано п = 64 • 64 = 4096 различных сочетаний.

Следовательно, два символа несут /= 1о§2(4096) = 12 бит информации.

Пр и мер 1.18. Оценим количество информации, содержащейся в числах.

Если предположить, что цифры 0, 1, ..., 9 используются одинаково часто (равновероятны), то одна цифра содержит / = ^2( 10) = 3,32 бита; четырехзначное число из диапазона [0..9999], если все его значения равновероятны, содержит /= к^2( 10 000) = 13,28 бита; восьмиразрядное число 1 = = 1ое2(100 обо 000) = 26,56 бита.

 
<<   СОДЕРЖАНИЕ   >>