Что такое посимвольное кодирование
Что такое посимвольное кодирование
1. Пользуясь таблицей кодировки ASCII и CP-1251 закодируйте следующие послания:
2. В некоторой кодировке для хранения одного символа отводится 2 байта. Определите вес слова из двадцати двух символов в данной кодировке.
3. В кодировке КОИ-8 для хранения одного символа отводится 1 байт. Определите вес (в битах) слова «дезоксирибонуклеиновая».
4. Некоторый текст записан в различных кодировках. Известно, что текс в 16-битной кодировке Unicode, на 120 бит больше текста, закодированного 8-битной кодировкой CP-1251. Определите количество символов в тексте.
5. В кодировке Unicode для хранения одного символа отводится 16 бит. Дан отрывок текста, записанного в данной кодировке:
«Калининград, Ярославль, Владимир, Елабуга, Троицк, Томск, Омск, Уфа – города России».
В результате редактирования текста, одно слово и ставшие лишними пробелы и запятые удалили. Новый текст стал на 14 байт меньше. Определите удалённое слово.
6. Текст, напечатанные на компьютере занял несколько страниц. Каждая страница текста состоит из 60 строк по 30 символов в строке. Файл с данным текстом занимает в компьютере 225 Кбайт. Сколько страниц содержит данный текст, если известно, что он закодирован в Unicode.
7. В кодировке Windows-1251 каждый символ кодируется 8 бит. Вова хотел написать текст (в нём нет лишних пробелов):
«Скользя по утреннему снегу,
Друг милый, предадимся бегу
И навестим поля пустые…»
Одно из слов ученик написал два раза подряд через пробел. При этом размер написанного предложения в данной кодировке оказался на 10 байт больше, чем размер нужного предложения. Напишите в ответе лишнее слово.
9. В кодировке КОИ-8 каждый символ кодируется 8 бит. Вова хотел написать текст (в нём нет лишних пробелов):
«Скользя по утреннему снегу,
друг милый, предадимся бегу
нетерпеливого коня и навестим поля пустые…»
Одно из слов ученик написал два раза подряд через пробел. При этом размер написанного предложения в данной кодировке оказался на 14 байт больше, чем размер нужного предложения. Напишите в ответе лишнее слово.
10. Растровое изображение размером 512х720 пикселей занимает 90 Кбайт памяти. Определите количество цветов в палитре, с помощью которой было закодировано данное изображение.
11. Монитор поддерживает 16-цветовую палитру и вмещает изображение размером 480х640 пикселей. Определите объём видео памяти, необходимый для хранение полноформатного изображения исходя из особенностей данного монитора. Ответ дайте в килобайтах.
12. Определите объём видеопамяти, необходимый для хранения изображения 1024х768 пикселей с палитрой 16 777 216 цветов.
13. Чёрно-белый графический файл (без градаций серого цвета) имеет размер 100х100 пикселей. Определите его информационный объём.
14. Страница видеопамяти составляет 16 000 байт. Дисплей работает в режиме 320х400 пикселей. Сколько цветов в данной палитре?
15. Чёрно-белый графический файл с 32 градациями серого цвета имеет размер 64х32 пикселя. Какое максимально возможное число таких файлов можно записать на флеш-носитель ёмкостью 1024 Кбайта?
Что такое посимвольное кодирование
1. Пользуясь таблицей кодировки ASCII и CP-1251 закодируйте следующие послания:
2. В некоторой кодировке для хранения одного символа отводится 2 байта. Определите вес слова из двадцати двух символов в данной кодировке.
3. В кодировке КОИ-8 для хранения одного символа отводится 1 байт. Определите вес (в битах) слова «дезоксирибонуклеиновая».
4. Некоторый текст записан в различных кодировках. Известно, что текс в 16-битной кодировке Unicode, на 120 бит больше текста, закодированного 8-битной кодировкой CP-1251. Определите количество символов в тексте.
5. В кодировке Unicode для хранения одного символа отводится 16 бит. Дан отрывок текста, записанного в данной кодировке:
«Калининград, Ярославль, Владимир, Елабуга, Троицк, Томск, Омск, Уфа – города России».
В результате редактирования текста, одно слово и ставшие лишними пробелы и запятые удалили. Новый текст стал на 14 байт меньше. Определите удалённое слово.
6. Текст, напечатанные на компьютере занял несколько страниц. Каждая страница текста состоит из 60 строк по 30 символов в строке. Файл с данным текстом занимает в компьютере 225 Кбайт. Сколько страниц содержит данный текст, если известно, что он закодирован в Unicode.
7. В кодировке Windows-1251 каждый символ кодируется 8 бит. Вова хотел написать текст (в нём нет лишних пробелов):
«Скользя по утреннему снегу,
Друг милый, предадимся бегу
И навестим поля пустые…»
Одно из слов ученик написал два раза подряд через пробел. При этом размер написанного предложения в данной кодировке оказался на 10 байт больше, чем размер нужного предложения. Напишите в ответе лишнее слово.
9. В кодировке КОИ-8 каждый символ кодируется 8 бит. Вова хотел написать текст (в нём нет лишних пробелов):
«Скользя по утреннему снегу,
друг милый, предадимся бегу
нетерпеливого коня и навестим поля пустые…»
Одно из слов ученик написал два раза подряд через пробел. При этом размер написанного предложения в данной кодировке оказался на 14 байт больше, чем размер нужного предложения. Напишите в ответе лишнее слово.
10. Растровое изображение размером 512х720 пикселей занимает 90 Кбайт памяти. Определите количество цветов в палитре, с помощью которой было закодировано данное изображение.
11. Монитор поддерживает 16-цветовую палитру и вмещает изображение размером 480х640 пикселей. Определите объём видео памяти, необходимый для хранение полноформатного изображения исходя из особенностей данного монитора. Ответ дайте в килобайтах.
12. Определите объём видеопамяти, необходимый для хранения изображения 1024х768 пикселей с палитрой 16 777 216 цветов.
13. Чёрно-белый графический файл (без градаций серого цвета) имеет размер 100х100 пикселей. Определите его информационный объём.
14. Страница видеопамяти составляет 16 000 байт. Дисплей работает в режиме 320х400 пикселей. Сколько цветов в данной палитре?
15. Чёрно-белый графический файл с 32 градациями серого цвета имеет размер 64х32 пикселя. Какое максимально возможное число таких файлов можно записать на флеш-носитель ёмкостью 1024 Кбайта?
Теория кодирования. Кодирование источника. Посимвольное кодирование
Теория кодирования изучает свойства различных кодов и их применимость в конкретных задачах.
В рамках теории кодирования, кодом называется некое правило (алгоритм), которое однозначно ставит неким словам над исходным алфавитом некие новые кодовые слова, возможно над другим, целевым, алфавитом.
Код Пусть \(S\) и \(T\) – конечные множества, называемые соответственно исходным и целевым алфавитами. Код \(C: S^* \to T^*\) есть всюду определённая функция, отображающая элементы \(S^*\) – слова (последовательностей символов) над исходным алфавитом – на элементы множества \(T^*\) – слова над целевым алфавитом.
В соответствии с исследуемыми задачами, выделяют четыре различных направления в теории кодирования:
Сжатие данных
Сжатие данных в общем случае – это представление информации в меньшем информационном объёме, чем исходные данные. Выделяют сжатие данных без потерь (lossless) и сжатие данных с потерями (lossy).
Сжатие данных без потерь позволяет в точности восстановить исходный сигнал. Сжатие данных с потерями позволяет восстановить некую “достаточно хорошую” аппроксимацию исходного сигнала.
Модель сжатия без потерь:
В качестве меры “успешности” сжатия без потерь вводится коэффициент сжатия: \[r = \frac
Модель сжатия с потерями:
Кроме требования однозначности, как правило, требуется так же обеспечить возможность каким-то образом разделять кодовые слова, соответствующие различным исходным сообщениям. Для достижения этого могут использоваться следующие подходы:
Определение энтропии так же даёт нам некоторые указания касательно свойств оптимального кода, исходя из того, что энтропия кодированного сигнала должна быть максимальна (т.е. количество информации на символ кода – максимально):
Наиболее экономным для большинства применений оказывается использование префиксных кодов.
Предел оптимального кодирования без потерь нам даёт теорема Шеннона о кодировании источника: средняя (в смысле теории вероятностей) длина кодового слова не может быть меньше энтропии источника.
Основные методы посимвольного кодирования
Посимвольное кодирование, или кодирование без памяти, является простейшим методом кодирования.
Понятно, что, по крайней мере в случае кодирования без потерь, код должен быть однозначно декодируемым.
Мы так же хотим, чтобы средний (ожидаемый) информационный объем кода был минимальный.
Ожидаемая длина кодового слова (средняя длина кода) Математическое ожидание длины кодового слова из кода \(C\) над источником \(X\) обозначается \(L(C, X)\) и называется ожидаемой (средней) длиной кодового слова: \[L(C,X) = \sum_
Необходимое и достаточное условие существования однозначно декодируемых префиксных кодов (и вообще однозначно декодируемых кодов переменной длины) устанавливается неравенством Крафта-МакМиллана:
Теорема (неравенство Крафта-МакМиллана) Пусть каждый символ исходного алфавита \(S=\
Пусть \(S = \sum_i r^<-l_i>.\) Рассмотрим число \[S^N = \sum_
l_i,\) \(l_
Теорема Шеннона о кодировании источника ограничивает снизу максимально достижимое сжатие энтропией источника. Сохраняется ли это ограничение при посимвольном кодировании? Вообще говоря, ответ может быть неочевиден. Поэтому, найдём нижнюю границу ожидаемой длины кода \(L(C, X).\) Сперва докажем неравенство Гиббса.
Для упрощения выкладок, без ограничения общности, положим двоичный целевой алфавит. Упрощение достигается за счёт того, что информационный объем кодового слова в битах в таком случае численно совпадает с его длиной.
Это важный результат, поэтому повторимся.
Верно так же и обратное: любой выбор длин кодовых слов неявно определяет оптимальный источник.
Оптимальный источник для посимвольного кодера \(C\)
Определяется распределением вероятностей \[P(x) = \frac<2^<-|C(x)|>> <\sum_
Мы установили нижнюю границу. Но насколько близко к ней можно подойти? Оказывается, в пределах одного бита.
\(\Delta\) : Первое неравенство \(L(C,X) \ge H(X)\) уже доказано выше.
Алгоритм Хаффмана
Один из способов построить оптимальный посимвольный код – алгоритм Хаффмана.
Более подробное описание доступно здесь
Код, составленный по алгоритму Хаффмана, оптимален.
Тогда, поскольку \(X’\) отличается от \(X\) тем, что два символа из \(X\) в нём отождествляются, а отождествлённый символ в наших кодах имеет кодовое слово на 1 бит короче, имеем \[L = L’ + P(x’),\] \[\hat L = \hat L’ + P(x’).\]
По индукции, код Хаффмана для любого алфавита размерности \(|X|\ge 2\) оптимален.
Другие алгоритмы посимвольного кодирования
Код Шеннона
Код Шеннона использовался Шенноном при доказательстве теоремы о кодировании источника, однако он не является оптимальным, и никогда не лучше (но иногда эквивалентен) коду Шеннона-Фано.
Код Шеннона-Фано
Все символы алфавита источника упорядочиваются по убыванию вероятности. Полученный массив делится на две непрерывные части, максимально близкие по сумме вероятностей входящих в них символов. Одной из этих частей присваивается метка “0”, второй – метка “1”. Алгоритм рекурсивно повторяется для каждой из частей, пока не дойдёт до единственного символа. Кодом этого символа является последовательность меток частей.
Следует отметить, что подход похож на подход Хаффмана, однако алгоритм Хаффмана строит дерево “снизу вверх”, от листьев, в то время как алгоритм Шеннона-Фано строит дерево “сверху вниз”, от корня.
Код Элиаса (Шеннона-Фано-Элиаса)
Так же известен как код Гильберта-Мура 1
Каждому символу ставится в соответствие число \[F_i = \frac
Gilbert E. N., Moore E. F. Variable‐Length Binary Encodings //Bell System Technical Journal. – 1959. – Т. 38. – №. 4. – С. 933-967.↩︎
Эффективное посимвольное кодирование для сжатия данных.
Основные моменты сводятся к следующему:
— согласно теореме Шеннона, наилучшее кодирование позволяет сократить lср. до величены энтропии Н, подсчитанной для данного набора символов;
— неравномерное кодирование позволяет автоматически устранить избыточность, связанную с тем, что количество символов в алфавите может быть не кратно степени двойки (так, например, чтобы закодировать одинаковым числом разрядов 5 разновидностей символов потребуется 3 бита, так же как и для 8 символов).
Идея неравномерного кодирования, в котором длина кодовой цепочки зависит от частоты появления соответствующего символа, реализована еще в знаменитой «азбуке Морзе». Однако там наряду с «точками» и «тире» использовался третий кодовый символ – разделитель «пауза». Если ограничиться только «O» и «1», то при построении кода необходимо учесть дополнительное требование: чтобы все кодовые цепочки однозначно выделялись в непрерывном потоке битов, ни одна из них не должна входить как начальный участок в кодовую, цепочку другого символа. Такое свойство кода называется префиксностью.
Наибольшее распространение получил способ построения эффективного кода предположенный Хаффменом. Рассмотрим его на примере. Пусть задан алфавит из 5 разновидностей символов Z1 – Z5, и их вероятности. В таблице 5.1 наряду с этими исходными данными приведены так же результаты кодирования по Хаффмену: кодовые цепочки Ki их длинны li. Процедуру построения кода иллюстрирует таблица и рисунок 1
Пример кода Хаффмена
| Zi | Pi | Ki | li |
| Z1 Z2 Z3 Z4 Z5 | 0,25 0,17 0,08 0,35 0,15 | ||
 | lср |
Таблица 2 Объединение вероятностей символов
| Zi | Pi | Шаги объединения | Ki | ||
| Z1 Z2 Z3 Z4 Z5 | 0,35 0,25 0,17 0,15 0,08 | 0,35 0,25 0,23 0,17 | 0,40 0,35 0,25 | 0,60 0,40 | 1,00 |
Процедура кодирования сводится к выбору из кодовой таблицы цепочек, соответствующих каждому символу источника. Декодирование предусматривает выделение в битовом потоке кодов символов и их расшифровку в соответствии с таблицей.
Код Хаффмена может быть двухпроходным и однопроходным. Первый строится по результатам подсчета частот (вероятностей) появления различных символов в данном сообщении. Второй использует готовую таблицу кодирования, построенную на основе вероятностей символов в сообщениях похожего типа. Например, кодирование текста на русском языке в первом случае включает его предварительный анализ, подсчет вероятностей символов, построение дерева кода и таблицы кодирования индивидуально для данного сообщения. Во втором случае будет работать готовая таблица, построенная по результатам анализа множества русскоязычных текстов. Двухпроходный код более полно использует возможности сжатия. Однако, при этом вместе с сообщением нужно передавать и кодовую таблицу. Однопроходный код не оптимален, однако прост в использовании, поэтому на практике обычно применяют именно его.
В целом код Хаффмена проигрывает по сравнению с «цепочечными» кодами и его редко используют самостоятельно, однако он часто фигурирует как элемент более сложных алгоритмов сжатия.
Дата добавления: 2015-09-18 ; просмотров: 1394 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ
Кодирование для чайников, ч.1
Не являясь специалистом в обозначенной области я, тем не менее, прочитал много специализированной литературы для знакомства с предметом и прорываясь через тернии к звёздам набил, на начальных этапах, немало шишек. При всём изобилии информации мне не удалось найти простые статьи о кодировании как таковом, вне рамок специальной литературы (так сказать без формул и с картинками).
Статья, в первой части, является ликбезом по кодированию как таковому с примерами манипуляций с битовыми кодами, а во второй я бы хотел затронуть простейшие способы кодирования изображений.
0. Начало
Давайте рассмотрим некоторые более подробно.
1.1 Речь, мимика, жесты
1.2 Чередующиеся сигналы
В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы «включено/выключено». Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.
1.3 Контекст
2. Кодирование текста
Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт (в значении ноль) равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.
Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.
Тестовая фраза «ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП».
2.1 Блочное кодирование
Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа: