Если нам нужно закодировать сообщение, написанное в алфавите мощностью M, при помощи компьютерных кодов, т.е. в алфавите мощностью 2, то для кодирования всех символов исходного алфавита нам нужно под каждый символ выделить такое количество бит K, что M <= 2K.
Тогда информационный объем сообщения I, содержащего N символов, будет равен: I = K * N
I = log2M * N (формула Хартли).
Если log2M не является целым числом, округляем значение в большую сторону.
Пример 1.
В велокроссе участвуют 28 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда все спортсмены прошли промежуточный финиш?
1) 21 байт
2) 140 бит
3) 28 бит
4) 28 байт
Решение:
По формуле Хартли объем сообщения I, написанного в исходном алфавите мощности M, содержащего N символов, будет равен: I = log2M * N.
Если log2M не является целым числом, округляем значение в большую сторону.
В нашем случае мощность алфавита (все символы, подлежащие кодированию) M = 28. N тоже = 28, т.к. все спортсмены прошли финиш.
Тогда I = log228 * 28 ≈ 5 * 28 = 140 бит.
Ответ: 2
Пример 2.
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 400 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
Решение:
Раз для хранения сведений о 20 пользователях потребовалось 400 байт, то для хранения сведений об 1 пользователе нужно 20 байт.
Для хранения пароля, по формуле Хартли, необходимо log2M * N = log212 * 15 ≈ 4 * 15 = 60 бит. Но под пароль отведено минимально возможное целое количество байт, значит под пароль отведено 60/8 ≈ 8 байт (округляем в большую сторону, иначе не получится записать пароль). Значит, для хранения дополнительных сведений остается 20 – 8 = 12 байт.
Ответ: 12
Пример 3.
При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 8 символов, первый и последний из которых — одна из 18 букв, а остальные — цифры (допускается использование 10 десятичных цифр). Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит).
Определите объём памяти, отводимый этой программой для записи 500 паролей.
1) 1500 байт
2) 2000 байт
3) 2500 байт
4) 3000 байт
Решение:
Рассмотрим отдельно буквенную и цифровую часть идентификатора.
Для записи каждой из 18 букв необходимо log218 ≈ 5 бит.
Для записи каждой из 10 цифр необходимо log210 ≈ 4 бит.
Для хранения всех 8 символов идентификатора нужно 5·2 + 4·6 = 34 бита, а т. к. для записи используется целое число байт, то 34/8 округляем в большую сторону. Получаем 5 байт.
Тогда для 500 паролей отводится 5·500 = 2500 байт.
Правильный ответ указан под номером 3.
Ответ:3