Материал для подготовки к ЕГЭ по темам "Кодирование" и "Измерение информации"

КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ

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

Двоичный код — это способ представления данных в виде кода, в котором каждый разряд принимает одно из двух возможных значений, обычно обозначаемых цифрами 0 и 1. 0 и 1 – это алфавит двоичной системы счисления. Основание двоичной системы счисления – q =2, т.к. в алфавит входят всего две цифры.

Для решения задач на двоичное кодирование необходимо:

1) уметь строить таблицу соответствия двоичных чисел десятичным, восьмеричным и шестнадцатеричным числам (знать алфавиты данных систем счисления и двоичную арифметику(8 класс))

2) уметь переводить из двоичной системы счисления в восьмеричную, шестнадцатеричную, десятичную и обратно (8 класс)

Примеры задач на кодирование:

1. Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

Алгоритм решения:

1) строим таблицу из того, что дано по условию задачи:

2) Вычисляем двоичное представление чисел 0, 1, 2, 3 и 4: для этого строим таблицу соответствия двоичной (с сохранением одного незначащего нуля в случае одноразрядного представления) и десятичной системы:

3) Записываем двоичные числа в таблицу:

4) Записываем двоичную последовательность для указанного слова ВОДОПАД = 01 00 10 00 11 100 10

5) Переводим полученное число двоичной системы счисления в указанную систему (в данном случае в восьмеричную):

ВОДОПАД = 010010001110010

Для этого делим СПРАВА налево полученное число на ТРИАДЫ (если переводим в шестнадцатеричную систему, то разделяем на ТЕТРАДЫ (группы по 4)): получится 010 010 001 110 010 и каждое полученное трехразрядное число переводим в восьмеричную систему счисления по уже созданной таблице (она включает числа от 0 до 7 – что совпадает с алфавитом восьмеричной системы счисления):

Ответ: 22162

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

1) 0001

2) 000

3) 11

4) 101

Алгоритм решения:

1) Находим среди вариантов двоичное число с наименьшим количеством разрядов, в данном случае это 11

2) Проверяем можно ли закодировать однозначно букву Г этим числом: А=1, поэтому, 11 можно принять как АА, таким образом это число не подходит

3) Находим следующее число после 11 с наименьшим количеством разрядов: 000 и 101.

4) Проверяем, можно ли закодировать букву Г данными числами: 101 можно принять как АБ, т.е. этот вариант не подходит. 000 – подходит.

Ответ: 2)000

ИЗМЕРЕНИЕ ИНФОРМАЦИИ.

ЕДИНИЦЫ ИЗМЕРЕНИЯ ИНФОРМАЦИИ

Основная единица измерения информации – бит.

Существует несколько подходов к измерению информации – алфавитный и содержательный. В алфавитном подходе речь идет об объеме информации. Количество символов в алфавите называется мощностью алфавита (N), а то, сколько «весит» один символ в битах – информационным весом символа (i). Чем больше символов в тексте, тем больше будет объем сообщения. Содержательный подход говорит не об объеме сообщения, а о количестве информации, которое человек может получить из него. В данном случае сообщение, уменьшающее неопределенность знания в два раза будет нести 1 бит информации. Если сообщение не несет нового знания и не убирает неопределенность, то оно несет в себе 0 бит, в независимости от того, сколько символов в данном сообщении.

Что нужно знать:

1) Единицы измерения информации и их перевод(8класс):

8 бит = 1 байт

1024 байта = 2¹⁰ байта = 1 Кбайт

1024 Кб = 2¹⁰ Кб = 1 Мб

1024 Мб = 2¹⁰ Мб = 1 Гб

1024 Гб = 2¹⁰ Гб = 1 Тб

2) Главную формулу информатики (7-9 класс):

N = 2ⁱ, где N – количество информации, i – количество бит на единицу информации.

3) Применение главной формулы информатики для алфавитного и содержательного подхода:

4)Целые степени двойки для вычисления i:

5) Формулу информационного объема сообщения:

I = K*i, где I – объем сообщения, K – количество символов в сообщении, i – количество бит на один символ сообщения.

Примеры задач:

1. B некоторой стране автомобильный номер длиной 6 символов составляют из заглавных букв (используются только 33 различных буквы) и десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов). Определите объём памяти, отводимый этой программой для записи 125 номеров. (Ответ дайте в байтах.)

Алгоритм решения:

1) находим N – в данном случае 33+10 = 43

2) находим i по формуле N = 2i: 25 (32)– мало, 26 (64) – достаточно, значит i = 6 бит (на один символ номера)

3) находим I номера (т.е. количество информации в одном номере): К = 6, i = 6, значит I = 36 бит (6 символов в номере – каждый по 6 бит)

4) Переводим в байты и округляем В БОЛЬШУЮ СТОРОНУ (ВСЕГДА!): 36/8 = 4,5 байта – не целое число, в большую сторону = 5 байт на 1 номер

5) Находим I для общего количества номеров: 125 номеров, каждый по 5 байт – 125*5 = 625 байт

Ответ: 625 байт

2. В скач­ках участвуют 20 лошадей. Спе­ци­аль­ное устройство регист­рирует про­хож­де­ние каждой ло­ша­дью финиша, за­пи­сы­вая ее номер с ис­поль­зо­ва­ни­ем минимально воз­мож­но­го количества бит, одина­кового для каж­дой лошади. Каков ин­фор­ма­ци­он­ный объем сообще­ния, за­пи­сан­но­го устройством, если до фи­ни­ша добрались толь­ко 15 из 20 участ­во­вав­ших в скач­ках лошадей? (Ответ дайте в битах.)

Это подобная задача, алгоритм почти тот же.

N = 20 (т.к. всего лошадей 20), i = 5 бит на одну лошадь, т.к. 24= 16 – мало, К = 15, т.к. из 20 только 15 добрались до финиша. I = 15*5 = 45 бит на 15 лошадей

Ответ: 45 бит

3. В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти?

Задача на содержательный подход. Алгоритм решения:

1) Находим какую часть от 32 составляет 4 клубка: 4 шара – 1/8 от 32

2) Если 1/8 часть – то частей всего – 8, т.е. количество вариантов – 8, иными словами N=8

3) N=8, значит i = 3 бита

Ответ: 3 бита

4. В корзине лежат 32 шаров. Сообщение о том, что из корзины достали красный шар содержит 3 бита. Сколько красных шаров?

Это обратная задача. Алгоритм:

1) i = 3 бита, значит N = 8, т.е. 1/8 от всех шаров

2) Всего шаров 32. 1/8 от 32 – 4 шара красных.

(находим сколько частей, находим какая это часть от всего количества, находим количество)

Ответ: 4 шара