Лекция 2. Информационная емкость сообщений. Исходное кодирование
Курс “Теория информации и кодирования”

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

Информационная емкость сообщений
Исходное кодирование текста
Исходное кодирование изображений
Исходное кодирование звука

Дополнительно об исходном кодировании

Информационная емкость сообщений
Рассмотрим общий случай дискретного сообщения, которое представляет собой последовательность из L знаков, принадлежащих алфавиту объемом N. Максимальное количество информации, которое способно нести такое сообщение, назовем его информационной емкостью. Используются две меры информационной емкости и, соответственно, информации (рис.2.1):
  • такой мерой может служит количество уникальных сочетаний знаков QL=NL. Действительно, каждому такому сочетанию можно присвоить индивидуальный смысл. В соответствии с видом функции данная мера информации называется показательной;
  • при очевидной простоте и наглядности показательная мера характеризуется и опредленными недостатками: во-первых, при сколько-нибудь значительных длинах сообщений значения Q становятся огромными и с ними неудобно работать; во-вторых, здесь отсутствует важное привычное свойство сообщений — количество информации не пропорционально их длине (например, два трехзначных числа могут иметь до 1000 значений каждое, а их объединение — число из шести цифр может иметь уже до 1000000 значений). Это называют неаддитивностью;
  • устранить упомянутые недостатки позволяет знакомая нам операция логарифмирования. Используем в качестве меры информации в сообщении из L знаков например величину IL = log2NL = L logLN. Как видно, теперь количество информации, которое может нести сообщение, пропорционально его длине (логарифмическая мера аддитивна), а порядок величин становится вполне обозримым (например, при довольно большом N=65536, которое характерно для двухбайтного кодирования звука, величина IL=L log265536 составляет всего Lх16). Итак, логарифмическая мера информации достаточно удобна и компактна. На практике применяется именно она;
  • если величину QL можно было трактовать как максимально возможное число сочетаний знаков в сообщении, то значение IL определяет необходимое количество разрядов для его кодирования. Так, в рассмотренном выше примере для сообщения из L=100 знаков необходимо 1600 двоичных разрядов. При этом нужно учитывать, что точное соответствие числу разрядов получается только если объем алфавита N кратен степени двойки. В случае, когда например N=10, получим log2N≈3,3219. При этом для сообщения длиной L=100 знаков понадобится I=333 двоичных разряда (с учетом округления до целого в большую сторону);
  • существенно, что преимущества логарифмической меры сохраняются при любом основании логарифма. То-есть, в общем виде можно записать формулу IL(m) = L logmN. При этом выбор m, разумеется, повлияет на результат расчета. На самом деле этот параметр определяет единицы измерения информации.

Единицы измерения информации
Как известно, общепринятой единицей количества информации является бит. При этом важно уточнить следующее (рис.2.2):
  • один бит — количество информации, которое соответствует ее элементарному кванту — двоичному выбору. Бит может иметь одно из двух противоположных значений (в связи с этим иногда говорят про «пол» бита - sex оf bit). Эти значения, в частности, реализуются как состояния двоичного разряда кода (0 или 1). Применительно к сообщениям такое означает использование двоичного алфавита. При этом значение I= logm2=1 достигается только при основании логарифма m=2. Таким образом, единица измерения бит предполагает именно использование основания 2 при логарифмировании;
  • поскольку в принципе возможно использование и других оснований m, могут существовать и альтернативные единицы измерения информации. В частности, m=10 соответствует единица “дит”, а m=e - “нит”. Это можно сравнить с использованием валют: одна и та же стоимость при различных валютных курсах будет отвечать разному количеству денежных единиц. Однако валюта “биты” (m=2) занимает уникальное положение, поскольку объективно соответствует минимальному кванту информации — двоичному выбору. К тому же, как известно, техническая реализация двоичного кода наиболее проста;
  • как мы уже обратили внимание, что количество битов, которое несет выбор из N альтернатив, может быть не целым (во всех случаях, когда значение N не кратно степени 2). Это вполне естественно, если понимать, что мы имеем дело с единицей измерения, а не с объектом. Объектами в случае сообщений являются знаки. При этом для объемных алфавитов знаки могут условно говоря дробиться за счет перекодирования в более простые алфавиты. По сути, мы уже знакомились с таким подходом, рассматривая способы форматирования сообщений с использованием двоичного алфавита.

2.2 Исходное кодирование текста

Подходы к кодированию текста
Значительная часть сообщений состоят из последовательности знаков (букв, цифр, разделителей, специальных знаков, пиктограмм и т.д.). При вводе знаков в цифровую среду они преобразуются в стандартные двоичные коды, длина которых кратна байту. В настоящее время применяются два основных способа форматирования знаков (рис.2.3):
  • компактное однобайтное кодирование с использованием так называемых «кодовых страниц» (code page или CP);
  • универсальное по большей части двухбайтное кодирование на базе стандарта Unicode.

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

Способ Unicode предусматривает однозначное соответствие кода и отображения знака. При условии, что общее количество разновидностей используемых знаков далеко превышает емкость двух байт (216 = 16635), за счет специальных приемов стандарт позволяет кодировать двумя байтами около миллиона знаков, что вполне достаточно. Применение Unicode – современный и перспективный способ кодирования знаков.

Особенности кодовых страниц
Кодовые страницы представляют собой таблицы соответствия знаков и их двоичных однобайтных кодов (рис.2.4):
  • каждая CP имеет форму квадратной таблицы с 16 строками и 16 столбцами. Номера строк и столбцов соответсвую первому и второму полубайтам (4 двоичных разряда) кода знака. Эти номера удобно обозначать 16-ричными цифрами. Так например, 16-ричный код 62h соответствует ячейке таблицы с номером строки 0110 (6h) и номером столбца 0010 (2h). При этом иногда пользуются и десятичной нумерацией ячеек (62h отвечает десятичное 98);
  • верхняя половина всех кодовых страниц имеет стандартное наполнение, которое охватывает наиболее употребимые знаки, используемые в текстах, и специальные знаки, применяющиеся для управления стандартными устройствами и передачей данных. Все они охватываются стандартом ANSI (ASCII). В частности, здесь расположены латинские буквы, цифры, знаки разделителей и математических операций (в таблице их 95). Интерпретация их кодов всегда одинакова: например, для любой CP код 62h будет отвечать латинской букве b. В таблице представлены также 33 специальных знака. Примерами здесь могут служить знаки LF и CR (возврат в начало строки и перевод строки) c кодами 0Ah и 0Dh. При этом их коды могут отображаться на экране как символы (например, 0Ah соотвествует символ “нота”);
  • нижняя половина CP предназначена для отображения знаков национальных алфавитов и может различаться для разных компьютерных платформ и операционных систем. При этом один и тот же код будет отображаться различными кодовыми страницами по-разному. В частности, знаки кириллического алфавита в Windows отображаются страницей CP-1251. Аналогичные страницы будут отличаться не только для компьютеров Apple или мэйнфреймов IBM, но и для других ОС на платформе Intel. Так в Microsoft-DOS знаки кириллицы размещаются на странице CP866. При этом если для Windows CP-1251 коду E1h будет соответствовать буква “б”, то для CP866 MS-DOS— кириллическая “с”. Мы ближе познакомимся с этими нюансами в лабораторной №1.

Особенности стандарта Unicode
Стандарт Unicode включает сквозную нумерацию всех известных символов (таблица Universal character set - UCS) и представление их номеров в формате 1, 2 и 4 байтов (таблицы Unicode transformation format UTF-8, -16, -32) – рис.2.5. При этом:
как мы уже знаем, распространение получил двухбайтный вариант кода (UTF-16). Однобайтное кодирование (UTF-8) применяется для совместимости с кодовыми страницами, а четырехбайтное (UTF-32), хотя и является наиболее емким, на практике не используется из-за громоздкости;
  • двухбайтному коду отвечает четыре 16-ричных цифры. Например, латинской букве «b» соответствует обозначение U+0062h (здесь нулевой код первого байта указывает, что данный символ находится в начале таблицы кодирования). А юникод кириллической буквы “б” имеет вид U+0431h. В отличие от CP такой код уникален и отвечает только данному знаку. Полные таблицы знаков юникода можно найти, в частности, на сайте https://unicode-table.com/ru/;
  • при использовании непосредственного 16-разрядного кодирования общее количество кодов не может превышать 216 ≈65 тыс. Однако, количество используемых знаков может быть значительно больше (например, включая полный состав используемых иероглифов). В связи с этим спецификация UTF-16 предусматривает специальный способ хранения кодов редко используемых знаков с помощью пар 16-разрядных слов. Из такой пары с помощь специального преобразования формируется трехбайтный код. В итоге, количество знаков, которые могут быть закодировано с помощью UTF-16 составляет порядка миллиона, что вполне достаточно для практических нужд.

Контрольные вопросы
1) Назовите основные способы исходного кодирования (форматирования) знаков и дайте их общую характеристику.
2) Поясните устройство кодовых страниц. Каковы особенности их верхней и нижней части.
3) Опираясь на коды знаков 64h и D7h, охарактеризуйте специфику отображения соответствующих знаков при использовании разных кодовых страниц.
4) Какова роль разделов UCS и UTF в стандарте Unicode.
5) Почему наибольшее распространение получил вариант UTF-16. Как используются варианты UTF-8 и UTF-32.


2.3 Исходное кодирование сообщений: Изображения

Растровая форма изображений
Растр — матрица цветовых точек — пикселей (pixel – от “элемент изображения”) - рис.2.6. Он характеризуется следующим:
  • растровая форма представления изображений универсальна в том смысле, что любое изображение может быть представлено таким образом. Альтернативой растровому является так называемое векторное представление, которое мы также рассмотрим в дальнейшем;
  • основными параметрами растра, связанными с кодированием, являются его габариты (количество точек по горизонтали X и по вертикали Y) и объем X*Y (объем обычно измеряется в мегапикселях - Mp). Например, растр габаритами 3000х2000 имеет объем 6Мp;
  • объем кода растра помимо числа пикселей определяется разрядностью кода пикселей Lp (используется также термин «глубина цвета»). Она может колебаться от 1 до 24 бит. При этом количество оттенков N зависит от разрядности n согласно формуле N=2n. Часто используемые значения глубины и цветности приведены на рис.1.9. При пересчете объема кода в нужно помнить о переходе битов к байтам и далее к мегабайтам (рис.1.9). Например, при габаритах растра X=3000, Y=2000 и глубине цвета Lp=24 объем кода составит 1,71661377≈1,72 MБ.

Отображение цветов пикселей
Оттенки пикселей, как правило, создаются за счет наложения нескольких базовых цветов. При этом могут использоваться различные наборы базовых цветов - цветовые модели. Таким образом, отображение цвета задается не только кодом, но и цветовой моделью (рис.2.7). При этом:
  • наиболее широко применяется модель RGB (красный, зеленый, голубой). Она приспособлена для мониторов, поскольку предполагает наложение цветовых составляющих на черный фон. Соответственно, такую модель называют аддитивной (от addition - сложение). Чаще всего каждая из составляющих кодируется одним байтом (24-битная глубина цвета). При этом равные или близкие значения кодов RGB дают градации серого цвета;
  • модель CMY (голубой, пурпурный, желтый) используется в основном при печати, где фоновым цветом является белый. Цвета CMY получаются вычитанием RGB из белого, поэтому ее называют субстрактивной (от substaction - вычитание). Чтобы облегчить получение важного для полиграфии черного цвета, его вводят в модель в качестве четвертого (CMYK);
  • на практике помимо RGB и CMY/CMYK применяются и другие цветовые модели. Здесь выделим так называемую цветоразностную модель YUV (YCrCb), которая понадобится нам при изучении сжатия изображений. Она включает наряду с друмя базовыми цветами (красным и синим) также суммарную яркость пикселя. Поскольку яркость может быть определена суммированием кодов базовых цветов (разумеется, с учетом ограничений разрядности), несложно построить процедуры взаимных переходов между моделями RGB и YUV (YcrCb).

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

Контрольные вопросы
1) Опишите основные характеристики растрового изображения.
2) Рассчитайте объем кода растрового изображения габаритами 1000х1500 пикселей при 16-битном непосредственном кодировании цветов.
3) Как проявляется специфика графических форматов в объеме кода растровых изображений.
4) Охарактеризуйте наиболее распространенные цветовые модели и их применение.
5) Поясните принцип векторного представления изображений. В чем состоят его преимущества и ограничения в применении.

2.4 Исходное кодирование сообщений: Звук

Этапы оцифровки звука
Звуковое сообщение обычно поступает в цифровую среду через микрофон, на выходе которого образуется непрерывная зависимость напряжения от времени u(t) (рис.2.9). Это частный случай непрерывной зависимости сигнала от времени и принципы ее оцифровки являются общими.
Такая оцифровка включает два этапа:
  • дискретизация по времени. Фиксируются «засечки» амплитуды непрерывного сигнала u(t) в моменты времени ti. Шаг по времени Δt берется постоянным в интересах простоты и стандартизации. Ему соответствует частота дискретизации fd=1/Δt;
  • квантование амплитуд. Зафиксированные значения амплитуд U(ti) приводятся к дискретным уровням Uj(ti). Величина шага квантования Δu также принимается постоянной — опять-таки для простоты реализации. Дискретным значениям Uj(ti) сразу ставятся в соответствие двоичные коды. Величина шага Δu вместе с диапазоном изменения Umах – Umin определяет разрядность n используемого кода;
  • очевидно, что выбор частоты дискретизации по времени fd а также разрядности n квантования амплитуд с одной стороны определяют точность оцифровки, а с другой - объем получаемого кода. Обоснование их выбора в общем виде мы рассмотрим в следующей лекции, а пока зафиксируем, какие значения принимаются при оцифровке звука.

Параметры оцифровки звука
Выбор частоты и разрядности оцифровки исходят из требований к качеству восприятия восстановленного звука. На практике выделяют две категории звуковых данных: произвольный звук и речь. В первую категорию входит, в частности, музыка. В этом случае ориентируются на предельные возможности человеческого слуха. Во втором случае требования к качеству значительно ниже. Здесь критерием является разборчивость содержания.
Параметры оцифровки звука для этих двух случаев существенно отличаются (рис.2.10):
  • стандартная частота дискретизации для произвольного звука принята на уровне 44 кГц (ниже мы выясним ее обоснование). Часто используются также кратные частоты. Например, частота 22 кГц все еще дает приемлемое качество звука. Для речи с позиций ее разборчивости принят стандарт fd = 8 кГц;
  • стандартная разрядность кода при оцифровке должна быть кратна байту. Чтобы обеспечить разборчивость речи, для кодирования амплитуды достаточно одного байта (n=8). Для произвольного звука используют двухбайтное кодирование (n=16). В дальнейшем мы рассмотрим общие подходы к выбору шага квантования амплитуд;
  • важным параметром оцифровки звука является скорость кодирования, которую принято называть битрейтом. Битрейт определяется в кбит/с и вычисляется как произведение fdxn (тыс. отсчетов/с х бит/отсчет). Например, для оцифрованной речи битрейт составляет 8х8=64 кбит/с, а для произвольного звука при максимальной частоте дискретизации 44х16=704 кбит/с (для стереозвука соответственно 1408 кбит/с). Обратим внимание, что измеритель кбит/с связан с частотой кГц, так что здесь не участвует привычный коэффициент 1024.

Представление данных оцифровки звука
Представление оцифрованного звука в компьютерной памяти (в частности, в файлах) характеризуется следующим (рис.2.11):
  • код представляет собой цепочку байтов, значения которых интерпретируются в зависимости от заданных параметров оцифровки (последние присутствуют в заголовке файла). Наиболее распространенным форматом исходного представления звука является .wav (от wave - волна);
  • код амплитуды выбирается из одного или двух байт (в зависимости от заданной разрядности кодирования). При этом старший разряд кодирует знак. В случае стереозвука пара амплитуд для разных каналов хранится в четверке смежных байтов;
  • частота, с которой амплитуды читаются для восстановления звука, также задается в заголовке звукового файла. Помимо уже упомянутых значений 8 кГц (для речи) и 44 кГц (для произвольного звука), используются и другие значения — например, 22 кГц при невысоких требованиях к качеству звука.


Контрольные вопросы
1) Используя рисунок 2.9, поясните принцип оцифровки непрерывных зависимостей (и в частности, звука): дискретизации по времени и квантования по уровню.
2) Исходя из каких требований выбираются параметры оцифровки произвольного звука и оцифровки речи.
3) Что такое битрейт и как он определяется.
4) Назовите основные значения параметров оцифровки звука (для случаев произвольного звука и речи). Объясните их.
5) Поясните интерпретацию значений байтов в звуковом файле формата .wav в зависимости от содержания заголовка файла.


2.5 Исходное кодирование сообщений: Дополнительные сведения

Дополнительно о кодировании текста
Практическое использование кодовых страниц иллюстрирует рисунок 2.12. Здесь показано содержание тестового файла, в котором использованы знаки кириллицы, в универсальном текстовом формате rtf. Файл создан в стандартной программе WordPad и содержит имя в латинской и русской транскрипции, а также год рождения. Для того, чтобы символы кириллицы отображались корректно на любом компьютере, программа сохраняет в файле ссылку на страницу CP1251 и 16-ричные коды букв, которые задают их позиции на кодовой странице. При этом латинские буквы и цифры сохраняются в файле непосредственно.

Особенности формирования «длинных» кодов для редко встречающихся знаков в рамках UTF-16 поясняет рис.2.13:
  • первоначально данные для формирования кода хранятся в двух 16-битных словах (так называемая «суррогатная пара»). При этом содержание первого и второго слов интерпретируется как номер строки и столбца большой таблицы размером 1024х1024, содержащей уже длинные коды знаков;
  • исходя из размеров таблицы, количество дополнительных знаков составляет 220, соотвественно, коды дополнительных знаков могут иметь 20 двоичных разрядов (5 шестнадцатиричных цифр). Например, код знака “поезд”, относящегося к категории “транспортные и картографические символы”, имеет вид U+1F686h. Однако, количество байтов кода должно быть целым, поэтому полный код будет 24-разрядным;
  • условные номера строк и столбцов привязаны к фиксированным диапазонам адресов: соответственно — от D800h до DBFFh и от DC00h до DFFFh. Соответственно, этот диапазон не используется для непосредственного кодирования знаков. Однако, исключив здесь всего 2K кодов, мы получаем возможность адресоваться дополнительно более, чем к миллиону знаков.

Дополнительно о кодировании изображений
На практике используются два способа кодирования цветов (рис.2.14):
  • непосредственное (для каждого пикселя задаются коды всех его составляющих) - этот способ проще;
  • с помощью «палитр» (код пикселя указывает на строку в таблице цветов) - такой вариант экономичнее.

При непосредственном кодировании для глубины цвета 24 разряда длина кода кратна трем и ее распределение по цветам равномерно. Для более коротких кодов (8- и 16-разрядных) может применяться неравномерное распределение кода по цветам. При этом учитывается, что базовые цвета RGB имеют разную значимость для восприятия: зрение наиболее чувствительно к зеленому и наименее — к синему (рис.1.17).

При использовании палитр 8- или 16-разрядный код цвета является указателем на таблицу из 28 или 216 строк, в которых точные коды оттенков представлены уже с помощью 24 разрядов (рис.2.14). Это позволяет значительно экономить память. Число используемых оттенков можно расширить например за счет применения разных палитр для различных зон изображения. Разумеется, палитры занимают в графических файлах дополнительное место.

Наглядным примером компактного описания векторного изображения может служить рис.2.15
Здесь показан текст описания простого изображения на языке SVG (подмножество XML). SVG-текст интерпретируется современными браузерами в растровую картинку. При этом сам он представляется знаками ASCII, занимающими по 1 байту. На рисунке показан пример описания трех перекрывающихся разноцветных прозрачных кругов, которые вписаны в квадрат. В частности, строка задает описание красного круга радиусом 104 пикселя, центр которого размещается на 52 пикселя выше центра фонового квадрата со сторонами 400х400 пикселей. Вы легко самостоятельно определите смысл других параметров описания этого изображения. Важно, что данное описание во много раз компактнее, чем файл с соответствующей растровой картинкой.

Дополнительно о кодировании звука
Представление о технической реализации оцифровки непрерывных зависимостей и, в частности, звука дает рис.2.16:
  • непрерывный сигнал u(t) первоначально поступает на вход блока дискретизации и удержания, где амплитуда U(ti) фиксируется на время Δt. Шаг по времени, как мы уже знаем, определяется по правилу Найквиста-Котельникова с учетом максимальной частоты изменения сигнала;
  • за время Δt алфавитно-цифровой преобразователь АЦП успевает сформировать двоичный код Kj(ti), который отвечает дискретному уровню сигнала Uj(ti). Современные АЦП представляют собой стандартные микросхемы чьи разрядности обычно принадлежат ряду 8, 10, 12 и 16
  • после цифровой обработки (передачи) звуковых данных они могут быть использованы для воспроизведения звука. При этом первоначально цифро-аналоговый преобразователь (ЦАП) восстанавливает дискретные уровни сигналов U*j(ti) для моментов по их коду K*j(ti) (здесь признак * означает, что значение кода в принципе могла измениться в ходе передачи и обработки). ЦАП как правило — тоже стандартная микросхема;
  • на последнем этапе сглаживающий фильтр (СФ) восстанавливает непрерывную зависимость u(t) для ее непосредственной выдачи на звуковоспроизводящую аппаратуру.

Контрольные вопросы
1) Опираясь на пример, показанный на рис.2.12, поясните способ использования кодовых страниц в файлах универсального текстового формата.
2) Используя рис.2.13, поясните способ, с помощью которого в рамках стандарта Unicode обеспечивается кодирование до миллиона знаков с помощью двухбайтных слов.
3) Поясните принцип и преимущества кодирования цвета с использованием палитр.
4) Прокомментируйте SVG-описание растрового изображения по рис.2.15.
5) Поясните работу схемы оцифровки и воспроизведения звуковых сигналов на рис.2.16.

О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP