Учебное пособие Курск 2016
 Скачать 0.64 Mb.
|
|
Понятие об оптимальном кодировании информации. В компьютере информация представляется в двоичном виде, и, вообще говоря, кодирование информации в ЭВМ - одна из задач теории кодирования. Теория кодирования - один из разделов теоретической информатики. Одна из задач - разработка принципов наиболее экономичного кодирования. Эта задача касается передачи, обработки, хранения информации. Частное ее решение – представление информации в компьютере. Источник представляет сообщение в алфавите, который называется первичным, далее это сообщение попадает в устройство, преобразующее и представляющее его во вторичном алфавите. Код – правило, описывающее соответствие знаков (или их сочетаний) первичного алфавита знаком (их сочетаниями) вторичного алфавита. Кодирование– перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов. Декодирование – операция обратная кодированию. Кодер – устройство, обеспечивающее выполнение операции кодирования. Декодер – устройство, производящее декодирование. Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечит возврат к исходной информации без каких-либо ее потерь. Пример обратимого: слова - телеграфный код. необратимого: английский - русский – здесь неоднозначно. Далее будем иметь в виду только обратимое кодирование. Математическая постановка условия обратимого кодирования. Пусть первичный алфавит А состоит из N знаков со средней информацией на знак IA , вторичный В – из М знаков со средней информацией на знак IB . Пусть сообщение в первичном алфавите содержит n знаков, а закодированное – m знаков. Если исходное сообщение содержит IS (A) информации, а закодированное If (B), то условие обратимости кодирования (то есть неисчезновения информации при кодировании) очевидно может быть записано так: IS(A) < If (B) - то есть операция обратимого кодирования может увеличить количество информации в сообщении, но не может уменьшить ее. n* I(A) < m* I(B) (заменили произведением числа знаков на среднее информационное содержание знака). Отношение m/n –характеризует среднее число знаков вторичного алфавита, который используется для кодирования одного знака первичного. Обозначим его К(А,В) К(А,В) > I(A) / I(B) . Обычно К(А,В) >1 => знак первичного алфавита кодируется несколькими вторичными =>? – проблема выбора наилучшего варианта – оптимального кода. Оптимальность- это экономический фактор (меньше энергии, времени, объема носителя - уже в зависимости от задачи и поставленных ограничений). Минимально возможная длина кода: Кmin (А,В)= I(A) / I(B)–это нижний предел длины кода. Но реально в схемах кодирования как близко возможное приближение К(А,В) к Кmin (А,В). Кодирование символьной и числовой информации. Начиная с конца 60-х годов, компьютеры все больше стали использоваться для обработки текстовой информации и в настоящее время большая часть персональных компьютеров в мире (и наибольшее время) занято обработкой именно текстовой информации. Традиционно для кодирования одного символа используется количество информации, равное 1 байту, то есть I= 1 байт = 8 битов. Для кодирования одного символа требуется 1 байт информации. Если рассматривать символы как возможные события, то по формуле N=2I можно вычислить, какое количество различных символов можно закодировать: N=2I=28=256. Такое количество символов вполне достаточно для представления текстовой информации, включая прописные и строчные буквы русского и латинского алфавита, цифры, знаки, графические символы и пр. Кодирование заключается в том, что каждому символу ставится в соответствие уникальный десятичный код от 0 до 255 или в соответсвующий ему двоичный код от 00000000 до 11111111. Таким образом, человек различает символы по их начертаниям, а компьютер – по их кодам. При вводе в компьютер текстовой информации происходит ее двоичное кодирование, изображение символа преобразуется в его двоичный код. Пользователь нажимает на клавиатуре клавишу с символом, и в компьютер поступает определенная последовательность из восьми электрических импульсов (двоичный код символа). Код символа хранится в оперативной памяти компьютера, где занимает один байт. В процессе вывода символа на экран компьютера производится обратный процесс – декодирование, то есть преобразование кода символа в его изображение. Важно, что присвоение символу конкретного кода – это вопрос соглашения, которое фиксируется в кодовой таблице. Первые 33 кода (с 0 по 32) соответствуют не символам, а операциям (перевод строки, ввод пробела и так далее). Коды с 33 по 127 являются интернациональными и соответствуют символам латинского алфавита, цифрам, знакам арифметических операций и знакам препинания. Коды с 128 по 255 являются национальными, то есть в национальных кодировках одному и тому же коду соответствуют различные символы. К сожалению, в настоящее время существует пять различных кодовых таблиц для русских букв (КОИ8, СР1251, СР866, Мас, ISO), поэтому тексты, созданные в одной кодировке, не будут правильно отображаться в другой. В настоящее время широкое распространение получил новый международный стандарт Unicode, который отводит на каждый символ не один байт, а два, поэтому с его помощью можно закодировать не 256 символов, а N=216=65536 различных символов. Эту кодировку поддерживают последние версии платформы Microsoft Windows&Office (начиная с 1997 года). Каждая кодировка задается своей собственной кодовой таблицей. Как видно из таблицы, одному и тому же двоичному коду в различных кодировках поставлены в соответствие различные символы. Таблица 9. Кодировки символов
Например, последовательность числовых кодов 221, 194, 204 в кодировке СР1251 образует слово «ЭВМ», тогда как в других кодировках это будет бессмысленный набор символов. К счастью, в большинстве случаев пользователь не должен заботиться о перекодировках текстовых документов. Так как это делают специальные программы-конверторы, встроенные в приложения. Кодирование графической информации. Пространственная дискретизация. В процессе кодирования изображения производится его пространственная дискретизация. Пространственную дискретизацию изображения можно сравнить с построением изображения из мозаики (большого количества маленьких разноцветных стекол). Изображение разбивается на отдельные маленькие фрагменты (точки), причем каждому фрагменту присваивается значение его цвета, то есть код цвета (красный, зеленый, синий и так далее). Качество кодирования изображения зависит от двух параметров. Во-первых, качество кодирования изображения тем выше, чем меньше размер точки и соответственно большее количество точек составляет изображение. Во-вторых, чем большее количество цветов, то есть большее количество возможных состояний точки изображения, используется, тем более качественно кодируется изображение (каждая точка несет большее количество информации). Совокупность используемых в наборе цветов образует палитру цветов. Формирование растрового изображения. Графическая информация на экране монитора представляется в виде растрового изображения, которое формируется из определенного количества строк, которые в свою очередь содержат определенное количество точек (пикселей). Такое количество символов вполне достаточно для представления текстовой информации, включая прописные и строчные буквы русского и латинского алфавита, цифры, знаки, графические символы и пр. Качество изображения определяется разрешающей способностью монитора, т.е. количеством точек, из которых оно складывается. Чем больше разрешающая способность, то есть чем больше количество строк растра и точек в строке, тем выше качество изображения. В современных персональных компьютерах обычно используются три основные разрешающие способности экрана: 800 на 600, 1024 на 768, 1280 на 1024 точки Рассмотрим формирование на экране монитора растрового изображения, состоящего из 600 строк по 800 точек в каждой строке (всего 480000 точек). В простейшем случае (черно-белое изображение без градаций серого цвета) каждая точка экрана может иметь одно из двух состояний – «черная» или «белая», то есть для хранения ее состояния необходим 1 бит. Цветные изображения формируются в соответствии с двоичным кодом цвета каждой точки, хранящимся в видеопамяти. Цветные изображения могут иметь различную глубину цвета, которая задается количеством битов, используемым для кодирования цвета точки. Наиболее распространенными значениями глубины цвета являются 8, 16, 24 или 32 бита. Таблица 10. Формирование растрового изображения.
Качество двоичного кодирования изображения определяется разрешающей способностью экрана и глубиной цвета. Каждый цвет можно рассматривать как возможное состояние точки, тогда количество цветов, отображаемых на экране монитора, может быть вычислено по формуле: N=2I, где I – глубина цвета. Таблица 11. Глубина цвета и количество отображаемых цветов.
Цветное изображение на экране монитора формируется за счет смешивания трех базовых цветов: красного, зеленого и синего. Такая цветовая модель называется RGB-моделью по первым буквам английских названий цветов. Для получения богатой палитры цветов базовым цветам могут быть заданы различные интенсивности. Например, при глубине цвета в 24 бита на каждый из цветов выделяется по 8 бит, то есть для каждого из цветов возможны N=28=256 уровней интенсивности, заданные двоичными кодами (от минимальной – 00000000 до максимальной - 11111111). Таблица 12. Формирование цветов при глубине цвета 24 бита
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||