1.2.2. Кодирование данных в двоичном алфавите
Справочные материалы
Выше мы рассмотрели примеры двоичного кодирования чисел, букв, цвета. Однако, поскольку любая информация, представленная в компьютере, имеет двоичную природу, очень часто возникает необходимость сопоставить двоичные коды и другим видам информации.
При кодировании информация записывается с помощью символов. Например, обычный текст – информация, закодированная с помощью набора символов, например русского алфавита. Набор символов, используемый для кодирования данных, называется алфавитом. Число символов в алфавите называется мощностью алфавита. Последовательность символов в алфавите называется словом.
Если есть два различных алфавита и задано правило преобразования слов из одного алфавита в слова другого алфавита, то такое процесс преобразование называется кодированием.
Наиболее распространенным является двоичный алфавит кодирования, состоящий из 2-х символов 0 и 1. Им кодируется вся информация в компьютере.
В общем виде задача кодирования ставится так: «Имеется некоторый набор значений (набор данных). Надо сопоставить каждому значению двоичный код, удовлетворяющий следующим требованиям:
· Во-первых, все коды должны быть одинаковой длины – состоять из одинакового количества бит. Это необходимо для вычисления объема кодируемой информации и правильного распознавания кода.
· Во-вторых, длина двоичного кода должна быть минимальной необходимой для кодирования всех значений из набора.
Минимальное количество бит, необходимое для кодирования N элементов набора определяется из следующего неравенства
2K-1 < N ≤ 2K, (5)
где К – количество бит, необходимых для кодирования.
Из неравенства видно, чтобы определить число бит, надо найти степень 2, большую или равную N, но самую близкую к этому числу.
Другая (обратная) постановка задач, связанных с кодированием набора данных, звучит так: «Какое максимальное количество двоичных кодов можно составить из К бит». Ответ выражается формулой
N = 2K. (6)
Анализ задач из демонстрационных вариантов ЕГЭ
Е1.1. (2004, А3) Шахматная доска состоит из 64 полей: 8 столбцов на 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?
1) | 4 | 2) | 5 | 3) | 6 | 4) | 7 |
Е1.2. (2005, А2) Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?
1) | 64 | 2) | 50 | 3) | 32 | 4) | 20 |
Е1.3. (2005, А3) Обычный дорожный светофор без дополнительных секций подает шесть видов сигналов (непрерывные красный, желтый и зеленый, мигающие желтый и зеленый, красный и желтый одновременно). Электронное устройство управления светофором последовательно воспроизводит записанные сигналы. Подряд записано 100 сигналов светофора. В байтах данный информационный объем составляет
1) | 37 | 2) | 38 | 3) | 50 | 4) | 100 |
Е1.4. (2006, А2) Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
1) | 80 | 2) | 120 | 3) | 112 | 4) | 96 |
Е1.5. (2007, А2) Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 50 различных сигналов?
1) | 5 | 2) | 6 | 3) | 25 | 4) | 50 |
Е1.6. (2007, А3) Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.
1) | 80 бит | 2) | 70 байт | 3) | 80 байт | 4) | 560 байт |
Е1.7. (2008, А3) Для передачи секретного сообщения используется код, состоящий из десятичных цифр. При этом все цифры кодируются одним и тем же (минимально возможным) количеством бит. Определите информационный объем сообщения длиной в 150 символов.
1) | 600 бит | 2) | 750 бит | 3) | 1200 бит | 4) | 60 байт |
Е1.8. (2009, А2) В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?
1) | 70 бит | 2) | 70 байт | 3) | 490 бит | 4) | 119 байт |
Е1.9. (2010, A2) В некоторой стране автомобильный номер состоит из 7 символов. В качестве символов используют 18 различных букв и десятичные цифры в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объем памяти, отводимый этой программой для записи 60 номеров.
1) 240 байт
2) 300 байт
3) 360 байт
4) 420 байт
Из анализа демонстрационных заданий можно сделать вывод, что задачи, связанные с кодированием набора данных, включаются в ЕГЭ по информатике каждый год. Наиболее простыми являются задачи на определение количества двоичных кодов одинаковой длины, которые предлагались в 2005 (А2) и 2006 (А2) году. Большинство задач связаны с определением минимального количества бит, необходимых для кодирования набора данных, и дальнейшим подсчетом информационного объема некоторого сообщения. Основная сложность этих задач заключается в том, что они имеют большое разнообразие конкретных постановок. Это связано с тем, что кодирование может потребоваться практически для любых наборов данных. Главное в этих задачах правильно определить набор данных, подлежащий кодированию.
Примеры типовых задач
П1.1. Для передачи сигналов используют последовательности из знаков «+» и «–» длиной по 6 символов. Сколько различных сигналов можно закодировать с их помощью? Выберите правильный ответ.
1) | 3 | 2) | 8 | 3) | 64 | 4) | 256 |
Решение
1. Прежде всего, отметим, что так как для кодирования используются всего 2 знака, то мы имеем место с двоичным кодированием, а последовательности, состоящие из знаков «+» и «–» аналогичны двоичным кодам из нулей и единиц. Таким образом один символ в таком коде тоже можно считать битом.
2. Определим, сколько различных двоичных кодов длиной 6 бит можно составить. Для этого используем формулу N = 2K, где К=6. Следовательно, N = 64.
Поясним на этом примере, почему из 6 бит можно составить 64 различных комбинации двоичных кодов. Самое большое двоичное число из 6 бит – это 1111112. Если перевести это число в десятичный код получится число
1×26 + 1×25 +1×24 + 1×23 + 1×22 + 1×21 + 1×20 = 6310
На первый взгляд может показаться, что из 6 бит можно составить 63 различных двоичных кода, начиная от кода, соответствующего 110 = 0 и заканчивая кодом, соответствующим 6310 = 1111112. Но нельзя забывать, что есть еще один двоичный код из 6 бит – это число 0000002. Таким образом всего можно составить 64 различных кода.
Ответ: 3 (3-й вариант из предложенных).
П1.2. Для учета каждому школьнику присваивается двоичный код одинаковой длины. Достаточно ли 9 бит для кодирования все учеников школы, если в школе учится 1000 человек? Вычислите разность между максимально возможным количеством двоичных кодов из 9 бит и числом школьников. Выберите правильный ответ.
1) | –24 | 2) | 512 | 3) | –448 | 4) | 448 |
Решение
1. Определим, сколько различных двоичных кодов длиной 9 бит можно составить. Для этого используем формулу N = 2K, где К=9. Следовательно, N = 512. Получили, что можно составить 512 двоичных кодов длиной 9 бит. Очевидно, что этого количества не хватит для кодирования всех 1000 учеников школы. Выберите правильный ответ.
2. Согласно условию задачи находим разность между количеством двоичных кодов и количеством учеников 512 – 1000 = –448.
Ответ: 3 (3-й вариант из предложенных).
П1.3. Для высвечивания цифры в электронных часах, используется прямоугольное световое табло из 7 продолговатых лампочек, которые расположены на нем подобно цифре 8, сложенной из спичек. Каждая лампочка может находиться в состоянии «включено» или «выключено». Какое количество комбинаций из включенных и выключенных лампочек являются лишними? Выберите правильный ответ.
1) | 3 | 2) | 56 | 3) | 104 | 4) | 118 |
Решение
1. Прежде всего, отметим, что поскольку лампочки на табло могут находиться только в двух состояниях, то мы имеем место с двоичным кодированием, а комбинации включенных и выключенных лампочек аналогичны двоичным кодам из нулей и единиц. Таким образом, одна лампочка на табло является аналогом 1-го бита.
2. Не обязательно представлять, как из 7 спичек можно сложить цифру 8, хотя действительно такие электронные табло встречаются довольно часто, не только в часах, но и в других электронных приборах.
3. Из 7 лампочек можно составить 27 = 128 различных световых сигналов. А для высвечивания цифры надо только 10 световых сигналов.
4. Следовательно, незадействованными окажутся 128 – 10 = 118 световых сигналов.
Ответ: 4 (4-й вариант из предложенных).
П1.4. Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях ("включено", "выключено"). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 20 различных сигналов? Выберите правильный ответ.
1) | 5 | 2) | 8 | 3) | 20 | 4) | 32 |
Решение
1. Так же как и в предыдущей задаче можно считать световые сигналы табло двоичными кодами. Однако по постановке эта задача является обратной предыдущей.
2. Чтобы определить, сколько минимально требуется лампочек для кодирования 20 сигналов, найдем степень 2, ближайшую к 20, но большую. Это 25 = 32. Следовательно, для кодирования 20 сигналов понадобится 5 лампочек.
Ответ: 1 (1-й вариант из предложенных).
П1.5. На магнитную карту для прохода через турникет в метро наносится закодированные в двоичном коде следующие данные: дата приобретения карты, количество поездок и номер тарифного плана, который отражает особенности использования карты. В дате кодируются отдельно число, месяц и две последние цифры года. В метро используются 8 различных тарифных планов. На карту может быть занесено не более 60 поездок. Каждый информационный элемент кодируется минимально необходимым количеством бит. Вычислите в битах информационный объем данных, закодированных на магнитной карте. Выберите правильный ответ.
1) | 213 | 2) | 256 | 3) | 25 | 4) | 8 |
Решение
1. Определим количество бит, необходимых для кодирования каждого элемента данных – дня месяца, месяца, года, тарифного плана и количества поездок. В месяце максимально может быть 31 число.
2. Выбираем степень 2, большую чем 31, но ближайшую к этому числу – это 32=25. Поэтому для кодирования, поэтому для кодирования порядковых чисел месяца необходимо 5 бит.
3. Аналогично определяем количество бит, необходимых для кодирования других элементов данных. Ниже в таблице приведено количество значений и количество бит.
Элемент данных | Число значений, подлежащих кодированию | Степень 2, ближайшая к числу значений, но большая | Число бит, необходимых для кодирования |
День месяца | 31 | 32=25 | 5 |
Месяц | 12 | 16=24 | 4 |
Год (две последние цифры) | 100 (от 0 до 99) | 128=27 | 7 |
Тарифный план | 8 | 8=23 | 3 |
Количество поездок | 60 | 64=26 | 6 |
Общее количество бит | 25 |
Примечание. В этой задаче нельзя сложить все возможные значения, а потом определить общее минимальное количество бит, необходимых для кодирования, т. к. для распознавания кода необходимо четко знать, сколько бит занимает каждый отдельный элемент данных. Так, если в этой задаче сосчитать общее количество значений, подлежащих кодированию, то получится 213. Для кодирования 213-ти значений достаточно 8 бит, но полученные таким образом коды не позволят выделить отдельные элементы данных.
4. В нижней строке таблицы подсчитано информационный объем данных на магнитной карте – 25 бит.
Ответ: 3 (3-й вариант из предложенных).
П1.6. Для сдачи ЕГЭ по информатике формируются группы из 30 человек или менее. Каждому участнику экзамена присваивается двоичный код. На экзамене каждый участник может набрать максимально 40 баллов. В файл электронной экзаменационной ведомости вносятся результаты экзамена: двоичный код участника и двоичный код числа набранных балов. Определите информационный объем файла, если на экзамен пришло 16 человек. Выберите правильный ответ.
1) | 11 | 2) | 176 | 3) | 330 | 4) | 112 |
Решение
1. Поскольку в группе может быть не более 30 человек, то для кодирования каждого участника понадобится 5 бит, т. к. 25=32 – ближайшая к 30 степень 2. Таким образом сколько бы ни пришло человек на экзамен, все равно каждому будет присваиваться 5-ти битный код.
2. Определяем количество бит, необходимых для кодирования набранных баллов. Всего можно набрать 40 баллов. Ближайшая, но большая 40 степень 2 это 26=64. Следовательно, для кодирования набранных балов будем использовать 6-ти битный код.
3. Данные одного участника в электронной ведомости занимают 5+6=11 бит.
4. Всего пришло на экзамен 16 человек, поэтому в ведомость было внесено 11 * 16 = 176 бит.
Ответ: 2 (2-й вариант из предложенных).
П1.7. В чемпионате России по футболу в высшей лиге участвует 16 команд. Каждая команда в течение сезона играет с каждой командой 2 раза – один раз на своем поле и 1 раз на поле соперника. В файл вносятся результаты матча – дата (день и месяц кодируются отдельно, год не кодируется), двоичные коды команд участников и коды числа забитых командами голов, на которые отводится по 1 байту для результата каждой команды. Для простоты кодирования месяцев будем считать, что футбольный сезон длится все 12 месяцев (хотя фактически это не так). Каков информационный объем файла в байтах после того как прошло пол сезона – сыграна половина всех матчей. Выберите правильный ответ.
1) | 495 | 2) | 512 | 3) | 7920 | 4) | 3960 |
Решение
1. Определим минимальное количество бит, необходимых для кодирования команды. Так как команд 16, то находим степень 2, ближайшую к 16 (или равную). Это будет число 16=24. Следовательно, для кодирования команды надо 4 бита.
2. Определяем количество бит, необходимых для кодирования даты (см. таблицу).
Элемент данных | Число значений, подлежащих кодированию | Степень 2, ближайшая к числу значений, но большая | Число бит, необходимых для кодирования |
День месяца | 31 | 32=25 | 5 |
Месяц | 12 | 16=24 | 4 |
3. Определяем сколько бит содержит запись результатов одного матч. Для кодирования голов отводит по 1 байту для каждой команды, т. е. по 8 бит. Всего надо сложить
· 5 бит (код дня месяца);
· 4 бита (код месяца);
· 4 бита (код одной команды);
· 4 бита (код другой команды);
· 8 бит (код числа голов одной команды);
· 8 бит (код числа голов другой команды).
Таким образом, одна запись занимает 33 бита.
4. Определяем, сколько матчей всего играют команды в сезоне. Удобно приставить сетку матчей, как это обычно делается.
К1 | К2 | … | К16 | |
К1 | ||||
К2 | ||||
… | ||||
К16 |
В нижней части таблицы указываются матчи 1-й половины сезона, в верхней части матчи второй половины сезона. Серым цветом выделены клетки, которые не заполняются, т. к. команда сама с собой не играет.
В таблице 16 столбцов и 16 строк с результатами матчей за вычетом закрашенных ячеек – их тоже 16.
Таким образом всего матчей за сезон 16 * 16 – 16 = 256 – 16 = 240.
За половину сезона играется 120 матчей.
5. Информационный объем файла с результатами после 120 сыгранных матчей равен 120 * 33 (бита). Для перевода в байты надо это число разделить на* 33 / 8 = 15 * 33 = 495 байт.
Ответ: 2 (2-й вариант из предложенных).
Задачи для самостоятельного решения
С1.1. Будем считать, что предприятие производит 16 видов мороженого. Какое наименьшее количество бит достаточно для двоичного кодирования видов мороженого? Выберите правильный ответ.
1) | 2 | 2) | 4 | 3) | 8 | 4) | 256 |
С1.2. В английском алфавите 26 букв. Слова кодируются только строчными буквами. Какое минимальное количество бит (двоичных разрядов) потребуется для кодирования одной буквы? Выберите правильный ответ.
1) | 16 | 2) | 32 | 3) | 5 | 4) | 6 |
С1.3. Будем считать, что в магазине продается 14 наименований товаров.
Какое наименьшее количество бит достаточно для двоичного кодирования наименований товаров в магазине? Выберите правильный ответ.
1) | 14 | 2) | 4 | 3) | 8 | 4) | 24 |
С1.4. С учетом того, что некоторые страны не имеют собственной валюты, будем считать, что в мире существует около 200 валют. Какое наименьшее количество бит достаточно для двоичного кодирования валют государств? Выберите правильный ответ.
1) | 25 | 2) | 16 | 3) | 8 | 4) | 4 |
С1.5. Для кодирования символов в ASCII-кодировке используется 1 байт. Сколько символов (мощность алфавита) можно закодировать 1 байтом? Выберите правильный ответ.
1) | 8 | 2) | 16 | 3) | 32 | 4) | 256 |
С1.6. Некоторый алфавит состоит только из следующих символов: {а, е, и, й, ы, о, у, э, ю, я}. Какое минимальное количество бит потребуется для кодирования одного символа? Выберите правильный ответ.
1) | 3 | 2) | 4 | 3) | 5 | 4) | 10 |
С1.7. Какое минимальное количество бит (двоичных разрядов) потребуется для кодирования 4-х арифметических операций: сложения, вычитания, умножения, деления? Выберите правильный ответ.
1) | 1 | 2) | 2 | 3) | 4 | 4) | 8 |
С1.8. Определите информационный объем сообщения в битах, если сообщение состоит из 98 символов и мощность алфавита (количество символов в алфавите) равна 28 . Выберите правильный ответ.
1) | 392 | 2) | 490 | 3) | 784 | 4) | 2744 |
С1.9. Сколько символов содержит сообщение, записанное с помощью 16-тисимвольного алфавита, если его информационный объем составил 1/16 Кбайта. Выберите правильный ответ.
1) | 32 | 2) | 64 | 3) | 128 | 4) | 256 |
С1.10. Информационный объем сообщения, содержащего 512 символов, составляет 0,5 Кбайта. Найти мощность алфавита, с помощью которого записано сообщение. Выберите правильный ответ.
1) | 32 | 2) | 64 | 3) | 128 | 4) | 256 |
С1.11. Для кодирования информации использовали только русские строчные буквы. Какой информационный объем в байтах будет иметь сообщение, состоящее из 16 символов? Выберите правильный ответ.
1) | 12 | 2) | 16 | 3) | 80 | 4) | 96 |
С1.12. В школе 30 классов. В каждом классе не более 30 учеников. Для кодирования каждого ученика используется код класса и код порядкового номера ученика в электронном журнале. Какое минимальное количество двоичных разрядов необходимо выделить для кодирования каждого ученика? Выберите правильный ответ.
1) | 11 | 2) | 10 | 3) | 9 | 4) | 900 |
С1.13. Для общения племя мумбо-юмбо использует язык, содержащий 24 основных понятий и 3 связки(ок), которые позволяют соединить эти понятия. Сообщения передаются с помощью ударов барабана порциями: понятие + связка. Все понятия кодируются одинаковым числом ударов и связки кодируются одинаковым числом ударов. Сколько ударов барабана используется в каждой порции сообщений?
С1.14. Для общения в языке племени мумбо-юмбо используется 13 основных понятий и 4 связки, позволяющих соединять эти понятия. Для передачи сообщений племя использует двоичный код: сочетание звонких и глухих звуков барабана. Сообщения передаются порциями — понятие + связка. Сколько ударов потребуется для кодирования каждой порции сообщения?
1) | 6 | 2) | 4 | 3) | 8 | 4) | 2 |
С1.15. мальчик, чтобы безошибочно определять, кто звонит в дверь, предложил своим друзьям использовать сочетания из длинных и коротких звонков по 3. Он раздал всем друзьям индивидуальные комбинации, и у него осталось еще 2 комбинации для родителей. Сколько друзей у мальчика?
1) | 4 | 2) | 6 | 3) | 8 | 4) | 2 |
