Кодирование информации

А2, В1: Тема: Вычисление информационного объема сообщения.

Для решения задач по данной теме необходимо знать следующие теоретические сведения:

1. С помощью K бит можно закодировать различных вариантов (чисел);

2. Таблица степеней двойки, она же показывает, сколько вариантов Q можно закодировать с помощью K бит:

К, бит                   1  2  3   4    5    6    7      8      9       10

N, вариантов       2  4  8  16  32  64  128  256  512   1024

3. При измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) - 1024 байта, в мегабайте (1 Мбайт) - 1024 Кбайта;

4. Чтобы найти информационный объем сообщения (текста) I, нужно умножить количество символов (отсчетов) N на число бит на символ (отсчет) K: ;

5. Две строчки текста не могут занимать 100 Кбайт в памяти;

6. Мощность алфавита M - это количество символов в этом алфавите;

7. Если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно ; для двоичного кодирования (мощность алфавита M - 2 символа) получаем известную формулу.

Пример задания.

В мотокроссе участвуют 238 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 140 мотоциклистов (Вовк Е.Т. 2012)?

1) 140 бит 2) 140 байт 3) 1120 бит 4) 238 байт

Решение:

1. Мотоциклистов было 238, у них 238 разных номеров, то есть, нам нужно закодировать 238 вариантов;

2. По таблице степеней двойки находим, что для этого нужно минимум 8 бит (при этом можно закодировать 256 вариантов, то есть, еще есть запас); итак, 8 бит на один отсчет;

3. Когда 140 мотоциклистов прошли промежуточный финиш, в память устройства записано 140 отсчетов;

4. Поэтому в сообщении 140*8 = 1120 бит информации (ответ 3).

При выборе правильного варианта ответа, необходимо обратить внимание на следующее:

1. Дано число, которое есть в условии (неверные ответы 140 бит, 140 байт, 238 байт), чтобы сбить случайное угадывание;

2. Указано правильное число, но другие единицы измерения (мог быть вариант 1120 байт);

3. Расчет на невнимательное чтение условия: можно не заметить, что требуется определить объем только 140 отсчетов, а не всех 238 (мог быть вариант 238 * 8 = 1904 бита).

Пример задания.

Каждая ячейка памяти компьютера, работающего в пятеричной системе счисления, может принимать 5 различных значений (-2, -1, 0, 1, 2). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

Решение:

1) Непривычность этой задачи состоит в том, что используется пятеричная система;

2) Фактически мы имеем дело с языком, алфавит которого содержит M = 5 различных символа;

3) Поэтому количество всех возможных «слов» длиной N равно;

4) Для N = 4 получаем;

5) Таким образом, правильный ответ - 625.

При решении данного задания необходимо обратить внимание на то, что, если не осознать, что используется пятеричная (а не двоичная!) система, можно «по инерции» получить неправильный ответ.

А3: Тема: Кодирование текстовой информации. Кодировка ASCII. Основные кодировки кириллицы.

Для решения задач по данной теме необходимо знать следующие теоретические сведения (Антонов Ю.С., Николаева Н.В., Павлов Е.Е., Павлов Н.Н. 2005):

1. Все символы кодируются одинаковым числом бит (алфавитный подход);

2. Чаще всего используют кодировки, в которых на символ отводится 8 бит (8-битные) или 16 бит (16-битные);

3. При измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) - 1024 байта, в мегабайте (1 Мбайт) - 1024 Кбайта;

4. После знака препинания внутри текста ставится пробел;

5. Чтобы найти информационный объем текста I, нужно умножить количество символов N на число бит на символ K;

6. Две строчки текста не могут занимать 100 Кбайт в памяти.

Пример задания.

Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 960 бит. Какова длина сообщения в символах?

1) 60 2) 120 3) 240 4) 960.

Решение:

1) Обозначим количество символов через N;

2) При 16-битной кодировке объем сообщения - 16*N бит;

3) Когда его перекодировали в 8-битный код, его объем стал равен - 8*N бит;

4) Таким образом, сообщение уменьшилось на 16*N - 8*N = 8*N = 960 бит;

5) Отсюда находим N = 960/8 = 120 символов (ответ 2).

Пример задания.

Определите информационный объем текста:

Учиться! Учиться! Учиться!

1) 52 бита 2) 192 бита 3) 208 бит 4) 26 бит

Решение:

1) В этом тексте 26 символов (обязательно считать пробелы и знаки препинания);

2) Если нет дополнительной информации, считаем, что используется 8-битная кодировка (чаще всего явно указано, что кодировка 8- или 16-битная);

3) Поэтому в сообщении 26*8 = 208 бит информации (ответ 3).

При выборе правильного варианта ответа необходимо обратить внимание на следующее:

1) Указано правильное число, но другие единицы измерения (объем текста 26 байт, а один из неверных ответов - 26 бит);

2) Расчет на то, что «забудут» пробел, в этом случае получается 24*8 = 192 бита (ответ 2, неверный);

3) В 16-битной кодировке объем текста - 52 байт, а один из неверных ответов - 52 бита.

А11: Тема: Кодирование и декодирование информации.

Для решения задач по данной теме необходимо знать следующие теоретические сведения:

1. Кодирование - это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите);

2. Обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием - обратный переход;

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

4. Кодирование может быть равномерное и неравномерное; при равномерном кодировании все символы кодируются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование.

Пример задания.

Для кодирования букв А, Б, В, Г, Д, Е, Ж, З решили использовать трёхразрядные последовательные двоичные числа (от 000 до 111, соответственно). Если таким способом закодировать последовательность символов БАВГЗЕЖД и записать результат шестнадцатеричным кодом, то получится

1) 213F7416 2) 213F7417 3) BACDHFGE 16 4) 47F31216

Решение:

1) Из условия коды букв такие: A - 000, Б - 001, В - 010, Г - 011, Д - 100, Е - 101,Ж - 110, З - 111, код равномерный;

2) Последовательность БАВГЗЕЖД кодируется так: 001 000 010 011 111 101 110 100 = 001000010011111101110100;

3) Разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F - получаем:

001000010011111101110100 = 0010 0001 0011 1111 0111 01002 =

= 213F7416

4) Правильный ответ - 1.

При решении данного задания необходимо обратить внимание на следующее (Т.Е. Чуркина 2011):

1) Расчет на то, что при переводе тетрадь в шестнадцатеричную систему можно забыть заменить большие числа (10 - 15) на буквы (11112 = 15, получаем неверный ответ 213F7416);

2) Может быть дан неверный ответ, в котором нужные цифры поменяли местами (расчет на невнимательность), например, 47F31216;

3) В ответах дана последовательность, напоминающая исходную (неверный ответ BACDHFGE16), чтобы сбить случайное угадывание.

Пример задания.

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A = 0, Б = 10, В = 110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 1 2) 1110 3) 111 4) 11

Решение (вариант 1, метод подбора):

1) Рассмотрим все варианты в порядке увеличения длины кода буквы Г;

2) Начнем с Г = 1; при этом получается, что сообщение «10» может быть раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит;

3) Следующий по длине вариант - Г = 11; в этом случае сообщение «110» может быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит;

4) Третий вариант, Г = 111, дает однозначное раскодирование во всех сочетаниях букв, поэтому…

5) … правильный ответ - 3.

Сложность данного метода заключается в том, что при переборе можно ошибиться и «просмотреть» какой-нибудь вариант.

Решение (вариант 2, «умный» метод):

1) Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода; это условие называют условием Фано;

2) Как и в первом решении, рассматриваем варианты, начиная с самого короткого кода для буквы Г; в нашем случае код Г = 1 является началом кодов букв Б и В, поэтому условие Фано не выполняется, такой код не подходит;

3) Код Г = 11 также является началом другого кода (кода буквы В), поэтому это тоже ошибочный вариант;

4) Третий вариант кода, Г = 111, не является началом никакого уже известного кода; кроме того, ни один уже имеющийся код не является началом кода 111; таким образом, условие Фано выполняется;

5) Поэтому правильный ответ - 3.

Сложность данного метода заключается в том, что нужно знать условие Фано.

А15: Тема: Кодирование и обработка графической информации.

Для решения задач по данной теме необходимо знать следующие теоретические сведения:

1. Графическая информация может храниться в растровом и векторном форматах;

2. Векторное изображение - это набор геометрических фигур, которые можно описать математическими зависимостями;

3. Растровое изображение хранится в виде набора пикселей, для каждого из которых задается свой цвет, независимо от других;

4. Глубина цвета - это количество бит на пиксель (обычно от 1 до 24 бит на пиксель)

5. В режиме истинного цвета (True Color) информация о цвете каждого пикселя растрового изображения хранится в виде набора его RGB - составляющих (Red, Green, Blue); каждая из RGB-составляющих - целое число (яркость) в интервале [0,255] (всего 256 вариантов), занимающее в памяти 1 байт или 8 бит (так как 28 = 256); таким образом, на каждый пиксель отводится 3 байта = 24 бита памяти (глубина цвета - 24 бита); нулевое значение какой-то составляющей означает, что ее нет в этом цвете, значение 255 - максимальная яркость; в режиме истинного цвета можно закодировать 2563 = 224 = 16 777 216 различных цветов;

6. Палитра - это ограниченный набор цветов, которые используются в изображении (обычно не более 256); при кодировании с палитрой выбираются N любых цветов (из полного набора 16 777 216 цветов), для каждого из них определяется RGB - код и уникальный номер от 0 до N-1; тогда информация о цвете пикселя - это номер его цвета в палитре; при кодировании с палитрой количество бит на 1 пиксель (K) зависит от количества цветов в палитре N, они связаны формулой: ; объем памяти на все изображение вычисляется по формуле , где - число бит на пиксель, а - общее количество пикселей (Крылов С.С. 2011);

7. Полезно знать на память таблицу степеней двойки: она показывает, сколько вариантов N (а данном случае - сколько цветов) можно закодировать с помощью K бит:

К, бит                   1 2  3  4    5    6    7      8      9       10

N, вариантов       2  4  8  16  32  64  128  256  512   1024

8. Цвет на Web-страницах кодируется в виде RGB - кода в шестнадцатеричной системе: #RRGGBB, где RR, GG и BB - яркости красного, зеленого и синего, записанные в виде двух шестнадцатеричных цифр; это позволяет закодировать 256 значений от 0 (0016) до 255 (FF16) для каждой составляющей; коды некоторых цветов: